Adds logical operations to arm64.

runtime/vm/assembler_arm64.cc

Index: runtime/vm/assembler_arm64.cc
===================================================================
--- runtime/vm/assembler_arm64.cc	(revision 34829)
+++ runtime/vm/assembler_arm64.cc	(working copy)
@@ -73,6 +73,132 @@
   return fpu_reg_names[reg];
 }
 
+
+static int CountLeadingZeros(uint64_t value, int width) {

[regis, 2014/04/09 20:49:49]

Can width be 32 with a value that does not fit in 32 bits?
I not, I would add an assert.
A comment explaining what this function expects and returns would be good.

[zra, 2014/04/09 22:14:28]

Added an ASSERT in IsImmLogical.

+  ASSERT((width == 32) || (width == 64));
+  int count = 0;
+  uint64_t bit_test = 1UL << (width - 1);
+  while ((count < width) && ((bit_test & value) == 0)) {
+    count++;
+    bit_test >>= 1;
+  }
+  return count;
+}

[regis, 2014/04/09 20:49:49]

There are faster ways of doing this.
A much simpler test + loop would work (modulo handling of width):

if (value == 0) return width;
int count = 0;
while (value >>= 1) count++;
return count;

You can even do this without a loop, but it may not be worth it.
Example:
https://github.com/gagern/gnulib/blob/master/lib/count-leading-zeros.h

[zra, 2014/04/09 22:14:28]

Done.

+
+
+static int CountOneBits(uint64_t value, int width) {
+  // Mask out unused bits to ensure that they are not counted.
+  value &= (0xffffffffffffffffUL >> (64-width));
+
+  value = ((value >> 1) & 0x5555555555555555) + (value & 0x5555555555555555);
+  value = ((value >> 2) & 0x3333333333333333) + (value & 0x3333333333333333);
+  value = ((value >> 4) & 0x0f0f0f0f0f0f0f0f) + (value & 0x0f0f0f0f0f0f0f0f);
+  value = ((value >> 8) & 0x00ff00ff00ff00ff) + (value & 0x00ff00ff00ff00ff);
+  value = ((value >> 16) & 0x0000ffff0000ffff) + (value & 0x0000ffff0000ffff);
+  value = ((value >> 32) & 0x00000000ffffffff) + (value & 0x00000000ffffffff);
+
+  return value;
+}
+
+
+// Test if a given value can be encoded in the immediate field of a logical
+// instruction.
+// If it can be encoded, the function returns true, and values pointed to by n,
+// imm_s and imm_r are updated with immediates encoded in the format required
+// by the corresponding fields in the logical instruction.
+// If it can't be encoded, the function returns false, and the values pointed
+// to by n, imm_s and imm_r are undefined.
+bool Assembler::IsImmLogical(uint64_t value,
+                             uint8_t width,
+                             uint8_t* n,
+                             uint8_t* imm_s,
+                             uint8_t* imm_r) {
+  ASSERT((n != NULL) && (imm_s != NULL) && (imm_r != NULL));
+  ASSERT((width == kWRegSizeInBits) || (width == kXRegSizeInBits));
+
+  // Logical immediates are encoded using parameters n, imm_s and imm_r using
+  // the following table:
+  //
+  //  N   imms    immr    size        S             R
+  //  1  ssssss  rrrrrr    64    UInt(ssssss)  UInt(rrrrrr)
+  //  0  0sssss  xrrrrr    32    UInt(sssss)   UInt(rrrrr)
+  //  0  10ssss  xxrrrr    16    UInt(ssss)    UInt(rrrr)
+  //  0  110sss  xxxrrr     8    UInt(sss)     UInt(rrr)
+  //  0  1110ss  xxxxrr     4    UInt(ss)      UInt(rr)
+  //  0  11110s  xxxxxr     2    UInt(s)       UInt(r)
+  // (s bits must not be all set)
+  //
+  // A pattern is constructed of size bits, where the least significant S+1
+  // bits are set. The pattern is rotated right by R, and repeated across a
+  // 32 or 64-bit value, depending on destination register width.
+  //
+  // To test if an arbitrary immediate can be encoded using this scheme, an
+  // iterative algorithm is used.
+
+  // 1. If the value has all set or all clear bits, it can't be encoded.
+  if ((value == 0) || (value == 0xffffffffffffffffULL) ||
+      ((width == kWRegSizeInBits) && (value == 0xffffffff))) {
+    return false;
+  }
+
+  int lead_zero = CountLeadingZeros(value, width);
+  int lead_one = CountLeadingZeros(~value, width);
+  int trail_zero = Utils::CountTrailingZeros(value);
+  int trail_one = Utils::CountTrailingZeros(~value);
+  int set_bits = CountOneBits(value, width);
+
+  // The fixed bits in the immediate s field.
+  // If width == 64 (X reg), start at 0xFFFFFF80.
+  // If width == 32 (W reg), start at 0xFFFFFFC0, as the iteration for 64-bit
+  // widths won't be executed.
+  int imm_s_fixed = (width == kXRegSizeInBits) ? -128 : -64;
+  int imm_s_mask = 0x3F;
+
+  for (;;) {
+    // 2. If the value is two bits wide, it can be encoded.
+    if (width == 2) {
+      *n = 0;
+      *imm_s = 0x3C;
+      *imm_r = (value & 3) - 1;
+      return true;
+    }
+
+    *n = (width == 64) ? 1 : 0;
+    *imm_s = ((imm_s_fixed | (set_bits - 1)) & imm_s_mask);
+    if ((lead_zero + set_bits) == width) {
+      *imm_r = 0;
+    } else {
+      *imm_r = (lead_zero > 0) ? (width - trail_zero) : lead_one;
+    }
+
+    // 3. If the sum of leading zeros, trailing zeros and set bits is equal to
+    //    the bit width of the value, it can be encoded.
+    if (lead_zero + trail_zero + set_bits == width) {
+      return true;
+    }
+
+    // 4. If the sum of leading ones, trailing ones and unset bits in the
+    //    value is equal to the bit width of the value, it can be encoded.
+    if (lead_one + trail_one + (width - set_bits) == width) {
+      return true;
+    }
+
+    // 5. If the most-significant half of the bitwise value is equal to the
+    //    least-significant half, return to step 2 using the least-significant
+    //    half of the value.
+    uint64_t mask = (1UL << (width >> 1)) - 1;
+    if ((value & mask) == ((value >> (width >> 1)) & mask)) {
+      width >>= 1;
+      set_bits >>= 1;
+      imm_s_fixed >>= 1;
+      continue;
+    }
+
+    // 6. Otherwise, the value can't be encoded.
+    return false;
+  }
+}
+
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_ARM64