Implement range analysis for smi values.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
diff --git a/runtime/vm/intermediate_language.h b/runtime/vm/intermediate_language.h
index f47d6e3b90e42ee873f3f74efc4a681f60ff1bb0..91d86ba7892f18ba327cf0c3b740167026314ac8 100644
--- a/runtime/vm/intermediate_language.h
+++ b/runtime/vm/intermediate_language.h
@@ -25,6 +25,7 @@ class FlowGraphCompiler;
 class FlowGraphVisitor;
 class Instruction;
 class LocalVariable;
+class Range;
 
 
 // TODO(srdjan): Add _ByteArrayBase, get:length.
@@ -80,6 +81,8 @@ class Value : public ZoneAllocated {
   void AddToInputUseList();
   void AddToEnvUseList();
 
+  void RemoveFromInputUseList();
+
   Value* Copy() { return new Value(definition_); }
 
   RawAbstractType* CompileType() const;
@@ -252,6 +255,7 @@ class EmbeddedArray<T, 0> {
   M(UnboxDouble)                                                               \
   M(BoxDouble)                                                                 \
   M(CheckArrayBound)                                                           \
+  M(Constraint)                                                                \
 
 
 #define FORWARD_DECLARATION(type) class type##Instr;
@@ -278,7 +282,8 @@ class Instruction : public ZoneAllocated {
 #undef DECLARE_TAG
 
   Instruction()
-      : deopt_id_(Isolate::Current()->GetNextDeoptId()),
+      : range_(NULL),
+        deopt_id_(Isolate::Current()->GetNextDeoptId()),
         lifetime_position_(-1),
         previous_(NULL),
         next_(NULL),
@@ -435,6 +440,12 @@ FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
     return next() == NULL;
   }
 
+  virtual bool InferRange() {
+    return false;
+  }
+
+  virtual Range* range();
+
   // Returns deoptimization id that corresponds to the deoptimization target
   // that input operands conversions inserted for this instruction can jump
   // to.
@@ -491,6 +502,8 @@ FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
     return deopt_id_;
   }
 
+  Range* range_;

[Florian Schneider, 2012/09/21 08:56:44]

It seems that range_ can be made a member of Definition instead of Instruction.

[Kevin Millikin (Google), 2012/09/21 08:59:33]

Does it buy us anything to make this a pointer instead of embedded?  The virtual
accessor and lazy initialization seems unnecessary.

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Done.

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Pointer allows use also to express _|_ state which is quite important for phi's
join function.

+
  private:
   friend class Definition;  // Needed for InsertBefore, InsertAfter.
 
@@ -723,6 +736,10 @@ class BlockEntryInstr : public Instruction {
     loop_info_ = loop_info;
   }
 
+  virtual BlockEntryInstr* GetBlock() const {
+    return const_cast<BlockEntryInstr*>(this);
+  }
+
  protected:
   explicit BlockEntryInstr(intptr_t try_index)
       : try_index_(try_index),
@@ -929,6 +946,37 @@ class JoinEntryInstr : public BlockEntryInstr {
 };
 
 
+class PhiIterator : public ValueObject {
+ public:
+  explicit PhiIterator(JoinEntryInstr* join)
+      : phis_(join->phis()), index_(-1) {
+    Advance();
+  }
+
+  void Advance() {

[Kevin Millikin (Google), 2012/09/21 08:59:33]

Simpler:

void Advance() {
  ++index_;
  while (!Done() && Current() == NULL) ++index_;
}

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

This is how it looked initially. I just wanted to make a register promotion
manually :-)

    do {
      index_++;
    } while (!Done() && (Current() == NULL))

+    if (Done()) return;

[Florian Schneider, 2012/09/21 08:56:44]

I'd rather write ASSERT(!Done());

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Done.

+
+    intptr_t i = index_ + 1;
+    while ((i < phis_->length()) && ((*phis_)[i] == NULL)) {
+      i++;
+    }
+    index_ = i;
+  }
+
+  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)
@@ -1106,7 +1154,8 @@ class PhiInstr : public Definition {
     : block_(block),
       inputs_(num_inputs),
       is_alive_(false),
-      representation_(kTagged) {
+      representation_(kTagged),
+      has_unranged_inputs_(true) {
     for (intptr_t i = 0; i < num_inputs; ++i) {
       inputs_.Add(NULL);
     }
@@ -1165,6 +1214,10 @@ class PhiInstr : public Definition {
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
+  virtual bool InferRange();
+
+  virtual Range* range() { return range_; }
+
  private:
   friend class JoinEntryInstr;  // Direct access to inputs_ array.
 
@@ -1173,6 +1226,8 @@ class PhiInstr : public Definition {
   bool is_alive_;
   Representation representation_;
 
+  bool has_unranged_inputs_;

[Florian Schneider, 2012/09/21 08:56:44]

Maybe rename to has_inputs_without_range_.

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Done.

+
   DISALLOW_COPY_AND_ASSIGN(PhiInstr);
 };
 
@@ -1530,9 +1585,257 @@ class TemplateDefinition : public Definition {
 };
 
 
+class RangeBoundary : public ValueObject {
+ public:
+  enum Kind { kUnknown, kSymbol, kConstant };
+
+  RangeBoundary() : kind_(kUnknown), value_(0), offs_(0) { }

[Kevin Millikin (Google), 2012/09/21 08:59:33]

Please burn two characters to spell out 'offset'.

Alternatively, you could save an additional two and just call this 'of'.

:)

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Done.

+
+  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((min_a < min_b) ? min_a : min_b);

[Kevin Millikin (Google), 2012/09/21 08:59:33]

You can spell this Utils::Minimum(min_a, min_b)

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Done.

+  }
+
+  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((max_a > max_b) ? 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_);

[Florian Schneider, 2012/09/21 08:56:44]

&& (offs_ == other.offs_)

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Nice catch!

+  }
+
+  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::IsValid64(result)) {

[Florian Schneider, 2012/09/21 08:56:44]

I think this should be Smi::IsValid(intptr_t value)

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Yes. 64 is a leftover of an experiment.

+      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::IsValid64(result)) {

[Florian Schneider, 2012/09/21 08:56:44]

Use Smi::IsValid(intptr_t value) here too.

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Done.

+      return overflow;
+    }
+    return RangeBoundary::FromConstant(result);
+  }
+
+ private:
+  RangeBoundary(Kind kind, intptr_t value, intptr_t offs)
+      : kind_(kind), value_(value), offs_(offs) { }
+
+  Kind kind_;
+  intptr_t value_;
+  intptr_t offs_;
+};
+
+
+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();
+
+  virtual Range* range() {
+    return range_;
+  }
+
+  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;
@@ -1550,6 +1853,16 @@ class ConstantInstr : public TemplateDefinition<0> {
   virtual bool AttributesEqual(Instruction* other) const;
   virtual bool AffectedBySideEffect() const { return false; }
 
+  virtual Range* range() {

[Kevin Millikin (Google), 2012/09/21 08:59:33]

This is disconcerting.  Simpler just to treat smi constants like smi definitions
in the analysis, implement InferRange for them, and make the range() accessor
non-virtual.

Also, I find it disconcerting that we can safely call "range()" for all
instructions except non-smi constants which ASSERT --- and that just seems to be
an artifact of the complicated lazy initialization and not treating smi
constants as smi definitions.

[Vyacheslav Egorov (Google), 2012/09/21 20:08:07]

Initially I wanted to make range() assert when you try to call it for a non-smi
value. But then it fell through. 

I refactored it to initialize range_ in the InferRange which asserts if you try
to apply it to a non-smi value.

+    ASSERT(value_.IsSmi());
+    if (range_ == NULL) {
+      intptr_t value = Smi::Cast(value_).Value();
+      range_ = new Range(RangeBoundary::FromConstant(value),
+                         RangeBoundary::FromConstant(value));
+    }
+    return range_;
+  }
+
  private:
   const Object& value_;
 
@@ -1855,7 +2168,8 @@ class PolymorphicInstanceCallInstr : public TemplateDefinition<0> {
 
 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;
@@ -3151,7 +3465,8 @@ class BinarySmiOpInstr : public TemplateDefinition<2> {
                    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;
@@ -3181,9 +3496,19 @@ class BinarySmiOpInstr : public TemplateDefinition<2> {
 
   virtual intptr_t ResultCid() const;
 
+  void set_overflow(bool overflow) {
+    overflow_ = overflow;
+  }
+
+  void PrintTo(BufferFormatter* f) const;
+
+  virtual bool InferRange();
+  virtual Range* range() { return range_; }
+
  private:
   const Token::Kind op_kind_;
   InstanceCallInstr* instance_call_;
+  bool overflow_;
 
   DISALLOW_COPY_AND_ASSIGN(BinarySmiOpInstr);
 };