12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines/* ===-- clzdi2.c - Implement __clzdi2 -------------------------------------===
22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *
32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *               The LLVM Compiler Infrastructure
42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *
52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines * This file is dual licensed under the MIT and the University of Illinois Open
62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines * Source Licenses. See LICENSE.TXT for details.
72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *
82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines * ===----------------------------------------------------------------------===
92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *
102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines * This file implements count leading zeros for 64bit arguments.
112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines *
122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines * ===----------------------------------------------------------------------===
132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines */
142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "../assembly.h"
152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines
162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	.syntax unified
172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	.text
185d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines#if __ARM_ARCH_ISA_THUMB == 2
195d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines	.thumb
205d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines#endif
215d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines
225d71de26cedae3dafc17449fe0182045c0bd20e8Stephen Hines
232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	.p2align	2
242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesDEFINE_COMPILERRT_FUNCTION(__clzdi2)
252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifdef __ARM_FEATURE_CLZ
262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifdef __ARMEB__
272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	cmp	r0, 0
282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	itee ne
292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	clzne	r0, r0
302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	clzeq	r0, r1
312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	addeq	r0, r0, 32
322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#else
332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	cmp	r1, 0
342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	itee ne
352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	clzne	r0, r1
362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	clzeq	r0, r0
372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	addeq	r0, r0, 32
382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif
392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	JMP(lr)
402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#else
412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	/* Assumption: n != 0 */
422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines
432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	/*
442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * r0: n
452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * r1: upper half of n, overwritten after check
462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * r1: count of leading zeros in n + 1
472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * r2: scratch register for shifted r0
482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 */
492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifdef __ARMEB__
502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	cmp	r0, 0
512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	moveq	r0, r1
522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#else
532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	cmp	r1, 0
542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	movne	r0, r1
552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif
562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	movne	r1, 1
572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	moveq	r1, 33
582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines
592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	/*
602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * Basic block:
612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * if ((r0 >> SHIFT) == 0)
622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 *   r1 += SHIFT;
632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * else
642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 *   r0 >>= SHIFT;
652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * for descending powers of two as SHIFT.
662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 */
672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define BLOCK(shift) \
682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	lsrs	r2, r0, shift; \
692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	movne	r0, r2; \
702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	addeq	r1, shift \
712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines
722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	BLOCK(16)
732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	BLOCK(8)
742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	BLOCK(4)
752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	BLOCK(2)
762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines
772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	/*
782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * The basic block invariants at this point are (r0 >> 2) == 0 and
792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * r0 != 0. This means 1 <= r0 <= 3 and 0 <= (r0 >> 1) <= 1.
802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 *
812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * r0 | (r0 >> 1) == 0 | (r0 >> 1) == 1 | -(r0 >> 1) | 1 - (r0 >> 1)
822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * ---+----------------+----------------+------------+--------------
832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * 1  | 1              | 0              | 0          | 1
842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * 2  | 0              | 1              | -1         | 0
852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * 3  | 0              | 1              | -1         | 0
862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 *
872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 * The r1's initial value of 1 compensates for the 1 here.
882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	 */
892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	sub	r0, r1, r0, lsr #1
902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines
912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines	JMP(lr)
922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif // __ARM_FEATURE_CLZ
932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesEND_COMPILERRT_FUNCTION(__clzdi2)
94