Consolidate all range analysis related code in a separate file.

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"
+
+namespace dart {
+
+class RangeBoundary : public ValueObject {
+ public:
+  enum Kind {
+    kUnknown,
+    kNegativeInfinity,
+    kPositiveInfinity,
+    kSymbol,
+    kConstant,
+  };
+
+  enum RangeSize {
+    kRangeBoundarySmi,
+    kRangeBoundaryInt64,
+  };
+
+  RangeBoundary() : kind_(kUnknown), value_(0), offset_(0) { }
+
+  RangeBoundary(const RangeBoundary& other)
+      : ValueObject(),
+        kind_(other.kind_),
+        value_(other.value_),
+        offset_(other.offset_) { }
+
+  explicit RangeBoundary(int64_t val)
+      : kind_(kConstant), value_(val), offset_(0) { }
+
+  RangeBoundary& operator=(const RangeBoundary& other) {
+    kind_ = other.kind_;
+    value_ = other.value_;
+    offset_ = other.offset_;
+    return *this;
+  }
+
+  static const int64_t kMin = kMinInt64;
+  static const int64_t kMax = kMaxInt64;
+
+  // Construct a RangeBoundary for a constant value.
+  static RangeBoundary FromConstant(int64_t val) {
+    return RangeBoundary(val);
+  }
+
+  // Construct a RangeBoundary for -inf.
+  static RangeBoundary NegativeInfinity() {
+    return RangeBoundary(kNegativeInfinity, 0, 0);
+  }
+
+  // Construct a RangeBoundary for +inf.
+  static RangeBoundary PositiveInfinity() {
+    return RangeBoundary(kPositiveInfinity, 0, 0);
+  }
+
+  // Construct a RangeBoundary from a definition and offset.
+  static RangeBoundary FromDefinition(Definition* defn, int64_t offs = 0);
+
+  // Construct a RangeBoundary for the constant MinSmi value.
+  static RangeBoundary MinSmi() {
+    return FromConstant(Smi::kMinValue);
+  }
+
+  // Construct a RangeBoundary for the constant MaxSmi value.
+  static RangeBoundary MaxSmi() {
+    return FromConstant(Smi::kMaxValue);
+  }
+
+    // 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);
+
+  // 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();
+  }
+
+  // -/+ infinity are clamped to MinConstant/MaxConstant of the given type.
+  RangeBoundary Clamp(RangeSize size) const {
+    if (IsNegativeInfinity()) {
+      return (size == kRangeBoundaryInt64) ? MinConstant() : MinSmi();
+    }
+    if (IsPositiveInfinity()) {
+      return (size == kRangeBoundaryInt64) ? MaxConstant() : MaxSmi();
+    }
+    if ((size == kRangeBoundarySmi) && IsConstant()) {
+      if (ConstantValue() <= Smi::kMinValue) {
+        return MinSmi();
+      }
+      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));
+  }
+
+  bool IsMinimumOrBelow() const {
+    return IsNegativeInfinity() || (IsConstant() && (ConstantValue() == kMin));
+  }
+
+  bool IsMaximumOrAbove() const {
+    return IsPositiveInfinity() || (IsConstant() && (ConstantValue() == kMax));
+  }
+
+  intptr_t kind() const {
+    return kind_;
+  }
+
+  // Kind tests.
+  bool IsUnknown() const { return kind_ == kUnknown; }
+  bool IsConstant() const { return kind_ == kConstant; }
+  bool IsSymbol() const { return kind_ == kSymbol; }
+  bool IsNegativeInfinity() const { return kind_ == kNegativeInfinity; }
+  bool IsPositiveInfinity() const { return kind_ == kPositiveInfinity; }
+  bool IsInfinity() const {
+    return IsNegativeInfinity() || IsPositiveInfinity();
+  }
+  bool IsConstantOrInfinity() const {
+    return IsConstant() || IsInfinity();
+  }
+
+  // Returns the value of a kConstant RangeBoundary.
+  int64_t ConstantValue() const;
+
+  // Returns the Definition associated with a kSymbol RangeBoundary.
+  Definition* symbol() const {
+    ASSERT(IsSymbol());
+    return reinterpret_cast<Definition*>(value_);
+  }
+
+  // Offset from symbol.
+  int64_t offset() const {
+    return offset_;
+  }
+
+  // Computes the LowerBound of this. Three cases:
+  // IsInfinity() -> NegativeInfinity().
+  // IsConstant() -> value().
+  // IsSymbol() -> lower bound computed from definition + offset.
+  RangeBoundary LowerBound() const;
+
+  // Computes the UpperBound of this. Three cases:
+  // IsInfinity() -> PositiveInfinity().
+  // IsConstant() -> value().
+  // IsSymbol() -> upper bound computed from definition + offset.
+  RangeBoundary UpperBound() const;
+
+  void PrintTo(BufferFormatter* f) const;
+  const char* ToCString() const;
+
+  static RangeBoundary Add(const RangeBoundary& a,
+                           const RangeBoundary& b,
+                           const RangeBoundary& overflow);
+
+  static RangeBoundary Sub(const RangeBoundary& a,
+                           const RangeBoundary& b,
+                           const RangeBoundary& overflow);
+
+  static RangeBoundary Shl(const RangeBoundary& value_boundary,
+                           int64_t shift_count,
+                           const RangeBoundary& overflow);
+
+  static RangeBoundary Shr(const RangeBoundary& value_boundary,
+                           int64_t shift_count) {
+    ASSERT(value_boundary.IsConstant());
+    ASSERT(shift_count >= 0);
+    int64_t value = static_cast<int64_t>(value_boundary.ConstantValue());
+    int64_t result = value >> shift_count;
+    return RangeBoundary(result);
+  }
+
+  // Attempts to calculate a + b when:
+  // a is a symbol and b is a constant OR
+  // a is a constant and b is a symbol
+  // returns true if it succeeds, output is in result.
+  static bool SymbolicAdd(const RangeBoundary& a,
+                          const RangeBoundary& b,
+                          RangeBoundary* result);
+
+  // 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;
+
+ 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());
+  }
+
+  static Range* UnknownSmi() {
+    return new Range(RangeBoundary::MinSmi(),
+                     RangeBoundary::MaxSmi());
+  }
+
+  void PrintTo(BufferFormatter* f) const;
+  static const char* ToCString(const Range* range);
+
+  const RangeBoundary& min() const { return min_; }
+  const RangeBoundary& max() const { return max_; }
+
+  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) {
+      return RangeBoundary::MaxSmi();
+    }
+    return range->max().UpperBound().Clamp(RangeBoundary::kRangeBoundarySmi);
+  }
+
+  static RangeBoundary ConstantMin(const Range* range) {
+    if (range == NULL) {
+      return RangeBoundary::MinConstant();
+    }
+    return range->min().LowerBound().Clamp(RangeBoundary::kRangeBoundaryInt64);
+  }
+
+  static RangeBoundary ConstantMax(const Range* range) {
+    if (range == NULL) {
+      return RangeBoundary::MaxConstant();
+    }
+    return range->max().UpperBound().Clamp(RangeBoundary::kRangeBoundaryInt64);
+  }
+
+  // [0, +inf]
+  bool IsPositive() const;
+
+  // [-inf, val].
+  bool OnlyLessThanOrEqualTo(int64_t val) const;
+
+  // [val, +inf].
+  bool OnlyGreaterThanOrEqualTo(int64_t val) const;
+
+  // Inclusive.
+  bool IsWithin(int64_t min_int, int64_t max_int) const;
+
+  // Inclusive.
+  bool Overlaps(int64_t min_int, int64_t max_int) const;
+
+  bool IsUnsatisfiable() const;
+
+  bool IsFinite() const {
+    return !min_.IsInfinity() && !max_.IsInfinity();
+  }
+
+  // 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,
+                  const Range* right_range,
+                  RangeBoundary* min,
+                  RangeBoundary* max,
+                  Definition* left_defn);
+
+  static bool Mul(const Range* left_range,
+                  const Range* right_range,
+                  RangeBoundary* min,
+                  RangeBoundary* max);
+  static void Shr(const Range* left_range,
+                  const Range* right_range,
+                  RangeBoundary* min,
+                  RangeBoundary* max);
+
+  static void Shl(const Range* left_range,
+                  const Range* right_range,
+                  RangeBoundary* min,
+                  RangeBoundary* max);
+
+  static bool And(const Range* left_range,
+                  const Range* right_range,
+                  RangeBoundary* min,
+                  RangeBoundary* max);
+
+
+  // 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);
+
+ 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) { }
+
+  // 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 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
+  // and false successor and rename all dominated uses to refer to a
+  // Constraint instead of this definition.
+  void InsertConstraintsFor(Definition* defn);
+
+  // Create a constraint for defn, insert it after given instruction and
+  // rename all uses that are dominated by it.
+  ConstraintInstr* InsertConstraintFor(Definition* defn,
+                                       Range* constraint,
+                                       Instruction* after);
+
+  void ConstrainValueAfterBranch(Definition* defn, Value* use);
+  void ConstrainValueAfterCheckArrayBound(Definition* defn,
+                                          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.
+  void InferRanges();
+  void InferRangesRecursive(BlockEntryInstr* block);
+
+  enum Direction {
+    kUnknown,
+    kPositive,
+    kNegative,
+    kBoth
+  };
+
+  Range* InferInductionVariableRange(JoinEntryInstr* loop_header,
+                                     PhiInstr* var);
+
+  void ResetWorklist();
+  void MarkDefinition(Definition* defn);
+
+  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* 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 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_;
+
+  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);
+
+  void Select();
+
+ private:
+  bool IsPotentialUint32Definition(Definition* def);
+  void FindPotentialUint32Definitions();
+  bool IsUint32NarrowingDefinition(Definition* def);
+  void FindUint32NarrowingDefinitions();
+  bool AllUsesAreUint32Narrowing(Value* list_head);
+  bool CanBecomeUint32(Definition* def);
+  void Propagate();
+  Definition* ConstructReplacementFor(Definition* def);
+  void ReplaceInstructions();
+
+  Isolate* isolate() const { return isolate_; }
+
+  GrowableArray<Definition*> potential_uint32_defs_;
+  BitVector* selected_uint32_defs_;
+
+  FlowGraph* flow_graph_;
+  Isolate* isolate_;
+};
+
+
+}  // namespace dart
+
+#endif  // VM_FLOW_GRAPH_RANGE_ANALYSIS_H_