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