aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/SimpleLoopUnswitch.cpp')
-rw-r--r--lib/Transforms/Scalar/SimpleLoopUnswitch.cpp130
1 files changed, 80 insertions, 50 deletions
diff --git a/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
index 5a67178cef37..aeac6f548b32 100644
--- a/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
@@ -1,9 +1,8 @@
///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
@@ -181,14 +180,9 @@ static void buildPartialUnswitchConditionalBranch(BasicBlock &BB,
BasicBlock &UnswitchedSucc,
BasicBlock &NormalSucc) {
IRBuilder<> IRB(&BB);
- Value *Cond = Invariants.front();
- for (Value *Invariant :
- make_range(std::next(Invariants.begin()), Invariants.end()))
- if (Direction)
- Cond = IRB.CreateOr(Cond, Invariant);
- else
- Cond = IRB.CreateAnd(Cond, Invariant);
-
+
+ Value *Cond = Direction ? IRB.CreateOr(Invariants) :
+ IRB.CreateAnd(Invariants);
IRB.CreateCondBr(Cond, Direction ? &UnswitchedSucc : &NormalSucc,
Direction ? &NormalSucc : &UnswitchedSucc);
}
@@ -268,7 +262,8 @@ static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB,
/// loops reachable and need to move the current loop up the loop nest or even
/// to an entirely separate nest.
static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader,
- DominatorTree &DT, LoopInfo &LI) {
+ DominatorTree &DT, LoopInfo &LI,
+ MemorySSAUpdater *MSSAU) {
// If the loop is already at the top level, we can't hoist it anywhere.
Loop *OldParentL = L.getParentLoop();
if (!OldParentL)
@@ -329,7 +324,8 @@ static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader,
// unswitching it is possible to get new non-dedicated exits out of parent
// loop so let's conservatively form dedicated exit blocks and figure out
// if we can optimize later.
- formDedicatedExitBlocks(OldContainingL, &DT, &LI, /*PreserveLCSSA*/ true);
+ formDedicatedExitBlocks(OldContainingL, &DT, &LI, MSSAU,
+ /*PreserveLCSSA*/ true);
}
}
@@ -536,7 +532,10 @@ static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
// If this was full unswitching, we may have changed the nesting relationship
// for this loop so hoist it to its correct parent if needed.
if (FullUnswitch)
- hoistLoopToNewParent(L, *NewPH, DT, LI);
+ hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+
+ if (MSSAU && VerifyMemorySSA)
+ MSSAU->getMemorySSA()->verifyMemorySSA();
LLVM_DEBUG(dbgs() << " done: unswitching trivial branch...\n");
++NumTrivial;
@@ -590,11 +589,13 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
ExitCaseIndices.push_back(Case.getCaseIndex());
}
BasicBlock *DefaultExitBB = nullptr;
+ SwitchInstProfUpdateWrapper::CaseWeightOpt DefaultCaseWeight =
+ SwitchInstProfUpdateWrapper::getSuccessorWeight(SI, 0);
if (!L.contains(SI.getDefaultDest()) &&
areLoopExitPHIsLoopInvariant(L, *ParentBB, *SI.getDefaultDest()) &&
- !isa<UnreachableInst>(SI.getDefaultDest()->getTerminator()))
+ !isa<UnreachableInst>(SI.getDefaultDest()->getTerminator())) {
DefaultExitBB = SI.getDefaultDest();
- else if (ExitCaseIndices.empty())
+ } else if (ExitCaseIndices.empty())
return false;
LLVM_DEBUG(dbgs() << " unswitching trivial switch...\n");
@@ -618,8 +619,11 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
// Store the exit cases into a separate data structure and remove them from
// the switch.
- SmallVector<std::pair<ConstantInt *, BasicBlock *>, 4> ExitCases;
+ SmallVector<std::tuple<ConstantInt *, BasicBlock *,
+ SwitchInstProfUpdateWrapper::CaseWeightOpt>,
+ 4> ExitCases;
ExitCases.reserve(ExitCaseIndices.size());
+ SwitchInstProfUpdateWrapper SIW(SI);
// We walk the case indices backwards so that we remove the last case first
// and don't disrupt the earlier indices.
for (unsigned Index : reverse(ExitCaseIndices)) {
@@ -629,9 +633,10 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
if (!ExitL || ExitL->contains(OuterL))
OuterL = ExitL;
// Save the value of this case.
- ExitCases.push_back({CaseI->getCaseValue(), CaseI->getCaseSuccessor()});
+ auto W = SIW.getSuccessorWeight(CaseI->getSuccessorIndex());
+ ExitCases.emplace_back(CaseI->getCaseValue(), CaseI->getCaseSuccessor(), W);
// Delete the unswitched cases.
- SI.removeCase(CaseI);
+ SIW.removeCase(CaseI);
}
if (SE) {
@@ -669,6 +674,7 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
// Now add the unswitched switch.
auto *NewSI = SwitchInst::Create(LoopCond, NewPH, ExitCases.size(), OldPH);
+ SwitchInstProfUpdateWrapper NewSIW(*NewSI);
// Rewrite the IR for the unswitched basic blocks. This requires two steps.
// First, we split any exit blocks with remaining in-loop predecessors. Then
@@ -696,9 +702,9 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
}
// Note that we must use a reference in the for loop so that we update the
// container.
- for (auto &CasePair : reverse(ExitCases)) {
+ for (auto &ExitCase : reverse(ExitCases)) {
// Grab a reference to the exit block in the pair so that we can update it.
- BasicBlock *ExitBB = CasePair.second;
+ BasicBlock *ExitBB = std::get<1>(ExitCase);
// If this case is the last edge into the exit block, we can simply reuse it
// as it will no longer be a loop exit. No mapping necessary.
@@ -720,27 +726,39 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
/*FullUnswitch*/ true);
}
// Update the case pair to point to the split block.
- CasePair.second = SplitExitBB;
+ std::get<1>(ExitCase) = SplitExitBB;
}
// Now add the unswitched cases. We do this in reverse order as we built them
// in reverse order.
- for (auto CasePair : reverse(ExitCases)) {
- ConstantInt *CaseVal = CasePair.first;
- BasicBlock *UnswitchedBB = CasePair.second;
+ for (auto &ExitCase : reverse(ExitCases)) {
+ ConstantInt *CaseVal = std::get<0>(ExitCase);
+ BasicBlock *UnswitchedBB = std::get<1>(ExitCase);
- NewSI->addCase(CaseVal, UnswitchedBB);
+ NewSIW.addCase(CaseVal, UnswitchedBB, std::get<2>(ExitCase));
}
// If the default was unswitched, re-point it and add explicit cases for
// entering the loop.
if (DefaultExitBB) {
- NewSI->setDefaultDest(DefaultExitBB);
+ NewSIW->setDefaultDest(DefaultExitBB);
+ NewSIW.setSuccessorWeight(0, DefaultCaseWeight);
// We removed all the exit cases, so we just copy the cases to the
// unswitched switch.
- for (auto Case : SI.cases())
- NewSI->addCase(Case.getCaseValue(), NewPH);
+ for (const auto &Case : SI.cases())
+ NewSIW.addCase(Case.getCaseValue(), NewPH,
+ SIW.getSuccessorWeight(Case.getSuccessorIndex()));
+ } else if (DefaultCaseWeight) {
+ // We have to set branch weight of the default case.
+ uint64_t SW = *DefaultCaseWeight;
+ for (const auto &Case : SI.cases()) {
+ auto W = SIW.getSuccessorWeight(Case.getSuccessorIndex());
+ assert(W &&
+ "case weight must be defined as default case weight is defined");
+ SW += *W;
+ }
+ NewSIW.setSuccessorWeight(0, SW);
}
// If we ended up with a common successor for every path through the switch
@@ -762,10 +780,10 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
continue;
}
CommonSuccBB->removePredecessor(BB,
- /*DontDeleteUselessPHIs*/ true);
+ /*KeepOneInputPHIs*/ true);
}
// Now nuke the switch and replace it with a direct branch.
- SI.eraseFromParent();
+ SIW.eraseFromParent();
BranchInst::Create(CommonSuccBB, BB);
} else if (DefaultExitBB) {
assert(SI.getNumCases() > 0 &&
@@ -775,8 +793,11 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
// being simple and keeping the number of edges from this switch to
// successors the same, and avoiding any PHI update complexity.
auto LastCaseI = std::prev(SI.case_end());
+
SI.setDefaultDest(LastCaseI->getCaseSuccessor());
- SI.removeCase(LastCaseI);
+ SIW.setSuccessorWeight(
+ 0, SIW.getSuccessorWeight(LastCaseI->getSuccessorIndex()));
+ SIW.removeCase(LastCaseI);
}
// Walk the unswitched exit blocks and the unswitched split blocks and update
@@ -789,9 +810,8 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
DTUpdates.push_back({DT.Insert, OldPH, UnswitchedExitBB});
}
for (auto SplitUnswitchedPair : SplitExitBBMap) {
- auto *UnswitchedBB = SplitUnswitchedPair.second;
- DTUpdates.push_back({DT.Delete, ParentBB, UnswitchedBB});
- DTUpdates.push_back({DT.Insert, OldPH, UnswitchedBB});
+ DTUpdates.push_back({DT.Delete, ParentBB, SplitUnswitchedPair.first});
+ DTUpdates.push_back({DT.Insert, OldPH, SplitUnswitchedPair.second});
}
DT.applyUpdates(DTUpdates);
@@ -805,7 +825,10 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
// We may have changed the nesting relationship for this loop so hoist it to
// its correct parent if needed.
- hoistLoopToNewParent(L, *NewPH, DT, LI);
+ hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+
+ if (MSSAU && VerifyMemorySSA)
+ MSSAU->getMemorySSA()->verifyMemorySSA();
++NumTrivial;
++NumSwitches;
@@ -848,6 +871,10 @@ static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT,
// Check if there are any side-effecting instructions (e.g. stores, calls,
// volatile loads) in the part of the loop that the code *would* execute
// without unswitching.
+ if (MSSAU) // Possible early exit with MSSA
+ if (auto *Defs = MSSAU->getMemorySSA()->getBlockDefs(CurrentBB))
+ if (!isa<MemoryPhi>(*Defs->begin()) || (++Defs->begin() != Defs->end()))
+ return Changed;
if (llvm::any_of(*CurrentBB,
[](Instruction &I) { return I.mayHaveSideEffects(); }))
return Changed;
@@ -1066,7 +1093,7 @@ static BasicBlock *buildClonedLoopBlocks(
continue;
ClonedSuccBB->removePredecessor(ClonedParentBB,
- /*DontDeleteUselessPHIs*/ true);
+ /*KeepOneInputPHIs*/ true);
}
// Replace the cloned branch with an unconditional branch to the cloned
@@ -1436,8 +1463,8 @@ deleteDeadClonedBlocks(Loop &L, ArrayRef<BasicBlock *> ExitBlocks,
// Remove all MemorySSA in the dead blocks
if (MSSAU) {
- SmallPtrSet<BasicBlock *, 16> DeadBlockSet(DeadBlocks.begin(),
- DeadBlocks.end());
+ SmallSetVector<BasicBlock *, 8> DeadBlockSet(DeadBlocks.begin(),
+ DeadBlocks.end());
MSSAU->removeBlocks(DeadBlockSet);
}
@@ -1455,7 +1482,7 @@ static void deleteDeadBlocksFromLoop(Loop &L,
MemorySSAUpdater *MSSAU) {
// Find all the dead blocks tied to this loop, and remove them from their
// successors.
- SmallPtrSet<BasicBlock *, 16> DeadBlockSet;
+ SmallSetVector<BasicBlock *, 8> DeadBlockSet;
// Start with loop/exit blocks and get a transitive closure of reachable dead
// blocks.
@@ -1712,10 +1739,9 @@ static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef<BasicBlock *> ExitBlocks,
// Sort the exits in ascending loop depth, we'll work backwards across these
// to process them inside out.
- std::stable_sort(ExitsInLoops.begin(), ExitsInLoops.end(),
- [&](BasicBlock *LHS, BasicBlock *RHS) {
- return LI.getLoopDepth(LHS) < LI.getLoopDepth(RHS);
- });
+ llvm::stable_sort(ExitsInLoops, [&](BasicBlock *LHS, BasicBlock *RHS) {
+ return LI.getLoopDepth(LHS) < LI.getLoopDepth(RHS);
+ });
// We'll build up a set for each exit loop.
SmallPtrSet<BasicBlock *, 16> NewExitLoopBlocks;
@@ -2075,7 +2101,7 @@ static void unswitchNontrivialInvariants(
"Only one possible unswitched block for a branch!");
BasicBlock *UnswitchedSuccBB = *UnswitchedSuccBBs.begin();
UnswitchedSuccBB->removePredecessor(ParentBB,
- /*DontDeleteUselessPHIs*/ true);
+ /*KeepOneInputPHIs*/ true);
DTUpdates.push_back({DominatorTree::Delete, ParentBB, UnswitchedSuccBB});
} else {
// Note that we actually want to remove the parent block as a predecessor
@@ -2090,7 +2116,7 @@ static void unswitchNontrivialInvariants(
for (auto &Case : NewSI->cases())
Case.getCaseSuccessor()->removePredecessor(
ParentBB,
- /*DontDeleteUselessPHIs*/ true);
+ /*KeepOneInputPHIs*/ true);
// We need to use the set to populate domtree updates as even when there
// are multiple cases pointing at the same successor we only want to
@@ -2236,7 +2262,7 @@ static void unswitchNontrivialInvariants(
// introduced new, non-dedicated exits. At least try to re-form dedicated
// exits for these loops. This may fail if they couldn't have dedicated
// exits to start with.
- formDedicatedExitBlocks(&UpdateL, &DT, &LI, /*PreserveLCSSA*/ true);
+ formDedicatedExitBlocks(&UpdateL, &DT, &LI, MSSAU, /*PreserveLCSSA*/ true);
};
// For non-child cloned loops and hoisted loops, we just need to update LCSSA
@@ -2526,7 +2552,7 @@ unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI,
// We can only consider fully loop-invariant switch conditions as we need
// to completely eliminate the switch after unswitching.
if (!isa<Constant>(SI->getCondition()) &&
- L.isLoopInvariant(SI->getCondition()))
+ L.isLoopInvariant(SI->getCondition()) && !BB->getUniqueSuccessor())
UnswitchCandidates.push_back({SI, {SI->getCondition()}});
continue;
}
@@ -2852,7 +2878,11 @@ PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
// Historically this pass has had issues with the dominator tree so verify it
// in asserts builds.
assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
- return getLoopPassPreservedAnalyses();
+
+ auto PA = getLoopPassPreservedAnalyses();
+ if (EnableMSSALoopDependency)
+ PA.preserve<MemorySSAAnalysis>();
+ return PA;
}
namespace {
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-08 05:45:09 +0000