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