Adds logical operations to arm64.

runtime/vm/assembler_arm64.cc

Index: runtime/vm/assembler_arm64.cc
===================================================================
--- runtime/vm/assembler_arm64.cc	(revision 34900)
+++ runtime/vm/assembler_arm64.cc	(working copy)
@@ -73,6 +73,136 @@
   return fpu_reg_names[reg];
 }
 
+
+static int CountLeadingZeros(uint64_t value, int width) {
+  ASSERT((width == 32) || (width == 64));
+  if (value == 0) {
+    return width;
+  }
+  int count = 0;
+  do {
+    count++;
+  } while (value >>= 1);
+  return width - count;
+}
+
+
+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 operand is
+// undefined.
+bool Assembler::IsImmLogical(uint64_t value, uint8_t width, Operand* imm_op) {
+  ASSERT(imm_op != NULL);
+  ASSERT((width == kWRegSizeInBits) || (width == kXRegSizeInBits));
+  ASSERT((width == kXRegSizeInBits) || (value <= 0xffffffffUL));
+  uint8_t n = 0;
+  uint8_t imm_s = 0;
+  uint8_t imm_r = 0;
+
+  // 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;
+      *imm_op = Operand(n, imm_s, imm_r);
+      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) {
+      *imm_op = Operand(n, imm_s, imm_r);
+      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) {
+      *imm_op = Operand(n, imm_s, imm_r);
+      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