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

src/hydrogen-check-elimination.cc

 // Copyright 2013 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 44 matching lines @@
 
 // The main data structure used during check elimination, which stores a
 // set of known maps for each object.
 class HCheckTable : public ZoneObject {
  public:
   static const int kMaxTrackedObjects = 10;
 
   explicit HCheckTable(HCheckEliminationPhase* phase)
     : phase_(phase),
       cursor_(0),
-      size_(0) {
+      size_(0),
+      unreachable_(false) {
   }
 
   // The main processing of instructions.
   HCheckTable* Process(HInstruction* instr, Zone* zone) {
     switch (instr->opcode()) {
       case HValue::kCheckMaps: {
         ReduceCheckMaps(HCheckMaps::cast(instr));
         break;
       }
       case HValue::kCheckValue: {
@@ skipping 36 matching lines @@
       // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
       // - track which values have been HCheckHeapObject'd
     }
 
     return this;
   }
 
   // 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_;
 
     // 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_->Copy(phase_->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) {
+    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);
         HValue* left = cmp->left()->ActualValue();
         HValue* right = cmp->right()->ActualValue();
         HCheckTableEntry* le = copy->Find(left);
         HCheckTableEntry* re = copy->Find(right);
         if (le == NULL) {
           if (re != NULL) {
             copy->Insert(left, NULL, re->maps_->Copy(zone));
@@ skipping 17 matching lines @@
              from_block->block_id());
       copy->Print();
     }
 
     return copy;
   }
 
   // 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);
+
+        } 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 (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 (FLAG_trace_check_elimination) {
       PrintF("B%d checkmaps-table merged with B%d table:\n",
              succ->block_id(), pred_block->block_id());
       Print();
     }
     return this;
   }
 
   void ReduceCheckMaps(HCheckMaps* instr) {
     HValue* object = instr->value()->ActualValue();
@@ skipping 90 matching lines @@
     instr->DeleteAndReplaceWith(constant);
     INC_STAT(loads_);
   }
 
   void ReduceCheckMapValue(HCheckMapValue* instr) {
     if (!instr->map()->IsConstant()) return;  // Nothing to learn.
 
     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);
     }
   }
 
   void ReduceCheckHeapObject(HCheckHeapObject* instr) {
     if (FindMaps(instr->value()->ActualValue()) != NULL) {
       // If the object has known maps, it's definitely a heap object.
       instr->DeleteAndReplaceWith(instr->value());
       INC_STAT(removed_cho_);
     }
   }
 
   void ReduceStoreNamedField(HStoreNamedField* instr) {
     HValue* object = instr->object()->ActualValue();
     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));
     }
   }
 
   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) {
     MapSet maps = FindMaps(instr->object()->ActualValue());
     // Can only learn more about an object that already has a known set of maps.
     if (maps == NULL) return;
     if (maps->Contains(instr->original_map())) {
       // If the object has the original map, it will be transitioned.
       maps->Remove(instr->original_map());
       maps->Add(instr->transitioned_map(), phase_->zone());
@@ skipping 51 matching lines @@
 
       OS::MemMove(&tmp_entries[0], &entries_[0], L * sizeof(HCheckTableEntry));
       OS::MemMove(&entries_[0], &entries_[L], R * sizeof(HCheckTableEntry));
       OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
     }
 
     cursor_ = size_;  // Move cursor to end.
   }
 
   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());
       }
       MapSet list = entry->maps_;
       PrintF("%d maps { ", list->size());
       for (int j = 0; j < list->size(); j++) {
         if (j > 0) PrintF(", ");
         PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
       }
       PrintF(" }\n");
     }
   }
 
  private:
   HCheckTableEntry* Find(HValue* object) {
     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 (phase_->aliasing_->MustAlias(entry->object_, object)) return entry;
     }
     return NULL;
   }
 
   MapSet FindMaps(HValue* object) {
     HCheckTableEntry* entry = Find(object);
     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;
     entry->maps_ = maps;
     // If the table becomes full, wrap around and overwrite older entries.
     if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
     if (size_ < kMaxTrackedObjects) size_++;
   }
 
   bool IsMapAccess(HObjectAccess access) {
     return access.IsInobject() && access.offset() == JSObject::kMapOffset;
   }
 
   Unique<Map> MapConstant(HValue* value) {
     return Unique<Map>::cast(HConstant::cast(value)->GetUnique());
   }
 
   friend class HCheckMapsEffects;
 
   HCheckEliminationPhase* phase_;
   HCheckTableEntry entries_[kMaxTrackedObjects];
   int16_t cursor_;  // Must be <= kMaxTrackedObjects
   int16_t size_;    // Must be <= kMaxTrackedObjects
   // TODO(titzer): STATIC_ASSERT kMaxTrackedObjects < max(cursor_)
+  bool unreachable_;
 };
 
 
 // Collects instructions that can cause effects that invalidate information
 // needed for check elimination.
 class HCheckMapsEffects : public ZoneObject {
  public:
   explicit HCheckMapsEffects(Zone* zone)
     : maps_stored_(false),
       stores_(5, zone) { }
@@ skipping 84 matching lines @@
   PRINT_STAT(removed_cho);
   PRINT_STAT(narrowed);
   PRINT_STAT(loads);
   PRINT_STAT(empty);
   PRINT_STAT(compares_true);
   PRINT_STAT(compares_false);
   PRINT_STAT(transitions);
 }
 
 } }  // namespace v8::internal