nodes.cc revision 3c04974a90b0e03f4b509010bff49f0b2a3da57f
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#include "ssa_builder.h" 19#include "utils/growable_array.h" 20 21namespace art { 22 23void HGraph::AddBlock(HBasicBlock* block) { 24 block->SetBlockId(blocks_.Size()); 25 blocks_.Add(block); 26} 27 28void HGraph::FindBackEdges(ArenaBitVector* visited) { 29 ArenaBitVector visiting(arena_, blocks_.Size(), false); 30 VisitBlockForBackEdges(entry_block_, visited, &visiting); 31} 32 33void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { 34 for (size_t i = 0; i < blocks_.Size(); ++i) { 35 if (!visited.IsBitSet(i)) { 36 HBasicBlock* block = blocks_.Get(i); 37 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 38 block->GetSuccessors().Get(j)->RemovePredecessor(block); 39 } 40 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 41 block->RemovePhi(it.Current()->AsPhi()); 42 } 43 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 44 block->RemoveInstruction(it.Current()); 45 } 46 } 47 } 48} 49 50void HGraph::VisitBlockForBackEdges(HBasicBlock* block, 51 ArenaBitVector* visited, 52 ArenaBitVector* visiting) { 53 int id = block->GetBlockId(); 54 if (visited->IsBitSet(id)) return; 55 56 visited->SetBit(id); 57 visiting->SetBit(id); 58 for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { 59 HBasicBlock* successor = block->GetSuccessors().Get(i); 60 if (visiting->IsBitSet(successor->GetBlockId())) { 61 successor->AddBackEdge(block); 62 } else { 63 VisitBlockForBackEdges(successor, visited, visiting); 64 } 65 } 66 visiting->ClearBit(id); 67} 68 69void HGraph::BuildDominatorTree() { 70 ArenaBitVector visited(arena_, blocks_.Size(), false); 71 72 // (1) Find the back edges in the graph doing a DFS traversal. 73 FindBackEdges(&visited); 74 75 // (2) Remove blocks not visited during the initial DFS. 76 // Step (3) requires dead blocks to be removed from the 77 // predecessors list of live blocks. 78 RemoveDeadBlocks(visited); 79 80 // (3) Simplify the CFG now, so that we don't need to recompute 81 // dominators and the reverse post order. 82 SimplifyCFG(); 83 84 // (4) Compute the immediate dominator of each block. We visit 85 // the successors of a block only when all its forward branches 86 // have been processed. 87 GrowableArray<size_t> visits(arena_, blocks_.Size()); 88 visits.SetSize(blocks_.Size()); 89 reverse_post_order_.Add(entry_block_); 90 for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) { 91 VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits); 92 } 93} 94 95HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const { 96 ArenaBitVector visited(arena_, blocks_.Size(), false); 97 // Walk the dominator tree of the first block and mark the visited blocks. 98 while (first != nullptr) { 99 visited.SetBit(first->GetBlockId()); 100 first = first->GetDominator(); 101 } 102 // Walk the dominator tree of the second block until a marked block is found. 103 while (second != nullptr) { 104 if (visited.IsBitSet(second->GetBlockId())) { 105 return second; 106 } 107 second = second->GetDominator(); 108 } 109 LOG(ERROR) << "Could not find common dominator"; 110 return nullptr; 111} 112 113void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, 114 HBasicBlock* predecessor, 115 GrowableArray<size_t>* visits) { 116 if (block->GetDominator() == nullptr) { 117 block->SetDominator(predecessor); 118 } else { 119 block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor)); 120 } 121 122 visits->Increment(block->GetBlockId()); 123 // Once all the forward edges have been visited, we know the immediate 124 // dominator of the block. We can then start visiting its successors. 125 if (visits->Get(block->GetBlockId()) == 126 block->GetPredecessors().Size() - block->NumberOfBackEdges()) { 127 block->GetDominator()->AddDominatedBlock(block); 128 reverse_post_order_.Add(block); 129 for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { 130 VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits); 131 } 132 } 133} 134 135void HGraph::TransformToSSA() { 136 DCHECK(!reverse_post_order_.IsEmpty()); 137 SsaBuilder ssa_builder(this); 138 ssa_builder.BuildSsa(); 139} 140 141void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { 142 // Insert a new node between `block` and `successor` to split the 143 // critical edge. 144 HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc()); 145 AddBlock(new_block); 146 new_block->AddInstruction(new (arena_) HGoto()); 147 block->ReplaceSuccessor(successor, new_block); 148 new_block->AddSuccessor(successor); 149 if (successor->IsLoopHeader()) { 150 // If we split at a back edge boundary, make the new block the back edge. 151 HLoopInformation* info = successor->GetLoopInformation(); 152 if (info->IsBackEdge(block)) { 153 info->RemoveBackEdge(block); 154 info->AddBackEdge(new_block); 155 } 156 } 157} 158 159void HGraph::SimplifyLoop(HBasicBlock* header) { 160 HLoopInformation* info = header->GetLoopInformation(); 161 162 // If there are more than one back edge, make them branch to the same block that 163 // will become the only back edge. This simplifies finding natural loops in the 164 // graph. 165 // Also, if the loop is a do/while (that is the back edge is an if), change the 166 // back edge to be a goto. This simplifies code generation of suspend cheks. 167 if (info->NumberOfBackEdges() > 1 || info->GetBackEdges().Get(0)->GetLastInstruction()->IsIf()) { 168 HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this, header->GetDexPc()); 169 AddBlock(new_back_edge); 170 new_back_edge->AddInstruction(new (arena_) HGoto()); 171 for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) { 172 HBasicBlock* back_edge = info->GetBackEdges().Get(pred); 173 back_edge->ReplaceSuccessor(header, new_back_edge); 174 } 175 info->ClearBackEdges(); 176 info->AddBackEdge(new_back_edge); 177 new_back_edge->AddSuccessor(header); 178 } 179 180 // Make sure the loop has only one pre header. This simplifies SSA building by having 181 // to just look at the pre header to know which locals are initialized at entry of the 182 // loop. 183 size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges(); 184 if (number_of_incomings != 1) { 185 HBasicBlock* pre_header = new (arena_) HBasicBlock(this, header->GetDexPc()); 186 AddBlock(pre_header); 187 pre_header->AddInstruction(new (arena_) HGoto()); 188 189 ArenaBitVector back_edges(arena_, GetBlocks().Size(), false); 190 HBasicBlock* back_edge = info->GetBackEdges().Get(0); 191 for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { 192 HBasicBlock* predecessor = header->GetPredecessors().Get(pred); 193 if (predecessor != back_edge) { 194 predecessor->ReplaceSuccessor(header, pre_header); 195 pred--; 196 } 197 } 198 pre_header->AddSuccessor(header); 199 } 200 201 // Make sure the second predecessor of a loop header is the back edge. 202 if (header->GetPredecessors().Get(1) != info->GetBackEdges().Get(0)) { 203 header->SwapPredecessors(); 204 } 205 206 // Place the suspend check at the beginning of the header, so that live registers 207 // will be known when allocating registers. Note that code generation can still 208 // generate the suspend check at the back edge, but needs to be careful with 209 // loop phi spill slots (which are not written to at back edge). 210 HInstruction* first_instruction = header->GetFirstInstruction(); 211 if (!first_instruction->IsSuspendCheck()) { 212 HSuspendCheck* check = new (arena_) HSuspendCheck(header->GetDexPc()); 213 header->InsertInstructionBefore(check, first_instruction); 214 first_instruction = check; 215 } 216 info->SetSuspendCheck(first_instruction->AsSuspendCheck()); 217} 218 219void HGraph::SimplifyCFG() { 220 // Simplify the CFG for future analysis, and code generation: 221 // (1): Split critical edges. 222 // (2): Simplify loops by having only one back edge, and one preheader. 223 for (size_t i = 0; i < blocks_.Size(); ++i) { 224 HBasicBlock* block = blocks_.Get(i); 225 if (block->GetSuccessors().Size() > 1) { 226 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 227 HBasicBlock* successor = block->GetSuccessors().Get(j); 228 if (successor->GetPredecessors().Size() > 1) { 229 SplitCriticalEdge(block, successor); 230 --j; 231 } 232 } 233 } 234 if (block->IsLoopHeader()) { 235 SimplifyLoop(block); 236 } 237 } 238} 239 240bool HGraph::FindNaturalLoops() const { 241 for (size_t i = 0; i < blocks_.Size(); ++i) { 242 HBasicBlock* block = blocks_.Get(i); 243 if (block->IsLoopHeader()) { 244 HLoopInformation* info = block->GetLoopInformation(); 245 if (!info->Populate()) { 246 // Abort if the loop is non natural. We currently bailout in such cases. 247 return false; 248 } 249 } 250 } 251 return true; 252} 253 254void HLoopInformation::PopulateRecursive(HBasicBlock* block) { 255 if (blocks_.IsBitSet(block->GetBlockId())) { 256 return; 257 } 258 259 blocks_.SetBit(block->GetBlockId()); 260 block->SetInLoop(this); 261 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 262 PopulateRecursive(block->GetPredecessors().Get(i)); 263 } 264} 265 266bool HLoopInformation::Populate() { 267 DCHECK_EQ(GetBackEdges().Size(), 1u); 268 HBasicBlock* back_edge = GetBackEdges().Get(0); 269 DCHECK(back_edge->GetDominator() != nullptr); 270 if (!header_->Dominates(back_edge)) { 271 // This loop is not natural. Do not bother going further. 272 return false; 273 } 274 275 // Populate this loop: starting with the back edge, recursively add predecessors 276 // that are not already part of that loop. Set the header as part of the loop 277 // to end the recursion. 278 // This is a recursive implementation of the algorithm described in 279 // "Advanced Compiler Design & Implementation" (Muchnick) p192. 280 blocks_.SetBit(header_->GetBlockId()); 281 PopulateRecursive(back_edge); 282 return true; 283} 284 285HBasicBlock* HLoopInformation::GetPreHeader() const { 286 DCHECK_EQ(header_->GetPredecessors().Size(), 2u); 287 return header_->GetDominator(); 288} 289 290bool HLoopInformation::Contains(const HBasicBlock& block) const { 291 return blocks_.IsBitSet(block.GetBlockId()); 292} 293 294bool HLoopInformation::IsIn(const HLoopInformation& other) const { 295 return other.blocks_.IsBitSet(header_->GetBlockId()); 296} 297 298bool HBasicBlock::Dominates(HBasicBlock* other) const { 299 // Walk up the dominator tree from `other`, to find out if `this` 300 // is an ancestor. 301 HBasicBlock* current = other; 302 while (current != nullptr) { 303 if (current == this) { 304 return true; 305 } 306 current = current->GetDominator(); 307 } 308 return false; 309} 310 311void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 312 DCHECK(cursor->AsPhi() == nullptr); 313 DCHECK(instruction->AsPhi() == nullptr); 314 DCHECK_EQ(instruction->GetId(), -1); 315 DCHECK_NE(cursor->GetId(), -1); 316 DCHECK_EQ(cursor->GetBlock(), this); 317 DCHECK(!instruction->IsControlFlow()); 318 instruction->next_ = cursor; 319 instruction->previous_ = cursor->previous_; 320 cursor->previous_ = instruction; 321 if (GetFirstInstruction() == cursor) { 322 instructions_.first_instruction_ = instruction; 323 } else { 324 instruction->previous_->next_ = instruction; 325 } 326 instruction->SetBlock(this); 327 instruction->SetId(GetGraph()->GetNextInstructionId()); 328} 329 330void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, 331 HInstruction* replacement) { 332 DCHECK(initial->GetBlock() == this); 333 InsertInstructionBefore(replacement, initial); 334 initial->ReplaceWith(replacement); 335 RemoveInstruction(initial); 336} 337 338static void Add(HInstructionList* instruction_list, 339 HBasicBlock* block, 340 HInstruction* instruction) { 341 DCHECK(instruction->GetBlock() == nullptr); 342 DCHECK_EQ(instruction->GetId(), -1); 343 instruction->SetBlock(block); 344 instruction->SetId(block->GetGraph()->GetNextInstructionId()); 345 instruction_list->AddInstruction(instruction); 346} 347 348void HBasicBlock::AddInstruction(HInstruction* instruction) { 349 Add(&instructions_, this, instruction); 350} 351 352void HBasicBlock::AddPhi(HPhi* phi) { 353 Add(&phis_, this, phi); 354} 355 356static void Remove(HInstructionList* instruction_list, 357 HBasicBlock* block, 358 HInstruction* instruction) { 359 DCHECK_EQ(block, instruction->GetBlock()); 360 DCHECK(instruction->GetUses() == nullptr); 361 DCHECK(instruction->GetEnvUses() == nullptr); 362 instruction->SetBlock(nullptr); 363 instruction_list->RemoveInstruction(instruction); 364 365 for (size_t i = 0; i < instruction->InputCount(); i++) { 366 instruction->InputAt(i)->RemoveUser(instruction, i); 367 } 368 369 HEnvironment* environment = instruction->GetEnvironment(); 370 if (environment != nullptr) { 371 for (size_t i = 0, e = environment->Size(); i < e; ++i) { 372 HInstruction* vreg = environment->GetInstructionAt(i); 373 if (vreg != nullptr) { 374 vreg->RemoveEnvironmentUser(environment, i); 375 } 376 } 377 } 378} 379 380void HBasicBlock::RemoveInstruction(HInstruction* instruction) { 381 Remove(&instructions_, this, instruction); 382} 383 384void HBasicBlock::RemovePhi(HPhi* phi) { 385 Remove(&phis_, this, phi); 386} 387 388template <typename T> 389static void RemoveFromUseList(T* user, 390 size_t input_index, 391 HUseListNode<T>** list) { 392 HUseListNode<T>* previous = nullptr; 393 HUseListNode<T>* current = *list; 394 while (current != nullptr) { 395 if (current->GetUser() == user && current->GetIndex() == input_index) { 396 if (previous == NULL) { 397 *list = current->GetTail(); 398 } else { 399 previous->SetTail(current->GetTail()); 400 } 401 } 402 previous = current; 403 current = current->GetTail(); 404 } 405} 406 407void HInstruction::RemoveUser(HInstruction* user, size_t input_index) { 408 RemoveFromUseList(user, input_index, &uses_); 409} 410 411void HInstruction::RemoveEnvironmentUser(HEnvironment* user, size_t input_index) { 412 RemoveFromUseList(user, input_index, &env_uses_); 413} 414 415void HInstructionList::AddInstruction(HInstruction* instruction) { 416 if (first_instruction_ == nullptr) { 417 DCHECK(last_instruction_ == nullptr); 418 first_instruction_ = last_instruction_ = instruction; 419 } else { 420 last_instruction_->next_ = instruction; 421 instruction->previous_ = last_instruction_; 422 last_instruction_ = instruction; 423 } 424 for (size_t i = 0; i < instruction->InputCount(); i++) { 425 instruction->InputAt(i)->AddUseAt(instruction, i); 426 } 427} 428 429void HInstructionList::RemoveInstruction(HInstruction* instruction) { 430 if (instruction->previous_ != nullptr) { 431 instruction->previous_->next_ = instruction->next_; 432 } 433 if (instruction->next_ != nullptr) { 434 instruction->next_->previous_ = instruction->previous_; 435 } 436 if (instruction == first_instruction_) { 437 first_instruction_ = instruction->next_; 438 } 439 if (instruction == last_instruction_) { 440 last_instruction_ = instruction->previous_; 441 } 442} 443 444bool HInstructionList::FoundBefore(const HInstruction* instruction1, 445 const HInstruction* instruction2) const { 446 DCHECK_EQ(instruction1->GetBlock(), instruction2->GetBlock()); 447 for (HInstructionIterator it(*this); !it.Done(); it.Advance()) { 448 if (it.Current() == instruction1) { 449 return true; 450 } 451 if (it.Current() == instruction2) { 452 return false; 453 } 454 } 455 LOG(FATAL) << "Did not find an order between two instructions of the same block."; 456 return true; 457} 458 459bool HInstruction::Dominates(HInstruction* other_instruction) const { 460 HBasicBlock* block = GetBlock(); 461 HBasicBlock* other_block = other_instruction->GetBlock(); 462 if (block != other_block) { 463 return GetBlock()->Dominates(other_instruction->GetBlock()); 464 } else { 465 // If both instructions are in the same block, ensure this 466 // instruction comes before `other_instruction`. 467 if (IsPhi()) { 468 if (!other_instruction->IsPhi()) { 469 // Phis appear before non phi-instructions so this instruction 470 // dominates `other_instruction`. 471 return true; 472 } else { 473 // There is no order among phis. 474 LOG(FATAL) << "There is no dominance between phis of a same block."; 475 return false; 476 } 477 } else { 478 // `this` is not a phi. 479 if (other_instruction->IsPhi()) { 480 // Phis appear before non phi-instructions so this instruction 481 // does not dominate `other_instruction`. 482 return false; 483 } else { 484 // Check whether this instruction comes before 485 // `other_instruction` in the instruction list. 486 return block->GetInstructions().FoundBefore(this, other_instruction); 487 } 488 } 489 } 490} 491 492void HInstruction::ReplaceWith(HInstruction* other) { 493 DCHECK(other != nullptr); 494 for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) { 495 HUseListNode<HInstruction>* current = it.Current(); 496 HInstruction* user = current->GetUser(); 497 size_t input_index = current->GetIndex(); 498 user->SetRawInputAt(input_index, other); 499 other->AddUseAt(user, input_index); 500 } 501 502 for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) { 503 HUseListNode<HEnvironment>* current = it.Current(); 504 HEnvironment* user = current->GetUser(); 505 size_t input_index = current->GetIndex(); 506 user->SetRawEnvAt(input_index, other); 507 other->AddEnvUseAt(user, input_index); 508 } 509 510 uses_ = nullptr; 511 env_uses_ = nullptr; 512} 513 514size_t HInstruction::EnvironmentSize() const { 515 return HasEnvironment() ? environment_->Size() : 0; 516} 517 518void HPhi::AddInput(HInstruction* input) { 519 DCHECK(input->GetBlock() != nullptr); 520 inputs_.Add(input); 521 input->AddUseAt(this, inputs_.Size() - 1); 522} 523 524#define DEFINE_ACCEPT(name) \ 525void H##name::Accept(HGraphVisitor* visitor) { \ 526 visitor->Visit##name(this); \ 527} 528 529FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) 530 531#undef DEFINE_ACCEPT 532 533void HGraphVisitor::VisitInsertionOrder() { 534 const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks(); 535 for (size_t i = 0 ; i < blocks.Size(); i++) { 536 VisitBasicBlock(blocks.Get(i)); 537 } 538} 539 540void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { 541 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 542 it.Current()->Accept(this); 543 } 544 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 545 it.Current()->Accept(this); 546 } 547} 548 549HConstant* HBinaryOperation::TryStaticEvaluation(ArenaAllocator* allocator) const { 550 if (GetLeft()->IsIntConstant() && GetRight()->IsIntConstant()) { 551 int32_t value = Evaluate(GetLeft()->AsIntConstant()->GetValue(), 552 GetRight()->AsIntConstant()->GetValue()); 553 return new(allocator) HIntConstant(value); 554 } else if (GetLeft()->IsLongConstant() && GetRight()->IsLongConstant()) { 555 int64_t value = Evaluate(GetLeft()->AsLongConstant()->GetValue(), 556 GetRight()->AsLongConstant()->GetValue()); 557 return new(allocator) HLongConstant(value); 558 } 559 return nullptr; 560} 561 562bool HCondition::NeedsMaterialization() const { 563 if (!HasOnlyOneUse()) { 564 return true; 565 } 566 HUseListNode<HInstruction>* uses = GetUses(); 567 HInstruction* user = uses->GetUser(); 568 if (!user->IsIf()) { 569 return true; 570 } 571 572 // TODO: if there is no intervening instructions with side-effect between this condition 573 // and the If instruction, we should move the condition just before the If. 574 if (GetNext() != user) { 575 return true; 576 } 577 return false; 578} 579 580bool HCondition::IsBeforeWhenDisregardMoves(HIf* if_) const { 581 HInstruction* previous = if_->GetPrevious(); 582 while (previous != nullptr && previous->IsParallelMove()) { 583 previous = previous->GetPrevious(); 584 } 585 return previous == this; 586} 587 588bool HInstruction::Equals(HInstruction* other) const { 589 if (!InstructionTypeEquals(other)) return false; 590 DCHECK_EQ(GetKind(), other->GetKind()); 591 if (!InstructionDataEquals(other)) return false; 592 if (GetType() != other->GetType()) return false; 593 if (InputCount() != other->InputCount()) return false; 594 595 for (size_t i = 0, e = InputCount(); i < e; ++i) { 596 if (InputAt(i) != other->InputAt(i)) return false; 597 } 598 DCHECK_EQ(ComputeHashCode(), other->ComputeHashCode()); 599 return true; 600} 601 602} // namespace art 603