Simplify range analysis algorithm.

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/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 1584 matching lines @@
 
 void FlowGraphOptimizer::PropagateSminess() {
   SminessPropagator propagator(flow_graph_);
   propagator.Propagate();
 }
 
 
 // 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.
   void Analyze();
 
  private:
   // Collect all values that were proven to be smi in smi_values_ array and all
   // CheckSmi instructions in smi_check_ array.
   void CollectSmiValues();
 
@@ skipping 12 matching lines @@
   ConstraintInstr* InsertConstraintFor(Definition* defn,
                                        Range* constraint,
                                        Instruction* after);
 
   // Replace uses of the definition def that are dominated by instruction dom
   // with uses of other definition.
   void RenameDominatedUses(Definition* def,
                            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);
+
+  void ResetWorklist();
+  void MarkDefinition(Definition* defn);
+
+  static GrowthDirection ToGrowthDirection(Value* val);
+
+  static GrowthDirection Invert(GrowthDirection direction) {
+    return (direction == POSITIVE) ? NEGATIVE : POSITIVE;
+  }
+
+  static void UpdateDirection(GrowthDirection* direction,
+                              GrowthDirection new_direction) {
+    if (*direction != new_direction) {
+      if (*direction != UNKNOWN) new_direction = BOTH;
+      *direction = new_direction;
+    }
+  }
 
   // Remove artificial Constraint instructions and replace them with actual
   // unconstrained definitions.
   void RemoveConstraints();
 
-  void CreateWorklists();
-
-  void AddToWorklist(Definition* value) {
-    const intptr_t index = value->ssa_temp_index();
-    if (!in_worklist_->Contains(index)) {
-      in_worklist_->Add(index);
-      worklist_.Add(value);
-    }
-  }
-
-  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;
-  }
-
-  void SwapWorklists();
-
   FlowGraph* flow_graph_;
 
   GrowableArray<Definition*> smi_values_;  // Value that are known to be smi.
   GrowableArray<CheckSmiInstr*> smi_checks_;  // All CheckSmi instructions.
 
   // All Constraints inserted during InsertConstraints phase. They are treated
   // as smi values.
   GrowableArray<ConstraintInstr*> constraints_;
 
   // 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);
 };
 
 
 void RangeAnalysis::Analyze() {
   CollectSmiValues();
   InsertConstraints();
   InferRanges();
   RemoveConstraints();
@@ skipping 234 matching lines @@
       InsertConstraintsFor(constraint);  // Constrain uses further.
     }
   }
 
   for (intptr_t i = 0; i < smi_values_.length(); i++) {
     InsertConstraintsFor(smi_values_[i]);
   }
 }
 
 
-void RangeAnalysis::InitializeRangesRecursive(BlockEntryInstr* block) {
+void RangeAnalysis::ResetWorklist() {
+  if (marked_defns_ == NULL) {
+    marked_defns_ = new BitVector(flow_graph_->current_ssa_temp_index());
+  } else {
+    marked_defns_->Clear();
+  }
+  worklist_.Clear();
+}
+
+
+void RangeAnalysis::MarkDefinition(Definition* defn) {
+  // Unwrap constrained value.
+  while (defn->IsConstraint()) {
+    defn = defn->AsConstraint()->value()->definition();
+  }
+
+  if (!marked_defns_->Contains(defn->ssa_temp_index())) {
+    worklist_.Add(defn);
+    marked_defns_->Add(defn->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;
+}
+
+
+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);
+      }
+    } 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;
+    }
+  }
+
+
+  // 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());
+
+    case NEGATIVE:
+      return new Range(RangeBoundary::MinSmi(),
+                       RangeBoundary::FromDefinition(initial_value));
+
+    case UNKNOWN:
+    case BOTH:
+      return Range::Unknown();
+  }
+
+  UNREACHABLE();
+  return NULL;
+}
+
+
+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())) {
-        phi->InferRange(Definition::kRangeInit);
-        AddToWorklist(phi);
+        if (is_loop_header) {
+          // Try recognizing simple induction variables.
+          Range* range = InferInductionVariableRange(join, phi);
+          if (range != NULL) {
+            phi->range_ = range;
+            continue;
+          }
+        }
+
+        phi->InferRange();
       }
     }
   }
 
   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);
+      defn->InferRange();
     }
   }
 
   for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
-    InitializeRangesRecursive(block->dominated_blocks()[i]);
-  }
-}
-
-
-void RangeAnalysis::CreateWorklists() {
-  in_worklist_ = new BitVector(flow_graph_->current_ssa_temp_index());
-}
-
-
-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 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);
-        }
-      }
-    }
+    InferRangesRecursive(block->dominated_blocks()[i]);
   }
 }
 
 
 void RangeAnalysis::InferRanges() {
-  CreateWorklists();
-
   // 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());
   }
 
   // Infer initial values of ranges.
-  InitializeRangesRecursive(flow_graph_->graph_entry());
-
-  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);
-        }
-      }
-    }
-  }
+  InferRangesRecursive(flow_graph_->graph_entry());
 
   if (FLAG_trace_range_analysis) {
-    OS::Print("---- after initialization -------\n");
+    OS::Print("---- after range analysis -------\n");
     FlowGraphPrinter printer(*flow_graph_);
     printer.PrintBlocks();
   }
-
-  if (FLAG_trace_range_analysis) {
-    OS::Print("---- widening ---------\n");
-  }
-  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.
-  for (intptr_t i = 0; i < smi_values_.length(); i++) {
-    if (smi_values_[i]->IsPhi()) AddToWorklist(smi_values_[i]);
-  }
-  ProcessWorklist(Definition::kRangeNarrow);
-
-  if (FLAG_trace_range_analysis) {
-    OS::Print("---- after narrowing -------\n");
-    FlowGraphPrinter printer(*flow_graph_);
-    printer.PrintBlocks();
-  }
 }
 
 
 void RangeAnalysis::RemoveConstraints() {
   for (intptr_t i = 0; i < constraints_.length(); i++) {
     Definition* def = constraints_[i]->value()->definition();
     // Some constraints might be constraining constraints. Unwind the chain of
     // constraints until we reach the actual definition.
     while (def->IsConstraint()) {
       def = def->AsConstraint()->value()->definition();
@@ skipping 1394 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart