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/nodes.h b/compiler/optimizing/nodes.h
index b89487f..18a8225 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -97,6 +97,9 @@
void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list);
void Add(const HInstructionList& instruction_list);
+ // Return the number of instructions in the list. This is an expensive operation.
+ size_t CountSize() const;
+
private:
HInstruction* first_instruction_;
HInstruction* last_instruction_;
@@ -168,7 +171,8 @@
// Inline this graph in `outer_graph`, replacing the given `invoke` instruction.
void InlineInto(HGraph* outer_graph, HInvoke* invoke);
- void MergeEmptyBranches(HBasicBlock* start_block, HBasicBlock* end_block);
+ // Removes `block` from the graph.
+ void DeleteDeadBlock(HBasicBlock* block);
void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
void SimplifyLoop(HBasicBlock* header);
@@ -248,8 +252,9 @@
return CreateConstant(value, &cached_long_constants_);
}
- private:
HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
+
+ private:
void VisitBlockForDominatorTree(HBasicBlock* block,
HBasicBlock* predecessor,
GrowableArray<size_t>* visits);
@@ -451,6 +456,7 @@
HBasicBlock* GetDominator() const { return dominator_; }
void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); }
+ void RemoveDominatedBlock(HBasicBlock* block) { dominated_blocks_.Delete(block); }
void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) {
for (size_t i = 0, e = dominated_blocks_.Size(); i < e; ++i) {
if (dominated_blocks_.Get(i) == existing) {
@@ -550,7 +556,7 @@
// that this method does not update the graph, reverse post order, loop
// information, nor make sure the blocks are consistent (for example ending
// with a control flow instruction).
- void MergeWith(HBasicBlock* other);
+ void MergeWithInlined(HBasicBlock* other);
// Replace `this` with `other`. Predecessors, successors, and dominated blocks
// of `this` are moved to `other`.
@@ -559,12 +565,17 @@
// with a control flow instruction).
void ReplaceWith(HBasicBlock* other);
- // Disconnects `this` from all its predecessors, successors and the dominator.
- // It assumes that `this` does not dominate any blocks.
- // Note that this method does not update the graph, reverse post order, loop
- // information, nor make sure the blocks are consistent (for example ending
- // with a control flow instruction).
- void DisconnectFromAll();
+ // Merge `other` at the end of `this`. This method updates loops, reverse post
+ // order, links to predecessors, successors, dominators and deletes the block
+ // from the graph. The two blocks must be successive, i.e. `this` the only
+ // predecessor of `other` and vice versa.
+ void MergeWith(HBasicBlock* other);
+
+ // Disconnects `this` from all its predecessors, successors and dominator,
+ // removes it from all loops it is included in and eventually from the graph.
+ // The block must not dominate any other block. Predecessors and successors
+ // are safely updated.
+ void DisconnectAndDelete();
void AddInstruction(HInstruction* instruction);
void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
@@ -2746,6 +2757,7 @@
size_t InputCount() const OVERRIDE { return inputs_.Size(); }
void AddInput(HInstruction* input);
+ void RemoveInputAt(size_t index);
Primitive::Type GetType() const OVERRIDE { return type_; }
void SetType(Primitive::Type type) { type_ = type; }