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