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"
 
+#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);
 
 
 Definition::Definition()
     : temp_index_(-1),
       ssa_temp_index_(-1),
       propagated_type_(AbstractType::Handle()),
       propagated_cid_(kIllegalCid),
@@ skipping 532 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;
 }
 
 
+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