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