Revision: 24848
Author: [email protected]
Date: Thu Oct 23 14:40:43 2014 UTC
Log: [turbofan] Use range types to type and lower arithmetic ops.
This is based on Georg's work on typing arithmetic operations
(https://codereview.chromium.org/658743002/).
Instead of weakening to bitset types, we weaken to the closest 2^n
limit if we see that we are re-typing a node with a range type (which
means that the node can be part of a cycle, so we might need
to speed up the fixpoint there).
BUG=
[email protected]
Review URL: https://codereview.chromium.org/636283009
https://code.google.com/p/v8/source/detail?r=24848
Modified:
/branches/bleeding_edge/src/compiler/representation-change.h
/branches/bleeding_edge/src/compiler/simplified-lowering.cc
/branches/bleeding_edge/src/compiler/typer.cc
/branches/bleeding_edge/src/compiler/typer.h
/branches/bleeding_edge/src/types.h
/branches/bleeding_edge/test/cctest/compiler/test-simplified-lowering.cc
/branches/bleeding_edge/test/cctest/compiler/test-typer.cc
/branches/bleeding_edge/test/cctest/test-types.cc
/branches/bleeding_edge/test/cctest/types-fuzz.h
=======================================
--- /branches/bleeding_edge/src/compiler/representation-change.h Wed Oct 8
11:16:45 2014 UTC
+++ /branches/bleeding_edge/src/compiler/representation-change.h Thu Oct 23
14:40:43 2014 UTC
@@ -215,6 +215,37 @@
return jsgraph()->Int32Constant(iv);
}
}
+
+ Node* GetTruncatedWord32For(Node* node, MachineTypeUnion output_type) {
+ // Eagerly fold truncations for constants.
+ switch (node->opcode()) {
+ case IrOpcode::kInt32Constant:
+ return node; // No change necessary.
+ case IrOpcode::kFloat32Constant:
+ return jsgraph()->Int32Constant(
+ DoubleToInt32(OpParameter<float>(node)));
+ case IrOpcode::kNumberConstant:
+ case IrOpcode::kFloat64Constant:
+ return jsgraph()->Int32Constant(
+ DoubleToInt32(OpParameter<double>(node)));
+ default:
+ break;
+ }
+ // Select the correct X -> Word32 truncation operator.
+ const Operator* op = NULL;
+ if (output_type & kRepFloat64) {
+ op = machine()->TruncateFloat64ToInt32();
+ } else if (output_type & kRepFloat32) {
+ node = InsertChangeFloat32ToFloat64(node);
+ op = machine()->TruncateFloat64ToInt32();
+ } else if (output_type & kRepTagged) {
+ node = InsertChangeTaggedToFloat64(node);
+ op = machine()->TruncateFloat64ToInt32();
+ } else {
+ return TypeError(node, output_type, kRepWord32);
+ }
+ return jsgraph()->graph()->NewNode(op, node);
+ }
Node* GetWord32RepresentationFor(Node* node, MachineTypeUnion
output_type,
bool use_unsigned) {
@@ -420,6 +451,11 @@
return jsgraph()->graph()->NewNode(machine()->ChangeFloat32ToFloat64(),
node);
}
+
+ Node* InsertChangeTaggedToFloat64(Node* node) {
+ return
jsgraph()->graph()->NewNode(simplified()->ChangeTaggedToFloat64(),
+ node);
+ }
JSGraph* jsgraph() { return jsgraph_; }
Isolate* isolate() { return isolate_; }
=======================================
--- /branches/bleeding_edge/src/compiler/simplified-lowering.cc Thu Oct 23
10:22:06 2014 UTC
+++ /branches/bleeding_edge/src/compiler/simplified-lowering.cc Thu Oct 23
14:40:43 2014 UTC
@@ -74,6 +74,10 @@
changer_(changer),
queue_(zone) {
memset(info_, 0, sizeof(NodeInfo) * count_);
+
+ Factory* f = zone->isolate()->factory();
+ safe_int_additive_range_ =
+ Type::Range(f->NewNumber(-pow(2, 52)), f->NewNumber(pow(2, 52)),
zone);
}
void Run(SimplifiedLowering* lowering) {
@@ -166,6 +170,30 @@
return NodeProperties::GetBounds(node->InputAt(0)).upper->Is(type) &&
NodeProperties::GetBounds(node->InputAt(1)).upper->Is(type);
}
+
+ void ProcessTruncateWord32Input(Node* node, int index, MachineTypeUnion
use) {
+ Node* input = node->InputAt(index);
+ if (phase_ == PROPAGATE) {
+ // In the propagate phase, propagate the usage information backward.
+ Enqueue(input, use);
+ } else {
+ // In the change phase, insert a change before the use if necessary.
+ MachineTypeUnion output = GetInfo(input)->output;
+ if ((output & kRepWord32) == 0) {
+ // Output representation doesn't match usage.
+ TRACE((" truncate-to-int32: #%d:%s(@%d #%d:%s) ", node->id(),
+ node->op()->mnemonic(), index, input->id(),
+ input->op()->mnemonic()));
+ TRACE((" from "));
+ PrintInfo(output);
+ TRACE((" to "));
+ PrintInfo(use);
+ TRACE(("\n"));
+ Node* n = changer_->GetTruncatedWord32For(input, output);
+ node->ReplaceInput(index, n);
+ }
+ }
+ }
void ProcessInput(Node* node, int index, MachineTypeUnion use) {
Node* input = node->InputAt(index);
@@ -370,10 +398,31 @@
bool CanLowerToInt32Binop(Node* node, MachineTypeUnion use) {
return BothInputsAre(node, Type::Signed32())
&& !CanObserveNonInt32(use);
}
+
+ bool IsSafeIntAdditiveOperand(Node* node) {
+ Type* type = NodeProperties::GetBounds(node).upper;
+ // TODO(jarin): Unfortunately, bitset types are not subtypes of larger
+ // range types, so we have to explicitly check for Integral32 here
+ // (in addition to the safe integer range). Once we fix subtyping for
+ // ranges, we should simplify this.
+ return type->Is(safe_int_additive_range_) ||
type->Is(Type::Integral32());
+ }
+
+ bool CanLowerToInt32AdditiveBinop(Node* node, MachineTypeUnion use) {
+ return IsSafeIntAdditiveOperand(node->InputAt(0)) &&
+ IsSafeIntAdditiveOperand(node->InputAt(1)) &&
+ !CanObserveNonInt32(use);
+ }
bool CanLowerToUint32Binop(Node* node, MachineTypeUnion use) {
return BothInputsAre(node, Type::Unsigned32())
&& !CanObserveNonUint32(use);
}
+
+ bool CanLowerToUint32AdditiveBinop(Node* node, MachineTypeUnion use) {
+ return IsSafeIntAdditiveOperand(node->InputAt(0)) &&
+ IsSafeIntAdditiveOperand(node->InputAt(1)) &&
+ !CanObserveNonUint32(use);
+ }
bool CanObserveNonInt32(MachineTypeUnion use) {
return (use & (kTypeUint32 | kTypeNumber | kTypeAny)) != 0;
@@ -515,11 +564,23 @@
if (CanLowerToInt32Binop(node, use)) {
// => signed Int32Add/Sub
VisitInt32Binop(node);
+ if (lower()) node->set_op(Int32Op(node));
+ } else if (CanLowerToInt32AdditiveBinop(node, use)) {
+ // => signed Int32Add/Sub, truncating inputs
+ ProcessTruncateWord32Input(node, 0, kTypeInt32);
+ ProcessTruncateWord32Input(node, 1, kTypeInt32);
+ SetOutput(node, kMachInt32);
if (lower()) node->set_op(Int32Op(node));
} else if (CanLowerToUint32Binop(node, use)) {
// => unsigned Int32Add/Sub
VisitUint32Binop(node);
if (lower()) node->set_op(Uint32Op(node));
+ } else if (CanLowerToUint32AdditiveBinop(node, use)) {
+ // => signed Int32Add/Sub, truncating inputs
+ ProcessTruncateWord32Input(node, 0, kTypeUint32);
+ ProcessTruncateWord32Input(node, 1, kTypeUint32);
+ SetOutput(node, kMachUint32);
+ if (lower()) node->set_op(Uint32Op(node));
} else {
// => Float64Add/Sub
VisitFloat64Binop(node);
@@ -915,6 +976,7 @@
Phase phase_; // current phase of algorithm
RepresentationChanger* changer_; // for inserting representation changes
ZoneQueue<Node*> queue_; // queue for traversing the graph
+ Type* safe_int_additive_range_;
NodeInfo* GetInfo(Node* node) {
DCHECK(node->id() >= 0);
=======================================
--- /branches/bleeding_edge/src/compiler/typer.cc Thu Oct 23 10:22:06 2014
UTC
+++ /branches/bleeding_edge/src/compiler/typer.cc Thu Oct 23 14:40:43 2014
UTC
@@ -26,14 +26,18 @@
Typer::Typer(Graph* graph, MaybeHandle<Context> context)
- : graph_(graph), context_(context), decorator_(NULL) {
+ : graph_(graph),
+ context_(context),
+ decorator_(NULL),
+ weaken_min_limits_(graph->zone()),
+ weaken_max_limits_(graph->zone()) {
Zone* zone = this->zone();
Factory* f = zone->isolate()->factory();
Handle<Object> zero = f->NewNumber(0);
Handle<Object> one = f->NewNumber(1);
- Handle<Object> positive_infinity = f->NewNumber(+V8_INFINITY);
- Handle<Object> negative_infinity = f->NewNumber(-V8_INFINITY);
+ Handle<Object> infinity = f->NewNumber(+V8_INFINITY);
+ Handle<Object> minusinfinity = f->NewNumber(-V8_INFINITY);
negative_signed32 = Type::Union(
Type::SignedSmall(), Type::OtherSigned32(), zone);
@@ -49,7 +53,9 @@
singleton_zero, Type::Union(Type::NaN(), Type::MinusZero(), zone),
zone);
falsish = Type::Union(Type::Undetectable(),
Type::Union(zeroish, undefined_or_null, zone), zone);
- integer = Type::Range(negative_infinity, positive_infinity, zone);
+ integer = Type::Range(minusinfinity, infinity, zone);
+ weakint = Type::Union(
+ integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
Type* number = Type::Number();
Type* signed32 = Type::Signed32();
@@ -57,8 +63,6 @@
Type* integral32 = Type::Integral32();
Type* object = Type::Object();
Type* undefined = Type::Undefined();
- Type* weakint = Type::Union(
- integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
number_fun0_ = Type::Function(number, zone);
number_fun1_ = Type::Function(number, number, zone);
@@ -112,6 +116,20 @@
uint32_array_fun_ = Type::Function(uint32_array, arg1, arg2, arg3, zone);
float32_array_fun_ = Type::Function(float32_array, arg1, arg2, arg3,
zone);
float64_array_fun_ = Type::Function(float64_array, arg1, arg2, arg3,
zone);
+
+ const int limits_count = 20;
+
+ weaken_min_limits_.reserve(limits_count + 1);
+ weaken_max_limits_.reserve(limits_count + 1);
+
+ double limit = 1 << 30;
+ weaken_min_limits_.push_back(f->NewNumber(0));
+ weaken_max_limits_.push_back(f->NewNumber(0));
+ for (int i = 0; i < limits_count; i++) {
+ weaken_min_limits_.push_back(f->NewNumber(-limit));
+ weaken_max_limits_.push_back(f->NewNumber(limit - 1));
+ limit *= 2;
+ }
decorator_ = new (zone) Decorator(this);
graph_->AddDecorator(decorator_);
@@ -165,8 +183,8 @@
#undef DECLARE_METHOD
Bounds BoundsOrNone(Node* node) {
- return NodeProperties::IsTyped(node)
- ? NodeProperties::GetBounds(node) : Bounds(Type::None(zone()));
+ return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node)
+ : Bounds(Type::None());
}
Bounds Operand(Node* node, int i) {
@@ -181,6 +199,8 @@
// back-propagate the constraint that it has to be a subtype of
Internal.
return result;
}
+
+ Type* Weaken(Type* current_type, Type* previous_type);
Zone* zone() { return typer_->zone(); }
Isolate* isolate() { return typer_->isolate(); }
@@ -199,6 +219,7 @@
static Type* Invert(Type*, Typer*);
static Type* FalsifyUndefined(Type*, Typer*);
+ static Type* Rangify(Type*, Typer*);
static Type* ToPrimitive(Type*, Typer*);
static Type* ToBoolean(Type*, Typer*);
@@ -252,12 +273,12 @@
GenericGraphVisit::Control Pre(Node* node) {
if (OperatorProperties::HasValueOutput(node->op())) {
Bounds previous = NodeProperties::GetBounds(node);
- Bounds bounds = TypeNode(node);
- NodeProperties::SetBounds(node, Bounds::Both(bounds, previous,
zone()));
- DCHECK(bounds.Narrows(previous));
+ Bounds current = TypeNode(node);
+ NodeProperties::SetBounds(node, Bounds::Both(current, previous,
zone()));
+ DCHECK(current.Narrows(previous));
// Stop when nothing changed (but allow re-entry in case it does
later).
- return previous.Narrows(bounds)
- ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER;
+ return previous.Narrows(current) ? GenericGraphVisit::DEFER
+ : GenericGraphVisit::REENTER;
} else {
return GenericGraphVisit::SKIP;
}
@@ -276,13 +297,20 @@
GenericGraphVisit::Control Pre(Node* node) {
if (OperatorProperties::HasValueOutput(node->op())) {
Bounds previous = BoundsOrNone(node);
- Bounds bounds = TypeNode(node);
- DCHECK(previous.lower->Is(bounds.lower));
- DCHECK(previous.upper->Is(bounds.upper));
- NodeProperties::SetBounds(node, bounds);
+ Bounds current = TypeNode(node);
+
+ // Speed up termination in the presence of range types:
+ current.upper = Weaken(current.upper, previous.upper);
+ current.lower = Weaken(current.lower, previous.lower);
+
+ DCHECK(previous.lower->Is(current.lower));
+ DCHECK(previous.upper->Is(current.upper));
+
+ NodeProperties::SetBounds(node, current);
// Stop when nothing changed (but allow re-entry in case it does
later).
- return bounds.Narrows(previous)
- ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER;
+ return previous.Narrows(current) && current.Narrows(previous)
+ ? GenericGraphVisit::DEFER
+ : GenericGraphVisit::REENTER;
} else {
return GenericGraphVisit::SKIP;
}
@@ -379,6 +407,15 @@
if (type->Is(Type::Undefined())) return t->singleton_false;
return type;
}
+
+
+Type* Typer::Visitor::Rangify(Type* type, Typer* t) {
+ if (type->IsRange()) return type; // Shortcut.
+ if (!type->Is(t->integer)) return type; // Give up.
+ Factory* f = t->isolate()->factory();
+ return Type::Range(f->NewNumber(type->Min()), f->NewNumber(type->Max()),
+ t->zone());
+}
// Type conversion.
@@ -455,7 +492,7 @@
Bounds Typer::Visitor::TypeInt32Constant(Node* node) {
- Factory* f = zone()->isolate()->factory();
+ Factory* f = isolate()->factory();
Handle<Object> number = f->NewNumber(OpParameter<int32_t>(node));
return Bounds(Type::Intersect(
Type::Range(number, number, zone()), Type::UntaggedInt32(), zone()));
@@ -482,7 +519,7 @@
Bounds Typer::Visitor::TypeNumberConstant(Node* node) {
- Factory* f = zone()->isolate()->factory();
+ Factory* f = isolate()->factory();
return Bounds(Type::Constant(
f->NewNumber(OpParameter<double>(node)), zone()));
}
@@ -659,7 +696,7 @@
Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) {
- Factory* f = t->zone()->isolate()->factory();
+ Factory* f = t->isolate()->factory();
lhs = NumberToInt32(ToNumber(lhs, t), t);
rhs = NumberToInt32(ToNumber(rhs, t), t);
double lmin = lhs->Min();
@@ -683,7 +720,7 @@
Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) {
- Factory* f = t->zone()->isolate()->factory();
+ Factory* f = t->isolate()->factory();
lhs = NumberToInt32(ToNumber(lhs, t), t);
rhs = NumberToInt32(ToNumber(rhs, t), t);
double lmin = lhs->Min();
@@ -731,7 +768,7 @@
Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) {
lhs = NumberToInt32(ToNumber(lhs, t), t);
- Factory* f = t->zone()->isolate()->factory();
+ Factory* f = t->isolate()->factory();
if (lhs->Min() >= 0) {
// Right-shifting a non-negative value cannot make it negative, nor
larger.
Handle<Object> min = f->NewNumber(0);
@@ -750,7 +787,7 @@
Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs,
Typer* t) {
lhs = NumberToUint32(ToNumber(lhs, t), t);
- Factory* f = t->zone()->isolate()->factory();
+ Factory* f = t->isolate()->factory();
// Logical right-shifting any value cannot make it larger.
Handle<Object> min = f->NewNumber(0);
Handle<Object> max = f->NewNumber(lhs->Max());
@@ -761,6 +798,66 @@
// JS arithmetic operators.
+// Returns the array's least element, ignoring NaN.
+// There must be at least one non-NaN element.
+// Any -0 is converted to 0.
+static double array_min(double a[], size_t n) {
+ DCHECK(n != 0);
+ double x = +V8_INFINITY;
+ for (size_t i = 0; i < n; ++i) {
+ if (!std::isnan(a[i])) {
+ x = std::min(a[i], x);
+ }
+ }
+ DCHECK(!std::isnan(x));
+ return x == 0 ? 0 : x; // -0 -> 0
+}
+
+
+// Returns the array's greatest element, ignoring NaN.
+// There must be at least one non-NaN element.
+// Any -0 is converted to 0.
+static double array_max(double a[], size_t n) {
+ DCHECK(n != 0);
+ double x = -V8_INFINITY;
+ for (size_t i = 0; i < n; ++i) {
+ if (!std::isnan(a[i])) {
+ x = std::max(a[i], x);
+ }
+ }
+ DCHECK(!std::isnan(x));
+ return x == 0 ? 0 : x; // -0 -> 0
+}
+
+
+Type* Typer::Visitor::JSAddRanger(Type::RangeType* lhs, Type::RangeType*
rhs,
+ Typer* t) {
+ double results[4];
+ results[0] = lhs->Min()->Number() + rhs->Min()->Number();
+ results[1] = lhs->Min()->Number() + rhs->Max()->Number();
+ results[2] = lhs->Max()->Number() + rhs->Min()->Number();
+ results[3] = lhs->Max()->Number() + rhs->Max()->Number();
+ // Since none of the inputs can be -0, the result cannot be -0 either.
+ // However, it can be nan (the sum of two infinities of opposite sign).
+ // On the other hand, if none of the "results" above is nan, then the
actual
+ // result cannot be nan either.
+ int nans = 0;
+ for (int i = 0; i < 4; ++i) {
+ if (std::isnan(results[i])) ++nans;
+ }
+ if (nans == 4) return Type::NaN(); // [-inf..-inf] + [inf..inf] or vice
versa
+ Factory* f = t->isolate()->factory();
+ Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
+ f->NewNumber(array_max(results, 4)),
t->zone());
+ return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
+ // Examples:
+ // [-inf, -inf] + [+inf, +inf] = NaN
+ // [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN
+ // [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN
+ // [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN
+}
+
+
Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) {
lhs = ToPrimitive(lhs, t);
rhs = ToPrimitive(rhs, t);
@@ -771,29 +868,93 @@
return Type::NumberOrString();
}
}
- lhs = ToNumber(lhs, t);
- rhs = ToNumber(rhs, t);
+ lhs = Rangify(ToNumber(lhs, t), t);
+ rhs = Rangify(ToNumber(rhs, t), t);
if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
- // TODO(neis): Do some analysis.
+ if (lhs->IsRange() && rhs->IsRange()) {
+ return JSAddRanger(lhs->AsRange(), rhs->AsRange(), t);
+ }
// TODO(neis): Deal with numeric bitsets here and elsewhere.
return Type::Number();
}
+
+
+Type* Typer::Visitor::JSSubtractRanger(Type::RangeType* lhs,
+ Type::RangeType* rhs, Typer* t) {
+ double results[4];
+ results[0] = lhs->Min()->Number() - rhs->Min()->Number();
+ results[1] = lhs->Min()->Number() - rhs->Max()->Number();
+ results[2] = lhs->Max()->Number() - rhs->Min()->Number();
+ results[3] = lhs->Max()->Number() - rhs->Max()->Number();
+ // Since none of the inputs can be -0, the result cannot be -0.
+ // However, it can be nan (the subtraction of two infinities of same
sign).
+ // On the other hand, if none of the "results" above is nan, then the
actual
+ // result cannot be nan either.
+ int nans = 0;
+ for (int i = 0; i < 4; ++i) {
+ if (std::isnan(results[i])) ++nans;
+ }
+ if (nans == 4) return Type::NaN(); // [inf..inf] - [inf..inf] (all same
sign)
+ Factory* f = t->isolate()->factory();
+ Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
+ f->NewNumber(array_max(results, 4)),
t->zone());
+ return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
+ // Examples:
+ // [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN
+ // [-inf, -inf] - [-inf, -inf] = NaN
+ // [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN
+ // [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN
+}
Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) {
- lhs = ToNumber(lhs, t);
- rhs = ToNumber(rhs, t);
+ lhs = Rangify(ToNumber(lhs, t), t);
+ rhs = Rangify(ToNumber(rhs, t), t);
if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
- // TODO(neis): Do some analysis.
+ if (lhs->IsRange() && rhs->IsRange()) {
+ return JSSubtractRanger(lhs->AsRange(), rhs->AsRange(), t);
+ }
return Type::Number();
}
+
+
+Type* Typer::Visitor::JSMultiplyRanger(Type::RangeType* lhs,
+ Type::RangeType* rhs, Typer* t) {
+ double results[4];
+ double lmin = lhs->Min()->Number();
+ double lmax = lhs->Max()->Number();
+ double rmin = rhs->Min()->Number();
+ double rmax = rhs->Max()->Number();
+ results[0] = lmin * rmin;
+ results[1] = lmin * rmax;
+ results[2] = lmax * rmin;
+ results[3] = lmax * rmax;
+ // If the result may be nan, we give up on calculating a precise type,
because
+ // the discontinuity makes it too complicated. Note that even if none
of the
+ // "results" above is nan, the actual result may still be, so we have to
do a
+ // different check:
+ bool maybe_nan = (lhs->Maybe(t->singleton_zero) &&
+ (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) ||
+ (rhs->Maybe(t->singleton_zero) &&
+ (lmin == -V8_INFINITY || lmax == +V8_INFINITY));
+ if (maybe_nan) return t->weakint; // Giving up.
+ bool maybe_minuszero = (lhs->Maybe(t->singleton_zero) && rmin < 0) ||
+ (rhs->Maybe(t->singleton_zero) && lmin < 0);
+ Factory* f = t->isolate()->factory();
+ Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
+ f->NewNumber(array_max(results, 4)),
t->zone());
+ return maybe_minuszero ? Type::Union(range, Type::MinusZero(), t->zone())
+ : range;
+}
Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) {
- lhs = ToNumber(lhs, t);
- rhs = ToNumber(rhs, t);
+ lhs = Rangify(ToNumber(lhs, t), t);
+ rhs = Rangify(ToNumber(rhs, t), t);
if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
- // TODO(neis): Do some analysis.
+ if (lhs->IsRange() && rhs->IsRange()) {
+ return JSMultiplyRanger(lhs->AsRange(), rhs->AsRange(), t);
+ }
return Type::Number();
}
@@ -802,8 +963,13 @@
lhs = ToNumber(lhs, t);
rhs = ToNumber(rhs, t);
if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
- // TODO(neis): Do some analysis.
- return Type::Number();
+ // Division is tricky, so all we do is try ruling out nan.
+ // TODO(neis): try ruling out -0 as well?
+ bool maybe_nan =
+ lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
+ ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
+ (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
+ return maybe_nan ? Type::Number() : Type::OrderedNumber();
}
@@ -811,8 +977,13 @@
lhs = ToNumber(lhs, t);
rhs = ToNumber(rhs, t);
if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
- // TODO(neis): Do some analysis.
- return Type::Number();
+ // Division is tricky, so all we do is try ruling out nan.
+ // TODO(neis): try ruling out -0 as well?
+ bool maybe_nan =
+ lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
+ ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
+ (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
+ return maybe_nan ? Type::Number() : Type::OrderedNumber();
}
@@ -888,6 +1059,51 @@
Bounds Typer::Visitor::TypeJSLoadNamed(Node* node) {
return Bounds::Unbounded(zone());
}
+
+
+// Returns a somewhat larger range if we previously assigned
+// a (smaller) range to this node. This is used to speed up
+// the fixpoint calculation in case there appears to be a loop
+// in the graph. In the current implementation, we are
+// increasing the limits to the closest power of two.
+Type* Typer::Visitor::Weaken(Type* current_type, Type* previous_type) {
+ if (current_type->IsRange() && previous_type->IsRange()) {
+ Type::RangeType* previous = previous_type->AsRange();
+ Type::RangeType* current = current_type->AsRange();
+
+ double current_min = current->Min()->Number();
+ Handle<Object> new_min = current->Min();
+
+ // Find the closest lower entry in the list of allowed
+ // minima (or negative infinity if there is no such entry).
+ if (current_min != previous->Min()->Number()) {
+ new_min = typer_->integer->AsRange()->Min();
+ for (const auto val : typer_->weaken_min_limits_) {
+ if (val->Number() <= current_min) {
+ new_min = val;
+ break;
+ }
+ }
+ }
+
+ double current_max = current->Max()->Number();
+ Handle<Object> new_max = current->Max();
+ // Find the closest greater entry in the list of allowed
+ // maxima (or infinity if there is no such entry).
+ if (current_max != previous->Max()->Number()) {
+ new_max = typer_->integer->AsRange()->Max();
+ for (const auto val : typer_->weaken_max_limits_) {
+ if (val->Number() >= current_max) {
+ new_max = val;
+ break;
+ }
+ }
+ }
+
+ return Type::Range(new_min, new_max, typer_->zone());
+ }
+ return current_type;
+}
Bounds Typer::Visitor::TypeJSStoreProperty(Node* node) {
=======================================
--- /branches/bleeding_edge/src/compiler/typer.h Wed Oct 15 14:12:20 2014
UTC
+++ /branches/bleeding_edge/src/compiler/typer.h Thu Oct 23 14:40:43 2014
UTC
@@ -51,6 +51,7 @@
Type* zeroish;
Type* falsish;
Type* integer;
+ Type* weakint;
Type* number_fun0_;
Type* number_fun1_;
Type* number_fun2_;
@@ -67,6 +68,9 @@
Type* uint32_array_fun_;
Type* float32_array_fun_;
Type* float64_array_fun_;
+
+ ZoneVector<Handle<Object> > weaken_min_limits_;
+ ZoneVector<Handle<Object> > weaken_max_limits_;
};
}
}
=======================================
--- /branches/bleeding_edge/src/types.h Wed Oct 15 11:38:04 2014 UTC
+++ /branches/bleeding_edge/src/types.h Thu Oct 23 14:40:43 2014 UTC
@@ -787,6 +787,7 @@
static RangeHandle New(
i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) {
+ DCHECK(IsInteger(min->Number()) && IsInteger(max->Number()));
DCHECK(min->Number() <= max->Number());
RangeHandle type = Config::template cast<RangeType>(
StructuralType::New(StructuralType::kRangeTag, 3, region));
=======================================
---
/branches/bleeding_edge/test/cctest/compiler/test-simplified-lowering.cc
Thu Oct 23 10:22:06 2014 UTC
+++
/branches/bleeding_edge/test/cctest/compiler/test-simplified-lowering.cc
Thu Oct 23 14:40:43 2014 UTC
@@ -947,24 +947,50 @@
TEST(LowerNumberAddSub_to_int32) {
- TestingGraph t(Type::Signed32(), Type::Signed32());
- t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Add,
- t.simplified()->NumberAdd(),
- t.simplified()->NumberToInt32());
- t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Sub,
- t.simplified()->NumberSubtract(),
- t.simplified()->NumberToInt32());
+ HandleAndZoneScope scope;
+ Factory* f = scope.main_zone()->isolate()->factory();
+ Type* small_range =
+ Type::Range(f->NewNumber(1), f->NewNumber(10), scope.main_zone());
+ Type* large_range =
+ Type::Range(f->NewNumber(-1e+13), f->NewNumber(1e+14),
scope.main_zone());
+ static Type* types[] = {Type::Signed32(), Type::Integral32(),
small_range,
+ large_range};
+
+ for (size_t i = 0; i < arraysize(types); i++) {
+ for (size_t j = 0; j < arraysize(types); j++) {
+ TestingGraph t(types[i], types[j]);
+ t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Add,
+ t.simplified()->NumberAdd(),
+ t.simplified()->NumberToInt32());
+ t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Sub,
+ t.simplified()->NumberSubtract(),
+ t.simplified()->NumberToInt32());
+ }
+ }
}
TEST(LowerNumberAddSub_to_uint32) {
- TestingGraph t(Type::Unsigned32(), Type::Unsigned32());
- t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Add,
- t.simplified()->NumberAdd(),
- t.simplified()->NumberToUint32());
- t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Sub,
- t.simplified()->NumberSubtract(),
- t.simplified()->NumberToUint32());
+ HandleAndZoneScope scope;
+ Factory* f = scope.main_zone()->isolate()->factory();
+ Type* small_range =
+ Type::Range(f->NewNumber(1), f->NewNumber(10), scope.main_zone());
+ Type* large_range =
+ Type::Range(f->NewNumber(-1e+13), f->NewNumber(1e+14),
scope.main_zone());
+ static Type* types[] = {Type::Signed32(), Type::Integral32(),
small_range,
+ large_range};
+
+ for (size_t i = 0; i < arraysize(types); i++) {
+ for (size_t j = 0; j < arraysize(types); j++) {
+ TestingGraph t(types[i], types[j]);
+ t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Add,
+ t.simplified()->NumberAdd(),
+ t.simplified()->NumberToUint32());
+ t.CheckLoweringTruncatedBinop(IrOpcode::kInt32Sub,
+ t.simplified()->NumberSubtract(),
+ t.simplified()->NumberToUint32());
+ }
+ }
}
=======================================
--- /branches/bleeding_edge/test/cctest/compiler/test-typer.cc Fri Oct 17
11:46:06 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-typer.cc Thu Oct 23
14:40:43 2014 UTC
@@ -194,7 +194,7 @@
TEST(TypeJSAdd) {
TyperTester t;
- t.TestBinaryArithOp(t.javascript_.Subtract(), std::plus<double>());
+ t.TestBinaryArithOp(t.javascript_.Add(), std::plus<double>());
}
=======================================
--- /branches/bleeding_edge/test/cctest/test-types.cc Fri Oct 17 11:46:06
2014 UTC
+++ /branches/bleeding_edge/test/cctest/test-types.cc Thu Oct 23 14:40:43
2014 UTC
@@ -590,6 +590,8 @@
}
void MinMax() {
+ Factory* fac = isolate->factory();
+
// If b is regular numeric bitset, then Range(b->Min(),
b->Max())->Is(b).
// TODO(neis): Need to ignore representation for this to be true.
/*
@@ -608,8 +610,7 @@
// If b is regular numeric bitset, then b->Min() and b->Max() are
integers.
for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
TypeHandle type = *it;
- if (this->IsBitset(type) && type->Is(T.Number) &&
- !type->Is(T.None) && !type->Is(T.NaN)) {
+ if (this->IsBitset(type) && type->Is(T.Number) && !type->Is(T.NaN)) {
CHECK(IsInteger(type->Min()) && IsInteger(type->Max()));
}
}
@@ -637,6 +638,15 @@
CHECK(lub->Min() <= type->Min() && type->Max() <= lub->Max());
}
}
+
+ // Rangification: If T->Is(Range(-inf,+inf)) and !T->Is(None), then
+ // T->Is(Range(T->Min(), T->Max())).
+ for (TypeIterator it = T.types.begin(); it != T.types.end(); ++it) {
+ TypeHandle type = *it;
+ CHECK(!(type->Is(T.Integer) && !type->Is(T.None)) ||
+ type->Is(T.Range(fac->NewNumber(type->Min()),
+ fac->NewNumber(type->Max()))));
+ }
}
void BitsetGlb() {
=======================================
--- /branches/bleeding_edge/test/cctest/types-fuzz.h Fri Oct 17 11:46:06
2014 UTC
+++ /branches/bleeding_edge/test/cctest/types-fuzz.h Thu Oct 23 14:40:43
2014 UTC
@@ -102,6 +102,9 @@
x *= rng_->NextInt();
if (!IsMinusZero(x))
integers.push_back(isolate->factory()->NewNumber(x));
}
+
+ Integer = Type::Range(isolate->factory()->NewNumber(-V8_INFINITY),
+ isolate->factory()->NewNumber(+V8_INFINITY),
region);
NumberArray = Type::Array(Number, region);
StringArray = Type::Array(String, region);
@@ -145,6 +148,8 @@
TypeHandle ArrayConstant;
TypeHandle UninitializedConstant;
+ TypeHandle Integer;
+
TypeHandle NumberArray;
TypeHandle StringArray;
TypeHandle AnyArray;
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
