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..dd791bcd1ecf748aae159d641eb1390d225f0bc8 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -2561,6 +2561,8 @@ HGraph* HGraphBuilder::CreateGraph() {
   HStackCheckEliminator sce(graph());
   sce.Process();
 
+  graph()->EliminateRedundantChecks();
+
   // 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
@@ -2570,6 +2572,220 @@ HGraph* HGraphBuilder::CreateGraph() {
   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 DT 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_;}
+
+  intptr_t Hash() {
+    return index_base_->Hashcode() ^ length_->Hashcode();
+  }
+
+  static BoundsCheckKey* CreateBoundsCheckKey(Zone* zone,

[Sven Panne, 2012/04/12 09:45:42]

To quote memegen: Just drop the "BoundsCheckKey" part in the function name, it's
cleaner... ;-)

[Massi, 2012/04/13 10:55:16]

Done.

+                                              HBoundsCheck* check,
+                                              int32_t* offset) {
+    HValue* index_base;
+    if (check->index()->IsAdd()) {

[Sven Panne, 2012/04/12 09:45:42]

It might be worthwhile to reduce the redundancy and nesting here somehow, a
human brain's stack depth is very limited. :-)

[Massi, 2012/04/13 10:55:16]

Done.

+      HAdd* index = HAdd::cast(check->index());
+      if (index->left()->IsConstant()) {
+        HConstant* constant = HConstant::cast(index->left());
+        if (constant->HasInteger32Value()) {
+          *offset = constant->Integer32Value();
+          index_base = index->right();
+        } else {
+          *offset = 0;
+          index_base = index;
+        }
+      } else if (index->right()->IsConstant()) {
+        HConstant* constant = HConstant::cast(index->right());
+        if (constant->HasInteger32Value()) {
+          *offset = constant->Integer32Value();
+          index_base = index->left();
+        } else {
+          *offset = 0;
+          index_base = index;
+        }
+      } else {
+        *offset = 0;
+        index_base = check->index();
+      }
+    } 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_;
+};
+
+// Data for each BB about HBoundsCheck that can be eliminated or moved.
+class BoundsCheckBbData: public ZoneObject {
+// class BoundsCheckBbData {
+ public:
+  BoundsCheckKey* Key() {return key_;}
+  int32_t Offset() {return offset_;}
+  HBasicBlock* BasicBlock() {return bb_;}
+  HBoundsCheck* Check() {return check_;}
+  BoundsCheckBbData* NextInBb() {return next_in_bb_;}
+  BoundsCheckBbData* FatherInDt() {return father_in_dt_;}
+
+  static void RemoveCheck(HBoundsCheck* check) {
+    HValue* index = check->index();
+    check->DeleteAndReplaceWith(NULL);
+    if (index->UseCount() == 0) {
+      index->DeleteAndReplaceWith(NULL);
+    }
+  }
+
+  void ReplaceCheck(HBoundsCheck* new_check, int32_t new_offset) {
+    // FIXME: can it be something else?
+    if (new_check->index()->IsInstruction()) {
+      HInstruction* new_index = HInstruction::cast(new_check->index());
+      new_index->Unlink();
+      new_check->Unlink();
+      new_index->InsertAfter(check_);
+      new_check->InsertAfter(new_index);
+
+      RemoveCheck(check_);
+
+      check_ = new_check;
+      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;
+    bb_ = bb;
+    check_ = check;
+    next_in_bb_ = next_in_bb;
+    father_in_dt_ = father_in_dt;
+  }
+
+ private:
+  BoundsCheckKey* key_;
+  int32_t offset_;
+  HBasicBlock* bb_;
+  HBoundsCheck* check_;
+  BoundsCheckBbData* next_in_bb_;
+  BoundsCheckBbData* father_in_dt_;

[Sven Panne, 2012/04/12 09:45:42]

I think using "bb" and "dt" is a little bit cryptic, and we normally don't use
the abbreviations. "bb" e.g. is already used for "block buffer", etc.  Names
which are blindingly obviously while writing the code aren't necessarily like
this 2 weeks later. ;-)

[Massi, 2012/04/13 10:55:16]

Done.

+};
+
+bool BoundsCheckKeyMatch(void* key1, void* key2) {

[Sven Panne, 2012/04/12 09:45:42]

This should probably be "static".

[Massi, 2012/04/13 10:55:16]

Done.

+  BoundsCheckKey* k1 = static_cast<BoundsCheckKey*>(key1);
+  BoundsCheckKey* k2 = static_cast<BoundsCheckKey*>(key2);
+  return k1->IndexBase() == k2->IndexBase() && k1->Length() == k2->Length();
+}
+
+class BoundsCheckTable BASE_EMBEDDED {
+ public:
+  void EliminateRedundantChecks(HBasicBlock* bb) {

[Sven Panne, 2012/04/12 09:45:42]

I don't think this function really belongs into this class. BoundsCheckTable's
responsibility should just be a more sane^H^H^H cleanly typed interface to
ZoneHashMap.

[Massi, 2012/04/13 10:55:16]

Done.

+    BoundsCheckBbData* bb_data_list = NULL;
+
+    for (HInstruction* i = bb->first(); i != NULL; i = i->next()) {

[Sven Panne, 2012/04/12 09:45:42]

Perhaps the first loop can be extracted into a separate function?

[Massi, 2012/04/13 10:55:16]

Done.

+      if (i->IsBoundsCheck()) {
+        HBoundsCheck* check = HBoundsCheck::cast(i);
+        int32_t offset;
+        // TODO(mmassi): allocate key only when we create a new table  entry...
+        BoundsCheckKey* key =
+            BoundsCheckKey::CreateBoundsCheckKey(bb->zone(), check, &offset);
+
+        BoundsCheckBbData** data_p = LookupOrInsert(key);
+        BoundsCheckBbData* data = *data_p;
+        if (data == NULL) {
+          bb_data_list = new(bb->zone()) BoundsCheckBbData(key,
+                                                           offset,
+                                                           bb,
+                                                           check,
+                                                           bb_data_list,
+                                                           NULL);
+        } else if (offset <= data->Offset()) {
+            BoundsCheckBbData::RemoveCheck(check);
+        } else if (data->BasicBlock() == bb) {
+            data->ReplaceCheck(check, offset);
+        } else {
+          bb_data_list = new(bb->zone()) BoundsCheckBbData(key,
+                                                           offset,
+                                                           bb,
+                                                           check,
+                                                           bb_data_list,
+                                                           data);
+        }
+      }
+    }
+
+    for (int i = 0; i < bb->dominated_blocks()->length(); ++i) {
+      EliminateRedundantChecks(bb->dominated_blocks()->at(i));
+    }
+
+    for (BoundsCheckBbData* data = bb_data_list;
+         data != NULL;
+         data = data->NextInBb()) {
+      if (data->FatherInDt()) {
+        Insert(data->Key(), data->FatherInDt());
+      } else {
+        Remove(data->Key());
+      }
+    }
+  }
+
+  BoundsCheckBbData* Lookup(BoundsCheckKey* key) {
+    intptr_t hash = key->Hash();
+    ZoneHashMap::Entry* entry = map->Lookup(key, hash, false);
+    return entry ? static_cast<BoundsCheckBbData*>(entry->value) : NULL;
+  }
+
+  BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key) {
+    intptr_t hash = key->Hash();
+    ZoneHashMap::Entry* entry = map->Lookup(key, hash, true);
+    return reinterpret_cast<BoundsCheckBbData**>(&(entry->value));
+  }
+
+  void Insert(BoundsCheckKey* key, BoundsCheckBbData* data) {
+    intptr_t hash = key->Hash();
+    ZoneHashMap::Entry* entry = map->Lookup(key, hash, true);
+    entry->value = data;
+  }
+
+  void Remove(BoundsCheckKey* key) {
+    intptr_t hash = key->Hash();
+    map->Remove(key, hash);
+  }
+
+  BoundsCheckTable() {
+    map = new ZoneHashMap(BoundsCheckKeyMatch);

[Sven Panne, 2012/04/12 09:45:42]

Using an initializer is a nicer and more standard way for doing this.

[Massi, 2012/04/13 10:55:16]

Done.

+  }
+
+ private:
+  ZoneHashMap *map;
+};
+
+void HGraph::EliminateRedundantChecks() {
+  HPhase phase("H_Eliminate redundant checks", this);
+
+  AssertNoAllocation no_gc;
+  BoundsCheckTable checks_table;
+  checks_table.EliminateRedundantChecks(entry_block());
+}
 
 void HGraph::ReplaceCheckedValues() {
   HPhase phase("H_Replace checked values", this);