summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/dead_code_elimination.cc24
-rw-r--r--compiler/optimizing/dead_code_elimination.h6
-rw-r--r--compiler/optimizing/graph_visualizer.cc4
-rw-r--r--compiler/optimizing/nodes.cc49
-rw-r--r--compiler/optimizing/nodes.h13
-rw-r--r--compiler/optimizing/optimizing_compiler.cc6
6 files changed, 70 insertions, 32 deletions
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index cd427c5ed8..6fbe75e802 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -47,6 +47,12 @@ static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) {
}
}
+static void MarkLoopHeadersContaining(const HBasicBlock& block, ArenaBitVector* set) {
+ for (HLoopInformationOutwardIterator it(block); !it.Done(); it.Advance()) {
+ set->SetBit(it.Current()->GetHeader()->GetBlockId());
+ }
+}
+
void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) {
if (stats_ != nullptr) {
stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction,
@@ -58,18 +64,24 @@ void HDeadCodeElimination::RemoveDeadBlocks() {
// Classify blocks as reachable/unreachable.
ArenaAllocator* allocator = graph_->GetArena();
ArenaBitVector live_blocks(allocator, graph_->GetBlocks().Size(), false);
+ ArenaBitVector affected_loops(allocator, graph_->GetBlocks().Size(), false);
+
MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks);
- // Remove all dead blocks. Process blocks in post-order, because removal needs
- // the block's chain of dominators.
+ // Remove all dead blocks. Iterate in post order because removal needs the
+ // block's chain of dominators and nested loops need to be updated from the
+ // inside out.
for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
- if (live_blocks.IsBitSet(block->GetBlockId())) {
- // If this block is part of a loop that is being dismantled, we need to
- // update its loop information.
- block->UpdateLoopInformation();
+ int id = block->GetBlockId();
+ if (live_blocks.IsBitSet(id)) {
+ if (affected_loops.IsBitSet(id)) {
+ DCHECK(block->IsLoopHeader());
+ block->GetLoopInformation()->Update();
+ }
} else {
MaybeRecordDeadBlock(block);
+ MarkLoopHeadersContaining(*block, &affected_loops);
block->DisconnectAndDelete();
}
}
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
index 0bea0fc1c2..59a57c4345 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -31,13 +31,13 @@ class HDeadCodeElimination : public HOptimization {
public:
HDeadCodeElimination(HGraph* graph,
OptimizingCompilerStats* stats = nullptr,
- const char* name = kDeadCodeEliminationPassName)
+ const char* name = kInitialDeadCodeEliminationPassName)
: HOptimization(graph, true, name, stats) {}
void Run() OVERRIDE;
- static constexpr const char* kDeadCodeEliminationPassName =
- "dead_code_elimination";
+ static constexpr const char* kInitialDeadCodeEliminationPassName = "dead_code_elimination";
+ static constexpr const char* kFinalDeadCodeEliminationPassName = "dead_code_elimination_final";
private:
void MaybeRecordDeadBlock(HBasicBlock* block);
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 7130127136..f5c630bf97 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -17,6 +17,7 @@
#include "graph_visualizer.h"
#include "code_generator.h"
+#include "dead_code_elimination.h"
#include "licm.h"
#include "nodes.h"
#include "optimization.h"
@@ -253,7 +254,8 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
}
}
output_ << " (liveness: " << instruction->GetLifetimePosition() << ")";
- } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)) {
+ } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
+ || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)) {
output_ << " ( loop_header:";
HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
if (info == nullptr) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index b9e58c7032..41adc7223e 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -17,6 +17,7 @@
#include "nodes.h"
#include "ssa_builder.h"
+#include "base/bit_vector-inl.h"
#include "utils/growable_array.h"
#include "scoped_thread_state_change.h"
@@ -346,6 +347,7 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
}
bool HLoopInformation::Populate() {
+ DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
for (size_t i = 0, e = GetBackEdges().Size(); i < e; ++i) {
HBasicBlock* back_edge = GetBackEdges().Get(i);
DCHECK(back_edge->GetDominator() != nullptr);
@@ -365,6 +367,39 @@ bool HLoopInformation::Populate() {
return true;
}
+void HLoopInformation::Update() {
+ HGraph* graph = header_->GetGraph();
+ for (uint32_t id : blocks_.Indexes()) {
+ HBasicBlock* block = graph->GetBlocks().Get(id);
+ // Reset loop information of non-header blocks inside the loop, except
+ // members of inner nested loops because those should already have been
+ // updated by their own LoopInformation.
+ if (block->GetLoopInformation() == this && block != header_) {
+ block->SetLoopInformation(nullptr);
+ }
+ }
+ blocks_.ClearAllBits();
+
+ if (back_edges_.IsEmpty()) {
+ // The loop has been dismantled, delete its suspend check and remove info
+ // from the header.
+ DCHECK(HasSuspendCheck());
+ header_->RemoveInstruction(suspend_check_);
+ header_->SetLoopInformation(nullptr);
+ header_ = nullptr;
+ suspend_check_ = nullptr;
+ } else {
+ if (kIsDebugBuild) {
+ for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
+ DCHECK(header_->Dominates(back_edges_.Get(i)));
+ }
+ }
+ // This loop still has reachable back edges. Repopulate the list of blocks.
+ bool populate_successful = Populate();
+ DCHECK(populate_successful);
+ }
+}
+
HBasicBlock* HLoopInformation::GetPreHeader() const {
return header_->GetDominator();
}
@@ -1049,20 +1084,6 @@ void HBasicBlock::DisconnectAndDelete() {
SetGraph(nullptr);
}
-void HBasicBlock::UpdateLoopInformation() {
- // Check if loop information points to a dismantled loop. If so, replace with
- // the loop information of a larger loop which contains this block, or nullptr
- // otherwise. We iterate in case the larger loop has been destroyed too.
- while (IsInLoop() && loop_information_->GetBackEdges().IsEmpty()) {
- if (IsLoopHeader()) {
- HSuspendCheck* suspend_check = loop_information_->GetSuspendCheck();
- DCHECK_EQ(suspend_check->GetBlock(), this);
- RemoveInstruction(suspend_check);
- }
- loop_information_ = loop_information_->GetPreHeader()->GetLoopInformation();
- }
-}
-
void HBasicBlock::MergeWith(HBasicBlock* other) {
DCHECK_EQ(GetGraph(), other->GetGraph());
DCHECK(GetDominatedBlocks().Contains(other));
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 031761e7f7..77b587e74f 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -436,6 +436,12 @@ class HLoopInformation : public ArenaObject<kArenaAllocMisc> {
// that is the header dominates the back edge.
bool Populate();
+ // Reanalyzes the loop by removing loop info from its blocks and re-running
+ // Populate(). If there are no back edges left, the loop info is completely
+ // removed as well as its SuspendCheck instruction. It must be run on nested
+ // inner loops first.
+ void Update();
+
// Returns whether this loop information contains `block`.
// Note that this loop information *must* be populated before entering this function.
bool Contains(const HBasicBlock& block) const;
@@ -705,14 +711,9 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
loop_information_ = info;
}
- // Checks if the loop information points to a valid loop. If the loop has been
- // dismantled (does not have a back edge any more), loop information is
- // removed or replaced with the information of the first valid outer loop.
- void UpdateLoopInformation();
-
bool IsInLoop() const { return loop_information_ != nullptr; }
- // Returns wheter this block dominates the blocked passed as parameter.
+ // Returns whether this block dominates the blocked passed as parameter.
bool Dominates(HBasicBlock* block) const;
size_t GetLifetimeStart() const { return lifetime_start_; }
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index e993d778d4..8bb5d8ebae 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -320,8 +320,10 @@ static void RunOptimizations(HGraph* graph,
const DexCompilationUnit& dex_compilation_unit,
PassInfoPrinter* pass_info_printer,
StackHandleScopeCollection* handles) {
- HDeadCodeElimination dce1(graph, stats);
- HDeadCodeElimination dce2(graph, stats, "dead_code_elimination_final");
+ HDeadCodeElimination dce1(graph, stats,
+ HDeadCodeElimination::kInitialDeadCodeEliminationPassName);
+ HDeadCodeElimination dce2(graph, stats,
+ HDeadCodeElimination::kFinalDeadCodeEliminationPassName);
HConstantFolding fold1(graph);
InstructionSimplifier simplify1(graph, stats);
HBooleanSimplifier boolean_simplify(graph);
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-12-16 05:20:29 +0000