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

Side by Side Diff: src/compiler/typer.cc

Issue 636283009: [turbofan] Use range types to type and lower arithmetic ops. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Rename MaybeWeaken and rebase Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/compiler/typer.h ('k') | src/types.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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"
11 #include "src/compiler/simplified-operator.h" 11 #include "src/compiler/simplified-operator.h"
12 #include "src/compiler/typer.h" 12 #include "src/compiler/typer.h"
13 13
14 namespace v8 { 14 namespace v8 {
15 namespace internal { 15 namespace internal {
16 namespace compiler { 16 namespace compiler {
17 17
18 class Typer::Decorator : public GraphDecorator { 18 class Typer::Decorator : public GraphDecorator {
19 public: 19 public:
20 explicit Decorator(Typer* typer) : typer_(typer) {} 20 explicit Decorator(Typer* typer) : typer_(typer) {}
21 virtual void Decorate(Node* node); 21 virtual void Decorate(Node* node);
22 22
23 private: 23 private:
24 Typer* typer_; 24 Typer* typer_;
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),
30 context_(context),
31 decorator_(NULL),
32 weaken_min_limits_(graph->zone()),
33 weaken_max_limits_(graph->zone()) {
30 Zone* zone = this->zone(); 34 Zone* zone = this->zone();
31 Factory* f = zone->isolate()->factory(); 35 Factory* f = zone->isolate()->factory();
32 36
33 Handle<Object> zero = f->NewNumber(0); 37 Handle<Object> zero = f->NewNumber(0);
34 Handle<Object> one = f->NewNumber(1); 38 Handle<Object> one = f->NewNumber(1);
35 Handle<Object> positive_infinity = f->NewNumber(+V8_INFINITY); 39 Handle<Object> infinity = f->NewNumber(+V8_INFINITY);
36 Handle<Object> negative_infinity = f->NewNumber(-V8_INFINITY); 40 Handle<Object> minusinfinity = f->NewNumber(-V8_INFINITY);
37 41
38 negative_signed32 = Type::Union( 42 negative_signed32 = Type::Union(
39 Type::SignedSmall(), Type::OtherSigned32(), zone); 43 Type::SignedSmall(), Type::OtherSigned32(), zone);
40 non_negative_signed32 = Type::Union( 44 non_negative_signed32 = Type::Union(
41 Type::UnsignedSmall(), Type::OtherUnsigned31(), zone); 45 Type::UnsignedSmall(), Type::OtherUnsigned31(), zone);
42 undefined_or_null = Type::Union(Type::Undefined(), Type::Null(), zone); 46 undefined_or_null = Type::Union(Type::Undefined(), Type::Null(), zone);
43 singleton_false = Type::Constant(f->false_value(), zone); 47 singleton_false = Type::Constant(f->false_value(), zone);
44 singleton_true = Type::Constant(f->true_value(), zone); 48 singleton_true = Type::Constant(f->true_value(), zone);
45 singleton_zero = Type::Range(zero, zero, zone); 49 singleton_zero = Type::Range(zero, zero, zone);
46 singleton_one = Type::Range(one, one, zone); 50 singleton_one = Type::Range(one, one, zone);
47 zero_or_one = Type::Union(singleton_zero, singleton_one, zone); 51 zero_or_one = Type::Union(singleton_zero, singleton_one, zone);
48 zeroish = Type::Union( 52 zeroish = Type::Union(
49 singleton_zero, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone); 53 singleton_zero, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
50 falsish = Type::Union(Type::Undetectable(), 54 falsish = Type::Union(Type::Undetectable(),
51 Type::Union(zeroish, undefined_or_null, zone), zone); 55 Type::Union(zeroish, undefined_or_null, zone), zone);
52 integer = Type::Range(negative_infinity, positive_infinity, zone); 56 integer = Type::Range(minusinfinity, infinity, zone);
57 weakint = Type::Union(
58 integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
53 59
54 Type* number = Type::Number(); 60 Type* number = Type::Number();
55 Type* signed32 = Type::Signed32(); 61 Type* signed32 = Type::Signed32();
56 Type* unsigned32 = Type::Unsigned32(); 62 Type* unsigned32 = Type::Unsigned32();
57 Type* integral32 = Type::Integral32(); 63 Type* integral32 = Type::Integral32();
58 Type* object = Type::Object(); 64 Type* object = Type::Object();
59 Type* undefined = Type::Undefined(); 65 Type* undefined = Type::Undefined();
60 Type* weakint = Type::Union(
61 integer, Type::Union(Type::NaN(), Type::MinusZero(), zone), zone);
62 66
63 number_fun0_ = Type::Function(number, zone); 67 number_fun0_ = Type::Function(number, zone);
64 number_fun1_ = Type::Function(number, number, zone); 68 number_fun1_ = Type::Function(number, number, zone);
65 number_fun2_ = Type::Function(number, number, number, zone); 69 number_fun2_ = Type::Function(number, number, number, zone);
66 weakint_fun1_ = Type::Function(weakint, number, zone); 70 weakint_fun1_ = Type::Function(weakint, number, zone);
67 imul_fun_ = Type::Function(signed32, integral32, integral32, zone); 71 imul_fun_ = Type::Function(signed32, integral32, integral32, zone);
68 clz32_fun_ = Type::Function( 72 clz32_fun_ = Type::Function(
69 Type::Range(zero, f->NewNumber(32), zone), number, zone); 73 Type::Range(zero, f->NewNumber(32), zone), number, zone);
70 random_fun_ = Type::Function(Type::Union( 74 random_fun_ = Type::Function(Type::Union(
71 Type::UnsignedSmall(), Type::OtherNumber(), zone), zone); 75 Type::UnsignedSmall(), Type::OtherNumber(), zone), zone);
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after
106 array_buffer_fun_ = Type::Function(buffer, unsigned32, zone); 110 array_buffer_fun_ = Type::Function(buffer, unsigned32, zone);
107 int8_array_fun_ = Type::Function(int8_array, arg1, arg2, arg3, zone); 111 int8_array_fun_ = Type::Function(int8_array, arg1, arg2, arg3, zone);
108 int16_array_fun_ = Type::Function(int16_array, arg1, arg2, arg3, zone); 112 int16_array_fun_ = Type::Function(int16_array, arg1, arg2, arg3, zone);
109 int32_array_fun_ = Type::Function(int32_array, arg1, arg2, arg3, zone); 113 int32_array_fun_ = Type::Function(int32_array, arg1, arg2, arg3, zone);
110 uint8_array_fun_ = Type::Function(uint8_array, arg1, arg2, arg3, zone); 114 uint8_array_fun_ = Type::Function(uint8_array, arg1, arg2, arg3, zone);
111 uint16_array_fun_ = Type::Function(uint16_array, arg1, arg2, arg3, zone); 115 uint16_array_fun_ = Type::Function(uint16_array, arg1, arg2, arg3, zone);
112 uint32_array_fun_ = Type::Function(uint32_array, arg1, arg2, arg3, zone); 116 uint32_array_fun_ = Type::Function(uint32_array, arg1, arg2, arg3, zone);
113 float32_array_fun_ = Type::Function(float32_array, arg1, arg2, arg3, zone); 117 float32_array_fun_ = Type::Function(float32_array, arg1, arg2, arg3, zone);
114 float64_array_fun_ = Type::Function(float64_array, arg1, arg2, arg3, zone); 118 float64_array_fun_ = Type::Function(float64_array, arg1, arg2, arg3, zone);
115 119
120 const int limits_count = 20;
121
122 weaken_min_limits_.reserve(limits_count + 1);
123 weaken_max_limits_.reserve(limits_count + 1);
124
125 double limit = 1 << 30;
126 weaken_min_limits_.push_back(f->NewNumber(0));
127 weaken_max_limits_.push_back(f->NewNumber(0));
128 for (int i = 0; i < limits_count; i++) {
129 weaken_min_limits_.push_back(f->NewNumber(-limit));
130 weaken_max_limits_.push_back(f->NewNumber(limit - 1));
131 limit *= 2;
132 }
133
116 decorator_ = new (zone) Decorator(this); 134 decorator_ = new (zone) Decorator(this);
117 graph_->AddDecorator(decorator_); 135 graph_->AddDecorator(decorator_);
118 } 136 }
119 137
120 138
121 Typer::~Typer() { 139 Typer::~Typer() {
122 graph_->RemoveDecorator(decorator_); 140 graph_->RemoveDecorator(decorator_);
123 } 141 }
124 142
125 143
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
158 176
159 Type* TypeConstant(Handle<Object> value); 177 Type* TypeConstant(Handle<Object> value);
160 178
161 protected: 179 protected:
162 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node); 180 #define DECLARE_METHOD(x) inline Bounds Type##x(Node* node);
163 DECLARE_METHOD(Start) 181 DECLARE_METHOD(Start)
164 VALUE_OP_LIST(DECLARE_METHOD) 182 VALUE_OP_LIST(DECLARE_METHOD)
165 #undef DECLARE_METHOD 183 #undef DECLARE_METHOD
166 184
167 Bounds BoundsOrNone(Node* node) { 185 Bounds BoundsOrNone(Node* node) {
168 return NodeProperties::IsTyped(node) 186 return NodeProperties::IsTyped(node) ? NodeProperties::GetBounds(node)
169 ? NodeProperties::GetBounds(node) : Bounds(Type::None(zone())); 187 : Bounds(Type::None());
170 } 188 }
171 189
172 Bounds Operand(Node* node, int i) { 190 Bounds Operand(Node* node, int i) {
173 Node* operand_node = NodeProperties::GetValueInput(node, i); 191 Node* operand_node = NodeProperties::GetValueInput(node, i);
174 return BoundsOrNone(operand_node); 192 return BoundsOrNone(operand_node);
175 } 193 }
176 194
177 Bounds ContextOperand(Node* node) { 195 Bounds ContextOperand(Node* node) {
178 Bounds result = BoundsOrNone(NodeProperties::GetContextInput(node)); 196 Bounds result = BoundsOrNone(NodeProperties::GetContextInput(node));
179 DCHECK(result.upper->Maybe(Type::Internal())); 197 DCHECK(result.upper->Maybe(Type::Internal()));
180 // TODO(rossberg): More precisely, instead of the above assertion, we should 198 // TODO(rossberg): More precisely, instead of the above assertion, we should
181 // back-propagate the constraint that it has to be a subtype of Internal. 199 // back-propagate the constraint that it has to be a subtype of Internal.
182 return result; 200 return result;
183 } 201 }
184 202
203 Type* Weaken(Type* current_type, Type* previous_type);
204
185 Zone* zone() { return typer_->zone(); } 205 Zone* zone() { return typer_->zone(); }
186 Isolate* isolate() { return typer_->isolate(); } 206 Isolate* isolate() { return typer_->isolate(); }
187 Graph* graph() { return typer_->graph(); } 207 Graph* graph() { return typer_->graph(); }
188 MaybeHandle<Context> context() { return typer_->context(); } 208 MaybeHandle<Context> context() { return typer_->context(); }
189 209
190 private: 210 private:
191 Typer* typer_; 211 Typer* typer_;
192 MaybeHandle<Context> context_; 212 MaybeHandle<Context> context_;
193 213
194 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); 214 typedef Type* (*UnaryTyperFun)(Type*, Typer* t);
195 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); 215 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t);
196 216
197 Bounds TypeUnaryOp(Node* node, UnaryTyperFun); 217 Bounds TypeUnaryOp(Node* node, UnaryTyperFun);
198 Bounds TypeBinaryOp(Node* node, BinaryTyperFun); 218 Bounds TypeBinaryOp(Node* node, BinaryTyperFun);
199 219
200 static Type* Invert(Type*, Typer*); 220 static Type* Invert(Type*, Typer*);
201 static Type* FalsifyUndefined(Type*, Typer*); 221 static Type* FalsifyUndefined(Type*, Typer*);
222 static Type* Rangify(Type*, Typer*);
202 223
203 static Type* ToPrimitive(Type*, Typer*); 224 static Type* ToPrimitive(Type*, Typer*);
204 static Type* ToBoolean(Type*, Typer*); 225 static Type* ToBoolean(Type*, Typer*);
205 static Type* ToNumber(Type*, Typer*); 226 static Type* ToNumber(Type*, Typer*);
206 static Type* ToString(Type*, Typer*); 227 static Type* ToString(Type*, Typer*);
207 static Type* NumberToInt32(Type*, Typer*); 228 static Type* NumberToInt32(Type*, Typer*);
208 static Type* NumberToUint32(Type*, Typer*); 229 static Type* NumberToUint32(Type*, Typer*);
209 230
210 static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*); 231 static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*);
211 static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*); 232 static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*);
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after
245 }; 266 };
246 267
247 268
248 class Typer::NarrowVisitor : public Typer::Visitor { 269 class Typer::NarrowVisitor : public Typer::Visitor {
249 public: 270 public:
250 explicit NarrowVisitor(Typer* typer) : Visitor(typer) {} 271 explicit NarrowVisitor(Typer* typer) : Visitor(typer) {}
251 272
252 GenericGraphVisit::Control Pre(Node* node) { 273 GenericGraphVisit::Control Pre(Node* node) {
253 if (OperatorProperties::HasValueOutput(node->op())) { 274 if (OperatorProperties::HasValueOutput(node->op())) {
254 Bounds previous = NodeProperties::GetBounds(node); 275 Bounds previous = NodeProperties::GetBounds(node);
255 Bounds bounds = TypeNode(node); 276 Bounds current = TypeNode(node);
256 NodeProperties::SetBounds(node, Bounds::Both(bounds, previous, zone())); 277 NodeProperties::SetBounds(node, Bounds::Both(current, previous, zone()));
257 DCHECK(bounds.Narrows(previous)); 278 DCHECK(current.Narrows(previous));
258 // Stop when nothing changed (but allow re-entry in case it does later). 279 // Stop when nothing changed (but allow re-entry in case it does later).
259 return previous.Narrows(bounds) 280 return previous.Narrows(current) ? GenericGraphVisit::DEFER
260 ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER; 281 : GenericGraphVisit::REENTER;
261 } else { 282 } else {
262 return GenericGraphVisit::SKIP; 283 return GenericGraphVisit::SKIP;
263 } 284 }
264 } 285 }
265 286
266 GenericGraphVisit::Control Post(Node* node) { 287 GenericGraphVisit::Control Post(Node* node) {
267 return GenericGraphVisit::REENTER; 288 return GenericGraphVisit::REENTER;
268 } 289 }
269 }; 290 };
270 291
271 292
272 class Typer::WidenVisitor : public Typer::Visitor { 293 class Typer::WidenVisitor : public Typer::Visitor {
273 public: 294 public:
274 explicit WidenVisitor(Typer* typer) : Visitor(typer) {} 295 explicit WidenVisitor(Typer* typer) : Visitor(typer) {}
275 296
276 GenericGraphVisit::Control Pre(Node* node) { 297 GenericGraphVisit::Control Pre(Node* node) {
277 if (OperatorProperties::HasValueOutput(node->op())) { 298 if (OperatorProperties::HasValueOutput(node->op())) {
278 Bounds previous = BoundsOrNone(node); 299 Bounds previous = BoundsOrNone(node);
279 Bounds bounds = TypeNode(node); 300 Bounds current = TypeNode(node);
280 DCHECK(previous.lower->Is(bounds.lower)); 301
281 DCHECK(previous.upper->Is(bounds.upper)); 302 // Speed up termination in the presence of range types:
282 NodeProperties::SetBounds(node, bounds); 303 current.upper = Weaken(current.upper, previous.upper);
304 current.lower = Weaken(current.lower, previous.lower);
305
306 DCHECK(previous.lower->Is(current.lower));
307 DCHECK(previous.upper->Is(current.upper));
308
309 NodeProperties::SetBounds(node, current);
283 // Stop when nothing changed (but allow re-entry in case it does later). 310 // Stop when nothing changed (but allow re-entry in case it does later).
284 return bounds.Narrows(previous) 311 return previous.Narrows(current) && current.Narrows(previous)
285 ? GenericGraphVisit::DEFER : GenericGraphVisit::REENTER; 312 ? GenericGraphVisit::DEFER
313 : GenericGraphVisit::REENTER;
286 } else { 314 } else {
287 return GenericGraphVisit::SKIP; 315 return GenericGraphVisit::SKIP;
288 } 316 }
289 } 317 }
290 318
291 GenericGraphVisit::Control Post(Node* node) { 319 GenericGraphVisit::Control Post(Node* node) {
292 return GenericGraphVisit::REENTER; 320 return GenericGraphVisit::REENTER;
293 } 321 }
294 }; 322 };
295 323
(...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after
374 return type; 402 return type;
375 } 403 }
376 404
377 405
378 Type* Typer::Visitor::FalsifyUndefined(Type* type, Typer* t) { 406 Type* Typer::Visitor::FalsifyUndefined(Type* type, Typer* t) {
379 if (type->Is(Type::Undefined())) return t->singleton_false; 407 if (type->Is(Type::Undefined())) return t->singleton_false;
380 return type; 408 return type;
381 } 409 }
382 410
383 411
412 Type* Typer::Visitor::Rangify(Type* type, Typer* t) {
413 if (type->IsRange()) return type; // Shortcut.
414 if (!type->Is(t->integer)) return type; // Give up.
415 Factory* f = t->isolate()->factory();
416 return Type::Range(f->NewNumber(type->Min()), f->NewNumber(type->Max()),
417 t->zone());
418 }
419
420
384 // Type conversion. 421 // Type conversion.
385 422
386 423
387 Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) { 424 Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) {
388 if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) { 425 if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) {
389 return type; 426 return type;
390 } 427 }
391 return Type::Primitive(); 428 return Type::Primitive();
392 } 429 }
393 430
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after
448 485
449 // Common operators. 486 // Common operators.
450 487
451 488
452 Bounds Typer::Visitor::TypeParameter(Node* node) { 489 Bounds Typer::Visitor::TypeParameter(Node* node) {
453 return Bounds::Unbounded(zone()); 490 return Bounds::Unbounded(zone());
454 } 491 }
455 492
456 493
457 Bounds Typer::Visitor::TypeInt32Constant(Node* node) { 494 Bounds Typer::Visitor::TypeInt32Constant(Node* node) {
458 Factory* f = zone()->isolate()->factory(); 495 Factory* f = isolate()->factory();
459 Handle<Object> number = f->NewNumber(OpParameter<int32_t>(node)); 496 Handle<Object> number = f->NewNumber(OpParameter<int32_t>(node));
460 return Bounds(Type::Intersect( 497 return Bounds(Type::Intersect(
461 Type::Range(number, number, zone()), Type::UntaggedInt32(), zone())); 498 Type::Range(number, number, zone()), Type::UntaggedInt32(), zone()));
462 } 499 }
463 500
464 501
465 Bounds Typer::Visitor::TypeInt64Constant(Node* node) { 502 Bounds Typer::Visitor::TypeInt64Constant(Node* node) {
466 return Bounds(Type::Internal()); // TODO(rossberg): Add int64 bitset type? 503 return Bounds(Type::Internal()); // TODO(rossberg): Add int64 bitset type?
467 } 504 }
468 505
469 506
470 Bounds Typer::Visitor::TypeFloat32Constant(Node* node) { 507 Bounds Typer::Visitor::TypeFloat32Constant(Node* node) {
471 return Bounds(Type::Intersect( 508 return Bounds(Type::Intersect(
472 Type::Of(OpParameter<float>(node), zone()), 509 Type::Of(OpParameter<float>(node), zone()),
473 Type::UntaggedFloat32(), zone())); 510 Type::UntaggedFloat32(), zone()));
474 } 511 }
475 512
476 513
477 Bounds Typer::Visitor::TypeFloat64Constant(Node* node) { 514 Bounds Typer::Visitor::TypeFloat64Constant(Node* node) {
478 return Bounds(Type::Intersect( 515 return Bounds(Type::Intersect(
479 Type::Of(OpParameter<double>(node), zone()), 516 Type::Of(OpParameter<double>(node), zone()),
480 Type::UntaggedFloat64(), zone())); 517 Type::UntaggedFloat64(), zone()));
481 } 518 }
482 519
483 520
484 Bounds Typer::Visitor::TypeNumberConstant(Node* node) { 521 Bounds Typer::Visitor::TypeNumberConstant(Node* node) {
485 Factory* f = zone()->isolate()->factory(); 522 Factory* f = isolate()->factory();
486 return Bounds(Type::Constant( 523 return Bounds(Type::Constant(
487 f->NewNumber(OpParameter<double>(node)), zone())); 524 f->NewNumber(OpParameter<double>(node)), zone()));
488 } 525 }
489 526
490 527
491 Bounds Typer::Visitor::TypeHeapConstant(Node* node) { 528 Bounds Typer::Visitor::TypeHeapConstant(Node* node) {
492 return Bounds(TypeConstant(OpParameter<Unique<Object> >(node).handle())); 529 return Bounds(TypeConstant(OpParameter<Unique<Object> >(node).handle()));
493 } 530 }
494 531
495 532
(...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after
652 Type* Typer::Visitor::JSGreaterThanOrEqualTyper( 689 Type* Typer::Visitor::JSGreaterThanOrEqualTyper(
653 Type* lhs, Type* rhs, Typer* t) { 690 Type* lhs, Type* rhs, Typer* t) {
654 return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t); 691 return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t);
655 } 692 }
656 693
657 694
658 // JS bitwise operators. 695 // JS bitwise operators.
659 696
660 697
661 Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) { 698 Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) {
662 Factory* f = t->zone()->isolate()->factory(); 699 Factory* f = t->isolate()->factory();
663 lhs = NumberToInt32(ToNumber(lhs, t), t); 700 lhs = NumberToInt32(ToNumber(lhs, t), t);
664 rhs = NumberToInt32(ToNumber(rhs, t), t); 701 rhs = NumberToInt32(ToNumber(rhs, t), t);
665 double lmin = lhs->Min(); 702 double lmin = lhs->Min();
666 double rmin = rhs->Min(); 703 double rmin = rhs->Min();
667 double lmax = lhs->Max(); 704 double lmax = lhs->Max();
668 double rmax = rhs->Max(); 705 double rmax = rhs->Max();
669 // Or-ing any two values results in a value no smaller than their minimum. 706 // Or-ing any two values results in a value no smaller than their minimum.
670 // Even no smaller than their maximum if both values are non-negative. 707 // Even no smaller than their maximum if both values are non-negative.
671 Handle<Object> min = f->NewNumber( 708 Handle<Object> min = f->NewNumber(
672 lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin)); 709 lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin));
673 if (lmax < 0 || rmax < 0) { 710 if (lmax < 0 || rmax < 0) {
674 // Or-ing two values of which at least one is negative results in a negative 711 // Or-ing two values of which at least one is negative results in a negative
675 // value. 712 // value.
676 Handle<Object> max = f->NewNumber(-1); 713 Handle<Object> max = f->NewNumber(-1);
677 return Type::Range(min, max, t->zone()); 714 return Type::Range(min, max, t->zone());
678 } 715 }
679 Handle<Object> max = f->NewNumber(Type::Signed32()->Max()); 716 Handle<Object> max = f->NewNumber(Type::Signed32()->Max());
680 return Type::Range(min, max, t->zone()); 717 return Type::Range(min, max, t->zone());
681 // TODO(neis): Be precise for singleton inputs, here and elsewhere. 718 // TODO(neis): Be precise for singleton inputs, here and elsewhere.
682 } 719 }
683 720
684 721
685 Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) { 722 Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) {
686 Factory* f = t->zone()->isolate()->factory(); 723 Factory* f = t->isolate()->factory();
687 lhs = NumberToInt32(ToNumber(lhs, t), t); 724 lhs = NumberToInt32(ToNumber(lhs, t), t);
688 rhs = NumberToInt32(ToNumber(rhs, t), t); 725 rhs = NumberToInt32(ToNumber(rhs, t), t);
689 double lmin = lhs->Min(); 726 double lmin = lhs->Min();
690 double rmin = rhs->Min(); 727 double rmin = rhs->Min();
691 double lmax = lhs->Max(); 728 double lmax = lhs->Max();
692 double rmax = rhs->Max(); 729 double rmax = rhs->Max();
693 // And-ing any two values results in a value no larger than their maximum. 730 // And-ing any two values results in a value no larger than their maximum.
694 // Even no larger than their minimum if both values are non-negative. 731 // Even no larger than their minimum if both values are non-negative.
695 Handle<Object> max = f->NewNumber( 732 Handle<Object> max = f->NewNumber(
696 lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax)); 733 lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax));
(...skipping 27 matching lines...) Expand all
724 } 761 }
725 762
726 763
727 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) { 764 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) {
728 return Type::Signed32(); 765 return Type::Signed32();
729 } 766 }
730 767
731 768
732 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) { 769 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) {
733 lhs = NumberToInt32(ToNumber(lhs, t), t); 770 lhs = NumberToInt32(ToNumber(lhs, t), t);
734 Factory* f = t->zone()->isolate()->factory(); 771 Factory* f = t->isolate()->factory();
735 if (lhs->Min() >= 0) { 772 if (lhs->Min() >= 0) {
736 // Right-shifting a non-negative value cannot make it negative, nor larger. 773 // Right-shifting a non-negative value cannot make it negative, nor larger.
737 Handle<Object> min = f->NewNumber(0); 774 Handle<Object> min = f->NewNumber(0);
738 Handle<Object> max = f->NewNumber(lhs->Max()); 775 Handle<Object> max = f->NewNumber(lhs->Max());
739 return Type::Range(min, max, t->zone()); 776 return Type::Range(min, max, t->zone());
740 } 777 }
741 if (lhs->Max() < 0) { 778 if (lhs->Max() < 0) {
742 // Right-shifting a negative value cannot make it non-negative, nor smaller. 779 // Right-shifting a negative value cannot make it non-negative, nor smaller.
743 Handle<Object> min = f->NewNumber(lhs->Min()); 780 Handle<Object> min = f->NewNumber(lhs->Min());
744 Handle<Object> max = f->NewNumber(-1); 781 Handle<Object> max = f->NewNumber(-1);
745 return Type::Range(min, max, t->zone()); 782 return Type::Range(min, max, t->zone());
746 } 783 }
747 return Type::Signed32(); 784 return Type::Signed32();
748 } 785 }
749 786
750 787
751 Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) { 788 Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) {
752 lhs = NumberToUint32(ToNumber(lhs, t), t); 789 lhs = NumberToUint32(ToNumber(lhs, t), t);
753 Factory* f = t->zone()->isolate()->factory(); 790 Factory* f = t->isolate()->factory();
754 // Logical right-shifting any value cannot make it larger. 791 // Logical right-shifting any value cannot make it larger.
755 Handle<Object> min = f->NewNumber(0); 792 Handle<Object> min = f->NewNumber(0);
756 Handle<Object> max = f->NewNumber(lhs->Max()); 793 Handle<Object> max = f->NewNumber(lhs->Max());
757 return Type::Range(min, max, t->zone()); 794 return Type::Range(min, max, t->zone());
758 } 795 }
759 796
760 797
761 // JS arithmetic operators. 798 // JS arithmetic operators.
762 799
763 800
801 // Returns the array's least element, ignoring NaN.
802 // There must be at least one non-NaN element.
803 // Any -0 is converted to 0.
804 static double array_min(double a[], size_t n) {
805 DCHECK(n != 0);
806 double x = +V8_INFINITY;
807 for (size_t i = 0; i < n; ++i) {
808 if (!std::isnan(a[i])) {
809 x = std::min(a[i], x);
810 }
811 }
812 DCHECK(!std::isnan(x));
813 return x == 0 ? 0 : x; // -0 -> 0
814 }
815
816
817 // Returns the array's greatest element, ignoring NaN.
818 // There must be at least one non-NaN element.
819 // Any -0 is converted to 0.
820 static double array_max(double a[], size_t n) {
821 DCHECK(n != 0);
822 double x = -V8_INFINITY;
823 for (size_t i = 0; i < n; ++i) {
824 if (!std::isnan(a[i])) {
825 x = std::max(a[i], x);
826 }
827 }
828 DCHECK(!std::isnan(x));
829 return x == 0 ? 0 : x; // -0 -> 0
830 }
831
832
833 Type* Typer::Visitor::JSAddRanger(Type::RangeType* lhs, Type::RangeType* rhs,
834 Typer* t) {
835 double results[4];
836 results[0] = lhs->Min()->Number() + rhs->Min()->Number();
837 results[1] = lhs->Min()->Number() + rhs->Max()->Number();
838 results[2] = lhs->Max()->Number() + rhs->Min()->Number();
839 results[3] = lhs->Max()->Number() + rhs->Max()->Number();
840 // Since none of the inputs can be -0, the result cannot be -0 either.
841 // However, it can be nan (the sum of two infinities of opposite sign).
842 // On the other hand, if none of the "results" above is nan, then the actual
843 // result cannot be nan either.
844 int nans = 0;
845 for (int i = 0; i < 4; ++i) {
846 if (std::isnan(results[i])) ++nans;
847 }
848 if (nans == 4) return Type::NaN(); // [-inf..-inf] + [inf..inf] or vice versa
849 Factory* f = t->isolate()->factory();
850 Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
851 f->NewNumber(array_max(results, 4)), t->zone());
852 return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
853 // Examples:
854 // [-inf, -inf] + [+inf, +inf] = NaN
855 // [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN
856 // [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN
857 // [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN
858 }
859
860
764 Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) { 861 Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) {
765 lhs = ToPrimitive(lhs, t); 862 lhs = ToPrimitive(lhs, t);
766 rhs = ToPrimitive(rhs, t); 863 rhs = ToPrimitive(rhs, t);
767 if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) { 864 if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) {
768 if (lhs->Is(Type::String()) || rhs->Is(Type::String())) { 865 if (lhs->Is(Type::String()) || rhs->Is(Type::String())) {
769 return Type::String(); 866 return Type::String();
770 } else { 867 } else {
771 return Type::NumberOrString(); 868 return Type::NumberOrString();
772 } 869 }
773 } 870 }
774 lhs = ToNumber(lhs, t); 871 lhs = Rangify(ToNumber(lhs, t), t);
775 rhs = ToNumber(rhs, t); 872 rhs = Rangify(ToNumber(rhs, t), t);
776 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 873 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
777 // TODO(neis): Do some analysis. 874 if (lhs->IsRange() && rhs->IsRange()) {
875 return JSAddRanger(lhs->AsRange(), rhs->AsRange(), t);
876 }
778 // TODO(neis): Deal with numeric bitsets here and elsewhere. 877 // TODO(neis): Deal with numeric bitsets here and elsewhere.
779 return Type::Number(); 878 return Type::Number();
780 } 879 }
781 880
782 881
882 Type* Typer::Visitor::JSSubtractRanger(Type::RangeType* lhs,
883 Type::RangeType* rhs, Typer* t) {
884 double results[4];
885 results[0] = lhs->Min()->Number() - rhs->Min()->Number();
886 results[1] = lhs->Min()->Number() - rhs->Max()->Number();
887 results[2] = lhs->Max()->Number() - rhs->Min()->Number();
888 results[3] = lhs->Max()->Number() - rhs->Max()->Number();
889 // Since none of the inputs can be -0, the result cannot be -0.
890 // However, it can be nan (the subtraction of two infinities of same sign).
891 // On the other hand, if none of the "results" above is nan, then the actual
892 // result cannot be nan either.
893 int nans = 0;
894 for (int i = 0; i < 4; ++i) {
895 if (std::isnan(results[i])) ++nans;
896 }
897 if (nans == 4) return Type::NaN(); // [inf..inf] - [inf..inf] (all same sign)
898 Factory* f = t->isolate()->factory();
899 Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
900 f->NewNumber(array_max(results, 4)), t->zone());
901 return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone());
902 // Examples:
903 // [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN
904 // [-inf, -inf] - [-inf, -inf] = NaN
905 // [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN
906 // [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN
907 }
908
909
783 Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) { 910 Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) {
784 lhs = ToNumber(lhs, t); 911 lhs = Rangify(ToNumber(lhs, t), t);
785 rhs = ToNumber(rhs, t); 912 rhs = Rangify(ToNumber(rhs, t), t);
786 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 913 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
787 // TODO(neis): Do some analysis. 914 if (lhs->IsRange() && rhs->IsRange()) {
915 return JSSubtractRanger(lhs->AsRange(), rhs->AsRange(), t);
916 }
788 return Type::Number(); 917 return Type::Number();
789 } 918 }
790 919
791 920
921 Type* Typer::Visitor::JSMultiplyRanger(Type::RangeType* lhs,
922 Type::RangeType* rhs, Typer* t) {
923 double results[4];
924 double lmin = lhs->Min()->Number();
925 double lmax = lhs->Max()->Number();
926 double rmin = rhs->Min()->Number();
927 double rmax = rhs->Max()->Number();
928 results[0] = lmin * rmin;
929 results[1] = lmin * rmax;
930 results[2] = lmax * rmin;
931 results[3] = lmax * rmax;
932 // If the result may be nan, we give up on calculating a precise type, because
933 // the discontinuity makes it too complicated. Note that even if none of the
934 // "results" above is nan, the actual result may still be, so we have to do a
935 // different check:
936 bool maybe_nan = (lhs->Maybe(t->singleton_zero) &&
937 (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) ||
938 (rhs->Maybe(t->singleton_zero) &&
939 (lmin == -V8_INFINITY || lmax == +V8_INFINITY));
940 if (maybe_nan) return t->weakint; // Giving up.
941 bool maybe_minuszero = (lhs->Maybe(t->singleton_zero) && rmin < 0) ||
942 (rhs->Maybe(t->singleton_zero) && lmin < 0);
943 Factory* f = t->isolate()->factory();
944 Type* range = Type::Range(f->NewNumber(array_min(results, 4)),
945 f->NewNumber(array_max(results, 4)), t->zone());
946 return maybe_minuszero ? Type::Union(range, Type::MinusZero(), t->zone())
947 : range;
948 }
949
950
792 Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) { 951 Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) {
793 lhs = ToNumber(lhs, t); 952 lhs = Rangify(ToNumber(lhs, t), t);
794 rhs = ToNumber(rhs, t); 953 rhs = Rangify(ToNumber(rhs, t), t);
795 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 954 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
796 // TODO(neis): Do some analysis. 955 if (lhs->IsRange() && rhs->IsRange()) {
956 return JSMultiplyRanger(lhs->AsRange(), rhs->AsRange(), t);
957 }
797 return Type::Number(); 958 return Type::Number();
798 } 959 }
799 960
800 961
801 Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) { 962 Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) {
802 lhs = ToNumber(lhs, t); 963 lhs = ToNumber(lhs, t);
803 rhs = ToNumber(rhs, t); 964 rhs = ToNumber(rhs, t);
804 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();
805 // TODO(neis): Do some analysis. 966 // Division is tricky, so all we do is try ruling out nan.
806 return Type::Number(); 967 // TODO(neis): try ruling out -0 as well?
968 bool maybe_nan =
969 lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
970 ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
971 (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
972 return maybe_nan ? Type::Number() : Type::OrderedNumber();
807 } 973 }
808 974
809 975
810 Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) { 976 Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) {
811 lhs = ToNumber(lhs, t); 977 lhs = ToNumber(lhs, t);
812 rhs = ToNumber(rhs, t); 978 rhs = ToNumber(rhs, t);
813 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 979 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN();
814 // TODO(neis): Do some analysis. 980 // Division is tricky, so all we do is try ruling out nan.
815 return Type::Number(); 981 // TODO(neis): try ruling out -0 as well?
982 bool maybe_nan =
983 lhs->Maybe(Type::NaN()) || rhs->Maybe(t->zeroish) ||
984 ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) &&
985 (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY));
986 return maybe_nan ? Type::Number() : Type::OrderedNumber();
816 } 987 }
817 988
818 989
819 // JS unary operators. 990 // JS unary operators.
820 991
821 992
822 Type* Typer::Visitor::JSUnaryNotTyper(Type* type, Typer* t) { 993 Type* Typer::Visitor::JSUnaryNotTyper(Type* type, Typer* t) {
823 return Invert(ToBoolean(type, t), t); 994 return Invert(ToBoolean(type, t), t);
824 } 995 }
825 996
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after
883 Bounds Typer::Visitor::TypeJSLoadProperty(Node* node) { 1054 Bounds Typer::Visitor::TypeJSLoadProperty(Node* node) {
884 return TypeBinaryOp(node, JSLoadPropertyTyper); 1055 return TypeBinaryOp(node, JSLoadPropertyTyper);
885 } 1056 }
886 1057
887 1058
888 Bounds Typer::Visitor::TypeJSLoadNamed(Node* node) { 1059 Bounds Typer::Visitor::TypeJSLoadNamed(Node* node) {
889 return Bounds::Unbounded(zone()); 1060 return Bounds::Unbounded(zone());
890 } 1061 }
891 1062
892 1063
1064 // Returns a somewhat larger range if we previously assigned
1065 // a (smaller) range to this node. This is used to speed up
1066 // the fixpoint calculation in case there appears to be a loop
1067 // in the graph. In the current implementation, we are
1068 // increasing the limits to the closest power of two.
1069 Type* Typer::Visitor::Weaken(Type* current_type, Type* previous_type) {
1070 if (current_type->IsRange() && previous_type->IsRange()) {
1071 Type::RangeType* previous = previous_type->AsRange();
1072 Type::RangeType* current = current_type->AsRange();
1073
1074 double current_min = current->Min()->Number();
1075 Handle<Object> new_min = current->Min();
1076
1077 // Find the closest lower entry in the list of allowed
1078 // minima (or negative infinity if there is no such entry).
1079 if (current_min != previous->Min()->Number()) {
1080 new_min = typer_->integer->AsRange()->Min();
1081 for (const auto val : typer_->weaken_min_limits_) {
1082 if (val->Number() <= current_min) {
1083 new_min = val;
1084 break;
1085 }
1086 }
1087 }
1088
1089 double current_max = current->Max()->Number();
1090 Handle<Object> new_max = current->Max();
1091 // Find the closest greater entry in the list of allowed
1092 // maxima (or infinity if there is no such entry).
1093 if (current_max != previous->Max()->Number()) {
1094 new_max = typer_->integer->AsRange()->Max();
1095 for (const auto val : typer_->weaken_max_limits_) {
1096 if (val->Number() >= current_max) {
1097 new_max = val;
1098 break;
1099 }
1100 }
1101 }
1102
1103 return Type::Range(new_min, new_max, typer_->zone());
1104 }
1105 return current_type;
1106 }
1107
1108
893 Bounds Typer::Visitor::TypeJSStoreProperty(Node* node) { 1109 Bounds Typer::Visitor::TypeJSStoreProperty(Node* node) {
894 UNREACHABLE(); 1110 UNREACHABLE();
895 return Bounds(); 1111 return Bounds();
896 } 1112 }
897 1113
898 1114
899 Bounds Typer::Visitor::TypeJSStoreNamed(Node* node) { 1115 Bounds Typer::Visitor::TypeJSStoreNamed(Node* node) {
900 UNREACHABLE(); 1116 UNREACHABLE();
901 return Bounds(); 1117 return Bounds();
902 } 1118 }
(...skipping 732 matching lines...) Expand 10 before | Expand all | Expand 10 after
1635 return typer_->float64_array_fun_; 1851 return typer_->float64_array_fun_;
1636 } 1852 }
1637 } 1853 }
1638 } 1854 }
1639 return Type::Constant(value, zone()); 1855 return Type::Constant(value, zone());
1640 } 1856 }
1641 1857
1642 } 1858 }
1643 } 1859 }
1644 } // namespace v8::internal::compiler 1860 } // namespace v8::internal::compiler
OLDNEW
« no previous file with comments | « src/compiler/typer.h ('k') | src/types.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698