Use range analysis to improve constant propagation.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 20842)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -2476,7 +2476,10 @@
                             branch->true_successor());
     // Mark true_constraint an artificial use of boundary. This ensures
     // that constraint's range is recalculated if boundary's range changes.
-    if (true_constraint != NULL) true_constraint->AddDependency(boundary);
+    if (true_constraint != NULL) {
+      true_constraint->AddDependency(boundary);
+      true_constraint->set_target(branch->true_successor());
+    }
 
     // Constrain definition with a negated condition at the false successor.
     ConstraintInstr* false_constraint =
@@ -2486,7 +2489,10 @@
             branch->false_successor());
     // Mark false_constraint an artificial use of boundary. This ensures
     // that constraint's range is recalculated if boundary's range changes.
-    if (false_constraint != NULL) false_constraint->AddDependency(boundary);
+    if (false_constraint != NULL) {
+      false_constraint->AddDependency(boundary);
+      false_constraint->set_target(branch->false_successor());
+    }
   }
 }
 
@@ -2704,6 +2710,31 @@
         (defn->ssa_temp_index() != -1) &&
         smi_definitions_->Contains(defn->ssa_temp_index())) {
       defn->InferRange();
+      // Mark branches that generate unsatisfiable constraints as constant.

[Vyacheslav Egorov (Google), 2013/04/03 19:38:57]

I wonder if this can be moved into the Constraint::InferRange?

[Florian Schneider, 2013/04/04 11:49:15]

Done.

+      if (defn->IsConstraint()) {
+        ConstraintInstr* constraint = defn->AsConstraint();
+        if (constraint->target() != NULL &&
+            constraint->range()->IsUnsatisfiable()) {
+          BranchInstr* branch = constraint->target()->PredecessorAt(0)->
+              last_instruction()->AsBranch();
+          if (constraint->target() == branch->true_successor()) {
+            // True unreachable.
+            if (FLAG_trace_constant_propagation) {
+              OS::Print("Range analysis: True unreachable (B%"Pd")\n",
+                        branch->true_successor()->block_id());
+            }
+            branch->set_constant_target(branch->false_successor());
+          } else {
+            ASSERT(constraint->target() == branch->false_successor());
+            // False unreachable.
+            if (FLAG_trace_constant_propagation) {
+              OS::Print("Range analysis: False unreachable (B%"Pd")\n",
+                        branch->false_successor()->block_id());
+            }
+            branch->set_constant_target(branch->true_successor());
+          }
+        }
+      }
     } else if (FLAG_array_bounds_check_elimination &&
                current->IsCheckArrayBound()) {
       CheckArrayBoundInstr* check = current->AsCheckArrayBound();
@@ -3619,6 +3650,14 @@
 }
 
 
+void ConstantPropagator::OptimizeBranches(FlowGraph* graph) {
+  GrowableArray<BlockEntryInstr*> ignored;
+  ConstantPropagator cp(graph, ignored);
+  cp.VisitBranches();
+  cp.Transform();
+}
+
+
 void ConstantPropagator::SetReachable(BlockEntryInstr* block) {
   if (!reachable_->Contains(block->preorder_number())) {
     reachable_->Add(block->preorder_number());
@@ -4337,6 +4376,40 @@
 }
 
 
+void ConstantPropagator::VisitBranches() {
+  GraphEntryInstr* entry = graph_->graph_entry();
+  reachable_->Add(entry->preorder_number());
+  // TODO(fschneider): Handle CatchEntry.
+  reachable_->Add(entry->normal_entry()->preorder_number());
+  block_worklist_.Add(entry->normal_entry());
+
+  while (!block_worklist_.is_empty()) {
+    BlockEntryInstr* block = block_worklist_.RemoveLast();
+    Instruction* last = block->last_instruction();
+    if (last->IsGoto()) {
+      SetReachable(last->AsGoto()->successor());
+    } else if (last->IsBranch()) {
+      BranchInstr* branch = last->AsBranch();
+      // The current block must be reachable.
+      ASSERT(reachable_->Contains(branch->GetBlock()->preorder_number()));
+      if (branch->constant_target() != NULL) {
+        // Found constant target computed by range analysis.
+        if (branch->constant_target() == branch->true_successor()) {
+          SetReachable(branch->true_successor());
+        } else {
+          ASSERT(branch->constant_target() == branch->false_successor());
+          SetReachable(branch->false_successor());
+        }
+      } else {
+        // No new information: Assume both targets are reachable.
+        SetReachable(branch->true_successor());
+        SetReachable(branch->false_successor());
+      }
+    }
+  }
+}
+
+
 void ConstantPropagator::Transform() {
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== Before constant propagation ====\n");