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