Add CLZ builtins for ARM and IA32

ARM: add __builtin_clzl, __builtin_clzll
IA32: add __builtin_clzl, __builtin_clzll,
          __builtin_ctzl, __builtin_ctzll
Add corresponding tests in tests/regression/

10 files changed, 68 insertions, 7 deletions

diff --git a/arm/Asmexpand.ml b/arm/Asmexpand.ml
index 2b19cbe8..65bb19ee 100644
--- a/arm/Asmexpand.ml
+++ b/arm/Asmexpand.ml
@@ -287,8 +287,14 @@ let expand_builtin_inline name args res =
      emit (Prev (res, a1))
   | "__builtin_bswap16", [BA(IR a1)], BR(IR res) ->
      emit (Prev16 (res, a1))
-  | "__builtin_clz", [BA(IR a1)], BR(IR res) ->
+  | ("__builtin_clz" | "__builtin_clzl"), [BA(IR a1)], BR(IR res) ->
      emit (Pclz (res, a1))
+  | "__builtin_clzll", [BA_splitlong(BA (IR ah), BA (IR al))], BR(IR res) ->
+     emit (Pclz (IR14, al));
+     emit (Pcmp (ah, SOimm _0));
+     emit (Pmovite (TCeq, IR14, SOimm _0, SOreg IR14));
+     emit (Pclz (res, ah));
+     emit (Padd (res, res, SOreg IR14))
   (* Float arithmetic *)
   | "__builtin_fabs",  [BA(FR a1)], BR(FR res) ->
      emit (Pfabsd (res,a1))
diff --git a/arm/CBuiltins.ml b/arm/CBuiltins.ml
index 6751074c..1b06b93b 100644
--- a/arm/CBuiltins.ml
+++ b/arm/CBuiltins.ml
@@ -31,6 +31,10 @@ let builtins = {
       (TInt(IUShort, []), [TInt(IUShort, [])], false);
     "__builtin_clz",
       (TInt(IInt, []), [TInt(IUInt, [])], false);
+    "__builtin_clzl",
+      (TInt(IInt, []), [TInt(IULong, [])], false);
+    "__builtin_clzll",
+      (TInt(IInt, []), [TInt(IULongLong, [])], false);
     (* Float arithmetic *)
     "__builtin_fsqrt",
       (TFloat(FDouble, []), [TFloat(FDouble, [])], false);
diff --git a/ia32/Asmexpand.ml b/ia32/Asmexpand.ml
index d7b554dc..7ca31902 100644
--- a/ia32/Asmexpand.ml
+++ b/ia32/Asmexpand.ml
@@ -245,11 +245,34 @@ let expand_builtin_inline name args res =
      if a1 <> res then
        emit (Pmov_rr (res,a1));
      emit (Pbswap16 res)
-  | "__builtin_clz", [BA(IR a1)], BR(IR res) ->
+  | ("__builtin_clz"|"__builtin_clzl"), [BA(IR a1)], BR(IR res) ->
      emit (Pbsr (res,a1));
      emit (Pxor_ri(res,coqint_of_camlint 31l))
-  | "__builtin_ctz", [BA(IR a1)], BR(IR res) ->
+  | "__builtin_clzll", [BA_splitlong(BA (IR ah), BA (IR al))], BR(IR res) ->
+     let lbl1 = new_label() in
+     let lbl2 = new_label() in
+     emit (Ptest_rr(ah, ah));
+     emit (Pjcc(Cond_e, lbl1));
+     emit (Pbsr(res, ah));
+     emit (Pxor_ri(res, coqint_of_camlint 31l));
+     emit (Pjmp_l lbl2);
+     emit (Plabel lbl1);
+     emit (Pbsr(res, al));
+     emit (Pxor_ri(res, coqint_of_camlint 63l));
+     emit (Plabel lbl2)
+  | ("__builtin_ctz" | "__builtin_ctzl"), [BA(IR a1)], BR(IR res) ->
      emit (Pbsf (res,a1))
+  | "__builtin_ctzll", [BA_splitlong(BA (IR ah), BA (IR al))], BR(IR res) ->
+     let lbl1 = new_label() in
+     let lbl2 = new_label() in
+     emit (Ptest_rr(al, al));
+     emit (Pjcc(Cond_e, lbl1));
+     emit (Pbsf(res, al));
+     emit (Pjmp_l lbl2);
+     emit (Plabel lbl1);
+     emit (Pbsf(res, ah));
+     emit (Padd_ri(res, coqint_of_camlint 32l));
+     emit (Plabel lbl2)
   (* Float arithmetic *)
   | "__builtin_fabs", [BA(FR a1)], BR(FR res) ->
      if a1 <> res then
diff --git a/ia32/CBuiltins.ml b/ia32/CBuiltins.ml
index 802588d4..79a839f3 100644
--- a/ia32/CBuiltins.ml
+++ b/ia32/CBuiltins.ml
@@ -31,8 +31,16 @@ let builtins = {
       (TInt(IUShort, []), [TInt(IUShort, [])], false);
     "__builtin_clz",
       (TInt(IInt, []), [TInt(IUInt, [])], false);
+    "__builtin_clzl",
+      (TInt(IInt, []), [TInt(IULong, [])], false);
+    "__builtin_clzll",
+      (TInt(IInt, []), [TInt(IULongLong, [])], false);
     "__builtin_ctz",
       (TInt(IInt, []), [TInt(IUInt, [])], false);
+    "__builtin_ctzl",
+      (TInt(IInt, []), [TInt(IULong, [])], false);
+    "__builtin_ctzll",
+      (TInt(IInt, []), [TInt(IULongLong, [])], false);
     (* Float arithmetic *)
     "__builtin_fsqrt",
       (TFloat(FDouble, []), [TFloat(FDouble, [])], false);
diff --git a/test/regression/Results/builtins-arm b/test/regression/Results/builtins-arm
index 4db7c32a..40cb6048 100644
--- a/test/regression/Results/builtins-arm
+++ b/test/regression/Results/builtins-arm
@@ -1,6 +1,8 @@
 bswap(12345678) = 78563412
 bswap16(1234) = 3412
-cntlz(12345678) = 3
+clz(12345678) = 3
+clzll(12345678) = 35
+clzll(1234567812345678) = 3
 fsqrt(3.141590) = 1.772453
 read_16_rev = 3412
 read_32_rev = efbeadde
diff --git a/test/regression/Results/builtins-ia32 b/test/regression/Results/builtins-ia32
index 3f9a9178..a7669f14 100644
--- a/test/regression/Results/builtins-ia32
+++ b/test/regression/Results/builtins-ia32
@@ -1,7 +1,11 @@
 bswap(12345678) = 78563412
 bswap16(1234) = 3412
 clz(12345678) = 3
+clzll(12345678) = 35
+clzll(1234567812345678) = 3
 ctz(1234) = 2
+ctzll(1234567812345678) = 3
+ctzll(1234567800000000) = 35
 fsqrt(3.141590) = 1.772453
 fmin(3.141590, 2.718000) = 2.718000
 fmax(3.141590, 2.718000) = 3.141590
diff --git a/test/regression/Results/builtins-powerpc b/test/regression/Results/builtins-powerpc
index b131e543..bb4edf3a 100644
--- a/test/regression/Results/builtins-powerpc
+++ b/test/regression/Results/builtins-powerpc
@@ -1,6 +1,8 @@
 mulhw(12345678, deadbeef) = fda16776
 mulhwu(12345678, deadbeef) = fd5bdee
-cntlz(12345678) = 3
+clz(12345678) = 3
+clzll(12345678) = 35
+clzll(1234567812345678) = 3
 bswap(12345678) = 78563412
 bswap16(1234) = 3412
 fmadd(3.141590, 2.718000, 1.414000) = 9.952842
diff --git a/test/regression/builtins-arm.c b/test/regression/builtins-arm.c
index 643c8f1a..5fa867c2 100644
--- a/test/regression/builtins-arm.c
+++ b/test/regression/builtins-arm.c
@@ -6,12 +6,15 @@ int main(int argc, char ** argv)
 {
   unsigned int x = 0x12345678;
   unsigned int y = 0xDEADBEEF;
+  unsigned long long xx = 0x1234567812345678ULL;
   double a = 3.14159;
   unsigned short s = 0x1234;
 
   printf("bswap(%x) = %x\n", x, __builtin_bswap(x));
   printf("bswap16(%x) = %x\n", s, __builtin_bswap16(s));
-  printf("cntlz(%x) = %d\n", x, __builtin_clz(x));
+  printf("clz(%x) = %d\n", x, __builtin_clz(x));
+  printf("clzll(%llx) = %d\n", (unsigned long long) x, __builtin_clzll(x));
+  printf("clzll(%llx) = %d\n", xx, __builtin_clzll(xx));
   printf("fsqrt(%f) = %f\n", a, __builtin_fsqrt(a));
   
   printf ("read_16_rev = %x\n", __builtin_read16_reversed(&s));
diff --git a/test/regression/builtins-ia32.c b/test/regression/builtins-ia32.c
index 558c3153..8df81800 100644
--- a/test/regression/builtins-ia32.c
+++ b/test/regression/builtins-ia32.c
@@ -6,6 +6,8 @@ int main(int argc, char ** argv)
 {
   unsigned int x = 0x12345678;
   unsigned int y = 0xDEADBEEF;
+  unsigned long long xx = 0x1234567812345678ULL;
+  unsigned long long yy = 0x1234567800000000ULL;
   double a = 3.14159;
   double b = 2.718;
   double c = 1.414;
@@ -14,7 +16,11 @@ int main(int argc, char ** argv)
   printf("bswap(%x) = %x\n", x, __builtin_bswap(x));
   printf("bswap16(%x) = %x\n", s, __builtin_bswap16(s));
   printf("clz(%x) = %d\n", x, __builtin_clz(x));
+  printf("clzll(%llx) = %d\n", (unsigned long long) x, __builtin_clzll(x));
+  printf("clzll(%llx) = %d\n", xx, __builtin_clzll(xx));
   printf("ctz(%x) = %d\n", s, __builtin_ctz(s));
+  printf("ctzll(%llx) = %d\n", xx, __builtin_ctzll(xx));
+  printf("ctzll(%llx) = %d\n", yy, __builtin_ctzll(yy));
 
   printf("fsqrt(%f) = %f\n", a, __builtin_fsqrt(a));
   printf("fmin(%f, %f) = %f\n", a, b, __builtin_fmin(a, b));
diff --git a/test/regression/builtins-powerpc.c b/test/regression/builtins-powerpc.c
index 5cb2e293..1d220c11 100644
--- a/test/regression/builtins-powerpc.c
+++ b/test/regression/builtins-powerpc.c
@@ -13,6 +13,7 @@ int main(int argc, char ** argv)
 {
   unsigned int x = 0x12345678;
   unsigned int y = 0xDEADBEEF;
+  unsigned long long xx = 0x1234567812345678ULL;
   double a = 3.14159;
   double b = 2.718;
   double c = 1.414;
@@ -20,7 +21,9 @@ int main(int argc, char ** argv)
 
   printf("mulhw(%x, %x) = %x\n", x, y, __builtin_mulhw(x, y));
   printf("mulhwu(%x, %x) = %x\n", x, y, __builtin_mulhwu(x, y));
-  printf("cntlz(%x) = %d\n", x, __builtin_clz(x));
+  printf("clz(%x) = %d\n", x, __builtin_clz(x));
+  printf("clzll(%llx) = %d\n", (unsigned long long) x, __builtin_clzll(x));
+  printf("clzll(%llx) = %d\n", xx, __builtin_clzll(xx));
   printf("bswap(%x) = %x\n", x, __builtin_bswap(x));
   printf("bswap16(%x) = %x\n", s, __builtin_bswap16(s));