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 "nodes.h" 18 19 #include "ssa_builder.h" 20 #include "base/bit_vector-inl.h" 21 #include "base/bit_utils.h" 22 #include "utils/growable_array.h" 23 #include "scoped_thread_state_change.h" 24 25 namespace art { 26 27 void HGraph::AddBlock(HBasicBlock* block) { 28 block->SetBlockId(blocks_.Size()); 29 blocks_.Add(block); 30 } 31 32 void HGraph::FindBackEdges(ArenaBitVector* visited) { 33 ArenaBitVector visiting(arena_, blocks_.Size(), false); 34 VisitBlockForBackEdges(entry_block_, visited, &visiting); 35 } 36 37 static void RemoveAsUser(HInstruction* instruction) { 38 for (size_t i = 0; i < instruction->InputCount(); i++) { 39 instruction->RemoveAsUserOfInput(i); 40 } 41 42 for (HEnvironment* environment = instruction->GetEnvironment(); 43 environment != nullptr; 44 environment = environment->GetParent()) { 45 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 46 if (environment->GetInstructionAt(i) != nullptr) { 47 environment->RemoveAsUserOfInput(i); 48 } 49 } 50 } 51 } 52 53 void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const { 54 for (size_t i = 0; i < blocks_.Size(); ++i) { 55 if (!visited.IsBitSet(i)) { 56 HBasicBlock* block = blocks_.Get(i); 57 DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage"; 58 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 59 RemoveAsUser(it.Current()); 60 } 61 } 62 } 63 } 64 65 void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) { 66 for (size_t i = 0; i < blocks_.Size(); ++i) { 67 if (!visited.IsBitSet(i)) { 68 HBasicBlock* block = blocks_.Get(i); 69 // We only need to update the successor, which might be live. 70 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 71 block->GetSuccessors().Get(j)->RemovePredecessor(block); 72 } 73 // Remove the block from the list of blocks, so that further analyses 74 // never see it. 75 blocks_.Put(i, nullptr); 76 } 77 } 78 } 79 80 void HGraph::VisitBlockForBackEdges(HBasicBlock* block, 81 ArenaBitVector* visited, 82 ArenaBitVector* visiting) { 83 int id = block->GetBlockId(); 84 if (visited->IsBitSet(id)) return; 85 86 visited->SetBit(id); 87 visiting->SetBit(id); 88 for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { 89 HBasicBlock* successor = block->GetSuccessors().Get(i); 90 if (visiting->IsBitSet(successor->GetBlockId())) { 91 successor->AddBackEdge(block); 92 } else { 93 VisitBlockForBackEdges(successor, visited, visiting); 94 } 95 } 96 visiting->ClearBit(id); 97 } 98 99 void HGraph::BuildDominatorTree() { 100 ArenaBitVector visited(arena_, blocks_.Size(), false); 101 102 // (1) Find the back edges in the graph doing a DFS traversal. 103 FindBackEdges(&visited); 104 105 // (2) Remove instructions and phis from blocks not visited during 106 // the initial DFS as users from other instructions, so that 107 // users can be safely removed before uses later. 108 RemoveInstructionsAsUsersFromDeadBlocks(visited); 109 110 // (3) Remove blocks not visited during the initial DFS. 111 // Step (4) requires dead blocks to be removed from the 112 // predecessors list of live blocks. 113 RemoveDeadBlocks(visited); 114 115 // (4) Simplify the CFG now, so that we don't need to recompute 116 // dominators and the reverse post order. 117 SimplifyCFG(); 118 119 // (5) Compute the dominance information and the reverse post order. 120 ComputeDominanceInformation(); 121 } 122 123 void HGraph::ClearDominanceInformation() { 124 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 125 it.Current()->ClearDominanceInformation(); 126 } 127 reverse_post_order_.Reset(); 128 } 129 130 void HBasicBlock::ClearDominanceInformation() { 131 dominated_blocks_.Reset(); 132 dominator_ = nullptr; 133 } 134 135 void HGraph::ComputeDominanceInformation() { 136 DCHECK(reverse_post_order_.IsEmpty()); 137 GrowableArray<size_t> visits(arena_, blocks_.Size()); 138 visits.SetSize(blocks_.Size()); 139 reverse_post_order_.Add(entry_block_); 140 for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) { 141 VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits); 142 } 143 } 144 145 HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const { 146 ArenaBitVector visited(arena_, blocks_.Size(), false); 147 // Walk the dominator tree of the first block and mark the visited blocks. 148 while (first != nullptr) { 149 visited.SetBit(first->GetBlockId()); 150 first = first->GetDominator(); 151 } 152 // Walk the dominator tree of the second block until a marked block is found. 153 while (second != nullptr) { 154 if (visited.IsBitSet(second->GetBlockId())) { 155 return second; 156 } 157 second = second->GetDominator(); 158 } 159 LOG(ERROR) << "Could not find common dominator"; 160 return nullptr; 161 } 162 163 void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, 164 HBasicBlock* predecessor, 165 GrowableArray<size_t>* visits) { 166 if (block->GetDominator() == nullptr) { 167 block->SetDominator(predecessor); 168 } else { 169 block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor)); 170 } 171 172 visits->Increment(block->GetBlockId()); 173 // Once all the forward edges have been visited, we know the immediate 174 // dominator of the block. We can then start visiting its successors. 175 if (visits->Get(block->GetBlockId()) == 176 block->GetPredecessors().Size() - block->NumberOfBackEdges()) { 177 block->GetDominator()->AddDominatedBlock(block); 178 reverse_post_order_.Add(block); 179 for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { 180 VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits); 181 } 182 } 183 } 184 185 void HGraph::TransformToSsa() { 186 DCHECK(!reverse_post_order_.IsEmpty()); 187 SsaBuilder ssa_builder(this); 188 ssa_builder.BuildSsa(); 189 } 190 191 void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { 192 // Insert a new node between `block` and `successor` to split the 193 // critical edge. 194 HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc()); 195 AddBlock(new_block); 196 new_block->AddInstruction(new (arena_) HGoto()); 197 // Use `InsertBetween` to ensure the predecessor index and successor index of 198 // `block` and `successor` are preserved. 199 new_block->InsertBetween(block, successor); 200 if (successor->IsLoopHeader()) { 201 // If we split at a back edge boundary, make the new block the back edge. 202 HLoopInformation* info = successor->GetLoopInformation(); 203 if (info->IsBackEdge(*block)) { 204 info->RemoveBackEdge(block); 205 info->AddBackEdge(new_block); 206 } 207 } 208 } 209 210 void HGraph::SimplifyLoop(HBasicBlock* header) { 211 HLoopInformation* info = header->GetLoopInformation(); 212 213 // Make sure the loop has only one pre header. This simplifies SSA building by having 214 // to just look at the pre header to know which locals are initialized at entry of the 215 // loop. 216 size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges(); 217 if (number_of_incomings != 1) { 218 HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 219 AddBlock(pre_header); 220 pre_header->AddInstruction(new (arena_) HGoto()); 221 222 for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { 223 HBasicBlock* predecessor = header->GetPredecessors().Get(pred); 224 if (!info->IsBackEdge(*predecessor)) { 225 predecessor->ReplaceSuccessor(header, pre_header); 226 pred--; 227 } 228 } 229 pre_header->AddSuccessor(header); 230 } 231 232 // Make sure the first predecessor of a loop header is the incoming block. 233 if (info->IsBackEdge(*header->GetPredecessors().Get(0))) { 234 HBasicBlock* to_swap = header->GetPredecessors().Get(0); 235 for (size_t pred = 1, e = header->GetPredecessors().Size(); pred < e; ++pred) { 236 HBasicBlock* predecessor = header->GetPredecessors().Get(pred); 237 if (!info->IsBackEdge(*predecessor)) { 238 header->predecessors_.Put(pred, to_swap); 239 header->predecessors_.Put(0, predecessor); 240 break; 241 } 242 } 243 } 244 245 // Place the suspend check at the beginning of the header, so that live registers 246 // will be known when allocating registers. Note that code generation can still 247 // generate the suspend check at the back edge, but needs to be careful with 248 // loop phi spill slots (which are not written to at back edge). 249 HInstruction* first_instruction = header->GetFirstInstruction(); 250 if (!first_instruction->IsSuspendCheck()) { 251 HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc()); 252 header->InsertInstructionBefore(check, first_instruction); 253 first_instruction = check; 254 } 255 info->SetSuspendCheck(first_instruction->AsSuspendCheck()); 256 } 257 258 void HGraph::SimplifyCFG() { 259 // Simplify the CFG for future analysis, and code generation: 260 // (1): Split critical edges. 261 // (2): Simplify loops by having only one back edge, and one preheader. 262 for (size_t i = 0; i < blocks_.Size(); ++i) { 263 HBasicBlock* block = blocks_.Get(i); 264 if (block == nullptr) continue; 265 if (block->GetSuccessors().Size() > 1) { 266 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 267 HBasicBlock* successor = block->GetSuccessors().Get(j); 268 if (successor->GetPredecessors().Size() > 1) { 269 SplitCriticalEdge(block, successor); 270 --j; 271 } 272 } 273 } 274 if (block->IsLoopHeader()) { 275 SimplifyLoop(block); 276 } 277 } 278 } 279 280 bool HGraph::AnalyzeNaturalLoops() const { 281 // Order does not matter. 282 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 283 HBasicBlock* block = it.Current(); 284 if (block->IsLoopHeader()) { 285 HLoopInformation* info = block->GetLoopInformation(); 286 if (!info->Populate()) { 287 // Abort if the loop is non natural. We currently bailout in such cases. 288 return false; 289 } 290 } 291 } 292 return true; 293 } 294 295 void HGraph::InsertConstant(HConstant* constant) { 296 // New constants are inserted before the final control-flow instruction 297 // of the graph, or at its end if called from the graph builder. 298 if (entry_block_->EndsWithControlFlowInstruction()) { 299 entry_block_->InsertInstructionBefore(constant, entry_block_->GetLastInstruction()); 300 } else { 301 entry_block_->AddInstruction(constant); 302 } 303 } 304 305 HNullConstant* HGraph::GetNullConstant() { 306 // For simplicity, don't bother reviving the cached null constant if it is 307 // not null and not in a block. Otherwise, we need to clear the instruction 308 // id and/or any invariants the graph is assuming when adding new instructions. 309 if ((cached_null_constant_ == nullptr) || (cached_null_constant_->GetBlock() == nullptr)) { 310 cached_null_constant_ = new (arena_) HNullConstant(); 311 InsertConstant(cached_null_constant_); 312 } 313 return cached_null_constant_; 314 } 315 316 HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value) { 317 switch (type) { 318 case Primitive::Type::kPrimBoolean: 319 DCHECK(IsUint<1>(value)); 320 FALLTHROUGH_INTENDED; 321 case Primitive::Type::kPrimByte: 322 case Primitive::Type::kPrimChar: 323 case Primitive::Type::kPrimShort: 324 case Primitive::Type::kPrimInt: 325 DCHECK(IsInt(Primitive::ComponentSize(type) * kBitsPerByte, value)); 326 return GetIntConstant(static_cast<int32_t>(value)); 327 328 case Primitive::Type::kPrimLong: 329 return GetLongConstant(value); 330 331 default: 332 LOG(FATAL) << "Unsupported constant type"; 333 UNREACHABLE(); 334 } 335 } 336 337 void HGraph::CacheFloatConstant(HFloatConstant* constant) { 338 int32_t value = bit_cast<int32_t, float>(constant->GetValue()); 339 DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end()); 340 cached_float_constants_.Overwrite(value, constant); 341 } 342 343 void HGraph::CacheDoubleConstant(HDoubleConstant* constant) { 344 int64_t value = bit_cast<int64_t, double>(constant->GetValue()); 345 DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end()); 346 cached_double_constants_.Overwrite(value, constant); 347 } 348 349 void HLoopInformation::Add(HBasicBlock* block) { 350 blocks_.SetBit(block->GetBlockId()); 351 } 352 353 void HLoopInformation::Remove(HBasicBlock* block) { 354 blocks_.ClearBit(block->GetBlockId()); 355 } 356 357 void HLoopInformation::PopulateRecursive(HBasicBlock* block) { 358 if (blocks_.IsBitSet(block->GetBlockId())) { 359 return; 360 } 361 362 blocks_.SetBit(block->GetBlockId()); 363 block->SetInLoop(this); 364 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 365 PopulateRecursive(block->GetPredecessors().Get(i)); 366 } 367 } 368 369 bool HLoopInformation::Populate() { 370 DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated"; 371 for (size_t i = 0, e = GetBackEdges().Size(); i < e; ++i) { 372 HBasicBlock* back_edge = GetBackEdges().Get(i); 373 DCHECK(back_edge->GetDominator() != nullptr); 374 if (!header_->Dominates(back_edge)) { 375 // This loop is not natural. Do not bother going further. 376 return false; 377 } 378 379 // Populate this loop: starting with the back edge, recursively add predecessors 380 // that are not already part of that loop. Set the header as part of the loop 381 // to end the recursion. 382 // This is a recursive implementation of the algorithm described in 383 // "Advanced Compiler Design & Implementation" (Muchnick) p192. 384 blocks_.SetBit(header_->GetBlockId()); 385 PopulateRecursive(back_edge); 386 } 387 return true; 388 } 389 390 void HLoopInformation::Update() { 391 HGraph* graph = header_->GetGraph(); 392 for (uint32_t id : blocks_.Indexes()) { 393 HBasicBlock* block = graph->GetBlocks().Get(id); 394 // Reset loop information of non-header blocks inside the loop, except 395 // members of inner nested loops because those should already have been 396 // updated by their own LoopInformation. 397 if (block->GetLoopInformation() == this && block != header_) { 398 block->SetLoopInformation(nullptr); 399 } 400 } 401 blocks_.ClearAllBits(); 402 403 if (back_edges_.IsEmpty()) { 404 // The loop has been dismantled, delete its suspend check and remove info 405 // from the header. 406 DCHECK(HasSuspendCheck()); 407 header_->RemoveInstruction(suspend_check_); 408 header_->SetLoopInformation(nullptr); 409 header_ = nullptr; 410 suspend_check_ = nullptr; 411 } else { 412 if (kIsDebugBuild) { 413 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 414 DCHECK(header_->Dominates(back_edges_.Get(i))); 415 } 416 } 417 // This loop still has reachable back edges. Repopulate the list of blocks. 418 bool populate_successful = Populate(); 419 DCHECK(populate_successful); 420 } 421 } 422 423 HBasicBlock* HLoopInformation::GetPreHeader() const { 424 return header_->GetDominator(); 425 } 426 427 bool HLoopInformation::Contains(const HBasicBlock& block) const { 428 return blocks_.IsBitSet(block.GetBlockId()); 429 } 430 431 bool HLoopInformation::IsIn(const HLoopInformation& other) const { 432 return other.blocks_.IsBitSet(header_->GetBlockId()); 433 } 434 435 size_t HLoopInformation::GetLifetimeEnd() const { 436 size_t last_position = 0; 437 for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { 438 last_position = std::max(back_edges_.Get(i)->GetLifetimeEnd(), last_position); 439 } 440 return last_position; 441 } 442 443 bool HBasicBlock::Dominates(HBasicBlock* other) const { 444 // Walk up the dominator tree from `other`, to find out if `this` 445 // is an ancestor. 446 HBasicBlock* current = other; 447 while (current != nullptr) { 448 if (current == this) { 449 return true; 450 } 451 current = current->GetDominator(); 452 } 453 return false; 454 } 455 456 static void UpdateInputsUsers(HInstruction* instruction) { 457 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { 458 instruction->InputAt(i)->AddUseAt(instruction, i); 459 } 460 // Environment should be created later. 461 DCHECK(!instruction->HasEnvironment()); 462 } 463 464 void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, 465 HInstruction* replacement) { 466 DCHECK(initial->GetBlock() == this); 467 InsertInstructionBefore(replacement, initial); 468 initial->ReplaceWith(replacement); 469 RemoveInstruction(initial); 470 } 471 472 static void Add(HInstructionList* instruction_list, 473 HBasicBlock* block, 474 HInstruction* instruction) { 475 DCHECK(instruction->GetBlock() == nullptr); 476 DCHECK_EQ(instruction->GetId(), -1); 477 instruction->SetBlock(block); 478 instruction->SetId(block->GetGraph()->GetNextInstructionId()); 479 UpdateInputsUsers(instruction); 480 instruction_list->AddInstruction(instruction); 481 } 482 483 void HBasicBlock::AddInstruction(HInstruction* instruction) { 484 Add(&instructions_, this, instruction); 485 } 486 487 void HBasicBlock::AddPhi(HPhi* phi) { 488 Add(&phis_, this, phi); 489 } 490 491 void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 492 DCHECK(!cursor->IsPhi()); 493 DCHECK(!instruction->IsPhi()); 494 DCHECK_EQ(instruction->GetId(), -1); 495 DCHECK_NE(cursor->GetId(), -1); 496 DCHECK_EQ(cursor->GetBlock(), this); 497 DCHECK(!instruction->IsControlFlow()); 498 instruction->SetBlock(this); 499 instruction->SetId(GetGraph()->GetNextInstructionId()); 500 UpdateInputsUsers(instruction); 501 instructions_.InsertInstructionBefore(instruction, cursor); 502 } 503 504 void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 505 DCHECK(!cursor->IsPhi()); 506 DCHECK(!instruction->IsPhi()); 507 DCHECK_EQ(instruction->GetId(), -1); 508 DCHECK_NE(cursor->GetId(), -1); 509 DCHECK_EQ(cursor->GetBlock(), this); 510 DCHECK(!instruction->IsControlFlow()); 511 DCHECK(!cursor->IsControlFlow()); 512 instruction->SetBlock(this); 513 instruction->SetId(GetGraph()->GetNextInstructionId()); 514 UpdateInputsUsers(instruction); 515 instructions_.InsertInstructionAfter(instruction, cursor); 516 } 517 518 void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) { 519 DCHECK_EQ(phi->GetId(), -1); 520 DCHECK_NE(cursor->GetId(), -1); 521 DCHECK_EQ(cursor->GetBlock(), this); 522 phi->SetBlock(this); 523 phi->SetId(GetGraph()->GetNextInstructionId()); 524 UpdateInputsUsers(phi); 525 phis_.InsertInstructionAfter(phi, cursor); 526 } 527 528 static void Remove(HInstructionList* instruction_list, 529 HBasicBlock* block, 530 HInstruction* instruction, 531 bool ensure_safety) { 532 DCHECK_EQ(block, instruction->GetBlock()); 533 instruction->SetBlock(nullptr); 534 instruction_list->RemoveInstruction(instruction); 535 if (ensure_safety) { 536 DCHECK(instruction->GetUses().IsEmpty()); 537 DCHECK(instruction->GetEnvUses().IsEmpty()); 538 RemoveAsUser(instruction); 539 } 540 } 541 542 void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) { 543 DCHECK(!instruction->IsPhi()); 544 Remove(&instructions_, this, instruction, ensure_safety); 545 } 546 547 void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) { 548 Remove(&phis_, this, phi, ensure_safety); 549 } 550 551 void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) { 552 if (instruction->IsPhi()) { 553 RemovePhi(instruction->AsPhi(), ensure_safety); 554 } else { 555 RemoveInstruction(instruction, ensure_safety); 556 } 557 } 558 559 void HEnvironment::CopyFrom(const GrowableArray<HInstruction*>& locals) { 560 for (size_t i = 0; i < locals.Size(); i++) { 561 HInstruction* instruction = locals.Get(i); 562 SetRawEnvAt(i, instruction); 563 if (instruction != nullptr) { 564 instruction->AddEnvUseAt(this, i); 565 } 566 } 567 } 568 569 void HEnvironment::CopyFrom(HEnvironment* env) { 570 for (size_t i = 0; i < env->Size(); i++) { 571 HInstruction* instruction = env->GetInstructionAt(i); 572 SetRawEnvAt(i, instruction); 573 if (instruction != nullptr) { 574 instruction->AddEnvUseAt(this, i); 575 } 576 } 577 } 578 579 void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env, 580 HBasicBlock* loop_header) { 581 DCHECK(loop_header->IsLoopHeader()); 582 for (size_t i = 0; i < env->Size(); i++) { 583 HInstruction* instruction = env->GetInstructionAt(i); 584 SetRawEnvAt(i, instruction); 585 if (instruction == nullptr) { 586 continue; 587 } 588 if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) { 589 // At the end of the loop pre-header, the corresponding value for instruction 590 // is the first input of the phi. 591 HInstruction* initial = instruction->AsPhi()->InputAt(0); 592 DCHECK(initial->GetBlock()->Dominates(loop_header)); 593 SetRawEnvAt(i, initial); 594 initial->AddEnvUseAt(this, i); 595 } else { 596 instruction->AddEnvUseAt(this, i); 597 } 598 } 599 } 600 601 void HEnvironment::RemoveAsUserOfInput(size_t index) const { 602 const HUserRecord<HEnvironment*> user_record = vregs_.Get(index); 603 user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode()); 604 } 605 606 HInstruction* HInstruction::GetNextDisregardingMoves() const { 607 HInstruction* next = GetNext(); 608 while (next != nullptr && next->IsParallelMove()) { 609 next = next->GetNext(); 610 } 611 return next; 612 } 613 614 HInstruction* HInstruction::GetPreviousDisregardingMoves() const { 615 HInstruction* previous = GetPrevious(); 616 while (previous != nullptr && previous->IsParallelMove()) { 617 previous = previous->GetPrevious(); 618 } 619 return previous; 620 } 621 622 void HInstructionList::AddInstruction(HInstruction* instruction) { 623 if (first_instruction_ == nullptr) { 624 DCHECK(last_instruction_ == nullptr); 625 first_instruction_ = last_instruction_ = instruction; 626 } else { 627 last_instruction_->next_ = instruction; 628 instruction->previous_ = last_instruction_; 629 last_instruction_ = instruction; 630 } 631 } 632 633 void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 634 DCHECK(Contains(cursor)); 635 if (cursor == first_instruction_) { 636 cursor->previous_ = instruction; 637 instruction->next_ = cursor; 638 first_instruction_ = instruction; 639 } else { 640 instruction->previous_ = cursor->previous_; 641 instruction->next_ = cursor; 642 cursor->previous_ = instruction; 643 instruction->previous_->next_ = instruction; 644 } 645 } 646 647 void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { 648 DCHECK(Contains(cursor)); 649 if (cursor == last_instruction_) { 650 cursor->next_ = instruction; 651 instruction->previous_ = cursor; 652 last_instruction_ = instruction; 653 } else { 654 instruction->next_ = cursor->next_; 655 instruction->previous_ = cursor; 656 cursor->next_ = instruction; 657 instruction->next_->previous_ = instruction; 658 } 659 } 660 661 void HInstructionList::RemoveInstruction(HInstruction* instruction) { 662 if (instruction->previous_ != nullptr) { 663 instruction->previous_->next_ = instruction->next_; 664 } 665 if (instruction->next_ != nullptr) { 666 instruction->next_->previous_ = instruction->previous_; 667 } 668 if (instruction == first_instruction_) { 669 first_instruction_ = instruction->next_; 670 } 671 if (instruction == last_instruction_) { 672 last_instruction_ = instruction->previous_; 673 } 674 } 675 676 bool HInstructionList::Contains(HInstruction* instruction) const { 677 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 678 if (it.Current() == instruction) { 679 return true; 680 } 681 } 682 return false; 683 } 684 685 bool HInstructionList::FoundBefore(const HInstruction* instruction1, 686 const HInstruction* instruction2) const { 687 DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock()); 688 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 689 if (it.Current() == instruction1) { 690 return true; 691 } 692 if (it.Current() == instruction2) { 693 return false; 694 } 695 } 696 LOG(FATAL) << "Did not find an order between two instructions of the same block."; 697 return true; 698 } 699 700 bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { 701 if (other_instruction == this) { 702 // An instruction does not strictly dominate itself. 703 return false; 704 } 705 HBasicBlock* block = GetBlock(); 706 HBasicBlock* other_block = other_instruction->GetBlock(); 707 if (block != other_block) { 708 return GetBlock()->Dominates(other_instruction->GetBlock()); 709 } else { 710 // If both instructions are in the same block, ensure this 711 // instruction comes before `other_instruction`. 712 if (IsPhi()) { 713 if (!other_instruction->IsPhi()) { 714 // Phis appear before non phi-instructions so this instruction 715 // dominates `other_instruction`. 716 return true; 717 } else { 718 // There is no order among phis. 719 LOG(FATAL) << "There is no dominance between phis of a same block."; 720 return false; 721 } 722 } else { 723 // `this` is not a phi. 724 if (other_instruction->IsPhi()) { 725 // Phis appear before non phi-instructions so this instruction 726 // does not dominate `other_instruction`. 727 return false; 728 } else { 729 // Check whether this instruction comes before 730 // `other_instruction` in the instruction list. 731 return block->GetInstructions().FoundBefore(this, other_instruction); 732 } 733 } 734 } 735 } 736 737 void HInstruction::ReplaceWith(HInstruction* other) { 738 DCHECK(other != nullptr); 739 for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) { 740 HUseListNode<HInstruction*>* current = it.Current(); 741 HInstruction* user = current->GetUser(); 742 size_t input_index = current->GetIndex(); 743 user->SetRawInputAt(input_index, other); 744 other->AddUseAt(user, input_index); 745 } 746 747 for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) { 748 HUseListNode<HEnvironment*>* current = it.Current(); 749 HEnvironment* user = current->GetUser(); 750 size_t input_index = current->GetIndex(); 751 user->SetRawEnvAt(input_index, other); 752 other->AddEnvUseAt(user, input_index); 753 } 754 755 uses_.Clear(); 756 env_uses_.Clear(); 757 } 758 759 void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) { 760 RemoveAsUserOfInput(index); 761 SetRawInputAt(index, replacement); 762 replacement->AddUseAt(this, index); 763 } 764 765 size_t HInstruction::EnvironmentSize() const { 766 return HasEnvironment() ? environment_->Size() : 0; 767 } 768 769 void HPhi::AddInput(HInstruction* input) { 770 DCHECK(input->GetBlock() != nullptr); 771 inputs_.Add(HUserRecord<HInstruction*>(input)); 772 input->AddUseAt(this, inputs_.Size() - 1); 773 } 774 775 void HPhi::RemoveInputAt(size_t index) { 776 RemoveAsUserOfInput(index); 777 inputs_.DeleteAt(index); 778 for (size_t i = index, e = InputCount(); i < e; ++i) { 779 InputRecordAt(i).GetUseNode()->SetIndex(i); 780 } 781 } 782 783 #define DEFINE_ACCEPT(name, super) \ 784 void H##name::Accept(HGraphVisitor* visitor) { \ 785 visitor->Visit##name(this); \ 786 } 787 788 FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) 789 790 #undef DEFINE_ACCEPT 791 792 void HGraphVisitor::VisitInsertionOrder() { 793 const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks(); 794 for (size_t i = 0 ; i < blocks.Size(); i++) { 795 HBasicBlock* block = blocks.Get(i); 796 if (block != nullptr) { 797 VisitBasicBlock(block); 798 } 799 } 800 } 801 802 void HGraphVisitor::VisitReversePostOrder() { 803 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 804 VisitBasicBlock(it.Current()); 805 } 806 } 807 808 void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { 809 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 810 it.Current()->Accept(this); 811 } 812 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 813 it.Current()->Accept(this); 814 } 815 } 816 817 HConstant* HUnaryOperation::TryStaticEvaluation() const { 818 if (GetInput()->IsIntConstant()) { 819 int32_t value = Evaluate(GetInput()->AsIntConstant()->GetValue()); 820 return GetBlock()->GetGraph()->GetIntConstant(value); 821 } else if (GetInput()->IsLongConstant()) { 822 // TODO: Implement static evaluation of long unary operations. 823 // 824 // Do not exit with a fatal condition here. Instead, simply 825 // return `null' to notify the caller that this instruction 826 // cannot (yet) be statically evaluated. 827 return nullptr; 828 } 829 return nullptr; 830 } 831 832 HConstant* HBinaryOperation::TryStaticEvaluation() const { 833 if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) { 834 int32_t value = Evaluate(GetLeft()->AsIntConstant()->GetValue(), 835 GetRight()->AsIntConstant()->GetValue()); 836 return GetBlock()->GetGraph()->GetIntConstant(value); 837 } else if (GetLeft()->IsLongConstant() && GetRight()->IsLongConstant()) { 838 int64_t value = Evaluate(GetLeft()->AsLongConstant()->GetValue(), 839 GetRight()->AsLongConstant()->GetValue()); 840 if (GetResultType() == Primitive::kPrimLong) { 841 return GetBlock()->GetGraph()->GetLongConstant(value); 842 } else { 843 DCHECK_EQ(GetResultType(), Primitive::kPrimInt); 844 return GetBlock()->GetGraph()->GetIntConstant(static_cast<int32_t>(value)); 845 } 846 } 847 return nullptr; 848 } 849 850 HConstant* HBinaryOperation::GetConstantRight() const { 851 if (GetRight()->IsConstant()) { 852 return GetRight()->AsConstant(); 853 } else if (IsCommutative() && GetLeft()->IsConstant()) { 854 return GetLeft()->AsConstant(); 855 } else { 856 return nullptr; 857 } 858 } 859 860 // If `GetConstantRight()` returns one of the input, this returns the other 861 // one. Otherwise it returns null. 862 HInstruction* HBinaryOperation::GetLeastConstantLeft() const { 863 HInstruction* most_constant_right = GetConstantRight(); 864 if (most_constant_right == nullptr) { 865 return nullptr; 866 } else if (most_constant_right == GetLeft()) { 867 return GetRight(); 868 } else { 869 return GetLeft(); 870 } 871 } 872 873 bool HCondition::IsBeforeWhenDisregardMoves(HInstruction* instruction) const { 874 return this == instruction->GetPreviousDisregardingMoves(); 875 } 876 877 bool HInstruction::Equals(HInstruction* other) const { 878 if (!InstructionTypeEquals(other)) return false; 879 DCHECK_EQ(GetKind(), other->GetKind()); 880 if (!InstructionDataEquals(other)) return false; 881 if (GetType() != other->GetType()) return false; 882 if (InputCount() != other->InputCount()) return false; 883 884 for (size_t i = 0, e = InputCount(); i < e; ++i) { 885 if (InputAt(i) != other->InputAt(i)) return false; 886 } 887 DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode()); 888 return true; 889 } 890 891 std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) { 892 #define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break; 893 switch (rhs) { 894 FOR_EACH_INSTRUCTION(DECLARE_CASE) 895 default: 896 os << "Unknown instruction kind " << static_cast<int>(rhs); 897 break; 898 } 899 #undef DECLARE_CASE 900 return os; 901 } 902 903 void HInstruction::MoveBefore(HInstruction* cursor) { 904 next_->previous_ = previous_; 905 if (previous_ != nullptr) { 906 previous_->next_ = next_; 907 } 908 if (block_->instructions_.first_instruction_ == this) { 909 block_->instructions_.first_instruction_ = next_; 910 } 911 DCHECK_NE(block_->instructions_.last_instruction_, this); 912 913 previous_ = cursor->previous_; 914 if (previous_ != nullptr) { 915 previous_->next_ = this; 916 } 917 next_ = cursor; 918 cursor->previous_ = this; 919 block_ = cursor->block_; 920 921 if (block_->instructions_.first_instruction_ == cursor) { 922 block_->instructions_.first_instruction_ = this; 923 } 924 } 925 926 HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) { 927 DCHECK(!cursor->IsControlFlow()); 928 DCHECK_NE(instructions_.last_instruction_, cursor); 929 DCHECK_EQ(cursor->GetBlock(), this); 930 931 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc()); 932 new_block->instructions_.first_instruction_ = cursor->GetNext(); 933 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 934 cursor->next_->previous_ = nullptr; 935 cursor->next_ = nullptr; 936 instructions_.last_instruction_ = cursor; 937 938 new_block->instructions_.SetBlockOfInstructions(new_block); 939 for (size_t i = 0, e = GetSuccessors().Size(); i < e; ++i) { 940 HBasicBlock* successor = GetSuccessors().Get(i); 941 new_block->successors_.Add(successor); 942 successor->predecessors_.Put(successor->GetPredecessorIndexOf(this), new_block); 943 } 944 successors_.Reset(); 945 946 for (size_t i = 0, e = GetDominatedBlocks().Size(); i < e; ++i) { 947 HBasicBlock* dominated = GetDominatedBlocks().Get(i); 948 dominated->dominator_ = new_block; 949 new_block->dominated_blocks_.Add(dominated); 950 } 951 dominated_blocks_.Reset(); 952 return new_block; 953 } 954 955 bool HBasicBlock::IsSingleGoto() const { 956 HLoopInformation* loop_info = GetLoopInformation(); 957 // TODO: Remove the null check b/19084197. 958 return GetFirstInstruction() != nullptr 959 && GetPhis().IsEmpty() 960 && GetFirstInstruction() == GetLastInstruction() 961 && GetLastInstruction()->IsGoto() 962 // Back edges generate the suspend check. 963 && (loop_info == nullptr || !loop_info->IsBackEdge(*this)); 964 } 965 966 bool HBasicBlock::EndsWithControlFlowInstruction() const { 967 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsControlFlow(); 968 } 969 970 bool HBasicBlock::EndsWithIf() const { 971 return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf(); 972 } 973 974 bool HBasicBlock::HasSinglePhi() const { 975 return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr; 976 } 977 978 size_t HInstructionList::CountSize() const { 979 size_t size = 0; 980 HInstruction* current = first_instruction_; 981 for (; current != nullptr; current = current->GetNext()) { 982 size++; 983 } 984 return size; 985 } 986 987 void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const { 988 for (HInstruction* current = first_instruction_; 989 current != nullptr; 990 current = current->GetNext()) { 991 current->SetBlock(block); 992 } 993 } 994 995 void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) { 996 DCHECK(Contains(cursor)); 997 if (!instruction_list.IsEmpty()) { 998 if (cursor == last_instruction_) { 999 last_instruction_ = instruction_list.last_instruction_; 1000 } else { 1001 cursor->next_->previous_ = instruction_list.last_instruction_; 1002 } 1003 instruction_list.last_instruction_->next_ = cursor->next_; 1004 cursor->next_ = instruction_list.first_instruction_; 1005 instruction_list.first_instruction_->previous_ = cursor; 1006 } 1007 } 1008 1009 void HInstructionList::Add(const HInstructionList& instruction_list) { 1010 if (IsEmpty()) { 1011 first_instruction_ = instruction_list.first_instruction_; 1012 last_instruction_ = instruction_list.last_instruction_; 1013 } else { 1014 AddAfter(last_instruction_, instruction_list); 1015 } 1016 } 1017 1018 void HBasicBlock::DisconnectAndDelete() { 1019 // Dominators must be removed after all the blocks they dominate. This way 1020 // a loop header is removed last, a requirement for correct loop information 1021 // iteration. 1022 DCHECK(dominated_blocks_.IsEmpty()); 1023 1024 // Remove the block from all loops it is included in. 1025 for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) { 1026 HLoopInformation* loop_info = it.Current(); 1027 loop_info->Remove(this); 1028 if (loop_info->IsBackEdge(*this)) { 1029 // If this was the last back edge of the loop, we deliberately leave the 1030 // loop in an inconsistent state and will fail SSAChecker unless the 1031 // entire loop is removed during the pass. 1032 loop_info->RemoveBackEdge(this); 1033 } 1034 } 1035 1036 // Disconnect the block from its predecessors and update their control-flow 1037 // instructions. 1038 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { 1039 HBasicBlock* predecessor = predecessors_.Get(i); 1040 HInstruction* last_instruction = predecessor->GetLastInstruction(); 1041 predecessor->RemoveInstruction(last_instruction); 1042 predecessor->RemoveSuccessor(this); 1043 if (predecessor->GetSuccessors().Size() == 1u) { 1044 DCHECK(last_instruction->IsIf()); 1045 predecessor->AddInstruction(new (graph_->GetArena()) HGoto()); 1046 } else { 1047 // The predecessor has no remaining successors and therefore must be dead. 1048 // We deliberately leave it without a control-flow instruction so that the 1049 // SSAChecker fails unless it is not removed during the pass too. 1050 DCHECK_EQ(predecessor->GetSuccessors().Size(), 0u); 1051 } 1052 } 1053 predecessors_.Reset(); 1054 1055 // Disconnect the block from its successors and update their phis. 1056 for (size_t i = 0, e = successors_.Size(); i < e; ++i) { 1057 HBasicBlock* successor = successors_.Get(i); 1058 // Delete this block from the list of predecessors. 1059 size_t this_index = successor->GetPredecessorIndexOf(this); 1060 successor->predecessors_.DeleteAt(this_index); 1061 1062 // Check that `successor` has other predecessors, otherwise `this` is the 1063 // dominator of `successor` which violates the order DCHECKed at the top. 1064 DCHECK(!successor->predecessors_.IsEmpty()); 1065 1066 // Remove this block's entries in the successor's phis. 1067 if (successor->predecessors_.Size() == 1u) { 1068 // The successor has just one predecessor left. Replace phis with the only 1069 // remaining input. 1070 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 1071 HPhi* phi = phi_it.Current()->AsPhi(); 1072 phi->ReplaceWith(phi->InputAt(1 - this_index)); 1073 successor->RemovePhi(phi); 1074 } 1075 } else { 1076 for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 1077 phi_it.Current()->AsPhi()->RemoveInputAt(this_index); 1078 } 1079 } 1080 } 1081 successors_.Reset(); 1082 1083 // Disconnect from the dominator. 1084 dominator_->RemoveDominatedBlock(this); 1085 SetDominator(nullptr); 1086 1087 // Delete from the graph. The function safely deletes remaining instructions 1088 // and updates the reverse post order. 1089 graph_->DeleteDeadBlock(this); 1090 SetGraph(nullptr); 1091 } 1092 1093 void HBasicBlock::MergeWith(HBasicBlock* other) { 1094 DCHECK_EQ(GetGraph(), other->GetGraph()); 1095 DCHECK(GetDominatedBlocks().Contains(other)); 1096 DCHECK_EQ(GetSuccessors().Size(), 1u); 1097 DCHECK_EQ(GetSuccessors().Get(0), other); 1098 DCHECK_EQ(other->GetPredecessors().Size(), 1u); 1099 DCHECK_EQ(other->GetPredecessors().Get(0), this); 1100 DCHECK(other->GetPhis().IsEmpty()); 1101 1102 // Move instructions from `other` to `this`. 1103 DCHECK(EndsWithControlFlowInstruction()); 1104 RemoveInstruction(GetLastInstruction()); 1105 instructions_.Add(other->GetInstructions()); 1106 other->instructions_.SetBlockOfInstructions(this); 1107 other->instructions_.Clear(); 1108 1109 // Remove `other` from the loops it is included in. 1110 for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) { 1111 HLoopInformation* loop_info = it.Current(); 1112 loop_info->Remove(other); 1113 if (loop_info->IsBackEdge(*other)) { 1114 loop_info->ReplaceBackEdge(other, this); 1115 } 1116 } 1117 1118 // Update links to the successors of `other`. 1119 successors_.Reset(); 1120 while (!other->successors_.IsEmpty()) { 1121 HBasicBlock* successor = other->successors_.Get(0); 1122 successor->ReplacePredecessor(other, this); 1123 } 1124 1125 // Update the dominator tree. 1126 dominated_blocks_.Delete(other); 1127 for (size_t i = 0, e = other->GetDominatedBlocks().Size(); i < e; ++i) { 1128 HBasicBlock* dominated = other->GetDominatedBlocks().Get(i); 1129 dominated_blocks_.Add(dominated); 1130 dominated->SetDominator(this); 1131 } 1132 other->dominated_blocks_.Reset(); 1133 other->dominator_ = nullptr; 1134 1135 // Clear the list of predecessors of `other` in preparation of deleting it. 1136 other->predecessors_.Reset(); 1137 1138 // Delete `other` from the graph. The function updates reverse post order. 1139 graph_->DeleteDeadBlock(other); 1140 other->SetGraph(nullptr); 1141 } 1142 1143 void HBasicBlock::MergeWithInlined(HBasicBlock* other) { 1144 DCHECK_NE(GetGraph(), other->GetGraph()); 1145 DCHECK(GetDominatedBlocks().IsEmpty()); 1146 DCHECK(GetSuccessors().IsEmpty()); 1147 DCHECK(!EndsWithControlFlowInstruction()); 1148 DCHECK_EQ(other->GetPredecessors().Size(), 1u); 1149 DCHECK(other->GetPredecessors().Get(0)->IsEntryBlock()); 1150 DCHECK(other->GetPhis().IsEmpty()); 1151 DCHECK(!other->IsInLoop()); 1152 1153 // Move instructions from `other` to `this`. 1154 instructions_.Add(other->GetInstructions()); 1155 other->instructions_.SetBlockOfInstructions(this); 1156 1157 // Update links to the successors of `other`. 1158 successors_.Reset(); 1159 while (!other->successors_.IsEmpty()) { 1160 HBasicBlock* successor = other->successors_.Get(0); 1161 successor->ReplacePredecessor(other, this); 1162 } 1163 1164 // Update the dominator tree. 1165 for (size_t i = 0, e = other->GetDominatedBlocks().Size(); i < e; ++i) { 1166 HBasicBlock* dominated = other->GetDominatedBlocks().Get(i); 1167 dominated_blocks_.Add(dominated); 1168 dominated->SetDominator(this); 1169 } 1170 other->dominated_blocks_.Reset(); 1171 other->dominator_ = nullptr; 1172 other->graph_ = nullptr; 1173 } 1174 1175 void HBasicBlock::ReplaceWith(HBasicBlock* other) { 1176 while (!GetPredecessors().IsEmpty()) { 1177 HBasicBlock* predecessor = GetPredecessors().Get(0); 1178 predecessor->ReplaceSuccessor(this, other); 1179 } 1180 while (!GetSuccessors().IsEmpty()) { 1181 HBasicBlock* successor = GetSuccessors().Get(0); 1182 successor->ReplacePredecessor(this, other); 1183 } 1184 for (size_t i = 0; i < dominated_blocks_.Size(); ++i) { 1185 other->AddDominatedBlock(dominated_blocks_.Get(i)); 1186 } 1187 GetDominator()->ReplaceDominatedBlock(this, other); 1188 other->SetDominator(GetDominator()); 1189 dominator_ = nullptr; 1190 graph_ = nullptr; 1191 } 1192 1193 // Create space in `blocks` for adding `number_of_new_blocks` entries 1194 // starting at location `at`. Blocks after `at` are moved accordingly. 1195 static void MakeRoomFor(GrowableArray<HBasicBlock*>* blocks, 1196 size_t number_of_new_blocks, 1197 size_t at) { 1198 size_t old_size = blocks->Size(); 1199 size_t new_size = old_size + number_of_new_blocks; 1200 blocks->SetSize(new_size); 1201 for (size_t i = old_size - 1, j = new_size - 1; i > at; --i, --j) { 1202 blocks->Put(j, blocks->Get(i)); 1203 } 1204 } 1205 1206 void HGraph::DeleteDeadBlock(HBasicBlock* block) { 1207 DCHECK_EQ(block->GetGraph(), this); 1208 DCHECK(block->GetSuccessors().IsEmpty()); 1209 DCHECK(block->GetPredecessors().IsEmpty()); 1210 DCHECK(block->GetDominatedBlocks().IsEmpty()); 1211 DCHECK(block->GetDominator() == nullptr); 1212 1213 for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 1214 block->RemoveInstruction(it.Current()); 1215 } 1216 for (HBackwardInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 1217 block->RemovePhi(it.Current()->AsPhi()); 1218 } 1219 1220 reverse_post_order_.Delete(block); 1221 blocks_.Put(block->GetBlockId(), nullptr); 1222 } 1223 1224 void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { 1225 if (GetBlocks().Size() == 3) { 1226 // Simple case of an entry block, a body block, and an exit block. 1227 // Put the body block's instruction into `invoke`'s block. 1228 HBasicBlock* body = GetBlocks().Get(1); 1229 DCHECK(GetBlocks().Get(0)->IsEntryBlock()); 1230 DCHECK(GetBlocks().Get(2)->IsExitBlock()); 1231 DCHECK(!body->IsExitBlock()); 1232 HInstruction* last = body->GetLastInstruction(); 1233 1234 invoke->GetBlock()->instructions_.AddAfter(invoke, body->GetInstructions()); 1235 body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock()); 1236 1237 // Replace the invoke with the return value of the inlined graph. 1238 if (last->IsReturn()) { 1239 invoke->ReplaceWith(last->InputAt(0)); 1240 } else { 1241 DCHECK(last->IsReturnVoid()); 1242 } 1243 1244 invoke->GetBlock()->RemoveInstruction(last); 1245 } else { 1246 // Need to inline multiple blocks. We split `invoke`'s block 1247 // into two blocks, merge the first block of the inlined graph into 1248 // the first half, and replace the exit block of the inlined graph 1249 // with the second half. 1250 ArenaAllocator* allocator = outer_graph->GetArena(); 1251 HBasicBlock* at = invoke->GetBlock(); 1252 HBasicBlock* to = at->SplitAfter(invoke); 1253 1254 HBasicBlock* first = entry_block_->GetSuccessors().Get(0); 1255 DCHECK(!first->IsInLoop()); 1256 at->MergeWithInlined(first); 1257 exit_block_->ReplaceWith(to); 1258 1259 // Update all predecessors of the exit block (now the `to` block) 1260 // to not `HReturn` but `HGoto` instead. 1261 HInstruction* return_value = nullptr; 1262 bool returns_void = to->GetPredecessors().Get(0)->GetLastInstruction()->IsReturnVoid(); 1263 if (to->GetPredecessors().Size() == 1) { 1264 HBasicBlock* predecessor = to->GetPredecessors().Get(0); 1265 HInstruction* last = predecessor->GetLastInstruction(); 1266 if (!returns_void) { 1267 return_value = last->InputAt(0); 1268 } 1269 predecessor->AddInstruction(new (allocator) HGoto()); 1270 predecessor->RemoveInstruction(last); 1271 } else { 1272 if (!returns_void) { 1273 // There will be multiple returns. 1274 return_value = new (allocator) HPhi( 1275 allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType())); 1276 to->AddPhi(return_value->AsPhi()); 1277 } 1278 for (size_t i = 0, e = to->GetPredecessors().Size(); i < e; ++i) { 1279 HBasicBlock* predecessor = to->GetPredecessors().Get(i); 1280 HInstruction* last = predecessor->GetLastInstruction(); 1281 if (!returns_void) { 1282 return_value->AsPhi()->AddInput(last->InputAt(0)); 1283 } 1284 predecessor->AddInstruction(new (allocator) HGoto()); 1285 predecessor->RemoveInstruction(last); 1286 } 1287 } 1288 1289 if (return_value != nullptr) { 1290 invoke->ReplaceWith(return_value); 1291 } 1292 1293 // Update the meta information surrounding blocks: 1294 // (1) the graph they are now in, 1295 // (2) the reverse post order of that graph, 1296 // (3) the potential loop information they are now in. 1297 1298 // We don't add the entry block, the exit block, and the first block, which 1299 // has been merged with `at`. 1300 static constexpr int kNumberOfSkippedBlocksInCallee = 3; 1301 1302 // We add the `to` block. 1303 static constexpr int kNumberOfNewBlocksInCaller = 1; 1304 size_t blocks_added = (reverse_post_order_.Size() - kNumberOfSkippedBlocksInCallee) 1305 + kNumberOfNewBlocksInCaller; 1306 1307 // Find the location of `at` in the outer graph's reverse post order. The new 1308 // blocks will be added after it. 1309 size_t index_of_at = 0; 1310 while (outer_graph->reverse_post_order_.Get(index_of_at) != at) { 1311 index_of_at++; 1312 } 1313 MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at); 1314 1315 // Do a reverse post order of the blocks in the callee and do (1), (2), 1316 // and (3) to the blocks that apply. 1317 HLoopInformation* info = at->GetLoopInformation(); 1318 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 1319 HBasicBlock* current = it.Current(); 1320 if (current != exit_block_ && current != entry_block_ && current != first) { 1321 DCHECK(!current->IsInLoop()); 1322 DCHECK(current->GetGraph() == this); 1323 current->SetGraph(outer_graph); 1324 outer_graph->AddBlock(current); 1325 outer_graph->reverse_post_order_.Put(++index_of_at, current); 1326 if (info != nullptr) { 1327 current->SetLoopInformation(info); 1328 for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) { 1329 loop_it.Current()->Add(current); 1330 } 1331 } 1332 } 1333 } 1334 1335 // Do (1), (2), and (3) to `to`. 1336 to->SetGraph(outer_graph); 1337 outer_graph->AddBlock(to); 1338 outer_graph->reverse_post_order_.Put(++index_of_at, to); 1339 if (info != nullptr) { 1340 to->SetLoopInformation(info); 1341 for (HLoopInformationOutwardIterator loop_it(*at); !loop_it.Done(); loop_it.Advance()) { 1342 loop_it.Current()->Add(to); 1343 } 1344 if (info->IsBackEdge(*at)) { 1345 // Only `to` can become a back edge, as the inlined blocks 1346 // are predecessors of `to`. 1347 info->ReplaceBackEdge(at, to); 1348 } 1349 } 1350 } 1351 1352 // Update the next instruction id of the outer graph, so that instructions 1353 // added later get bigger ids than those in the inner graph. 1354 outer_graph->SetCurrentInstructionId(GetNextInstructionId()); 1355 1356 // Walk over the entry block and: 1357 // - Move constants from the entry block to the outer_graph's entry block, 1358 // - Replace HParameterValue instructions with their real value. 1359 // - Remove suspend checks, that hold an environment. 1360 // We must do this after the other blocks have been inlined, otherwise ids of 1361 // constants could overlap with the inner graph. 1362 size_t parameter_index = 0; 1363 for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) { 1364 HInstruction* current = it.Current(); 1365 if (current->IsNullConstant()) { 1366 current->ReplaceWith(outer_graph->GetNullConstant()); 1367 } else if (current->IsIntConstant()) { 1368 current->ReplaceWith(outer_graph->GetIntConstant(current->AsIntConstant()->GetValue())); 1369 } else if (current->IsLongConstant()) { 1370 current->ReplaceWith(outer_graph->GetLongConstant(current->AsLongConstant()->GetValue())); 1371 } else if (current->IsFloatConstant()) { 1372 current->ReplaceWith(outer_graph->GetFloatConstant(current->AsFloatConstant()->GetValue())); 1373 } else if (current->IsDoubleConstant()) { 1374 current->ReplaceWith(outer_graph->GetDoubleConstant(current->AsDoubleConstant()->GetValue())); 1375 } else if (current->IsParameterValue()) { 1376 if (kIsDebugBuild 1377 && invoke->IsInvokeStaticOrDirect() 1378 && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) { 1379 // Ensure we do not use the last input of `invoke`, as it 1380 // contains a clinit check which is not an actual argument. 1381 size_t last_input_index = invoke->InputCount() - 1; 1382 DCHECK(parameter_index != last_input_index); 1383 } 1384 current->ReplaceWith(invoke->InputAt(parameter_index++)); 1385 } else { 1386 DCHECK(current->IsGoto() || current->IsSuspendCheck()); 1387 entry_block_->RemoveInstruction(current); 1388 } 1389 } 1390 1391 // Finally remove the invoke from the caller. 1392 invoke->GetBlock()->RemoveInstruction(invoke); 1393 } 1394 1395 /* 1396 * Loop will be transformed to: 1397 * old_pre_header 1398 * | 1399 * if_block 1400 * / \ 1401 * dummy_block deopt_block 1402 * \ / 1403 * new_pre_header 1404 * | 1405 * header 1406 */ 1407 void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) { 1408 DCHECK(header->IsLoopHeader()); 1409 HBasicBlock* pre_header = header->GetDominator(); 1410 1411 // Need this to avoid critical edge. 1412 HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 1413 // Need this to avoid critical edge. 1414 HBasicBlock* dummy_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 1415 HBasicBlock* deopt_block = new (arena_) HBasicBlock(this, header->GetDexPc()); 1416 HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 1417 AddBlock(if_block); 1418 AddBlock(dummy_block); 1419 AddBlock(deopt_block); 1420 AddBlock(new_pre_header); 1421 1422 header->ReplacePredecessor(pre_header, new_pre_header); 1423 pre_header->successors_.Reset(); 1424 pre_header->dominated_blocks_.Reset(); 1425 1426 pre_header->AddSuccessor(if_block); 1427 if_block->AddSuccessor(dummy_block); // True successor 1428 if_block->AddSuccessor(deopt_block); // False successor 1429 dummy_block->AddSuccessor(new_pre_header); 1430 deopt_block->AddSuccessor(new_pre_header); 1431 1432 pre_header->dominated_blocks_.Add(if_block); 1433 if_block->SetDominator(pre_header); 1434 if_block->dominated_blocks_.Add(dummy_block); 1435 dummy_block->SetDominator(if_block); 1436 if_block->dominated_blocks_.Add(deopt_block); 1437 deopt_block->SetDominator(if_block); 1438 if_block->dominated_blocks_.Add(new_pre_header); 1439 new_pre_header->SetDominator(if_block); 1440 new_pre_header->dominated_blocks_.Add(header); 1441 header->SetDominator(new_pre_header); 1442 1443 size_t index_of_header = 0; 1444 while (reverse_post_order_.Get(index_of_header) != header) { 1445 index_of_header++; 1446 } 1447 MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1); 1448 reverse_post_order_.Put(index_of_header++, if_block); 1449 reverse_post_order_.Put(index_of_header++, dummy_block); 1450 reverse_post_order_.Put(index_of_header++, deopt_block); 1451 reverse_post_order_.Put(index_of_header++, new_pre_header); 1452 1453 HLoopInformation* info = pre_header->GetLoopInformation(); 1454 if (info != nullptr) { 1455 if_block->SetLoopInformation(info); 1456 dummy_block->SetLoopInformation(info); 1457 deopt_block->SetLoopInformation(info); 1458 new_pre_header->SetLoopInformation(info); 1459 for (HLoopInformationOutwardIterator loop_it(*pre_header); 1460 !loop_it.Done(); 1461 loop_it.Advance()) { 1462 loop_it.Current()->Add(if_block); 1463 loop_it.Current()->Add(dummy_block); 1464 loop_it.Current()->Add(deopt_block); 1465 loop_it.Current()->Add(new_pre_header); 1466 } 1467 } 1468 } 1469 1470 std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) { 1471 ScopedObjectAccess soa(Thread::Current()); 1472 os << "[" 1473 << " is_top=" << rhs.IsTop() 1474 << " type=" << (rhs.IsTop() ? "?" : PrettyClass(rhs.GetTypeHandle().Get())) 1475 << " is_exact=" << rhs.IsExact() 1476 << " ]"; 1477 return os; 1478 } 1479 1480 } // namespace art 1481