1 files changed, 76 insertions, 3 deletions
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 8045cc5027..91cd60acce 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() {
   }
 }
 
+void HDeadCodeElimination::Run() {
+  RemoveDeadBlocks();
+  RemoveDeadInstructions();
+}
+
 }  // namespace art