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_;
+};
+
+// 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_;}

[fschneider, 2012/04/18 07:51:35]

Spaces around { and }.

[Massi, 2012/04/18 09:19:27]

Done.

+  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());

[fschneider, 2012/04/18 07:51:35]

Indentation.

[Massi, 2012/04/18 09:19:27]

Done.

+    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 07:51:35]

Two empty lines here.

[Massi, 2012/04/18 09:19:27]

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 07:51:35]

Two lines also here (and in other places between functions and classes)

[Massi, 2012/04/18 09:19:27]

Done.

+class BoundsCheckTable : private ZoneHashMap {
+ public:
+  BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key) {
+    return reinterpret_cast<BoundsCheckBbData**>(&(Lookup(key,

[fschneider, 2012/04/18 07:51:35]

I'd break the line before the &. I think it will be better readable.

[Massi, 2012/04/18 09:19:27]

Done.

+                                                          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) {
+  }
+};
+
+// 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 07:51:35]

To solve this TODO you can maybe consider making BoundsCheckKey BASE_EMBEDDED
(i.e. not zone-allocated). Then you don't need to heap-allocate the space for it
except when creating a new BoundsCheckBbData object.

[Massi, 2012/04/18 09:19:27]

We decided to leave the code as it is and remove the TODO.
This should cost us two pointers in the zone for every bounds check, which is
not *that* much.
The alternative is not hard to implement but the code would be less clean, and
the maintainability cost is likely higher than the memory cost.

+    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());
+    }
+  }
+}
+
+void HGraph::EliminateRedundantBoundsChecks() {
+  HPhase phase("H_Eliminate redundant 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