Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(625)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: runtime/vm/flow_graph_range_analysis.cc

Issue 472303002: Revert "Switch to a fix-point based range analysis to improve its precision." (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « runtime/vm/flow_graph_range_analysis.h ('k') | runtime/vm/flow_graph_range_analysis_test.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/vm/flow_graph_range_analysis.cc
diff --git a/runtime/vm/flow_graph_range_analysis.cc b/runtime/vm/flow_graph_range_analysis.cc
index 5d132c264af728080049e27d55f2ee6826fb7a95..ff95ed041e7a6e1450e5ba271ab8c931bd06d577 100644
--- a/runtime/vm/flow_graph_range_analysis.cc
+++ b/runtime/vm/flow_graph_range_analysis.cc
@@ -23,12 +23,8 @@ void RangeAnalysis::Analyze() {
CollectValues();
InsertConstraints();
InferRanges();
- EliminateRedundantBoundsChecks();
- MarkUnreachableBlocks();
-
IntegerInstructionSelector iis(flow_graph_);
iis.Select();
-
RemoveConstraints();
}
@@ -89,13 +85,7 @@ void RangeAnalysis::CollectValues() {
values_.Add(defn);
}
} else if (current->IsCheckSmi()) {
- if (current->Canonicalize(flow_graph_) == NULL) {
- instr_it.RemoveCurrentFromGraph();
- continue;
- }
smi_checks_.Add(current->AsCheckSmi());
- } else if (current->IsCheckArrayBound()) {
- bounds_checks_.Add(current->AsCheckArrayBound());
}
}
}
@@ -170,13 +160,13 @@ static Token::Kind FlipComparison(Token::Kind op) {
// that it evaluated to true.
// For example for the comparison a < b symbol a is constrained with range
// [Smi::kMinValue, b - 1].
-Range* RangeAnalysis::ConstraintSmiRange(Token::Kind op, Definition* boundary) {
+Range* RangeAnalysis::ConstraintRange(Token::Kind op, Definition* boundary) {
switch (op) {
case Token::kEQ:
return new(I) Range(RangeBoundary::FromDefinition(boundary),
RangeBoundary::FromDefinition(boundary));
case Token::kNE:
- return new(I) Range(Range::Full(RangeBoundary::kRangeBoundarySmi));
+ return Range::Unknown();
case Token::kLT:
return new(I) Range(RangeBoundary::MinSmi(),
RangeBoundary::FromDefinition(boundary, -1));
@@ -191,7 +181,7 @@ Range* RangeAnalysis::ConstraintSmiRange(Token::Kind op, Definition* boundary) {
RangeBoundary::MaxSmi());
default:
UNREACHABLE();
- return NULL;
+ return Range::Unknown();
}
}
@@ -202,18 +192,7 @@ ConstraintInstr* RangeAnalysis::InsertConstraintFor(Definition* defn,
// No need to constrain constants.
if (defn->IsConstant()) return NULL;
- // Check if the value is already constrained to avoid inserting duplicated
- // constraints.
- ConstraintInstr* constraint = after->next()->AsConstraint();
- while (constraint != NULL) {
- if ((constraint->value()->definition() == defn) &&
- constraint->constraint()->Equals(constraint_range)) {
- return NULL;
- }
- constraint = constraint->next()->AsConstraint();
- }
-
- constraint = new(I) ConstraintInstr(
+ ConstraintInstr* constraint = new(I) ConstraintInstr(
new(I) Value(defn), constraint_range);
flow_graph_->InsertAfter(after, constraint, NULL, FlowGraph::kValue);
RenameDominatedUses(defn, constraint, constraint);
@@ -244,7 +223,7 @@ void RangeAnalysis::ConstrainValueAfterBranch(Definition* defn, Value* use) {
// Constrain definition at the true successor.
ConstraintInstr* true_constraint =
InsertConstraintFor(defn,
- ConstraintSmiRange(op_kind, boundary),
+ ConstraintRange(op_kind, boundary),
branch->true_successor());
// Mark true_constraint an artificial use of boundary. This ensures
// that constraint's range is recalculated if boundary's range changes.
@@ -257,7 +236,7 @@ void RangeAnalysis::ConstrainValueAfterBranch(Definition* defn, Value* use) {
ConstraintInstr* false_constraint =
InsertConstraintFor(
defn,
- ConstraintSmiRange(Token::NegateComparison(op_kind), boundary),
+ ConstraintRange(Token::NegateComparison(op_kind), boundary),
branch->false_successor());
// Mark false_constraint an artificial use of boundary. This ensures
// that constraint's range is recalculated if boundary's range changes.
@@ -305,23 +284,16 @@ void RangeAnalysis::ConstrainValueAfterCheckArrayBound(
void RangeAnalysis::InsertConstraints() {
- Range* smi_range = new(I) Range(
- Range::Full(RangeBoundary::kRangeBoundarySmi));
-
for (intptr_t i = 0; i < smi_checks_.length(); i++) {
CheckSmiInstr* check = smi_checks_[i];
ConstraintInstr* constraint =
InsertConstraintFor(check->value()->definition(),
- smi_range,
+ Range::UnknownSmi(),
check);
if (constraint == NULL) {
// No constraint was needed.
continue;
}
- if (!check->value()->definition()->IsBoxInteger()) {
- constraint->set_range(Range::Full(RangeBoundary::kRangeBoundarySmi));
- }
-
// Mark the constraint's value's reaching type as smi.
CompileType* smi_compile_type =
ZoneCompileType::Wrap(CompileType::FromCid(kSmiCid));
@@ -338,305 +310,220 @@ void RangeAnalysis::InsertConstraints() {
}
-static Definition* UnwrapConstraint(Definition* defn) {
- while (defn->IsConstraint()) {
- defn = defn->AsConstraint()->value()->definition();
+void RangeAnalysis::ResetWorklist() {
+ if (marked_defns_ == NULL) {
+ marked_defns_ = new(I) BitVector(flow_graph_->current_ssa_temp_index());
+ } else {
+ marked_defns_->Clear();
}
- return defn;
+ worklist_.Clear();
}
-static bool AreEqualDefinitions(Definition* a, Definition* b) {
- a = UnwrapConstraint(a);
- b = UnwrapConstraint(b);
- return (a == b) ||
- (a->AllowsCSE() &&
- a->Dependencies().IsNone() &&
- b->AllowsCSE() &&
- b->Dependencies().IsNone() &&
- a->Equals(b));
-}
-
+void RangeAnalysis::MarkDefinition(Definition* defn) {
+ // Unwrap constrained value.
+ while (defn->IsConstraint()) {
+ defn = defn->AsConstraint()->value()->definition();
+ }
-static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) {
- return a.IsSymbol() && b.IsSymbol() &&
- AreEqualDefinitions(a.symbol(), b.symbol());
+ if (!marked_defns_->Contains(defn->ssa_temp_index())) {
+ worklist_.Add(defn);
+ marked_defns_->Add(defn->ssa_temp_index());
+ }
}
-// Given the current range of a phi and a newly computed range check
-// if it is growing towards negative infinity, if it does widen it to
-// MinSmi.
-static RangeBoundary WidenMin(const Range* range, const Range* new_range) {
- RangeBoundary min = range->min();
- RangeBoundary new_min = new_range->min();
-
- if (min.IsSymbol()) {
- if (min.LowerBound().OverflowedSmi()) {
- return RangeBoundary::MinSmi();
- } else if (DependOnSameSymbol(min, new_min)) {
- return min.offset() <= new_min.offset() ? min : RangeBoundary::MinSmi();
- } else if (min.SmiUpperBound() <= new_min.SmiLowerBound()) {
- return min;
+RangeAnalysis::Direction RangeAnalysis::ToDirection(Value* val) {
+ if (val->BindsToConstant()) {
+ return (Smi::Cast(val->BoundConstant()).Value() >= 0) ? kPositive
+ : kNegative;
+ } else if (val->definition()->range() != NULL) {
+ Range* range = val->definition()->range();
+ if (Range::ConstantMin(range).ConstantValue() >= 0) {
+ return kPositive;
+ } else if (Range::ConstantMax(range).ConstantValue() <= 0) {
+ return kNegative;
}
}
-
- min = Range::ConstantMinSmi(range);
- new_min = Range::ConstantMinSmi(new_range);
-
- return (min.ConstantValue() <= new_min.ConstantValue()) ?
- min : RangeBoundary::MinSmi();
+ return kUnknown;
}
-// Given the current range of a phi and a newly computed range check
-// if it is growing towards positive infinity, if it does widen it to
-// MaxSmi.
-static RangeBoundary WidenMax(const Range* range, const Range* new_range) {
- RangeBoundary max = range->max();
- RangeBoundary new_max = new_range->max();
- if (max.IsSymbol()) {
- if (max.UpperBound().OverflowedSmi()) {
- return RangeBoundary::MaxSmi();
- } else if (DependOnSameSymbol(max, new_max)) {
- return max.offset() >= new_max.offset() ? max : RangeBoundary::MaxSmi();
- } else if (max.SmiLowerBound() >= new_max.SmiUpperBound()) {
- return max;
- }
- }
+Range* RangeAnalysis::InferInductionVariableRange(JoinEntryInstr* loop_header,
+ PhiInstr* var) {
+ BitVector* loop_info = loop_header->loop_info();
- max = Range::ConstantMaxSmi(range);
- new_max = Range::ConstantMaxSmi(new_range);
+ Definition* initial_value = NULL;
+ Direction direction = kUnknown;
- return (max.ConstantValue() >= new_max.ConstantValue()) ?
- max : RangeBoundary::MaxSmi();
-}
+ ResetWorklist();
+ MarkDefinition(var);
+ while (!worklist_.is_empty()) {
+ Definition* defn = worklist_.RemoveLast();
+ if (defn->IsPhi()) {
+ PhiInstr* phi = defn->AsPhi();
+ for (intptr_t i = 0; i < phi->InputCount(); i++) {
+ Definition* defn = phi->InputAt(i)->definition();
-// Given the current range of a phi and a newly computed range check
-// if we can perform narrowing: use newly computed minimum to improve precision
-// of the computed range. We do it only if current minimum was widened and is
-// equal to MinSmi.
-// Newly computed minimum is expected to be greater of equal then old one as
-// we are running after widening phase.
-static RangeBoundary NarrowMin(const Range* range, const Range* new_range) {
-#ifdef DEBUG
- const RangeBoundary min = Range::ConstantMinSmi(range);
- const RangeBoundary new_min = Range::ConstantMinSmi(new_range);
- ASSERT(min.ConstantValue() <= new_min.ConstantValue());
-#endif
- // TODO(vegorov): consider using negative infinity to indicate widened bound.
- return range->min().IsSmiMinimumOrBelow() ? new_range->min() : range->min();
-}
+ if (!loop_info->Contains(defn->GetBlock()->preorder_number())) {
+ // The value is coming from outside of the loop.
+ if (initial_value == NULL) {
+ initial_value = defn;
+ continue;
+ } else if (initial_value == defn) {
+ continue;
+ } else {
+ return NULL;
+ }
+ }
+ MarkDefinition(defn);
+ }
+ } else if (defn->IsBinarySmiOp()) {
+ BinarySmiOpInstr* binary_op = defn->AsBinarySmiOp();
+
+ switch (binary_op->op_kind()) {
+ case Token::kADD: {
+ const Direction growth_right =
+ ToDirection(binary_op->right());
+ if (growth_right != kUnknown) {
+ UpdateDirection(&direction, growth_right);
+ MarkDefinition(binary_op->left()->definition());
+ break;
+ }
-// Given the current range of a phi and a newly computed range check
-// if we can perform narrowing: use newly computed maximum to improve precision
-// of the computed range. We do it only if current maximum was widened and is
-// equal to MaxSmi.
-// Newly computed minimum is expected to be greater of equal then old one as
-// we are running after widening phase.
-static RangeBoundary NarrowMax(const Range* range, const Range* new_range) {
-#ifdef DEBUG
- const RangeBoundary max = Range::ConstantMaxSmi(range);
- const RangeBoundary new_max = Range::ConstantMaxSmi(new_range);
- ASSERT(max.ConstantValue() >= new_max.ConstantValue());
-#endif
- // TODO(vegorov): consider using positive infinity to indicate widened bound.
- return range->max().IsSmiMaximumOrAbove() ? new_range->max() : range->max();
-}
+ const Direction growth_left =
+ ToDirection(binary_op->left());
+ if (growth_left != kUnknown) {
+ UpdateDirection(&direction, growth_left);
+ MarkDefinition(binary_op->right()->definition());
+ break;
+ }
+ return NULL;
+ }
-char RangeAnalysis::OpPrefix(JoinOperator op) {
- switch (op) {
- case WIDEN: return 'W';
- case NARROW: return 'N';
- case NONE: return 'I';
- }
- UNREACHABLE();
- return ' ';
-}
-
-
-bool RangeAnalysis::InferRange(JoinOperator op,
- Definition* defn,
- intptr_t iteration) {
- Range range;
- defn->InferRange(&range);
-
- if (!Range::IsUnknown(&range)) {
- if (!Range::IsUnknown(defn->range()) && defn->IsPhi()) {
- // TODO(vegorov): we are currently supporting only smi phis.
- ASSERT(defn->Type()->ToCid() == kSmiCid);
- if (op == WIDEN) {
- range = Range(WidenMin(defn->range(), &range),
- WidenMax(defn->range(), &range));
- } else if (op == NARROW) {
- range = Range(NarrowMin(defn->range(), &range),
- NarrowMax(defn->range(), &range));
- }
- }
+ case Token::kSUB: {
+ const Direction growth_right =
+ ToDirection(binary_op->right());
+ if (growth_right != kUnknown) {
+ UpdateDirection(&direction, Invert(growth_right));
+ MarkDefinition(binary_op->left()->definition());
+ break;
+ }
+ return NULL;
+ }
- if (!range.Equals(defn->range())) {
- if (FLAG_trace_range_analysis) {
- OS::Print("%c [%" Pd "] %s: %s => %s\n",
- OpPrefix(op),
- iteration,
- defn->ToCString(),
- Range::ToCString(defn->range()),
- Range::ToCString(&range));
+ default:
+ return NULL;
}
- defn->set_range(range);
- return true;
+ } else {
+ return NULL;
}
}
- return false;
-}
+ // We transitively discovered all dependencies of the given phi
+ // and confirmed that it depends on a single value coming from outside of
+ // the loop and some linear combinations of itself.
+ // Compute the range based on initial value and the direction of the growth.
+ switch (direction) {
+ case kPositive:
+ return new(I) Range(RangeBoundary::FromDefinition(initial_value),
+ RangeBoundary::MaxSmi());
-void RangeAnalysis::CollectDefinitions(BlockEntryInstr* block, BitVector* set) {
- for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator();
- !block_it.Done();
- block_it.Advance()) {
- BlockEntryInstr* block = block_it.Current();
+ case kNegative:
+ return new(I) Range(RangeBoundary::MinSmi(),
+ RangeBoundary::FromDefinition(initial_value));
- JoinEntryInstr* join = block->AsJoinEntry();
- if (join != NULL) {
- for (PhiIterator it(join); !it.Done(); it.Advance()) {
- PhiInstr* phi = it.Current();
- if (set->Contains(phi->ssa_temp_index())) {
- definitions_.Add(phi);
+ case kUnknown:
+ case kBoth:
+ return Range::UnknownSmi();
+ }
+
+ UNREACHABLE();
+ return NULL;
+}
+
+
+void RangeAnalysis::InferRangesRecursive(BlockEntryInstr* block) {
+ JoinEntryInstr* join = block->AsJoinEntry();
+ if (join != NULL) {
+ const bool is_loop_header = (join->loop_info() != NULL);
+ for (PhiIterator it(join); !it.Done(); it.Advance()) {
+ PhiInstr* phi = it.Current();
+ if (definitions_->Contains(phi->ssa_temp_index())) {
+ if (is_loop_header) {
+ // Try recognizing simple induction variables.
+ Range* range = InferInductionVariableRange(join, phi);
+ if (range != NULL) {
+ phi->range_ = range;
+ continue;
+ }
}
- }
- }
- for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
- Definition* defn = it.Current()->AsDefinition();
- if ((defn != NULL) &&
- (defn->ssa_temp_index() != -1) &&
- set->Contains(defn->ssa_temp_index())) {
- definitions_.Add(defn);
+ phi->InferRange();
}
}
}
-}
+ for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+ Instruction* current = it.Current();
-void RangeAnalysis::Iterate(JoinOperator op, intptr_t max_iterations) {
- // TODO(vegorov): switch to worklist if this becomes performance bottleneck.
- intptr_t iteration = 0;
- bool changed;
- do {
- changed = false;
- for (intptr_t i = 0; i < definitions_.length(); i++) {
- Definition* defn = definitions_[i];
- if (InferRange(op, defn, iteration)) {
- changed = true;
+ Definition* defn = current->AsDefinition();
+ if ((defn != NULL) &&
+ (defn->ssa_temp_index() != -1) &&
+ definitions_->Contains(defn->ssa_temp_index())) {
+ defn->InferRange();
+ } else if (FLAG_array_bounds_check_elimination &&
+ current->IsCheckArrayBound()) {
+ CheckArrayBoundInstr* check = current->AsCheckArrayBound();
+ RangeBoundary array_length =
+ RangeBoundary::FromDefinition(check->length()->definition());
+ if (check->IsRedundant(array_length)) {
+ it.RemoveCurrentFromGraph();
}
}
+ }
- iteration++;
- } while (changed && (iteration < max_iterations));
+ for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
+ InferRangesRecursive(block->dominated_blocks()[i]);
+ }
}
void RangeAnalysis::InferRanges() {
if (FLAG_trace_range_analysis) {
- FlowGraphPrinter::PrintGraph("Range Analysis (BEFORE)", flow_graph_);
+ OS::Print("---- before range analysis -------\n");
+ FlowGraphPrinter printer(*flow_graph_);
+ printer.PrintBlocks();
}
-
// Initialize bitvector for quick filtering of int values.
- BitVector* set = new(I) BitVector(flow_graph_->current_ssa_temp_index());
+ definitions_ =
+ new(I) BitVector(flow_graph_->current_ssa_temp_index());
for (intptr_t i = 0; i < values_.length(); i++) {
- set->Add(values_[i]->ssa_temp_index());
+ definitions_->Add(values_[i]->ssa_temp_index());
}
for (intptr_t i = 0; i < constraints_.length(); i++) {
- set->Add(constraints_[i]->ssa_temp_index());
+ definitions_->Add(constraints_[i]->ssa_temp_index());
}
- // Collect integer definitions (including constraints) in the reverse
- // postorder. This improves convergence speed compared to iterating
- // values_ and constraints_ array separately.
+ // Infer initial values of ranges.
const GrowableArray<Definition*>& initial =
*flow_graph_->graph_entry()->initial_definitions();
for (intptr_t i = 0; i < initial.length(); ++i) {
Definition* definition = initial[i];
- if (set->Contains(definition->ssa_temp_index())) {
- definitions_.Add(definition);
+ if (definitions_->Contains(definition->ssa_temp_index())) {
+ definition->InferRange();
}
}
- CollectDefinitions(flow_graph_->graph_entry(), set);
-
- // Perform an iteration of range inference just propagating ranges
- // through the graph as-is without applying widening or narrowing.
- // This helps to improve precision of initial bounds.
- Iterate(NONE, 1);
-
- // Perform fix-point iteration of range inference applying widening
- // operator to phis to ensure fast convergence.
- // Widening simply maps growing bounds to the respective range bound.
- Iterate(WIDEN, kMaxInt32);
-
- if (FLAG_trace_range_analysis) {
- FlowGraphPrinter::PrintGraph("Range Analysis (WIDEN)", flow_graph_);
- }
-
- // Perform fix-point iteration of range inference applying narrowing
- // to phis to compute more accurate range.
- // Narrowing only improves those boundaries that were widened up to
- // range boundary and leaves other boundaries intact.
- Iterate(NARROW, kMaxInt32);
+ InferRangesRecursive(flow_graph_->graph_entry());
if (FLAG_trace_range_analysis) {
- FlowGraphPrinter::PrintGraph("Range Analysis (AFTER)", flow_graph_);
- }
-}
-
-
-void RangeAnalysis::EliminateRedundantBoundsChecks() {
- if (FLAG_array_bounds_check_elimination) {
- for (intptr_t i = 0; i < bounds_checks_.length(); i++) {
- CheckArrayBoundInstr* check = bounds_checks_[i];
- RangeBoundary array_length =
- RangeBoundary::FromDefinition(check->length()->definition());
- if (check->IsRedundant(array_length)) {
- check->RemoveFromGraph();
- }
- }
- }
-}
-
-
-void RangeAnalysis::MarkUnreachableBlocks() {
- for (intptr_t i = 0; i < constraints_.length(); i++) {
- if (Range::IsUnknown(constraints_[i]->range())) {
- TargetEntryInstr* target = constraints_[i]->target();
- if (target == NULL) {
- // TODO(vegorov): replace Constraint with an uncoditional
- // deoptimization and kill all dominated dead code.
- continue;
- }
-
- BranchInstr* branch =
- target->PredecessorAt(0)->last_instruction()->AsBranch();
- if (target == branch->true_successor()) {
- // True unreachable.
- if (FLAG_trace_constant_propagation) {
- OS::Print("Range analysis: True unreachable (B%" Pd ")\n",
- branch->true_successor()->block_id());
- }
- branch->set_constant_target(branch->false_successor());
- } else {
- ASSERT(target == branch->false_successor());
- // False unreachable.
- if (FLAG_trace_constant_propagation) {
- OS::Print("Range analysis: False unreachable (B%" Pd ")\n",
- branch->false_successor()->block_id());
- }
- branch->set_constant_target(branch->true_successor());
- }
- }
+ OS::Print("---- after range analysis -------\n");
+ FlowGraphPrinter printer(*flow_graph_);
+ printer.PrintBlocks();
}
}
@@ -920,7 +807,7 @@ RangeBoundary RangeBoundary::LowerBound() const {
return NegativeInfinity();
}
if (IsConstant()) return *this;
- return Add(Range::ConstantMinSmi(symbol()->range()),
+ return Add(Range::ConstantMin(symbol()->range()),
RangeBoundary::FromConstant(offset_),
NegativeInfinity());
}
@@ -931,8 +818,7 @@ RangeBoundary RangeBoundary::UpperBound() const {
return PositiveInfinity();
}
if (IsConstant()) return *this;
-
- return Add(Range::ConstantMaxSmi(symbol()->range()),
+ return Add(Range::ConstantMax(symbol()->range()),
RangeBoundary::FromConstant(offset_),
PositiveInfinity());
}
@@ -1005,6 +891,33 @@ bool RangeBoundary::SymbolicSub(const RangeBoundary& a,
}
+static Definition* UnwrapConstraint(Definition* defn) {
+ while (defn->IsConstraint()) {
+ defn = defn->AsConstraint()->value()->definition();
+ }
+ return defn;
+}
+
+
+static bool AreEqualDefinitions(Definition* a, Definition* b) {
+ a = UnwrapConstraint(a);
+ b = UnwrapConstraint(b);
+ return (a == b) ||
+ (a->AllowsCSE() &&
+ a->Dependencies().IsNone() &&
+ b->AllowsCSE() &&
+ b->Dependencies().IsNone() &&
+ a->Equals(b));
+}
+
+
+// Returns true if two range boundaries refer to the same symbol.
+static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) {
+ return a.IsSymbol() && b.IsSymbol() &&
+ AreEqualDefinitions(a.symbol(), b.symbol());
+}
+
+
bool RangeBoundary::Equals(const RangeBoundary& other) const {
if (IsConstant() && other.IsConstant()) {
return ConstantValue() == other.ConstantValue();
@@ -1144,143 +1057,118 @@ static bool CanonicalizeMinBoundary(RangeBoundary* a) {
return true;
}
-typedef bool (*BoundaryOp)(RangeBoundary*);
-static bool CanonicalizeForComparison(RangeBoundary* a,
- RangeBoundary* b,
- BoundaryOp op,
- const RangeBoundary& overflow) {
- if (!a->IsSymbol() || !b->IsSymbol()) {
- return false;
+RangeBoundary RangeBoundary::Min(RangeBoundary a, RangeBoundary b,
+ RangeSize size) {
+ ASSERT(!(a.IsNegativeInfinity() || b.IsNegativeInfinity()));
+ ASSERT(!a.IsUnknown() || !b.IsUnknown());
+ if (a.IsUnknown() && !b.IsUnknown()) {
+ return b;
}
-
- if (DependOnSameSymbol(*a, *b)) {
- return true;
+ if (!a.IsUnknown() && b.IsUnknown()) {
+ return a;
}
-
-
- RangeBoundary canonical_a = CanonicalizeBoundary(*a, overflow);
- RangeBoundary canonical_b = CanonicalizeBoundary(*b, overflow);
-
- do {
- if (DependOnSameSymbol(canonical_a, canonical_b)) {
- *a = canonical_a;
- *b = canonical_b;
- return true;
+ if (size == kRangeBoundarySmi) {
+ if (a.IsSmiMaximumOrAbove() && !b.IsSmiMaximumOrAbove()) {
+ return b;
}
- } while (op(&canonical_a) || op(&canonical_b));
-
- return false;
-}
-
+ if (!a.IsSmiMaximumOrAbove() && b.IsSmiMaximumOrAbove()) {
+ return a;
+ }
+ } else {
+ ASSERT(size == kRangeBoundaryInt64);
+ if (a.IsMaximumOrAbove() && !b.IsMaximumOrAbove()) {
+ return b;
+ }
+ if (!a.IsMaximumOrAbove() && b.IsMaximumOrAbove()) {
+ return a;
+ }
+ }
-RangeBoundary RangeBoundary::JoinMin(RangeBoundary a, RangeBoundary b) {
if (a.Equals(b)) {
return b;
}
- if (CanonicalizeForComparison(&a,
- &b,
- &CanonicalizeMinBoundary,
- RangeBoundary::NegativeInfinity())) {
+ {
+ RangeBoundary canonical_a =
+ CanonicalizeBoundary(a, RangeBoundary::PositiveInfinity());
+ RangeBoundary canonical_b =
+ CanonicalizeBoundary(b, RangeBoundary::PositiveInfinity());
+ do {
+ if (DependOnSameSymbol(canonical_a, canonical_b)) {
+ a = canonical_a;
+ b = canonical_b;
+ break;
+ }
+ } while (CanonicalizeMaxBoundary(&canonical_a) ||
+ CanonicalizeMaxBoundary(&canonical_b));
+ }
+
+ if (DependOnSameSymbol(a, b)) {
return (a.offset() <= b.offset()) ? a : b;
}
- const int64_t inf_a = a.SmiLowerBound();
- const int64_t inf_b = b.SmiLowerBound();
- const int64_t sup_a = a.SmiUpperBound();
- const int64_t sup_b = b.SmiUpperBound();
+ const int64_t min_a = a.UpperBound().Clamp(size).ConstantValue();
+ const int64_t min_b = b.UpperBound().Clamp(size).ConstantValue();
- if ((sup_a <= inf_b) && !a.LowerBound().OverflowedSmi()) {
- return a;
- } else if ((sup_b <= inf_a) && !b.LowerBound().OverflowedSmi()) {
- return b;
- } else {
- return RangeBoundary::FromConstant(Utils::Minimum(inf_a, inf_b));
- }
+ return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_b));
}
-RangeBoundary RangeBoundary::JoinMax(RangeBoundary a, RangeBoundary b) {
- if (a.Equals(b)) {
+RangeBoundary RangeBoundary::Max(RangeBoundary a, RangeBoundary b,
+ RangeSize size) {
+ ASSERT(!(a.IsPositiveInfinity() || b.IsPositiveInfinity()));
+ ASSERT(!a.IsUnknown() || !b.IsUnknown());
+ if (a.IsUnknown() && !b.IsUnknown()) {
return b;
}
-
- if (CanonicalizeForComparison(&a,
- &b,
- &CanonicalizeMaxBoundary,
- RangeBoundary::PositiveInfinity())) {
- return (a.offset() >= b.offset()) ? a : b;
- }
-
- const int64_t inf_a = a.SmiLowerBound();
- const int64_t inf_b = b.SmiLowerBound();
- const int64_t sup_a = a.SmiUpperBound();
- const int64_t sup_b = b.SmiUpperBound();
-
- if ((sup_a <= inf_b) && !b.UpperBound().OverflowedSmi()) {
- return b;
- } else if ((sup_b <= inf_a) && !a.UpperBound().OverflowedSmi()) {
+ if (!a.IsUnknown() && b.IsUnknown()) {
return a;
+ }
+ if (size == kRangeBoundarySmi) {
+ if (a.IsSmiMinimumOrBelow() && !b.IsSmiMinimumOrBelow()) {
+ return b;
+ }
+ if (!a.IsSmiMinimumOrBelow() && b.IsSmiMinimumOrBelow()) {
+ return a;
+ }
} else {
- return RangeBoundary::FromConstant(Utils::Maximum(sup_a, sup_b));
+ ASSERT(size == kRangeBoundaryInt64);
+ if (a.IsMinimumOrBelow() && !b.IsMinimumOrBelow()) {
+ return b;
+ }
+ if (!a.IsMinimumOrBelow() && b.IsMinimumOrBelow()) {
+ return a;
+ }
}
-}
-
-
-RangeBoundary RangeBoundary::IntersectionMin(RangeBoundary a, RangeBoundary b) {
- ASSERT(!a.IsPositiveInfinity() && !b.IsPositiveInfinity());
- ASSERT(!a.IsUnknown() && !b.IsUnknown());
-
if (a.Equals(b)) {
- return a;
- }
-
- if (a.IsSmiMinimumOrBelow()) {
return b;
- } else if (b.IsSmiMinimumOrBelow()) {
- return a;
- }
-
- if (CanonicalizeForComparison(&a,
- &b,
- &CanonicalizeMinBoundary,
- RangeBoundary::NegativeInfinity())) {
- return (a.offset() >= b.offset()) ? a : b;
}
- const int64_t inf_a = a.SmiLowerBound();
- const int64_t inf_b = b.SmiLowerBound();
+ {
+ RangeBoundary canonical_a =
+ CanonicalizeBoundary(a, RangeBoundary::NegativeInfinity());
+ RangeBoundary canonical_b =
+ CanonicalizeBoundary(b, RangeBoundary::NegativeInfinity());
- return (inf_a >= inf_b) ? a : b;
-}
-
-
-RangeBoundary RangeBoundary::IntersectionMax(RangeBoundary a, RangeBoundary b) {
- ASSERT(!a.IsNegativeInfinity() && !b.IsNegativeInfinity());
- ASSERT(!a.IsUnknown() && !b.IsUnknown());
-
- if (a.Equals(b)) {
- return a;
- }
-
- if (a.IsSmiMaximumOrAbove()) {
- return b;
- } else if (b.IsSmiMaximumOrAbove()) {
- return a;
+ do {
+ if (DependOnSameSymbol(canonical_a, canonical_b)) {
+ a = canonical_a;
+ b = canonical_b;
+ break;
+ }
+ } while (CanonicalizeMinBoundary(&canonical_a) ||
+ CanonicalizeMinBoundary(&canonical_b));
}
- if (CanonicalizeForComparison(&a,
- &b,
- &CanonicalizeMaxBoundary,
- RangeBoundary::PositiveInfinity())) {
- return (a.offset() <= b.offset()) ? a : b;
+ if (DependOnSameSymbol(a, b)) {
+ return (a.offset() <= b.offset()) ? b : a;
}
- const int64_t sup_a = a.SmiUpperBound();
- const int64_t sup_b = b.SmiUpperBound();
+ const int64_t max_a = a.LowerBound().Clamp(size).ConstantValue();
+ const int64_t max_b = b.LowerBound().Clamp(size).ConstantValue();
- return (sup_a <= sup_b) ? a : b;
+ return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
}
@@ -1465,7 +1353,7 @@ static bool IsArrayLength(Definition* defn) {
if (defn == NULL) {
return false;
}
- LoadFieldInstr* load = UnwrapConstraint(defn)->AsLoadField();
+ LoadFieldInstr* load = defn->AsLoadField();
return (load != NULL) && load->IsImmutableLengthLoad();
}
@@ -1557,15 +1445,6 @@ bool Range::Mul(const Range* left_range,
return true;
}
}
-
- // TODO(vegorov): handle mixed sign case that leads to (-Infinity, 0] range.
- if (OnlyPositiveOrZero(*left_range, *right_range) ||
- OnlyNegativeOrZero(*left_range, *right_range)) {
- *result_min = RangeBoundary::FromConstant(0);
- *result_max = RangeBoundary::PositiveInfinity();
- return true;
- }
-
return false;
}
@@ -1593,11 +1472,10 @@ int64_t Range::ConstantAbsMax(const Range* range) {
}
-void Range::BinaryOp(const Token::Kind op,
- const Range* left_range,
- const Range* right_range,
- Definition* left_defn,
- Range* result) {
+Range* Range::BinaryOp(const Token::Kind op,
+ const Range* left_range,
+ const Range* right_range,
+ Definition* left_defn) {
ASSERT(left_range != NULL);
ASSERT(right_range != NULL);
@@ -1618,8 +1496,7 @@ void Range::BinaryOp(const Token::Kind op,
break;
case Token::kMUL: {
if (!Range::Mul(left_range, right_range, &min, &max)) {
- *result = Range::Full(RangeBoundary::kRangeBoundaryInt64);
- return;
+ return NULL;
}
break;
}
@@ -1633,34 +1510,29 @@ void Range::BinaryOp(const Token::Kind op,
}
case Token::kBIT_AND:
if (!Range::And(left_range, right_range, &min, &max)) {
- *result = Range::Full(RangeBoundary::kRangeBoundaryInt64);
- return;
+ return NULL;
}
break;
default:
- *result = Range::Full(RangeBoundary::kRangeBoundaryInt64);
- return;
+ return NULL;
+ break;
}
ASSERT(!min.IsUnknown() && !max.IsUnknown());
- *result = Range(min, max);
+ return new Range(min, max);
}
-void Definition::set_range(const Range& range) {
- if (range_ == NULL) {
- range_ = new Range();
- }
- *range_ = range;
-}
-
-
-void Definition::InferRange(Range* range) {
+void Definition::InferRange() {
if (Type()->ToCid() == kSmiCid) {
- *range = Range::Full(RangeBoundary::kRangeBoundarySmi);
+ if (range_ == NULL) {
+ range_ = Range::UnknownSmi();
+ }
} else if (IsMintDefinition()) {
- *range = Range::Full(RangeBoundary::kRangeBoundaryInt64);
+ if (range_ == NULL) {
+ range_ = Range::Unknown();
+ }
} else {
// Only Smi and Mint supported.
UNREACHABLE();
@@ -1668,112 +1540,59 @@ void Definition::InferRange(Range* range) {
}
-static bool DependsOnSymbol(const RangeBoundary& a, Definition* symbol) {
- return a.IsSymbol() && (UnwrapConstraint(a.symbol()) == symbol);
-}
+void PhiInstr::InferRange() {
+ RangeBoundary new_min;
+ RangeBoundary new_max;
+ ASSERT(Type()->ToCid() == kSmiCid);
-// Given the range and definition update the range so that
-// it covers both original range and defintions range.
-//
-// The following should also hold:
-//
-// [_|_, _|_] U a = a U [_|_, _|_] = a
-//
-static void Join(Range* range, Definition* defn) {
- if (Range::IsUnknown(defn->range())) {
- return;
- }
-
- if (Range::IsUnknown(range)) {
- *range = *defn->range();
- return;
- }
-
- Range other = *defn->range();
-
- // Handle patterns where range already depends on defn as a symbol:
- //
- // (..., S+o] U range(S) and [S+o, ...) U range(S)
- //
- // To improve precision of the computed join use [S, S] instead of
- // using range(S). It will be canonicalized away by JoinMin/JoinMax
- // functions.
- Definition* unwrapped = UnwrapConstraint(defn);
- if (DependsOnSymbol(range->min(), unwrapped) ||
- DependsOnSymbol(range->max(), unwrapped)) {
- other = Range(RangeBoundary::FromDefinition(defn, 0),
- RangeBoundary::FromDefinition(defn, 0));
- }
-
- // First try to compare ranges based on their upper and lower bounds.
- const int64_t inf_range = range->min().SmiLowerBound();
- const int64_t inf_other = other.min().SmiLowerBound();
- const int64_t sup_range = range->max().SmiUpperBound();
- const int64_t sup_other = other.max().SmiUpperBound();
-
- if (sup_range <= inf_other) {
- // The range is fully below defn's range. Keep the minimum and
- // expand the maximum.
- range->set_max(other.max());
- } else if (sup_other <= inf_range) {
- // The range is fully above defn's range. Keep the maximum and
- // expand the minimum.
- range->set_min(other.min());
- } else {
- // Can't compare ranges as whole. Join minimum and maximum separately.
- *range = Range(RangeBoundary::JoinMin(range->min(), other.min()),
- RangeBoundary::JoinMax(range->max(), other.max()));
- }
-}
-
+ for (intptr_t i = 0; i < InputCount(); i++) {
+ Range* input_range = InputAt(i)->definition()->range();
+ if (input_range == NULL) {
+ range_ = Range::UnknownSmi();
+ return;
+ }
-// When assigning range to a phi we must take care to avoid self-reference
-// cycles when phi's range depends on the phi itself.
-// To prevent such cases we impose additional restriction on symbols that
-// can be used as boundaries for phi's range: they must dominate
-// phi's definition.
-static RangeBoundary EnsureAcyclicSymbol(BlockEntryInstr* phi_block,
- const RangeBoundary& a,
- const RangeBoundary& limit) {
- if (!a.IsSymbol() || a.symbol()->GetBlock()->Dominates(phi_block)) {
- return a;
- }
+ if (new_min.IsUnknown()) {
+ new_min = Range::ConstantMin(input_range);
+ } else {
+ new_min = RangeBoundary::Min(new_min,
+ Range::ConstantMinSmi(input_range),
+ RangeBoundary::kRangeBoundarySmi);
+ }
- // Symbol does not dominate phi. Try unwrapping constraint and check again.
- Definition* unwrapped = UnwrapConstraint(a.symbol());
- if ((unwrapped != a.symbol()) &&
- unwrapped->GetBlock()->Dominates(phi_block)) {
- return RangeBoundary::FromDefinition(unwrapped, a.offset());
+ if (new_max.IsUnknown()) {
+ new_max = Range::ConstantMax(input_range);
+ } else {
+ new_max = RangeBoundary::Max(new_max,
+ Range::ConstantMaxSmi(input_range),
+ RangeBoundary::kRangeBoundarySmi);
+ }
}
- return limit;
-}
-
-
-void PhiInstr::InferRange(Range* range) {
- ASSERT(Type()->ToCid() == kSmiCid);
- for (intptr_t i = 0; i < InputCount(); i++) {
- Join(range, InputAt(i)->definition());
+ ASSERT(new_min.IsUnknown() == new_max.IsUnknown());
+ if (new_min.IsUnknown()) {
+ range_ = Range::UnknownSmi();
+ return;
}
- BlockEntryInstr* phi_block = GetBlock();
- range->set_min(EnsureAcyclicSymbol(
- phi_block, range->min(), RangeBoundary::MinSmi()));
- range->set_max(EnsureAcyclicSymbol(
- phi_block, range->max(), RangeBoundary::MaxSmi()));
+ range_ = new Range(new_min, new_max);
}
-void ConstantInstr::InferRange(Range* range) {
+void ConstantInstr::InferRange() {
if (value_.IsSmi()) {
- int64_t value = Smi::Cast(value_).Value();
- *range = Range(RangeBoundary::FromConstant(value),
- RangeBoundary::FromConstant(value));
+ if (range_ == NULL) {
+ int64_t value = Smi::Cast(value_).Value();
+ range_ = new Range(RangeBoundary::FromConstant(value),
+ RangeBoundary::FromConstant(value));
+ }
} else if (value_.IsMint()) {
- int64_t value = Mint::Cast(value_).value();
- *range = Range(RangeBoundary::FromConstant(value),
- RangeBoundary::FromConstant(value));
+ if (range_ == NULL) {
+ int64_t value = Mint::Cast(value_).value();
+ range_ = new Range(RangeBoundary::FromConstant(value),
+ RangeBoundary::FromConstant(value));
+ }
} else {
// Only Smi and Mint supported.
UNREACHABLE();
@@ -1781,114 +1600,160 @@ void ConstantInstr::InferRange(Range* range) {
}
-void ConstraintInstr::InferRange(Range* range) {
+void UnboxIntegerInstr::InferRange() {
+ if (range_ == NULL) {
+ Definition* unboxed = value()->definition();
+ ASSERT(unboxed != NULL);
+ Range* range = unboxed->range();
+ if (range == NULL) {
+ range_ = Range::Unknown();
+ return;
+ }
+ range_ = new Range(range->min(), range->max());
+ }
+}
+
+
+void ConstraintInstr::InferRange() {
+ Range* value_range = value()->definition()->range();
+
// Only constraining smi values.
ASSERT(value()->IsSmiValue());
- Range* value_range = value()->definition()->range();
- if (Range::IsUnknown(value_range)) {
- return;
- }
+ RangeBoundary min;
+ RangeBoundary max;
- // TODO(vegorov) check if precision of the analysis can be improved by
- // recognizing intersections of the form:
- //
- // (..., S+x] ^ [S+x, ...) = [S+x, S+x]
- //
- Range result = value_range->Intersect(constraint());
- if (result.IsUnsatisfiable()) {
- return;
+ {
+ RangeBoundary value_min = (value_range == NULL) ?
+ RangeBoundary() : value_range->min();
+ RangeBoundary constraint_min = constraint()->min();
+ min = RangeBoundary::Max(value_min, constraint_min,
+ RangeBoundary::kRangeBoundarySmi);
}
- *range = result;
-}
+ ASSERT(!min.IsUnknown());
+ {
+ RangeBoundary value_max = (value_range == NULL) ?
+ RangeBoundary() : value_range->max();
+ RangeBoundary constraint_max = constraint()->max();
+ max = RangeBoundary::Min(value_max, constraint_max,
+ RangeBoundary::kRangeBoundarySmi);
+ }
-void LoadFieldInstr::InferRange(Range* range) {
- switch (recognized_kind()) {
- case MethodRecognizer::kObjectArrayLength:
- case MethodRecognizer::kImmutableArrayLength:
- *range = Range(RangeBoundary::FromConstant(0),
- RangeBoundary::FromConstant(Array::kMaxElements));
- break;
+ ASSERT(!max.IsUnknown());
- case MethodRecognizer::kTypedDataLength:
- *range = Range(RangeBoundary::FromConstant(0), RangeBoundary::MaxSmi());
- break;
+ range_ = new Range(min, max);
- case MethodRecognizer::kStringBaseLength:
- *range = Range(RangeBoundary::FromConstant(0),
- RangeBoundary::FromConstant(String::kMaxElements));
- break;
+ // Mark branches that generate unsatisfiable constraints as constant.
+ if (target() != NULL && range_->IsUnsatisfiable()) {
+ BranchInstr* branch =
+ target()->PredecessorAt(0)->last_instruction()->AsBranch();
+ if (target() == branch->true_successor()) {
+ // True unreachable.
+ if (FLAG_trace_constant_propagation) {
+ OS::Print("Range analysis: True unreachable (B%" Pd ")\n",
+ branch->true_successor()->block_id());
+ }
+ branch->set_constant_target(branch->false_successor());
+ } else {
+ ASSERT(target() == branch->false_successor());
+ // False unreachable.
+ if (FLAG_trace_constant_propagation) {
+ OS::Print("Range analysis: False unreachable (B%" Pd ")\n",
+ branch->false_successor()->block_id());
+ }
+ branch->set_constant_target(branch->true_successor());
+ }
+ }
+}
- default:
- Definition::InferRange(range);
+
+void LoadFieldInstr::InferRange() {
+ if ((range_ == NULL) &&
+ ((recognized_kind() == MethodRecognizer::kObjectArrayLength) ||
+ (recognized_kind() == MethodRecognizer::kImmutableArrayLength))) {
+ range_ = new Range(RangeBoundary::FromConstant(0),
+ RangeBoundary::FromConstant(Array::kMaxElements));
+ return;
+ }
+ if ((range_ == NULL) &&
+ (recognized_kind() == MethodRecognizer::kTypedDataLength)) {
+ range_ = new Range(RangeBoundary::FromConstant(0), RangeBoundary::MaxSmi());
+ return;
+ }
+ if ((range_ == NULL) &&
+ (recognized_kind() == MethodRecognizer::kStringBaseLength)) {
+ range_ = new Range(RangeBoundary::FromConstant(0),
+ RangeBoundary::FromConstant(String::kMaxElements));
+ return;
}
+ Definition::InferRange();
}
-void LoadIndexedInstr::InferRange(Range* range) {
+void LoadIndexedInstr::InferRange() {
switch (class_id()) {
case kTypedDataInt8ArrayCid:
- *range = Range(RangeBoundary::FromConstant(-128),
- RangeBoundary::FromConstant(127));
+ range_ = new Range(RangeBoundary::FromConstant(-128),
+ RangeBoundary::FromConstant(127));
break;
case kTypedDataUint8ArrayCid:
case kTypedDataUint8ClampedArrayCid:
case kExternalTypedDataUint8ArrayCid:
case kExternalTypedDataUint8ClampedArrayCid:
- *range = Range(RangeBoundary::FromConstant(0),
- RangeBoundary::FromConstant(255));
+ range_ = new Range(RangeBoundary::FromConstant(0),
+ RangeBoundary::FromConstant(255));
break;
case kTypedDataInt16ArrayCid:
- *range = Range(RangeBoundary::FromConstant(-32768),
- RangeBoundary::FromConstant(32767));
+ range_ = new Range(RangeBoundary::FromConstant(-32768),
+ RangeBoundary::FromConstant(32767));
break;
case kTypedDataUint16ArrayCid:
- *range = Range(RangeBoundary::FromConstant(0),
- RangeBoundary::FromConstant(65535));
+ range_ = new Range(RangeBoundary::FromConstant(0),
+ RangeBoundary::FromConstant(65535));
break;
case kTypedDataInt32ArrayCid:
if (Typed32BitIsSmi()) {
- *range = Range::Full(RangeBoundary::kRangeBoundarySmi);
+ range_ = Range::UnknownSmi();
} else {
- *range = Range(RangeBoundary::FromConstant(kMinInt32),
- RangeBoundary::FromConstant(kMaxInt32));
+ range_ = new Range(RangeBoundary::FromConstant(kMinInt32),
+ RangeBoundary::FromConstant(kMaxInt32));
}
break;
case kTypedDataUint32ArrayCid:
if (Typed32BitIsSmi()) {
- *range = Range::Full(RangeBoundary::kRangeBoundarySmi);
+ range_ = Range::UnknownSmi();
} else {
- *range = Range(RangeBoundary::FromConstant(0),
- RangeBoundary::FromConstant(kMaxUint32));
+ range_ = new Range(RangeBoundary::FromConstant(0),
+ RangeBoundary::FromConstant(kMaxUint32));
}
break;
case kOneByteStringCid:
- *range = Range(RangeBoundary::FromConstant(0),
- RangeBoundary::FromConstant(0xFF));
+ range_ = new Range(RangeBoundary::FromConstant(0),
+ RangeBoundary::FromConstant(0xFF));
break;
case kTwoByteStringCid:
- *range = Range(RangeBoundary::FromConstant(0),
- RangeBoundary::FromConstant(0xFFFF));
+ range_ = new Range(RangeBoundary::FromConstant(0),
+ RangeBoundary::FromConstant(0xFFFF));
break;
default:
- Definition::InferRange(range);
+ Definition::InferRange();
break;
}
}
-void IfThenElseInstr::InferRange(Range* range) {
+void IfThenElseInstr::InferRange() {
const intptr_t min = Utils::Minimum(if_true_, if_false_);
const intptr_t max = Utils::Maximum(if_true_, if_false_);
- *range = Range(RangeBoundary::FromConstant(min),
- RangeBoundary::FromConstant(max));
+ range_ = new Range(RangeBoundary::FromConstant(min),
+ RangeBoundary::FromConstant(max));
}
-void BinarySmiOpInstr::InferRange(Range* range) {
+void BinarySmiOpInstr::InferRange() {
// TODO(vegorov): canonicalize BinarySmiOp to always have constant on the
// right and a non-constant on the left.
Definition* left_defn = left()->definition();
@@ -1896,28 +1761,41 @@ void BinarySmiOpInstr::InferRange(Range* range) {
Range* left_range = left_defn->range();
Range* right_range = right()->definition()->range();
- if (Range::IsUnknown(left_range) || Range::IsUnknown(right_range)) {
+ if ((left_range == NULL) || (right_range == NULL)) {
+ range_ = Range::UnknownSmi();
+ return;
+ }
+
+ Range* possible_range = Range::BinaryOp(op_kind(),
+ left_range,
+ right_range,
+ left_defn);
+
+ if ((range_ == NULL) && (possible_range == NULL)) {
+ // Initialize.
+ range_ = Range::UnknownSmi();
return;
}
- Range::BinaryOp(op_kind(),
- left_range,
- right_range,
- left_defn,
- range);
- ASSERT(!Range::IsUnknown(range));
+ if (possible_range == NULL) {
+ // Nothing new.
+ return;
+ }
+
+ range_ = possible_range;
+ ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
// Calculate overflowed status before clamping.
- const bool overflowed = range->min().LowerBound().OverflowedSmi() ||
- range->max().UpperBound().OverflowedSmi();
+ const bool overflowed = range_->min().LowerBound().OverflowedSmi() ||
+ range_->max().UpperBound().OverflowedSmi();
set_overflow(overflowed);
// Clamp value to be within smi range.
- range->Clamp(RangeBoundary::kRangeBoundarySmi);
+ range_->Clamp(RangeBoundary::kRangeBoundarySmi);
}
-void BinaryMintOpInstr::InferRange(Range* range) {
+void BinaryMintOpInstr::InferRange() {
// TODO(vegorov): canonicalize BinaryMintOpInstr to always have constant on
// the right and a non-constant on the left.
Definition* left_defn = left()->definition();
@@ -1925,73 +1803,90 @@ void BinaryMintOpInstr::InferRange(Range* range) {
Range* left_range = left_defn->range();
Range* right_range = right()->definition()->range();
- if (Range::IsUnknown(left_range) || Range::IsUnknown(right_range)) {
+ if ((left_range == NULL) || (right_range == NULL)) {
+ range_ = Range::Unknown();
return;
}
- Range::BinaryOp(op_kind(),
- left_range,
- right_range,
- left_defn,
- range);
- ASSERT(!Range::IsUnknown(range));
+ Range* possible_range = Range::BinaryOp(op_kind(),
+ left_range,
+ right_range,
+ left_defn);
+
+ if ((range_ == NULL) && (possible_range == NULL)) {
+ // Initialize.
+ range_ = Range::Unknown();
+ return;
+ }
+
+ if (possible_range == NULL) {
+ // Nothing new.
+ return;
+ }
+
+ range_ = possible_range;
+
+ ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
// Calculate overflowed status before clamping.
- const bool overflowed = range->min().LowerBound().OverflowedMint() ||
- range->max().UpperBound().OverflowedMint();
+ const bool overflowed = range_->min().LowerBound().OverflowedMint() ||
+ range_->max().UpperBound().OverflowedMint();
set_can_overflow(overflowed);
// Clamp value to be within mint range.
- range->Clamp(RangeBoundary::kRangeBoundaryInt64);
+ range_->Clamp(RangeBoundary::kRangeBoundaryInt64);
}
-void ShiftMintOpInstr::InferRange(Range* range) {
+void ShiftMintOpInstr::InferRange() {
Definition* left_defn = left()->definition();
Range* left_range = left_defn->range();
Range* right_range = right()->definition()->range();
- if (Range::IsUnknown(left_range) || Range::IsUnknown(right_range)) {
+ if ((left_range == NULL) || (right_range == NULL)) {
+ range_ = Range::Unknown();
return;
}
- Range::BinaryOp(op_kind(),
- left_range,
- right_range,
- left_defn,
- range);
- ASSERT(!Range::IsUnknown(range));
+ Range* possible_range = Range::BinaryOp(op_kind(),
+ left_range,
+ right_range,
+ left_defn);
+
+ if ((range_ == NULL) && (possible_range == NULL)) {
+ // Initialize.
+ range_ = Range::Unknown();
+ return;
+ }
+
+ if (possible_range == NULL) {
+ // Nothing new.
+ return;
+ }
+
+ range_ = possible_range;
+
+ ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
// Calculate overflowed status before clamping.
- const bool overflowed = range->min().LowerBound().OverflowedMint() ||
- range->max().UpperBound().OverflowedMint();
+ const bool overflowed = range_->min().LowerBound().OverflowedMint() ||
+ range_->max().UpperBound().OverflowedMint();
set_can_overflow(overflowed);
// Clamp value to be within mint range.
- range->Clamp(RangeBoundary::kRangeBoundaryInt64);
+ range_->Clamp(RangeBoundary::kRangeBoundaryInt64);
}
-void BoxIntegerInstr::InferRange(Range* range) {
+void BoxIntegerInstr::InferRange() {
Range* input_range = value()->definition()->range();
if (input_range != NULL) {
bool is_smi = !input_range->min().LowerBound().OverflowedSmi() &&
!input_range->max().UpperBound().OverflowedSmi();
set_is_smi(is_smi);
// The output range is the same as the input range.
- *range = *input_range;
- }
-}
-
-
-void UnboxIntegerInstr::InferRange(Range* range) {
- Range* value_range = value()->definition()->range();
- if (value_range != NULL) {
- *range = *value_range;
- } else if (!value()->definition()->IsMintDefinition() &&
- (value()->Type()->ToCid() != kSmiCid)) {
- *range = Range::Full(RangeBoundary::kRangeBoundaryInt64);
+ range_ = input_range;
}
}
« no previous file with comments | « runtime/vm/flow_graph_range_analysis.h ('k') | runtime/vm/flow_graph_range_analysis_test.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698