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