Make processLogicalImmediate in AArch64AddressingModes.h more efficient

[ahatanak]

Summary

Hi Tim,

While I was working on the AArch64 bitmask immediate optimization patch, I noticed the code in processLogicalImmediate, which determines whether an immediate value can be encoded as the immediate operand of a logical instruction, isn't using an efficient algorithm. The attached patch attempts to make it more efficient.

[t.p.northover]

Hi,

I think it'd be good to convert this function to LLVM style (mainly local variables begin with a capital letter) since we're already changing so much of it.

Other than that, a couple of minor nits:

lib/Target/AArch64/MCTargetDesc/AArch64AddressingModes.h

224

This is undefined behaviour if size > 62. I think "(1ULL << size) - 1" is OK.

226

This is an equality comparison: I think "(Imm & Mask) != (Imm >> Size) & Mask" is clearer.

[ahatanak]

Closed by commit rL221204 (authored by @ahatanak).

lib/Target/AArch64/MCTargetDesc/AArch64AddressingModes.h

 /// size.  If so, return true with "encoding" set to the encoded value in
 /// the form N:immr:imms.
 static inline bool processLogicalImmediate(uint64_t imm, unsigned regSize,
                                            uint64_t &encoding) {
   if (imm == 0ULL || imm == ~0ULL ||
       (regSize != 64 && (imm >> regSize != 0 || imm == ~0U)))
     return false;
 
-  unsigned size = 2;
-  uint64_t eltVal = imm;
-
   // First, determine the element size.
-  while (size < regSize) {
-    unsigned numElts = regSize / size;
-    unsigned mask = (1ULL << size) - 1;
-    uint64_t lowestEltVal = imm & mask;
-
-    bool allMatched = true;
-    for (unsigned i = 1; i < numElts; ++i) {
-     uint64_t currEltVal = (imm >> (i*size)) & mask;
-      if (currEltVal != lowestEltVal) {
-        allMatched = false;
-        break;
-      }
-    }
+  unsigned size = regSize;
 
-    if (allMatched) {
-      eltVal = lowestEltVal;
-      break;
-    }
+  do {
+    size /= 2;
+    uint64_t mask = (1LL << size) - 1;
 
+    if (((imm ^ imm >> size) & mask) != 0) {
       size *= 2;
+      break;
     }
+  } while (size > 2);
 
   // Second, determine the rotation to make the element be: 0^m 1^n.
-  for (unsigned i = 0; i < size; ++i) {
-    eltVal = ror(eltVal, size);
-    uint32_t clz = countLeadingZeros(eltVal) - (64 - size);
-    uint32_t cto = CountTrailingOnes_64(eltVal);
-
-    if (clz + cto == size) {
-      // Encode in immr the number of RORs it would take to get *from* this
-      // element value to our target value, where i+1 is the number of RORs
-      // to go the opposite direction.
-      unsigned immr = size - (i + 1);
+  uint32_t cto, i;
+  uint64_t mask = ((uint64_t)-1LL) >> (64 - size);
+  imm &= mask;
+
+  if (isShiftedMask_64(imm)) {
+    i = countTrailingZeros(imm);
+    cto = CountTrailingOnes_64(imm >> i);
+  } else {
+    imm |= ~mask;
+    if (!isShiftedMask_64(~imm))
+      return false;
+
+    unsigned clo = CountLeadingOnes_64(imm);
+    i = 64 - clo;
+    cto = clo + CountTrailingOnes_64(imm) - (64 - size);
+  }
+
+  // Encode in immr the number of RORs it would take to get *from* 0^m 1^n
+  // to our target value, where i is the number of RORs to go the opposite
+  // direction.
+  assert(size > i && "i should be smaller than element size");
+  unsigned immr = (size - i) & (size - 1);
 
-      // If size has a 1 in the n'th bit, create a value that has zeroes in
-      // bits [0, n] and ones above that.
-      uint64_t nimms = ~(size-1) << 1;
 
-      // Or the CTO value into the low bits, which must be below the Nth bit
-      // bit mentioned above.
-      nimms |= (cto-1);
 
-      // Extract the seventh bit and toggle it to create the N field.
-      unsigned N = ((nimms >> 6) & 1) ^ 1;
 
-      encoding = (N << 12) | (immr << 6) | (nimms & 0x3f);
-      return true;
-    }
-  }
-
-  return false;
-}
 
 /// isLogicalImmediate - Return true if the immediate is valid for a logical
 /// immediate instruction of the given register size. Return false otherwise.
 static inline bool isLogicalImmediate(uint64_t imm, unsigned regSize) {
   uint64_t encoding;
   return processLogicalImmediate(imm, regSize, encoding);
 }