| Stephen Hines | 2d1fdb2 | 2014-05-28 23:58:16 -0700 | [diff] [blame^] | 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 | |
| 18 | .text |
| 19 | .p2align 2 |
| 20 | DEFINE_COMPILERRT_FUNCTION(__clzdi2) |
| 21 | #ifdef __ARM_FEATURE_CLZ |
| 22 | #ifdef __ARMEB__ |
| 23 | cmp r0, 0 |
| 24 | itee ne |
| 25 | clzne r0, r0 |
| 26 | clzeq r0, r1 |
| 27 | addeq r0, r0, 32 |
| 28 | #else |
| 29 | cmp r1, 0 |
| 30 | itee ne |
| 31 | clzne r0, r1 |
| 32 | clzeq r0, r0 |
| 33 | addeq r0, r0, 32 |
| 34 | #endif |
| 35 | JMP(lr) |
| 36 | #else |
| 37 | /* Assumption: n != 0 */ |
| 38 | |
| 39 | /* |
| 40 | * r0: n |
| 41 | * r1: upper half of n, overwritten after check |
| 42 | * r1: count of leading zeros in n + 1 |
| 43 | * r2: scratch register for shifted r0 |
| 44 | */ |
| 45 | #ifdef __ARMEB__ |
| 46 | cmp r0, 0 |
| 47 | moveq r0, r1 |
| 48 | #else |
| 49 | cmp r1, 0 |
| 50 | movne r0, r1 |
| 51 | #endif |
| 52 | movne r1, 1 |
| 53 | moveq r1, 33 |
| 54 | |
| 55 | /* |
| 56 | * Basic block: |
| 57 | * if ((r0 >> SHIFT) == 0) |
| 58 | * r1 += SHIFT; |
| 59 | * else |
| 60 | * r0 >>= SHIFT; |
| 61 | * for descending powers of two as SHIFT. |
| 62 | */ |
| 63 | #define BLOCK(shift) \ |
| 64 | lsrs r2, r0, shift; \ |
| 65 | movne r0, r2; \ |
| 66 | addeq r1, shift \ |
| 67 | |
| 68 | BLOCK(16) |
| 69 | BLOCK(8) |
| 70 | BLOCK(4) |
| 71 | BLOCK(2) |
| 72 | |
| 73 | /* |
| 74 | * The basic block invariants at this point are (r0 >> 2) == 0 and |
| 75 | * r0 != 0. This means 1 <= r0 <= 3 and 0 <= (r0 >> 1) <= 1. |
| 76 | * |
| 77 | * r0 | (r0 >> 1) == 0 | (r0 >> 1) == 1 | -(r0 >> 1) | 1 - (r0 >> 1) |
| 78 | * ---+----------------+----------------+------------+-------------- |
| 79 | * 1 | 1 | 0 | 0 | 1 |
| 80 | * 2 | 0 | 1 | -1 | 0 |
| 81 | * 3 | 0 | 1 | -1 | 0 |
| 82 | * |
| 83 | * The r1's initial value of 1 compensates for the 1 here. |
| 84 | */ |
| 85 | sub r0, r1, r0, lsr #1 |
| 86 | |
| 87 | JMP(lr) |
| 88 | #endif // __ARM_FEATURE_CLZ |
| 89 | END_COMPILERRT_FUNCTION(__clzdi2) |