Eliminate redundant array bound checks (checks already performed earlier in the DT).

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index f9d41910f31edb9f1bbbda6ac22ec0ce5935d1c0..a6504345dee066465b07464e3ac8c912479e4aa2 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -2561,31 +2561,230 @@ HGraph* HGraphBuilder::CreateGraph() {
   HStackCheckEliminator sce(graph());
   sce.Process();
 
-  // Replace the results of check instructions with the original value, if the
-  // result is used. This is safe now, since we don't do code motion after this
-  // point. It enables better register allocation since the value produced by
-  // check instructions is really a copy of the original value.
-  graph()->ReplaceCheckedValues();
+  graph()->EliminateRedundantBoundsChecks();
 
   return graph();
 }
 
-
-void HGraph::ReplaceCheckedValues() {
-  HPhase phase("H_Replace checked values", this);
-  for (int i = 0; i < blocks()->length(); ++i) {
-    HInstruction* instr = blocks()->at(i)->first();
-    while (instr != NULL) {
-      if (instr->IsBoundsCheck()) {
-        // Replace all uses of the checked value with the original input.
-        ASSERT(instr->UseCount() > 0);
-        instr->ReplaceAllUsesWith(HBoundsCheck::cast(instr)->index());
+// 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
+// v2 > v1 we can use v2 in the 1st check and again remove the second.
+// To do so we keep a dictionary of all checks where the key if the pair
+// "exp, length".
+// The class BoundsCheckKey represents this key.
+class BoundsCheckKey : public ZoneObject {
+ public:
+  HValue* IndexBase() const {return index_base_;}
+  HValue* Length() const {return length_;}
+
+  uint32_t Hash() {
+    return static_cast<uint32_t>(index_base_->Hashcode() ^ length_->Hashcode());
+  }
+
+  static BoundsCheckKey* Create(Zone* zone,
+                                HBoundsCheck* check,
+                                int32_t* offset) {
+    HValue* index_base = NULL;
+    HConstant* constant = NULL;
+    if (check->index()->IsAdd()) {
+      HAdd* index = HAdd::cast(check->index());
+      if (index->left()->IsConstant()) {
+        constant = HConstant::cast(index->left());
+        index_base = index->right();
+      } else if (index->right()->IsConstant()) {
+        constant = HConstant::cast(index->right());
+        index_base = index->left();
       }
-      instr = instr->next();
+    }
+
+    if (constant != NULL && constant->HasInteger32Value()) {
+      *offset = constant->Integer32Value();
+    } else {
+      *offset = 0;
+      index_base = check->index();
+    }
+    return new(zone) BoundsCheckKey(index_base, check->length());
+  }
+
+ private:
+  BoundsCheckKey(HValue* index_base, HValue* length) {
+    index_base_ = index_base;
+    length_ = length;
+  }
+
+  HValue* index_base_;
+  HValue* length_;
+};
+

[fschneider, 2012/04/18 09:42:18]

Two lines space here.

[Massi, 2012/04/23 15:19:19]

Done.

+// Data about each HBoundsCheck that can be eliminated or moved.
+// It is the "value" in the dictionary indexed by "base-index, length"
+// (the key is BoundsCheckKey).
+// We scan the code with a dominator tree traversal.
+// Traversing the dominator tree we keep a stack (implemented as a singly
+// linked list) of "data" for each basic block that contains a relevant check
+// with the same key (the dictionary holds the head of the list).
+// We also keep all the "data" created for a given basic block in a list, and
+// use it to "clean up" the dictionary when backtracking in the dominator tree
+// traversal.
+// Doing this each dictionary entry always directly points to the check that
+// is dominating the code being examined now.
+// We also track the current "offset" of the index expression and use it to
+// decide if any check is already "covered" (so it can be removed) or not.
+class BoundsCheckBbData: public ZoneObject {
+ public:
+  BoundsCheckKey* Key() { return key_; }
+  int32_t Offset() { return offset_; }
+  HBasicBlock* BasicBlock() { return basic_block_; }
+  HBoundsCheck* Check() { return check_; }
+  BoundsCheckBbData* NextInBasicBlock() { return next_in_bb_; }
+  BoundsCheckBbData* FatherInDominatorTree() { return father_in_dt_; }
+
+  void CoverCheck(HBoundsCheck* new_check,
+                  int32_t new_offset) {
+    ASSERT(new_check->index()->representation().IsInteger32());
+    HConstant* new_constant =
+        new HConstant(Handle<Object>(Smi::FromInt(new_offset)),
+                      Representation::Integer32());
+    if (added_index_ == NULL) {
+      new_constant->InsertBefore(Check());
+      added_index_ =
+          new(BasicBlock()->zone()) HAdd(NULL,
+                                         Key()->IndexBase(),
+                                         new_constant);
+      added_index_->AssumeRepresentation(new_check->index()->representation());
+      added_index_->InsertBefore(Check());
+    } else {
+      new_constant->InsertBefore(added_index_);
+      added_offset_->DeleteAndReplaceWith(new_constant);
+    }
+    added_offset_ = new_constant;
+    Check()->SetOperandAt(0, added_index_);
+    new_check->DeleteAndReplaceWith(NULL);
+    offset_ = new_offset;
+  }
+
+  BoundsCheckBbData(BoundsCheckKey* key,
+                    int32_t offset,
+                    HBasicBlock* bb,
+                    HBoundsCheck* check,
+                    BoundsCheckBbData* next_in_bb,
+                    BoundsCheckBbData* father_in_dt) :
+                       key_(key),
+                       offset_(offset),
+                       basic_block_(bb),
+                       check_(check),
+                       added_offset_(NULL),
+                       added_index_(NULL),
+                       next_in_bb_(next_in_bb),
+                       father_in_dt_(father_in_dt) { }
+
+ private:
+  BoundsCheckKey* key_;
+  int32_t offset_;
+  HBasicBlock* basic_block_;
+  HBoundsCheck* check_;
+  HConstant* added_offset_;
+  HAdd* added_index_;
+  BoundsCheckBbData* next_in_bb_;
+  BoundsCheckBbData* father_in_dt_;
+};
+

[fschneider, 2012/04/18 09:42:18]

Two lines space here.

[Massi, 2012/04/23 15:19:19]

Done.

+static bool BoundsCheckKeyMatch(void* key1, void* key2) {
+  BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
+  BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
+
+  return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
+}
+

[fschneider, 2012/04/18 09:42:18]

Two lines space here.

[Massi, 2012/04/23 15:19:19]

Done.

+class BoundsCheckTable : private ZoneHashMap {
+ public:
+  BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key) {
+    return reinterpret_cast<BoundsCheckBbData**>(
+        &(Lookup(key, key->Hash(), true)->value));
+  }
+
+  void Insert(BoundsCheckKey* key, BoundsCheckBbData* data) {
+    Lookup(key, key->Hash(), true)->value = data;
+  }
+
+  void Delete(BoundsCheckKey* key) {
+    Remove(key, key->Hash());
+  }
+
+  BoundsCheckTable() : ZoneHashMap(BoundsCheckKeyMatch) {
+  }
+};
+

[fschneider, 2012/04/18 09:42:18]

Two lines space here.

[Massi, 2012/04/23 15:19:19]

Done.

+// Eliminates checks in bb and recursively in the dominated blocks.
+// Also replace the results of check instructions with the original value, if
+// the result is used. This is safe now, since we don't do code motion after
+// this point. It enables better register allocation since the value produced
+// by check instructions is really a copy of the original value.
+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();
+    int32_t offset;
+    // TODO(mmassi): allocate key only when we create a new table  entry...

[fschneider, 2012/04/18 09:42:18]

If we plan to implement the TODO, we usually create an issue on the v8 issue
tracker and write TODO(issue number).

As discussed offline, we leave it as is for now, so I'd remove the TODO-line
completely.

+    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(bb->zone()) BoundsCheckBbData(key,
+                                                       offset,
+                                                       bb,
+                                                       check,
+                                                       bb_data_list,
+                                                       NULL);
+      *data_p = bb_data_list;
+    } else if (offset <= data->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 {
+      bb_data_list = new(bb->zone()) BoundsCheckBbData(key,
+                                                       offset,
+                                                       bb,
+                                                       check,
+                                                       bb_data_list,
+                                                       data);
+      table->Insert(key, bb_data_list);
+    }
+  }
+
+  for (int i = 0; i < bb->dominated_blocks()->length(); ++i) {
+    EliminateRedundantBoundsChecks(bb->dominated_blocks()->at(i), table);
+  }
+
+  for (BoundsCheckBbData* data = bb_data_list;
+       data != NULL;
+       data = data->NextInBasicBlock()) {
+    if (data->FatherInDominatorTree()) {
+      table->Insert(data->Key(), data->FatherInDominatorTree());
+    } else {
+      table->Delete(data->Key());
     }
   }
 }
 

[fschneider, 2012/04/18 09:42:18]

Two lines space here.

[Massi, 2012/04/23 15:19:19]

Done.

+void HGraph::EliminateRedundantBoundsChecks() {
+  HPhase phase("H_Eliminate bounds checks", this);
+  AssertNoAllocation no_gc;
+  BoundsCheckTable checks_table;
+  EliminateRedundantBoundsChecks(entry_block(), &checks_table);
+}
 
 HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) {
   ASSERT(current_block() != NULL);