More check elimination improvements including partial learning on false branches of CompareMap and …

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 e393234067095408e1a68bb107212f9ef90903e9..7672c1bc6dee109f1ffc226322a21c1a6c7fafbc 100644
--- a/src/hydrogen-check-elimination.cc
+++ b/src/hydrogen-check-elimination.cc
@@ -62,7 +62,8 @@ class HCheckTable : public ZoneObject {
   explicit HCheckTable(HCheckEliminationPhase* phase)
     : phase_(phase),
       cursor_(0),
-      size_(0) {
+      size_(0),
+      unreachable_(false) {
   }
 
   // The main processing of instructions.
@@ -119,13 +120,24 @@ class HCheckTable : public ZoneObject {
   // Global analysis: Copy state to successor block.
   HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
     HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
+    if (from_block->IsUnreachable() || succ->IsUnreachable()) {
+      copy->unreachable_ = true;
+      return copy;
+    }
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* old_entry = &entries_[i];
       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());
+      // Keep the check if the existing check's block dominates the successor.
+      if (old_entry->check_ != NULL &&
+          old_entry->check_->block()->Dominates(succ)) {
+        new_entry->check_ = old_entry->check_;
+      } else {
+        // Leave it NULL till we meet a new check instruction for this object
+        // in the control flow.
+        new_entry->check_ = NULL;
+      }
     }
     copy->cursor_ = cursor_;
     copy->size_ = size_;
@@ -150,22 +162,32 @@ class HCheckTable : public ZoneObject {
     // 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) {
+    HBasicBlock* pred_block = succ->predecessors()->at(0);
+    HControlInstruction* end = pred_block->end();
+    if (pred_block->IsReachable() && succ->predecessors()->length() == 1) {

[Toon Verwaest, 2014/02/11 14:54:04]

I think we shouldn't explicitly care about the number of predecessors, but
rather just copy information from all reachable blocks down and merge it in the
regular way. If the length of reachable predecessors is one, it will
automagically do what you expect.

+      bool is_true_branch = end->SuccessorAt(0) == succ;
       if (end->IsCompareMap()) {
-        // Learn on the true branch of if(CompareMap(x)).
         HCompareMap* cmp = HCompareMap::cast(end);
         HValue* object = cmp->value()->ActualValue();
         HCheckTableEntry* entry = copy->Find(object);
-        if (entry == NULL) {
-          copy->Insert(object, cmp->map());
+        if (is_true_branch) {
+          // Learn on the true branch of if(CompareMap(x)).
+          if (entry == NULL) {
+            copy->Insert(object, cmp, cmp->map());
+          } else {
+            MapSet list = new(phase_->zone()) UniqueSet<Map>();
+            list->Add(cmp->map(), phase_->zone());
+            entry->maps_ = list;
+            entry->check_ = cmp;
+          }
         } else {
-          MapSet list = new(phase_->zone()) UniqueSet<Map>();
-          list->Add(cmp->map(), phase_->zone());
-          entry->maps_ = list;
+          // Learn on the false branch of if(CompareMap(x)).
+          if (entry != NULL) {
+            entry->maps_->Remove(cmp->map());
+          }
         }
         learned = true;
-      } else if (end->IsCompareObjectEqAndBranch()) {
+      } else if (is_true_branch && end->IsCompareObjectEqAndBranch()) {
         // Learn on the true branch of if(CmpObjectEq(x, y)).
         HCompareObjectEqAndBranch* cmp =
           HCompareObjectEqAndBranch::cast(end);
@@ -203,42 +225,46 @@ class HCheckTable : public ZoneObject {
   // Global analysis: Merge this state with the other incoming state.
   HCheckTable* Merge(HBasicBlock* succ, HCheckTable* that,
                      HBasicBlock* pred_block, Zone* zone) {
-    if (pred_block->IsReachable()) {
-      if (that->size_ == 0) {
-        // If the other state is empty, simply reset.
-        size_ = 0;
-        cursor_ = 0;
-      } else {
-        int pred_index = succ->PredecessorIndexOf(pred_block);
-        bool compact = false;
-        for (int i = 0; i < size_; i++) {
-          HCheckTableEntry* this_entry = &entries_[i];
-          HCheckTableEntry* that_entry;
-          if (this_entry->object_->IsPhi() &&
-              this_entry->object_->block() == succ) {
-            HPhi* phi = HPhi::cast(this_entry->object_);
-            HValue* phi_operand = phi->OperandAt(pred_index);
-            that_entry = that->Find(phi_operand);
+    if (pred_block->IsUnreachable() || that->unreachable_) return this;
+    if (unreachable_) {
+      return that->Copy(succ, pred_block, zone);
+    }
 
-          } else {
-            that_entry = that->Find(this_entry->object_);
-          }
+    if (that->size_ == 0) {
+      // If the other state is empty, simply reset.
+      size_ = 0;
+      cursor_ = 0;
+    } else {
+      int pred_index = succ->PredecessorIndexOf(pred_block);
+      bool compact = false;
+      for (int i = 0; i < size_; i++) {
+        HCheckTableEntry* this_entry = &entries_[i];
+        HCheckTableEntry* that_entry;
+        if (this_entry->object_->IsPhi() &&
+            this_entry->object_->block() == succ) {
+          HPhi* phi = HPhi::cast(this_entry->object_);
+          HValue* phi_operand = phi->OperandAt(pred_index);
+          that_entry = that->Find(phi_operand);
 
-          if (that_entry == NULL) {
-            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);
+        } else {
+          that_entry = that->Find(this_entry->object_);
+        }
+
+        if (that_entry == NULL) {
+          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 (compact) Compact();
     }
+
     if (FLAG_trace_check_elimination) {
       PrintF("B%d checkmaps-table merged with B%d table:\n",
              succ->block_id(), pred_block->block_id());
@@ -349,22 +375,32 @@ class HCheckTable : public ZoneObject {
     HValue* object = instr->value()->ActualValue();
     // Match a HCheckMapValue(object, HConstant(map))
     Unique<Map> map = MapConstant(instr->map());
-    MapSet maps = FindMaps(object);
-    if (maps != NULL) {
+
+    HCheckTableEntry* entry = Find(object);
+    if (entry != NULL) {
+      MapSet maps = entry->maps_;
       if (maps->Contains(map)) {
         if (maps->size() == 1) {
           // Object is known to have exactly this map.
-          instr->DeleteAndReplaceWith(NULL);
+          if (entry->check_ != NULL) {
+            instr->DeleteAndReplaceWith(entry->check_);
+          } else {
+            // 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_);
         } else {
           // Only one map survives the check.
           maps->Clear();
           maps->Add(map, phase_->zone());
+          entry->check_ = instr;
         }
       }
     } else {
       // No prior information.
-      Insert(object, map);
+      Insert(object, instr, map);
     }
   }
 
@@ -381,12 +417,12 @@ class HCheckTable : public ZoneObject {
     if (instr->has_transition()) {
       // This store transitions the object to a new map.
       Kill(object);
-      Insert(object, MapConstant(instr->transition()));
+      Insert(object, NULL, MapConstant(instr->transition()));
     } else if (IsMapAccess(instr->access())) {
       // This is a store directly to the map field of the object.
       Kill(object);
       if (!instr->value()->IsConstant()) return;
-      Insert(object, MapConstant(instr->value()));
+      Insert(object, NULL, MapConstant(instr->value()));
     } else {
       // If the instruction changes maps, it should be handled above.
       CHECK(!instr->CheckGVNFlag(kChangesMaps));
@@ -396,19 +432,29 @@ class HCheckTable : public ZoneObject {
   void ReduceCompareMap(HCompareMap* instr) {
     MapSet maps = FindMaps(instr->value()->ActualValue());
     if (maps == NULL) return;
+
+    TRACE(("CompareMap for #%d at B%d ",
+        instr->value()->ActualValue()->id(), instr->block()->block_id()));
+
+    int succ;
     if (maps->Contains(instr->map())) {
-      if (maps->size() == 1) {
-        TRACE(("Marking redundant CompareMap #%d at B%d as true\n",
-            instr->id(), instr->block()->block_id()));
-        instr->set_known_successor_index(0);
-        INC_STAT(compares_true_);
+      if (maps->size() != 1) {
+        TRACE(("can't be replaced with goto: ambiguous set of maps\n"));
+        return;
       }
+      succ = 0;
+      INC_STAT(compares_true_);
     } else {
-      TRACE(("Marking redundant CompareMap #%d at B%d as false\n",
-          instr->id(), instr->block()->block_id()));
-      instr->set_known_successor_index(1);
+      succ = 1;
       INC_STAT(compares_false_);
     }
+
+    TRACE(("Marking redundant CompareMap #%d at B%d as %s\n",
+        instr->id(), instr->block()->block_id(), succ == 0 ? "true" : "false"));
+    instr->set_known_successor_index(succ);
+
+    int unreachable_succ = 1 - succ;
+    instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
   }
 
   void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
@@ -480,12 +526,15 @@ class HCheckTable : public ZoneObject {
   }
 
   void Print() {
+    if (unreachable_) {
+      PrintF("  checkmaps-table: unreachable\n");
+      return;
+    }
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* entry = &entries_[i];
       ASSERT(entry->object_ != NULL);
       PrintF("  checkmaps-table @%d: %s #%d ", i,
-             entry->object_->IsPhi() ? "phi" : "object",
-             entry->object_->id());
+             entry->object_->IsPhi() ? "phi" : "object", entry->object_->id());
       if (entry->check_ != NULL) {
         PrintF("check #%d ", entry->check_->id());
       }
@@ -515,13 +564,13 @@ class HCheckTable : public ZoneObject {
     return entry == NULL ? NULL : entry->maps_;
   }
 
-  void Insert(HValue* object, Unique<Map> map) {
+  void Insert(HValue* object, HInstruction* check, Unique<Map> map) {
     MapSet list = new(phase_->zone()) UniqueSet<Map>();
     list->Add(map, phase_->zone());
-    Insert(object, NULL, list);
+    Insert(object, check, list);
   }
 
-  void Insert(HValue* object, HCheckMaps* check, MapSet maps) {
+  void Insert(HValue* object, HInstruction* check, MapSet maps) {
     HCheckTableEntry* entry = &entries_[cursor_++];
     entry->object_ = object;
     entry->check_ = check;
@@ -546,6 +595,7 @@ class HCheckTable : public ZoneObject {
   int16_t cursor_;  // Must be <= kMaxTrackedObjects
   int16_t size_;    // Must be <= kMaxTrackedObjects
   // TODO(titzer): STATIC_ASSERT kMaxTrackedObjects < max(cursor_)
+  bool unreachable_;
 };