diff options
Diffstat (limited to 'llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp | 822 |
1 files changed, 822 insertions, 0 deletions
diff --git a/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp b/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp new file mode 100644 index 0000000000000..bf2e87b0d49f6 --- /dev/null +++ b/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp @@ -0,0 +1,822 @@ +//===-- LoopUnrollAndJam.cpp - Loop unrolling utilities -------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements loop unroll and jam as a routine, much like +// LoopUnroll.cpp implements loop unroll. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/DependenceAnalysis.h" +#include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopIterator.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" +#include "llvm/Analysis/Utils/Local.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/LoopSimplify.h" +#include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Utils/SimplifyIndVar.h" +#include "llvm/Transforms/Utils/UnrollLoop.h" +using namespace llvm; + +#define DEBUG_TYPE "loop-unroll-and-jam" + +STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed"); +STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed"); + +typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet; + +// Partition blocks in an outer/inner loop pair into blocks before and after +// the loop +static bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop, + BasicBlockSet &ForeBlocks, + BasicBlockSet &SubLoopBlocks, + BasicBlockSet &AftBlocks, + DominatorTree *DT) { + BasicBlock *SubLoopLatch = SubLoop->getLoopLatch(); + SubLoopBlocks.insert(SubLoop->block_begin(), SubLoop->block_end()); + + for (BasicBlock *BB : L->blocks()) { + if (!SubLoop->contains(BB)) { + if (DT->dominates(SubLoopLatch, BB)) + AftBlocks.insert(BB); + else + ForeBlocks.insert(BB); + } + } + + // Check that all blocks in ForeBlocks together dominate the subloop + // TODO: This might ideally be done better with a dominator/postdominators. + BasicBlock *SubLoopPreHeader = SubLoop->getLoopPreheader(); + for (BasicBlock *BB : ForeBlocks) { + if (BB == SubLoopPreHeader) + continue; + Instruction *TI = BB->getTerminator(); + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + if (!ForeBlocks.count(TI->getSuccessor(i))) + return false; + } + + return true; +} + +// Looks at the phi nodes in Header for values coming from Latch. For these +// instructions and all their operands calls Visit on them, keeping going for +// all the operands in AftBlocks. Returns false if Visit returns false, +// otherwise returns true. This is used to process the instructions in the +// Aft blocks that need to be moved before the subloop. It is used in two +// places. One to check that the required set of instructions can be moved +// before the loop. Then to collect the instructions to actually move in +// moveHeaderPhiOperandsToForeBlocks. +template <typename T> +static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch, + BasicBlockSet &AftBlocks, T Visit) { + SmallVector<Instruction *, 8> Worklist; + for (auto &Phi : Header->phis()) { + Value *V = Phi.getIncomingValueForBlock(Latch); + if (Instruction *I = dyn_cast<Instruction>(V)) + Worklist.push_back(I); + } + + while (!Worklist.empty()) { + Instruction *I = Worklist.back(); + Worklist.pop_back(); + if (!Visit(I)) + return false; + + if (AftBlocks.count(I->getParent())) + for (auto &U : I->operands()) + if (Instruction *II = dyn_cast<Instruction>(U)) + Worklist.push_back(II); + } + + return true; +} + +// Move the phi operands of Header from Latch out of AftBlocks to InsertLoc. +static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header, + BasicBlock *Latch, + Instruction *InsertLoc, + BasicBlockSet &AftBlocks) { + // We need to ensure we move the instructions in the correct order, + // starting with the earliest required instruction and moving forward. + std::vector<Instruction *> Visited; + processHeaderPhiOperands(Header, Latch, AftBlocks, + [&Visited, &AftBlocks](Instruction *I) { + if (AftBlocks.count(I->getParent())) + Visited.push_back(I); + return true; + }); + + // Move all instructions in program order to before the InsertLoc + BasicBlock *InsertLocBB = InsertLoc->getParent(); + for (Instruction *I : reverse(Visited)) { + if (I->getParent() != InsertLocBB) + I->moveBefore(InsertLoc); + } +} + +/* + This method performs Unroll and Jam. For a simple loop like: + for (i = ..) + Fore(i) + for (j = ..) + SubLoop(i, j) + Aft(i) + + Instead of doing normal inner or outer unrolling, we do: + for (i = .., i+=2) + Fore(i) + Fore(i+1) + for (j = ..) + SubLoop(i, j) + SubLoop(i+1, j) + Aft(i) + Aft(i+1) + + So the outer loop is essetially unrolled and then the inner loops are fused + ("jammed") together into a single loop. This can increase speed when there + are loads in SubLoop that are invariant to i, as they become shared between + the now jammed inner loops. + + We do this by spliting the blocks in the loop into Fore, Subloop and Aft. + Fore blocks are those before the inner loop, Aft are those after. Normal + Unroll code is used to copy each of these sets of blocks and the results are + combined together into the final form above. + + 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, Loop **EpilogueLoop) { + + // When we enter here we should have already checked that it is safe + BasicBlock *Header = L->getHeader(); + assert(L->getSubLoops().size() == 1); + Loop *SubLoop = *L->begin(); + + // Don't enter the unroll code if there is nothing to do. + if (TripCount == 0 && Count < 2) { + LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; almost nothing to do\n"); + return LoopUnrollResult::Unmodified; + } + + assert(Count > 0); + assert(TripMultiple > 0); + assert(TripCount == 0 || TripCount % TripMultiple == 0); + + // Are we eliminating the loop control altogether? + bool CompletelyUnroll = (Count == TripCount); + + // We use the runtime remainder in cases where we don't know trip multiple + if (TripMultiple == 1 || TripMultiple % Count != 0) { + if (!UnrollRuntimeLoopRemainder(L, Count, /*AllowExpensiveTripCount*/ false, + /*UseEpilogRemainder*/ true, + UnrollRemainder, /*ForgetAllSCEV*/ false, + 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; + } + } + + // Notify ScalarEvolution that the loop will be substantially changed, + // if not outright eliminated. + if (SE) { + SE->forgetLoop(L); + SE->forgetLoop(SubLoop); + } + + using namespace ore; + // Report the unrolling decision. + if (CompletelyUnroll) { + LLVM_DEBUG(dbgs() << "COMPLETELY UNROLL AND JAMMING loop %" + << Header->getName() << " with trip count " << TripCount + << "!\n"); + ORE->emit(OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(), + L->getHeader()) + << "completely unroll and jammed loop with " + << NV("UnrollCount", TripCount) << " iterations"); + } else { + auto DiagBuilder = [&]() { + OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(), + L->getHeader()); + return Diag << "unroll and jammed loop by a factor of " + << NV("UnrollCount", Count); + }; + + LLVM_DEBUG(dbgs() << "UNROLL AND JAMMING loop %" << Header->getName() + << " by " << Count); + if (TripMultiple != 1) { + LLVM_DEBUG(dbgs() << " with " << TripMultiple << " trips per branch"); + ORE->emit([&]() { + return DiagBuilder() << " with " << NV("TripMultiple", TripMultiple) + << " trips per branch"; + }); + } else { + LLVM_DEBUG(dbgs() << " with run-time trip count"); + ORE->emit([&]() { return DiagBuilder() << " with run-time trip count"; }); + } + LLVM_DEBUG(dbgs() << "!\n"); + } + + BasicBlock *Preheader = L->getLoopPreheader(); + BasicBlock *LatchBlock = L->getLoopLatch(); + BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator()); + assert(Preheader && LatchBlock && Header); + assert(BI && !BI->isUnconditional()); + bool ContinueOnTrue = L->contains(BI->getSuccessor(0)); + BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue); + bool SubLoopContinueOnTrue = SubLoop->contains( + SubLoop->getLoopLatch()->getTerminator()->getSuccessor(0)); + + // Partition blocks in an outer/inner loop pair into blocks before and after + // the loop + BasicBlockSet SubLoopBlocks; + BasicBlockSet ForeBlocks; + BasicBlockSet AftBlocks; + partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks, AftBlocks, + DT); + + // We keep track of the entering/first and exiting/last block of each of + // Fore/SubLoop/Aft in each iteration. This helps make the stapling up of + // blocks easier. + std::vector<BasicBlock *> ForeBlocksFirst; + std::vector<BasicBlock *> ForeBlocksLast; + std::vector<BasicBlock *> SubLoopBlocksFirst; + std::vector<BasicBlock *> SubLoopBlocksLast; + std::vector<BasicBlock *> AftBlocksFirst; + std::vector<BasicBlock *> AftBlocksLast; + ForeBlocksFirst.push_back(Header); + ForeBlocksLast.push_back(SubLoop->getLoopPreheader()); + SubLoopBlocksFirst.push_back(SubLoop->getHeader()); + SubLoopBlocksLast.push_back(SubLoop->getExitingBlock()); + AftBlocksFirst.push_back(SubLoop->getExitBlock()); + AftBlocksLast.push_back(L->getExitingBlock()); + // Maps Blocks[0] -> Blocks[It] + ValueToValueMapTy LastValueMap; + + // Move any instructions from fore phi operands from AftBlocks into Fore. + moveHeaderPhiOperandsToForeBlocks( + Header, LatchBlock, SubLoop->getLoopPreheader()->getTerminator(), + AftBlocks); + + // The current on-the-fly SSA update requires blocks to be processed in + // reverse postorder so that LastValueMap contains the correct value at each + // exit. + LoopBlocksDFS DFS(L); + DFS.perform(LI); + // Stash the DFS iterators before adding blocks to the loop. + LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO(); + LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO(); + + if (Header->getParent()->isDebugInfoForProfiling()) + for (BasicBlock *BB : L->getBlocks()) + for (Instruction &I : *BB) + if (!isa<DbgInfoIntrinsic>(&I)) + if (const DILocation *DIL = I.getDebugLoc()) { + auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(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) { + std::vector<BasicBlock *> NewBlocks; + // Maps Blocks[It] -> Blocks[It-1] + DenseMap<Value *, Value *> PrevItValueMap; + + for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { + ValueToValueMapTy VMap; + BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It)); + Header->getParent()->getBasicBlockList().push_back(New); + + if (ForeBlocks.count(*BB)) { + L->addBasicBlockToLoop(New, *LI); + + if (*BB == ForeBlocksFirst[0]) + ForeBlocksFirst.push_back(New); + if (*BB == ForeBlocksLast[0]) + ForeBlocksLast.push_back(New); + } else if (SubLoopBlocks.count(*BB)) { + SubLoop->addBasicBlockToLoop(New, *LI); + + if (*BB == SubLoopBlocksFirst[0]) + SubLoopBlocksFirst.push_back(New); + if (*BB == SubLoopBlocksLast[0]) + SubLoopBlocksLast.push_back(New); + } else if (AftBlocks.count(*BB)) { + L->addBasicBlockToLoop(New, *LI); + + if (*BB == AftBlocksFirst[0]) + AftBlocksFirst.push_back(New); + if (*BB == AftBlocksLast[0]) + AftBlocksLast.push_back(New); + } else { + llvm_unreachable("BB being cloned should be in Fore/Sub/Aft"); + } + + // Update our running maps of newest clones + PrevItValueMap[New] = (It == 1 ? *BB : LastValueMap[*BB]); + LastValueMap[*BB] = New; + for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end(); + VI != VE; ++VI) { + PrevItValueMap[VI->second] = + const_cast<Value *>(It == 1 ? VI->first : LastValueMap[VI->first]); + LastValueMap[VI->first] = VI->second; + } + + NewBlocks.push_back(New); + + // Update DomTree: + if (*BB == ForeBlocksFirst[0]) + DT->addNewBlock(New, ForeBlocksLast[It - 1]); + else if (*BB == SubLoopBlocksFirst[0]) + DT->addNewBlock(New, SubLoopBlocksLast[It - 1]); + else if (*BB == AftBlocksFirst[0]) + DT->addNewBlock(New, AftBlocksLast[It - 1]); + else { + // Each set of blocks (Fore/Sub/Aft) will have the same internal domtree + // structure. + auto BBDomNode = DT->getNode(*BB); + auto BBIDom = BBDomNode->getIDom(); + BasicBlock *OriginalBBIDom = BBIDom->getBlock(); + assert(OriginalBBIDom); + assert(LastValueMap[cast<Value>(OriginalBBIDom)]); + DT->addNewBlock( + New, cast<BasicBlock>(LastValueMap[cast<Value>(OriginalBBIDom)])); + } + } + + // Remap all instructions in the most recent iteration + for (BasicBlock *NewBlock : NewBlocks) { + for (Instruction &I : *NewBlock) { + ::remapInstruction(&I, LastValueMap); + if (auto *II = dyn_cast<IntrinsicInst>(&I)) + if (II->getIntrinsicID() == Intrinsic::assume) + AC->registerAssumption(II); + } + } + + // Alter the ForeBlocks phi's, pointing them at the latest version of the + // value from the previous iteration's phis + for (PHINode &Phi : ForeBlocksFirst[It]->phis()) { + Value *OldValue = Phi.getIncomingValueForBlock(AftBlocksLast[It]); + assert(OldValue && "should have incoming edge from Aft[It]"); + Value *NewValue = OldValue; + if (Value *PrevValue = PrevItValueMap[OldValue]) + NewValue = PrevValue; + + assert(Phi.getNumOperands() == 2); + Phi.setIncomingBlock(0, ForeBlocksLast[It - 1]); + Phi.setIncomingValue(0, NewValue); + Phi.removeIncomingValue(1); + } + } + + // Now that all the basic blocks for the unrolled iterations are in place, + // finish up connecting the blocks and phi nodes. At this point LastValueMap + // is the last unrolled iterations values. + + // Update Phis in BB from OldBB to point to NewBB + auto updatePHIBlocks = [](BasicBlock *BB, BasicBlock *OldBB, + BasicBlock *NewBB) { + for (PHINode &Phi : BB->phis()) { + int I = Phi.getBasicBlockIndex(OldBB); + Phi.setIncomingBlock(I, NewBB); + } + }; + // Update Phis in BB from OldBB to point to NewBB and use the latest value + // from LastValueMap + auto updatePHIBlocksAndValues = [](BasicBlock *BB, BasicBlock *OldBB, + BasicBlock *NewBB, + ValueToValueMapTy &LastValueMap) { + for (PHINode &Phi : BB->phis()) { + for (unsigned b = 0; b < Phi.getNumIncomingValues(); ++b) { + if (Phi.getIncomingBlock(b) == OldBB) { + Value *OldValue = Phi.getIncomingValue(b); + if (Value *LastValue = LastValueMap[OldValue]) + Phi.setIncomingValue(b, LastValue); + Phi.setIncomingBlock(b, NewBB); + break; + } + } + } + }; + // Move all the phis from Src into Dest + auto movePHIs = [](BasicBlock *Src, BasicBlock *Dest) { + Instruction *insertPoint = Dest->getFirstNonPHI(); + while (PHINode *Phi = dyn_cast<PHINode>(Src->begin())) + Phi->moveBefore(insertPoint); + }; + + // Update the PHI values outside the loop to point to the last block + updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.back(), + LastValueMap); + + // Update ForeBlocks successors and phi nodes + BranchInst *ForeTerm = + cast<BranchInst>(ForeBlocksLast.back()->getTerminator()); + BasicBlock *Dest = SubLoopBlocksFirst[0]; + ForeTerm->setSuccessor(0, Dest); + + if (CompletelyUnroll) { + while (PHINode *Phi = dyn_cast<PHINode>(ForeBlocksFirst[0]->begin())) { + Phi->replaceAllUsesWith(Phi->getIncomingValueForBlock(Preheader)); + Phi->getParent()->getInstList().erase(Phi); + } + } else { + // Update the PHI values to point to the last aft block + updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0], + AftBlocksLast.back(), LastValueMap); + } + + for (unsigned It = 1; It != Count; It++) { + // Remap ForeBlock successors from previous iteration to this + BranchInst *ForeTerm = + cast<BranchInst>(ForeBlocksLast[It - 1]->getTerminator()); + BasicBlock *Dest = ForeBlocksFirst[It]; + ForeTerm->setSuccessor(0, Dest); + } + + // Subloop successors and phis + BranchInst *SubTerm = + cast<BranchInst>(SubLoopBlocksLast.back()->getTerminator()); + SubTerm->setSuccessor(!SubLoopContinueOnTrue, SubLoopBlocksFirst[0]); + SubTerm->setSuccessor(SubLoopContinueOnTrue, AftBlocksFirst[0]); + updatePHIBlocks(SubLoopBlocksFirst[0], ForeBlocksLast[0], + ForeBlocksLast.back()); + updatePHIBlocks(SubLoopBlocksFirst[0], SubLoopBlocksLast[0], + SubLoopBlocksLast.back()); + + for (unsigned It = 1; It != Count; It++) { + // Replace the conditional branch of the previous iteration subloop with an + // unconditional one to this one + BranchInst *SubTerm = + cast<BranchInst>(SubLoopBlocksLast[It - 1]->getTerminator()); + BranchInst::Create(SubLoopBlocksFirst[It], SubTerm); + SubTerm->eraseFromParent(); + + updatePHIBlocks(SubLoopBlocksFirst[It], ForeBlocksLast[It], + ForeBlocksLast.back()); + updatePHIBlocks(SubLoopBlocksFirst[It], SubLoopBlocksLast[It], + SubLoopBlocksLast.back()); + movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]); + } + + // Aft blocks successors and phis + BranchInst *Term = cast<BranchInst>(AftBlocksLast.back()->getTerminator()); + if (CompletelyUnroll) { + BranchInst::Create(LoopExit, Term); + Term->eraseFromParent(); + } else { + Term->setSuccessor(!ContinueOnTrue, ForeBlocksFirst[0]); + } + updatePHIBlocks(AftBlocksFirst[0], SubLoopBlocksLast[0], + SubLoopBlocksLast.back()); + + for (unsigned It = 1; It != Count; It++) { + // Replace the conditional branch of the previous iteration subloop with an + // unconditional one to this one + BranchInst *AftTerm = + cast<BranchInst>(AftBlocksLast[It - 1]->getTerminator()); + BranchInst::Create(AftBlocksFirst[It], AftTerm); + AftTerm->eraseFromParent(); + + updatePHIBlocks(AftBlocksFirst[It], SubLoopBlocksLast[It], + SubLoopBlocksLast.back()); + movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]); + } + + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); + // Dominator Tree. Remove the old links between Fore, Sub and Aft, adding the + // new ones required. + if (Count != 1) { + SmallVector<DominatorTree::UpdateType, 4> DTUpdates; + DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete, ForeBlocksLast[0], + SubLoopBlocksFirst[0]); + DTUpdates.emplace_back(DominatorTree::UpdateKind::Delete, + SubLoopBlocksLast[0], AftBlocksFirst[0]); + + DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert, + ForeBlocksLast.back(), SubLoopBlocksFirst[0]); + DTUpdates.emplace_back(DominatorTree::UpdateKind::Insert, + SubLoopBlocksLast.back(), AftBlocksFirst[0]); + DTU.applyUpdatesPermissive(DTUpdates); + } + + // Merge adjacent basic blocks, if possible. + SmallPtrSet<BasicBlock *, 16> MergeBlocks; + MergeBlocks.insert(ForeBlocksLast.begin(), ForeBlocksLast.end()); + MergeBlocks.insert(SubLoopBlocksLast.begin(), SubLoopBlocksLast.end()); + MergeBlocks.insert(AftBlocksLast.begin(), AftBlocksLast.end()); + while (!MergeBlocks.empty()) { + BasicBlock *BB = *MergeBlocks.begin(); + BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator()); + if (Term && Term->isUnconditional() && L->contains(Term->getSuccessor(0))) { + BasicBlock *Dest = Term->getSuccessor(0); + BasicBlock *Fold = Dest->getUniquePredecessor(); + if (MergeBlockIntoPredecessor(Dest, &DTU, LI)) { + // Don't remove BB and add Fold as they are the same BB + assert(Fold == BB); + (void)Fold; + MergeBlocks.erase(Dest); + } else + MergeBlocks.erase(BB); + } else + MergeBlocks.erase(BB); + } + // Apply updates to the DomTree. + DT = &DTU.getDomTree(); + + // 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. + simplifyLoopAfterUnroll(SubLoop, true, LI, SE, DT, AC); + simplifyLoopAfterUnroll(L, !CompletelyUnroll && Count > 1, LI, SE, DT, AC); + + NumCompletelyUnrolledAndJammed += CompletelyUnroll; + ++NumUnrolledAndJammed; + +#ifndef NDEBUG + // We shouldn't have done anything to break loop simplify form or LCSSA. + Loop *OuterL = L->getParentLoop(); + Loop *OutestLoop = OuterL ? OuterL : (!CompletelyUnroll ? L : SubLoop); + assert(OutestLoop->isRecursivelyLCSSAForm(*DT, *LI)); + if (!CompletelyUnroll) + assert(L->isLoopSimplifyForm()); + assert(SubLoop->isLoopSimplifyForm()); + assert(DT->verify()); +#endif + + // Update LoopInfo if the loop is completely removed. + if (CompletelyUnroll) + LI->erase(L); + + return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled + : LoopUnrollResult::PartiallyUnrolled; +} + +static bool getLoadsAndStores(BasicBlockSet &Blocks, + SmallVector<Value *, 4> &MemInstr) { + // Scan the BBs and collect legal loads and stores. + // Returns false if non-simple loads/stores are found. + for (BasicBlock *BB : Blocks) { + for (Instruction &I : *BB) { + if (auto *Ld = dyn_cast<LoadInst>(&I)) { + if (!Ld->isSimple()) + return false; + MemInstr.push_back(&I); + } else if (auto *St = dyn_cast<StoreInst>(&I)) { + if (!St->isSimple()) + return false; + MemInstr.push_back(&I); + } else if (I.mayReadOrWriteMemory()) { + return false; + } + } + } + return true; +} + +static bool checkDependencies(SmallVector<Value *, 4> &Earlier, + SmallVector<Value *, 4> &Later, + unsigned LoopDepth, bool InnerLoop, + DependenceInfo &DI) { + // Use DA to check for dependencies between loads and stores that make unroll + // and jam invalid + for (Value *I : Earlier) { + for (Value *J : Later) { + Instruction *Src = cast<Instruction>(I); + Instruction *Dst = cast<Instruction>(J); + if (Src == Dst) + continue; + // Ignore Input dependencies. + if (isa<LoadInst>(Src) && isa<LoadInst>(Dst)) + continue; + + // Track dependencies, and if we find them take a conservative approach + // by allowing only = or < (not >), altough some > would be safe + // (depending upon unroll width). + // For the inner loop, we need to disallow any (> <) dependencies + // FIXME: Allow > so long as distance is less than unroll width + if (auto D = DI.depends(Src, Dst, true)) { + assert(D->isOrdered() && "Expected an output, flow or anti dep."); + + 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) { + 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) { + LLVM_DEBUG(dbgs() << " < > dependency between:\n" + << " " << *Src << "\n" + << " " << *Dst << "\n"); + return false; + } + } + } + } + } + return true; +} + +static bool checkDependencies(Loop *L, BasicBlockSet &ForeBlocks, + BasicBlockSet &SubLoopBlocks, + BasicBlockSet &AftBlocks, DependenceInfo &DI) { + // Get all loads/store pairs for each blocks + SmallVector<Value *, 4> ForeMemInstr; + SmallVector<Value *, 4> SubLoopMemInstr; + SmallVector<Value *, 4> AftMemInstr; + if (!getLoadsAndStores(ForeBlocks, ForeMemInstr) || + !getLoadsAndStores(SubLoopBlocks, SubLoopMemInstr) || + !getLoadsAndStores(AftBlocks, AftMemInstr)) + return false; + + // Check for dependencies between any blocks that may change order + unsigned LoopDepth = L->getLoopDepth(); + return checkDependencies(ForeMemInstr, SubLoopMemInstr, LoopDepth, false, + DI) && + checkDependencies(ForeMemInstr, AftMemInstr, LoopDepth, false, DI) && + checkDependencies(SubLoopMemInstr, AftMemInstr, LoopDepth, false, + DI) && + checkDependencies(SubLoopMemInstr, SubLoopMemInstr, LoopDepth, true, + DI); +} + +bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, + DependenceInfo &DI) { + /* We currently handle outer loops like this: + | + ForeFirst <----\ } + Blocks | } ForeBlocks + ForeLast | } + | | + SubLoopFirst <\ | } + Blocks | | } SubLoopBlocks + SubLoopLast -/ | } + | | + AftFirst | } + Blocks | } AftBlocks + AftLast ------/ } + | + + There are (theoretically) any number of blocks in ForeBlocks, SubLoopBlocks + and AftBlocks, providing that there is one edge from Fores to SubLoops, + one edge from SubLoops to Afts and a single outer loop exit (from Afts). + In practice we currently limit Aft blocks to a single block, and limit + things further in the profitablility checks of the unroll and jam pass. + + Because of the way we rearrange basic blocks, we also require that + the Fore blocks on all unrolled iterations are safe to move before the + SubLoop blocks of all iterations. So we require that the phi node looping + operands of ForeHeader can be moved to at least the end of ForeEnd, so that + we can arrange cloned Fore Blocks before the subloop and match up Phi's + correctly. + + i.e. The old order of blocks used to be F1 S1_1 S1_2 A1 F2 S2_1 S2_2 A2. + It needs to be safe to tranform this to F1 F2 S1_1 S2_1 S1_2 S2_2 A1 A2. + + There are then a number of checks along the lines of no calls, no + exceptions, inner loop IV is consistent, etc. Note that for loops requiring + runtime unrolling, UnrollRuntimeLoopRemainder can also fail in + UnrollAndJamLoop if the trip count cannot be easily calculated. + */ + + if (!L->isLoopSimplifyForm() || L->getSubLoops().size() != 1) + return false; + Loop *SubLoop = L->getSubLoops()[0]; + if (!SubLoop->isLoopSimplifyForm()) + return false; + + BasicBlock *Header = L->getHeader(); + BasicBlock *Latch = L->getLoopLatch(); + BasicBlock *Exit = L->getExitingBlock(); + BasicBlock *SubLoopHeader = SubLoop->getHeader(); + BasicBlock *SubLoopLatch = SubLoop->getLoopLatch(); + BasicBlock *SubLoopExit = SubLoop->getExitingBlock(); + + if (Latch != Exit) + return false; + if (SubLoopLatch != SubLoopExit) + return false; + + 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)) { + 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) { + LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Can't currently handle " + "multiple blocks after the loop\n"); + return false; + } + + // 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. + 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: + // ForeBlocks before Subloop and AftBlocks. + // Subloop before AftBlocks. + // ForeBlock phi operands before the subloop + + // Make sure we can move all instructions we need to before the subloop + if (!processHeaderPhiOperands( + Header, Latch, AftBlocks, [&AftBlocks, &SubLoop](Instruction *I) { + if (SubLoop->contains(I->getParent())) + return false; + if (AftBlocks.count(I->getParent())) { + // If we hit a phi node in afts we know we are done (probably + // LCSSA) + if (isa<PHINode>(I)) + return false; + // Can't move instructions with side effects or memory + // reads/writes + if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory()) + return false; + } + // 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)) { + LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; failed dependency check\n"); + return false; + } + + return true; +} |