summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/gvn.cc34
-rw-r--r--compiler/optimizing/gvn.h82
-rw-r--r--compiler/optimizing/live_interval_test.cc51
-rw-r--r--compiler/optimizing/optimizing_compiler.cc4
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.h27
5 files changed, 139 insertions, 59 deletions
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 6e5f1bd203..781aad5c72 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -18,24 +18,12 @@
namespace art {
-void GlobalValueNumberer::Run() {
- ComputeSideEffects();
-
- sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_));
-
- // Do reverse post order to ensure the non back-edge predecessors of a block are
- // visited before the block itself.
- for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
- VisitBasicBlock(it.Current());
- }
-}
-
-void GlobalValueNumberer::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
+void SideEffectsAnalysis::UpdateLoopEffects(HLoopInformation* info, SideEffects effects) {
int id = info->GetHeader()->GetBlockId();
loop_effects_.Put(id, loop_effects_.Get(id).Union(effects));
}
-void GlobalValueNumberer::ComputeSideEffects() {
+void SideEffectsAnalysis::Run() {
if (kIsDebugBuild) {
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
@@ -80,17 +68,29 @@ void GlobalValueNumberer::ComputeSideEffects() {
UpdateLoopEffects(block->GetLoopInformation(), effects);
}
}
+ has_run_ = true;
}
-SideEffects GlobalValueNumberer::GetLoopEffects(HBasicBlock* block) const {
+SideEffects SideEffectsAnalysis::GetLoopEffects(HBasicBlock* block) const {
DCHECK(block->IsLoopHeader());
return loop_effects_.Get(block->GetBlockId());
}
-SideEffects GlobalValueNumberer::GetBlockEffects(HBasicBlock* block) const {
+SideEffects SideEffectsAnalysis::GetBlockEffects(HBasicBlock* block) const {
return block_effects_.Get(block->GetBlockId());
}
+void GlobalValueNumberer::Run() {
+ DCHECK(side_effects_.HasRun());
+ sets_.Put(graph_->GetEntryBlock()->GetBlockId(), new (allocator_) ValueSet(allocator_));
+
+ // Use the reverse post order to ensure the non back-edge predecessors of a block are
+ // visited before the block itself.
+ for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ VisitBasicBlock(it.Current());
+ }
+}
+
void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
ValueSet* set = nullptr;
const GrowableArray<HBasicBlock*>& predecessors = block->GetPredecessors();
@@ -110,7 +110,7 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
if (!set->IsEmpty()) {
if (block->IsLoopHeader()) {
DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
- set->Kill(GetLoopEffects(block));
+ set->Kill(side_effects_.GetLoopEffects(block));
} else if (predecessors.Size() > 1) {
for (size_t i = 0, e = predecessors.Size(); i < e; ++i) {
set->IntersectionWith(sets_.Get(predecessors.Get(i)->GetBlockId()));
diff --git a/compiler/optimizing/gvn.h b/compiler/optimizing/gvn.h
index 81f2c3fa87..2e38511532 100644
--- a/compiler/optimizing/gvn.h
+++ b/compiler/optimizing/gvn.h
@@ -220,46 +220,30 @@ class ValueSet : public ArenaObject<kArenaAllocMisc> {
DISALLOW_COPY_AND_ASSIGN(ValueSet);
};
-/**
- * Optimization phase that removes redundant instruction.
- */
-class GlobalValueNumberer : public ValueObject {
+class SideEffectsAnalysis : public HOptimization {
public:
- GlobalValueNumberer(ArenaAllocator* allocator, HGraph* graph)
- : graph_(graph),
- allocator_(allocator),
- block_effects_(allocator, graph->GetBlocks().Size()),
- loop_effects_(allocator, graph->GetBlocks().Size()),
- sets_(allocator, graph->GetBlocks().Size()) {
- size_t number_of_blocks = graph->GetBlocks().Size();
- block_effects_.SetSize(number_of_blocks);
- loop_effects_.SetSize(number_of_blocks);
- sets_.SetSize(number_of_blocks);
-
- for (size_t i = 0; i < number_of_blocks; ++i) {
- block_effects_.Put(i, SideEffects::None());
- loop_effects_.Put(i, SideEffects::None());
- }
- }
+ explicit SideEffectsAnalysis(HGraph* graph)
+ : HOptimization(graph, true, "SideEffects"),
+ graph_(graph),
+ block_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()),
+ loop_effects_(graph->GetArena(), graph->GetBlocks().Size(), SideEffects::None()) {}
- void Run();
+ SideEffects GetLoopEffects(HBasicBlock* block) const;
+ SideEffects GetBlockEffects(HBasicBlock* block) const;
- private:
- // Per-block GVN. Will also update the ValueSet of the dominated and
- // successor blocks.
- void VisitBasicBlock(HBasicBlock* block);
+ // Compute side effects of individual blocks and loops.
+ void Run();
- // Compute side effects of individual blocks and loops. The GVN algorithm
- // will use these side effects to update the ValueSet of individual blocks.
- void ComputeSideEffects();
+ bool HasRun() const { return has_run_; }
+ private:
void UpdateLoopEffects(HLoopInformation* info, SideEffects effects);
- SideEffects GetLoopEffects(HBasicBlock* block) const;
- SideEffects GetBlockEffects(HBasicBlock* block) const;
HGraph* graph_;
- ArenaAllocator* const allocator_;
+ // Checked in debug build, to ensure the pass has been run prior to
+ // running a pass that depends on it.
+ bool has_run_ = false;
// Side effects of individual blocks, that is the union of the side effects
// of the instructions in the block.
@@ -269,25 +253,55 @@ class GlobalValueNumberer : public ValueObject {
// blocks contained in that loop.
GrowableArray<SideEffects> loop_effects_;
+ ART_FRIEND_TEST(GVNTest, LoopSideEffects);
+ DISALLOW_COPY_AND_ASSIGN(SideEffectsAnalysis);
+};
+
+/**
+ * Optimization phase that removes redundant instruction.
+ */
+class GlobalValueNumberer : public ValueObject {
+ public:
+ GlobalValueNumberer(ArenaAllocator* allocator,
+ HGraph* graph,
+ const SideEffectsAnalysis& side_effects)
+ : graph_(graph),
+ allocator_(allocator),
+ side_effects_(side_effects),
+ sets_(allocator, graph->GetBlocks().Size(), nullptr) {}
+
+ void Run();
+
+ private:
+ // Per-block GVN. Will also update the ValueSet of the dominated and
+ // successor blocks.
+ void VisitBasicBlock(HBasicBlock* block);
+
+ HGraph* graph_;
+ ArenaAllocator* const allocator_;
+ const SideEffectsAnalysis& side_effects_;
+
// ValueSet for blocks. Initially null, but for an individual block they
// are allocated and populated by the dominator, and updated by all blocks
// in the path from the dominator to the block.
GrowableArray<ValueSet*> sets_;
- ART_FRIEND_TEST(GVNTest, LoopSideEffects);
DISALLOW_COPY_AND_ASSIGN(GlobalValueNumberer);
};
class GVNOptimization : public HOptimization {
public:
- explicit GVNOptimization(HGraph* graph) : HOptimization(graph, true, "GVN") {}
+ GVNOptimization(HGraph* graph, const SideEffectsAnalysis& side_effects)
+ : HOptimization(graph, true, "GVN"), side_effects_(side_effects) {}
void Run() OVERRIDE {
- GlobalValueNumberer gvn(graph_->GetArena(), graph_);
+ GlobalValueNumberer gvn(graph_->GetArena(), graph_, side_effects_);
gvn.Run();
}
private:
+ const SideEffectsAnalysis& side_effects_;
+
DISALLOW_COPY_AND_ASSIGN(GVNOptimization);
};
diff --git a/compiler/optimizing/live_interval_test.cc b/compiler/optimizing/live_interval_test.cc
index 3e4b83b0b1..ac8759c805 100644
--- a/compiler/optimizing/live_interval_test.cc
+++ b/compiler/optimizing/live_interval_test.cc
@@ -278,4 +278,55 @@ TEST(LiveInterval, SplitAt) {
}
}
+TEST(LiveInterval, AddLoopRange) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+
+ {
+ // Test when only used in a loop.
+ static constexpr size_t ranges[][2] = {{0, 4}};
+ LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+ interval->AddLoopRange(0, 8);
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_TRUE(range->GetNext() == nullptr);
+ ASSERT_EQ(range->GetStart(), 0u);
+ ASSERT_EQ(range->GetEnd(), 8u);
+ }
+
+ {
+ // Test when only used in a loop.
+ static constexpr size_t ranges[][2] = {{2, 4}};
+ LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+ interval->AddLoopRange(0, 8);
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_TRUE(range->GetNext() == nullptr);
+ ASSERT_EQ(range->GetStart(), 0u);
+ ASSERT_EQ(range->GetEnd(), 8u);
+ }
+
+ {
+ // Test when used just after the loop.
+ static constexpr size_t ranges[][2] = {{2, 4}, {8, 10}};
+ LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+ interval->AddLoopRange(0, 8);
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_TRUE(range->GetNext() == nullptr);
+ ASSERT_EQ(range->GetStart(), 0u);
+ ASSERT_EQ(range->GetEnd(), 10u);
+ }
+
+ {
+ // Test when use after the loop is after a lifetime hole.
+ static constexpr size_t ranges[][2] = {{2, 4}, {10, 12}};
+ LiveInterval* interval = BuildInterval(ranges, arraysize(ranges), &allocator);
+ interval->AddLoopRange(0, 8);
+ LiveRange* range = interval->GetFirstRange();
+ ASSERT_EQ(range->GetStart(), 0u);
+ ASSERT_EQ(range->GetEnd(), 8u);
+ range = range->GetNext();
+ ASSERT_EQ(range->GetStart(), 10u);
+ ASSERT_EQ(range->GetEnd(), 12u);
+ }
+}
+
} // namespace art
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 5bca73003e..7f99edb0a8 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -214,7 +214,8 @@ static void RunOptimizations(HGraph* graph,
HInliner inliner(graph, dex_compilation_unit, driver, stats);
HConstantFolding fold2(graph);
- GVNOptimization gvn(graph);
+ SideEffectsAnalysis side_effects(graph);
+ GVNOptimization gvn(graph, side_effects);
BoundsCheckElimination bce(graph);
InstructionSimplifier simplify2(graph);
@@ -229,6 +230,7 @@ static void RunOptimizations(HGraph* graph,
&simplify1,
&inliner,
&fold2,
+ &side_effects,
&gvn,
&bce,
&simplify2
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index a123313426..b0d38531e9 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -254,16 +254,28 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
void AddLoopRange(size_t start, size_t end) {
DCHECK(first_range_ != nullptr);
- while (first_range_ != nullptr && first_range_->GetEnd() < end) {
- DCHECK_LE(start, first_range_->GetStart());
- first_range_ = first_range_->GetNext();
+ DCHECK_LE(start, first_range_->GetStart());
+ // Find the range that covers the positions after the loop.
+ LiveRange* after_loop = first_range_;
+ LiveRange* last_in_loop = nullptr;
+ while (after_loop != nullptr && after_loop->GetEnd() < end) {
+ DCHECK_LE(start, after_loop->GetStart());
+ last_in_loop = after_loop;
+ after_loop = after_loop->GetNext();
}
- if (first_range_ == nullptr) {
+ if (after_loop == nullptr) {
// Uses are only in the loop.
first_range_ = last_range_ = new (allocator_) LiveRange(start, end, nullptr);
- } else {
+ } else if (after_loop->GetStart() <= end) {
+ first_range_ = after_loop;
// There are uses after the loop.
first_range_->start_ = start;
+ } else {
+ // The use after the loop is after a lifetime hole.
+ DCHECK(last_in_loop != nullptr);
+ first_range_ = last_in_loop;
+ first_range_->start_ = start;
+ first_range_->end_ = end;
}
}
@@ -479,10 +491,11 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
void Dump(std::ostream& stream) const {
stream << "ranges: { ";
LiveRange* current = first_range_;
- do {
+ while (current != nullptr) {
current->Dump(stream);
stream << " ";
- } while ((current = current->GetNext()) != nullptr);
+ current = current->GetNext();
+ }
stream << "}, uses: { ";
UsePosition* use = first_use_;
if (use != nullptr) {
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-21 23:09:19 +0000