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 238 matching lines @@
 void HGraph::EliminateRedundantBoundsChecks(HBasicBlock* bb,
                                             BoundsCheckTable* table) {
   BoundsCheckBbData* bb_data_list = NULL;
 
   for (HInstruction* i = bb->first(); i != NULL; i = i->next()) {
     if (!i->IsBoundsCheck()) continue;
 
     HBoundsCheck* check = HBoundsCheck::cast(i);
     check->ReplaceAllUsesWith(check->index());
 
-    isolate()->counters()->array_bounds_checks_seen()->Increment();
     if (!FLAG_array_bounds_checks_elimination) continue;
 
     int32_t offset;
     BoundsCheckKey* key =
         BoundsCheckKey::Create(bb->zone(), check, &offset);
     BoundsCheckBbData** data_p = table->LookupOrInsert(key);
     BoundsCheckBbData* data = *data_p;
     if (data == NULL) {
       bb_data_list = new(zone()) BoundsCheckBbData(key,
                                                    offset,
                                                    offset,
                                                    bb,
                                                    check,
                                                    bb_data_list,
                                                    NULL);
       *data_p = bb_data_list;
     } else if (data->OffsetIsCovered(offset)) {
       check->DeleteAndReplaceWith(NULL);
-      isolate()->counters()->array_bounds_checks_removed()->Increment();
     } else if (data->BasicBlock() == bb) {
       data->CoverCheck(check, offset);
-      isolate()->counters()->array_bounds_checks_removed()->Increment();
     } else {
       int32_t new_lower_offset = offset < data->LowerOffset()
           ? offset
           : data->LowerOffset();
       int32_t new_upper_offset = offset > data->UpperOffset()
           ? offset
           : data->UpperOffset();
       bb_data_list = new(bb->zone()) BoundsCheckBbData(key,
                                                        new_lower_offset,
                                                        new_upper_offset,
@@ skipping 23 matching lines @@
 
 
 void HGraph::EliminateRedundantBoundsChecks() {
   HPhase phase("H_Eliminate bounds checks", this);
   AssertNoAllocation no_gc;
   BoundsCheckTable checks_table;
   EliminateRedundantBoundsChecks(entry_block(), &checks_table);
 }
 
 
+static void DehoistArrayIndex(ArrayInstructionInterface* array_operation,
+                              Counters* counters) {

[Jakob Kummerow, 2012/05/15 15:53:23]

No need to pass in |counters| any more, is there?

+  HValue* index = array_operation->GetKey();
+  array_operation->SetDehoisted(false);

[Jakob Kummerow, 2012/05/15 15:53:23]

It's cleaner to do this in the instruction's c'tor (see comment there).

+
+  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;
+    }
+  } 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;
+  } else {
+    return;
+  }
+
+  if (!constant->HasInteger32Value()) return;
+  int32_t value = constant->Integer32Value() * sign;
+  // We limit offset values to 30 bits because we want to avoid the risk of
+  // overflows when the offset is added to the object header size.
+  if (value >= 1 << 30 || value < 0) return;
+  array_operation->SetKey(subexpression);
+  if (index->HasNoUses()) {
+    index->DeleteAndReplaceWith(NULL);
+  }
+  ASSERT(value >= 0);
+  array_operation->SetIndexOffset(static_cast<uint32_t>(value));
+  array_operation->SetDehoisted(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()) {
+      ArrayInstructionInterface* array_instruction = NULL;
+      if (instr->IsLoadKeyedFastElement()) {
+        HLoadKeyedFastElement* op = HLoadKeyedFastElement::cast(instr);
+        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+      } else if (instr->IsLoadKeyedFastDoubleElement()) {
+        HLoadKeyedFastDoubleElement* op =
+            HLoadKeyedFastDoubleElement::cast(instr);
+        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+      } else if (instr->IsLoadKeyedSpecializedArrayElement()) {
+        HLoadKeyedSpecializedArrayElement* op =
+            HLoadKeyedSpecializedArrayElement::cast(instr);
+        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+      } else if (instr->IsStoreKeyedFastElement()) {
+        HStoreKeyedFastElement* op = HStoreKeyedFastElement::cast(instr);
+        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+      } else if (instr->IsStoreKeyedFastDoubleElement()) {
+        HStoreKeyedFastDoubleElement* op =
+            HStoreKeyedFastDoubleElement::cast(instr);
+        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+      } else if (instr->IsStoreKeyedSpecializedArrayElement()) {
+        HStoreKeyedSpecializedArrayElement* op =
+            HStoreKeyedSpecializedArrayElement::cast(instr);
+        array_instruction = static_cast<ArrayInstructionInterface*>(op);
+      } else {
+        continue;
+      }
+      DehoistArrayIndex(array_instruction, isolate()->counters());
+    }
+  }
+}
+
+
 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