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 21 namespace art { 22 23 void HGraph::AddBlock(HBasicBlock* block) { 24 block->SetBlockId(blocks_.Size()); 25 blocks_.Add(block); 26 } 27 28 void HGraph::FindBackEdges(ArenaBitVector* visited) { 29 ArenaBitVector visiting(arena_, blocks_.Size(), false); 30 VisitBlockForBackEdges(entry_block_, visited, &visiting); 31 } 32 33 void 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 50 void 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 69 void 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 95 HBasicBlock* 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 113 void 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 reverse_post_order_.Add(block); 128 for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { 129 VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits); 130 } 131 } 132 } 133 134 void HGraph::TransformToSSA() { 135 DCHECK(!reverse_post_order_.IsEmpty()); 136 SsaBuilder ssa_builder(this); 137 ssa_builder.BuildSsa(); 138 } 139 140 void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { 141 // Insert a new node between `block` and `successor` to split the 142 // critical edge. 143 HBasicBlock* new_block = new (arena_) HBasicBlock(this); 144 AddBlock(new_block); 145 new_block->AddInstruction(new (arena_) HGoto()); 146 block->ReplaceSuccessor(successor, new_block); 147 new_block->AddSuccessor(successor); 148 if (successor->IsLoopHeader()) { 149 // If we split at a back edge boundary, make the new block the back edge. 150 HLoopInformation* info = successor->GetLoopInformation(); 151 if (info->IsBackEdge(block)) { 152 info->RemoveBackEdge(block); 153 info->AddBackEdge(new_block); 154 } 155 } 156 } 157 158 void HGraph::SimplifyLoop(HBasicBlock* header) { 159 HLoopInformation* info = header->GetLoopInformation(); 160 161 // If there are more than one back edge, make them branch to the same block that 162 // will become the only back edge. This simplifies finding natural loops in the 163 // graph. 164 if (info->NumberOfBackEdges() > 1) { 165 HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this); 166 AddBlock(new_back_edge); 167 new_back_edge->AddInstruction(new (arena_) HGoto()); 168 for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) { 169 HBasicBlock* back_edge = info->GetBackEdges().Get(pred); 170 back_edge->ReplaceSuccessor(header, new_back_edge); 171 } 172 info->ClearBackEdges(); 173 info->AddBackEdge(new_back_edge); 174 new_back_edge->AddSuccessor(header); 175 } 176 177 // Make sure the loop has only one pre header. This simplifies SSA building by having 178 // to just look at the pre header to know which locals are initialized at entry of the 179 // loop. 180 size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges(); 181 if (number_of_incomings != 1) { 182 HBasicBlock* pre_header = new (arena_) HBasicBlock(this); 183 AddBlock(pre_header); 184 pre_header->AddInstruction(new (arena_) HGoto()); 185 186 ArenaBitVector back_edges(arena_, GetBlocks().Size(), false); 187 HBasicBlock* back_edge = info->GetBackEdges().Get(0); 188 for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { 189 HBasicBlock* predecessor = header->GetPredecessors().Get(pred); 190 if (predecessor != back_edge) { 191 predecessor->ReplaceSuccessor(header, pre_header); 192 pred--; 193 } 194 } 195 pre_header->AddSuccessor(header); 196 } 197 } 198 199 void HGraph::SimplifyCFG() { 200 // Simplify the CFG for future analysis, and code generation: 201 // (1): Split critical edges. 202 // (2): Simplify loops by having only one back edge, and one preheader. 203 for (size_t i = 0; i < blocks_.Size(); ++i) { 204 HBasicBlock* block = blocks_.Get(i); 205 if (block->GetSuccessors().Size() > 1) { 206 for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { 207 HBasicBlock* successor = block->GetSuccessors().Get(j); 208 if (successor->GetPredecessors().Size() > 1) { 209 SplitCriticalEdge(block, successor); 210 --j; 211 } 212 } 213 } 214 if (block->IsLoopHeader()) { 215 SimplifyLoop(block); 216 } 217 } 218 } 219 220 bool HGraph::FindNaturalLoops() const { 221 for (size_t i = 0; i < blocks_.Size(); ++i) { 222 HBasicBlock* block = blocks_.Get(i); 223 if (block->IsLoopHeader()) { 224 HLoopInformation* info = block->GetLoopInformation(); 225 if (!info->Populate()) { 226 // Abort if the loop is non natural. We currently bailout in such cases. 227 return false; 228 } 229 } 230 } 231 return true; 232 } 233 234 void HLoopInformation::PopulateRecursive(HBasicBlock* block) { 235 if (blocks_.IsBitSet(block->GetBlockId())) { 236 return; 237 } 238 239 blocks_.SetBit(block->GetBlockId()); 240 block->SetInLoop(this); 241 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 242 PopulateRecursive(block->GetPredecessors().Get(i)); 243 } 244 } 245 246 bool HLoopInformation::Populate() { 247 DCHECK_EQ(GetBackEdges().Size(), 1u); 248 HBasicBlock* back_edge = GetBackEdges().Get(0); 249 DCHECK(back_edge->GetDominator() != nullptr); 250 if (!header_->Dominates(back_edge)) { 251 // This loop is not natural. Do not bother going further. 252 return false; 253 } 254 255 // Populate this loop: starting with the back edge, recursively add predecessors 256 // that are not already part of that loop. Set the header as part of the loop 257 // to end the recursion. 258 // This is a recursive implementation of the algorithm described in 259 // "Advanced Compiler Design & Implementation" (Muchnick) p192. 260 blocks_.SetBit(header_->GetBlockId()); 261 PopulateRecursive(back_edge); 262 return true; 263 } 264 265 HBasicBlock* HLoopInformation::GetPreHeader() const { 266 DCHECK_EQ(header_->GetPredecessors().Size(), 2u); 267 return header_->GetDominator(); 268 } 269 270 bool HLoopInformation::Contains(const HBasicBlock& block) const { 271 return blocks_.IsBitSet(block.GetBlockId()); 272 } 273 274 bool HLoopInformation::IsIn(const HLoopInformation& other) const { 275 return other.blocks_.IsBitSet(header_->GetBlockId()); 276 } 277 278 bool HBasicBlock::Dominates(HBasicBlock* other) const { 279 // Walk up the dominator tree from `other`, to find out if `this` 280 // is an ancestor. 281 HBasicBlock* current = other; 282 while (current != nullptr) { 283 if (current == this) { 284 return true; 285 } 286 current = current->GetDominator(); 287 } 288 return false; 289 } 290 291 void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { 292 DCHECK(cursor->AsPhi() == nullptr); 293 DCHECK(instruction->AsPhi() == nullptr); 294 DCHECK_EQ(instruction->GetId(), -1); 295 DCHECK_NE(cursor->GetId(), -1); 296 DCHECK_EQ(cursor->GetBlock(), this); 297 DCHECK(!instruction->IsControlFlow()); 298 instruction->next_ = cursor; 299 instruction->previous_ = cursor->previous_; 300 cursor->previous_ = instruction; 301 if (GetFirstInstruction() == cursor) { 302 instructions_.first_instruction_ = instruction; 303 } else { 304 instruction->previous_->next_ = instruction; 305 } 306 instruction->SetBlock(this); 307 instruction->SetId(GetGraph()->GetNextInstructionId()); 308 } 309 310 static void Add(HInstructionList* instruction_list, 311 HBasicBlock* block, 312 HInstruction* instruction) { 313 DCHECK(instruction->GetBlock() == nullptr); 314 DCHECK_EQ(instruction->GetId(), -1); 315 instruction->SetBlock(block); 316 instruction->SetId(block->GetGraph()->GetNextInstructionId()); 317 instruction_list->AddInstruction(instruction); 318 } 319 320 void HBasicBlock::AddInstruction(HInstruction* instruction) { 321 Add(&instructions_, this, instruction); 322 } 323 324 void HBasicBlock::AddPhi(HPhi* phi) { 325 Add(&phis_, this, phi); 326 } 327 328 static void Remove(HInstructionList* instruction_list, 329 HBasicBlock* block, 330 HInstruction* instruction) { 331 DCHECK_EQ(block, instruction->GetBlock()); 332 DCHECK(instruction->GetUses() == nullptr); 333 DCHECK(instruction->GetEnvUses() == nullptr); 334 instruction->SetBlock(nullptr); 335 instruction_list->RemoveInstruction(instruction); 336 337 for (size_t i = 0; i < instruction->InputCount(); i++) { 338 instruction->InputAt(i)->RemoveUser(instruction, i); 339 } 340 } 341 342 void HBasicBlock::RemoveInstruction(HInstruction* instruction) { 343 Remove(&instructions_, this, instruction); 344 } 345 346 void HBasicBlock::RemovePhi(HPhi* phi) { 347 Remove(&phis_, this, phi); 348 } 349 350 void HInstruction::RemoveUser(HInstruction* user, size_t input_index) { 351 HUseListNode<HInstruction>* previous = nullptr; 352 HUseListNode<HInstruction>* current = uses_; 353 while (current != nullptr) { 354 if (current->GetUser() == user && current->GetIndex() == input_index) { 355 if (previous == NULL) { 356 uses_ = current->GetTail(); 357 } else { 358 previous->SetTail(current->GetTail()); 359 } 360 } 361 previous = current; 362 current = current->GetTail(); 363 } 364 } 365 366 void HInstructionList::AddInstruction(HInstruction* instruction) { 367 if (first_instruction_ == nullptr) { 368 DCHECK(last_instruction_ == nullptr); 369 first_instruction_ = last_instruction_ = instruction; 370 } else { 371 last_instruction_->next_ = instruction; 372 instruction->previous_ = last_instruction_; 373 last_instruction_ = instruction; 374 } 375 for (size_t i = 0; i < instruction->InputCount(); i++) { 376 instruction->InputAt(i)->AddUseAt(instruction, i); 377 } 378 } 379 380 void HInstructionList::RemoveInstruction(HInstruction* instruction) { 381 if (instruction->previous_ != nullptr) { 382 instruction->previous_->next_ = instruction->next_; 383 } 384 if (instruction->next_ != nullptr) { 385 instruction->next_->previous_ = instruction->previous_; 386 } 387 if (instruction == first_instruction_) { 388 first_instruction_ = instruction->next_; 389 } 390 if (instruction == last_instruction_) { 391 last_instruction_ = instruction->previous_; 392 } 393 } 394 395 void HInstruction::ReplaceWith(HInstruction* other) { 396 DCHECK(other != nullptr); 397 for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) { 398 HUseListNode<HInstruction>* current = it.Current(); 399 HInstruction* user = current->GetUser(); 400 size_t input_index = current->GetIndex(); 401 user->SetRawInputAt(input_index, other); 402 other->AddUseAt(user, input_index); 403 } 404 405 for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) { 406 HUseListNode<HEnvironment>* current = it.Current(); 407 HEnvironment* user = current->GetUser(); 408 size_t input_index = current->GetIndex(); 409 user->SetRawEnvAt(input_index, other); 410 other->AddEnvUseAt(user, input_index); 411 } 412 413 uses_ = nullptr; 414 env_uses_ = nullptr; 415 } 416 417 void HPhi::AddInput(HInstruction* input) { 418 DCHECK(input->GetBlock() != nullptr); 419 inputs_.Add(input); 420 input->AddUseAt(this, inputs_.Size() - 1); 421 } 422 423 #define DEFINE_ACCEPT(name) \ 424 void H##name::Accept(HGraphVisitor* visitor) { \ 425 visitor->Visit##name(this); \ 426 } 427 428 FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) 429 430 #undef DEFINE_ACCEPT 431 432 void HGraphVisitor::VisitInsertionOrder() { 433 const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks(); 434 for (size_t i = 0 ; i < blocks.Size(); i++) { 435 VisitBasicBlock(blocks.Get(i)); 436 } 437 } 438 439 void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { 440 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 441 it.Current()->Accept(this); 442 } 443 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 444 it.Current()->Accept(this); 445 } 446 } 447 448 449 bool HCondition::NeedsMaterialization() const { 450 if (!HasOnlyOneUse()) { 451 return true; 452 } 453 HUseListNode<HInstruction>* uses = GetUses(); 454 HInstruction* user = uses->GetUser(); 455 if (!user->IsIf()) { 456 return true; 457 } 458 459 // TODO: should we allow intervening instructions with no side-effect between this condition 460 // and the If instruction? 461 if (GetNext() != user) { 462 return true; 463 } 464 return false; 465 } 466 467 } // namespace art 468