summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/LoopInfo.h2
-rw-r--r--llvm/lib/Analysis/LoopInfo.cpp66
-rw-r--r--llvm/lib/Transforms/Scalar/IndVarSimplify.cpp9
-rw-r--r--llvm/lib/Transforms/Utils/LCSSA.cpp3
-rw-r--r--llvm/lib/Transforms/Utils/LoopSimplify.cpp10
5 files changed, 50 insertions, 40 deletions
diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h
index 85c06826dae..2e7f4d016bb 100644
--- a/llvm/include/llvm/Analysis/LoopInfo.h
+++ b/llvm/include/llvm/Analysis/LoopInfo.h
@@ -412,7 +412,7 @@ public:
bool isLCSSAForm(DominatorTree &DT) const;
/// Return true if this Loop and all inner subloops are in LCSSA form.
- bool isRecursivelyLCSSAForm(DominatorTree &DT) const;
+ bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const;
/// Return true if the Loop is in the form that the LoopSimplify form
/// transforms loops to, which is sometimes called normal form.
diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp
index a5f816dd5ad..d37443cbdbe 100644
--- a/llvm/lib/Analysis/LoopInfo.cpp
+++ b/llvm/lib/Analysis/LoopInfo.cpp
@@ -143,42 +143,48 @@ PHINode *Loop::getCanonicalInductionVariable() const {
return nullptr;
}
-bool Loop::isLCSSAForm(DominatorTree &DT) const {
- for (BasicBlock *BB : this->blocks()) {
- for (Instruction &I : *BB) {
- // Tokens can't be used in PHI nodes and live-out tokens prevent loop
- // optimizations, so for the purposes of considered LCSSA form, we
- // can ignore them.
- if (I.getType()->isTokenTy())
- continue;
+// Check that 'BB' doesn't have any uses outside of the 'L'
+static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
+ DominatorTree &DT) {
+ for (const Instruction &I : BB) {
+ // Tokens can't be used in PHI nodes and live-out tokens prevent loop
+ // optimizations, so for the purposes of considered LCSSA form, we
+ // can ignore them.
+ if (I.getType()->isTokenTy())
+ continue;
- for (Use &U : I.uses()) {
- Instruction *UI = cast<Instruction>(U.getUser());
- BasicBlock *UserBB = UI->getParent();
- if (PHINode *P = dyn_cast<PHINode>(UI))
- UserBB = P->getIncomingBlock(U);
-
- // Check the current block, as a fast-path, before checking whether
- // the use is anywhere in the loop. Most values are used in the same
- // block they are defined in. Also, blocks not reachable from the
- // entry are special; uses in them don't need to go through PHIs.
- if (UserBB != BB &&
- !contains(UserBB) &&
- DT.isReachableFromEntry(UserBB))
- return false;
- }
+ for (const Use &U : I.uses()) {
+ const Instruction *UI = cast<Instruction>(U.getUser());
+ const BasicBlock *UserBB = UI->getParent();
+ if (const PHINode *P = dyn_cast<PHINode>(UI))
+ UserBB = P->getIncomingBlock(U);
+
+ // Check the current block, as a fast-path, before checking whether
+ // the use is anywhere in the loop. Most values are used in the same
+ // block they are defined in. Also, blocks not reachable from the
+ // entry are special; uses in them don't need to go through PHIs.
+ if (UserBB != &BB && !L.contains(UserBB) &&
+ DT.isReachableFromEntry(UserBB))
+ return false;
}
}
-
return true;
}
-bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const {
- if (!isLCSSAForm(DT))
- return false;
-
- return all_of(*this,
- [&](const Loop *L) { return L->isRecursivelyLCSSAForm(DT); });
+bool Loop::isLCSSAForm(DominatorTree &DT) const {
+ // For each block we check that it doesn't have any uses outside of this loop.
+ return all_of(this->blocks(), [&](const BasicBlock *BB) {
+ return isBlockInLCSSAForm(*this, *BB, DT);
+ });
+}
+
+bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const {
+ // For each block we check that it doesn't have any uses outside of it's
+ // innermost loop. This process will transitivelly guarntee that current loop
+ // and all of the nested loops are in the LCSSA form.
+ return all_of(this->blocks(), [&](const BasicBlock *BB) {
+ return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
+ });
}
bool Loop::isLoopSimplifyForm() const {
diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
index daeb8e3e588..d6756e6a254 100644
--- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -505,7 +505,8 @@ Value *IndVarSimplify::expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
/// constant operands at the beginning of the loop.
void IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
// Check a pre-condition.
- assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
+ assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
+ "Indvars did not preserve LCSSA!");
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
@@ -2184,7 +2185,8 @@ void IndVarSimplify::sinkUnusedInvariants(Loop *L) {
bool IndVarSimplify::run(Loop *L) {
// We need (and expect!) the incoming loop to be in LCSSA.
- assert(L->isRecursivelyLCSSAForm(*DT) && "LCSSA required to run indvars!");
+ assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
+ "LCSSA required to run indvars!");
// If LoopSimplify form is not available, stay out of trouble. Some notes:
// - LSR currently only supports LoopSimplify-form loops. Indvars'
@@ -2277,7 +2279,8 @@ bool IndVarSimplify::run(Loop *L) {
Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
// Check a post-condition.
- assert(L->isRecursivelyLCSSAForm(*DT) && "Indvars did not preserve LCSSA!");
+ assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
+ "Indvars did not preserve LCSSA!");
// Verify that LFTR, and any other change have not interfered with SCEV's
// ability to compute trip count.
diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp
index ac403cc72c6..5d818cc734b 100644
--- a/llvm/lib/Transforms/Utils/LCSSA.cpp
+++ b/llvm/lib/Transforms/Utils/LCSSA.cpp
@@ -323,7 +323,8 @@ struct LCSSAWrapperPass : public FunctionPass {
bool runOnFunction(Function &F) override;
void verifyAnalysis() const override {
assert(
- all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); }) &&
+ all_of(*LI,
+ [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); }) &&
"LCSSA form is broken!");
};
diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp
index 36e2fea63dc..89933e0f574 100644
--- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp
@@ -366,7 +366,7 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
// already be a use of an LCSSA phi node.
formLCSSA(*L, *DT, LI, SE);
- assert(NewOuter->isRecursivelyLCSSAForm(*DT) &&
+ assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
"LCSSA is broken after separating nested loops!");
}
@@ -810,8 +810,8 @@ bool LoopSimplify::runOnFunction(Function &F) {
if (PreserveLCSSA) {
assert(DT && "DT not available.");
assert(LI && "LI not available.");
- bool InLCSSA =
- all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+ bool InLCSSA = all_of(
+ *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
assert(InLCSSA && "Requested to preserve LCSSA, but it's already broken.");
}
#endif
@@ -822,8 +822,8 @@ bool LoopSimplify::runOnFunction(Function &F) {
#ifndef NDEBUG
if (PreserveLCSSA) {
- bool InLCSSA =
- all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+ bool InLCSSA = all_of(
+ *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
assert(InLCSSA && "LCSSA is broken after loop-simplify.");
}
#endif
OpenPOWER on IntegriCloud