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;
 };
 
 
+bool HGraph::TryRotateLeft(HInstruction* instr) {
+  HInstruction* current = instr;
+  ASSERT(current->IsBitwise());
+  HBitwise* bor = HBitwise::cast(current);
+  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;
+  }
+
+
+  if (shl->UseCount()>1 || shr->UseCount()>1) return false;

[ulan, 2012/09/27 14:55:30]

Please add space before and after each ">" operator.

+  if (!shr->representation().IsInteger32() ||
+      !shl->representation().IsInteger32())

[Erik Corry, 2012/09/27 14:45:44]

Missing {}

+    return false;
+  if (shl->left() != shr->left()) return false;
+
+  if (!shr->right()->representation().IsInteger32() ||
+      !shl->right()->representation().IsInteger32() ||
+      !shl->left()->representation().IsInteger32())
+    return false;
+
+  if (!shr->right()->IsSub()) return false;

[Erik Corry, 2012/09/27 14:45:44]

This function needs a comment explaining what it is looking for, and the line
above here needs an explanation of why only a sub function is OK here.

+  HSub* sub = HSub::cast(shr->right());
+  if (!sub->left()->IsConstant() ||
+      !sub->left()->representation().IsInteger32() ||
+      !sub->right()->representation().IsInteger32())
+    return false;
+
+  if (HConstant::cast(sub->left())->Integer32Value() != 32) return false;
+
+  if (sub->right()->IsChange() && shl->right()->IsChange()) {
+     if (sub->right()->OperandAt(0) != shl->right()->OperandAt(0))

[Erik Corry, 2012/09/27 14:45:44]

Missing {}

+       return false;
+  } else if (sub->right() != shl->right()) {
+    return false;
+  }
+
+  // start replacement
+  HValue* left = shr->left();
+  HValue* right = shr->right();
+  HValue* context = shr->context();
+  HInstruction* ror = new(zone()) HRor(context, left, right);
+  ror->InsertAfter(bor);
+  bor->DeleteAndReplaceWith(ror);
+  shl->DeleteAndReplaceWith(NULL);
+  shr->DeleteAndReplaceWith(NULL);
+
+  return true;
+}
+
+
+
+bool HGraph::TryRotateRight(HInstruction* instr) {

[Erik Corry, 2012/09/27 14:45:44]

There is a lot of copied code here - can they be combined into one function with
a flag?

+  HInstruction* current = instr;
+  ASSERT(current->IsBitwise());
+  HBitwise* bor = HBitwise::cast(current);
+  HShl* shl;
+  HShr* shr;
+  if (bor->left()->IsShl() && bor->right()->IsShr()) {

[ulan, 2012/09/27 14:55:30]

Please add space before and after each ">" operator.

+    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;
+  }
+  if (shl->UseCount()>1 || shr->UseCount()>1) return false;
+  if (!shr->representation().IsInteger32() ||
+      !shl->representation().IsInteger32())
+    return false;
+  if (shl->left() != shr->left()) return false;
+  if (!shr->right()->representation().IsInteger32() ||
+      !shl->right()->representation().IsInteger32() ||
+      !shl->left()->representation().IsInteger32())
+    return false;
+  if (!shl->right()->IsSub()) return false;
+  HSub* sub = HSub::cast(shl->right());
+  if (!sub->left()->IsConstant() ||
+      !sub->left()->representation().IsInteger32() ||
+      !sub->right()->representation().IsInteger32())
+    return false;
+  HConstant* constant = HConstant::cast(sub->left());
+  if (constant->Integer32Value() != 32) return false;
+
+  if (sub->right()->IsChange() && shl->right()->IsChange()) {
+     if (sub->right()->OperandAt(0) != shl->right()->OperandAt(0))
+       return false;
+  } else if (sub->right() != shl->right()) {
+    return false;
+  }
+
+  // start replacement
+  HValue* left = shr->left();
+  HValue* right = shr->right();
+  HValue* context = shr->context();
+  HInstruction* ror = new(zone()) HRor(context, left, right);
+  ror->InsertAfter(bor);
+  bor->DeleteAndReplaceWith(ror);
+  shl->DeleteAndReplaceWith(NULL);
+  shr->DeleteAndReplaceWith(NULL);
+  if (sub->HasNoUses()) sub->DeleteAndReplaceWith(NULL);
+  if (constant->HasNoUses()) constant->DeleteAndReplaceWith(NULL);
+
+  return true;
+}
+
+
+
+void HGraph::ReplaceWithRor() {
+  if (!FLAG_use_replace_with_ror) return;
+  HPhase phase("H_ReplaceWithRor", 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) {
+        if (!TryRotateLeft(instr)) {
+          TryRotateRight(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)

[ulan, 2012/09/27 15:30:10]

I am concerned with this ifdef. Hydrogen should contain platform independent
code and these kind of optimizations should be done on the Lithium level.

+  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