From 93d0e79d6ee09bacc87ab14ff845dc657c799ff3 Mon Sep 17 00:00:00 2001 From: "neis@chromium.org" Date: Wed, 15 Oct 2014 08:21:46 +0000 Subject: [PATCH] Again reland "Refine expression typing, esp. by propagating range information." This relands commit 24552. TBR=rossberg@chromium.org BUG= Review URL: https://codereview.chromium.org/650513003 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@24615 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/compiler/js-typed-lowering.cc | 10 - src/compiler/typer.cc | 695 +++++++++++++++++++------ src/compiler/typer.h | 11 + src/types.cc | 2 +- src/types.h | 3 + test/cctest/cctest.gyp | 1 + test/cctest/compiler/test-js-constant-cache.cc | 2 +- test/cctest/compiler/test-js-typed-lowering.cc | 15 +- test/cctest/compiler/test-typer.cc | 277 ++++++++++ test/cctest/test-types.cc | 22 +- 10 files changed, 865 insertions(+), 173 deletions(-) create mode 100644 test/cctest/compiler/test-typer.cc diff --git a/src/compiler/js-typed-lowering.cc b/src/compiler/js-typed-lowering.cc index 886846e..b63d232 100644 --- a/src/compiler/js-typed-lowering.cc +++ b/src/compiler/js-typed-lowering.cc @@ -383,16 +383,6 @@ Reduction JSTypedLowering::ReduceJSStrictEqual(Node* node, bool invert) { : jsgraph()->TrueConstant()); } } - /* TODO(neis): This is currently unsound. - if (!r.left_type()->Maybe(r.right_type())) { - // Type intersection is empty; === is always false unless both - // inputs could be strings (one internalized and one not). - if (r.OneInputCannotBe(Type::String())) { - return ReplaceEagerly(node, invert ? jsgraph()->TrueConstant() - : jsgraph()->FalseConstant()); - } - } - */ if (r.OneInputIs(Type::Undefined())) { return r.ChangeToPureOperator( simplified()->ReferenceEqual(Type::Undefined()), invert); diff --git a/src/compiler/typer.cc b/src/compiler/typer.cc index f50adbd..b34b5b1 100644 --- a/src/compiler/typer.cc +++ b/src/compiler/typer.cc @@ -17,6 +17,27 @@ namespace compiler { Typer::Typer(Zone* zone) : zone_(zone) { Factory* f = zone->isolate()->factory(); + Handle zero = f->NewNumber(0); + Handle one = f->NewNumber(1); + Handle positive_infinity = f->NewNumber(+V8_INFINITY); + Handle negative_infinity = f->NewNumber(-V8_INFINITY); + + negative_signed32 = Type::Union( + Type::SignedSmall(), Type::OtherSigned32(), zone); + non_negative_signed32 = Type::Union( + Type::UnsignedSmall(), Type::OtherUnsigned31(), zone); + undefined_or_null = Type::Union(Type::Undefined(), Type::Null(), zone); + singleton_false = Type::Constant(f->false_value(), zone); + singleton_true = Type::Constant(f->true_value(), zone); + singleton_zero = Type::Range(zero, zero, zone); + singleton_one = Type::Range(one, one, zone); + zero_or_one = Type::Union(singleton_zero, singleton_one, zone); + zeroish = Type::Union( + 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); + Type* number = Type::Number(); Type* signed32 = Type::Signed32(); Type* unsigned32 = Type::Unsigned32(); @@ -24,8 +45,7 @@ Typer::Typer(Zone* zone) : zone_(zone) { Type* object = Type::Object(); Type* undefined = Type::Undefined(); Type* weakint = Type::Union( - Type::Range(f->NewNumber(-V8_INFINITY), f->NewNumber(+V8_INFINITY), zone), - Type::Union(Type::NaN(), Type::MinusZero(), zone), zone); + integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone); number_fun0_ = Type::Function(number, zone); number_fun1_ = Type::Function(number, number, zone); @@ -35,19 +55,27 @@ Typer::Typer(Zone* zone) : zone_(zone) { random_fun_ = Type::Function(Type::Union( Type::UnsignedSmall(), Type::OtherNumber(), zone), zone); + Type* int8 = Type::Intersect( + Type::Range(f->NewNumber(-0x7F), f->NewNumber(0x7F-1), zone), + Type::UntaggedInt8(), zone); + Type* int16 = Type::Intersect( + Type::Range(f->NewNumber(-0x7FFF), f->NewNumber(0x7FFF-1), zone), + Type::UntaggedInt16(), zone); + Type* uint8 = Type::Intersect( + Type::Range(zero, f->NewNumber(0xFF-1), zone), + Type::UntaggedInt8(), zone); + Type* uint16 = Type::Intersect( + Type::Range(zero, f->NewNumber(0xFFFF-1), zone), + Type::UntaggedInt16(), zone); #define NATIVE_TYPE(sem, rep) \ - Type::Intersect(Type::sem(zone), Type::rep(zone), zone) - // TODO(rossberg): Use range types for more precision, once we have them. - Type* int8 = NATIVE_TYPE(SignedSmall, UntaggedInt8); - Type* int16 = NATIVE_TYPE(SignedSmall, UntaggedInt16); + Type::Intersect(Type::sem(), Type::rep(), zone) Type* int32 = NATIVE_TYPE(Signed32, UntaggedInt32); - Type* uint8 = NATIVE_TYPE(UnsignedSmall, UntaggedInt8); - Type* uint16 = NATIVE_TYPE(UnsignedSmall, UntaggedInt16); Type* uint32 = NATIVE_TYPE(Unsigned32, UntaggedInt32); Type* float32 = NATIVE_TYPE(Number, UntaggedFloat32); Type* float64 = NATIVE_TYPE(Number, UntaggedFloat64); #undef NATIVE_TYPE + Type* buffer = Type::Buffer(zone); Type* int8_array = Type::Array(int8, zone); Type* int16_array = Type::Array(int16, zone); @@ -79,9 +107,21 @@ class Typer::Visitor : public NullNodeVisitor { Bounds TypeNode(Node* node) { switch (node->opcode()) { +#define DECLARE_CASE(x) \ + case IrOpcode::k##x: return TypeBinaryOp(node, x##Typer); + JS_SIMPLE_BINOP_LIST(DECLARE_CASE) +#undef DECLARE_CASE + #define DECLARE_CASE(x) case IrOpcode::k##x: return Type##x(node); DECLARE_CASE(Start) - VALUE_OP_LIST(DECLARE_CASE) + // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST: + COMMON_OP_LIST(DECLARE_CASE) + SIMPLIFIED_OP_LIST(DECLARE_CASE) + MACHINE_OP_LIST(DECLARE_CASE) + JS_SIMPLE_UNOP_LIST(DECLARE_CASE) + JS_OBJECT_OP_LIST(DECLARE_CASE) + JS_CONTEXT_OP_LIST(DECLARE_CASE) + JS_OTHER_OP_LIST(DECLARE_CASE) #undef DECLARE_CASE #define DECLARE_CASE(x) case IrOpcode::k##x: @@ -102,11 +142,11 @@ class Typer::Visitor : public NullNodeVisitor { VALUE_OP_LIST(DECLARE_METHOD) #undef DECLARE_METHOD - Bounds OperandType(Node* node, int i) { + static Bounds OperandType(Node* node, int i) { return NodeProperties::GetBounds(NodeProperties::GetValueInput(node, i)); } - Type* ContextType(Node* node) { + static Type* ContextType(Node* node) { Bounds result = NodeProperties::GetBounds(NodeProperties::GetContextInput(node)); DCHECK(result.upper->Maybe(Type::Internal())); @@ -122,6 +162,37 @@ class Typer::Visitor : public NullNodeVisitor { private: Typer* typer_; MaybeHandle context_; + + typedef Type* (*UnaryTyperFun)(Type*, Typer* t); + typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); + + Bounds TypeUnaryOp(Node* node, UnaryTyperFun); + Bounds TypeBinaryOp(Node* node, BinaryTyperFun); + + static Type* Invert(Type*, Typer*); + static Type* FalsifyUndefined(Type*, Typer*); + + static Type* ToPrimitive(Type*, Typer*); + static Type* ToBoolean(Type*, Typer*); + static Type* ToNumber(Type*, Typer*); + static Type* ToString(Type*, Typer*); + static Type* NumberToInt32(Type*, Typer*); + static Type* NumberToUint32(Type*, Typer*); + + static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*); + static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*); + static Type* JSMultiplyRanger(Type::RangeType*, Type::RangeType*, Typer*); + static Type* JSDivideRanger(Type::RangeType*, Type::RangeType*, Typer*); + + static Type* JSCompareTyper(Type*, Type*, Typer*); + +#define DECLARE_METHOD(x) static Type* x##Typer(Type*, Type*, Typer*); + JS_SIMPLE_BINOP_LIST(DECLARE_METHOD) +#undef DECLARE_METHOD + + static Type* JSUnaryNotTyper(Type*, Typer*); + static Type* JSLoadPropertyTyper(Type*, Type*, Typer*); + static Type* JSCallFunctionTyper(Type*, Typer*); }; @@ -237,49 +308,160 @@ void Typer::Init(Node* node) { // ----------------------------------------------------------------------------- +// Helper functions that lift a function f on types to a function on bounds, +// and uses that to type the given node. Note that f is never called with None +// as an argument. + + +Bounds Typer::Visitor::TypeUnaryOp(Node* node, UnaryTyperFun f) { + Bounds input = OperandType(node, 0); + Type* upper = input.upper->Is(Type::None()) + ? Type::None() + : f(input.upper, typer_); + Type* lower = input.lower->Is(Type::None()) + ? Type::None() + : (input.lower == input.upper || upper->IsConstant()) + ? upper // TODO(neis): Extend this to Range(x,x), NaN, MinusZero, ...? + : f(input.lower, typer_); + // TODO(neis): Figure out what to do with lower bound. + return Bounds(lower, upper); +} + + +Bounds Typer::Visitor::TypeBinaryOp(Node* node, BinaryTyperFun f) { + Bounds left = OperandType(node, 0); + Bounds right = OperandType(node, 1); + Type* upper = left.upper->Is(Type::None()) || right.upper->Is(Type::None()) + ? Type::None() + : f(left.upper, right.upper, typer_); + Type* lower = left.lower->Is(Type::None()) || right.lower->Is(Type::None()) + ? Type::None() + : ((left.lower == left.upper && right.lower == right.upper) || + upper->IsConstant()) + ? upper + : f(left.lower, right.lower, typer_); + // TODO(neis): Figure out what to do with lower bound. + return Bounds(lower, upper); +} + + +Type* Typer::Visitor::Invert(Type* type, Typer* t) { + if (type->Is(t->singleton_false)) return t->singleton_true; + if (type->Is(t->singleton_true)) return t->singleton_false; + return type; +} + + +Type* Typer::Visitor::FalsifyUndefined(Type* type, Typer* t) { + if (type->Is(Type::Undefined())) return t->singleton_false; + return type; +} + + +// Type conversion. + + +Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) { + if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) { + return type; + } + return Type::Primitive(); +} + + +Type* Typer::Visitor::ToBoolean(Type* type, Typer* t) { + if (type->Is(Type::Boolean())) return type; + if (type->Is(t->falsish)) return t->singleton_false; + if (type->Is(Type::DetectableReceiver())) return t->singleton_true; + if (type->Is(Type::OrderedNumber()) && (type->Max() < 0 || 0 < type->Min())) { + return t->singleton_true; // Ruled out nan, -0 and +0. + } + return Type::Boolean(); +} + + +Type* Typer::Visitor::ToNumber(Type* type, Typer* t) { + if (type->Is(Type::Number())) return type; + if (type->Is(Type::Undefined())) return Type::NaN(); + if (type->Is(t->singleton_false)) return t->singleton_zero; + if (type->Is(t->singleton_true)) return t->singleton_one; + if (type->Is(Type::Boolean())) return t->zero_or_one; + return Type::Number(); +} + + +Type* Typer::Visitor::ToString(Type* type, Typer* t) { + if (type->Is(Type::String())) return type; + return Type::String(); +} + + +Type* Typer::Visitor::NumberToInt32(Type* type, Typer* t) { + // TODO(neis): DCHECK(type->Is(Type::Number())); + if (type->Is(Type::Signed32())) return type; + if (type->Is(t->zeroish)) return t->singleton_zero; + return Type::Signed32(); +} + + +Type* Typer::Visitor::NumberToUint32(Type* type, Typer* t) { + // TODO(neis): DCHECK(type->Is(Type::Number())); + if (type->Is(Type::Unsigned32())) return type; + if (type->Is(t->zeroish)) return t->singleton_zero; + return Type::Unsigned32(); +} + + +// ----------------------------------------------------------------------------- + // Control operators. + Bounds Typer::Visitor::TypeStart(Node* node) { - return Bounds(Type::Internal(zone())); + return Bounds(Type::Internal()); } // Common operators. + Bounds Typer::Visitor::TypeParameter(Node* node) { return Bounds::Unbounded(zone()); } Bounds Typer::Visitor::TypeInt32Constant(Node* node) { - // TODO(titzer): only call Type::Of() if the type is not already known. - return Bounds(Type::Of(OpParameter(node), zone())); + Factory* f = zone()->isolate()->factory(); + Handle number = f->NewNumber(OpParameter(node)); + return Bounds(Type::Intersect( + Type::Range(number, number, zone()), Type::UntaggedInt32(), zone())); } Bounds Typer::Visitor::TypeInt64Constant(Node* node) { - // TODO(titzer): only call Type::Of() if the type is not already known. - return Bounds( - Type::Of(static_cast(OpParameter(node)), zone())); + return Bounds(Type::Internal()); // TODO(rossberg): Add int64 bitset type? } Bounds Typer::Visitor::TypeFloat32Constant(Node* node) { - // TODO(titzer): only call Type::Of() if the type is not already known. - return Bounds(Type::Of(OpParameter(node), zone())); + return Bounds(Type::Intersect( + Type::Of(OpParameter(node), zone()), + Type::UntaggedFloat32(), zone())); } Bounds Typer::Visitor::TypeFloat64Constant(Node* node) { - // TODO(titzer): only call Type::Of() if the type is not already known. - return Bounds(Type::Of(OpParameter(node), zone())); + return Bounds(Type::Intersect( + Type::Of(OpParameter(node), zone()), + Type::UntaggedFloat64(), zone())); } Bounds Typer::Visitor::TypeNumberConstant(Node* node) { - // TODO(titzer): only call Type::Of() if the type is not already known. - return Bounds(Type::Of(OpParameter(node), zone())); + Factory* f = zone()->isolate()->factory(); + return Bounds(Type::Constant( + f->NewNumber(OpParameter(node)), zone())); } @@ -289,7 +471,7 @@ Bounds Typer::Visitor::TypeHeapConstant(Node* node) { Bounds Typer::Visitor::TypeExternalConstant(Node* node) { - return Bounds(Type::Internal(zone())); + return Bounds(Type::Internal()); } @@ -322,12 +504,12 @@ Bounds Typer::Visitor::TypeFinish(Node* node) { Bounds Typer::Visitor::TypeFrameState(Node* node) { // TODO(rossberg): Ideally FrameState wouldn't have a value output. - return Bounds(Type::Internal(zone())); + return Bounds(Type::Internal()); } Bounds Typer::Visitor::TypeStateValues(Node* node) { - return Bounds(Type::Internal(zone())); + return Bounds(Type::Internal()); } @@ -344,159 +526,339 @@ Bounds Typer::Visitor::TypeProjection(Node* node) { // JS comparison operators. -#define DEFINE_METHOD(x) \ - Bounds Typer::Visitor::Type##x(Node* node) { \ - return Bounds(Type::Boolean(zone())); \ + +Type* Typer::Visitor::JSEqualTyper(Type* lhs, Type* rhs, Typer* t) { + if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false; + if (lhs->Is(t->undefined_or_null) && rhs->Is(t->undefined_or_null)) { + return t->singleton_true; } -JS_COMPARE_BINOP_LIST(DEFINE_METHOD) -#undef DEFINE_METHOD + if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) && + (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) { + return t->singleton_false; + } + if (lhs->IsConstant() && rhs->Is(lhs)) { + // Types are equal and are inhabited only by a single semantic value, + // which is not nan due to the earlier check. + // TODO(neis): Extend this to Range(x,x), MinusZero, ...? + return t->singleton_true; + } + return Type::Boolean(); +} -// JS bitwise operators. +Type* Typer::Visitor::JSNotEqualTyper(Type* lhs, Type* rhs, Typer* t) { + return Invert(JSEqualTyper(lhs, rhs, t), t); +} -Bounds Typer::Visitor::TypeJSBitwiseOr(Node* node) { - Bounds left = OperandType(node, 0); - Bounds right = OperandType(node, 1); - Type* upper = Type::Union(left.upper, right.upper, zone()); - if (!upper->Is(Type::Signed32())) upper = Type::Signed32(zone()); - Type* lower = Type::Intersect(Type::SignedSmall(zone()), upper, zone()); - return Bounds(lower, upper); + +static Type* JSType(Type* type) { + if (type->Is(Type::Boolean())) return Type::Boolean(); + if (type->Is(Type::String())) return Type::String(); + if (type->Is(Type::Number())) return Type::Number(); + if (type->Is(Type::Undefined())) return Type::Undefined(); + if (type->Is(Type::Null())) return Type::Null(); + if (type->Is(Type::Symbol())) return Type::Symbol(); + if (type->Is(Type::Receiver())) return Type::Receiver(); // JS "Object" + return Type::Any(); } -Bounds Typer::Visitor::TypeJSBitwiseAnd(Node* node) { - Bounds left = OperandType(node, 0); - Bounds right = OperandType(node, 1); - Type* upper = Type::Union(left.upper, right.upper, zone()); - if (!upper->Is(Type::Signed32())) upper = Type::Signed32(zone()); - Type* lower = Type::Intersect(Type::SignedSmall(zone()), upper, zone()); - return Bounds(lower, upper); +Type* Typer::Visitor::JSStrictEqualTyper(Type* lhs, Type* rhs, Typer* t) { + if (!JSType(lhs)->Maybe(JSType(rhs))) return t->singleton_false; + if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false; + if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) && + (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) { + return t->singleton_false; + } + if (lhs->IsConstant() && rhs->Is(lhs)) { + // Types are equal and are inhabited only by a single semantic value, + // which is not nan due to the earlier check. + return t->singleton_true; + } + return Type::Boolean(); +} + + +Type* Typer::Visitor::JSStrictNotEqualTyper(Type* lhs, Type* rhs, Typer* t) { + return Invert(JSStrictEqualTyper(lhs, rhs, t), t); +} + + +// The EcmaScript specification defines the four relational comparison operators +// (<, <=, >=, >) with the help of a single abstract one. It behaves like < +// but returns undefined when the inputs cannot be compared. +// We implement the typing analogously. +Type* Typer::Visitor::JSCompareTyper(Type* lhs, Type* rhs, Typer* t) { + lhs = ToPrimitive(lhs, t); + rhs = ToPrimitive(rhs, t); + if (lhs->Maybe(Type::String()) && rhs->Maybe(Type::String())) { + return Type::Boolean(); + } + lhs = ToNumber(lhs, t); + rhs = ToNumber(rhs, t); + if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::Undefined(); + if (lhs->IsConstant() && rhs->Is(lhs)) { + // Types are equal and are inhabited only by a single semantic value, + // which is not NaN due to the previous check. + return t->singleton_false; + } + if (lhs->Min() >= rhs->Max()) return t->singleton_false; + if (lhs->Max() < rhs->Min() && + !lhs->Maybe(Type::NaN()) && !rhs->Maybe(Type::NaN())) { + return t->singleton_true; + } + return Type::Boolean(); +} + + +Type* Typer::Visitor::JSLessThanTyper(Type* lhs, Type* rhs, Typer* t) { + return FalsifyUndefined(JSCompareTyper(lhs, rhs, t), t); +} + + +Type* Typer::Visitor::JSGreaterThanTyper(Type* lhs, Type* rhs, Typer* t) { + return FalsifyUndefined(JSCompareTyper(rhs, lhs, t), t); +} + + +Type* Typer::Visitor::JSLessThanOrEqualTyper(Type* lhs, Type* rhs, Typer* t) { + return FalsifyUndefined(Invert(JSCompareTyper(rhs, lhs, t), t), t); } -Bounds Typer::Visitor::TypeJSBitwiseXor(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Signed32(zone())); +Type* Typer::Visitor::JSGreaterThanOrEqualTyper( + Type* lhs, Type* rhs, Typer* t) { + return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t); } -Bounds Typer::Visitor::TypeJSShiftLeft(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Signed32(zone())); +// JS bitwise operators. + + +Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) { + Factory* f = t->zone()->isolate()->factory(); + lhs = NumberToInt32(ToNumber(lhs, t), t); + rhs = NumberToInt32(ToNumber(rhs, t), t); + double lmin = lhs->Min(); + double rmin = rhs->Min(); + double lmax = lhs->Max(); + double rmax = rhs->Max(); + // Or-ing any two values results in a value no smaller than their minimum. + // Even no smaller than their maximum if both values are non-negative. + Handle min = f->NewNumber( + lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin)); + if (lmax < 0 || rmax < 0) { + // Or-ing two values of which at least one is negative results in a negative + // value. + Handle max = f->NewNumber(-1); + return Type::Range(min, max, t->zone()); + } + Handle max = f->NewNumber(Type::Signed32()->Max()); + return Type::Range(min, max, t->zone()); + // TODO(neis): Be precise for singleton inputs, here and elsewhere. +} + + +Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) { + Factory* f = t->zone()->isolate()->factory(); + lhs = NumberToInt32(ToNumber(lhs, t), t); + rhs = NumberToInt32(ToNumber(rhs, t), t); + double lmin = lhs->Min(); + double rmin = rhs->Min(); + double lmax = lhs->Max(); + double rmax = rhs->Max(); + // And-ing any two values results in a value no larger than their maximum. + // Even no larger than their minimum if both values are non-negative. + Handle max = f->NewNumber( + lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax)); + if (lmin >= 0 || rmin >= 0) { + // And-ing two values of which at least one is non-negative results in a + // non-negative value. + Handle min = f->NewNumber(0); + return Type::Range(min, max, t->zone()); + } + Handle min = f->NewNumber(Type::Signed32()->Min()); + return Type::Range(min, max, t->zone()); } -Bounds Typer::Visitor::TypeJSShiftRight(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Signed32(zone())); +Type* Typer::Visitor::JSBitwiseXorTyper(Type* lhs, Type* rhs, Typer* t) { + lhs = NumberToInt32(ToNumber(lhs, t), t); + rhs = NumberToInt32(ToNumber(rhs, t), t); + double lmin = lhs->Min(); + double rmin = rhs->Min(); + double lmax = lhs->Max(); + double rmax = rhs->Max(); + if ((lmin >= 0 && rmin >= 0) || (lmax < 0 && rmax < 0)) { + // Xor-ing negative or non-negative values results in a non-negative value. + return t->non_negative_signed32; + } + if ((lmax < 0 && rmin >= 0) || (lmin >= 0 && rmax < 0)) { + // Xor-ing a negative and a non-negative value results in a negative value. + return t->negative_signed32; + } + return Type::Signed32(); } -Bounds Typer::Visitor::TypeJSShiftRightLogical(Node* node) { - return Bounds(Type::UnsignedSmall(zone()), Type::Unsigned32(zone())); +Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) { + return Type::Signed32(); +} + + +Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) { + lhs = NumberToInt32(ToNumber(lhs, t), t); + Factory* f = t->zone()->isolate()->factory(); + if (lhs->Min() >= 0) { + // Right-shifting a non-negative value cannot make it negative, nor larger. + Handle min = f->NewNumber(0); + Handle max = f->NewNumber(lhs->Max()); + return Type::Range(min, max, t->zone()); + } + if (lhs->Max() < 0) { + // Right-shifting a negative value cannot make it non-negative, nor smaller. + Handle min = f->NewNumber(lhs->Min()); + Handle max = f->NewNumber(-1); + return Type::Range(min, max, t->zone()); + } + return Type::Signed32(); +} + + +Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) { + lhs = NumberToUint32(ToNumber(lhs, t), t); + Factory* f = t->zone()->isolate()->factory(); + // Logical right-shifting any value cannot make it larger. + Handle min = f->NewNumber(0); + Handle max = f->NewNumber(lhs->Max()); + return Type::Range(min, max, t->zone()); } // JS arithmetic operators. -Bounds Typer::Visitor::TypeJSAdd(Node* node) { - Bounds left = OperandType(node, 0); - Bounds right = OperandType(node, 1); - Type* lower = - left.lower->Is(Type::None()) || right.lower->Is(Type::None()) ? - Type::None(zone()) : - left.lower->Is(Type::Number()) && right.lower->Is(Type::Number()) ? - Type::SignedSmall(zone()) : - left.lower->Is(Type::String()) || right.lower->Is(Type::String()) ? - Type::String(zone()) : Type::None(zone()); - Type* upper = - left.upper->Is(Type::None()) && right.upper->Is(Type::None()) ? - Type::None(zone()) : - left.upper->Is(Type::Number()) && right.upper->Is(Type::Number()) ? - Type::Number(zone()) : - left.upper->Is(Type::String()) || right.upper->Is(Type::String()) ? - Type::String(zone()) : Type::NumberOrString(zone()); - return Bounds(lower, upper); + +Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) { + lhs = ToPrimitive(lhs, t); + rhs = ToPrimitive(rhs, t); + if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) { + if (lhs->Is(Type::String()) || rhs->Is(Type::String())) { + return Type::String(); + } else { + return Type::NumberOrString(); + } + } + 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. + // TODO(neis): Deal with numeric bitsets here and elsewhere. + return Type::Number(); } -Bounds Typer::Visitor::TypeJSSubtract(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Number(zone())); +Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) { + 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(); } -Bounds Typer::Visitor::TypeJSMultiply(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Number(zone())); +Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) { + 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(); } -Bounds Typer::Visitor::TypeJSDivide(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Number(zone())); +Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) { + 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(); } -Bounds Typer::Visitor::TypeJSModulus(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Number(zone())); +Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) { + 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(); } // JS unary operators. + +Type* Typer::Visitor::JSUnaryNotTyper(Type* type, Typer* t) { + return Invert(ToBoolean(type, t), t); +} + + Bounds Typer::Visitor::TypeJSUnaryNot(Node* node) { - return Bounds(Type::Boolean(zone())); + return TypeUnaryOp(node, JSUnaryNotTyper); } Bounds Typer::Visitor::TypeJSTypeOf(Node* node) { - return Bounds(Type::InternalizedString(zone())); + return Bounds(Type::InternalizedString()); } // JS conversion operators. + Bounds Typer::Visitor::TypeJSToBoolean(Node* node) { - return Bounds(Type::Boolean(zone())); + return TypeUnaryOp(node, ToBoolean); } Bounds Typer::Visitor::TypeJSToNumber(Node* node) { - return Bounds(Type::SignedSmall(zone()), Type::Number(zone())); + return TypeUnaryOp(node, ToNumber); } Bounds Typer::Visitor::TypeJSToString(Node* node) { - return Bounds(Type::None(zone()), Type::String(zone())); + return TypeUnaryOp(node, ToString); } Bounds Typer::Visitor::TypeJSToName(Node* node) { - return Bounds(Type::None(zone()), Type::Name(zone())); + return Bounds(Type::None(), Type::Name()); } Bounds Typer::Visitor::TypeJSToObject(Node* node) { - return Bounds(Type::None(zone()), Type::Receiver(zone())); + return Bounds(Type::None(), Type::Receiver()); } // JS object operators. + Bounds Typer::Visitor::TypeJSCreate(Node* node) { - return Bounds(Type::None(zone()), Type::Object(zone())); + return Bounds(Type::None(), Type::Object()); } -Bounds Typer::Visitor::TypeJSLoadProperty(Node* node) { - Bounds object = OperandType(node, 0); - Bounds name = OperandType(node, 1); - Bounds result = Bounds::Unbounded(zone()); +Type* Typer::Visitor::JSLoadPropertyTyper(Type* object, Type* name, Typer* t) { // TODO(rossberg): Use range types and sized array types to filter undefined. - if (object.lower->IsArray() && name.lower->Is(Type::Integral32())) { - result.lower = Type::Union( - object.lower->AsArray()->Element(), Type::Undefined(zone()), zone()); - } - if (object.upper->IsArray() && name.upper->Is(Type::Integral32())) { - result.upper = Type::Union( - object.upper->AsArray()->Element(), Type::Undefined(zone()), zone()); + if (object->IsArray() && name->Is(Type::Integral32())) { + return Type::Union( + object->AsArray()->Element(), Type::Undefined(), t->zone()); } - return result; + return Type::Any(); +} + + +Bounds Typer::Visitor::TypeJSLoadProperty(Node* node) { + return TypeBinaryOp(node, JSLoadPropertyTyper); } @@ -518,22 +880,23 @@ Bounds Typer::Visitor::TypeJSStoreNamed(Node* node) { Bounds Typer::Visitor::TypeJSDeleteProperty(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeJSHasProperty(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeJSInstanceOf(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } // JS context operators. + Bounds Typer::Visitor::TypeJSLoadContext(Node* node) { Bounds outer = OperandType(node, 0); DCHECK(outer.upper->Maybe(Type::Internal())); @@ -568,7 +931,7 @@ Bounds Typer::Visitor::TypeJSLoadContext(Node* node) { handle(context.ToHandleChecked()->get(static_cast(access.index())), isolate()); Type* lower = TypeConstant(value); - return Bounds(lower, Type::Any(zone())); + return Bounds(lower, Type::Any()); } } @@ -618,23 +981,24 @@ Bounds Typer::Visitor::TypeJSCreateGlobalContext(Node* node) { // JS other operators. + Bounds Typer::Visitor::TypeJSYield(Node* node) { return Bounds::Unbounded(zone()); } Bounds Typer::Visitor::TypeJSCallConstruct(Node* node) { - return Bounds(Type::None(zone()), Type::Receiver(zone())); + return Bounds(Type::None(), Type::Receiver()); +} + + +Type* Typer::Visitor::JSCallFunctionTyper(Type* fun, Typer* t) { + return fun->IsFunction() ? fun->AsFunction()->Result() : Type::Any(); } Bounds Typer::Visitor::TypeJSCallFunction(Node* node) { - Bounds fun = OperandType(node, 0); - Type* lower = fun.lower->IsFunction() - ? fun.lower->AsFunction()->Result() : Type::None(zone()); - Type* upper = fun.upper->IsFunction() - ? fun.upper->AsFunction()->Result() : Type::Any(zone()); - return Bounds(lower, upper); + return TypeUnaryOp(node, JSCallFunctionTyper); // We ignore argument types. } @@ -650,143 +1014,172 @@ Bounds Typer::Visitor::TypeJSDebugger(Node* node) { // Simplified operators. + Bounds Typer::Visitor::TypeBooleanNot(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeBooleanToNumber(Node* node) { - return Bounds(Type::Number(zone())); + return Bounds(Type::Number()); } Bounds Typer::Visitor::TypeNumberEqual(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeNumberLessThan(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeNumberLessThanOrEqual(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeNumberAdd(Node* node) { - return Bounds(Type::Number(zone())); + return Bounds(Type::Number()); } Bounds Typer::Visitor::TypeNumberSubtract(Node* node) { - return Bounds(Type::Number(zone())); + return Bounds(Type::Number()); } Bounds Typer::Visitor::TypeNumberMultiply(Node* node) { - return Bounds(Type::Number(zone())); + return Bounds(Type::Number()); } Bounds Typer::Visitor::TypeNumberDivide(Node* node) { - return Bounds(Type::Number(zone())); + return Bounds(Type::Number()); } Bounds Typer::Visitor::TypeNumberModulus(Node* node) { - return Bounds(Type::Number(zone())); + return Bounds(Type::Number()); } Bounds Typer::Visitor::TypeNumberToInt32(Node* node) { - Bounds arg = OperandType(node, 0); - Type* s32 = Type::Signed32(zone()); - Type* lower = arg.lower->Is(s32) ? arg.lower : s32; - Type* upper = arg.upper->Is(s32) ? arg.upper : s32; - return Bounds(lower, upper); + return TypeUnaryOp(node, NumberToInt32); } Bounds Typer::Visitor::TypeNumberToUint32(Node* node) { - Bounds arg = OperandType(node, 0); - Type* u32 = Type::Unsigned32(zone()); - Type* lower = arg.lower->Is(u32) ? arg.lower : u32; - Type* upper = arg.upper->Is(u32) ? arg.upper : u32; - return Bounds(lower, upper); + return TypeUnaryOp(node, NumberToUint32); } Bounds Typer::Visitor::TypeReferenceEqual(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeStringEqual(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeStringLessThan(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeStringLessThanOrEqual(Node* node) { - return Bounds(Type::Boolean(zone())); + return Bounds(Type::Boolean()); } Bounds Typer::Visitor::TypeStringAdd(Node* node) { - return Bounds(Type::String(zone())); + return Bounds(Type::String()); +} + + +static Type* ChangeRepresentation(Type* type, Type* rep, Zone* zone) { + // TODO(neis): Enable when expressible. + /* + return Type::Union( + Type::Intersect(type, Type::Semantic(), zone), + Type::Intersect(rep, Type::Representation(), zone), zone); + */ + return type; } Bounds Typer::Visitor::TypeChangeTaggedToInt32(Node* node) { - // TODO(titzer): type is type of input, representation is Word32. - return Bounds(Type::Integral32()); + Bounds arg = OperandType(node, 0); + // TODO(neis): DCHECK(arg.upper->Is(Type::Signed32())); + return Bounds( + ChangeRepresentation(arg.lower, Type::UntaggedInt32(), zone()), + ChangeRepresentation(arg.upper, Type::UntaggedInt32(), zone())); } Bounds Typer::Visitor::TypeChangeTaggedToUint32(Node* node) { - return Bounds(Type::Integral32()); // TODO(titzer): add appropriate rep + Bounds arg = OperandType(node, 0); + // TODO(neis): DCHECK(arg.upper->Is(Type::Unsigned32())); + return Bounds( + ChangeRepresentation(arg.lower, Type::UntaggedInt32(), zone()), + ChangeRepresentation(arg.upper, Type::UntaggedInt32(), zone())); } Bounds Typer::Visitor::TypeChangeTaggedToFloat64(Node* node) { - // TODO(titzer): type is type of input, representation is Float64. - return Bounds(Type::Number()); + Bounds arg = OperandType(node, 0); + // TODO(neis): DCHECK(arg.upper->Is(Type::Number())); + return Bounds( + ChangeRepresentation(arg.lower, Type::UntaggedFloat64(), zone()), + ChangeRepresentation(arg.upper, Type::UntaggedFloat64(), zone())); } Bounds Typer::Visitor::TypeChangeInt32ToTagged(Node* node) { - // TODO(titzer): type is type of input, representation is Tagged. - return Bounds(Type::Integral32()); + Bounds arg = OperandType(node, 0); + // TODO(neis): DCHECK(arg.upper->Is(Type::Signed32())); + return Bounds( + ChangeRepresentation(arg.lower, Type::Tagged(), zone()), + ChangeRepresentation(arg.upper, Type::Tagged(), zone())); } Bounds Typer::Visitor::TypeChangeUint32ToTagged(Node* node) { - // TODO(titzer): type is type of input, representation is Tagged. - return Bounds(Type::Unsigned32()); + Bounds arg = OperandType(node, 0); + // TODO(neis): DCHECK(arg.upper->Is(Type::Unsigned32())); + return Bounds( + ChangeRepresentation(arg.lower, Type::Tagged(), zone()), + ChangeRepresentation(arg.upper, Type::Tagged(), zone())); } Bounds Typer::Visitor::TypeChangeFloat64ToTagged(Node* node) { - // TODO(titzer): type is type of input, representation is Tagged. - return Bounds(Type::Number()); + Bounds arg = OperandType(node, 0); + // TODO(neis): CHECK(arg.upper->Is(Type::Number())); + return Bounds( + ChangeRepresentation(arg.lower, Type::Tagged(), zone()), + ChangeRepresentation(arg.upper, Type::Tagged(), zone())); } Bounds Typer::Visitor::TypeChangeBoolToBit(Node* node) { - // TODO(titzer): type is type of input, representation is Bit. - return Bounds(Type::Boolean()); + Bounds arg = OperandType(node, 0); + // TODO(neis): DCHECK(arg.upper->Is(Type::Boolean())); + return Bounds( + ChangeRepresentation(arg.lower, Type::UntaggedInt1(), zone()), + ChangeRepresentation(arg.upper, Type::UntaggedInt1(), zone())); } Bounds Typer::Visitor::TypeChangeBitToBool(Node* node) { - // TODO(titzer): type is type of input, representation is Tagged. - return Bounds(Type::Boolean()); + Bounds arg = OperandType(node, 0); + // TODO(neis): DCHECK(arg.upper->Is(Type::Boolean())); + return Bounds( + ChangeRepresentation(arg.lower, Type::TaggedPtr(), zone()), + ChangeRepresentation(arg.upper, Type::TaggedPtr(), zone())); } diff --git a/src/compiler/typer.h b/src/compiler/typer.h index 2adbab5..3b37a92 100644 --- a/src/compiler/typer.h +++ b/src/compiler/typer.h @@ -36,6 +36,17 @@ class Typer { class WidenVisitor; Zone* zone_; + Type* negative_signed32; + Type* non_negative_signed32; + Type* undefined_or_null; + Type* singleton_false; + Type* singleton_true; + Type* singleton_zero; + Type* singleton_one; + Type* zero_or_one; + Type* zeroish; + Type* falsish; + Type* integer; Type* number_fun0_; Type* number_fun1_; Type* number_fun2_; diff --git a/src/types.cc b/src/types.cc index 307dc91..a3a0ac9 100644 --- a/src/types.cc +++ b/src/types.cc @@ -344,7 +344,7 @@ double TypeImpl::BitsetType::Max(bitset bits) { DisallowHeapAllocation no_allocation; DCHECK(Is(bits, kNumber)); const BitsetMin* mins = BitsetMins(); - bool mz = bits & kMinusZero; + bool mz = SEMANTIC(bits & kMinusZero); if (BitsetType::Is(mins[BitsetMinsSize()-1].bits, bits)) { return +V8_INFINITY; } diff --git a/src/types.h b/src/types.h index b349b6b..99bae80 100644 --- a/src/types.h +++ b/src/types.h @@ -242,6 +242,9 @@ namespace internal { * * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. * + * NOTE: OtherSigned32 (OS32) and OU31 (OtherUnsigned31) are empty if Smis are + * 32-bit wide. They should thus never be used directly, only indirectly + * via e.g. Number. */ #define PROPER_BITSET_TYPE_LIST(V) \ diff --git a/test/cctest/cctest.gyp b/test/cctest/cctest.gyp index fdcffba..003a643 100644 --- a/test/cctest/cctest.gyp +++ b/test/cctest/cctest.gyp @@ -86,6 +86,7 @@ 'compiler/test-schedule.cc', 'compiler/test-scheduler.cc', 'compiler/test-simplified-lowering.cc', + 'compiler/test-typer.cc', 'cctest.cc', 'gay-fixed.cc', 'gay-precision.cc', diff --git a/test/cctest/compiler/test-js-constant-cache.cc b/test/cctest/compiler/test-js-constant-cache.cc index eb0975e..d7f1997 100644 --- a/test/cctest/compiler/test-js-constant-cache.cc +++ b/test/cctest/compiler/test-js-constant-cache.cc @@ -227,7 +227,7 @@ TEST(NumberTypes) { FOR_FLOAT64_INPUTS(i) { double value = *i; Node* node = T.Constant(value); - CHECK(T.upper(node)->Equals(Type::Of(value, T.main_zone()))); + CHECK(T.upper(node)->Is(Type::Of(value, T.main_zone()))); } } diff --git a/test/cctest/compiler/test-js-typed-lowering.cc b/test/cctest/compiler/test-js-typed-lowering.cc index 5e8ac7a..ba7f094 100644 --- a/test/cctest/compiler/test-js-typed-lowering.cc +++ b/test/cctest/compiler/test-js-typed-lowering.cc @@ -262,16 +262,15 @@ TEST(NumberBinops) { static void CheckToI32(Node* old_input, Node* new_input, bool is_signed) { Type* old_type = NodeProperties::GetBounds(old_input).upper; + Type* new_type = NodeProperties::GetBounds(new_input).upper; Type* expected_type = I32Type(is_signed); + CHECK(new_type->Is(expected_type)); if (old_type->Is(expected_type)) { CHECK_EQ(old_input, new_input); } else if (new_input->opcode() == IrOpcode::kNumberConstant) { - CHECK(NodeProperties::GetBounds(new_input).upper->Is(expected_type)); double v = OpParameter(new_input); double e = static_cast(is_signed ? FastD2I(v) : FastD2UI(v)); CHECK_EQ(e, v); - } else { - CHECK_EQ(NumberToI32(is_signed), new_input->opcode()); } } @@ -365,11 +364,11 @@ TEST(Int32BitwiseBinops) { JSBitwiseTypedLoweringTester R; Type* types[] = { - Type::SignedSmall(), Type::UnsignedSmall(), Type::OtherSigned32(), - Type::Unsigned32(), Type::Signed32(), Type::MinusZero(), - Type::NaN(), Type::OtherNumber(), Type::Undefined(), - Type::Null(), Type::Boolean(), Type::Number(), - Type::String(), Type::Object()}; + Type::SignedSmall(), Type::UnsignedSmall(), Type::Unsigned32(), + Type::Signed32(), Type::MinusZero(), Type::NaN(), + Type::OtherNumber(), Type::Undefined(), Type::Null(), + Type::Boolean(), Type::Number(), Type::String(), + Type::Object()}; for (size_t i = 0; i < arraysize(types); ++i) { Node* p0 = R.Parameter(types[i], 0); diff --git a/test/cctest/compiler/test-typer.cc b/test/cctest/compiler/test-typer.cc new file mode 100644 index 0000000..0c9438a --- /dev/null +++ b/test/cctest/compiler/test-typer.cc @@ -0,0 +1,277 @@ +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + + +// This tests the correctness of the typer. +// +// For simplicity, it currently only tests it on expression operators that have +// a direct equivalent in C++. Also, testing is currently limited to ranges as +// input types. + + +#include + +#include "src/compiler/node-properties-inl.h" +#include "src/compiler/typer.h" +#include "test/cctest/cctest.h" +#include "test/cctest/compiler/graph-builder-tester.h" + +using namespace v8::internal; +using namespace v8::internal::compiler; + + + +class TyperTester : public HandleAndZoneScope, public GraphAndBuilders { + public: + TyperTester() + : GraphAndBuilders(main_zone()), + typer_(main_zone()), + javascript_(main_zone()) { + Node* s = graph()->NewNode(common()->Start(3)); + graph()->SetStart(s); + context_node_ = graph()->NewNode(common()->Parameter(2), graph()->start()); + rng_ = isolate()->random_number_generator(); + + integers.push_back(0); + integers.push_back(0); + integers.push_back(-1); + integers.push_back(+1); + integers.push_back(-V8_INFINITY); + integers.push_back(+V8_INFINITY); + for (int i = 0; i < 5; ++i) { + double x = rng_->NextInt(); + integers.push_back(x); + x *= rng_->NextInt(); + if (!IsMinusZero(x)) integers.push_back(x); + } + + int32s.push_back(0); + int32s.push_back(0); + int32s.push_back(-1); + int32s.push_back(+1); + int32s.push_back(kMinInt); + int32s.push_back(kMaxInt); + for (int i = 0; i < 10; ++i) { + int32s.push_back(rng_->NextInt()); + } + } + + Typer typer_; + JSOperatorBuilder javascript_; + Node* context_node_; + v8::base::RandomNumberGenerator* rng_; + std::vector integers; + std::vector int32s; + + Isolate* isolate() { return main_isolate(); } + Graph* graph() { return main_graph_; } + CommonOperatorBuilder* common() { return &main_common_; } + + Node* Parameter(int index = 0) { + return graph()->NewNode(common()->Parameter(index), graph()->start()); + } + + Type* TypeBinaryOp(const Operator* op, Type* lhs, Type* rhs) { + Node* p0 = Parameter(0); + Node* p1 = Parameter(1); + NodeProperties::SetBounds(p0, Bounds(lhs)); + NodeProperties::SetBounds(p1, Bounds(rhs)); + Node* n = graph()->NewNode( + op, p0, p1, context_node_, graph()->start(), graph()->start()); + typer_.Init(n); + return NodeProperties::GetBounds(n).upper; + } + + Type* RandomRange(bool int32 = false) { + std::vector& numbers = int32 ? int32s : integers; + Factory* f = isolate()->factory(); + int i = rng_->NextInt(static_cast(numbers.size())); + int j = rng_->NextInt(static_cast(numbers.size())); + i::Handle min = f->NewNumber(numbers[i]); + i::Handle max = f->NewNumber(numbers[j]); + if (min->Number() > max->Number()) std::swap(min, max); + return Type::Range(min, max, main_zone()); + } + + double RandomInt(double min, double max) { + switch (rng_->NextInt(4)) { + case 0: return min; + case 1: return max; + default: break; + } + if (min == +V8_INFINITY) return +V8_INFINITY; + if (max == -V8_INFINITY) return -V8_INFINITY; + if (min == -V8_INFINITY && max == +V8_INFINITY) { + return rng_->NextInt() * static_cast(rng_->NextInt()); + } + double result = nearbyint(min + (max - min) * rng_->NextDouble()); + if (IsMinusZero(result)) return 0; + if (std::isnan(result)) return rng_->NextInt(2) ? min : max; + DCHECK(min <= result && result <= max); + return result; + } + + double RandomInt(Type::RangeType* range) { + return RandomInt(range->Min()->Number(), range->Max()->Number()); + } + + template + void TestBinaryArithOp(const Operator* op, BinaryFunction opfun) { + for (int i = 0; i < 100; ++i) { + Type::RangeType* r1 = RandomRange()->AsRange(); + Type::RangeType* r2 = RandomRange()->AsRange(); + Type* expected_type = TypeBinaryOp(op, r1, r2); + double x1 = RandomInt(r1); + double x2 = RandomInt(r2); + double result_value = opfun(x1, x2); + Type* result_type = Type::Constant( + isolate()->factory()->NewNumber(result_value), main_zone()); + CHECK(result_type->Is(expected_type)); + } + } + + template + void TestBinaryCompareOp(const Operator* op, BinaryFunction opfun) { + for (int i = 0; i < 100; ++i) { + Type::RangeType* r1 = RandomRange()->AsRange(); + Type::RangeType* r2 = RandomRange()->AsRange(); + Type* expected_type = TypeBinaryOp(op, r1, r2); + double x1 = RandomInt(r1); + double x2 = RandomInt(r2); + bool result_value = opfun(x1, x2); + Type* result_type = Type::Constant(result_value ? + isolate()->factory()->true_value() : + isolate()->factory()->false_value(), main_zone()); + CHECK(result_type->Is(expected_type)); + } + } + + template + void TestBinaryBitOp(const Operator* op, BinaryFunction opfun) { + for (int i = 0; i < 100; ++i) { + Type::RangeType* r1 = RandomRange(true)->AsRange(); + Type::RangeType* r2 = RandomRange(true)->AsRange(); + Type* expected_type = TypeBinaryOp(op, r1, r2); + int32_t x1 = static_cast(RandomInt(r1)); + int32_t x2 = static_cast(RandomInt(r2)); + double result_value = opfun(x1, x2); + Type* result_type = Type::Constant( + isolate()->factory()->NewNumber(result_value), main_zone()); + CHECK(result_type->Is(expected_type)); + } + } +}; + + +static int32_t shift_left(int32_t x, int32_t y) { return x << y; } +static int32_t shift_right(int32_t x, int32_t y) { return x >> y; } +static int32_t bit_or(int32_t x, int32_t y) { return x | y; } +static int32_t bit_and(int32_t x, int32_t y) { return x & y; } +static int32_t bit_xor(int32_t x, int32_t y) { return x ^ y; } + + +TEST(TypeJSAdd) { + TyperTester t; + t.TestBinaryArithOp(t.javascript_.Subtract(), std::plus()); +} + + +TEST(TypeJSSubtract) { + TyperTester t; + t.TestBinaryArithOp(t.javascript_.Subtract(), std::minus()); +} + + +TEST(TypeJSMultiply) { + TyperTester t; + t.TestBinaryArithOp(t.javascript_.Multiply(), std::multiplies()); +} + + +TEST(TypeJSDivide) { + TyperTester t; + t.TestBinaryArithOp(t.javascript_.Divide(), std::divides()); +} + + +TEST(TypeJSBitwiseOr) { + TyperTester t; + t.TestBinaryBitOp(t.javascript_.BitwiseOr(), bit_or); +} + + +TEST(TypeJSBitwiseAnd) { + TyperTester t; + t.TestBinaryBitOp(t.javascript_.BitwiseAnd(), bit_and); +} + + +TEST(TypeJSBitwiseXor) { + TyperTester t; + t.TestBinaryBitOp(t.javascript_.BitwiseXor(), bit_xor); +} + + +TEST(TypeJSShiftLeft) { + TyperTester t; + t.TestBinaryBitOp(t.javascript_.ShiftLeft(), shift_left); +} + + +TEST(TypeJSShiftRight) { + TyperTester t; + t.TestBinaryBitOp(t.javascript_.ShiftRight(), shift_right); +} + + +TEST(TypeJSLessThan) { + TyperTester t; + t.TestBinaryCompareOp(t.javascript_.LessThan(), std::less()); +} + + +TEST(TypeJSLessThanOrEqual) { + TyperTester t; + t.TestBinaryCompareOp( + t.javascript_.LessThanOrEqual(), std::less_equal()); +} + + +TEST(TypeJSGreaterThan) { + TyperTester t; + t.TestBinaryCompareOp(t.javascript_.GreaterThan(), std::greater()); +} + + +TEST(TypeJSGreaterThanOrEqual) { + TyperTester t; + t.TestBinaryCompareOp( + t.javascript_.GreaterThanOrEqual(), std::greater_equal()); +} + + +TEST(TypeJSEqual) { + TyperTester t; + t.TestBinaryCompareOp(t.javascript_.Equal(), std::equal_to()); +} + + +TEST(TypeJSNotEqual) { + TyperTester t; + t.TestBinaryCompareOp(t.javascript_.NotEqual(), std::not_equal_to()); +} + + +// For numbers there's no difference between strict and non-strict equality. +TEST(TypeJSStrictEqual) { + TyperTester t; + t.TestBinaryCompareOp(t.javascript_.StrictEqual(), std::equal_to()); +} + + +TEST(TypeJSStrictNotEqual) { + TyperTester t; + t.TestBinaryCompareOp( + t.javascript_.StrictNotEqual(), std::not_equal_to()); +} diff --git a/test/cctest/test-types.cc b/test/cctest/test-types.cc index e9122b1..86a8d4e 100644 --- a/test/cctest/test-types.cc +++ b/test/cctest/test-types.cc @@ -97,7 +97,12 @@ class Types { : region_(region), rng_(isolate->random_number_generator()) { #define DECLARE_TYPE(name, value) \ name = Type::name(region); \ - types.push_back(name); + if (SmiValuesAre31Bits() || \ + (!Type::name(region)->Equals(Type::OtherSigned32()) && \ + !Type::name(region)->Equals(Type::OtherUnsigned31()))) { \ + /* Hack: Avoid generating those empty bitset types. */ \ + types.push_back(name); \ + } PROPER_BITSET_TYPE_LIST(DECLARE_TYPE) #undef DECLARE_TYPE @@ -284,11 +289,17 @@ class Types { int j = rng_->NextInt(n); #define PICK_BITSET_TYPE(type, value) \ if (j-- == 0) { \ + if (!SmiValuesAre31Bits() && \ + (Type::type(region_)->Equals(Type::OtherSigned32()) || \ + Type::type(region_)->Equals(Type::OtherUnsigned31()))) { \ + /* Hack: Avoid generating those empty bitset types. */ \ + continue; \ + } \ TypeHandle tmp = Type::Intersect( \ result, Type::type(region_), region_); \ if (tmp->Is(Type::None()) && i != 0) { \ break; \ - } { \ + } else { \ result = tmp; \ continue; \ } \ @@ -2179,6 +2190,13 @@ TEST(NowOf) { } +TEST(MinMax) { + CcTest::InitializeVM(); + ZoneTests().MinMax(); + HeapTests().MinMax(); +} + + TEST(BitsetGlb) { CcTest::InitializeVM(); ZoneTests().BitsetGlb(); -- 2.7.4