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