1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "graph_checker.h"
18
19 #include <algorithm>
20 #include <sstream>
21 #include <string>
22
23 #include "android-base/stringprintf.h"
24
25 #include "base/bit_vector-inl.h"
26 #include "base/scoped_arena_allocator.h"
27 #include "base/scoped_arena_containers.h"
28 #include "code_generator.h"
29 #include "handle.h"
30 #include "intrinsics.h"
31 #include "mirror/class.h"
32 #include "nodes.h"
33 #include "obj_ptr-inl.h"
34 #include "optimizing/data_type.h"
35 #include "scoped_thread_state_change-inl.h"
36 #include "subtype_check.h"
37
38 namespace art HIDDEN {
39
40 using android::base::StringPrintf;
41
IsAllowedToJumpToExitBlock(HInstruction * instruction)42 static bool IsAllowedToJumpToExitBlock(HInstruction* instruction) {
43 // Anything that returns is allowed to jump into the exit block.
44 if (instruction->IsReturn() || instruction->IsReturnVoid()) {
45 return true;
46 }
47 // Anything that always throws is allowed to jump into the exit block.
48 if (instruction->IsGoto() && instruction->GetPrevious() != nullptr) {
49 instruction = instruction->GetPrevious();
50 }
51 return instruction->AlwaysThrows();
52 }
53
IsExitTryBoundaryIntoExitBlock(HBasicBlock * block)54 static bool IsExitTryBoundaryIntoExitBlock(HBasicBlock* block) {
55 if (!block->IsSingleTryBoundary()) {
56 return false;
57 }
58
59 HTryBoundary* boundary = block->GetLastInstruction()->AsTryBoundary();
60 return block->GetPredecessors().size() == 1u &&
61 boundary->GetNormalFlowSuccessor()->IsExitBlock() &&
62 !boundary->IsEntry();
63 }
64
65
Run(bool pass_change,size_t last_size)66 size_t GraphChecker::Run(bool pass_change, size_t last_size) {
67 size_t current_size = GetGraph()->GetReversePostOrder().size();
68 if (!pass_change) {
69 // Nothing changed for certain. Do a quick check of the validity on that assertion
70 // for anything other than the first call (when last size was still 0).
71 if (last_size != 0) {
72 if (current_size != last_size) {
73 AddError(StringPrintf("Incorrect no-change assertion, "
74 "last graph size %zu vs current graph size %zu",
75 last_size, current_size));
76 }
77 }
78 // TODO: if we would trust the "false" value of the flag completely, we
79 // could skip checking the graph at this point.
80 }
81
82 // VisitReversePostOrder is used instead of VisitInsertionOrder,
83 // as the latter might visit dead blocks removed by the dominator
84 // computation.
85 VisitReversePostOrder();
86 CheckGraphFlags();
87 return current_size;
88 }
89
VisitReversePostOrder()90 void GraphChecker::VisitReversePostOrder() {
91 for (HBasicBlock* block : GetGraph()->GetReversePostOrder()) {
92 if (block->IsInLoop()) {
93 flag_info_.seen_loop = true;
94 if (block->GetLoopInformation()->IsIrreducible()) {
95 flag_info_.seen_irreducible_loop = true;
96 }
97 }
98
99 VisitBasicBlock(block);
100 }
101 }
102
StrBool(bool val)103 static const char* StrBool(bool val) {
104 return val ? "true" : "false";
105 }
106
CheckGraphFlags()107 void GraphChecker::CheckGraphFlags() {
108 if (GetGraph()->HasMonitorOperations() != flag_info_.seen_monitor_operation) {
109 AddError(
110 StringPrintf("Flag mismatch: HasMonitorOperations() (%s) should be equal to "
111 "flag_info_.seen_monitor_operation (%s)",
112 StrBool(GetGraph()->HasMonitorOperations()),
113 StrBool(flag_info_.seen_monitor_operation)));
114 }
115
116 if (GetGraph()->HasTryCatch() != flag_info_.seen_try_boundary) {
117 AddError(
118 StringPrintf("Flag mismatch: HasTryCatch() (%s) should be equal to "
119 "flag_info_.seen_try_boundary (%s)",
120 StrBool(GetGraph()->HasTryCatch()),
121 StrBool(flag_info_.seen_try_boundary)));
122 }
123
124 if (GetGraph()->HasLoops() != flag_info_.seen_loop) {
125 AddError(
126 StringPrintf("Flag mismatch: HasLoops() (%s) should be equal to "
127 "flag_info_.seen_loop (%s)",
128 StrBool(GetGraph()->HasLoops()),
129 StrBool(flag_info_.seen_loop)));
130 }
131
132 if (GetGraph()->HasIrreducibleLoops() && !GetGraph()->HasLoops()) {
133 AddError(StringPrintf("Flag mismatch: HasIrreducibleLoops() (%s) implies HasLoops() (%s)",
134 StrBool(GetGraph()->HasIrreducibleLoops()),
135 StrBool(GetGraph()->HasLoops())));
136 }
137
138 if (GetGraph()->HasIrreducibleLoops() != flag_info_.seen_irreducible_loop) {
139 AddError(
140 StringPrintf("Flag mismatch: HasIrreducibleLoops() (%s) should be equal to "
141 "flag_info_.seen_irreducible_loop (%s)",
142 StrBool(GetGraph()->HasIrreducibleLoops()),
143 StrBool(flag_info_.seen_irreducible_loop)));
144 }
145
146 if (GetGraph()->HasSIMD() != flag_info_.seen_SIMD) {
147 AddError(
148 StringPrintf("Flag mismatch: HasSIMD() (%s) should be equal to "
149 "flag_info_.seen_SIMD (%s)",
150 StrBool(GetGraph()->HasSIMD()),
151 StrBool(flag_info_.seen_SIMD)));
152 }
153
154 if (GetGraph()->HasBoundsChecks() != flag_info_.seen_bounds_checks) {
155 AddError(
156 StringPrintf("Flag mismatch: HasBoundsChecks() (%s) should be equal to "
157 "flag_info_.seen_bounds_checks (%s)",
158 StrBool(GetGraph()->HasBoundsChecks()),
159 StrBool(flag_info_.seen_bounds_checks)));
160 }
161
162 if (GetGraph()->HasAlwaysThrowingInvokes() != flag_info_.seen_always_throwing_invokes) {
163 AddError(
164 StringPrintf("Flag mismatch: HasAlwaysThrowingInvokes() (%s) should be equal to "
165 "flag_info_.seen_always_throwing_invokes (%s)",
166 StrBool(GetGraph()->HasAlwaysThrowingInvokes()),
167 StrBool(flag_info_.seen_always_throwing_invokes)));
168 }
169 }
170
VisitBasicBlock(HBasicBlock * block)171 void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
172 current_block_ = block;
173
174 {
175 // Use local allocator for allocating memory. We use C++ scopes (i.e. `{}`) to reclaim the
176 // memory as soon as possible, and to end the scope of this `ScopedArenaAllocator`.
177 ScopedArenaAllocator allocator(GetGraph()->GetArenaStack());
178
179 {
180 // Check consistency with respect to predecessors of `block`.
181 // Note: Counting duplicates with a sorted vector uses up to 6x less memory
182 // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
183 ScopedArenaVector<HBasicBlock*> sorted_predecessors(
184 allocator.Adapter(kArenaAllocGraphChecker));
185 sorted_predecessors.assign(block->GetPredecessors().begin(), block->GetPredecessors().end());
186 std::sort(sorted_predecessors.begin(), sorted_predecessors.end());
187 for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end;) {
188 HBasicBlock* p = *it++;
189 size_t p_count_in_block_predecessors = 1u;
190 for (; it != end && *it == p; ++it) {
191 ++p_count_in_block_predecessors;
192 }
193 size_t block_count_in_p_successors =
194 std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block);
195 if (p_count_in_block_predecessors != block_count_in_p_successors) {
196 AddError(StringPrintf(
197 "Block %d lists %zu occurrences of block %d in its predecessors, whereas "
198 "block %d lists %zu occurrences of block %d in its successors.",
199 block->GetBlockId(),
200 p_count_in_block_predecessors,
201 p->GetBlockId(),
202 p->GetBlockId(),
203 block_count_in_p_successors,
204 block->GetBlockId()));
205 }
206 }
207 }
208
209 {
210 // Check consistency with respect to successors of `block`.
211 // Note: Counting duplicates with a sorted vector uses up to 6x less memory
212 // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
213 ScopedArenaVector<HBasicBlock*> sorted_successors(allocator.Adapter(kArenaAllocGraphChecker));
214 sorted_successors.assign(block->GetSuccessors().begin(), block->GetSuccessors().end());
215 std::sort(sorted_successors.begin(), sorted_successors.end());
216 for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end;) {
217 HBasicBlock* s = *it++;
218 size_t s_count_in_block_successors = 1u;
219 for (; it != end && *it == s; ++it) {
220 ++s_count_in_block_successors;
221 }
222 size_t block_count_in_s_predecessors =
223 std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block);
224 if (s_count_in_block_successors != block_count_in_s_predecessors) {
225 AddError(
226 StringPrintf("Block %d lists %zu occurrences of block %d in its successors, whereas "
227 "block %d lists %zu occurrences of block %d in its predecessors.",
228 block->GetBlockId(),
229 s_count_in_block_successors,
230 s->GetBlockId(),
231 s->GetBlockId(),
232 block_count_in_s_predecessors,
233 block->GetBlockId()));
234 }
235 }
236 }
237 }
238
239 // Ensure `block` ends with a branch instruction.
240 // This invariant is not enforced on non-SSA graphs. Graph built from DEX with
241 // dead code that falls out of the method will not end with a control-flow
242 // instruction. Such code is removed during the SSA-building DCE phase.
243 if (GetGraph()->IsInSsaForm() && !block->EndsWithControlFlowInstruction()) {
244 AddError(StringPrintf("Block %d does not end with a branch instruction.",
245 block->GetBlockId()));
246 }
247
248 // Ensure that only Return(Void) and Throw jump to Exit. An exiting TryBoundary
249 // may be between the instructions if the Throw/Return(Void) is in a try block.
250 if (block->IsExitBlock()) {
251 for (HBasicBlock* predecessor : block->GetPredecessors()) {
252 HInstruction* last_instruction = IsExitTryBoundaryIntoExitBlock(predecessor) ?
253 predecessor->GetSinglePredecessor()->GetLastInstruction() :
254 predecessor->GetLastInstruction();
255 if (!IsAllowedToJumpToExitBlock(last_instruction)) {
256 AddError(StringPrintf("Unexpected instruction %s:%d jumps into the exit block.",
257 last_instruction->DebugName(),
258 last_instruction->GetId()));
259 }
260 }
261 }
262
263 // Make sure the first instruction of a catch block is always a Nop that emits an environment.
264 if (block->IsCatchBlock()) {
265 if (!block->GetFirstInstruction()->IsNop()) {
266 AddError(StringPrintf("Block %d doesn't have a Nop as its first instruction.",
267 current_block_->GetBlockId()));
268 } else {
269 HNop* nop = block->GetFirstInstruction()->AsNop();
270 if (!nop->NeedsEnvironment()) {
271 AddError(
272 StringPrintf("%s:%d is a Nop and the first instruction of block %d, but it doesn't "
273 "need an environment.",
274 nop->DebugName(),
275 nop->GetId(),
276 current_block_->GetBlockId()));
277 }
278 }
279 }
280
281 // Visit this block's list of phis.
282 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
283 HInstruction* current = it.Current();
284 // Ensure this block's list of phis contains only phis.
285 if (!current->IsPhi()) {
286 AddError(StringPrintf("Block %d has a non-phi in its phi list.",
287 current_block_->GetBlockId()));
288 }
289 if (current->GetNext() == nullptr && current != block->GetLastPhi()) {
290 AddError(StringPrintf("The recorded last phi of block %d does not match "
291 "the actual last phi %d.",
292 current_block_->GetBlockId(),
293 current->GetId()));
294 }
295 current->Accept(this);
296 }
297
298 // Visit this block's list of instructions.
299 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
300 HInstruction* current = it.Current();
301 // Ensure this block's list of instructions does not contains phis.
302 if (current->IsPhi()) {
303 AddError(StringPrintf("Block %d has a phi in its non-phi list.",
304 current_block_->GetBlockId()));
305 }
306 if (current->GetNext() == nullptr && current != block->GetLastInstruction()) {
307 AddError(
308 StringPrintf("The recorded last instruction of block %d does not match "
309 "the actual last instruction %d.",
310 current_block_->GetBlockId(),
311 current->GetId()));
312 }
313 current->Accept(this);
314 }
315
316 // Ensure that catch blocks are not normal successors, and normal blocks are
317 // never exceptional successors.
318 for (HBasicBlock* successor : block->GetNormalSuccessors()) {
319 if (successor->IsCatchBlock()) {
320 AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
321 successor->GetBlockId(),
322 block->GetBlockId()));
323 }
324 }
325 for (HBasicBlock* successor : block->GetExceptionalSuccessors()) {
326 if (!successor->IsCatchBlock()) {
327 AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
328 successor->GetBlockId(),
329 block->GetBlockId()));
330 }
331 }
332
333 // Ensure dominated blocks have `block` as the dominator.
334 for (HBasicBlock* dominated : block->GetDominatedBlocks()) {
335 if (dominated->GetDominator() != block) {
336 AddError(StringPrintf("Block %d should be the dominator of %d.",
337 block->GetBlockId(),
338 dominated->GetBlockId()));
339 }
340 }
341
342 // Ensure all blocks have at least one successor, except the Exit block.
343 if (block->GetSuccessors().empty() && !block->IsExitBlock()) {
344 AddError(StringPrintf("Block %d has no successor and it is not the Exit block.",
345 block->GetBlockId()));
346 }
347
348 // Ensure there is no critical edge (i.e., an edge connecting a
349 // block with multiple successors to a block with multiple
350 // predecessors). Exceptional edges are synthesized and hence
351 // not accounted for.
352 if (block->GetSuccessors().size() > 1) {
353 if (IsExitTryBoundaryIntoExitBlock(block)) {
354 // Allowed critical edge (Throw/Return/ReturnVoid)->TryBoundary->Exit.
355 } else {
356 for (HBasicBlock* successor : block->GetNormalSuccessors()) {
357 if (successor->GetPredecessors().size() > 1) {
358 AddError(StringPrintf("Critical edge between blocks %d and %d.",
359 block->GetBlockId(),
360 successor->GetBlockId()));
361 }
362 }
363 }
364 }
365
366 // Ensure try membership information is consistent.
367 if (block->IsCatchBlock()) {
368 if (block->IsTryBlock()) {
369 const HTryBoundary& try_entry = block->GetTryCatchInformation()->GetTryEntry();
370 AddError(StringPrintf("Catch blocks should not be try blocks but catch block %d "
371 "has try entry %s:%d.",
372 block->GetBlockId(),
373 try_entry.DebugName(),
374 try_entry.GetId()));
375 }
376
377 if (block->IsLoopHeader()) {
378 AddError(StringPrintf("Catch blocks should not be loop headers but catch block %d is.",
379 block->GetBlockId()));
380 }
381 } else {
382 for (HBasicBlock* predecessor : block->GetPredecessors()) {
383 const HTryBoundary* incoming_try_entry = predecessor->ComputeTryEntryOfSuccessors();
384 if (block->IsTryBlock()) {
385 const HTryBoundary& stored_try_entry = block->GetTryCatchInformation()->GetTryEntry();
386 if (incoming_try_entry == nullptr) {
387 AddError(StringPrintf("Block %d has try entry %s:%d but no try entry follows "
388 "from predecessor %d.",
389 block->GetBlockId(),
390 stored_try_entry.DebugName(),
391 stored_try_entry.GetId(),
392 predecessor->GetBlockId()));
393 } else if (!incoming_try_entry->HasSameExceptionHandlersAs(stored_try_entry)) {
394 AddError(StringPrintf("Block %d has try entry %s:%d which is not consistent "
395 "with %s:%d that follows from predecessor %d.",
396 block->GetBlockId(),
397 stored_try_entry.DebugName(),
398 stored_try_entry.GetId(),
399 incoming_try_entry->DebugName(),
400 incoming_try_entry->GetId(),
401 predecessor->GetBlockId()));
402 }
403 } else if (incoming_try_entry != nullptr) {
404 AddError(StringPrintf("Block %d is not a try block but try entry %s:%d follows "
405 "from predecessor %d.",
406 block->GetBlockId(),
407 incoming_try_entry->DebugName(),
408 incoming_try_entry->GetId(),
409 predecessor->GetBlockId()));
410 }
411 }
412 }
413
414 if (block->IsLoopHeader()) {
415 HandleLoop(block);
416 }
417 }
418
VisitBoundsCheck(HBoundsCheck * check)419 void GraphChecker::VisitBoundsCheck(HBoundsCheck* check) {
420 VisitInstruction(check);
421
422 if (!GetGraph()->HasBoundsChecks()) {
423 AddError(
424 StringPrintf("The graph doesn't have the HasBoundsChecks flag set but we saw "
425 "%s:%d in block %d.",
426 check->DebugName(),
427 check->GetId(),
428 check->GetBlock()->GetBlockId()));
429 }
430
431 flag_info_.seen_bounds_checks = true;
432 }
433
VisitDeoptimize(HDeoptimize * deopt)434 void GraphChecker::VisitDeoptimize(HDeoptimize* deopt) {
435 VisitInstruction(deopt);
436 if (GetGraph()->IsCompilingOsr()) {
437 AddError(StringPrintf("A graph compiled OSR cannot have a HDeoptimize instruction"));
438 }
439 }
440
VisitTryBoundary(HTryBoundary * try_boundary)441 void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) {
442 VisitInstruction(try_boundary);
443
444 ArrayRef<HBasicBlock* const> handlers = try_boundary->GetExceptionHandlers();
445
446 // Ensure that all exception handlers are catch blocks.
447 // Note that a normal-flow successor may be a catch block before CFG
448 // simplification. We only test normal-flow successors in GraphChecker.
449 for (HBasicBlock* handler : handlers) {
450 if (!handler->IsCatchBlock()) {
451 AddError(StringPrintf("Block %d with %s:%d has exceptional successor %d which "
452 "is not a catch block.",
453 current_block_->GetBlockId(),
454 try_boundary->DebugName(),
455 try_boundary->GetId(),
456 handler->GetBlockId()));
457 }
458 }
459
460 // Ensure that handlers are not listed multiple times.
461 for (size_t i = 0, e = handlers.size(); i < e; ++i) {
462 if (ContainsElement(handlers, handlers[i], i + 1)) {
463 AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.",
464 handlers[i]->GetBlockId(),
465 try_boundary->DebugName(),
466 try_boundary->GetId()));
467 }
468 }
469
470 if (!GetGraph()->HasTryCatch()) {
471 AddError(
472 StringPrintf("The graph doesn't have the HasTryCatch flag set but we saw "
473 "%s:%d in block %d.",
474 try_boundary->DebugName(),
475 try_boundary->GetId(),
476 try_boundary->GetBlock()->GetBlockId()));
477 }
478
479 flag_info_.seen_try_boundary = true;
480 }
481
VisitLoadClass(HLoadClass * load)482 void GraphChecker::VisitLoadClass(HLoadClass* load) {
483 VisitInstruction(load);
484
485 if (load->GetLoadedClassRTI().IsValid() && !load->GetLoadedClassRTI().IsExact()) {
486 std::stringstream ssRTI;
487 ssRTI << load->GetLoadedClassRTI();
488 AddError(StringPrintf("%s:%d in block %d with RTI %s has valid but inexact RTI.",
489 load->DebugName(),
490 load->GetId(),
491 load->GetBlock()->GetBlockId(),
492 ssRTI.str().c_str()));
493 }
494 }
495
VisitLoadException(HLoadException * load)496 void GraphChecker::VisitLoadException(HLoadException* load) {
497 VisitInstruction(load);
498
499 // Ensure that LoadException is the second instruction in a catch block. The first one should be a
500 // Nop (checked separately).
501 if (!load->GetBlock()->IsCatchBlock()) {
502 AddError(StringPrintf("%s:%d is in a non-catch block %d.",
503 load->DebugName(),
504 load->GetId(),
505 load->GetBlock()->GetBlockId()));
506 } else if (load->GetBlock()->GetFirstInstruction()->GetNext() != load) {
507 AddError(StringPrintf("%s:%d is not the second instruction in catch block %d.",
508 load->DebugName(),
509 load->GetId(),
510 load->GetBlock()->GetBlockId()));
511 }
512 }
513
VisitMonitorOperation(HMonitorOperation * monitor_op)514 void GraphChecker::VisitMonitorOperation(HMonitorOperation* monitor_op) {
515 VisitInstruction(monitor_op);
516
517 if (!GetGraph()->HasMonitorOperations()) {
518 AddError(
519 StringPrintf("The graph doesn't have the HasMonitorOperations flag set but we saw "
520 "%s:%d in block %d.",
521 monitor_op->DebugName(),
522 monitor_op->GetId(),
523 monitor_op->GetBlock()->GetBlockId()));
524 }
525
526 flag_info_.seen_monitor_operation = true;
527 }
528
ContainedInItsBlockList(HInstruction * instruction)529 bool GraphChecker::ContainedInItsBlockList(HInstruction* instruction) {
530 HBasicBlock* block = instruction->GetBlock();
531 ScopedArenaSafeMap<HBasicBlock*, ScopedArenaHashSet<HInstruction*>>& instruction_set =
532 instruction->IsPhi() ? phis_per_block_ : instructions_per_block_;
533 auto map_it = instruction_set.find(block);
534 if (map_it == instruction_set.end()) {
535 // Populate extra bookkeeping.
536 map_it = instruction_set.insert(
537 {block, ScopedArenaHashSet<HInstruction*>(allocator_.Adapter(kArenaAllocGraphChecker))})
538 .first;
539 const HInstructionList& instruction_list = instruction->IsPhi() ?
540 instruction->GetBlock()->GetPhis() :
541 instruction->GetBlock()->GetInstructions();
542 for (HInstructionIterator list_it(instruction_list); !list_it.Done(); list_it.Advance()) {
543 map_it->second.insert(list_it.Current());
544 }
545 }
546 return map_it->second.find(instruction) != map_it->second.end();
547 }
548
VisitInstruction(HInstruction * instruction)549 void GraphChecker::VisitInstruction(HInstruction* instruction) {
550 if (seen_ids_.IsBitSet(instruction->GetId())) {
551 AddError(StringPrintf("Instruction id %d is duplicate in graph.",
552 instruction->GetId()));
553 } else {
554 seen_ids_.SetBit(instruction->GetId());
555 }
556
557 // Ensure `instruction` is associated with `current_block_`.
558 if (instruction->GetBlock() == nullptr) {
559 AddError(StringPrintf("%s %d in block %d not associated with any block.",
560 instruction->IsPhi() ? "Phi" : "Instruction",
561 instruction->GetId(),
562 current_block_->GetBlockId()));
563 } else if (instruction->GetBlock() != current_block_) {
564 AddError(StringPrintf("%s %d in block %d associated with block %d.",
565 instruction->IsPhi() ? "Phi" : "Instruction",
566 instruction->GetId(),
567 current_block_->GetBlockId(),
568 instruction->GetBlock()->GetBlockId()));
569 }
570
571 // Ensure the inputs of `instruction` are defined in a block of the graph, and the entry in the
572 // use list is consistent.
573 for (HInstruction* input : instruction->GetInputs()) {
574 if (input->GetBlock() == nullptr) {
575 AddError(StringPrintf("Input %d of instruction %d is not in any "
576 "basic block of the control-flow graph.",
577 input->GetId(),
578 instruction->GetId()));
579 } else if (!ContainedInItsBlockList(input)) {
580 AddError(StringPrintf("Input %d of instruction %d is not defined "
581 "in a basic block of the control-flow graph.",
582 input->GetId(),
583 instruction->GetId()));
584 }
585 }
586
587 // Ensure the uses of `instruction` are defined in a block of the graph,
588 // and the entry in the use list is consistent.
589 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
590 HInstruction* user = use.GetUser();
591 if (!ContainedInItsBlockList(user)) {
592 AddError(StringPrintf("User %s:%d of instruction %d is not defined "
593 "in a basic block of the control-flow graph.",
594 user->DebugName(),
595 user->GetId(),
596 instruction->GetId()));
597 }
598 size_t use_index = use.GetIndex();
599 HConstInputsRef user_inputs = user->GetInputs();
600 if ((use_index >= user_inputs.size()) || (user_inputs[use_index] != instruction)) {
601 AddError(StringPrintf("User %s:%d of instruction %s:%d has a wrong "
602 "UseListNode index.",
603 user->DebugName(),
604 user->GetId(),
605 instruction->DebugName(),
606 instruction->GetId()));
607 }
608 }
609
610 // Ensure the environment uses entries are consistent.
611 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
612 HEnvironment* user = use.GetUser();
613 size_t use_index = use.GetIndex();
614 if ((use_index >= user->Size()) || (user->GetInstructionAt(use_index) != instruction)) {
615 AddError(StringPrintf("Environment user of %s:%d has a wrong "
616 "UseListNode index.",
617 instruction->DebugName(),
618 instruction->GetId()));
619 }
620 }
621
622 // Ensure 'instruction' has pointers to its inputs' use entries.
623 {
624 auto&& input_records = instruction->GetInputRecords();
625 for (size_t i = 0; i < input_records.size(); ++i) {
626 const HUserRecord<HInstruction*>& input_record = input_records[i];
627 HInstruction* input = input_record.GetInstruction();
628
629 // Populate bookkeeping, if needed. See comment in graph_checker.h for uses_per_instruction_.
630 auto it = uses_per_instruction_.find(input->GetId());
631 if (it == uses_per_instruction_.end()) {
632 it = uses_per_instruction_
633 .insert({input->GetId(),
634 ScopedArenaSet<const art::HUseListNode<art::HInstruction*>*>(
635 allocator_.Adapter(kArenaAllocGraphChecker))})
636 .first;
637 for (auto&& use : input->GetUses()) {
638 it->second.insert(std::addressof(use));
639 }
640 }
641
642 if ((input_record.GetBeforeUseNode() == input->GetUses().end()) ||
643 (input_record.GetUseNode() == input->GetUses().end()) ||
644 (it->second.find(std::addressof(*input_record.GetUseNode())) == it->second.end()) ||
645 (input_record.GetUseNode()->GetIndex() != i)) {
646 AddError(
647 StringPrintf("Instruction %s:%d has an invalid iterator before use entry "
648 "at input %u (%s:%d).",
649 instruction->DebugName(),
650 instruction->GetId(),
651 static_cast<unsigned>(i),
652 input->DebugName(),
653 input->GetId()));
654 }
655 }
656 }
657
658 // Ensure an instruction dominates all its uses.
659 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
660 HInstruction* user = use.GetUser();
661 if (!user->IsPhi() && (instruction->GetBlock() == user->GetBlock()
662 ? seen_ids_.IsBitSet(user->GetId())
663 : !instruction->GetBlock()->Dominates(user->GetBlock()))) {
664 AddError(
665 StringPrintf("Instruction %s:%d in block %d does not dominate "
666 "use %s:%d in block %d.",
667 instruction->DebugName(),
668 instruction->GetId(),
669 current_block_->GetBlockId(),
670 user->DebugName(),
671 user->GetId(),
672 user->GetBlock()->GetBlockId()));
673 }
674 }
675
676 if (instruction->NeedsEnvironment() != instruction->HasEnvironment()) {
677 const char* str;
678 if (instruction->NeedsEnvironment()) {
679 str = "Instruction %s:%d in block %d requires an environment but does not have one.";
680 } else {
681 str = "Instruction %s:%d in block %d doesn't require an environment but it has one.";
682 }
683
684 AddError(StringPrintf(str,
685 instruction->DebugName(),
686 instruction->GetId(),
687 current_block_->GetBlockId()));
688 }
689
690 // Ensure an instruction dominates all its environment uses.
691 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
692 HInstruction* user = use.GetUser()->GetHolder();
693 if (user->IsPhi()) {
694 AddError(StringPrintf("Phi %d shouldn't have an environment", instruction->GetId()));
695 }
696 if (instruction->GetBlock() == user->GetBlock()
697 ? seen_ids_.IsBitSet(user->GetId())
698 : !instruction->GetBlock()->Dominates(user->GetBlock())) {
699 AddError(
700 StringPrintf("Instruction %s:%d in block %d does not dominate "
701 "environment use %s:%d in block %d.",
702 instruction->DebugName(),
703 instruction->GetId(),
704 current_block_->GetBlockId(),
705 user->DebugName(),
706 user->GetId(),
707 user->GetBlock()->GetBlockId()));
708 }
709 }
710
711 if (instruction->CanThrow() && !instruction->HasEnvironment()) {
712 AddError(StringPrintf("Throwing instruction %s:%d in block %d does not have an environment.",
713 instruction->DebugName(),
714 instruction->GetId(),
715 current_block_->GetBlockId()));
716 } else if (instruction->CanThrowIntoCatchBlock()) {
717 // Find all catch blocks and test that `instruction` has an environment value for each one.
718 const HTryBoundary& entry = instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
719 for (HBasicBlock* catch_block : entry.GetExceptionHandlers()) {
720 const HEnvironment* environment = catch_block->GetFirstInstruction()->GetEnvironment();
721 for (HInstructionIterator phi_it(catch_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
722 HPhi* catch_phi = phi_it.Current()->AsPhi();
723 if (environment->GetInstructionAt(catch_phi->GetRegNumber()) == nullptr) {
724 AddError(
725 StringPrintf("Instruction %s:%d throws into catch block %d "
726 "with catch phi %d for vreg %d but its "
727 "corresponding environment slot is empty.",
728 instruction->DebugName(),
729 instruction->GetId(),
730 catch_block->GetBlockId(),
731 catch_phi->GetId(),
732 catch_phi->GetRegNumber()));
733 }
734 }
735 }
736 }
737 }
738
VisitInvoke(HInvoke * invoke)739 void GraphChecker::VisitInvoke(HInvoke* invoke) {
740 VisitInstruction(invoke);
741
742 if (invoke->AlwaysThrows()) {
743 if (!GetGraph()->HasAlwaysThrowingInvokes()) {
744 AddError(
745 StringPrintf("The graph doesn't have the HasAlwaysThrowingInvokes flag set but we saw "
746 "%s:%d in block %d and it always throws.",
747 invoke->DebugName(),
748 invoke->GetId(),
749 invoke->GetBlock()->GetBlockId()));
750 }
751 flag_info_.seen_always_throwing_invokes = true;
752 }
753
754 // Check for intrinsics which should have been replaced by intermediate representation in the
755 // instruction builder.
756 if (!IsValidIntrinsicAfterBuilder(invoke->GetIntrinsic())) {
757 std::stringstream ss;
758 ss << invoke->GetIntrinsic();
759 AddError(
760 StringPrintf("The graph contains the intrinsic %s which should have been replaced in the "
761 "instruction builder: %s:%d in block %d.",
762 ss.str().c_str(),
763 invoke->DebugName(),
764 invoke->GetId(),
765 invoke->GetBlock()->GetBlockId()));
766 }
767 }
768
VisitInvokeStaticOrDirect(HInvokeStaticOrDirect * invoke)769 void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
770 // We call VisitInvoke and not VisitInstruction to de-duplicate the common code: always throwing
771 // and intrinsic checks.
772 VisitInvoke(invoke);
773
774 if (invoke->IsStaticWithExplicitClinitCheck()) {
775 const HInstruction* last_input = invoke->GetInputs().back();
776 if (last_input == nullptr) {
777 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
778 "has a null pointer as last input.",
779 invoke->DebugName(),
780 invoke->GetId()));
781 } else if (!last_input->IsClinitCheck() && !last_input->IsLoadClass()) {
782 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
783 "has a last instruction (%s:%d) which is neither a clinit check "
784 "nor a load class instruction.",
785 invoke->DebugName(),
786 invoke->GetId(),
787 last_input->DebugName(),
788 last_input->GetId()));
789 }
790 }
791 }
792
VisitReturn(HReturn * ret)793 void GraphChecker::VisitReturn(HReturn* ret) {
794 VisitInstruction(ret);
795 HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor();
796 if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) {
797 AddError(StringPrintf("%s:%d does not jump to the exit block.",
798 ret->DebugName(),
799 ret->GetId()));
800 }
801 }
802
VisitReturnVoid(HReturnVoid * ret)803 void GraphChecker::VisitReturnVoid(HReturnVoid* ret) {
804 VisitInstruction(ret);
805 HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor();
806 if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) {
807 AddError(StringPrintf("%s:%d does not jump to the exit block.",
808 ret->DebugName(),
809 ret->GetId()));
810 }
811 }
812
CheckTypeCheckBitstringInput(HTypeCheckInstruction * check,size_t input_pos,bool check_value,uint32_t expected_value,const char * name)813 void GraphChecker::CheckTypeCheckBitstringInput(HTypeCheckInstruction* check,
814 size_t input_pos,
815 bool check_value,
816 uint32_t expected_value,
817 const char* name) {
818 if (!check->InputAt(input_pos)->IsIntConstant()) {
819 AddError(StringPrintf("%s:%d (bitstring) expects a HIntConstant input %zu (%s), not %s:%d.",
820 check->DebugName(),
821 check->GetId(),
822 input_pos,
823 name,
824 check->InputAt(2)->DebugName(),
825 check->InputAt(2)->GetId()));
826 } else if (check_value) {
827 uint32_t actual_value =
828 static_cast<uint32_t>(check->InputAt(input_pos)->AsIntConstant()->GetValue());
829 if (actual_value != expected_value) {
830 AddError(StringPrintf("%s:%d (bitstring) has %s 0x%x, not 0x%x as expected.",
831 check->DebugName(),
832 check->GetId(),
833 name,
834 actual_value,
835 expected_value));
836 }
837 }
838 }
839
HandleTypeCheckInstruction(HTypeCheckInstruction * check)840 void GraphChecker::HandleTypeCheckInstruction(HTypeCheckInstruction* check) {
841 VisitInstruction(check);
842
843 if (check->GetTargetClassRTI().IsValid() && !check->GetTargetClassRTI().IsExact()) {
844 std::stringstream ssRTI;
845 ssRTI << check->GetTargetClassRTI();
846 AddError(StringPrintf("%s:%d in block %d with RTI %s has valid but inexact RTI.",
847 check->DebugName(),
848 check->GetId(),
849 check->GetBlock()->GetBlockId(),
850 ssRTI.str().c_str()));
851 }
852
853 HInstruction* input = check->InputAt(1);
854 if (check->GetTypeCheckKind() == TypeCheckKind::kBitstringCheck) {
855 if (!input->IsNullConstant()) {
856 AddError(StringPrintf("%s:%d (bitstring) expects a HNullConstant as second input, not %s:%d.",
857 check->DebugName(),
858 check->GetId(),
859 input->DebugName(),
860 input->GetId()));
861 }
862 bool check_values = false;
863 BitString::StorageType expected_path_to_root = 0u;
864 BitString::StorageType expected_mask = 0u;
865 {
866 ScopedObjectAccess soa(Thread::Current());
867 ObjPtr<mirror::Class> klass = check->GetClass().Get();
868 MutexLock subtype_check_lock(Thread::Current(), *Locks::subtype_check_lock_);
869 SubtypeCheckInfo::State state = SubtypeCheck<ObjPtr<mirror::Class>>::GetState(klass);
870 if (state == SubtypeCheckInfo::kAssigned) {
871 expected_path_to_root =
872 SubtypeCheck<ObjPtr<mirror::Class>>::GetEncodedPathToRootForTarget(klass);
873 expected_mask = SubtypeCheck<ObjPtr<mirror::Class>>::GetEncodedPathToRootMask(klass);
874 check_values = true;
875 } else {
876 AddError(StringPrintf("%s:%d (bitstring) references a class with unassigned bitstring.",
877 check->DebugName(),
878 check->GetId()));
879 }
880 }
881 CheckTypeCheckBitstringInput(
882 check, /* input_pos= */ 2, check_values, expected_path_to_root, "path_to_root");
883 CheckTypeCheckBitstringInput(check, /* input_pos= */ 3, check_values, expected_mask, "mask");
884 } else {
885 if (!input->IsLoadClass()) {
886 AddError(StringPrintf("%s:%d (classic) expects a HLoadClass as second input, not %s:%d.",
887 check->DebugName(),
888 check->GetId(),
889 input->DebugName(),
890 input->GetId()));
891 }
892 }
893 }
894
VisitCheckCast(HCheckCast * check)895 void GraphChecker::VisitCheckCast(HCheckCast* check) {
896 HandleTypeCheckInstruction(check);
897 }
898
VisitInstanceOf(HInstanceOf * instruction)899 void GraphChecker::VisitInstanceOf(HInstanceOf* instruction) {
900 HandleTypeCheckInstruction(instruction);
901 }
902
HandleLoop(HBasicBlock * loop_header)903 void GraphChecker::HandleLoop(HBasicBlock* loop_header) {
904 int id = loop_header->GetBlockId();
905 HLoopInformation* loop_information = loop_header->GetLoopInformation();
906
907 if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
908 AddError(StringPrintf(
909 "Loop pre-header %d of loop defined by header %d has %zu successors.",
910 loop_information->GetPreHeader()->GetBlockId(),
911 id,
912 loop_information->GetPreHeader()->GetSuccessors().size()));
913 }
914
915 if (!GetGraph()->SuspendChecksAreAllowedToNoOp() &&
916 loop_information->GetSuspendCheck() == nullptr) {
917 AddError(StringPrintf("Loop with header %d does not have a suspend check.",
918 loop_header->GetBlockId()));
919 }
920
921 if (!GetGraph()->SuspendChecksAreAllowedToNoOp() &&
922 loop_information->GetSuspendCheck() != loop_header->GetFirstInstructionDisregardMoves()) {
923 AddError(StringPrintf(
924 "Loop header %d does not have the loop suspend check as the first instruction.",
925 loop_header->GetBlockId()));
926 }
927
928 // Ensure the loop header has only one incoming branch and the remaining
929 // predecessors are back edges.
930 size_t num_preds = loop_header->GetPredecessors().size();
931 if (num_preds < 2) {
932 AddError(StringPrintf(
933 "Loop header %d has less than two predecessors: %zu.",
934 id,
935 num_preds));
936 } else {
937 HBasicBlock* first_predecessor = loop_header->GetPredecessors()[0];
938 if (loop_information->IsBackEdge(*first_predecessor)) {
939 AddError(StringPrintf(
940 "First predecessor of loop header %d is a back edge.",
941 id));
942 }
943 for (size_t i = 1, e = loop_header->GetPredecessors().size(); i < e; ++i) {
944 HBasicBlock* predecessor = loop_header->GetPredecessors()[i];
945 if (!loop_information->IsBackEdge(*predecessor)) {
946 AddError(StringPrintf(
947 "Loop header %d has multiple incoming (non back edge) blocks: %d.",
948 id,
949 predecessor->GetBlockId()));
950 }
951 }
952 }
953
954 const ArenaBitVector& loop_blocks = loop_information->GetBlocks();
955
956 // Ensure back edges belong to the loop.
957 if (loop_information->NumberOfBackEdges() == 0) {
958 AddError(StringPrintf(
959 "Loop defined by header %d has no back edge.",
960 id));
961 } else {
962 for (HBasicBlock* back_edge : loop_information->GetBackEdges()) {
963 int back_edge_id = back_edge->GetBlockId();
964 if (!loop_blocks.IsBitSet(back_edge_id)) {
965 AddError(StringPrintf(
966 "Loop defined by header %d has an invalid back edge %d.",
967 id,
968 back_edge_id));
969 } else if (back_edge->GetLoopInformation() != loop_information) {
970 AddError(StringPrintf(
971 "Back edge %d of loop defined by header %d belongs to nested loop "
972 "with header %d.",
973 back_edge_id,
974 id,
975 back_edge->GetLoopInformation()->GetHeader()->GetBlockId()));
976 }
977 }
978 }
979
980 // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
981 for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
982 HLoopInformation* outer_info = it.Current();
983 if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) {
984 AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of "
985 "an outer loop defined by header %d.",
986 id,
987 outer_info->GetHeader()->GetBlockId()));
988 }
989 }
990
991 // Ensure the pre-header block is first in the list of predecessors of a loop
992 // header and that the header block is its only successor.
993 if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
994 AddError(StringPrintf(
995 "Loop pre-header is not the first predecessor of the loop header %d.",
996 id));
997 }
998
999 // Ensure all blocks in the loop are live and dominated by the loop header in
1000 // the case of natural loops.
1001 for (uint32_t i : loop_blocks.Indexes()) {
1002 HBasicBlock* loop_block = GetGraph()->GetBlocks()[i];
1003 if (loop_block == nullptr) {
1004 AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
1005 id,
1006 i));
1007 } else if (!loop_information->IsIrreducible() && !loop_header->Dominates(loop_block)) {
1008 AddError(StringPrintf("Loop block %d not dominated by loop header %d.",
1009 i,
1010 id));
1011 }
1012 }
1013 }
1014
IsSameSizeConstant(const HInstruction * insn1,const HInstruction * insn2)1015 static bool IsSameSizeConstant(const HInstruction* insn1, const HInstruction* insn2) {
1016 return insn1->IsConstant()
1017 && insn2->IsConstant()
1018 && DataType::Is64BitType(insn1->GetType()) == DataType::Is64BitType(insn2->GetType());
1019 }
1020
IsConstantEquivalent(const HInstruction * insn1,const HInstruction * insn2,BitVector * visited)1021 static bool IsConstantEquivalent(const HInstruction* insn1,
1022 const HInstruction* insn2,
1023 BitVector* visited) {
1024 if (insn1->IsPhi() && insn1->AsPhi()->IsVRegEquivalentOf(insn2)) {
1025 HConstInputsRef insn1_inputs = insn1->GetInputs();
1026 HConstInputsRef insn2_inputs = insn2->GetInputs();
1027 if (insn1_inputs.size() != insn2_inputs.size()) {
1028 return false;
1029 }
1030
1031 // Testing only one of the two inputs for recursion is sufficient.
1032 if (visited->IsBitSet(insn1->GetId())) {
1033 return true;
1034 }
1035 visited->SetBit(insn1->GetId());
1036
1037 for (size_t i = 0; i < insn1_inputs.size(); ++i) {
1038 if (!IsConstantEquivalent(insn1_inputs[i], insn2_inputs[i], visited)) {
1039 return false;
1040 }
1041 }
1042 return true;
1043 } else if (IsSameSizeConstant(insn1, insn2)) {
1044 return insn1->AsConstant()->GetValueAsUint64() == insn2->AsConstant()->GetValueAsUint64();
1045 } else {
1046 return false;
1047 }
1048 }
1049
VisitPhi(HPhi * phi)1050 void GraphChecker::VisitPhi(HPhi* phi) {
1051 VisitInstruction(phi);
1052
1053 // Ensure the first input of a phi is not itself.
1054 ArrayRef<HUserRecord<HInstruction*>> input_records = phi->GetInputRecords();
1055 if (input_records[0].GetInstruction() == phi) {
1056 AddError(StringPrintf("Loop phi %d in block %d is its own first input.",
1057 phi->GetId(),
1058 phi->GetBlock()->GetBlockId()));
1059 }
1060
1061 // Ensure that the inputs have the same primitive kind as the phi.
1062 for (size_t i = 0; i < input_records.size(); ++i) {
1063 HInstruction* input = input_records[i].GetInstruction();
1064 if (DataType::Kind(input->GetType()) != DataType::Kind(phi->GetType())) {
1065 AddError(StringPrintf(
1066 "Input %d at index %zu of phi %d from block %d does not have the "
1067 "same kind as the phi: %s versus %s",
1068 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
1069 DataType::PrettyDescriptor(input->GetType()),
1070 DataType::PrettyDescriptor(phi->GetType())));
1071 }
1072 }
1073 if (phi->GetType() != HPhi::ToPhiType(phi->GetType())) {
1074 AddError(StringPrintf("Phi %d in block %d does not have an expected phi type: %s",
1075 phi->GetId(),
1076 phi->GetBlock()->GetBlockId(),
1077 DataType::PrettyDescriptor(phi->GetType())));
1078 }
1079
1080 if (phi->IsCatchPhi()) {
1081 // The number of inputs of a catch phi should be the total number of throwing
1082 // instructions caught by this catch block. We do not enforce this, however,
1083 // because we do not remove the corresponding inputs when we prove that an
1084 // instruction cannot throw. Instead, we at least test that all phis have the
1085 // same, non-zero number of inputs (b/24054676).
1086 if (input_records.empty()) {
1087 AddError(StringPrintf("Phi %d in catch block %d has zero inputs.",
1088 phi->GetId(),
1089 phi->GetBlock()->GetBlockId()));
1090 } else {
1091 HInstruction* next_phi = phi->GetNext();
1092 if (next_phi != nullptr) {
1093 size_t input_count_next = next_phi->InputCount();
1094 if (input_records.size() != input_count_next) {
1095 AddError(StringPrintf("Phi %d in catch block %d has %zu inputs, "
1096 "but phi %d has %zu inputs.",
1097 phi->GetId(),
1098 phi->GetBlock()->GetBlockId(),
1099 input_records.size(),
1100 next_phi->GetId(),
1101 input_count_next));
1102 }
1103 }
1104 }
1105 } else {
1106 // Ensure the number of inputs of a non-catch phi is the same as the number
1107 // of its predecessors.
1108 const ArenaVector<HBasicBlock*>& predecessors = phi->GetBlock()->GetPredecessors();
1109 if (input_records.size() != predecessors.size()) {
1110 AddError(StringPrintf(
1111 "Phi %d in block %d has %zu inputs, "
1112 "but block %d has %zu predecessors.",
1113 phi->GetId(), phi->GetBlock()->GetBlockId(), input_records.size(),
1114 phi->GetBlock()->GetBlockId(), predecessors.size()));
1115 } else {
1116 // Ensure phi input at index I either comes from the Ith
1117 // predecessor or from a block that dominates this predecessor.
1118 for (size_t i = 0; i < input_records.size(); ++i) {
1119 HInstruction* input = input_records[i].GetInstruction();
1120 HBasicBlock* predecessor = predecessors[i];
1121 if (!(input->GetBlock() == predecessor
1122 || input->GetBlock()->Dominates(predecessor))) {
1123 AddError(StringPrintf(
1124 "Input %d at index %zu of phi %d from block %d is not defined in "
1125 "predecessor number %zu nor in a block dominating it.",
1126 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
1127 i));
1128 }
1129 }
1130 }
1131 }
1132
1133 // Ensure that catch phis are sorted by their vreg number, as required by
1134 // the register allocator and code generator. This does not apply to normal
1135 // phis which can be constructed artifically.
1136 if (phi->IsCatchPhi()) {
1137 HInstruction* next_phi = phi->GetNext();
1138 if (next_phi != nullptr && phi->GetRegNumber() > next_phi->AsPhi()->GetRegNumber()) {
1139 AddError(StringPrintf("Catch phis %d and %d in block %d are not sorted by their "
1140 "vreg numbers.",
1141 phi->GetId(),
1142 next_phi->GetId(),
1143 phi->GetBlock()->GetBlockId()));
1144 }
1145 }
1146
1147 // Test phi equivalents. There should not be two of the same type and they should only be
1148 // created for constants which were untyped in DEX. Note that this test can be skipped for
1149 // a synthetic phi (indicated by lack of a virtual register).
1150 if (phi->GetRegNumber() != kNoRegNumber) {
1151 for (HInstructionIterator phi_it(phi->GetBlock()->GetPhis());
1152 !phi_it.Done();
1153 phi_it.Advance()) {
1154 HPhi* other_phi = phi_it.Current()->AsPhi();
1155 if (phi != other_phi && phi->GetRegNumber() == other_phi->GetRegNumber()) {
1156 if (phi->GetType() == other_phi->GetType()) {
1157 std::stringstream type_str;
1158 type_str << phi->GetType();
1159 AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s.",
1160 phi->GetId(),
1161 phi->GetRegNumber(),
1162 type_str.str().c_str()));
1163 } else if (phi->GetType() == DataType::Type::kReference) {
1164 std::stringstream type_str;
1165 type_str << other_phi->GetType();
1166 AddError(StringPrintf(
1167 "Equivalent non-reference phi (%d) found for VReg %d with type: %s.",
1168 phi->GetId(),
1169 phi->GetRegNumber(),
1170 type_str.str().c_str()));
1171 } else {
1172 // Use local allocator for allocating memory.
1173 ScopedArenaAllocator allocator(GetGraph()->GetArenaStack());
1174 // If we get here, make sure we allocate all the necessary storage at once
1175 // because the BitVector reallocation strategy has very bad worst-case behavior.
1176 ArenaBitVector visited(&allocator,
1177 GetGraph()->GetCurrentInstructionId(),
1178 /* expandable= */ false,
1179 kArenaAllocGraphChecker);
1180 if (!IsConstantEquivalent(phi, other_phi, &visited)) {
1181 AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they "
1182 "are not equivalents of constants.",
1183 phi->GetId(),
1184 other_phi->GetId(),
1185 phi->GetRegNumber()));
1186 }
1187 }
1188 }
1189 }
1190 }
1191 }
1192
HandleBooleanInput(HInstruction * instruction,size_t input_index)1193 void GraphChecker::HandleBooleanInput(HInstruction* instruction, size_t input_index) {
1194 HInstruction* input = instruction->InputAt(input_index);
1195 if (input->IsIntConstant()) {
1196 int32_t value = input->AsIntConstant()->GetValue();
1197 if (value != 0 && value != 1) {
1198 AddError(StringPrintf(
1199 "%s instruction %d has a non-Boolean constant input %d whose value is: %d.",
1200 instruction->DebugName(),
1201 instruction->GetId(),
1202 static_cast<int>(input_index),
1203 value));
1204 }
1205 } else if (DataType::Kind(input->GetType()) != DataType::Type::kInt32) {
1206 // TODO: We need a data-flow analysis to determine if an input like Phi,
1207 // Select or a binary operation is actually Boolean. Allow for now.
1208 AddError(StringPrintf(
1209 "%s instruction %d has a non-integer input %d whose type is: %s.",
1210 instruction->DebugName(),
1211 instruction->GetId(),
1212 static_cast<int>(input_index),
1213 DataType::PrettyDescriptor(input->GetType())));
1214 }
1215 }
1216
VisitPackedSwitch(HPackedSwitch * instruction)1217 void GraphChecker::VisitPackedSwitch(HPackedSwitch* instruction) {
1218 VisitInstruction(instruction);
1219 // Check that the number of block successors matches the switch count plus
1220 // one for the default block.
1221 HBasicBlock* block = instruction->GetBlock();
1222 if (instruction->GetNumEntries() + 1u != block->GetSuccessors().size()) {
1223 AddError(StringPrintf(
1224 "%s instruction %d in block %d expects %u successors to the block, but found: %zu.",
1225 instruction->DebugName(),
1226 instruction->GetId(),
1227 block->GetBlockId(),
1228 instruction->GetNumEntries() + 1u,
1229 block->GetSuccessors().size()));
1230 }
1231 }
1232
VisitIf(HIf * instruction)1233 void GraphChecker::VisitIf(HIf* instruction) {
1234 VisitInstruction(instruction);
1235 HandleBooleanInput(instruction, 0);
1236 }
1237
VisitSelect(HSelect * instruction)1238 void GraphChecker::VisitSelect(HSelect* instruction) {
1239 VisitInstruction(instruction);
1240 HandleBooleanInput(instruction, 2);
1241 }
1242
VisitBooleanNot(HBooleanNot * instruction)1243 void GraphChecker::VisitBooleanNot(HBooleanNot* instruction) {
1244 VisitInstruction(instruction);
1245 HandleBooleanInput(instruction, 0);
1246 }
1247
VisitCondition(HCondition * op)1248 void GraphChecker::VisitCondition(HCondition* op) {
1249 VisitInstruction(op);
1250 if (op->GetType() != DataType::Type::kBool) {
1251 AddError(StringPrintf(
1252 "Condition %s %d has a non-Boolean result type: %s.",
1253 op->DebugName(), op->GetId(),
1254 DataType::PrettyDescriptor(op->GetType())));
1255 }
1256 HInstruction* lhs = op->InputAt(0);
1257 HInstruction* rhs = op->InputAt(1);
1258 if (DataType::Kind(lhs->GetType()) != DataType::Kind(rhs->GetType())) {
1259 AddError(StringPrintf(
1260 "Condition %s %d has inputs of different kinds: %s, and %s.",
1261 op->DebugName(), op->GetId(),
1262 DataType::PrettyDescriptor(lhs->GetType()),
1263 DataType::PrettyDescriptor(rhs->GetType())));
1264 }
1265 if (!op->IsEqual() && !op->IsNotEqual()) {
1266 if ((lhs->GetType() == DataType::Type::kReference)) {
1267 AddError(StringPrintf(
1268 "Condition %s %d uses an object as left-hand side input.",
1269 op->DebugName(), op->GetId()));
1270 } else if (rhs->GetType() == DataType::Type::kReference) {
1271 AddError(StringPrintf(
1272 "Condition %s %d uses an object as right-hand side input.",
1273 op->DebugName(), op->GetId()));
1274 }
1275 }
1276 }
1277
VisitNeg(HNeg * instruction)1278 void GraphChecker::VisitNeg(HNeg* instruction) {
1279 VisitInstruction(instruction);
1280 DataType::Type input_type = instruction->InputAt(0)->GetType();
1281 DataType::Type result_type = instruction->GetType();
1282 if (result_type != DataType::Kind(input_type)) {
1283 AddError(StringPrintf("Binary operation %s %d has a result type different "
1284 "from its input kind: %s vs %s.",
1285 instruction->DebugName(), instruction->GetId(),
1286 DataType::PrettyDescriptor(result_type),
1287 DataType::PrettyDescriptor(input_type)));
1288 }
1289 }
1290
HuntForOriginalReference(HInstruction * ref)1291 HInstruction* HuntForOriginalReference(HInstruction* ref) {
1292 // An original reference can be transformed by instructions like:
1293 // i0 NewArray
1294 // i1 HInstruction(i0) <-- NullCheck, BoundType, IntermediateAddress.
1295 // i2 ArraySet(i1, index, value)
1296 DCHECK(ref != nullptr);
1297 while (ref->IsNullCheck() || ref->IsBoundType() || ref->IsIntermediateAddress()) {
1298 ref = ref->InputAt(0);
1299 }
1300 return ref;
1301 }
1302
IsRemovedWriteBarrier(DataType::Type type,WriteBarrierKind write_barrier_kind,HInstruction * value)1303 bool IsRemovedWriteBarrier(DataType::Type type,
1304 WriteBarrierKind write_barrier_kind,
1305 HInstruction* value) {
1306 return write_barrier_kind == WriteBarrierKind::kDontEmit &&
1307 type == DataType::Type::kReference &&
1308 !HuntForOriginalReference(value)->IsNullConstant();
1309 }
1310
VisitArraySet(HArraySet * instruction)1311 void GraphChecker::VisitArraySet(HArraySet* instruction) {
1312 VisitInstruction(instruction);
1313
1314 if (instruction->NeedsTypeCheck() !=
1315 instruction->GetSideEffects().Includes(SideEffects::CanTriggerGC())) {
1316 AddError(
1317 StringPrintf("%s %d has a flag mismatch. An ArraySet instruction can trigger a GC iff it "
1318 "needs a type check. Needs type check: %s, Can trigger GC: %s",
1319 instruction->DebugName(),
1320 instruction->GetId(),
1321 StrBool(instruction->NeedsTypeCheck()),
1322 StrBool(instruction->GetSideEffects().Includes(SideEffects::CanTriggerGC()))));
1323 }
1324
1325 if (IsRemovedWriteBarrier(instruction->GetComponentType(),
1326 instruction->GetWriteBarrierKind(),
1327 instruction->GetValue())) {
1328 CheckWriteBarrier(instruction, [](HInstruction* it_instr) {
1329 return it_instr->AsArraySet()->GetWriteBarrierKind();
1330 });
1331 }
1332 }
1333
VisitInstanceFieldSet(HInstanceFieldSet * instruction)1334 void GraphChecker::VisitInstanceFieldSet(HInstanceFieldSet* instruction) {
1335 VisitInstruction(instruction);
1336 if (IsRemovedWriteBarrier(instruction->GetFieldType(),
1337 instruction->GetWriteBarrierKind(),
1338 instruction->GetValue())) {
1339 CheckWriteBarrier(instruction, [](HInstruction* it_instr) {
1340 return it_instr->AsInstanceFieldSet()->GetWriteBarrierKind();
1341 });
1342 }
1343 }
1344
VisitStaticFieldSet(HStaticFieldSet * instruction)1345 void GraphChecker::VisitStaticFieldSet(HStaticFieldSet* instruction) {
1346 VisitInstruction(instruction);
1347 if (IsRemovedWriteBarrier(instruction->GetFieldType(),
1348 instruction->GetWriteBarrierKind(),
1349 instruction->GetValue())) {
1350 CheckWriteBarrier(instruction, [](HInstruction* it_instr) {
1351 return it_instr->AsStaticFieldSet()->GetWriteBarrierKind();
1352 });
1353 }
1354 }
1355
1356 template <typename GetWriteBarrierKind>
CheckWriteBarrier(HInstruction * instruction,GetWriteBarrierKind && get_write_barrier_kind)1357 void GraphChecker::CheckWriteBarrier(HInstruction* instruction,
1358 GetWriteBarrierKind&& get_write_barrier_kind) {
1359 DCHECK(instruction->IsStaticFieldSet() ||
1360 instruction->IsInstanceFieldSet() ||
1361 instruction->IsArraySet());
1362
1363 // For removed write barriers, we expect that the write barrier they are relying on is:
1364 // A) In the same block, and
1365 // B) There's no instruction between them that can trigger a GC.
1366 HInstruction* object = HuntForOriginalReference(instruction->InputAt(0));
1367 bool found = false;
1368 for (HBackwardInstructionIterator it(instruction); !it.Done(); it.Advance()) {
1369 if (instruction->GetKind() == it.Current()->GetKind() &&
1370 object == HuntForOriginalReference(it.Current()->InputAt(0)) &&
1371 get_write_barrier_kind(it.Current()) == WriteBarrierKind::kEmitBeingReliedOn) {
1372 // Found the write barrier we are relying on.
1373 found = true;
1374 break;
1375 }
1376
1377 // We check the `SideEffects::CanTriggerGC` after failing to find the write barrier since having
1378 // a write barrier that's relying on an ArraySet that can trigger GC is fine because the card
1379 // table is marked after the GC happens.
1380 if (it.Current()->GetSideEffects().Includes(SideEffects::CanTriggerGC())) {
1381 AddError(
1382 StringPrintf("%s %d from block %d was expecting a write barrier and it didn't find "
1383 "any. %s %d can trigger GC",
1384 instruction->DebugName(),
1385 instruction->GetId(),
1386 instruction->GetBlock()->GetBlockId(),
1387 it.Current()->DebugName(),
1388 it.Current()->GetId()));
1389 }
1390 }
1391
1392 if (!found) {
1393 AddError(StringPrintf("%s %d in block %d didn't find a write barrier to latch onto",
1394 instruction->DebugName(),
1395 instruction->GetId(),
1396 instruction->GetBlock()->GetBlockId()));
1397 }
1398 }
1399
VisitBinaryOperation(HBinaryOperation * op)1400 void GraphChecker::VisitBinaryOperation(HBinaryOperation* op) {
1401 VisitInstruction(op);
1402 DataType::Type lhs_type = op->InputAt(0)->GetType();
1403 DataType::Type rhs_type = op->InputAt(1)->GetType();
1404 DataType::Type result_type = op->GetType();
1405
1406 // Type consistency between inputs.
1407 if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRol() || op->IsRor()) {
1408 if (DataType::Kind(rhs_type) != DataType::Type::kInt32) {
1409 AddError(StringPrintf("Shift/rotate operation %s %d has a non-int kind second input: "
1410 "%s of type %s.",
1411 op->DebugName(), op->GetId(),
1412 op->InputAt(1)->DebugName(),
1413 DataType::PrettyDescriptor(rhs_type)));
1414 }
1415 } else {
1416 if (DataType::Kind(lhs_type) != DataType::Kind(rhs_type)) {
1417 AddError(StringPrintf("Binary operation %s %d has inputs of different kinds: %s, and %s.",
1418 op->DebugName(), op->GetId(),
1419 DataType::PrettyDescriptor(lhs_type),
1420 DataType::PrettyDescriptor(rhs_type)));
1421 }
1422 }
1423
1424 // Type consistency between result and input(s).
1425 if (op->IsCompare()) {
1426 if (result_type != DataType::Type::kInt32) {
1427 AddError(StringPrintf("Compare operation %d has a non-int result type: %s.",
1428 op->GetId(),
1429 DataType::PrettyDescriptor(result_type)));
1430 }
1431 } else if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRol() || op->IsRor()) {
1432 // Only check the first input (value), as the second one (distance)
1433 // must invariably be of kind `int`.
1434 if (result_type != DataType::Kind(lhs_type)) {
1435 AddError(StringPrintf("Shift/rotate operation %s %d has a result type different "
1436 "from its left-hand side (value) input kind: %s vs %s.",
1437 op->DebugName(), op->GetId(),
1438 DataType::PrettyDescriptor(result_type),
1439 DataType::PrettyDescriptor(lhs_type)));
1440 }
1441 } else {
1442 if (DataType::Kind(result_type) != DataType::Kind(lhs_type)) {
1443 AddError(StringPrintf("Binary operation %s %d has a result kind different "
1444 "from its left-hand side input kind: %s vs %s.",
1445 op->DebugName(), op->GetId(),
1446 DataType::PrettyDescriptor(result_type),
1447 DataType::PrettyDescriptor(lhs_type)));
1448 }
1449 if (DataType::Kind(result_type) != DataType::Kind(rhs_type)) {
1450 AddError(StringPrintf("Binary operation %s %d has a result kind different "
1451 "from its right-hand side input kind: %s vs %s.",
1452 op->DebugName(), op->GetId(),
1453 DataType::PrettyDescriptor(result_type),
1454 DataType::PrettyDescriptor(rhs_type)));
1455 }
1456 }
1457 }
1458
VisitConstant(HConstant * instruction)1459 void GraphChecker::VisitConstant(HConstant* instruction) {
1460 VisitInstruction(instruction);
1461
1462 HBasicBlock* block = instruction->GetBlock();
1463 if (!block->IsEntryBlock()) {
1464 AddError(StringPrintf(
1465 "%s %d should be in the entry block but is in block %d.",
1466 instruction->DebugName(),
1467 instruction->GetId(),
1468 block->GetBlockId()));
1469 }
1470 }
1471
VisitBoundType(HBoundType * instruction)1472 void GraphChecker::VisitBoundType(HBoundType* instruction) {
1473 VisitInstruction(instruction);
1474
1475 if (!instruction->GetUpperBound().IsValid()) {
1476 AddError(StringPrintf(
1477 "%s %d does not have a valid upper bound RTI.",
1478 instruction->DebugName(),
1479 instruction->GetId()));
1480 }
1481 }
1482
VisitTypeConversion(HTypeConversion * instruction)1483 void GraphChecker::VisitTypeConversion(HTypeConversion* instruction) {
1484 VisitInstruction(instruction);
1485 DataType::Type result_type = instruction->GetResultType();
1486 DataType::Type input_type = instruction->GetInputType();
1487 // Invariant: We should never generate a conversion to a Boolean value.
1488 if (result_type == DataType::Type::kBool) {
1489 AddError(StringPrintf(
1490 "%s %d converts to a %s (from a %s).",
1491 instruction->DebugName(),
1492 instruction->GetId(),
1493 DataType::PrettyDescriptor(result_type),
1494 DataType::PrettyDescriptor(input_type)));
1495 }
1496 }
1497
VisitVecOperation(HVecOperation * instruction)1498 void GraphChecker::VisitVecOperation(HVecOperation* instruction) {
1499 VisitInstruction(instruction);
1500
1501 if (!GetGraph()->HasSIMD()) {
1502 AddError(
1503 StringPrintf("The graph doesn't have the HasSIMD flag set but we saw "
1504 "%s:%d in block %d.",
1505 instruction->DebugName(),
1506 instruction->GetId(),
1507 instruction->GetBlock()->GetBlockId()));
1508 }
1509
1510 flag_info_.seen_SIMD = true;
1511
1512 if (codegen_ == nullptr) {
1513 return;
1514 }
1515
1516 if (!codegen_->SupportsPredicatedSIMD() && instruction->IsPredicated()) {
1517 AddError(StringPrintf(
1518 "%s %d must not be predicated.",
1519 instruction->DebugName(),
1520 instruction->GetId()));
1521 }
1522
1523 if (codegen_->SupportsPredicatedSIMD() &&
1524 (instruction->MustBePredicatedInPredicatedSIMDMode() != instruction->IsPredicated())) {
1525 AddError(StringPrintf(
1526 "%s %d predication mode is incorrect; see HVecOperation::MustBePredicated.",
1527 instruction->DebugName(),
1528 instruction->GetId()));
1529 }
1530 }
1531
1532 } // namespace art
1533