Continue work on type propagation in optimizing compiler (still WIP).

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 10461)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -549,27 +549,95 @@
 void FlowGraphTypePropagator::VisitAssertAssignable(AssertAssignableComp* comp,
                                                     BindInstr* instr) {
   if (FLAG_eliminate_type_checks &&
+      !comp->IsEliminated() &&
       (comp->value() != NULL) &&

[srdjan, 2012/08/09 22:20:53]

When can comp->value() be NULL?

[regis, 2012/08/09 23:51:37]

It cannot. Code reuse error. Removed.

       !comp->dst_type().IsMalformed() &&
-      comp->value()->StaticTypeIsMoreSpecificThan(comp->dst_type())) {
-    // TODO(regis): Eliminate type check by removing comp node from graph.
+      comp->value()->CompileTypeIsMoreSpecificThan(comp->dst_type())) {
+    comp->Eliminate();
     if (FLAG_trace_type_check_elimination) {
       FlowGraphPrinter::PrintTypeCheck(parsed_function(),
                                        comp->token_pos(),
                                        comp->value(),
                                        comp->dst_type(),
                                        comp->dst_name(),
-                                       /*eliminated*/ true);
+                                       comp->IsEliminated());
     }
   }
 }
 
 
-void FlowGraphTypePropagator::VisitBind(BindInstr* instr) {
-  instr->computation()->Accept(this, instr);
+void FlowGraphTypePropagator::VisitGraphEntry(GraphEntryInstr* graph_entry) {
+  if (graph_entry->start_env() == NULL) {
+    return;
+  }
+  // Visit incoming parameters.
+  for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) {
+    Value* val = graph_entry->start_env()->values()[i];
+    if (val->IsUse()) {
+      ParameterInstr* param = val->AsUse()->definition()->AsParameter();
+      if (param != NULL) {
+        VisitParameter(param);
+      }
+    }
+  }
 }
 
 
+void FlowGraphTypePropagator::VisitJoinEntry(JoinEntryInstr* join_entry) {
+  if (join_entry->phis() != NULL) {
+    for (intptr_t i = 0; i < join_entry->phis()->length(); ++i) {
+      PhiInstr* phi = (*join_entry->phis())[i];
+      if (phi != NULL) {
+        VisitPhi(phi);
+      }
+    }
+  }
+}
+
+
+void FlowGraphTypePropagator::VisitBind(BindInstr* bind) {
+  // No need to propagate the input types of the bound computation, as long as
+  // PhiInstr's are handled as part of JoinEntryInstr.
+  // Cache propagated computation type.
+  AbstractType& type = AbstractType::Handle(bind->computation()->CompileType());
+  bool changed = bind->SetPropagatedType(type);
+  if (changed) {
+    still_changing_ = true;
+  }
+}
+
+
+void FlowGraphTypePropagator::VisitPhi(PhiInstr* phi) {
+  // We could set the propagated type of the phi to the least upper bound of its
+  // input propagated types. However, keeping all propagated types allows us to
+  // optimize method dispatch.
+  // TODO(regis): Support a set of propagated types. For now, we compute the
+  // least specific of the input propagated types.
+  AbstractType& type = AbstractType::Handle(phi->LeastSpecificInputType());
+  bool changed = phi->SetPropagatedType(type);
+  if (changed) {
+    still_changing_ = true;
+  }
+}
+
+
+void FlowGraphTypePropagator::VisitParameter(ParameterInstr* param) {
+  // TODO(regis): Set propagated type according to type feedback.
+  bool changed = param->SetPropagatedType(Type::Handle(Type::DynamicType()));
+  if (changed) {
+    still_changing_ = true;
+  }
+}
+
+
+void FlowGraphTypePropagator::PropagateTypes() {
+  do {
+    still_changing_ = false;
+    VisitBlocks();
+  } while (still_changing_);

[srdjan, 2012/08/09 22:20:53]

This could be made more efficient by visiting only blocks that have changed and
not the whole graph. Please add a TODO.

[regis, 2012/08/09 23:51:37]

Added TODO.
I think we would need to revisit blocks that depend on blocks that have changed,
not just those that have changed.

+}
+
+
 void FlowGraphAnalyzer::Analyze() {
   is_leaf_ = true;
   for (intptr_t i = 0; i < blocks_.length(); ++i) {
@@ -584,9 +652,4 @@
   }
 }
 
-
-void FlowGraphTypePropagator::PropagateTypes() {
-  VisitBlocks();
-}
-
 }  // namespace dart