Various cleanups in check elimination.

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"
 #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 UniqueSet<Map>* MapSet;
+typedef const UniqueSet<Map>* MapSet;
 
 struct HCheckTableEntry {
   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.
 };
 
 
 // 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;
+  static const int kMaxTrackedObjects = 16;
 
   explicit HCheckTable(HCheckEliminationPhase* phase)
     : phase_(phase),
       cursor_(0),
       size_(0) {
   }
 
   // The main processing of instructions.
   HCheckTable* Process(HInstruction* instr, Zone* zone) {
     switch (instr->opcode()) {
@@ skipping 25 matching lines @@
       case HValue::kCheckMapValue: {
         ReduceCheckMapValue(HCheckMapValue::cast(instr));
         break;
       }
       case HValue::kCheckHeapObject: {
         ReduceCheckHeapObject(HCheckHeapObject::cast(instr));
         break;
       }
       default: {
         // If the instruction changes maps uncontrollably, drop everything.
-        if (instr->CheckChangesFlag(kMaps) ||
+        if (instr->CheckChangesFlag(kElementsKind) ||
+            instr->CheckChangesFlag(kMaps) ||
             instr->CheckChangesFlag(kOsrEntries)) {
           Kill();
         }
       }
       // Improvements possible:
       // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
       // - track which values have been HCheckHeapObject'd
     }
 
     return this;
@@ skipping 26 matching lines @@
     if (FLAG_trace_check_elimination) {
       PrintF("Processing B%d, checkmaps-table:\n", block->block_id());
       Print(state);
     }
     return state;
   }
 
  private:
   // Copy state to successor block.
   HCheckTable* Copy(HBasicBlock* succ, HBasicBlock* from_block, Zone* zone) {
-    HCheckTable* copy = new(phase_->zone()) HCheckTable(phase_);
+    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_->Copy(phase_->zone());
+      new_entry->maps_ = old_entry->maps_;
       // 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(phase_->zone()));
+          copy->Insert(phi, NULL, pred_entry->maps_);
         }
       }
     }
 
     // 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) {
           // 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->maps_ = new(zone) UniqueSet<Map>(cmp->map(), zone);
             entry->check_ = cmp;
           }
         } else {
           // Learn on the false branch of if(CompareMap(x)).
           if (entry != NULL) {
-            entry->maps_->Remove(cmp->map());
+            UniqueSet<Map>* maps = entry->maps_->Copy(zone);
+            maps->Remove(cmp->map());
+            entry->maps_ = maps;
           }
         }
         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(zone));
+            copy->Insert(left, NULL, re->maps_);
           }
         } else if (re == NULL) {
-          copy->Insert(right, NULL, le->maps_->Copy(zone));
+          copy->Insert(right, NULL, le->maps_);
         } else {
-          MapSet intersect = le->maps_->Intersect(re->maps_, zone);
-          le->maps_ = intersect;
-          re->maps_ = intersect->Copy(zone);
+          le->maps_ = re->maps_ = le->maps_->Intersect(re->maps_, zone);
         }
         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 25 matching lines @@
 
         } 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());
+              this_entry->maps_->Union(that_entry->maps_, 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(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->map_set();
+      const UniqueSet<Map>* i = instr->maps();
       if (a->IsSubset(i)) {
         // The first check is more strict; the second is redundant.
         if (entry->check_ != NULL) {
           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 {
           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;
       }
-      MapSet intersection = i->Intersect(a, phase_->zone());
+      HGraph* graph = instr->block()->graph();
+      MapSet intersection = i->Intersect(a, graph->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 {
         // 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();
           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_);
             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_map_set(intersection, graph->zone());
+            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_map_set(intersection, graph->zone());
+            instr->set_maps(intersection);
             entry->check_ = instr;
           }
 
           if (FLAG_trace_check_elimination) {
             Print(this);
           }
           INC_STAT(narrowed_);
         }
       }
     } else {
       // No entry; insert a new one.
-      Insert(object, instr, instr->map_set()->Copy(phase_->zone()));
+      Insert(object, instr, instr->maps());
     }
   }
 
   void ReduceLoadNamedField(HLoadNamedField* instr) {
     // Reduce a load of the map field when it is known to be a constant.
-    if (!IsMapAccess(instr->access())) {
+    if (!instr->access().IsMap()) {
       // Check if we introduce field maps here.
-      if (instr->map_set()->size() != 0) {
-        Insert(instr, instr, instr->map_set()->Copy(phase_->zone()));
+      if (instr->maps()->size() != 0) {
+        Insert(instr, instr, instr->maps());
       }
       return;
     }
 
     HValue* object = instr->object()->ActualValue();
     MapSet maps = FindMaps(object);
     if (maps == NULL || maps->size() != 1) return;  // Not a constant.
 
     Unique<Map> map = maps->at(0);
     HConstant* constant = HConstant::CreateAndInsertBefore(
         instr->block()->graph()->zone(), map, true, instr);
     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());
 
     HCheckTableEntry* entry = Find(object);
     if (entry != NULL) {
-      MapSet maps = entry->maps_;
-      if (maps->Contains(map)) {
-        if (maps->size() == 1) {
+      if (entry->maps_->Contains(map)) {
+        if (entry->maps_->size() == 1) {
           // Object is known to have exactly this map.
           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->maps_ = new(zone()) UniqueSet<Map>(map, zone());
           entry->check_ = instr;
         }
       }
     } else {
       // No prior information.
       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, NULL, MapConstant(instr->transition()));
-    } else if (IsMapAccess(instr->access())) {
+    } 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, MapConstant(instr->value()));
     } else {
       // If the instruction changes maps, it should be handled above.
       CHECK(!instr->CheckChangesFlag(kMaps));
     }
   }
 
@@ skipping 23 matching lines @@
 
     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, phase_->zone());
+    MapSet intersection = maps_left->Intersect(maps_right, 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) {
-    MapSet maps = FindMaps(instr->object()->ActualValue());
+    HCheckTableEntry* entry = Find(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 (entry == NULL) return;
+    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(), phase_->zone());
+      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());
       INC_STAT(transitions_);
     }
   }
 
   // Kill everything in the table.
   void Kill() {
     size_ = 0;
@@ skipping 80 matching lines @@
     }
     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) {
-    MapSet list = new(phase_->zone()) UniqueSet<Map>();
-    list->Add(map, phase_->zone());
-    Insert(object, check, list);
+    Insert(object, check, new(zone()) UniqueSet<Map>(map, zone()));
   }
 
   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());
   }
 
+  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_)
 };
 
 
 // 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) { }
+      : objects_(0, zone), maps_stored_(false) {}
 
-  inline bool Disabled() {
-    return false;  // Effects are _not_ disabled.
-  }
+  // 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: {
-        stores_.Add(HStoreNamedField::cast(instr), zone);
+        HStoreNamedField* store = HStoreNamedField::cast(instr);
+        if (store->access().IsMap() && store->has_transition()) {
+          objects_.Add(store->object(), zone);
+        }
         break;
       }
-      case HValue::kOsrEntry: {
-        // Kill everything. Loads must not be hoisted past the OSR entry.
-        maps_stored_ = true;
+      case HValue::kTransitionElementsKind: {
+        objects_.Add(HTransitionElementsKind::cast(instr)->object(), zone);
+        break;
       }
       default: {
         maps_stored_ |= (instr->CheckChangesFlag(kMaps) |
+                         instr->CheckChangesFlag(kOsrEntries) |
                          instr->CheckChangesFlag(kElementsKind));
       }
     }
   }
 
   // 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());
-      }
+    // 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_;
-    for (int i = 0; i < that->stores_.length(); i++) {
-      stores_.Add(that->stores_[i], zone);
+    for (int i = 0; i < that->objects_.length(); ++i) {
+      objects_.Add(that->objects_[i], zone);
     }
   }
 
  private:
+  ZoneList<HValue*> objects_;
   bool maps_stored_ : 1;
-  ZoneList<HStoreNamedField*> stores_;
 };
 
 
 // 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