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 99 matching lines @@
       }
       // Improvements possible:
       // - eliminate redundant HCheckSmi, HCheckInstanceType instructions
       // - track which values have been HCheckHeapObject'd
     }
 
     return this;
   }
 
   // Global analysis: Copy state to successor block.
-  HCheckTable* Copy(HBasicBlock* succ, Zone* zone) {
+  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];
       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);
         if (entry == NULL) {
           copy->Insert(object, cmp->map());
         } else {
           MapSet list = new(phase_->zone()) UniqueSet<Map>();
           list->Add(cmp->map(), phase_->zone());
           entry->maps_ = list;
         }
+        learned = true;
       } else if (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));
           }
         } else if (re == NULL) {
           copy->Insert(right, NULL, le->maps_->Copy(zone));
         } else {
           MapSet intersect = le->maps_->Intersect(re->maps_, zone);
           le->maps_ = intersect;
           re->maps_ = intersect->Copy(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",
+             from_block->block_id());
+      copy->Print();
+    }
+
     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;
+  void Merge(HBasicBlock* succ, HCheckTable* that,
+             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 {
-        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);
+        InheritPhiOperands(succ, that, that_block, MERGE, zone);
+
+        bool compact = false;
+        for (int i = 0; i < size_; i++) {
+          HCheckTableEntry* this_entry = &entries_[i];
+          HCheckTableEntry* that_entry = that->Find(this_entry->object_);
+          // Keep those phis in the table that dominate succ block.
+          if (that_entry == NULL) {
+            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 (compact) Compact();
-    return this;
+
+    if (FLAG_trace_check_elimination) {
+      PrintF("B%d checkmaps-table merged with B%d table:\n",
+             succ->block_id(), that_block->block_id());
+      Print();
+    }
+  }
+
+  enum InheritPhiOperandsMode { COPY, MERGE };
+  void InheritPhiOperands(HBasicBlock* succ, HCheckTable* that,
+                          HBasicBlock* that_block, InheritPhiOperandsMode mode,
+                          Zone* zone) {
+    if (succ->predecessors()->length() == 1) return;
+
+    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 {
-          instr->DeleteAndReplaceWith(instr->value());
+          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 narrowed_maps = i->Intersect(a, phase_->zone());

[titzer, 2014/01/23 18:40:55]

Would prefer the name "intersection" instead of narrowed_maps

[Igor Sheludko, 2014/01/29 12:27:13]

Done.

+      if (narrowed_maps->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
+        // Narrow set of maps in the second check and replace the first
+        // check with a more strict one.
+        entry->maps_ = narrowed_maps;
+        if (narrowed_maps->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(),
+                              narrowed_maps, instr->typecheck());
+          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);

[titzer, 2014/01/23 18:40:55]

I think you want to replace both entry->check_ (if it exists) and instr with the
new check. If the entry->check_ exists, then insert the new check before it.

[Igor Sheludko, 2014/01/29 12:27:13]

Done.

+          entry->check_ = new_check_maps;
+        } else {
+          TRACE(("CheckMaps #%d for #%d narrowed:\n",
+                 instr->id(), instr->value()->id()));

[titzer, 2014/01/23 18:40:55]

In this case, you haven't actually changed anything, so the trace output would
be incorrect.

[Igor Sheludko, 2014/01/29 12:27:13]

Done.

+          entry->check_ = instr;
+        }
+        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.
@@ skipping 316 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