summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/loop_optimization.cc93
-rw-r--r--test/618-checker-induction/src/Main.java39
2 files changed, 104 insertions, 28 deletions
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 51be1d1e91..55e1a2c409 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -28,6 +28,17 @@ static void RemoveFromCycle(HInstruction* instruction) {
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::SimplifyInduction(LoopNode* node) {
}
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 @@ void HLoopOptimization::RemoveIfEmptyInnerLoop(LoopNode* node) {
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 @@ void HLoopOptimization::RemoveIfEmptyInnerLoop(LoopNode* node) {
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;
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
index d8bc611c22..f85479aa54 100644
--- a/test/618-checker-induction/src/Main.java
+++ b/test/618-checker-induction/src/Main.java
@@ -92,6 +92,43 @@ public class Main {
}
}
+ /// CHECK-START: void Main.deadConditional(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
+ //
+ /// CHECK-START: void Main.deadConditional(int) loop_optimization (after)
+ /// CHECK-NOT: Phi loop:{{B\d+}}
+ public static void deadConditional(int n) {
+ int k = 0;
+ int m = 0;
+ for (int i = 0; i < n; i++) {
+ if (i == 3)
+ k = i;
+ else
+ m = i;
+ }
+ }
+
+ /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (after)
+ /// CHECK-NOT: Phi loop:{{B\d+}}
+ public static void deadConditionalCycle(int n) {
+ int k = 0;
+ int m = 0;
+ for (int i = 0; i < n; i++) {
+ if (i == 3)
+ k--;
+ else
+ m++;
+ }
+ }
+
+
/// CHECK-START: void Main.deadInduction() loop_optimization (before)
/// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
@@ -668,6 +705,8 @@ public class Main {
potentialInfiniteLoop(4);
deadNestedLoops();
deadNestedAndFollowingLoops();
+ deadConditional(4);
+ deadConditionalCycle(4);
deadInduction();
for (int i = 0; i < a.length; i++) {
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2026-01-04 10:35:36 +0000