| /* |
| * Copyright (C) 2014 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "nodes.h" |
| #include "ssa_builder.h" |
| #include "utils/growable_array.h" |
| |
| namespace art { |
| |
| void HGraph::AddBlock(HBasicBlock* block) { |
| block->SetBlockId(blocks_.Size()); |
| blocks_.Add(block); |
| } |
| |
| void HGraph::FindBackEdges(ArenaBitVector* visited) const { |
| ArenaBitVector visiting(arena_, blocks_.Size(), false); |
| VisitBlockForBackEdges(entry_block_, visited, &visiting); |
| } |
| |
| void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { |
| for (size_t i = 0; i < blocks_.Size(); i++) { |
| if (!visited.IsBitSet(i)) { |
| HBasicBlock* block = blocks_.Get(i); |
| for (size_t j = 0; j < block->GetSuccessors()->Size(); j++) { |
| block->GetSuccessors()->Get(j)->RemovePredecessor(block, false); |
| } |
| for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) { |
| block->RemovePhi(it.Current()->AsPhi()); |
| } |
| for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) { |
| block->RemoveInstruction(it.Current()); |
| } |
| } |
| } |
| } |
| |
| void HGraph::VisitBlockForBackEdges(HBasicBlock* block, |
| ArenaBitVector* visited, |
| ArenaBitVector* visiting) const { |
| int id = block->GetBlockId(); |
| if (visited->IsBitSet(id)) return; |
| |
| visited->SetBit(id); |
| visiting->SetBit(id); |
| for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) { |
| HBasicBlock* successor = block->GetSuccessors()->Get(i); |
| if (visiting->IsBitSet(successor->GetBlockId())) { |
| successor->AddBackEdge(block); |
| } else { |
| VisitBlockForBackEdges(successor, visited, visiting); |
| } |
| } |
| visiting->ClearBit(id); |
| } |
| |
| void HGraph::BuildDominatorTree() { |
| ArenaBitVector visited(arena_, blocks_.Size(), false); |
| |
| // (1) Find the back edges in the graph doing a DFS traversal. |
| FindBackEdges(&visited); |
| |
| // (2) Remove blocks not visited during the initial DFS. |
| // Step (3) requires dead blocks to be removed from the |
| // predecessors list of live blocks. |
| RemoveDeadBlocks(visited); |
| |
| // (3) Compute the immediate dominator of each block. We visit |
| // the successors of a block only when all its forward branches |
| // have been processed. |
| GrowableArray<size_t> visits(arena_, blocks_.Size()); |
| visits.SetSize(blocks_.Size()); |
| dominator_order_.Add(entry_block_); |
| for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) { |
| VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits); |
| } |
| } |
| |
| HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const { |
| ArenaBitVector visited(arena_, blocks_.Size(), false); |
| // Walk the dominator tree of the first block and mark the visited blocks. |
| while (first != nullptr) { |
| visited.SetBit(first->GetBlockId()); |
| first = first->GetDominator(); |
| } |
| // Walk the dominator tree of the second block until a marked block is found. |
| while (second != nullptr) { |
| if (visited.IsBitSet(second->GetBlockId())) { |
| return second; |
| } |
| second = second->GetDominator(); |
| } |
| LOG(ERROR) << "Could not find common dominator"; |
| return nullptr; |
| } |
| |
| void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, |
| HBasicBlock* predecessor, |
| GrowableArray<size_t>* visits) { |
| if (block->GetDominator() == nullptr) { |
| block->SetDominator(predecessor); |
| } else { |
| block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor)); |
| } |
| |
| visits->Increment(block->GetBlockId()); |
| // Once all the forward edges have been visited, we know the immediate |
| // dominator of the block. We can then start visiting its successors. |
| if (visits->Get(block->GetBlockId()) == |
| block->GetPredecessors()->Size() - block->NumberOfBackEdges()) { |
| dominator_order_.Add(block); |
| for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) { |
| VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits); |
| } |
| } |
| } |
| |
| void HGraph::TransformToSSA() { |
| DCHECK(!dominator_order_.IsEmpty()); |
| SimplifyCFG(); |
| SsaBuilder ssa_builder(this); |
| ssa_builder.BuildSsa(); |
| } |
| |
| void HGraph::SimplifyCFG() { |
| for (size_t i = 0; i < dominator_order_.Size(); i++) { |
| HBasicBlock* current = dominator_order_.Get(i); |
| if (current->IsLoopHeader()) { |
| // Make sure the loop has only one pre header. This simplifies SSA building by having |
| // to just look at the pre header to know which locals are initialized at entry of the |
| // loop. |
| HLoopInformation* info = current->GetLoopInformation(); |
| size_t number_of_incomings = current->GetPredecessors()->Size() - info->NumberOfBackEdges(); |
| if (number_of_incomings != 1) { |
| HBasicBlock* pre_header = new (arena_) HBasicBlock(this); |
| AddBlock(pre_header); |
| pre_header->AddInstruction(new (arena_) HGoto()); |
| pre_header->SetDominator(current->GetDominator()); |
| current->SetDominator(pre_header); |
| dominator_order_.InsertAt(i, pre_header); |
| i++; |
| |
| ArenaBitVector back_edges(arena_, GetBlocks()->Size(), false); |
| for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) { |
| back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId()); |
| } |
| for (size_t pred = 0; pred < current->GetPredecessors()->Size(); pred++) { |
| HBasicBlock* predecessor = current->GetPredecessors()->Get(pred); |
| if (!back_edges.IsBitSet(predecessor->GetBlockId())) { |
| current->RemovePredecessor(predecessor); |
| pred--; |
| predecessor->AddSuccessor(pre_header); |
| } |
| } |
| pre_header->AddSuccessor(current); |
| } |
| info->SetPreHeader(current->GetDominator()); |
| } |
| } |
| } |
| |
| void HLoopInformation::SetPreHeader(HBasicBlock* block) { |
| DCHECK_EQ(header_->GetDominator(), block); |
| pre_header_ = block; |
| } |
| |
| static void Add(HInstructionList* instruction_list, |
| HBasicBlock* block, |
| HInstruction* instruction) { |
| DCHECK(instruction->GetBlock() == nullptr); |
| DCHECK_EQ(instruction->GetId(), -1); |
| instruction->SetBlock(block); |
| instruction->SetId(block->GetGraph()->GetNextInstructionId()); |
| instruction_list->AddInstruction(instruction); |
| } |
| |
| void HBasicBlock::AddInstruction(HInstruction* instruction) { |
| Add(&instructions_, this, instruction); |
| } |
| |
| void HBasicBlock::AddPhi(HPhi* phi) { |
| Add(&phis_, this, phi); |
| } |
| |
| static void Remove(HInstructionList* instruction_list, |
| HBasicBlock* block, |
| HInstruction* instruction) { |
| DCHECK_EQ(block, instruction->GetBlock()); |
| DCHECK(instruction->GetUses() == nullptr); |
| DCHECK(instruction->GetEnvUses() == nullptr); |
| instruction->SetBlock(nullptr); |
| instruction_list->RemoveInstruction(instruction); |
| |
| for (size_t i = 0; i < instruction->InputCount(); i++) { |
| instruction->InputAt(i)->RemoveUser(instruction, i); |
| } |
| } |
| |
| void HBasicBlock::RemoveInstruction(HInstruction* instruction) { |
| Remove(&instructions_, this, instruction); |
| } |
| |
| void HBasicBlock::RemovePhi(HPhi* phi) { |
| Remove(&phis_, this, phi); |
| } |
| |
| void HInstruction::RemoveUser(HInstruction* user, size_t input_index) { |
| HUseListNode<HInstruction>* previous = nullptr; |
| HUseListNode<HInstruction>* current = uses_; |
| while (current != nullptr) { |
| if (current->GetUser() == user && current->GetIndex() == input_index) { |
| if (previous == NULL) { |
| uses_ = current->GetTail(); |
| } else { |
| previous->SetTail(current->GetTail()); |
| } |
| } |
| previous = current; |
| current = current->GetTail(); |
| } |
| } |
| |
| void HInstructionList::AddInstruction(HInstruction* instruction) { |
| if (first_instruction_ == nullptr) { |
| DCHECK(last_instruction_ == nullptr); |
| first_instruction_ = last_instruction_ = instruction; |
| } else { |
| last_instruction_->next_ = instruction; |
| instruction->previous_ = last_instruction_; |
| last_instruction_ = instruction; |
| } |
| for (size_t i = 0; i < instruction->InputCount(); i++) { |
| instruction->InputAt(i)->AddUseAt(instruction, i); |
| } |
| } |
| |
| void HInstructionList::RemoveInstruction(HInstruction* instruction) { |
| if (instruction->previous_ != nullptr) { |
| instruction->previous_->next_ = instruction->next_; |
| } |
| if (instruction->next_ != nullptr) { |
| instruction->next_->previous_ = instruction->previous_; |
| } |
| if (instruction == first_instruction_) { |
| first_instruction_ = instruction->next_; |
| } |
| if (instruction == last_instruction_) { |
| last_instruction_ = instruction->previous_; |
| } |
| } |
| |
| void HInstruction::ReplaceWith(HInstruction* other) { |
| for (HUseIterator<HInstruction> it(GetUses()); !it.Done(); it.Advance()) { |
| HUseListNode<HInstruction>* current = it.Current(); |
| HInstruction* user = current->GetUser(); |
| size_t input_index = current->GetIndex(); |
| user->SetRawInputAt(input_index, other); |
| other->AddUseAt(user, input_index); |
| } |
| |
| for (HUseIterator<HEnvironment> it(GetEnvUses()); !it.Done(); it.Advance()) { |
| HUseListNode<HEnvironment>* current = it.Current(); |
| HEnvironment* user = current->GetUser(); |
| size_t input_index = current->GetIndex(); |
| user->SetRawEnvAt(input_index, other); |
| other->AddEnvUseAt(user, input_index); |
| } |
| |
| uses_ = nullptr; |
| env_uses_ = nullptr; |
| } |
| |
| void HPhi::AddInput(HInstruction* input) { |
| DCHECK(input->GetBlock() != nullptr); |
| inputs_.Add(input); |
| input->AddUseAt(this, inputs_.Size() - 1); |
| } |
| |
| #define DEFINE_ACCEPT(name) \ |
| void H##name::Accept(HGraphVisitor* visitor) { \ |
| visitor->Visit##name(this); \ |
| } |
| |
| FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) |
| |
| #undef DEFINE_ACCEPT |
| |
| void HGraphVisitor::VisitInsertionOrder() { |
| const GrowableArray<HBasicBlock*>* blocks = graph_->GetBlocks(); |
| for (size_t i = 0 ; i < blocks->Size(); i++) { |
| VisitBasicBlock(blocks->Get(i)); |
| } |
| } |
| |
| void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { |
| for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) { |
| it.Current()->Accept(this); |
| } |
| for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) { |
| it.Current()->Accept(this); |
| } |
| } |
| |
| } // namespace art |