Improve LoadOptimizer::ReplacePhiWith.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index 64599e74f1057cdda9e30c976dd98bca3017c6fc..bf3cdbf408ead15c207450b9149ad44289572ee6 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -6845,79 +6845,149 @@ class LoadOptimizer : public ValueObject {
     return true;
   }
 
-  bool AddPhiPairToWorklist(PhiInstr* a, PhiInstr* b) {
-    // Can't compare two phis from different blocks.
-    if (a->block() != b->block()) {
+  // Returns true if definitions are congruent assuming their inputs
+  // are congruent.
+  bool CanBeCongruent(Definition* a, Definition* b) {
+    return (a->tag() == b->tag()) &&
+       ((a->IsPhi() && (a->GetBlock() == b->GetBlock())) ||
+        (a->AllowsCSE() && a->Dependencies().IsNone() &&
+         a->AttributesEqual(b)));
+  }
+
+  // Given two definitions check if they are congruent under assumption that
+  // their inputs will be proven congruent. If they are - add them to the
+  // worklist to check their inputs' congruency.
+  // Returns true if pair was added to the worklist or is already in the
+  // worklist and false if a and b are not congruent.
+  bool AddPairToCongruencyWorklist(Definition* a, Definition* b) {
+    if (!CanBeCongruent(a, b)) {
       return false;
     }
 
     // If a is already in the worklist check if it is being compared to b.
     // Give up if it is not.
     if (in_worklist_->Contains(a->ssa_temp_index())) {
-      for (intptr_t i = 0; i < worklist_.length(); i += 2) {
-        if (a == worklist_[i]) {
-          return (b == worklist_[i + 1]);
+      for (intptr_t i = 0; i < congruency_worklist_.length(); i += 2) {
+        if (a == congruency_worklist_[i]) {
+          return (b == congruency_worklist_[i + 1]);
         }
       }
       UNREACHABLE();
+    } else if (in_worklist_->Contains(b->ssa_temp_index())) {
+      return AddPairToCongruencyWorklist(b, a);
     }
 
-    worklist_.Add(a);
-    worklist_.Add(b);
+    congruency_worklist_.Add(a);
+    congruency_worklist_.Add(b);
     in_worklist_->Add(a->ssa_temp_index());
     return true;
   }
 
-  // Replace the given phi with another if they are equal.
+  bool AreInputsCongruent(Definition* a, Definition* b) {
+    ASSERT(a->tag() == b->tag());
+    ASSERT(a->InputCount() == b->InputCount());
+    for (intptr_t j = 0; j < a->InputCount(); j++) {
+      Definition* inputA = a->InputAt(j)->definition();
+      Definition* inputB = b->InputAt(j)->definition();
+
+      if (inputA != inputB) {
+        if (!AddPairToCongruencyWorklist(inputA, inputB)) {
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  // Returns true if instruction dom dominates instruction other.
+  static bool Dominates(Instruction* dom, Instruction* other) {
+    BlockEntryInstr* dom_block = dom->GetBlock();
+    BlockEntryInstr* other_block = other->GetBlock();
+
+    if (dom_block == other_block) {
+      for (Instruction* current = dom->next();
+           current != NULL;
+           current = current->next()) {
+        if (current == other) {
+          return true;
+        }
+      }
+      return false;
+    }
+
+    return dom_block->Dominates(other_block);
+  }
+
+  // Replace the given phi with another if they are congruent.
   // Returns true if succeeds.
   bool ReplacePhiWith(PhiInstr* phi, PhiInstr* replacement) {
     ASSERT(phi->InputCount() == replacement->InputCount());
     ASSERT(phi->block() == replacement->block());
 
-    worklist_.Clear();
+    congruency_worklist_.Clear();
     if (in_worklist_ == NULL) {
       in_worklist_ = new(I) BitVector(graph_->current_ssa_temp_index());
     } else {
       in_worklist_->Clear();
     }
 
-    // During the comparison worklist contains pairs of phis to be compared.
-    AddPhiPairToWorklist(phi, replacement);
+    // During the comparison worklist contains pairs of definintions to be

[Florian Schneider, 2014/09/04 12:30:48]

s/definintions/definitions/

[Vyacheslav Egorov (Google), 2014/09/04 12:56:13]

Done.

+    // compared.
+    if (!AddPairToCongruencyWorklist(phi, replacement)) {
+      return false;
+    }
 
     // Process the worklist. It might grow during each comparison step.
-    for (intptr_t i = 0; i < worklist_.length(); i += 2) {
-      PhiInstr* a = worklist_[i];
-      PhiInstr* b = worklist_[i + 1];
-
-      // Compare phi inputs.
-      for (intptr_t j = 0; j < a->InputCount(); j++) {
-        Definition* inputA = a->InputAt(j)->definition();
-        Definition* inputB = b->InputAt(j)->definition();
-
-        if (inputA != inputB) {
-          // If inputs are unequal by they are phis then add them to
-          // the worklist for recursive comparison.
-          if (inputA->IsPhi() && inputB->IsPhi() &&
-              AddPhiPairToWorklist(inputA->AsPhi(), inputB->AsPhi())) {
-            continue;
-          }
-          return false;  // Not equal.
-        }
+    for (intptr_t i = 0; i < congruency_worklist_.length(); i += 2) {
+      if (!AreInputsCongruent(congruency_worklist_[i],
+                              congruency_worklist_[i + 1])) {
+        return false;
       }
     }
 
-    // At this point worklist contains pairs of equal phis. Replace the first
-    // phi in the pair with the second.
-    for (intptr_t i = 0; i < worklist_.length(); i += 2) {
-      PhiInstr* a = worklist_[i];
-      PhiInstr* b = worklist_[i + 1];
+    // At this point worklist contains pairs of congruent definitions.
+    // Replace the one membmer of the pair with another maintaining proper
+    // domination relation between definitions and uses.
+    for (intptr_t i = 0; i < congruency_worklist_.length(); i += 2) {
+      Definition* a = congruency_worklist_[i];
+      Definition* b = congruency_worklist_[i + 1];
+
+      // If these definitions are not phis then we need to pick up one
+      // that dominates another as the replacement: if a dominates b swap them.
+      // Note: both a and b are used as a phi input at the same block B which
+      // means a dominates B and b dominates B, which guarantees that either
+      // a dominates b or b dominates a.
+      if (!a->IsPhi()) {
+        if (Dominates(a, b)) {
+          Definition* t = a;
+          a = b;
+          b = t;
+        }
+        ASSERT(Dominates(b, a));
+      }
+
+      if (FLAG_trace_load_optimization) {
+        OS::Print("Replacing %s with congruent %s\n",
+                  a->ToCString(),
+                  b->ToCString());
+      }
+
       a->ReplaceUsesWith(b);
-      if (a->is_alive()) {
-        a->mark_dead();
-        a->block()->RemovePhi(a);
-        a->UnuseAllInputs();
+      if (a->IsPhi()) {
+        // We might be replacing a phi introduced by the load forwarding
+        // that is not inserted in the graph yet.
+        ASSERT(b->IsPhi());
+        PhiInstr* phi_a = a->AsPhi();
+        if (phi_a->is_alive()) {
+          phi_a->mark_dead();
+          phi_a->block()->RemovePhi(phi_a);
+          phi_a->UnuseAllInputs();
+        }
+      } else {
+        a->RemoveFromGraph();
       }
     }
+
     return true;
   }
 
@@ -6996,8 +7066,11 @@ class LoadOptimizer : public ValueObject {
 
   // Auxiliary worklist used by redundant phi elimination.
   GrowableArray<PhiInstr*> worklist_;
+  GrowableArray<Definition*> congruency_worklist_;
   BitVector* in_worklist_;
 
+

[Florian Schneider, 2014/09/04 12:30:48]

2dd

[Vyacheslav Egorov (Google), 2014/09/04 12:56:13]

Done.

+
   // True if any load was eliminated.
   bool forwarded_;