Use range analysis to improve constant propagation.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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/flow_graph_compiler.h"
@@ skipping 2458 matching lines @@
       op_kind = FlipComparison(rel_op->kind());
     }
 
     // Constrain definition at the true successor.
     ConstraintInstr* true_constraint =
         InsertConstraintFor(defn,
                             ConstraintRange(op_kind, boundary),
                             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 =
         InsertConstraintFor(
             defn,
             ConstraintRange(Token::NegateComparison(op_kind), boundary),
             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());
+    }
   }
 }
 
 void RangeAnalysis::InsertConstraintsFor(Definition* defn) {
   for (Value* use = defn->input_use_list();
        use != NULL;
        use = use->next_use()) {
     if (use->instruction()->IsBranch()) {
       ConstrainValueAfterBranch(defn, use);
     } else if (use->instruction()->IsCheckArrayBound()) {
@@ skipping 197 matching lines @@
   }
 
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
 
     Definition* defn = current->AsDefinition();
     if ((defn != NULL) &&
         (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();
       RangeBoundary array_length =
           RangeBoundary::FromDefinition(check->length()->definition());
       if (check->IsRedundant(array_length)) {
         it.RemoveCurrentFromGraph();
       }
     }
   }
@@ skipping 895 matching lines @@
 
 
 void ConstantPropagator::Optimize(FlowGraph* graph) {
   GrowableArray<BlockEntryInstr*> ignored;
   ConstantPropagator cp(graph, ignored);
   cp.Analyze();
   cp.Transform();
 }
 
 
+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());
     block_worklist_.Add(block);
   }
 }
 
 
 void ConstantPropagator::SetValue(Definition* definition, const Object& value) {
   // We would like to assert we only go up (toward non-constant) in the lattice.
@@ skipping 698 matching lines @@
         use = use->next_use();
       }
     } else {
       BlockEntryInstr* block = block_worklist_.RemoveLast();
       block->Accept(this);
     }
   }
 }
 
 
+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");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 
   GrowableArray<PhiInstr*> redundant_phis(10);
 
   // We will recompute dominators, block ordering, block ids, block last
@@ skipping 319 matching lines @@
   if (changed) {
     // We may have changed the block order and the dominator tree.
     flow_graph->DiscoverBlocks();
     GrowableArray<BitVector*> dominance_frontier;
     flow_graph->ComputeDominators(&dominance_frontier);
   }
 }
 
 
 }  // namespace dart