Fix convergence issues in range analysis.

runtime/vm/intermediate_language.cc

 // 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.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 1852 matching lines @@
   for (Environment::DeepIterator it(copy); !it.Done(); it.Advance()) {
     Value* value = it.CurrentValue();
     value->set_instruction(instr);
     value->set_use_index(use_index++);
     value->AddToEnvUseList();
   }
   instr->env()->outer_ = copy;
 }
 
 
-bool Definition::InferRange() {
+RangeBoundary RangeBoundary::LowerBound() const {
+  if (IsConstant()) return *this;
+  if (symbol()->range() == NULL) return MinSmi();
+  return Add(symbol()->range()->min().LowerBound(),
+             RangeBoundary::FromConstant(offset_),
+             MinSmi());
+}
+
+
+RangeBoundary RangeBoundary::UpperBound() const {
+  if (IsConstant()) return *this;
+  if (symbol()->range() == NULL) return MaxSmi();
+  return Add(symbol()->range()->max().UpperBound(),
+             RangeBoundary::FromConstant(offset_),
+             MaxSmi());
+}
+
+
+bool Definition::InferRange(RangeOperator op) {
   ASSERT(GetPropagatedCid() == kSmiCid);  // Has meaning only for smis.
   if (range_ == NULL) {
     range_ = Range::Unknown();
     return true;
   }
   return false;
 }
 
 
-bool ConstantInstr::InferRange() {
+bool ConstantInstr::InferRange(RangeOperator op) {
   ASSERT(value_.IsSmi());
   if (range_ == NULL) {
     intptr_t value = Smi::Cast(value_).Value();
     range_ = new Range(RangeBoundary::FromConstant(value),
                        RangeBoundary::FromConstant(value));
     return true;
   }
   return false;
 }
 
 
-RangeBoundary RangeBoundary::LowerBound() const {
-  if (IsConstant()) return *this;
-  if (symbol()->range() == NULL) return MinSmi();
-  return Add(symbol()->range()->min().LowerBound(),
-             RangeBoundary::FromConstant(offset_),
-             MinSmi());
-}
-
-
-RangeBoundary RangeBoundary::UpperBound() const {
-  if (IsConstant()) return *this;
-  if (symbol()->range() == NULL) return MaxSmi();
-  return Add(symbol()->range()->max().UpperBound(),
-             RangeBoundary::FromConstant(offset_),
-             MaxSmi());
-}
-
-
-bool ConstraintInstr::InferRange() {
+bool ConstraintInstr::InferRange(RangeOperator op) {
   Range* value_range = value()->definition()->range();
 
   // Compute intersection of constraint and value ranges.
   return Range::Update(&range_,
       RangeBoundary::Max(Range::ConstantMin(value_range),
                          Range::ConstantMin(constraint())),
       RangeBoundary::Min(Range::ConstantMax(value_range),
                          Range::ConstantMax(constraint())));
 }
 
 
-bool PhiInstr::InferRange() {
+bool PhiInstr::InferRange(RangeOperator op) {
   RangeBoundary new_min;
   RangeBoundary new_max;
 
-  bool has_inputs_without_range = false;
   for (intptr_t i = 0; i < InputCount(); i++) {
     Range* input_range = InputAt(i)->definition()->range();
     if (input_range == NULL) {
-      has_inputs_without_range = true;
       continue;
     }
 
     if (new_min.IsUnknown()) {
       new_min = Range::ConstantMin(input_range);
     } else {
       new_min = RangeBoundary::Min(new_min, Range::ConstantMin(input_range));
     }
 
     if (new_max.IsUnknown()) {
       new_max = Range::ConstantMax(input_range);
     } else {
       new_max = RangeBoundary::Max(new_max, Range::ConstantMax(input_range));
     }
   }
 
   ASSERT(new_min.IsUnknown() == new_max.IsUnknown());
   if (new_min.IsUnknown()) {
-    ASSERT(range_ == NULL);
+    range_ = Range::Unknown();
     return false;
   }
 
-  if ((range_ != NULL) && !has_inputs_without_range_) {
-    // If phi's range is growing widen it in the direction of growth to
-    // speedup convergence.
+  if (op == Definition::kRangeWiden) {
+    // Apply widening operator.
     new_min = RangeBoundary::WidenMin(range_->min(), new_min);
     new_max = RangeBoundary::WidenMax(range_->max(), new_max);
+  } else if (op == Definition::kRangeNarrow) {
+    // Apply narrowing operator.
+    new_min = RangeBoundary::NarrowMin(range_->min(), new_min);
+    new_max = RangeBoundary::NarrowMax(range_->max(), new_max);
   }
-  has_inputs_without_range_ = has_inputs_without_range;
 
   return Range::Update(&range_, new_min, new_max);
 }
 
 
-bool BinarySmiOpInstr::InferRange() {
+bool BinarySmiOpInstr::InferRange(RangeOperator op) {
   Range* left_range = left()->definition()->range();
   Range* right_range = right()->definition()->range();
 
   if ((left_range == NULL) || (right_range == NULL)) {
     return Range::Update(&range_,
                          RangeBoundary::MinSmi(),
                          RangeBoundary::MaxSmi());
   }
 
   RangeBoundary new_min;
@@ skipping 24 matching lines @@
     default:
       if (range_ == NULL) {
         range_ = Range::Unknown();
         return true;
       }
       return false;
   }
 
   ASSERT(!new_min.IsUnknown() && !new_max.IsUnknown());
   set_overflow(new_min.Overflowed() || new_max.Overflowed());
+
+  if (op == Definition::kRangeNarrow) {
+    new_min = new_min.Clamp();
+    new_max = new_max.Clamp();
+  }
+
   return Range::Update(&range_, new_min, new_max);
 }
 
 
 #undef __
 
 }  // namespace dart