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;
+    bool is_sub = false;
+
+    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();
-    }
-  }
+    } else if (check->index()->IsSub()) {
+      HSub* index = HSub::cast(check->index());
+      is_sub = true;
+      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();
+      }
+    }
+
+    if (constant != NULL && constant->HasInteger32Value()) {
+      *offset = is_sub ? - constant->Integer32Value()

[fschneider, 2012/04/25 09:40:48]

I'd break this expression like this:

*offset = is_sub ? -constant->Integer32Value()
                 : constant->Integer32Value();

[Massi, 2012/04/25 12:19:19]

Done.

+          : constant->Integer32Value();
+    } else {
+      *offset = 0;
+      index_base = check->index();
+    }
+
+    return new(zone) BoundsCheckKey(index_base, check->length());
+  }
+
+ private:
+  BoundsCheckKey(HValue* index_base, HValue* length) {

[fschneider, 2012/04/25 09:40:48]

This is may be rewritten shorter using an initializer list:

BoundsCheckKey(HValue* index_base, HValue* length)
  : index_base_(index_base),
    length_(length) { }

[Massi, 2012/04/25 12:19:19]

Done but with the colon be on the 1st line: is it ok anyway?

[Massi, 2012/04/25 12:29:16]

Fixed this and another one...

+    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() const { return key_; }
+  int32_t LowerOffset() const { return lower_offset_; }
+  int32_t UpperOffset() const { return upper_offset_; }
+  HBasicBlock* BasicBlock() const { return basic_block_; }
+  HBoundsCheck* Check() const { return check_; }
+  BoundsCheckBbData* NextInBasicBlock() const { return next_in_bb_; }
+  BoundsCheckBbData* FatherInDominatorTree() const { return father_in_dt_; }
+
+  bool OffsetIsCovered(int32_t offset) const {
+    return offset >= LowerOffset() && offset <= UpperOffset();
+  }
+
+  // This method removes new_check and modifies the current check so that it
+  // also "covers" what new_check covered.
+  // The obvious precondition is that new_check follows Check() in the
+  // same basic block, and that new_offset is not covered (otherwise we
+  // could simply remove new_check).
+  // As a consequence LowerOffset() or UpperOffset() change (the covered
+  // range grows).
+  //
+  // In the general case the check covering the current range should be like
+  // these two checks:
+  // 0 <= Key()->IndexBase() + LowerOffset()
+  // Key()->IndexBase() + UpperOffset() < Key()->Length()
+  //
+  // We can transform the second check like this:
+  // Key()->IndexBase() + LowerOffset() <
+  //     Key()->Length() + (LowerOffset() - UpperOffset())
+  // so we can handle both checks with a single unsigned comparison.
+  //
+  // The bulk of this method changes Check()->index() and Check()->length()
+  // replacing them with new HAdd instructions to perform the transformation
+  // described above.
+  void CoverCheck(HBoundsCheck* new_check,
+                  int32_t new_offset) {
+    ASSERT(new_check->index()->representation().IsInteger32());
+
+    if (new_offset > upper_offset_) {
+      upper_offset_ = new_offset;
+    } else if (new_offset < lower_offset_) {
+      lower_offset_ = new_offset;
+    } else {
+      ASSERT(false);
+    }
+
+    BuildOffsetAdd(&added_index_,
+                   &added_index_offset_,
+                   Key()->IndexBase(),
+                   new_check->index()->representation(),
+                   lower_offset_);
+    Check()->SetOperandAt(0, added_index_);
+    BuildOffsetAdd(&added_length_,
+                   &added_length_offset_,
+                   Key()->Length(),
+                   new_check->length()->representation(),
+                   lower_offset_ - upper_offset_);
+    Check()->SetOperandAt(1, added_length_);
+
+    new_check->DeleteAndReplaceWith(NULL);
+  }
+
+  void RemoveZeroOperations() {
+    RemoveZeroAdd(&added_index_, &added_index_offset_);
+    RemoveZeroAdd(&added_length_, &added_length_offset_);
+  }
+
+  BoundsCheckBbData(BoundsCheckKey* key,
+                    int32_t lower_offset,
+                    int32_t upper_offset,
+                    HBasicBlock* bb,
+                    HBoundsCheck* check,
+                    BoundsCheckBbData* next_in_bb,
+                    BoundsCheckBbData* father_in_dt) :
+                       key_(key),
+                       lower_offset_(lower_offset),
+                       upper_offset_(upper_offset),
+                       basic_block_(bb),
+                       check_(check),
+                       added_index_offset_(NULL),
+                       added_index_(NULL),
+                       added_length_offset_(NULL),
+                       added_length_(NULL),
+                       next_in_bb_(next_in_bb),
+                       father_in_dt_(father_in_dt) { }
+
+ private:
+  BoundsCheckKey* key_;
+  int32_t lower_offset_;
+  int32_t upper_offset_;
+  HBasicBlock* basic_block_;
+  HBoundsCheck* check_;
+  HConstant* added_index_offset_;
+  HAdd* added_index_;
+  HConstant* added_length_offset_;
+  HAdd* added_length_;
+  BoundsCheckBbData* next_in_bb_;
+  BoundsCheckBbData* father_in_dt_;
+
+  void BuildOffsetAdd(HAdd** add,
+                      HConstant** constant,
+                      HValue* original_value,
+                      Representation representation,
+                      int32_t new_offset) {
+    HConstant* new_constant = new(BasicBlock()->zone())
+        HConstant(Handle<Object>(Smi::FromInt(new_offset)),
+                  Representation::Integer32());
+    if (*add == NULL) {
+      new_constant->InsertBefore(Check());
+      *add = new(BasicBlock()->zone()) HAdd(NULL,
+                                            original_value,

[fschneider, 2012/04/25 09:40:48]

Don't the arguments fit on one line?

[Massi, 2012/04/25 12:19:19]

No: 81 chars wide :-(

+                                            new_constant);
+      (*add)->AssumeRepresentation(representation);
+      (*add)->InsertBefore(Check());
+    } else {
+      new_constant->InsertBefore(*add);
+      (*constant)->DeleteAndReplaceWith(new_constant);
+    }
+    *constant = new_constant;
+  }
+
+  void RemoveZeroAdd(HAdd** add,
+                     HConstant** constant) {

[fschneider, 2012/04/25 09:40:48]

Fits on the previous line?

[Massi, 2012/04/25 12:19:19]

Done.

+    if (*add != NULL && (*constant)->Integer32Value() == 0) {
+      (*add)->DeleteAndReplaceWith((*add)->left());
+      (*constant)->Unlink();

[fschneider, 2012/04/25 09:40:48]

We use normally the helper DeleteAndReplaceWith(NULL) for deleting instructions
from the graph. It has some additional assertions that the value does not have
any uses left.

[Massi, 2012/04/25 12: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();
 }
 
 
+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/25 09:40:48]

Fits on the previous line.

[Massi, 2012/04/25 12: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();
+    if (!FLAG_array_bounds_checks_elimination) continue;
+
+    int32_t offset;
+    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,

[fschneider, 2012/04/25 09:40:48]

Since HGraph already has a zone() accessor, you can just write:

new (zone())

[Massi, 2012/04/25 12:19:19]

Done.

+                                                       offset,
+                                                       offset,
+                                                       bb,
+                                                       check,
+                                                       bb_data_list,
+                                                       NULL);
+      *data_p = bb_data_list;
+    } else if (data->OffsetIsCovered(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 {
+      int32_t new_lower_offset = offset < data->LowerOffset() ? offset

[fschneider, 2012/04/25 09:40:48]

Maybe the expressions here better readable as:

int32_t new_lower_offset = offset < data->LowerOffset()
    ? offset
    : data->LowerOffset();

[Massi, 2012/04/25 12:19:19]

Done.

+          : data->LowerOffset();
+      int32_t new_upper_offset = offset > data->UpperOffset() ? offset
+          : data->UpperOffset();
+      bb_data_list = new(bb->zone()) BoundsCheckBbData(key,
+                                                       new_lower_offset,
+                                                       new_upper_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()) {
+    data->RemoveZeroOperations();
+    if (data->FatherInDominatorTree()) {
+      table->Insert(data->Key(), data->FatherInDominatorTree());
+    } else {
+      table->Delete(data->Key());
+    }
+  }
+}
+
+
+void HGraph::EliminateRedundantBoundsChecks() {
+  HPhase phase("H_Eliminate bounds checks", this);
+  AssertNoAllocation no_gc;

[fschneider, 2012/04/25 09:40:48]

Why would you want to assert no allocation here? It does not hurt, but does not
seem necessary.

We use this assert in places where we use raw pointers to the JS heap instead of
handles (e.g. many function in objects.cc, runtime.cc).

[Massi, 2012/04/25 12:19:19]

It is necessary: I was hitting asserts without it.
This happened computing key hashes calling HConstant::Hashcode().

[fschneider, 2012/04/26 09:35:49]

I don't believe it is necessary. If anything it will trigger an assert once you
allocate a heap object on the JS heap in your code.
I don't this is currently the case, and even if it would, we can deal with
allocations inside the compiler since everything is handlified.

+  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);
   current_block()->AddSimulate(ast_id);
@@ skipping 5631 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal