blob: 31136772c7596ac93e337343313f2f86442b4879 [file] [log] [blame]
Roland Levillainccc07a92014-09-16 14:48:16 +01001/*
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
Vladimir Marko655e5852015-10-12 10:38:28 +010019#include <algorithm>
Roland Levillainccc07a92014-09-16 14:48:16 +010020#include <map>
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +000021#include <string>
Calin Juravlea4f88312015-04-16 12:57:19 +010022#include <sstream>
Roland Levillainccc07a92014-09-16 14:48:16 +010023
Vladimir Marko655e5852015-10-12 10:38:28 +010024#include "base/arena_containers.h"
Roland Levillain7e53b412014-09-23 10:50:22 +010025#include "base/bit_vector-inl.h"
Roland Levillain5c4405e2015-01-21 11:39:58 +000026#include "base/stringprintf.h"
David Brazdild9510df2015-11-04 23:30:22 +000027#include "handle_scope-inl.h"
Roland Levillain7e53b412014-09-23 10:50:22 +010028
Roland Levillainccc07a92014-09-16 14:48:16 +010029namespace art {
30
31void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
32 current_block_ = block;
33
34 // Check consistency with respect to predecessors of `block`.
Vladimir Marko655e5852015-10-12 10:38:28 +010035 ArenaSafeMap<HBasicBlock*, size_t> predecessors_count(
36 std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
Vladimir Marko60584552015-09-03 13:35:12 +000037 for (HBasicBlock* p : block->GetPredecessors()) {
Vladimir Marko655e5852015-10-12 10:38:28 +010038 auto it = predecessors_count.find(p);
39 if (it != predecessors_count.end()) {
40 ++it->second;
41 } else {
42 predecessors_count.Put(p, 1u);
43 }
Roland Levillainccc07a92014-09-16 14:48:16 +010044 }
45 for (auto& pc : predecessors_count) {
46 HBasicBlock* p = pc.first;
47 size_t p_count_in_block_predecessors = pc.second;
Vladimir Marko655e5852015-10-12 10:38:28 +010048 size_t block_count_in_p_successors =
49 std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block);
Roland Levillainccc07a92014-09-16 14:48:16 +010050 if (p_count_in_block_predecessors != block_count_in_p_successors) {
Roland Levillain5c4405e2015-01-21 11:39:58 +000051 AddError(StringPrintf(
52 "Block %d lists %zu occurrences of block %d in its predecessors, whereas "
53 "block %d lists %zu occurrences of block %d in its successors.",
54 block->GetBlockId(), p_count_in_block_predecessors, p->GetBlockId(),
55 p->GetBlockId(), block_count_in_p_successors, block->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +010056 }
57 }
58
59 // Check consistency with respect to successors of `block`.
Vladimir Marko655e5852015-10-12 10:38:28 +010060 ArenaSafeMap<HBasicBlock*, size_t> successors_count(
61 std::less<HBasicBlock*>(), GetGraph()->GetArena()->Adapter(kArenaAllocGraphChecker));
Vladimir Marko60584552015-09-03 13:35:12 +000062 for (HBasicBlock* s : block->GetSuccessors()) {
Vladimir Marko655e5852015-10-12 10:38:28 +010063 auto it = successors_count.find(s);
64 if (it != successors_count.end()) {
65 ++it->second;
66 } else {
67 successors_count.Put(s, 1u);
68 }
Roland Levillainccc07a92014-09-16 14:48:16 +010069 }
70 for (auto& sc : successors_count) {
71 HBasicBlock* s = sc.first;
72 size_t s_count_in_block_successors = sc.second;
Vladimir Marko655e5852015-10-12 10:38:28 +010073 size_t block_count_in_s_predecessors =
74 std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block);
Roland Levillainccc07a92014-09-16 14:48:16 +010075 if (s_count_in_block_successors != block_count_in_s_predecessors) {
Roland Levillain5c4405e2015-01-21 11:39:58 +000076 AddError(StringPrintf(
77 "Block %d lists %zu occurrences of block %d in its successors, whereas "
78 "block %d lists %zu occurrences of block %d in its predecessors.",
79 block->GetBlockId(), s_count_in_block_successors, s->GetBlockId(),
80 s->GetBlockId(), block_count_in_s_predecessors, block->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +010081 }
82 }
83
84 // Ensure `block` ends with a branch instruction.
David Brazdilfc6a86a2015-06-26 10:33:45 +000085 // This invariant is not enforced on non-SSA graphs. Graph built from DEX with
86 // dead code that falls out of the method will not end with a control-flow
87 // instruction. Such code is removed during the SSA-building DCE phase.
88 if (GetGraph()->IsInSsaForm() && !block->EndsWithControlFlowInstruction()) {
Roland Levillain5c4405e2015-01-21 11:39:58 +000089 AddError(StringPrintf("Block %d does not end with a branch instruction.",
90 block->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +010091 }
92
David Brazdil29fc0082015-08-18 17:17:38 +010093 // Ensure that only Return(Void) and Throw jump to Exit. An exiting
David Brazdilb618ade2015-07-29 10:31:29 +010094 // TryBoundary may be between a Throw and the Exit if the Throw is in a try.
95 if (block->IsExitBlock()) {
Vladimir Marko60584552015-09-03 13:35:12 +000096 for (HBasicBlock* predecessor : block->GetPredecessors()) {
David Brazdilb618ade2015-07-29 10:31:29 +010097 if (predecessor->IsSingleTryBoundary()
98 && !predecessor->GetLastInstruction()->AsTryBoundary()->IsEntry()) {
99 HBasicBlock* real_predecessor = predecessor->GetSinglePredecessor();
100 HInstruction* last_instruction = real_predecessor->GetLastInstruction();
101 if (!last_instruction->IsThrow()) {
102 AddError(StringPrintf("Unexpected TryBoundary between %s:%d and Exit.",
103 last_instruction->DebugName(),
104 last_instruction->GetId()));
105 }
106 } else {
107 HInstruction* last_instruction = predecessor->GetLastInstruction();
108 if (!last_instruction->IsReturn()
109 && !last_instruction->IsReturnVoid()
110 && !last_instruction->IsThrow()) {
111 AddError(StringPrintf("Unexpected instruction %s:%d jumps into the exit block.",
112 last_instruction->DebugName(),
113 last_instruction->GetId()));
114 }
115 }
116 }
117 }
118
Roland Levillainccc07a92014-09-16 14:48:16 +0100119 // Visit this block's list of phis.
120 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
David Brazdilc3d743f2015-04-22 13:40:50 +0100121 HInstruction* current = it.Current();
Roland Levillainccc07a92014-09-16 14:48:16 +0100122 // Ensure this block's list of phis contains only phis.
David Brazdilc3d743f2015-04-22 13:40:50 +0100123 if (!current->IsPhi()) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000124 AddError(StringPrintf("Block %d has a non-phi in its phi list.",
125 current_block_->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100126 }
David Brazdilc3d743f2015-04-22 13:40:50 +0100127 if (current->GetNext() == nullptr && current != block->GetLastPhi()) {
128 AddError(StringPrintf("The recorded last phi of block %d does not match "
129 "the actual last phi %d.",
130 current_block_->GetBlockId(),
131 current->GetId()));
132 }
133 current->Accept(this);
Roland Levillainccc07a92014-09-16 14:48:16 +0100134 }
135
136 // Visit this block's list of instructions.
David Brazdilc3d743f2015-04-22 13:40:50 +0100137 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
138 HInstruction* current = it.Current();
Roland Levillainccc07a92014-09-16 14:48:16 +0100139 // Ensure this block's list of instructions does not contains phis.
David Brazdilc3d743f2015-04-22 13:40:50 +0100140 if (current->IsPhi()) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000141 AddError(StringPrintf("Block %d has a phi in its non-phi list.",
142 current_block_->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100143 }
David Brazdilc3d743f2015-04-22 13:40:50 +0100144 if (current->GetNext() == nullptr && current != block->GetLastInstruction()) {
145 AddError(StringPrintf("The recorded last instruction of block %d does not match "
146 "the actual last instruction %d.",
147 current_block_->GetBlockId(),
148 current->GetId()));
149 }
150 current->Accept(this);
Roland Levillainccc07a92014-09-16 14:48:16 +0100151 }
152}
153
Mark Mendell1152c922015-04-24 17:06:35 -0400154void GraphChecker::VisitBoundsCheck(HBoundsCheck* check) {
155 if (!GetGraph()->HasBoundsChecks()) {
156 AddError(StringPrintf("Instruction %s:%d is a HBoundsCheck, "
157 "but HasBoundsChecks() returns false",
158 check->DebugName(),
159 check->GetId()));
160 }
161
162 // Perform the instruction base checks too.
163 VisitInstruction(check);
164}
165
David Brazdilffee3d32015-07-06 11:48:53 +0100166void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) {
David Brazdild26a4112015-11-10 11:07:31 +0000167 ArrayRef<HBasicBlock* const> handlers = try_boundary->GetExceptionHandlers();
168
169 // Ensure that all exception handlers are catch blocks.
David Brazdilffee3d32015-07-06 11:48:53 +0100170 // Note that a normal-flow successor may be a catch block before CFG
171 // simplification. We only test normal-flow successors in SsaChecker.
David Brazdild26a4112015-11-10 11:07:31 +0000172 for (HBasicBlock* handler : handlers) {
David Brazdilffee3d32015-07-06 11:48:53 +0100173 if (!handler->IsCatchBlock()) {
174 AddError(StringPrintf("Block %d with %s:%d has exceptional successor %d which "
175 "is not a catch block.",
176 current_block_->GetBlockId(),
177 try_boundary->DebugName(),
178 try_boundary->GetId(),
179 handler->GetBlockId()));
180 }
David Brazdild26a4112015-11-10 11:07:31 +0000181 }
182
183 // Ensure that handlers are not listed multiple times.
184 for (size_t i = 0, e = handlers.size(); i < e; ++i) {
David Brazdild8ef0c62015-11-10 18:49:28 +0000185 if (ContainsElement(handlers, handlers[i], i + 1)) {
186 AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.",
David Brazdild26a4112015-11-10 11:07:31 +0000187 handlers[i]->GetBlockId(),
David Brazdilffee3d32015-07-06 11:48:53 +0100188 try_boundary->DebugName(),
189 try_boundary->GetId()));
190 }
191 }
192
193 VisitInstruction(try_boundary);
194}
195
David Brazdil9bc43612015-11-05 21:25:24 +0000196void GraphChecker::VisitLoadException(HLoadException* load) {
197 // Ensure that LoadException is the first instruction in a catch block.
198 if (!load->GetBlock()->IsCatchBlock()) {
199 AddError(StringPrintf("%s:%d is in a non-catch block %d.",
200 load->DebugName(),
201 load->GetId(),
202 load->GetBlock()->GetBlockId()));
203 } else if (load->GetBlock()->GetFirstInstruction() != load) {
204 AddError(StringPrintf("%s:%d is not the first instruction in catch block %d.",
205 load->DebugName(),
206 load->GetId(),
207 load->GetBlock()->GetBlockId()));
208 }
209}
210
Roland Levillainccc07a92014-09-16 14:48:16 +0100211void GraphChecker::VisitInstruction(HInstruction* instruction) {
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +0000212 if (seen_ids_.IsBitSet(instruction->GetId())) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000213 AddError(StringPrintf("Instruction id %d is duplicate in graph.",
214 instruction->GetId()));
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +0000215 } else {
216 seen_ids_.SetBit(instruction->GetId());
217 }
218
Roland Levillainccc07a92014-09-16 14:48:16 +0100219 // Ensure `instruction` is associated with `current_block_`.
Roland Levillain5c4405e2015-01-21 11:39:58 +0000220 if (instruction->GetBlock() == nullptr) {
221 AddError(StringPrintf("%s %d in block %d not associated with any block.",
222 instruction->IsPhi() ? "Phi" : "Instruction",
223 instruction->GetId(),
224 current_block_->GetBlockId()));
225 } else if (instruction->GetBlock() != current_block_) {
226 AddError(StringPrintf("%s %d in block %d associated with block %d.",
227 instruction->IsPhi() ? "Phi" : "Instruction",
228 instruction->GetId(),
229 current_block_->GetBlockId(),
230 instruction->GetBlock()->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100231 }
Roland Levillain6b469232014-09-25 10:10:38 +0100232
233 // Ensure the inputs of `instruction` are defined in a block of the graph.
234 for (HInputIterator input_it(instruction); !input_it.Done();
235 input_it.Advance()) {
236 HInstruction* input = input_it.Current();
237 const HInstructionList& list = input->IsPhi()
238 ? input->GetBlock()->GetPhis()
239 : input->GetBlock()->GetInstructions();
240 if (!list.Contains(input)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000241 AddError(StringPrintf("Input %d of instruction %d is not defined "
242 "in a basic block of the control-flow graph.",
243 input->GetId(),
244 instruction->GetId()));
Roland Levillain6b469232014-09-25 10:10:38 +0100245 }
246 }
247
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100248 // Ensure the uses of `instruction` are defined in a block of the graph,
249 // and the entry in the use list is consistent.
David Brazdiled596192015-01-23 10:39:45 +0000250 for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
Roland Levillain6b469232014-09-25 10:10:38 +0100251 !use_it.Done(); use_it.Advance()) {
252 HInstruction* use = use_it.Current()->GetUser();
253 const HInstructionList& list = use->IsPhi()
254 ? use->GetBlock()->GetPhis()
255 : use->GetBlock()->GetInstructions();
256 if (!list.Contains(use)) {
Nicolas Geoffray276d9da2015-02-02 18:24:11 +0000257 AddError(StringPrintf("User %s:%d of instruction %d is not defined "
Roland Levillain5c4405e2015-01-21 11:39:58 +0000258 "in a basic block of the control-flow graph.",
Nicolas Geoffray276d9da2015-02-02 18:24:11 +0000259 use->DebugName(),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000260 use->GetId(),
261 instruction->GetId()));
Roland Levillain6b469232014-09-25 10:10:38 +0100262 }
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100263 size_t use_index = use_it.Current()->GetIndex();
264 if ((use_index >= use->InputCount()) || (use->InputAt(use_index) != instruction)) {
Vladimir Markob554b5a2015-11-06 12:57:55 +0000265 AddError(StringPrintf("User %s:%d of instruction %s:%d has a wrong "
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100266 "UseListNode index.",
267 use->DebugName(),
268 use->GetId(),
Vladimir Markob554b5a2015-11-06 12:57:55 +0000269 instruction->DebugName(),
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100270 instruction->GetId()));
271 }
272 }
273
274 // Ensure the environment uses entries are consistent.
275 for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
276 !use_it.Done(); use_it.Advance()) {
277 HEnvironment* use = use_it.Current()->GetUser();
278 size_t use_index = use_it.Current()->GetIndex();
279 if ((use_index >= use->Size()) || (use->GetInstructionAt(use_index) != instruction)) {
280 AddError(StringPrintf("Environment user of %s:%d has a wrong "
281 "UseListNode index.",
282 instruction->DebugName(),
283 instruction->GetId()));
284 }
Roland Levillain6b469232014-09-25 10:10:38 +0100285 }
David Brazdil1abb4192015-02-17 18:33:36 +0000286
287 // Ensure 'instruction' has pointers to its inputs' use entries.
288 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
289 HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
290 HInstruction* input = input_record.GetInstruction();
291 HUseListNode<HInstruction*>* use_node = input_record.GetUseNode();
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100292 size_t use_index = use_node->GetIndex();
293 if ((use_node == nullptr)
294 || !input->GetUses().Contains(use_node)
295 || (use_index >= e)
296 || (use_index != i)) {
David Brazdil1abb4192015-02-17 18:33:36 +0000297 AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry "
298 "at input %u (%s:%d).",
299 instruction->DebugName(),
300 instruction->GetId(),
301 static_cast<unsigned>(i),
302 input->DebugName(),
303 input->GetId()));
304 }
305 }
Roland Levillainccc07a92014-09-16 14:48:16 +0100306}
307
Roland Levillain4c0eb422015-04-24 16:43:49 +0100308void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
309 VisitInstruction(invoke);
310
311 if (invoke->IsStaticWithExplicitClinitCheck()) {
312 size_t last_input_index = invoke->InputCount() - 1;
313 HInstruction* last_input = invoke->InputAt(last_input_index);
314 if (last_input == nullptr) {
315 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
316 "has a null pointer as last input.",
317 invoke->DebugName(),
318 invoke->GetId()));
319 }
320 if (!last_input->IsClinitCheck() && !last_input->IsLoadClass()) {
321 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
322 "has a last instruction (%s:%d) which is neither a clinit check "
323 "nor a load class instruction.",
324 invoke->DebugName(),
325 invoke->GetId(),
326 last_input->DebugName(),
327 last_input->GetId()));
328 }
329 }
330}
331
David Brazdilfc6a86a2015-06-26 10:33:45 +0000332void GraphChecker::VisitReturn(HReturn* ret) {
Nicolas Geoffrayf9a19952015-06-29 13:43:54 +0100333 VisitInstruction(ret);
David Brazdilfc6a86a2015-06-26 10:33:45 +0000334 if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
335 AddError(StringPrintf("%s:%d does not jump to the exit block.",
336 ret->DebugName(),
337 ret->GetId()));
338 }
339}
340
341void GraphChecker::VisitReturnVoid(HReturnVoid* ret) {
Nicolas Geoffrayf9a19952015-06-29 13:43:54 +0100342 VisitInstruction(ret);
David Brazdilfc6a86a2015-06-26 10:33:45 +0000343 if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
344 AddError(StringPrintf("%s:%d does not jump to the exit block.",
345 ret->DebugName(),
346 ret->GetId()));
347 }
348}
349
Nicolas Geoffrayf9a19952015-06-29 13:43:54 +0100350void GraphChecker::VisitCheckCast(HCheckCast* check) {
351 VisitInstruction(check);
352 HInstruction* input = check->InputAt(1);
353 if (!input->IsLoadClass()) {
354 AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
355 check->DebugName(),
356 check->GetId(),
357 input->DebugName(),
358 input->GetId()));
359 }
360}
361
362void GraphChecker::VisitInstanceOf(HInstanceOf* instruction) {
363 VisitInstruction(instruction);
364 HInstruction* input = instruction->InputAt(1);
365 if (!input->IsLoadClass()) {
366 AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
367 instruction->DebugName(),
368 instruction->GetId(),
369 input->DebugName(),
370 input->GetId()));
371 }
372}
373
Roland Levillainccc07a92014-09-16 14:48:16 +0100374void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
375 super_type::VisitBasicBlock(block);
376
David Brazdilffee3d32015-07-06 11:48:53 +0100377 // Ensure that catch blocks are not normal successors, and normal blocks are
378 // never exceptional successors.
David Brazdild26a4112015-11-10 11:07:31 +0000379 for (HBasicBlock* successor : block->GetNormalSuccessors()) {
David Brazdilffee3d32015-07-06 11:48:53 +0100380 if (successor->IsCatchBlock()) {
381 AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
382 successor->GetBlockId(),
383 block->GetBlockId()));
384 }
385 }
David Brazdild26a4112015-11-10 11:07:31 +0000386 for (HBasicBlock* successor : block->GetExceptionalSuccessors()) {
David Brazdilffee3d32015-07-06 11:48:53 +0100387 if (!successor->IsCatchBlock()) {
388 AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
389 successor->GetBlockId(),
390 block->GetBlockId()));
391 }
392 }
393
Nicolas Geoffray15bd2282016-01-05 15:55:41 +0000394 // Ensure dominated blocks have `block` as the dominator.
395 for (HBasicBlock* dominated : block->GetDominatedBlocks()) {
396 if (dominated->GetDominator() != block) {
397 AddError(StringPrintf("Block %d should be the dominator of %d.",
398 block->GetBlockId(),
399 dominated->GetBlockId()));
400 }
401 }
402
Roland Levillainccc07a92014-09-16 14:48:16 +0100403 // Ensure there is no critical edge (i.e., an edge connecting a
404 // block with multiple successors to a block with multiple
David Brazdilffee3d32015-07-06 11:48:53 +0100405 // predecessors). Exceptional edges are synthesized and hence
406 // not accounted for.
David Brazdil81e479e2015-11-10 10:12:41 +0000407 if (block->GetSuccessors().size() > 1) {
David Brazdild26a4112015-11-10 11:07:31 +0000408 for (HBasicBlock* successor : block->GetNormalSuccessors()) {
David Brazdil81e479e2015-11-10 10:12:41 +0000409 if (successor->IsExitBlock() &&
410 block->IsSingleTryBoundary() &&
411 block->GetPredecessors().size() == 1u &&
412 block->GetSinglePredecessor()->GetLastInstruction()->IsThrow()) {
413 // Allowed critical edge Throw->TryBoundary->Exit.
414 } else if (successor->GetPredecessors().size() > 1) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000415 AddError(StringPrintf("Critical edge between blocks %d and %d.",
416 block->GetBlockId(),
417 successor->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100418 }
419 }
420 }
Roland Levillain6b879dd2014-09-22 17:13:44 +0100421
David Brazdilffee3d32015-07-06 11:48:53 +0100422 // Ensure try membership information is consistent.
David Brazdilffee3d32015-07-06 11:48:53 +0100423 if (block->IsCatchBlock()) {
David Brazdilec16f792015-08-19 15:04:01 +0100424 if (block->IsTryBlock()) {
425 const HTryBoundary& try_entry = block->GetTryCatchInformation()->GetTryEntry();
David Brazdilffee3d32015-07-06 11:48:53 +0100426 AddError(StringPrintf("Catch blocks should not be try blocks but catch block %d "
427 "has try entry %s:%d.",
428 block->GetBlockId(),
David Brazdilec16f792015-08-19 15:04:01 +0100429 try_entry.DebugName(),
430 try_entry.GetId()));
David Brazdilffee3d32015-07-06 11:48:53 +0100431 }
432
433 if (block->IsLoopHeader()) {
434 AddError(StringPrintf("Catch blocks should not be loop headers but catch block %d is.",
435 block->GetBlockId()));
436 }
437 } else {
Vladimir Marko60584552015-09-03 13:35:12 +0000438 for (HBasicBlock* predecessor : block->GetPredecessors()) {
David Brazdilec16f792015-08-19 15:04:01 +0100439 const HTryBoundary* incoming_try_entry = predecessor->ComputeTryEntryOfSuccessors();
440 if (block->IsTryBlock()) {
441 const HTryBoundary& stored_try_entry = block->GetTryCatchInformation()->GetTryEntry();
442 if (incoming_try_entry == nullptr) {
443 AddError(StringPrintf("Block %d has try entry %s:%d but no try entry follows "
David Brazdilffee3d32015-07-06 11:48:53 +0100444 "from predecessor %d.",
445 block->GetBlockId(),
David Brazdilec16f792015-08-19 15:04:01 +0100446 stored_try_entry.DebugName(),
447 stored_try_entry.GetId(),
448 predecessor->GetBlockId()));
449 } else if (!incoming_try_entry->HasSameExceptionHandlersAs(stored_try_entry)) {
450 AddError(StringPrintf("Block %d has try entry %s:%d which is not consistent "
451 "with %s:%d that follows from predecessor %d.",
452 block->GetBlockId(),
453 stored_try_entry.DebugName(),
454 stored_try_entry.GetId(),
David Brazdilffee3d32015-07-06 11:48:53 +0100455 incoming_try_entry->DebugName(),
456 incoming_try_entry->GetId(),
457 predecessor->GetBlockId()));
458 }
David Brazdilec16f792015-08-19 15:04:01 +0100459 } else if (incoming_try_entry != nullptr) {
460 AddError(StringPrintf("Block %d is not a try block but try entry %s:%d follows "
David Brazdilffee3d32015-07-06 11:48:53 +0100461 "from predecessor %d.",
462 block->GetBlockId(),
David Brazdilffee3d32015-07-06 11:48:53 +0100463 incoming_try_entry->DebugName(),
464 incoming_try_entry->GetId(),
465 predecessor->GetBlockId()));
466 }
467 }
468 }
469
Roland Levillain6b879dd2014-09-22 17:13:44 +0100470 if (block->IsLoopHeader()) {
471 CheckLoop(block);
472 }
473}
474
475void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
476 int id = loop_header->GetBlockId();
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100477 HLoopInformation* loop_information = loop_header->GetLoopInformation();
Roland Levillain6b879dd2014-09-22 17:13:44 +0100478
Nicolas Geoffray15bd2282016-01-05 15:55:41 +0000479 if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
David Brazdildb51efb2015-11-06 01:36:20 +0000480 AddError(StringPrintf(
481 "Loop pre-header %d of loop defined by header %d has %zu successors.",
482 loop_information->GetPreHeader()->GetBlockId(),
483 id,
484 loop_information->GetPreHeader()->GetSuccessors().size()));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100485 }
486
Nicolas Geoffray09aa1472016-01-19 10:52:54 +0000487 if (loop_information->GetSuspendCheck() == nullptr) {
488 AddError(StringPrintf(
489 "Loop with header %d does not have a suspend check.",
490 loop_header->GetBlockId()));
491 }
492
493 if (loop_information->GetSuspendCheck() != loop_header->GetFirstInstructionDisregardMoves()) {
494 AddError(StringPrintf(
495 "Loop header %d does not have the loop suspend check as the first instruction.",
496 loop_header->GetBlockId()));
497 }
498
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100499 // Ensure the loop header has only one incoming branch and the remaining
500 // predecessors are back edges.
Vladimir Marko60584552015-09-03 13:35:12 +0000501 size_t num_preds = loop_header->GetPredecessors().size();
Roland Levillain5c4405e2015-01-21 11:39:58 +0000502 if (num_preds < 2) {
503 AddError(StringPrintf(
504 "Loop header %d has less than two predecessors: %zu.",
505 id,
506 num_preds));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100507 } else {
Vladimir Markoec7802a2015-10-01 20:57:57 +0100508 HBasicBlock* first_predecessor = loop_header->GetPredecessors()[0];
David Brazdil46e2a392015-03-16 17:31:52 +0000509 if (loop_information->IsBackEdge(*first_predecessor)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000510 AddError(StringPrintf(
511 "First predecessor of loop header %d is a back edge.",
512 id));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100513 }
Vladimir Marko60584552015-09-03 13:35:12 +0000514 for (size_t i = 1, e = loop_header->GetPredecessors().size(); i < e; ++i) {
Vladimir Markoec7802a2015-10-01 20:57:57 +0100515 HBasicBlock* predecessor = loop_header->GetPredecessors()[i];
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100516 if (!loop_information->IsBackEdge(*predecessor)) {
517 AddError(StringPrintf(
518 "Loop header %d has multiple incoming (non back edge) blocks.",
519 id));
520 }
Roland Levillain6b879dd2014-09-22 17:13:44 +0100521 }
522 }
523
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100524 const ArenaBitVector& loop_blocks = loop_information->GetBlocks();
David Brazdil2d7352b2015-04-20 14:52:42 +0100525
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100526 // Ensure back edges belong to the loop.
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100527 if (loop_information->NumberOfBackEdges() == 0) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000528 AddError(StringPrintf(
529 "Loop defined by header %d has no back edge.",
530 id));
David Brazdil2d7352b2015-04-20 14:52:42 +0100531 } else {
Vladimir Markofa6b93c2015-09-15 10:15:55 +0100532 for (HBasicBlock* back_edge : loop_information->GetBackEdges()) {
533 int back_edge_id = back_edge->GetBlockId();
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100534 if (!loop_blocks.IsBitSet(back_edge_id)) {
535 AddError(StringPrintf(
536 "Loop defined by header %d has an invalid back edge %d.",
537 id,
538 back_edge_id));
David Brazdildb51efb2015-11-06 01:36:20 +0000539 } else if (back_edge->GetLoopInformation() != loop_information) {
540 AddError(StringPrintf(
541 "Back edge %d of loop defined by header %d belongs to nested loop "
542 "with header %d.",
543 back_edge_id,
544 id,
545 back_edge->GetLoopInformation()->GetHeader()->GetBlockId()));
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100546 }
David Brazdil2d7352b2015-04-20 14:52:42 +0100547 }
Roland Levillain6b879dd2014-09-22 17:13:44 +0100548 }
Roland Levillain7e53b412014-09-23 10:50:22 +0100549
David Brazdil7d275372015-04-21 16:36:35 +0100550 // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
551 for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
552 HLoopInformation* outer_info = it.Current();
553 if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) {
554 AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of "
555 "an outer loop defined by header %d.",
David Brazdil2d7352b2015-04-20 14:52:42 +0100556 id,
David Brazdil7d275372015-04-21 16:36:35 +0100557 outer_info->GetHeader()->GetBlockId()));
558 }
559 }
Nicolas Geoffray15bd2282016-01-05 15:55:41 +0000560
561 // Ensure the pre-header block is first in the list of predecessors of a loop
562 // header and that the header block is its only successor.
563 if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
564 AddError(StringPrintf(
565 "Loop pre-header is not the first predecessor of the loop header %d.",
566 id));
567 }
568
569 // Ensure all blocks in the loop are live and dominated by the loop header in
570 // the case of natural loops.
571 for (uint32_t i : loop_blocks.Indexes()) {
572 HBasicBlock* loop_block = GetGraph()->GetBlocks()[i];
573 if (loop_block == nullptr) {
574 AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
575 id,
576 i));
577 } else if (!loop_information->IsIrreducible() && !loop_header->Dominates(loop_block)) {
578 AddError(StringPrintf("Loop block %d not dominated by loop header %d.",
579 i,
580 id));
581 }
582 }
Roland Levillainccc07a92014-09-16 14:48:16 +0100583}
584
585void SSAChecker::VisitInstruction(HInstruction* instruction) {
586 super_type::VisitInstruction(instruction);
587
Roland Levillaina8069ce2014-10-01 10:48:29 +0100588 // Ensure an instruction dominates all its uses.
David Brazdiled596192015-01-23 10:39:45 +0000589 for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
Roland Levillaina8069ce2014-10-01 10:48:29 +0100590 !use_it.Done(); use_it.Advance()) {
591 HInstruction* use = use_it.Current()->GetUser();
Roland Levillain6c82d402014-10-13 16:10:27 +0100592 if (!use->IsPhi() && !instruction->StrictlyDominates(use)) {
Vladimir Markob554b5a2015-11-06 12:57:55 +0000593 AddError(StringPrintf("Instruction %s:%d in block %d does not dominate "
594 "use %s:%d in block %d.",
595 instruction->DebugName(),
596 instruction->GetId(),
597 current_block_->GetBlockId(),
598 use->DebugName(),
599 use->GetId(),
600 use->GetBlock()->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100601 }
602 }
Roland Levillaina8069ce2014-10-01 10:48:29 +0100603
Nicolas Geoffray09aa1472016-01-19 10:52:54 +0000604 if (instruction->NeedsEnvironment() && !instruction->HasEnvironment()) {
605 AddError(StringPrintf("Instruction %s:%d in block %d requires an environment "
606 "but does not have one.",
607 instruction->DebugName(),
608 instruction->GetId(),
609 current_block_->GetBlockId()));
610 }
611
Roland Levillaina8069ce2014-10-01 10:48:29 +0100612 // Ensure an instruction having an environment is dominated by the
613 // instructions contained in the environment.
Nicolas Geoffray0a23d742015-05-07 11:57:35 +0100614 for (HEnvironment* environment = instruction->GetEnvironment();
615 environment != nullptr;
616 environment = environment->GetParent()) {
Roland Levillaina8069ce2014-10-01 10:48:29 +0100617 for (size_t i = 0, e = environment->Size(); i < e; ++i) {
618 HInstruction* env_instruction = environment->GetInstructionAt(i);
619 if (env_instruction != nullptr
Roland Levillain6c82d402014-10-13 16:10:27 +0100620 && !env_instruction->StrictlyDominates(instruction)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000621 AddError(StringPrintf("Instruction %d in environment of instruction %d "
622 "from block %d does not dominate instruction %d.",
623 env_instruction->GetId(),
624 instruction->GetId(),
625 current_block_->GetBlockId(),
626 instruction->GetId()));
Roland Levillaina8069ce2014-10-01 10:48:29 +0100627 }
628 }
629 }
David Brazdild9510df2015-11-04 23:30:22 +0000630
631 // Ensure that reference type instructions have reference type info.
632 if (instruction->GetType() == Primitive::kPrimNot) {
633 ScopedObjectAccess soa(Thread::Current());
634 if (!instruction->GetReferenceTypeInfo().IsValid()) {
635 AddError(StringPrintf("Reference type instruction %s:%d does not have "
636 "valid reference type information.",
637 instruction->DebugName(),
638 instruction->GetId()));
639 }
640 }
David Brazdil6de19382016-01-08 17:37:10 +0000641
642 if (instruction->CanThrowIntoCatchBlock()) {
643 // Find the top-level environment. This corresponds to the environment of
644 // the catch block since we do not inline methods with try/catch.
645 HEnvironment* environment = instruction->GetEnvironment();
646 while (environment->GetParent() != nullptr) {
647 environment = environment->GetParent();
648 }
649
650 // Find all catch blocks and test that `instruction` has an environment
651 // value for each one.
652 const HTryBoundary& entry = instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
653 for (HBasicBlock* catch_block : entry.GetExceptionHandlers()) {
654 for (HInstructionIterator phi_it(catch_block->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
655 HPhi* catch_phi = phi_it.Current()->AsPhi();
656 if (environment->GetInstructionAt(catch_phi->GetRegNumber()) == nullptr) {
657 AddError(StringPrintf("Instruction %s:%d throws into catch block %d "
658 "with catch phi %d for vreg %d but its "
659 "corresponding environment slot is empty.",
660 instruction->DebugName(),
661 instruction->GetId(),
662 catch_block->GetBlockId(),
663 catch_phi->GetId(),
664 catch_phi->GetRegNumber()));
665 }
666 }
667 }
668 }
Roland Levillainccc07a92014-09-16 14:48:16 +0100669}
670
Nicolas Geoffrayd6138ef2015-02-18 14:48:53 +0000671static Primitive::Type PrimitiveKind(Primitive::Type type) {
672 switch (type) {
673 case Primitive::kPrimBoolean:
674 case Primitive::kPrimByte:
675 case Primitive::kPrimShort:
676 case Primitive::kPrimChar:
677 case Primitive::kPrimInt:
678 return Primitive::kPrimInt;
679 default:
680 return type;
681 }
682}
683
David Brazdil77a48ae2015-09-15 12:34:04 +0000684static bool IsSameSizeConstant(HInstruction* insn1, HInstruction* insn2) {
685 return insn1->IsConstant()
686 && insn2->IsConstant()
687 && Primitive::Is64BitType(insn1->GetType()) == Primitive::Is64BitType(insn2->GetType());
688}
689
690static bool IsConstantEquivalent(HInstruction* insn1, HInstruction* insn2, BitVector* visited) {
691 if (insn1->IsPhi() &&
692 insn1->AsPhi()->IsVRegEquivalentOf(insn2) &&
693 insn1->InputCount() == insn2->InputCount()) {
694 // Testing only one of the two inputs for recursion is sufficient.
695 if (visited->IsBitSet(insn1->GetId())) {
696 return true;
697 }
698 visited->SetBit(insn1->GetId());
699
700 for (size_t i = 0, e = insn1->InputCount(); i < e; ++i) {
701 if (!IsConstantEquivalent(insn1->InputAt(i), insn2->InputAt(i), visited)) {
702 return false;
703 }
704 }
705 return true;
706 } else if (IsSameSizeConstant(insn1, insn2)) {
707 return insn1->AsConstant()->GetValueAsUint64() == insn2->AsConstant()->GetValueAsUint64();
708 } else {
709 return false;
710 }
711}
712
Roland Levillain6b879dd2014-09-22 17:13:44 +0100713void SSAChecker::VisitPhi(HPhi* phi) {
714 VisitInstruction(phi);
715
716 // Ensure the first input of a phi is not itself.
717 if (phi->InputAt(0) == phi) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000718 AddError(StringPrintf("Loop phi %d in block %d is its own first input.",
719 phi->GetId(),
720 phi->GetBlock()->GetBlockId()));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100721 }
722
Nicolas Geoffrayd6138ef2015-02-18 14:48:53 +0000723 // Ensure that the inputs have the same primitive kind as the phi.
724 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
725 HInstruction* input = phi->InputAt(i);
726 if (PrimitiveKind(input->GetType()) != PrimitiveKind(phi->GetType())) {
727 AddError(StringPrintf(
728 "Input %d at index %zu of phi %d from block %d does not have the "
729 "same type as the phi: %s versus %s",
730 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
731 Primitive::PrettyDescriptor(input->GetType()),
732 Primitive::PrettyDescriptor(phi->GetType())));
733 }
Nicolas Geoffray31596742014-11-24 15:28:45 +0000734 }
Nicolas Geoffraye0fe7ae2015-03-09 10:02:49 +0000735 if (phi->GetType() != HPhi::ToPhiType(phi->GetType())) {
736 AddError(StringPrintf("Phi %d in block %d does not have an expected phi type: %s",
737 phi->GetId(),
738 phi->GetBlock()->GetBlockId(),
739 Primitive::PrettyDescriptor(phi->GetType())));
740 }
David Brazdilffee3d32015-07-06 11:48:53 +0100741
742 if (phi->IsCatchPhi()) {
David Brazdil3eaa32f2015-09-18 10:58:32 +0100743 // The number of inputs of a catch phi should be the total number of throwing
744 // instructions caught by this catch block. We do not enforce this, however,
745 // because we do not remove the corresponding inputs when we prove that an
746 // instruction cannot throw. Instead, we at least test that all phis have the
747 // same, non-zero number of inputs (b/24054676).
748 size_t input_count_this = phi->InputCount();
749 if (input_count_this == 0u) {
750 AddError(StringPrintf("Phi %d in catch block %d has zero inputs.",
751 phi->GetId(),
752 phi->GetBlock()->GetBlockId()));
753 } else {
754 HInstruction* next_phi = phi->GetNext();
755 if (next_phi != nullptr) {
756 size_t input_count_next = next_phi->InputCount();
757 if (input_count_this != input_count_next) {
758 AddError(StringPrintf("Phi %d in catch block %d has %zu inputs, "
759 "but phi %d has %zu inputs.",
760 phi->GetId(),
761 phi->GetBlock()->GetBlockId(),
762 input_count_this,
763 next_phi->GetId(),
764 input_count_next));
765 }
766 }
767 }
David Brazdilffee3d32015-07-06 11:48:53 +0100768 } else {
769 // Ensure the number of inputs of a non-catch phi is the same as the number
770 // of its predecessors.
Vladimir Marko60584552015-09-03 13:35:12 +0000771 const ArenaVector<HBasicBlock*>& predecessors = phi->GetBlock()->GetPredecessors();
772 if (phi->InputCount() != predecessors.size()) {
David Brazdilffee3d32015-07-06 11:48:53 +0100773 AddError(StringPrintf(
774 "Phi %d in block %d has %zu inputs, "
775 "but block %d has %zu predecessors.",
776 phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(),
Vladimir Marko60584552015-09-03 13:35:12 +0000777 phi->GetBlock()->GetBlockId(), predecessors.size()));
David Brazdilffee3d32015-07-06 11:48:53 +0100778 } else {
779 // Ensure phi input at index I either comes from the Ith
780 // predecessor or from a block that dominates this predecessor.
781 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
782 HInstruction* input = phi->InputAt(i);
Vladimir Marko60584552015-09-03 13:35:12 +0000783 HBasicBlock* predecessor = predecessors[i];
David Brazdilffee3d32015-07-06 11:48:53 +0100784 if (!(input->GetBlock() == predecessor
785 || input->GetBlock()->Dominates(predecessor))) {
786 AddError(StringPrintf(
787 "Input %d at index %zu of phi %d from block %d is not defined in "
788 "predecessor number %zu nor in a block dominating it.",
789 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
790 i));
791 }
792 }
793 }
794 }
David Brazdil77a48ae2015-09-15 12:34:04 +0000795
796 // Ensure that catch phis are sorted by their vreg number, as required by
797 // the register allocator and code generator. This does not apply to normal
798 // phis which can be constructed artifically.
799 if (phi->IsCatchPhi()) {
800 HInstruction* next_phi = phi->GetNext();
801 if (next_phi != nullptr && phi->GetRegNumber() > next_phi->AsPhi()->GetRegNumber()) {
802 AddError(StringPrintf("Catch phis %d and %d in block %d are not sorted by their "
803 "vreg numbers.",
804 phi->GetId(),
805 next_phi->GetId(),
806 phi->GetBlock()->GetBlockId()));
807 }
808 }
809
Aart Bik3fc7f352015-11-20 22:03:03 -0800810 // Test phi equivalents. There should not be two of the same type and they should only be
811 // created for constants which were untyped in DEX. Note that this test can be skipped for
812 // a synthetic phi (indicated by lack of a virtual register).
813 if (phi->GetRegNumber() != kNoRegNumber) {
Aart Bik4a342772015-11-30 10:17:46 -0800814 for (HInstructionIterator phi_it(phi->GetBlock()->GetPhis());
815 !phi_it.Done();
816 phi_it.Advance()) {
Aart Bik3fc7f352015-11-20 22:03:03 -0800817 HPhi* other_phi = phi_it.Current()->AsPhi();
818 if (phi != other_phi && phi->GetRegNumber() == other_phi->GetRegNumber()) {
819 if (phi->GetType() == other_phi->GetType()) {
820 std::stringstream type_str;
821 type_str << phi->GetType();
822 AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s.",
David Brazdil77a48ae2015-09-15 12:34:04 +0000823 phi->GetId(),
Aart Bik3fc7f352015-11-20 22:03:03 -0800824 phi->GetRegNumber(),
825 type_str.str().c_str()));
Nicolas Geoffrayf5f64ef2015-12-15 14:11:59 +0000826 } else if (phi->GetType() == Primitive::kPrimNot) {
827 std::stringstream type_str;
828 type_str << other_phi->GetType();
829 AddError(StringPrintf(
830 "Equivalent non-reference phi (%d) found for VReg %d with type: %s.",
831 phi->GetId(),
832 phi->GetRegNumber(),
833 type_str.str().c_str()));
Aart Bik3fc7f352015-11-20 22:03:03 -0800834 } else {
835 ArenaBitVector visited(GetGraph()->GetArena(), 0, /* expandable */ true);
836 if (!IsConstantEquivalent(phi, other_phi, &visited)) {
837 AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they "
838 "are not equivalents of constants.",
839 phi->GetId(),
840 other_phi->GetId(),
841 phi->GetRegNumber()));
842 }
David Brazdil77a48ae2015-09-15 12:34:04 +0000843 }
844 }
845 }
846 }
Nicolas Geoffray31596742014-11-24 15:28:45 +0000847}
848
David Brazdil13b47182015-04-15 16:29:32 +0100849void SSAChecker::HandleBooleanInput(HInstruction* instruction, size_t input_index) {
850 HInstruction* input = instruction->InputAt(input_index);
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000851 if (input->IsIntConstant()) {
David Brazdil13b47182015-04-15 16:29:32 +0100852 int32_t value = input->AsIntConstant()->GetValue();
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000853 if (value != 0 && value != 1) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000854 AddError(StringPrintf(
David Brazdil13b47182015-04-15 16:29:32 +0100855 "%s instruction %d has a non-Boolean constant input %d whose value is: %d.",
856 instruction->DebugName(),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000857 instruction->GetId(),
David Brazdil13b47182015-04-15 16:29:32 +0100858 static_cast<int>(input_index),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000859 value));
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000860 }
David Brazdil2fa194b2015-04-20 10:14:42 +0100861 } else if (input->GetType() == Primitive::kPrimInt
862 && (input->IsPhi() || input->IsAnd() || input->IsOr() || input->IsXor())) {
863 // TODO: We need a data-flow analysis to determine if the Phi or
864 // binary operation is actually Boolean. Allow for now.
David Brazdil13b47182015-04-15 16:29:32 +0100865 } else if (input->GetType() != Primitive::kPrimBoolean) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000866 AddError(StringPrintf(
David Brazdil13b47182015-04-15 16:29:32 +0100867 "%s instruction %d has a non-Boolean input %d whose type is: %s.",
868 instruction->DebugName(),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000869 instruction->GetId(),
David Brazdil13b47182015-04-15 16:29:32 +0100870 static_cast<int>(input_index),
871 Primitive::PrettyDescriptor(input->GetType())));
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000872 }
873}
874
Mark Mendellfe57faa2015-09-18 09:26:15 -0400875void SSAChecker::VisitPackedSwitch(HPackedSwitch* instruction) {
876 VisitInstruction(instruction);
877 // Check that the number of block successors matches the switch count plus
878 // one for the default block.
879 HBasicBlock* block = instruction->GetBlock();
880 if (instruction->GetNumEntries() + 1u != block->GetSuccessors().size()) {
881 AddError(StringPrintf(
882 "%s instruction %d in block %d expects %u successors to the block, but found: %zu.",
883 instruction->DebugName(),
884 instruction->GetId(),
885 block->GetBlockId(),
886 instruction->GetNumEntries() + 1u,
887 block->GetSuccessors().size()));
888 }
889}
890
David Brazdil13b47182015-04-15 16:29:32 +0100891void SSAChecker::VisitIf(HIf* instruction) {
892 VisitInstruction(instruction);
893 HandleBooleanInput(instruction, 0);
894}
895
896void SSAChecker::VisitBooleanNot(HBooleanNot* instruction) {
897 VisitInstruction(instruction);
898 HandleBooleanInput(instruction, 0);
899}
900
Nicolas Geoffray31596742014-11-24 15:28:45 +0000901void SSAChecker::VisitCondition(HCondition* op) {
902 VisitInstruction(op);
Nicolas Geoffray31596742014-11-24 15:28:45 +0000903 if (op->GetType() != Primitive::kPrimBoolean) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000904 AddError(StringPrintf(
905 "Condition %s %d has a non-Boolean result type: %s.",
906 op->DebugName(), op->GetId(),
907 Primitive::PrettyDescriptor(op->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000908 }
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000909 HInstruction* lhs = op->InputAt(0);
910 HInstruction* rhs = op->InputAt(1);
Calin Juravlea4f88312015-04-16 12:57:19 +0100911 if (PrimitiveKind(lhs->GetType()) != PrimitiveKind(rhs->GetType())) {
912 AddError(StringPrintf(
913 "Condition %s %d has inputs of different types: %s, and %s.",
914 op->DebugName(), op->GetId(),
915 Primitive::PrettyDescriptor(lhs->GetType()),
916 Primitive::PrettyDescriptor(rhs->GetType())));
917 }
918 if (!op->IsEqual() && !op->IsNotEqual()) {
919 if ((lhs->GetType() == Primitive::kPrimNot)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000920 AddError(StringPrintf(
921 "Condition %s %d uses an object as left-hand side input.",
922 op->DebugName(), op->GetId()));
Calin Juravlea4f88312015-04-16 12:57:19 +0100923 } else if (rhs->GetType() == Primitive::kPrimNot) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000924 AddError(StringPrintf(
925 "Condition %s %d uses an object as right-hand side input.",
926 op->DebugName(), op->GetId()));
Roland Levillainaecbd262015-01-19 12:44:01 +0000927 }
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000928 }
Nicolas Geoffray31596742014-11-24 15:28:45 +0000929}
930
931void SSAChecker::VisitBinaryOperation(HBinaryOperation* op) {
932 VisitInstruction(op);
Scott Wakeling40a04bf2015-12-11 09:50:36 +0000933 if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRor()) {
Nicolas Geoffray31596742014-11-24 15:28:45 +0000934 if (PrimitiveKind(op->InputAt(1)->GetType()) != Primitive::kPrimInt) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000935 AddError(StringPrintf(
936 "Shift operation %s %d has a non-int kind second input: "
937 "%s of type %s.",
938 op->DebugName(), op->GetId(),
939 op->InputAt(1)->DebugName(),
940 Primitive::PrettyDescriptor(op->InputAt(1)->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000941 }
942 } else {
Roland Levillain4c0eb422015-04-24 16:43:49 +0100943 if (PrimitiveKind(op->InputAt(0)->GetType()) != PrimitiveKind(op->InputAt(1)->GetType())) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000944 AddError(StringPrintf(
945 "Binary operation %s %d has inputs of different types: "
946 "%s, and %s.",
947 op->DebugName(), op->GetId(),
948 Primitive::PrettyDescriptor(op->InputAt(0)->GetType()),
949 Primitive::PrettyDescriptor(op->InputAt(1)->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000950 }
951 }
952
953 if (op->IsCompare()) {
954 if (op->GetType() != Primitive::kPrimInt) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000955 AddError(StringPrintf(
956 "Compare operation %d has a non-int result type: %s.",
957 op->GetId(),
958 Primitive::PrettyDescriptor(op->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000959 }
960 } else {
961 // Use the first input, so that we can also make this check for shift operations.
962 if (PrimitiveKind(op->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000963 AddError(StringPrintf(
964 "Binary operation %s %d has a result type different "
965 "from its input type: %s vs %s.",
966 op->DebugName(), op->GetId(),
967 Primitive::PrettyDescriptor(op->GetType()),
Roland Levillain4c0eb422015-04-24 16:43:49 +0100968 Primitive::PrettyDescriptor(op->InputAt(0)->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000969 }
970 }
971}
972
David Brazdil8d5b8b22015-03-24 10:51:52 +0000973void SSAChecker::VisitConstant(HConstant* instruction) {
974 HBasicBlock* block = instruction->GetBlock();
975 if (!block->IsEntryBlock()) {
976 AddError(StringPrintf(
977 "%s %d should be in the entry block but is in block %d.",
978 instruction->DebugName(),
979 instruction->GetId(),
980 block->GetBlockId()));
981 }
982}
983
David Brazdilf5552582015-12-27 13:36:12 +0000984void SSAChecker::VisitBoundType(HBoundType* instruction) {
985 VisitInstruction(instruction);
986
987 ScopedObjectAccess soa(Thread::Current());
988 if (!instruction->GetUpperBound().IsValid()) {
989 AddError(StringPrintf(
990 "%s %d does not have a valid upper bound RTI.",
991 instruction->DebugName(),
992 instruction->GetId()));
993 }
994}
995
Roland Levillainccc07a92014-09-16 14:48:16 +0100996} // namespace art