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