summaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils/LoopUnrollAndJam.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils/LoopUnrollAndJam.cpp')
-rw-r--r--lib/Transforms/Utils/LoopUnrollAndJam.cpp92
1 files changed, 63 insertions, 29 deletions
diff --git a/lib/Transforms/Utils/LoopUnrollAndJam.cpp b/lib/Transforms/Utils/LoopUnrollAndJam.cpp
index b919f73c3817f..e26762639c13f 100644
--- a/lib/Transforms/Utils/LoopUnrollAndJam.cpp
+++ b/lib/Transforms/Utils/LoopUnrollAndJam.cpp
@@ -72,7 +72,7 @@ static bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop,
for (BasicBlock *BB : ForeBlocks) {
if (BB == SubLoopPreHeader)
continue;
- TerminatorInst *TI = BB->getTerminator();
+ Instruction *TI = BB->getTerminator();
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
if (!ForeBlocks.count(TI->getSuccessor(i)))
return false;
@@ -167,12 +167,14 @@ static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header,
isSafeToUnrollAndJam should be used prior to calling this to make sure the
unrolling will be valid. Checking profitablility is also advisable.
+
+ If EpilogueLoop is non-null, it receives the epilogue loop (if it was
+ necessary to create one and not fully unrolled).
*/
-LoopUnrollResult
-llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
- unsigned TripMultiple, bool UnrollRemainder,
- LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
- AssumptionCache *AC, OptimizationRemarkEmitter *ORE) {
+LoopUnrollResult llvm::UnrollAndJamLoop(
+ Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple,
+ bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
+ AssumptionCache *AC, OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop) {
// When we enter here we should have already checked that it is safe
BasicBlock *Header = L->getHeader();
@@ -181,7 +183,7 @@ llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
// Don't enter the unroll code if there is nothing to do.
if (TripCount == 0 && Count < 2) {
- LLVM_DEBUG(dbgs() << "Won't unroll; almost nothing to do\n");
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; almost nothing to do\n");
return LoopUnrollResult::Unmodified;
}
@@ -196,7 +198,8 @@ llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
if (TripMultiple == 1 || TripMultiple % Count != 0) {
if (!UnrollRuntimeLoopRemainder(L, Count, /*AllowExpensiveTripCount*/ false,
/*UseEpilogRemainder*/ true,
- UnrollRemainder, LI, SE, DT, AC, true)) {
+ UnrollRemainder, LI, SE, DT, AC, true,
+ EpilogueLoop)) {
LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; remainder loop could not be "
"generated when assuming runtime trip count\n");
return LoopUnrollResult::Unmodified;
@@ -297,8 +300,15 @@ llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
for (BasicBlock *BB : L->getBlocks())
for (Instruction &I : *BB)
if (!isa<DbgInfoIntrinsic>(&I))
- if (const DILocation *DIL = I.getDebugLoc())
- I.setDebugLoc(DIL->cloneWithDuplicationFactor(Count));
+ if (const DILocation *DIL = I.getDebugLoc()) {
+ auto NewDIL = DIL->cloneWithDuplicationFactor(Count);
+ if (NewDIL)
+ I.setDebugLoc(NewDIL.getValue());
+ else
+ LLVM_DEBUG(dbgs()
+ << "Failed to create new discriminator: "
+ << DIL->getFilename() << " Line: " << DIL->getLine());
+ }
// Copy all blocks
for (unsigned It = 1; It != Count; ++It) {
@@ -619,16 +629,28 @@ static bool checkDependencies(SmallVector<Value *, 4> &Earlier,
if (auto D = DI.depends(Src, Dst, true)) {
assert(D->isOrdered() && "Expected an output, flow or anti dep.");
- if (D->isConfused())
+ if (D->isConfused()) {
+ LLVM_DEBUG(dbgs() << " Confused dependency between:\n"
+ << " " << *Src << "\n"
+ << " " << *Dst << "\n");
return false;
+ }
if (!InnerLoop) {
- if (D->getDirection(LoopDepth) & Dependence::DVEntry::GT)
+ if (D->getDirection(LoopDepth) & Dependence::DVEntry::GT) {
+ LLVM_DEBUG(dbgs() << " > dependency between:\n"
+ << " " << *Src << "\n"
+ << " " << *Dst << "\n");
return false;
+ }
} else {
assert(LoopDepth + 1 <= D->getLevels());
if (D->getDirection(LoopDepth) & Dependence::DVEntry::GT &&
- D->getDirection(LoopDepth + 1) & Dependence::DVEntry::LT)
+ D->getDirection(LoopDepth + 1) & Dependence::DVEntry::LT) {
+ LLVM_DEBUG(dbgs() << " < > dependency between:\n"
+ << " " << *Src << "\n"
+ << " " << *Dst << "\n");
return false;
+ }
}
}
}
@@ -716,38 +738,45 @@ bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
if (SubLoopLatch != SubLoopExit)
return false;
- if (Header->hasAddressTaken() || SubLoopHeader->hasAddressTaken())
+ if (Header->hasAddressTaken() || SubLoopHeader->hasAddressTaken()) {
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Address taken\n");
return false;
+ }
// Split blocks into Fore/SubLoop/Aft based on dominators
BasicBlockSet SubLoopBlocks;
BasicBlockSet ForeBlocks;
BasicBlockSet AftBlocks;
if (!partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks,
- AftBlocks, &DT))
+ AftBlocks, &DT)) {
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Incompatible loop layout\n");
return false;
+ }
// Aft blocks may need to move instructions to fore blocks, which becomes more
// difficult if there are multiple (potentially conditionally executed)
// blocks. For now we just exclude loops with multiple aft blocks.
- if (AftBlocks.size() != 1)
+ if (AftBlocks.size() != 1) {
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Can't currently handle "
+ "multiple blocks after the loop\n");
return false;
+ }
- // Check inner loop IV is consistent between all iterations
- const SCEV *SubLoopBECountSC = SE.getExitCount(SubLoop, SubLoopLatch);
- if (isa<SCEVCouldNotCompute>(SubLoopBECountSC) ||
- !SubLoopBECountSC->getType()->isIntegerTy())
- return false;
- ScalarEvolution::LoopDisposition LD =
- SE.getLoopDisposition(SubLoopBECountSC, L);
- if (LD != ScalarEvolution::LoopInvariant)
+ // Check inner loop backedge count is consistent on all iterations of the
+ // outer loop
+ if (!hasIterationCountInvariantInParent(SubLoop, SE)) {
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "
+ "not consistent on each iteration\n");
return false;
+ }
// Check the loop safety info for exceptions.
- LoopSafetyInfo LSI;
- computeLoopSafetyInfo(&LSI, L);
- if (LSI.MayThrow)
+ SimpleLoopSafetyInfo LSI;
+ LSI.computeLoopSafetyInfo(L);
+ if (LSI.anyBlockMayThrow()) {
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n");
return false;
+ }
// We've ruled out the easy stuff and now need to check that there are no
// interdependencies which may prevent us from moving the:
@@ -772,14 +801,19 @@ bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
}
// Keep going
return true;
- }))
+ })) {
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't move required "
+ "instructions after subloop to before it\n");
return false;
+ }
// Check for memory dependencies which prohibit the unrolling we are doing.
// Because of the way we are unrolling Fore/Sub/Aft blocks, we need to check
// there are no dependencies between Fore-Sub, Fore-Aft, Sub-Aft and Sub-Sub.
- if (!checkDependencies(L, ForeBlocks, SubLoopBlocks, AftBlocks, DI))
+ if (!checkDependencies(L, ForeBlocks, SubLoopBlocks, AftBlocks, DI)) {
+ LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; failed dependency check\n");
return false;
+ }
return true;
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 03:11:58 +0000