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