Check elimination improvement: propagation of state through phis is supported, CheckMap narrowing i…

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 30 matching lines @@
 // For code de-uglification.
 #define TRACE(x) if (FLAG_trace_check_elimination) PrintF x
 
 namespace v8 {
 namespace internal {
 
 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.
+  HInstruction* check_;  // The last check instruction.
+  MapSet maps_;          // The set of known maps for the object.
+  bool remove_at_compation_;

[titzer, 2014/02/05 11:47:46]

I don't think we need this; see below

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

 };
 
 
-// The main datastructure used during check elimination, which stores a
+// 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) {
   }
@@ skipping 47 matching lines @@
     }
 
     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_);
     for (int i = 0; i < size_; i++) {
       HCheckTableEntry* old_entry = &entries_[i];
+      ASSERT(!old_entry->remove_at_compation_);
       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());
+      new_entry->remove_at_compation_ = false;
     }
     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_);

[titzer, 2014/02/05 11:47:46]

I think you want to make a copy of pred_entry->maps_, since these sets are
mutable and the new entry for the phi would alias the maps for the entry that
was just found.

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

+        }
+      }
+    }
+
     // 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) {
       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);
@@ skipping 34 matching lines @@
              succ->block_id(),
              learned ? "learned" : "copied",
              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* that_block, Zone* zone) {
-    if (that_block->IsReachable()) {
-      if (that->size_ == 0) {
+  HCheckTable* Merge(HBasicBlock* succ, HCheckTable* pred,
+                     HBasicBlock* pred_block, Zone* zone) {
+    if (pred_block->IsReachable()) {
+      if (pred->size_ == 0) {
         // If the other state is empty, simply reset.
         size_ = 0;
         cursor_ = 0;
       } else {
         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;
+          if (this_entry->object_->IsPhi() &&
+              this_entry->object_->block() == succ) {
+            // Entries corresponding to succ block's phis are processed
+            // separately.
+            continue;

[titzer, 2014/02/05 11:47:46]

I think in this case you can just immediately process the phi. Look up the
corresponding phi input from pred and union into the entry for this phi. If
there is no entry for the corresponding phi input, kill this entry.

Thus you need only one pass through this table and don't need to iterate over
succ's phi list.

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

+          }
+          HCheckTableEntry* pred_entry = pred->Find(this_entry->object_);
+          if (pred_entry == NULL) {
+            // This entry should be removed, but keep it till the end of
+            // merging as the value could be used as input for one of the
+            // for succ block's phis.
+            this_entry->remove_at_compation_ = true;
             compact = true;
           } else {
             this_entry->maps_ =
-                this_entry->maps_->Union(that_entry->maps_, phase_->zone());
-            if (this_entry->check_ != that_entry->check_) {
+                this_entry->maps_->Union(pred_entry->maps_, phase_->zone());
+            if (this_entry->check_ != pred_entry->check_) {
               this_entry->check_ = NULL;
             }
             ASSERT(this_entry->maps_->size() > 0);
           }
         }
+        // Process succ block's phis.
+        if (succ->phis()->length() > 0) {
+          int pred_index = succ->PredecessorIndexOf(pred_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* phi_entry = Find(phi);
+            if (phi_entry != NULL) {
+              HCheckTableEntry* pred_entry = pred->Find(phi_operand);
+              if (pred_entry == NULL) {
+                phi_entry->object_ = NULL;
+                compact = true;
+              } else {
+                phi_entry->maps_ =
+                    phi_entry->maps_->Union(pred_entry->maps_, phase_->zone());
+              }
+            }
+          }
+        }
         if (compact) Compact();
       }
     }
     if (FLAG_trace_check_elimination) {
       PrintF("B%d checkmaps-table merged with B%d table:\n",
-             succ->block_id(), that_block->block_id());
+             succ->block_id(), pred_block->block_id());
       Print();
     }
     return this;
   }
 
   void ReduceCheckMaps(HCheckMaps* instr) {
     HValue* object = instr->value()->ActualValue();
     HCheckTableEntry* entry = Find(object);
     if (entry != NULL) {
       // entry found;
@@ skipping 10 matching lines @@
           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;
       }
-      i = i->Intersect(a, phase_->zone());
-      if (i->size() == 0) {
+      MapSet intersection = i->Intersect(a, phase_->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 {
-        // TODO(titzer): replace the first check with a more strict check
-        INC_STAT(narrowed_);
+        // 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();
+          HCheckMaps* new_check_maps =
+              HCheckMaps::New(graph->zone(), NULL, instr->value(),
+                              intersection, instr->typecheck());
+          if (entry->check_ != NULL &&
+              entry->check_->block() == instr->block()) {
+            // There is a check in the same block so replace it with a more
+            // strict check and eliminate the second check entirely.
+            new_check_maps->InsertBefore(entry->check_);
+            entry->check_->DeleteAndReplaceWith(new_check_maps);
+            TRACE(("Check #%d narrowed to #%d\n",
+                entry->check_->id(), new_check_maps->id()));
+
+          } else {
+            new_check_maps->InsertBefore(instr);
+          }
+          TRACE(("CheckMaps #%d for #%d narrowed to #%d:\n",
+              instr->id(), instr->value()->id(), new_check_maps->id()));
+          instr->DeleteAndReplaceWith(new_check_maps);
+          entry->check_ = new_check_maps;
+
+          if (FLAG_trace_check_elimination) {
+            Print();
+          }
+          INC_STAT(narrowed_);
+        }
       }
     } else {
       // No entry; insert a new one.
       Insert(object, instr, instr->map_set().Copy(phase_->zone()));
     }
   }
 
   void ReduceCheckValue(HCheckValue* instr) {
     // Canonicalize HCheckValues; they might have their values load-eliminated.
     HValue* value = instr->Canonicalize();
@@ skipping 118 matching lines @@
       }
     }
     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 (entries_[i].object_ != NULL && !entries_[i].remove_at_compation_) {
         if (dest != i) entries_[dest] = entries_[i];
         dest++;
       } else {
         if (i < old_cursor) cursor_--;
         size_--;
       }
     }
     ASSERT(size_ == dest);
     ASSERT(cursor_ <= size_);
 
@@ skipping 11 matching lines @@
       OS::MemMove(&entries_[R], &tmp_entries[0], L * sizeof(HCheckTableEntry));
     }
 
     cursor_ = size_;  // Move cursor to end.
   }
 
   void Print() {
     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());
+      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());
       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 (entry->object_ == NULL) continue;

[titzer, 2014/02/05 11:47:46]

Why did this invariant change?

[Igor Sheludko, 2014/02/05 12:26:10]

Done.

       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) {
     MapSet list = new(phase_->zone()) UniqueSet<Map>();
     list->Add(map, phase_->zone());
     Insert(object, NULL, list);
   }
 
   void Insert(HValue* object, HCheckMaps* check, MapSet maps) {
     HCheckTableEntry* entry = &entries_[cursor_++];
     entry->object_ = object;
     entry->check_ = check;
     entry->maps_ = maps;
+    entry->remove_at_compation_ = false;
     // 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) {
@@ skipping 104 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