OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/bootstrapper.h" | 5 #include "src/bootstrapper.h" |
6 #include "src/compiler/graph-inl.h" | 6 #include "src/compiler/graph-inl.h" |
7 #include "src/compiler/js-operator.h" | 7 #include "src/compiler/js-operator.h" |
8 #include "src/compiler/node.h" | 8 #include "src/compiler/node.h" |
9 #include "src/compiler/node-properties-inl.h" | 9 #include "src/compiler/node-properties-inl.h" |
10 #include "src/compiler/node-properties.h" | 10 #include "src/compiler/node-properties.h" |
(...skipping 14 matching lines...) Expand all Loading... |
25 }; | 25 }; |
26 | 26 |
27 | 27 |
28 Typer::Typer(Graph* graph, MaybeHandle<Context> context) | 28 Typer::Typer(Graph* graph, MaybeHandle<Context> context) |
29 : graph_(graph), context_(context), decorator_(NULL) { | 29 : graph_(graph), context_(context), decorator_(NULL) { |
30 Zone* zone = this->zone(); | 30 Zone* zone = this->zone(); |
31 Factory* f = zone->isolate()->factory(); | 31 Factory* f = zone->isolate()->factory(); |
32 | 32 |
33 Handle<Object> zero = f->NewNumber(0); | 33 Handle<Object> zero = f->NewNumber(0); |
34 Handle<Object> one = f->NewNumber(1); | 34 Handle<Object> one = f->NewNumber(1); |
35 Handle<Object> positive_infinity = f->NewNumber(+V8_INFINITY); | 35 Handle<Object> infinity = f->NewNumber(+V8_INFINITY); |
36 Handle<Object> negative_infinity = f->NewNumber(-V8_INFINITY); | 36 Handle<Object> minusinfinity = f->NewNumber(-V8_INFINITY); |
37 | 37 |
38 negative_signed32 = Type::Union( | 38 negative_signed32 = Type::Union( |
39 Type::SignedSmall(), Type::OtherSigned32(), zone); | 39 Type::SignedSmall(), Type::OtherSigned32(), zone); |
40 non_negative_signed32 = Type::Union( | 40 non_negative_signed32 = Type::Union( |
41 Type::UnsignedSmall(), Type::OtherUnsigned31(), zone); | 41 Type::UnsignedSmall(), Type::OtherUnsigned31(), zone); |
42 undefined_or_null = Type::Union(Type::Undefined(), Type::Null(), zone); | 42 undefined_or_null = Type::Union(Type::Undefined(), Type::Null(), zone); |
43 singleton_false = Type::Constant(f->false_value(), zone); | 43 singleton_false = Type::Constant(f->false_value(), zone); |
44 singleton_true = Type::Constant(f->true_value(), zone); | 44 singleton_true = Type::Constant(f->true_value(), zone); |
45 singleton_zero = Type::Range(zero, zero, zone); | 45 singleton_zero = Type::Range(zero, zero, zone); |
46 singleton_one = Type::Range(one, one, zone); | 46 singleton_one = Type::Range(one, one, zone); |
47 zero_or_one = Type::Union(singleton_zero, singleton_one, zone); | 47 zero_or_one = Type::Union(singleton_zero, singleton_one, zone); |
48 zeroish = Type::Union( | 48 zeroish = Type::Union( |
49 singleton_zero, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone); | 49 singleton_zero, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone); |
50 falsish = Type::Union(Type::Undetectable(), | 50 falsish = Type::Union(Type::Undetectable(), |
51 Type::Union(zeroish, undefined_or_null, zone), zone); | 51 Type::Union(zeroish, undefined_or_null, zone), zone); |
52 integer = Type::Range(negative_infinity, positive_infinity, zone); | 52 integer = Type::Range(minusinfinity, infinity, zone); |
| 53 weakint = Type::Union( |
| 54 integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone); |
53 | 55 |
54 Type* number = Type::Number(); | 56 Type* number = Type::Number(); |
55 Type* signed32 = Type::Signed32(); | 57 Type* signed32 = Type::Signed32(); |
56 Type* unsigned32 = Type::Unsigned32(); | 58 Type* unsigned32 = Type::Unsigned32(); |
57 Type* integral32 = Type::Integral32(); | 59 Type* integral32 = Type::Integral32(); |
58 Type* object = Type::Object(); | 60 Type* object = Type::Object(); |
59 Type* undefined = Type::Undefined(); | 61 Type* undefined = Type::Undefined(); |
60 Type* weakint = Type::Union( | |
61 integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone); | |
62 | 62 |
63 number_fun0_ = Type::Function(number, zone); | 63 number_fun0_ = Type::Function(number, zone); |
64 number_fun1_ = Type::Function(number, number, zone); | 64 number_fun1_ = Type::Function(number, number, zone); |
65 number_fun2_ = Type::Function(number, number, number, zone); | 65 number_fun2_ = Type::Function(number, number, number, zone); |
66 weakint_fun1_ = Type::Function(weakint, number, zone); | 66 weakint_fun1_ = Type::Function(weakint, number, zone); |
67 imul_fun_ = Type::Function(signed32, integral32, integral32, zone); | 67 imul_fun_ = Type::Function(signed32, integral32, integral32, zone); |
68 random_fun_ = Type::Function(Type::Union( | 68 random_fun_ = Type::Function(Type::Union( |
69 Type::UnsignedSmall(), Type::OtherNumber(), zone), zone); | 69 Type::UnsignedSmall(), Type::OtherNumber(), zone), zone); |
70 | 70 |
71 Type* int8 = Type::Intersect( | 71 Type* int8 = Type::Intersect( |
(...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
157 Type* TypeConstant(Handle<Object> value); | 157 Type* TypeConstant(Handle<Object> value); |
158 | 158 |
159 protected: | 159 protected: |
160 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); | 160 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); |
161 DECLARE_METHOD(Start) | 161 DECLARE_METHOD(Start) |
162 VALUE_OP_LIST(DECLARE_METHOD) | 162 VALUE_OP_LIST(DECLARE_METHOD) |
163 #undef DECLARE_METHOD | 163 #undef DECLARE_METHOD |
164 | 164 |
165 Bounds BoundsOrNone(Node* node) { | 165 Bounds BoundsOrNone(Node* node) { |
166 return NodeProperties::IsTyped(node) | 166 return NodeProperties::IsTyped(node) |
167 ? NodeProperties::GetBounds(node) : Bounds(Type::None(zone())); | 167 ? NodeProperties::GetBounds(node) : Bounds(Type::None()); |
168 } | 168 } |
169 | 169 |
170 Bounds Operand(Node* node, int i) { | 170 Bounds Operand(Node* node, int i) { |
171 Node* operand_node = NodeProperties::GetValueInput(node, i); | 171 Node* operand_node = NodeProperties::GetValueInput(node, i); |
172 return BoundsOrNone(operand_node); | 172 return BoundsOrNone(operand_node); |
173 } | 173 } |
174 | 174 |
175 Bounds ContextOperand(Node* node) { | 175 Bounds ContextOperand(Node* node) { |
176 Bounds result = BoundsOrNone(NodeProperties::GetContextInput(node)); | 176 Bounds result = BoundsOrNone(NodeProperties::GetContextInput(node)); |
177 DCHECK(result.upper->Maybe(Type::Internal())); | 177 DCHECK(result.upper->Maybe(Type::Internal())); |
(...skipping 12 matching lines...) Expand all Loading... |
190 MaybeHandle<Context> context_; | 190 MaybeHandle<Context> context_; |
191 | 191 |
192 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); | 192 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); |
193 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); | 193 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); |
194 | 194 |
195 Bounds TypeUnaryOp(Node* node, UnaryTyperFun); | 195 Bounds TypeUnaryOp(Node* node, UnaryTyperFun); |
196 Bounds TypeBinaryOp(Node* node, BinaryTyperFun); | 196 Bounds TypeBinaryOp(Node* node, BinaryTyperFun); |
197 | 197 |
198 static Type* Invert(Type*, Typer*); | 198 static Type* Invert(Type*, Typer*); |
199 static Type* FalsifyUndefined(Type*, Typer*); | 199 static Type* FalsifyUndefined(Type*, Typer*); |
| 200 static Type* Rangify(Type*, Typer*); |
200 | 201 |
201 static Type* ToPrimitive(Type*, Typer*); | 202 static Type* ToPrimitive(Type*, Typer*); |
202 static Type* ToBoolean(Type*, Typer*); | 203 static Type* ToBoolean(Type*, Typer*); |
203 static Type* ToNumber(Type*, Typer*); | 204 static Type* ToNumber(Type*, Typer*); |
204 static Type* ToString(Type*, Typer*); | 205 static Type* ToString(Type*, Typer*); |
205 static Type* NumberToInt32(Type*, Typer*); | 206 static Type* NumberToInt32(Type*, Typer*); |
206 static Type* NumberToUint32(Type*, Typer*); | 207 static Type* NumberToUint32(Type*, Typer*); |
207 | 208 |
208 static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*); | 209 static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*); |
209 static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*); | 210 static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*); |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
243 }; | 244 }; |
244 | 245 |
245 | 246 |
246 class Typer::NarrowVisitor : public Typer::Visitor { | 247 class Typer::NarrowVisitor : public Typer::Visitor { |
247 public: | 248 public: |
248 explicit NarrowVisitor(Typer* typer) : Visitor(typer) {} | 249 explicit NarrowVisitor(Typer* typer) : Visitor(typer) {} |
249 | 250 |
250 GenericGraphVisit::Control Pre(Node* node) { | 251 GenericGraphVisit::Control Pre(Node* node) { |
251 if (OperatorProperties::HasValueOutput(node->op())) { | 252 if (OperatorProperties::HasValueOutput(node->op())) { |
252 Bounds previous = NodeProperties::GetBounds(node); | 253 Bounds previous = NodeProperties::GetBounds(node); |
253 Bounds bounds = TypeNode(node); | 254 Bounds current = TypeNode(node); |
254 NodeProperties::SetBounds(node, Bounds::Both(bounds, previous, zone())); | 255 NodeProperties::SetBounds(node, Bounds::Both(current, previous, zone())); |
255 DCHECK(bounds.Narrows(previous)); | 256 DCHECK(current.Narrows(previous)); |
256 // Stop when nothing changed (but allow re-entry in case it does later). | 257 // Stop when nothing changed (but allow re-entry in case it does later). |
257 return previous.Narrows(bounds) | 258 return previous.Narrows(current) |
258 ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER; | 259 ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER; |
259 } else { | 260 } else { |
260 return GenericGraphVisit::SKIP; | 261 return GenericGraphVisit::SKIP; |
261 } | 262 } |
262 } | 263 } |
263 | 264 |
264 GenericGraphVisit::Control Post(Node* node) { | 265 GenericGraphVisit::Control Post(Node* node) { |
265 return GenericGraphVisit::REENTER; | 266 return GenericGraphVisit::REENTER; |
266 } | 267 } |
267 }; | 268 }; |
268 | 269 |
269 | 270 |
270 class Typer::WidenVisitor : public Typer::Visitor { | 271 class Typer::WidenVisitor : public Typer::Visitor { |
271 public: | 272 public: |
272 explicit WidenVisitor(Typer* typer) : Visitor(typer) {} | 273 explicit WidenVisitor(Typer* typer) : Visitor(typer) {} |
273 | 274 |
274 GenericGraphVisit::Control Pre(Node* node) { | 275 GenericGraphVisit::Control Pre(Node* node) { |
275 if (OperatorProperties::HasValueOutput(node->op())) { | 276 if (OperatorProperties::HasValueOutput(node->op())) { |
276 Bounds previous = BoundsOrNone(node); | 277 Bounds previous = BoundsOrNone(node); |
277 Bounds bounds = TypeNode(node); | 278 Bounds current = TypeNode(node); |
278 DCHECK(previous.lower->Is(bounds.lower)); | 279 DCHECK(previous.lower->Is(current.lower)); |
279 DCHECK(previous.upper->Is(bounds.upper)); | 280 DCHECK(previous.upper->Is(current.upper)); |
280 NodeProperties::SetBounds(node, bounds); | 281 |
| 282 // Speed up termination in the presence of range types: |
| 283 current.upper = MaybeWeaken(current.upper, previous.upper); |
| 284 current.lower = MaybeWeaken(current.lower, previous.lower); |
| 285 |
| 286 NodeProperties::SetBounds(node, current); |
281 // Stop when nothing changed (but allow re-entry in case it does later). | 287 // Stop when nothing changed (but allow re-entry in case it does later). |
282 return bounds.Narrows(previous) | 288 return previous.Narrows(current) && current.Narrows(previous) |
283 ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER; | 289 ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER; |
284 } else { | 290 } else { |
285 return GenericGraphVisit::SKIP; | 291 return GenericGraphVisit::SKIP; |
286 } | 292 } |
287 } | 293 } |
288 | 294 |
289 GenericGraphVisit::Control Post(Node* node) { | 295 GenericGraphVisit::Control Post(Node* node) { |
290 return GenericGraphVisit::REENTER; | 296 return GenericGraphVisit::REENTER; |
291 } | 297 } |
| 298 |
| 299 private: |
| 300 Type* MaybeWeaken(Type* current, Type* previous) { |
| 301 if (current->IsRange() && previous->IsRange() && !current->Is(previous)) { |
| 302 return current->AsRange()->Weaken(zone()); |
| 303 } |
| 304 return current; |
| 305 } |
292 }; | 306 }; |
293 | 307 |
294 | 308 |
295 void Typer::Run() { | 309 void Typer::Run() { |
296 RunVisitor typing(this); | 310 RunVisitor typing(this); |
297 graph_->VisitNodeInputsFromEnd(&typing); | 311 graph_->VisitNodeInputsFromEnd(&typing); |
298 // Find least fixpoint. | 312 // Find least fixpoint. |
299 WidenVisitor widen(this); | 313 WidenVisitor widen(this); |
300 for (NodeSetIter it = typing.redo.begin(); it != typing.redo.end(); ++it) { | 314 for (NodeSetIter it = typing.redo.begin(); it != typing.redo.end(); ++it) { |
301 graph_->VisitNodeUsesFrom(*it, &widen); | 315 graph_->VisitNodeUsesFrom(*it, &widen); |
(...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
372 return type; | 386 return type; |
373 } | 387 } |
374 | 388 |
375 | 389 |
376 Type* Typer::Visitor::FalsifyUndefined(Type* type, Typer* t) { | 390 Type* Typer::Visitor::FalsifyUndefined(Type* type, Typer* t) { |
377 if (type->Is(Type::Undefined())) return t->singleton_false; | 391 if (type->Is(Type::Undefined())) return t->singleton_false; |
378 return type; | 392 return type; |
379 } | 393 } |
380 | 394 |
381 | 395 |
| 396 Type* Typer::Visitor::Rangify(Type* type, Typer* t) { |
| 397 if (!type->Is(t->integer)) return type; // Give up. |
| 398 if (type->IsRange()) return type; // Shortcut. |
| 399 Factory* f = t->isolate()->factory(); |
| 400 return Type::Range( |
| 401 f->NewNumber(type->Min()), f->NewNumber(type->Max()), t->zone()); |
| 402 } |
| 403 |
| 404 |
382 // Type conversion. | 405 // Type conversion. |
383 | 406 |
384 | 407 |
385 Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) { | 408 Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) { |
386 if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) { | 409 if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) { |
387 return type; | 410 return type; |
388 } | 411 } |
389 return Type::Primitive(); | 412 return Type::Primitive(); |
390 } | 413 } |
391 | 414 |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
446 | 469 |
447 // Common operators. | 470 // Common operators. |
448 | 471 |
449 | 472 |
450 Bounds Typer::Visitor::TypeParameter(Node* node) { | 473 Bounds Typer::Visitor::TypeParameter(Node* node) { |
451 return Bounds::Unbounded(zone()); | 474 return Bounds::Unbounded(zone()); |
452 } | 475 } |
453 | 476 |
454 | 477 |
455 Bounds Typer::Visitor::TypeInt32Constant(Node* node) { | 478 Bounds Typer::Visitor::TypeInt32Constant(Node* node) { |
456 Factory* f = zone()->isolate()->factory(); | 479 Factory* f = isolate()->factory(); |
457 Handle<Object> number = f->NewNumber(OpParameter<int32_t>(node)); | 480 Handle<Object> number = f->NewNumber(OpParameter<int32_t>(node)); |
458 return Bounds(Type::Intersect( | 481 return Bounds(Type::Intersect( |
459 Type::Range(number, number, zone()), Type::UntaggedInt32(), zone())); | 482 Type::Range(number, number, zone()), Type::UntaggedInt32(), zone())); |
460 } | 483 } |
461 | 484 |
462 | 485 |
463 Bounds Typer::Visitor::TypeInt64Constant(Node* node) { | 486 Bounds Typer::Visitor::TypeInt64Constant(Node* node) { |
464 return Bounds(Type::Internal()); // TODO(rossberg): Add int64 bitset type? | 487 return Bounds(Type::Internal()); // TODO(rossberg): Add int64 bitset type? |
465 } | 488 } |
466 | 489 |
467 | 490 |
468 Bounds Typer::Visitor::TypeFloat32Constant(Node* node) { | 491 Bounds Typer::Visitor::TypeFloat32Constant(Node* node) { |
469 return Bounds(Type::Intersect( | 492 return Bounds(Type::Intersect( |
470 Type::Of(OpParameter<float>(node), zone()), | 493 Type::Of(OpParameter<float>(node), zone()), |
471 Type::UntaggedFloat32(), zone())); | 494 Type::UntaggedFloat32(), zone())); |
472 } | 495 } |
473 | 496 |
474 | 497 |
475 Bounds Typer::Visitor::TypeFloat64Constant(Node* node) { | 498 Bounds Typer::Visitor::TypeFloat64Constant(Node* node) { |
476 return Bounds(Type::Intersect( | 499 return Bounds(Type::Intersect( |
477 Type::Of(OpParameter<double>(node), zone()), | 500 Type::Of(OpParameter<double>(node), zone()), |
478 Type::UntaggedFloat64(), zone())); | 501 Type::UntaggedFloat64(), zone())); |
479 } | 502 } |
480 | 503 |
481 | 504 |
482 Bounds Typer::Visitor::TypeNumberConstant(Node* node) { | 505 Bounds Typer::Visitor::TypeNumberConstant(Node* node) { |
483 Factory* f = zone()->isolate()->factory(); | 506 Factory* f = isolate()->factory(); |
484 return Bounds(Type::Constant( | 507 return Bounds(Type::Constant( |
485 f->NewNumber(OpParameter<double>(node)), zone())); | 508 f->NewNumber(OpParameter<double>(node)), zone())); |
486 } | 509 } |
487 | 510 |
488 | 511 |
489 Bounds Typer::Visitor::TypeHeapConstant(Node* node) { | 512 Bounds Typer::Visitor::TypeHeapConstant(Node* node) { |
490 return Bounds(TypeConstant(OpParameter<Unique<Object> >(node).handle())); | 513 return Bounds(TypeConstant(OpParameter<Unique<Object> >(node).handle())); |
491 } | 514 } |
492 | 515 |
493 | 516 |
(...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
650 Type* Typer::Visitor::JSGreaterThanOrEqualTyper( | 673 Type* Typer::Visitor::JSGreaterThanOrEqualTyper( |
651 Type* lhs, Type* rhs, Typer* t) { | 674 Type* lhs, Type* rhs, Typer* t) { |
652 return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t); | 675 return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t); |
653 } | 676 } |
654 | 677 |
655 | 678 |
656 // JS bitwise operators. | 679 // JS bitwise operators. |
657 | 680 |
658 | 681 |
659 Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) { | 682 Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) { |
660 Factory* f = t->zone()->isolate()->factory(); | 683 Factory* f = t->isolate()->factory(); |
661 lhs = NumberToInt32(ToNumber(lhs, t), t); | 684 lhs = NumberToInt32(ToNumber(lhs, t), t); |
662 rhs = NumberToInt32(ToNumber(rhs, t), t); | 685 rhs = NumberToInt32(ToNumber(rhs, t), t); |
663 double lmin = lhs->Min(); | 686 double lmin = lhs->Min(); |
664 double rmin = rhs->Min(); | 687 double rmin = rhs->Min(); |
665 double lmax = lhs->Max(); | 688 double lmax = lhs->Max(); |
666 double rmax = rhs->Max(); | 689 double rmax = rhs->Max(); |
667 // Or-ing any two values results in a value no smaller than their minimum. | 690 // Or-ing any two values results in a value no smaller than their minimum. |
668 // Even no smaller than their maximum if both values are non-negative. | 691 // Even no smaller than their maximum if both values are non-negative. |
669 Handle<Object> min = f->NewNumber( | 692 Handle<Object> min = f->NewNumber( |
670 lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin)); | 693 lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin)); |
671 if (lmax < 0 || rmax < 0) { | 694 if (lmax < 0 || rmax < 0) { |
672 // Or-ing two values of which at least one is negative results in a negative | 695 // Or-ing two values of which at least one is negative results in a negative |
673 // value. | 696 // value. |
674 Handle<Object> max = f->NewNumber(-1); | 697 Handle<Object> max = f->NewNumber(-1); |
675 return Type::Range(min, max, t->zone()); | 698 return Type::Range(min, max, t->zone()); |
676 } | 699 } |
677 Handle<Object> max = f->NewNumber(Type::Signed32()->Max()); | 700 Handle<Object> max = f->NewNumber(Type::Signed32()->Max()); |
678 return Type::Range(min, max, t->zone()); | 701 return Type::Range(min, max, t->zone()); |
679 // TODO(neis): Be precise for singleton inputs, here and elsewhere. | 702 // TODO(neis): Be precise for singleton inputs, here and elsewhere. |
680 } | 703 } |
681 | 704 |
682 | 705 |
683 Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) { | 706 Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) { |
684 Factory* f = t->zone()->isolate()->factory(); | 707 Factory* f = t->isolate()->factory(); |
685 lhs = NumberToInt32(ToNumber(lhs, t), t); | 708 lhs = NumberToInt32(ToNumber(lhs, t), t); |
686 rhs = NumberToInt32(ToNumber(rhs, t), t); | 709 rhs = NumberToInt32(ToNumber(rhs, t), t); |
687 double lmin = lhs->Min(); | 710 double lmin = lhs->Min(); |
688 double rmin = rhs->Min(); | 711 double rmin = rhs->Min(); |
689 double lmax = lhs->Max(); | 712 double lmax = lhs->Max(); |
690 double rmax = rhs->Max(); | 713 double rmax = rhs->Max(); |
691 // And-ing any two values results in a value no larger than their maximum. | 714 // And-ing any two values results in a value no larger than their maximum. |
692 // Even no larger than their minimum if both values are non-negative. | 715 // Even no larger than their minimum if both values are non-negative. |
693 Handle<Object> max = f->NewNumber( | 716 Handle<Object> max = f->NewNumber( |
694 lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax)); | 717 lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax)); |
(...skipping 27 matching lines...) Expand all Loading... |
722 } | 745 } |
723 | 746 |
724 | 747 |
725 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) { | 748 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) { |
726 return Type::Signed32(); | 749 return Type::Signed32(); |
727 } | 750 } |
728 | 751 |
729 | 752 |
730 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) { | 753 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) { |
731 lhs = NumberToInt32(ToNumber(lhs, t), t); | 754 lhs = NumberToInt32(ToNumber(lhs, t), t); |
732 Factory* f = t->zone()->isolate()->factory(); | 755 Factory* f = t->isolate()->factory(); |
733 if (lhs->Min() >= 0) { | 756 if (lhs->Min() >= 0) { |
734 // Right-shifting a non-negative value cannot make it negative, nor larger. | 757 // Right-shifting a non-negative value cannot make it negative, nor larger. |
735 Handle<Object> min = f->NewNumber(0); | 758 Handle<Object> min = f->NewNumber(0); |
736 Handle<Object> max = f->NewNumber(lhs->Max()); | 759 Handle<Object> max = f->NewNumber(lhs->Max()); |
737 return Type::Range(min, max, t->zone()); | 760 return Type::Range(min, max, t->zone()); |
738 } | 761 } |
739 if (lhs->Max() < 0) { | 762 if (lhs->Max() < 0) { |
740 // Right-shifting a negative value cannot make it non-negative, nor smaller. | 763 // Right-shifting a negative value cannot make it non-negative, nor smaller. |
741 Handle<Object> min = f->NewNumber(lhs->Min()); | 764 Handle<Object> min = f->NewNumber(lhs->Min()); |
742 Handle<Object> max = f->NewNumber(-1); | 765 Handle<Object> max = f->NewNumber(-1); |
743 return Type::Range(min, max, t->zone()); | 766 return Type::Range(min, max, t->zone()); |
744 } | 767 } |
745 return Type::Signed32(); | 768 return Type::Signed32(); |
746 } | 769 } |
747 | 770 |
748 | 771 |
749 Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) { | 772 Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) { |
750 lhs = NumberToUint32(ToNumber(lhs, t), t); | 773 lhs = NumberToUint32(ToNumber(lhs, t), t); |
751 Factory* f = t->zone()->isolate()->factory(); | 774 Factory* f = t->isolate()->factory(); |
752 // Logical right-shifting any value cannot make it larger. | 775 // Logical right-shifting any value cannot make it larger. |
753 Handle<Object> min = f->NewNumber(0); | 776 Handle<Object> min = f->NewNumber(0); |
754 Handle<Object> max = f->NewNumber(lhs->Max()); | 777 Handle<Object> max = f->NewNumber(lhs->Max()); |
755 return Type::Range(min, max, t->zone()); | 778 return Type::Range(min, max, t->zone()); |
756 } | 779 } |
757 | 780 |
758 | 781 |
759 // JS arithmetic operators. | 782 // JS arithmetic operators. |
760 | 783 |
761 | 784 |
| 785 // Returns the array's least element, ignoring NaN. |
| 786 // There must be at least one non-NaN element. |
| 787 // Any -0 is converted to 0. |
| 788 static double array_min(double a[], size_t n) { |
| 789 DCHECK(n != 0); |
| 790 double x = a[0]; |
| 791 for (size_t i = 1; i < n; ++i) { |
| 792 x = std::min(std::isnan(a[i]) ? +V8_INFINITY : a[i], x); |
| 793 } |
| 794 DCHECK(!std::isnan(x)); |
| 795 return x == 0 ? 0 : x; // -0 -> 0 |
| 796 } |
| 797 |
| 798 |
| 799 // Returns the array's greatest element, ignoring NaN. |
| 800 // There must be at least one non-NaN element. |
| 801 // Any -0 is converted to 0. |
| 802 static double array_max(double a[], size_t n) { |
| 803 DCHECK(n != 0); |
| 804 double x = a[0]; |
| 805 for (size_t i = 1; i < n; ++i) { |
| 806 x = std::max(std::isnan(a[i]) ? -V8_INFINITY : a[i], x); |
| 807 } |
| 808 DCHECK(!std::isnan(x)); |
| 809 return x == 0 ? 0 : x; // -0 -> 0 |
| 810 } |
| 811 |
| 812 |
| 813 Type* Typer::Visitor::JSAddRanger( |
| 814 Type::RangeType* lhs, Type::RangeType* rhs, Typer* t) { |
| 815 double results[4]; |
| 816 results[0] = lhs->Min()->Number() + rhs->Min()->Number(); |
| 817 results[1] = lhs->Min()->Number() + rhs->Max()->Number(); |
| 818 results[2] = lhs->Max()->Number() + rhs->Min()->Number(); |
| 819 results[3] = lhs->Max()->Number() + rhs->Max()->Number(); |
| 820 // Since none of the inputs can be -0, the result cannot be -0 either. |
| 821 // However, it can be nan (the sum of two infinities of opposite sign). |
| 822 // On the other hand, if none of the "results" above is nan, then the actual |
| 823 // result cannot be nan either. |
| 824 int nans = 0; |
| 825 for (int i = 0; i < 4; ++i) { |
| 826 if (std::isnan(results[i])) ++nans; |
| 827 } |
| 828 if (nans == 4) return Type::NaN(); // [-inf..-inf] + [inf..inf] or vice versa |
| 829 Factory* f = t->isolate()->factory(); |
| 830 Type* range = Type::Range( |
| 831 f->NewNumber(array_min(results, 4)), f->NewNumber(array_max(results, 4)), |
| 832 t->zone()); |
| 833 return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone()); |
| 834 // Examples: |
| 835 // [-inf, -inf] + [+inf, +inf] = NaN |
| 836 // [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN |
| 837 // [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN |
| 838 // [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN |
| 839 } |
| 840 |
| 841 |
762 Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) { | 842 Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) { |
763 lhs = ToPrimitive(lhs, t); | 843 lhs = ToPrimitive(lhs, t); |
764 rhs = ToPrimitive(rhs, t); | 844 rhs = ToPrimitive(rhs, t); |
765 if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) { | 845 if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) { |
766 if (lhs->Is(Type::String()) || rhs->Is(Type::String())) { | 846 if (lhs->Is(Type::String()) || rhs->Is(Type::String())) { |
767 return Type::String(); | 847 return Type::String(); |
768 } else { | 848 } else { |
769 return Type::NumberOrString(); | 849 return Type::NumberOrString(); |
770 } | 850 } |
771 } | 851 } |
772 lhs = ToNumber(lhs, t); | 852 lhs = Rangify(ToNumber(lhs, t), t); |
773 rhs = ToNumber(rhs, t); | 853 rhs = Rangify(ToNumber(rhs, t), t); |
774 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); | 854 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); |
775 // TODO(neis): Do some analysis. | 855 if (lhs->IsRange() && rhs->IsRange()) { |
| 856 return JSAddRanger(lhs->AsRange(), rhs->AsRange(), t); |
| 857 } |
776 // TODO(neis): Deal with numeric bitsets here and elsewhere. | 858 // TODO(neis): Deal with numeric bitsets here and elsewhere. |
777 return Type::Number(); | 859 return Type::Number(); |
778 } | 860 } |
779 | 861 |
780 | 862 |
| 863 Type* Typer::Visitor::JSSubtractRanger( |
| 864 Type::RangeType* lhs, Type::RangeType* rhs, Typer* t) { |
| 865 double results[4]; |
| 866 results[0] = lhs->Min()->Number() - rhs->Min()->Number(); |
| 867 results[1] = lhs->Min()->Number() - rhs->Max()->Number(); |
| 868 results[2] = lhs->Max()->Number() - rhs->Min()->Number(); |
| 869 results[3] = lhs->Max()->Number() - rhs->Max()->Number(); |
| 870 // Since none of the inputs can be -0, the result cannot be -0. |
| 871 // However, it can be nan (the subtraction of two infinities of same sign). |
| 872 // On the other hand, if none of the "results" above is nan, then the actual |
| 873 // result cannot be nan either. |
| 874 int nans = 0; |
| 875 for (int i = 0; i < 4; ++i) { |
| 876 if (std::isnan(results[i])) ++nans; |
| 877 } |
| 878 if (nans == 4) return Type::NaN(); // [inf..inf] - [inf..inf] (all same sign) |
| 879 Factory* f = t->isolate()->factory(); |
| 880 Type* range = Type::Range( |
| 881 f->NewNumber(array_min(results, 4)), f->NewNumber(array_max(results, 4)), |
| 882 t->zone()); |
| 883 return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone()); |
| 884 // Examples: |
| 885 // [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN |
| 886 // [-inf, -inf] - [-inf, -inf] = NaN |
| 887 // [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN |
| 888 // [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN |
| 889 } |
| 890 |
| 891 |
781 Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) { | 892 Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) { |
782 lhs = ToNumber(lhs, t); | 893 lhs = Rangify(ToNumber(lhs, t), t); |
783 rhs = ToNumber(rhs, t); | 894 rhs = Rangify(ToNumber(rhs, t), t); |
784 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); | 895 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); |
785 // TODO(neis): Do some analysis. | 896 if (lhs->IsRange() && rhs->IsRange()) { |
| 897 return JSSubtractRanger(lhs->AsRange(), rhs->AsRange(), t); |
| 898 } |
786 return Type::Number(); | 899 return Type::Number(); |
787 } | 900 } |
788 | 901 |
789 | 902 |
| 903 Type* Typer::Visitor::JSMultiplyRanger( |
| 904 Type::RangeType* lhs, Type::RangeType* rhs, Typer* t) { |
| 905 double results[4]; |
| 906 double lmin = lhs->Min()->Number(); |
| 907 double lmax = lhs->Max()->Number(); |
| 908 double rmin = rhs->Min()->Number(); |
| 909 double rmax = rhs->Max()->Number(); |
| 910 results[0] = lmin * rmin; |
| 911 results[1] = lmin * rmax; |
| 912 results[2] = lmax * rmin; |
| 913 results[3] = lmax * rmax; |
| 914 // If the result may be nan, we give up on calculating a precise type, because |
| 915 // the discontinuity makes it too complicated. Note that even if none of the |
| 916 // "results" above is nan, the actual result may still be, so we have to do a |
| 917 // different check: |
| 918 bool maybe_nan = |
| 919 (lhs->Maybe(t->singleton_zero) && |
| 920 (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) || |
| 921 (rhs->Maybe(t->singleton_zero) && |
| 922 (lmin == -V8_INFINITY || lmax == +V8_INFINITY)); |
| 923 if (maybe_nan) return t->weakint; // Giving up. |
| 924 bool maybe_minuszero = |
| 925 (lhs->Maybe(t->singleton_zero) && rmin < 0) || |
| 926 (rhs->Maybe(t->singleton_zero) && lmin < 0); |
| 927 Factory* f = t->isolate()->factory(); |
| 928 Type* range = Type::Range( |
| 929 f->NewNumber(array_min(results, 4)), f->NewNumber(array_max(results, 4)), |
| 930 t->zone()); |
| 931 return maybe_minuszero ? |
| 932 Type::Union(range, Type::MinusZero(), t->zone()) : range; |
| 933 } |
| 934 |
| 935 |
790 Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) { | 936 Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) { |
791 lhs = ToNumber(lhs, t); | 937 lhs = Rangify(ToNumber(lhs, t), t); |
792 rhs = ToNumber(rhs, t); | 938 rhs = Rangify(ToNumber(rhs, t), t); |
793 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); | 939 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); |
794 // TODO(neis): Do some analysis. | 940 if (lhs->IsRange() && rhs->IsRange()) { |
| 941 return JSMultiplyRanger(lhs->AsRange(), rhs->AsRange(), t); |
| 942 } |
795 return Type::Number(); | 943 return Type::Number(); |
796 } | 944 } |
797 | 945 |
798 | 946 |
799 Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) { | 947 Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) { |
800 lhs = ToNumber(lhs, t); | 948 lhs = ToNumber(lhs, t); |
801 rhs = ToNumber(rhs, t); | 949 rhs = ToNumber(rhs, t); |
802 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); | 950 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); |
803 // TODO(neis): Do some analysis. | 951 // Division is tricky, so all we do is try ruling out nan. |
804 return Type::Number(); | 952 // TODO(neis): try ruling out -0 as well? |
| 953 bool maybe_nan = |
| 954 lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN()) || |
| 955 rhs->Maybe(t->singleton_zero) || |
| 956 ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) && |
| 957 (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY)); |
| 958 return maybe_nan ? Type::Number() : Type::OrderedNumber(); |
805 } | 959 } |
806 | 960 |
807 | 961 |
808 Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) { | 962 Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) { |
809 lhs = ToNumber(lhs, t); | 963 lhs = ToNumber(lhs, t); |
810 rhs = ToNumber(rhs, t); | 964 rhs = ToNumber(rhs, t); |
811 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); | 965 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); |
812 // TODO(neis): Do some analysis. | 966 // TODO(neis): Do some analysis. |
813 return Type::Number(); | 967 return Type::Number(); |
814 } | 968 } |
(...skipping 800 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1615 return typer_->float64_array_fun_; | 1769 return typer_->float64_array_fun_; |
1616 } | 1770 } |
1617 } | 1771 } |
1618 } | 1772 } |
1619 return Type::Constant(value, zone()); | 1773 return Type::Constant(value, zone()); |
1620 } | 1774 } |
1621 | 1775 |
1622 } | 1776 } |
1623 } | 1777 } |
1624 } // namespace v8::internal::compiler | 1778 } // namespace v8::internal::compiler |
OLD | NEW |