summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopUnswitch.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/LoopUnswitch.cpp')
-rw-r--r--lib/Transforms/Scalar/LoopUnswitch.cpp103
1 files changed, 76 insertions, 27 deletions
diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp
index 6aad077ff19e..4a089dfa7dbf 100644
--- a/lib/Transforms/Scalar/LoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -28,18 +28,19 @@
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
-#include "llvm/Analysis/DivergenceAnalysis.h"
#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LegacyDivergenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
@@ -65,8 +66,10 @@
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
@@ -180,11 +183,13 @@ namespace {
Loop *currentLoop = nullptr;
DominatorTree *DT = nullptr;
+ MemorySSA *MSSA = nullptr;
+ std::unique_ptr<MemorySSAUpdater> MSSAU;
BasicBlock *loopHeader = nullptr;
BasicBlock *loopPreheader = nullptr;
bool SanitizeMemory;
- LoopSafetyInfo SafetyInfo;
+ SimpleLoopSafetyInfo SafetyInfo;
// LoopBlocks contains all of the basic blocks of the loop, including the
// preheader of the loop, the body of the loop, and the exit blocks of the
@@ -214,8 +219,12 @@ namespace {
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<AssumptionCacheTracker>();
AU.addRequired<TargetTransformInfoWrapperPass>();
+ if (EnableMSSALoopDependency) {
+ AU.addRequired<MemorySSAWrapperPass>();
+ AU.addPreserved<MemorySSAWrapperPass>();
+ }
if (hasBranchDivergence)
- AU.addRequired<DivergenceAnalysis>();
+ AU.addRequired<LegacyDivergenceAnalysis>();
getLoopAnalysisUsage(AU);
}
@@ -237,11 +246,11 @@ namespace {
bool TryTrivialLoopUnswitch(bool &Changed);
bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,
- TerminatorInst *TI = nullptr);
+ Instruction *TI = nullptr);
void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
- BasicBlock *ExitBlock, TerminatorInst *TI);
+ BasicBlock *ExitBlock, Instruction *TI);
void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L,
- TerminatorInst *TI);
+ Instruction *TI);
void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
Constant *Val, bool isEqual);
@@ -249,8 +258,7 @@ namespace {
void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
BasicBlock *TrueDest,
BasicBlock *FalseDest,
- BranchInst *OldBranch,
- TerminatorInst *TI);
+ BranchInst *OldBranch, Instruction *TI);
void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L);
@@ -383,7 +391,8 @@ INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(LoopPass)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(DivergenceAnalysis)
+INITIALIZE_PASS_DEPENDENCY(LegacyDivergenceAnalysis)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
false, false)
@@ -515,20 +524,33 @@ bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
LPM = &LPM_Ref;
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ if (EnableMSSALoopDependency) {
+ MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
+ MSSAU = make_unique<MemorySSAUpdater>(MSSA);
+ assert(DT && "Cannot update MemorySSA without a valid DomTree.");
+ }
currentLoop = L;
Function *F = currentLoop->getHeader()->getParent();
SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
if (SanitizeMemory)
- computeLoopSafetyInfo(&SafetyInfo, L);
+ SafetyInfo.computeLoopSafetyInfo(L);
+
+ if (MSSA && VerifyMemorySSA)
+ MSSA->verifyMemorySSA();
bool Changed = false;
do {
assert(currentLoop->isLCSSAForm(*DT));
+ if (MSSA && VerifyMemorySSA)
+ MSSA->verifyMemorySSA();
redoLoop = false;
Changed |= processCurrentLoop();
} while(redoLoop);
+ if (MSSA && VerifyMemorySSA)
+ MSSA->verifyMemorySSA();
+
return Changed;
}
@@ -690,7 +712,7 @@ bool LoopUnswitch::processCurrentLoop() {
// loop.
for (Loop::block_iterator I = currentLoop->block_begin(),
E = currentLoop->block_end(); I != E; ++I) {
- TerminatorInst *TI = (*I)->getTerminator();
+ Instruction *TI = (*I)->getTerminator();
// Unswitching on a potentially uninitialized predicate is not
// MSan-friendly. Limit this to the cases when the original predicate is
@@ -699,7 +721,7 @@ bool LoopUnswitch::processCurrentLoop() {
// This is a workaround for the discrepancy between LLVM IR and MSan
// semantics. See PR28054 for more details.
if (SanitizeMemory &&
- !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo))
+ !SafetyInfo.isGuaranteedToExecute(*TI, DT, currentLoop))
continue;
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
@@ -853,7 +875,7 @@ static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) {
/// simplify the loop. If we decide that this is profitable,
/// unswitch the loop, reprocess the pieces, then return true.
bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,
- TerminatorInst *TI) {
+ Instruction *TI) {
// Check to see if it would be profitable to unswitch current loop.
if (!BranchesInfo.CostAllowsUnswitching()) {
LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
@@ -864,7 +886,7 @@ bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,
return false;
}
if (hasBranchDivergence &&
- getAnalysis<DivergenceAnalysis>().isDivergent(LoopCond)) {
+ getAnalysis<LegacyDivergenceAnalysis>().isDivergent(LoopCond)) {
LLVM_DEBUG(dbgs() << "NOT unswitching loop %"
<< currentLoop->getHeader()->getName()
<< " at non-trivial condition '" << *Val
@@ -908,7 +930,7 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
BasicBlock *TrueDest,
BasicBlock *FalseDest,
BranchInst *OldBranch,
- TerminatorInst *TI) {
+ Instruction *TI) {
assert(OldBranch->isUnconditional() && "Preheader is not split correctly");
assert(TrueDest != FalseDest && "Branch targets should be different");
// Insert a conditional branch on LIC to the two preheaders. The original
@@ -952,13 +974,16 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
}
-
DT->applyUpdates(Updates);
+
+ if (MSSAU)
+ MSSAU->applyUpdates(Updates, *DT);
}
// If either edge is critical, split it. This helps preserve LoopSimplify
// form for enclosing loops.
- auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA();
+ auto Options =
+ CriticalEdgeSplittingOptions(DT, LI, MSSAU.get()).setPreserveLCSSA();
SplitCriticalEdge(BI, 0, Options);
SplitCriticalEdge(BI, 1, Options);
}
@@ -970,7 +995,7 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
/// outside of the loop and updating loop info.
void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
BasicBlock *ExitBlock,
- TerminatorInst *TI) {
+ Instruction *TI) {
LLVM_DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"
<< loopHeader->getName() << " [" << L->getBlocks().size()
<< " blocks] in Function "
@@ -984,7 +1009,7 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
// First step, split the preheader, so that we know that there is a safe place
// to insert the conditional branch. We will change loopPreheader to have a
// conditional branch on Cond.
- BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI);
+ BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get());
// Now that we have a place to insert the conditional branch, create a place
// to branch to: this is the exit block out of the loop that we should
@@ -995,7 +1020,8 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
// without actually branching to it (the exit block should be dominated by the
// loop header, not the preheader).
assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
- BasicBlock *NewExit = SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI);
+ BasicBlock *NewExit =
+ SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI, MSSAU.get());
// Okay, now we have a position to branch from and a position to branch to,
// insert the new conditional branch.
@@ -1015,6 +1041,7 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
// particular value, rewrite the loop with this info. We know that this will
// at least eliminate the old branch.
RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
+
++NumTrivial;
}
@@ -1026,7 +1053,7 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
/// condition.
bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) {
BasicBlock *CurrentBB = currentLoop->getHeader();
- TerminatorInst *CurrentTerm = CurrentBB->getTerminator();
+ Instruction *CurrentTerm = CurrentBB->getTerminator();
LLVMContext &Context = CurrentBB->getContext();
// If loop header has only one reachable successor (currently via an
@@ -1190,7 +1217,7 @@ void LoopUnswitch::SplitExitEdges(Loop *L,
// Although SplitBlockPredecessors doesn't preserve loop-simplify in
// general, if we call it on all predecessors of all exits then it does.
- SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI,
+ SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, MSSAU.get(),
/*PreserveLCSSA*/ true);
}
}
@@ -1199,7 +1226,7 @@ void LoopUnswitch::SplitExitEdges(Loop *L,
/// Split it into loop versions and test the condition outside of either loop.
/// Return the loops created as Out1/Out2.
void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
- Loop *L, TerminatorInst *TI) {
+ Loop *L, Instruction *TI) {
Function *F = loopHeader->getParent();
LLVM_DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"
<< loopHeader->getName() << " [" << L->getBlocks().size()
@@ -1216,7 +1243,8 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
// First step, split the preheader and exit blocks, and add these blocks to
// the LoopBlocks list.
- BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI);
+ BasicBlock *NewPreheader =
+ SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get());
LoopBlocks.push_back(NewPreheader);
// We want the loop to come after the preheader, but before the exit blocks.
@@ -1318,10 +1346,24 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
"Preheader splitting did not work correctly!");
+ if (MSSAU) {
+ // Update MemorySSA after cloning, and before splitting to unreachables,
+ // since that invalidates the 1:1 mapping of clones in VMap.
+ LoopBlocksRPO LBRPO(L);
+ LBRPO.perform(LI);
+ MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, VMap);
+ }
+
// Emit the new branch that selects between the two versions of this loop.
EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
TI);
LPM->deleteSimpleAnalysisValue(OldBR, L);
+ if (MSSAU) {
+ // Update MemoryPhis in Exit blocks.
+ MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT);
+ if (VerifyMemorySSA)
+ MSSA->verifyMemorySSA();
+ }
// The OldBr was replaced by a new one and removed (but not erased) by
// EmitPreheaderBranchOnCondition. It is no longer needed, so delete it.
@@ -1347,6 +1389,9 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
LICHandle && !isa<Constant>(LICHandle))
RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
+
+ if (MSSA && VerifyMemorySSA)
+ MSSA->verifyMemorySSA();
}
/// Remove all instances of I from the worklist vector specified.
@@ -1485,7 +1530,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC,
// and hooked up so as to preserve the loop structure, because
// trying to update it is complicated. So instead we preserve the
// loop structure and put the block on a dead code path.
- SplitEdge(Switch, SISucc, DT, LI);
+ SplitEdge(Switch, SISucc, DT, LI, MSSAU.get());
// Compute the successors instead of relying on the return value
// of SplitEdge, since it may have split the switch successor
// after PHI nodes.
@@ -1539,6 +1584,8 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
Worklist.push_back(Use);
LPM->deleteSimpleAnalysisValue(I, L);
RemoveFromWorklist(I, Worklist);
+ if (MSSAU)
+ MSSAU->removeMemoryAccess(I);
I->eraseFromParent();
++NumSimplify;
continue;
@@ -1578,6 +1625,8 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
// Move all of the successor contents from Succ to Pred.
Pred->getInstList().splice(BI->getIterator(), Succ->getInstList(),
Succ->begin(), Succ->end());
+ if (MSSAU)
+ MSSAU->moveAllAfterMergeBlocks(Succ, Pred, BI);
LPM->deleteSimpleAnalysisValue(BI, L);
RemoveFromWorklist(BI, Worklist);
BI->eraseFromParent();
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 12:15:06 +0000