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 3 // found in the LICENSE file. 4 5 #include "src/compiler/typer.h" 6 7 #include "src/base/flags.h" 8 #include "src/bootstrapper.h" 9 #include "src/compilation-dependencies.h" 10 #include "src/compiler/common-operator.h" 11 #include "src/compiler/graph-reducer.h" 12 #include "src/compiler/js-operator.h" 13 #include "src/compiler/node.h" 14 #include "src/compiler/node-properties.h" 15 #include "src/compiler/simplified-operator.h" 16 #include "src/objects-inl.h" 17 #include "src/type-cache.h" 18 19 namespace v8 { 20 namespace internal { 21 namespace compiler { 22 23 class Typer::Decorator final : public GraphDecorator { 24 public: 25 explicit Decorator(Typer* typer) : typer_(typer) {} 26 void Decorate(Node* node) final; 27 28 private: 29 Typer* const typer_; 30 }; 31 32 33 Typer::Typer(Isolate* isolate, Graph* graph, Flags flags, 34 CompilationDependencies* dependencies, 35 Type::FunctionType* function_type) 36 : isolate_(isolate), 37 graph_(graph), 38 flags_(flags), 39 dependencies_(dependencies), 40 function_type_(function_type), 41 decorator_(nullptr), 42 cache_(TypeCache::Get()) { 43 Zone* zone = this->zone(); 44 Factory* const factory = isolate->factory(); 45 46 Type* infinity = Type::Constant(factory->infinity_value(), zone); 47 Type* minus_infinity = Type::Constant(factory->minus_infinity_value(), zone); 48 // TODO(neis): Unfortunately, the infinities created in other places might 49 // be different ones (eg the result of NewNumber in TypeNumberConstant). 50 Type* truncating_to_zero = 51 Type::Union(Type::Union(infinity, minus_infinity, zone), 52 Type::MinusZeroOrNaN(), zone); 53 DCHECK(!truncating_to_zero->Maybe(Type::Integral32())); 54 55 singleton_false_ = Type::Constant(factory->false_value(), zone); 56 singleton_true_ = Type::Constant(factory->true_value(), zone); 57 singleton_the_hole_ = Type::Constant(factory->the_hole_value(), zone); 58 signed32ish_ = Type::Union(Type::Signed32(), truncating_to_zero, zone); 59 unsigned32ish_ = Type::Union(Type::Unsigned32(), truncating_to_zero, zone); 60 falsish_ = Type::Union( 61 Type::Undetectable(), 62 Type::Union( 63 Type::Union(Type::Union(singleton_false_, cache_.kZeroish, zone), 64 Type::NullOrUndefined(), zone), 65 singleton_the_hole_, zone), 66 zone); 67 truish_ = Type::Union( 68 singleton_true_, 69 Type::Union(Type::DetectableReceiver(), Type::Symbol(), zone), zone); 70 71 decorator_ = new (zone) Decorator(this); 72 graph_->AddDecorator(decorator_); 73 } 74 75 76 Typer::~Typer() { 77 graph_->RemoveDecorator(decorator_); 78 } 79 80 81 class Typer::Visitor : public Reducer { 82 public: 83 explicit Visitor(Typer* typer) 84 : typer_(typer), weakened_nodes_(typer->zone()) {} 85 86 Reduction Reduce(Node* node) override { 87 if (node->op()->ValueOutputCount() == 0) return NoChange(); 88 switch (node->opcode()) { 89 #define DECLARE_CASE(x) \ 90 case IrOpcode::k##x: \ 91 return UpdateType(node, TypeBinaryOp(node, x##Typer)); 92 JS_SIMPLE_BINOP_LIST(DECLARE_CASE) 93 #undef DECLARE_CASE 94 95 #define DECLARE_CASE(x) \ 96 case IrOpcode::k##x: \ 97 return UpdateType(node, Type##x(node)); 98 DECLARE_CASE(Start) 99 DECLARE_CASE(IfException) 100 // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST: 101 COMMON_OP_LIST(DECLARE_CASE) 102 SIMPLIFIED_OP_LIST(DECLARE_CASE) 103 MACHINE_OP_LIST(DECLARE_CASE) 104 JS_SIMPLE_UNOP_LIST(DECLARE_CASE) 105 JS_OBJECT_OP_LIST(DECLARE_CASE) 106 JS_CONTEXT_OP_LIST(DECLARE_CASE) 107 JS_OTHER_OP_LIST(DECLARE_CASE) 108 #undef DECLARE_CASE 109 110 #define DECLARE_CASE(x) case IrOpcode::k##x: 111 DECLARE_CASE(Loop) 112 DECLARE_CASE(Branch) 113 DECLARE_CASE(IfTrue) 114 DECLARE_CASE(IfFalse) 115 DECLARE_CASE(IfSuccess) 116 DECLARE_CASE(Switch) 117 DECLARE_CASE(IfValue) 118 DECLARE_CASE(IfDefault) 119 DECLARE_CASE(Merge) 120 DECLARE_CASE(Deoptimize) 121 DECLARE_CASE(Return) 122 DECLARE_CASE(TailCall) 123 DECLARE_CASE(Terminate) 124 DECLARE_CASE(OsrNormalEntry) 125 DECLARE_CASE(OsrLoopEntry) 126 DECLARE_CASE(Throw) 127 DECLARE_CASE(End) 128 #undef DECLARE_CASE 129 break; 130 } 131 return NoChange(); 132 } 133 134 Type* TypeNode(Node* node) { 135 switch (node->opcode()) { 136 #define DECLARE_CASE(x) \ 137 case IrOpcode::k##x: return TypeBinaryOp(node, x##Typer); 138 JS_SIMPLE_BINOP_LIST(DECLARE_CASE) 139 #undef DECLARE_CASE 140 141 #define DECLARE_CASE(x) case IrOpcode::k##x: return Type##x(node); 142 DECLARE_CASE(Start) 143 DECLARE_CASE(IfException) 144 // VALUE_OP_LIST without JS_SIMPLE_BINOP_LIST: 145 COMMON_OP_LIST(DECLARE_CASE) 146 SIMPLIFIED_OP_LIST(DECLARE_CASE) 147 MACHINE_OP_LIST(DECLARE_CASE) 148 JS_SIMPLE_UNOP_LIST(DECLARE_CASE) 149 JS_OBJECT_OP_LIST(DECLARE_CASE) 150 JS_CONTEXT_OP_LIST(DECLARE_CASE) 151 JS_OTHER_OP_LIST(DECLARE_CASE) 152 #undef DECLARE_CASE 153 154 #define DECLARE_CASE(x) case IrOpcode::k##x: 155 DECLARE_CASE(Loop) 156 DECLARE_CASE(Branch) 157 DECLARE_CASE(IfTrue) 158 DECLARE_CASE(IfFalse) 159 DECLARE_CASE(IfSuccess) 160 DECLARE_CASE(Switch) 161 DECLARE_CASE(IfValue) 162 DECLARE_CASE(IfDefault) 163 DECLARE_CASE(Merge) 164 DECLARE_CASE(Deoptimize) 165 DECLARE_CASE(Return) 166 DECLARE_CASE(TailCall) 167 DECLARE_CASE(Terminate) 168 DECLARE_CASE(OsrNormalEntry) 169 DECLARE_CASE(OsrLoopEntry) 170 DECLARE_CASE(Throw) 171 DECLARE_CASE(End) 172 #undef DECLARE_CASE 173 break; 174 } 175 UNREACHABLE(); 176 return nullptr; 177 } 178 179 Type* TypeConstant(Handle<Object> value); 180 181 private: 182 Typer* typer_; 183 ZoneSet<NodeId> weakened_nodes_; 184 185 #define DECLARE_METHOD(x) inline Type* Type##x(Node* node); 186 DECLARE_METHOD(Start) 187 DECLARE_METHOD(IfException) 188 VALUE_OP_LIST(DECLARE_METHOD) 189 #undef DECLARE_METHOD 190 191 Type* TypeOrNone(Node* node) { 192 return NodeProperties::IsTyped(node) ? NodeProperties::GetType(node) 193 : Type::None(); 194 } 195 196 Type* Operand(Node* node, int i) { 197 Node* operand_node = NodeProperties::GetValueInput(node, i); 198 return TypeOrNone(operand_node); 199 } 200 201 Type* WrapContextTypeForInput(Node* node); 202 Type* Weaken(Node* node, Type* current_type, Type* previous_type); 203 204 Zone* zone() { return typer_->zone(); } 205 Isolate* isolate() { return typer_->isolate(); } 206 Graph* graph() { return typer_->graph(); } 207 Typer::Flags flags() const { return typer_->flags(); } 208 CompilationDependencies* dependencies() const { 209 return typer_->dependencies(); 210 } 211 212 void SetWeakened(NodeId node_id) { weakened_nodes_.insert(node_id); } 213 bool IsWeakened(NodeId node_id) { 214 return weakened_nodes_.find(node_id) != weakened_nodes_.end(); 215 } 216 217 typedef Type* (*UnaryTyperFun)(Type*, Typer* t); 218 typedef Type* (*BinaryTyperFun)(Type*, Type*, Typer* t); 219 220 Type* TypeUnaryOp(Node* node, UnaryTyperFun); 221 Type* TypeBinaryOp(Node* node, BinaryTyperFun); 222 223 enum ComparisonOutcomeFlags { 224 kComparisonTrue = 1, 225 kComparisonFalse = 2, 226 kComparisonUndefined = 4 227 }; 228 typedef base::Flags<ComparisonOutcomeFlags> ComparisonOutcome; 229 230 static ComparisonOutcome Invert(ComparisonOutcome, Typer*); 231 static Type* Invert(Type*, Typer*); 232 static Type* FalsifyUndefined(ComparisonOutcome, Typer*); 233 static Type* Rangify(Type*, Typer*); 234 235 static Type* ToPrimitive(Type*, Typer*); 236 static Type* ToBoolean(Type*, Typer*); 237 static Type* ToInteger(Type*, Typer*); 238 static Type* ToLength(Type*, Typer*); 239 static Type* ToName(Type*, Typer*); 240 static Type* ToNumber(Type*, Typer*); 241 static Type* ToObject(Type*, Typer*); 242 static Type* ToString(Type*, Typer*); 243 static Type* NumberToInt32(Type*, Typer*); 244 static Type* NumberToUint32(Type*, Typer*); 245 246 static Type* JSAddRanger(Type::RangeType*, Type::RangeType*, Typer*); 247 static Type* JSSubtractRanger(Type::RangeType*, Type::RangeType*, Typer*); 248 static Type* JSMultiplyRanger(Type::RangeType*, Type::RangeType*, Typer*); 249 static Type* JSDivideRanger(Type::RangeType*, Type::RangeType*, Typer*); 250 static Type* JSModulusRanger(Type::RangeType*, Type::RangeType*, Typer*); 251 252 static ComparisonOutcome JSCompareTyper(Type*, Type*, Typer*); 253 254 #define DECLARE_METHOD(x) static Type* x##Typer(Type*, Type*, Typer*); 255 JS_SIMPLE_BINOP_LIST(DECLARE_METHOD) 256 #undef DECLARE_METHOD 257 258 static Type* JSTypeOfTyper(Type*, Typer*); 259 static Type* JSLoadPropertyTyper(Type*, Type*, Typer*); 260 static Type* JSCallFunctionTyper(Type*, Typer*); 261 262 static Type* ReferenceEqualTyper(Type*, Type*, Typer*); 263 264 Reduction UpdateType(Node* node, Type* current) { 265 if (NodeProperties::IsTyped(node)) { 266 // Widen the type of a previously typed node. 267 Type* previous = NodeProperties::GetType(node); 268 if (node->opcode() == IrOpcode::kPhi) { 269 // Speed up termination in the presence of range types: 270 current = Weaken(node, current, previous); 271 } 272 273 CHECK(previous->Is(current)); 274 275 NodeProperties::SetType(node, current); 276 if (!current->Is(previous)) { 277 // If something changed, revisit all uses. 278 return Changed(node); 279 } 280 return NoChange(); 281 } else { 282 // No previous type, simply update the type. 283 NodeProperties::SetType(node, current); 284 return Changed(node); 285 } 286 } 287 }; 288 289 290 void Typer::Run() { Run(NodeVector(zone())); } 291 292 293 void Typer::Run(const NodeVector& roots) { 294 Visitor visitor(this); 295 GraphReducer graph_reducer(zone(), graph()); 296 graph_reducer.AddReducer(&visitor); 297 for (Node* const root : roots) graph_reducer.ReduceNode(root); 298 graph_reducer.ReduceGraph(); 299 } 300 301 302 void Typer::Decorator::Decorate(Node* node) { 303 if (node->op()->ValueOutputCount() > 0) { 304 // Only eagerly type-decorate nodes with known input types. 305 // Other cases will generally require a proper fixpoint iteration with Run. 306 bool is_typed = NodeProperties::IsTyped(node); 307 if (is_typed || NodeProperties::AllValueInputsAreTyped(node)) { 308 Visitor typing(typer_); 309 Type* type = typing.TypeNode(node); 310 if (is_typed) { 311 type = Type::Intersect(type, NodeProperties::GetType(node), 312 typer_->zone()); 313 } 314 NodeProperties::SetType(node, type); 315 } 316 } 317 } 318 319 320 // ----------------------------------------------------------------------------- 321 322 // Helper functions that lift a function f on types to a function on bounds, 323 // and uses that to type the given node. Note that f is never called with None 324 // as an argument. 325 326 327 Type* Typer::Visitor::TypeUnaryOp(Node* node, UnaryTyperFun f) { 328 Type* input = Operand(node, 0); 329 return input->IsInhabited() ? f(input, typer_) : Type::None(); 330 } 331 332 333 Type* Typer::Visitor::TypeBinaryOp(Node* node, BinaryTyperFun f) { 334 Type* left = Operand(node, 0); 335 Type* right = Operand(node, 1); 336 return left->IsInhabited() && right->IsInhabited() ? f(left, right, typer_) 337 : Type::None(); 338 } 339 340 341 Type* Typer::Visitor::Invert(Type* type, Typer* t) { 342 DCHECK(type->Is(Type::Boolean())); 343 DCHECK(type->IsInhabited()); 344 if (type->Is(t->singleton_false_)) return t->singleton_true_; 345 if (type->Is(t->singleton_true_)) return t->singleton_false_; 346 return type; 347 } 348 349 350 Typer::Visitor::ComparisonOutcome Typer::Visitor::Invert( 351 ComparisonOutcome outcome, Typer* t) { 352 ComparisonOutcome result(0); 353 if ((outcome & kComparisonUndefined) != 0) result |= kComparisonUndefined; 354 if ((outcome & kComparisonTrue) != 0) result |= kComparisonFalse; 355 if ((outcome & kComparisonFalse) != 0) result |= kComparisonTrue; 356 return result; 357 } 358 359 360 Type* Typer::Visitor::FalsifyUndefined(ComparisonOutcome outcome, Typer* t) { 361 if ((outcome & kComparisonFalse) != 0 || 362 (outcome & kComparisonUndefined) != 0) { 363 return (outcome & kComparisonTrue) != 0 ? Type::Boolean() 364 : t->singleton_false_; 365 } 366 // Type should be non empty, so we know it should be true. 367 DCHECK((outcome & kComparisonTrue) != 0); 368 return t->singleton_true_; 369 } 370 371 372 Type* Typer::Visitor::Rangify(Type* type, Typer* t) { 373 if (type->IsRange()) return type; // Shortcut. 374 if (!type->Is(t->cache_.kInteger)) { 375 return type; // Give up on non-integer types. 376 } 377 double min = type->Min(); 378 double max = type->Max(); 379 // Handle the degenerate case of empty bitset types (such as 380 // OtherUnsigned31 and OtherSigned32 on 64-bit architectures). 381 if (std::isnan(min)) { 382 DCHECK(std::isnan(max)); 383 return type; 384 } 385 return Type::Range(min, max, t->zone()); 386 } 387 388 389 // Type conversion. 390 391 392 Type* Typer::Visitor::ToPrimitive(Type* type, Typer* t) { 393 if (type->Is(Type::Primitive()) && !type->Maybe(Type::Receiver())) { 394 return type; 395 } 396 return Type::Primitive(); 397 } 398 399 400 Type* Typer::Visitor::ToBoolean(Type* type, Typer* t) { 401 if (type->Is(Type::Boolean())) return type; 402 if (type->Is(t->falsish_)) return t->singleton_false_; 403 if (type->Is(t->truish_)) return t->singleton_true_; 404 if (type->Is(Type::PlainNumber()) && (type->Max() < 0 || 0 < type->Min())) { 405 return t->singleton_true_; // Ruled out nan, -0 and +0. 406 } 407 return Type::Boolean(); 408 } 409 410 411 // static 412 Type* Typer::Visitor::ToInteger(Type* type, Typer* t) { 413 // ES6 section 7.1.4 ToInteger ( argument ) 414 type = ToNumber(type, t); 415 if (type->Is(t->cache_.kIntegerOrMinusZero)) return type; 416 return t->cache_.kIntegerOrMinusZero; 417 } 418 419 420 // static 421 Type* Typer::Visitor::ToLength(Type* type, Typer* t) { 422 // ES6 section 7.1.15 ToLength ( argument ) 423 type = ToInteger(type, t); 424 double min = type->Min(); 425 double max = type->Max(); 426 if (min <= 0.0) min = 0.0; 427 if (max > kMaxSafeInteger) max = kMaxSafeInteger; 428 if (max <= min) max = min; 429 return Type::Range(min, max, t->zone()); 430 } 431 432 433 // static 434 Type* Typer::Visitor::ToName(Type* type, Typer* t) { 435 // ES6 section 7.1.14 ToPropertyKey ( argument ) 436 type = ToPrimitive(type, t); 437 if (type->Is(Type::Name())) return type; 438 if (type->Maybe(Type::Symbol())) return Type::Name(); 439 return ToString(type, t); 440 } 441 442 443 // static 444 Type* Typer::Visitor::ToNumber(Type* type, Typer* t) { 445 if (type->Is(Type::Number())) return type; 446 if (type->Is(Type::NullOrUndefined())) { 447 if (type->Is(Type::Null())) return t->cache_.kSingletonZero; 448 if (type->Is(Type::Undefined())) return Type::NaN(); 449 return Type::Union(Type::NaN(), t->cache_.kSingletonZero, t->zone()); 450 } 451 if (type->Is(Type::NumberOrUndefined())) { 452 return Type::Union(Type::Intersect(type, Type::Number(), t->zone()), 453 Type::NaN(), t->zone()); 454 } 455 if (type->Is(t->singleton_false_)) return t->cache_.kSingletonZero; 456 if (type->Is(t->singleton_true_)) return t->cache_.kSingletonOne; 457 if (type->Is(Type::Boolean())) return t->cache_.kZeroOrOne; 458 if (type->Is(Type::BooleanOrNumber())) { 459 return Type::Union(Type::Intersect(type, Type::Number(), t->zone()), 460 t->cache_.kZeroOrOne, t->zone()); 461 } 462 return Type::Number(); 463 } 464 465 466 // static 467 Type* Typer::Visitor::ToObject(Type* type, Typer* t) { 468 // ES6 section 7.1.13 ToObject ( argument ) 469 if (type->Is(Type::Receiver())) return type; 470 if (type->Is(Type::Primitive())) return Type::OtherObject(); 471 if (!type->Maybe(Type::Undetectable())) return Type::DetectableReceiver(); 472 return Type::Receiver(); 473 } 474 475 476 // static 477 Type* Typer::Visitor::ToString(Type* type, Typer* t) { 478 // ES6 section 7.1.12 ToString ( argument ) 479 type = ToPrimitive(type, t); 480 if (type->Is(Type::String())) return type; 481 return Type::String(); 482 } 483 484 485 Type* Typer::Visitor::NumberToInt32(Type* type, Typer* t) { 486 // TODO(neis): DCHECK(type->Is(Type::Number())); 487 if (type->Is(Type::Signed32())) return type; 488 if (type->Is(t->cache_.kZeroish)) return t->cache_.kSingletonZero; 489 if (type->Is(t->signed32ish_)) { 490 return Type::Intersect( 491 Type::Union(type, t->cache_.kSingletonZero, t->zone()), 492 Type::Signed32(), t->zone()); 493 } 494 return Type::Signed32(); 495 } 496 497 498 Type* Typer::Visitor::NumberToUint32(Type* type, Typer* t) { 499 // TODO(neis): DCHECK(type->Is(Type::Number())); 500 if (type->Is(Type::Unsigned32())) return type; 501 if (type->Is(t->cache_.kZeroish)) return t->cache_.kSingletonZero; 502 if (type->Is(t->unsigned32ish_)) { 503 return Type::Intersect( 504 Type::Union(type, t->cache_.kSingletonZero, t->zone()), 505 Type::Unsigned32(), t->zone()); 506 } 507 return Type::Unsigned32(); 508 } 509 510 511 // ----------------------------------------------------------------------------- 512 513 514 // Control operators. 515 516 517 Type* Typer::Visitor::TypeStart(Node* node) { return Type::Internal(zone()); } 518 519 520 Type* Typer::Visitor::TypeIfException(Node* node) { return Type::Any(); } 521 522 523 // Common operators. 524 525 526 Type* Typer::Visitor::TypeParameter(Node* node) { 527 if (Type::FunctionType* function_type = typer_->function_type()) { 528 int const index = ParameterIndexOf(node->op()); 529 if (index >= 0 && index < function_type->Arity()) { 530 return function_type->Parameter(index); 531 } 532 } 533 return Type::Any(); 534 } 535 536 537 Type* Typer::Visitor::TypeOsrValue(Node* node) { return Type::Any(); } 538 539 540 Type* Typer::Visitor::TypeInt32Constant(Node* node) { 541 double number = OpParameter<int32_t>(node); 542 return Type::Intersect(Type::Range(number, number, zone()), 543 Type::UntaggedIntegral32(), zone()); 544 } 545 546 547 Type* Typer::Visitor::TypeInt64Constant(Node* node) { 548 // TODO(rossberg): This actually seems to be a PointerConstant so far... 549 return Type::Internal(); // TODO(rossberg): Add int64 bitset type? 550 } 551 552 553 Type* Typer::Visitor::TypeFloat32Constant(Node* node) { 554 return Type::Intersect(Type::Of(OpParameter<float>(node), zone()), 555 Type::UntaggedFloat32(), zone()); 556 } 557 558 559 Type* Typer::Visitor::TypeFloat64Constant(Node* node) { 560 return Type::Intersect(Type::Of(OpParameter<double>(node), zone()), 561 Type::UntaggedFloat64(), zone()); 562 } 563 564 565 Type* Typer::Visitor::TypeNumberConstant(Node* node) { 566 Factory* f = isolate()->factory(); 567 double number = OpParameter<double>(node); 568 if (Type::IsInteger(number)) { 569 return Type::Range(number, number, zone()); 570 } 571 return Type::Constant(f->NewNumber(number), zone()); 572 } 573 574 575 Type* Typer::Visitor::TypeHeapConstant(Node* node) { 576 return TypeConstant(OpParameter<Handle<HeapObject>>(node)); 577 } 578 579 580 Type* Typer::Visitor::TypeExternalConstant(Node* node) { 581 return Type::Internal(zone()); 582 } 583 584 585 Type* Typer::Visitor::TypeSelect(Node* node) { 586 return Type::Union(Operand(node, 1), Operand(node, 2), zone()); 587 } 588 589 590 Type* Typer::Visitor::TypePhi(Node* node) { 591 int arity = node->op()->ValueInputCount(); 592 Type* type = Operand(node, 0); 593 for (int i = 1; i < arity; ++i) { 594 type = Type::Union(type, Operand(node, i), zone()); 595 } 596 return type; 597 } 598 599 600 Type* Typer::Visitor::TypeEffectPhi(Node* node) { 601 UNREACHABLE(); 602 return nullptr; 603 } 604 605 606 Type* Typer::Visitor::TypeEffectSet(Node* node) { 607 UNREACHABLE(); 608 return nullptr; 609 } 610 611 612 Type* Typer::Visitor::TypeGuard(Node* node) { 613 Type* input_type = Operand(node, 0); 614 Type* guard_type = OpParameter<Type*>(node); 615 return Type::Intersect(input_type, guard_type, zone()); 616 } 617 618 619 Type* Typer::Visitor::TypeBeginRegion(Node* node) { 620 UNREACHABLE(); 621 return nullptr; 622 } 623 624 625 Type* Typer::Visitor::TypeFinishRegion(Node* node) { return Operand(node, 0); } 626 627 628 Type* Typer::Visitor::TypeFrameState(Node* node) { 629 // TODO(rossberg): Ideally FrameState wouldn't have a value output. 630 return Type::Internal(zone()); 631 } 632 633 634 Type* Typer::Visitor::TypeStateValues(Node* node) { 635 return Type::Internal(zone()); 636 } 637 638 639 Type* Typer::Visitor::TypeObjectState(Node* node) { 640 return Type::Internal(zone()); 641 } 642 643 644 Type* Typer::Visitor::TypeTypedStateValues(Node* node) { 645 return Type::Internal(zone()); 646 } 647 648 649 Type* Typer::Visitor::TypeCall(Node* node) { return Type::Any(); } 650 651 652 Type* Typer::Visitor::TypeProjection(Node* node) { 653 // TODO(titzer): use the output type of the input to determine the bounds. 654 return Type::Any(); 655 } 656 657 658 Type* Typer::Visitor::TypeDead(Node* node) { return Type::Any(); } 659 660 661 // JS comparison operators. 662 663 664 Type* Typer::Visitor::JSEqualTyper(Type* lhs, Type* rhs, Typer* t) { 665 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false_; 666 if (lhs->Is(Type::NullOrUndefined()) && rhs->Is(Type::NullOrUndefined())) { 667 return t->singleton_true_; 668 } 669 if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) && 670 (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) { 671 return t->singleton_false_; 672 } 673 if (lhs->IsConstant() && rhs->Is(lhs)) { 674 // Types are equal and are inhabited only by a single semantic value, 675 // which is not nan due to the earlier check. 676 // TODO(neis): Extend this to Range(x,x), MinusZero, ...? 677 return t->singleton_true_; 678 } 679 return Type::Boolean(); 680 } 681 682 683 Type* Typer::Visitor::JSNotEqualTyper(Type* lhs, Type* rhs, Typer* t) { 684 return Invert(JSEqualTyper(lhs, rhs, t), t); 685 } 686 687 688 static Type* JSType(Type* type) { 689 if (type->Is(Type::Boolean())) return Type::Boolean(); 690 if (type->Is(Type::String())) return Type::String(); 691 if (type->Is(Type::Number())) return Type::Number(); 692 if (type->Is(Type::Undefined())) return Type::Undefined(); 693 if (type->Is(Type::Null())) return Type::Null(); 694 if (type->Is(Type::Symbol())) return Type::Symbol(); 695 if (type->Is(Type::Receiver())) return Type::Receiver(); // JS "Object" 696 return Type::Any(); 697 } 698 699 700 Type* Typer::Visitor::JSStrictEqualTyper(Type* lhs, Type* rhs, Typer* t) { 701 if (!JSType(lhs)->Maybe(JSType(rhs))) return t->singleton_false_; 702 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return t->singleton_false_; 703 if (lhs->Is(Type::Number()) && rhs->Is(Type::Number()) && 704 (lhs->Max() < rhs->Min() || lhs->Min() > rhs->Max())) { 705 return t->singleton_false_; 706 } 707 if ((lhs->Is(t->singleton_the_hole_) || rhs->Is(t->singleton_the_hole_)) && 708 !lhs->Maybe(rhs)) { 709 return t->singleton_false_; 710 } 711 if (lhs->IsConstant() && rhs->Is(lhs)) { 712 // Types are equal and are inhabited only by a single semantic value, 713 // which is not nan due to the earlier check. 714 return t->singleton_true_; 715 } 716 return Type::Boolean(); 717 } 718 719 720 Type* Typer::Visitor::JSStrictNotEqualTyper(Type* lhs, Type* rhs, Typer* t) { 721 return Invert(JSStrictEqualTyper(lhs, rhs, t), t); 722 } 723 724 725 // The EcmaScript specification defines the four relational comparison operators 726 // (<, <=, >=, >) with the help of a single abstract one. It behaves like < 727 // but returns undefined when the inputs cannot be compared. 728 // We implement the typing analogously. 729 Typer::Visitor::ComparisonOutcome Typer::Visitor::JSCompareTyper(Type* lhs, 730 Type* rhs, 731 Typer* t) { 732 lhs = ToPrimitive(lhs, t); 733 rhs = ToPrimitive(rhs, t); 734 if (lhs->Maybe(Type::String()) && rhs->Maybe(Type::String())) { 735 return ComparisonOutcome(kComparisonTrue) | 736 ComparisonOutcome(kComparisonFalse); 737 } 738 lhs = ToNumber(lhs, t); 739 rhs = ToNumber(rhs, t); 740 741 // Shortcut for NaNs. 742 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return kComparisonUndefined; 743 744 ComparisonOutcome result; 745 if (lhs->IsConstant() && rhs->Is(lhs)) { 746 // Types are equal and are inhabited only by a single semantic value. 747 result = kComparisonFalse; 748 } else if (lhs->Min() >= rhs->Max()) { 749 result = kComparisonFalse; 750 } else if (lhs->Max() < rhs->Min()) { 751 result = kComparisonTrue; 752 } else { 753 // We cannot figure out the result, return both true and false. (We do not 754 // have to return undefined because that cannot affect the result of 755 // FalsifyUndefined.) 756 return ComparisonOutcome(kComparisonTrue) | 757 ComparisonOutcome(kComparisonFalse); 758 } 759 // Add the undefined if we could see NaN. 760 if (lhs->Maybe(Type::NaN()) || rhs->Maybe(Type::NaN())) { 761 result |= kComparisonUndefined; 762 } 763 return result; 764 } 765 766 767 Type* Typer::Visitor::JSLessThanTyper(Type* lhs, Type* rhs, Typer* t) { 768 return FalsifyUndefined(JSCompareTyper(lhs, rhs, t), t); 769 } 770 771 772 Type* Typer::Visitor::JSGreaterThanTyper(Type* lhs, Type* rhs, Typer* t) { 773 return FalsifyUndefined(JSCompareTyper(rhs, lhs, t), t); 774 } 775 776 777 Type* Typer::Visitor::JSLessThanOrEqualTyper(Type* lhs, Type* rhs, Typer* t) { 778 return FalsifyUndefined(Invert(JSCompareTyper(rhs, lhs, t), t), t); 779 } 780 781 782 Type* Typer::Visitor::JSGreaterThanOrEqualTyper( 783 Type* lhs, Type* rhs, Typer* t) { 784 return FalsifyUndefined(Invert(JSCompareTyper(lhs, rhs, t), t), t); 785 } 786 787 788 // JS bitwise operators. 789 790 791 Type* Typer::Visitor::JSBitwiseOrTyper(Type* lhs, Type* rhs, Typer* t) { 792 lhs = NumberToInt32(ToNumber(lhs, t), t); 793 rhs = NumberToInt32(ToNumber(rhs, t), t); 794 double lmin = lhs->Min(); 795 double rmin = rhs->Min(); 796 double lmax = lhs->Max(); 797 double rmax = rhs->Max(); 798 // Or-ing any two values results in a value no smaller than their minimum. 799 // Even no smaller than their maximum if both values are non-negative. 800 double min = 801 lmin >= 0 && rmin >= 0 ? std::max(lmin, rmin) : std::min(lmin, rmin); 802 double max = Type::Signed32()->Max(); 803 804 // Or-ing with 0 is essentially a conversion to int32. 805 if (rmin == 0 && rmax == 0) { 806 min = lmin; 807 max = lmax; 808 } 809 if (lmin == 0 && lmax == 0) { 810 min = rmin; 811 max = rmax; 812 } 813 814 if (lmax < 0 || rmax < 0) { 815 // Or-ing two values of which at least one is negative results in a negative 816 // value. 817 max = std::min(max, -1.0); 818 } 819 return Type::Range(min, max, t->zone()); 820 // TODO(neis): Be precise for singleton inputs, here and elsewhere. 821 } 822 823 824 Type* Typer::Visitor::JSBitwiseAndTyper(Type* lhs, Type* rhs, Typer* t) { 825 lhs = NumberToInt32(ToNumber(lhs, t), t); 826 rhs = NumberToInt32(ToNumber(rhs, t), t); 827 double lmin = lhs->Min(); 828 double rmin = rhs->Min(); 829 double lmax = lhs->Max(); 830 double rmax = rhs->Max(); 831 double min = Type::Signed32()->Min(); 832 // And-ing any two values results in a value no larger than their maximum. 833 // Even no larger than their minimum if both values are non-negative. 834 double max = 835 lmin >= 0 && rmin >= 0 ? std::min(lmax, rmax) : std::max(lmax, rmax); 836 // And-ing with a non-negative value x causes the result to be between 837 // zero and x. 838 if (lmin >= 0) { 839 min = 0; 840 max = std::min(max, lmax); 841 } 842 if (rmin >= 0) { 843 min = 0; 844 max = std::min(max, rmax); 845 } 846 return Type::Range(min, max, t->zone()); 847 } 848 849 850 Type* Typer::Visitor::JSBitwiseXorTyper(Type* lhs, Type* rhs, Typer* t) { 851 lhs = NumberToInt32(ToNumber(lhs, t), t); 852 rhs = NumberToInt32(ToNumber(rhs, t), t); 853 double lmin = lhs->Min(); 854 double rmin = rhs->Min(); 855 double lmax = lhs->Max(); 856 double rmax = rhs->Max(); 857 if ((lmin >= 0 && rmin >= 0) || (lmax < 0 && rmax < 0)) { 858 // Xor-ing negative or non-negative values results in a non-negative value. 859 return Type::Unsigned31(); 860 } 861 if ((lmax < 0 && rmin >= 0) || (lmin >= 0 && rmax < 0)) { 862 // Xor-ing a negative and a non-negative value results in a negative value. 863 // TODO(jarin) Use a range here. 864 return Type::Negative32(); 865 } 866 return Type::Signed32(); 867 } 868 869 870 Type* Typer::Visitor::JSShiftLeftTyper(Type* lhs, Type* rhs, Typer* t) { 871 return Type::Signed32(); 872 } 873 874 875 Type* Typer::Visitor::JSShiftRightTyper(Type* lhs, Type* rhs, Typer* t) { 876 lhs = NumberToInt32(ToNumber(lhs, t), t); 877 rhs = NumberToUint32(ToNumber(rhs, t), t); 878 double min = kMinInt; 879 double max = kMaxInt; 880 if (lhs->Min() >= 0) { 881 // Right-shifting a non-negative value cannot make it negative, nor larger. 882 min = std::max(min, 0.0); 883 max = std::min(max, lhs->Max()); 884 if (rhs->Min() > 0 && rhs->Max() <= 31) { 885 max = static_cast<int>(max) >> static_cast<int>(rhs->Min()); 886 } 887 } 888 if (lhs->Max() < 0) { 889 // Right-shifting a negative value cannot make it non-negative, nor smaller. 890 min = std::max(min, lhs->Min()); 891 max = std::min(max, -1.0); 892 if (rhs->Min() > 0 && rhs->Max() <= 31) { 893 min = static_cast<int>(min) >> static_cast<int>(rhs->Min()); 894 } 895 } 896 if (rhs->Min() > 0 && rhs->Max() <= 31) { 897 // Right-shifting by a positive value yields a small integer value. 898 double shift_min = kMinInt >> static_cast<int>(rhs->Min()); 899 double shift_max = kMaxInt >> static_cast<int>(rhs->Min()); 900 min = std::max(min, shift_min); 901 max = std::min(max, shift_max); 902 } 903 // TODO(jarin) Ideally, the following micro-optimization should be performed 904 // by the type constructor. 905 if (max != Type::Signed32()->Max() || min != Type::Signed32()->Min()) { 906 return Type::Range(min, max, t->zone()); 907 } 908 return Type::Signed32(); 909 } 910 911 912 Type* Typer::Visitor::JSShiftRightLogicalTyper(Type* lhs, Type* rhs, Typer* t) { 913 lhs = NumberToUint32(ToNumber(lhs, t), t); 914 // Logical right-shifting any value cannot make it larger. 915 return Type::Range(0.0, lhs->Max(), t->zone()); 916 } 917 918 919 // JS arithmetic operators. 920 921 922 // Returns the array's least element, ignoring NaN. 923 // There must be at least one non-NaN element. 924 // Any -0 is converted to 0. 925 static double array_min(double a[], size_t n) { 926 DCHECK(n != 0); 927 double x = +V8_INFINITY; 928 for (size_t i = 0; i < n; ++i) { 929 if (!std::isnan(a[i])) { 930 x = std::min(a[i], x); 931 } 932 } 933 DCHECK(!std::isnan(x)); 934 return x == 0 ? 0 : x; // -0 -> 0 935 } 936 937 938 // Returns the array's greatest element, ignoring NaN. 939 // There must be at least one non-NaN element. 940 // Any -0 is converted to 0. 941 static double array_max(double a[], size_t n) { 942 DCHECK(n != 0); 943 double x = -V8_INFINITY; 944 for (size_t i = 0; i < n; ++i) { 945 if (!std::isnan(a[i])) { 946 x = std::max(a[i], x); 947 } 948 } 949 DCHECK(!std::isnan(x)); 950 return x == 0 ? 0 : x; // -0 -> 0 951 } 952 953 954 Type* Typer::Visitor::JSAddRanger(Type::RangeType* lhs, Type::RangeType* rhs, 955 Typer* t) { 956 double results[4]; 957 results[0] = lhs->Min() + rhs->Min(); 958 results[1] = lhs->Min() + rhs->Max(); 959 results[2] = lhs->Max() + rhs->Min(); 960 results[3] = lhs->Max() + rhs->Max(); 961 // Since none of the inputs can be -0, the result cannot be -0 either. 962 // However, it can be nan (the sum of two infinities of opposite sign). 963 // On the other hand, if none of the "results" above is nan, then the actual 964 // result cannot be nan either. 965 int nans = 0; 966 for (int i = 0; i < 4; ++i) { 967 if (std::isnan(results[i])) ++nans; 968 } 969 if (nans == 4) return Type::NaN(); // [-inf..-inf] + [inf..inf] or vice versa 970 Type* range = 971 Type::Range(array_min(results, 4), array_max(results, 4), t->zone()); 972 return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone()); 973 // Examples: 974 // [-inf, -inf] + [+inf, +inf] = NaN 975 // [-inf, -inf] + [n, +inf] = [-inf, -inf] \/ NaN 976 // [-inf, +inf] + [n, +inf] = [-inf, +inf] \/ NaN 977 // [-inf, m] + [n, +inf] = [-inf, +inf] \/ NaN 978 } 979 980 981 Type* Typer::Visitor::JSAddTyper(Type* lhs, Type* rhs, Typer* t) { 982 lhs = ToPrimitive(lhs, t); 983 rhs = ToPrimitive(rhs, t); 984 if (lhs->Maybe(Type::String()) || rhs->Maybe(Type::String())) { 985 if (lhs->Is(Type::String()) || rhs->Is(Type::String())) { 986 return Type::String(); 987 } else { 988 return Type::NumberOrString(); 989 } 990 } 991 lhs = Rangify(ToNumber(lhs, t), t); 992 rhs = Rangify(ToNumber(rhs, t), t); 993 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 994 if (lhs->IsRange() && rhs->IsRange()) { 995 return JSAddRanger(lhs->AsRange(), rhs->AsRange(), t); 996 } 997 // TODO(neis): Deal with numeric bitsets here and elsewhere. 998 return Type::Number(); 999 } 1000 1001 1002 Type* Typer::Visitor::JSSubtractRanger(Type::RangeType* lhs, 1003 Type::RangeType* rhs, Typer* t) { 1004 double results[4]; 1005 results[0] = lhs->Min() - rhs->Min(); 1006 results[1] = lhs->Min() - rhs->Max(); 1007 results[2] = lhs->Max() - rhs->Min(); 1008 results[3] = lhs->Max() - rhs->Max(); 1009 // Since none of the inputs can be -0, the result cannot be -0. 1010 // However, it can be nan (the subtraction of two infinities of same sign). 1011 // On the other hand, if none of the "results" above is nan, then the actual 1012 // result cannot be nan either. 1013 int nans = 0; 1014 for (int i = 0; i < 4; ++i) { 1015 if (std::isnan(results[i])) ++nans; 1016 } 1017 if (nans == 4) return Type::NaN(); // [inf..inf] - [inf..inf] (all same sign) 1018 Type* range = 1019 Type::Range(array_min(results, 4), array_max(results, 4), t->zone()); 1020 return nans == 0 ? range : Type::Union(range, Type::NaN(), t->zone()); 1021 // Examples: 1022 // [-inf, +inf] - [-inf, +inf] = [-inf, +inf] \/ NaN 1023 // [-inf, -inf] - [-inf, -inf] = NaN 1024 // [-inf, -inf] - [n, +inf] = [-inf, -inf] \/ NaN 1025 // [m, +inf] - [-inf, n] = [-inf, +inf] \/ NaN 1026 } 1027 1028 1029 Type* Typer::Visitor::JSSubtractTyper(Type* lhs, Type* rhs, Typer* t) { 1030 lhs = Rangify(ToNumber(lhs, t), t); 1031 rhs = Rangify(ToNumber(rhs, t), t); 1032 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 1033 if (lhs->IsRange() && rhs->IsRange()) { 1034 return JSSubtractRanger(lhs->AsRange(), rhs->AsRange(), t); 1035 } 1036 return Type::Number(); 1037 } 1038 1039 1040 Type* Typer::Visitor::JSMultiplyRanger(Type::RangeType* lhs, 1041 Type::RangeType* rhs, Typer* t) { 1042 double results[4]; 1043 double lmin = lhs->Min(); 1044 double lmax = lhs->Max(); 1045 double rmin = rhs->Min(); 1046 double rmax = rhs->Max(); 1047 results[0] = lmin * rmin; 1048 results[1] = lmin * rmax; 1049 results[2] = lmax * rmin; 1050 results[3] = lmax * rmax; 1051 // If the result may be nan, we give up on calculating a precise type, because 1052 // the discontinuity makes it too complicated. Note that even if none of the 1053 // "results" above is nan, the actual result may still be, so we have to do a 1054 // different check: 1055 bool maybe_nan = (lhs->Maybe(t->cache_.kSingletonZero) && 1056 (rmin == -V8_INFINITY || rmax == +V8_INFINITY)) || 1057 (rhs->Maybe(t->cache_.kSingletonZero) && 1058 (lmin == -V8_INFINITY || lmax == +V8_INFINITY)); 1059 if (maybe_nan) return t->cache_.kIntegerOrMinusZeroOrNaN; // Giving up. 1060 bool maybe_minuszero = (lhs->Maybe(t->cache_.kSingletonZero) && rmin < 0) || 1061 (rhs->Maybe(t->cache_.kSingletonZero) && lmin < 0); 1062 Type* range = 1063 Type::Range(array_min(results, 4), array_max(results, 4), t->zone()); 1064 return maybe_minuszero ? Type::Union(range, Type::MinusZero(), t->zone()) 1065 : range; 1066 } 1067 1068 1069 Type* Typer::Visitor::JSMultiplyTyper(Type* lhs, Type* rhs, Typer* t) { 1070 lhs = Rangify(ToNumber(lhs, t), t); 1071 rhs = Rangify(ToNumber(rhs, t), t); 1072 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 1073 if (lhs->IsRange() && rhs->IsRange()) { 1074 return JSMultiplyRanger(lhs->AsRange(), rhs->AsRange(), t); 1075 } 1076 return Type::Number(); 1077 } 1078 1079 1080 Type* Typer::Visitor::JSDivideTyper(Type* lhs, Type* rhs, Typer* t) { 1081 lhs = ToNumber(lhs, t); 1082 rhs = ToNumber(rhs, t); 1083 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 1084 // Division is tricky, so all we do is try ruling out nan. 1085 // TODO(neis): try ruling out -0 as well? 1086 bool maybe_nan = 1087 lhs->Maybe(Type::NaN()) || rhs->Maybe(t->cache_.kZeroish) || 1088 ((lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) && 1089 (rhs->Min() == -V8_INFINITY || rhs->Max() == +V8_INFINITY)); 1090 return maybe_nan ? Type::Number() : Type::OrderedNumber(); 1091 } 1092 1093 1094 Type* Typer::Visitor::JSModulusRanger(Type::RangeType* lhs, 1095 Type::RangeType* rhs, Typer* t) { 1096 double lmin = lhs->Min(); 1097 double lmax = lhs->Max(); 1098 double rmin = rhs->Min(); 1099 double rmax = rhs->Max(); 1100 1101 double labs = std::max(std::abs(lmin), std::abs(lmax)); 1102 double rabs = std::max(std::abs(rmin), std::abs(rmax)) - 1; 1103 double abs = std::min(labs, rabs); 1104 bool maybe_minus_zero = false; 1105 double omin = 0; 1106 double omax = 0; 1107 if (lmin >= 0) { // {lhs} positive. 1108 omin = 0; 1109 omax = abs; 1110 } else if (lmax <= 0) { // {lhs} negative. 1111 omin = 0 - abs; 1112 omax = 0; 1113 maybe_minus_zero = true; 1114 } else { 1115 omin = 0 - abs; 1116 omax = abs; 1117 maybe_minus_zero = true; 1118 } 1119 1120 Type* result = Type::Range(omin, omax, t->zone()); 1121 if (maybe_minus_zero) 1122 result = Type::Union(result, Type::MinusZero(), t->zone()); 1123 return result; 1124 } 1125 1126 1127 Type* Typer::Visitor::JSModulusTyper(Type* lhs, Type* rhs, Typer* t) { 1128 lhs = ToNumber(lhs, t); 1129 rhs = ToNumber(rhs, t); 1130 if (lhs->Is(Type::NaN()) || rhs->Is(Type::NaN())) return Type::NaN(); 1131 1132 if (lhs->Maybe(Type::NaN()) || rhs->Maybe(t->cache_.kZeroish) || 1133 lhs->Min() == -V8_INFINITY || lhs->Max() == +V8_INFINITY) { 1134 // Result maybe NaN. 1135 return Type::Number(); 1136 } 1137 1138 lhs = Rangify(lhs, t); 1139 rhs = Rangify(rhs, t); 1140 if (lhs->IsRange() && rhs->IsRange()) { 1141 return JSModulusRanger(lhs->AsRange(), rhs->AsRange(), t); 1142 } 1143 return Type::OrderedNumber(); 1144 } 1145 1146 1147 // JS unary operators. 1148 1149 1150 Type* Typer::Visitor::JSTypeOfTyper(Type* type, Typer* t) { 1151 Factory* const f = t->isolate()->factory(); 1152 if (type->Is(Type::Boolean())) { 1153 return Type::Constant(f->boolean_string(), t->zone()); 1154 } else if (type->Is(Type::Number())) { 1155 return Type::Constant(f->number_string(), t->zone()); 1156 } else if (type->Is(Type::String())) { 1157 return Type::Constant(f->string_string(), t->zone()); 1158 } else if (type->Is(Type::Symbol())) { 1159 return Type::Constant(f->symbol_string(), t->zone()); 1160 } else if (type->Is(Type::Union(Type::Undefined(), Type::Undetectable(), 1161 t->zone()))) { 1162 return Type::Constant(f->undefined_string(), t->zone()); 1163 } else if (type->Is(Type::Null())) { 1164 return Type::Constant(f->object_string(), t->zone()); 1165 } else if (type->Is(Type::Function())) { 1166 return Type::Constant(f->function_string(), t->zone()); 1167 } else if (type->IsConstant()) { 1168 return Type::Constant( 1169 Object::TypeOf(t->isolate(), type->AsConstant()->Value()), t->zone()); 1170 } 1171 return Type::InternalizedString(); 1172 } 1173 1174 1175 Type* Typer::Visitor::TypeJSTypeOf(Node* node) { 1176 return TypeUnaryOp(node, JSTypeOfTyper); 1177 } 1178 1179 1180 // JS conversion operators. 1181 1182 1183 Type* Typer::Visitor::TypeJSToBoolean(Node* node) { 1184 return TypeUnaryOp(node, ToBoolean); 1185 } 1186 1187 1188 Type* Typer::Visitor::TypeJSToNumber(Node* node) { 1189 return TypeUnaryOp(node, ToNumber); 1190 } 1191 1192 1193 Type* Typer::Visitor::TypeJSToString(Node* node) { 1194 return TypeUnaryOp(node, ToString); 1195 } 1196 1197 1198 Type* Typer::Visitor::TypeJSToName(Node* node) { 1199 return TypeUnaryOp(node, ToName); 1200 } 1201 1202 1203 Type* Typer::Visitor::TypeJSToObject(Node* node) { 1204 return TypeUnaryOp(node, ToObject); 1205 } 1206 1207 1208 // JS object operators. 1209 1210 1211 Type* Typer::Visitor::TypeJSCreate(Node* node) { return Type::Object(); } 1212 1213 1214 Type* Typer::Visitor::TypeJSCreateArguments(Node* node) { 1215 return Type::OtherObject(); 1216 } 1217 1218 1219 Type* Typer::Visitor::TypeJSCreateArray(Node* node) { 1220 return Type::OtherObject(); 1221 } 1222 1223 1224 Type* Typer::Visitor::TypeJSCreateClosure(Node* node) { 1225 return Type::Function(); 1226 } 1227 1228 1229 Type* Typer::Visitor::TypeJSCreateIterResultObject(Node* node) { 1230 return Type::OtherObject(); 1231 } 1232 1233 1234 Type* Typer::Visitor::TypeJSCreateLiteralArray(Node* node) { 1235 return Type::OtherObject(); 1236 } 1237 1238 1239 Type* Typer::Visitor::TypeJSCreateLiteralObject(Node* node) { 1240 return Type::OtherObject(); 1241 } 1242 1243 1244 Type* Typer::Visitor::TypeJSCreateLiteralRegExp(Node* node) { 1245 return Type::OtherObject(); 1246 } 1247 1248 1249 Type* Typer::Visitor::JSLoadPropertyTyper(Type* object, Type* name, Typer* t) { 1250 // TODO(rossberg): Use range types and sized array types to filter undefined. 1251 if (object->IsArray() && name->Is(Type::Integral32())) { 1252 return Type::Union( 1253 object->AsArray()->Element(), Type::Undefined(), t->zone()); 1254 } 1255 return Type::Any(); 1256 } 1257 1258 1259 Type* Typer::Visitor::TypeJSLoadProperty(Node* node) { 1260 return TypeBinaryOp(node, JSLoadPropertyTyper); 1261 } 1262 1263 1264 Type* Typer::Visitor::TypeJSLoadNamed(Node* node) { 1265 Factory* const f = isolate()->factory(); 1266 Handle<Name> name = NamedAccessOf(node->op()).name(); 1267 if (name.is_identical_to(f->prototype_string())) { 1268 Type* receiver = Operand(node, 0); 1269 if (receiver->Is(Type::None())) return Type::None(); 1270 if (receiver->IsConstant() && 1271 receiver->AsConstant()->Value()->IsJSFunction()) { 1272 Handle<JSFunction> function = 1273 Handle<JSFunction>::cast(receiver->AsConstant()->Value()); 1274 if (function->has_prototype()) { 1275 // We need to add a code dependency on the initial map of the {function} 1276 // in order to be notified about changes to "prototype" of {function}, 1277 // so we can only infer a constant type if deoptimization is enabled. 1278 if (flags() & kDeoptimizationEnabled) { 1279 JSFunction::EnsureHasInitialMap(function); 1280 Handle<Map> initial_map(function->initial_map(), isolate()); 1281 dependencies()->AssumeInitialMapCantChange(initial_map); 1282 return Type::Constant(handle(initial_map->prototype(), isolate()), 1283 zone()); 1284 } 1285 } 1286 } else if (receiver->IsClass() && 1287 receiver->AsClass()->Map()->IsJSFunctionMap()) { 1288 Handle<Map> map = receiver->AsClass()->Map(); 1289 return map->has_non_instance_prototype() ? Type::Primitive(zone()) 1290 : Type::Receiver(zone()); 1291 } 1292 } 1293 return Type::Any(); 1294 } 1295 1296 1297 Type* Typer::Visitor::TypeJSLoadGlobal(Node* node) { return Type::Any(); } 1298 1299 1300 // Returns a somewhat larger range if we previously assigned 1301 // a (smaller) range to this node. This is used to speed up 1302 // the fixpoint calculation in case there appears to be a loop 1303 // in the graph. In the current implementation, we are 1304 // increasing the limits to the closest power of two. 1305 Type* Typer::Visitor::Weaken(Node* node, Type* current_type, 1306 Type* previous_type) { 1307 static const double kWeakenMinLimits[] = { 1308 0.0, -1073741824.0, -2147483648.0, -4294967296.0, -8589934592.0, 1309 -17179869184.0, -34359738368.0, -68719476736.0, -137438953472.0, 1310 -274877906944.0, -549755813888.0, -1099511627776.0, -2199023255552.0, 1311 -4398046511104.0, -8796093022208.0, -17592186044416.0, -35184372088832.0, 1312 -70368744177664.0, -140737488355328.0, -281474976710656.0, 1313 -562949953421312.0}; 1314 static const double kWeakenMaxLimits[] = { 1315 0.0, 1073741823.0, 2147483647.0, 4294967295.0, 8589934591.0, 1316 17179869183.0, 34359738367.0, 68719476735.0, 137438953471.0, 1317 274877906943.0, 549755813887.0, 1099511627775.0, 2199023255551.0, 1318 4398046511103.0, 8796093022207.0, 17592186044415.0, 35184372088831.0, 1319 70368744177663.0, 140737488355327.0, 281474976710655.0, 1320 562949953421311.0}; 1321 STATIC_ASSERT(arraysize(kWeakenMinLimits) == arraysize(kWeakenMaxLimits)); 1322 1323 // If the types have nothing to do with integers, return the types. 1324 Type* const integer = typer_->cache_.kInteger; 1325 if (!previous_type->Maybe(integer)) { 1326 return current_type; 1327 } 1328 DCHECK(current_type->Maybe(integer)); 1329 1330 Type* current_integer = Type::Intersect(current_type, integer, zone()); 1331 Type* previous_integer = Type::Intersect(previous_type, integer, zone()); 1332 1333 // Once we start weakening a node, we should always weaken. 1334 if (!IsWeakened(node->id())) { 1335 // Only weaken if there is range involved; we should converge quickly 1336 // for all other types (the exception is a union of many constants, 1337 // but we currently do not increase the number of constants in unions). 1338 Type::RangeType* previous = previous_integer->GetRange(); 1339 Type::RangeType* current = current_integer->GetRange(); 1340 if (current == nullptr || previous == nullptr) { 1341 return current_type; 1342 } 1343 // Range is involved => we are weakening. 1344 SetWeakened(node->id()); 1345 } 1346 1347 double current_min = current_integer->Min(); 1348 double new_min = current_min; 1349 // Find the closest lower entry in the list of allowed 1350 // minima (or negative infinity if there is no such entry). 1351 if (current_min != previous_integer->Min()) { 1352 new_min = -V8_INFINITY; 1353 for (double const min : kWeakenMinLimits) { 1354 if (min <= current_min) { 1355 new_min = min; 1356 break; 1357 } 1358 } 1359 } 1360 1361 double current_max = current_integer->Max(); 1362 double new_max = current_max; 1363 // Find the closest greater entry in the list of allowed 1364 // maxima (or infinity if there is no such entry). 1365 if (current_max != previous_integer->Max()) { 1366 new_max = V8_INFINITY; 1367 for (double const max : kWeakenMaxLimits) { 1368 if (max >= current_max) { 1369 new_max = max; 1370 break; 1371 } 1372 } 1373 } 1374 1375 return Type::Union(current_type, 1376 Type::Range(new_min, new_max, typer_->zone()), 1377 typer_->zone()); 1378 } 1379 1380 1381 Type* Typer::Visitor::TypeJSStoreProperty(Node* node) { 1382 UNREACHABLE(); 1383 return nullptr; 1384 } 1385 1386 1387 Type* Typer::Visitor::TypeJSStoreNamed(Node* node) { 1388 UNREACHABLE(); 1389 return nullptr; 1390 } 1391 1392 1393 Type* Typer::Visitor::TypeJSStoreGlobal(Node* node) { 1394 UNREACHABLE(); 1395 return nullptr; 1396 } 1397 1398 1399 Type* Typer::Visitor::TypeJSDeleteProperty(Node* node) { 1400 return Type::Boolean(zone()); 1401 } 1402 1403 1404 Type* Typer::Visitor::TypeJSHasProperty(Node* node) { 1405 return Type::Boolean(zone()); 1406 } 1407 1408 1409 Type* Typer::Visitor::TypeJSInstanceOf(Node* node) { 1410 return Type::Boolean(zone()); 1411 } 1412 1413 1414 // JS context operators. 1415 1416 1417 Type* Typer::Visitor::TypeJSLoadContext(Node* node) { 1418 ContextAccess const& access = ContextAccessOf(node->op()); 1419 if (access.index() == Context::EXTENSION_INDEX) { 1420 return Type::TaggedPointer(); 1421 } 1422 // Since contexts are mutable, we just return the top. 1423 return Type::Any(); 1424 } 1425 1426 1427 Type* Typer::Visitor::TypeJSStoreContext(Node* node) { 1428 UNREACHABLE(); 1429 return nullptr; 1430 } 1431 1432 1433 Type* Typer::Visitor::TypeJSLoadDynamic(Node* node) { return Type::Any(); } 1434 1435 1436 Type* Typer::Visitor::WrapContextTypeForInput(Node* node) { 1437 Type* outer = TypeOrNone(NodeProperties::GetContextInput(node)); 1438 if (outer->Is(Type::None())) { 1439 return Type::None(); 1440 } else { 1441 DCHECK(outer->Maybe(Type::Internal())); 1442 return Type::Context(outer, zone()); 1443 } 1444 } 1445 1446 1447 Type* Typer::Visitor::TypeJSCreateFunctionContext(Node* node) { 1448 return WrapContextTypeForInput(node); 1449 } 1450 1451 1452 Type* Typer::Visitor::TypeJSCreateCatchContext(Node* node) { 1453 return WrapContextTypeForInput(node); 1454 } 1455 1456 1457 Type* Typer::Visitor::TypeJSCreateWithContext(Node* node) { 1458 return WrapContextTypeForInput(node); 1459 } 1460 1461 1462 Type* Typer::Visitor::TypeJSCreateBlockContext(Node* node) { 1463 return WrapContextTypeForInput(node); 1464 } 1465 1466 1467 Type* Typer::Visitor::TypeJSCreateModuleContext(Node* node) { 1468 // TODO(rossberg): this is probably incorrect 1469 return WrapContextTypeForInput(node); 1470 } 1471 1472 1473 Type* Typer::Visitor::TypeJSCreateScriptContext(Node* node) { 1474 return WrapContextTypeForInput(node); 1475 } 1476 1477 1478 // JS other operators. 1479 1480 1481 Type* Typer::Visitor::TypeJSYield(Node* node) { return Type::Any(); } 1482 1483 1484 Type* Typer::Visitor::TypeJSCallConstruct(Node* node) { 1485 return Type::Receiver(); 1486 } 1487 1488 1489 Type* Typer::Visitor::JSCallFunctionTyper(Type* fun, Typer* t) { 1490 if (fun->IsFunction()) { 1491 return fun->AsFunction()->Result(); 1492 } 1493 if (fun->IsConstant() && fun->AsConstant()->Value()->IsJSFunction()) { 1494 Handle<JSFunction> function = 1495 Handle<JSFunction>::cast(fun->AsConstant()->Value()); 1496 if (function->shared()->HasBuiltinFunctionId()) { 1497 switch (function->shared()->builtin_function_id()) { 1498 case kMathRandom: 1499 return Type::OrderedNumber(); 1500 case kMathFloor: 1501 case kMathRound: 1502 case kMathCeil: 1503 return t->cache_.kIntegerOrMinusZeroOrNaN; 1504 // Unary math functions. 1505 case kMathAbs: 1506 case kMathLog: 1507 case kMathExp: 1508 case kMathSqrt: 1509 case kMathCos: 1510 case kMathSin: 1511 case kMathTan: 1512 case kMathAcos: 1513 case kMathAsin: 1514 case kMathAtan: 1515 case kMathFround: 1516 return Type::Number(); 1517 // Binary math functions. 1518 case kMathAtan2: 1519 case kMathPow: 1520 case kMathMax: 1521 case kMathMin: 1522 return Type::Number(); 1523 case kMathImul: 1524 return Type::Signed32(); 1525 case kMathClz32: 1526 return t->cache_.kZeroToThirtyTwo; 1527 // String functions. 1528 case kStringCharAt: 1529 case kStringFromCharCode: 1530 return Type::String(); 1531 // Array functions. 1532 case kArrayIndexOf: 1533 case kArrayLastIndexOf: 1534 return Type::Number(); 1535 default: 1536 break; 1537 } 1538 } 1539 } 1540 return Type::Any(); 1541 } 1542 1543 1544 Type* Typer::Visitor::TypeJSCallFunction(Node* node) { 1545 // TODO(bmeurer): We could infer better types if we wouldn't ignore the 1546 // argument types for the JSCallFunctionTyper above. 1547 return TypeUnaryOp(node, JSCallFunctionTyper); 1548 } 1549 1550 1551 Type* Typer::Visitor::TypeJSCallRuntime(Node* node) { 1552 switch (CallRuntimeParametersOf(node->op()).id()) { 1553 case Runtime::kInlineIsSmi: 1554 case Runtime::kInlineIsArray: 1555 case Runtime::kInlineIsDate: 1556 case Runtime::kInlineIsTypedArray: 1557 case Runtime::kInlineIsMinusZero: 1558 case Runtime::kInlineIsFunction: 1559 case Runtime::kInlineIsRegExp: 1560 case Runtime::kInlineIsJSReceiver: 1561 return Type::Boolean(zone()); 1562 case Runtime::kInlineDoubleLo: 1563 case Runtime::kInlineDoubleHi: 1564 return Type::Signed32(); 1565 case Runtime::kInlineConstructDouble: 1566 case Runtime::kInlineMathFloor: 1567 case Runtime::kInlineMathSqrt: 1568 case Runtime::kInlineMathAcos: 1569 case Runtime::kInlineMathAsin: 1570 case Runtime::kInlineMathAtan: 1571 case Runtime::kInlineMathAtan2: 1572 return Type::Number(); 1573 case Runtime::kInlineMathClz32: 1574 return Type::Range(0, 32, zone()); 1575 case Runtime::kInlineCreateIterResultObject: 1576 case Runtime::kInlineRegExpConstructResult: 1577 return Type::OtherObject(); 1578 case Runtime::kInlineSubString: 1579 return Type::String(); 1580 case Runtime::kInlineToInteger: 1581 return TypeUnaryOp(node, ToInteger); 1582 case Runtime::kInlineToLength: 1583 return TypeUnaryOp(node, ToLength); 1584 case Runtime::kInlineToName: 1585 return TypeUnaryOp(node, ToName); 1586 case Runtime::kInlineToNumber: 1587 return TypeUnaryOp(node, ToNumber); 1588 case Runtime::kInlineToObject: 1589 return TypeUnaryOp(node, ToObject); 1590 case Runtime::kInlineToPrimitive: 1591 case Runtime::kInlineToPrimitive_Number: 1592 case Runtime::kInlineToPrimitive_String: 1593 return TypeUnaryOp(node, ToPrimitive); 1594 case Runtime::kInlineToString: 1595 return TypeUnaryOp(node, ToString); 1596 case Runtime::kHasInPrototypeChain: 1597 return Type::Boolean(); 1598 default: 1599 break; 1600 } 1601 return Type::Any(); 1602 } 1603 1604 1605 Type* Typer::Visitor::TypeJSConvertReceiver(Node* node) { 1606 return Type::Receiver(); 1607 } 1608 1609 1610 Type* Typer::Visitor::TypeJSForInNext(Node* node) { 1611 return Type::Union(Type::Name(), Type::Undefined(), zone()); 1612 } 1613 1614 1615 Type* Typer::Visitor::TypeJSForInPrepare(Node* node) { 1616 // TODO(bmeurer): Return a tuple type here. 1617 return Type::Any(); 1618 } 1619 1620 1621 Type* Typer::Visitor::TypeJSForInDone(Node* node) { 1622 return Type::Boolean(zone()); 1623 } 1624 1625 1626 Type* Typer::Visitor::TypeJSForInStep(Node* node) { 1627 STATIC_ASSERT(Map::EnumLengthBits::kMax <= FixedArray::kMaxLength); 1628 return Type::Range(1, FixedArray::kMaxLength + 1, zone()); 1629 } 1630 1631 1632 Type* Typer::Visitor::TypeJSLoadMessage(Node* node) { return Type::Any(); } 1633 1634 1635 Type* Typer::Visitor::TypeJSStoreMessage(Node* node) { 1636 UNREACHABLE(); 1637 return nullptr; 1638 } 1639 1640 1641 Type* Typer::Visitor::TypeJSStackCheck(Node* node) { return Type::Any(); } 1642 1643 1644 // Simplified operators. 1645 1646 1647 Type* Typer::Visitor::TypeBooleanNot(Node* node) { 1648 return Type::Boolean(zone()); 1649 } 1650 1651 1652 Type* Typer::Visitor::TypeBooleanToNumber(Node* node) { 1653 return TypeUnaryOp(node, ToNumber); 1654 } 1655 1656 1657 Type* Typer::Visitor::TypeNumberEqual(Node* node) { 1658 return Type::Boolean(zone()); 1659 } 1660 1661 1662 Type* Typer::Visitor::TypeNumberLessThan(Node* node) { 1663 return Type::Boolean(zone()); 1664 } 1665 1666 1667 Type* Typer::Visitor::TypeNumberLessThanOrEqual(Node* node) { 1668 return Type::Boolean(zone()); 1669 } 1670 1671 1672 Type* Typer::Visitor::TypeNumberAdd(Node* node) { return Type::Number(zone()); } 1673 1674 1675 Type* Typer::Visitor::TypeNumberSubtract(Node* node) { 1676 return Type::Number(zone()); 1677 } 1678 1679 1680 Type* Typer::Visitor::TypeNumberMultiply(Node* node) { 1681 return Type::Number(zone()); 1682 } 1683 1684 1685 Type* Typer::Visitor::TypeNumberDivide(Node* node) { 1686 return Type::Number(zone()); 1687 } 1688 1689 1690 Type* Typer::Visitor::TypeNumberModulus(Node* node) { 1691 return Type::Number(zone()); 1692 } 1693 1694 1695 Type* Typer::Visitor::TypeNumberBitwiseOr(Node* node) { 1696 return Type::Signed32(zone()); 1697 } 1698 1699 1700 Type* Typer::Visitor::TypeNumberBitwiseXor(Node* node) { 1701 return Type::Signed32(zone()); 1702 } 1703 1704 1705 Type* Typer::Visitor::TypeNumberBitwiseAnd(Node* node) { 1706 return Type::Signed32(zone()); 1707 } 1708 1709 1710 Type* Typer::Visitor::TypeNumberShiftLeft(Node* node) { 1711 return Type::Signed32(zone()); 1712 } 1713 1714 1715 Type* Typer::Visitor::TypeNumberShiftRight(Node* node) { 1716 return Type::Signed32(zone()); 1717 } 1718 1719 1720 Type* Typer::Visitor::TypeNumberShiftRightLogical(Node* node) { 1721 return Type::Unsigned32(zone()); 1722 } 1723 1724 1725 Type* Typer::Visitor::TypeNumberToInt32(Node* node) { 1726 return TypeUnaryOp(node, NumberToInt32); 1727 } 1728 1729 1730 Type* Typer::Visitor::TypeNumberToUint32(Node* node) { 1731 return TypeUnaryOp(node, NumberToUint32); 1732 } 1733 1734 1735 Type* Typer::Visitor::TypeNumberIsHoleNaN(Node* node) { 1736 return Type::Boolean(zone()); 1737 } 1738 1739 1740 Type* Typer::Visitor::TypePlainPrimitiveToNumber(Node* node) { 1741 return TypeUnaryOp(node, ToNumber); 1742 } 1743 1744 1745 // static 1746 Type* Typer::Visitor::ReferenceEqualTyper(Type* lhs, Type* rhs, Typer* t) { 1747 if (lhs->IsConstant() && rhs->Is(lhs)) { 1748 return t->singleton_true_; 1749 } 1750 return Type::Boolean(); 1751 } 1752 1753 1754 Type* Typer::Visitor::TypeReferenceEqual(Node* node) { 1755 return TypeBinaryOp(node, ReferenceEqualTyper); 1756 } 1757 1758 1759 Type* Typer::Visitor::TypeStringEqual(Node* node) { 1760 return Type::Boolean(zone()); 1761 } 1762 1763 1764 Type* Typer::Visitor::TypeStringLessThan(Node* node) { 1765 return Type::Boolean(zone()); 1766 } 1767 1768 1769 Type* Typer::Visitor::TypeStringLessThanOrEqual(Node* node) { 1770 return Type::Boolean(zone()); 1771 } 1772 1773 1774 namespace { 1775 1776 Type* ChangeRepresentation(Type* type, Type* rep, Zone* zone) { 1777 return Type::Union(Type::Semantic(type, zone), 1778 Type::Representation(rep, zone), zone); 1779 } 1780 1781 } // namespace 1782 1783 1784 Type* Typer::Visitor::TypeChangeTaggedToInt32(Node* node) { 1785 Type* arg = Operand(node, 0); 1786 // TODO(neis): DCHECK(arg->Is(Type::Signed32())); 1787 return ChangeRepresentation(arg, Type::UntaggedIntegral32(), zone()); 1788 } 1789 1790 1791 Type* Typer::Visitor::TypeChangeTaggedToUint32(Node* node) { 1792 Type* arg = Operand(node, 0); 1793 // TODO(neis): DCHECK(arg->Is(Type::Unsigned32())); 1794 return ChangeRepresentation(arg, Type::UntaggedIntegral32(), zone()); 1795 } 1796 1797 1798 Type* Typer::Visitor::TypeChangeTaggedToFloat64(Node* node) { 1799 Type* arg = Operand(node, 0); 1800 // TODO(neis): DCHECK(arg->Is(Type::Number())); 1801 return ChangeRepresentation(arg, Type::UntaggedFloat64(), zone()); 1802 } 1803 1804 1805 Type* Typer::Visitor::TypeChangeInt32ToTagged(Node* node) { 1806 Type* arg = Operand(node, 0); 1807 // TODO(neis): DCHECK(arg->Is(Type::Signed32())); 1808 Type* rep = 1809 arg->Is(Type::SignedSmall()) ? Type::TaggedSigned() : Type::Tagged(); 1810 return ChangeRepresentation(arg, rep, zone()); 1811 } 1812 1813 1814 Type* Typer::Visitor::TypeChangeUint32ToTagged(Node* node) { 1815 Type* arg = Operand(node, 0); 1816 // TODO(neis): DCHECK(arg->Is(Type::Unsigned32())); 1817 return ChangeRepresentation(arg, Type::Tagged(), zone()); 1818 } 1819 1820 1821 Type* Typer::Visitor::TypeChangeFloat64ToTagged(Node* node) { 1822 Type* arg = Operand(node, 0); 1823 // TODO(neis): CHECK(arg.upper->Is(Type::Number())); 1824 return ChangeRepresentation(arg, Type::Tagged(), zone()); 1825 } 1826 1827 1828 Type* Typer::Visitor::TypeChangeBoolToBit(Node* node) { 1829 Type* arg = Operand(node, 0); 1830 // TODO(neis): DCHECK(arg.upper->Is(Type::Boolean())); 1831 return ChangeRepresentation(arg, Type::UntaggedBit(), zone()); 1832 } 1833 1834 1835 Type* Typer::Visitor::TypeChangeBitToBool(Node* node) { 1836 Type* arg = Operand(node, 0); 1837 // TODO(neis): DCHECK(arg.upper->Is(Type::Boolean())); 1838 return ChangeRepresentation(arg, Type::TaggedPointer(), zone()); 1839 } 1840 1841 1842 Type* Typer::Visitor::TypeAllocate(Node* node) { return Type::TaggedPointer(); } 1843 1844 1845 namespace { 1846 1847 MaybeHandle<Map> GetStableMapFromObjectType(Type* object_type) { 1848 if (object_type->IsConstant() && 1849 object_type->AsConstant()->Value()->IsHeapObject()) { 1850 Handle<Map> object_map( 1851 Handle<HeapObject>::cast(object_type->AsConstant()->Value())->map()); 1852 if (object_map->is_stable()) return object_map; 1853 } else if (object_type->IsClass()) { 1854 Handle<Map> object_map = object_type->AsClass()->Map(); 1855 if (object_map->is_stable()) return object_map; 1856 } 1857 return MaybeHandle<Map>(); 1858 } 1859 1860 } // namespace 1861 1862 1863 Type* Typer::Visitor::TypeLoadField(Node* node) { 1864 FieldAccess const& access = FieldAccessOf(node->op()); 1865 if (access.base_is_tagged == kTaggedBase && 1866 access.offset == HeapObject::kMapOffset) { 1867 // The type of LoadField[Map](o) is Constant(map) if map is stable and 1868 // either 1869 // (a) o has type Constant(object) and map == object->map, or 1870 // (b) o has type Class(map), 1871 // and either 1872 // (1) map cannot transition further, or 1873 // (2) deoptimization is enabled and we can add a code dependency on the 1874 // stability of map (to guard the Constant type information). 1875 Type* const object = Operand(node, 0); 1876 if (object->Is(Type::None())) return Type::None(); 1877 Handle<Map> object_map; 1878 if (GetStableMapFromObjectType(object).ToHandle(&object_map)) { 1879 if (object_map->CanTransition()) { 1880 if (flags() & kDeoptimizationEnabled) { 1881 dependencies()->AssumeMapStable(object_map); 1882 } else { 1883 return access.type; 1884 } 1885 } 1886 Type* object_map_type = Type::Constant(object_map, zone()); 1887 DCHECK(object_map_type->Is(access.type)); 1888 return object_map_type; 1889 } 1890 } 1891 return access.type; 1892 } 1893 1894 1895 Type* Typer::Visitor::TypeLoadBuffer(Node* node) { 1896 // TODO(bmeurer): This typing is not yet correct. Since we can still access 1897 // out of bounds, the type in the general case has to include Undefined. 1898 switch (BufferAccessOf(node->op()).external_array_type()) { 1899 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \ 1900 case kExternal##Type##Array: \ 1901 return typer_->cache_.k##Type; 1902 TYPED_ARRAYS(TYPED_ARRAY_CASE) 1903 #undef TYPED_ARRAY_CASE 1904 } 1905 UNREACHABLE(); 1906 return nullptr; 1907 } 1908 1909 1910 Type* Typer::Visitor::TypeLoadElement(Node* node) { 1911 return ElementAccessOf(node->op()).type; 1912 } 1913 1914 1915 Type* Typer::Visitor::TypeStoreField(Node* node) { 1916 UNREACHABLE(); 1917 return nullptr; 1918 } 1919 1920 1921 Type* Typer::Visitor::TypeStoreBuffer(Node* node) { 1922 UNREACHABLE(); 1923 return nullptr; 1924 } 1925 1926 1927 Type* Typer::Visitor::TypeStoreElement(Node* node) { 1928 UNREACHABLE(); 1929 return nullptr; 1930 } 1931 1932 1933 Type* Typer::Visitor::TypeObjectIsNumber(Node* node) { 1934 Type* arg = Operand(node, 0); 1935 if (arg->Is(Type::None())) return Type::None(); 1936 if (arg->Is(Type::Number())) return typer_->singleton_true_; 1937 if (!arg->Maybe(Type::Number())) return typer_->singleton_false_; 1938 return Type::Boolean(); 1939 } 1940 1941 1942 Type* Typer::Visitor::TypeObjectIsSmi(Node* node) { 1943 Type* arg = Operand(node, 0); 1944 if (arg->Is(Type::None())) return Type::None(); 1945 if (arg->Is(Type::TaggedSigned())) return typer_->singleton_true_; 1946 if (arg->Is(Type::TaggedPointer())) return typer_->singleton_false_; 1947 return Type::Boolean(); 1948 } 1949 1950 1951 // Machine operators. 1952 1953 Type* Typer::Visitor::TypeLoad(Node* node) { return Type::Any(); } 1954 1955 1956 Type* Typer::Visitor::TypeStore(Node* node) { 1957 UNREACHABLE(); 1958 return nullptr; 1959 } 1960 1961 1962 Type* Typer::Visitor::TypeWord32And(Node* node) { return Type::Integral32(); } 1963 1964 1965 Type* Typer::Visitor::TypeWord32Or(Node* node) { return Type::Integral32(); } 1966 1967 1968 Type* Typer::Visitor::TypeWord32Xor(Node* node) { return Type::Integral32(); } 1969 1970 1971 Type* Typer::Visitor::TypeWord32Shl(Node* node) { return Type::Integral32(); } 1972 1973 1974 Type* Typer::Visitor::TypeWord32Shr(Node* node) { return Type::Integral32(); } 1975 1976 1977 Type* Typer::Visitor::TypeWord32Sar(Node* node) { return Type::Integral32(); } 1978 1979 1980 Type* Typer::Visitor::TypeWord32Ror(Node* node) { return Type::Integral32(); } 1981 1982 1983 Type* Typer::Visitor::TypeWord32Equal(Node* node) { return Type::Boolean(); } 1984 1985 1986 Type* Typer::Visitor::TypeWord32Clz(Node* node) { return Type::Integral32(); } 1987 1988 1989 Type* Typer::Visitor::TypeWord32Ctz(Node* node) { return Type::Integral32(); } 1990 1991 1992 Type* Typer::Visitor::TypeWord32Popcnt(Node* node) { 1993 return Type::Integral32(); 1994 } 1995 1996 1997 Type* Typer::Visitor::TypeWord64And(Node* node) { return Type::Internal(); } 1998 1999 2000 Type* Typer::Visitor::TypeWord64Or(Node* node) { return Type::Internal(); } 2001 2002 2003 Type* Typer::Visitor::TypeWord64Xor(Node* node) { return Type::Internal(); } 2004 2005 2006 Type* Typer::Visitor::TypeWord64Shl(Node* node) { return Type::Internal(); } 2007 2008 2009 Type* Typer::Visitor::TypeWord64Shr(Node* node) { return Type::Internal(); } 2010 2011 2012 Type* Typer::Visitor::TypeWord64Sar(Node* node) { return Type::Internal(); } 2013 2014 2015 Type* Typer::Visitor::TypeWord64Ror(Node* node) { return Type::Internal(); } 2016 2017 2018 Type* Typer::Visitor::TypeWord64Clz(Node* node) { return Type::Internal(); } 2019 2020 2021 Type* Typer::Visitor::TypeWord64Ctz(Node* node) { return Type::Internal(); } 2022 2023 2024 Type* Typer::Visitor::TypeWord64Popcnt(Node* node) { return Type::Internal(); } 2025 2026 2027 Type* Typer::Visitor::TypeWord64Equal(Node* node) { return Type::Boolean(); } 2028 2029 2030 Type* Typer::Visitor::TypeInt32Add(Node* node) { return Type::Integral32(); } 2031 2032 2033 Type* Typer::Visitor::TypeInt32AddWithOverflow(Node* node) { 2034 return Type::Internal(); 2035 } 2036 2037 2038 Type* Typer::Visitor::TypeInt32Sub(Node* node) { return Type::Integral32(); } 2039 2040 2041 Type* Typer::Visitor::TypeInt32SubWithOverflow(Node* node) { 2042 return Type::Internal(); 2043 } 2044 2045 2046 Type* Typer::Visitor::TypeInt32Mul(Node* node) { return Type::Integral32(); } 2047 2048 2049 Type* Typer::Visitor::TypeInt32MulHigh(Node* node) { return Type::Signed32(); } 2050 2051 2052 Type* Typer::Visitor::TypeInt32Div(Node* node) { return Type::Integral32(); } 2053 2054 2055 Type* Typer::Visitor::TypeInt32Mod(Node* node) { return Type::Integral32(); } 2056 2057 2058 Type* Typer::Visitor::TypeInt32LessThan(Node* node) { return Type::Boolean(); } 2059 2060 2061 Type* Typer::Visitor::TypeInt32LessThanOrEqual(Node* node) { 2062 return Type::Boolean(); 2063 } 2064 2065 2066 Type* Typer::Visitor::TypeUint32Div(Node* node) { return Type::Unsigned32(); } 2067 2068 2069 Type* Typer::Visitor::TypeUint32LessThan(Node* node) { return Type::Boolean(); } 2070 2071 2072 Type* Typer::Visitor::TypeUint32LessThanOrEqual(Node* node) { 2073 return Type::Boolean(); 2074 } 2075 2076 2077 Type* Typer::Visitor::TypeUint32Mod(Node* node) { return Type::Unsigned32(); } 2078 2079 2080 Type* Typer::Visitor::TypeUint32MulHigh(Node* node) { 2081 return Type::Unsigned32(); 2082 } 2083 2084 2085 Type* Typer::Visitor::TypeInt64Add(Node* node) { return Type::Internal(); } 2086 2087 2088 Type* Typer::Visitor::TypeInt64AddWithOverflow(Node* node) { 2089 return Type::Internal(); 2090 } 2091 2092 2093 Type* Typer::Visitor::TypeInt64Sub(Node* node) { return Type::Internal(); } 2094 2095 2096 Type* Typer::Visitor::TypeInt64SubWithOverflow(Node* node) { 2097 return Type::Internal(); 2098 } 2099 2100 2101 Type* Typer::Visitor::TypeInt64Mul(Node* node) { return Type::Internal(); } 2102 2103 2104 Type* Typer::Visitor::TypeInt64Div(Node* node) { return Type::Internal(); } 2105 2106 2107 Type* Typer::Visitor::TypeInt64Mod(Node* node) { return Type::Internal(); } 2108 2109 2110 Type* Typer::Visitor::TypeInt64LessThan(Node* node) { return Type::Boolean(); } 2111 2112 2113 Type* Typer::Visitor::TypeInt64LessThanOrEqual(Node* node) { 2114 return Type::Boolean(); 2115 } 2116 2117 2118 Type* Typer::Visitor::TypeUint64Div(Node* node) { return Type::Internal(); } 2119 2120 2121 Type* Typer::Visitor::TypeUint64LessThan(Node* node) { return Type::Boolean(); } 2122 2123 2124 Type* Typer::Visitor::TypeUint64LessThanOrEqual(Node* node) { 2125 return Type::Boolean(); 2126 } 2127 2128 2129 Type* Typer::Visitor::TypeUint64Mod(Node* node) { return Type::Internal(); } 2130 2131 2132 Type* Typer::Visitor::TypeChangeFloat32ToFloat64(Node* node) { 2133 return Type::Intersect(Type::Number(), Type::UntaggedFloat64(), zone()); 2134 } 2135 2136 2137 Type* Typer::Visitor::TypeChangeFloat64ToInt32(Node* node) { 2138 return Type::Intersect(Type::Signed32(), Type::UntaggedIntegral32(), zone()); 2139 } 2140 2141 2142 Type* Typer::Visitor::TypeChangeFloat64ToUint32(Node* node) { 2143 return Type::Intersect(Type::Unsigned32(), Type::UntaggedIntegral32(), 2144 zone()); 2145 } 2146 2147 2148 Type* Typer::Visitor::TypeTryTruncateFloat32ToInt64(Node* node) { 2149 return Type::Internal(); 2150 } 2151 2152 2153 Type* Typer::Visitor::TypeTryTruncateFloat64ToInt64(Node* node) { 2154 return Type::Internal(); 2155 } 2156 2157 2158 Type* Typer::Visitor::TypeTryTruncateFloat32ToUint64(Node* node) { 2159 return Type::Internal(); 2160 } 2161 2162 2163 Type* Typer::Visitor::TypeTryTruncateFloat64ToUint64(Node* node) { 2164 return Type::Internal(); 2165 } 2166 2167 2168 Type* Typer::Visitor::TypeChangeInt32ToFloat64(Node* node) { 2169 return Type::Intersect(Type::Signed32(), Type::UntaggedFloat64(), zone()); 2170 } 2171 2172 2173 Type* Typer::Visitor::TypeChangeInt32ToInt64(Node* node) { 2174 return Type::Internal(); 2175 } 2176 2177 2178 Type* Typer::Visitor::TypeChangeUint32ToFloat64(Node* node) { 2179 return Type::Intersect(Type::Unsigned32(), Type::UntaggedFloat64(), zone()); 2180 } 2181 2182 2183 Type* Typer::Visitor::TypeChangeUint32ToUint64(Node* node) { 2184 return Type::Internal(); 2185 } 2186 2187 2188 Type* Typer::Visitor::TypeTruncateFloat64ToFloat32(Node* node) { 2189 return Type::Intersect(Type::Number(), Type::UntaggedFloat32(), zone()); 2190 } 2191 2192 2193 Type* Typer::Visitor::TypeTruncateFloat64ToInt32(Node* node) { 2194 return Type::Intersect(Type::Signed32(), Type::UntaggedIntegral32(), zone()); 2195 } 2196 2197 2198 Type* Typer::Visitor::TypeTruncateInt64ToInt32(Node* node) { 2199 return Type::Intersect(Type::Signed32(), Type::UntaggedIntegral32(), zone()); 2200 } 2201 2202 2203 Type* Typer::Visitor::TypeRoundInt64ToFloat32(Node* node) { 2204 return Type::Intersect(Type::PlainNumber(), Type::UntaggedFloat32(), zone()); 2205 } 2206 2207 2208 Type* Typer::Visitor::TypeRoundInt64ToFloat64(Node* node) { 2209 return Type::Intersect(Type::PlainNumber(), Type::UntaggedFloat64(), zone()); 2210 } 2211 2212 2213 Type* Typer::Visitor::TypeRoundUint64ToFloat32(Node* node) { 2214 return Type::Intersect(Type::PlainNumber(), Type::UntaggedFloat32(), zone()); 2215 } 2216 2217 2218 Type* Typer::Visitor::TypeRoundUint64ToFloat64(Node* node) { 2219 return Type::Intersect(Type::PlainNumber(), Type::UntaggedFloat64(), zone()); 2220 } 2221 2222 2223 Type* Typer::Visitor::TypeBitcastFloat32ToInt32(Node* node) { 2224 return Type::Number(); 2225 } 2226 2227 2228 Type* Typer::Visitor::TypeBitcastFloat64ToInt64(Node* node) { 2229 return Type::Number(); 2230 } 2231 2232 2233 Type* Typer::Visitor::TypeBitcastInt32ToFloat32(Node* node) { 2234 return Type::Number(); 2235 } 2236 2237 2238 Type* Typer::Visitor::TypeBitcastInt64ToFloat64(Node* node) { 2239 return Type::Number(); 2240 } 2241 2242 2243 Type* Typer::Visitor::TypeFloat32Add(Node* node) { return Type::Number(); } 2244 2245 2246 Type* Typer::Visitor::TypeFloat32Sub(Node* node) { return Type::Number(); } 2247 2248 2249 Type* Typer::Visitor::TypeFloat32Mul(Node* node) { return Type::Number(); } 2250 2251 2252 Type* Typer::Visitor::TypeFloat32Div(Node* node) { return Type::Number(); } 2253 2254 2255 Type* Typer::Visitor::TypeFloat32Max(Node* node) { return Type::Number(); } 2256 2257 2258 Type* Typer::Visitor::TypeFloat32Min(Node* node) { return Type::Number(); } 2259 2260 2261 Type* Typer::Visitor::TypeFloat32Abs(Node* node) { 2262 // TODO(turbofan): We should be able to infer a better type here. 2263 return Type::Number(); 2264 } 2265 2266 2267 Type* Typer::Visitor::TypeFloat32Sqrt(Node* node) { return Type::Number(); } 2268 2269 2270 Type* Typer::Visitor::TypeFloat32Equal(Node* node) { return Type::Boolean(); } 2271 2272 2273 Type* Typer::Visitor::TypeFloat32LessThan(Node* node) { 2274 return Type::Boolean(); 2275 } 2276 2277 2278 Type* Typer::Visitor::TypeFloat32LessThanOrEqual(Node* node) { 2279 return Type::Boolean(); 2280 } 2281 2282 2283 Type* Typer::Visitor::TypeFloat64Add(Node* node) { return Type::Number(); } 2284 2285 2286 Type* Typer::Visitor::TypeFloat64Sub(Node* node) { return Type::Number(); } 2287 2288 2289 Type* Typer::Visitor::TypeFloat64Mul(Node* node) { return Type::Number(); } 2290 2291 2292 Type* Typer::Visitor::TypeFloat64Div(Node* node) { return Type::Number(); } 2293 2294 2295 Type* Typer::Visitor::TypeFloat64Mod(Node* node) { return Type::Number(); } 2296 2297 2298 Type* Typer::Visitor::TypeFloat64Max(Node* node) { return Type::Number(); } 2299 2300 2301 Type* Typer::Visitor::TypeFloat64Min(Node* node) { return Type::Number(); } 2302 2303 2304 Type* Typer::Visitor::TypeFloat64Abs(Node* node) { 2305 // TODO(turbofan): We should be able to infer a better type here. 2306 return Type::Number(); 2307 } 2308 2309 2310 Type* Typer::Visitor::TypeFloat64Sqrt(Node* node) { return Type::Number(); } 2311 2312 2313 Type* Typer::Visitor::TypeFloat64Equal(Node* node) { return Type::Boolean(); } 2314 2315 2316 Type* Typer::Visitor::TypeFloat64LessThan(Node* node) { 2317 return Type::Boolean(); 2318 } 2319 2320 2321 Type* Typer::Visitor::TypeFloat64LessThanOrEqual(Node* node) { 2322 return Type::Boolean(); 2323 } 2324 2325 2326 Type* Typer::Visitor::TypeFloat32RoundDown(Node* node) { 2327 // TODO(sigurds): We could have a tighter bound here. 2328 return Type::Number(); 2329 } 2330 2331 2332 Type* Typer::Visitor::TypeFloat64RoundDown(Node* node) { 2333 // TODO(sigurds): We could have a tighter bound here. 2334 return Type::Number(); 2335 } 2336 2337 2338 Type* Typer::Visitor::TypeFloat32RoundUp(Node* node) { 2339 // TODO(sigurds): We could have a tighter bound here. 2340 return Type::Number(); 2341 } 2342 2343 2344 Type* Typer::Visitor::TypeFloat64RoundUp(Node* node) { 2345 // TODO(sigurds): We could have a tighter bound here. 2346 return Type::Number(); 2347 } 2348 2349 2350 Type* Typer::Visitor::TypeFloat32RoundTruncate(Node* node) { 2351 // TODO(sigurds): We could have a tighter bound here. 2352 return Type::Number(); 2353 } 2354 2355 2356 Type* Typer::Visitor::TypeFloat64RoundTruncate(Node* node) { 2357 // TODO(sigurds): We could have a tighter bound here. 2358 return Type::Number(); 2359 } 2360 2361 2362 Type* Typer::Visitor::TypeFloat64RoundTiesAway(Node* node) { 2363 // TODO(sigurds): We could have a tighter bound here. 2364 return Type::Number(); 2365 } 2366 2367 2368 Type* Typer::Visitor::TypeFloat32RoundTiesEven(Node* node) { 2369 // TODO(sigurds): We could have a tighter bound here. 2370 return Type::Number(); 2371 } 2372 2373 2374 Type* Typer::Visitor::TypeFloat64RoundTiesEven(Node* node) { 2375 // TODO(sigurds): We could have a tighter bound here. 2376 return Type::Number(); 2377 } 2378 2379 2380 Type* Typer::Visitor::TypeFloat64ExtractLowWord32(Node* node) { 2381 return Type::Signed32(); 2382 } 2383 2384 2385 Type* Typer::Visitor::TypeFloat64ExtractHighWord32(Node* node) { 2386 return Type::Signed32(); 2387 } 2388 2389 2390 Type* Typer::Visitor::TypeFloat64InsertLowWord32(Node* node) { 2391 return Type::Number(); 2392 } 2393 2394 2395 Type* Typer::Visitor::TypeFloat64InsertHighWord32(Node* node) { 2396 return Type::Number(); 2397 } 2398 2399 2400 Type* Typer::Visitor::TypeLoadStackPointer(Node* node) { 2401 return Type::Internal(); 2402 } 2403 2404 2405 Type* Typer::Visitor::TypeLoadFramePointer(Node* node) { 2406 return Type::Internal(); 2407 } 2408 2409 2410 Type* Typer::Visitor::TypeCheckedLoad(Node* node) { return Type::Any(); } 2411 2412 2413 Type* Typer::Visitor::TypeCheckedStore(Node* node) { 2414 UNREACHABLE(); 2415 return nullptr; 2416 } 2417 2418 2419 // Heap constants. 2420 2421 2422 Type* Typer::Visitor::TypeConstant(Handle<Object> value) { 2423 if (value->IsJSTypedArray()) { 2424 switch (JSTypedArray::cast(*value)->type()) { 2425 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \ 2426 case kExternal##Type##Array: \ 2427 return typer_->cache_.k##Type##Array; 2428 TYPED_ARRAYS(TYPED_ARRAY_CASE) 2429 #undef TYPED_ARRAY_CASE 2430 } 2431 } 2432 if (Type::IsInteger(*value)) { 2433 return Type::Range(value->Number(), value->Number(), zone()); 2434 } 2435 return Type::Constant(value, zone()); 2436 } 2437 2438 } // namespace compiler 2439 } // namespace internal 2440 } // namespace v8 2441
