Replace a set of Hydrogen instructions with rotate instructions on ARM

src/hydrogen.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1003 matching lines @@
   PostorderProcessor* child_;
   HLoopInformation* loop_;
   HBasicBlock* block_;
   HBasicBlock* loop_header_;
   int loop_index;
   int loop_length;
   HSuccessorIterator successor_iterator;
 };
 
 
+// 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());
 
   ZoneList<HBasicBlock*> reverse_result(8, zone());
   HBasicBlock* start = blocks_[0];
   PostorderProcessor* postorder =
       PostorderProcessor::CreateEntryProcessor(zone(), start, &visited);
   while (postorder != NULL) {
     postorder = postorder->PerformStep(zone(), &visited, &reverse_result);
@@ skipping 2361 matching lines @@
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(this);
     rangeAnalysis.Analyze();
   }
   ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   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();
 
   return true;
 }
 
 
 // We try to "factor up" HBoundsCheck instructions towards the root of the
 // dominator tree.
 // For now we handle checks where the index is like "exp + int32value".
@@ skipping 6568 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal