1/* ===-- clzdi2.c - Implement __clzdi2 -------------------------------------===
2 *
3 *               The LLVM Compiler Infrastructure
4 *
5 * This file is dual licensed under the MIT and the University of Illinois Open
6 * Source Licenses. See LICENSE.TXT for details.
7 *
8 * ===----------------------------------------------------------------------===
9 *
10 * This file implements count leading zeros for 64bit arguments.
11 *
12 * ===----------------------------------------------------------------------===
13 */
14#include "../assembly.h"
15
16	.syntax unified
17	.text
18#if __ARM_ARCH_ISA_THUMB == 2
19	.thumb
20#endif
21
22
23	.p2align	2
24#if __ARM_ARCH_ISA_THUMB == 2
25DEFINE_COMPILERRT_THUMB_FUNCTION(__clzdi2)
26#else
27DEFINE_COMPILERRT_FUNCTION(__clzdi2)
28#endif
29#ifdef __ARM_FEATURE_CLZ
30#ifdef __ARMEB__
31	cmp	r0, 0
32	itee ne
33	clzne	r0, r0
34	clzeq	r0, r1
35	addeq	r0, r0, 32
36#else
37	cmp	r1, 0
38	itee ne
39	clzne	r0, r1
40	clzeq	r0, r0
41	addeq	r0, r0, 32
42#endif
43	JMP(lr)
44#else
45	/* Assumption: n != 0 */
46
47	/*
48	 * r0: n
49	 * r1: upper half of n, overwritten after check
50	 * r1: count of leading zeros in n + 1
51	 * r2: scratch register for shifted r0
52	 */
53#ifdef __ARMEB__
54	cmp	r0, 0
55	moveq	r0, r1
56#else
57	cmp	r1, 0
58	movne	r0, r1
59#endif
60	movne	r1, 1
61	moveq	r1, 33
62
63	/*
64	 * Basic block:
65	 * if ((r0 >> SHIFT) == 0)
66	 *   r1 += SHIFT;
67	 * else
68	 *   r0 >>= SHIFT;
69	 * for descending powers of two as SHIFT.
70	 */
71#define BLOCK(shift) \
72	lsrs	r2, r0, shift; \
73	movne	r0, r2; \
74	addeq	r1, shift \
75
76	BLOCK(16)
77	BLOCK(8)
78	BLOCK(4)
79	BLOCK(2)
80
81	/*
82	 * The basic block invariants at this point are (r0 >> 2) == 0 and
83	 * r0 != 0. This means 1 <= r0 <= 3 and 0 <= (r0 >> 1) <= 1.
84	 *
85	 * r0 | (r0 >> 1) == 0 | (r0 >> 1) == 1 | -(r0 >> 1) | 1 - (r0 >> 1)
86	 * ---+----------------+----------------+------------+--------------
87	 * 1  | 1              | 0              | 0          | 1
88	 * 2  | 0              | 1              | -1         | 0
89	 * 3  | 0              | 1              | -1         | 0
90	 *
91	 * The r1's initial value of 1 compensates for the 1 here.
92	 */
93	sub	r0, r1, r0, lsr #1
94
95	JMP(lr)
96#endif // __ARM_FEATURE_CLZ
97END_COMPILERRT_FUNCTION(__clzdi2)
98