summaryrefslogtreecommitdiff
path: root/compiler/optimizing/graph_checker.cc
diff options
context:
space:
mode:
author Nicolas Geoffray <ngeoffray@google.com> 2016-01-05 15:55:41 +0000
committer Nicolas Geoffray <ngeoffray@google.com> 2016-01-14 15:00:20 +0000
commit15bd22849ee6a1ffb3fb3630f686c2870bdf1bbc (patch)
treea261601589163faa4538bcf1c9d156e8ec4a42b3 /compiler/optimizing/graph_checker.cc
parent5b7b5ddb515828c93f0c2aec67aa513c32d0de22 (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.cc52
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) {