Simplify range analysis algorithm.

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 1092 matching lines @@
   // formatting. Otherwise, it prints in the format "opcode(op1, op2, op3)".
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintOperandsTo(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_; }
 
-  enum RangeOperator { kRangeInit, kRangeWiden, kRangeNarrow };
-
-  virtual bool InferRange(RangeOperator op);
+  virtual void 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:
+  friend class RangeAnalysis;
+
   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),
-      has_inputs_without_range_(true) {
+      representation_(kTagged) {
     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 37 matching lines @@
 
   virtual intptr_t ResultCid() const {
     UNREACHABLE();
     return kIllegalCid;
   }
 
   DECLARE_INSTRUCTION(Phi)
 
   virtual void PrintTo(BufferFormatter* f) const;
 
-  virtual bool InferRange(RangeOperator op);
+  virtual void InferRange();
 
  private:
   friend class ConstantPropagator;  // Direct access to inputs_.
 
   JoinEntryInstr* block_;
   GrowableArray<Value*> inputs_;
   bool is_alive_;
   Representation representation_;
 
-  // Used to determine an interation of a range analysis after all phi inputs
-  // 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 413 matching lines @@
   }
 
   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 OverflowedMinSmi();
-    }
-    return old_min;
-  }
-
-  static RangeBoundary WidenMax(const RangeBoundary& old_max,
-                                const RangeBoundary& new_max) {
-    if (new_max.UpperBound().value() > old_max.UpperBound().value()) {
-      return OverflowedMaxSmi();
-    }
-    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();
     if (!Smi::IsValid(result)) {
       return overflow;
@@ skipping 34 matching lines @@
   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,
-                     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();
   }
 
@@ skipping 26 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(RangeOperator op);
+  virtual void 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() {
@@ 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(RangeOperator op);
+  virtual void InferRange();
 
  private:
   const Object& value_;
 
   DISALLOW_COPY_AND_ASSIGN(ConstantInstr);
 };
 
 
 class AssertAssignableInstr : public TemplateDefinition<3> {
  public:
@@ skipping 1901 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(RangeOperator op);
+  virtual void InferRange();
 
  private:
   const Token::Kind op_kind_;
   InstanceCallInstr* instance_call_;
   bool overflow_;
 
   DISALLOW_COPY_AND_ASSIGN(BinarySmiOpInstr);
 };
 
 
@@ skipping 455 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_