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 <deque>
8 #include <queue>
9
10 #include "src/compiler/generic-algorithm.h"
11 #include "src/compiler/generic-node-inl.h"
12 #include "src/compiler/generic-node.h"
13 #include "src/compiler/graph-inl.h"
14 #include "src/compiler/graph.h"
15 #include "src/compiler/node.h"
16 #include "src/compiler/node-properties-inl.h"
17 #include "src/compiler/node-properties.h"
18 #include "src/compiler/opcodes.h"
19 #include "src/compiler/operator.h"
20 #include "src/compiler/schedule.h"
21 #include "src/data-flow.h"
22
23 namespace v8 {
24 namespace internal {
25 namespace compiler {
26
27
IsDefUseChainLinkPresent(Node * def,Node * use)28 static bool IsDefUseChainLinkPresent(Node* def, Node* use) {
29 Node::Uses uses = def->uses();
30 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
31 if (*it == use) return true;
32 }
33 return false;
34 }
35
36
IsUseDefChainLinkPresent(Node * def,Node * use)37 static bool IsUseDefChainLinkPresent(Node* def, Node* use) {
38 Node::Inputs inputs = use->inputs();
39 for (Node::Inputs::iterator it = inputs.begin(); it != inputs.end(); ++it) {
40 if (*it == def) return true;
41 }
42 return false;
43 }
44
45
46 class Verifier::Visitor : public NullNodeVisitor {
47 public:
Visitor(Zone * zone)48 explicit Visitor(Zone* zone)
49 : reached_from_start(NodeSet::key_compare(),
50 NodeSet::allocator_type(zone)),
51 reached_from_end(NodeSet::key_compare(),
52 NodeSet::allocator_type(zone)) {}
53
54 // Fulfills the PreNodeCallback interface.
55 GenericGraphVisit::Control Pre(Node* node);
56
57 bool from_start;
58 NodeSet reached_from_start;
59 NodeSet reached_from_end;
60 };
61
62
Pre(Node * node)63 GenericGraphVisit::Control Verifier::Visitor::Pre(Node* node) {
64 int value_count = OperatorProperties::GetValueInputCount(node->op());
65 int context_count = OperatorProperties::GetContextInputCount(node->op());
66 int frame_state_count =
67 OperatorProperties::GetFrameStateInputCount(node->op());
68 int effect_count = OperatorProperties::GetEffectInputCount(node->op());
69 int control_count = OperatorProperties::GetControlInputCount(node->op());
70
71 // Verify number of inputs matches up.
72 int input_count = value_count + context_count + frame_state_count +
73 effect_count + control_count;
74 CHECK_EQ(input_count, node->InputCount());
75
76 // Verify that frame state has been inserted for the nodes that need it.
77 if (OperatorProperties::HasFrameStateInput(node->op())) {
78 Node* frame_state = NodeProperties::GetFrameStateInput(node);
79 CHECK(frame_state->opcode() == IrOpcode::kFrameState ||
80 // kFrameState uses undefined as a sentinel.
81 (node->opcode() == IrOpcode::kFrameState &&
82 frame_state->opcode() == IrOpcode::kHeapConstant));
83 CHECK(IsDefUseChainLinkPresent(frame_state, node));
84 CHECK(IsUseDefChainLinkPresent(frame_state, node));
85 }
86
87 // Verify all value inputs actually produce a value.
88 for (int i = 0; i < value_count; ++i) {
89 Node* value = NodeProperties::GetValueInput(node, i);
90 CHECK(OperatorProperties::HasValueOutput(value->op()));
91 CHECK(IsDefUseChainLinkPresent(value, node));
92 CHECK(IsUseDefChainLinkPresent(value, node));
93 }
94
95 // Verify all context inputs are value nodes.
96 for (int i = 0; i < context_count; ++i) {
97 Node* context = NodeProperties::GetContextInput(node);
98 CHECK(OperatorProperties::HasValueOutput(context->op()));
99 CHECK(IsDefUseChainLinkPresent(context, node));
100 CHECK(IsUseDefChainLinkPresent(context, node));
101 }
102
103 // Verify all effect inputs actually have an effect.
104 for (int i = 0; i < effect_count; ++i) {
105 Node* effect = NodeProperties::GetEffectInput(node);
106 CHECK(OperatorProperties::HasEffectOutput(effect->op()));
107 CHECK(IsDefUseChainLinkPresent(effect, node));
108 CHECK(IsUseDefChainLinkPresent(effect, node));
109 }
110
111 // Verify all control inputs are control nodes.
112 for (int i = 0; i < control_count; ++i) {
113 Node* control = NodeProperties::GetControlInput(node, i);
114 CHECK(OperatorProperties::HasControlOutput(control->op()));
115 CHECK(IsDefUseChainLinkPresent(control, node));
116 CHECK(IsUseDefChainLinkPresent(control, node));
117 }
118
119 // Verify all successors are projections if multiple value outputs exist.
120 if (OperatorProperties::GetValueOutputCount(node->op()) > 1) {
121 Node::Uses uses = node->uses();
122 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
123 CHECK(!NodeProperties::IsValueEdge(it.edge()) ||
124 (*it)->opcode() == IrOpcode::kProjection ||
125 (*it)->opcode() == IrOpcode::kParameter);
126 }
127 }
128
129 switch (node->opcode()) {
130 case IrOpcode::kStart:
131 // Start has no inputs.
132 CHECK_EQ(0, input_count);
133 break;
134 case IrOpcode::kEnd:
135 // End has no outputs.
136 CHECK(!OperatorProperties::HasValueOutput(node->op()));
137 CHECK(!OperatorProperties::HasEffectOutput(node->op()));
138 CHECK(!OperatorProperties::HasControlOutput(node->op()));
139 break;
140 case IrOpcode::kDead:
141 // Dead is never connected to the graph.
142 UNREACHABLE();
143 case IrOpcode::kBranch: {
144 // Branch uses are IfTrue and IfFalse.
145 Node::Uses uses = node->uses();
146 bool got_true = false, got_false = false;
147 for (Node::Uses::iterator it = uses.begin(); it != uses.end(); ++it) {
148 CHECK(((*it)->opcode() == IrOpcode::kIfTrue && !got_true) ||
149 ((*it)->opcode() == IrOpcode::kIfFalse && !got_false));
150 if ((*it)->opcode() == IrOpcode::kIfTrue) got_true = true;
151 if ((*it)->opcode() == IrOpcode::kIfFalse) got_false = true;
152 }
153 // TODO(rossberg): Currently fails for various tests.
154 // CHECK(got_true && got_false);
155 break;
156 }
157 case IrOpcode::kIfTrue:
158 case IrOpcode::kIfFalse:
159 CHECK_EQ(IrOpcode::kBranch,
160 NodeProperties::GetControlInput(node, 0)->opcode());
161 break;
162 case IrOpcode::kLoop:
163 case IrOpcode::kMerge:
164 break;
165 case IrOpcode::kReturn:
166 // TODO(rossberg): check successor is End
167 break;
168 case IrOpcode::kThrow:
169 // TODO(rossberg): what are the constraints on these?
170 break;
171 case IrOpcode::kParameter: {
172 // Parameters have the start node as inputs.
173 CHECK_EQ(1, input_count);
174 CHECK_EQ(IrOpcode::kStart,
175 NodeProperties::GetValueInput(node, 0)->opcode());
176 // Parameter has an input that produces enough values.
177 int index = OpParameter<int>(node);
178 Node* input = NodeProperties::GetValueInput(node, 0);
179 // Currently, parameter indices start at -1 instead of 0.
180 CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()), index + 1);
181 break;
182 }
183 case IrOpcode::kInt32Constant:
184 case IrOpcode::kInt64Constant:
185 case IrOpcode::kFloat64Constant:
186 case IrOpcode::kExternalConstant:
187 case IrOpcode::kNumberConstant:
188 case IrOpcode::kHeapConstant:
189 // Constants have no inputs.
190 CHECK_EQ(0, input_count);
191 break;
192 case IrOpcode::kPhi: {
193 // Phi input count matches parent control node.
194 CHECK_EQ(1, control_count);
195 Node* control = NodeProperties::GetControlInput(node, 0);
196 CHECK_EQ(value_count,
197 OperatorProperties::GetControlInputCount(control->op()));
198 break;
199 }
200 case IrOpcode::kEffectPhi: {
201 // EffectPhi input count matches parent control node.
202 CHECK_EQ(1, control_count);
203 Node* control = NodeProperties::GetControlInput(node, 0);
204 CHECK_EQ(effect_count,
205 OperatorProperties::GetControlInputCount(control->op()));
206 break;
207 }
208 case IrOpcode::kFrameState:
209 // TODO(jarin): what are the constraints on these?
210 break;
211 case IrOpcode::kCall:
212 // TODO(rossberg): what are the constraints on these?
213 break;
214 case IrOpcode::kProjection: {
215 // Projection has an input that produces enough values.
216 size_t index = OpParameter<size_t>(node);
217 Node* input = NodeProperties::GetValueInput(node, 0);
218 CHECK_GT(OperatorProperties::GetValueOutputCount(input->op()),
219 static_cast<int>(index));
220 break;
221 }
222 default:
223 // TODO(rossberg): Check other node kinds.
224 break;
225 }
226
227 if (from_start) {
228 reached_from_start.insert(node);
229 } else {
230 reached_from_end.insert(node);
231 }
232
233 return GenericGraphVisit::CONTINUE;
234 }
235
236
Run(Graph * graph)237 void Verifier::Run(Graph* graph) {
238 Visitor visitor(graph->zone());
239
240 CHECK_NE(NULL, graph->start());
241 visitor.from_start = true;
242 graph->VisitNodeUsesFromStart(&visitor);
243 CHECK_NE(NULL, graph->end());
244 visitor.from_start = false;
245 graph->VisitNodeInputsFromEnd(&visitor);
246
247 // All control nodes reachable from end are reachable from start.
248 for (NodeSet::iterator it = visitor.reached_from_end.begin();
249 it != visitor.reached_from_end.end(); ++it) {
250 CHECK(!NodeProperties::IsControl(*it) ||
251 visitor.reached_from_start.count(*it));
252 }
253 }
254
255
HasDominatingDef(Schedule * schedule,Node * node,BasicBlock * container,BasicBlock * use_block,int use_pos)256 static bool HasDominatingDef(Schedule* schedule, Node* node,
257 BasicBlock* container, BasicBlock* use_block,
258 int use_pos) {
259 BasicBlock* block = use_block;
260 while (true) {
261 while (use_pos >= 0) {
262 if (block->nodes_[use_pos] == node) return true;
263 use_pos--;
264 }
265 block = block->dominator_;
266 if (block == NULL) break;
267 use_pos = static_cast<int>(block->nodes_.size()) - 1;
268 if (node == block->control_input_) return true;
269 }
270 return false;
271 }
272
273
CheckInputsDominate(Schedule * schedule,BasicBlock * block,Node * node,int use_pos)274 static void CheckInputsDominate(Schedule* schedule, BasicBlock* block,
275 Node* node, int use_pos) {
276 for (int j = OperatorProperties::GetValueInputCount(node->op()) - 1; j >= 0;
277 j--) {
278 BasicBlock* use_block = block;
279 if (node->opcode() == IrOpcode::kPhi) {
280 use_block = use_block->PredecessorAt(j);
281 use_pos = static_cast<int>(use_block->nodes_.size()) - 1;
282 }
283 Node* input = node->InputAt(j);
284 if (!HasDominatingDef(schedule, node->InputAt(j), block, use_block,
285 use_pos)) {
286 V8_Fatal(__FILE__, __LINE__,
287 "Node #%d:%s in B%d is not dominated by input@%d #%d:%s",
288 node->id(), node->op()->mnemonic(), block->id(), j, input->id(),
289 input->op()->mnemonic());
290 }
291 }
292 }
293
294
Run(Schedule * schedule)295 void ScheduleVerifier::Run(Schedule* schedule) {
296 const int count = schedule->BasicBlockCount();
297 Zone tmp_zone(schedule->zone()->isolate());
298 Zone* zone = &tmp_zone;
299 BasicBlock* start = schedule->start();
300 BasicBlockVector* rpo_order = schedule->rpo_order();
301
302 // Verify the RPO order contains only blocks from this schedule.
303 CHECK_GE(count, static_cast<int>(rpo_order->size()));
304 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
305 ++b) {
306 CHECK_EQ((*b), schedule->GetBlockById((*b)->id()));
307 }
308
309 // Verify RPO numbers of blocks.
310 CHECK_EQ(start, rpo_order->at(0)); // Start should be first.
311 for (size_t b = 0; b < rpo_order->size(); b++) {
312 BasicBlock* block = rpo_order->at(b);
313 CHECK_EQ(static_cast<int>(b), block->rpo_number_);
314 BasicBlock* dom = block->dominator_;
315 if (b == 0) {
316 // All blocks except start should have a dominator.
317 CHECK_EQ(NULL, dom);
318 } else {
319 // Check that the immediate dominator appears somewhere before the block.
320 CHECK_NE(NULL, dom);
321 CHECK_LT(dom->rpo_number_, block->rpo_number_);
322 }
323 }
324
325 // Verify that all blocks reachable from start are in the RPO.
326 BoolVector marked(count, false, zone);
327 {
328 ZoneQueue<BasicBlock*> queue(zone);
329 queue.push(start);
330 marked[start->id()] = true;
331 while (!queue.empty()) {
332 BasicBlock* block = queue.front();
333 queue.pop();
334 for (int s = 0; s < block->SuccessorCount(); s++) {
335 BasicBlock* succ = block->SuccessorAt(s);
336 if (!marked[succ->id()]) {
337 marked[succ->id()] = true;
338 queue.push(succ);
339 }
340 }
341 }
342 }
343 // Verify marked blocks are in the RPO.
344 for (int i = 0; i < count; i++) {
345 BasicBlock* block = schedule->GetBlockById(i);
346 if (marked[i]) {
347 CHECK_GE(block->rpo_number_, 0);
348 CHECK_EQ(block, rpo_order->at(block->rpo_number_));
349 }
350 }
351 // Verify RPO blocks are marked.
352 for (size_t b = 0; b < rpo_order->size(); b++) {
353 CHECK(marked[rpo_order->at(b)->id()]);
354 }
355
356 {
357 // Verify the dominance relation.
358 ZoneList<BitVector*> dominators(count, zone);
359 dominators.Initialize(count, zone);
360 dominators.AddBlock(NULL, count, zone);
361
362 // Compute a set of all the nodes that dominate a given node by using
363 // a forward fixpoint. O(n^2).
364 ZoneQueue<BasicBlock*> queue(zone);
365 queue.push(start);
366 dominators[start->id()] = new (zone) BitVector(count, zone);
367 while (!queue.empty()) {
368 BasicBlock* block = queue.front();
369 queue.pop();
370 BitVector* block_doms = dominators[block->id()];
371 BasicBlock* idom = block->dominator_;
372 if (idom != NULL && !block_doms->Contains(idom->id())) {
373 V8_Fatal(__FILE__, __LINE__, "Block B%d is not dominated by B%d",
374 block->id(), idom->id());
375 }
376 for (int s = 0; s < block->SuccessorCount(); s++) {
377 BasicBlock* succ = block->SuccessorAt(s);
378 BitVector* succ_doms = dominators[succ->id()];
379
380 if (succ_doms == NULL) {
381 // First time visiting the node. S.doms = B U B.doms
382 succ_doms = new (zone) BitVector(count, zone);
383 succ_doms->CopyFrom(*block_doms);
384 succ_doms->Add(block->id());
385 dominators[succ->id()] = succ_doms;
386 queue.push(succ);
387 } else {
388 // Nth time visiting the successor. S.doms = S.doms ^ (B U B.doms)
389 bool had = succ_doms->Contains(block->id());
390 if (had) succ_doms->Remove(block->id());
391 if (succ_doms->IntersectIsChanged(*block_doms)) queue.push(succ);
392 if (had) succ_doms->Add(block->id());
393 }
394 }
395 }
396
397 // Verify the immediateness of dominators.
398 for (BasicBlockVector::iterator b = rpo_order->begin();
399 b != rpo_order->end(); ++b) {
400 BasicBlock* block = *b;
401 BasicBlock* idom = block->dominator_;
402 if (idom == NULL) continue;
403 BitVector* block_doms = dominators[block->id()];
404
405 for (BitVector::Iterator it(block_doms); !it.Done(); it.Advance()) {
406 BasicBlock* dom = schedule->GetBlockById(it.Current());
407 if (dom != idom && !dominators[idom->id()]->Contains(dom->id())) {
408 V8_Fatal(__FILE__, __LINE__,
409 "Block B%d is not immediately dominated by B%d", block->id(),
410 idom->id());
411 }
412 }
413 }
414 }
415
416 // Verify phis are placed in the block of their control input.
417 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
418 ++b) {
419 for (BasicBlock::const_iterator i = (*b)->begin(); i != (*b)->end(); ++i) {
420 Node* phi = *i;
421 if (phi->opcode() != IrOpcode::kPhi) continue;
422 // TODO(titzer): Nasty special case. Phis from RawMachineAssembler
423 // schedules don't have control inputs.
424 if (phi->InputCount() >
425 OperatorProperties::GetValueInputCount(phi->op())) {
426 Node* control = NodeProperties::GetControlInput(phi);
427 CHECK(control->opcode() == IrOpcode::kMerge ||
428 control->opcode() == IrOpcode::kLoop);
429 CHECK_EQ((*b), schedule->block(control));
430 }
431 }
432 }
433
434 // Verify that all uses are dominated by their definitions.
435 for (BasicBlockVector::iterator b = rpo_order->begin(); b != rpo_order->end();
436 ++b) {
437 BasicBlock* block = *b;
438
439 // Check inputs to control for this block.
440 Node* control = block->control_input_;
441 if (control != NULL) {
442 CHECK_EQ(block, schedule->block(control));
443 CheckInputsDominate(schedule, block, control,
444 static_cast<int>(block->nodes_.size()) - 1);
445 }
446 // Check inputs for all nodes in the block.
447 for (size_t i = 0; i < block->nodes_.size(); i++) {
448 Node* node = block->nodes_[i];
449 CheckInputsDominate(schedule, block, node, static_cast<int>(i) - 1);
450 }
451 }
452 }
453 }
454 }
455 } // namespace v8::internal::compiler
456