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 <string>
21 #include <sstream>
22 
23 #include "base/arena_containers.h"
24 #include "base/bit_vector-inl.h"
25 #include "base/stringprintf.h"
26 #include "handle_scope-inl.h"
27 
28 namespace art {
29 
IsAllowedToJumpToExitBlock(HInstruction * instruction)30 static bool IsAllowedToJumpToExitBlock(HInstruction* instruction) {
31   return instruction->IsThrow() || instruction->IsReturn() || instruction->IsReturnVoid();
32 }
33 
IsExitTryBoundaryIntoExitBlock(HBasicBlock * block)34 static bool IsExitTryBoundaryIntoExitBlock(HBasicBlock* block) {
35   if (!block->IsSingleTryBoundary()) {
36     return false;
37   }
38 
39   HTryBoundary* boundary = block->GetLastInstruction()->AsTryBoundary();
40   return block->GetPredecessors().size() == 1u &&
41          boundary->GetNormalFlowSuccessor()->IsExitBlock() &&
42          !boundary->IsEntry();
43 }
44 
VisitBasicBlock(HBasicBlock * block)45 void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
46   current_block_ = block;
47 
48   // Check consistency with respect to predecessors of `block`.
49   // Note: Counting duplicates with a sorted vector uses up to 6x less memory
50   // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
51   ArenaVector<HBasicBlock*>& sorted_predecessors = blocks_storage_;
52   sorted_predecessors.assign(block->GetPredecessors().begin(), block->GetPredecessors().end());
53   std::sort(sorted_predecessors.begin(), sorted_predecessors.end());
54   for (auto it = sorted_predecessors.begin(), end = sorted_predecessors.end(); it != end; ) {
55     HBasicBlock* p = *it++;
56     size_t p_count_in_block_predecessors = 1u;
57     for (; it != end && *it == p; ++it) {
58       ++p_count_in_block_predecessors;
59     }
60     size_t block_count_in_p_successors =
61         std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block);
62     if (p_count_in_block_predecessors != block_count_in_p_successors) {
63       AddError(StringPrintf(
64           "Block %d lists %zu occurrences of block %d in its predecessors, whereas "
65           "block %d lists %zu occurrences of block %d in its successors.",
66           block->GetBlockId(), p_count_in_block_predecessors, p->GetBlockId(),
67           p->GetBlockId(), block_count_in_p_successors, block->GetBlockId()));
68     }
69   }
70 
71   // Check consistency with respect to successors of `block`.
72   // Note: Counting duplicates with a sorted vector uses up to 6x less memory
73   // than ArenaSafeMap<HBasicBlock*, size_t> and also allows storage reuse.
74   ArenaVector<HBasicBlock*>& sorted_successors = blocks_storage_;
75   sorted_successors.assign(block->GetSuccessors().begin(), block->GetSuccessors().end());
76   std::sort(sorted_successors.begin(), sorted_successors.end());
77   for (auto it = sorted_successors.begin(), end = sorted_successors.end(); it != end; ) {
78     HBasicBlock* s = *it++;
79     size_t s_count_in_block_successors = 1u;
80     for (; it != end && *it == s; ++it) {
81       ++s_count_in_block_successors;
82     }
83     size_t block_count_in_s_predecessors =
84         std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block);
85     if (s_count_in_block_successors != block_count_in_s_predecessors) {
86       AddError(StringPrintf(
87           "Block %d lists %zu occurrences of block %d in its successors, whereas "
88           "block %d lists %zu occurrences of block %d in its predecessors.",
89           block->GetBlockId(), s_count_in_block_successors, s->GetBlockId(),
90           s->GetBlockId(), block_count_in_s_predecessors, block->GetBlockId()));
91     }
92   }
93 
94   // Ensure `block` ends with a branch instruction.
95   // This invariant is not enforced on non-SSA graphs. Graph built from DEX with
96   // dead code that falls out of the method will not end with a control-flow
97   // instruction. Such code is removed during the SSA-building DCE phase.
98   if (GetGraph()->IsInSsaForm() && !block->EndsWithControlFlowInstruction()) {
99     AddError(StringPrintf("Block %d does not end with a branch instruction.",
100                           block->GetBlockId()));
101   }
102 
103   // Ensure that only Return(Void) and Throw jump to Exit. An exiting TryBoundary
104   // may be between the instructions if the Throw/Return(Void) is in a try block.
105   if (block->IsExitBlock()) {
106     for (HBasicBlock* predecessor : block->GetPredecessors()) {
107       HInstruction* last_instruction = IsExitTryBoundaryIntoExitBlock(predecessor) ?
108         predecessor->GetSinglePredecessor()->GetLastInstruction() :
109         predecessor->GetLastInstruction();
110       if (!IsAllowedToJumpToExitBlock(last_instruction)) {
111         AddError(StringPrintf("Unexpected instruction %s:%d jumps into the exit block.",
112                               last_instruction->DebugName(),
113                               last_instruction->GetId()));
114       }
115     }
116   }
117 
118   // Visit this block's list of phis.
119   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
120     HInstruction* current = it.Current();
121     // Ensure this block's list of phis contains only phis.
122     if (!current->IsPhi()) {
123       AddError(StringPrintf("Block %d has a non-phi in its phi list.",
124                             current_block_->GetBlockId()));
125     }
126     if (current->GetNext() == nullptr && current != block->GetLastPhi()) {
127       AddError(StringPrintf("The recorded last phi of block %d does not match "
128                             "the actual last phi %d.",
129                             current_block_->GetBlockId(),
130                             current->GetId()));
131     }
132     current->Accept(this);
133   }
134 
135   // Visit this block's list of instructions.
136   for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
137     HInstruction* current = it.Current();
138     // Ensure this block's list of instructions does not contains phis.
139     if (current->IsPhi()) {
140       AddError(StringPrintf("Block %d has a phi in its non-phi list.",
141                             current_block_->GetBlockId()));
142     }
143     if (current->GetNext() == nullptr && current != block->GetLastInstruction()) {
144       AddError(StringPrintf("The recorded last instruction of block %d does not match "
145                             "the actual last instruction %d.",
146                             current_block_->GetBlockId(),
147                             current->GetId()));
148     }
149     current->Accept(this);
150   }
151 
152   // Ensure that catch blocks are not normal successors, and normal blocks are
153   // never exceptional successors.
154   for (HBasicBlock* successor : block->GetNormalSuccessors()) {
155     if (successor->IsCatchBlock()) {
156       AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
157                             successor->GetBlockId(),
158                             block->GetBlockId()));
159     }
160   }
161   for (HBasicBlock* successor : block->GetExceptionalSuccessors()) {
162     if (!successor->IsCatchBlock()) {
163       AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
164                             successor->GetBlockId(),
165                             block->GetBlockId()));
166     }
167   }
168 
169   // Ensure dominated blocks have `block` as the dominator.
170   for (HBasicBlock* dominated : block->GetDominatedBlocks()) {
171     if (dominated->GetDominator() != block) {
172       AddError(StringPrintf("Block %d should be the dominator of %d.",
173                             block->GetBlockId(),
174                             dominated->GetBlockId()));
175     }
176   }
177 
178   // Ensure there is no critical edge (i.e., an edge connecting a
179   // block with multiple successors to a block with multiple
180   // predecessors). Exceptional edges are synthesized and hence
181   // not accounted for.
182   if (block->GetSuccessors().size() > 1) {
183     if (IsExitTryBoundaryIntoExitBlock(block)) {
184       // Allowed critical edge (Throw/Return/ReturnVoid)->TryBoundary->Exit.
185     } else {
186       for (HBasicBlock* successor : block->GetNormalSuccessors()) {
187         if (successor->GetPredecessors().size() > 1) {
188           AddError(StringPrintf("Critical edge between blocks %d and %d.",
189                                 block->GetBlockId(),
190                                 successor->GetBlockId()));
191         }
192       }
193     }
194   }
195 
196   // Ensure try membership information is consistent.
197   if (block->IsCatchBlock()) {
198     if (block->IsTryBlock()) {
199       const HTryBoundary& try_entry = block->GetTryCatchInformation()->GetTryEntry();
200       AddError(StringPrintf("Catch blocks should not be try blocks but catch block %d "
201                             "has try entry %s:%d.",
202                             block->GetBlockId(),
203                             try_entry.DebugName(),
204                             try_entry.GetId()));
205     }
206 
207     if (block->IsLoopHeader()) {
208       AddError(StringPrintf("Catch blocks should not be loop headers but catch block %d is.",
209                             block->GetBlockId()));
210     }
211   } else {
212     for (HBasicBlock* predecessor : block->GetPredecessors()) {
213       const HTryBoundary* incoming_try_entry = predecessor->ComputeTryEntryOfSuccessors();
214       if (block->IsTryBlock()) {
215         const HTryBoundary& stored_try_entry = block->GetTryCatchInformation()->GetTryEntry();
216         if (incoming_try_entry == nullptr) {
217           AddError(StringPrintf("Block %d has try entry %s:%d but no try entry follows "
218                                 "from predecessor %d.",
219                                 block->GetBlockId(),
220                                 stored_try_entry.DebugName(),
221                                 stored_try_entry.GetId(),
222                                 predecessor->GetBlockId()));
223         } else if (!incoming_try_entry->HasSameExceptionHandlersAs(stored_try_entry)) {
224           AddError(StringPrintf("Block %d has try entry %s:%d which is not consistent "
225                                 "with %s:%d that follows from predecessor %d.",
226                                 block->GetBlockId(),
227                                 stored_try_entry.DebugName(),
228                                 stored_try_entry.GetId(),
229                                 incoming_try_entry->DebugName(),
230                                 incoming_try_entry->GetId(),
231                                 predecessor->GetBlockId()));
232         }
233       } else if (incoming_try_entry != nullptr) {
234         AddError(StringPrintf("Block %d is not a try block but try entry %s:%d follows "
235                               "from predecessor %d.",
236                               block->GetBlockId(),
237                               incoming_try_entry->DebugName(),
238                               incoming_try_entry->GetId(),
239                               predecessor->GetBlockId()));
240       }
241     }
242   }
243 
244   if (block->IsLoopHeader()) {
245     HandleLoop(block);
246   }
247 }
248 
VisitBoundsCheck(HBoundsCheck * check)249 void GraphChecker::VisitBoundsCheck(HBoundsCheck* check) {
250   if (!GetGraph()->HasBoundsChecks()) {
251     AddError(StringPrintf("Instruction %s:%d is a HBoundsCheck, "
252                           "but HasBoundsChecks() returns false",
253                           check->DebugName(),
254                           check->GetId()));
255   }
256 
257   // Perform the instruction base checks too.
258   VisitInstruction(check);
259 }
260 
VisitDeoptimize(HDeoptimize * deopt)261 void GraphChecker::VisitDeoptimize(HDeoptimize* deopt) {
262   if (GetGraph()->IsCompilingOsr()) {
263     AddError(StringPrintf("A graph compiled OSR cannot have a HDeoptimize instruction"));
264   }
265 
266   // Perform the instruction base checks too.
267   VisitInstruction(deopt);
268 }
269 
VisitTryBoundary(HTryBoundary * try_boundary)270 void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) {
271   ArrayRef<HBasicBlock* const> handlers = try_boundary->GetExceptionHandlers();
272 
273   // Ensure that all exception handlers are catch blocks.
274   // Note that a normal-flow successor may be a catch block before CFG
275   // simplification. We only test normal-flow successors in GraphChecker.
276   for (HBasicBlock* handler : handlers) {
277     if (!handler->IsCatchBlock()) {
278       AddError(StringPrintf("Block %d with %s:%d has exceptional successor %d which "
279                             "is not a catch block.",
280                             current_block_->GetBlockId(),
281                             try_boundary->DebugName(),
282                             try_boundary->GetId(),
283                             handler->GetBlockId()));
284     }
285   }
286 
287   // Ensure that handlers are not listed multiple times.
288   for (size_t i = 0, e = handlers.size(); i < e; ++i) {
289     if (ContainsElement(handlers, handlers[i], i + 1)) {
290         AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.",
291                             handlers[i]->GetBlockId(),
292                             try_boundary->DebugName(),
293                             try_boundary->GetId()));
294     }
295   }
296 
297   VisitInstruction(try_boundary);
298 }
299 
VisitLoadException(HLoadException * load)300 void GraphChecker::VisitLoadException(HLoadException* load) {
301   // Ensure that LoadException is the first instruction in a catch block.
302   if (!load->GetBlock()->IsCatchBlock()) {
303     AddError(StringPrintf("%s:%d is in a non-catch block %d.",
304                           load->DebugName(),
305                           load->GetId(),
306                           load->GetBlock()->GetBlockId()));
307   } else if (load->GetBlock()->GetFirstInstruction() != load) {
308     AddError(StringPrintf("%s:%d is not the first instruction in catch block %d.",
309                           load->DebugName(),
310                           load->GetId(),
311                           load->GetBlock()->GetBlockId()));
312   }
313 }
314 
VisitInstruction(HInstruction * instruction)315 void GraphChecker::VisitInstruction(HInstruction* instruction) {
316   if (seen_ids_.IsBitSet(instruction->GetId())) {
317     AddError(StringPrintf("Instruction id %d is duplicate in graph.",
318                           instruction->GetId()));
319   } else {
320     seen_ids_.SetBit(instruction->GetId());
321   }
322 
323   // Ensure `instruction` is associated with `current_block_`.
324   if (instruction->GetBlock() == nullptr) {
325     AddError(StringPrintf("%s %d in block %d not associated with any block.",
326                           instruction->IsPhi() ? "Phi" : "Instruction",
327                           instruction->GetId(),
328                           current_block_->GetBlockId()));
329   } else if (instruction->GetBlock() != current_block_) {
330     AddError(StringPrintf("%s %d in block %d associated with block %d.",
331                           instruction->IsPhi() ? "Phi" : "Instruction",
332                           instruction->GetId(),
333                           current_block_->GetBlockId(),
334                           instruction->GetBlock()->GetBlockId()));
335   }
336 
337   // Ensure the inputs of `instruction` are defined in a block of the graph.
338   for (HInputIterator input_it(instruction); !input_it.Done();
339        input_it.Advance()) {
340     HInstruction* input = input_it.Current();
341     const HInstructionList& list = input->IsPhi()
342         ? input->GetBlock()->GetPhis()
343         : input->GetBlock()->GetInstructions();
344     if (!list.Contains(input)) {
345       AddError(StringPrintf("Input %d of instruction %d is not defined "
346                             "in a basic block of the control-flow graph.",
347                             input->GetId(),
348                             instruction->GetId()));
349     }
350   }
351 
352   // Ensure the uses of `instruction` are defined in a block of the graph,
353   // and the entry in the use list is consistent.
354   for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
355     HInstruction* user = use.GetUser();
356     const HInstructionList& list = user->IsPhi()
357         ? user->GetBlock()->GetPhis()
358         : user->GetBlock()->GetInstructions();
359     if (!list.Contains(user)) {
360       AddError(StringPrintf("User %s:%d of instruction %d is not defined "
361                             "in a basic block of the control-flow graph.",
362                             user->DebugName(),
363                             user->GetId(),
364                             instruction->GetId()));
365     }
366     size_t use_index = use.GetIndex();
367     if ((use_index >= user->InputCount()) || (user->InputAt(use_index) != instruction)) {
368       AddError(StringPrintf("User %s:%d of instruction %s:%d has a wrong "
369                             "UseListNode index.",
370                             user->DebugName(),
371                             user->GetId(),
372                             instruction->DebugName(),
373                             instruction->GetId()));
374     }
375   }
376 
377   // Ensure the environment uses entries are consistent.
378   for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
379     HEnvironment* user = use.GetUser();
380     size_t use_index = use.GetIndex();
381     if ((use_index >= user->Size()) || (user->GetInstructionAt(use_index) != instruction)) {
382       AddError(StringPrintf("Environment user of %s:%d has a wrong "
383                             "UseListNode index.",
384                             instruction->DebugName(),
385                             instruction->GetId()));
386     }
387   }
388 
389   // Ensure 'instruction' has pointers to its inputs' use entries.
390   for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
391     HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
392     HInstruction* input = input_record.GetInstruction();
393     if ((input_record.GetBeforeUseNode() == input->GetUses().end()) ||
394         (input_record.GetUseNode() == input->GetUses().end()) ||
395         !input->GetUses().ContainsNode(*input_record.GetUseNode()) ||
396         (input_record.GetUseNode()->GetIndex() != i)) {
397       AddError(StringPrintf("Instruction %s:%d has an invalid iterator before use entry "
398                             "at input %u (%s:%d).",
399                             instruction->DebugName(),
400                             instruction->GetId(),
401                             static_cast<unsigned>(i),
402                             input->DebugName(),
403                             input->GetId()));
404     }
405   }
406 
407   // Ensure an instruction dominates all its uses.
408   for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
409     HInstruction* user = use.GetUser();
410     if (!user->IsPhi() && !instruction->StrictlyDominates(user)) {
411       AddError(StringPrintf("Instruction %s:%d in block %d does not dominate "
412                             "use %s:%d in block %d.",
413                             instruction->DebugName(),
414                             instruction->GetId(),
415                             current_block_->GetBlockId(),
416                             user->DebugName(),
417                             user->GetId(),
418                             user->GetBlock()->GetBlockId()));
419     }
420   }
421 
422   if (instruction->NeedsEnvironment() && !instruction->HasEnvironment()) {
423     AddError(StringPrintf("Instruction %s:%d in block %d requires an environment "
424                           "but does not have one.",
425                           instruction->DebugName(),
426                           instruction->GetId(),
427                           current_block_->GetBlockId()));
428   }
429 
430   // Ensure an instruction having an environment is dominated by the
431   // instructions contained in the environment.
432   for (HEnvironment* environment = instruction->GetEnvironment();
433        environment != nullptr;
434        environment = environment->GetParent()) {
435     for (size_t i = 0, e = environment->Size(); i < e; ++i) {
436       HInstruction* env_instruction = environment->GetInstructionAt(i);
437       if (env_instruction != nullptr
438           && !env_instruction->StrictlyDominates(instruction)) {
439         AddError(StringPrintf("Instruction %d in environment of instruction %d "
440                               "from block %d does not dominate instruction %d.",
441                               env_instruction->GetId(),
442                               instruction->GetId(),
443                               current_block_->GetBlockId(),
444                               instruction->GetId()));
445       }
446     }
447   }
448 
449   // Ensure that reference type instructions have reference type info.
450   if (instruction->GetType() == Primitive::kPrimNot) {
451     ScopedObjectAccess soa(Thread::Current());
452     if (!instruction->GetReferenceTypeInfo().IsValid()) {
453       AddError(StringPrintf("Reference type instruction %s:%d does not have "
454                             "valid reference type information.",
455                             instruction->DebugName(),
456                             instruction->GetId()));
457     }
458   }
459 
460   if (instruction->CanThrowIntoCatchBlock()) {
461     // Find the top-level environment. This corresponds to the environment of
462     // the catch block since we do not inline methods with try/catch.
463     HEnvironment* environment = instruction->GetEnvironment();
464     while (environment->GetParent() != nullptr) {
465       environment = environment->GetParent();
466     }
467 
468     // Find all catch blocks and test that `instruction` has an environment
469     // value for each one.
470     const HTryBoundary& entry = instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
471     for (HBasicBlock* catch_block : entry.GetExceptionHandlers()) {
472       for (HInstructionIterator phi_it(catch_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
473         HPhi* catch_phi = phi_it.Current()->AsPhi();
474         if (environment->GetInstructionAt(catch_phi->GetRegNumber()) == nullptr) {
475           AddError(StringPrintf("Instruction %s:%d throws into catch block %d "
476                                 "with catch phi %d for vreg %d but its "
477                                 "corresponding environment slot is empty.",
478                                 instruction->DebugName(),
479                                 instruction->GetId(),
480                                 catch_block->GetBlockId(),
481                                 catch_phi->GetId(),
482                                 catch_phi->GetRegNumber()));
483         }
484       }
485     }
486   }
487 }
488 
VisitInvokeStaticOrDirect(HInvokeStaticOrDirect * invoke)489 void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
490   VisitInstruction(invoke);
491 
492   if (invoke->IsStaticWithExplicitClinitCheck()) {
493     size_t last_input_index = invoke->InputCount() - 1;
494     HInstruction* last_input = invoke->InputAt(last_input_index);
495     if (last_input == nullptr) {
496       AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
497                             "has a null pointer as last input.",
498                             invoke->DebugName(),
499                             invoke->GetId()));
500     }
501     if (!last_input->IsClinitCheck() && !last_input->IsLoadClass()) {
502       AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
503                             "has a last instruction (%s:%d) which is neither a clinit check "
504                             "nor a load class instruction.",
505                             invoke->DebugName(),
506                             invoke->GetId(),
507                             last_input->DebugName(),
508                             last_input->GetId()));
509     }
510   }
511 }
512 
VisitReturn(HReturn * ret)513 void GraphChecker::VisitReturn(HReturn* ret) {
514   VisitInstruction(ret);
515   HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor();
516   if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) {
517     AddError(StringPrintf("%s:%d does not jump to the exit block.",
518                           ret->DebugName(),
519                           ret->GetId()));
520   }
521 }
522 
VisitReturnVoid(HReturnVoid * ret)523 void GraphChecker::VisitReturnVoid(HReturnVoid* ret) {
524   VisitInstruction(ret);
525   HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor();
526   if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) {
527     AddError(StringPrintf("%s:%d does not jump to the exit block.",
528                           ret->DebugName(),
529                           ret->GetId()));
530   }
531 }
532 
VisitCheckCast(HCheckCast * check)533 void GraphChecker::VisitCheckCast(HCheckCast* check) {
534   VisitInstruction(check);
535   HInstruction* input = check->InputAt(1);
536   if (!input->IsLoadClass()) {
537     AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
538                           check->DebugName(),
539                           check->GetId(),
540                           input->DebugName(),
541                           input->GetId()));
542   }
543 }
544 
VisitInstanceOf(HInstanceOf * instruction)545 void GraphChecker::VisitInstanceOf(HInstanceOf* instruction) {
546   VisitInstruction(instruction);
547   HInstruction* input = instruction->InputAt(1);
548   if (!input->IsLoadClass()) {
549     AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
550                           instruction->DebugName(),
551                           instruction->GetId(),
552                           input->DebugName(),
553                           input->GetId()));
554   }
555 }
556 
HandleLoop(HBasicBlock * loop_header)557 void GraphChecker::HandleLoop(HBasicBlock* loop_header) {
558   int id = loop_header->GetBlockId();
559   HLoopInformation* loop_information = loop_header->GetLoopInformation();
560 
561   if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
562     AddError(StringPrintf(
563         "Loop pre-header %d of loop defined by header %d has %zu successors.",
564         loop_information->GetPreHeader()->GetBlockId(),
565         id,
566         loop_information->GetPreHeader()->GetSuccessors().size()));
567   }
568 
569   if (loop_information->GetSuspendCheck() == nullptr) {
570     AddError(StringPrintf(
571         "Loop with header %d does not have a suspend check.",
572         loop_header->GetBlockId()));
573   }
574 
575   if (loop_information->GetSuspendCheck() != loop_header->GetFirstInstructionDisregardMoves()) {
576     AddError(StringPrintf(
577         "Loop header %d does not have the loop suspend check as the first instruction.",
578         loop_header->GetBlockId()));
579   }
580 
581   // Ensure the loop header has only one incoming branch and the remaining
582   // predecessors are back edges.
583   size_t num_preds = loop_header->GetPredecessors().size();
584   if (num_preds < 2) {
585     AddError(StringPrintf(
586         "Loop header %d has less than two predecessors: %zu.",
587         id,
588         num_preds));
589   } else {
590     HBasicBlock* first_predecessor = loop_header->GetPredecessors()[0];
591     if (loop_information->IsBackEdge(*first_predecessor)) {
592       AddError(StringPrintf(
593           "First predecessor of loop header %d is a back edge.",
594           id));
595     }
596     for (size_t i = 1, e = loop_header->GetPredecessors().size(); i < e; ++i) {
597       HBasicBlock* predecessor = loop_header->GetPredecessors()[i];
598       if (!loop_information->IsBackEdge(*predecessor)) {
599         AddError(StringPrintf(
600             "Loop header %d has multiple incoming (non back edge) blocks: %d.",
601             id,
602             predecessor->GetBlockId()));
603       }
604     }
605   }
606 
607   const ArenaBitVector& loop_blocks = loop_information->GetBlocks();
608 
609   // Ensure back edges belong to the loop.
610   if (loop_information->NumberOfBackEdges() == 0) {
611     AddError(StringPrintf(
612         "Loop defined by header %d has no back edge.",
613         id));
614   } else {
615     for (HBasicBlock* back_edge : loop_information->GetBackEdges()) {
616       int back_edge_id = back_edge->GetBlockId();
617       if (!loop_blocks.IsBitSet(back_edge_id)) {
618         AddError(StringPrintf(
619             "Loop defined by header %d has an invalid back edge %d.",
620             id,
621             back_edge_id));
622       } else if (back_edge->GetLoopInformation() != loop_information) {
623         AddError(StringPrintf(
624             "Back edge %d of loop defined by header %d belongs to nested loop "
625             "with header %d.",
626             back_edge_id,
627             id,
628             back_edge->GetLoopInformation()->GetHeader()->GetBlockId()));
629       }
630     }
631   }
632 
633   // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
634   for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
635     HLoopInformation* outer_info = it.Current();
636     if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) {
637       AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of "
638                             "an outer loop defined by header %d.",
639                             id,
640                             outer_info->GetHeader()->GetBlockId()));
641     }
642   }
643 
644   // Ensure the pre-header block is first in the list of predecessors of a loop
645   // header and that the header block is its only successor.
646   if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
647     AddError(StringPrintf(
648         "Loop pre-header is not the first predecessor of the loop header %d.",
649         id));
650   }
651 
652   // Ensure all blocks in the loop are live and dominated by the loop header in
653   // the case of natural loops.
654   for (uint32_t i : loop_blocks.Indexes()) {
655     HBasicBlock* loop_block = GetGraph()->GetBlocks()[i];
656     if (loop_block == nullptr) {
657       AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
658                             id,
659                             i));
660     } else if (!loop_information->IsIrreducible() && !loop_header->Dominates(loop_block)) {
661       AddError(StringPrintf("Loop block %d not dominated by loop header %d.",
662                             i,
663                             id));
664     }
665   }
666 }
667 
IsSameSizeConstant(HInstruction * insn1,HInstruction * insn2)668 static bool IsSameSizeConstant(HInstruction* insn1, HInstruction* insn2) {
669   return insn1->IsConstant()
670       && insn2->IsConstant()
671       && Primitive::Is64BitType(insn1->GetType()) == Primitive::Is64BitType(insn2->GetType());
672 }
673 
IsConstantEquivalent(HInstruction * insn1,HInstruction * insn2,BitVector * visited)674 static bool IsConstantEquivalent(HInstruction* insn1, HInstruction* insn2, BitVector* visited) {
675   if (insn1->IsPhi() &&
676       insn1->AsPhi()->IsVRegEquivalentOf(insn2) &&
677       insn1->InputCount() == insn2->InputCount()) {
678     // Testing only one of the two inputs for recursion is sufficient.
679     if (visited->IsBitSet(insn1->GetId())) {
680       return true;
681     }
682     visited->SetBit(insn1->GetId());
683 
684     for (size_t i = 0, e = insn1->InputCount(); i < e; ++i) {
685       if (!IsConstantEquivalent(insn1->InputAt(i), insn2->InputAt(i), visited)) {
686         return false;
687       }
688     }
689     return true;
690   } else if (IsSameSizeConstant(insn1, insn2)) {
691     return insn1->AsConstant()->GetValueAsUint64() == insn2->AsConstant()->GetValueAsUint64();
692   } else {
693     return false;
694   }
695 }
696 
VisitPhi(HPhi * phi)697 void GraphChecker::VisitPhi(HPhi* phi) {
698   VisitInstruction(phi);
699 
700   // Ensure the first input of a phi is not itself.
701   if (phi->InputAt(0) == phi) {
702     AddError(StringPrintf("Loop phi %d in block %d is its own first input.",
703                           phi->GetId(),
704                           phi->GetBlock()->GetBlockId()));
705   }
706 
707   // Ensure that the inputs have the same primitive kind as the phi.
708   for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
709     HInstruction* input = phi->InputAt(i);
710     if (Primitive::PrimitiveKind(input->GetType()) != Primitive::PrimitiveKind(phi->GetType())) {
711         AddError(StringPrintf(
712             "Input %d at index %zu of phi %d from block %d does not have the "
713             "same kind as the phi: %s versus %s",
714             input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
715             Primitive::PrettyDescriptor(input->GetType()),
716             Primitive::PrettyDescriptor(phi->GetType())));
717     }
718   }
719   if (phi->GetType() != HPhi::ToPhiType(phi->GetType())) {
720     AddError(StringPrintf("Phi %d in block %d does not have an expected phi type: %s",
721                           phi->GetId(),
722                           phi->GetBlock()->GetBlockId(),
723                           Primitive::PrettyDescriptor(phi->GetType())));
724   }
725 
726   if (phi->IsCatchPhi()) {
727     // The number of inputs of a catch phi should be the total number of throwing
728     // instructions caught by this catch block. We do not enforce this, however,
729     // because we do not remove the corresponding inputs when we prove that an
730     // instruction cannot throw. Instead, we at least test that all phis have the
731     // same, non-zero number of inputs (b/24054676).
732     size_t input_count_this = phi->InputCount();
733     if (input_count_this == 0u) {
734       AddError(StringPrintf("Phi %d in catch block %d has zero inputs.",
735                             phi->GetId(),
736                             phi->GetBlock()->GetBlockId()));
737     } else {
738       HInstruction* next_phi = phi->GetNext();
739       if (next_phi != nullptr) {
740         size_t input_count_next = next_phi->InputCount();
741         if (input_count_this != input_count_next) {
742           AddError(StringPrintf("Phi %d in catch block %d has %zu inputs, "
743                                 "but phi %d has %zu inputs.",
744                                 phi->GetId(),
745                                 phi->GetBlock()->GetBlockId(),
746                                 input_count_this,
747                                 next_phi->GetId(),
748                                 input_count_next));
749         }
750       }
751     }
752   } else {
753     // Ensure the number of inputs of a non-catch phi is the same as the number
754     // of its predecessors.
755     const ArenaVector<HBasicBlock*>& predecessors = phi->GetBlock()->GetPredecessors();
756     if (phi->InputCount() != predecessors.size()) {
757       AddError(StringPrintf(
758           "Phi %d in block %d has %zu inputs, "
759           "but block %d has %zu predecessors.",
760           phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(),
761           phi->GetBlock()->GetBlockId(), predecessors.size()));
762     } else {
763       // Ensure phi input at index I either comes from the Ith
764       // predecessor or from a block that dominates this predecessor.
765       for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
766         HInstruction* input = phi->InputAt(i);
767         HBasicBlock* predecessor = predecessors[i];
768         if (!(input->GetBlock() == predecessor
769               || input->GetBlock()->Dominates(predecessor))) {
770           AddError(StringPrintf(
771               "Input %d at index %zu of phi %d from block %d is not defined in "
772               "predecessor number %zu nor in a block dominating it.",
773               input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
774               i));
775         }
776       }
777     }
778   }
779 
780   // Ensure that catch phis are sorted by their vreg number, as required by
781   // the register allocator and code generator. This does not apply to normal
782   // phis which can be constructed artifically.
783   if (phi->IsCatchPhi()) {
784     HInstruction* next_phi = phi->GetNext();
785     if (next_phi != nullptr && phi->GetRegNumber() > next_phi->AsPhi()->GetRegNumber()) {
786       AddError(StringPrintf("Catch phis %d and %d in block %d are not sorted by their "
787                             "vreg numbers.",
788                             phi->GetId(),
789                             next_phi->GetId(),
790                             phi->GetBlock()->GetBlockId()));
791     }
792   }
793 
794   // Test phi equivalents. There should not be two of the same type and they should only be
795   // created for constants which were untyped in DEX. Note that this test can be skipped for
796   // a synthetic phi (indicated by lack of a virtual register).
797   if (phi->GetRegNumber() != kNoRegNumber) {
798     for (HInstructionIterator phi_it(phi->GetBlock()->GetPhis());
799          !phi_it.Done();
800          phi_it.Advance()) {
801       HPhi* other_phi = phi_it.Current()->AsPhi();
802       if (phi != other_phi && phi->GetRegNumber() == other_phi->GetRegNumber()) {
803         if (phi->GetType() == other_phi->GetType()) {
804           std::stringstream type_str;
805           type_str << phi->GetType();
806           AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s.",
807                                 phi->GetId(),
808                                 phi->GetRegNumber(),
809                                 type_str.str().c_str()));
810         } else if (phi->GetType() == Primitive::kPrimNot) {
811           std::stringstream type_str;
812           type_str << other_phi->GetType();
813           AddError(StringPrintf(
814               "Equivalent non-reference phi (%d) found for VReg %d with type: %s.",
815               phi->GetId(),
816               phi->GetRegNumber(),
817               type_str.str().c_str()));
818         } else {
819           // If we get here, make sure we allocate all the necessary storage at once
820           // because the BitVector reallocation strategy has very bad worst-case behavior.
821           ArenaBitVector& visited = visited_storage_;
822           visited.SetBit(GetGraph()->GetCurrentInstructionId());
823           visited.ClearAllBits();
824           if (!IsConstantEquivalent(phi, other_phi, &visited)) {
825             AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they "
826                                   "are not equivalents of constants.",
827                                   phi->GetId(),
828                                   other_phi->GetId(),
829                                   phi->GetRegNumber()));
830           }
831         }
832       }
833     }
834   }
835 }
836 
HandleBooleanInput(HInstruction * instruction,size_t input_index)837 void GraphChecker::HandleBooleanInput(HInstruction* instruction, size_t input_index) {
838   HInstruction* input = instruction->InputAt(input_index);
839   if (input->IsIntConstant()) {
840     int32_t value = input->AsIntConstant()->GetValue();
841     if (value != 0 && value != 1) {
842       AddError(StringPrintf(
843           "%s instruction %d has a non-Boolean constant input %d whose value is: %d.",
844           instruction->DebugName(),
845           instruction->GetId(),
846           static_cast<int>(input_index),
847           value));
848     }
849   } else if (Primitive::PrimitiveKind(input->GetType()) != Primitive::kPrimInt) {
850     // TODO: We need a data-flow analysis to determine if an input like Phi,
851     //       Select or a binary operation is actually Boolean. Allow for now.
852     AddError(StringPrintf(
853         "%s instruction %d has a non-integer input %d whose type is: %s.",
854         instruction->DebugName(),
855         instruction->GetId(),
856         static_cast<int>(input_index),
857         Primitive::PrettyDescriptor(input->GetType())));
858   }
859 }
860 
VisitPackedSwitch(HPackedSwitch * instruction)861 void GraphChecker::VisitPackedSwitch(HPackedSwitch* instruction) {
862   VisitInstruction(instruction);
863   // Check that the number of block successors matches the switch count plus
864   // one for the default block.
865   HBasicBlock* block = instruction->GetBlock();
866   if (instruction->GetNumEntries() + 1u != block->GetSuccessors().size()) {
867     AddError(StringPrintf(
868         "%s instruction %d in block %d expects %u successors to the block, but found: %zu.",
869         instruction->DebugName(),
870         instruction->GetId(),
871         block->GetBlockId(),
872         instruction->GetNumEntries() + 1u,
873         block->GetSuccessors().size()));
874   }
875 }
876 
VisitIf(HIf * instruction)877 void GraphChecker::VisitIf(HIf* instruction) {
878   VisitInstruction(instruction);
879   HandleBooleanInput(instruction, 0);
880 }
881 
VisitSelect(HSelect * instruction)882 void GraphChecker::VisitSelect(HSelect* instruction) {
883   VisitInstruction(instruction);
884   HandleBooleanInput(instruction, 2);
885 }
886 
VisitBooleanNot(HBooleanNot * instruction)887 void GraphChecker::VisitBooleanNot(HBooleanNot* instruction) {
888   VisitInstruction(instruction);
889   HandleBooleanInput(instruction, 0);
890 }
891 
VisitCondition(HCondition * op)892 void GraphChecker::VisitCondition(HCondition* op) {
893   VisitInstruction(op);
894   if (op->GetType() != Primitive::kPrimBoolean) {
895     AddError(StringPrintf(
896         "Condition %s %d has a non-Boolean result type: %s.",
897         op->DebugName(), op->GetId(),
898         Primitive::PrettyDescriptor(op->GetType())));
899   }
900   HInstruction* lhs = op->InputAt(0);
901   HInstruction* rhs = op->InputAt(1);
902   if (Primitive::PrimitiveKind(lhs->GetType()) != Primitive::PrimitiveKind(rhs->GetType())) {
903     AddError(StringPrintf(
904         "Condition %s %d has inputs of different kinds: %s, and %s.",
905         op->DebugName(), op->GetId(),
906         Primitive::PrettyDescriptor(lhs->GetType()),
907         Primitive::PrettyDescriptor(rhs->GetType())));
908   }
909   if (!op->IsEqual() && !op->IsNotEqual()) {
910     if ((lhs->GetType() == Primitive::kPrimNot)) {
911       AddError(StringPrintf(
912           "Condition %s %d uses an object as left-hand side input.",
913           op->DebugName(), op->GetId()));
914     } else if (rhs->GetType() == Primitive::kPrimNot) {
915       AddError(StringPrintf(
916           "Condition %s %d uses an object as right-hand side input.",
917           op->DebugName(), op->GetId()));
918     }
919   }
920 }
921 
VisitNeg(HNeg * instruction)922 void GraphChecker::VisitNeg(HNeg* instruction) {
923   VisitInstruction(instruction);
924   Primitive::Type input_type = instruction->InputAt(0)->GetType();
925   Primitive::Type result_type = instruction->GetType();
926   if (result_type != Primitive::PrimitiveKind(input_type)) {
927     AddError(StringPrintf("Binary operation %s %d has a result type different "
928                           "from its input kind: %s vs %s.",
929                           instruction->DebugName(), instruction->GetId(),
930                           Primitive::PrettyDescriptor(result_type),
931                           Primitive::PrettyDescriptor(input_type)));
932   }
933 }
934 
VisitBinaryOperation(HBinaryOperation * op)935 void GraphChecker::VisitBinaryOperation(HBinaryOperation* op) {
936   VisitInstruction(op);
937   Primitive::Type lhs_type = op->InputAt(0)->GetType();
938   Primitive::Type rhs_type = op->InputAt(1)->GetType();
939   Primitive::Type result_type = op->GetType();
940 
941   // Type consistency between inputs.
942   if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRor()) {
943     if (Primitive::PrimitiveKind(rhs_type) != Primitive::kPrimInt) {
944       AddError(StringPrintf("Shift/rotate operation %s %d has a non-int kind second input: "
945                             "%s of type %s.",
946                             op->DebugName(), op->GetId(),
947                             op->InputAt(1)->DebugName(),
948                             Primitive::PrettyDescriptor(rhs_type)));
949     }
950   } else {
951     if (Primitive::PrimitiveKind(lhs_type) != Primitive::PrimitiveKind(rhs_type)) {
952       AddError(StringPrintf("Binary operation %s %d has inputs of different kinds: %s, and %s.",
953                             op->DebugName(), op->GetId(),
954                             Primitive::PrettyDescriptor(lhs_type),
955                             Primitive::PrettyDescriptor(rhs_type)));
956     }
957   }
958 
959   // Type consistency between result and input(s).
960   if (op->IsCompare()) {
961     if (result_type != Primitive::kPrimInt) {
962       AddError(StringPrintf("Compare operation %d has a non-int result type: %s.",
963                             op->GetId(),
964                             Primitive::PrettyDescriptor(result_type)));
965     }
966   } else if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRor()) {
967     // Only check the first input (value), as the second one (distance)
968     // must invariably be of kind `int`.
969     if (result_type != Primitive::PrimitiveKind(lhs_type)) {
970       AddError(StringPrintf("Shift/rotate operation %s %d has a result type different "
971                             "from its left-hand side (value) input kind: %s vs %s.",
972                             op->DebugName(), op->GetId(),
973                             Primitive::PrettyDescriptor(result_type),
974                             Primitive::PrettyDescriptor(lhs_type)));
975     }
976   } else {
977     if (Primitive::PrimitiveKind(result_type) != Primitive::PrimitiveKind(lhs_type)) {
978       AddError(StringPrintf("Binary operation %s %d has a result kind different "
979                             "from its left-hand side input kind: %s vs %s.",
980                             op->DebugName(), op->GetId(),
981                             Primitive::PrettyDescriptor(result_type),
982                             Primitive::PrettyDescriptor(lhs_type)));
983     }
984     if (Primitive::PrimitiveKind(result_type) != Primitive::PrimitiveKind(rhs_type)) {
985       AddError(StringPrintf("Binary operation %s %d has a result kind different "
986                             "from its right-hand side input kind: %s vs %s.",
987                             op->DebugName(), op->GetId(),
988                             Primitive::PrettyDescriptor(result_type),
989                             Primitive::PrettyDescriptor(rhs_type)));
990     }
991   }
992 }
993 
VisitConstant(HConstant * instruction)994 void GraphChecker::VisitConstant(HConstant* instruction) {
995   HBasicBlock* block = instruction->GetBlock();
996   if (!block->IsEntryBlock()) {
997     AddError(StringPrintf(
998         "%s %d should be in the entry block but is in block %d.",
999         instruction->DebugName(),
1000         instruction->GetId(),
1001         block->GetBlockId()));
1002   }
1003 }
1004 
VisitBoundType(HBoundType * instruction)1005 void GraphChecker::VisitBoundType(HBoundType* instruction) {
1006   VisitInstruction(instruction);
1007 
1008   ScopedObjectAccess soa(Thread::Current());
1009   if (!instruction->GetUpperBound().IsValid()) {
1010     AddError(StringPrintf(
1011         "%s %d does not have a valid upper bound RTI.",
1012         instruction->DebugName(),
1013         instruction->GetId()));
1014   }
1015 }
1016 
VisitTypeConversion(HTypeConversion * instruction)1017 void GraphChecker::VisitTypeConversion(HTypeConversion* instruction) {
1018   VisitInstruction(instruction);
1019   Primitive::Type result_type = instruction->GetResultType();
1020   Primitive::Type input_type = instruction->GetInputType();
1021   // Invariant: We should never generate a conversion to a Boolean value.
1022   if (result_type == Primitive::kPrimBoolean) {
1023     AddError(StringPrintf(
1024         "%s %d converts to a %s (from a %s).",
1025         instruction->DebugName(),
1026         instruction->GetId(),
1027         Primitive::PrettyDescriptor(result_type),
1028         Primitive::PrettyDescriptor(input_type)));
1029   }
1030 }
1031 
1032 }  // namespace art
1033