Fix convergence issues in range analysis.

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"
@@ skipping 1096 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();
+  enum RangeOperator { kRangeInit, kRangeWiden, kRangeNarrow };
+
+  virtual bool InferRange(RangeOperator op);
 
   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_;
@@ skipping 74 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 bool InferRange(RangeOperator op);
 
  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
@@ skipping 372 matching lines @@
   }
 
   static RangeBoundary MinSmi() {
     return FromConstant(Smi::kMinValue);
   }
 
   static RangeBoundary MaxSmi() {
     return FromConstant(Smi::kMaxValue);
   }
 
+  static const intptr_t kMinusInfinity = Smi::kMinValue - 1;
+  static const intptr_t kPlusInfinity = Smi::kMaxValue + 1;
+
   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();
@@ skipping 38 matching lines @@
     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 OverflowedMinSmi();
     }
-    return new_min;
+    return old_min;
   }
 
   static RangeBoundary WidenMax(const RangeBoundary& old_max,
                                 const RangeBoundary& new_max) {
     if (new_max.UpperBound().value() > old_max.UpperBound().value()) {
-      return MaxSmi();
+      return OverflowedMaxSmi();
     }
-    return new_max;
+    return old_max;
+  }
+
+  static RangeBoundary NarrowMin(const RangeBoundary& old_min,
+                                 const RangeBoundary& new_min) {
+    ASSERT(old_min.IsConstant());
+    ASSERT(new_min.IsConstant());
+    return (old_min.value() == kMinusInfinity) ? new_min
+                                               : Min(old_min, new_min);
+  }
+
+  static RangeBoundary NarrowMax(const RangeBoundary& old_max,
+                                const RangeBoundary& new_max) {
+    return (old_max.value() == kPlusInfinity) ? new_max
+                                              : Max(old_max, 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();
@@ skipping 27 matching lines @@
 
 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;
+  static const char* ToCString(Range* range);
 
   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,
@@ skipping 53 matching lines @@
   virtual bool AttributesEqual(Instruction* 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 bool InferRange(RangeOperator op);
 
   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() {
@@ skipping 32 matching lines @@
 
   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();
+  virtual bool InferRange(RangeOperator op);
 
  private:
   const Object& value_;
 
   DISALLOW_COPY_AND_ASSIGN(ConstantInstr);
 };
 
 
 class AssertAssignableInstr : public TemplateDefinition<3> {
  public:
@@ skipping 1620 matching lines @@
   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();
+  virtual bool InferRange(RangeOperator op);
 
  private:
   const Token::Kind op_kind_;
   InstanceCallInstr* instance_call_;
   bool overflow_;
 
   DISALLOW_COPY_AND_ASSIGN(BinarySmiOpInstr);
 };
 
 
@@ skipping 467 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_