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();
 
-  // 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);
   current_block()->AddInstruction(instr);
   return instr;
 }
 
 
 void HGraphBuilder::AddSimulate(int ast_id) {
   ASSERT(current_block() != NULL);
@@ skipping 5632 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal