Revert "Revert "ART: DCHECK zero case for CLZ/CTZ""

This reverts commit 4318d91ea4be673d4deba39d33ac4718d77986a7.

Fix up the lit=-1 case in the arm32 Quick backend; add test case.

Change-Id: I8d0861133db950090ee959f532ede1448683dfa9

4 files changed, 42 insertions, 17 deletions

diff --git a/compiler/dex/quick/arm/int_arm.cc b/compiler/dex/quick/arm/int_arm.cc
index cf0188456d..db76cc6f53 100644
--- a/compiler/dex/quick/arm/int_arm.cc
+++ b/compiler/dex/quick/arm/int_arm.cc
@@ -593,13 +593,20 @@ bool ArmMir2Lir::GetEasyMultiplyOp(int lit, ArmMir2Lir::EasyMultiplyOp* op) {
     return true;
   }
 
+  // At this point lit != 1 (which is a power of two).
+  DCHECK_NE(lit, 1);
   if (IsPowerOfTwo(lit - 1)) {
     op->op = kOpAdd;
     op->shift = CTZ(lit - 1);
     return true;
   }
 
-  if (IsPowerOfTwo(lit + 1)) {
+  if (lit == -1) {
+    // Can be created as neg.
+    op->op = kOpNeg;
+    op->shift = 0;
+    return true;
+  } else if (IsPowerOfTwo(lit + 1)) {
     op->op = kOpRsub;
     op->shift = CTZ(lit + 1);
     return true;
@@ -612,21 +619,26 @@ bool ArmMir2Lir::GetEasyMultiplyOp(int lit, ArmMir2Lir::EasyMultiplyOp* op) {
 
 // Try to convert *lit to 1~2 RegRegRegShift/RegRegShift forms.
 bool ArmMir2Lir::GetEasyMultiplyTwoOps(int lit, EasyMultiplyOp* ops) {
+  DCHECK_NE(lit, 1);           // A case of "1" should have been folded.
+  DCHECK_NE(lit, -1);          // A case of "-1" should have been folded.
   if (GetEasyMultiplyOp(lit, &ops[0])) {
     ops[1].op = kOpInvalid;
     ops[1].shift = 0;
     return true;
   }
 
-  int lit1 = lit;
-  uint32_t shift = CTZ(lit1);
+  DCHECK_NE(lit, 0);           // Should be handled above.
+  DCHECK(!IsPowerOfTwo(lit));  // Same.
+
+  int lit1 = lit;              // With the DCHECKs, it's clear we don't get "0", "1" or "-1" for
+  uint32_t shift = CTZ(lit1);  // lit1.
   if (GetEasyMultiplyOp(lit1 >> shift, &ops[0])) {
     ops[1].op = kOpLsl;
     ops[1].shift = shift;
     return true;
   }
 
-  lit1 = lit - 1;
+  lit1 = lit - 1;              // With the DCHECKs, it's clear we don't get "0" or "1" for lit1.
   shift = CTZ(lit1);
   if (GetEasyMultiplyOp(lit1 >> shift, &ops[0])) {
     ops[1].op = kOpAdd;
@@ -634,7 +646,7 @@ bool ArmMir2Lir::GetEasyMultiplyTwoOps(int lit, EasyMultiplyOp* ops) {
     return true;
   }
 
-  lit1 = lit + 1;
+  lit1 = lit + 1;              // With the DCHECKs, it's clear we don't get "0" here.
   shift = CTZ(lit1);
   if (GetEasyMultiplyOp(lit1 >> shift, &ops[0])) {
     ops[1].op = kOpRsub;
@@ -652,7 +664,7 @@ bool ArmMir2Lir::GetEasyMultiplyTwoOps(int lit, EasyMultiplyOp* ops) {
 // Additional temporary register is required,
 // if it need to generate 2 instructions and src/dest overlap.
 void ArmMir2Lir::GenEasyMultiplyTwoOps(RegStorage r_dest, RegStorage r_src, EasyMultiplyOp* ops) {
-  // tmp1 = ( src << shift1) + [ src | -src | 0 ]
+  // tmp1 = (( src << shift1) + [ src | -src | 0 ] ) | -src
   // dest = (tmp1 << shift2) + [ src | -src | 0 ]
 
   RegStorage r_tmp1;
@@ -674,6 +686,9 @@ void ArmMir2Lir::GenEasyMultiplyTwoOps(RegStorage r_dest, RegStorage r_src, Easy
     case kOpRsub:
       OpRegRegRegShift(kOpRsub, r_tmp1, r_src, r_src, EncodeShift(kArmLsl, ops[0].shift));
       break;
+    case kOpNeg:
+      OpRegReg(kOpNeg, r_tmp1, r_src);
+      break;
     default:
       DCHECK_EQ(ops[0].op, kOpInvalid);
       break;
@@ -691,6 +706,7 @@ void ArmMir2Lir::GenEasyMultiplyTwoOps(RegStorage r_dest, RegStorage r_src, Easy
     case kOpRsub:
       OpRegRegRegShift(kOpRsub, r_dest, r_src, r_tmp1, EncodeShift(kArmLsl, ops[1].shift));
       break;
+    // No negation allowed in second op.
     default:
       LOG(FATAL) << "Unexpected opcode passed to GenEasyMultiplyTwoOps";
       break;
diff --git a/runtime/base/bit_utils.h b/runtime/base/bit_utils.h
index 1da6750b45..1b0d774419 100644
--- a/runtime/base/bit_utils.h
+++ b/runtime/base/bit_utils.h
@@ -29,21 +29,28 @@ namespace art {
 template<typename T>
 static constexpr int CLZ(T x) {
   static_assert(std::is_integral<T>::value, "T must be integral");
-  // TODO: assert unsigned. There is currently many uses with signed values.
+  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
   static_assert(sizeof(T) <= sizeof(long long),  // NOLINT [runtime/int] [4]
                 "T too large, must be smaller than long long");
-  return (sizeof(T) == sizeof(uint32_t))
-      ? __builtin_clz(x)  // TODO: __builtin_clz[ll] has undefined behavior for x=0
-      : __builtin_clzll(x);
+  return
+      DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0))
+      (sizeof(T) == sizeof(uint32_t))
+          ? __builtin_clz(x)
+          : __builtin_clzll(x);
 }
 
 template<typename T>
 static constexpr int CTZ(T x) {
   static_assert(std::is_integral<T>::value, "T must be integral");
-  // TODO: assert unsigned. There is currently many uses with signed values.
-  return (sizeof(T) == sizeof(uint32_t))
-      ? __builtin_ctz(x)
-      : __builtin_ctzll(x);
+  // It is not unreasonable to ask for trailing zeros in a negative number. As such, do not check
+  // that T is an unsigned type.
+  static_assert(sizeof(T) <= sizeof(long long),  // NOLINT [runtime/int] [4]
+                "T too large, must be smaller than long long");
+  return
+      DCHECK_CONSTEXPR(x != 0, "x must not be zero", T(0))
+      (sizeof(T) == sizeof(uint32_t))
+          ? __builtin_ctz(x)
+          : __builtin_ctzll(x);
 }
 
 template<typename T>
diff --git a/runtime/leb128.h b/runtime/leb128.h
index 14683d4063..976936d639 100644
--- a/runtime/leb128.h
+++ b/runtime/leb128.h
@@ -101,7 +101,7 @@ static inline int32_t DecodeSignedLeb128(const uint8_t** data) {
 static inline uint32_t UnsignedLeb128Size(uint32_t data) {
   // bits_to_encode = (data != 0) ? 32 - CLZ(x) : 1  // 32 - CLZ(data | 1)
   // bytes = ceil(bits_to_encode / 7.0);             // (6 + bits_to_encode) / 7
-  uint32_t x = 6 + 32 - CLZ(data | 1);
+  uint32_t x = 6 + 32 - CLZ(data | 1U);
   // Division by 7 is done by (x * 37) >> 8 where 37 = ceil(256 / 7).
   // This works for 0 <= x < 256 / (7 * 37 - 256), i.e. 0 <= x <= 85.
   return (x * 37) >> 8;
@@ -111,7 +111,7 @@ static inline uint32_t UnsignedLeb128Size(uint32_t data) {
 static inline uint32_t SignedLeb128Size(int32_t data) {
   // Like UnsignedLeb128Size(), but we need one bit beyond the highest bit that differs from sign.
   data = data ^ (data >> 31);
-  uint32_t x = 1 /* we need to encode the sign bit */ + 6 + 32 - CLZ(data | 1);
+  uint32_t x = 1 /* we need to encode the sign bit */ + 6 + 32 - CLZ(data | 1U);
   return (x * 37) >> 8;
 }
 
diff --git a/test/107-int-math2/src/Main.java b/test/107-int-math2/src/Main.java
index 6a6227cee5..0c91d4438d 100644
--- a/test/107-int-math2/src/Main.java
+++ b/test/107-int-math2/src/Main.java
@@ -412,7 +412,7 @@ class Main extends IntMathBase {
      */
     static int lit8Test(int x) {
 
-        int[] results = new int[8];
+        int[] results = new int[9];
 
         /* try to generate op-int/lit8" instructions */
         results[0] = x + 10;
@@ -423,6 +423,7 @@ class Main extends IntMathBase {
         results[5] = x & 10;
         results[6] = x | -10;
         results[7] = x ^ -10;
+        results[8] = x * -256;
         int minInt = -2147483648;
         int result = minInt / -1;
         if (result != minInt) {return 1; }
@@ -434,6 +435,7 @@ class Main extends IntMathBase {
         if (results[5] != 8) {return 7; }
         if (results[6] != -1) {return 8; }
         if (results[7] != 55563) {return 9; }
+        if (results[8] != 14222080) {return 10; }
         return 0;
     }