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 16 matching lines @@
   Range* constraint_range = new Range(
       RangeBoundary::FromConstant(0),
       RangeBoundary::FromDefinition(length, -1));
   InsertConstraintFor(defn, constraint_range, check);
 }
 
 
 void RangeAnalysis::InsertConstraints() {
   for (intptr_t i = 0; i < smi_checks_.length(); i++) {
     CheckSmiInstr* check = smi_checks_[i];
-    ConstraintInstr* constraint =
-        InsertConstraintFor(check->value()->definition(),
-                            Range::Unknown(),
-                            check);
-    if (constraint != NULL) {
-      InsertConstraintsFor(constraint);  // Constrain uses further.
-    }
+    InsertConstraintFor(check->value()->definition(), Range::Unknown(), check);
   }
 
   for (intptr_t i = 0; i < smi_values_.length(); i++) {
     InsertConstraintsFor(smi_values_[i]);
   }
+
+  for (intptr_t i = 0; i < constraints_.length(); i++) {
+    InsertConstraintsFor(constraints_[i]);
+  }
 }
 
 
 void RangeAnalysis::ResetWorklist() {
   if (marked_defns_ == NULL) {
     marked_defns_ = new BitVector(flow_graph_->current_ssa_temp_index());
   } else {
     marked_defns_->Clear();
   }
   worklist_.Clear();
@@ skipping 1064 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