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 19 #include <algorithm> 20 #include <string> 21 #include <sstream> 22 23 #include "base/arena_containers.h" 24 #include "base/bit_vector-inl.h" 25 #include "base/stringprintf.h" 26 #include "handle_scope-inl.h" 27 28 namespace art { 29 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 45 void GraphChecker::VisitBasicBlock(HBasicBlock* block) { 46 current_block_ = block; 47 48 // Check consistency with respect to predecessors of `block`. 49 // Note: Counting duplicates with a sorted vector uses up to 6x less memory 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()); 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; 59 } 60 size_t block_count_in_p_successors = 61 std::count(p->GetSuccessors().begin(), p->GetSuccessors().end(), block); 62 if (p_count_in_block_predecessors != block_count_in_p_successors) { 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())); 68 } 69 } 70 71 // Check consistency with respect to successors of `block`. 72 // Note: Counting duplicates with a sorted vector uses up to 6x less memory 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()); 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; 82 } 83 size_t block_count_in_s_predecessors = 84 std::count(s->GetPredecessors().begin(), s->GetPredecessors().end(), block); 85 if (s_count_in_block_successors != block_count_in_s_predecessors) { 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())); 91 } 92 } 93 94 // Ensure `block` ends with a branch instruction. 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()) { 99 AddError(StringPrintf("Block %d does not end with a branch instruction.", 100 block->GetBlockId())); 101 } 102 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. 105 if (block->IsExitBlock()) { 106 for (HBasicBlock* predecessor : block->GetPredecessors()) { 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())); 114 } 115 } 116 } 117 118 // Visit this block's list of phis. 119 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 120 HInstruction* current = it.Current(); 121 // Ensure this block's list of phis contains only phis. 122 if (!current->IsPhi()) { 123 AddError(StringPrintf("Block %d has a non-phi in its phi list.", 124 current_block_->GetBlockId())); 125 } 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); 133 } 134 135 // Visit this block's list of instructions. 136 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 137 HInstruction* current = it.Current(); 138 // Ensure this block's list of instructions does not contains phis. 139 if (current->IsPhi()) { 140 AddError(StringPrintf("Block %d has a phi in its non-phi list.", 141 current_block_->GetBlockId())); 142 } 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); 150 } 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) { 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 } 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 } 247 } 248 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 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 270 void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) { 271 ArrayRef<HBasicBlock* const> handlers = try_boundary->GetExceptionHandlers(); 272 273 // Ensure that all exception handlers are catch blocks. 274 // Note that a normal-flow successor may be a catch block before CFG 275 // simplification. We only test normal-flow successors in GraphChecker. 276 for (HBasicBlock* handler : handlers) { 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 } 285 } 286 287 // Ensure that handlers are not listed multiple times. 288 for (size_t i = 0, e = handlers.size(); i < e; ++i) { 289 if (ContainsElement(handlers, handlers[i], i + 1)) { 290 AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.", 291 handlers[i]->GetBlockId(), 292 try_boundary->DebugName(), 293 try_boundary->GetId())); 294 } 295 } 296 297 VisitInstruction(try_boundary); 298 } 299 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 315 void GraphChecker::VisitInstruction(HInstruction* instruction) { 316 if (seen_ids_.IsBitSet(instruction->GetId())) { 317 AddError(StringPrintf("Instruction id %d is duplicate in graph.", 318 instruction->GetId())); 319 } else { 320 seen_ids_.SetBit(instruction->GetId()); 321 } 322 323 // Ensure `instruction` is associated with `current_block_`. 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())); 335 } 336 337 // Ensure the inputs of `instruction` are defined in a block of the graph. 338 for (HInputIterator input_it(instruction); !input_it.Done(); 339 input_it.Advance()) { 340 HInstruction* input = input_it.Current(); 341 const HInstructionList& list = input->IsPhi() 342 ? input->GetBlock()->GetPhis() 343 : input->GetBlock()->GetInstructions(); 344 if (!list.Contains(input)) { 345 AddError(StringPrintf("Input %d of instruction %d is not defined " 346 "in a basic block of the control-flow graph.", 347 input->GetId(), 348 instruction->GetId())); 349 } 350 } 351 352 // Ensure the uses of `instruction` are defined in a block of the graph, 353 // and the entry in the use list is consistent. 354 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 355 HInstruction* user = use.GetUser(); 356 const HInstructionList& list = user->IsPhi() 357 ? user->GetBlock()->GetPhis() 358 : user->GetBlock()->GetInstructions(); 359 if (!list.Contains(user)) { 360 AddError(StringPrintf("User %s:%d of instruction %d is not defined " 361 "in a basic block of the control-flow graph.", 362 user->DebugName(), 363 user->GetId(), 364 instruction->GetId())); 365 } 366 size_t use_index = use.GetIndex(); 367 if ((use_index >= user->InputCount()) || (user->InputAt(use_index) != instruction)) { 368 AddError(StringPrintf("User %s:%d of instruction %s:%d has a wrong " 369 "UseListNode index.", 370 user->DebugName(), 371 user->GetId(), 372 instruction->DebugName(), 373 instruction->GetId())); 374 } 375 } 376 377 // Ensure the environment uses entries are consistent. 378 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 379 HEnvironment* user = use.GetUser(); 380 size_t use_index = use.GetIndex(); 381 if ((use_index >= user->Size()) || (user->GetInstructionAt(use_index) != instruction)) { 382 AddError(StringPrintf("Environment user of %s:%d has a wrong " 383 "UseListNode index.", 384 instruction->DebugName(), 385 instruction->GetId())); 386 } 387 } 388 389 // Ensure 'instruction' has pointers to its inputs' use entries. 390 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { 391 HUserRecord<HInstruction*> input_record = instruction->InputRecordAt(i); 392 HInstruction* input = input_record.GetInstruction(); 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 " 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 } 406 407 // Ensure an instruction dominates all its uses. 408 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 409 HInstruction* user = use.GetUser(); 410 if (!user->IsPhi() && !instruction->StrictlyDominates(user)) { 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(), 416 user->DebugName(), 417 user->GetId(), 418 user->GetBlock()->GetBlockId())); 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 } 487 } 488 489 void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { 490 VisitInstruction(invoke); 491 492 if (invoke->IsStaticWithExplicitClinitCheck()) { 493 size_t last_input_index = invoke->InputCount() - 1; 494 HInstruction* last_input = invoke->InputAt(last_input_index); 495 if (last_input == nullptr) { 496 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check " 497 "has a null pointer as last input.", 498 invoke->DebugName(), 499 invoke->GetId())); 500 } 501 if (!last_input->IsClinitCheck() && !last_input->IsLoadClass()) { 502 AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check " 503 "has a last instruction (%s:%d) which is neither a clinit check " 504 "nor a load class instruction.", 505 invoke->DebugName(), 506 invoke->GetId(), 507 last_input->DebugName(), 508 last_input->GetId())); 509 } 510 } 511 } 512 513 void GraphChecker::VisitReturn(HReturn* ret) { 514 VisitInstruction(ret); 515 HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor(); 516 if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) { 517 AddError(StringPrintf("%s:%d does not jump to the exit block.", 518 ret->DebugName(), 519 ret->GetId())); 520 } 521 } 522 523 void GraphChecker::VisitReturnVoid(HReturnVoid* ret) { 524 VisitInstruction(ret); 525 HBasicBlock* successor = ret->GetBlock()->GetSingleSuccessor(); 526 if (!successor->IsExitBlock() && !IsExitTryBoundaryIntoExitBlock(successor)) { 527 AddError(StringPrintf("%s:%d does not jump to the exit block.", 528 ret->DebugName(), 529 ret->GetId())); 530 } 531 } 532 533 void GraphChecker::VisitCheckCast(HCheckCast* check) { 534 VisitInstruction(check); 535 HInstruction* input = check->InputAt(1); 536 if (!input->IsLoadClass()) { 537 AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.", 538 check->DebugName(), 539 check->GetId(), 540 input->DebugName(), 541 input->GetId())); 542 } 543 } 544 545 void GraphChecker::VisitInstanceOf(HInstanceOf* instruction) { 546 VisitInstruction(instruction); 547 HInstruction* input = instruction->InputAt(1); 548 if (!input->IsLoadClass()) { 549 AddError(StringPrintf("%s:%d expects a HLoadClass as second input, not %s:%d.", 550 instruction->DebugName(), 551 instruction->GetId(), 552 input->DebugName(), 553 input->GetId())); 554 } 555 } 556 557 void GraphChecker::HandleLoop(HBasicBlock* loop_header) { 558 int id = loop_header->GetBlockId(); 559 HLoopInformation* loop_information = loop_header->GetLoopInformation(); 560 561 if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) { 562 AddError(StringPrintf( 563 "Loop pre-header %d of loop defined by header %d has %zu successors.", 564 loop_information->GetPreHeader()->GetBlockId(), 565 id, 566 loop_information->GetPreHeader()->GetSuccessors().size())); 567 } 568 569 if (loop_information->GetSuspendCheck() == nullptr) { 570 AddError(StringPrintf( 571 "Loop with header %d does not have a suspend check.", 572 loop_header->GetBlockId())); 573 } 574 575 if (loop_information->GetSuspendCheck() != loop_header->GetFirstInstructionDisregardMoves()) { 576 AddError(StringPrintf( 577 "Loop header %d does not have the loop suspend check as the first instruction.", 578 loop_header->GetBlockId())); 579 } 580 581 // Ensure the loop header has only one incoming branch and the remaining 582 // predecessors are back edges. 583 size_t num_preds = loop_header->GetPredecessors().size(); 584 if (num_preds < 2) { 585 AddError(StringPrintf( 586 "Loop header %d has less than two predecessors: %zu.", 587 id, 588 num_preds)); 589 } else { 590 HBasicBlock* first_predecessor = loop_header->GetPredecessors()[0]; 591 if (loop_information->IsBackEdge(*first_predecessor)) { 592 AddError(StringPrintf( 593 "First predecessor of loop header %d is a back edge.", 594 id)); 595 } 596 for (size_t i = 1, e = loop_header->GetPredecessors().size(); i < e; ++i) { 597 HBasicBlock* predecessor = loop_header->GetPredecessors()[i]; 598 if (!loop_information->IsBackEdge(*predecessor)) { 599 AddError(StringPrintf( 600 "Loop header %d has multiple incoming (non back edge) blocks: %d.", 601 id, 602 predecessor->GetBlockId())); 603 } 604 } 605 } 606 607 const ArenaBitVector& loop_blocks = loop_information->GetBlocks(); 608 609 // Ensure back edges belong to the loop. 610 if (loop_information->NumberOfBackEdges() == 0) { 611 AddError(StringPrintf( 612 "Loop defined by header %d has no back edge.", 613 id)); 614 } else { 615 for (HBasicBlock* back_edge : loop_information->GetBackEdges()) { 616 int back_edge_id = back_edge->GetBlockId(); 617 if (!loop_blocks.IsBitSet(back_edge_id)) { 618 AddError(StringPrintf( 619 "Loop defined by header %d has an invalid back edge %d.", 620 id, 621 back_edge_id)); 622 } else if (back_edge->GetLoopInformation() != loop_information) { 623 AddError(StringPrintf( 624 "Back edge %d of loop defined by header %d belongs to nested loop " 625 "with header %d.", 626 back_edge_id, 627 id, 628 back_edge->GetLoopInformation()->GetHeader()->GetBlockId())); 629 } 630 } 631 } 632 633 // If this is a nested loop, ensure the outer loops contain a superset of the blocks. 634 for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) { 635 HLoopInformation* outer_info = it.Current(); 636 if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) { 637 AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of " 638 "an outer loop defined by header %d.", 639 id, 640 outer_info->GetHeader()->GetBlockId())); 641 } 642 } 643 644 // Ensure the pre-header block is first in the list of predecessors of a loop 645 // header and that the header block is its only successor. 646 if (!loop_header->IsLoopPreHeaderFirstPredecessor()) { 647 AddError(StringPrintf( 648 "Loop pre-header is not the first predecessor of the loop header %d.", 649 id)); 650 } 651 652 // Ensure all blocks in the loop are live and dominated by the loop header in 653 // the case of natural loops. 654 for (uint32_t i : loop_blocks.Indexes()) { 655 HBasicBlock* loop_block = GetGraph()->GetBlocks()[i]; 656 if (loop_block == nullptr) { 657 AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.", 658 id, 659 i)); 660 } else if (!loop_information->IsIrreducible() && !loop_header->Dominates(loop_block)) { 661 AddError(StringPrintf("Loop block %d not dominated by loop header %d.", 662 i, 663 id)); 664 } 665 } 666 } 667 668 static bool IsSameSizeConstant(HInstruction* insn1, HInstruction* insn2) { 669 return insn1->IsConstant() 670 && insn2->IsConstant() 671 && Primitive::Is64BitType(insn1->GetType()) == Primitive::Is64BitType(insn2->GetType()); 672 } 673 674 static bool IsConstantEquivalent(HInstruction* insn1, HInstruction* insn2, BitVector* visited) { 675 if (insn1->IsPhi() && 676 insn1->AsPhi()->IsVRegEquivalentOf(insn2) && 677 insn1->InputCount() == insn2->InputCount()) { 678 // Testing only one of the two inputs for recursion is sufficient. 679 if (visited->IsBitSet(insn1->GetId())) { 680 return true; 681 } 682 visited->SetBit(insn1->GetId()); 683 684 for (size_t i = 0, e = insn1->InputCount(); i < e; ++i) { 685 if (!IsConstantEquivalent(insn1->InputAt(i), insn2->InputAt(i), visited)) { 686 return false; 687 } 688 } 689 return true; 690 } else if (IsSameSizeConstant(insn1, insn2)) { 691 return insn1->AsConstant()->GetValueAsUint64() == insn2->AsConstant()->GetValueAsUint64(); 692 } else { 693 return false; 694 } 695 } 696 697 void GraphChecker::VisitPhi(HPhi* phi) { 698 VisitInstruction(phi); 699 700 // Ensure the first input of a phi is not itself. 701 if (phi->InputAt(0) == phi) { 702 AddError(StringPrintf("Loop phi %d in block %d is its own first input.", 703 phi->GetId(), 704 phi->GetBlock()->GetBlockId())); 705 } 706 707 // Ensure that the inputs have the same primitive kind as the phi. 708 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 709 HInstruction* input = phi->InputAt(i); 710 if (Primitive::PrimitiveKind(input->GetType()) != Primitive::PrimitiveKind(phi->GetType())) { 711 AddError(StringPrintf( 712 "Input %d at index %zu of phi %d from block %d does not have the " 713 "same kind as the phi: %s versus %s", 714 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(), 715 Primitive::PrettyDescriptor(input->GetType()), 716 Primitive::PrettyDescriptor(phi->GetType()))); 717 } 718 } 719 if (phi->GetType() != HPhi::ToPhiType(phi->GetType())) { 720 AddError(StringPrintf("Phi %d in block %d does not have an expected phi type: %s", 721 phi->GetId(), 722 phi->GetBlock()->GetBlockId(), 723 Primitive::PrettyDescriptor(phi->GetType()))); 724 } 725 726 if (phi->IsCatchPhi()) { 727 // The number of inputs of a catch phi should be the total number of throwing 728 // instructions caught by this catch block. We do not enforce this, however, 729 // because we do not remove the corresponding inputs when we prove that an 730 // instruction cannot throw. Instead, we at least test that all phis have the 731 // same, non-zero number of inputs (b/24054676). 732 size_t input_count_this = phi->InputCount(); 733 if (input_count_this == 0u) { 734 AddError(StringPrintf("Phi %d in catch block %d has zero inputs.", 735 phi->GetId(), 736 phi->GetBlock()->GetBlockId())); 737 } else { 738 HInstruction* next_phi = phi->GetNext(); 739 if (next_phi != nullptr) { 740 size_t input_count_next = next_phi->InputCount(); 741 if (input_count_this != input_count_next) { 742 AddError(StringPrintf("Phi %d in catch block %d has %zu inputs, " 743 "but phi %d has %zu inputs.", 744 phi->GetId(), 745 phi->GetBlock()->GetBlockId(), 746 input_count_this, 747 next_phi->GetId(), 748 input_count_next)); 749 } 750 } 751 } 752 } else { 753 // Ensure the number of inputs of a non-catch phi is the same as the number 754 // of its predecessors. 755 const ArenaVector<HBasicBlock*>& predecessors = phi->GetBlock()->GetPredecessors(); 756 if (phi->InputCount() != predecessors.size()) { 757 AddError(StringPrintf( 758 "Phi %d in block %d has %zu inputs, " 759 "but block %d has %zu predecessors.", 760 phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(), 761 phi->GetBlock()->GetBlockId(), predecessors.size())); 762 } else { 763 // Ensure phi input at index I either comes from the Ith 764 // predecessor or from a block that dominates this predecessor. 765 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 766 HInstruction* input = phi->InputAt(i); 767 HBasicBlock* predecessor = predecessors[i]; 768 if (!(input->GetBlock() == predecessor 769 || input->GetBlock()->Dominates(predecessor))) { 770 AddError(StringPrintf( 771 "Input %d at index %zu of phi %d from block %d is not defined in " 772 "predecessor number %zu nor in a block dominating it.", 773 input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(), 774 i)); 775 } 776 } 777 } 778 } 779 780 // Ensure that catch phis are sorted by their vreg number, as required by 781 // the register allocator and code generator. This does not apply to normal 782 // phis which can be constructed artifically. 783 if (phi->IsCatchPhi()) { 784 HInstruction* next_phi = phi->GetNext(); 785 if (next_phi != nullptr && phi->GetRegNumber() > next_phi->AsPhi()->GetRegNumber()) { 786 AddError(StringPrintf("Catch phis %d and %d in block %d are not sorted by their " 787 "vreg numbers.", 788 phi->GetId(), 789 next_phi->GetId(), 790 phi->GetBlock()->GetBlockId())); 791 } 792 } 793 794 // Test phi equivalents. There should not be two of the same type and they should only be 795 // created for constants which were untyped in DEX. Note that this test can be skipped for 796 // a synthetic phi (indicated by lack of a virtual register). 797 if (phi->GetRegNumber() != kNoRegNumber) { 798 for (HInstructionIterator phi_it(phi->GetBlock()->GetPhis()); 799 !phi_it.Done(); 800 phi_it.Advance()) { 801 HPhi* other_phi = phi_it.Current()->AsPhi(); 802 if (phi != other_phi && phi->GetRegNumber() == other_phi->GetRegNumber()) { 803 if (phi->GetType() == other_phi->GetType()) { 804 std::stringstream type_str; 805 type_str << phi->GetType(); 806 AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s.", 807 phi->GetId(), 808 phi->GetRegNumber(), 809 type_str.str().c_str())); 810 } else if (phi->GetType() == Primitive::kPrimNot) { 811 std::stringstream type_str; 812 type_str << other_phi->GetType(); 813 AddError(StringPrintf( 814 "Equivalent non-reference phi (%d) found for VReg %d with type: %s.", 815 phi->GetId(), 816 phi->GetRegNumber(), 817 type_str.str().c_str())); 818 } else { 819 // If we get here, make sure we allocate all the necessary storage at once 820 // because the BitVector reallocation strategy has very bad worst-case behavior. 821 ArenaBitVector& visited = visited_storage_; 822 visited.SetBit(GetGraph()->GetCurrentInstructionId()); 823 visited.ClearAllBits(); 824 if (!IsConstantEquivalent(phi, other_phi, &visited)) { 825 AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they " 826 "are not equivalents of constants.", 827 phi->GetId(), 828 other_phi->GetId(), 829 phi->GetRegNumber())); 830 } 831 } 832 } 833 } 834 } 835 } 836 837 void GraphChecker::HandleBooleanInput(HInstruction* instruction, size_t input_index) { 838 HInstruction* input = instruction->InputAt(input_index); 839 if (input->IsIntConstant()) { 840 int32_t value = input->AsIntConstant()->GetValue(); 841 if (value != 0 && value != 1) { 842 AddError(StringPrintf( 843 "%s instruction %d has a non-Boolean constant input %d whose value is: %d.", 844 instruction->DebugName(), 845 instruction->GetId(), 846 static_cast<int>(input_index), 847 value)); 848 } 849 } else if (Primitive::PrimitiveKind(input->GetType()) != Primitive::kPrimInt) { 850 // TODO: We need a data-flow analysis to determine if an input like Phi, 851 // Select or a binary operation is actually Boolean. Allow for now. 852 AddError(StringPrintf( 853 "%s instruction %d has a non-integer input %d whose type is: %s.", 854 instruction->DebugName(), 855 instruction->GetId(), 856 static_cast<int>(input_index), 857 Primitive::PrettyDescriptor(input->GetType()))); 858 } 859 } 860 861 void GraphChecker::VisitPackedSwitch(HPackedSwitch* instruction) { 862 VisitInstruction(instruction); 863 // Check that the number of block successors matches the switch count plus 864 // one for the default block. 865 HBasicBlock* block = instruction->GetBlock(); 866 if (instruction->GetNumEntries() + 1u != block->GetSuccessors().size()) { 867 AddError(StringPrintf( 868 "%s instruction %d in block %d expects %u successors to the block, but found: %zu.", 869 instruction->DebugName(), 870 instruction->GetId(), 871 block->GetBlockId(), 872 instruction->GetNumEntries() + 1u, 873 block->GetSuccessors().size())); 874 } 875 } 876 877 void GraphChecker::VisitIf(HIf* instruction) { 878 VisitInstruction(instruction); 879 HandleBooleanInput(instruction, 0); 880 } 881 882 void GraphChecker::VisitSelect(HSelect* instruction) { 883 VisitInstruction(instruction); 884 HandleBooleanInput(instruction, 2); 885 } 886 887 void GraphChecker::VisitBooleanNot(HBooleanNot* instruction) { 888 VisitInstruction(instruction); 889 HandleBooleanInput(instruction, 0); 890 } 891 892 void GraphChecker::VisitCondition(HCondition* op) { 893 VisitInstruction(op); 894 if (op->GetType() != Primitive::kPrimBoolean) { 895 AddError(StringPrintf( 896 "Condition %s %d has a non-Boolean result type: %s.", 897 op->DebugName(), op->GetId(), 898 Primitive::PrettyDescriptor(op->GetType()))); 899 } 900 HInstruction* lhs = op->InputAt(0); 901 HInstruction* rhs = op->InputAt(1); 902 if (Primitive::PrimitiveKind(lhs->GetType()) != Primitive::PrimitiveKind(rhs->GetType())) { 903 AddError(StringPrintf( 904 "Condition %s %d has inputs of different kinds: %s, and %s.", 905 op->DebugName(), op->GetId(), 906 Primitive::PrettyDescriptor(lhs->GetType()), 907 Primitive::PrettyDescriptor(rhs->GetType()))); 908 } 909 if (!op->IsEqual() && !op->IsNotEqual()) { 910 if ((lhs->GetType() == Primitive::kPrimNot)) { 911 AddError(StringPrintf( 912 "Condition %s %d uses an object as left-hand side input.", 913 op->DebugName(), op->GetId())); 914 } else if (rhs->GetType() == Primitive::kPrimNot) { 915 AddError(StringPrintf( 916 "Condition %s %d uses an object as right-hand side input.", 917 op->DebugName(), op->GetId())); 918 } 919 } 920 } 921 922 void GraphChecker::VisitNeg(HNeg* instruction) { 923 VisitInstruction(instruction); 924 Primitive::Type input_type = instruction->InputAt(0)->GetType(); 925 Primitive::Type result_type = instruction->GetType(); 926 if (result_type != Primitive::PrimitiveKind(input_type)) { 927 AddError(StringPrintf("Binary operation %s %d has a result type different " 928 "from its input kind: %s vs %s.", 929 instruction->DebugName(), instruction->GetId(), 930 Primitive::PrettyDescriptor(result_type), 931 Primitive::PrettyDescriptor(input_type))); 932 } 933 } 934 935 void GraphChecker::VisitBinaryOperation(HBinaryOperation* op) { 936 VisitInstruction(op); 937 Primitive::Type lhs_type = op->InputAt(0)->GetType(); 938 Primitive::Type rhs_type = op->InputAt(1)->GetType(); 939 Primitive::Type result_type = op->GetType(); 940 941 // Type consistency between inputs. 942 if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRor()) { 943 if (Primitive::PrimitiveKind(rhs_type) != Primitive::kPrimInt) { 944 AddError(StringPrintf("Shift/rotate operation %s %d has a non-int kind second input: " 945 "%s of type %s.", 946 op->DebugName(), op->GetId(), 947 op->InputAt(1)->DebugName(), 948 Primitive::PrettyDescriptor(rhs_type))); 949 } 950 } else { 951 if (Primitive::PrimitiveKind(lhs_type) != Primitive::PrimitiveKind(rhs_type)) { 952 AddError(StringPrintf("Binary operation %s %d has inputs of different kinds: %s, and %s.", 953 op->DebugName(), op->GetId(), 954 Primitive::PrettyDescriptor(lhs_type), 955 Primitive::PrettyDescriptor(rhs_type))); 956 } 957 } 958 959 // Type consistency between result and input(s). 960 if (op->IsCompare()) { 961 if (result_type != Primitive::kPrimInt) { 962 AddError(StringPrintf("Compare operation %d has a non-int result type: %s.", 963 op->GetId(), 964 Primitive::PrettyDescriptor(result_type))); 965 } 966 } else if (op->IsUShr() || op->IsShr() || op->IsShl() || op->IsRor()) { 967 // Only check the first input (value), as the second one (distance) 968 // must invariably be of kind `int`. 969 if (result_type != Primitive::PrimitiveKind(lhs_type)) { 970 AddError(StringPrintf("Shift/rotate operation %s %d has a result type different " 971 "from its left-hand side (value) input kind: %s vs %s.", 972 op->DebugName(), op->GetId(), 973 Primitive::PrettyDescriptor(result_type), 974 Primitive::PrettyDescriptor(lhs_type))); 975 } 976 } else { 977 if (Primitive::PrimitiveKind(result_type) != Primitive::PrimitiveKind(lhs_type)) { 978 AddError(StringPrintf("Binary operation %s %d has a result kind different " 979 "from its left-hand side input kind: %s vs %s.", 980 op->DebugName(), op->GetId(), 981 Primitive::PrettyDescriptor(result_type), 982 Primitive::PrettyDescriptor(lhs_type))); 983 } 984 if (Primitive::PrimitiveKind(result_type) != Primitive::PrimitiveKind(rhs_type)) { 985 AddError(StringPrintf("Binary operation %s %d has a result kind different " 986 "from its right-hand side input kind: %s vs %s.", 987 op->DebugName(), op->GetId(), 988 Primitive::PrettyDescriptor(result_type), 989 Primitive::PrettyDescriptor(rhs_type))); 990 } 991 } 992 } 993 994 void GraphChecker::VisitConstant(HConstant* instruction) { 995 HBasicBlock* block = instruction->GetBlock(); 996 if (!block->IsEntryBlock()) { 997 AddError(StringPrintf( 998 "%s %d should be in the entry block but is in block %d.", 999 instruction->DebugName(), 1000 instruction->GetId(), 1001 block->GetBlockId())); 1002 } 1003 } 1004 1005 void GraphChecker::VisitBoundType(HBoundType* instruction) { 1006 VisitInstruction(instruction); 1007 1008 ScopedObjectAccess soa(Thread::Current()); 1009 if (!instruction->GetUpperBound().IsValid()) { 1010 AddError(StringPrintf( 1011 "%s %d does not have a valid upper bound RTI.", 1012 instruction->DebugName(), 1013 instruction->GetId())); 1014 } 1015 } 1016 1017 void GraphChecker::VisitTypeConversion(HTypeConversion* instruction) { 1018 VisitInstruction(instruction); 1019 Primitive::Type result_type = instruction->GetResultType(); 1020 Primitive::Type input_type = instruction->GetInputType(); 1021 // Invariant: We should never generate a conversion to a Boolean value. 1022 if (result_type == Primitive::kPrimBoolean) { 1023 AddError(StringPrintf( 1024 "%s %d converts to a %s (from a %s).", 1025 instruction->DebugName(), 1026 instruction->GetId(), 1027 Primitive::PrettyDescriptor(result_type), 1028 Primitive::PrettyDescriptor(input_type))); 1029 } 1030 } 1031 1032 } // namespace art 1033
