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