nodes.cc revision 46e2a3915aa68c77426b71e95b9f3658250646b7
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 "utils/growable_array.h" 21#include "scoped_thread_state_change.h" 22 23namespace art { 24 25void HGraph::AddBlock(HBasicBlock* block) { 26 block->SetBlockId(blocks_.Size()); 27 blocks_.Add(block); 28} 29 30void HGraph::FindBackEdges(ArenaBitVector* visited) { 31 ArenaBitVector visiting(arena_, blocks_.Size(), false); 32 VisitBlockForBackEdges(entry_block_, visited, &visiting); 33} 34 35static void RemoveAsUser(HInstruction* instruction) { 36 for (size_t i = 0; i < instruction->InputCount(); i++) { 37 instruction->RemoveAsUserOfInput(i); 38 } 39 40 HEnvironment* environment = instruction->GetEnvironment(); 41 if (environment != nullptr) { 42 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 43 if (environment->GetInstructionAt(i) != nullptr) { 44 environment->RemoveAsUserOfInput(i); 45 } 46 } 47 } 48} 49 50void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const { 51 for (size_t i = 0; i < blocks_.Size(); ++i) { 52 if (!visited.IsBitSet(i)) { 53 HBasicBlock* block = blocks_.Get(i); 54 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 55 RemoveAsUser(it.Current()); 56 } 57 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 58 RemoveAsUser(it.Current()); 59 } 60 } 61 } 62} 63 64void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { 65 for (size_t i = 0; i < blocks_.Size(); ++i) { 66 if (!visited.IsBitSet(i)) { 67 HBasicBlock* block = blocks_.Get(i); 68 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 69 block->GetSuccessors().Get(j)->RemovePredecessor(block); 70 } 71 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 72 block->RemovePhi(it.Current()->AsPhi(), /*ensure_safety=*/ false); 73 } 74 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 75 block->RemoveInstruction(it.Current(), /*ensure_safety=*/ false); 76 } 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 // If there are more than one back edge, make them branch to the same block that 199 // will become the only back edge. This simplifies finding natural loops in the 200 // graph. 201 // Also, if the loop is a do/while (that is the back edge is an if), change the 202 // back edge to be a goto. This simplifies code generation of suspend cheks. 203 if (info->NumberOfBackEdges() > 1 || info->GetBackEdges().Get(0)->GetLastInstruction()->IsIf()) { 204 HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this, header->GetDexPc()); 205 AddBlock(new_back_edge); 206 new_back_edge->AddInstruction(new (arena_) HGoto()); 207 for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) { 208 HBasicBlock* back_edge = info->GetBackEdges().Get(pred); 209 back_edge->ReplaceSuccessor(header, new_back_edge); 210 } 211 info->ClearBackEdges(); 212 info->AddBackEdge(new_back_edge); 213 new_back_edge->AddSuccessor(header); 214 } 215 216 // Make sure the loop has only one pre header. This simplifies SSA building by having 217 // to just look at the pre header to know which locals are initialized at entry of the 218 // loop. 219 size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges(); 220 if (number_of_incomings != 1) { 221 HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 222 AddBlock(pre_header); 223 pre_header->AddInstruction(new (arena_) HGoto()); 224 225 ArenaBitVector back_edges(arena_, GetBlocks().Size(), false); 226 HBasicBlock* back_edge = info->GetBackEdges().Get(0); 227 for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { 228 HBasicBlock* predecessor = header->GetPredecessors().Get(pred); 229 if (predecessor != back_edge) { 230 predecessor->ReplaceSuccessor(header, pre_header); 231 pred--; 232 } 233 } 234 pre_header->AddSuccessor(header); 235 } 236 237 // Make sure the second predecessor of a loop header is the back edge. 238 if (header->GetPredecessors().Get(1) != info->GetBackEdges().Get(0)) { 239 header->SwapPredecessors(); 240 } 241 242 // Place the suspend check at the beginning of the header, so that live registers 243 // will be known when allocating registers. Note that code generation can still 244 // generate the suspend check at the back edge, but needs to be careful with 245 // loop phi spill slots (which are not written to at back edge). 246 HInstruction* first_instruction = header->GetFirstInstruction(); 247 if (!first_instruction->IsSuspendCheck()) { 248 HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc()); 249 header->InsertInstructionBefore(check, first_instruction); 250 first_instruction = check; 251 } 252 info->SetSuspendCheck(first_instruction->AsSuspendCheck()); 253} 254 255void HGraph::SimplifyCFG() { 256 // Simplify the CFG for future analysis, and code generation: 257 // (1): Split critical edges. 258 // (2): Simplify loops by having only one back edge, and one preheader. 259 for (size_t i = 0; i < blocks_.Size(); ++i) { 260 HBasicBlock* block = blocks_.Get(i); 261 if (block->GetSuccessors().Size() > 1) { 262 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 263 HBasicBlock* successor = block->GetSuccessors().Get(j); 264 if (successor->GetPredecessors().Size() > 1) { 265 SplitCriticalEdge(block, successor); 266 --j; 267 } 268 } 269 } 270 if (block->IsLoopHeader()) { 271 SimplifyLoop(block); 272 } 273 } 274} 275 276bool HGraph::AnalyzeNaturalLoops() const { 277 for (size_t i = 0; i < blocks_.Size(); ++i) { 278 HBasicBlock* block = blocks_.Get(i); 279 if (block->IsLoopHeader()) { 280 HLoopInformation* info = block->GetLoopInformation(); 281 if (!info->Populate()) { 282 // Abort if the loop is non natural. We currently bailout in such cases. 283 return false; 284 } 285 } 286 } 287 return true; 288} 289 290void HGraph::AddConstant(HConstant* instruction) { 291 HInstruction* last_instruction = entry_block_->GetLastInstruction(); 292 if (last_instruction == nullptr || !last_instruction->IsControlFlow()) { 293 // Called from the builder. Insert at the end of the block. 294 entry_block_->AddInstruction(instruction); 295 } else { 296 // Entry block ends with control-flow. Insert before the last instruction. 297 entry_block_->InsertInstructionBefore(instruction, last_instruction); 298 } 299} 300 301HNullConstant* HGraph::GetNullConstant() { 302 if (cached_null_constant_ == nullptr) { 303 cached_null_constant_ = new (arena_) HNullConstant(); 304 AddConstant(cached_null_constant_); 305 } 306 return cached_null_constant_; 307} 308 309HIntConstant* HGraph::GetIntConstant0() { 310 if (cached_int_constant0_ == nullptr) { 311 cached_int_constant0_ = new (arena_) HIntConstant(0); 312 AddConstant(cached_int_constant0_); 313 } 314 return cached_int_constant0_; 315} 316 317HIntConstant* HGraph::GetIntConstant1() { 318 if (cached_int_constant1_ == nullptr) { 319 cached_int_constant1_ = new (arena_) HIntConstant(1); 320 AddConstant(cached_int_constant1_); 321 } 322 return cached_int_constant1_; 323} 324 325void HLoopInformation::Add(HBasicBlock* block) { 326 blocks_.SetBit(block->GetBlockId()); 327} 328 329void HLoopInformation::Remove(HBasicBlock* block) { 330 blocks_.ClearBit(block->GetBlockId()); 331} 332 333void HLoopInformation::PopulateRecursive(HBasicBlock* block) { 334 if (blocks_.IsBitSet(block->GetBlockId())) { 335 return; 336 } 337 338 blocks_.SetBit(block->GetBlockId()); 339 block->SetInLoop(this); 340 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 341 PopulateRecursive(block->GetPredecessors().Get(i)); 342 } 343} 344 345bool HLoopInformation::Populate() { 346 DCHECK_EQ(GetBackEdges().Size(), 1u); 347 HBasicBlock* back_edge = GetBackEdges().Get(0); 348 DCHECK(back_edge->GetDominator() != nullptr); 349 if (!header_->Dominates(back_edge)) { 350 // This loop is not natural. Do not bother going further. 351 return false; 352 } 353 354 // Populate this loop: starting with the back edge, recursively add predecessors 355 // that are not already part of that loop. Set the header as part of the loop 356 // to end the recursion. 357 // This is a recursive implementation of the algorithm described in 358 // "Advanced Compiler Design & Implementation" (Muchnick) p192. 359 blocks_.SetBit(header_->GetBlockId()); 360 PopulateRecursive(back_edge); 361 return true; 362} 363 364HBasicBlock* HLoopInformation::GetPreHeader() const { 365 DCHECK_EQ(header_->GetPredecessors().Size(), 2u); 366 return header_->GetDominator(); 367} 368 369bool HLoopInformation::Contains(const HBasicBlock& block) const { 370 return blocks_.IsBitSet(block.GetBlockId()); 371} 372 373bool HLoopInformation::IsIn(const HLoopInformation& other) const { 374 return other.blocks_.IsBitSet(header_->GetBlockId()); 375} 376 377bool HBasicBlock::Dominates(HBasicBlock* other) const { 378 // Walk up the dominator tree from `other`, to find out if `this` 379 // is an ancestor. 380 HBasicBlock* current = other; 381 while (current != nullptr) { 382 if (current == this) { 383 return true; 384 } 385 current = current->GetDominator(); 386 } 387 return false; 388} 389 390static void UpdateInputsUsers(HInstruction* instruction) { 391 for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { 392 instruction->InputAt(i)->AddUseAt(instruction, i); 393 } 394 // Environment should be created later. 395 DCHECK(!instruction->HasEnvironment()); 396} 397 398void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 399 DCHECK(!cursor->IsPhi()); 400 DCHECK(!instruction->IsPhi()); 401 DCHECK_EQ(instruction->GetId(), -1); 402 DCHECK_NE(cursor->GetId(), -1); 403 DCHECK_EQ(cursor->GetBlock(), this); 404 DCHECK(!instruction->IsControlFlow()); 405 instruction->next_ = cursor; 406 instruction->previous_ = cursor->previous_; 407 cursor->previous_ = instruction; 408 if (GetFirstInstruction() == cursor) { 409 instructions_.first_instruction_ = instruction; 410 } else { 411 instruction->previous_->next_ = instruction; 412 } 413 instruction->SetBlock(this); 414 instruction->SetId(GetGraph()->GetNextInstructionId()); 415 UpdateInputsUsers(instruction); 416} 417 418void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, 419 HInstruction* replacement) { 420 DCHECK(initial->GetBlock() == this); 421 InsertInstructionBefore(replacement, initial); 422 initial->ReplaceWith(replacement); 423 RemoveInstruction(initial); 424} 425 426static void Add(HInstructionList* instruction_list, 427 HBasicBlock* block, 428 HInstruction* instruction) { 429 DCHECK(instruction->GetBlock() == nullptr); 430 DCHECK_EQ(instruction->GetId(), -1); 431 instruction->SetBlock(block); 432 instruction->SetId(block->GetGraph()->GetNextInstructionId()); 433 UpdateInputsUsers(instruction); 434 instruction_list->AddInstruction(instruction); 435} 436 437void HBasicBlock::AddInstruction(HInstruction* instruction) { 438 Add(&instructions_, this, instruction); 439} 440 441void HBasicBlock::AddPhi(HPhi* phi) { 442 Add(&phis_, this, phi); 443} 444 445void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) { 446 DCHECK_EQ(phi->GetId(), -1); 447 DCHECK_NE(cursor->GetId(), -1); 448 DCHECK_EQ(cursor->GetBlock(), this); 449 if (cursor->next_ == nullptr) { 450 cursor->next_ = phi; 451 phi->previous_ = cursor; 452 DCHECK(phi->next_ == nullptr); 453 } else { 454 phi->next_ = cursor->next_; 455 phi->previous_ = cursor; 456 cursor->next_ = phi; 457 phi->next_->previous_ = phi; 458 } 459 phi->SetBlock(this); 460 phi->SetId(GetGraph()->GetNextInstructionId()); 461 UpdateInputsUsers(phi); 462} 463 464static void Remove(HInstructionList* instruction_list, 465 HBasicBlock* block, 466 HInstruction* instruction, 467 bool ensure_safety) { 468 DCHECK_EQ(block, instruction->GetBlock()); 469 instruction->SetBlock(nullptr); 470 instruction_list->RemoveInstruction(instruction); 471 if (ensure_safety) { 472 DCHECK(instruction->GetUses().IsEmpty()); 473 DCHECK(instruction->GetEnvUses().IsEmpty()); 474 RemoveAsUser(instruction); 475 } 476} 477 478void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) { 479 Remove(&instructions_, this, instruction, ensure_safety); 480} 481 482void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) { 483 Remove(&phis_, this, phi, ensure_safety); 484} 485 486void HEnvironment::CopyFrom(HEnvironment* env) { 487 for (size_t i = 0; i < env->Size(); i++) { 488 HInstruction* instruction = env->GetInstructionAt(i); 489 SetRawEnvAt(i, instruction); 490 if (instruction != nullptr) { 491 instruction->AddEnvUseAt(this, i); 492 } 493 } 494} 495 496void HEnvironment::RemoveAsUserOfInput(size_t index) const { 497 const HUserRecord<HEnvironment*> user_record = vregs_.Get(index); 498 user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode()); 499} 500 501HInstruction* HInstruction::GetNextDisregardingMoves() const { 502 HInstruction* next = GetNext(); 503 while (next != nullptr && next->IsParallelMove()) { 504 next = next->GetNext(); 505 } 506 return next; 507} 508 509HInstruction* HInstruction::GetPreviousDisregardingMoves() const { 510 HInstruction* previous = GetPrevious(); 511 while (previous != nullptr && previous->IsParallelMove()) { 512 previous = previous->GetPrevious(); 513 } 514 return previous; 515} 516 517void HInstructionList::AddInstruction(HInstruction* instruction) { 518 if (first_instruction_ == nullptr) { 519 DCHECK(last_instruction_ == nullptr); 520 first_instruction_ = last_instruction_ = instruction; 521 } else { 522 last_instruction_->next_ = instruction; 523 instruction->previous_ = last_instruction_; 524 last_instruction_ = instruction; 525 } 526} 527 528void HInstructionList::RemoveInstruction(HInstruction* instruction) { 529 if (instruction->previous_ != nullptr) { 530 instruction->previous_->next_ = instruction->next_; 531 } 532 if (instruction->next_ != nullptr) { 533 instruction->next_->previous_ = instruction->previous_; 534 } 535 if (instruction == first_instruction_) { 536 first_instruction_ = instruction->next_; 537 } 538 if (instruction == last_instruction_) { 539 last_instruction_ = instruction->previous_; 540 } 541} 542 543bool HInstructionList::Contains(HInstruction* instruction) const { 544 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 545 if (it.Current() == instruction) { 546 return true; 547 } 548 } 549 return false; 550} 551 552bool HInstructionList::FoundBefore(const HInstruction* instruction1, 553 const HInstruction* instruction2) const { 554 DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock()); 555 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 556 if (it.Current() == instruction1) { 557 return true; 558 } 559 if (it.Current() == instruction2) { 560 return false; 561 } 562 } 563 LOG(FATAL) << "Did not find an order between two instructions of the same block."; 564 return true; 565} 566 567bool HInstruction::StrictlyDominates(HInstruction* other_instruction) const { 568 if (other_instruction == this) { 569 // An instruction does not strictly dominate itself. 570 return false; 571 } 572 HBasicBlock* block = GetBlock(); 573 HBasicBlock* other_block = other_instruction->GetBlock(); 574 if (block != other_block) { 575 return GetBlock()->Dominates(other_instruction->GetBlock()); 576 } else { 577 // If both instructions are in the same block, ensure this 578 // instruction comes before `other_instruction`. 579 if (IsPhi()) { 580 if (!other_instruction->IsPhi()) { 581 // Phis appear before non phi-instructions so this instruction 582 // dominates `other_instruction`. 583 return true; 584 } else { 585 // There is no order among phis. 586 LOG(FATAL) << "There is no dominance between phis of a same block."; 587 return false; 588 } 589 } else { 590 // `this` is not a phi. 591 if (other_instruction->IsPhi()) { 592 // Phis appear before non phi-instructions so this instruction 593 // does not dominate `other_instruction`. 594 return false; 595 } else { 596 // Check whether this instruction comes before 597 // `other_instruction` in the instruction list. 598 return block->GetInstructions().FoundBefore(this, other_instruction); 599 } 600 } 601 } 602} 603 604void HInstruction::ReplaceWith(HInstruction* other) { 605 DCHECK(other != nullptr); 606 for (HUseIterator<HInstruction*> it(GetUses()); !it.Done(); it.Advance()) { 607 HUseListNode<HInstruction*>* current = it.Current(); 608 HInstruction* user = current->GetUser(); 609 size_t input_index = current->GetIndex(); 610 user->SetRawInputAt(input_index, other); 611 other->AddUseAt(user, input_index); 612 } 613 614 for (HUseIterator<HEnvironment*> it(GetEnvUses()); !it.Done(); it.Advance()) { 615 HUseListNode<HEnvironment*>* current = it.Current(); 616 HEnvironment* user = current->GetUser(); 617 size_t input_index = current->GetIndex(); 618 user->SetRawEnvAt(input_index, other); 619 other->AddEnvUseAt(user, input_index); 620 } 621 622 uses_.Clear(); 623 env_uses_.Clear(); 624} 625 626void HInstruction::ReplaceInput(HInstruction* replacement, size_t index) { 627 RemoveAsUserOfInput(index); 628 SetRawInputAt(index, replacement); 629 replacement->AddUseAt(this, index); 630} 631 632size_t HInstruction::EnvironmentSize() const { 633 return HasEnvironment() ? environment_->Size() : 0; 634} 635 636void HPhi::AddInput(HInstruction* input) { 637 DCHECK(input->GetBlock() != nullptr); 638 inputs_.Add(HUserRecord<HInstruction*>(input)); 639 input->AddUseAt(this, inputs_.Size() - 1); 640} 641 642#define DEFINE_ACCEPT(name, super) \ 643void H##name::Accept(HGraphVisitor* visitor) { \ 644 visitor->Visit##name(this); \ 645} 646 647FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) 648 649#undef DEFINE_ACCEPT 650 651void HGraphVisitor::VisitInsertionOrder() { 652 const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks(); 653 for (size_t i = 0 ; i < blocks.Size(); i++) { 654 HBasicBlock* block = blocks.Get(i); 655 if (block != nullptr) { 656 VisitBasicBlock(block); 657 } 658 } 659} 660 661void HGraphVisitor::VisitReversePostOrder() { 662 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 663 VisitBasicBlock(it.Current()); 664 } 665} 666 667void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { 668 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 669 it.Current()->Accept(this); 670 } 671 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 672 it.Current()->Accept(this); 673 } 674} 675 676HConstant* HUnaryOperation::TryStaticEvaluation() const { 677 if (GetInput()->IsIntConstant()) { 678 int32_t value = Evaluate(GetInput()->AsIntConstant()->GetValue()); 679 return new(GetBlock()->GetGraph()->GetArena()) HIntConstant(value); 680 } else if (GetInput()->IsLongConstant()) { 681 // TODO: Implement static evaluation of long unary operations. 682 // 683 // Do not exit with a fatal condition here. Instead, simply 684 // return `nullptr' to notify the caller that this instruction 685 // cannot (yet) be statically evaluated. 686 return nullptr; 687 } 688 return nullptr; 689} 690 691HConstant* HBinaryOperation::TryStaticEvaluation() const { 692 if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) { 693 int32_t value = Evaluate(GetLeft()->AsIntConstant()->GetValue(), 694 GetRight()->AsIntConstant()->GetValue()); 695 return new(GetBlock()->GetGraph()->GetArena()) HIntConstant(value); 696 } else if (GetLeft()->IsLongConstant() && GetRight()->IsLongConstant()) { 697 int64_t value = Evaluate(GetLeft()->AsLongConstant()->GetValue(), 698 GetRight()->AsLongConstant()->GetValue()); 699 if (GetResultType() == Primitive::kPrimLong) { 700 return new(GetBlock()->GetGraph()->GetArena()) HLongConstant(value); 701 } else { 702 DCHECK_EQ(GetResultType(), Primitive::kPrimInt); 703 return new(GetBlock()->GetGraph()->GetArena()) HIntConstant(value); 704 } 705 } 706 return nullptr; 707} 708 709HConstant* HBinaryOperation::GetConstantRight() const { 710 if (GetRight()->IsConstant()) { 711 return GetRight()->AsConstant(); 712 } else if (IsCommutative() && GetLeft()->IsConstant()) { 713 return GetLeft()->AsConstant(); 714 } else { 715 return nullptr; 716 } 717} 718 719// If `GetConstantRight()` returns one of the input, this returns the other 720// one. Otherwise it returns nullptr. 721HInstruction* HBinaryOperation::GetLeastConstantLeft() const { 722 HInstruction* most_constant_right = GetConstantRight(); 723 if (most_constant_right == nullptr) { 724 return nullptr; 725 } else if (most_constant_right == GetLeft()) { 726 return GetRight(); 727 } else { 728 return GetLeft(); 729 } 730} 731 732bool HCondition::IsBeforeWhenDisregardMoves(HIf* if_) const { 733 return this == if_->GetPreviousDisregardingMoves(); 734} 735 736HConstant* HConstant::NewConstant(ArenaAllocator* allocator, Primitive::Type type, int64_t val) { 737 if (type == Primitive::kPrimInt) { 738 DCHECK(IsInt<32>(val)); 739 return new (allocator) HIntConstant(val); 740 } else { 741 DCHECK_EQ(type, Primitive::kPrimLong); 742 return new (allocator) HLongConstant(val); 743 } 744} 745 746bool HInstruction::Equals(HInstruction* other) const { 747 if (!InstructionTypeEquals(other)) return false; 748 DCHECK_EQ(GetKind(), other->GetKind()); 749 if (!InstructionDataEquals(other)) return false; 750 if (GetType() != other->GetType()) return false; 751 if (InputCount() != other->InputCount()) return false; 752 753 for (size_t i = 0, e = InputCount(); i < e; ++i) { 754 if (InputAt(i) != other->InputAt(i)) return false; 755 } 756 DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode()); 757 return true; 758} 759 760std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind& rhs) { 761#define DECLARE_CASE(type, super) case HInstruction::k##type: os << #type; break; 762 switch (rhs) { 763 FOR_EACH_INSTRUCTION(DECLARE_CASE) 764 default: 765 os << "Unknown instruction kind " << static_cast<int>(rhs); 766 break; 767 } 768#undef DECLARE_CASE 769 return os; 770} 771 772void HInstruction::MoveBefore(HInstruction* cursor) { 773 next_->previous_ = previous_; 774 if (previous_ != nullptr) { 775 previous_->next_ = next_; 776 } 777 if (block_->instructions_.first_instruction_ == this) { 778 block_->instructions_.first_instruction_ = next_; 779 } 780 DCHECK_NE(block_->instructions_.last_instruction_, this); 781 782 previous_ = cursor->previous_; 783 if (previous_ != nullptr) { 784 previous_->next_ = this; 785 } 786 next_ = cursor; 787 cursor->previous_ = this; 788 block_ = cursor->block_; 789 790 if (block_->instructions_.first_instruction_ == cursor) { 791 block_->instructions_.first_instruction_ = this; 792 } 793} 794 795HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) { 796 DCHECK(!cursor->IsControlFlow()); 797 DCHECK_NE(instructions_.last_instruction_, cursor); 798 DCHECK_EQ(cursor->GetBlock(), this); 799 800 HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc()); 801 new_block->instructions_.first_instruction_ = cursor->GetNext(); 802 new_block->instructions_.last_instruction_ = instructions_.last_instruction_; 803 cursor->next_->previous_ = nullptr; 804 cursor->next_ = nullptr; 805 instructions_.last_instruction_ = cursor; 806 807 new_block->instructions_.SetBlockOfInstructions(new_block); 808 for (size_t i = 0, e = GetSuccessors().Size(); i < e; ++i) { 809 HBasicBlock* successor = GetSuccessors().Get(i); 810 new_block->successors_.Add(successor); 811 successor->predecessors_.Put(successor->GetPredecessorIndexOf(this), new_block); 812 } 813 successors_.Reset(); 814 815 for (size_t i = 0, e = GetDominatedBlocks().Size(); i < e; ++i) { 816 HBasicBlock* dominated = GetDominatedBlocks().Get(i); 817 dominated->dominator_ = new_block; 818 new_block->dominated_blocks_.Add(dominated); 819 } 820 dominated_blocks_.Reset(); 821 return new_block; 822} 823 824bool HBasicBlock::IsSingleGoto() const { 825 HLoopInformation* loop_info = GetLoopInformation(); 826 // TODO: Remove the null check b/19084197. 827 return GetFirstInstruction() != nullptr 828 && GetPhis().IsEmpty() 829 && GetFirstInstruction() == GetLastInstruction() 830 && GetLastInstruction()->IsGoto() 831 // Back edges generate the suspend check. 832 && (loop_info == nullptr || !loop_info->IsBackEdge(*this)); 833} 834 835void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const { 836 for (HInstruction* current = first_instruction_; 837 current != nullptr; 838 current = current->GetNext()) { 839 current->SetBlock(block); 840 } 841} 842 843void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) { 844 DCHECK(Contains(cursor)); 845 if (!instruction_list.IsEmpty()) { 846 if (cursor == last_instruction_) { 847 last_instruction_ = instruction_list.last_instruction_; 848 } else { 849 cursor->next_->previous_ = instruction_list.last_instruction_; 850 } 851 instruction_list.last_instruction_->next_ = cursor->next_; 852 cursor->next_ = instruction_list.first_instruction_; 853 instruction_list.first_instruction_->previous_ = cursor; 854 } 855} 856 857void HInstructionList::Add(const HInstructionList& instruction_list) { 858 if (IsEmpty()) { 859 first_instruction_ = instruction_list.first_instruction_; 860 last_instruction_ = instruction_list.last_instruction_; 861 } else { 862 AddAfter(last_instruction_, instruction_list); 863 } 864} 865 866void HBasicBlock::DisconnectFromAll() { 867 DCHECK(dominated_blocks_.IsEmpty()) << "Unimplemented scenario"; 868 869 for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { 870 predecessors_.Get(i)->successors_.Delete(this); 871 } 872 for (size_t i = 0, e = successors_.Size(); i < e; ++i) { 873 successors_.Get(i)->predecessors_.Delete(this); 874 } 875 dominator_->dominated_blocks_.Delete(this); 876 877 predecessors_.Reset(); 878 successors_.Reset(); 879 dominator_ = nullptr; 880 graph_ = nullptr; 881} 882 883void HBasicBlock::MergeWith(HBasicBlock* other) { 884 DCHECK(successors_.IsEmpty()) << "Unimplemented block merge scenario"; 885 DCHECK(dominated_blocks_.IsEmpty() 886 || (dominated_blocks_.Size() == 1 && dominated_blocks_.Get(0) == other)) 887 << "Unimplemented block merge scenario"; 888 DCHECK(other->GetPhis().IsEmpty()); 889 890 successors_.Reset(); 891 dominated_blocks_.Reset(); 892 instructions_.Add(other->GetInstructions()); 893 other->GetInstructions().SetBlockOfInstructions(this); 894 895 while (!other->GetSuccessors().IsEmpty()) { 896 HBasicBlock* successor = other->GetSuccessors().Get(0); 897 successor->ReplacePredecessor(other, this); 898 } 899 900 for (size_t i = 0, e = other->GetDominatedBlocks().Size(); i < e; ++i) { 901 HBasicBlock* dominated = other->GetDominatedBlocks().Get(i); 902 dominated_blocks_.Add(dominated); 903 dominated->SetDominator(this); 904 } 905 other->dominated_blocks_.Reset(); 906 other->dominator_ = nullptr; 907 other->graph_ = nullptr; 908} 909 910void HBasicBlock::ReplaceWith(HBasicBlock* other) { 911 while (!GetPredecessors().IsEmpty()) { 912 HBasicBlock* predecessor = GetPredecessors().Get(0); 913 predecessor->ReplaceSuccessor(this, other); 914 } 915 while (!GetSuccessors().IsEmpty()) { 916 HBasicBlock* successor = GetSuccessors().Get(0); 917 successor->ReplacePredecessor(this, other); 918 } 919 for (size_t i = 0; i < dominated_blocks_.Size(); ++i) { 920 other->AddDominatedBlock(dominated_blocks_.Get(i)); 921 } 922 GetDominator()->ReplaceDominatedBlock(this, other); 923 other->SetDominator(GetDominator()); 924 dominator_ = nullptr; 925 graph_ = nullptr; 926} 927 928// Create space in `blocks` for adding `number_of_new_blocks` entries 929// starting at location `at`. Blocks after `at` are moved accordingly. 930static void MakeRoomFor(GrowableArray<HBasicBlock*>* blocks, 931 size_t number_of_new_blocks, 932 size_t at) { 933 size_t old_size = blocks->Size(); 934 size_t new_size = old_size + number_of_new_blocks; 935 blocks->SetSize(new_size); 936 for (size_t i = old_size - 1, j = new_size - 1; i > at; --i, --j) { 937 blocks->Put(j, blocks->Get(i)); 938 } 939} 940 941void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { 942 // Walk over the entry block and: 943 // - Move constants from the entry block to the outer_graph's entry block, 944 // - Replace HParameterValue instructions with their real value. 945 // - Remove suspend checks, that hold an environment. 946 int parameter_index = 0; 947 for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) { 948 HInstruction* current = it.Current(); 949 if (current->IsConstant()) { 950 current->MoveBefore(outer_graph->GetEntryBlock()->GetLastInstruction()); 951 } else if (current->IsParameterValue()) { 952 current->ReplaceWith(invoke->InputAt(parameter_index++)); 953 } else { 954 DCHECK(current->IsGoto() || current->IsSuspendCheck()); 955 entry_block_->RemoveInstruction(current); 956 } 957 } 958 959 if (GetBlocks().Size() == 3) { 960 // Simple case of an entry block, a body block, and an exit block. 961 // Put the body block's instruction into `invoke`'s block. 962 HBasicBlock* body = GetBlocks().Get(1); 963 DCHECK(GetBlocks().Get(0)->IsEntryBlock()); 964 DCHECK(GetBlocks().Get(2)->IsExitBlock()); 965 DCHECK(!body->IsExitBlock()); 966 HInstruction* last = body->GetLastInstruction(); 967 968 invoke->GetBlock()->instructions_.AddAfter(invoke, body->GetInstructions()); 969 body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock()); 970 971 // Replace the invoke with the return value of the inlined graph. 972 if (last->IsReturn()) { 973 invoke->ReplaceWith(last->InputAt(0)); 974 } else { 975 DCHECK(last->IsReturnVoid()); 976 } 977 978 invoke->GetBlock()->RemoveInstruction(last); 979 } else { 980 // Need to inline multiple blocks. We split `invoke`'s block 981 // into two blocks, merge the first block of the inlined graph into 982 // the first half, and replace the exit block of the inlined graph 983 // with the second half. 984 ArenaAllocator* allocator = outer_graph->GetArena(); 985 HBasicBlock* at = invoke->GetBlock(); 986 HBasicBlock* to = at->SplitAfter(invoke); 987 988 HBasicBlock* first = entry_block_->GetSuccessors().Get(0); 989 DCHECK(!first->IsInLoop()); 990 at->MergeWith(first); 991 exit_block_->ReplaceWith(to); 992 993 // Update all predecessors of the exit block (now the `to` block) 994 // to not `HReturn` but `HGoto` instead. 995 HInstruction* return_value = nullptr; 996 bool returns_void = to->GetPredecessors().Get(0)->GetLastInstruction()->IsReturnVoid(); 997 if (to->GetPredecessors().Size() == 1) { 998 HBasicBlock* predecessor = to->GetPredecessors().Get(0); 999 HInstruction* last = predecessor->GetLastInstruction(); 1000 if (!returns_void) { 1001 return_value = last->InputAt(0); 1002 } 1003 predecessor->AddInstruction(new (allocator) HGoto()); 1004 predecessor->RemoveInstruction(last); 1005 } else { 1006 if (!returns_void) { 1007 // There will be multiple returns. 1008 return_value = new (allocator) HPhi( 1009 allocator, kNoRegNumber, 0, HPhi::ToPhiType(invoke->GetType())); 1010 to->AddPhi(return_value->AsPhi()); 1011 } 1012 for (size_t i = 0, e = to->GetPredecessors().Size(); i < e; ++i) { 1013 HBasicBlock* predecessor = to->GetPredecessors().Get(i); 1014 HInstruction* last = predecessor->GetLastInstruction(); 1015 if (!returns_void) { 1016 return_value->AsPhi()->AddInput(last->InputAt(0)); 1017 } 1018 predecessor->AddInstruction(new (allocator) HGoto()); 1019 predecessor->RemoveInstruction(last); 1020 } 1021 } 1022 1023 if (return_value != nullptr) { 1024 invoke->ReplaceWith(return_value); 1025 } 1026 1027 // Update the meta information surrounding blocks: 1028 // (1) the graph they are now in, 1029 // (2) the reverse post order of that graph, 1030 // (3) the potential loop information they are now in. 1031 1032 // We don't add the entry block, the exit block, and the first block, which 1033 // has been merged with `at`. 1034 static constexpr int kNumberOfSkippedBlocksInCallee = 3; 1035 1036 // We add the `to` block. 1037 static constexpr int kNumberOfNewBlocksInCaller = 1; 1038 size_t blocks_added = (reverse_post_order_.Size() - kNumberOfSkippedBlocksInCallee) 1039 + kNumberOfNewBlocksInCaller; 1040 1041 // Find the location of `at` in the outer graph's reverse post order. The new 1042 // blocks will be added after it. 1043 size_t index_of_at = 0; 1044 while (outer_graph->reverse_post_order_.Get(index_of_at) != at) { 1045 index_of_at++; 1046 } 1047 MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at); 1048 1049 // Do a reverse post order of the blocks in the callee and do (1), (2), 1050 // and (3) to the blocks that apply. 1051 HLoopInformation* info = at->GetLoopInformation(); 1052 for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) { 1053 HBasicBlock* current = it.Current(); 1054 if (current != exit_block_ && current != entry_block_ && current != first) { 1055 DCHECK(!current->IsInLoop()); 1056 DCHECK(current->GetGraph() == this); 1057 current->SetGraph(outer_graph); 1058 outer_graph->AddBlock(current); 1059 outer_graph->reverse_post_order_.Put(++index_of_at, current); 1060 if (info != nullptr) { 1061 info->Add(current); 1062 current->SetLoopInformation(info); 1063 } 1064 } 1065 } 1066 1067 // Do (1), (2), and (3) to `to`. 1068 to->SetGraph(outer_graph); 1069 outer_graph->AddBlock(to); 1070 outer_graph->reverse_post_order_.Put(++index_of_at, to); 1071 if (info != nullptr) { 1072 info->Add(to); 1073 to->SetLoopInformation(info); 1074 if (info->IsBackEdge(*at)) { 1075 // Only `at` can become a back edge, as the inlined blocks 1076 // are predecessors of `at`. 1077 DCHECK_EQ(1u, info->NumberOfBackEdges()); 1078 info->ClearBackEdges(); 1079 info->AddBackEdge(to); 1080 } 1081 } 1082 } 1083 1084 // Finally remove the invoke from the caller. 1085 invoke->GetBlock()->RemoveInstruction(invoke); 1086} 1087 1088void HGraph::MergeEmptyBranches(HBasicBlock* start_block, HBasicBlock* end_block) { 1089 // Make sure this is a diamond control-flow path, find the two branches. 1090 DCHECK_EQ(start_block->GetSuccessors().Size(), 2u); 1091 DCHECK_EQ(end_block->GetPredecessors().Size(), 2u); 1092 HBasicBlock* left_branch = start_block->GetSuccessors().Get(0); 1093 HBasicBlock* right_branch = start_block->GetSuccessors().Get(1); 1094 DCHECK_EQ(left_branch->GetSuccessors().Get(0), end_block); 1095 DCHECK_EQ(right_branch->GetSuccessors().Get(0), end_block); 1096 DCHECK_EQ(start_block, end_block->GetDominator()); 1097 1098 // Disconnect the branches and merge the two blocks. This will move 1099 // all instructions from 'end_block' to 'start_block'. 1100 DCHECK(left_branch->IsSingleGoto()); 1101 DCHECK(right_branch->IsSingleGoto()); 1102 left_branch->DisconnectFromAll(); 1103 right_branch->DisconnectFromAll(); 1104 start_block->RemoveInstruction(start_block->GetLastInstruction()); 1105 start_block->MergeWith(end_block); 1106 1107 // Delete the now redundant blocks from the graph. 1108 blocks_.Put(left_branch->GetBlockId(), nullptr); 1109 blocks_.Put(right_branch->GetBlockId(), nullptr); 1110 blocks_.Put(end_block->GetBlockId(), nullptr); 1111 1112 // Update reverse post order. 1113 reverse_post_order_.Delete(left_branch); 1114 reverse_post_order_.Delete(right_branch); 1115 reverse_post_order_.Delete(end_block); 1116 1117 // Update loop information. 1118 HLoopInformation* loop_info = start_block->GetLoopInformation(); 1119 if (kIsDebugBuild) { 1120 if (loop_info != nullptr) { 1121 DCHECK_EQ(loop_info, left_branch->GetLoopInformation()); 1122 DCHECK_EQ(loop_info, right_branch->GetLoopInformation()); 1123 DCHECK_EQ(loop_info, end_block->GetLoopInformation()); 1124 } 1125 } 1126 while (loop_info != nullptr) { 1127 loop_info->Remove(left_branch); 1128 loop_info->Remove(right_branch); 1129 loop_info->Remove(end_block); 1130 if (loop_info->IsBackEdge(*end_block)) { 1131 loop_info->RemoveBackEdge(end_block); 1132 loop_info->AddBackEdge(start_block); 1133 } 1134 // Move to parent loop if nested. 1135 loop_info = loop_info->GetHeader()->GetDominator()->GetLoopInformation(); 1136 } 1137} 1138 1139std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) { 1140 ScopedObjectAccess soa(Thread::Current()); 1141 os << "[" 1142 << " is_top=" << rhs.IsTop() 1143 << " type=" << (rhs.IsTop() ? "?" : PrettyClass(rhs.GetTypeHandle().Get())) 1144 << " is_exact=" << rhs.IsExact() 1145 << " ]"; 1146 return os; 1147} 1148 1149} // namespace art 1150