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