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