Check elimination improvement: propagation of state through phis is supported, CheckMap narrowing i…

src/hydrogen-check-elimination.cc

Index: src/hydrogen-check-elimination.cc
diff --git a/src/hydrogen-check-elimination.cc b/src/hydrogen-check-elimination.cc
index cd002a1d5c80a5d9a76ee4eded2f889461958dc6..c54a08051b7f9eccb82f3aa603951cd4d35e441f 100644
--- a/src/hydrogen-check-elimination.cc
+++ b/src/hydrogen-check-elimination.cc
@@ -48,12 +48,13 @@ typedef UniqueSet<Map>* MapSet;
 
 struct HCheckTableEntry {
   HValue* object_;  // The object being approximated. NULL => invalid entry.
-  HValue* check_;   // The last check instruction.
-  MapSet maps_;     // The set of known maps for the object.
+  HInstruction* check_;  // The last check instruction.
+  MapSet maps_;          // The set of known maps for the object.
+  bool remove_at_compation_;

[titzer, 2014/02/05 11:47:46]

I don't think we need this; see below

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

 };
 
 
-// The main datastructure used during check elimination, which stores a
+// The main data structure used during check elimination, which stores a
 // set of known maps for each object.
 class HCheckTable : public ZoneObject {
  public:
@@ -121,15 +122,34 @@ class HCheckTable : public ZoneObject {
     HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* old_entry = &entries_[i];
+      ASSERT(!old_entry->remove_at_compation_);
       HCheckTableEntry* new_entry = &copy->entries_[i];
       // TODO(titzer): keep the check if this block dominates the successor?
       new_entry->object_ = old_entry->object_;
       new_entry->check_ = NULL;
       new_entry->maps_ = old_entry->maps_->Copy(phase_->zone());
+      new_entry->remove_at_compation_ = false;
     }
     copy->cursor_ = cursor_;
     copy->size_ = size_;
 
+    // Create entries for succ block's phis.
+    if (succ->phis()->length() > 0) {
+      int pred_index = succ->PredecessorIndexOf(from_block);
+      for (int phi_index = 0;
+           phi_index < succ->phis()->length();
+           ++phi_index) {
+        HPhi* phi = succ->phis()->at(phi_index);
+        HValue* phi_operand = phi->OperandAt(pred_index);
+
+        HCheckTableEntry* pred_entry = copy->Find(phi_operand);
+        if (pred_entry != NULL) {
+          // Create an entry for a phi in the table.
+          copy->Insert(phi, NULL, pred_entry->maps_);

[titzer, 2014/02/05 11:47:46]

I think you want to make a copy of pred_entry->maps_, since these sets are
mutable and the new entry for the phi would alias the maps for the entry that
was just found.

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

+        }
+      }
+    }
+
     // Branch-sensitive analysis for certain comparisons may add more facts
     // to the state for the successor on the true branch.
     bool learned = false;
@@ -184,10 +204,10 @@ class HCheckTable : public ZoneObject {
   }
 
   // Global analysis: Merge this state with the other incoming state.
-  HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
-                     HBasicBlock* that_block, Zone* zone) {
-    if (that_block->IsReachable()) {
-      if (that->size_ == 0) {
+  HCheckTable* Merge(HBasicBlock* succ, HCheckTable* pred,
+                     HBasicBlock* pred_block, Zone* zone) {
+    if (pred_block->IsReachable()) {
+      if (pred->size_ == 0) {
         // If the other state is empty, simply reset.
         size_ = 0;
         cursor_ = 0;
@@ -195,25 +215,57 @@ class HCheckTable : public ZoneObject {
         bool compact = false;
         for (int i = 0; i < size_; i++) {
           HCheckTableEntry* this_entry = &entries_[i];
-          HCheckTableEntry* that_entry = that->Find(this_entry->object_);
-          if (that_entry == NULL) {
-            this_entry->object_ = NULL;
+          if (this_entry->object_->IsPhi() &&
+              this_entry->object_->block() == succ) {
+            // Entries corresponding to succ block's phis are processed
+            // separately.
+            continue;

[titzer, 2014/02/05 11:47:46]

I think in this case you can just immediately process the phi. Look up the
corresponding phi input from pred and union into the entry for this phi. If
there is no entry for the corresponding phi input, kill this entry.

Thus you need only one pass through this table and don't need to iterate over
succ's phi list.

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

+          }
+          HCheckTableEntry* pred_entry = pred->Find(this_entry->object_);
+          if (pred_entry == NULL) {
+            // This entry should be removed, but keep it till the end of
+            // merging as the value could be used as input for one of the
+            // for succ block's phis.
+            this_entry->remove_at_compation_ = true;
             compact = true;
           } else {
             this_entry->maps_ =
-                this_entry->maps_->Union(that_entry->maps_, phase_->zone());
-            if (this_entry->check_ != that_entry->check_) {
+                this_entry->maps_->Union(pred_entry->maps_, phase_->zone());
+            if (this_entry->check_ != pred_entry->check_) {
               this_entry->check_ = NULL;
             }
             ASSERT(this_entry->maps_->size() > 0);
           }
         }
+        // Process succ block's phis.
+        if (succ->phis()->length() > 0) {
+          int pred_index = succ->PredecessorIndexOf(pred_block);
+
+          for (int phi_index = 0;
+               phi_index < succ->phis()->length();
+               ++phi_index) {
+            HPhi* phi = succ->phis()->at(phi_index);
+            HValue* phi_operand = phi->OperandAt(pred_index);
+
+            HCheckTableEntry* phi_entry = Find(phi);
+            if (phi_entry != NULL) {
+              HCheckTableEntry* pred_entry = pred->Find(phi_operand);
+              if (pred_entry == NULL) {
+                phi_entry->object_ = NULL;
+                compact = true;
+              } else {
+                phi_entry->maps_ =
+                    phi_entry->maps_->Union(pred_entry->maps_, phase_->zone());
+              }
+            }
+          }
+        }
         if (compact) Compact();
       }
     }
     if (FLAG_trace_check_elimination) {
       PrintF("B%d checkmaps-table merged with B%d table:\n",
-             succ->block_id(), that_block->block_id());
+             succ->block_id(), pred_block->block_id());
       Print();
     }
     return this;
@@ -244,14 +296,42 @@ class HCheckTable : public ZoneObject {
         }
         return;
       }
-      i = i->Intersect(a, phase_->zone());
-      if (i->size() == 0) {
+      MapSet intersection = i->Intersect(a, phase_->zone());
+      if (intersection->size() == 0) {
         // Intersection is empty; probably megamorphic, which is likely to
         // deopt anyway, so just leave things as they are.
         INC_STAT(empty_);
       } else {
-        // TODO(titzer): replace the first check with a more strict check
-        INC_STAT(narrowed_);
+        // Update set of maps in the entry.
+        entry->maps_ = intersection;
+        if (intersection->size() != i->size()) {
+          // Narrow set of maps in the second check maps instruction.
+          HGraph* graph = instr->block()->graph();
+          HCheckMaps* new_check_maps =
+              HCheckMaps::New(graph->zone(), NULL, instr->value(),
+                              intersection, instr->typecheck());
+          if (entry->check_ != NULL &&
+              entry->check_->block() == instr->block()) {
+            // There is a check in the same block so replace it with a more
+            // strict check and eliminate the second check entirely.
+            new_check_maps->InsertBefore(entry->check_);
+            entry->check_->DeleteAndReplaceWith(new_check_maps);
+            TRACE(("Check #%d narrowed to #%d\n",
+                entry->check_->id(), new_check_maps->id()));
+
+          } else {
+            new_check_maps->InsertBefore(instr);
+          }
+          TRACE(("CheckMaps #%d for #%d narrowed to #%d:\n",
+              instr->id(), instr->value()->id(), new_check_maps->id()));
+          instr->DeleteAndReplaceWith(new_check_maps);
+          entry->check_ = new_check_maps;
+
+          if (FLAG_trace_check_elimination) {
+            Print();
+          }
+          INC_STAT(narrowed_);
+        }
       }
     } else {
       // No entry; insert a new one.
@@ -390,7 +470,7 @@ class HCheckTable : public ZoneObject {
     // First, compact the array in place.
     int max = size_, dest = 0, old_cursor = cursor_;
     for (int i = 0; i < max; i++) {
-      if (entries_[i].object_ != NULL) {
+      if (entries_[i].object_ != NULL && !entries_[i].remove_at_compation_) {
         if (dest != i) entries_[dest] = entries_[i];
         dest++;
       } else {
@@ -422,7 +502,9 @@ class HCheckTable : public ZoneObject {
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* entry = &entries_[i];
       ASSERT(entry->object_ != NULL);
-      PrintF("  checkmaps-table @%d: object #%d ", i, entry->object_->id());
+      PrintF("  checkmaps-table @%d: %s #%d ", i,
+             entry->object_->IsPhi() ? "phi" : "object",
+             entry->object_->id());
       if (entry->check_ != NULL) {
         PrintF("check #%d ", entry->check_->id());
       }
@@ -441,7 +523,7 @@ class HCheckTable : public ZoneObject {
     for (int i = size_ - 1; i >= 0; i--) {
       // Search from most-recently-inserted to least-recently-inserted.
       HCheckTableEntry* entry = &entries_[i];
-      ASSERT(entry->object_ != NULL);
+      if (entry->object_ == NULL) continue;

[titzer, 2014/02/05 11:47:46]

Why did this invariant change?

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

       if (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
     }
     return NULL;
@@ -463,6 +545,7 @@ class HCheckTable : public ZoneObject {
     entry->object_ = object;
     entry->check_ = check;
     entry->maps_ = maps;
+    entry->remove_at_compation_ = false;
     // If the table becomes full, wrap around and overwrite older entries.
     if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
     if (size_ < kMaxTrackedObjects) size_++;