blob: 847d5a4e9e3bb05f2a4c3983e38796058bca3998 [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
Roland Levillainccc07a92014-09-16 14:48:16 +010019#include <map>
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +000020#include <string>
Calin Juravlea4f88312015-04-16 12:57:19 +010021#include <sstream>
Roland Levillainccc07a92014-09-16 14:48:16 +010022
Roland Levillain7e53b412014-09-23 10:50:22 +010023#include "base/bit_vector-inl.h"
Roland Levillain5c4405e2015-01-21 11:39:58 +000024#include "base/stringprintf.h"
Roland Levillain7e53b412014-09-23 10:50:22 +010025
Roland Levillainccc07a92014-09-16 14:48:16 +010026namespace art {
27
28void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
29 current_block_ = block;
30
31 // Check consistency with respect to predecessors of `block`.
32 const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
33 std::map<HBasicBlock*, size_t> predecessors_count;
34 for (size_t i = 0, e = predecessors.Size(); i < e; ++i) {
35 HBasicBlock* p = predecessors.Get(i);
36 ++predecessors_count[p];
37 }
38 for (auto& pc : predecessors_count) {
39 HBasicBlock* p = pc.first;
40 size_t p_count_in_block_predecessors = pc.second;
41 const GrowableArray<HBasicBlock*>& p_successors = p->GetSuccessors();
42 size_t block_count_in_p_successors = 0;
43 for (size_t j = 0, f = p_successors.Size(); j < f; ++j) {
44 if (p_successors.Get(j) == block) {
45 ++block_count_in_p_successors;
46 }
47 }
48 if (p_count_in_block_predecessors != block_count_in_p_successors) {
Roland Levillain5c4405e2015-01-21 11:39:58 +000049 AddError(StringPrintf(
50 "Block %d lists %zu occurrences of block %d in its predecessors, whereas "
51 "block %d lists %zu occurrences of block %d in its successors.",
52 block->GetBlockId(), p_count_in_block_predecessors, p->GetBlockId(),
53 p->GetBlockId(), block_count_in_p_successors, block->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +010054 }
55 }
56
57 // Check consistency with respect to successors of `block`.
58 const GrowableArray<HBasicBlock*>& successors = block->GetSuccessors();
59 std::map<HBasicBlock*, size_t> successors_count;
60 for (size_t i = 0, e = successors.Size(); i < e; ++i) {
61 HBasicBlock* s = successors.Get(i);
62 ++successors_count[s];
63 }
64 for (auto& sc : successors_count) {
65 HBasicBlock* s = sc.first;
66 size_t s_count_in_block_successors = sc.second;
67 const GrowableArray<HBasicBlock*>& s_predecessors = s->GetPredecessors();
68 size_t block_count_in_s_predecessors = 0;
69 for (size_t j = 0, f = s_predecessors.Size(); j < f; ++j) {
70 if (s_predecessors.Get(j) == block) {
71 ++block_count_in_s_predecessors;
72 }
73 }
74 if (s_count_in_block_successors != block_count_in_s_predecessors) {
Roland Levillain5c4405e2015-01-21 11:39:58 +000075 AddError(StringPrintf(
76 "Block %d lists %zu occurrences of block %d in its successors, whereas "
77 "block %d lists %zu occurrences of block %d in its predecessors.",
78 block->GetBlockId(), s_count_in_block_successors, s->GetBlockId(),
79 s->GetBlockId(), block_count_in_s_predecessors, block->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +010080 }
81 }
82
83 // Ensure `block` ends with a branch instruction.
David Brazdilfc6a86a2015-06-26 10:33:45 +000084 // This invariant is not enforced on non-SSA graphs. Graph built from DEX with
85 // dead code that falls out of the method will not end with a control-flow
86 // instruction. Such code is removed during the SSA-building DCE phase.
87 if (GetGraph()->IsInSsaForm() && !block->EndsWithControlFlowInstruction()) {
Roland Levillain5c4405e2015-01-21 11:39:58 +000088 AddError(StringPrintf("Block %d does not end with a branch instruction.",
89 block->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +010090 }
91
David Brazdil29fc0082015-08-18 17:17:38 +010092 // Ensure that only Return(Void) and Throw jump to Exit. An exiting
David Brazdilb618ade2015-07-29 10:31:29 +010093 // TryBoundary may be between a Throw and the Exit if the Throw is in a try.
94 if (block->IsExitBlock()) {
95 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
96 HBasicBlock* predecessor = block->GetPredecessors().Get(i);
97 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) {
167 // Ensure that all exception handlers are catch blocks and that handlers
168 // are not listed multiple times.
169 // Note that a normal-flow successor may be a catch block before CFG
170 // simplification. We only test normal-flow successors in SsaChecker.
171 for (HExceptionHandlerIterator it(*try_boundary); !it.Done(); it.Advance()) {
172 HBasicBlock* handler = it.Current();
173 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 }
181 if (current_block_->GetSuccessors().Contains(
182 handler, /* start_from */ it.CurrentSuccessorIndex() + 1)) {
183 AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.",
184 handler->GetBlockId(),
185 try_boundary->DebugName(),
186 try_boundary->GetId()));
187 }
188 }
189
190 VisitInstruction(try_boundary);
191}
192
Roland Levillainccc07a92014-09-16 14:48:16 +0100193void GraphChecker::VisitInstruction(HInstruction* instruction) {
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +0000194 if (seen_ids_.IsBitSet(instruction->GetId())) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000195 AddError(StringPrintf("Instruction id %d is duplicate in graph.",
196 instruction->GetId()));
Nicolas Geoffray7c5367b2014-12-17 10:13:46 +0000197 } else {
198 seen_ids_.SetBit(instruction->GetId());
199 }
200
Roland Levillainccc07a92014-09-16 14:48:16 +0100201 // Ensure `instruction` is associated with `current_block_`.
Roland Levillain5c4405e2015-01-21 11:39:58 +0000202 if (instruction->GetBlock() == nullptr) {
203 AddError(StringPrintf("%s %d in block %d not associated with any block.",
204 instruction->IsPhi() ? "Phi" : "Instruction",
205 instruction->GetId(),
206 current_block_->GetBlockId()));
207 } else if (instruction->GetBlock() != current_block_) {
208 AddError(StringPrintf("%s %d in block %d associated with block %d.",
209 instruction->IsPhi() ? "Phi" : "Instruction",
210 instruction->GetId(),
211 current_block_->GetBlockId(),
212 instruction->GetBlock()->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100213 }
Roland Levillain6b469232014-09-25 10:10:38 +0100214
215 // Ensure the inputs of `instruction` are defined in a block of the graph.
216 for (HInputIterator input_it(instruction); !input_it.Done();
217 input_it.Advance()) {
218 HInstruction* input = input_it.Current();
219 const HInstructionList& list = input->IsPhi()
220 ? input->GetBlock()->GetPhis()
221 : input->GetBlock()->GetInstructions();
222 if (!list.Contains(input)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000223 AddError(StringPrintf("Input %d of instruction %d is not defined "
224 "in a basic block of the control-flow graph.",
225 input->GetId(),
226 instruction->GetId()));
Roland Levillain6b469232014-09-25 10:10:38 +0100227 }
228 }
229
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100230 // Ensure the uses of `instruction` are defined in a block of the graph,
231 // and the entry in the use list is consistent.
David Brazdiled596192015-01-23 10:39:45 +0000232 for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
Roland Levillain6b469232014-09-25 10:10:38 +0100233 !use_it.Done(); use_it.Advance()) {
234 HInstruction* use = use_it.Current()->GetUser();
235 const HInstructionList& list = use->IsPhi()
236 ? use->GetBlock()->GetPhis()
237 : use->GetBlock()->GetInstructions();
238 if (!list.Contains(use)) {
Nicolas Geoffray276d9da2015-02-02 18:24:11 +0000239 AddError(StringPrintf("User %s:%d of instruction %d is not defined "
Roland Levillain5c4405e2015-01-21 11:39:58 +0000240 "in a basic block of the control-flow graph.",
Nicolas Geoffray276d9da2015-02-02 18:24:11 +0000241 use->DebugName(),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000242 use->GetId(),
243 instruction->GetId()));
Roland Levillain6b469232014-09-25 10:10:38 +0100244 }
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100245 size_t use_index = use_it.Current()->GetIndex();
246 if ((use_index >= use->InputCount()) || (use->InputAt(use_index) != instruction)) {
247 AddError(StringPrintf("User %s:%d of instruction %d has a wrong "
248 "UseListNode index.",
249 use->DebugName(),
250 use->GetId(),
251 instruction->GetId()));
252 }
253 }
254
255 // Ensure the environment uses entries are consistent.
256 for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses());
257 !use_it.Done(); use_it.Advance()) {
258 HEnvironment* use = use_it.Current()->GetUser();
259 size_t use_index = use_it.Current()->GetIndex();
260 if ((use_index >= use->Size()) || (use->GetInstructionAt(use_index) != instruction)) {
261 AddError(StringPrintf("Environment user of %s:%d has a wrong "
262 "UseListNode index.",
263 instruction->DebugName(),
264 instruction->GetId()));
265 }
Roland Levillain6b469232014-09-25 10:10:38 +0100266 }
David Brazdil1abb4192015-02-17 18:33:36 +0000267
268 // Ensure 'instruction' has pointers to its inputs' use entries.
269 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
270 HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i);
271 HInstruction* input = input_record.GetInstruction();
272 HUseListNode<HInstruction*>* use_node = input_record.GetUseNode();
Nicolas Geoffray5d7b7f82015-04-28 00:52:43 +0100273 size_t use_index = use_node->GetIndex();
274 if ((use_node == nullptr)
275 || !input->GetUses().Contains(use_node)
276 || (use_index >= e)
277 || (use_index != i)) {
David Brazdil1abb4192015-02-17 18:33:36 +0000278 AddError(StringPrintf("Instruction %s:%d has an invalid pointer to use entry "
279 "at input %u (%s:%d).",
280 instruction->DebugName(),
281 instruction->GetId(),
282 static_cast<unsigned>(i),
283 input->DebugName(),
284 input->GetId()));
285 }
286 }
Roland Levillainccc07a92014-09-16 14:48:16 +0100287}
288
Roland Levillain4c0eb422015-04-24 16:43:49 +0100289void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
290 VisitInstruction(invoke);
291
292 if (invoke->IsStaticWithExplicitClinitCheck()) {
293 size_t last_input_index = invoke->InputCount() - 1;
294 HInstruction* last_input = invoke->InputAt(last_input_index);
295 if (last_input == nullptr) {
296 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
297 "has a null pointer as last input.",
298 invoke->DebugName(),
299 invoke->GetId()));
300 }
301 if (!last_input->IsClinitCheck() && !last_input->IsLoadClass()) {
302 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check "
303 "has a last instruction (%s:%d) which is neither a clinit check "
304 "nor a load class instruction.",
305 invoke->DebugName(),
306 invoke->GetId(),
307 last_input->DebugName(),
308 last_input->GetId()));
309 }
310 }
311}
312
David Brazdilfc6a86a2015-06-26 10:33:45 +0000313void GraphChecker::VisitReturn(HReturn* ret) {
Nicolas Geoffrayf9a19952015-06-29 13:43:54 +0100314 VisitInstruction(ret);
David Brazdilfc6a86a2015-06-26 10:33:45 +0000315 if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
316 AddError(StringPrintf("%s:%d does not jump to the exit block.",
317 ret->DebugName(),
318 ret->GetId()));
319 }
320}
321
322void GraphChecker::VisitReturnVoid(HReturnVoid* ret) {
Nicolas Geoffrayf9a19952015-06-29 13:43:54 +0100323 VisitInstruction(ret);
David Brazdilfc6a86a2015-06-26 10:33:45 +0000324 if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
325 AddError(StringPrintf("%s:%d does not jump to the exit block.",
326 ret->DebugName(),
327 ret->GetId()));
328 }
329}
330
Nicolas Geoffrayf9a19952015-06-29 13:43:54 +0100331void GraphChecker::VisitCheckCast(HCheckCast* check) {
332 VisitInstruction(check);
333 HInstruction* input = check->InputAt(1);
334 if (!input->IsLoadClass()) {
335 AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
336 check->DebugName(),
337 check->GetId(),
338 input->DebugName(),
339 input->GetId()));
340 }
341}
342
343void GraphChecker::VisitInstanceOf(HInstanceOf* instruction) {
344 VisitInstruction(instruction);
345 HInstruction* input = instruction->InputAt(1);
346 if (!input->IsLoadClass()) {
347 AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.",
348 instruction->DebugName(),
349 instruction->GetId(),
350 input->DebugName(),
351 input->GetId()));
352 }
353}
354
Roland Levillainccc07a92014-09-16 14:48:16 +0100355void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
356 super_type::VisitBasicBlock(block);
357
David Brazdilffee3d32015-07-06 11:48:53 +0100358 // Ensure that catch blocks are not normal successors, and normal blocks are
359 // never exceptional successors.
360 const size_t num_normal_successors = block->NumberOfNormalSuccessors();
361 for (size_t j = 0; j < num_normal_successors; ++j) {
362 HBasicBlock* successor = block->GetSuccessors().Get(j);
363 if (successor->IsCatchBlock()) {
364 AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
365 successor->GetBlockId(),
366 block->GetBlockId()));
367 }
368 }
369 for (size_t j = num_normal_successors, e = block->GetSuccessors().Size(); j < e; ++j) {
370 HBasicBlock* successor = block->GetSuccessors().Get(j);
371 if (!successor->IsCatchBlock()) {
372 AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
373 successor->GetBlockId(),
374 block->GetBlockId()));
375 }
376 }
377
Roland Levillainccc07a92014-09-16 14:48:16 +0100378 // Ensure there is no critical edge (i.e., an edge connecting a
379 // block with multiple successors to a block with multiple
David Brazdilffee3d32015-07-06 11:48:53 +0100380 // predecessors). Exceptional edges are synthesized and hence
381 // not accounted for.
382 if (block->NumberOfNormalSuccessors() > 1) {
383 for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) {
Roland Levillainccc07a92014-09-16 14:48:16 +0100384 HBasicBlock* successor = block->GetSuccessors().Get(j);
385 if (successor->GetPredecessors().Size() > 1) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000386 AddError(StringPrintf("Critical edge between blocks %d and %d.",
387 block->GetBlockId(),
388 successor->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100389 }
390 }
391 }
Roland Levillain6b879dd2014-09-22 17:13:44 +0100392
Calin Juravle1d8b49f2015-05-12 12:40:07 +0000393 // Check Phi uniqueness (no two Phis with the same type refer to the same register).
Calin Juravlea4f88312015-04-16 12:57:19 +0100394 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
395 HPhi* phi = it.Current()->AsPhi();
396 if (phi->GetNextEquivalentPhiWithSameType() != nullptr) {
397 std::stringstream type_str;
398 type_str << phi->GetType();
399 AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s",
400 phi->GetId(), phi->GetRegNumber(), type_str.str().c_str()));
401 }
402 }
403
David Brazdilffee3d32015-07-06 11:48:53 +0100404 // Ensure try membership information is consistent.
David Brazdilffee3d32015-07-06 11:48:53 +0100405 if (block->IsCatchBlock()) {
David Brazdilec16f792015-08-19 15:04:01 +0100406 if (block->IsTryBlock()) {
407 const HTryBoundary& try_entry = block->GetTryCatchInformation()->GetTryEntry();
David Brazdilffee3d32015-07-06 11:48:53 +0100408 AddError(StringPrintf("Catch blocks should not be try blocks but catch block %d "
409 "has try entry %s:%d.",
410 block->GetBlockId(),
David Brazdilec16f792015-08-19 15:04:01 +0100411 try_entry.DebugName(),
412 try_entry.GetId()));
David Brazdilffee3d32015-07-06 11:48:53 +0100413 }
414
415 if (block->IsLoopHeader()) {
416 AddError(StringPrintf("Catch blocks should not be loop headers but catch block %d is.",
417 block->GetBlockId()));
418 }
419 } else {
420 for (size_t i = 0; i < block->GetPredecessors().Size(); ++i) {
421 HBasicBlock* predecessor = block->GetPredecessors().Get(i);
David Brazdilec16f792015-08-19 15:04:01 +0100422 const HTryBoundary* incoming_try_entry = predecessor->ComputeTryEntryOfSuccessors();
423 if (block->IsTryBlock()) {
424 const HTryBoundary& stored_try_entry = block->GetTryCatchInformation()->GetTryEntry();
425 if (incoming_try_entry == nullptr) {
426 AddError(StringPrintf("Block %d has try entry %s:%d but no try entry follows "
David Brazdilffee3d32015-07-06 11:48:53 +0100427 "from predecessor %d.",
428 block->GetBlockId(),
David Brazdilec16f792015-08-19 15:04:01 +0100429 stored_try_entry.DebugName(),
430 stored_try_entry.GetId(),
431 predecessor->GetBlockId()));
432 } else if (!incoming_try_entry->HasSameExceptionHandlersAs(stored_try_entry)) {
433 AddError(StringPrintf("Block %d has try entry %s:%d which is not consistent "
434 "with %s:%d that follows from predecessor %d.",
435 block->GetBlockId(),
436 stored_try_entry.DebugName(),
437 stored_try_entry.GetId(),
David Brazdilffee3d32015-07-06 11:48:53 +0100438 incoming_try_entry->DebugName(),
439 incoming_try_entry->GetId(),
440 predecessor->GetBlockId()));
441 }
David Brazdilec16f792015-08-19 15:04:01 +0100442 } else if (incoming_try_entry != nullptr) {
443 AddError(StringPrintf("Block %d is not a try block but try entry %s:%d follows "
David Brazdilffee3d32015-07-06 11:48:53 +0100444 "from predecessor %d.",
445 block->GetBlockId(),
David Brazdilffee3d32015-07-06 11:48:53 +0100446 incoming_try_entry->DebugName(),
447 incoming_try_entry->GetId(),
448 predecessor->GetBlockId()));
449 }
450 }
451 }
452
Roland Levillain6b879dd2014-09-22 17:13:44 +0100453 if (block->IsLoopHeader()) {
454 CheckLoop(block);
455 }
456}
457
458void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
459 int id = loop_header->GetBlockId();
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100460 HLoopInformation* loop_information = loop_header->GetLoopInformation();
Roland Levillain6b879dd2014-09-22 17:13:44 +0100461
462 // Ensure the pre-header block is first in the list of
463 // predecessors of a loop header.
464 if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000465 AddError(StringPrintf(
466 "Loop pre-header is not the first predecessor of the loop header %d.",
467 id));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100468 }
469
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100470 // Ensure the loop header has only one incoming branch and the remaining
471 // predecessors are back edges.
Roland Levillain5c4405e2015-01-21 11:39:58 +0000472 size_t num_preds = loop_header->GetPredecessors().Size();
473 if (num_preds < 2) {
474 AddError(StringPrintf(
475 "Loop header %d has less than two predecessors: %zu.",
476 id,
477 num_preds));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100478 } else {
Roland Levillain6b879dd2014-09-22 17:13:44 +0100479 HBasicBlock* first_predecessor = loop_header->GetPredecessors().Get(0);
David Brazdil46e2a392015-03-16 17:31:52 +0000480 if (loop_information->IsBackEdge(*first_predecessor)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000481 AddError(StringPrintf(
482 "First predecessor of loop header %d is a back edge.",
483 id));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100484 }
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100485 for (size_t i = 1, e = loop_header->GetPredecessors().Size(); i < e; ++i) {
486 HBasicBlock* predecessor = loop_header->GetPredecessors().Get(i);
487 if (!loop_information->IsBackEdge(*predecessor)) {
488 AddError(StringPrintf(
489 "Loop header %d has multiple incoming (non back edge) blocks.",
490 id));
491 }
Roland Levillain6b879dd2014-09-22 17:13:44 +0100492 }
493 }
494
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100495 const ArenaBitVector& loop_blocks = loop_information->GetBlocks();
David Brazdil2d7352b2015-04-20 14:52:42 +0100496
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100497 // Ensure back edges belong to the loop.
498 size_t num_back_edges = loop_information->GetBackEdges().Size();
Roland Levillain5c4405e2015-01-21 11:39:58 +0000499 if (num_back_edges == 0) {
500 AddError(StringPrintf(
501 "Loop defined by header %d has no back edge.",
502 id));
David Brazdil2d7352b2015-04-20 14:52:42 +0100503 } else {
Nicolas Geoffraydb216f42015-05-05 17:02:20 +0100504 for (size_t i = 0; i < num_back_edges; ++i) {
505 int back_edge_id = loop_information->GetBackEdges().Get(i)->GetBlockId();
506 if (!loop_blocks.IsBitSet(back_edge_id)) {
507 AddError(StringPrintf(
508 "Loop defined by header %d has an invalid back edge %d.",
509 id,
510 back_edge_id));
511 }
David Brazdil2d7352b2015-04-20 14:52:42 +0100512 }
Roland Levillain6b879dd2014-09-22 17:13:44 +0100513 }
Roland Levillain7e53b412014-09-23 10:50:22 +0100514
David Brazdil2d7352b2015-04-20 14:52:42 +0100515 // Ensure all blocks in the loop are live and dominated by the loop header.
Roland Levillain7e53b412014-09-23 10:50:22 +0100516 for (uint32_t i : loop_blocks.Indexes()) {
517 HBasicBlock* loop_block = GetGraph()->GetBlocks().Get(i);
David Brazdil2d7352b2015-04-20 14:52:42 +0100518 if (loop_block == nullptr) {
519 AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
520 id,
521 i));
522 } else if (!loop_header->Dominates(loop_block)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000523 AddError(StringPrintf("Loop block %d not dominated by loop header %d.",
David Brazdil2d7352b2015-04-20 14:52:42 +0100524 i,
Roland Levillain5c4405e2015-01-21 11:39:58 +0000525 id));
Roland Levillain7e53b412014-09-23 10:50:22 +0100526 }
527 }
David Brazdil7d275372015-04-21 16:36:35 +0100528
529 // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
530 for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
531 HLoopInformation* outer_info = it.Current();
532 if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) {
533 AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of "
534 "an outer loop defined by header %d.",
David Brazdil2d7352b2015-04-20 14:52:42 +0100535 id,
David Brazdil7d275372015-04-21 16:36:35 +0100536 outer_info->GetHeader()->GetBlockId()));
537 }
538 }
Roland Levillainccc07a92014-09-16 14:48:16 +0100539}
540
541void SSAChecker::VisitInstruction(HInstruction* instruction) {
542 super_type::VisitInstruction(instruction);
543
Roland Levillaina8069ce2014-10-01 10:48:29 +0100544 // Ensure an instruction dominates all its uses.
David Brazdiled596192015-01-23 10:39:45 +0000545 for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
Roland Levillaina8069ce2014-10-01 10:48:29 +0100546 !use_it.Done(); use_it.Advance()) {
547 HInstruction* use = use_it.Current()->GetUser();
Roland Levillain6c82d402014-10-13 16:10:27 +0100548 if (!use->IsPhi() && !instruction->StrictlyDominates(use)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000549 AddError(StringPrintf("Instruction %d in block %d does not dominate "
550 "use %d in block %d.",
551 instruction->GetId(), current_block_->GetBlockId(),
552 use->GetId(), use->GetBlock()->GetBlockId()));
Roland Levillainccc07a92014-09-16 14:48:16 +0100553 }
554 }
Roland Levillaina8069ce2014-10-01 10:48:29 +0100555
556 // Ensure an instruction having an environment is dominated by the
557 // instructions contained in the environment.
Nicolas Geoffray0a23d742015-05-07 11:57:35 +0100558 for (HEnvironment* environment = instruction->GetEnvironment();
559 environment != nullptr;
560 environment = environment->GetParent()) {
Roland Levillaina8069ce2014-10-01 10:48:29 +0100561 for (size_t i = 0, e = environment->Size(); i < e; ++i) {
562 HInstruction* env_instruction = environment->GetInstructionAt(i);
563 if (env_instruction != nullptr
Roland Levillain6c82d402014-10-13 16:10:27 +0100564 && !env_instruction->StrictlyDominates(instruction)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000565 AddError(StringPrintf("Instruction %d in environment of instruction %d "
566 "from block %d does not dominate instruction %d.",
567 env_instruction->GetId(),
568 instruction->GetId(),
569 current_block_->GetBlockId(),
570 instruction->GetId()));
Roland Levillaina8069ce2014-10-01 10:48:29 +0100571 }
572 }
573 }
Roland Levillainccc07a92014-09-16 14:48:16 +0100574}
575
Nicolas Geoffrayd6138ef2015-02-18 14:48:53 +0000576static Primitive::Type PrimitiveKind(Primitive::Type type) {
577 switch (type) {
578 case Primitive::kPrimBoolean:
579 case Primitive::kPrimByte:
580 case Primitive::kPrimShort:
581 case Primitive::kPrimChar:
582 case Primitive::kPrimInt:
583 return Primitive::kPrimInt;
584 default:
585 return type;
586 }
587}
588
Roland Levillain6b879dd2014-09-22 17:13:44 +0100589void SSAChecker::VisitPhi(HPhi* phi) {
590 VisitInstruction(phi);
591
592 // Ensure the first input of a phi is not itself.
593 if (phi->InputAt(0) == phi) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000594 AddError(StringPrintf("Loop phi %d in block %d is its own first input.",
595 phi->GetId(),
596 phi->GetBlock()->GetBlockId()));
Roland Levillain6b879dd2014-09-22 17:13:44 +0100597 }
598
Nicolas Geoffrayd6138ef2015-02-18 14:48:53 +0000599 // Ensure that the inputs have the same primitive kind as the phi.
600 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
601 HInstruction* input = phi->InputAt(i);
602 if (PrimitiveKind(input->GetType()) != PrimitiveKind(phi->GetType())) {
603 AddError(StringPrintf(
604 "Input %d at index %zu of phi %d from block %d does not have the "
605 "same type as the phi: %s versus %s",
606 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
607 Primitive::PrettyDescriptor(input->GetType()),
608 Primitive::PrettyDescriptor(phi->GetType())));
609 }
Nicolas Geoffray31596742014-11-24 15:28:45 +0000610 }
Nicolas Geoffraye0fe7ae2015-03-09 10:02:49 +0000611 if (phi->GetType() != HPhi::ToPhiType(phi->GetType())) {
612 AddError(StringPrintf("Phi %d in block %d does not have an expected phi type: %s",
613 phi->GetId(),
614 phi->GetBlock()->GetBlockId(),
615 Primitive::PrettyDescriptor(phi->GetType())));
616 }
David Brazdilffee3d32015-07-06 11:48:53 +0100617
618 if (phi->IsCatchPhi()) {
619 // The number of inputs of a catch phi corresponds to the total number of
620 // throwing instructions caught by this catch block.
621 } else {
622 // Ensure the number of inputs of a non-catch phi is the same as the number
623 // of its predecessors.
624 const GrowableArray<HBasicBlock*>& predecessors =
David Brazdilb618ade2015-07-29 10:31:29 +0100625 phi->GetBlock()->GetPredecessors();
David Brazdilffee3d32015-07-06 11:48:53 +0100626 if (phi->InputCount() != predecessors.Size()) {
627 AddError(StringPrintf(
628 "Phi %d in block %d has %zu inputs, "
629 "but block %d has %zu predecessors.",
630 phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(),
631 phi->GetBlock()->GetBlockId(), predecessors.Size()));
632 } else {
633 // Ensure phi input at index I either comes from the Ith
634 // predecessor or from a block that dominates this predecessor.
635 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
636 HInstruction* input = phi->InputAt(i);
637 HBasicBlock* predecessor = predecessors.Get(i);
638 if (!(input->GetBlock() == predecessor
639 || input->GetBlock()->Dominates(predecessor))) {
640 AddError(StringPrintf(
641 "Input %d at index %zu of phi %d from block %d is not defined in "
642 "predecessor number %zu nor in a block dominating it.",
643 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
644 i));
645 }
646 }
647 }
648 }
Nicolas Geoffray31596742014-11-24 15:28:45 +0000649}
650
David Brazdil13b47182015-04-15 16:29:32 +0100651void SSAChecker::HandleBooleanInput(HInstruction* instruction, size_t input_index) {
652 HInstruction* input = instruction->InputAt(input_index);
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000653 if (input->IsIntConstant()) {
David Brazdil13b47182015-04-15 16:29:32 +0100654 int32_t value = input->AsIntConstant()->GetValue();
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000655 if (value != 0 && value != 1) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000656 AddError(StringPrintf(
David Brazdil13b47182015-04-15 16:29:32 +0100657 "%s instruction %d has a non-Boolean constant input %d whose value is: %d.",
658 instruction->DebugName(),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000659 instruction->GetId(),
David Brazdil13b47182015-04-15 16:29:32 +0100660 static_cast<int>(input_index),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000661 value));
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000662 }
David Brazdil2fa194b2015-04-20 10:14:42 +0100663 } else if (input->GetType() == Primitive::kPrimInt
664 && (input->IsPhi() || input->IsAnd() || input->IsOr() || input->IsXor())) {
665 // TODO: We need a data-flow analysis to determine if the Phi or
666 // binary operation is actually Boolean. Allow for now.
David Brazdil13b47182015-04-15 16:29:32 +0100667 } else if (input->GetType() != Primitive::kPrimBoolean) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000668 AddError(StringPrintf(
David Brazdil13b47182015-04-15 16:29:32 +0100669 "%s instruction %d has a non-Boolean input %d whose type is: %s.",
670 instruction->DebugName(),
Roland Levillain5c4405e2015-01-21 11:39:58 +0000671 instruction->GetId(),
David Brazdil13b47182015-04-15 16:29:32 +0100672 static_cast<int>(input_index),
673 Primitive::PrettyDescriptor(input->GetType())));
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000674 }
675}
676
David Brazdil13b47182015-04-15 16:29:32 +0100677void SSAChecker::VisitIf(HIf* instruction) {
678 VisitInstruction(instruction);
679 HandleBooleanInput(instruction, 0);
680}
681
682void SSAChecker::VisitBooleanNot(HBooleanNot* instruction) {
683 VisitInstruction(instruction);
684 HandleBooleanInput(instruction, 0);
685}
686
Nicolas Geoffray31596742014-11-24 15:28:45 +0000687void SSAChecker::VisitCondition(HCondition* op) {
688 VisitInstruction(op);
Nicolas Geoffray31596742014-11-24 15:28:45 +0000689 if (op->GetType() != Primitive::kPrimBoolean) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000690 AddError(StringPrintf(
691 "Condition %s %d has a non-Boolean result type: %s.",
692 op->DebugName(), op->GetId(),
693 Primitive::PrettyDescriptor(op->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000694 }
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000695 HInstruction* lhs = op->InputAt(0);
696 HInstruction* rhs = op->InputAt(1);
Calin Juravlea4f88312015-04-16 12:57:19 +0100697 if (PrimitiveKind(lhs->GetType()) != PrimitiveKind(rhs->GetType())) {
698 AddError(StringPrintf(
699 "Condition %s %d has inputs of different types: %s, and %s.",
700 op->DebugName(), op->GetId(),
701 Primitive::PrettyDescriptor(lhs->GetType()),
702 Primitive::PrettyDescriptor(rhs->GetType())));
703 }
704 if (!op->IsEqual() && !op->IsNotEqual()) {
705 if ((lhs->GetType() == Primitive::kPrimNot)) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000706 AddError(StringPrintf(
707 "Condition %s %d uses an object as left-hand side input.",
708 op->DebugName(), op->GetId()));
Calin Juravlea4f88312015-04-16 12:57:19 +0100709 } else if (rhs->GetType() == Primitive::kPrimNot) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000710 AddError(StringPrintf(
711 "Condition %s %d uses an object as right-hand side input.",
712 op->DebugName(), op->GetId()));
Roland Levillainaecbd262015-01-19 12:44:01 +0000713 }
Nicolas Geoffray9ee66182015-01-16 12:35:40 +0000714 }
Nicolas Geoffray31596742014-11-24 15:28:45 +0000715}
716
717void SSAChecker::VisitBinaryOperation(HBinaryOperation* op) {
718 VisitInstruction(op);
719 if (op->IsUShr() || op->IsShr() || op->IsShl()) {
720 if (PrimitiveKind(op->InputAt(1)->GetType()) != Primitive::kPrimInt) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000721 AddError(StringPrintf(
722 "Shift operation %s %d has a non-int kind second input: "
723 "%s of type %s.",
724 op->DebugName(), op->GetId(),
725 op->InputAt(1)->DebugName(),
726 Primitive::PrettyDescriptor(op->InputAt(1)->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000727 }
728 } else {
Roland Levillain4c0eb422015-04-24 16:43:49 +0100729 if (PrimitiveKind(op->InputAt(0)->GetType()) != PrimitiveKind(op->InputAt(1)->GetType())) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000730 AddError(StringPrintf(
731 "Binary operation %s %d has inputs of different types: "
732 "%s, and %s.",
733 op->DebugName(), op->GetId(),
734 Primitive::PrettyDescriptor(op->InputAt(0)->GetType()),
735 Primitive::PrettyDescriptor(op->InputAt(1)->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000736 }
737 }
738
739 if (op->IsCompare()) {
740 if (op->GetType() != Primitive::kPrimInt) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000741 AddError(StringPrintf(
742 "Compare operation %d has a non-int result type: %s.",
743 op->GetId(),
744 Primitive::PrettyDescriptor(op->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000745 }
746 } else {
747 // Use the first input, so that we can also make this check for shift operations.
748 if (PrimitiveKind(op->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) {
Roland Levillain5c4405e2015-01-21 11:39:58 +0000749 AddError(StringPrintf(
750 "Binary operation %s %d has a result type different "
751 "from its input type: %s vs %s.",
752 op->DebugName(), op->GetId(),
753 Primitive::PrettyDescriptor(op->GetType()),
Roland Levillain4c0eb422015-04-24 16:43:49 +0100754 Primitive::PrettyDescriptor(op->InputAt(0)->GetType())));
Nicolas Geoffray31596742014-11-24 15:28:45 +0000755 }
756 }
757}
758
David Brazdil8d5b8b22015-03-24 10:51:52 +0000759void SSAChecker::VisitConstant(HConstant* instruction) {
760 HBasicBlock* block = instruction->GetBlock();
761 if (!block->IsEntryBlock()) {
762 AddError(StringPrintf(
763 "%s %d should be in the entry block but is in block %d.",
764 instruction->DebugName(),
765 instruction->GetId(),
766 block->GetBlockId()));
767 }
768}
769
Roland Levillainccc07a92014-09-16 14:48:16 +0100770} // namespace art