From 622d9c31febd950255b36a48b47e1f630197c5fe Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Mon, 12 May 2014 16:11:02 +0100 Subject: Add loop recognition and CFG simplifications in new compiler. We do three simplifications: - Split critical edges, for code generation from SSA (new). - Ensure one back edge per loop, to simplify loop recognition (new). - Ensure only one pre header for a loop, to simplify SSA creation (existing). Change-Id: I9bfccd4b236a00486a261078627b091c8a68be33 --- compiler/optimizing/nodes.cc | 209 +++++++++++++++++++++++++++++++++---------- 1 file changed, 163 insertions(+), 46 deletions(-) (limited to 'compiler/optimizing/nodes.cc') diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index d153bf7..cf2d1ee 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -31,11 +31,11 @@ void HGraph::FindBackEdges(ArenaBitVector* visited) { } void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { - for (size_t i = 0; i < blocks_.Size(); i++) { + 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 (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()); @@ -55,15 +55,14 @@ void HGraph::VisitBlockForBackEdges(HBasicBlock* block, visited->SetBit(id); visiting->SetBit(id); - for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) { - HBasicBlock* successor = block->GetSuccessors()->Get(i); + 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); } } - post_order_.Add(block); visiting->ClearBit(id); } @@ -78,13 +77,18 @@ void HGraph::BuildDominatorTree() { // predecessors list of live blocks. RemoveDeadBlocks(visited); - // (3) Compute the immediate dominator of each block. We visit + // (3) Simplify the CFG now, so that we don't need to recompute + // dominators and the reverse post order. + SimplifyCFG(); + + // (4) Compute the immediate dominator of each block. We visit // the successors of a block only when all its forward branches // have been processed. GrowableArray visits(arena_, blocks_.Size()); visits.SetSize(blocks_.Size()); - for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) { - VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits); + reverse_post_order_.Add(entry_block_); + for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) { + VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits); } } @@ -119,59 +123,172 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, // 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()) { - for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) { - VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits); + block->GetPredecessors().Size() - block->NumberOfBackEdges()) { + reverse_post_order_.Add(block); + for (size_t i = 0; i < block->GetSuccessors().Size(); i++) { + VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits); } } } void HGraph::TransformToSSA() { - DCHECK(!post_order_.IsEmpty()); - SimplifyCFG(); + DCHECK(!reverse_post_order_.IsEmpty()); SsaBuilder ssa_builder(this); ssa_builder.BuildSsa(); } +void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { + // Insert a new node between `block` and `successor` to split the + // critical edge. + HBasicBlock* new_block = new (arena_) HBasicBlock(this); + AddBlock(new_block); + new_block->AddInstruction(new (arena_) HGoto()); + block->RemoveSuccessor(successor); + block->AddSuccessor(new_block); + new_block->AddSuccessor(successor); + if (successor->IsLoopHeader()) { + // If we split at a back edge boundary, make the new block the back edge. + HLoopInformation* info = successor->GetLoopInformation(); + if (info->IsBackEdge(block)) { + info->RemoveBackEdge(block); + info->AddBackEdge(new_block); + } + } +} + +void HGraph::SimplifyLoop(HBasicBlock* header) { + HLoopInformation* info = header->GetLoopInformation(); + + // If there are more than one back edge, make them branch to the same block that + // will become the only back edge. This simplifies finding natural loops in the + // graph. + if (info->NumberOfBackEdges() > 1) { + HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this); + AddBlock(new_back_edge); + new_back_edge->AddInstruction(new (arena_) HGoto()); + for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) { + HBasicBlock* back_edge = info->GetBackEdges().Get(pred); + header->RemovePredecessor(back_edge); + back_edge->AddSuccessor(new_back_edge); + } + info->ClearBackEdges(); + info->AddBackEdge(new_back_edge); + new_back_edge->AddSuccessor(header); + } + + // 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. + size_t number_of_incomings = header->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()); + + ArenaBitVector back_edges(arena_, GetBlocks().Size(), false); + HBasicBlock* back_edge = info->GetBackEdges().Get(0); + for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { + HBasicBlock* predecessor = header->GetPredecessors().Get(pred); + if (predecessor != back_edge) { + header->RemovePredecessor(predecessor); + pred--; + predecessor->AddSuccessor(pre_header); + } + } + pre_header->AddSuccessor(header); + } +} + void HGraph::SimplifyCFG() { - for (size_t i = post_order_.Size(); i > 0; --i) { - HBasicBlock* current = post_order_.Get(i - 1); - 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); - post_order_.InsertAt(i, pre_header); - - 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()); + // Simplify the CFG for future analysis, and code generation: + // (1): Split critical edges. + // (2): Simplify loops by having only one back edge, and one preheader. + for (size_t i = 0; i < blocks_.Size(); ++i) { + HBasicBlock* block = blocks_.Get(i); + if (block->GetSuccessors().Size() > 1) { + for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) { + HBasicBlock* successor = block->GetSuccessors().Get(j); + if (successor->GetPredecessors().Size() > 1) { + SplitCriticalEdge(block, successor); + --j; } - 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()); } + if (block->IsLoopHeader()) { + SimplifyLoop(block); + } + } +} + +bool HGraph::FindNaturalLoops() const { + for (size_t i = 0; i < blocks_.Size(); ++i) { + HBasicBlock* block = blocks_.Get(i); + if (block->IsLoopHeader()) { + HLoopInformation* info = block->GetLoopInformation(); + if (!info->Populate()) { + // Abort if the loop is non natural. We currently bailout in such cases. + return false; + } + } + } + return true; +} + +void HLoopInformation::PopulateRecursive(HBasicBlock* block) { + if (blocks_.IsBitSet(block->GetBlockId())) { + return; + } + + blocks_.SetBit(block->GetBlockId()); + block->SetInLoop(this); + for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { + PopulateRecursive(block->GetPredecessors().Get(i)); + } +} + +bool HLoopInformation::Populate() { + DCHECK_EQ(GetBackEdges().Size(), 1u); + HBasicBlock* back_edge = GetBackEdges().Get(0); + DCHECK(back_edge->GetDominator() != nullptr); + if (!header_->Dominates(back_edge)) { + // This loop is not natural. Do not bother going further. + return false; } + + // Populate this loop: starting with the back edge, recursively add predecessors + // that are not already part of that loop. Set the header as part of the loop + // to end the recursion. + // This is a recursive implementation of the algorithm described in + // "Advanced Compiler Design & Implementation" (Muchnick) p192. + blocks_.SetBit(header_->GetBlockId()); + PopulateRecursive(back_edge); + return true; +} + +HBasicBlock* HLoopInformation::GetPreHeader() const { + DCHECK_EQ(header_->GetPredecessors().Size(), 2u); + return header_->GetDominator(); +} + +bool HLoopInformation::Contains(const HBasicBlock& block) const { + return blocks_.IsBitSet(block.GetBlockId()); } -void HLoopInformation::SetPreHeader(HBasicBlock* block) { - DCHECK_EQ(header_->GetDominator(), block); - pre_header_ = block; +bool HLoopInformation::IsIn(const HLoopInformation& other) const { + return other.blocks_.IsBitSet(header_->GetBlockId()); +} + +bool HBasicBlock::Dominates(HBasicBlock* other) const { + // Walk up the dominator tree from `other`, to find out if `this` + // is an ancestor. + HBasicBlock* current = other; + while (current != nullptr) { + if (current == this) { + return true; + } + current = current->GetDominator(); + } + return false; } static void Add(HInstructionList* instruction_list, -- cgit v1.1