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