summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/dead_code_elimination.cc9
-rw-r--r--compiler/optimizing/induction_var_range.h8
-rw-r--r--compiler/optimizing/loop_optimization.cc94
-rw-r--r--compiler/optimizing/loop_optimization.h10
-rw-r--r--compiler/optimizing/nodes.h13
5 files changed, 77 insertions, 57 deletions
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index aa3f26809a..adfe09ba9f 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -343,14 +343,7 @@ void HDeadCodeElimination::RemoveDeadInstructions() {
for (i.Advance(); !i.Done(); i.Advance()) {
HInstruction* inst = i.Current();
DCHECK(!inst->IsControlFlow());
- if (!inst->HasSideEffects()
- && !inst->CanThrow()
- && !inst->IsSuspendCheck()
- && !inst->IsNativeDebugInfo()
- // If we added an explicit barrier then we should keep it.
- && !inst->IsMemoryBarrier()
- && !inst->IsParameterValue()
- && !inst->HasUses()) {
+ if (inst->IsDeadAndRemovable()) {
block->RemoveInstruction(inst);
MaybeRecordStat(MethodCompilationStat::kRemovedDeadInstruction);
}
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 63850b34b8..df31e81169 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -131,6 +131,14 @@ class InductionVarRange {
*/
void Replace(HInstruction* instruction, HInstruction* fetch, HInstruction* replacement);
+ /**
+ * Incrementally updates induction information for just the given loop.
+ */
+ void ReVisit(HLoopInformation* loop) {
+ induction_analysis_->induction_.erase(loop);
+ induction_analysis_->VisitLoop(loop);
+ }
+
private:
/*
* Enum used in IsConstant() request.
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 93c6c20d7c..33fa87d568 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -69,33 +69,6 @@ static bool IsEmptyBody(HBasicBlock* block, ArenaSet<HInstruction*>* iset) {
i->GetNext() != nullptr && i->GetNext()->IsGoto();
}
-static HBasicBlock* TryRemovePreHeader(HBasicBlock* preheader, HBasicBlock* entry_block) {
- if (preheader->GetPredecessors().size() == 1) {
- HBasicBlock* entry = preheader->GetSinglePredecessor();
- HInstruction* anchor = entry->GetLastInstruction();
- // If the pre-header has a single predecessor we can remove it too if
- // either the pre-header just contains a goto, or if the predecessor
- // is not the entry block so we can push instructions backward
- // (moving computation into the entry block is too dangerous!).
- if (preheader->GetFirstInstruction() == nullptr ||
- preheader->GetFirstInstruction()->IsGoto() ||
- (entry != entry_block && anchor->IsGoto())) {
- // Push non-goto statements backward to empty the pre-header.
- for (HInstructionIterator it(preheader->GetInstructions()); !it.Done(); it.Advance()) {
- HInstruction* instruction = it.Current();
- if (!instruction->IsGoto()) {
- if (!instruction->CanBeMoved()) {
- return nullptr; // pushing failed to move all
- }
- it.Current()->MoveBefore(anchor);
- }
- }
- return entry;
- }
- }
- return nullptr;
-}
-
static void RemoveFromCycle(HInstruction* instruction) {
// A bit more elaborate than the usual instruction removal,
// since there may be a cycle in the use structure.
@@ -115,7 +88,8 @@ HLoopOptimization::HLoopOptimization(HGraph* graph,
loop_allocator_(nullptr),
top_loop_(nullptr),
last_loop_(nullptr),
- iset_(nullptr) {
+ iset_(nullptr),
+ induction_simplication_count_(0) {
}
void HLoopOptimization::Run() {
@@ -211,11 +185,17 @@ void HLoopOptimization::RemoveLoop(LoopNode* node) {
void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) {
for ( ; node != nullptr; node = node->next) {
+ int current_induction_simplification_count = induction_simplication_count_;
if (node->inner != nullptr) {
TraverseLoopsInnerToOuter(node->inner);
}
- // Visit loop after its inner loops have been visited.
+ // Visit loop after its inner loops have been visited. If the induction of any inner
+ // loop has been simplified, recompute the induction information of this loop first.
+ if (current_induction_simplification_count != induction_simplication_count_) {
+ induction_range_.ReVisit(node->loop_info);
+ }
SimplifyInduction(node);
+ SimplifyBlocks(node);
RemoveIfEmptyLoop(node);
}
}
@@ -233,11 +213,41 @@ void HLoopOptimization::SimplifyInduction(LoopNode* node) {
iset_->clear();
int32_t use_count = 0;
if (IsPhiInduction(phi, iset_) &&
- IsOnlyUsedAfterLoop(*node->loop_info, phi, &use_count) &&
+ IsOnlyUsedAfterLoop(node->loop_info, phi, &use_count) &&
TryReplaceWithLastValue(phi, use_count, preheader)) {
for (HInstruction* i : *iset_) {
RemoveFromCycle(i);
}
+ induction_simplication_count_++;
+ }
+ }
+}
+
+void HLoopOptimization::SimplifyBlocks(LoopNode* node) {
+ for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ // Remove instructions that are dead, usually resulting from eliminating induction cycles.
+ for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) {
+ HInstruction* instruction = i.Current();
+ if (instruction->IsDeadAndRemovable()) {
+ block->RemoveInstruction(instruction);
+ }
+ }
+ // Remove trivial control flow blocks from the loop body, again usually resulting
+ // from eliminating induction cycles.
+ 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) {
+ pred->ReplaceSuccessor(block, succ);
+ block->ClearDominanceInformation();
+ block->SetDominator(pred); // needed by next disconnect.
+ block->DisconnectAndDelete();
+ pred->AddDominatedBlock(succ);
+ succ->SetDominator(pred);
+ }
}
}
}
@@ -272,41 +282,31 @@ void HLoopOptimization::RemoveIfEmptyLoop(LoopNode* node) {
int32_t use_count = 0;
if (IsEmptyHeader(header, iset_) &&
IsEmptyBody(body, iset_) &&
- IsOnlyUsedAfterLoop(*node->loop_info, header->GetFirstPhi(), &use_count) &&
+ IsOnlyUsedAfterLoop(node->loop_info, header->GetFirstPhi(), &use_count) &&
TryReplaceWithLastValue(header->GetFirstPhi(), use_count, preheader)) {
- HBasicBlock* entry = TryRemovePreHeader(preheader, graph_->GetEntryBlock());
body->DisconnectAndDelete();
exit->RemovePredecessor(header);
header->RemoveSuccessor(exit);
header->ClearDominanceInformation();
header->SetDominator(preheader); // needed by next disconnect.
header->DisconnectAndDelete();
- // If allowed, remove preheader too, which may expose next outer empty loop
- // Otherwise, link preheader directly to exit to restore the flow graph.
- if (entry != nullptr) {
- entry->ReplaceSuccessor(preheader, exit);
- entry->AddDominatedBlock(exit);
- exit->SetDominator(entry);
- preheader->DisconnectAndDelete();
- } else {
- preheader->AddSuccessor(exit);
- preheader->AddInstruction(new (graph_->GetArena()) HGoto()); // global allocator
- preheader->AddDominatedBlock(exit);
- exit->SetDominator(preheader);
- }
+ preheader->AddSuccessor(exit);
+ preheader->AddInstruction(new (graph_->GetArena()) HGoto()); // global allocator
+ preheader->AddDominatedBlock(exit);
+ exit->SetDominator(preheader);
// Update hierarchy.
RemoveLoop(node);
}
}
-bool HLoopOptimization::IsOnlyUsedAfterLoop(const HLoopInformation& loop_info,
+bool HLoopOptimization::IsOnlyUsedAfterLoop(HLoopInformation* loop_info,
HInstruction* instruction,
/*out*/ int32_t* use_count) {
for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
HInstruction* user = use.GetUser();
if (iset_->find(user) == iset_->end()) { // not excluded?
HLoopInformation* other_loop_info = user->GetBlock()->GetLoopInformation();
- if (other_loop_info != nullptr && other_loop_info->IsIn(loop_info)) {
+ if (other_loop_info != nullptr && other_loop_info->IsIn(*loop_info)) {
return false;
}
++*use_count;
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index b2bf1c8507..9c4b462a1f 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -46,7 +46,7 @@ class HLoopOptimization : public HOptimization {
inner(nullptr),
previous(nullptr),
next(nullptr) {}
- const HLoopInformation* const loop_info;
+ HLoopInformation* const loop_info;
LoopNode* outer;
LoopNode* inner;
LoopNode* previous;
@@ -61,9 +61,10 @@ class HLoopOptimization : public HOptimization {
void TraverseLoopsInnerToOuter(LoopNode* node);
void SimplifyInduction(LoopNode* node);
+ void SimplifyBlocks(LoopNode* node);
void RemoveIfEmptyLoop(LoopNode* node);
- bool IsOnlyUsedAfterLoop(const HLoopInformation& loop_info,
+ bool IsOnlyUsedAfterLoop(HLoopInformation* loop_info,
HInstruction* instruction,
/*out*/ int32_t* use_count);
void ReplaceAllUses(HInstruction* instruction, HInstruction* replacement);
@@ -87,6 +88,11 @@ class HLoopOptimization : public HOptimization {
// Contents reside in phase-local heap memory.
ArenaSet<HInstruction*>* iset_;
+ // Counter that tracks how many induction cycles have been simplified. Useful
+ // to trigger incremental updates of induction variable analysis of outer loops
+ // when the induction of inner loops has changed.
+ int32_t induction_simplication_count_;
+
friend class LoopOptimizationTest;
DISALLOW_COPY_AND_ASSIGN(HLoopOptimization);
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 828c0e51c8..348f99d6df 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1931,6 +1931,19 @@ class HInstruction : public ArenaObject<kArenaAllocInstruction> {
return !HasEnvironmentUses() && GetUses().HasExactlyOneElement();
}
+ bool IsDeadAndRemovable() const {
+ return
+ !HasSideEffects() &&
+ !CanThrow() &&
+ !IsSuspendCheck() &&
+ !IsControlFlow() &&
+ !IsNativeDebugInfo() &&
+ !IsParameterValue() &&
+ !HasUses() &&
+ // If we added an explicit barrier then we should keep it.
+ !IsMemoryBarrier();
+ }
+
// Does this instruction strictly dominate `other_instruction`?
// Returns false if this instruction and `other_instruction` are the same.
// Aborts if this instruction and `other_instruction` are both phis.
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-12-31 03:22:17 +0000