summaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils/LoopSimplify.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils/LoopSimplify.cpp')
-rw-r--r--lib/Transforms/Utils/LoopSimplify.cpp88
1 files changed, 60 insertions, 28 deletions
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 1fa469595d168..b3a928bf77531 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -37,6 +37,7 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/Transforms/Utils/LoopSimplify.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SetOperations.h"
@@ -489,14 +490,9 @@ ReprocessLoop:
DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
<< P->getName() << "\n");
- // Inform each successor of each dead pred.
- for (succ_iterator SI = succ_begin(P), SE = succ_end(P); SI != SE; ++SI)
- (*SI)->removePredecessor(P);
// Zap the dead pred's terminator and replace it with unreachable.
TerminatorInst *TI = P->getTerminator();
- TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
- P->getTerminator()->eraseFromParent();
- new UnreachableInst(P->getContext(), P);
+ changeToUnreachable(TI, /*UseLLVMTrap=*/false);
Changed = true;
}
}
@@ -506,14 +502,13 @@ ReprocessLoop:
// trip count computations.
SmallVector<BasicBlock*, 8> ExitingBlocks;
L->getExitingBlocks(ExitingBlocks);
- for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
- E = ExitingBlocks.end(); I != E; ++I)
- if (BranchInst *BI = dyn_cast<BranchInst>((*I)->getTerminator()))
+ for (BasicBlock *ExitingBlock : ExitingBlocks)
+ if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
if (BI->isConditional()) {
if (UndefValue *Cond = dyn_cast<UndefValue>(BI->getCondition())) {
DEBUG(dbgs() << "LoopSimplify: Resolving \"br i1 undef\" to exit in "
- << (*I)->getName() << "\n");
+ << ExitingBlock->getName() << "\n");
BI->setCondition(ConstantInt::get(Cond->getType(),
!L->contains(BI->getSuccessor(0))));
@@ -545,9 +540,7 @@ ReprocessLoop:
SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
ExitBlocks.end());
- for (SmallSetVector<BasicBlock *, 8>::iterator I = ExitBlockSet.begin(),
- E = ExitBlockSet.end(); I != E; ++I) {
- BasicBlock *ExitBlock = *I;
+ for (BasicBlock *ExitBlock : ExitBlockSet) {
for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
PI != PE; ++PI)
// Must be exactly this loop: no subloops, parent loops, or non-loop preds
@@ -691,8 +684,10 @@ ReprocessLoop:
}
DT->eraseNode(ExitingBlock);
- BI->getSuccessor(0)->removePredecessor(ExitingBlock);
- BI->getSuccessor(1)->removePredecessor(ExitingBlock);
+ BI->getSuccessor(0)->removePredecessor(
+ ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA);
+ BI->getSuccessor(1)->removePredecessor(
+ ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA);
ExitingBlock->eraseFromParent();
}
}
@@ -731,11 +726,6 @@ namespace {
initializeLoopSimplifyPass(*PassRegistry::getPassRegistry());
}
- DominatorTree *DT;
- LoopInfo *LI;
- ScalarEvolution *SE;
- AssumptionCache *AC;
-
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
@@ -753,7 +743,8 @@ namespace {
AU.addPreserved<GlobalsAAWrapperPass>();
AU.addPreserved<ScalarEvolutionWrapperPass>();
AU.addPreserved<SCEVAAWrapperPass>();
- AU.addPreserved<DependenceAnalysis>();
+ AU.addPreservedID(LCSSAID);
+ AU.addPreserved<DependenceAnalysisWrapperPass>();
AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added.
}
@@ -768,9 +759,6 @@ INITIALIZE_PASS_BEGIN(LoopSimplify, "loop-simplify",
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
INITIALIZE_PASS_END(LoopSimplify, "loop-simplify",
"Canonicalize natural loops", false, false)
@@ -783,20 +771,64 @@ Pass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
///
bool LoopSimplify::runOnFunction(Function &F) {
bool Changed = false;
- LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
- DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+ DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
- SE = SEWP ? &SEWP->getSE() : nullptr;
- AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+ ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
+ AssumptionCache *AC =
+ &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+
bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+#ifndef NDEBUG
+ if (PreserveLCSSA) {
+ assert(DT && "DT not available.");
+ assert(LI && "LI not available.");
+ bool InLCSSA =
+ all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+ assert(InLCSSA && "Requested to preserve LCSSA, but it's already broken.");
+ }
+#endif
// Simplify each loop nest in the function.
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
Changed |= simplifyLoop(*I, DT, LI, SE, AC, PreserveLCSSA);
+#ifndef NDEBUG
+ if (PreserveLCSSA) {
+ bool InLCSSA =
+ all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+ assert(InLCSSA && "LCSSA is broken after loop-simplify.");
+ }
+#endif
return Changed;
}
+PreservedAnalyses LoopSimplifyPass::run(Function &F,
+ AnalysisManager<Function> &AM) {
+ bool Changed = false;
+ LoopInfo *LI = &AM.getResult<LoopAnalysis>(F);
+ DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
+ ScalarEvolution *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
+ AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
+
+ // FIXME: This pass should verify that the loops on which it's operating
+ // are in canonical SSA form, and that the pass itself preserves this form.
+ for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
+ Changed |= simplifyLoop(*I, DT, LI, SE, AC, true /* PreserveLCSSA */);
+
+ if (!Changed)
+ return PreservedAnalyses::all();
+ PreservedAnalyses PA;
+ PA.preserve<DominatorTreeAnalysis>();
+ PA.preserve<LoopAnalysis>();
+ PA.preserve<BasicAA>();
+ PA.preserve<GlobalsAA>();
+ PA.preserve<SCEVAA>();
+ PA.preserve<ScalarEvolutionAnalysis>();
+ PA.preserve<DependenceAnalysis>();
+ return PA;
+}
+
// FIXME: Restore this code when we re-enable verification in verifyAnalysis
// below.
#if 0