Index: runtime/vm/intermediate_language.cc |
diff --git a/runtime/vm/intermediate_language.cc b/runtime/vm/intermediate_language.cc |
index c564930ec7955da7bc676bedeb586feb5e91b0ff..118e6522785e4646c971aa157781351c378535af 100644 |
--- a/runtime/vm/intermediate_language.cc |
+++ b/runtime/vm/intermediate_language.cc |
@@ -12,6 +12,7 @@ |
#include "vm/flow_graph_builder.h" |
#include "vm/flow_graph_compiler.h" |
#include "vm/flow_graph_optimizer.h" |
+#include "vm/flow_graph_range_analysis.h" |
#include "vm/locations.h" |
#include "vm/object.h" |
#include "vm/object_store.h" |
@@ -2582,579 +2583,6 @@ void Environment::DeepCopyToOuter(Isolate* isolate, Instruction* instr) const { |
} |
-RangeBoundary RangeBoundary::FromDefinition(Definition* defn, int64_t offs) { |
- if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) { |
- return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value() + offs); |
- } |
- return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs); |
-} |
- |
- |
-RangeBoundary RangeBoundary::LowerBound() const { |
- if (IsInfinity()) { |
- return NegativeInfinity(); |
- } |
- if (IsConstant()) return *this; |
- return Add(Range::ConstantMin(symbol()->range()), |
- RangeBoundary::FromConstant(offset_), |
- NegativeInfinity()); |
-} |
- |
- |
-RangeBoundary RangeBoundary::UpperBound() const { |
- if (IsInfinity()) { |
- return PositiveInfinity(); |
- } |
- if (IsConstant()) return *this; |
- return Add(Range::ConstantMax(symbol()->range()), |
- RangeBoundary::FromConstant(offset_), |
- PositiveInfinity()); |
-} |
- |
- |
-RangeBoundary RangeBoundary::Add(const RangeBoundary& a, |
- const RangeBoundary& b, |
- const RangeBoundary& overflow) { |
- if (a.IsInfinity() || b.IsInfinity()) return overflow; |
- |
- ASSERT(a.IsConstant() && b.IsConstant()); |
- if (Utils::WillAddOverflow(a.ConstantValue(), b.ConstantValue())) { |
- return overflow; |
- } |
- |
- int64_t result = a.ConstantValue() + b.ConstantValue(); |
- |
- return RangeBoundary::FromConstant(result); |
-} |
- |
- |
-RangeBoundary RangeBoundary::Sub(const RangeBoundary& a, |
- const RangeBoundary& b, |
- const RangeBoundary& overflow) { |
- if (a.IsInfinity() || b.IsInfinity()) return overflow; |
- ASSERT(a.IsConstant() && b.IsConstant()); |
- if (Utils::WillSubOverflow(a.ConstantValue(), b.ConstantValue())) { |
- return overflow; |
- } |
- |
- int64_t result = a.ConstantValue() - b.ConstantValue(); |
- |
- return RangeBoundary::FromConstant(result); |
-} |
- |
- |
-bool RangeBoundary::SymbolicAdd(const RangeBoundary& a, |
- const RangeBoundary& b, |
- RangeBoundary* result) { |
- if (a.IsSymbol() && b.IsConstant()) { |
- if (Utils::WillAddOverflow(a.offset(), b.ConstantValue())) { |
- return false; |
- } |
- |
- const int64_t offset = a.offset() + b.ConstantValue(); |
- |
- *result = RangeBoundary::FromDefinition(a.symbol(), offset); |
- return true; |
- } else if (b.IsSymbol() && a.IsConstant()) { |
- return SymbolicAdd(b, a, result); |
- } |
- return false; |
-} |
- |
- |
-bool RangeBoundary::SymbolicSub(const RangeBoundary& a, |
- const RangeBoundary& b, |
- RangeBoundary* result) { |
- if (a.IsSymbol() && b.IsConstant()) { |
- if (Utils::WillSubOverflow(a.offset(), b.ConstantValue())) { |
- return false; |
- } |
- |
- const int64_t offset = a.offset() - b.ConstantValue(); |
- |
- *result = RangeBoundary::FromDefinition(a.symbol(), offset); |
- return true; |
- } |
- return false; |
-} |
- |
- |
-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(); |
- } else if (IsInfinity() && other.IsInfinity()) { |
- return kind() == other.kind(); |
- } else if (IsSymbol() && other.IsSymbol()) { |
- return (offset() == other.offset()) && DependOnSameSymbol(*this, other); |
- } else if (IsUnknown() && other.IsUnknown()) { |
- return true; |
- } |
- return false; |
-} |
- |
- |
-RangeBoundary RangeBoundary::Shl(const RangeBoundary& value_boundary, |
- int64_t shift_count, |
- const RangeBoundary& overflow) { |
- ASSERT(value_boundary.IsConstant()); |
- ASSERT(shift_count >= 0); |
- int64_t limit = 64 - shift_count; |
- int64_t value = value_boundary.ConstantValue(); |
- |
- if ((value == 0) || |
- (shift_count == 0) || |
- ((limit > 0) && Utils::IsInt(static_cast<int>(limit), value))) { |
- // Result stays in 64 bit range. |
- int64_t result = value << shift_count; |
- return RangeBoundary(result); |
- } |
- |
- return overflow; |
-} |
- |
- |
-static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a, |
- const RangeBoundary& overflow) { |
- if (a.IsConstant() || a.IsInfinity()) { |
- return a; |
- } |
- |
- int64_t offset = a.offset(); |
- Definition* symbol = a.symbol(); |
- |
- bool changed; |
- do { |
- changed = false; |
- if (symbol->IsConstraint()) { |
- symbol = symbol->AsConstraint()->value()->definition(); |
- changed = true; |
- } else if (symbol->IsBinarySmiOp()) { |
- BinarySmiOpInstr* op = symbol->AsBinarySmiOp(); |
- Definition* left = op->left()->definition(); |
- Definition* right = op->right()->definition(); |
- switch (op->op_kind()) { |
- case Token::kADD: |
- if (right->IsConstant()) { |
- int64_t rhs = Smi::Cast(right->AsConstant()->value()).Value(); |
- if (Utils::WillAddOverflow(offset, rhs)) { |
- return overflow; |
- } |
- offset += rhs; |
- symbol = left; |
- changed = true; |
- } else if (left->IsConstant()) { |
- int64_t rhs = Smi::Cast(left->AsConstant()->value()).Value(); |
- if (Utils::WillAddOverflow(offset, rhs)) { |
- return overflow; |
- } |
- offset += rhs; |
- symbol = right; |
- changed = true; |
- } |
- break; |
- |
- case Token::kSUB: |
- if (right->IsConstant()) { |
- int64_t rhs = Smi::Cast(right->AsConstant()->value()).Value(); |
- if (Utils::WillSubOverflow(offset, rhs)) { |
- return overflow; |
- } |
- offset -= rhs; |
- symbol = left; |
- changed = true; |
- } |
- break; |
- |
- default: |
- break; |
- } |
- } |
- } while (changed); |
- |
- return RangeBoundary::FromDefinition(symbol, offset); |
-} |
- |
- |
-static bool CanonicalizeMaxBoundary(RangeBoundary* a) { |
- if (!a->IsSymbol()) return false; |
- |
- Range* range = a->symbol()->range(); |
- if ((range == NULL) || !range->max().IsSymbol()) return false; |
- |
- |
- if (Utils::WillAddOverflow(range->max().offset(), a->offset())) { |
- *a = RangeBoundary::PositiveInfinity(); |
- return true; |
- } |
- |
- const int64_t offset = range->max().offset() + a->offset(); |
- |
- |
- *a = CanonicalizeBoundary( |
- RangeBoundary::FromDefinition(range->max().symbol(), offset), |
- RangeBoundary::PositiveInfinity()); |
- |
- return true; |
-} |
- |
- |
-static bool CanonicalizeMinBoundary(RangeBoundary* a) { |
- if (!a->IsSymbol()) return false; |
- |
- Range* range = a->symbol()->range(); |
- if ((range == NULL) || !range->min().IsSymbol()) return false; |
- |
- if (Utils::WillAddOverflow(range->min().offset(), a->offset())) { |
- *a = RangeBoundary::NegativeInfinity(); |
- return true; |
- } |
- |
- const int64_t offset = range->min().offset() + a->offset(); |
- |
- *a = CanonicalizeBoundary( |
- RangeBoundary::FromDefinition(range->min().symbol(), offset), |
- RangeBoundary::NegativeInfinity()); |
- |
- return true; |
-} |
- |
- |
-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 (!a.IsUnknown() && b.IsUnknown()) { |
- return a; |
- } |
- if (size == kRangeBoundarySmi) { |
- if (a.IsSmiMaximumOrAbove() && !b.IsSmiMaximumOrAbove()) { |
- return b; |
- } |
- 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; |
- } |
- } |
- |
- if (a.Equals(b)) { |
- return b; |
- } |
- |
- { |
- 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 min_a = a.UpperBound().Clamp(size).ConstantValue(); |
- const int64_t min_b = b.UpperBound().Clamp(size).ConstantValue(); |
- |
- return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_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 (!a.IsUnknown() && b.IsUnknown()) { |
- return a; |
- } |
- if (size == kRangeBoundarySmi) { |
- if (a.IsSmiMinimumOrBelow() && !b.IsSmiMinimumOrBelow()) { |
- return b; |
- } |
- if (!a.IsSmiMinimumOrBelow() && b.IsSmiMinimumOrBelow()) { |
- return a; |
- } |
- } else { |
- ASSERT(size == kRangeBoundaryInt64); |
- if (a.IsMinimumOrBelow() && !b.IsMinimumOrBelow()) { |
- return b; |
- } |
- if (!a.IsMinimumOrBelow() && b.IsMinimumOrBelow()) { |
- return a; |
- } |
- } |
- if (a.Equals(b)) { |
- return b; |
- } |
- |
- { |
- RangeBoundary canonical_a = |
- CanonicalizeBoundary(a, RangeBoundary::NegativeInfinity()); |
- RangeBoundary canonical_b = |
- CanonicalizeBoundary(b, RangeBoundary::NegativeInfinity()); |
- |
- do { |
- if (DependOnSameSymbol(canonical_a, canonical_b)) { |
- a = canonical_a; |
- b = canonical_b; |
- break; |
- } |
- } while (CanonicalizeMinBoundary(&canonical_a) || |
- CanonicalizeMinBoundary(&canonical_b)); |
- } |
- |
- if (DependOnSameSymbol(a, b)) { |
- return (a.offset() <= b.offset()) ? b : a; |
- } |
- |
- const int64_t max_a = a.LowerBound().Clamp(size).ConstantValue(); |
- const int64_t max_b = b.LowerBound().Clamp(size).ConstantValue(); |
- |
- return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b)); |
-} |
- |
- |
-int64_t RangeBoundary::ConstantValue() const { |
- ASSERT(IsConstant()); |
- return value_; |
-} |
- |
- |
-void Definition::InferRange() { |
- if (Type()->ToCid() == kSmiCid) { |
- if (range_ == NULL) { |
- range_ = Range::UnknownSmi(); |
- } |
- } else if (IsMintDefinition()) { |
- if (range_ == NULL) { |
- range_ = Range::Unknown(); |
- } |
- } else { |
- // Only Smi and Mint supported. |
- UNREACHABLE(); |
- } |
-} |
- |
- |
-void ConstantInstr::InferRange() { |
- if (value_.IsSmi()) { |
- if (range_ == NULL) { |
- int64_t value = Smi::Cast(value_).Value(); |
- range_ = new Range(RangeBoundary::FromConstant(value), |
- RangeBoundary::FromConstant(value)); |
- } |
- } else if (value_.IsMint()) { |
- 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(); |
- } |
-} |
- |
- |
-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()); |
- |
- RangeBoundary min; |
- RangeBoundary max; |
- |
- { |
- RangeBoundary value_min = (value_range == NULL) ? |
- RangeBoundary() : value_range->min(); |
- RangeBoundary constraint_min = constraint()->min(); |
- min = RangeBoundary::Max(value_min, constraint_min, |
- RangeBoundary::kRangeBoundarySmi); |
- } |
- |
- 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); |
- } |
- |
- ASSERT(!max.IsUnknown()); |
- |
- range_ = new Range(min, max); |
- |
- // 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()); |
- } |
- } |
-} |
- |
- |
-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() { |
- switch (class_id()) { |
- case kTypedDataInt8ArrayCid: |
- range_ = new Range(RangeBoundary::FromConstant(-128), |
- RangeBoundary::FromConstant(127)); |
- break; |
- case kTypedDataUint8ArrayCid: |
- case kTypedDataUint8ClampedArrayCid: |
- case kExternalTypedDataUint8ArrayCid: |
- case kExternalTypedDataUint8ClampedArrayCid: |
- range_ = new Range(RangeBoundary::FromConstant(0), |
- RangeBoundary::FromConstant(255)); |
- break; |
- case kTypedDataInt16ArrayCid: |
- range_ = new Range(RangeBoundary::FromConstant(-32768), |
- RangeBoundary::FromConstant(32767)); |
- break; |
- case kTypedDataUint16ArrayCid: |
- range_ = new Range(RangeBoundary::FromConstant(0), |
- RangeBoundary::FromConstant(65535)); |
- break; |
- case kTypedDataInt32ArrayCid: |
- if (Typed32BitIsSmi()) { |
- range_ = Range::UnknownSmi(); |
- } else { |
- range_ = new Range(RangeBoundary::FromConstant(kMinInt32), |
- RangeBoundary::FromConstant(kMaxInt32)); |
- } |
- break; |
- case kTypedDataUint32ArrayCid: |
- if (Typed32BitIsSmi()) { |
- range_ = Range::UnknownSmi(); |
- } else { |
- range_ = new Range(RangeBoundary::FromConstant(0), |
- RangeBoundary::FromConstant(kMaxUint32)); |
- } |
- break; |
- case kOneByteStringCid: |
- range_ = new Range(RangeBoundary::FromConstant(0), |
- RangeBoundary::FromConstant(0xFF)); |
- break; |
- case kTwoByteStringCid: |
- range_ = new Range(RangeBoundary::FromConstant(0), |
- RangeBoundary::FromConstant(0xFFFF)); |
- break; |
- default: |
- Definition::InferRange(); |
- break; |
- } |
-} |
- |
- |
-void IfThenElseInstr::InferRange() { |
- const intptr_t min = Utils::Minimum(if_true_, if_false_); |
- const intptr_t max = Utils::Maximum(if_true_, if_false_); |
- range_ = new Range(RangeBoundary::FromConstant(min), |
- RangeBoundary::FromConstant(max)); |
-} |
- |
- |
static bool BindsToSmiConstant(Value* value) { |
return value->BindsToConstant() && value->BoundConstant().IsSmi(); |
} |
@@ -3246,46 +2674,6 @@ bool IfThenElseInstr::Supports(ComparisonInstr* comparison, |
} |
-void PhiInstr::InferRange() { |
- RangeBoundary new_min; |
- RangeBoundary new_max; |
- |
- ASSERT(Type()->ToCid() == kSmiCid); |
- |
- for (intptr_t i = 0; i < InputCount(); i++) { |
- Range* input_range = InputAt(i)->definition()->range(); |
- if (input_range == NULL) { |
- range_ = Range::UnknownSmi(); |
- return; |
- } |
- |
- if (new_min.IsUnknown()) { |
- new_min = Range::ConstantMin(input_range); |
- } else { |
- new_min = RangeBoundary::Min(new_min, |
- Range::ConstantMinSmi(input_range), |
- RangeBoundary::kRangeBoundarySmi); |
- } |
- |
- if (new_max.IsUnknown()) { |
- new_max = Range::ConstantMax(input_range); |
- } else { |
- new_max = RangeBoundary::Max(new_max, |
- Range::ConstantMaxSmi(input_range), |
- RangeBoundary::kRangeBoundarySmi); |
- } |
- } |
- |
- ASSERT(new_min.IsUnknown() == new_max.IsUnknown()); |
- if (new_min.IsUnknown()) { |
- range_ = Range::UnknownSmi(); |
- return; |
- } |
- |
- range_ = new Range(new_min, new_max); |
-} |
- |
- |
bool PhiInstr::IsRedundant() const { |
ASSERT(InputCount() > 1); |
Definition* first = InputAt(0)->definition(); |
@@ -3297,543 +2685,11 @@ bool PhiInstr::IsRedundant() const { |
} |
-static bool IsArrayLength(Definition* defn) { |
- if (defn == NULL) { |
- return false; |
- } |
- LoadFieldInstr* load = defn->AsLoadField(); |
- return (load != NULL) && load->IsImmutableLengthLoad(); |
-} |
- |
- |
-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(); |
- |
- Range* left_range = left_defn->range(); |
- Range* right_range = right()->definition()->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; |
- } |
- |
- 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(); |
- set_overflow(overflowed); |
- |
- // Clamp value to be within smi range. |
- range_->Clamp(RangeBoundary::kRangeBoundarySmi); |
-} |
- |
- |
-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(); |
- |
- Range* left_range = left_defn->range(); |
- Range* right_range = right()->definition()->range(); |
- |
- if ((left_range == NULL) || (right_range == NULL)) { |
- range_ = Range::Unknown(); |
- return; |
- } |
- |
- 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(); |
- set_can_overflow(overflowed); |
- |
- // Clamp value to be within mint range. |
- range_->Clamp(RangeBoundary::kRangeBoundaryInt64); |
-} |
- |
- |
-void ShiftMintOpInstr::InferRange() { |
- Definition* left_defn = left()->definition(); |
- |
- Range* left_range = left_defn->range(); |
- Range* right_range = right()->definition()->range(); |
- |
- if ((left_range == NULL) || (right_range == NULL)) { |
- range_ = Range::Unknown(); |
- return; |
- } |
- |
- 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(); |
- set_can_overflow(overflowed); |
- |
- // Clamp value to be within mint range. |
- range_->Clamp(RangeBoundary::kRangeBoundaryInt64); |
-} |
- |
- |
-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; |
- } |
-} |
- |
- |
-bool Range::IsPositive() const { |
- if (min().IsNegativeInfinity()) { |
- return false; |
- } |
- if (min().LowerBound().ConstantValue() < 0) { |
- return false; |
- } |
- if (max().IsPositiveInfinity()) { |
- return true; |
- } |
- return max().UpperBound().ConstantValue() >= 0; |
-} |
- |
- |
-bool Range::OnlyLessThanOrEqualTo(int64_t val) const { |
- if (max().IsPositiveInfinity()) { |
- // Cannot be true. |
- return false; |
- } |
- if (max().UpperBound().ConstantValue() > val) { |
- // Not true. |
- return false; |
- } |
- return true; |
-} |
- |
- |
-bool Range::OnlyGreaterThanOrEqualTo(int64_t val) const { |
- if (min().IsNegativeInfinity()) { |
- return false; |
- } |
- if (min().LowerBound().ConstantValue() < val) { |
- return false; |
- } |
- return true; |
-} |
- |
- |
-// Inclusive. |
-bool Range::IsWithin(int64_t min_int, int64_t max_int) const { |
- RangeBoundary lower_min = min().LowerBound(); |
- if (lower_min.IsNegativeInfinity() || (lower_min.ConstantValue() < min_int)) { |
- return false; |
- } |
- RangeBoundary upper_max = max().UpperBound(); |
- if (upper_max.IsPositiveInfinity() || (upper_max.ConstantValue() > max_int)) { |
- return false; |
- } |
- return true; |
-} |
- |
- |
-bool Range::Overlaps(int64_t min_int, int64_t max_int) const { |
- RangeBoundary lower = min().LowerBound(); |
- RangeBoundary upper = max().UpperBound(); |
- const int64_t this_min = lower.IsNegativeInfinity() ? |
- RangeBoundary::kMin : lower.ConstantValue(); |
- const int64_t this_max = upper.IsPositiveInfinity() ? |
- RangeBoundary::kMax : upper.ConstantValue(); |
- if ((this_min <= min_int) && (min_int <= this_max)) return true; |
- if ((this_min <= max_int) && (max_int <= this_max)) return true; |
- if ((min_int < this_min) && (max_int > this_max)) return true; |
- return false; |
-} |
- |
- |
-bool Range::IsUnsatisfiable() const { |
- // Infinity case: [+inf, ...] || [..., -inf] |
- if (min().IsPositiveInfinity() || max().IsNegativeInfinity()) { |
- return true; |
- } |
- // Constant case: For example [0, -1]. |
- if (Range::ConstantMin(this).ConstantValue() > |
- Range::ConstantMax(this).ConstantValue()) { |
- return true; |
- } |
- // Symbol case: For example [v+1, v]. |
- if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) { |
- return true; |
- } |
- return false; |
-} |
- |
- |
-void Range::Clamp(RangeBoundary::RangeSize size) { |
- min_ = min_.Clamp(size); |
- max_ = max_.Clamp(size); |
-} |
- |
- |
-void Range::Shl(const Range* left, |
- const Range* right, |
- RangeBoundary* result_min, |
- RangeBoundary* result_max) { |
- ASSERT(left != NULL); |
- ASSERT(right != NULL); |
- ASSERT(result_min != NULL); |
- ASSERT(result_max != NULL); |
- RangeBoundary left_max = Range::ConstantMax(left); |
- RangeBoundary left_min = Range::ConstantMin(left); |
- // A negative shift count always deoptimizes (and throws), so the minimum |
- // shift count is zero. |
- int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(), |
- static_cast<int64_t>(0)); |
- int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(), |
- static_cast<int64_t>(0)); |
- |
- *result_min = RangeBoundary::Shl( |
- left_min, |
- left_min.ConstantValue() > 0 ? right_min : right_max, |
- left_min.ConstantValue() > 0 |
- ? RangeBoundary::PositiveInfinity() |
- : RangeBoundary::NegativeInfinity()); |
- |
- *result_max = RangeBoundary::Shl( |
- left_max, |
- left_max.ConstantValue() > 0 ? right_max : right_min, |
- left_max.ConstantValue() > 0 |
- ? RangeBoundary::PositiveInfinity() |
- : RangeBoundary::NegativeInfinity()); |
-} |
- |
- |
-void Range::Shr(const Range* left, |
- const Range* right, |
- RangeBoundary* result_min, |
- RangeBoundary* result_max) { |
- RangeBoundary left_max = Range::ConstantMax(left); |
- RangeBoundary left_min = Range::ConstantMin(left); |
- // A negative shift count always deoptimizes (and throws), so the minimum |
- // shift count is zero. |
- int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(), |
- static_cast<int64_t>(0)); |
- int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(), |
- static_cast<int64_t>(0)); |
- |
- *result_min = RangeBoundary::Shr( |
- left_min, |
- left_min.ConstantValue() > 0 ? right_max : right_min); |
- |
- *result_max = RangeBoundary::Shr( |
- left_max, |
- left_max.ConstantValue() > 0 ? right_min : right_max); |
-} |
- |
- |
-bool Range::And(const Range* left_range, |
- const Range* right_range, |
- RangeBoundary* result_min, |
- RangeBoundary* result_max) { |
- ASSERT(left_range != NULL); |
- ASSERT(right_range != NULL); |
- ASSERT(result_min != NULL); |
- ASSERT(result_max != NULL); |
- |
- if (Range::ConstantMin(right_range).ConstantValue() >= 0) { |
- *result_min = RangeBoundary::FromConstant(0); |
- *result_max = Range::ConstantMax(right_range); |
- return true; |
- } |
- |
- if (Range::ConstantMin(left_range).ConstantValue() >= 0) { |
- *result_min = RangeBoundary::FromConstant(0); |
- *result_max = Range::ConstantMax(left_range); |
- return true; |
- } |
- |
- return false; |
-} |
- |
- |
-void Range::Add(const Range* left_range, |
- const Range* right_range, |
- RangeBoundary* result_min, |
- RangeBoundary* result_max, |
- Definition* left_defn) { |
- ASSERT(left_range != NULL); |
- ASSERT(right_range != NULL); |
- ASSERT(result_min != NULL); |
- ASSERT(result_max != NULL); |
- |
- RangeBoundary left_min = |
- IsArrayLength(left_defn) ? |
- RangeBoundary::FromDefinition(left_defn) : left_range->min(); |
- |
- RangeBoundary left_max = |
- IsArrayLength(left_defn) ? |
- RangeBoundary::FromDefinition(left_defn) : left_range->max(); |
- |
- if (!RangeBoundary::SymbolicAdd(left_min, right_range->min(), result_min)) { |
- *result_min = RangeBoundary::Add(left_range->min().LowerBound(), |
- right_range->min().LowerBound(), |
- RangeBoundary::NegativeInfinity()); |
- } |
- if (!RangeBoundary::SymbolicAdd(left_max, right_range->max(), result_max)) { |
- *result_max = RangeBoundary::Add(right_range->max().UpperBound(), |
- left_range->max().UpperBound(), |
- RangeBoundary::PositiveInfinity()); |
- } |
-} |
- |
- |
-void Range::Sub(const Range* left_range, |
- const Range* right_range, |
- RangeBoundary* result_min, |
- RangeBoundary* result_max, |
- Definition* left_defn) { |
- ASSERT(left_range != NULL); |
- ASSERT(right_range != NULL); |
- ASSERT(result_min != NULL); |
- ASSERT(result_max != NULL); |
- |
- RangeBoundary left_min = |
- IsArrayLength(left_defn) ? |
- RangeBoundary::FromDefinition(left_defn) : left_range->min(); |
- |
- RangeBoundary left_max = |
- IsArrayLength(left_defn) ? |
- RangeBoundary::FromDefinition(left_defn) : left_range->max(); |
- |
- if (!RangeBoundary::SymbolicSub(left_min, right_range->max(), result_min)) { |
- *result_min = RangeBoundary::Sub(left_range->min().LowerBound(), |
- right_range->max().UpperBound(), |
- RangeBoundary::NegativeInfinity()); |
- } |
- if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), result_max)) { |
- *result_max = RangeBoundary::Sub(left_range->max().UpperBound(), |
- right_range->min().LowerBound(), |
- RangeBoundary::PositiveInfinity()); |
- } |
-} |
- |
- |
-bool Range::Mul(const Range* left_range, |
- const Range* right_range, |
- RangeBoundary* result_min, |
- RangeBoundary* result_max) { |
- ASSERT(left_range != NULL); |
- ASSERT(right_range != NULL); |
- ASSERT(result_min != NULL); |
- ASSERT(result_max != NULL); |
- |
- const int64_t left_max = ConstantAbsMax(left_range); |
- const int64_t right_max = ConstantAbsMax(right_range); |
- if ((left_max <= -kSmiMin) && (right_max <= -kSmiMin) && |
- ((left_max == 0) || (right_max <= kMaxInt64 / left_max))) { |
- // Product of left and right max values stays in 64 bit range. |
- const int64_t mul_max = left_max * right_max; |
- if (Smi::IsValid(mul_max) && Smi::IsValid(-mul_max)) { |
- const int64_t r_min = |
- OnlyPositiveOrZero(*left_range, *right_range) ? 0 : -mul_max; |
- *result_min = RangeBoundary::FromConstant(r_min); |
- const int64_t r_max = |
- OnlyNegativeOrZero(*left_range, *right_range) ? 0 : mul_max; |
- *result_max = RangeBoundary::FromConstant(r_max); |
- return true; |
- } |
- } |
- return false; |
-} |
- |
- |
-// Both the a and b ranges are >= 0. |
-bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) { |
- return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0); |
-} |
- |
- |
-// Both the a and b ranges are <= 0. |
-bool Range::OnlyNegativeOrZero(const Range& a, const Range& b) { |
- return a.OnlyLessThanOrEqualTo(0) && b.OnlyLessThanOrEqualTo(0); |
-} |
- |
- |
-// Return the maximum absolute value included in range. |
-int64_t Range::ConstantAbsMax(const Range* range) { |
- if (range == NULL) { |
- return RangeBoundary::kMax; |
- } |
- const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); |
- const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); |
- return Utils::Maximum(abs_min, abs_max); |
-} |
- |
- |
-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); |
- |
- // Both left and right ranges are finite. |
- ASSERT(left_range->IsFinite()); |
- ASSERT(right_range->IsFinite()); |
- |
- RangeBoundary min; |
- RangeBoundary max; |
- ASSERT(min.IsUnknown() && max.IsUnknown()); |
- |
- switch (op) { |
- case Token::kADD: |
- Range::Add(left_range, right_range, &min, &max, left_defn); |
- break; |
- case Token::kSUB: |
- Range::Sub(left_range, right_range, &min, &max, left_defn); |
- break; |
- case Token::kMUL: { |
- if (!Range::Mul(left_range, right_range, &min, &max)) { |
- return NULL; |
- } |
- break; |
- } |
- case Token::kSHL: { |
- Range::Shl(left_range, right_range, &min, &max); |
- break; |
- } |
- case Token::kSHR: { |
- Range::Shr(left_range, right_range, &min, &max); |
- break; |
- } |
- case Token::kBIT_AND: |
- if (!Range::And(left_range, right_range, &min, &max)) { |
- return NULL; |
- } |
- break; |
- default: |
- return NULL; |
- break; |
- } |
- |
- ASSERT(!min.IsUnknown() && !max.IsUnknown()); |
- |
- return new Range(min, max); |
-} |
- |
- |
bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) { |
return LoadFieldInstr::IsFixedLengthArrayCid(cid); |
} |
-bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) { |
- Range* index_range = index()->definition()->range(); |
- |
- // Range of the index is unknown can't decide if the check is redundant. |
- if (index_range == NULL) { |
- return false; |
- } |
- |
- // Range of the index is not positive. Check can't be redundant. |
- if (Range::ConstantMinSmi(index_range).ConstantValue() < 0) { |
- return false; |
- } |
- |
- RangeBoundary max = CanonicalizeBoundary(index_range->max(), |
- RangeBoundary::PositiveInfinity()); |
- |
- if (max.OverflowedSmi()) { |
- return false; |
- } |
- |
- |
- RangeBoundary max_upper = max.UpperBound(); |
- RangeBoundary length_lower = length.LowerBound(); |
- |
- if (max_upper.OverflowedSmi() || length_lower.OverflowedSmi()) { |
- return false; |
- } |
- |
- // Try to compare constant boundaries. |
- if (max_upper.ConstantValue() < length_lower.ConstantValue()) { |
- return true; |
- } |
- |
- length = CanonicalizeBoundary(length, RangeBoundary::PositiveInfinity()); |
- if (length.OverflowedSmi()) { |
- return false; |
- } |
- |
- // Try symbolic comparison. |
- do { |
- if (DependOnSameSymbol(max, length)) return max.offset() < length.offset(); |
- } while (CanonicalizeMaxBoundary(&max) || CanonicalizeMinBoundary(&length)); |
- |
- // Failed to prove that maximum is bounded with array length. |
- return false; |
-} |
- |
- |
Instruction* CheckArrayBoundInstr::Canonicalize(FlowGraph* flow_graph) { |
return IsRedundant(RangeBoundary::FromDefinition(length()->definition())) ? |
NULL : this; |