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);
   }
 
-  // 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);
+  // 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);
 
   // 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(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) { }
-
-  static Range* Unknown() {
-    return new Range(RangeBoundary::MinConstant(),
-                     RangeBoundary::MaxConstant());
+  Range() : min_(), max_() { }
+  Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) {
+    ASSERT(min_.IsUnknown() == max_.IsUnknown());
   }
 
-  static Range* UnknownSmi() {
-    return new Range(RangeBoundary::MinSmi(),
-                     RangeBoundary::MaxSmi());
+  Range(const Range& other)
+      : ZoneAllocated(),

[Florian Schneider, 2014/08/15 11:58:02]

explicit super constructor call not needed?

+        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());
+    }
   }
 
   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 Range* BinaryOp(const Token::Kind op,
-                         const Range* left_range,
-                         const Range* right_range,
-                         Definition* left_defn);
+  static void BinaryOp(const Token::Kind op,
+                       const Range* left_range,
+                       const Range* right_range,
+                       Definition* left_defn,
+                       Range* result);
 
  private:
   RangeBoundary min_;
   RangeBoundary max_;
 };
 
 
 // Range analysis for integer values.
 class RangeAnalysis : public ValueObject {
  public:
   explicit RangeAnalysis(FlowGraph* flow_graph)
-      : flow_graph_(flow_graph),
-        marked_defns_(NULL) { }
+      : flow_graph_(flow_graph) { }
 
   // 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);
 
 
-  // Walk the dominator tree and infer ranges for smi values.
+  // Infer ranges for integer (smi or mint) definitions.
   void InferRanges();
-  void InferRangesRecursive(BlockEntryInstr* block);
 
-  enum Direction {
-    kUnknown,
-    kPositive,
-    kNegative,
-    kBoth
-  };
+  // Collect integer definition in the dominator tree traversal order.
+  void CollectDefinitionsRecursive(BlockEntryInstr* block,
+                                   BitVector* set);
 
-  Range* InferInductionVariableRange(JoinEntryInstr* loop_header,
-                                     PhiInstr* var);
+  // 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);
 
-  void ResetWorklist();
-  void MarkDefinition(Definition* defn);
+  // Based on computed ranges find and eliminate redundant CheckArrayBound
+  // instructions.
+  void EliminateRedundantBoundsChecks();
 
-  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;
-    }
-  }
+  // Find unsatisfiable constraints and mark corresponding blocks unreachable.
+  void MarkUnreachableBlocks();
 
   // Remove artificial Constraint instructions and replace them with actual
   // unconstrained definitions.
   void RemoveConstraints();
 
   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 CheckSmi instructions.

[Florian Schneider, 2014/08/15 11:58:02]

s/CheckSmi/CheckArrayBoundInstr/

+  GrowableArray<CheckArrayBoundInstr*> bounds_checks_;
+
   // All Constraints inserted during InsertConstraints phase. They are treated
   // as smi values.
   GrowableArray<ConstraintInstr*> constraints_;
 
-  // Bitvector for a quick filtering of known smi or mint values.
-  BitVector* definitions_;
-
-  // Worklist for induction variables analysis.
-  GrowableArray<Definition*> worklist_;
-  BitVector* marked_defns_;
+  // List of integer (smi or mint) definitions including constraints sorted
+  // in the dominator tree traversal order.
+  GrowableArray<Definition*> definitions_;
 
   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_