Array index computation dehoisting.

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 2740 matching lines @@
     HRangeAnalysis rangeAnalysis(graph());
     rangeAnalysis.Analyze();
   }
   graph()->ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   HStackCheckEliminator sce(graph());
   sce.Process();
 
   graph()->EliminateRedundantBoundsChecks();
+  graph()->DehoistSimpleArrayIndexComputations();
 
   return graph();
 }
 
 
 // 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".
 // If in the dominator tree we check "exp + v1" and later (dominated)
 // "exp + v2", if v2 <= v1 we can safely remove the second check, and if
@@ skipping 304 matching lines @@
 
 
 void HGraph::EliminateRedundantBoundsChecks() {
   HPhase phase("H_Eliminate bounds checks", this);
   AssertNoAllocation no_gc;
   BoundsCheckTable checks_table;
   EliminateRedundantBoundsChecks(entry_block(), &checks_table);
 }
 
 
+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);
   return instr;
 }
 
 
 void HGraphBuilder::AddSimulate(int ast_id) {
   ASSERT(current_block() != NULL);
   current_block()->AddSimulate(ast_id);
@@ skipping 5765 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal