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()) {

[Sven Panne, 2012/04/13 11:38:06]

If we extract a function like 'MatchOffsetExpresssion(HValue** index_base,
HConstant** constant)' and massage CoverCheck a tiny bit, it should be
straightforward to handle the HMinus case, too. I leave it up to you to do this
now or in a separate CL.

[Massi, 2012/04/17 10:56:58]

I'll do it in a separate CL.

+      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 {
+// class BoundsCheckBbData {

[Sven Panne, 2012/04/13 11:38:06]

Remove that line.

[Massi, 2012/04/17 10:56:58]

Done.

+ public:
+  BoundsCheckKey* Key() {return key_;}

[fschneider, 2012/04/13 12:38:00]

style-nit: add spaces after/before {}. 

[Massi, 2012/04/17 10:56:58]

Done.

+  int32_t Offset() {return offset_;}
+  HBasicBlock* BasicBlock() {return basic_block_;}
+  HBoundsCheck* Check() {return check_;}
+  BoundsCheckBbData* NextInBasicBlock() {return next_in_basic_block_;}
+  BoundsCheckBbData* FatherInDominatorTree() {return father_in_dominator_tree_;}
+
+  static void RemoveCheck(HBoundsCheck* check) {

[Sven Panne, 2012/04/13 11:38:06]

I think this method should be generalized and moved to HTemplateInstruction
(under a better name). In general, static methods are a code smell, with very
few exceptions like factory methods.

[Massi, 2012/04/17 10:56:58]

Done.

+    HValue* index = check->index();
+    HValue* length = check->length();
+    check->DeleteAndReplaceWith(NULL);
+    if (index->HasNoUses()) {
+      index->DeleteAndReplaceWith(NULL);
+    }
+    if (length->HasNoUses()) {
+      length->DeleteAndReplaceWith(NULL);
+    }
+  }
+
+  void CoverCheck(HBoundsCheck* new_check, int32_t new_offset) {
+    if (check_simulate_ != NULL) {

[Sven Panne, 2012/04/13 11:38:06]

Use a guard clause instead, see
http://martinfowler.com/refactoring/catalog/replaceNestedConditionalWithGuard...

[Massi, 2012/04/17 10:56:58]

Done.

+      ASSERT(new_check->index()->IsAdd());
+      HAdd* new_check_index = HAdd::cast(new_check->index());
+      if (added_index_ == NULL) {
+        HSimulate* added_simulate =
+            new(BasicBlock()->zone()) HSimulate(check_simulate_->ast_id(),
+                                                check_simulate_->pop_count());
+        added_simulate->InsertBefore(Check());
+        added_index_ =
+            new(BasicBlock()->zone()) HAdd(new_check_index->context(),
+                                           new_check_index->left(),
+                                           new_check_index->right());
+        added_index_->InsertBefore(added_simulate);

[fschneider, 2012/04/13 12:38:00]

I think this is a little problematic and can be simplified: You only need an
HSimulate if the HAdd has side-effects (i.e. if it is a tagged-add). In this
case it is not safe to move it around in any case, since it can have side
effects.)

If you limit yourself to index expressions a[i+c] where the index i+c is an
integer add (hadd->representation()->IsInteger32()), then you don't need to
worry about the HSimulate at all and you can insert it anywhere without creating
a new HSimulate.

[Sven Panne, 2012/04/13 12:49:33]

Good point, but I suggest using 'foo->HasObservableSideEffects()' instead of
'foo->representation()->IsInteger32()'. The side effects are the real reason for
disallowing this, and it's more consistent with HInstruction::Verify().

[Massi, 2012/04/17 10:56:58]

I ended up asserting that the index representation is int32 because it must be
true and it's enough for what we need.

+      } else {
+        added_index_->SetOperandAt(1, new_check_index->left());
+        added_index_->SetOperandAt(2, new_check_index->right());
+      }
+      Check()->SetOperandAt(0, added_index_);
+      RemoveCheck(new_check);
+      offset_ = new_offset;
+    }
+  }
+
+  BoundsCheckBbData(BoundsCheckKey* key, int32_t offset, HBasicBlock* bb,

[fschneider, 2012/04/13 12:38:00]

style-nit: One parameter pre line in definitions and declarations.

[Massi, 2012/04/17 10:56:58]

Done.

+                     HBoundsCheck* check, BoundsCheckBbData* next_in_bb,
+                     BoundsCheckBbData* father_in_dt) {
+    key_ = key;
+    offset_ = offset;
+    basic_block_ = bb;
+    check_ = check;
+    if (check->next()->IsSimulate()) {

[Sven Panne, 2012/04/13 11:38:06]

Using a ternary operator here and using initializer syntax instead is more
"C++"-like.

[Massi, 2012/04/17 10:56:58]

Done.

+      check_simulate_ = HSimulate::cast(check->next());
+    } else {
+      check_simulate_ = NULL;
+    }
+    added_index_ = NULL;
+    next_in_basic_block_ = next_in_bb;
+    father_in_dominator_tree_ = father_in_dt;
+  }
+
+ private:
+  BoundsCheckKey* key_;
+  int32_t offset_;
+  HBasicBlock* basic_block_;
+  HBoundsCheck* check_;
+  HSimulate* check_simulate_;
+  HAdd* added_index_;
+  BoundsCheckBbData* next_in_basic_block_;
+  BoundsCheckBbData* father_in_dominator_tree_;
+};
+
+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();
+}
+
+class BoundsCheckTable : private ZoneHashMap {
+ public:
+  BoundsCheckBbData** LookupOrInsert(BoundsCheckKey* key) {
+    intptr_t hash = key->Hash();

[Sven Panne, 2012/04/13 11:38:06]

Wrong type, but this is nicer when inlined, anyway.

[Massi, 2012/04/17 10:56:58]

Done.

+    ZoneHashMap::Entry* entry = Lookup(key, hash, true);
+    return reinterpret_cast<BoundsCheckBbData**>(&(entry->value));
+  }
+
+  void Insert(BoundsCheckKey* key, BoundsCheckBbData* data) {
+    intptr_t hash = key->Hash();

[Sven Panne, 2012/04/13 11:38:06]

Inline again.

[Massi, 2012/04/17 10:56:58]

Done.

+    ZoneHashMap::Entry* entry = Lookup(key, hash, true);

[Sven Panne, 2012/04/13 11:38:06]

No need to name this explicitly.

[Massi, 2012/04/17 10:56:58]

Done.

+    entry->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()) {

[Sven Panne, 2012/04/13 11:38:06]

'if (!i->IsBoundsCheck()) continue;' reduces nesting a bit and is clearer IMHO.

[Massi, 2012/04/17 10:56:58]

Done.

+      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...
+      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()) {
+        BoundsCheckBbData::RemoveCheck(check);

[Sven Panne, 2012/04/13 11:38:06]

This will probably be something like 'check->Remove()' or whatever the function
will be called.

[Massi, 2012/04/17 10:56:58]

Done.

+        isolate()->counters()->array_bounds_checks_removed()->Increment();
+      } else if (data->BasicBlock() == bb) {
+        data->CoverCheck(check, offset);
+        isolate()->counters()->array_bounds_checks_removed()->Increment();

[Sven Panne, 2012/04/13 11:38:06]

I don't think that the increment here is correct, because the check is removed
conditionally.

[Massi, 2012/04/17 10:56:58]

Done.

+      } 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