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();
 
+  bool IsPossiblySmiPhi(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)) {
+    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;
+    }
+  }
   return true;
 }
 
 
 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());
         }
       }
     }
   }
 }
 
 
 void SminessPropagator::PropagateSminessRecursive(BlockEntryInstr* block) {
   const intptr_t rollback_point = rollback_checks_.length();
@@ skipping 1339 matching lines @@
        it.Advance()) {
     JoinEntryInstr* join = it.Current()->AsJoinEntry();
     if (join != NULL) join->EliminateUnreachablePhiInputs();
   }
 
   graph_->ComputeUseLists();
 }
 
 
 }  // namespace dart