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..2d240b22690cb2b2aa46eb2f6a9d2aeeda8aa860 100644
--- a/src/hydrogen-check-elimination.cc
+++ b/src/hydrogen-check-elimination.cc
@@ -48,12 +48,12 @@ 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.
 };
 
 
-// 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:
@@ -130,6 +130,8 @@ 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;
@@ -192,13 +194,19 @@ class HCheckTable : public ZoneObject {
         size_ = 0;
         cursor_ = 0;
       } else {
+        InheritPhiOperands(succ, that, that_block, MERGE, zone);

[titzer, 2014/02/04 13:12:26]

Why don't you process the phis after first merging the tables? That way, you can
just go through the phis of this block and then insert (in the case of COPY) or
union (in the case of MERGE) their entries with the entries from the incoming
block. I think that would be significantly simpler, and potentially faster.

[Igor Sheludko, 2014/02/05 11:28:01]

Good idea!

+
         bool compact = false;
         for (int i = 0; i < size_; i++) {
           HCheckTableEntry* this_entry = &entries_[i];

[titzer, 2014/02/04 13:12:26]

Using the above suggestion, you can simply retain any entries in this table for
phis that are defined in "succ". Then you don't need the dominance check for the
other phis, since "that" can't have entries for anything that doesn't dominate
"succ" (i.e. they are handled implicitly).

[Igor Sheludko, 2014/02/05 11:28:01]

Done.

           HCheckTableEntry* that_entry = that->Find(this_entry->object_);
+          // Keep those phis in the table that dominate succ block.
           if (that_entry == NULL) {
-            this_entry->object_ = NULL;
-            compact = true;
+            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());
@@ -219,6 +227,43 @@ class HCheckTable : public ZoneObject {
     return this;
   }
 
+  enum InheritPhiOperandsMode { COPY, MERGE };
+  void InheritPhiOperands(HBasicBlock* succ, HCheckTable* that,
+                          HBasicBlock* that_block, InheritPhiOperandsMode mode,
+                          Zone* zone) {
+    if (succ->predecessors()->length() == 1) return;

[titzer, 2014/02/04 13:12:26]

I think you want to check succ->phis()->length() == 0 for the early return here.

[Igor Sheludko, 2014/02/05 11:28:01]

Done.

+
+    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());
+          }
+        }
+      }
+    }
+  }
+
   void ReduceCheckMaps(HCheckMaps* instr) {
     HValue* object = instr->value()->ActualValue();
     HCheckTableEntry* entry = Find(object);
@@ -244,14 +289,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.