Use stability to only conditionally flush information from the map check table.

src/hydrogen-check-elimination.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "hydrogen-check-elimination.h"
+

[Igor Sheludko, 2014/05/07 16:53:26]

Spurious change?

[Benedikt Meurer, 2014/05/08 04:45:49]

Updated to follow Google C++ Style Guide.

 #include "hydrogen-alias-analysis.h"
 #include "hydrogen-flow-engine.h"
 
 #define GLOBAL 1
 
 // Only collect stats in debug mode.
 #if DEBUG
 #define INC_STAT(x) phase_->x++
 #else
 #define INC_STAT(x)
 #endif
 
 // For code de-uglification.
 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
 
 namespace v8 {
 namespace internal {
 
 typedef const UniqueSet<Map>* MapSet;
 
 struct HCheckTableEntry {
+  enum State {
+    CHECKED,

[Igor Sheludko, 2014/05/07 16:53:26]

Please add comments about meaning of the states.

[Benedikt Meurer, 2014/05/08 04:45:49]

Done.

+    CHECKED_STABLE,
+    UNCHECKED_STABLE
+  };
+
+  static const char* State2String(State state) {
+    switch (state) {
+      case CHECKED: return "checked";
+      case CHECKED_STABLE: return "checked stable";
+      case UNCHECKED_STABLE: return "unchecked stable";
+    }
+    UNREACHABLE();
+    return NULL;
+  }
+
+  static State StateMerge(State state1, State state2) {
+    if (state1 == state2) return state1;
+    if ((state1 == CHECKED && state2 == CHECKED_STABLE) ||
+        (state2 == CHECKED && state1 == CHECKED_STABLE)) {
+      return CHECKED;
+    }
+    ASSERT((state1 == CHECKED_STABLE && state2 == UNCHECKED_STABLE) ||
+           (state2 == CHECKED_STABLE && state1 == UNCHECKED_STABLE));
+    return UNCHECKED_STABLE;
+  }
+
   HValue* object_;  // The object being approximated. NULL => invalid entry.
   HInstruction* check_;  // The last check instruction.
   MapSet maps_;          // The set of known maps for the object.
+  State state_;          // The state of this entry.
 };
 
 
 // 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 = 16;
 
   explicit HCheckTable(HCheckEliminationPhase* phase)
@@ skipping 29 matching lines @@
         ReduceTransitionElementsKind(
             HTransitionElementsKind::cast(instr));
         break;
       }
       case HValue::kCheckHeapObject: {
         ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
         break;
       }
       default: {
         // If the instruction changes maps uncontrollably, drop everything.
+        if (instr->CheckChangesFlag(kOsrEntries)) {
+          Kill();
+          break;
+        }
         if (instr->CheckChangesFlag(kElementsKind) ||
-            instr->CheckChangesFlag(kMaps) ||
-            instr->CheckChangesFlag(kOsrEntries)) {
-          Kill();
+            instr->CheckChangesFlag(kMaps)) {
+          KillUnstableEntries();
         }
       }
       // Improvements possible:
       // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
       // - track which values have been HCheckHeapObject'd
     }
 
     return this;
   }
 
@@ skipping 31 matching lines @@
  private:
   // Copy state to successor block.
   HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
     HCheckTable* copy = new(zone) HCheckTable(phase_);
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* old_entry = &entries_[i];
       ASSERT(old_entry->maps_->size() > 0);
       HCheckTableEntry* new_entry = &copy->entries_[i];
       new_entry->object_ = old_entry->object_;
       new_entry->maps_ = old_entry->maps_;
+      new_entry->state_ = old_entry->state_;
       // 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->IsLoopHeader() && 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->Insert(phi, NULL, pred_entry->maps_, pred_entry->state_);
         }
       }
     }
 
     // Branch-sensitive analysis for certain comparisons may add more facts
     // to the state for the successor on the true branch.
     bool learned = false;
     if (succ->predecessors()->length() == 1) {
       HControlInstruction* end = succ->predecessors()->at(0)->end();
       bool is_true_branch = end->SuccessorAt(0) == succ;
       if (end->IsCompareMap()) {
         HCompareMap* cmp = HCompareMap::cast(end);
         HValue* object = cmp->value()->ActualValue();
         HCheckTableEntry* entry = copy->Find(object);
         if (is_true_branch) {
+          HCheckTableEntry::State state = cmp->map_is_stable()
+              ? HCheckTableEntry::CHECKED_STABLE
+              : HCheckTableEntry::CHECKED;
           // Learn on the true branch of if(CompareMap(x)).
           if (entry == NULL) {
-            copy->Insert(object, cmp, cmp->map());
+            copy->Insert(object, cmp, cmp->map(), state);
           } else {
             entry->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone);
             entry->check_ = cmp;
+            entry->state_ = state;
           }
         } else {
           // Learn on the false branch of if(CompareMap(x)).
           if (entry != NULL) {
+            EnsureChecked(entry, object, cmp);
             UniqueSet<Map>* maps = entry->maps_->Copy(zone);
             maps->Remove(cmp->map());
             entry->maps_ = maps;
+            ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
           }
         }
         learned = true;
       } 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->Insert(left, NULL, re->maps_, re->state_);
           }
         } else if (re == NULL) {
-          copy->Insert(right, NULL, le->maps_);
+          copy->Insert(right, NULL, le->maps_, le->state_);
         } else {
+          EnsureChecked(le, cmp->left(), cmp);
+          EnsureChecked(re, cmp->right(), cmp);
           le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone);
+          le->state_ = re->state_ = HCheckTableEntry::StateMerge(
+              le->state_, re->state_);
+          ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, le->state_);
+          ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, re->state_);
         }
         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",
@@ skipping 20 matching lines @@
         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) {
+        if (that_entry == NULL ||
+            (that_entry->state_ == HCheckTableEntry::CHECKED &&
+             this_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) ||
+            (this_entry->state_ == HCheckTableEntry::CHECKED &&
+             that_entry->state_ == HCheckTableEntry::UNCHECKED_STABLE)) {
           this_entry->object_ = NULL;
           compact = true;
         } else {
           this_entry->maps_ =
               this_entry->maps_->Union(that_entry->maps_, zone);
+          this_entry->state_ = HCheckTableEntry::StateMerge(
+              this_entry->state_, that_entry->state_);
           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(this);
     }
     return this;
   }
 
   void ReduceCheckMaps(HCheckMaps* instr) {
     HValue* object = instr->value()->ActualValue();
     HCheckTableEntry* entry = Find(object);
     if (entry != NULL) {
       // entry found;
-      MapSet a = entry->maps_;
-      const UniqueSet<Map>* i = instr->maps();
-      if (a->IsSubset(i)) {
+      HGraph* graph = instr->block()->graph();
+      if (entry->maps_->IsSubset(instr->maps())) {
         // The first check is more strict; the second is redundant.
         if (entry->check_ != NULL) {
+          ASSERT_NE(HCheckTableEntry::UNCHECKED_STABLE, entry->state_);
           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 {
+        } else if (entry->state_ == HCheckTableEntry::UNCHECKED_STABLE) {
+          ASSERT_EQ(NULL, entry->check_);
+          TRACE(("Marking redundant CheckMaps #%d at B%d as stability check\n",
+                 instr->id(), instr->block()->block_id()));
+          instr->set_maps(entry->maps_->Copy(graph->zone()));
+          instr->MarkAsStabilityCheck();
+          entry->state_ = HCheckTableEntry::CHECKED_STABLE;
+        } else if (!instr->IsStabilityCheck()) {
           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;
       }
-      HGraph* graph = instr->block()->graph();
-      MapSet intersection = i->Intersect(a, graph->zone());
+      MapSet intersection = instr->maps()->Intersect(
+          entry->maps_, graph->zone());
       if (intersection->size() == 0) {
-        // Intersection is empty; probably megamorphic, which is likely to
-        // deopt anyway, so just leave things as they are.
+        // Intersection is empty; probably megamorphic.
         INC_STAT(empty_);
+        entry->object_ = NULL;
+        Compact();
       } else {
         // Update set of maps in the entry.
         entry->maps_ = intersection;
-        if (intersection->size() != i->size()) {
+        entry->state_ = instr->maps_are_stable()

[Igor Sheludko, 2014/05/07 16:53:26]

|| entry->check_->maps_are_stable()?

[Benedikt Meurer, 2014/05/08 04:45:49]

entry->check_ may be NULL at this point. But entry->state_ is already set
according to the previous check, so it all comes down to setting entry->state_
to CHECKED_STABLE if it was UNCHECKED_STABLE before, or
instr->maps_are_stable().

+            ? HCheckTableEntry::CHECKED_STABLE
+            : HCheckTableEntry::CHECKED;
+        if (intersection->size() != instr->maps()->size()) {
           // Narrow set of maps in the second check maps instruction.
           if (entry->check_ != NULL &&
               entry->check_->block() == instr->block() &&
               entry->check_->IsCheckMaps()) {
             // There is a check in the same block so replace it with a more
             // strict check and eliminate the second check entirely.
             HCheckMaps* check = HCheckMaps::cast(entry->check_);
+            ASSERT(!check->IsStabilityCheck());
             TRACE(("CheckMaps #%d at B%d narrowed\n", check->id(),
                 check->block()->block_id()));
             // Update map set and ensure that the check is alive.
             check->set_maps(intersection);
             check->ClearFlag(HValue::kIsDead);
             TRACE(("Replacing redundant CheckMaps #%d at B%d with #%d\n",
                 instr->id(), instr->block()->block_id(), entry->check_->id()));
             instr->DeleteAndReplaceWith(entry->check_);
           } else {
             TRACE(("CheckMaps #%d at B%d narrowed\n", instr->id(),
                 instr->block()->block_id()));
             instr->set_maps(intersection);
-            entry->check_ = instr;
+            entry->check_ = instr->IsStabilityCheck() ? NULL : instr;
           }
 
           if (FLAG_trace_check_elimination) {
             Print(this);
           }
           INC_STAT(narrowed_);
         }
       }
     } else {
       // No entry; insert a new one.
-      Insert(object, instr, instr->maps());
+      HCheckTableEntry::State state = instr->maps_are_stable()
+          ? HCheckTableEntry::CHECKED_STABLE
+          : HCheckTableEntry::CHECKED;
+      HCheckMaps* check = instr->IsStabilityCheck() ? NULL : instr;
+      Insert(object, check, instr->maps(), state);
     }
   }
 
   void ReduceLoadNamedField(HLoadNamedField* instr) {
     // Reduce a load of the map field when it is known to be a constant.
     if (!instr->access().IsMap()) {
       // Check if we introduce field maps here.
       MapSet maps = instr->maps();
       if (maps != NULL) {
         ASSERT_NE(0, maps->size());
-        Insert(instr, NULL, maps);
+        Insert(instr, NULL, maps, HCheckTableEntry::UNCHECKED_STABLE);
       }
       return;
     }
 
     HValue* object = instr->object()->ActualValue();
-    MapSet maps = FindMaps(object);
-    if (maps == NULL || maps->size() != 1) return;  // Not a constant.
+    HCheckTableEntry* entry = Find(object);
+    if (entry == NULL || entry->maps_->size() != 1) return;  // Not a constant.
 
-    Unique<Map> map = maps->at(0);
+    EnsureChecked(entry, object, instr);
+    Unique<Map> map = entry->maps_->at(0);
+    bool map_is_stable = (entry->state_ != HCheckTableEntry::CHECKED);
     HConstant* constant = HConstant::CreateAndInsertBefore(
-        instr->block()->graph()->zone(), map, true, instr);
+        instr->block()->graph()->zone(), map, map_is_stable, instr);
     instr->DeleteAndReplaceWith(constant);
     INC_STAT(loads_);
   }
 
   void ReduceCheckHeapObject(HCheckHeapObject* instr) {
-    if (FindMaps(instr->value()->ActualValue()) != NULL) {
+    HValue* value = instr->value()->ActualValue();
+    if (Find(value) != NULL) {
       // If the object has known maps, it's definitely a heap object.
-      instr->DeleteAndReplaceWith(instr->value());
+      instr->DeleteAndReplaceWith(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, NULL, HConstant::cast(instr->transition())->MapValue());
+      HConstant* c_transition = HConstant::cast(instr->transition());
+      HCheckTableEntry::State state = c_transition->HasStableMapValue()
+          ? HCheckTableEntry::CHECKED_STABLE
+          : HCheckTableEntry::CHECKED;
+      Insert(object, NULL, c_transition->MapValue(), state);
     } else if (instr->access().IsMap()) {
       // This is a store directly to the map field of the object.
       Kill(object);
       if (!instr->value()->IsConstant()) return;
-      Insert(object, NULL, HConstant::cast(instr->value())->MapValue());
+      HConstant* c_value = HConstant::cast(instr->value());
+      HCheckTableEntry::State state = c_value->HasStableMapValue()
+          ? HCheckTableEntry::CHECKED_STABLE
+          : HCheckTableEntry::CHECKED;
+      Insert(object, NULL, c_value->MapValue(), state);
     } else {
       // If the instruction changes maps, it should be handled above.
       CHECK(!instr->CheckChangesFlag(kMaps));
     }
   }
 
   void ReduceCompareMap(HCompareMap* instr) {
-    MapSet maps = FindMaps(instr->value()->ActualValue());
-    if (maps == NULL) return;
+    HCheckTableEntry* entry = Find(instr->value()->ActualValue());
+    if (entry == NULL) return;
+
+    EnsureChecked(entry, instr->value(), instr);
 
     int succ;
-    if (maps->Contains(instr->map())) {
-      if (maps->size() != 1) {
+    if (entry->maps_->Contains(instr->map())) {
+      if (entry->maps_->size() != 1) {
         TRACE(("CompareMap #%d for #%d at B%d can't be eliminated: "
                "ambiguous set of maps\n", instr->id(), instr->value()->id(),
                instr->block()->block_id()));
         return;
       }
       succ = 0;
       INC_STAT(compares_true_);
     } else {
       succ = 1;
       INC_STAT(compares_false_);
     }
 
     TRACE(("Marking redundant CompareMap #%d for #%d at B%d as %s\n",
         instr->id(), instr->value()->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 ReduceCompareObjectEqAndBranch(HCompareObjectEqAndBranch* instr) {
-    MapSet maps_left = FindMaps(instr->left()->ActualValue());
-    if (maps_left == NULL) return;
-    MapSet maps_right = FindMaps(instr->right()->ActualValue());
-    if (maps_right == NULL) return;
-    MapSet intersection = maps_left->Intersect(maps_right, zone());
+    HValue* left = instr->left()->ActualValue();
+    HCheckTableEntry* le = Find(left);
+    if (le == NULL) return;
+    HValue* right = instr->right()->ActualValue();
+    HCheckTableEntry* re = Find(right);
+    if (re == NULL) return;
+
+    EnsureChecked(le, left, instr);
+    EnsureChecked(re, right, instr);
+
+    // TODO(bmeurer): Add a predicate here instead of computing the intersection
+    MapSet intersection = le->maps_->Intersect(re->maps_, zone());
     if (intersection->size() > 0) return;
 
     TRACE(("Marking redundant CompareObjectEqAndBranch #%d at B%d as false\n",
         instr->id(), instr->block()->block_id()));
     int succ = 1;
     instr->set_known_successor_index(succ);
 
     int unreachable_succ = 1 - succ;
     instr->block()->MarkSuccEdgeUnreachable(unreachable_succ);
   }
 
   void ReduceTransitionElementsKind(HTransitionElementsKind* instr) {
-    HCheckTableEntry* entry = Find(instr->object()->ActualValue());
+    HValue* object = instr->object()->ActualValue();
+    HCheckTableEntry* entry = Find(object);
     // Can only learn more about an object that already has a known set of maps.
     if (entry == NULL) return;
+    EnsureChecked(entry, object, instr);
     if (entry->maps_->Contains(instr->original_map())) {
       // If the object has the original map, it will be transitioned.
       UniqueSet<Map>* maps = entry->maps_->Copy(zone());
       maps->Remove(instr->original_map());
       maps->Add(instr->transitioned_map(), zone());
       entry->maps_ = maps;
     } else {
       // Object does not have the given map, thus the transition is redundant.
-      instr->DeleteAndReplaceWith(instr->object());
+      instr->DeleteAndReplaceWith(object);
       INC_STAT(transitions_);
     }
   }
 
+  void EnsureChecked(HCheckTableEntry* entry,
+                     HValue* value,
+                     HInstruction* instr) {
+    if (entry->state_ != HCheckTableEntry::UNCHECKED_STABLE) return;
+    HGraph* graph = instr->block()->graph();
+    HCheckMaps* check = HCheckMaps::CreateAndInsertBefore(
+        graph->zone(), value, entry->maps_->Copy(graph->zone()), true, instr);
+    check->MarkAsStabilityCheck();
+    entry->state_ = HCheckTableEntry::CHECKED_STABLE;
+    entry->check_ = NULL;
+  }
+
   // Kill everything in the table.
   void Kill() {
     size_ = 0;
     cursor_ = 0;
   }
 
+  // Kill all unstable entries in the table.
+  void KillUnstableEntries() {
+    bool compact = false;
+    for (int i = 0; i < size_; ++i) {
+      HCheckTableEntry* entry = &entries_[i];
+      ASSERT_NOT_NULL(entry->object_);
+      if (entry->state_ == HCheckTableEntry::CHECKED) {
+        entry->object_ = NULL;
+        compact = true;
+      } else {
+        // All checked stable entries become unchecked stable.
+        entry->state_ = HCheckTableEntry::UNCHECKED_STABLE;

[Igor Sheludko, 2014/05/07 16:53:26]

Does it mean that we could end up adding multiple stability check instructions
for the same set of maps?
We could probably fix that by setting CHECKED_STABLE state only for the
stability check instructions and instead of it initially use UNCHECKED_STABLE
for all the other instructions with stable maps. WDYT?

[Benedikt Meurer, 2014/05/08 04:45:49]

This is not an issue, because the stability checks are simply markers (i.e. they
do not generate code, they do not add register constraints, they do not
change/depend on flags, etc.), but simply add their maps to a set of maps in the
LChunk.

+        entry->check_ = NULL;
+      }
+    }
+    if (compact) Compact();
+  }
+
   // Kill everything in the table that may alias {object}.
   void Kill(HValue* object) {
     bool compact = false;
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* entry = &entries_[i];
       ASSERT(entry->object_ != NULL);
       if (phase_->aliasing_->MayAlias(entry->object_, object)) {
         entry->object_ = NULL;
         compact = true;
       }
@@ skipping 42 matching lines @@
 
     for (int i = 0; i < table->size_; i++) {
       HCheckTableEntry* entry = &table->entries_[i];
       ASSERT(entry->object_ != NULL);
       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());
       }
       MapSet list = entry->maps_;
-      PrintF("%d maps { ", list->size());
+      PrintF("%d %s maps { ", list->size(),
+             HCheckTableEntry::State2String(entry->state_));
       for (int j = 0; j < list->size(); j++) {
         if (j > 0) PrintF(", ");
         PrintF("%" V8PRIxPTR, list->at(j).Hashcode());
       }
       PrintF(" }\n");
     }
   }
 
   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,
+              HInstruction* check,
+              Unique<Map> map,
+              HCheckTableEntry::State state) {
+    Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()), state);
   }
 
-  void Insert(HValue* object, HInstruction* check, Unique<Map> map) {
-    Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()));
-  }
-
-  void Insert(HValue* object, HInstruction* check, MapSet maps) {
+  void Insert(HValue* object,
+              HInstruction* check,
+              MapSet maps,
+              HCheckTableEntry::State state) {
+    ASSERT(state != HCheckTableEntry::UNCHECKED_STABLE || check == NULL);
     HCheckTableEntry* entry = &entries_[cursor_++];
     entry->object_ = object;
     entry->check_ = check;
     entry->maps_ = maps;
+    entry->state_ = state;
     // If the table becomes full, wrap around and overwrite older entries.
     if (cursor_ == kMaxTrackedObjects) cursor_ = 0;
     if (size_ < kMaxTrackedObjects) size_++;
   }
 
   Zone* zone() const { return phase_->zone(); }
 
   friend class HCheckMapsEffects;
   friend class HCheckEliminationPhase;
 
   HCheckEliminationPhase* phase_;
   HCheckTableEntry entries_[kMaxTrackedObjects];
   int16_t cursor_;  // Must be <= kMaxTrackedObjects
   int16_t size_;    // Must be <= kMaxTrackedObjects
-  // TODO(titzer): STATIC_ASSERT kMaxTrackedObjects < max(cursor_)
+  STATIC_ASSERT(kMaxTrackedObjects < (1 << 15));
 };
 
 
 // Collects instructions that can cause effects that invalidate information
 // needed for check elimination.
 class HCheckMapsEffects : public ZoneObject {
  public:
   explicit HCheckMapsEffects(Zone* zone)
-      : objects_(0, zone), maps_stored_(false) {}
+      : objects_(0, zone), maps_stored_(false), osr_entries_(false) { }
 
   // Effects are _not_ disabled.
   inline bool Disabled() const { return false; }
 
   // Process a possibly side-effecting instruction.
   void Process(HInstruction* instr, Zone* zone) {
     switch (instr->opcode()) {
       case HValue::kStoreNamedField: {
         HStoreNamedField* store = HStoreNamedField::cast(instr);
         if (store->access().IsMap() && store->has_transition()) {
           objects_.Add(store->object(), zone);
         }
         break;
       }
       case HValue::kTransitionElementsKind: {
         objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone);
         break;
       }
       default: {
-        maps_stored_ |= (instr->CheckChangesFlag(kMaps) |
-                         instr->CheckChangesFlag(kOsrEntries) |
-                         instr->CheckChangesFlag(kElementsKind));
+        if (instr->CheckChangesFlag(kMaps) ||
+            instr->CheckChangesFlag(kElementsKind)) {
+          maps_stored_ = true;
+        }
+        if (instr->CheckChangesFlag(kOsrEntries)) {
+          osr_entries_ = true;
+        }
       }
     }
   }
 
   // Apply these effects to the given check elimination table.
   void Apply(HCheckTable* table) {
-    if (maps_stored_) {
+    if (osr_entries_) {
       // Uncontrollable map modifications; kill everything.
       table->Kill();
       return;
     }
 
+    // Kill all unstable entries.
+    if (maps_stored_) {
+      table->KillUnstableEntries();

[Igor Sheludko, 2014/05/07 16:53:26]

I think you can return at this point as all the entries that are killed below
must be unstable anyway.

[Benedikt Meurer, 2014/05/08 04:45:49]

No, because we can have stored maps to objects with (UN)CHECKED_STABLE entries,
and this is handled below.

+    }
+
     // Kill maps for each object contained in these effects.
     for (int i = 0; i < objects_.length(); ++i) {
       table->Kill(objects_[i]->ActualValue());
     }
   }
 
   // Union these effects with the other effects.
   void Union(HCheckMapsEffects* that, Zone* zone) {
     maps_stored_ |= that->maps_stored_;
+    osr_entries_ |= that->osr_entries_;
     for (int i = 0; i < that->objects_.length(); ++i) {
       objects_.Add(that->objects_[i], zone);
     }
   }
 
  private:
   ZoneList<HValue*> objects_;
   bool maps_stored_ : 1;
+  bool osr_entries_ : 1;

[Igor Sheludko, 2014/05/07 16:53:26]

Consider using GVNFlags instead of set of booleans.

[Benedikt Meurer, 2014/05/08 04:45:49]

Done.

 };
 
 
 // The main routine of the analysis phase. Use the HFlowEngine for either a
 // local or a global analysis.
 void HCheckEliminationPhase::Run() {
   HFlowEngine<HCheckTable, HCheckMapsEffects> engine(graph(), zone());
   HCheckTable* table = new(zone()) HCheckTable(this);
 
   if (GLOBAL) {
@@ skipping 23 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