Disable DCE when there are irreducible loops.
Also ensure an instruction that requires an environment
does have one.
Change-Id: I41a8460e05ef320f872197d3be7847e7ffaa6ee8
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 86a695b..e170e37 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -89,15 +89,18 @@
}
void HDeadCodeElimination::RemoveDeadBlocks() {
+ if (graph_->HasIrreducibleLoops()) {
+ // Do not eliminate dead blocks if the graph has irreducible loops. We could
+ // support it, but that would require changes in our loop representation to handle
+ // multiple entry points. We decided it was not worth the complexity.
+ return;
+ }
// Classify blocks as reachable/unreachable.
ArenaAllocator* allocator = graph_->GetArena();
ArenaBitVector live_blocks(allocator, graph_->GetBlocks().size(), false);
MarkReachableBlocks(graph_, &live_blocks);
bool removed_one_or_more_blocks = false;
- // If the graph has irreducible loops we need to reset all graph analysis we have done
- // before: the irreducible loop can be turned into a reducible one.
- // For simplicity, we do the full computation regardless of the type of the loops.
bool rerun_dominance_and_loop_analysis = false;
// Remove all dead blocks. Iterate in post order because removal needs the
@@ -105,9 +108,6 @@
// inside out.
for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
- if (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible()) {
- rerun_dominance_and_loop_analysis = true;
- }
int id = block->GetBlockId();
if (!live_blocks.IsBitSet(id)) {
MaybeRecordDeadBlock(block);
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 9439ba0..3113677 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -484,6 +484,18 @@
loop_information->GetPreHeader()->GetSuccessors().size()));
}
+ if (loop_information->GetSuspendCheck() == nullptr) {
+ AddError(StringPrintf(
+ "Loop with header %d does not have a suspend check.",
+ loop_header->GetBlockId()));
+ }
+
+ if (loop_information->GetSuspendCheck() != loop_header->GetFirstInstructionDisregardMoves()) {
+ AddError(StringPrintf(
+ "Loop header %d does not have the loop suspend check as the first instruction.",
+ loop_header->GetBlockId()));
+ }
+
// Ensure the loop header has only one incoming branch and the remaining
// predecessors are back edges.
size_t num_preds = loop_header->GetPredecessors().size();
@@ -589,6 +601,14 @@
}
}
+ if (instruction->NeedsEnvironment() && !instruction->HasEnvironment()) {
+ AddError(StringPrintf("Instruction %s:%d in block %d requires an environment "
+ "but does not have one.",
+ instruction->DebugName(),
+ instruction->GetId(),
+ current_block_->GetBlockId()));
+ }
+
// Ensure an instruction having an environment is dominated by the
// instructions contained in the environment.
for (HEnvironment* environment = instruction->GetEnvironment();
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 854d92a..2eabadf 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -167,11 +167,7 @@
void HGraph::ClearLoopInformation() {
SetHasIrreducibleLoops(false);
for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
- HBasicBlock* current = it.Current();
- if (current->IsLoopHeader()) {
- current->RemoveInstruction(current->GetLoopInformation()->GetSuspendCheck());
- }
- current->SetLoopInformation(nullptr);
+ it.Current()->SetLoopInformation(nullptr);
}
}
@@ -180,6 +176,14 @@
dominator_ = nullptr;
}
+HInstruction* HBasicBlock::GetFirstInstructionDisregardMoves() const {
+ HInstruction* instruction = GetFirstInstruction();
+ while (instruction->IsParallelMove()) {
+ instruction = instruction->GetNext();
+ }
+ return instruction;
+}
+
void HGraph::ComputeDominanceInformation() {
DCHECK(reverse_post_order_.empty());
reverse_post_order_.reserve(blocks_.size());
@@ -457,6 +461,10 @@
}
if (block->IsLoopHeader()) {
SimplifyLoop(block);
+ } else if (!block->IsEntryBlock() && block->GetFirstInstruction()->IsSuspendCheck()) {
+ // We are being called by the dead code elimiation pass, and what used to be
+ // a loop got dismantled. Just remove the suspend check.
+ block->RemoveInstruction(block->GetFirstInstruction());
}
}
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 859d570..e222ef7 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -860,6 +860,8 @@
HInstruction* GetLastPhi() const { return phis_.last_instruction_; }
const HInstructionList& GetPhis() const { return phis_; }
+ HInstruction* GetFirstInstructionDisregardMoves() const;
+
void AddSuccessor(HBasicBlock* block) {
successors_.push_back(block);
block->predecessors_.push_back(this);
diff --git a/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
index 30a648d..971ad84 100644
--- a/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
+++ b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
@@ -91,9 +91,7 @@
goto :other_loop_entry
.end method
-# Check that if a irreducible loop entry is dead, the loop can become
-# natural.
-# We start with:
+# Check that dce does not apply for irreducible loops.
#
# entry
# / \
@@ -106,18 +104,8 @@
## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination (before)
## CHECK: irreducible:true
-# And end with:
-#
-# entry
-# /
-# /
-# loop_entry
-# / \-
-# exit \-
-# other_loop_entry
-
## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination (after)
-## CHECK-NOT: irreducible:true
+## CHECK: irreducible:true
.method public static dce(I)I
.registers 3
const/16 v0, 42