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
IsDefUseChainLinkPresent(Node * def,Node * use)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
IsUseDefChainLinkPresent(Node * def,Node * use)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:
Visitor(Zone * z,Typing typed)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:
CheckNotTyped(Node * node)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 }
CheckUpperIs(Node * node,Type * type)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 }
CheckUpperMaybe(Node * node,Type * type)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 }
CheckValueInputIs(Node * node,int i,Type * type)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 }
CheckOutput(Node * node,Node * use,int count,const char * kind)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
Check(Node * node)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
Run(Graph * graph,Typing typing)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
HasDominatingDef(Schedule * schedule,Node * node,BasicBlock * container,BasicBlock * use_block,int use_pos)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
Dominates(Schedule * schedule,Node * dominator,Node * dominatee)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
CheckInputsDominate(Schedule * schedule,BasicBlock * block,Node * node,int use_pos)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
Run(Schedule * schedule)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
VerifyNode(Node * node)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
VerifyEdgeInputReplacement(const Edge & edge,const Node * replacement)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