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/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index d399bc2..5ab4547 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -179,9 +179,11 @@
ProcessInstruction(inst_it.Current());
}
- if (block->IsCatchBlock()) {
- // By blocking all registers at the top of each catch block, we force
- // intervals used after catch to spill.
+ if (block->IsCatchBlock() ||
+ (block->GetLoopInformation() != nullptr && block->GetLoopInformation()->IsIrreducible())) {
+ // By blocking all registers at the top of each catch block or irreducible loop, we force
+ // intervals belonging to the live-in set of the catch/header block to be spilled.
+ // TODO(ngeoffray): Phis in this block could be allocated in register.
size_t position = block->GetLifetimeStart();
BlockRegisters(position, position + 1);
}
@@ -1864,8 +1866,10 @@
// Resolve non-linear control flow across branches. Order does not matter.
for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
- if (block->IsCatchBlock()) {
- // Instructions live at the top of catch blocks were forced to spill.
+ if (block->IsCatchBlock() ||
+ (block->GetLoopInformation() != nullptr && block->GetLoopInformation()->IsIrreducible())) {
+ // Instructions live at the top of catch blocks or irreducible loop header
+ // were forced to spill.
if (kIsDebugBuild) {
BitVector* live = liveness_.GetLiveInSet(*block);
for (uint32_t idx : live->Indexes()) {