[LCSSA] Implement linear algorithm for the isRecursivelyLCSSAForm
For each block check that it doesn't have any uses outside of it's innermost loop.
Differential Revision: https://reviews.llvm.org/D25364
llvm-svn: 283877
diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp
index a5f816d..d37443c 100644
--- a/llvm/lib/Analysis/LoopInfo.cpp
+++ b/llvm/lib/Analysis/LoopInfo.cpp
@@ -143,42 +143,48 @@
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);
+ 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 &&
- !contains(UserBB) &&
- DT.isReachableFromEntry(UserBB))
- return false;
- }
+ // 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;
+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);
+ });
+}
- return all_of(*this,
- [&](const Loop *L) { return L->isRecursivelyLCSSAForm(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 {