Improve SminessPropagator to propagate sminess across cycles of phis.

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 fc311613061d29ff9f3628b1074c474d16a4aa7d..d4b16a15237bf4edf2add108a773be46cc943244 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -1051,6 +1051,8 @@ class SminessPropagator {
   PhiInstr* RemoveLastFromWorklist();
   void ProcessPhis();
 
+  bool IsPossiblySmiPhi(PhiInstr* phi);
+
   FlowGraph* flow_graph_;
 
   BitVector* known_smis_;
@@ -1081,11 +1083,22 @@ PhiInstr* SminessPropagator::RemoveLastFromWorklist() {
 }
 
 
-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)) {
+    if (input->ResultCid() != kSmiCid) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
+bool SminessPropagator::IsPossiblySmiPhi(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())) {

[Florian Schneider, 2012/09/20 08:54:02]

What about operands defined by phis that depend (possibly indirectly) on this
phi? They may not be in the worklist because initially only phis that change
because of a check instruction are added to the worklist.

       return false;
     }
   }
@@ -1094,16 +1107,26 @@ static bool IsSmiPhi(PhiInstr* phi) {
 
 
 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);
+    if (IsPossiblySmiPhi(phi)) phi->SetPropagatedCid(kSmiCid);
+  }
+
+  // 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)) {
+            (use->definition()->GetPropagatedCid() == kSmiCid)) {
           AddToWorklist(use->definition()->AsPhi());
         }
       }