Implement range analysis for smi values.

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
 #include "vm/handles_impl.h"
 #include "vm/locations.h"
 #include "vm/object.h"
 
 namespace dart {
 
 class BitVector;
 class BlockEntryInstr;
 class BufferFormatter;
 class ComparisonInstr;
 class ControlInstruction;
 class Definition;
 class Environment;
 class FlowGraphCompiler;
 class FlowGraphVisitor;
 class Instruction;
 class LocalVariable;
+class Range;
 
 
 // TODO(srdjan): Add _ByteArrayBase, get:length.
 
 #define RECOGNIZED_LIST(V)                                                     \
   V(ObjectArray, get:length, ObjectArrayLength)                                \
   V(ImmutableArray, get:length, ImmutableArrayLength)                          \
   V(GrowableObjectArray, get:length, GrowableArrayLength)                      \
   V(GrowableObjectArray, get:capacity, GrowableArrayCapacity)                  \
   V(StringBase, get:length, StringBaseLength)                                  \
@@ skipping 35 matching lines @@
 
   Instruction* instruction() const { return instruction_; }
   void set_instruction(Instruction* instruction) { instruction_ = instruction; }
 
   intptr_t use_index() const { return use_index_; }
   void set_use_index(intptr_t index) { use_index_ = index; }
 
   void AddToInputUseList();
   void AddToEnvUseList();
 
+  void RemoveFromInputUseList();
+
   Value* Copy() { return new Value(definition_); }
 
   RawAbstractType* CompileType() const;
   intptr_t ResultCid() const;
 
   void PrintTo(BufferFormatter* f) const;
 
   const char* DebugName() const { return "Value"; }
 
   // Return true if the value represents a constant.
@@ skipping 152 matching lines @@
   M(SmiToDouble)                                                               \
   M(CheckClass)                                                                \
   M(CheckSmi)                                                                  \
   M(Constant)                                                                  \
   M(CheckEitherNonSmi)                                                         \
   M(UnboxedDoubleBinaryOp)                                                     \
   M(MathSqrt)                                                                  \
   M(UnboxDouble)                                                               \
   M(BoxDouble)                                                                 \
   M(CheckArrayBound)                                                           \
+  M(Constraint)                                                                \
 
 
 #define FORWARD_DECLARATION(type) class type##Instr;
 FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
 
 // Functions required in all concrete instruction classes.
 #define DECLARE_INSTRUCTION(type)                                              \
   virtual Tag tag() const { return k##type; }                                  \
@@ skipping 451 matching lines @@
 
   virtual bool HasSideEffect() const { return false; }
 
   intptr_t try_index() const { return try_index_; }
 
   BitVector* loop_info() const { return loop_info_; }
   void set_loop_info(BitVector* loop_info) {
     loop_info_ = loop_info;
   }
 
+  virtual BlockEntryInstr* GetBlock() const {
+    return const_cast<BlockEntryInstr*>(this);
+  }
+
  protected:
   explicit BlockEntryInstr(intptr_t try_index)
       : try_index_(try_index),
         preorder_number_(-1),
         postorder_number_(-1),
         block_id_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL),
         parallel_move_(NULL),
@@ skipping 186 matching lines @@
 
   GrowableArray<BlockEntryInstr*> predecessors_;
   ZoneGrowableArray<PhiInstr*>* phis_;
   intptr_t phi_count_;
   GrowableArray<BlockEntryInstr*> stale_predecessors_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
 };
 
 
+class PhiIterator : public ValueObject {
+ public:
+  explicit PhiIterator(JoinEntryInstr* join)
+      : phis_(join->phis()), index_(-1) {
+    if (!Done()) Advance();  // Advance to the first smi.
+  }
+
+  void Advance() {
+    ASSERT(!Done());
+    do {
+      index_++;
+    } while (!Done() && (Current() == NULL));
+  }
+
+  bool Done() const {
+    return (phis_ == NULL) || (index_ >= phis_->length());
+  }
+
+  PhiInstr* Current() const {
+    return (*phis_)[index_];
+  }
+
+ private:
+  ZoneGrowableArray<PhiInstr*>* phis_;
+  intptr_t index_;
+};
+
+
 class TargetEntryInstr : public BlockEntryInstr {
  public:
   explicit TargetEntryInstr(intptr_t try_index)
       : BlockEntryInstr(try_index),
         predecessor_(NULL),
         catch_try_index_(CatchClauseNode::kInvalidTryIndex) { }
 
   // Used for exception catch entries.
   TargetEntryInstr(intptr_t try_index, intptr_t catch_try_index)
       : BlockEntryInstr(try_index),
@@ skipping 129 matching lines @@
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintOperandsTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
   // A value in the constant propagation lattice.
   //    - non-constant sentinel
   //    - a constant (any non-sentinel value)
   //    - unknown sentinel
   Object& constant_value() const { return constant_value_; }
 
+  virtual bool InferRange();
+
+  Range* range() const { return range_; }
+
   // Definitions can be canonicalized only into definitions to ensure
   // this check statically we override base Canonicalize with a Canonicalize
   // returning Definition (return type is covariant).
   virtual Definition* Canonicalize();
 
+ protected:
+  Range* range_;
+
  private:
   intptr_t temp_index_;
   intptr_t ssa_temp_index_;
   // TODO(regis): GrowableArray<const AbstractType*> propagated_types_;
   // For now:
   AbstractType& propagated_type_;
   intptr_t propagated_cid_;
   Value* input_use_list_;
   Value* env_use_list_;
   UseKind use_kind_;
 
   Object& constant_value_;
 
   DISALLOW_COPY_AND_ASSIGN(Definition);
 };
 
 
 class PhiInstr : public Definition {
  public:
   explicit PhiInstr(JoinEntryInstr* block, intptr_t num_inputs)
     : block_(block),
       inputs_(num_inputs),
       is_alive_(false),
-      representation_(kTagged) {
+      representation_(kTagged),
+      has_inputs_without_range_(true) {
     for (intptr_t i = 0; i < num_inputs; ++i) {
       inputs_.Add(NULL);
     }
   }
 
   // Get the block entry for that instruction.
   virtual BlockEntryInstr* GetBlock() const { return block(); }
   JoinEntryInstr* block() const { return block_; }
 
   virtual RawAbstractType* CompileType() const;
@@ skipping 38 matching lines @@
   virtual intptr_t ResultCid() const {
     UNREACHABLE();
     return kIllegalCid;
   }
 
   DECLARE_INSTRUCTION(Phi)
 
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
+  virtual bool InferRange();
+
  private:
   friend class JoinEntryInstr;  // Direct access to inputs_ array.
 
   JoinEntryInstr* block_;
   GrowableArray<Value*> inputs_;
   bool is_alive_;
   Representation representation_;
 
+  // Used to determine an interation of a range analysis after all phi inputs

[ngeoffray, 2012/09/24 21:44:15]

interation -> iteration

+  // were initialized to apply widening.
+  bool has_inputs_without_range_;
+
   DISALLOW_COPY_AND_ASSIGN(PhiInstr);
 };
 
 
 class ParameterInstr : public Definition {
  public:
   explicit ParameterInstr(intptr_t index, GraphEntryInstr* block)
       : index_(index), block_(block) { }
 
   DECLARE_INSTRUCTION(Parameter)
@@ skipping 337 matching lines @@
  protected:
   EmbeddedArray<Value*, N> inputs_;
 
  private:
   friend class BranchInstr;
 
   LocationSummary* locs_;
 };
 
 
+class RangeBoundary : public ValueObject {
+ public:
+  enum Kind { kUnknown, kSymbol, kConstant };
+
+  RangeBoundary() : kind_(kUnknown), value_(0), offset_(0) { }
+
+  static RangeBoundary FromConstant(intptr_t val) {
+    return RangeBoundary(kConstant, val, 0);
+  }
+
+  static RangeBoundary FromDefinition(Definition* defn, intptr_t offs = 0) {
+    return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs);
+  }
+
+  static RangeBoundary MinSmi() {
+    return FromConstant(Smi::kMinValue);
+  }
+
+  static RangeBoundary MaxSmi() {
+    return FromConstant(Smi::kMaxValue);
+  }
+
+  static RangeBoundary OverflowedMinSmi() {
+    return FromConstant(Smi::kMinValue - 1);
+  }
+
+  static RangeBoundary OverflowedMaxSmi() {
+    return FromConstant(Smi::kMaxValue + 1);
+  }
+
+  static RangeBoundary Min(RangeBoundary a, RangeBoundary b) {
+    const intptr_t min_a = a.LowerBound().value();
+    const intptr_t min_b = b.LowerBound().value();
+
+    return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_b));
+  }
+
+  static RangeBoundary Max(RangeBoundary a, RangeBoundary b) {
+    const intptr_t max_a = a.UpperBound().value();
+    const intptr_t max_b = b.UpperBound().value();
+
+    return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
+  }
+
+  bool Overflowed() const {
+    return !Smi::IsValid(value());
+  }
+
+  RangeBoundary Clamp() const {
+    if (IsConstant()) {
+      if (value() < Smi::kMinValue) return MinSmi();
+      if (value() > Smi::kMaxValue) return MaxSmi();
+    }
+    return *this;
+  }
+
+  bool Equals(const RangeBoundary& other) const {
+    return (kind_ == other.kind_) && (value_ == other.value_);
+  }
+
+  bool IsUnknown() const { return kind_ == kUnknown; }
+  bool IsConstant() const { return kind_ == kConstant; }
+  bool IsSymbol() const { return kind_ == kSymbol; }
+
+  intptr_t value() const {
+    ASSERT(IsConstant());
+    return value_;
+  }
+
+  Definition* symbol() const {
+    ASSERT(IsSymbol());
+    return reinterpret_cast<Definition*>(value_);
+  }
+
+  RangeBoundary LowerBound() const;
+  RangeBoundary UpperBound() const;
+
+  static RangeBoundary WidenMin(const RangeBoundary& old_min,
+                                const RangeBoundary& new_min) {
+    if (new_min.LowerBound().value() < old_min.LowerBound().value()) {
+      return MinSmi();
+    }
+    return new_min;
+  }
+
+  static RangeBoundary WidenMax(const RangeBoundary& old_max,
+                                const RangeBoundary& new_max) {
+    if (new_max.UpperBound().value() > old_max.UpperBound().value()) {
+      return MaxSmi();
+    }
+    return new_max;
+  }
+
+  void PrintTo(BufferFormatter* f) const;
+
+  static RangeBoundary Add(const RangeBoundary& a,
+                           const RangeBoundary& b,
+                           const RangeBoundary& overflow) {
+    ASSERT(a.IsConstant() && b.IsConstant());
+
+    intptr_t result = a.value() + b.value();
+    if (!Smi::IsValid(result)) {
+      return overflow;
+    }
+    return RangeBoundary::FromConstant(result);
+  }
+
+  static RangeBoundary Sub(const RangeBoundary& a,
+                           const RangeBoundary& b,
+                           const RangeBoundary& overflow) {
+    ASSERT(a.IsConstant() && b.IsConstant());
+
+    intptr_t result = a.value() - b.value();
+    if (!Smi::IsValid(result)) {
+      return overflow;
+    }
+    return RangeBoundary::FromConstant(result);
+  }
+
+ private:
+  RangeBoundary(Kind kind, intptr_t value, intptr_t offset)
+      : kind_(kind), value_(value), offset_(offset) { }
+
+  Kind kind_;
+  intptr_t value_;
+  intptr_t offset_;
+};
+
+
+class Range : public ZoneAllocated {
+ public:
+  Range(RangeBoundary min, RangeBoundary max) : min_(min), max_(max) { }
+
+  static Range* Unknown() {
+    return new Range(RangeBoundary::MinSmi(), RangeBoundary::MaxSmi());
+  }
+
+  void PrintTo(BufferFormatter* f) const;
+
+  const RangeBoundary& min() { return min_; }
+  const RangeBoundary& max() { return max_; }
+
+  bool Equals(Range* other) {
+    return min_.Equals(other->min_) && max_.Equals(other->max_);
+  }
+
+  static bool Update(Range** range_slot,
+                     const RangeBoundary& min,
+                     const RangeBoundary& max) {
+    if (*range_slot == NULL) {
+      *range_slot = new Range(min, max);
+      return true;
+    }
+
+    Range* range = *range_slot;
+    if (range->min_.Equals(min) && range->max_.Equals(max)) {
+      return false;
+    }
+
+    range->min_ = min;
+    range->max_ = max;
+
+    return true;
+  }
+
+  static RangeBoundary ConstantMin(Range* range) {
+    if (range == NULL) return RangeBoundary::MinSmi();
+    return range->min().LowerBound();
+  }
+
+  static RangeBoundary ConstantMax(Range* range) {
+    if (range == NULL) return RangeBoundary::MaxSmi();
+    return range->max().UpperBound();
+  }
+
+ private:
+  RangeBoundary min_;
+  RangeBoundary max_;
+};
+
+
+class ConstraintInstr : public TemplateDefinition<2> {
+ public:
+  ConstraintInstr(Value* value, Range* constraint)
+      : constraint_(constraint) {
+    inputs_[0] = value;
+    inputs_[1] = NULL;  // Dependency.
+  }
+
+  DECLARE_INSTRUCTION(Constraint)
+
+  virtual RawAbstractType* CompileType() const {
+    return Type::SmiType();
+  }
+
+  virtual bool CanDeoptimize() const { return false; }
+
+  virtual bool HasSideEffect() const { return false; }
+
+  virtual intptr_t ResultCid() const { return kSmiCid; }
+
+  virtual bool AttributesEqual(Definition* other) const {
+    UNREACHABLE();
+    return false;
+  }
+
+  virtual void PrintOperandsTo(BufferFormatter* f) const;
+
+  Value* value() const { return inputs_[0]; }
+  Range* constraint() const { return constraint_; }
+
+  virtual bool InferRange();
+
+  void AddDependency(Definition* defn) {
+    Value* val = new Value(defn);
+    val->set_use_index(1);
+    val->set_instruction(this);
+    val->AddToInputUseList();
+    set_dependency(val);
+  }
+
+  void RemoveDependency() {
+    if (dependency() != NULL) {
+      dependency()->RemoveFromInputUseList();
+      set_dependency(NULL);
+    }
+  }
+
+ private:
+  Value* dependency() {
+    return inputs_[1];
+  }
+
+  void set_dependency(Value* value) {
+    inputs_[1] = value;
+  }
+
+  Range* constraint_;
+
+  DISALLOW_COPY_AND_ASSIGN(ConstraintInstr);
+};
+
+
 class ConstantInstr : public TemplateDefinition<0> {
  public:
-  explicit ConstantInstr(const Object& value) : value_(value) { }
+  explicit ConstantInstr(const Object& value)
+      : value_(value) { }
 
   DECLARE_INSTRUCTION(Constant)
   virtual RawAbstractType* CompileType() const;
 
   const Object& value() const { return value_; }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
 
   virtual bool HasSideEffect() const { return false; }
 
   virtual intptr_t ResultCid() const;
 
   virtual bool AttributesEqual(Instruction* other) const;
   virtual bool AffectedBySideEffect() const { return false; }
 
+  virtual bool InferRange();
+
  private:
   const Object& value_;
 
   DISALLOW_COPY_AND_ASSIGN(ConstantInstr);
 };
 
 
 class AssertAssignableInstr : public TemplateDefinition<3> {
  public:
   AssertAssignableInstr(intptr_t token_pos,
@@ skipping 285 matching lines @@
   InstanceCallInstr* instance_call_;
   const ICData& ic_data_;
   const bool with_checks_;
 
   DISALLOW_COPY_AND_ASSIGN(PolymorphicInstanceCallInstr);
 };
 
 
 class ComparisonInstr : public TemplateDefinition<2> {
  public:
-  ComparisonInstr(Token::Kind kind, Value* left, Value* right) : kind_(kind) {
+  ComparisonInstr(Token::Kind kind, Value* left, Value* right)
+      : kind_(kind) {
     ASSERT(left != NULL);
     ASSERT(right != NULL);
     inputs_[0] = left;
     inputs_[1] = right;
   }
 
   Value* left() const { return inputs_[0]; }
   Value* right() const { return inputs_[1]; }
 
   virtual ComparisonInstr* AsComparison() { return this; }
@@ skipping 1275 matching lines @@
 };
 
 
 class BinarySmiOpInstr : public TemplateDefinition<2> {
  public:
   BinarySmiOpInstr(Token::Kind op_kind,
                    InstanceCallInstr* instance_call,
                    Value* left,
                    Value* right)
       : op_kind_(op_kind),
-        instance_call_(instance_call) {
+        instance_call_(instance_call),
+        overflow_(true) {
     ASSERT(left != NULL);
     ASSERT(right != NULL);
     inputs_[0] = left;
     inputs_[1] = right;
   }
 
   Value* left() const { return inputs_[0]; }
   Value* right() const { return inputs_[1]; }
 
   Token::Kind op_kind() const { return op_kind_; }
 
   InstanceCallInstr* instance_call() const { return instance_call_; }
 
   const ICData* ic_data() const { return instance_call()->ic_data(); }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   DECLARE_INSTRUCTION(BinarySmiOp)
   virtual RawAbstractType* CompileType() const;
 
   virtual bool CanDeoptimize() const;
 
   virtual bool HasSideEffect() const { return false; }
 
   virtual bool AffectedBySideEffect() const { return false; }
   virtual bool AttributesEqual(Instruction* other) const;
 
   virtual intptr_t ResultCid() const;
 
+  void set_overflow(bool overflow) {
+    overflow_ = overflow;
+  }
+
+  void PrintTo(BufferFormatter* f) const;
+
+  virtual bool InferRange();
+
  private:
   const Token::Kind op_kind_;
   InstanceCallInstr* instance_call_;
+  bool overflow_;
 
   DISALLOW_COPY_AND_ASSIGN(BinarySmiOpInstr);
 };
 
 
 class BinaryMintOpInstr : public TemplateDefinition<2> {
  public:
   BinaryMintOpInstr(Token::Kind op_kind,
                     InstanceCallInstr* instance_call,
                     Value* left,
@@ skipping 462 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_