Implement global check elimination using the HFlowEngine.

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 f712a39db8de128063b687ba512946e448365627..513306f2bf6441ad8fe273ffe5e902cf37b05de1 100644
--- a/src/hydrogen-check-elimination.cc
+++ b/src/hydrogen-check-elimination.cc
@@ -27,6 +27,19 @@
 
 #include "hydrogen-check-elimination.h"
 #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 {
@@ -34,52 +47,139 @@ namespace internal {
 static const int kMaxTrackedObjects = 10;

[mvstanton, 2013/10/31 11:16:13]

Could this be public static inside the HCheckTable?

 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.
+};
+
+
 // The main datastructure used during check elimination, which stores a
 // set of known maps for each object.
-class HCheckTable {
+class HCheckTable : public ZoneObject {
  public:
-  explicit HCheckTable(Zone* zone) : zone_(zone) {
-    Kill();
-    redundant_ = 0;
-    narrowed_ = 0;
-    empty_ = 0;
-    removed_ = 0;
-    compares_true_ = 0;
-    compares_false_ = 0;
-    transitions_ = 0;
-    loads_ = 0;
+  explicit HCheckTable(HCheckEliminationPhase* phase)
+    : phase_(phase),
+      cursor_(0),
+      size_(0) {
+  }
+
+  // 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: {
+        ReduceCheckValue(HCheckValue::cast(instr));
+        break;
+      }
+      case HValue::kLoadNamedField: {
+        ReduceLoadNamedField(HLoadNamedField::cast(instr));
+        break;
+      }
+      case HValue::kStoreNamedField: {
+        ReduceStoreNamedField(HStoreNamedField::cast(instr));
+        break;
+      }
+      case HValue::kCompareMap: {
+        ReduceCompareMap(HCompareMap::cast(instr));
+        break;
+      }
+      case HValue::kTransitionElementsKind: {
+        ReduceTransitionElementsKind(
+            HTransitionElementsKind::cast(instr));
+        break;
+      }
+      case HValue::kCheckMapValue: {
+        ReduceCheckMapValue(HCheckMapValue::cast(instr));
+        break;
+      }
+      default: {
+        // If the instruction changes maps uncontrollably, kill the whole town.

[mvstanton, 2013/10/31 11:16:13]

LOL! But a more sober comment for checking in, pleez.

Also, should these flags be checked for the instructions in the cases above too?

+        if (instr->CheckGVNFlag(kChangesMaps) ||
+            instr->CheckGVNFlag(kChangesOsrEntries)) {
+          Kill();
+        }
+      }
+      // Improvements possible:
+      // - eliminate HCheckSmi and HCheckHeapObject
+    }
+
+    return this;
+  }
+
+  // Global analysis: Copy state to successor block.
+  HCheckTable* Copy(HBasicBlock* succ, Zone* zone) {
+    HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
+    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_;

[mvstanton, 2013/10/31 11:16:13]

Can you explain here why you don't copy the checks as well as object_/maps_?

+      new_entry->check_ = NULL;
+      new_entry->maps_ = old_entry->maps_->Copy(phase_->zone());
+    }
+    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;
+      } 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();
+    return this;
   }
 
   void ReduceCheckMaps(HCheckMaps* instr) {
     HValue* object = instr->value()->ActualValue();
-    int index = Find(object);
-    if (index >= 0) {
+    HCheckTableEntry* entry = Find(object);
+    if (entry != NULL) {
       // entry found;
-      MapSet a = known_maps_[index];
-      MapSet i = instr->map_set().Copy(zone_);
+      MapSet a = entry->maps_;
+      MapSet i = instr->map_set().Copy(phase_->zone());
       if (a->IsSubset(i)) {
         // The first check is more strict; the second is redundant.
-        if (checks_[index] != NULL) {
-          instr->DeleteAndReplaceWith(checks_[index]);
-          redundant_++;
+        if (entry->check_ != NULL) {
+          instr->DeleteAndReplaceWith(entry->check_);
+          INC_STAT(redundant_);
         } else {
           instr->DeleteAndReplaceWith(instr->value());
-          removed_++;
+          INC_STAT(removed_);
         }
         return;
       }
-      i = i->Intersect(a, zone_);
+      i = i->Intersect(a, phase_->zone());
       if (i->size() == 0) {
         // Intersection is empty; probably megamorphic, which is likely to
         // deopt anyway, so just leave things as they are.
-        empty_++;
+        INC_STAT(empty_);
       } else {
-        // TODO(titzer): replace the first check with a more strict check.
-        narrowed_++;
+        // TODO(titzer): replace the first check with a more strict check
+        INC_STAT(narrowed_);
       }
     } else {
       // No entry; insert a new one.
-      Insert(object, instr, instr->map_set().Copy(zone_));
+      Insert(object, instr, instr->map_set().Copy(phase_->zone()));
     }
   }
 
@@ -88,10 +188,10 @@ class HCheckTable {
     HValue* value = instr->Canonicalize();
     if (value == NULL) {
       instr->DeleteAndReplaceWith(instr->value());
-      removed_++;
+      INC_STAT(removed_);
     } else if (value != instr) {
       instr->DeleteAndReplaceWith(value);
-      redundant_++;
+      INC_STAT(redundant_);
     }
   }
 
@@ -107,7 +207,7 @@ class HCheckTable {
     HConstant* constant = HConstant::CreateAndInsertBefore(
         instr->block()->graph()->zone(), map, true, instr);
     instr->DeleteAndReplaceWith(constant);
-    loads_++;
+    INC_STAT(loads_);
   }
 
   void ReduceCheckMapValue(HCheckMapValue* instr) {
@@ -122,11 +222,11 @@ class HCheckTable {
         if (maps->size() == 1) {
           // Object is known to have exactly this map.
           instr->DeleteAndReplaceWith(NULL);
-          removed_++;
+          INC_STAT(removed_);
         } else {
           // Only one map survives the check.
           maps->Clear();
-          maps->Add(map, zone_);
+          maps->Add(map, phase_->zone());
         }
       }
     } else {
@@ -158,10 +258,10 @@ class HCheckTable {
     if (maps == NULL) return;
     if (maps->Contains(instr->map())) {
       // TODO(titzer): replace with goto true branch
-      if (maps->size() == 1) compares_true_++;
+      if (maps->size() == 1) INC_STAT(compares_true_);

[mvstanton, 2013/10/31 11:16:13]

It looks like this function just serves to update reporting stats, at least
until the TODOs are addressed. Could you put stat collection behind a flag
(instead of implicit with DEBUG), and avoid going deep into code paths if stat
reporting is turned off? So this function would begin with

if (!FLAG_check_elimination_stats) return;
...
// TODO(...

(those TODOs point the way that soon an implementation will make it worthwhile
to come into this function).
The INC_STAT macro will check the flag.

     } else {
       // TODO(titzer): replace with goto false branch
-      compares_false_++;
+      INC_STAT(compares_false_);
     }
   }
 
@@ -172,36 +272,76 @@ class HCheckTable {
     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(), zone_);
+      maps->Add(instr->transitioned_map(), phase_->zone());
     } else {
       // Object does not have the given map, thus the transition is redundant.
       instr->DeleteAndReplaceWith(instr->object());
-      transitions_++;
+      INC_STAT(transitions_);
     }
   }
 
   // Kill everything in the table.
   void Kill() {
-    memset(objects_, 0, sizeof(objects_));
+    size_ = 0;
+    cursor_ = 0;
   }
 
   // Kill everything in the table that may alias {object}.
   void Kill(HValue* object) {
-    for (int i = 0; i < kMaxTrackedObjects; i++) {
-      if (objects_[i] == NULL) continue;
-      if (aliasing_.MayAlias(objects_[i], object)) objects_[i] = NULL;
+    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;
+      }
     }
-    ASSERT(Find(object) < 0);
+    if (compact) Compact();
+    ASSERT(Find(object) == NULL);
+  }
+
+  void Compact() {
+    // First, compact the array in place.
+    int max = size_, dest = 0, old_cursor = cursor_;
+    for (int i = 0; i < max; i++) {
+      if (entries_[i].object_ != NULL) {
+        if (dest != i) entries_[dest] = entries_[i];
+        dest++;
+      } else {
+        if (i < old_cursor) cursor_--;
+        size_--;
+      }
+    }
+    ASSERT(size_ == dest);
+    ASSERT(cursor_ <= size_);
+
+    // Preserve the age of the entries by moving the older entries to the end.
+    if (cursor_ == size_) return;  // Cursor already points at end.
+    if (cursor_ != 0) {
+      // | L = oldest |   R = newest   |       |
+      //              ^ cursor         ^ size  ^ MAX
+      HCheckTableEntry tmp_entries[kMaxTrackedObjects];
+      int L = cursor_;
+      int R = size_ - cursor_;
+
+      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.

[mvstanton, 2013/10/31 11:16:13]

Do performance concerns justify the complexity? How about just use the
tmp_entries every time as a serialization from cursor_ to the oldest entry?

   }
 
   void Print() {
-    for (int i = 0; i < kMaxTrackedObjects; i++) {
-      if (objects_[i] == NULL) continue;
-      PrintF("  checkmaps-table @%d: object #%d ", i, objects_[i]->id());
-      if (checks_[i] != NULL) {
-        PrintF("check #%d ", checks_[i]->id());
+    for (int i = 0; i < size_; i++) {
+      HCheckTableEntry* entry = &entries_[i];
+      ASSERT(entry->object_ != NULL);
+      PrintF("  checkmaps-table @%d: object #%d ", i, entry->object_->id());
+      if (entry->check_ != NULL) {
+        PrintF("check #%d ", entry->check_->id());
       }
-      MapSet list = known_maps_[i];
+      MapSet list = entry->maps_;
       PrintF("%d maps { ", list->size());
       for (int j = 0; j < list->size(); j++) {
         if (j > 0) PrintF(", ");
@@ -211,47 +351,36 @@ class HCheckTable {
     }
   }
 
-  void PrintStats() {
-    if (redundant_ > 0)      PrintF("  redundant   = %2d\n", redundant_);
-    if (removed_ > 0)        PrintF("  removed     = %2d\n", removed_);
-    if (narrowed_ > 0)       PrintF("  narrowed    = %2d\n", narrowed_);
-    if (loads_ > 0)          PrintF("  loads       = %2d\n", loads_);
-    if (empty_ > 0)          PrintF("  empty       = %2d\n", empty_);
-    if (compares_true_ > 0)  PrintF("  cmp_true    = %2d\n", compares_true_);
-    if (compares_false_ > 0) PrintF("  cmp_false   = %2d\n", compares_false_);
-    if (transitions_ > 0)    PrintF("  transitions = %2d\n", transitions_);
-  }
-
  private:
-  int Find(HValue* object) {
-    for (int i = 0; i < kMaxTrackedObjects; i++) {
-      if (objects_[i] == NULL) continue;
-      if (aliasing_.MustAlias(objects_[i], object)) return i;
+  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 -1;
+    return NULL;
   }
 
   MapSet FindMaps(HValue* object) {
-    int index = Find(object);
-    return index < 0 ? NULL : known_maps_[index];
+    HCheckTableEntry* entry = Find(object);
+    return entry == NULL ? NULL : entry->maps_;
   }
 
   void Insert(HValue* object, Unique<Map> map) {
-    MapSet list = new(zone_) UniqueSet<Map>();
-    list->Add(map, zone_);
+    MapSet list = new(phase_->zone()) UniqueSet<Map>();
+    list->Add(map, phase_->zone());
     Insert(object, NULL, list);
   }
 
   void Insert(HValue* object, HCheckMaps* check, MapSet maps) {
-    for (int i = 0; i < kMaxTrackedObjects; i++) {
-      // TODO(titzer): drop old entries instead of disallowing new ones.
-      if (objects_[i] == NULL) {
-        objects_[i] = object;
-        checks_[i] = check;
-        known_maps_[i] = maps;
-        return;
-      }
-    }
+    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) {
@@ -262,96 +391,109 @@ class HCheckTable {
     return Unique<Map>::cast(HConstant::cast(value)->GetUnique());
   }
 
-  Zone* zone_;
-  HValue* objects_[kMaxTrackedObjects];
-  HValue* checks_[kMaxTrackedObjects];
-  MapSet known_maps_[kMaxTrackedObjects];
-  HAliasAnalyzer aliasing_;
-  int redundant_;
-  int removed_;
-  int narrowed_;
-  int loads_;
-  int empty_;
-  int compares_true_;
-  int compares_false_;
-  int transitions_;
-};
-
+  friend class HCheckMapsEffects;
 
-void HCheckEliminationPhase::Run() {
-  for (int i = 0; i < graph()->blocks()->length(); i++) {
-    EliminateLocalChecks(graph()->blocks()->at(i));
-  }
-}
-
-
-// For code de-uglification.
-#define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
+  HCheckEliminationPhase* phase_;
+  HCheckTableEntry entries_[kMaxTrackedObjects];
+  int16_t cursor_;  // Must be <= kMaxTrackedObjects

[mvstanton, 2013/10/31 11:16:13]

STATIC_ASSERT on sizeof cursor_ and size_ that they hold kMaxTrackedObjects,
since you are already reducing their size.

[mvstanton, 2013/11/28 07:14:47]

Ben asked: "where should I put this?"

I think right here next to the declaration, like
STATIC_ASSERT((1 << (sizeof(cursor_) * 8) >= kMaxTrackedObjects);

+  int16_t size_;    // Must be <= kMaxTrackedObjects
+};
 
 
-// Eliminate checks local to a block.
-void HCheckEliminationPhase::EliminateLocalChecks(HBasicBlock* block) {
-  HCheckTable table(zone());
-  TRACE(("-- check-elim B%d ------------------------------------------------\n",
-         block->block_id()));
+// 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) { }
 
-  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
-    bool changed = false;
-    HInstruction* instr = it.Current();
+  inline bool Disabled() {
+    return false;  // Effects are _not_ disabled.
+  }
 
+  // Process a possibly side-effecting instruction.
+  void Process(HInstruction* instr, Zone* zone) {
     switch (instr->opcode()) {
-      case HValue::kCheckMaps: {
-        table.ReduceCheckMaps(HCheckMaps::cast(instr));
-        changed = true;
-        break;
-      }
-      case HValue::kCheckValue: {
-        table.ReduceCheckValue(HCheckValue::cast(instr));
-        changed = true;
-        break;
-      }
-      case HValue::kLoadNamedField: {
-        table.ReduceLoadNamedField(HLoadNamedField::cast(instr));
-        changed = true;
-        break;
-      }
       case HValue::kStoreNamedField: {
-        table.ReduceStoreNamedField(HStoreNamedField::cast(instr));
-        changed = true;
+        stores_.Add(HStoreNamedField::cast(instr), zone);
         break;
       }
-      case HValue::kCompareMap: {
-        table.ReduceCompareMap(HCompareMap::cast(instr));
-        changed = true;
-        break;
-      }
-      case HValue::kTransitionElementsKind: {
-        table.ReduceTransitionElementsKind(
-            HTransitionElementsKind::cast(instr));
-        changed = true;
-        break;
-      }
-      case HValue::kCheckMapValue: {
-        table.ReduceCheckMapValue(HCheckMapValue::cast(instr));
-        changed = true;
-        break;
+      case HValue::kOsrEntry: {
+        // Kill everything. Loads must not be hoisted past the OSR entry.
+        maps_stored_ = true;
       }
       default: {
-        // If the instruction changes maps uncontrollably, kill the whole town.
-        if (instr->CheckGVNFlag(kChangesMaps)) {
-          table.Kill();
-          changed = true;
-        }
+        maps_stored_ |= (instr->CheckGVNFlag(kChangesMaps) |
+                         instr->CheckGVNFlag(kChangesElementsKind));
+      }
+    }
+  }
+
+  // Apply these effects to the given check elimination table.
+  void Apply(HCheckTable* table) {
+    if (maps_stored_) {
+      // Uncontrollable map modifications; kill everything.
+      table->Kill();
+      return;
+    }
+
+    // Kill maps for each store contained in these effects.
+    for (int i = 0; i < stores_.length(); i++) {
+      HStoreNamedField* s = stores_[i];
+      if (table->IsMapAccess(s->access()) || s->has_transition()) {
+        table->Kill(s->object()->ActualValue());
       }
-      // Improvements possible:
-      // - eliminate HCheckSmi and HCheckHeapObject
     }
+  }
+
+  // Union these effects with the other effects.
+  void Union(HCheckMapsEffects* that, Zone* zone) {
+    maps_stored_ |= that->maps_stored_;
+    for (int i = 0; i < that->stores_.length(); i++) {
+      stores_.Add(that->stores_[i], zone);
+    }
+  }
+
+ private:
+  bool maps_stored_ : 1;
+  ZoneList<HStoreNamedField*> stores_;
+};
 
-    if (changed && FLAG_trace_check_elimination) table.Print();
+
+// 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) {
+    // Perform a global analysis.
+    engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), table);
+  } else {
+    // Perform only local analysis.
+    for (int i = 0; i < graph()->blocks()->length(); i++) {
+      table->Kill();
+      engine.AnalyzeOneBlock(graph()->blocks()->at(i), table);
+    }
   }
 
-  if (FLAG_trace_check_elimination) table.PrintStats();
+  if (FLAG_trace_check_elimination) PrintStats();
 }
 
 
+// Are we eliminated yet?
+void HCheckEliminationPhase::PrintStats() {
+#if DEBUG

[mvstanton, 2013/10/31 11:16:13]

Same here with a defined flag instead of DEBUG. I guess the flag is already
FLAG_trace_check_elimination.

+  if (redundant_ > 0)      PrintF("  redundant   = %2d\n", redundant_);
+  if (removed_ > 0)        PrintF("  removed     = %2d\n", removed_);
+  if (narrowed_ > 0)       PrintF("  narrowed    = %2d\n", narrowed_);
+  if (loads_ > 0)          PrintF("  loads       = %2d\n", loads_);
+  if (empty_ > 0)          PrintF("  empty       = %2d\n", empty_);
+  if (compares_true_ > 0)  PrintF("  cmp_true    = %2d\n", compares_true_);
+  if (compares_false_ > 0) PrintF("  cmp_false   = %2d\n", compares_false_);
+  if (transitions_ > 0)    PrintF("  transitions = %2d\n", transitions_);
+#endif
+}
+
 } }  // namespace v8::internal