diff options
author | 2016-01-05 15:55:41 +0000 | |
---|---|---|
committer | 2016-01-14 15:00:20 +0000 | |
commit | 15bd22849ee6a1ffb3fb3630f686c2870bdf1bbc (patch) | |
tree | a261601589163faa4538bcf1c9d156e8ec4a42b3 /compiler/optimizing/graph_checker.cc | |
parent | 5b7b5ddb515828c93f0c2aec67aa513c32d0de22 (diff) |
Implement irreducible loop support in optimizing.
So we don't fallback to the interpreter in the presence of
irreducible loops.
Implications:
- A loop pre-header does not necessarily dominate a loop header.
- Non-constant redundant phis will be kept in loop headers, to
satisfy our linear scan register allocation algorithm.
- while-graph optimizations, such as gvn, licm, lse, and dce
need to know when they are dealing with irreducible loops.
Change-Id: I2cea8934ce0b40162d215353497c7f77d6c9137e
Diffstat (limited to 'compiler/optimizing/graph_checker.cc')
-rw-r--r-- | compiler/optimizing/graph_checker.cc | 52 |
1 files changed, 32 insertions, 20 deletions
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 6d0bdbe19b..d60f3e31a5 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -391,6 +391,15 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) { } } + // Ensure dominated blocks have `block` as the dominator. + for (HBasicBlock* dominated : block->GetDominatedBlocks()) { + if (dominated->GetDominator() != block) { + AddError(StringPrintf("Block %d should be the dominator of %d.", + block->GetBlockId(), + dominated->GetBlockId())); + } + } + // Ensure there is no critical edge (i.e., an edge connecting a // block with multiple successors to a block with multiple // predecessors). Exceptional edges are synthesized and hence @@ -467,13 +476,7 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { int id = loop_header->GetBlockId(); HLoopInformation* loop_information = loop_header->GetLoopInformation(); - // Ensure the pre-header block is first in the list of predecessors of a loop - // header and that the header block is its only successor. - if (!loop_header->IsLoopPreHeaderFirstPredecessor()) { - AddError(StringPrintf( - "Loop pre-header is not the first predecessor of the loop header %d.", - id)); - } else if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) { + if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) { AddError(StringPrintf( "Loop pre-header %d of loop defined by header %d has %zu successors.", loop_information->GetPreHeader()->GetBlockId(), @@ -532,30 +535,39 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { } } - // Ensure all blocks in the loop are live and dominated by the loop header. + // If this is a nested loop, ensure the outer loops contain a superset of the blocks. + for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) { + HLoopInformation* outer_info = it.Current(); + if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) { + AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of " + "an outer loop defined by header %d.", + id, + outer_info->GetHeader()->GetBlockId())); + } + } + + // Ensure the pre-header block is first in the list of predecessors of a loop + // header and that the header block is its only successor. + if (!loop_header->IsLoopPreHeaderFirstPredecessor()) { + AddError(StringPrintf( + "Loop pre-header is not the first predecessor of the loop header %d.", + id)); + } + + // Ensure all blocks in the loop are live and dominated by the loop header in + // the case of natural loops. for (uint32_t i : loop_blocks.Indexes()) { HBasicBlock* loop_block = GetGraph()->GetBlocks()[i]; if (loop_block == nullptr) { AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.", id, i)); - } else if (!loop_header->Dominates(loop_block)) { + } else if (!loop_information->IsIrreducible() && !loop_header->Dominates(loop_block)) { AddError(StringPrintf("Loop block %d not dominated by loop header %d.", i, id)); } } - - // If this is a nested loop, ensure the outer loops contain a superset of the blocks. - for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) { - HLoopInformation* outer_info = it.Current(); - if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) { - AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of " - "an outer loop defined by header %d.", - id, - outer_info->GetHeader()->GetBlockId())); - } - } } void SSAChecker::VisitInstruction(HInstruction* instruction) { |