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.
 };
 
 
-// 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 56 matching lines @@
       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());
     }
     copy->cursor_ = cursor_;
     copy->size_ = size_;
 
+    copy->InheritPhiOperands(succ, this, from_block, COPY, 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) {
       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,

[titzer, 2014/02/04 13:12:26]

We should rename "that" to be "pred", to be more clear.

[Igor Sheludko, 2014/02/05 11:28:01]

Done.

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

To be clearer:
"that_block" to "pred_block"

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

Done.

                      HBasicBlock* that_block, Zone* zone) {
     if (that_block->IsReachable()) {
       if (that->size_ == 0) {
         // If the other state is empty, simply reset.
         size_ = 0;
         cursor_ = 0;
       } else {
+        InheritPhiOperands(succ, that, that_block, MERGE, zone);

[titzer, 2014/02/04 13:12:26]

Why don't you process the phis after first merging the tables? That way, you can
just go through the phis of this block and then insert (in the case of COPY) or
union (in the case of MERGE) their entries with the entries from the incoming
block. I think that would be significantly simpler, and potentially faster.

[Igor Sheludko, 2014/02/05 11:28:01]

Good idea!

+
         bool compact = false;
         for (int i = 0; i < size_; i++) {
           HCheckTableEntry* this_entry = &entries_[i];

[titzer, 2014/02/04 13:12:26]

Using the above suggestion, you can simply retain any entries in this table for
phis that are defined in "succ". Then you don't need the dominance check for the
other phis, since "that" can't have entries for anything that doesn't dominate
"succ" (i.e. they are handled implicitly).

[Igor Sheludko, 2014/02/05 11:28:01]

Done.

           HCheckTableEntry* that_entry = that->Find(this_entry->object_);
+          // Keep those phis in the table that dominate succ block.
           if (that_entry == NULL) {
-            this_entry->object_ = NULL;
-            compact = true;
+            if (!this_entry->object_->IsPhi() ||
+                !this_entry->object_->block()->EqualToOrDominates(succ)) {
+              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(), that_block->block_id());
       Print();
     }
     return this;
   }
 
+  enum InheritPhiOperandsMode { COPY, MERGE };
+  void InheritPhiOperands(HBasicBlock* succ, HCheckTable* that,
+                          HBasicBlock* that_block, InheritPhiOperandsMode mode,
+                          Zone* zone) {
+    if (succ->predecessors()->length() == 1) return;

[titzer, 2014/02/04 13:12:26]

I think you want to check succ->phis()->length() == 0 for the early return here.

[Igor Sheludko, 2014/02/05 11:28:01]

Done.

+
+    int pred_index = succ->PredecessorIndexOf(that_block);
+
+    for (int i = 0; i < that->size_; i++) {
+      HCheckTableEntry* that_entry = &that->entries_[i];
+      if (that_entry->object_ != NULL) {
+        HPhi* phi = NULL;
+        for (int phi_index = 0;
+             phi_index < succ->phis()->length();
+             ++phi_index) {
+          HPhi* tmp_phi = succ->phis()->at(phi_index);
+          if (tmp_phi->OperandAt(pred_index) == that_entry->object_) {
+            phi = tmp_phi;
+            break;
+          }
+        }
+
+        if (phi != NULL) {
+          // Found a |phi| with operand equal to |that_entry->object_|.
+          HCheckTableEntry* phi_entry = (mode == MERGE) ? Find(phi) : NULL;
+          if (phi_entry == NULL) {
+            // Create an entry for a phi in the table.
+            Insert(phi, NULL, that_entry->maps_);
+          } else {
+            phi_entry->maps_ =
+                phi_entry->maps_->Union(that_entry->maps_, phase_->zone());
+          }
+        }
+      }
+    }
+  }
+
   void ReduceCheckMaps(HCheckMaps* instr) {
     HValue* object = instr->value()->ActualValue();
     HCheckTableEntry* entry = Find(object);
     if (entry != NULL) {
       // entry found;
       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 (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;
       }
-      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 315 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