Improve LoadOptimizer::ReplacePhiWith.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 6827 matching lines @@
     // All phis in the worklist are redundant and have the same computed
     // value on all code paths.
     ASSERT(value != NULL);
     for (intptr_t i = 0; i < worklist_.length(); i++) {
       worklist_[i]->ReplaceUsesWith(value);
     }
 
     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;
   }
 
   // Insert the given phi into the graph. Attempt to find an equal one in the
   // target block first.
   // Returns true if the phi was inserted and false if it was replaced.
   bool EmitPhi(PhiInstr* phi) {
     for (PhiIterator it(phi->block()); !it.Done(); it.Advance()) {
       if (ReplacePhiWith(phi, it.Current())) {
         return false;
@@ skipping 58 matching lines @@
   // represent those ids.
   GrowableArray<ZoneGrowableArray<Definition*>*> out_values_;
 
   // List of phis generated during ComputeOutValues and ForwardLoads.
   // Some of these phis might be redundant and thus a separate pass is
   // needed to emit only non-redundant ones.
   GrowableArray<PhiInstr*> phis_;
 
   // 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_;
 
   DISALLOW_COPY_AND_ASSIGN(LoadOptimizer);
 };
 
 
 class StoreOptimizer : public LivenessAnalysis {
  public:
   StoreOptimizer(FlowGraph* graph,
@@ skipping 2956 matching lines @@
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) {
     CreateMaterializationAt(
         exits_collector_.exits()[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart