/// of loops that have already been forgotten to prevent redundant, expensive
/// calls to ScalarEvolution::forgetLoop. Returns the new combined block.
static BasicBlock *
-FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI, LPPassManager *LPM,
+FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI, ScalarEvolution *SE,
SmallPtrSetImpl<Loop *> &ForgottenLoops) {
// Merge basic blocks into their predecessor if there is only one distinct
// pred, and if there is only one distinct successor of the predecessor, and
// Erase basic block from the function...
// ScalarEvolution holds references to loop exit blocks.
- if (LPM) {
- if (auto *SEWP =
- LPM->getAnalysisIfAvailable<ScalarEvolutionWrapperPass>()) {
- if (Loop *L = LI->getLoopFor(BB)) {
- if (ForgottenLoops.insert(L).second)
- SEWP->getSE().forgetLoop(L);
- }
+ if (SE) {
+ if (Loop *L = LI->getLoopFor(BB)) {
+ if (ForgottenLoops.insert(L).second)
+ SE->forgetLoop(L);
}
}
LI->removeBlock(BB);
///
/// The LoopInfo Analysis that is passed will be kept consistent.
///
-/// If a LoopPassManager is passed in, and the loop is fully removed, it will be
-/// removed from the LoopPassManager as well. LPM can also be NULL.
-///
-/// This utility preserves LoopInfo. If DominatorTree or ScalarEvolution are
-/// available from the Pass it must also preserve those analyses.
+/// This utility preserves LoopInfo. It will also preserve ScalarEvolution and
+/// DominatorTree if they are non-null.
bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
bool AllowRuntime, bool AllowExpensiveTripCount,
- unsigned TripMultiple, LoopInfo *LI, Pass *PP,
- LPPassManager *LPM, AssumptionCache *AC) {
+ unsigned TripMultiple, LoopInfo *LI, ScalarEvolution *SE,
+ DominatorTree *DT, AssumptionCache *AC,
+ bool PreserveLCSSA) {
BasicBlock *Preheader = L->getLoopPreheader();
if (!Preheader) {
DEBUG(dbgs() << " Can't unroll; loop preheader-insertion failed.\n");
// Are we eliminating the loop control altogether?
bool CompletelyUnroll = Count == TripCount;
+ SmallVector<BasicBlock *, 4> ExitBlocks;
+ L->getExitBlocks(ExitBlocks);
+ Loop *ParentL = L->getParentLoop();
+ bool AllExitsAreInsideParentLoop = !ParentL ||
+ std::all_of(ExitBlocks.begin(), ExitBlocks.end(),
+ [&](BasicBlock *BB) { return ParentL->contains(BB); });
// We assume a run-time trip count if the compiler cannot
// figure out the loop trip count and the unroll-runtime
bool RuntimeTripCount = (TripCount == 0 && Count > 0 && AllowRuntime);
if (RuntimeTripCount &&
- !UnrollRuntimeLoopProlog(L, Count, AllowExpensiveTripCount, LI, LPM))
+ !UnrollRuntimeLoopProlog(L, Count, AllowExpensiveTripCount, LI, SE, DT,
+ PreserveLCSSA))
return false;
// Notify ScalarEvolution that the loop will be substantially changed,
// if not outright eliminated.
- auto *SEWP =
- PP ? PP->getAnalysisIfAvailable<ScalarEvolutionWrapperPass>() : nullptr;
- ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
if (SE)
SE->forgetLoop(L);
for (unsigned i = 0; i < NewBlocks.size(); ++i)
for (BasicBlock::iterator I = NewBlocks[i]->begin(),
E = NewBlocks[i]->end(); I != E; ++I)
- ::RemapInstruction(I, LastValueMap);
+ ::RemapInstruction(&*I, LastValueMap);
}
// Loop over the PHI nodes in the original block, setting incoming values.
BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
if (Term->isUnconditional()) {
BasicBlock *Dest = Term->getSuccessor(0);
- if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, LPM,
+ if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, SE,
ForgottenLoops))
std::replace(Latches.begin(), Latches.end(), Dest, Fold);
}
// whole function's cache.
AC->clear();
- DominatorTree *DT = nullptr;
- if (PP) {
- // FIXME: Reconstruct dom info, because it is not preserved properly.
- // Incrementally updating domtree after loop unrolling would be easy.
- if (DominatorTreeWrapperPass *DTWP =
- PP->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
- DT = &DTWP->getDomTree();
- DT->recalculate(*L->getHeader()->getParent());
- }
-
- // Simplify any new induction variables in the partially unrolled loop.
- if (SE && !CompletelyUnroll) {
- SmallVector<WeakVH, 16> DeadInsts;
- simplifyLoopIVs(L, SE, LPM, DeadInsts);
-
- // Aggressively clean up dead instructions that simplifyLoopIVs already
- // identified. Any remaining should be cleaned up below.
- while (!DeadInsts.empty())
- if (Instruction *Inst =
- dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
- RecursivelyDeleteTriviallyDeadInstructions(Inst);
- }
+ // FIXME: Reconstruct dom info, because it is not preserved properly.
+ // Incrementally updating domtree after loop unrolling would be easy.
+ if (DT)
+ DT->recalculate(*L->getHeader()->getParent());
+
+ // Simplify any new induction variables in the partially unrolled loop.
+ if (SE && !CompletelyUnroll) {
+ SmallVector<WeakVH, 16> DeadInsts;
+ simplifyLoopIVs(L, SE, DT, LI, DeadInsts);
+
+ // Aggressively clean up dead instructions that simplifyLoopIVs already
+ // identified. Any remaining should be cleaned up below.
+ while (!DeadInsts.empty())
+ if (Instruction *Inst =
+ dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
+ RecursivelyDeleteTriviallyDeadInstructions(Inst);
}
+
// At this point, the code is well formed. We now do a quick sweep over the
// inserted code, doing constant propagation and dead code elimination as we
// go.
for (std::vector<BasicBlock*>::const_iterator BB = NewLoopBlocks.begin(),
BBE = NewLoopBlocks.end(); BB != BBE; ++BB)
for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) {
- Instruction *Inst = I++;
+ Instruction *Inst = &*I++;
if (isInstructionTriviallyDead(Inst))
(*BB)->getInstList().erase(Inst);
++NumUnrolled;
Loop *OuterL = L->getParentLoop();
- // Remove the loop from the LoopPassManager if it's completely removed.
- if (CompletelyUnroll && LPM != nullptr)
- LPM->deleteLoopFromQueue(L);
+ // Update LoopInfo if the loop is completely removed.
+ if (CompletelyUnroll)
+ LI->updateUnloop(L);;
// If we have a pass and a DominatorTree we should re-simplify impacted loops
// to ensure subsequent analyses can rely on this form. We want to simplify
// at least one layer outside of the loop that was unrolled so that any
// changes to the parent loop exposed by the unrolling are considered.
- if (PP && DT) {
+ if (DT) {
if (!OuterL && !CompletelyUnroll)
OuterL = L;
if (OuterL) {
- simplifyLoop(OuterL, DT, LI, PP, SE, AC);
+ bool Simplified = simplifyLoop(OuterL, DT, LI, SE, AC, PreserveLCSSA);
// LCSSA must be performed on the outermost affected loop. The unrolled
// loop's last loop latch is guaranteed to be in the outermost loop after
- // deleteLoopFromQueue updates LoopInfo.
+ // LoopInfo's been updated by updateUnloop.
Loop *LatchLoop = LI->getLoopFor(Latches.back());
if (!OuterL->contains(LatchLoop))
while (OuterL->getParentLoop() != LatchLoop)
OuterL = OuterL->getParentLoop();
- formLCSSARecursively(*OuterL, *DT, LI, SE);
+ if (CompletelyUnroll && (!AllExitsAreInsideParentLoop || Simplified))
+ formLCSSARecursively(*OuterL, *DT, LI, SE);
+ else
+ assert(OuterL->isLCSSAForm(*DT) &&
+ "Loops should be in LCSSA form after loop-unroll.");
}
}
projects / oota-llvm.git / blobdiff