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
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 02befc0..a6b4078 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -94,6 +94,16 @@
SideEffects loop_effects = side_effects_.GetLoopEffects(block);
HBasicBlock* pre_header = loop_info->GetPreHeader();
+ bool contains_irreducible_loop = false;
+ if (graph_->HasIrreducibleLoops()) {
+ for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
+ if (it_loop.Current()->GetLoopInformation()->IsIrreducible()) {
+ contains_irreducible_loop = true;
+ break;
+ }
+ }
+ }
+
for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
HBasicBlock* inner = it_loop.Current();
DCHECK(inner->IsInLoop());
@@ -104,6 +114,12 @@
}
visited.SetBit(inner->GetBlockId());
+ if (contains_irreducible_loop) {
+ // We cannot licm in an irreducible loop, or in a natural loop containing an
+ // irreducible loop.
+ continue;
+ }
+
// We can move an instruction that can throw only if it is the first
// throwing instruction in the loop. Note that the first potentially
// throwing instruction encountered that is not hoisted stops this