Optimizing: Rewrite DCE's MarkReachableBlocks().
Replace a recursive implementation with a loop using a work
list to avoid stack overflow that we would presumably hit
for 702-LargeBranchOffset in host debug build with -O0, once
the DCE block elimination is enabled for methods containing
try-catch.
Bug: 24133462
Change-Id: I41288ba368722bcb5d68259c7c147552c8928099
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 345ff72..b322759 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -16,49 +16,63 @@
#include "dead_code_elimination.h"
+#include "utils/array_ref.h"
#include "base/bit_vector-inl.h"
#include "ssa_phi_elimination.h"
namespace art {
-static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) {
- int block_id = block->GetBlockId();
- if (visited->IsBitSet(block_id)) {
- return;
- }
- visited->SetBit(block_id);
+static void MarkReachableBlocks(HGraph* graph, ArenaBitVector* visited) {
+ ArenaVector<HBasicBlock*> worklist(graph->GetArena()->Adapter());
+ constexpr size_t kDefaultWorlistSize = 8;
+ worklist.reserve(kDefaultWorlistSize);
+ visited->SetBit(graph->GetEntryBlock()->GetBlockId());
+ worklist.push_back(graph->GetEntryBlock());
- 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 if (last_instruction->IsPackedSwitch() &&
- last_instruction->AsPackedSwitch()->InputAt(0)->IsIntConstant()) {
- HPackedSwitch* switch_instruction = last_instruction->AsPackedSwitch();
- int32_t switch_value = switch_instruction->InputAt(0)->AsIntConstant()->GetValue();
- int32_t start_value = switch_instruction->GetStartValue();
- int32_t last_value = start_value + switch_instruction->GetNumEntries();
- for (int32_t case_value = start_value; case_value <= last_value; case_value++) {
- if (case_value == last_value) {
- MarkReachableBlocks(switch_instruction->GetDefaultBlock(), visited);
+ while (!worklist.empty()) {
+ HBasicBlock* block = worklist.back();
+ worklist.pop_back();
+ int block_id = block->GetBlockId();
+ DCHECK(visited->IsBitSet(block_id));
+
+ ArrayRef<HBasicBlock* const> live_successors(block->GetSuccessors());
+ HInstruction* last_instruction = block->GetLastInstruction();
+ if (last_instruction->IsIf()) {
+ HIf* if_instruction = last_instruction->AsIf();
+ HInstruction* condition = if_instruction->InputAt(0);
+ if (condition->IsIntConstant()) {
+ if (condition->AsIntConstant()->IsOne()) {
+ live_successors = live_successors.SubArray(0u, 1u);
+ DCHECK_EQ(live_successors[0], if_instruction->IfTrueSuccessor());
+ } else {
+ DCHECK(condition->AsIntConstant()->IsZero());
+ live_successors = live_successors.SubArray(1u, 1u);
+ DCHECK_EQ(live_successors[0], if_instruction->IfFalseSuccessor());
+ }
}
- if (case_value == switch_value) {
- MarkReachableBlocks(block->GetSuccessor(case_value - start_value), visited);
- break;
+ } else if (last_instruction->IsPackedSwitch()) {
+ HPackedSwitch* switch_instruction = last_instruction->AsPackedSwitch();
+ HInstruction* switch_input = switch_instruction->InputAt(0);
+ if (switch_input->IsIntConstant()) {
+ int32_t switch_value = switch_input->AsIntConstant()->GetValue();
+ int32_t start_value = switch_instruction->GetStartValue();
+ uint32_t switch_index = static_cast<uint32_t>(switch_value - start_value);
+ if (switch_index < switch_instruction->GetNumEntries()) {
+ live_successors = live_successors.SubArray(switch_index, 1u);
+ DCHECK_EQ(live_successors[0], block->GetSuccessor(switch_index));
+ } else {
+ live_successors = live_successors.SubArray(switch_instruction->GetNumEntries(), 1u);
+ DCHECK_EQ(live_successors[0], switch_instruction->GetDefaultBlock());
+ }
}
}
- } else {
- for (HBasicBlock* successor : block->GetSuccessors()) {
- MarkReachableBlocks(successor, visited);
+
+ for (HBasicBlock* successor : live_successors) {
+ // Add only those successors that have not been visited yet.
+ if (!visited->IsBitSet(successor->GetBlockId())) {
+ visited->SetBit(successor->GetBlockId());
+ worklist.push_back(successor);
+ }
}
}
}
@@ -82,7 +96,7 @@
ArenaBitVector live_blocks(allocator, graph_->GetBlocks().size(), false);
ArenaBitVector affected_loops(allocator, graph_->GetBlocks().size(), false);
- MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks);
+ MarkReachableBlocks(graph_, &live_blocks);
bool removed_one_or_more_blocks = false;
// Remove all dead blocks. Iterate in post order because removal needs the
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index d79852c..6b0ccf8 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2409,7 +2409,7 @@
// will be the block containing the next Dex opcode.
class HPackedSwitch : public HTemplateInstruction<1> {
public:
- HPackedSwitch(int32_t start_value, int32_t num_entries, HInstruction* input,
+ HPackedSwitch(int32_t start_value, uint32_t num_entries, HInstruction* input,
uint32_t dex_pc = kNoDexPc)
: HTemplateInstruction(SideEffects::None(), dex_pc),
start_value_(start_value),
@@ -2421,7 +2421,7 @@
int32_t GetStartValue() const { return start_value_; }
- int32_t GetNumEntries() const { return num_entries_; }
+ uint32_t GetNumEntries() const { return num_entries_; }
HBasicBlock* GetDefaultBlock() const {
// Last entry is the default block.
@@ -2431,7 +2431,7 @@
private:
int32_t start_value_;
- int32_t num_entries_;
+ uint32_t num_entries_;
DISALLOW_COPY_AND_ASSIGN(HPackedSwitch);
};
diff --git a/compiler/utils/array_ref.h b/compiler/utils/array_ref.h
index 303e0d5..48f0328 100644
--- a/compiler/utils/array_ref.h
+++ b/compiler/utils/array_ref.h
@@ -161,6 +161,15 @@
value_type* data() { return array_; }
const value_type* data() const { return array_; }
+ ArrayRef SubArray(size_type pos) const {
+ return SubArray(pos, size_ - pos);
+ }
+ ArrayRef SubArray(size_type pos, size_type length) const {
+ DCHECK_LE(pos, size());
+ DCHECK_LE(length, size() - pos);
+ return ArrayRef(array_ + pos, length);
+ }
+
private:
T* array_;
size_t size_;