Improve SminessPropagator to propagate sminess across cycles of phis.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2012, 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/flow_graph_builder.h"
 #include "vm/hash_map.h"
@@ skipping 1033 matching lines @@
         worklist_(0) { }
 
   void Propagate();
 
  private:
   void PropagateSminessRecursive(BlockEntryInstr* block);
   void AddToWorklist(PhiInstr* phi);
   PhiInstr* RemoveLastFromWorklist();
   void ProcessPhis();
 
+  void MarkPossiblySmiPhi(PhiInstr* phi);
+
   FlowGraph* flow_graph_;
 
   BitVector* known_smis_;
   GrowableArray<intptr_t> rollback_checks_;
 
   BitVector* in_worklist_;
   GrowableArray<PhiInstr*> worklist_;
 };
 
 
@@ skipping 10 matching lines @@
 
 PhiInstr* SminessPropagator::RemoveLastFromWorklist() {
   PhiInstr* phi = worklist_.Last();
   ASSERT(in_worklist_->Contains(phi->ssa_temp_index()));
   worklist_.RemoveLast();
   in_worklist_->Remove(phi->ssa_temp_index());
   return phi;
 }
 
 
-static bool IsSmiPhi(PhiInstr* phi) {
+static bool IsDefinitelySmiPhi(PhiInstr* phi) {
   for (intptr_t i = 0; i < phi->InputCount(); i++) {
-    Value* input = phi->InputAt(i);
-    if ((input->definition() != phi) &&
-        (input->ResultCid() != kSmiCid)) {
+    const intptr_t cid = phi->InputAt(i)->ResultCid();
+    if (cid != kSmiCid) {
       return false;
     }
   }
   return true;
 }
 
 
+static bool IsPossiblySmiPhi(PhiInstr* phi) {
+  for (intptr_t i = 0; i < phi->InputCount(); i++) {
+    const intptr_t cid = phi->InputAt(i)->ResultCid();
+    if ((cid != kSmiCid) && (cid != kDynamicCid)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
+void SminessPropagator::MarkPossiblySmiPhi(PhiInstr* phi) {
+  for (intptr_t i = 0; i < phi->InputCount(); i++) {
+    Value* input = phi->InputAt(i);
+    if ((input->ResultCid() != kSmiCid) &&
+        !in_worklist_->Contains(input->definition()->ssa_temp_index())) {
+      // Place all operands that are potentially smi phis to worklist.

[Florian Schneider, 2012/09/20 11:48:50]

I don't see how input operands can be affected by the current phi. Shouldn't it
be enough to add all uses of this phi to the worklist?

+      PhiInstr* phi_input = input->definition()->AsPhi();
+      if ((phi_input != NULL) && IsPossiblySmiPhi(phi_input)) {
+        AddToWorklist(phi_input);
+        continue;
+      }
+      return;
+    }
+  }
+
+  phi->SetPropagatedCid(kSmiCid);
+
+  // Place all phis that use this phi and can potentially be smi to worklist.
+  for (Value* use = phi->input_use_list();
+       use != NULL;
+       use = use->next_use()) {
+    PhiInstr* phi_use = use->definition()->AsPhi();
+    if ((phi_use != NULL) &&
+        (phi_use->GetPropagatedCid() == kDynamicCid) &&
+        IsPossiblySmiPhi(phi_use)) {
+      AddToWorklist(phi_use);

[Florian Schneider, 2012/09/20 11:48:50]

Maybe rename this to AppendToWorkList since the algorithm relies on the fact
that new phis are added at the end of the list.

+    }
+  }
+}
+
+
 void SminessPropagator::ProcessPhis() {
+  // First optimistically mark all possible smi-phis: phi is possibly a smi if
+  // its operands are either smis or phis in the worklist.
+  for (intptr_t i = 0; i < worklist_.length(); i++) {
+    PhiInstr* phi = worklist_[i];
+    ASSERT(phi->GetPropagatedCid() == kDynamicCid);
+    MarkPossiblySmiPhi(phi);
+  }
+
+  // Now unmark phis that are not definitely smi: that is have only
+  // smi operands.
   while (!worklist_.is_empty()) {
     PhiInstr* phi = RemoveLastFromWorklist();
-    if (IsSmiPhi(phi)) {
-      ASSERT(phi->GetPropagatedCid() != kSmiCid);
-      phi->SetPropagatedCid(kSmiCid);
+    if (!IsDefinitelySmiPhi(phi)) {
+      // Phi result is not a smi. Propagate this fact to phis that depend on it.
+      phi->SetPropagatedCid(kDynamicCid);
       for (Value* use = phi->input_use_list();
            use != NULL;
            use = use->next_use()) {
-        if (use->definition()->IsPhi() &&
-            (use->definition()->GetPropagatedCid() != kSmiCid)) {
-          AddToWorklist(use->definition()->AsPhi());
+        PhiInstr* phi_use = use->definition()->AsPhi();
+        if ((phi_use != NULL) && (phi_use->GetPropagatedCid() == kSmiCid)) {
+          AddToWorklist(phi_use);
         }
       }
     }
   }
 }
 
 
 void SminessPropagator::PropagateSminessRecursive(BlockEntryInstr* block) {
   const intptr_t rollback_point = rollback_checks_.length();
 
@@ skipping 1338 matching lines @@
        it.Advance()) {
     JoinEntryInstr* join = it.Current()->AsJoinEntry();
     if (join != NULL) join->EliminateUnreachablePhiInputs();
   }
 
   graph_->ComputeUseLists();
 }
 
 
 }  // namespace dart