summaryrefslogtreecommitdiff
path: root/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'compiler')
-rw-r--r--compiler/optimizing/graph_visualizer.cc29
-rw-r--r--compiler/optimizing/gvn.cc9
-rw-r--r--compiler/optimizing/licm.cc13
-rw-r--r--compiler/optimizing/nodes.cc15
-rw-r--r--compiler/optimizing/nodes.h7
-rw-r--r--compiler/optimizing/register_allocator.cc4
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.cc16
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.h17
8 files changed, 65 insertions, 45 deletions
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 9efc13f61b..ccaf492f65 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -544,26 +544,19 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
}
}
- if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
- || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)
- || IsPass(HDeadCodeElimination::kInitialDeadCodeEliminationPassName)
- || IsPass(BoundsCheckElimination::kBoundsCheckEliminationPassName)
- || IsPass(RegisterAllocator::kRegisterAllocatorPassName)
- || IsPass(HGraphBuilder::kBuilderPassName)) {
- HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
- if (info == nullptr) {
- StartAttributeStream("loop") << "none";
+ HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation();
+ if (loop_info == nullptr) {
+ StartAttributeStream("loop") << "none";
+ } else {
+ StartAttributeStream("loop") << "B" << loop_info->GetHeader()->GetBlockId();
+ HLoopInformation* outer = loop_info->GetPreHeader()->GetLoopInformation();
+ if (outer != nullptr) {
+ StartAttributeStream("outer_loop") << "B" << outer->GetHeader()->GetBlockId();
} else {
- StartAttributeStream("loop") << "B" << info->GetHeader()->GetBlockId();
- HLoopInformation* outer = info->GetPreHeader()->GetLoopInformation();
- if (outer != nullptr) {
- StartAttributeStream("outer_loop") << "B" << outer->GetHeader()->GetBlockId();
- } else {
- StartAttributeStream("outer_loop") << "none";
- }
- StartAttributeStream("irreducible")
- << std::boolalpha << info->IsIrreducible() << std::noboolalpha;
+ StartAttributeStream("outer_loop") << "none";
}
+ StartAttributeStream("irreducible")
+ << std::boolalpha << loop_info->IsIrreducible() << std::noboolalpha;
}
if ((IsPass(HGraphBuilder::kBuilderPassName)
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index d0d52bf6cc..1e86b75075 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -454,11 +454,16 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
if (!set->IsEmpty()) {
if (block->IsLoopHeader()) {
- if (block->GetLoopInformation()->IsIrreducible()) {
+ if (block->GetLoopInformation()->ContainsIrreducibleLoop()) {
// To satisfy our linear scan algorithm, no instruction should flow in an irreducible
- // loop header.
+ // loop header. We clear the set at entry of irreducible loops and any loop containing
+ // an irreducible loop, as in both cases, GVN can extend the liveness of an instruction
+ // across the irreducible loop.
+ // Note that, if we're not compiling OSR, we could still do GVN and introduce
+ // phis at irreducible loop headers. We decided it was not worth the complexity.
set->Clear();
} else {
+ DCHECK(!block->GetLoopInformation()->IsIrreducible());
DCHECK_EQ(block->GetDominator(), block->GetLoopInformation()->GetPreHeader());
set->Kill(side_effects_.GetLoopEffects(block));
}
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 5a0b89c90a..7543cd6c54 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -101,16 +101,6 @@ void LICM::Run() {
SideEffects loop_effects = side_effects_.GetLoopEffects(block);
HBasicBlock* pre_header = loop_info->GetPreHeader();
- bool contains_irreducible_loop = false;
- if (graph_->HasIrreducibleLoops()) {
- for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
- if (it_loop.Current()->GetLoopInformation()->IsIrreducible()) {
- contains_irreducible_loop = true;
- break;
- }
- }
- }
-
for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
HBasicBlock* inner = it_loop.Current();
DCHECK(inner->IsInLoop());
@@ -123,11 +113,12 @@ void LICM::Run() {
visited->SetBit(inner->GetBlockId());
}
- if (contains_irreducible_loop) {
+ if (loop_info->ContainsIrreducibleLoop()) {
// We cannot licm in an irreducible loop, or in a natural loop containing an
// irreducible loop.
continue;
}
+ DCHECK(!loop_info->IsIrreducible());
// We can move an instruction that can throw only if it is the first
// throwing instruction in the loop. Note that the first potentially
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index eb9c381c4e..3910ca402a 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -442,8 +442,10 @@ void HGraph::SimplifyCFG() {
}
GraphAnalysisResult HGraph::AnalyzeLoops() const {
- // Order does not matter.
- for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+ // We iterate post order to ensure we visit inner loops before outer loops.
+ // `PopulateRecursive` needs this guarantee to know whether a natural loop
+ // contains an irreducible loop.
+ for (HPostOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
if (block->IsLoopHeader()) {
if (block->IsCatchBlock()) {
@@ -576,6 +578,14 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
blocks_.SetBit(block->GetBlockId());
block->SetInLoop(this);
+ if (block->IsLoopHeader()) {
+ // We're visiting loops in post-order, so inner loops must have been
+ // populated already.
+ DCHECK(block->GetLoopInformation()->IsPopulated());
+ if (block->GetLoopInformation()->IsIrreducible()) {
+ contains_irreducible_loop_ = true;
+ }
+ }
for (HBasicBlock* predecessor : block->GetPredecessors()) {
PopulateRecursive(predecessor);
}
@@ -679,6 +689,7 @@ void HLoopInformation::Populate() {
}
if (is_irreducible_loop) {
irreducible_ = true;
+ contains_irreducible_loop_ = true;
graph->SetHasIrreducibleLoops(true);
}
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 71ad8e57a7..6960ceb965 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -650,6 +650,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
: header_(header),
suspend_check_(nullptr),
irreducible_(false),
+ contains_irreducible_loop_(false),
back_edges_(graph->GetArena()->Adapter(kArenaAllocLoopInfoBackEdges)),
// Make bit vector growable, as the number of blocks may change.
blocks_(graph->GetArena(), graph->GetBlocks().size(), true, kArenaAllocLoopInfoBackEdges) {
@@ -657,6 +658,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
}
bool IsIrreducible() const { return irreducible_; }
+ bool ContainsIrreducibleLoop() const { return contains_irreducible_loop_; }
void Dump(std::ostream& os);
@@ -727,6 +729,10 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
bool HasBackEdgeNotDominatedByHeader() const;
+ bool IsPopulated() const {
+ return blocks_.GetHighestBitSet() != -1;
+ }
+
private:
// Internal recursive implementation of `Populate`.
void PopulateRecursive(HBasicBlock* block);
@@ -735,6 +741,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocLoopInfo> {
HBasicBlock* header_;
HSuspendCheck* suspend_check_;
bool irreducible_;
+ bool contains_irreducible_loop_;
ArenaVector<HBasicBlock*> back_edges_;
ArenaBitVector blocks_;
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index b1f9cbcdfa..4405b803e0 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1773,7 +1773,9 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
// therefore will not have a location for that instruction for `to`.
// Because the instruction is a constant or the ArtMethod, we don't need to
// do anything: it will be materialized in the irreducible loop.
- DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by));
+ DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by))
+ << defined_by->DebugName() << ":" << defined_by->GetId()
+ << " " << from->GetBlockId() << " -> " << to->GetBlockId();
return;
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 5534aeac29..36e0d993d1 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -309,17 +309,8 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
}
if (block->IsLoopHeader()) {
- if (kIsDebugBuild && block->GetLoopInformation()->IsIrreducible()) {
- // To satisfy our liveness algorithm, we need to ensure loop headers of
- // irreducible loops do not have any live-in instructions, except constants
- // and the current method, which can be trivially re-materialized.
- for (uint32_t idx : live_in->Indexes()) {
- HInstruction* instruction = GetInstructionFromSsaIndex(idx);
- DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
- DCHECK(!instruction->IsParameterValue());
- DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
- << instruction->DebugName();
- }
+ if (kIsDebugBuild) {
+ CheckNoLiveInIrreducibleLoop(*block);
}
size_t last_position = block->GetLoopInformation()->GetLifetimeEnd();
// For all live_in instructions at the loop header, we need to create a range
@@ -344,6 +335,9 @@ void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
// change in this loop), and the live_out set. If the live_out
// set does not change, there is no need to update the live_in set.
if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
+ if (kIsDebugBuild) {
+ CheckNoLiveInIrreducibleLoop(block);
+ }
changed = true;
}
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 1141fd1c76..1fcba8bc77 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -1260,6 +1260,23 @@ class SsaLivenessAnalysis : public ValueObject {
return instruction->GetType() == Primitive::kPrimNot;
}
+ void CheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const {
+ if (!block.IsLoopHeader() || !block.GetLoopInformation()->IsIrreducible()) {
+ return;
+ }
+ BitVector* live_in = GetLiveInSet(block);
+ // To satisfy our liveness algorithm, we need to ensure loop headers of
+ // irreducible loops do not have any live-in instructions, except constants
+ // and the current method, which can be trivially re-materialized.
+ for (uint32_t idx : live_in->Indexes()) {
+ HInstruction* instruction = GetInstructionFromSsaIndex(idx);
+ DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
+ DCHECK(!instruction->IsParameterValue());
+ DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
+ << instruction->DebugName();
+ }
+ }
+
HGraph* const graph_;
CodeGenerator* const codegen_;
ArenaVector<BlockInfo*> block_infos_;
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-20 04:55:24 +0000