More loop-body simplifications.
Rationale:
This removes all dead induction from the CaffeineLogic loop,
giving yet the next performance boost (2700us->1700us).
Also, the runtime is now the same between a DX compiled
and JACK compiled version, giving confidence that all
recent introduced optimizations are generally useful
and something expected from any optimizing compiler.
Last, less realistic improvement will pale anything
seen so far, since it removes the full loop (still TBD).
Test: test-art-host
Change-Id: Id6b89f74b7d009616821dca195200933cc0eaaf2
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 51be1d1..55e1a2c 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -28,6 +28,17 @@
instruction->GetBlock()->RemoveInstructionOrPhi(instruction, /*ensure_safety=*/ false);
}
+// Detects a goto block and sets succ to the single successor.
+static bool IsGotoBlock(HBasicBlock* block, /*out*/ HBasicBlock** succ) {
+ if (block->GetPredecessors().size() == 1 &&
+ block->GetSuccessors().size() == 1 &&
+ block->IsSingleGoto()) {
+ *succ = block->GetSingleSuccessor();
+ return true;
+ }
+ return false;
+}
+
//
// Class methods.
//
@@ -178,31 +189,57 @@
}
void HLoopOptimization::SimplifyBlocks(LoopNode* node) {
- for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
- HBasicBlock* block = it.Current();
- // Remove instructions that are dead.
- for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) {
- HInstruction* instruction = i.Current();
- if (instruction->IsDeadAndRemovable()) {
- block->RemoveInstruction(instruction);
+ // Repeat the block simplifications until no more changes occur. Note that since
+ // each simplification consists of eliminating code (without introducing new code),
+ // this process is always finite.
+ bool changed;
+ do {
+ changed = false;
+ // Iterate over all basic blocks in the loop-body.
+ for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ // Remove dead instructions from the loop-body.
+ for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) {
+ HInstruction* instruction = i.Current();
+ if (instruction->IsDeadAndRemovable()) {
+ changed = true;
+ block->RemoveInstruction(instruction);
+ }
}
- }
- // Remove trivial control flow blocks from the loop-body.
- if (block->GetPredecessors().size() == 1 &&
- block->GetSuccessors().size() == 1 &&
- block->GetFirstInstruction()->IsGoto()) {
- HBasicBlock* pred = block->GetSinglePredecessor();
- HBasicBlock* succ = block->GetSingleSuccessor();
- if (succ->GetPredecessors().size() == 1) {
+ // Remove trivial control flow blocks from the loop-body.
+ HBasicBlock* succ = nullptr;
+ if (IsGotoBlock(block, &succ) && succ->GetPredecessors().size() == 1) {
+ // Trivial goto block can be removed.
+ HBasicBlock* pred = block->GetSinglePredecessor();
+ changed = true;
pred->ReplaceSuccessor(block, succ);
- block->ClearDominanceInformation();
- block->SetDominator(pred); // needed by next disconnect.
+ block->RemoveDominatedBlock(succ);
block->DisconnectAndDelete();
pred->AddDominatedBlock(succ);
succ->SetDominator(pred);
+ } else if (block->GetSuccessors().size() == 2) {
+ // Trivial if block can be bypassed to either branch.
+ HBasicBlock* succ0 = block->GetSuccessors()[0];
+ HBasicBlock* succ1 = block->GetSuccessors()[1];
+ HBasicBlock* meet0 = nullptr;
+ HBasicBlock* meet1 = nullptr;
+ if (succ0 != succ1 &&
+ IsGotoBlock(succ0, &meet0) &&
+ IsGotoBlock(succ1, &meet1) &&
+ meet0 == meet1 && // meets again
+ meet0 != block && // no self-loop
+ meet0->GetPhis().IsEmpty()) { // not used for merging
+ changed = true;
+ succ0->DisconnectAndDelete();
+ if (block->Dominates(meet0)) {
+ block->RemoveDominatedBlock(meet0);
+ succ1->AddDominatedBlock(meet0);
+ meet0->SetDominator(succ1);
+ }
+ }
}
}
- }
+ } while (changed);
}
void HLoopOptimization::RemoveIfEmptyInnerLoop(LoopNode* node) {
@@ -244,8 +281,7 @@
body->DisconnectAndDelete();
exit->RemovePredecessor(header);
header->RemoveSuccessor(exit);
- header->ClearDominanceInformation();
- header->SetDominator(preheader); // needed by next disconnect.
+ header->RemoveDominatedBlock(exit);
header->DisconnectAndDelete();
preheader->AddSuccessor(exit);
preheader->AddInstruction(new (graph_->GetArena()) HGoto()); // global allocator
@@ -259,22 +295,23 @@
bool HLoopOptimization::IsPhiInduction(HPhi* phi) {
ArenaSet<HInstruction*>* set = induction_range_.LookupCycle(phi);
if (set != nullptr) {
+ DCHECK(iset_->empty());
for (HInstruction* i : *set) {
- // Check that, other than phi, instruction are removable with uses contained in the cycle.
- // TODO: investigate what cases are no longer in the graph.
- if (i != phi) {
- if (!i->IsInBlock() || !i->IsRemovable()) {
- return false;
- }
+ // Check that, other than instructions that are no longer in the graph (removed earlier)
+ // each instruction is removable and, other than the phi, uses are contained in the cycle.
+ if (!i->IsInBlock()) {
+ continue;
+ } else if (!i->IsRemovable()) {
+ return false;
+ } else if (i != phi) {
for (const HUseListNode<HInstruction*>& use : i->GetUses()) {
if (set->find(use.GetUser()) == set->end()) {
return false;
}
}
}
+ iset_->insert(i); // copy
}
- DCHECK(iset_->empty());
- iset_->insert(set->begin(), set->end()); // copy
return true;
}
return false;