Implement __clzdi2 and __clzsi2 for early ARM architectures that lack the clz instruction

[joerg]

Summary

Implement clzdi2 and clzsi2 for early ARM architectures that lack the clz instruction. For __clzdi2 special care is needed for dealing with Little Endian vs Big Endian.

[joerg]

Better thumb encoding.

[compnerd]

lib/arm/clzdi2.S

36 ↗

(On Diff #6688)

Should this bx also be handled similarly for uniformity? clz being present is indicative of ARMv5T+ so bx is obviously available, but, the uniformity might be nice (since the cost is 0).

38 ↗

(On Diff #6688)

I dont see how this assumption holds.

64 ↗

(On Diff #6688)

I believe that the IMM prefix unnecessary in unified syntax.

66 ↗

(On Diff #6688)

Can you change the name of block to upper case to indicate that it is a macro?

[joerg]

lib/arm/clzdi2.S

38 ↗

(On Diff #6688)

It is part of the interface contract:

• Built-in Function: int __builtin_clz (unsigned int x) Returns the number of leading 0-bits in X, starting at the most significant bit position. If X is 0, the result is undefined.

[joerg]

Clean up.

[joerg]

Closed by commit rL200394 (authored by @joerg).

compiler-rt/trunk/lib/arm/clzdi2.S

+/* ===-- clzdi2.c - Implement __clzdi2 -------------------------------------===
+ *
+ *               The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file implements count leading zeros for 64bit arguments.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+#include "../assembly.h"
+
+#ifdef ARM_HAS_BX
+#define JMP(r)  bx  r
+#else
+#define JMP(r)  mov pc, r
+#endif
+
+  .syntax unified
+
+  .text
+  .align  2
+DEFINE_COMPILERRT_FUNCTION(__clzdi2)
+#ifdef __ARM_FEATURE_CLZ
+#ifdef __ARMEB__
+  cmp r0, 0
+  itee ne
+  clzne r0, r0
+  clzeq r0, r1
+  addeq r0, r0, 32
+#else
+  cmp r1, 0
+  itee ne
+  clzne r0, r1
+  clzeq r0, r0
+  addeq r0, r0, 32
+#endif
+  JMP(lr)
+#else
+  /* Assumption: n != 0 */
+
+  /*
+   * r0: n
+   * r1: upper half of n, overwritten after check
+   * r1: count of leading zeros in n + 1
+   * r2: scratch register for shifted r0
+   */
+#ifdef __ARMEB__
+  cmp r0, 0
+  moveq r0, r1
+#else
+  cmp r1, 0
+  movne r0, r1
+#endif
+  movne r1, 1
+  moveq r1, 33
+
+  /*
+   * Basic block:
+   * if ((r0 >> SHIFT) == 0)
+   *   r1 += SHIFT;
+   * else
+   *   r0 >>= SHIFT;
+   * for descending powers of two as SHIFT.
+   */
+#define BLOCK(shift) \
+  lsrs  r2, r0, shift; \
+  movne r0, r2; \
+  addeq r1, shift \
+
+  BLOCK(16)
+  BLOCK(8)
+  BLOCK(4)
+  BLOCK(2)
+
+  /*
+   * The basic block invariants at this point are (r0 >> 2) == 0 and
+   * r0 != 0. This means 1 <= r0 <= 3 and 0 <= (r0 >> 1) <= 1.
+   *
+   * r0 | (r0 >> 1) == 0 | (r0 >> 1) == 1 | -(r0 >> 1) | 1 - (r0 >> 1)
+   * ---+----------------+----------------+------------+--------------
+   * 1  | 1              | 0              | 0          | 1
+   * 2  | 0              | 1              | -1         | 0
+   * 3  | 0              | 1              | -1         | 0
+   *
+   * The r1's initial value of 1 compensates for the 1 here.
+   */
+  sub r0, r1, r0, lsr #1
+
+  JMP(lr)
+#endif // __ARM_FEATURE_CLZ
+END_COMPILERRT_FUNCTION(__clzdi2)

compiler-rt/trunk/lib/arm/clzsi2.S

+/* ===-- clzsi2.c - Implement __clzsi2 -------------------------------------===
+ *
+ *               The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * This file implements count leading zeros for 32bit arguments.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+#include "../assembly.h"
+
+#ifdef ARM_HAS_BX
+#define JMP(r)  bx  r
+#else
+#define JMP(r)  mov pc, r
+#endif
+
+  .syntax unified
+
+  .text
+  .align  2
+DEFINE_COMPILERRT_FUNCTION(__clzsi2)
+#ifdef __ARM_FEATURE_CLZ
+  clz r0, r0
+  JMP(lr)
+#else
+  /* Assumption: n != 0 */
+
+  /*
+   * r0: n
+   * r1: count of leading zeros in n + 1
+   * r2: scratch register for shifted r0
+   */
+  mov r1, 1
+
+  /*
+   * Basic block:
+   * if ((r0 >> SHIFT) == 0)
+   *   r1 += SHIFT;
+   * else
+   *   r0 >>= SHIFT;
+   * for descending powers of two as SHIFT.
+   */
+
+#define BLOCK(shift) \
+  lsrs  r2, r0, shift; \
+  movne r0, r2; \
+  addeq r1, shift \
+
+  BLOCK(16)
+  BLOCK(8)
+  BLOCK(4)
+  BLOCK(2)
+
+  /*
+   * The basic block invariants at this point are (r0 >> 2) == 0 and
+   * r0 != 0. This means 1 <= r0 <= 3 and 0 <= (r0 >> 1) <= 1.
+   *
+   * r0 | (r0 >> 1) == 0 | (r0 >> 1) == 1 | -(r0 >> 1) | 1 - (r0 >> 1)
+   * ---+----------------+----------------+------------+--------------
+   * 1  | 1              | 0              | 0          | 1
+   * 2  | 0              | 1              | -1         | 0
+   * 3  | 0              | 1              | -1         | 0
+   *
+   * The r1's initial value of 1 compensates for the 1 here.
+   */
+  sub r0, r1, r0, lsr #1
+
+  JMP(lr)
+#endif // __ARM_FEATURE_CLZ
+END_COMPILERRT_FUNCTION(__clzsi2)