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

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 2543 matching lines @@
   if (FLAG_use_range) {
     HRangeAnalysis rangeAnalysis(graph());
     rangeAnalysis.Analyze();
   }
   graph()->ComputeMinusZeroChecks();
 
   // Eliminate redundant stack checks on backwards branches.
   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
   // check instructions is really a copy of the original value.
   graph()->ReplaceCheckedValues();
 
   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);
   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());
@@ skipping 5648 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal