1// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#if defined(DEBUG)
6
7#include "vm/compiler/backend/flow_graph_checker.h"
8
9#include "vm/compiler/backend/flow_graph.h"
10#include "vm/compiler/backend/il.h"
11#include "vm/compiler/backend/loops.h"
12
13namespace dart {
14
15DECLARE_FLAG(bool, trace_compiler);
16
17DEFINE_FLAG(int,
18 verify_definitions_threshold,
19 250,
20 "Definition count threshold for extensive instruction checks");
21
22// Returns true for the "optimized out" and "null" constant.
23// Such constants reside outside the IR in the sense that
24// succ/pred/block links are not maintained.
25static bool IsSpecialConstant(Definition* def) {
26 if (auto c = def->AsConstant()) {
27 return c->value().raw() == Symbols::OptimizedOut().raw() ||
28 c->value().raw() == Object::ZoneHandle().raw();
29 }
30 return false;
31}
32
33// Returns true if block is a predecessor of succ.
34static bool IsPred(BlockEntryInstr* block, BlockEntryInstr* succ) {
35 for (intptr_t i = 0, n = succ->PredecessorCount(); i < n; ++i) {
36 if (succ->PredecessorAt(i) == block) {
37 return true;
38 }
39 }
40 return false;
41}
42
43// Returns true if block is a successor of pred.
44static bool IsSucc(BlockEntryInstr* block, BlockEntryInstr* pred) {
45 Instruction* last = pred->last_instruction();
46 for (intptr_t i = 0, n = last->SuccessorCount(); i < n; ++i) {
47 if (last->SuccessorAt(i) == block) {
48 return true;
49 }
50 }
51 return false;
52}
53
54// Returns true if dom directly dominates block.
55static bool IsDirectlyDominated(BlockEntryInstr* block, BlockEntryInstr* dom) {
56 for (intptr_t i = 0, n = dom->dominated_blocks().length(); i < n; ++i) {
57 if (dom->dominated_blocks()[i] == block) {
58 return true;
59 }
60 }
61 return false;
62}
63
64// Returns true if instruction appears in use list.
65static bool IsInUseList(Value* use, Instruction* instruction) {
66 for (; use != nullptr; use = use->next_use()) {
67 if (use->instruction() == instruction) {
68 return true;
69 }
70 }
71 return false;
72}
73
74// Returns true if definition dominates instruction. Note that this
75// helper is required to account for some situations that are not
76// accounted for in the IR methods that compute dominance.
77static bool DefDominatesUse(Definition* def, Instruction* instruction) {
78 if (instruction->IsPhi()) {
79 // A phi use is not necessarily dominated by a definition.
80 // Proper dominance relation on the input values of Phis is
81 // checked by the Phi visitor below.
82 return true;
83 } else if (def->IsMaterializeObject() || instruction->IsMaterializeObject()) {
84 // These instructions reside outside the IR.
85 return true;
86 } else if (auto entry =
87 instruction->GetBlock()->AsBlockEntryWithInitialDefs()) {
88 // An initial definition in the same block.
89 // TODO(ajcbik): use an initial def too?
90 for (auto idef : *entry->initial_definitions()) {
91 if (idef == def) {
92 return true;
93 }
94 }
95 }
96 // Use the standard IR method for dominance.
97 return instruction->IsDominatedBy(def);
98}
99
100// Returns true if instruction forces control flow.
101static bool IsControlFlow(Instruction* instruction) {
102 return instruction->IsBranch() || instruction->IsGoto() ||
103 instruction->IsIndirectGoto() || instruction->IsReturn() ||
104 instruction->IsThrow() || instruction->IsReThrow() ||
105 instruction->IsTailCall();
106}
107
108// Asserts that arguments appear in environment at the right place.
109static void AssertArgumentsInEnv(FlowGraph* flow_graph, Definition* call) {
110 Environment* env = call->env();
111 if (env == nullptr) {
112 // Environments can be removed by EliminateEnvironments pass and
113 // are not present before SSA.
114 } else if (flow_graph->function().IsIrregexpFunction()) {
115 // TODO(dartbug.com/38577): cleanup regexp pipeline too....
116 } else {
117 // Otherwise, the trailing environment entries must
118 // correspond directly with the arguments.
119 const intptr_t env_count = env->Length();
120 const intptr_t arg_count = call->ArgumentCount();
121 ASSERT(arg_count <= env_count);
122 const intptr_t env_base = env_count - arg_count;
123 for (intptr_t i = 0; i < arg_count; i++) {
124 if (call->HasPushArguments()) {
125 ASSERT(call->ArgumentAt(i) == env->ValueAt(env_base + i)
126 ->definition()
127 ->AsPushArgument()
128 ->value()
129 ->definition());
130 } else {
131 // Redefintion instructions and boxing/unboxing are inserted
132 // without updating environment uses (FlowGraph::RenameDominatedUses,
133 // FlowGraph::InsertConversionsFor).
134 // Also, constants may belong to different blocks (e.g. function entry
135 // and graph entry).
136 Definition* arg_def =
137 call->ArgumentAt(i)->OriginalDefinitionIgnoreBoxingAndConstraints();
138 Definition* env_def =
139 env->ValueAt(env_base + i)
140 ->definition()
141 ->OriginalDefinitionIgnoreBoxingAndConstraints();
142 ASSERT((arg_def == env_def) ||
143 (arg_def->IsConstant() && env_def->IsConstant() &&
144 arg_def->AsConstant()->value().raw() ==
145 env_def->AsConstant()->value().raw()));
146 }
147 }
148 }
149}
150
151void FlowGraphChecker::VisitBlocks() {
152 const GrowableArray<BlockEntryInstr*>& preorder = flow_graph_->preorder();
153 const GrowableArray<BlockEntryInstr*>& postorder = flow_graph_->postorder();
154 const GrowableArray<BlockEntryInstr*>& rev_postorder =
155 flow_graph_->reverse_postorder();
156
157 // Make sure lengths match.
158 const intptr_t block_count = preorder.length();
159 ASSERT(block_count == postorder.length());
160 ASSERT(block_count == rev_postorder.length());
161
162 // Make sure postorder has true reverse.
163 for (intptr_t i = 0; i < block_count; ++i) {
164 ASSERT(postorder[i] == rev_postorder[block_count - i - 1]);
165 }
166
167 // Iterate over all basic blocks.
168 const intptr_t max_block_id = flow_graph_->max_block_id();
169 for (BlockIterator it = flow_graph_->reverse_postorder_iterator(); !it.Done();
170 it.Advance()) {
171 BlockEntryInstr* block = it.Current();
172 ASSERT(block->block_id() <= max_block_id);
173 // Make sure ordering is consistent.
174 ASSERT(block->preorder_number() <= block_count);
175 ASSERT(block->postorder_number() <= block_count);
176 ASSERT(preorder[block->preorder_number()] == block);
177 ASSERT(postorder[block->postorder_number()] == block);
178 // Make sure predecessors and successors agree.
179 Instruction* last = block->last_instruction();
180 for (intptr_t i = 0, n = last->SuccessorCount(); i < n; ++i) {
181 ASSERT(IsPred(block, last->SuccessorAt(i)));
182 }
183 for (intptr_t i = 0, n = block->PredecessorCount(); i < n; ++i) {
184 ASSERT(IsSucc(block, block->PredecessorAt(i)));
185 }
186 // Make sure dominance relations agree.
187 for (intptr_t i = 0, n = block->dominated_blocks().length(); i < n; ++i) {
188 ASSERT(block->dominated_blocks()[i]->dominator() == block);
189 }
190 if (block->dominator() != nullptr) {
191 ASSERT(IsDirectlyDominated(block, block->dominator()));
192 }
193 // Visit all instructions in this block.
194 VisitInstructions(block);
195 }
196}
197
198void FlowGraphChecker::VisitInstructions(BlockEntryInstr* block) {
199 // To avoid excessive runtimes, skip the instructions check if there
200 // are many definitions (as happens in e.g. an initialization block).
201 if (flow_graph_->current_ssa_temp_index() >
202 FLAG_verify_definitions_threshold) {
203 return;
204 }
205 // Give all visitors quick access.
206 current_block_ = block;
207 // Visit initial definitions.
208 if (auto entry = block->AsBlockEntryWithInitialDefs()) {
209 for (auto def : *entry->initial_definitions()) {
210 ASSERT(def != nullptr);
211 ASSERT(def->IsConstant() || def->IsParameter() ||
212 def->IsSpecialParameter());
213 // Special constants reside outside the IR.
214 if (IsSpecialConstant(def)) continue;
215 // Make sure block lookup agrees.
216 ASSERT(def->GetBlock() == entry);
217 // Initial definitions are partially linked into graph.
218 ASSERT(def->next() == nullptr);
219 ASSERT(def->previous() == entry);
220 // Visit the initial definition as instruction.
221 VisitInstruction(def);
222 }
223 }
224 // Visit phis in join.
225 if (auto entry = block->AsJoinEntry()) {
226 for (PhiIterator it(entry); !it.Done(); it.Advance()) {
227 PhiInstr* phi = it.Current();
228 // Make sure block lookup agrees.
229 ASSERT(phi->GetBlock() == entry);
230 // Phis are never linked into graph.
231 ASSERT(phi->next() == nullptr);
232 ASSERT(phi->previous() == nullptr);
233 // Visit the phi as instruction.
234 VisitInstruction(phi);
235 }
236 }
237 // Visit regular instructions.
238 Instruction* last = block->last_instruction();
239 ASSERT((last == block) == block->IsGraphEntry());
240 Instruction* prev = block;
241 ASSERT(prev->previous() == nullptr);
242 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
243 Instruction* instruction = it.Current();
244 // Make sure block lookup agrees (scan in scan).
245 ASSERT(instruction->GetBlock() == block);
246 // Make sure linked list agrees.
247 ASSERT(prev->next() == instruction);
248 ASSERT(instruction->previous() == prev);
249 prev = instruction;
250 // Make sure control flow makes sense.
251 ASSERT(IsControlFlow(instruction) == (instruction == last));
252 ASSERT(!instruction->IsPhi());
253 // Visit the instruction.
254 VisitInstruction(instruction);
255 }
256 ASSERT(prev->next() == nullptr);
257 ASSERT(prev == last);
258 // Make sure loop information, when up-to-date, agrees.
259 if (flow_graph_->loop_hierarchy_ != nullptr) {
260 for (LoopInfo* loop = block->loop_info(); loop != nullptr;
261 loop = loop->outer()) {
262 ASSERT(loop->Contains(block));
263 }
264 }
265}
266
267void FlowGraphChecker::VisitInstruction(Instruction* instruction) {
268 ASSERT(!instruction->IsBlockEntry());
269
270#if !defined(DART_PRECOMPILER)
271 // In JIT mode, any instruction which may throw must have a deopt-id, except
272 // tail-call because it replaces the stack frame.
273 ASSERT(!instruction->MayThrow() || instruction->IsTailCall() ||
274 instruction->deopt_id() != DeoptId::kNone);
275#endif // !defined(DART_PRECOMPILER)
276
277 // Check all regular inputs.
278 for (intptr_t i = 0, n = instruction->InputCount(); i < n; ++i) {
279 VisitUseDef(instruction, instruction->InputAt(i), i, /*is_env*/ false);
280 }
281 // Check all environment inputs (including outer ones).
282 intptr_t i = 0;
283 for (Environment::DeepIterator it(instruction->env()); !it.Done();
284 it.Advance()) {
285 VisitUseDef(instruction, it.CurrentValue(), i++, /*is_env*/ true);
286 }
287 // Visit specific instructions (definitions and anything with Visit()).
288 if (auto def = instruction->AsDefinition()) {
289 VisitDefinition(def);
290 }
291 instruction->Accept(this);
292}
293
294void FlowGraphChecker::VisitDefinition(Definition* def) {
295 // Used definitions must have an SSA name, and the SSA name must
296 // be less than the current_ssa_temp_index.
297 if (def->HasSSATemp()) {
298 ASSERT(def->ssa_temp_index() < flow_graph_->current_ssa_temp_index());
299 } else {
300 ASSERT(def->input_use_list() == nullptr);
301 }
302 // Check all regular uses.
303 Value* prev = nullptr;
304 for (Value* use = def->input_use_list(); use != nullptr;
305 use = use->next_use()) {
306 VisitDefUse(def, use, prev, /*is_env*/ false);
307 prev = use;
308 }
309 // Check all environment uses.
310 prev = nullptr;
311 for (Value* use = def->env_use_list(); use != nullptr;
312 use = use->next_use()) {
313 VisitDefUse(def, use, prev, /*is_env*/ true);
314 prev = use;
315 }
316}
317
318void FlowGraphChecker::VisitUseDef(Instruction* instruction,
319 Value* use,
320 intptr_t index,
321 bool is_env) {
322 ASSERT(use->instruction() == instruction);
323 ASSERT(use->use_index() == index);
324 // Get definition.
325 Definition* def = use->definition();
326 ASSERT(def != nullptr);
327 ASSERT(def != instruction || def->IsPhi() || def->IsMaterializeObject());
328 // Make sure each input is properly defined in the graph by something
329 // that dominates the input (note that the proper dominance relation
330 // on the input values of Phis is checked by the Phi visitor below).
331 if (def->IsPhi()) {
332 ASSERT(def->GetBlock()->IsJoinEntry());
333 // Phis are never linked into graph.
334 ASSERT(def->next() == nullptr);
335 ASSERT(def->previous() == nullptr);
336 } else if (def->IsConstant() || def->IsParameter() ||
337 def->IsSpecialParameter()) {
338 // Special constants reside outside the IR.
339 if (IsSpecialConstant(def)) return;
340 // Initial definitions are partially linked into graph, but some
341 // constants are fully linked into graph (so no next() assert).
342 ASSERT(def->previous() != nullptr);
343 } else {
344 // Others are fully linked into graph.
345 ASSERT(def->next() != nullptr);
346 ASSERT(def->previous() != nullptr);
347 }
348 if (def->HasSSATemp()) {
349 ASSERT(DefDominatesUse(def, instruction));
350 ASSERT(IsInUseList(is_env ? def->env_use_list() : def->input_use_list(),
351 instruction));
352 }
353}
354
355void FlowGraphChecker::VisitDefUse(Definition* def,
356 Value* use,
357 Value* prev,
358 bool is_env) {
359 ASSERT(use->definition() == def);
360 ASSERT(use->previous_use() == prev);
361 // Get using instruction.
362 Instruction* instruction = use->instruction();
363 ASSERT(instruction != nullptr);
364 ASSERT(def != instruction || def->IsPhi() || def->IsMaterializeObject());
365 if (is_env) {
366 ASSERT(instruction->env()->ValueAtUseIndex(use->use_index()) == use);
367 } else {
368 ASSERT(instruction->InputAt(use->use_index()) == use);
369 }
370 // Make sure the reaching type, if any, has an owner consistent with this use.
371 if (auto const type = use->reaching_type()) {
372 ASSERT(type->owner() == nullptr || type->owner() == def);
373 }
374 // Make sure each use appears in the graph and is properly dominated
375 // by the definition (note that the proper dominance relation on the
376 // input values of Phis is checked by the Phi visitor below).
377 if (instruction->IsPhi()) {
378 ASSERT(instruction->AsPhi()->is_alive());
379 ASSERT(instruction->GetBlock()->IsJoinEntry());
380 // Phis are never linked into graph.
381 ASSERT(instruction->next() == nullptr);
382 ASSERT(instruction->previous() == nullptr);
383 } else if (instruction->IsBlockEntry()) {
384 // BlockEntry instructions have environments attached to them but
385 // have no reliable way to verify if they are still in the graph.
386 ASSERT(is_env);
387 ASSERT(instruction->next() != nullptr);
388 ASSERT(DefDominatesUse(def, instruction));
389 } else {
390 // Others are fully linked into graph.
391 ASSERT(IsControlFlow(instruction) || instruction->next() != nullptr);
392 ASSERT(instruction->previous() != nullptr);
393 ASSERT(!def->HasSSATemp() || DefDominatesUse(def, instruction));
394 }
395}
396
397void FlowGraphChecker::VisitConstant(ConstantInstr* constant) {
398 // Range check on smi.
399 const Object& value = constant->value();
400 if (value.IsSmi()) {
401 const int64_t smi_value = Integer::Cast(value).AsInt64Value();
402 ASSERT(compiler::target::kSmiMin <= smi_value);
403 ASSERT(smi_value <= compiler::target::kSmiMax);
404 }
405 // Any constant involved in SSA should appear in the entry (making it more
406 // likely it was inserted by the utility that avoids duplication).
407 //
408 // TODO(dartbug.com/36894)
409 //
410 // ASSERT(constant->GetBlock() == flow_graph_->graph_entry());
411}
412
413void FlowGraphChecker::VisitPhi(PhiInstr* phi) {
414 // Make sure the definition of each input value of a Phi dominates
415 // the corresponding incoming edge, as defined by order.
416 ASSERT(phi->InputCount() == current_block_->PredecessorCount());
417 for (intptr_t i = 0, n = phi->InputCount(); i < n; ++i) {
418 Definition* def = phi->InputAt(i)->definition();
419 ASSERT(def->HasSSATemp()); // phis have SSA defs
420 BlockEntryInstr* edge = current_block_->PredecessorAt(i);
421 ASSERT(DefDominatesUse(def, edge->last_instruction()));
422 }
423}
424
425void FlowGraphChecker::VisitGoto(GotoInstr* jmp) {
426 ASSERT(jmp->SuccessorCount() == 1);
427}
428
429void FlowGraphChecker::VisitIndirectGoto(IndirectGotoInstr* jmp) {
430 ASSERT(jmp->SuccessorCount() >= 1);
431}
432
433void FlowGraphChecker::VisitBranch(BranchInstr* branch) {
434 ASSERT(branch->SuccessorCount() == 2);
435}
436
437void FlowGraphChecker::VisitRedefinition(RedefinitionInstr* def) {
438 ASSERT(def->value()->definition() != def);
439}
440
441void FlowGraphChecker::VisitClosureCall(ClosureCallInstr* call) {
442 AssertArgumentsInEnv(flow_graph_, call);
443}
444
445void FlowGraphChecker::VisitStaticCall(StaticCallInstr* call) {
446 AssertArgumentsInEnv(flow_graph_, call);
447}
448
449void FlowGraphChecker::VisitInstanceCall(InstanceCallInstr* call) {
450 AssertArgumentsInEnv(flow_graph_, call);
451 // Force-optimized functions may not have instance calls inside them because
452 // we do not reset ICData for these.
453 ASSERT(!flow_graph_->function().ForceOptimize());
454}
455
456void FlowGraphChecker::VisitPolymorphicInstanceCall(
457 PolymorphicInstanceCallInstr* call) {
458 AssertArgumentsInEnv(flow_graph_, call);
459 // Force-optimized functions may not have instance calls inside them because
460 // we do not reset ICData for these.
461 ASSERT(!flow_graph_->function().ForceOptimize());
462}
463
464// Main entry point of graph checker.
465void FlowGraphChecker::Check(const char* pass_name) {
466 if (FLAG_trace_compiler) {
467 THR_Print("Running checker after %s\n", pass_name);
468 }
469 ASSERT(flow_graph_ != nullptr);
470 VisitBlocks();
471}
472
473} // namespace dart
474
475#endif // defined(DEBUG)
476