Array index computation dehoisting.

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index a179e808a3f63a11b6ab784e02b6bce06e597670..dfebc164fa50433babc778fb1f363d913e6043cf 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -2758,6 +2758,7 @@ HGraph* HGraphBuilder::CreateGraph() {
   sce.Process();
 
   graph()->EliminateRedundantBoundsChecks();
+  graph()->DehoistSimpleArrayIndexComputations();
 
   return graph();
 }
@@ -3082,6 +3083,131 @@ void HGraph::EliminateRedundantBoundsChecks() {
 }
 
 
+static bool DehoistArrayIndex(HInstruction* array_operation,
+                              HValue* index,
+                              int32_t index_position,
+                              int32_t* offset_value,
+                              Counters* counters) {
+  HConstant* constant;
+  HValue* subexpression;
+  int32_t sign;
+  if (index->IsAdd()) {
+    sign = 1;
+    HAdd* add = HAdd::cast(index);
+    if (add->left()->IsConstant()) {
+      subexpression = add->right();
+      constant = HConstant::cast(add->left());
+    } else if (add->right()->IsConstant()) {
+      subexpression = add->left();
+      constant = HConstant::cast(add->right());
+    } else {
+      return false;
+    }
+  } else if (index->IsSub()) {
+    sign = -1;
+    HSub* sub = HSub::cast(index);
+    if (sub->left()->IsConstant()) {
+      subexpression = sub->right();
+      constant = HConstant::cast(sub->left());
+    } else if (sub->right()->IsConstant()) {
+      subexpression = sub->left();
+      constant = HConstant::cast(sub->right());
+    } return false;
+  } else {
+    return false;
+  }
+
+  if (!constant->HasInteger32Value()) return false;
+  (*offset_value) = constant->Integer32Value() * sign;
+  // FIXME(mmassi): decide meaningful bound

[Jakob Kummerow, 2012/05/08 13:46:26]

fix this before landing? :-)

[Massi, 2012/05/14 13:48:52]

Done.

+  if ((*offset_value) >= 1 << 8 || (*offset_value) < 0) return false;
+  array_operation->SetOperandAt(index_position, subexpression);
+  if (index->HasNoUses()) {
+    index->DeleteAndReplaceWith(NULL);
+    counters->array_indexes_removed()->Increment();

[Jakob Kummerow, 2012/05/08 13:46:26]

Is it useful to keep those counters, or have they served their purpose?

[Massi, 2012/05/14 13:48:52]

Done.

+  }
+  counters->array_indexes_dehoisted()->Increment();
+  return true;
+}
+
+
+void HGraph::DehoistSimpleArrayIndexComputations() {
+  if (!FLAG_array_index_dehoisting) return;
+
+  HPhase phase("H_Dehoist index computations", this);
+  for (int i = 0; i < blocks()->length(); ++i) {
+    for (HInstruction* instr = blocks()->at(i)->first();
+        instr != NULL;
+        instr = instr->next()) {
+      int32_t index_offset = 0;
+      if (instr->IsLoadKeyedFastElement()) {

[Jakob Kummerow, 2012/05/08 13:46:26]

This is a lot of duplicate code...

Suggestion: 
class ArrayInstructionInterface {
 public:
  virtual HInstruction* key() = 0;
  virtual int32_t key_position { return 1; }
  virtual void SetIndexOffset(int32_t index_offset) = 0;
}
Then you can let H{Load,Store}Keyed{Fast,FastDouble,SpecializedArray}Element
inherit that and make DehoistArrayIndex() a whole lot easier (or even inline it
into its single remaining call site).
The downside would be that those three virtual methods can no longer be inlined,
but I think they're not that performance critical.

[Massi, 2012/05/14 13:48:52]

Oddly enough, this was my original idea but Sven decided against it, likely on
the base that we would still need the switch to detect those 6 instructions.

But I still like the "interface" approach more so I will happily implement it.

+        HLoadKeyedFastElement* operation =
+            HLoadKeyedFastElement::cast(instr);
+        if (DehoistArrayIndex(operation,
+                              operation->key(),
+                              1,
+                              &index_offset,
+                              isolate()->counters())) {
+          operation->SetIndexOffset(index_offset);
+        }
+      } else if (instr->IsLoadKeyedFastDoubleElement()) {
+        HLoadKeyedFastDoubleElement* operation =
+            HLoadKeyedFastDoubleElement::cast(instr);
+        if (DehoistArrayIndex(operation,
+                              operation->key(),
+                              1,
+                              &index_offset,
+                              isolate()->counters())) {
+          operation->SetIndexOffset(index_offset);
+        }
+      } else if (instr->IsLoadKeyedSpecializedArrayElement()) {
+        HLoadKeyedSpecializedArrayElement* operation =
+            HLoadKeyedSpecializedArrayElement::cast(instr);
+        if (DehoistArrayIndex(operation,
+                              operation->key(),
+                              1,
+                              &index_offset,
+                              isolate()->counters())) {
+          operation->SetIndexOffset(index_offset);
+        }
+      } else if (instr->IsStoreKeyedFastElement()) {
+        HStoreKeyedFastElement* operation =
+            HStoreKeyedFastElement::cast(instr);
+        if (DehoistArrayIndex(operation,
+                              operation->key(),
+                              1,
+                              &index_offset,
+                              isolate()->counters())) {
+          operation->SetIndexOffset(index_offset);
+        }
+      } else if (instr->IsStoreKeyedFastDoubleElement()) {
+        HStoreKeyedFastDoubleElement* operation =
+            HStoreKeyedFastDoubleElement::cast(instr);
+        if (DehoistArrayIndex(operation,
+                              operation->key(),
+                              1,
+                              &index_offset,
+                              isolate()->counters())) {
+          operation->SetIndexOffset(index_offset);
+        }
+      } else if (instr->IsStoreKeyedSpecializedArrayElement()) {
+        HStoreKeyedSpecializedArrayElement* operation =
+            HStoreKeyedSpecializedArrayElement::cast(instr);
+        if (DehoistArrayIndex(operation,
+                              operation->key(),
+                              1,
+                              &index_offset,
+                              isolate()->counters())) {
+          operation->SetIndexOffset(index_offset);
+        }
+      } else {
+        continue;
+      }
+    }
+  }
+}
+
+
 HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) {
   ASSERT(current_block() != NULL);
   current_block()->AddInstruction(instr);