Replace a set of Hydrogen instructions with rotate instructions on ARM

src/hydrogen.cc

Index: src/hydrogen.cc
===================================================================
--- src/hydrogen.cc	(revision 12582)
+++ src/hydrogen.cc	(working copy)
@@ -1021,6 +1021,98 @@
 };
 
 
+// Help with TryRotate pattern matching by checking if sub is 32 - s. It's okay
+// if the right operand of sub isn't the same HValue as s if both are HChange
+// instructions from the same value. This is called twice to determine whether
+// we do a left or right rotation.
+static bool TryMatchShiftAmountForRotate(HValue* s, HValue* sub) {
+  if (!sub->IsSub())
+    return false;
+  HValue* subl = HSub::cast(sub)->left();
+  HValue* subr = HSub::cast(sub)->right();
+  return subl->representation().IsInteger32() &&
+         subl->IsConstant() &&
+         HConstant::cast(subl)->Integer32Value() == 32 &&
+         (s == subr ||
+          (subr->IsChange() && s->IsChange() &&
+           subr->OperandAt(0) == s->OperandAt(0)));
+}
+
+
+// Attempt to replace one of the following patterns with a rotate instruction:
+//   n << s  | n >>> (32 - s)    ==> rotate left
+//   n >>> s | n <<  (32 - s)    ==> rotate right
+bool HGraph::TryRotate(HInstruction* instr) {
+  HBitwise* bor = HBitwise::cast(instr);
+  ASSERT(bor->op() == Token::BIT_OR);
+  HShl* shl;
+  HShr* shr;
+  if (bor->left()->IsShl() && bor->right()->IsShr()) {
+    shl = HShl::cast(bor->left());
+    shr = HShr::cast(bor->right());
+  } else if (bor->left()->IsShr() && bor->right()->IsShl()) {
+    shl = HShl::cast(bor->right());
+    shr = HShr::cast(bor->left());
+  } else {
+    return false;
+  }
+
+  // Neither shift can be used elsewhere (or it is not safe to delete them).
+  // Also, both must have Integer32 representation, since we can't rotate
+  // anything else quickly.
+  if (shl->UseCount() > 1 || !shl->representation().IsInteger32() ||
+      shr->UseCount() > 1 || !shr->representation().IsInteger32() ||
+      !shr->right()->representation().IsInteger32() ||
+      !shr->left()->representation().IsInteger32()  ||
+      !shl->right()->representation().IsInteger32() ||
+      !shl->left()->representation().IsInteger32()) {
+    return false;
+  }
+
+  // The value being shifted must be the same.
+  if (shl->left() != shr->left())
+    return false;
+  HValue* number = shl->left();
+
+  // The shift values must be s and 32-s. Whether we have found a left or
+  // right rotate depends on which shift has 32-s. Note that it's okay if the
+  // "s" values on both sides are distinct HChange instructions, as long as
+  // their operands are the same value.
+  HValue* shift_amount = NULL;
+  if (TryMatchShiftAmountForRotate(shl->right(), shr->right()) |
+      TryMatchShiftAmountForRotate(shr->right(), shl->right())) {
+    shift_amount = shr->right();
+  } else {
+    return false;
+  }
+
+  // We have matched all the operands. Do the replacement.
+  HRor* ror = new(zone()) HRor(shr->context(), number, shift_amount);
+  ror->InsertAfter(bor);
+  bor->DeleteAndReplaceWith(ror);
+  shl->DeleteAndReplaceWith(NULL);
+  shr->DeleteAndReplaceWith(NULL);
+
+  return true;
+}
+
+
+void HGraph::ReplaceWithRor() {
+  if (!FLAG_use_replace_with_ror) return;
+  HPhase phase("H_Replace with ror", this);
+  for (int i = 0; i < blocks()->length(); ++i) {
+    HInstruction* instr = blocks()->at(i)->first();
+    while (instr != NULL) {
+      if (instr->IsBitwise() &&
+          HBitwise::cast(instr)->op() == Token::BIT_OR) {
+        TryRotate(instr);
+      }
+      instr = instr->next();
+    }
+  }
+}
+
+
 void HGraph::OrderBlocks() {
   HPhase phase("H_Block ordering");
   BitVector visited(blocks_.length(), zone());
@@ -3402,6 +3494,12 @@
   HStackCheckEliminator sce(this);
   sce.Process();
 
+#if defined(V8_TARGET_ARCH_ARM)
+  // TODO: support rotate instructions on other architectures. For now they are
+  // only supported on ARM.
+  ReplaceWithRor();
+#endif
+
   EliminateRedundantBoundsChecks();
   DehoistSimpleArrayIndexComputations();