Simplify range analysis algorithm.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index 27d1d8ff7120f852878aa63343ec1455ef33c2cf..d8b44efe37e817da6eac1111dfef340af26f248a 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -1602,7 +1602,9 @@ void FlowGraphOptimizer::PropagateSminess() {
 // Range analysis for smi values.
 class RangeAnalysis : public ValueObject {
  public:
-  explicit RangeAnalysis(FlowGraph* flow_graph) : flow_graph_(flow_graph) { }
+  explicit RangeAnalysis(FlowGraph* flow_graph)
+      : flow_graph_(flow_graph),
+        marked_defns_(NULL) { }
 
   // Infer ranges for all values and remove overflow checks from binary smi
   // operations when proven redundant.
@@ -1635,42 +1637,41 @@ class RangeAnalysis : public ValueObject {
                            Instruction* dom,
                            Definition* other);
 
-  // Propagate range information until fix-point is reached.
+
+  // Walk the dominator tree and infer ranges for smi values.
   void InferRanges();
+  void InferRangesRecursive(BlockEntryInstr* block);
 
-  void ProcessWorklist(Definition::RangeOperator op);
+  enum GrowthDirection {

[Florian Schneider, 2012/10/25 11:15:43]

I'd rename this to just Direction. Growth implies growing numbers which is not
the case with e.g. i--.

[Vyacheslav Egorov (Google), 2012/10/25 11:24:27]

Done.

+    UNKNOWN,

[Florian Schneider, 2012/10/25 11:15:43]

Maybe rename to the more common style

kUnknown, kPositive, kNegative, kBoth

[Vyacheslav Egorov (Google), 2012/10/25 11:24:27]

Done.

+    POSITIVE,
+    NEGATIVE,
+    BOTH
+  };
 
-  // Walk the dominator tree, initialize ranges for smi values and place them
-  // to the worklist.
-  void InitializeRangesRecursive(BlockEntryInstr* block);
+  Range* InferInductionVariableRange(JoinEntryInstr* loop_header,
+                                     PhiInstr* var);
 
-  // Remove artificial Constraint instructions and replace them with actual
-  // unconstrained definitions.
-  void RemoveConstraints();
+  void ResetWorklist();
+  void MarkDefinition(Definition* defn);
 
-  void CreateWorklists();
+  static GrowthDirection ToGrowthDirection(Value* val);
 
-  void AddToWorklist(Definition* value) {
-    const intptr_t index = value->ssa_temp_index();
-    if (!in_worklist_->Contains(index)) {
-      in_worklist_->Add(index);
-      worklist_.Add(value);
-    }
+  static GrowthDirection Invert(GrowthDirection direction) {
+    return (direction == POSITIVE) ? NEGATIVE : POSITIVE;
   }
 
-  bool IsWorklistEmpty() const {
-    return worklist_.is_empty();
-  }
-
-  Definition* RemoveLastFromWorklist() {
-    Definition* defn = worklist_.Last();
-    worklist_.RemoveLast();
-    ASSERT(in_worklist_->Contains(defn->ssa_temp_index()));
-    in_worklist_->Remove(defn->ssa_temp_index());
-    return defn;
+  static void UpdateDirection(GrowthDirection* direction,
+                              GrowthDirection new_direction) {
+    if (*direction != new_direction) {
+      if (*direction != UNKNOWN) new_direction = BOTH;
+      *direction = new_direction;
+    }
   }
 
-  void SwapWorklists();
+  // Remove artificial Constraint instructions and replace them with actual
+  // unconstrained definitions.
+  void RemoveConstraints();
 
   FlowGraph* flow_graph_;
 
@@ -1684,9 +1685,9 @@ class RangeAnalysis : public ValueObject {
   // Bitvector for a quick filtering of known smi values.
   BitVector* smi_definitions_;
 
-  // Worklist used during range propagation.
+  // Worklist for induction variables analysis.
   GrowableArray<Definition*> worklist_;
-  BitVector* in_worklist_;
+  BitVector* marked_defns_;
 
   DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
 };
@@ -1941,129 +1942,194 @@ void RangeAnalysis::InsertConstraints() {
 }
 
 
-void RangeAnalysis::InitializeRangesRecursive(BlockEntryInstr* block) {
-  JoinEntryInstr* join = block->AsJoinEntry();
-  if (join != NULL) {
-    for (PhiIterator it(join); !it.Done(); it.Advance()) {
-      PhiInstr* phi = it.Current();
-      if (smi_definitions_->Contains(phi->ssa_temp_index())) {
-        phi->InferRange(Definition::kRangeInit);
-        AddToWorklist(phi);
-      }
-    }
+void RangeAnalysis::ResetWorklist() {
+  if (marked_defns_ == NULL) {
+    marked_defns_ = new BitVector(flow_graph_->current_ssa_temp_index());
+  } else {
+    marked_defns_->Clear();
   }
+  worklist_.Clear();
+}
 
-  for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
-    Definition* defn = it.Current()->AsDefinition();
-    if ((defn != NULL) &&
-        (defn->ssa_temp_index() != -1) &&
-        smi_definitions_->Contains(defn->ssa_temp_index())) {
-      defn->InferRange(Definition::kRangeInit);
-      AddToWorklist(defn);
-    }
+
+void RangeAnalysis::MarkDefinition(Definition* defn) {
+  // Unwrap constrained value.
+  while (defn->IsConstraint()) {
+    defn = defn->AsConstraint()->value()->definition();
   }
 
-  for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
-    InitializeRangesRecursive(block->dominated_blocks()[i]);
+  if (!marked_defns_->Contains(defn->ssa_temp_index())) {
+    worklist_.Add(defn);
+    marked_defns_->Add(defn->ssa_temp_index());
   }
 }
 
 
-void RangeAnalysis::CreateWorklists() {
-  in_worklist_ = new BitVector(flow_graph_->current_ssa_temp_index());
+RangeAnalysis::GrowthDirection RangeAnalysis::ToGrowthDirection(Value* val) {
+  if (val->BindsToConstant()) {
+    return (Smi::Cast(val->BoundConstant()).Value() >= 0) ? POSITIVE : NEGATIVE;
+  } else if (val->definition()->range() != NULL) {
+    Range* range = val->definition()->range();
+    if (Range::ConstantMin(range).value() >= 0) {
+      return POSITIVE;
+    } else if (Range::ConstantMax(range).value() <= 0) {
+      return NEGATIVE;
+    }
+  }
+  return UNKNOWN;
 }
 
 
-void RangeAnalysis::ProcessWorklist(Definition::RangeOperator op) {
-  // Iterate until fix point is reached.
-  while (!IsWorklistEmpty()) {
-    Definition* defn = RemoveLastFromWorklist();
-    if (FLAG_trace_range_analysis) {
-      OS::Print("infering range for v%"Pd" %s\n",
-                defn->ssa_temp_index(),
-                Range::ToCString(defn->range()));
-    }
-    if (defn->InferRange(op)) {  // Update the range.
-      if (FLAG_trace_range_analysis) {
-        OS::Print("  changed to %s\n", Range::ToCString(defn->range()));
+Range* RangeAnalysis::InferInductionVariableRange(JoinEntryInstr* loop_header,
+                                                  PhiInstr* var) {
+  BitVector* loop_info = loop_header->loop_info();
+
+  Definition* initial_value = NULL;
+  GrowthDirection direction = UNKNOWN;
+
+  ResetWorklist();
+  MarkDefinition(var);
+  while (!worklist_.is_empty()) {
+    Definition* defn = worklist_.Last();
+    worklist_.RemoveLast();
+
+    if (defn->IsPhi()) {
+      PhiInstr* phi = defn->AsPhi();
+      for (intptr_t i = 0; i < phi->InputCount(); i++) {
+        Definition* defn = phi->InputAt(i)->definition();
+
+        if (!loop_info->Contains(defn->GetBlock()->preorder_number())) {
+          // The value is comming from outside of the loop.

[Florian Schneider, 2012/10/25 11:15:43]

s/comming/coming/

[Vyacheslav Egorov (Google), 2012/10/25 11:24:27]

Done.

+          if (initial_value == NULL) {
+            initial_value = defn;
+            continue;
+          } else if (initial_value == defn) {
+            continue;
+          } else {
+            return NULL;
+          }
+        }
+
+        MarkDefinition(defn);
       }
-      // Range change. Place all uses to the worklist.
-      for (Value* use = defn->input_use_list();
-           use != NULL;
-           use = use->next_use()) {
-        Definition* use_defn = use->instruction()->AsDefinition();
-        if ((use_defn != NULL) &&
-            (use_defn->ssa_temp_index() != -1) &&
-            smi_definitions_->Contains(use_defn->ssa_temp_index())) {
-          AddToWorklist(use_defn);
+    } else if (defn->IsBinarySmiOp()) {
+      BinarySmiOpInstr* binary_op = defn->AsBinarySmiOp();
+
+      switch (binary_op->op_kind()) {
+        case Token::kADD: {
+          const GrowthDirection growth_right =
+              ToGrowthDirection(binary_op->right());
+          if (growth_right != UNKNOWN) {
+            UpdateDirection(&direction, growth_right);
+            MarkDefinition(binary_op->left()->definition());
+            break;
+          }
+
+          const GrowthDirection growth_left =
+              ToGrowthDirection(binary_op->left());
+          if (growth_left != UNKNOWN) {
+            UpdateDirection(&direction, growth_left);
+            MarkDefinition(binary_op->right()->definition());
+            break;
+          }
+
+          return NULL;
         }
+
+        case Token::kSUB: {
+          const GrowthDirection growth_right =
+              ToGrowthDirection(binary_op->right());
+          if (growth_right != UNKNOWN) {
+            UpdateDirection(&direction, Invert(growth_right));
+            MarkDefinition(binary_op->left()->definition());
+            break;
+          }
+          return NULL;
+        }
+
+        default:
+          return NULL;
       }
+    } else {
+      return NULL;
     }
   }
-}
 
 
-void RangeAnalysis::InferRanges() {
-  CreateWorklists();
+  // We transitively discovered all dependecies of the given phi

[Florian Schneider, 2012/10/25 11:15:43]

s/dependecies/dependencies/

[Vyacheslav Egorov (Google), 2012/10/25 11:24:27]

Done.

+  // and confirmed that it depends on a sigle value comming from outside of

[Florian Schneider, 2012/10/25 11:15:43]

s/sigle/single/
s/comming/coming/g

[Vyacheslav Egorov (Google), 2012/10/25 11:24:27]

Done.

+  // the loop and some linear combinations of itself.
+  // Compute the range based on initial value and the direction of the growth.
+  switch (direction) {
+    case POSITIVE:
+      return new Range(RangeBoundary::FromDefinition(initial_value),
+                       RangeBoundary::MaxSmi());
 
-  // Initialize bitvector for quick filtering of smi values.
-  smi_definitions_ = new BitVector(flow_graph_->current_ssa_temp_index());
-  for (intptr_t i = 0; i < smi_values_.length(); i++) {
-    smi_definitions_->Add(smi_values_[i]->ssa_temp_index());
-  }
-  for (intptr_t i = 0; i < constraints_.length(); i++) {
-    smi_definitions_->Add(constraints_[i]->ssa_temp_index());
+    case NEGATIVE:
+      return new Range(RangeBoundary::MinSmi(),
+                       RangeBoundary::FromDefinition(initial_value));
+
+    case UNKNOWN:
+    case BOTH:
+      return Range::Unknown();
   }
 
-  // Infer initial values of ranges.
-  InitializeRangesRecursive(flow_graph_->graph_entry());
+  UNREACHABLE();
+  return NULL;
+}
 
-  for (intptr_t i = 0; i < smi_values_.length(); i++) {
-    if (smi_values_[i]->IsPhi() &&
-        smi_values_[i]->InferRange(Definition::kRangeInit)) {
-      Definition* defn = smi_values_[i];
-      for (Value* use = defn->input_use_list();
-           use != NULL;
-           use = use->next_use()) {
-        Definition* use_defn = use->instruction()->AsDefinition();
-        if ((use_defn != NULL) &&
-            (use_defn->ssa_temp_index() != -1) &&
-            smi_definitions_->Contains(use_defn->ssa_temp_index())) {
-          AddToWorklist(use_defn);
+
+void RangeAnalysis::InferRangesRecursive(BlockEntryInstr* block) {
+  JoinEntryInstr* join = block->AsJoinEntry();
+  if (join != NULL) {
+    const bool is_loop_header = (join->loop_info() != NULL);
+    for (PhiIterator it(join); !it.Done(); it.Advance()) {
+      PhiInstr* phi = it.Current();
+      if (smi_definitions_->Contains(phi->ssa_temp_index())) {
+        if (is_loop_header) {
+          // Try recognizing simple induction variables.
+          Range* range = InferInductionVariableRange(join, phi);
+          if (range != NULL) {
+            phi->range_ = range;
+            continue;
+          }
         }
+
+        phi->InferRange();
       }
     }
   }
 
-  if (FLAG_trace_range_analysis) {
-    OS::Print("---- after initialization -------\n");
-    FlowGraphPrinter printer(*flow_graph_);
-    printer.PrintBlocks();
+  for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+    Definition* defn = it.Current()->AsDefinition();
+    if ((defn != NULL) &&
+        (defn->ssa_temp_index() != -1) &&
+        smi_definitions_->Contains(defn->ssa_temp_index())) {
+      defn->InferRange();
+    }
   }
 
-  if (FLAG_trace_range_analysis) {
-    OS::Print("---- widening ---------\n");
+  for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
+    InferRangesRecursive(block->dominated_blocks()[i]);
   }
-  ProcessWorklist(Definition::kRangeWiden);
+}
 
-  if (FLAG_trace_range_analysis) {
-    OS::Print("---- after widening -------\n");
-    FlowGraphPrinter printer(*flow_graph_);
-    printer.PrintBlocks();
-  }
 
-  if (FLAG_trace_range_analysis) {
-    OS::Print("---- narrowing ---------\n");
-  }
-  // Only phis can change under narrowing operator. Place all phis
-  // into the worklist.
+void RangeAnalysis::InferRanges() {
+  // Initialize bitvector for quick filtering of smi values.
+  smi_definitions_ = new BitVector(flow_graph_->current_ssa_temp_index());
   for (intptr_t i = 0; i < smi_values_.length(); i++) {
-    if (smi_values_[i]->IsPhi()) AddToWorklist(smi_values_[i]);
+    smi_definitions_->Add(smi_values_[i]->ssa_temp_index());
   }
-  ProcessWorklist(Definition::kRangeNarrow);
+  for (intptr_t i = 0; i < constraints_.length(); i++) {
+    smi_definitions_->Add(constraints_[i]->ssa_temp_index());
+  }
+
+  // Infer initial values of ranges.
+  InferRangesRecursive(flow_graph_->graph_entry());
 
   if (FLAG_trace_range_analysis) {
-    OS::Print("---- after narrowing -------\n");
+    OS::Print("---- after range analysis -------\n");
     FlowGraphPrinter printer(*flow_graph_);
     printer.PrintBlocks();
   }