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