Implement range analysis for smi values.

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"
 #include "vm/flow_graph_compiler.h"
 #include "vm/flow_graph_optimizer.h"
 #include "vm/locations.h"
 #include "vm/object.h"
 #include "vm/object_store.h"
 #include "vm/os.h"
 #include "vm/scopes.h"
 #include "vm/stub_code.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, enable_type_checks);
 
 
 Definition::Definition()
-    : temp_index_(-1),
+    : range_(NULL),
+      temp_index_(-1),
       ssa_temp_index_(-1),
       propagated_type_(AbstractType::Handle()),
       propagated_cid_(kIllegalCid),
       input_use_list_(NULL),
       env_use_list_(NULL),
       use_kind_(kValue),  // Phis and parameters rely on this default.
       constant_value_(Object::ZoneHandle(ConstantPropagator::Unknown())) {
 }
 
 
@@ skipping 50 matching lines @@
 bool StrictCompareInstr::AttributesEqual(Instruction* other) const {
   StrictCompareInstr* other_op = other->AsStrictCompare();
   ASSERT(other_op != NULL);
   return kind() == other_op->kind();
 }
 
 
 bool BinarySmiOpInstr::AttributesEqual(Instruction* other) const {
   BinarySmiOpInstr* other_op = other->AsBinarySmiOp();
   ASSERT(other_op != NULL);
-  return op_kind() == other_op->op_kind();
+  return (op_kind() == other_op->op_kind()) &&
+      (overflow_ == other_op->overflow_);
 }
 
 
 bool LoadFieldInstr::AttributesEqual(Instruction* other) const {
   LoadFieldInstr* other_load = other->AsLoadField();
   ASSERT(other_load != NULL);
   ASSERT((offset_in_bytes() != other_load->offset_in_bytes()) ||
          ((immutable_ == other_load->immutable_) &&
           (ResultCid() == other_load->ResultCid())));
   return offset_in_bytes() == other_load->offset_in_bytes();
@@ skipping 454 matching lines @@
   definition()->set_input_use_list(this);
 }
 
 
 void Value::AddToEnvUseList() {
   set_next_use(definition()->env_use_list());
   definition()->set_env_use_list(this);
 }
 
 
+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);
   while (input_use_list_ != NULL) {
     Value* current = input_use_list_;
     input_use_list_ = input_use_list_->next_use();
     current->set_definition(other);
     current->AddToInputUseList();
   }
   while (env_use_list_ != NULL) {
@@ skipping 621 matching lines @@
 }
 
 
 bool BinarySmiOpInstr::CanDeoptimize() const {
   switch (op_kind()) {
     case Token::kBIT_AND:
     case Token::kBIT_OR:
     case Token::kBIT_XOR:
       return false;
     default:
-      return true;
+      return overflow_;
   }
 }
 
 
 RawAbstractType* BinaryMintOpInstr::CompileType() const {
   return Type::MintType();
 }
 
 
 intptr_t BinaryMintOpInstr::ResultCid() const {
@@ skipping 204 matching lines @@
 LocationSummary* ParallelMoveInstr::MakeLocationSummary() const {
   return NULL;
 }
 
 
 void ParallelMoveInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
   UNREACHABLE();
 }
 
 
+LocationSummary* ConstraintInstr::MakeLocationSummary() const {
+  UNREACHABLE();
+  return NULL;
+}
+
+
+void ConstraintInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
+  UNREACHABLE();
+}
+
 LocationSummary* ThrowInstr::MakeLocationSummary() const {
   return new LocationSummary(0, 0, LocationSummary::kCall);
 }
 
 
 
 void ThrowInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
   compiler->GenerateCallRuntime(token_pos(),
                                 kThrowRuntimeEntry,
                                 locs());
@@ skipping 387 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() {
+  ASSERT(GetPropagatedCid() == kSmiCid);  // Has meaning only for smis.
+  if (range_ == NULL) {
+    range_ = Range::Unknown();
+    return true;
+  }
+  return false;
+}
+
+
+bool ConstantInstr::InferRange() {
+  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() {
+  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_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);
+    return false;
+  }
+
+  if ((range_ != NULL) && !has_inputs_without_range_) {
+    // If phi's range is growing widen it in the direction of growth to

[ngeoffray, 2012/09/24 21:44:15]

growing widen -> growing, widen

+    // speedup convergence.

[ngeoffray, 2012/09/24 21:44:15]

What's the check for 'growing' here? At first glance it looks like it is the
(range_ != NULL check), but what about phi instructions that use a loop phi?

+    new_min = RangeBoundary::WidenMin(range_->min(), new_min);
+    new_max = RangeBoundary::WidenMax(range_->max(), new_max);
+  }
+  has_inputs_without_range_ = has_inputs_without_range;
+
+  return Range::Update(&range_, new_min, new_max);
+}
+
+
+bool BinarySmiOpInstr::InferRange() {
+  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;
+  RangeBoundary new_max;
+  switch (op_kind()) {
+    case Token::kADD:
+      new_min =
+        RangeBoundary::Add(Range::ConstantMin(left_range),
+                           Range::ConstantMin(right_range),
+                           RangeBoundary::OverflowedMinSmi());
+      new_max =
+        RangeBoundary::Add(Range::ConstantMax(left_range),
+                           Range::ConstantMax(right_range),
+                           RangeBoundary::OverflowedMaxSmi());
+      break;
+
+    case Token::kSUB:
+      new_min =
+        RangeBoundary::Sub(Range::ConstantMin(left_range),
+                           Range::ConstantMax(right_range),
+                           RangeBoundary::OverflowedMinSmi());
+      new_max =
+        RangeBoundary::Sub(Range::ConstantMax(left_range),
+                           Range::ConstantMin(right_range),
+                           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