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

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/flow_graph_builder.h"
 #include "vm/il_printer.h"
 #include "vm/object_store.h"
 
@@ skipping 531 matching lines @@
 
 
 void FlowGraphOptimizer::VisitBind(BindInstr* instr) {
   instr->computation()->Accept(this, instr);
 }
 
 
 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) {
     BlockEntryInstr* entry = blocks_[i];
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       LocationSummary* locs = it.Current()->locs();
       if ((locs != NULL) && locs->is_call()) {
         is_leaf_ = false;
         return;
       }
     }
   }
 }
 
-
-void FlowGraphTypePropagator::PropagateTypes() {
-  VisitBlocks();
-}
-
 }  // namespace dart