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
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::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 @@
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 @@
// 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<size_t> 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 @@
// 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::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());
- }
- 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 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 HLoopInformation::SetPreHeader(HBasicBlock* block) {
- DCHECK_EQ(header_->GetDominator(), block);
- pre_header_ = 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() {
+ // 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;
+ }
+ }
+ }
+ 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());
+}
+
+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,