/// uses.
static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
const SmallVectorImpl<BasicBlock *> &ExitBlocks,
- PredIteratorCache &PredCache) {
+ PredIteratorCache &PredCache, LoopInfo *LI) {
SmallVector<Use *, 16> UsesToRewrite;
BasicBlock *InstBB = Inst.getParent();
DomTreeNode *DomNode = DT.getNode(DomBB);
SmallVector<PHINode *, 16> AddedPHIs;
+ SmallVector<PHINode *, 8> PostProcessPHIs;
SSAUpdater SSAUpdate;
SSAUpdate.Initialize(Inst.getType(), Inst.getName());
// Remember that this phi makes the value alive in this block.
SSAUpdate.AddAvailableValue(ExitBB, PN);
+
+ // LoopSimplify might fail to simplify some loops (e.g. when indirect
+ // branches are involved). In such situations, it might happen that an exit
+ // for Loop L1 is the header of a disjoint Loop L2. Thus, when we create
+ // PHIs in such an exit block, we are also inserting PHIs into L2's header.
+ // This could break LCSSA form for L2 because these inserted PHIs can also
+ // have uses outside of L2. Remember all PHIs in such situation as to
+ // revisit than later on. FIXME: Remove this if indirectbr support into
+ // LoopSimplify gets improved.
+ if (auto *OtherLoop = LI->getLoopFor(ExitBB))
+ if (!L.contains(OtherLoop))
+ PostProcessPHIs.push_back(PN);
}
// Rewrite all uses outside the loop in terms of the new PHIs we just
SSAUpdate.RewriteUse(*UsesToRewrite[i]);
}
+ // Post process PHI instructions that were inserted into another disjoint loop
+ // and update their exits properly.
+ for (auto *I : PostProcessPHIs) {
+ if (I->use_empty())
+ continue;
+
+ BasicBlock *PHIBB = I->getParent();
+ Loop *OtherLoop = LI->getLoopFor(PHIBB);
+ SmallVector<BasicBlock *, 8> EBs;
+ OtherLoop->getExitBlocks(EBs);
+ if (EBs.empty())
+ continue;
+
+ // Recurse and re-process each PHI instruction. FIXME: we should really
+ // convert this entire thing to a worklist approach where we process a
+ // vector of instructions...
+ processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI);
+ }
+
// Remove PHI nodes that did not have any uses rewritten.
for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) {
if (AddedPHIs[i]->use_empty())
return false;
}
-bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
+bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
+ ScalarEvolution *SE) {
bool Changed = false;
// Get the set of exiting blocks.
!isa<PHINode>(I->user_back())))
continue;
- Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache);
+ Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache, LI);
}
}
}
/// Process a loop nest depth first.
-bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT,
+bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
ScalarEvolution *SE) {
bool Changed = false;
// Recurse depth-first through inner loops.
- for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
- Changed |= formLCSSARecursively(**LI, DT, SE);
+ for (Loop::iterator I = L.begin(), E = L.end(); I != E; ++I)
+ Changed |= formLCSSARecursively(**I, DT, LI, SE);
- Changed |= formLCSSA(L, DT, SE);
+ Changed |= formLCSSA(L, DT, LI, SE);
return Changed;
}
AU.setPreservesCFG();
AU.addRequired<DominatorTreeWrapperPass>();
- AU.addRequired<LoopInfo>();
+ AU.addRequired<LoopInfoWrapperPass>();
AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<ScalarEvolution>();
char LCSSA::ID = 0;
INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(LoopInfo)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false)
Pass *llvm::createLCSSAPass() { return new LCSSA(); }
/// Process all loops in the function, inner-most out.
bool LCSSA::runOnFunction(Function &F) {
bool Changed = false;
- LI = &getAnalysis<LoopInfo>();
+ LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
SE = getAnalysisIfAvailable<ScalarEvolution>();
// Simplify each loop nest in the function.
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
- Changed |= formLCSSARecursively(**I, *DT, SE);
+ Changed |= formLCSSARecursively(**I, *DT, LI, SE);
return Changed;
}