Implement range analysis for smi values.

runtime/vm/intermediate_language.cc

Index: runtime/vm/intermediate_language.cc
diff --git a/runtime/vm/intermediate_language.cc b/runtime/vm/intermediate_language.cc
index a76b8dd953705261a9af13c323f6ea5c1d36a5e9..0fa75ac7f6441ae350ef3dabc647d3cd416ba9e3 100644
--- a/runtime/vm/intermediate_language.cc
+++ b/runtime/vm/intermediate_language.cc
@@ -18,6 +18,8 @@
 #include "vm/stub_code.h"
 #include "vm/symbols.h"
 
+#include "vm/il_printer.h"

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

Why this include?

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

Is there any reason to split this out from all the other includes?  Is it needed
here?

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

Debugging leftover. Removing.

+
 namespace dart {
 
 DECLARE_FLAG(bool, enable_type_checks);
@@ -570,6 +572,21 @@ void Value::AddToEnvUseList() {
 }
 
 
+void Value::RemoveFromInputUseList() {
+  if (definition_->input_use_list() == this) {
+    definition_->set_input_use_list(next_use_);
+    return;
+  }
+
+  Value* prev = definition_->input_use_list();
+  while (prev->next_use_ != this) {
+    prev = prev->next_use_;
+  }
+  prev->next_use_ = next_use_;
+  definition_ = NULL;
+}
+
+
 void Definition::ReplaceUsesWith(Definition* other) {
   ASSERT(other != NULL);
   ASSERT(this != other);
@@ -1211,7 +1228,7 @@ bool BinarySmiOpInstr::CanDeoptimize() const {
     case Token::kBIT_XOR:
       return false;
     default:
-      return true;
+      return overflow_;
   }
 }
 
@@ -1436,6 +1453,16 @@ void ParallelMoveInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
 }
 
 
+LocationSummary* ConstraintInstr::MakeLocationSummary() const {
+  UNREACHABLE();
+  return NULL;
+}
+
+
+void ConstraintInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
+  UNREACHABLE();
+}
+
 LocationSummary* ThrowInstr::MakeLocationSummary() const {
   return new LocationSummary(0, 0, LocationSummary::kCall);
 }
@@ -1843,6 +1870,138 @@ void Environment::DeepCopyToOuter(Instruction* instr) const {
 }
 
 
+Range* Instruction::range() {
+  if (range_ == NULL) {
+    range_ = Range::Unknown();
+  }
+  return range_;
+}
+
+
+RangeBoundary RangeBoundary::LowerBound() const {
+  if (IsConstant()) return *this;
+  if (symbol()->range() == NULL) return MinSmi();
+  return Add(symbol()->range()->min().LowerBound(),
+             RangeBoundary::FromConstant(offs_),
+             MinSmi());
+}
+
+
+RangeBoundary RangeBoundary::UpperBound() const {
+  if (IsConstant()) return *this;
+  if (symbol()->range() == NULL) return MaxSmi();
+  return Add(symbol()->range()->max().UpperBound(),
+             RangeBoundary::FromConstant(offs_),
+             MaxSmi());
+}
+
+
+bool ConstraintInstr::InferRange() {
+  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() {
+  RangeBoundary new_min;
+  RangeBoundary new_max;
+
+  bool has_unranged_inputs = false;
+  for (intptr_t i = 0; i < InputCount(); i++) {
+    Range* input_range = InputAt(i)->definition()->range();
+    if (input_range == NULL) {
+      has_unranged_inputs = 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);
+    return false;
+  }
+
+  bool had_unranged_inputs = has_unranged_inputs_;

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

Simpler to test the old value before changing it:

if ((range_ != NULL) && !has_unranged_inputs_) {
  ...
}
has_unranged_inputs_ = has_unranged_inputs_ && has_unranged_inputs;

(Though, I think it should be monotone, so:

ASSERT(has_unranged_inputs <= has_unranged_inputs_);  // Ha ha.
has_unranged_inputs_ = has_unranged_inputs;

)

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

Agreed. The control flow in this function was previously more convoluted (had
multiple exits) that is why I used an additional variable to keep previous
state.

+  if (!has_unranged_inputs) has_unranged_inputs_ = false;
+
+  if ((range_ != NULL) && !had_unranged_inputs) {
+    // If phi's range is growing widen it in the direction of growth to
+    // speedup convergence.
+    new_min = RangeBoundary::WidenMin(range_->min(), new_min);
+    new_max = RangeBoundary::WidenMax(range_->max(), new_max);
+  }
+
+  return Range::Update(&range_, new_min, new_max);
+}
+
+
+bool BinarySmiOpInstr::InferRange() {
+  Range* lrange = left()->definition()->range();

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

lrange and rrange are easy to confuse. How about just left_range and
right_range?

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

Done.

+  Range* rrange = right()->definition()->range();
+
+  if ((lrange == NULL) || (rrange == NULL)) {
+    return Range::Update(&range_,
+                         RangeBoundary::MinSmi(),
+                         RangeBoundary::MaxSmi());
+  }
+
+  RangeBoundary new_min;
+  RangeBoundary new_max;
+  switch (op_kind()) {
+    case Token::kADD:
+      new_min =
+        RangeBoundary::Add(Range::ConstantMin(lrange),
+                           Range::ConstantMin(rrange),
+                           RangeBoundary::OverflowedMinSmi());
+      new_max =
+        RangeBoundary::Add(Range::ConstantMax(lrange),
+                           Range::ConstantMax(rrange),
+                           RangeBoundary::OverflowedMaxSmi());
+      break;
+
+    case Token::kSUB:
+      new_min =
+        RangeBoundary::Sub(Range::ConstantMin(lrange),
+                           Range::ConstantMax(rrange),
+                           RangeBoundary::OverflowedMinSmi());
+      new_max =
+        RangeBoundary::Sub(Range::ConstantMax(lrange),
+                           Range::ConstantMin(rrange),
+                           RangeBoundary::OverflowedMaxSmi());
+      break;
+
+    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());
+  return Range::Update(&range_, new_min, new_max);
+}
+
+
 #undef __
 
 }  // namespace dart