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/verifier.h" 6 7 #include <algorithm> 8 #include <deque> 9 #include <queue> 10 #include <sstream> 11 #include <string> 12 13 #include "src/bit-vector.h" 14 #include "src/compiler/all-nodes.h" 15 #include "src/compiler/common-operator.h" 16 #include "src/compiler/graph.h" 17 #include "src/compiler/node.h" 18 #include "src/compiler/node-properties.h" 19 #include "src/compiler/opcodes.h" 20 #include "src/compiler/operator.h" 21 #include "src/compiler/operator-properties.h" 22 #include "src/compiler/schedule.h" 23 #include "src/compiler/simplified-operator.h" 24 #include "src/ostreams.h" 25 26 namespace v8 { 27 namespace internal { 28 namespace compiler { 29 30 31 static bool IsDefUseChainLinkPresent(Node* def, Node* use) { 32 const Node::Uses uses = def->uses(); 33 return std::find(uses.begin(), uses.end(), use) != uses.end(); 34 } 35 36 37 static bool IsUseDefChainLinkPresent(Node* def, Node* use) { 38 const Node::Inputs inputs = use->inputs(); 39 return std::find(inputs.begin(), inputs.end(), def) != inputs.end(); 40 } 41 42 43 class Verifier::Visitor { 44 public: 45 Visitor(Zone* z, Typing typed, CheckInputs check_inputs) 46 : zone(z), typing(typed), check_inputs(check_inputs) {} 47 48 void Check(Node* node); 49 50 Zone* zone; 51 Typing typing; 52 CheckInputs check_inputs; 53 54 private: 55 void CheckNotTyped(Node* node) { 56 if (NodeProperties::IsTyped(node)) { 57 std::ostringstream str; 58 str << "TypeError: node #" << node->id() << ":" << *node->op() 59 << " should never have a type"; 60 FATAL(str.str().c_str()); 61 } 62 } 63 void CheckUpperIs(Node* node, Type* type) { 64 if (typing == TYPED && !NodeProperties::GetType(node)->Is(type)) { 65 std::ostringstream str; 66 str << "TypeError: node #" << node->id() << ":" << *node->op() 67 << " type "; 68 NodeProperties::GetType(node)->PrintTo(str); 69 str << " is not "; 70 type->PrintTo(str); 71 FATAL(str.str().c_str()); 72 } 73 } 74 void CheckUpperMaybe(Node* node, Type* type) { 75 if (typing == TYPED && !NodeProperties::GetType(node)->Maybe(type)) { 76 std::ostringstream str; 77 str << "TypeError: node #" << node->id() << ":" << *node->op() 78 << " type "; 79 NodeProperties::GetType(node)->PrintTo(str); 80 str << " must intersect "; 81 type->PrintTo(str); 82 FATAL(str.str().c_str()); 83 } 84 } 85 void CheckValueInputIs(Node* node, int i, Type* type) { 86 Node* input = NodeProperties::GetValueInput(node, i); 87 if (typing == TYPED && !NodeProperties::GetType(input)->Is(type)) { 88 std::ostringstream str; 89 str << "TypeError: node #" << node->id() << ":" << *node->op() 90 << "(input @" << i << " = " << input->opcode() << ":" 91 << input->op()->mnemonic() << ") type "; 92 NodeProperties::GetType(input)->PrintTo(str); 93 str << " is not "; 94 type->PrintTo(str); 95 FATAL(str.str().c_str()); 96 } 97 } 98 void CheckOutput(Node* node, Node* use, int count, const char* kind) { 99 if (count <= 0) { 100 std::ostringstream str; 101 str << "GraphError: node #" << node->id() << ":" << *node->op() 102 << " does not produce " << kind << " output used by node #" 103 << use->id() << ":" << *use->op(); 104 FATAL(str.str().c_str()); 105 } 106 } 107 }; 108 109 110 void Verifier::Visitor::Check(Node* node) { 111 int value_count = node->op()->ValueInputCount(); 112 int context_count = OperatorProperties::GetContextInputCount(node->op()); 113 int frame_state_count = 114 OperatorProperties::GetFrameStateInputCount(node->op()); 115 int effect_count = node->op()->EffectInputCount(); 116 int control_count = node->op()->ControlInputCount(); 117 118 // Verify number of inputs matches up. 119 int input_count = value_count + context_count + frame_state_count; 120 if (check_inputs == kAll) { 121 input_count += effect_count + control_count; 122 } 123 CHECK_EQ(input_count, node->InputCount()); 124 125 // Verify that frame state has been inserted for the nodes that need it. 126 for (int i = 0; i < frame_state_count; i++) { 127 Node* frame_state = NodeProperties::GetFrameStateInput(node, i); 128 CHECK(frame_state->opcode() == IrOpcode::kFrameState || 129 // kFrameState uses Start as a sentinel. 130 (node->opcode() == IrOpcode::kFrameState && 131 frame_state->opcode() == IrOpcode::kStart)); 132 CHECK(IsDefUseChainLinkPresent(frame_state, node)); 133 CHECK(IsUseDefChainLinkPresent(frame_state, node)); 134 } 135 136 // Verify all value inputs actually produce a value. 137 for (int i = 0; i < value_count; ++i) { 138 Node* value = NodeProperties::GetValueInput(node, i); 139 CheckOutput(value, node, value->op()->ValueOutputCount(), "value"); 140 CHECK(IsDefUseChainLinkPresent(value, node)); 141 CHECK(IsUseDefChainLinkPresent(value, node)); 142 // Verify that only parameters and projections can have input nodes with 143 // multiple outputs. 144 CHECK(node->opcode() == IrOpcode::kParameter || 145 node->opcode() == IrOpcode::kProjection || 146 value->op()->ValueOutputCount() <= 1); 147 } 148 149 // Verify all context inputs are value nodes. 150 for (int i = 0; i < context_count; ++i) { 151 Node* context = NodeProperties::GetContextInput(node); 152 CheckOutput(context, node, context->op()->ValueOutputCount(), "context"); 153 CHECK(IsDefUseChainLinkPresent(context, node)); 154 CHECK(IsUseDefChainLinkPresent(context, node)); 155 } 156 157 if (check_inputs == kAll) { 158 // Verify all effect inputs actually have an effect. 159 for (int i = 0; i < effect_count; ++i) { 160 Node* effect = NodeProperties::GetEffectInput(node); 161 CheckOutput(effect, node, effect->op()->EffectOutputCount(), "effect"); 162 CHECK(IsDefUseChainLinkPresent(effect, node)); 163 CHECK(IsUseDefChainLinkPresent(effect, node)); 164 } 165 166 // Verify all control inputs are control nodes. 167 for (int i = 0; i < control_count; ++i) { 168 Node* control = NodeProperties::GetControlInput(node, i); 169 CheckOutput(control, node, control->op()->ControlOutputCount(), 170 "control"); 171 CHECK(IsDefUseChainLinkPresent(control, node)); 172 CHECK(IsUseDefChainLinkPresent(control, node)); 173 } 174 } 175 176 switch (node->opcode()) { 177 case IrOpcode::kStart: 178 // Start has no inputs. 179 CHECK_EQ(0, input_count); 180 // Type is a tuple. 181 // TODO(rossberg): Multiple outputs are currently typed as Internal. 182 CheckUpperIs(node, Type::Internal()); 183 break; 184 case IrOpcode::kEnd: 185 // End has no outputs. 186 CHECK(node->op()->ValueOutputCount() == 0); 187 CHECK(node->op()->EffectOutputCount() == 0); 188 CHECK(node->op()->ControlOutputCount() == 0); 189 // Type is empty. 190 CheckNotTyped(node); 191 break; 192 case IrOpcode::kDead: 193 // Dead is never connected to the graph. 194 UNREACHABLE(); 195 break; 196 case IrOpcode::kBranch: { 197 // Branch uses are IfTrue and IfFalse. 198 int count_true = 0, count_false = 0; 199 for (const Node* use : node->uses()) { 200 CHECK(use->opcode() == IrOpcode::kIfTrue || 201 use->opcode() == IrOpcode::kIfFalse); 202 if (use->opcode() == IrOpcode::kIfTrue) ++count_true; 203 if (use->opcode() == IrOpcode::kIfFalse) ++count_false; 204 } 205 CHECK_EQ(1, count_true); 206 CHECK_EQ(1, count_false); 207 // Type is empty. 208 CheckNotTyped(node); 209 break; 210 } 211 case IrOpcode::kIfTrue: 212 case IrOpcode::kIfFalse: 213 CHECK_EQ(IrOpcode::kBranch, 214 NodeProperties::GetControlInput(node, 0)->opcode()); 215 // Type is empty. 216 CheckNotTyped(node); 217 break; 218 case IrOpcode::kIfSuccess: { 219 // IfSuccess and IfException continuation only on throwing nodes. 220 Node* input = NodeProperties::GetControlInput(node, 0); 221 CHECK(!input->op()->HasProperty(Operator::kNoThrow)); 222 // Type is empty. 223 CheckNotTyped(node); 224 break; 225 } 226 case IrOpcode::kIfException: { 227 // IfSuccess and IfException continuation only on throwing nodes. 228 Node* input = NodeProperties::GetControlInput(node, 0); 229 CHECK(!input->op()->HasProperty(Operator::kNoThrow)); 230 // Type can be anything. 231 CheckUpperIs(node, Type::Any()); 232 break; 233 } 234 case IrOpcode::kSwitch: { 235 // Switch uses are Case and Default. 236 int count_case = 0, count_default = 0; 237 for (const Node* use : node->uses()) { 238 switch (use->opcode()) { 239 case IrOpcode::kIfValue: { 240 for (const Node* user : node->uses()) { 241 if (user != use && user->opcode() == IrOpcode::kIfValue) { 242 CHECK_NE(OpParameter<int32_t>(use->op()), 243 OpParameter<int32_t>(user->op())); 244 } 245 } 246 ++count_case; 247 break; 248 } 249 case IrOpcode::kIfDefault: { 250 ++count_default; 251 break; 252 } 253 default: { 254 V8_Fatal(__FILE__, __LINE__, "Switch #%d illegally used by #%d:%s", 255 node->id(), use->id(), use->op()->mnemonic()); 256 break; 257 } 258 } 259 } 260 CHECK_EQ(1, count_default); 261 CHECK_EQ(node->op()->ControlOutputCount(), count_case + count_default); 262 // Type is empty. 263 CheckNotTyped(node); 264 break; 265 } 266 case IrOpcode::kIfValue: 267 case IrOpcode::kIfDefault: 268 CHECK_EQ(IrOpcode::kSwitch, 269 NodeProperties::GetControlInput(node)->opcode()); 270 // Type is empty. 271 CheckNotTyped(node); 272 break; 273 case IrOpcode::kLoop: 274 case IrOpcode::kMerge: 275 CHECK_EQ(control_count, input_count); 276 // Type is empty. 277 CheckNotTyped(node); 278 break; 279 case IrOpcode::kDeoptimizeIf: 280 case IrOpcode::kDeoptimizeUnless: 281 // Type is empty. 282 CheckNotTyped(node); 283 break; 284 case IrOpcode::kDeoptimize: 285 case IrOpcode::kReturn: 286 case IrOpcode::kThrow: 287 // Deoptimize, Return and Throw uses are End. 288 for (const Node* use : node->uses()) { 289 CHECK_EQ(IrOpcode::kEnd, use->opcode()); 290 } 291 // Type is empty. 292 CheckNotTyped(node); 293 break; 294 case IrOpcode::kTerminate: 295 // Terminates take one loop and effect. 296 CHECK_EQ(1, control_count); 297 CHECK_EQ(1, effect_count); 298 CHECK_EQ(2, input_count); 299 CHECK_EQ(IrOpcode::kLoop, 300 NodeProperties::GetControlInput(node)->opcode()); 301 // Terminate uses are End. 302 for (const Node* use : node->uses()) { 303 CHECK_EQ(IrOpcode::kEnd, use->opcode()); 304 } 305 // Type is empty. 306 CheckNotTyped(node); 307 break; 308 case IrOpcode::kOsrNormalEntry: 309 case IrOpcode::kOsrLoopEntry: 310 // Osr entries take one control and effect. 311 CHECK_EQ(1, control_count); 312 CHECK_EQ(1, effect_count); 313 CHECK_EQ(2, input_count); 314 // Type is empty. 315 CheckNotTyped(node); 316 break; 317 318 // Common operators 319 // ---------------- 320 case IrOpcode::kParameter: { 321 // Parameters have the start node as inputs. 322 CHECK_EQ(1, input_count); 323 // Parameter has an input that produces enough values. 324 int const index = ParameterIndexOf(node->op()); 325 Node* const start = NodeProperties::GetValueInput(node, 0); 326 CHECK_EQ(IrOpcode::kStart, start->opcode()); 327 // Currently, parameter indices start at -1 instead of 0. 328 CHECK_LE(-1, index); 329 CHECK_LT(index + 1, start->op()->ValueOutputCount()); 330 // Type can be anything. 331 CheckUpperIs(node, Type::Any()); 332 break; 333 } 334 case IrOpcode::kInt32Constant: // TODO(rossberg): rename Word32Constant? 335 // Constants have no inputs. 336 CHECK_EQ(0, input_count); 337 // Type is a 32 bit integer, signed or unsigned. 338 CheckUpperIs(node, Type::Integral32()); 339 break; 340 case IrOpcode::kInt64Constant: 341 // Constants have no inputs. 342 CHECK_EQ(0, input_count); 343 // Type is internal. 344 // TODO(rossberg): Introduce proper Int64 type. 345 CheckUpperIs(node, Type::Internal()); 346 break; 347 case IrOpcode::kFloat32Constant: 348 case IrOpcode::kFloat64Constant: 349 case IrOpcode::kNumberConstant: 350 // Constants have no inputs. 351 CHECK_EQ(0, input_count); 352 // Type is a number. 353 CheckUpperIs(node, Type::Number()); 354 break; 355 case IrOpcode::kRelocatableInt32Constant: 356 case IrOpcode::kRelocatableInt64Constant: 357 CHECK_EQ(0, input_count); 358 break; 359 case IrOpcode::kHeapConstant: 360 // Constants have no inputs. 361 CHECK_EQ(0, input_count); 362 // Type can be anything represented as a heap pointer. 363 CheckUpperIs(node, Type::TaggedPointer()); 364 break; 365 case IrOpcode::kExternalConstant: 366 // Constants have no inputs. 367 CHECK_EQ(0, input_count); 368 // Type is considered internal. 369 CheckUpperIs(node, Type::Internal()); 370 break; 371 case IrOpcode::kOsrValue: 372 // OSR values have a value and a control input. 373 CHECK_EQ(1, control_count); 374 CHECK_EQ(1, input_count); 375 // Type is merged from other values in the graph and could be any. 376 CheckUpperIs(node, Type::Any()); 377 break; 378 case IrOpcode::kProjection: { 379 // Projection has an input that produces enough values. 380 int index = static_cast<int>(ProjectionIndexOf(node->op())); 381 Node* input = NodeProperties::GetValueInput(node, 0); 382 CHECK_GT(input->op()->ValueOutputCount(), index); 383 // Type can be anything. 384 // TODO(rossberg): Introduce tuple types for this. 385 // TODO(titzer): Convince rossberg not to. 386 CheckUpperIs(node, Type::Any()); 387 break; 388 } 389 case IrOpcode::kSelect: { 390 CHECK_EQ(0, effect_count); 391 CHECK_EQ(0, control_count); 392 CHECK_EQ(3, value_count); 393 break; 394 } 395 case IrOpcode::kPhi: { 396 // Phi input count matches parent control node. 397 CHECK_EQ(0, effect_count); 398 CHECK_EQ(1, control_count); 399 Node* control = NodeProperties::GetControlInput(node, 0); 400 CHECK_EQ(value_count, control->op()->ControlInputCount()); 401 CHECK_EQ(input_count, 1 + value_count); 402 // Type must be subsumed by all input types. 403 // TODO(rossberg): for now at least, narrowing does not really hold. 404 /* 405 for (int i = 0; i < value_count; ++i) { 406 CHECK(type_of(ValueInput(node, i))->Is(type_of(node))); 407 } 408 */ 409 break; 410 } 411 case IrOpcode::kEffectPhi: { 412 // EffectPhi input count matches parent control node. 413 CHECK_EQ(0, value_count); 414 CHECK_EQ(1, control_count); 415 Node* control = NodeProperties::GetControlInput(node, 0); 416 CHECK_EQ(effect_count, control->op()->ControlInputCount()); 417 CHECK_EQ(input_count, 1 + effect_count); 418 break; 419 } 420 case IrOpcode::kTypeGuard: 421 // TODO(bmeurer): what are the constraints on these? 422 break; 423 case IrOpcode::kCheckpoint: 424 // Type is empty. 425 CheckNotTyped(node); 426 break; 427 case IrOpcode::kBeginRegion: 428 // TODO(rossberg): what are the constraints on these? 429 break; 430 case IrOpcode::kFinishRegion: { 431 // TODO(rossberg): what are the constraints on these? 432 // Type must be subsumed by input type. 433 if (typing == TYPED) { 434 Node* val = NodeProperties::GetValueInput(node, 0); 435 CHECK(NodeProperties::GetType(val)->Is(NodeProperties::GetType(node))); 436 } 437 break; 438 } 439 case IrOpcode::kFrameState: { 440 // TODO(jarin): what are the constraints on these? 441 CHECK_EQ(5, value_count); 442 CHECK_EQ(0, control_count); 443 CHECK_EQ(0, effect_count); 444 CHECK_EQ(6, input_count); 445 for (int i = 0; i < 3; ++i) { 446 CHECK(NodeProperties::GetValueInput(node, i)->opcode() == 447 IrOpcode::kStateValues || 448 NodeProperties::GetValueInput(node, i)->opcode() == 449 IrOpcode::kTypedStateValues); 450 } 451 break; 452 } 453 case IrOpcode::kStateValues: 454 case IrOpcode::kObjectState: 455 case IrOpcode::kTypedStateValues: 456 // TODO(jarin): what are the constraints on these? 457 break; 458 case IrOpcode::kCall: 459 // TODO(rossberg): what are the constraints on these? 460 break; 461 case IrOpcode::kTailCall: 462 // TODO(bmeurer): what are the constraints on these? 463 break; 464 465 // JavaScript operators 466 // -------------------- 467 case IrOpcode::kJSEqual: 468 case IrOpcode::kJSNotEqual: 469 case IrOpcode::kJSStrictEqual: 470 case IrOpcode::kJSStrictNotEqual: 471 case IrOpcode::kJSLessThan: 472 case IrOpcode::kJSGreaterThan: 473 case IrOpcode::kJSLessThanOrEqual: 474 case IrOpcode::kJSGreaterThanOrEqual: 475 // Type is Boolean. 476 CheckUpperIs(node, Type::Boolean()); 477 break; 478 479 case IrOpcode::kJSBitwiseOr: 480 case IrOpcode::kJSBitwiseXor: 481 case IrOpcode::kJSBitwiseAnd: 482 case IrOpcode::kJSShiftLeft: 483 case IrOpcode::kJSShiftRight: 484 case IrOpcode::kJSShiftRightLogical: 485 // Type is 32 bit integral. 486 CheckUpperIs(node, Type::Integral32()); 487 break; 488 case IrOpcode::kJSAdd: 489 // Type is Number or String. 490 CheckUpperIs(node, Type::NumberOrString()); 491 break; 492 case IrOpcode::kJSSubtract: 493 case IrOpcode::kJSMultiply: 494 case IrOpcode::kJSDivide: 495 case IrOpcode::kJSModulus: 496 // Type is Number. 497 CheckUpperIs(node, Type::Number()); 498 break; 499 500 case IrOpcode::kJSToBoolean: 501 // Type is Boolean. 502 CheckUpperIs(node, Type::Boolean()); 503 break; 504 case IrOpcode::kJSToInteger: 505 // Type is OrderedNumber. 506 CheckUpperIs(node, Type::OrderedNumber()); 507 break; 508 case IrOpcode::kJSToLength: 509 // Type is OrderedNumber. 510 CheckUpperIs(node, Type::OrderedNumber()); 511 break; 512 case IrOpcode::kJSToName: 513 // Type is Name. 514 CheckUpperIs(node, Type::Name()); 515 break; 516 case IrOpcode::kJSToNumber: 517 // Type is Number. 518 CheckUpperIs(node, Type::Number()); 519 break; 520 case IrOpcode::kJSToString: 521 // Type is String. 522 CheckUpperIs(node, Type::String()); 523 break; 524 case IrOpcode::kJSToObject: 525 // Type is Receiver. 526 CheckUpperIs(node, Type::Receiver()); 527 break; 528 529 case IrOpcode::kJSCreate: 530 // Type is Object. 531 CheckUpperIs(node, Type::Object()); 532 break; 533 case IrOpcode::kJSCreateArguments: 534 // Type is OtherObject. 535 CheckUpperIs(node, Type::OtherObject()); 536 break; 537 case IrOpcode::kJSCreateArray: 538 // Type is OtherObject. 539 CheckUpperIs(node, Type::OtherObject()); 540 break; 541 case IrOpcode::kJSCreateClosure: 542 // Type is Function. 543 CheckUpperIs(node, Type::Function()); 544 break; 545 case IrOpcode::kJSCreateIterResultObject: 546 // Type is OtherObject. 547 CheckUpperIs(node, Type::OtherObject()); 548 break; 549 case IrOpcode::kJSCreateLiteralArray: 550 case IrOpcode::kJSCreateLiteralObject: 551 case IrOpcode::kJSCreateLiteralRegExp: 552 // Type is OtherObject. 553 CheckUpperIs(node, Type::OtherObject()); 554 break; 555 case IrOpcode::kJSLoadProperty: 556 case IrOpcode::kJSLoadNamed: 557 case IrOpcode::kJSLoadGlobal: 558 // Type can be anything. 559 CheckUpperIs(node, Type::Any()); 560 break; 561 case IrOpcode::kJSStoreProperty: 562 case IrOpcode::kJSStoreNamed: 563 case IrOpcode::kJSStoreGlobal: 564 // Type is empty. 565 CheckNotTyped(node); 566 break; 567 case IrOpcode::kJSDeleteProperty: 568 case IrOpcode::kJSHasProperty: 569 case IrOpcode::kJSInstanceOf: 570 // Type is Boolean. 571 CheckUpperIs(node, Type::Boolean()); 572 break; 573 case IrOpcode::kJSTypeOf: 574 // Type is String. 575 CheckUpperIs(node, Type::String()); 576 break; 577 578 case IrOpcode::kJSLoadContext: 579 // Type can be anything. 580 CheckUpperIs(node, Type::Any()); 581 break; 582 case IrOpcode::kJSStoreContext: 583 // Type is empty. 584 CheckNotTyped(node); 585 break; 586 case IrOpcode::kJSCreateFunctionContext: 587 case IrOpcode::kJSCreateCatchContext: 588 case IrOpcode::kJSCreateWithContext: 589 case IrOpcode::kJSCreateBlockContext: 590 case IrOpcode::kJSCreateModuleContext: 591 case IrOpcode::kJSCreateScriptContext: { 592 // Type is Context, and operand is Internal. 593 Node* context = NodeProperties::GetContextInput(node); 594 // TODO(rossberg): This should really be Is(Internal), but the typer 595 // currently can't do backwards propagation. 596 CheckUpperMaybe(context, Type::Internal()); 597 if (typing == TYPED) CHECK(NodeProperties::GetType(node)->IsContext()); 598 break; 599 } 600 601 case IrOpcode::kJSCallConstruct: 602 case IrOpcode::kJSConvertReceiver: 603 // Type is Receiver. 604 CheckUpperIs(node, Type::Receiver()); 605 break; 606 case IrOpcode::kJSCallFunction: 607 case IrOpcode::kJSCallRuntime: 608 // Type can be anything. 609 CheckUpperIs(node, Type::Any()); 610 break; 611 612 case IrOpcode::kJSForInPrepare: { 613 // TODO(bmeurer): What are the constraints on thse? 614 CheckUpperIs(node, Type::Any()); 615 break; 616 } 617 case IrOpcode::kJSForInDone: { 618 // TODO(bmeurer): OSR breaks this invariant, although the node is not user 619 // visible, so we know it is safe (fullcodegen has an unsigned smi there). 620 // CheckValueInputIs(node, 0, Type::UnsignedSmall()); 621 break; 622 } 623 case IrOpcode::kJSForInNext: { 624 CheckUpperIs(node, Type::Union(Type::Name(), Type::Undefined(), zone)); 625 break; 626 } 627 case IrOpcode::kJSForInStep: { 628 // TODO(bmeurer): OSR breaks this invariant, although the node is not user 629 // visible, so we know it is safe (fullcodegen has an unsigned smi there). 630 // CheckValueInputIs(node, 0, Type::UnsignedSmall()); 631 CheckUpperIs(node, Type::UnsignedSmall()); 632 break; 633 } 634 635 case IrOpcode::kJSLoadMessage: 636 case IrOpcode::kJSStoreMessage: 637 break; 638 639 case IrOpcode::kJSGeneratorStore: 640 CheckNotTyped(node); 641 break; 642 643 case IrOpcode::kJSGeneratorRestoreContinuation: 644 CheckUpperIs(node, Type::SignedSmall()); 645 break; 646 647 case IrOpcode::kJSGeneratorRestoreRegister: 648 CheckUpperIs(node, Type::Any()); 649 break; 650 651 case IrOpcode::kJSStackCheck: 652 // Type is empty. 653 CheckNotTyped(node); 654 break; 655 656 case IrOpcode::kDebugBreak: 657 CheckNotTyped(node); 658 break; 659 660 case IrOpcode::kComment: 661 CheckNotTyped(node); 662 break; 663 664 // Simplified operators 665 // ------------------------------- 666 case IrOpcode::kBooleanNot: 667 // Boolean -> Boolean 668 CheckValueInputIs(node, 0, Type::Boolean()); 669 CheckUpperIs(node, Type::Boolean()); 670 break; 671 case IrOpcode::kBooleanToNumber: 672 // Boolean -> Number 673 CheckValueInputIs(node, 0, Type::Boolean()); 674 CheckUpperIs(node, Type::Number()); 675 break; 676 case IrOpcode::kNumberEqual: 677 // (Number, Number) -> Boolean 678 CheckValueInputIs(node, 0, Type::Number()); 679 CheckValueInputIs(node, 1, Type::Number()); 680 CheckUpperIs(node, Type::Boolean()); 681 break; 682 case IrOpcode::kNumberLessThan: 683 case IrOpcode::kNumberLessThanOrEqual: 684 // (Number, Number) -> Boolean 685 CheckValueInputIs(node, 0, Type::Number()); 686 CheckValueInputIs(node, 1, Type::Number()); 687 CheckUpperIs(node, Type::Boolean()); 688 break; 689 case IrOpcode::kSpeculativeNumberAdd: 690 case IrOpcode::kSpeculativeNumberSubtract: 691 case IrOpcode::kSpeculativeNumberMultiply: 692 case IrOpcode::kSpeculativeNumberDivide: 693 case IrOpcode::kSpeculativeNumberModulus: 694 CheckUpperIs(node, Type::Number()); 695 break; 696 case IrOpcode::kSpeculativeNumberEqual: 697 case IrOpcode::kSpeculativeNumberLessThan: 698 case IrOpcode::kSpeculativeNumberLessThanOrEqual: 699 CheckUpperIs(node, Type::Boolean()); 700 break; 701 case IrOpcode::kNumberAdd: 702 case IrOpcode::kNumberSubtract: 703 case IrOpcode::kNumberMultiply: 704 case IrOpcode::kNumberDivide: 705 // (Number, Number) -> Number 706 CheckValueInputIs(node, 0, Type::Number()); 707 CheckValueInputIs(node, 1, Type::Number()); 708 CheckUpperIs(node, Type::Number()); 709 break; 710 case IrOpcode::kNumberModulus: 711 // (Number, Number) -> Number 712 CheckValueInputIs(node, 0, Type::Number()); 713 CheckValueInputIs(node, 1, Type::Number()); 714 CheckUpperIs(node, Type::Number()); 715 break; 716 case IrOpcode::kNumberBitwiseOr: 717 case IrOpcode::kNumberBitwiseXor: 718 case IrOpcode::kNumberBitwiseAnd: 719 // (Signed32, Signed32) -> Signed32 720 CheckValueInputIs(node, 0, Type::Signed32()); 721 CheckValueInputIs(node, 1, Type::Signed32()); 722 CheckUpperIs(node, Type::Signed32()); 723 break; 724 case IrOpcode::kNumberShiftLeft: 725 case IrOpcode::kNumberShiftRight: 726 // (Signed32, Unsigned32) -> Signed32 727 CheckValueInputIs(node, 0, Type::Signed32()); 728 CheckValueInputIs(node, 1, Type::Unsigned32()); 729 CheckUpperIs(node, Type::Signed32()); 730 break; 731 case IrOpcode::kNumberShiftRightLogical: 732 // (Unsigned32, Unsigned32) -> Unsigned32 733 CheckValueInputIs(node, 0, Type::Unsigned32()); 734 CheckValueInputIs(node, 1, Type::Unsigned32()); 735 CheckUpperIs(node, Type::Unsigned32()); 736 break; 737 case IrOpcode::kNumberImul: 738 // (Unsigned32, Unsigned32) -> Signed32 739 CheckValueInputIs(node, 0, Type::Unsigned32()); 740 CheckValueInputIs(node, 1, Type::Unsigned32()); 741 CheckUpperIs(node, Type::Signed32()); 742 break; 743 case IrOpcode::kNumberClz32: 744 // Unsigned32 -> Unsigned32 745 CheckValueInputIs(node, 0, Type::Unsigned32()); 746 CheckUpperIs(node, Type::Unsigned32()); 747 break; 748 case IrOpcode::kNumberAtan2: 749 // (Number, Number) -> Number 750 CheckValueInputIs(node, 0, Type::Number()); 751 CheckValueInputIs(node, 1, Type::Number()); 752 CheckUpperIs(node, Type::Number()); 753 break; 754 case IrOpcode::kNumberAbs: 755 case IrOpcode::kNumberCeil: 756 case IrOpcode::kNumberFloor: 757 case IrOpcode::kNumberFround: 758 case IrOpcode::kNumberAtan: 759 case IrOpcode::kNumberAtanh: 760 case IrOpcode::kNumberCos: 761 case IrOpcode::kNumberExp: 762 case IrOpcode::kNumberExpm1: 763 case IrOpcode::kNumberLog: 764 case IrOpcode::kNumberLog1p: 765 case IrOpcode::kNumberLog2: 766 case IrOpcode::kNumberLog10: 767 case IrOpcode::kNumberCbrt: 768 case IrOpcode::kNumberRound: 769 case IrOpcode::kNumberSin: 770 case IrOpcode::kNumberSqrt: 771 case IrOpcode::kNumberTan: 772 case IrOpcode::kNumberTrunc: 773 // Number -> Number 774 CheckValueInputIs(node, 0, Type::Number()); 775 CheckUpperIs(node, Type::Number()); 776 break; 777 case IrOpcode::kNumberToInt32: 778 // Number -> Signed32 779 CheckValueInputIs(node, 0, Type::Number()); 780 CheckUpperIs(node, Type::Signed32()); 781 break; 782 case IrOpcode::kNumberToUint32: 783 // Number -> Unsigned32 784 CheckValueInputIs(node, 0, Type::Number()); 785 CheckUpperIs(node, Type::Unsigned32()); 786 break; 787 case IrOpcode::kPlainPrimitiveToNumber: 788 // Type is Number. 789 CheckUpperIs(node, Type::Number()); 790 break; 791 case IrOpcode::kPlainPrimitiveToWord32: 792 CheckUpperIs(node, Type::Number()); 793 break; 794 case IrOpcode::kPlainPrimitiveToFloat64: 795 CheckUpperIs(node, Type::Number()); 796 break; 797 case IrOpcode::kStringEqual: 798 case IrOpcode::kStringLessThan: 799 case IrOpcode::kStringLessThanOrEqual: 800 // (String, String) -> Boolean 801 CheckValueInputIs(node, 0, Type::String()); 802 CheckValueInputIs(node, 1, Type::String()); 803 CheckUpperIs(node, Type::Boolean()); 804 break; 805 case IrOpcode::kStringFromCharCode: 806 // Number -> String 807 CheckValueInputIs(node, 0, Type::Number()); 808 CheckUpperIs(node, Type::String()); 809 break; 810 case IrOpcode::kStringToNumber: 811 // String -> Number 812 CheckValueInputIs(node, 0, Type::String()); 813 CheckUpperIs(node, Type::Number()); 814 break; 815 case IrOpcode::kReferenceEqual: { 816 // (Unique, Any) -> Boolean and 817 // (Any, Unique) -> Boolean 818 CheckUpperIs(node, Type::Boolean()); 819 break; 820 } 821 case IrOpcode::kObjectIsCallable: 822 case IrOpcode::kObjectIsNumber: 823 case IrOpcode::kObjectIsReceiver: 824 case IrOpcode::kObjectIsSmi: 825 case IrOpcode::kObjectIsString: 826 case IrOpcode::kObjectIsUndetectable: 827 CheckValueInputIs(node, 0, Type::Any()); 828 CheckUpperIs(node, Type::Boolean()); 829 break; 830 case IrOpcode::kAllocate: 831 CheckValueInputIs(node, 0, Type::PlainNumber()); 832 CheckUpperIs(node, Type::TaggedPointer()); 833 break; 834 835 case IrOpcode::kChangeTaggedSignedToInt32: { 836 // Signed32 /\ Tagged -> Signed32 /\ UntaggedInt32 837 // TODO(neis): Activate once ChangeRepresentation works in typer. 838 // Type* from = Type::Intersect(Type::Signed32(), Type::Tagged()); 839 // Type* to = Type::Intersect(Type::Signed32(), Type::UntaggedInt32()); 840 // CheckValueInputIs(node, 0, from)); 841 // CheckUpperIs(node, to)); 842 break; 843 } 844 case IrOpcode::kChangeTaggedToInt32: { 845 // Signed32 /\ Tagged -> Signed32 /\ UntaggedInt32 846 // TODO(neis): Activate once ChangeRepresentation works in typer. 847 // Type* from = Type::Intersect(Type::Signed32(), Type::Tagged()); 848 // Type* to = Type::Intersect(Type::Signed32(), Type::UntaggedInt32()); 849 // CheckValueInputIs(node, 0, from)); 850 // CheckUpperIs(node, to)); 851 break; 852 } 853 case IrOpcode::kChangeTaggedToUint32: { 854 // Unsigned32 /\ Tagged -> Unsigned32 /\ UntaggedInt32 855 // TODO(neis): Activate once ChangeRepresentation works in typer. 856 // Type* from = Type::Intersect(Type::Unsigned32(), Type::Tagged()); 857 // Type* to =Type::Intersect(Type::Unsigned32(), Type::UntaggedInt32()); 858 // CheckValueInputIs(node, 0, from)); 859 // CheckUpperIs(node, to)); 860 break; 861 } 862 case IrOpcode::kChangeTaggedToFloat64: { 863 // NumberOrUndefined /\ Tagged -> Number /\ UntaggedFloat64 864 // TODO(neis): Activate once ChangeRepresentation works in typer. 865 // Type* from = Type::Intersect(Type::Number(), Type::Tagged()); 866 // Type* to = Type::Intersect(Type::Number(), Type::UntaggedFloat64()); 867 // CheckValueInputIs(node, 0, from)); 868 // CheckUpperIs(node, to)); 869 break; 870 } 871 case IrOpcode::kTruncateTaggedToFloat64: { 872 // NumberOrUndefined /\ Tagged -> Number /\ UntaggedFloat64 873 // TODO(neis): Activate once ChangeRepresentation works in typer. 874 // Type* from = Type::Intersect(Type::NumberOrUndefined(), 875 // Type::Tagged()); 876 // Type* to = Type::Intersect(Type::Number(), Type::UntaggedFloat64()); 877 // CheckValueInputIs(node, 0, from)); 878 // CheckUpperIs(node, to)); 879 break; 880 } 881 case IrOpcode::kChangeInt31ToTaggedSigned: { 882 // Signed31 /\ UntaggedInt32 -> Signed31 /\ Tagged 883 // TODO(neis): Activate once ChangeRepresentation works in typer. 884 // Type* from =Type::Intersect(Type::Signed31(), Type::UntaggedInt32()); 885 // Type* to = Type::Intersect(Type::Signed31(), Type::Tagged()); 886 // CheckValueInputIs(node, 0, from)); 887 // CheckUpperIs(node, to)); 888 break; 889 } 890 case IrOpcode::kChangeInt32ToTagged: { 891 // Signed32 /\ UntaggedInt32 -> Signed32 /\ Tagged 892 // TODO(neis): Activate once ChangeRepresentation works in typer. 893 // Type* from =Type::Intersect(Type::Signed32(), Type::UntaggedInt32()); 894 // Type* to = Type::Intersect(Type::Signed32(), Type::Tagged()); 895 // CheckValueInputIs(node, 0, from)); 896 // CheckUpperIs(node, to)); 897 break; 898 } 899 case IrOpcode::kChangeUint32ToTagged: { 900 // Unsigned32 /\ UntaggedInt32 -> Unsigned32 /\ Tagged 901 // TODO(neis): Activate once ChangeRepresentation works in typer. 902 // Type* from=Type::Intersect(Type::Unsigned32(),Type::UntaggedInt32()); 903 // Type* to = Type::Intersect(Type::Unsigned32(), Type::Tagged()); 904 // CheckValueInputIs(node, 0, from)); 905 // CheckUpperIs(node, to)); 906 break; 907 } 908 case IrOpcode::kChangeFloat64ToTagged: { 909 // Number /\ UntaggedFloat64 -> Number /\ Tagged 910 // TODO(neis): Activate once ChangeRepresentation works in typer. 911 // Type* from =Type::Intersect(Type::Number(), Type::UntaggedFloat64()); 912 // Type* to = Type::Intersect(Type::Number(), Type::Tagged()); 913 // CheckValueInputIs(node, 0, from)); 914 // CheckUpperIs(node, to)); 915 break; 916 } 917 case IrOpcode::kChangeTaggedToBit: { 918 // Boolean /\ TaggedPtr -> Boolean /\ UntaggedInt1 919 // TODO(neis): Activate once ChangeRepresentation works in typer. 920 // Type* from = Type::Intersect(Type::Boolean(), Type::TaggedPtr()); 921 // Type* to = Type::Intersect(Type::Boolean(), Type::UntaggedInt1()); 922 // CheckValueInputIs(node, 0, from)); 923 // CheckUpperIs(node, to)); 924 break; 925 } 926 case IrOpcode::kChangeBitToTagged: { 927 // Boolean /\ UntaggedInt1 -> Boolean /\ TaggedPtr 928 // TODO(neis): Activate once ChangeRepresentation works in typer. 929 // Type* from = Type::Intersect(Type::Boolean(), Type::UntaggedInt1()); 930 // Type* to = Type::Intersect(Type::Boolean(), Type::TaggedPtr()); 931 // CheckValueInputIs(node, 0, from)); 932 // CheckUpperIs(node, to)); 933 break; 934 } 935 case IrOpcode::kTruncateTaggedToWord32: { 936 // Number /\ Tagged -> Signed32 /\ UntaggedInt32 937 // TODO(neis): Activate once ChangeRepresentation works in typer. 938 // Type* from = Type::Intersect(Type::Number(), Type::Tagged()); 939 // Type* to = Type::Intersect(Type::Number(), Type::UntaggedInt32()); 940 // CheckValueInputIs(node, 0, from)); 941 // CheckUpperIs(node, to)); 942 break; 943 } 944 945 case IrOpcode::kCheckBounds: 946 CheckValueInputIs(node, 0, Type::Any()); 947 CheckValueInputIs(node, 1, Type::Unsigned31()); 948 CheckUpperIs(node, Type::Unsigned31()); 949 break; 950 case IrOpcode::kCheckTaggedSigned: 951 CheckValueInputIs(node, 0, Type::Any()); 952 CheckUpperIs(node, Type::TaggedSigned()); 953 break; 954 case IrOpcode::kCheckTaggedPointer: 955 CheckValueInputIs(node, 0, Type::Any()); 956 CheckUpperIs(node, Type::TaggedPointer()); 957 break; 958 959 case IrOpcode::kCheckedInt32Add: 960 case IrOpcode::kCheckedInt32Sub: 961 case IrOpcode::kCheckedUint32ToInt32: 962 case IrOpcode::kCheckedFloat64ToInt32: 963 case IrOpcode::kCheckedTaggedToInt32: 964 case IrOpcode::kCheckedTaggedToFloat64: 965 break; 966 967 case IrOpcode::kCheckFloat64Hole: 968 CheckValueInputIs(node, 0, Type::Number()); 969 CheckUpperIs(node, Type::Number()); 970 break; 971 case IrOpcode::kCheckTaggedHole: 972 CheckValueInputIs(node, 0, Type::Any()); 973 CheckUpperIs(node, Type::Any()); 974 break; 975 976 case IrOpcode::kLoadField: 977 // Object -> fieldtype 978 // TODO(rossberg): activate once machine ops are typed. 979 // CheckValueInputIs(node, 0, Type::Object()); 980 // CheckUpperIs(node, FieldAccessOf(node->op()).type)); 981 break; 982 case IrOpcode::kLoadBuffer: 983 break; 984 case IrOpcode::kLoadElement: 985 // Object -> elementtype 986 // TODO(rossberg): activate once machine ops are typed. 987 // CheckValueInputIs(node, 0, Type::Object()); 988 // CheckUpperIs(node, ElementAccessOf(node->op()).type)); 989 break; 990 case IrOpcode::kStoreField: 991 // (Object, fieldtype) -> _|_ 992 // TODO(rossberg): activate once machine ops are typed. 993 // CheckValueInputIs(node, 0, Type::Object()); 994 // CheckValueInputIs(node, 1, FieldAccessOf(node->op()).type)); 995 CheckNotTyped(node); 996 break; 997 case IrOpcode::kStoreBuffer: 998 break; 999 case IrOpcode::kStoreElement: 1000 // (Object, elementtype) -> _|_ 1001 // TODO(rossberg): activate once machine ops are typed. 1002 // CheckValueInputIs(node, 0, Type::Object()); 1003 // CheckValueInputIs(node, 1, ElementAccessOf(node->op()).type)); 1004 CheckNotTyped(node); 1005 break; 1006 case IrOpcode::kNumberSilenceNaN: 1007 CheckValueInputIs(node, 0, Type::Number()); 1008 CheckUpperIs(node, Type::Number()); 1009 break; 1010 1011 // Machine operators 1012 // ----------------------- 1013 case IrOpcode::kLoad: 1014 case IrOpcode::kStore: 1015 case IrOpcode::kStackSlot: 1016 case IrOpcode::kWord32And: 1017 case IrOpcode::kWord32Or: 1018 case IrOpcode::kWord32Xor: 1019 case IrOpcode::kWord32Shl: 1020 case IrOpcode::kWord32Shr: 1021 case IrOpcode::kWord32Sar: 1022 case IrOpcode::kWord32Ror: 1023 case IrOpcode::kWord32Equal: 1024 case IrOpcode::kWord32Clz: 1025 case IrOpcode::kWord32Ctz: 1026 case IrOpcode::kWord32ReverseBits: 1027 case IrOpcode::kWord32Popcnt: 1028 case IrOpcode::kWord64And: 1029 case IrOpcode::kWord64Or: 1030 case IrOpcode::kWord64Xor: 1031 case IrOpcode::kWord64Shl: 1032 case IrOpcode::kWord64Shr: 1033 case IrOpcode::kWord64Sar: 1034 case IrOpcode::kWord64Ror: 1035 case IrOpcode::kWord64Clz: 1036 case IrOpcode::kWord64Popcnt: 1037 case IrOpcode::kWord64Ctz: 1038 case IrOpcode::kWord64ReverseBits: 1039 case IrOpcode::kWord64Equal: 1040 case IrOpcode::kInt32Add: 1041 case IrOpcode::kInt32AddWithOverflow: 1042 case IrOpcode::kInt32Sub: 1043 case IrOpcode::kInt32SubWithOverflow: 1044 case IrOpcode::kInt32Mul: 1045 case IrOpcode::kInt32MulHigh: 1046 case IrOpcode::kInt32Div: 1047 case IrOpcode::kInt32Mod: 1048 case IrOpcode::kInt32LessThan: 1049 case IrOpcode::kInt32LessThanOrEqual: 1050 case IrOpcode::kUint32Div: 1051 case IrOpcode::kUint32Mod: 1052 case IrOpcode::kUint32MulHigh: 1053 case IrOpcode::kUint32LessThan: 1054 case IrOpcode::kUint32LessThanOrEqual: 1055 case IrOpcode::kInt64Add: 1056 case IrOpcode::kInt64AddWithOverflow: 1057 case IrOpcode::kInt64Sub: 1058 case IrOpcode::kInt64SubWithOverflow: 1059 case IrOpcode::kInt64Mul: 1060 case IrOpcode::kInt64Div: 1061 case IrOpcode::kInt64Mod: 1062 case IrOpcode::kInt64LessThan: 1063 case IrOpcode::kInt64LessThanOrEqual: 1064 case IrOpcode::kUint64Div: 1065 case IrOpcode::kUint64Mod: 1066 case IrOpcode::kUint64LessThan: 1067 case IrOpcode::kUint64LessThanOrEqual: 1068 case IrOpcode::kFloat32Add: 1069 case IrOpcode::kFloat32Sub: 1070 case IrOpcode::kFloat32SubPreserveNan: 1071 case IrOpcode::kFloat32Neg: 1072 case IrOpcode::kFloat32Mul: 1073 case IrOpcode::kFloat32Div: 1074 case IrOpcode::kFloat32Max: 1075 case IrOpcode::kFloat32Min: 1076 case IrOpcode::kFloat32Abs: 1077 case IrOpcode::kFloat32Sqrt: 1078 case IrOpcode::kFloat32Equal: 1079 case IrOpcode::kFloat32LessThan: 1080 case IrOpcode::kFloat32LessThanOrEqual: 1081 case IrOpcode::kFloat64Add: 1082 case IrOpcode::kFloat64Sub: 1083 case IrOpcode::kFloat64SubPreserveNan: 1084 case IrOpcode::kFloat64Neg: 1085 case IrOpcode::kFloat64Mul: 1086 case IrOpcode::kFloat64Div: 1087 case IrOpcode::kFloat64Mod: 1088 case IrOpcode::kFloat64Max: 1089 case IrOpcode::kFloat64Min: 1090 case IrOpcode::kFloat64Abs: 1091 case IrOpcode::kFloat64Atan: 1092 case IrOpcode::kFloat64Atan2: 1093 case IrOpcode::kFloat64Atanh: 1094 case IrOpcode::kFloat64Cos: 1095 case IrOpcode::kFloat64Exp: 1096 case IrOpcode::kFloat64Expm1: 1097 case IrOpcode::kFloat64Log: 1098 case IrOpcode::kFloat64Log1p: 1099 case IrOpcode::kFloat64Log2: 1100 case IrOpcode::kFloat64Log10: 1101 case IrOpcode::kFloat64Cbrt: 1102 case IrOpcode::kFloat64Sin: 1103 case IrOpcode::kFloat64Sqrt: 1104 case IrOpcode::kFloat64Tan: 1105 case IrOpcode::kFloat32RoundDown: 1106 case IrOpcode::kFloat64RoundDown: 1107 case IrOpcode::kFloat32RoundUp: 1108 case IrOpcode::kFloat64RoundUp: 1109 case IrOpcode::kFloat32RoundTruncate: 1110 case IrOpcode::kFloat64RoundTruncate: 1111 case IrOpcode::kFloat64RoundTiesAway: 1112 case IrOpcode::kFloat32RoundTiesEven: 1113 case IrOpcode::kFloat64RoundTiesEven: 1114 case IrOpcode::kFloat64Equal: 1115 case IrOpcode::kFloat64LessThan: 1116 case IrOpcode::kFloat64LessThanOrEqual: 1117 case IrOpcode::kTruncateInt64ToInt32: 1118 case IrOpcode::kRoundFloat64ToInt32: 1119 case IrOpcode::kRoundInt32ToFloat32: 1120 case IrOpcode::kRoundInt64ToFloat32: 1121 case IrOpcode::kRoundInt64ToFloat64: 1122 case IrOpcode::kRoundUint32ToFloat32: 1123 case IrOpcode::kRoundUint64ToFloat64: 1124 case IrOpcode::kRoundUint64ToFloat32: 1125 case IrOpcode::kTruncateFloat64ToFloat32: 1126 case IrOpcode::kTruncateFloat64ToWord32: 1127 case IrOpcode::kBitcastFloat32ToInt32: 1128 case IrOpcode::kBitcastFloat64ToInt64: 1129 case IrOpcode::kBitcastInt32ToFloat32: 1130 case IrOpcode::kBitcastInt64ToFloat64: 1131 case IrOpcode::kBitcastWordToTagged: 1132 case IrOpcode::kChangeInt32ToInt64: 1133 case IrOpcode::kChangeUint32ToUint64: 1134 case IrOpcode::kChangeInt32ToFloat64: 1135 case IrOpcode::kChangeUint32ToFloat64: 1136 case IrOpcode::kChangeFloat32ToFloat64: 1137 case IrOpcode::kChangeFloat64ToInt32: 1138 case IrOpcode::kChangeFloat64ToUint32: 1139 case IrOpcode::kFloat64SilenceNaN: 1140 case IrOpcode::kTruncateFloat64ToUint32: 1141 case IrOpcode::kTruncateFloat32ToInt32: 1142 case IrOpcode::kTruncateFloat32ToUint32: 1143 case IrOpcode::kTryTruncateFloat32ToInt64: 1144 case IrOpcode::kTryTruncateFloat64ToInt64: 1145 case IrOpcode::kTryTruncateFloat32ToUint64: 1146 case IrOpcode::kTryTruncateFloat64ToUint64: 1147 case IrOpcode::kFloat64ExtractLowWord32: 1148 case IrOpcode::kFloat64ExtractHighWord32: 1149 case IrOpcode::kFloat64InsertLowWord32: 1150 case IrOpcode::kFloat64InsertHighWord32: 1151 case IrOpcode::kInt32PairAdd: 1152 case IrOpcode::kInt32PairSub: 1153 case IrOpcode::kInt32PairMul: 1154 case IrOpcode::kWord32PairShl: 1155 case IrOpcode::kWord32PairShr: 1156 case IrOpcode::kWord32PairSar: 1157 case IrOpcode::kLoadStackPointer: 1158 case IrOpcode::kLoadFramePointer: 1159 case IrOpcode::kLoadParentFramePointer: 1160 case IrOpcode::kCheckedLoad: 1161 case IrOpcode::kCheckedStore: 1162 case IrOpcode::kAtomicLoad: 1163 case IrOpcode::kAtomicStore: 1164 1165 #define SIMD_MACHINE_OP_CASE(Name) case IrOpcode::k##Name: 1166 MACHINE_SIMD_OP_LIST(SIMD_MACHINE_OP_CASE) 1167 #undef SIMD_MACHINE_OP_CASE 1168 1169 // TODO(rossberg): Check. 1170 break; 1171 } 1172 } // NOLINT(readability/fn_size) 1173 1174 void Verifier::Run(Graph* graph, Typing typing, CheckInputs check_inputs) { 1175 CHECK_NOT_NULL(graph->start()); 1176 CHECK_NOT_NULL(graph->end()); 1177 Zone zone(graph->zone()->allocator()); 1178 Visitor visitor(&zone, typing, check_inputs); 1179 AllNodes all(&zone, graph); 1180 for (Node* node : all.live) visitor.Check(node); 1181 1182 // Check the uniqueness of projections. 1183 for (Node* proj : all.live) { 1184 if (proj->opcode() != IrOpcode::kProjection) continue; 1185 Node* node = proj->InputAt(0); 1186 for (Node* other : node->uses()) { 1187 if (all.IsLive(other) && other != proj && 1188 other->opcode() == IrOpcode::kProjection && 1189 ProjectionIndexOf(other->op()) == ProjectionIndexOf(proj->op())) { 1190 V8_Fatal(__FILE__, __LINE__, 1191 "Node #%d:%s has duplicate projections #%d and #%d", 1192 node->id(), node->op()->mnemonic(), proj->id(), other->id()); 1193 } 1194 } 1195 } 1196 } 1197 1198 1199 // ----------------------------------------------------------------------------- 1200 1201 static bool HasDominatingDef(Schedule* schedule, Node* node, 1202 BasicBlock* container, BasicBlock* use_block, 1203 int use_pos) { 1204 BasicBlock* block = use_block; 1205 while (true) { 1206 while (use_pos >= 0) { 1207 if (block->NodeAt(use_pos) == node) return true; 1208 use_pos--; 1209 } 1210 block = block->dominator(); 1211 if (block == nullptr) break; 1212 use_pos = static_cast<int>(block->NodeCount()) - 1; 1213 if (node == block->control_input()) return true; 1214 } 1215 return false; 1216 } 1217 1218 1219 static bool Dominates(Schedule* schedule, Node* dominator, Node* dominatee) { 1220 BasicBlock* dom = schedule->block(dominator); 1221 BasicBlock* sub = schedule->block(dominatee); 1222 while (sub != nullptr) { 1223 if (sub == dom) { 1224 return true; 1225 } 1226 sub = sub->dominator(); 1227 } 1228 return false; 1229 } 1230 1231 1232 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block, 1233 Node* node, int use_pos) { 1234 for (int j = node->op()->ValueInputCount() - 1; j >= 0; j--) { 1235 BasicBlock* use_block = block; 1236 if (node->opcode() == IrOpcode::kPhi) { 1237 use_block = use_block->PredecessorAt(j); 1238 use_pos = static_cast<int>(use_block->NodeCount()) - 1; 1239 } 1240 Node* input = node->InputAt(j); 1241 if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block, 1242 use_pos)) { 1243 V8_Fatal(__FILE__, __LINE__, 1244 "Node #%d:%s in B%d is not dominated by input@%d #%d:%s", 1245 node->id(), node->op()->mnemonic(), block->rpo_number(), j, 1246 input->id(), input->op()->mnemonic()); 1247 } 1248 } 1249 // Ensure that nodes are dominated by their control inputs; 1250 // kEnd is an exception, as unreachable blocks resulting from kMerge 1251 // are not in the RPO. 1252 if (node->op()->ControlInputCount() == 1 && 1253 node->opcode() != IrOpcode::kEnd) { 1254 Node* ctl = NodeProperties::GetControlInput(node); 1255 if (!Dominates(schedule, ctl, node)) { 1256 V8_Fatal(__FILE__, __LINE__, 1257 "Node #%d:%s in B%d is not dominated by control input #%d:%s", 1258 node->id(), node->op()->mnemonic(), block->rpo_number(), 1259 ctl->id(), ctl->op()->mnemonic()); 1260 } 1261 } 1262 } 1263 1264 1265 void ScheduleVerifier::Run(Schedule* schedule) { 1266 const size_t count = schedule->BasicBlockCount(); 1267 Zone tmp_zone(schedule->zone()->allocator()); 1268 Zone* zone = &tmp_zone; 1269 BasicBlock* start = schedule->start(); 1270 BasicBlockVector* rpo_order = schedule->rpo_order(); 1271 1272 // Verify the RPO order contains only blocks from this schedule. 1273 CHECK_GE(count, rpo_order->size()); 1274 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 1275 ++b) { 1276 CHECK_EQ((*b), schedule->GetBlockById((*b)->id())); 1277 // All predecessors and successors should be in rpo and in this schedule. 1278 for (BasicBlock const* predecessor : (*b)->predecessors()) { 1279 CHECK_GE(predecessor->rpo_number(), 0); 1280 CHECK_EQ(predecessor, schedule->GetBlockById(predecessor->id())); 1281 } 1282 for (BasicBlock const* successor : (*b)->successors()) { 1283 CHECK_GE(successor->rpo_number(), 0); 1284 CHECK_EQ(successor, schedule->GetBlockById(successor->id())); 1285 } 1286 } 1287 1288 // Verify RPO numbers of blocks. 1289 CHECK_EQ(start, rpo_order->at(0)); // Start should be first. 1290 for (size_t b = 0; b < rpo_order->size(); b++) { 1291 BasicBlock* block = rpo_order->at(b); 1292 CHECK_EQ(static_cast<int>(b), block->rpo_number()); 1293 BasicBlock* dom = block->dominator(); 1294 if (b == 0) { 1295 // All blocks except start should have a dominator. 1296 CHECK_NULL(dom); 1297 } else { 1298 // Check that the immediate dominator appears somewhere before the block. 1299 CHECK_NOT_NULL(dom); 1300 CHECK_LT(dom->rpo_number(), block->rpo_number()); 1301 } 1302 } 1303 1304 // Verify that all blocks reachable from start are in the RPO. 1305 BoolVector marked(static_cast<int>(count), false, zone); 1306 { 1307 ZoneQueue<BasicBlock*> queue(zone); 1308 queue.push(start); 1309 marked[start->id().ToSize()] = true; 1310 while (!queue.empty()) { 1311 BasicBlock* block = queue.front(); 1312 queue.pop(); 1313 for (size_t s = 0; s < block->SuccessorCount(); s++) { 1314 BasicBlock* succ = block->SuccessorAt(s); 1315 if (!marked[succ->id().ToSize()]) { 1316 marked[succ->id().ToSize()] = true; 1317 queue.push(succ); 1318 } 1319 } 1320 } 1321 } 1322 // Verify marked blocks are in the RPO. 1323 for (size_t i = 0; i < count; i++) { 1324 BasicBlock* block = schedule->GetBlockById(BasicBlock::Id::FromSize(i)); 1325 if (marked[i]) { 1326 CHECK_GE(block->rpo_number(), 0); 1327 CHECK_EQ(block, rpo_order->at(block->rpo_number())); 1328 } 1329 } 1330 // Verify RPO blocks are marked. 1331 for (size_t b = 0; b < rpo_order->size(); b++) { 1332 CHECK(marked[rpo_order->at(b)->id().ToSize()]); 1333 } 1334 1335 { 1336 // Verify the dominance relation. 1337 ZoneVector<BitVector*> dominators(zone); 1338 dominators.resize(count, nullptr); 1339 1340 // Compute a set of all the nodes that dominate a given node by using 1341 // a forward fixpoint. O(n^2). 1342 ZoneQueue<BasicBlock*> queue(zone); 1343 queue.push(start); 1344 dominators[start->id().ToSize()] = 1345 new (zone) BitVector(static_cast<int>(count), zone); 1346 while (!queue.empty()) { 1347 BasicBlock* block = queue.front(); 1348 queue.pop(); 1349 BitVector* block_doms = dominators[block->id().ToSize()]; 1350 BasicBlock* idom = block->dominator(); 1351 if (idom != nullptr && !block_doms->Contains(idom->id().ToInt())) { 1352 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d", 1353 block->rpo_number(), idom->rpo_number()); 1354 } 1355 for (size_t s = 0; s < block->SuccessorCount(); s++) { 1356 BasicBlock* succ = block->SuccessorAt(s); 1357 BitVector* succ_doms = dominators[succ->id().ToSize()]; 1358 1359 if (succ_doms == nullptr) { 1360 // First time visiting the node. S.doms = B U B.doms 1361 succ_doms = new (zone) BitVector(static_cast<int>(count), zone); 1362 succ_doms->CopyFrom(*block_doms); 1363 succ_doms->Add(block->id().ToInt()); 1364 dominators[succ->id().ToSize()] = succ_doms; 1365 queue.push(succ); 1366 } else { 1367 // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms) 1368 bool had = succ_doms->Contains(block->id().ToInt()); 1369 if (had) succ_doms->Remove(block->id().ToInt()); 1370 if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ); 1371 if (had) succ_doms->Add(block->id().ToInt()); 1372 } 1373 } 1374 } 1375 1376 // Verify the immediateness of dominators. 1377 for (BasicBlockVector::iterator b = rpo_order->begin(); 1378 b != rpo_order->end(); ++b) { 1379 BasicBlock* block = *b; 1380 BasicBlock* idom = block->dominator(); 1381 if (idom == nullptr) continue; 1382 BitVector* block_doms = dominators[block->id().ToSize()]; 1383 1384 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) { 1385 BasicBlock* dom = 1386 schedule->GetBlockById(BasicBlock::Id::FromInt(it.Current())); 1387 if (dom != idom && 1388 !dominators[idom->id().ToSize()]->Contains(dom->id().ToInt())) { 1389 V8_Fatal(__FILE__, __LINE__, 1390 "Block B%d is not immediately dominated by B%d", 1391 block->rpo_number(), idom->rpo_number()); 1392 } 1393 } 1394 } 1395 } 1396 1397 // Verify phis are placed in the block of their control input. 1398 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 1399 ++b) { 1400 for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) { 1401 Node* phi = *i; 1402 if (phi->opcode() != IrOpcode::kPhi) continue; 1403 // TODO(titzer): Nasty special case. Phis from RawMachineAssembler 1404 // schedules don't have control inputs. 1405 if (phi->InputCount() > phi->op()->ValueInputCount()) { 1406 Node* control = NodeProperties::GetControlInput(phi); 1407 CHECK(control->opcode() == IrOpcode::kMerge || 1408 control->opcode() == IrOpcode::kLoop); 1409 CHECK_EQ((*b), schedule->block(control)); 1410 } 1411 } 1412 } 1413 1414 // Verify that all uses are dominated by their definitions. 1415 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end(); 1416 ++b) { 1417 BasicBlock* block = *b; 1418 1419 // Check inputs to control for this block. 1420 Node* control = block->control_input(); 1421 if (control != nullptr) { 1422 CHECK_EQ(block, schedule->block(control)); 1423 CheckInputsDominate(schedule, block, control, 1424 static_cast<int>(block->NodeCount()) - 1); 1425 } 1426 // Check inputs for all nodes in the block. 1427 for (size_t i = 0; i < block->NodeCount(); i++) { 1428 Node* node = block->NodeAt(i); 1429 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1); 1430 } 1431 } 1432 } 1433 1434 1435 #ifdef DEBUG 1436 1437 // static 1438 void Verifier::VerifyNode(Node* node) { 1439 CHECK_EQ(OperatorProperties::GetTotalInputCount(node->op()), 1440 node->InputCount()); 1441 // If this node has no effect or no control outputs, 1442 // we check that no its uses are effect or control inputs. 1443 bool check_no_control = node->op()->ControlOutputCount() == 0; 1444 bool check_no_effect = node->op()->EffectOutputCount() == 0; 1445 bool check_no_frame_state = node->opcode() != IrOpcode::kFrameState; 1446 if (check_no_effect || check_no_control) { 1447 for (Edge edge : node->use_edges()) { 1448 Node* const user = edge.from(); 1449 CHECK(!user->IsDead()); 1450 if (NodeProperties::IsControlEdge(edge)) { 1451 CHECK(!check_no_control); 1452 } else if (NodeProperties::IsEffectEdge(edge)) { 1453 CHECK(!check_no_effect); 1454 } else if (NodeProperties::IsFrameStateEdge(edge)) { 1455 CHECK(!check_no_frame_state); 1456 } 1457 } 1458 } 1459 // Frame state inputs should be frame states (or sentinels). 1460 for (int i = 0; i < OperatorProperties::GetFrameStateInputCount(node->op()); 1461 i++) { 1462 Node* input = NodeProperties::GetFrameStateInput(node, i); 1463 CHECK(input->opcode() == IrOpcode::kFrameState || 1464 input->opcode() == IrOpcode::kStart || 1465 input->opcode() == IrOpcode::kDead); 1466 } 1467 // Effect inputs should be effect-producing nodes (or sentinels). 1468 for (int i = 0; i < node->op()->EffectInputCount(); i++) { 1469 Node* input = NodeProperties::GetEffectInput(node, i); 1470 CHECK(input->op()->EffectOutputCount() > 0 || 1471 input->opcode() == IrOpcode::kDead); 1472 } 1473 // Control inputs should be control-producing nodes (or sentinels). 1474 for (int i = 0; i < node->op()->ControlInputCount(); i++) { 1475 Node* input = NodeProperties::GetControlInput(node, i); 1476 CHECK(input->op()->ControlOutputCount() > 0 || 1477 input->opcode() == IrOpcode::kDead); 1478 } 1479 } 1480 1481 1482 void Verifier::VerifyEdgeInputReplacement(const Edge& edge, 1483 const Node* replacement) { 1484 // Check that the user does not misuse the replacement. 1485 DCHECK(!NodeProperties::IsControlEdge(edge) || 1486 replacement->op()->ControlOutputCount() > 0); 1487 DCHECK(!NodeProperties::IsEffectEdge(edge) || 1488 replacement->op()->EffectOutputCount() > 0); 1489 DCHECK(!NodeProperties::IsFrameStateEdge(edge) || 1490 replacement->opcode() == IrOpcode::kFrameState); 1491 } 1492 1493 #endif // DEBUG 1494 1495 } // namespace compiler 1496 } // namespace internal 1497 } // namespace v8 1498
