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 ae11042ba1e449b3c33b2d036ca36477165142d6..627a1adc61fe6c1a6dddc4fa7399aaadbe64fdca 100644
--- a/src/hydrogen-check-elimination.cc
+++ b/src/hydrogen-check-elimination.cc
@@ -117,7 +117,7 @@ class HCheckTable : public ZoneObject {
   }
 
   // Global analysis: Copy state to successor block.
-  HCheckTable* Copy(HBasicBlock* succ, Zone* zone) {
+  HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
     HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* old_entry = &entries_[i];
@@ -130,8 +130,11 @@ class HCheckTable : public ZoneObject {
     copy->cursor_ = cursor_;
     copy->size_ = size_;
 
+    copy->InheritPhiOperands(succ, this, from_block, COPY, zone);
+
     // Branch-sensitive analysis for certain comparisons may add more facts
     // to the state for the successor on the true branch.
+    bool learned = false;
     HControlInstruction* end = succ->predecessors()->at(0)->end();
     if (succ->predecessors()->length() == 1 && end->SuccessorAt(0) == succ) {
       if (end->IsCompareMap()) {
@@ -146,6 +149,7 @@ class HCheckTable : public ZoneObject {
           list->Add(cmp->map(), phase_->zone());
           entry->maps_ = list;
         }
+        learned = true;
       } else if (end->IsCompareObjectEqAndBranch()) {
         // Learn on the true branch of if(CmpObjectEq(x, y)).
         HCompareObjectEqAndBranch* cmp =
@@ -165,37 +169,99 @@ class HCheckTable : public ZoneObject {
           le->maps_ = intersect;
           re->maps_ = intersect->Copy(zone);
         }
+        learned = true;
       }
       // Learning on false branches requires storing negative facts.
     }
 
+    if (FLAG_trace_check_elimination) {
+      PrintF("B%d checkmaps-table %s from B%d:\n",
+             succ->block_id(),
+             learned ? "learned" : "copied",
+             from_block->block_id());
+      copy->Print();
+    }
+
     return copy;
   }
 
   // Global analysis: Merge this state with the other incoming state.
-  HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that, Zone* zone) {
-    if (that->size_ == 0) {
-      // If the other state is empty, simply reset.
-      size_ = 0;
-      cursor_ = 0;
-      return this;
-    }
-    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;
-        compact = true;
+  void Merge(HBasicBlock* succ, HCheckTable* that,
+             HBasicBlock* that_block, Zone* zone) {
+    if (that_block->IsReachable()) {
+      if (that->size_ == 0) {
+        // If the other state is empty, simply reset.
+        size_ = 0;
+        cursor_ = 0;
       } else {
-        this_entry->maps_ = this_entry->maps_->Union(
-            that_entry->maps_, phase_->zone());
-        if (this_entry->check_ != that_entry->check_) this_entry->check_ = NULL;
-        ASSERT(this_entry->maps_->size() > 0);
+        InheritPhiOperands(succ, that, that_block, MERGE, zone);
+
+        bool compact = false;
+        for (int i = 0; i < size_; i++) {
+          HCheckTableEntry* this_entry = &entries_[i];
+          HCheckTableEntry* that_entry = that->Find(this_entry->object_);
+          // Keep those phis in the table that dominate succ block.
+          if (that_entry == NULL) {
+            if (!this_entry->object_->IsPhi() ||
+                !this_entry->object_->block()->EqualToOrDominates(succ)) {
+              this_entry->object_ = NULL;
+              compact = true;
+            }
+          } else {
+            this_entry->maps_ =
+                this_entry->maps_->Union(that_entry->maps_, phase_->zone());
+            if (this_entry->check_ != that_entry->check_) {
+              this_entry->check_ = NULL;
+            }
+            ASSERT(this_entry->maps_->size() > 0);
+          }
+        }
+        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());
+      Print();
+    }
+  }
+
+  enum InheritPhiOperandsMode { COPY, MERGE };
+  void InheritPhiOperands(HBasicBlock* succ, HCheckTable* that,
+                          HBasicBlock* that_block, InheritPhiOperandsMode mode,
+                          Zone* zone) {
+    if (succ->predecessors()->length() == 1) return;
+
+    int pred_index = succ->PredecessorIndexOf(that_block);
+
+    for (int i = 0; i < that->size_; i++) {
+      HCheckTableEntry* that_entry = &that->entries_[i];
+      if (that_entry->object_ != NULL) {
+        HPhi* phi = NULL;
+        for (int phi_index = 0;
+             phi_index < succ->phis()->length();
+             ++phi_index) {
+          HPhi* tmp_phi = succ->phis()->at(phi_index);
+          if (tmp_phi->OperandAt(pred_index) == that_entry->object_) {
+            phi = tmp_phi;
+            break;
+          }
+        }
+
+        if (phi != NULL) {
+          // Found a |phi| with operand equal to |that_entry->object_|.
+          HCheckTableEntry* phi_entry = (mode == MERGE) ? Find(phi) : NULL;
+          if (phi_entry == NULL) {
+            // Create an entry for a phi in the table.
+            Insert(phi, NULL, that_entry->maps_);
+          } else {
+            phi_entry->maps_ =
+                phi_entry->maps_->Union(that_entry->maps_, phase_->zone());
+          }
+        }
       }
     }
-    if (compact) Compact();
-    return this;
   }
 
   void ReduceCheckMaps(HCheckMaps* instr) {
@@ -208,21 +274,49 @@ class HCheckTable : public ZoneObject {
       if (a->IsSubset(i)) {
         // The first check is more strict; the second is redundant.
         if (entry->check_ != NULL) {
+          TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
+              instr->id(), instr->block()->block_id(), entry->check_->id()));
           instr->DeleteAndReplaceWith(entry->check_);
           INC_STAT(redundant_);
         } else {
-          instr->DeleteAndReplaceWith(instr->value());
+          TRACE(("Marking redundant CheckMaps #%d at B%d as dead\n",
+              instr->id(), instr->block()->block_id()));
+          // Mark check as dead but leave it in the graph as a checkpoint for
+          // subsequent checks.
+          instr->SetFlag(HValue::kIsDead);
+          entry->check_ = instr;
           INC_STAT(removed_);
         }
         return;
       }
-      i = i->Intersect(a, phase_->zone());
-      if (i->size() == 0) {
+      MapSet narrowed_maps = i->Intersect(a, phase_->zone());

[titzer, 2014/01/23 18:40:55]

Would prefer the name "intersection" instead of narrowed_maps

[Igor Sheludko, 2014/01/29 12:27:13]

Done.

+      if (narrowed_maps->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
+        // Narrow set of maps in the second check and replace the first
+        // check with a more strict one.
+        entry->maps_ = narrowed_maps;
+        if (narrowed_maps->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(),
+                              narrowed_maps, instr->typecheck());
+          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);

[titzer, 2014/01/23 18:40:55]

I think you want to replace both entry->check_ (if it exists) and instr with the
new check. If the entry->check_ exists, then insert the new check before it.

[Igor Sheludko, 2014/01/29 12:27:13]

Done.

+          entry->check_ = new_check_maps;
+        } else {
+          TRACE(("CheckMaps #%d for #%d narrowed:\n",
+                 instr->id(), instr->value()->id()));

[titzer, 2014/01/23 18:40:55]

In this case, you haven't actually changed anything, so the trace output would
be incorrect.

[Igor Sheludko, 2014/01/29 12:27:13]

Done.

+          entry->check_ = instr;
+        }
+        if (FLAG_trace_check_elimination) {
+          Print();
+        }
         INC_STAT(narrowed_);
       }
     } else {