Revert "Switch to a fix-point based range analysis to improve its precision."

runtime/vm/flow_graph_range_analysis.h

 // Copyright (c) 2014, 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.
 
 #ifndef VM_FLOW_GRAPH_RANGE_ANALYSIS_H_
 #define VM_FLOW_GRAPH_RANGE_ANALYSIS_H_
 
 #include "vm/flow_graph.h"
 #include "vm/intermediate_language.h"
 
@@ skipping 66 matching lines @@
     // Construct a RangeBoundary for the constant kMin value.
   static RangeBoundary MinConstant() {
     return FromConstant(kMin);
   }
 
   // Construct a RangeBoundary for the constant kMax value.
   static RangeBoundary MaxConstant() {
     return FromConstant(kMax);
   }
 
-  // Given two boundaries a and b, select one of them as c so that
-  //
-  //   inf {[a, ...) ^ [b, ...)} >= inf {c}
-  //
-  static RangeBoundary IntersectionMin(RangeBoundary a, RangeBoundary b);
-
-  // Given two boundaries a and b, select one of them as c so that
-  //
-  //   sup {(..., a] ^ (..., b]} <= sup {c}
-  //
-  static RangeBoundary IntersectionMax(RangeBoundary a, RangeBoundary b);
-
-  // Given two boundaries a and b compute boundary c such that
-  //
-  //   inf {[a, ...) U  [b, ...)} >= inf {c}
-  //
-  // Try to select c such that it is as close to inf {[a, ...) U [b, ...)}
-  // as possible.
-  static RangeBoundary JoinMin(RangeBoundary a, RangeBoundary b);
-
-  // Given two boundaries a and b compute boundary c such that
-  //
-  //   sup {(..., a] U (..., b]} <= sup {c}
-  //
-  // Try to select c such that it is as close to sup {(..., a] U (..., b]}
-  // as possible.
-  static RangeBoundary JoinMax(RangeBoundary a, RangeBoundary b);
+  // Calculate the minimum of a and b within the given range.
+  static RangeBoundary Min(RangeBoundary a, RangeBoundary b, RangeSize size);
+  static RangeBoundary Max(RangeBoundary a, RangeBoundary b, RangeSize size);
 
   // Returns true when this is a constant that is outside of Smi range.
   bool OverflowedSmi() const {
     return (IsConstant() && !Smi::IsValid(ConstantValue())) || IsInfinity();
   }
 
   // Returns true if this outside mint range.
   bool OverflowedMint() const {
     return IsInfinity();
   }
@@ skipping 12 matching lines @@
       }
       if (ConstantValue() >= Smi::kMaxValue) {
         return MaxSmi();
       }
     }
     // If this range is a symbolic range, we do not clamp it.
     // This could lead to some imprecision later on.
     return *this;
   }
 
+
   bool IsSmiMinimumOrBelow() const {
     return IsNegativeInfinity() ||
            (IsConstant() && (ConstantValue() <= Smi::kMinValue));
   }
 
   bool IsSmiMaximumOrAbove() const {
     return IsPositiveInfinity() ||
            (IsConstant() && (ConstantValue() >= Smi::kMaxValue));
   }
 
@@ skipping 82 matching lines @@
 
   // Attempts to calculate a - b when:
   // a is a symbol and b is a constant
   // returns true if it succeeds, output is in result.
   static bool SymbolicSub(const RangeBoundary& a,
                           const RangeBoundary& b,
                           RangeBoundary* result);
 
   bool Equals(const RangeBoundary& other) const;
 
-  int64_t SmiUpperBound() const {
-    return UpperBound().Clamp(kRangeBoundarySmi).ConstantValue();
-  }
-
-  int64_t SmiLowerBound() const {
-    return LowerBound().Clamp(kRangeBoundarySmi).ConstantValue();
-  }
-
  private:
   RangeBoundary(Kind kind, int64_t value, int64_t offset)
       : kind_(kind), value_(value), offset_(offset) { }
 
   Kind kind_;
   int64_t value_;
   int64_t offset_;
 };
 
 
 class Range : public ZoneAllocated {
  public:
-  Range() : min_(), max_() { }
-  Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) {
-    ASSERT(min_.IsUnknown() == max_.IsUnknown());
+  Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) { }
+
+  static Range* Unknown() {
+    return new Range(RangeBoundary::MinConstant(),
+                     RangeBoundary::MaxConstant());
   }
 
-  Range(const Range& other)
-      : ZoneAllocated(),
-        min_(other.min_),
-        max_(other.max_) {
-  }
-
-  Range& operator=(const Range& other) {
-    min_ = other.min_;
-    max_ = other.max_;
-    return *this;
-  }
-
-  static bool IsUnknown(const Range* other) {
-    if (other == NULL) {
-      return true;
-    }
-    return other->min().IsUnknown();
-  }
-
-  static Range Full(RangeBoundary::RangeSize size) {
-    if (size == RangeBoundary::kRangeBoundarySmi) {
-      return Range(RangeBoundary::MinSmi(), RangeBoundary::MaxSmi());
-    } else {
-      ASSERT(size == RangeBoundary::kRangeBoundaryInt64);
-      return Range(RangeBoundary::MinConstant(), RangeBoundary::MaxConstant());
-    }
+  static Range* UnknownSmi() {
+    return new Range(RangeBoundary::MinSmi(),
+                     RangeBoundary::MaxSmi());
   }
 
   void PrintTo(BufferFormatter* f) const;
   static const char* ToCString(const Range* range);
 
-  bool Equals(const Range* other) {
-    ASSERT(min_.IsUnknown() == max_.IsUnknown());
-    if (other == NULL) {
-      return min_.IsUnknown();
-    }
-    return min_.Equals(other->min_) &&
-        max_.Equals(other->max_);
-  }
-
   const RangeBoundary& min() const { return min_; }
   const RangeBoundary& max() const { return max_; }
-  void set_min(const RangeBoundary& value) {
-    min_ = value;
-  }
-  void set_max(const RangeBoundary& value) {
-    max_ = value;
-  }
 
   static RangeBoundary ConstantMinSmi(const Range* range) {
     if (range == NULL) {
       return RangeBoundary::MinSmi();
     }
     return range->min().LowerBound().Clamp(RangeBoundary::kRangeBoundarySmi);
   }
 
   static RangeBoundary ConstantMaxSmi(const Range* range) {
     if (range == NULL) {
@@ skipping 30 matching lines @@
 
   // Inclusive.
   bool Overlaps(int64_t min_int, int64_t max_int) const;
 
   bool IsUnsatisfiable() const;
 
   bool IsFinite() const {
     return !min_.IsInfinity() && !max_.IsInfinity();
   }
 
-  Range Intersect(const Range* other) const {
-    return Range(RangeBoundary::IntersectionMin(min(), other->min()),
-                 RangeBoundary::IntersectionMax(max(), other->max()));
-  }
-
   // Clamp this to be within size.
   void Clamp(RangeBoundary::RangeSize size);
 
   static void Add(const Range* left_range,
                   const Range* right_range,
                   RangeBoundary* min,
                   RangeBoundary* max,
                   Definition* left_defn);
 
   static void Sub(const Range* left_range,
@@ skipping 24 matching lines @@
 
   // Both the a and b ranges are >= 0.
   static bool OnlyPositiveOrZero(const Range& a, const Range& b);
 
   // Both the a and b ranges are <= 0.
   static bool OnlyNegativeOrZero(const Range& a, const Range& b);
 
   // Return the maximum absolute value included in range.
   static int64_t ConstantAbsMax(const Range* range);
 
-  static void BinaryOp(const Token::Kind op,
-                       const Range* left_range,
-                       const Range* right_range,
-                       Definition* left_defn,
-                       Range* result);
+  static Range* BinaryOp(const Token::Kind op,
+                         const Range* left_range,
+                         const Range* right_range,
+                         Definition* left_defn);
 
  private:
   RangeBoundary min_;
   RangeBoundary max_;
 };
 
 
 // Range analysis for integer values.
 class RangeAnalysis : public ValueObject {
  public:
   explicit RangeAnalysis(FlowGraph* flow_graph)
-      : flow_graph_(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:
-  enum JoinOperator {
-    NONE,
-    WIDEN,
-    NARROW
-  };
-  static char OpPrefix(JoinOperator op);
-
   // Collect all values that were proven to be smi in smi_values_ array and all
   // CheckSmi instructions in smi_check_ array.
   void CollectValues();
 
   // Iterate over smi values and constrain them at branch successors.
   // Additionally constraint values after CheckSmi instructions.
   void InsertConstraints();
 
   // Iterate over uses of the given definition and discover branches that
   // constrain it. Insert appropriate Constraint instructions at true
@@ skipping 12 matching lines @@
                                           CheckArrayBoundInstr* check,
                                           intptr_t use_index);
 
   // 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);
 
 
-  // Infer ranges for integer (smi or mint) definitions.
+  // Walk the dominator tree and infer ranges for smi values.
   void InferRanges();
+  void InferRangesRecursive(BlockEntryInstr* block);
 
-  // Collect integer definition in the reverse postorder.
-  void CollectDefinitions(BlockEntryInstr* block, BitVector* set);
+  enum Direction {
+    kUnknown,
+    kPositive,
+    kNegative,
+    kBoth
+  };
 
-  // Recompute ranges of all definitions until they stop changing.
-  // Apply the given JoinOperator when computing Phi ranges.
-  void Iterate(JoinOperator op, intptr_t max_iterations);
-  bool InferRange(JoinOperator op, Definition* defn, intptr_t iteration);
+  Range* InferInductionVariableRange(JoinEntryInstr* loop_header,
+                                     PhiInstr* var);
 
-  // Based on computed ranges find and eliminate redundant CheckArrayBound
-  // instructions.
-  void EliminateRedundantBoundsChecks();
+  void ResetWorklist();
+  void MarkDefinition(Definition* defn);
 
-  // Find unsatisfiable constraints and mark corresponding blocks unreachable.
-  void MarkUnreachableBlocks();
+  static Direction ToDirection(Value* val);
+
+  static Direction Invert(Direction direction) {
+    return (direction == kPositive) ? kNegative : kPositive;
+  }
+
+  static void UpdateDirection(Direction* direction,
+                              Direction new_direction) {
+    if (*direction != new_direction) {
+      if (*direction != kUnknown) new_direction = kBoth;
+      *direction = new_direction;
+    }
+  }
 
   // Remove artificial Constraint instructions and replace them with actual
   // unconstrained definitions.
   void RemoveConstraints();
 
-  Range* ConstraintSmiRange(Token::Kind op, Definition* boundary);
+  Range* ConstraintRange(Token::Kind op, Definition* boundary);
 
   Isolate* isolate() const { return flow_graph_->isolate(); }
 
   FlowGraph* flow_graph_;
 
   // Value that are known to be smi or mint.
   GrowableArray<Definition*> values_;
-
   // All CheckSmi instructions.
   GrowableArray<CheckSmiInstr*> smi_checks_;
 
-  // All CheckArrayBound instructions.
-  GrowableArray<CheckArrayBoundInstr*> bounds_checks_;
-
   // All Constraints inserted during InsertConstraints phase. They are treated
   // as smi values.
   GrowableArray<ConstraintInstr*> constraints_;
 
-  // List of integer (smi or mint) definitions including constraints sorted
-  // in the reverse postorder.
-  GrowableArray<Definition*> definitions_;
+  // Bitvector for a quick filtering of known smi or mint values.
+  BitVector* definitions_;
+
+  // Worklist for induction variables analysis.
+  GrowableArray<Definition*> worklist_;
+  BitVector* marked_defns_;
 
   DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
 };
 
 
 // Replaces Mint IL instructions with Uint32 IL instructions
 // when possible. Uses output of RangeAnalysis.
 class IntegerInstructionSelector : public ValueObject {
  public:
   explicit IntegerInstructionSelector(FlowGraph* flow_graph);
@@ skipping 17 matching lines @@
   BitVector* selected_uint32_defs_;
 
   FlowGraph* flow_graph_;
   Isolate* isolate_;
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_RANGE_ANALYSIS_H_