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; }                                  \
   virtual void Accept(FlowGraphVisitor* visitor);                              \
   virtual type##Instr* As##type() { return this; }                             \
   virtual const char* DebugName() const { return #type; }                      \
   virtual LocationSummary* MakeLocationSummary() const;                        \
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);                    \
 
 
 class Instruction : public ZoneAllocated {
  public:
 #define DECLARE_TAG(type) k##type,
   enum Tag {
     FOR_EACH_INSTRUCTION(DECLARE_TAG)
   };
 #undef DECLARE_TAG
 
   Instruction()
-      : deopt_id_(Isolate::Current()->GetNextDeoptId()),
+      : range_(NULL),
+        deopt_id_(Isolate::Current()->GetNextDeoptId()),
         lifetime_position_(-1),
         previous_(NULL),
         next_(NULL),
         env_(NULL),
         expr_id_(-1) { }
 
   virtual Tag tag() const = 0;
 
   intptr_t deopt_id() const {
     ASSERT(CanDeoptimize());
@@ skipping 136 matching lines @@
 
   // Representation of the value produced by this computation.
   virtual Representation representation() const {
     return kTagged;
   }
 
   bool WasEliminated() const {
     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.
   virtual intptr_t DeoptimizationTarget() const {
     UNREACHABLE();
     return Isolate::kNoDeoptId;
   }
 
   // Returns a replacement for the instruction or NULL if the instruction can
   // be eliminated.  By default returns the this instruction which means no
@@ skipping 36 matching lines @@
     UNREACHABLE();
     return false;
   }
 
  protected:
   // Fetch deopt id without checking if this computation can deoptimize.
   intptr_t GetDeoptId() const {
     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.
 
   // Classes that set deopt_id_.
   friend class UnboxDoubleInstr;
   friend class UnboxedDoubleBinaryOpInstr;
   friend class MathSqrtInstr;
   friend class CheckClassInstr;
   friend class CheckSmiInstr;
   friend class CheckArrayBoundInstr;
@@ skipping 212 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) {
+    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)
       : 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 157 matching lines @@
   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_unranged_inputs_(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();
+
+  virtual Range* range() { return range_; }
+
  private:
   friend class JoinEntryInstr;  // Direct access to inputs_ array.
 
   JoinEntryInstr* block_;
   GrowableArray<Value*> inputs_;
   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);
 };
 
 
 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), 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;
 
   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 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_;
 
   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;

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

You need to update AttributesEqual to check of overflow_ matches.

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

Yes, thanks for reminding me. I kept this in mind, but I forgot to do that. It
does not matter at this stage though because LICM and CSE precede RangeAnalysis.

 
   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);
 };
 
 
 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_