ART: Dead block removal
Adds a new pass which finds all unreachable blocks, typically due to
simplifying an if-condition to a constant, and removes them from the
graph. The patch also slightly generalizes the graph-transforming
operations.
Change-Id: Iff7c97f1d10b52886f3cd7401689ebe1bfdbf456
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 8045cc5..91cd60a 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -20,10 +20,78 @@
namespace art {
-void HDeadCodeElimination::Run() {
+static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) {
+ int block_id = block->GetBlockId();
+ if (visited->IsBitSet(block_id)) {
+ return;
+ }
+ visited->SetBit(block_id);
+
+ HInstruction* last_instruction = block->GetLastInstruction();
+ if (last_instruction->IsIf()) {
+ HIf* if_instruction = last_instruction->AsIf();
+ HInstruction* condition = if_instruction->InputAt(0);
+ if (!condition->IsIntConstant()) {
+ MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited);
+ MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited);
+ } else if (condition->AsIntConstant()->IsOne()) {
+ MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited);
+ } else {
+ DCHECK(condition->AsIntConstant()->IsZero());
+ MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited);
+ }
+ } else {
+ for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
+ MarkReachableBlocks(block->GetSuccessors().Get(i), visited);
+ }
+ }
+}
+
+void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) {
+ if (stats_ != nullptr) {
+ stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction,
+ block->GetPhis().CountSize() + block->GetInstructions().CountSize());
+ }
+}
+
+void HDeadCodeElimination::RemoveDeadBlocks() {
+ // Classify blocks as reachable/unreachable.
+ ArenaAllocator* allocator = graph_->GetArena();
+ ArenaBitVector live_blocks(allocator, graph_->GetBlocks().Size(), false);
+ MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks);
+
+ // Remove all dead blocks. Process blocks in post-order, because removal needs
+ // the block's chain of dominators.
+ for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ if (live_blocks.IsBitSet(block->GetBlockId())) {
+ continue;
+ }
+ MaybeRecordDeadBlock(block);
+ block->DisconnectAndDelete();
+ }
+
+ // Connect successive blocks created by dead branches. Order does not matter.
+ for (HReversePostOrderIterator it(*graph_); !it.Done();) {
+ HBasicBlock* block = it.Current();
+ if (block->IsEntryBlock() || block->GetSuccessors().Size() != 1u) {
+ it.Advance();
+ continue;
+ }
+ HBasicBlock* successor = block->GetSuccessors().Get(0);
+ if (successor->IsExitBlock() || successor->GetPredecessors().Size() != 1u) {
+ it.Advance();
+ continue;
+ }
+ block->MergeWith(successor);
+
+ // Reiterate on this block in case it can be merged with its new successor.
+ }
+}
+
+void HDeadCodeElimination::RemoveDeadInstructions() {
// Process basic blocks in post-order in the dominator tree, so that
- // a dead instruction depending on another dead instruction is
- // removed.
+ // a dead instruction depending on another dead instruction is removed.
for (HPostOrderIterator b(*graph_); !b.Done(); b.Advance()) {
HBasicBlock* block = b.Current();
// Traverse this block's instructions in backward order and remove
@@ -47,4 +115,9 @@
}
}
+void HDeadCodeElimination::Run() {
+ RemoveDeadBlocks();
+ RemoveDeadInstructions();
+}
+
} // namespace art