Index: include/llvm/Analysis/TargetTransformInfo.h =================================================================== --- include/llvm/Analysis/TargetTransformInfo.h +++ include/llvm/Analysis/TargetTransformInfo.h @@ -422,6 +422,10 @@ bool AllowPeeling; /// Allow unrolling of all the iterations of the runtime loop remainder. bool UnrollRemainder; + /// Allow unroll and jam + bool UnrollAndJam; + /// Threshold for unroll and jam, for inner loop size + unsigned UnrollAndJamThreshold; }; /// \brief Get target-customized preferences for the generic loop unrolling Index: include/llvm/Transforms/Utils/UnrollLoop.h =================================================================== --- include/llvm/Transforms/Utils/UnrollLoop.h +++ include/llvm/Transforms/Utils/UnrollLoop.h @@ -19,11 +19,13 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Transforms/Utils/ValueMapper.h" namespace llvm { class AssumptionCache; class BasicBlock; +class DependenceInfo; class DominatorTree; class Loop; class LoopInfo; @@ -61,6 +63,12 @@ DominatorTree *DT, AssumptionCache *AC, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA); +LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, + unsigned TripMultiple, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, + DominatorTree *DT, AssumptionCache *AC, + OptimizationRemarkEmitter *ORE); + bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, bool AllowExpensiveTripCount, bool UseEpilogRemainder, bool UnrollRemainder, @@ -76,8 +84,27 @@ bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA); +bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, + DependenceInfo &DI); + +bool isProfitableToUnrollAndJam(Loop *L, const TargetTransformInfo &TTI, + ScalarEvolution &SE, DominatorTree &DT, + DependenceInfo &DI, + TargetTransformInfo::UnrollingPreferences &UP); + +BasicBlock *foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI, + ScalarEvolution *SE, + SmallPtrSetImpl &ForgottenLoops, + DominatorTree *DT); + +void remapInstruction(Instruction *I, ValueToValueMapTy &VMap); + MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name); +void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC); + } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H Index: lib/Analysis/DependenceAnalysis.cpp =================================================================== --- lib/Analysis/DependenceAnalysis.cpp +++ lib/Analysis/DependenceAnalysis.cpp @@ -108,7 +108,7 @@ STATISTIC(BanerjeeSuccesses, "Banerjee successes"); static cl::opt -Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, +Delinearize("da-delinearize", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Try to delinearize array references.")); //===----------------------------------------------------------------------===// @@ -623,12 +623,27 @@ } static AliasResult underlyingObjectsAlias(AliasAnalysis *AA, - const DataLayout &DL, const Value *A, + const DataLayout &DL, + const Instruction *AI, const Value *A, + const Instruction *BI, const Value *B) { const Value *AObj = GetUnderlyingObject(A, DL); const Value *BObj = GetUnderlyingObject(B, DL); - return AA->alias(AObj, DL.getTypeStoreSize(AObj->getType()), - BObj, DL.getTypeStoreSize(BObj->getType())); + + MemoryLocation MAObj(AObj); + MemoryLocation MBObj(BObj); + + if (const auto *LI = dyn_cast(AI)) + LI->getAAMetadata(MAObj.AATags); + else if (const auto *SI = dyn_cast(AI)) + SI->getAAMetadata(MAObj.AATags); + + if (const auto *LI = dyn_cast(BI)) + LI->getAAMetadata(MBObj.AATags); + else if (const auto *SI = dyn_cast(BI)) + SI->getAAMetadata(MBObj.AATags); + + return AA->alias(MAObj, MBObj); } @@ -3306,8 +3321,8 @@ Value *SrcPtr = getPointerOperand(Src); Value *DstPtr = getPointerOperand(Dst); - switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, - SrcPtr)) { + switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), Dst, + DstPtr, Src, SrcPtr)) { case MayAlias: case PartialAlias: // cannot analyse objects if we don't understand their aliasing. @@ -3755,8 +3770,8 @@ assert(isLoadOrStore(Dst)); Value *SrcPtr = getPointerOperand(Src); Value *DstPtr = getPointerOperand(Dst); - assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, - SrcPtr) == MustAlias); + assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), Dst, + DstPtr, Src, SrcPtr) == MustAlias); // establish loop nesting levels establishNestingLevels(Src, Dst); Index: lib/Target/ARM/ARMTargetTransformInfo.cpp =================================================================== --- lib/Target/ARM/ARMTargetTransformInfo.cpp +++ lib/Target/ARM/ARMTargetTransformInfo.cpp @@ -618,6 +618,8 @@ UP.Runtime = true; UP.UnrollRemainder = true; UP.DefaultUnrollRuntimeCount = 4; + UP.UnrollAndJam = true; + UP.UnrollAndJamThreshold = 50; // Force unrolling small loops can be very useful because of the branch // taken cost of the backedge. Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -503,43 +503,6 @@ return Changed; } -/// Computes loop safety information, checks loop body & header -/// for the possibility of may throw exception. -/// -void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) { - assert(CurLoop != nullptr && "CurLoop cant be null"); - BasicBlock *Header = CurLoop->getHeader(); - // Setting default safety values. - SafetyInfo->MayThrow = false; - SafetyInfo->HeaderMayThrow = false; - // Iterate over header and compute safety info. - for (BasicBlock::iterator I = Header->begin(), E = Header->end(); - (I != E) && !SafetyInfo->HeaderMayThrow; ++I) - SafetyInfo->HeaderMayThrow |= - !isGuaranteedToTransferExecutionToSuccessor(&*I); - - SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow; - // Iterate over loop instructions and compute safety info. - // Skip header as it has been computed and stored in HeaderMayThrow. - // The first block in loopinfo.Blocks is guaranteed to be the header. - assert(Header == *CurLoop->getBlocks().begin() && - "First block must be header"); - for (Loop::block_iterator BB = std::next(CurLoop->block_begin()), - BBE = CurLoop->block_end(); - (BB != BBE) && !SafetyInfo->MayThrow; ++BB) - for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); - (I != E) && !SafetyInfo->MayThrow; ++I) - SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I); - - // Compute funclet colors if we might sink/hoist in a function with a funclet - // personality routine. - Function *Fn = CurLoop->getHeader()->getParent(); - if (Fn->hasPersonalityFn()) - if (Constant *PersonalityFn = Fn->getPersonalityFn()) - if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn))) - SafetyInfo->BlockColors = colorEHFunclets(*Fn); -} - // Return true if LI is invariant within scope of the loop. LI is invariant if // CurLoop is dominated by an invariant.start representing the same memory // location and size as the memory location LI loads from, and also the Index: lib/Transforms/Scalar/LoopUnrollPass.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnrollPass.cpp +++ lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -25,6 +25,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CodeMetrics.h" +#include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" @@ -191,6 +192,8 @@ UP.Force = false; UP.UpperBound = false; UP.AllowPeeling = true; + UP.UnrollAndJam = false; + UP.UnrollAndJamThreshold = 50; // Override with any target specific settings TTI.getUnrollingPreferences(L, SE, UP); @@ -950,7 +953,7 @@ static LoopUnrollResult tryToUnrollLoop( Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, - const TargetTransformInfo &TTI, AssumptionCache &AC, + const TargetTransformInfo &TTI, AssumptionCache &AC, DependenceInfo *DI, OptimizationRemarkEmitter &ORE, bool PreserveLCSSA, int OptLevel, Optional ProvidedCount, Optional ProvidedThreshold, Optional ProvidedAllowPartial, Optional ProvidedRuntime, @@ -1049,11 +1052,40 @@ if (TripCount && UP.Count > TripCount) UP.Count = TripCount; + // TODOD Move somewhere better + bool UnrollAndJam = false; + if (UP.UnrollAndJam && UP.Count > 1 && DI) { + if (isProfitableToUnrollAndJam(L, TTI, SE, DT, *DI, UP)) + UnrollAndJam = true; + else if (L->getParentLoop() && + isProfitableToUnrollAndJam(L->getParentLoop(), TTI, SE, DT, *DI, + UP)) + return LoopUnrollResult::Unmodified; + } + // Unroll the loop. - LoopUnrollResult UnrollResult = UnrollLoop( - L, UP.Count, TripCount, UP.Force, UP.Runtime, UP.AllowExpensiveTripCount, - UseUpperBound, MaxOrZero, TripMultiple, UP.PeelCount, UP.UnrollRemainder, - LI, &SE, &DT, &AC, &ORE, PreserveLCSSA); + LoopUnrollResult UnrollResult; + if (!UnrollAndJam) + UnrollResult = + UnrollLoop(L, UP.Count, TripCount, UP.Force, UP.Runtime, + UP.AllowExpensiveTripCount, UseUpperBound, MaxOrZero, + TripMultiple, UP.PeelCount, UP.UnrollRemainder, LI, &SE, &DT, + &AC, &ORE, PreserveLCSSA); + else { + Loop *SubLoop = L->getSubLoops()[0]; + + UnrollResult = + UnrollAndJamLoop(L, UP.Count, TripCount, TripMultiple, + UP.UnrollRemainder, LI, &SE, &DT, &AC, &ORE); + + // Outer loop has been unrolled and jammed, now unroll the inner loop up to + // the threshold + tryToUnrollLoop(SubLoop, DT, LI, SE, TTI, AC, DI, ORE, PreserveLCSSA, + OptLevel, ProvidedCount, ProvidedThreshold, + ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound, + ProvidedAllowPeeling); + } + if (UnrollResult == LoopUnrollResult::Unmodified) return LoopUnrollResult::Unmodified; @@ -1106,6 +1138,7 @@ const TargetTransformInfo &TTI = getAnalysis().getTTI(F); auto &AC = getAnalysis().getAssumptionCache(F); + auto &DI = getAnalysis().getDI(); // For the old PM, we can't use OptimizationRemarkEmitter as an analysis // pass. Function analyses need to be preserved across loop transformations // but ORE cannot be preserved (see comment before the pass definition). @@ -1113,8 +1146,8 @@ bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); LoopUnrollResult Result = tryToUnrollLoop( - L, DT, LI, SE, TTI, AC, ORE, PreserveLCSSA, OptLevel, ProvidedCount, - ProvidedThreshold, ProvidedAllowPartial, ProvidedRuntime, + L, DT, LI, SE, TTI, AC, &DI, ORE, PreserveLCSSA, OptLevel, + ProvidedCount, ProvidedThreshold, ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound, ProvidedAllowPeeling); if (Result == LoopUnrollResult::FullyUnrolled) @@ -1128,6 +1161,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); + AU.addRequired(); // FIXME: Loop passes are required to preserve domtree, and for now we just // recreate dom info if anything gets unrolled. getLoopAnalysisUsage(AU); @@ -1142,6 +1176,7 @@ INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(LoopPass) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass) INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false) Pass *llvm::createLoopUnrollPass(int OptLevel, int Threshold, int Count, @@ -1170,6 +1205,7 @@ AM.getResult(L, AR).getManager(); Function *F = L.getHeader()->getParent(); + auto *DI = FAM.getCachedResult(*F); auto *ORE = FAM.getCachedResult(*F); // FIXME: This should probably be optional rather than required. if (!ORE) @@ -1189,7 +1225,7 @@ std::string LoopName = L.getName(); bool Changed = - tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, *ORE, + tryToUnrollLoop(&L, AR.DT, &AR.LI, AR.SE, AR.TTI, AR.AC, DI, *ORE, /*PreserveLCSSA*/ true, OptLevel, /*Count*/ None, /*Threshold*/ None, /*AllowPartial*/ false, /*Runtime*/ false, /*UpperBound*/ false, @@ -1281,6 +1317,7 @@ auto &TTI = AM.getResult(F); auto &DT = AM.getResult(F); auto &AC = AM.getResult(F); + auto &DI = AM.getResult(F); auto &ORE = AM.getResult(F); LoopAnalysisManager *LAM = nullptr; @@ -1329,7 +1366,7 @@ AllowPeeling = false; std::string LoopName = L.getName(); LoopUnrollResult Result = - tryToUnrollLoop(&L, DT, &LI, SE, TTI, AC, ORE, + tryToUnrollLoop(&L, DT, &LI, SE, TTI, AC, &DI, ORE, /*PreserveLCSSA*/ true, OptLevel, /*Count*/ None, /*Threshold*/ None, AllowPartialParam, RuntimeParam, UpperBoundParam, AllowPeeling); Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -27,6 +27,7 @@ Local.cpp LoopSimplify.cpp LoopUnroll.cpp + LoopUnrollAndJam.cpp LoopUnrollPeel.cpp LoopUnrollRuntime.cpp LoopUtils.cpp Index: lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- lib/Transforms/Utils/LoopUnroll.cpp +++ lib/Transforms/Utils/LoopUnroll.cpp @@ -51,7 +51,7 @@ cl::desc("Allow runtime unrolled loops to be unrolled " "with epilog instead of prolog.")); -static cl::opt +cl::opt UnrollVerifyDomtree("unroll-verify-domtree", cl::Hidden, cl::desc("Verify domtree after unrolling"), #ifdef NDEBUG @@ -63,8 +63,7 @@ /// Convert the instruction operands from referencing the current values into /// those specified by VMap. -static inline void remapInstruction(Instruction *I, - ValueToValueMapTy &VMap) { +void llvm::remapInstruction(Instruction *I, ValueToValueMapTy &VMap) { for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { Value *Op = I->getOperand(op); @@ -103,10 +102,9 @@ /// references to the eliminated BB. The argument ForgottenLoops contains a set /// 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, ScalarEvolution *SE, - SmallPtrSetImpl &ForgottenLoops, - DominatorTree *DT) { +BasicBlock *llvm::foldBlockIntoPredecessor( + BasicBlock *BB, LoopInfo *LI, ScalarEvolution *SE, + SmallPtrSetImpl &ForgottenLoops, DominatorTree *DT) { // 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 // if there are no PHI nodes. @@ -116,7 +114,8 @@ if (OnlyPred->getTerminator()->getNumSuccessors() != 1) return nullptr; - DEBUG(dbgs() << "Merging: " << *BB << "into: " << *OnlyPred); + DEBUG(dbgs() << "Merging: " << BB->getName() << " into " + << OnlyPred->getName() << "\n"); // Resolve any PHI nodes at the start of the block. They are all // guaranteed to have exactly one entry if they exist, unless there are @@ -265,6 +264,45 @@ return false; } +void llvm::simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, + ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC) { + // Simplify any new induction variables in the partially unrolled loop. + if (SE && SimplifyIVs) { + SmallVector 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(&*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. + const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); + const std::vector &NewLoopBlocks = L->getBlocks(); + for (BasicBlock *BB : NewLoopBlocks) { + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { + Instruction *Inst = &*I++; + + if (Value *V = SimplifyInstruction(Inst, {DL, nullptr, DT, AC})) + if (LI->replacementPreservesLCSSAForm(Inst, V)) + Inst->replaceAllUsesWith(V); + if (isInstructionTriviallyDead(Inst)) + BB->getInstList().erase(Inst); + } + } + + // TODO: after peeling or unrolling, previously loop variant conditions are + // likely to fold to constants, eagerly propagating those here will require + // fewer cleanup passes to be run. Alternatively, a LoopEarlyCSE might be + // appropriate. +} + /// Unroll the given loop by Count. The loop must be in LCSSA form. Unrolling /// can only fail when the loop's latch block is not terminated by a conditional /// branch instruction. However, if the trip count (and multiple) are not known, @@ -789,40 +827,10 @@ } } - // Simplify any new induction variables in the partially unrolled loop. - if (SE && !CompletelyUnroll && Count > 1) { - SmallVector 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(&*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. - const DataLayout &DL = Header->getModule()->getDataLayout(); - const std::vector &NewLoopBlocks = L->getBlocks(); - for (BasicBlock *BB : NewLoopBlocks) { - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { - Instruction *Inst = &*I++; - - if (Value *V = SimplifyInstruction(Inst, {DL, nullptr, DT, AC})) - if (LI->replacementPreservesLCSSAForm(Inst, V)) - Inst->replaceAllUsesWith(V); - if (isInstructionTriviallyDead(Inst)) - BB->getInstList().erase(Inst); - } - } - - // TODO: after peeling or unrolling, previously loop variant conditions are - // likely to fold to constants, eagerly propagating those here will require - // fewer cleanup passes to be run. Alternatively, a LoopEarlyCSE might be - // appropriate. + simplifyLoopAfterUnroll(L, !CompletelyUnroll && Count > 1, LI, SE, DT, AC); NumCompletelyUnrolled += CompletelyUnroll; ++NumUnrolled; Index: lib/Transforms/Utils/LoopUnrollAndJam.cpp =================================================================== --- /dev/null +++ lib/Transforms/Utils/LoopUnrollAndJam.cpp @@ -0,0 +1,876 @@ +//===-- LoopUnrollAndJam.cpp - Loop unrolling utilities -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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/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/Local.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" + +STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed"); +STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed"); + +static cl::opt AllowUnrollAndJam("unroll-and-jam", cl::init(true), + cl::Hidden, + cl::desc("Allow Unroll And Jam")); + +static cl::opt +AlwaysUnrollAndJam("always-unroll-and-jam", cl::init(false), cl::Hidden, + cl::desc("Always Unroll And Jam whenever Safe")); + +extern cl::opt UnrollVerifyDomtree; + +bool containsBB(std::vector &V, BasicBlock *BB) { + return std::find(V.begin(), V.end(), BB) != V.end(); +} + +// Partition blocks in an outer/inner loop pair into blocks before and after +// the loop +bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop, + std::vector &ForeBlocks, + std::vector &SubLoopBlocks, + std::vector &AftBlocks, + DominatorTree *DT) { + BasicBlock *SubLoopLatch = SubLoop->getLoopLatch(); + SubLoopBlocks = SubLoop->getBlocks(); + + for (BasicBlock *BB : L->blocks()) { + if (!SubLoop->contains(BB)) { + if (DT->dominates(SubLoopLatch, BB)) + AftBlocks.push_back(BB); + else + ForeBlocks.push_back(BB); + } + } + + // Check that all blocks in ForeBlocks together dominate the subloop + // TODOD: This might ideally be done better with a dominator/postdominators. + BasicBlock *SubLoopPreHeader = SubLoop->getLoopPreheader(); + for (BasicBlock *BB : ForeBlocks) { + if (BB == SubLoopPreHeader) + continue; + TerminatorInst *TI = BB->getTerminator(); + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + if (!containsBB(ForeBlocks, TI->getSuccessor(i))) + return false; + } + + return true; +} + +// Move the phi operands of Header from Latch out of AftBlocks to InsertLoc. +void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header, BasicBlock *Latch, + Instruction *InsertLoc, + std::vector &AftBlocks) { + // We need to ensure we move the instructions in the correct order, + // starting with the earliest required instruction and going moving + // forward. + std::vector Worklist; + std::vector Visited; + for (auto &Phi : Header->phis()) { + Value *V = Phi.getIncomingValueForBlock(Latch); + if (Instruction *I = dyn_cast(V)) + Worklist.push_back(I); + } + + while (!Worklist.empty()) { + Instruction *I = Worklist.back(); + Worklist.pop_back(); + if (!containsBB(AftBlocks, I->getParent())) + continue; + + Visited.push_back(I); + for (auto &U : I->operands()) + if (Instruction *II = dyn_cast(U)) + Worklist.push_back(II); + } + + // 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 blocks are essentially outer unrolled and then fused ("jammed") + together into a single inner loop. This can increase speed when there are + loads in SubLoop that are invariant to i, as they become shared between the + loops. + + We do this by spliting the blocks in the loop into Fore, Subloop and Aft. + Normal Unroll code is used to copy each of these sets of blocks and the + results are combined together into the final form above. + + isSafeTounrollAndFuse should be used prior to calling this to make sure the + unrolling will be valid. isProfitable is also advisable. + */ +LoopUnrollResult +llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, + unsigned TripMultiple, bool UnrollRemainder, + LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, + AssumptionCache *AC, OptimizationRemarkEmitter *ORE) { + + // When we enter here we should already have checked isSafeToUnrollAndJam + 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) { + DEBUG(dbgs() << "Won't unroll; 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, false /*AllowExpensiveTripCount*/, + /*UseEpilogRemainder*/ true, + UnrollRemainder, LI, SE, DT, AC, true)) { + DEBUG(dbgs() << "Wont 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) { + 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); + }; + + DEBUG(dbgs() << "UNROLL AND JAMMING loop %" << Header->getName() << " by " + << Count); + if (TripMultiple != 1) { + DEBUG(dbgs() << " with " << TripMultiple << " trips per branch"); + ORE->emit([&]() { + return DiagBuilder() << " with " << NV("TripMultiple", TripMultiple) + << " trips per branch"; + }); + } else { + DEBUG(dbgs() << " with run-time trip count"); + ORE->emit([&]() { return DiagBuilder() << " with run-time trip count"; }); + } + DEBUG(dbgs() << "!\n"); + } + + BasicBlock *Preheader = L->getLoopPreheader(); + BasicBlock *LatchBlock = L->getLoopLatch(); + BranchInst *BI = dyn_cast(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 + std::vector SubLoopBlocks; + std::vector ForeBlocks; + std::vector 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 ForeBlocksFirst; + std::vector ForeBlocksLast; + std::vector SubLoopBlocksFirst; + std::vector SubLoopBlocksLast; + std::vector AftBlocksFirst; + std::vector 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(&I)) + if (const DILocation *DIL = I.getDebugLoc()) + I.setDebugLoc(DIL->cloneWithDuplicationFactor(Count)); + + // Copy all blocks + for (unsigned It = 1; It != Count; ++It) { + std::vector NewBlocks; + // Maps Blocks[It] -> Blocks[It-1] + DenseMap 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 (containsBB(ForeBlocks, *BB)) { + L->addBasicBlockToLoop(New, *LI); + + if (*BB == ForeBlocksFirst[0]) + ForeBlocksFirst.push_back(New); + if (*BB == ForeBlocksLast[0]) + ForeBlocksLast.push_back(New); + } else if (containsBB(SubLoopBlocks, *BB)) { + SubLoop->addBasicBlockToLoop(New, *LI); + + if (*BB == SubLoopBlocksFirst[0]) + SubLoopBlocksFirst.push_back(New); + if (*BB == SubLoopBlocksLast[0]) + SubLoopBlocksLast.push_back(New); + } else if (containsBB(AftBlocks, *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(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(OriginalBBIDom)]); + DT->addNewBlock( + New, cast(LastValueMap[cast(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(&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(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(ForeBlocksLast.back()->getTerminator()); + BasicBlock *Dest = SubLoopBlocksFirst[0]; + ForeTerm->setSuccessor(0, Dest); + + if (CompletelyUnroll) { + while (PHINode *Phi = dyn_cast(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(ForeBlocksLast[It - 1]->getTerminator()); + BasicBlock *Dest = ForeBlocksFirst[It]; + ForeTerm->setSuccessor(0, Dest); + } + + // Subloop successors and phis + BranchInst *SubTerm = + cast(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(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 + if (CompletelyUnroll) { + BranchInst *Term = cast(AftBlocksLast.back()->getTerminator()); + BranchInst::Create(LoopExit, Term); + Term->eraseFromParent(); + } else { + BranchInst *Term = cast(AftBlocksLast.back()->getTerminator()); + 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(AftBlocksLast[It - 1]->getTerminator()); + BranchInst::Create(AftBlocksFirst[It], AftTerm); + AftTerm->eraseFromParent(); + + updatePHIBlocks(AftBlocksFirst[It], SubLoopBlocksLast[It], + SubLoopBlocksLast.back()); + movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]); + } + + // Dominator Tree. Remove the old links between Fore, Sub and Aft, adding the + // new ones required. + if (Count != 1) { + SmallVector 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]); + DT->applyUpdates(DTUpdates); + } + + if (UnrollVerifyDomtree) + DT->verifyDomTree(); + + // Merge adjacent basic blocks, if possible. + SmallPtrSet MergeBlocks; + MergeBlocks.insert(ForeBlocksLast.begin(), ForeBlocksLast.end()); + MergeBlocks.insert(SubLoopBlocksLast.begin(), SubLoopBlocksLast.end()); + MergeBlocks.insert(AftBlocksLast.begin(), AftBlocksLast.end()); + SmallPtrSet ForgottenLoops; + while (!MergeBlocks.empty()) { + BasicBlock *BB = *MergeBlocks.begin(); + BranchInst *Term = dyn_cast(BB->getTerminator()); + if (Term && Term->isUnconditional() && L->contains(Term->getSuccessor(0))) { + BasicBlock *Dest = Term->getSuccessor(0); + if (BasicBlock *Fold = + foldBlockIntoPredecessor(Dest, LI, SE, ForgottenLoops, DT)) { + // Don't remove BB and add Fold as they are the same BB + assert(Fold == BB); + MergeBlocks.erase(Dest); + } else + MergeBlocks.erase(BB); + } else + MergeBlocks.erase(BB); + } + + // 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; + + Loop *OuterL = L->getParentLoop(); + // Update LoopInfo if the loop is completely removed. + if (CompletelyUnroll) + LI->erase(L); + + // We shouldnt have done anything to break loop simplify form or LCSSA. + Loop *OutestLoop = OuterL ? OuterL : (!CompletelyUnroll ? L : SubLoop); + assert(OutestLoop->isRecursivelyLCSSAForm(*DT, *LI)); + if (!CompletelyUnroll) + assert(L->isLoopSimplifyForm()); + assert(SubLoop->isLoopSimplifyForm()); + DT->verifyDomTree(); + + return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled + : LoopUnrollResult::PartiallyUnrolled; +} + +static bool getLoadsAndStores(std::vector &Blocks, + SmallVector &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(&I)) { + if (!Ld->isSimple()) + return false; + MemInstr.push_back(&I); + } else if (auto *St = dyn_cast(&I)) { + if (!St->isSimple()) + return false; + MemInstr.push_back(&I); + } else if (I.mayReadOrWriteMemory()) { + return false; + } + } + } + return true; +} + +static bool checkDependencies(SmallVector &Earlier, + SmallVector &Later, + unsigned LoopDepth, 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(I); + Instruction *Dst = cast(J); + if (Src == Dst) + continue; + // Ignore Input dependencies. + if (isa(Src) && isa(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). + // 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."); + unsigned Levels = D->getLevels(); + + if (D->isConfused()) + return false; + for (unsigned II = LoopDepth; II <= Levels; ++II) { + const SCEV *Distance = D->getDistance(II); + const SCEVConstant *SCEVConst = + dyn_cast_or_null(Distance); + if (SCEVConst) { + const ConstantInt *CI = SCEVConst->getValue(); + if (CI->isNegative()) + return false; + } else + return false; + } + } + } + } + return true; +} + +static bool checkDependencies(Loop *L, std::vector &ForeBlocks, + std::vector &SubLoopBlocks, + std::vector &AftBlocks, + DependenceInfo &DI) { + // TODOD This needs someone who knows what they are talking about to take a look. + // Get all loads/store pairs for each blocks + SmallVector ForeMemInstr; + SmallVector SubLoopMemInstr; + SmallVector 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, DI) && + checkDependencies(ForeMemInstr, AftMemInstr, LoopDepth, DI) && + checkDependencies(SubLoopMemInstr, AftMemInstr, LoopDepth, DI) && + checkDependencies(SubLoopMemInstr, SubLoopMemInstr, LoopDepth + 1, 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 isProfitableToUnrollAndJam. + + 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 S1 S1 A1 F2 S2 S2 S2 A2. + It needs to be safe to tranform this to F1 F2 S1 S2 S1 S2 S1 S2 A1 A2. + + There are then a number of checks along the lines of no calls, no + exceptions, inner loop IV is consistent, etc. + */ + + if (!AllowUnrollAndJam) + return false; + if (!L->isLoopSimplifyForm() || L->getSubLoops().size() != 1) + return false; + Loop *SubLoop = L->getSubLoops()[0]; + if (!SubLoop->isLoopSimplifyForm()) + return false; + + BasicBlock *PreHeader = L->getLoopPreheader(); + 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()) + return false; + + // Split blocks into Fore/SubLoop/Aft based on dominators + std::vector SubLoopBlocks; + std::vector ForeBlocks; + std::vector AftBlocks; + if (!partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks, + AftBlocks, &DT)) + 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) + return false; + + // Check outer loop IV is easily calcable + const SCEV *BECountSC = SE.getExitCount(L, Latch); + if (isa(BECountSC) || + !BECountSC->getType()->isIntegerTy()) + return false; + // Add 1 since the backedge count doesn't include the first loop iteration. + const SCEV *TripCountSC = + SE.getAddExpr(BECountSC, SE.getConstant(BECountSC->getType(), 1)); + if (isa(TripCountSC)) + return false; + BranchInst *PreHeaderBR = cast(PreHeader->getTerminator()); + const DataLayout &DL = Header->getModule()->getDataLayout(); + SCEVExpander Expander(SE, DL, "loop-unroll"); + if (Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR)) + return false; + + // Check inner loop IV is consistent between all iterations + const SCEV *SubLoopBECountSC = SE.getExitCount(SubLoop, SubLoopLatch); + if (isa(SubLoopBECountSC) || + !SubLoopBECountSC->getType()->isIntegerTy()) + return false; + ScalarEvolution::LoopDisposition LD = + SE.getLoopDisposition(SubLoopBECountSC, L); + if (LD != ScalarEvolution::LoopInvariant) + return false; + + // Check the loop safety info for exceptions. + LoopSafetyInfo LSI; + computeLoopSafetyInfo(&LSI, L); + if (LSI.MayThrow) + return false; + + // We've ruled out the easy stuff, and 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 + SmallVector Worklist; + SmallPtrSet Visited; + for (auto &Phi : Header->phis()) { + Value *V = Phi.getIncomingValueForBlock(Latch); + if (Instruction *I = dyn_cast(V)) + Worklist.push_back(I); + } + while (!Worklist.empty()) { + Instruction *I = Worklist.back(); + Worklist.pop_back(); + if (Visited.insert(I).second) { + if (SubLoop->contains(I->getParent())) + return false; + if (containsBB(AftBlocks, I->getParent())) { + // If we hit a phi node in afts we know we are done (probably LCSSA) + if (isa(I)) + return false; + if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory()) + return false; + for (auto &U : I->operands()) + if (Instruction *II = dyn_cast(U)) + Worklist.push_back(II); + } + } + } + + // 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)) + return false; + + return true; +} + +/* + Attempts to work out of it will be profitable to unroll-and-jam, as opposed to + normal unrolling. Also calls isSafeToUnrollAndJam to ensure we can unroll and + jam. Returns true if it is not expected to be profitable. May alter UP.Count. + */ +bool llvm::isProfitableToUnrollAndJam( + Loop *L, const TargetTransformInfo &TTI, ScalarEvolution &SE, + DominatorTree &DT, DependenceInfo &DI, + TargetTransformInfo::UnrollingPreferences &UP) { + if (AlwaysUnrollAndJam) + return isSafeToUnrollAndJam(L, SE, DT, DI); + + // First up we do some very quick checks to see if the structure is anything + // like what we want. Only unroll and jam on the outer two most levels + if (L->getSubLoops().size() != 1) + return false; + Loop *SubLoop = L->getSubLoops()[0]; + if (!SubLoop->getSubLoops().empty()) + return false; + // Also limit to single basic block inner loops. As a proxy for simple + // subloops + if (SubLoop->getBlocks().size() != 1) + return false; + + // Check that unroll and jam is safe + if (!isSafeToUnrollAndJam(L, SE, DT, DI)) + return false; + + // Check if the inner loop count is constant. In this case we should just + // unroll the inner loop. + // FIXME: this isn't always true when the inner loop is not completely + // unrolled + const SCEV *BECount = SE.getExitCount(SubLoop, SubLoop->getLoopLatch()); + if (isa(BECount)) + return false; + + // We ideally want a load that after unrollandjam is shared between inner + // loop iterations. I.e is invariant to the outer loop. + // We also measure the size of the inner loop and ensure it's below some + // threshold. + int numInvariant = 0; + unsigned Cost = 0; + unsigned Threshold = UP.UnrollAndJamThreshold; + for (BasicBlock *BB : SubLoop->getBlocks()) { + for (Instruction &I : *BB) { + if (auto *Ld = dyn_cast(&I)) { + Value *V = Ld->getPointerOperand(); + const SCEV *LSCEV = SE.getSCEVAtScope(V, L); + if (SE.isLoopInvariant(LSCEV, L)) + numInvariant++; + } + + SmallVector Operands(I.value_op_begin(), + I.value_op_end()); + Cost += TTI.getUserCost(&I, Operands); + if (Cost >= Threshold) + return false; + } + } + if (numInvariant == 0) + return false; + + // Very (very) rough measure of register pressure. + while (Cost * UP.Count > Threshold) + UP.Count--; + if (UP.Count <= 1) + return false; + + // FIXME: May be useful in more general situations. + return true; +} Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -23,6 +23,7 @@ #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Module.h" @@ -1646,3 +1647,40 @@ VecOp->andIRFlags(V); } } + +/// Computes loop safety information, checks loop body & header +/// for the possibility of may throw exception. +/// +void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) { + assert(CurLoop != nullptr && "CurLoop cant be null"); + BasicBlock *Header = CurLoop->getHeader(); + // Setting default safety values. + SafetyInfo->MayThrow = false; + SafetyInfo->HeaderMayThrow = false; + // Iterate over header and compute safety info. + for (BasicBlock::iterator I = Header->begin(), E = Header->end(); + (I != E) && !SafetyInfo->HeaderMayThrow; ++I) + SafetyInfo->HeaderMayThrow |= + !isGuaranteedToTransferExecutionToSuccessor(&*I); + + SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow; + // Iterate over loop instructions and compute safety info. + // Skip header as it has been computed and stored in HeaderMayThrow. + // The first block in loopinfo.Blocks is guaranteed to be the header. + assert(Header == *CurLoop->getBlocks().begin() && + "First block must be header"); + for (Loop::block_iterator BB = std::next(CurLoop->block_begin()), + BBE = CurLoop->block_end(); + (BB != BBE) && !SafetyInfo->MayThrow; ++BB) + for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); + (I != E) && !SafetyInfo->MayThrow; ++I) + SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I); + + // Compute funclet colors if we might sink/hoist in a function with a funclet + // personality routine. + Function *Fn = CurLoop->getHeader()->getParent(); + if (Fn->hasPersonalityFn()) + if (Constant *PersonalityFn = Fn->getPersonalityFn()) + if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn))) + SafetyInfo->BlockColors = colorEHFunclets(*Fn); +} Index: test/Other/new-pm-defaults.ll =================================================================== --- test/Other/new-pm-defaults.ll +++ test/Other/new-pm-defaults.ll @@ -217,6 +217,7 @@ ; CHECK-O-NEXT: Running pass: SLPVectorizerPass ; CHECK-O-NEXT: Running pass: InstCombinePass ; CHECK-O-NEXT: Running pass: LoopUnrollPass +; CHECK-O-NEXT: Running analysis: DependenceAnalysis ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy ; CHECK-O-NEXT: Running pass: InstCombinePass ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}OptimizationRemarkEmitterAnalysis Index: test/Other/new-pm-thinlto-defaults.ll =================================================================== --- test/Other/new-pm-thinlto-defaults.ll +++ test/Other/new-pm-thinlto-defaults.ll @@ -205,6 +205,7 @@ ; CHECK-POSTLINK-O-NEXT: Running pass: SLPVectorizerPass ; CHECK-POSTLINK-O-NEXT: Running pass: InstCombinePass ; CHECK-POSTLINK-O-NEXT: Running pass: LoopUnrollPass +; CHECK-POSTLINK-O-NEXT: Running analysis: DependenceAnalysis ; CHECK-POSTLINK-O-NEXT: Running analysis: OuterAnalysisManagerProxy ; CHECK-POSTLINK-O-NEXT: Running pass: InstCombinePass ; CHECK-POSTLINK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}OptimizationRemarkEmitterAnalysis Index: test/Other/pass-pipelines.ll =================================================================== --- test/Other/pass-pipelines.ll +++ test/Other/pass-pipelines.ll @@ -45,6 +45,8 @@ ; CHECK-O2: Combine redundant instructions ; CHECK-O2-NOT: Manager ; CHECK-O2: Loop Pass Manager +; FIXME: DA is adding another loop pass manager. Fix this. +; CHECK-O2: Loop Pass Manager ; CHECK-O2-NOT: Manager ; FIXME: It isn't clear that we need yet another loop pass pipeline ; and run of LICM here. Index: test/Transforms/LoopUnroll/unroll-and-jam-disabled.ll =================================================================== --- /dev/null +++ test/Transforms/LoopUnroll/unroll-and-jam-disabled.ll @@ -0,0 +1,728 @@ +; RUN: opt -loop-unroll -unroll-and-jam -always-unroll-and-jam -pass-remarks=loop-unroll < %s -S 2>&1 | FileCheck %s + +target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" +target triple = "thumbv8m.main-arm-none-eabi" + +;; Common check for all tests. None should be unroll and jammed +; CHECK-NOT: remark: {{.*}} unroll and jammed + + +; CHECK-LABEL: disabled1 +; Tests for(i) { sum = A[i]; for(j) sum += B[j]; A[i+1] = sum; } +; A[i] to A[i+1] dependency should block unrollandjam +define void @disabled1(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp127 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp127, %cmp + br i1 %or.cond, label %for.preheader, label %return + +for.preheader: + br label %for.outer + +for.outer: + %i.029 = phi i32 [ %add10, %for.latch ], [ 0, %for.preheader ] + %b.028 = phi i32 [ %inc8, %for.latch ], [ 1, %for.preheader ] + %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.029 + %0 = load i32, i32* %arrayidx, align 4, !tbaa !5 + br label %for.inner + +for.inner: + %j.026 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] + %sum1.025 = phi i32 [ %0, %for.outer ], [ %add, %for.inner ] + %arrayidx6 = getelementptr inbounds i32, i32* %B, i32 %j.026 + %1 = load i32, i32* %arrayidx6, align 4, !tbaa !5 + %add = add i32 %1, %sum1.025 + %inc = add nuw i32 %j.026, 1 + %exitcond = icmp eq i32 %inc, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %arrayidx7 = getelementptr inbounds i32, i32* %A, i32 %b.028 + store i32 %add, i32* %arrayidx7, align 4, !tbaa !5 + %inc8 = add nuw nsw i32 %b.028, 1 + %add10 = add nuw nsw i32 %i.029, 1 + %exitcond30 = icmp eq i32 %add10, %I + br i1 %exitcond30, label %return, label %for.outer + +return: + ret void +} + + +; CHECK-LABEL: disabled2 +; Tests an incompatible block layout (for.outer jumps past for.inner) +; FIXME: Make this work +define void @disabled2(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp131 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp131, %cmp + br i1 %or.cond, label %for.preheader, label %for.end14 + +for.preheader: + br label %for.outer + +for.outer: + %i.032 = phi i32 [ %add13, %for.latch ], [ 0, %for.preheader ] + %arrayidx = getelementptr inbounds i32, i32* %B, i32 %i.032 + %0 = load i32, i32* %arrayidx, align 4, !tbaa !5 + %tobool = icmp eq i32 %0, 0 + br i1 %tobool, label %for.latch, label %for.inner + +for.inner: + %j.030 = phi i32 [ %inc, %for.inner ], [ 0, %for.outer ] + %sum1.029 = phi i32 [ %sum1.1, %for.inner ], [ 0, %for.outer ] + %arrayidx6 = getelementptr inbounds i32, i32* %B, i32 %j.030 + %1 = load i32, i32* %arrayidx6, align 4, !tbaa !5 + %tobool7 = icmp eq i32 %1, 0 + %sub = add i32 %sum1.029, 10 + %add = sub i32 %sub, %1 + %sum1.1 = select i1 %tobool7, i32 %sum1.029, i32 %add + %inc = add nuw i32 %j.030, 1 + %exitcond = icmp eq i32 %inc, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %sum1.1.lcssa = phi i32 [ 0, %for.outer ], [ %sum1.1, %for.inner ] + %arrayidx11 = getelementptr inbounds i32, i32* %A, i32 %i.032 + store i32 %sum1.1.lcssa, i32* %arrayidx11, align 4, !tbaa !5 + %add13 = add nuw i32 %i.032, 1 + %exitcond33 = icmp eq i32 %add13, %I + br i1 %exitcond33, label %for.end14, label %for.outer + +for.end14: + ret void +} + + + +; CHECK-LABEL: disabled3 +; Tests loop carry dependencies in an array S +define void @disabled3(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %S = alloca [4 x i32], align 4 + %cmp = icmp eq i32 %J, 0 + br i1 %cmp, label %return, label %if.end + +if.end: + %0 = bitcast [4 x i32]* %S to i8* + call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull %0) #2 + %cmp128 = icmp eq i32 %I, 0 + br i1 %cmp128, label %for.cond.cleanup, label %for.preheader + +for.preheader: + %arrayidx9 = getelementptr inbounds [4 x i32], [4 x i32]* %S, i32 0, i32 0 + br label %for.outer + +for.cond.cleanup: + call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull %0) #2 + br label %return + +for.outer: + %i.029 = phi i32 [ 0, %for.preheader ], [ %add12, %for.latch ] + br label %for.inner + +for.inner: + %j.027 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] + %arrayidx = getelementptr inbounds i32, i32* %B, i32 %j.027 + %l2 = load i32, i32* %arrayidx, align 4, !tbaa !5 + %add = add i32 %j.027, %i.029 + %rem = urem i32 %add, %J + %arrayidx6 = getelementptr inbounds i32, i32* %B, i32 %rem + %l3 = load i32, i32* %arrayidx6, align 4, !tbaa !5 + %mul = mul i32 %l3, %l2 + %rem7 = urem i32 %j.027, 3 + %arrayidx8 = getelementptr inbounds [4 x i32], [4 x i32]* %S, i32 0, i32 %rem7 + store i32 %mul, i32* %arrayidx8, align 4, !tbaa !5 + %inc = add nuw i32 %j.027, 1 + %exitcond = icmp eq i32 %inc, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %l1 = load i32, i32* %arrayidx9, align 4, !tbaa !5 + %arrayidx10 = getelementptr inbounds i32, i32* %A, i32 %i.029 + store i32 %l1, i32* %arrayidx10, align 4, !tbaa !5 + %add12 = add nuw i32 %i.029, 1 + %exitcond31 = icmp eq i32 %add12, %I + br i1 %exitcond31, label %for.cond.cleanup, label %for.outer + +return: + ret void +} + + +; CHECK-LABEL: disabled4 +; Inner looop induction variable in not consistent +; ie for(i = 0..n) for (j = 0..i) sum+=B[j] +define void @disabled4(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ugt i32 %I, 1 + %or.cond = and i1 %cmp122, %cmp + br i1 %or.cond, label %for.preheader, label %for.end9 + +for.preheader: + br label %for.outer + +for.outer: + %indvars.iv = phi i32 [ %indvars.iv.next, %for.latch ], [ 1, %for.preheader ] + br label %for.inner + +for.inner: + %j.021 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] + %sum1.020 = phi i32 [ 0, %for.outer ], [ %add, %for.inner ] + %arrayidx = getelementptr inbounds i32, i32* %B, i32 %j.021 + %0 = load i32, i32* %arrayidx, align 4, !tbaa !5 + %add = add i32 %0, %sum1.020 + %inc = add nuw i32 %j.021, 1 + %exitcond = icmp eq i32 %inc, %indvars.iv + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %arrayidx6 = getelementptr inbounds i32, i32* %A, i32 %indvars.iv + store i32 %add, i32* %arrayidx6, align 4, !tbaa !5 + %indvars.iv.next = add nuw i32 %indvars.iv, 1 + %exitcond24 = icmp eq i32 %indvars.iv.next, %I + br i1 %exitcond24, label %for.end9, label %for.outer + +for.end9: + ret void +} + + +; CHECK-LABEL: disabled5 +; Test odd uses of phi nodes where the outer IV cannot be moved into Fore as it hits a PHI +@f = hidden local_unnamed_addr global i32 0, align 4 +define i32 @disabled5() local_unnamed_addr #0 { +entry: + %f.promoted10 = load i32, i32* @f, align 4, !tbaa !5 + br label %for.outer + +for.outer: + %0 = phi i32 [ %f.promoted10, %entry ], [ 2, %for.latch ] + %d.018 = phi i16 [ 0, %entry ], [ %odd.lcssa, %for.latch ] + %inc5.sink9 = phi i32 [ 2, %entry ], [ %inc5, %for.latch ] + br label %for.inner + +for.inner: + %1 = phi i32 [ %0, %for.outer ], [ 2, %for.inner ] + %inc.sink8 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] + %inc = add nuw nsw i32 %inc.sink8, 1 + %exitcond = icmp ne i32 %inc, 7 + br i1 %exitcond, label %for.inner, label %for.latch + +for.latch: + %.lcssa = phi i32 [ %1, %for.inner ] + %odd.lcssa = phi i16 [ 1, %for.inner ] + %inc5 = add nuw nsw i32 %inc5.sink9, 1 + %exitcond11 = icmp ne i32 %inc5, 7 + br i1 %exitcond11, label %for.outer, label %for.end + +for.end: + %.lcssa.lcssa = phi i32 [ %.lcssa, %for.latch ] + %inc.lcssa.lcssa = phi i32 [ 7, %for.latch ] + ret i32 0 +} + + +; CHECK-LABEL: disabled6 +; There is a dependency in here, between @d and %0 (=@f) +@d6 = hidden global i16 5, align 2 +@f6 = hidden local_unnamed_addr global i16* @d6, align 4 +define i32 @disabled6() local_unnamed_addr #1 { +entry: + store i16 1, i16* @d6, align 2 + %0 = load i16*, i16** @f6, align 4 + br label %for.body.i + +for.body.i: + %inc8.sink14.i = phi i16 [ 1, %entry ], [ %inc8.i, %for.cond.cleanup.i ] + %1 = load i16, i16* %0, align 2 + br label %for.body6.i + +for.cond.cleanup.i: + %inc8.i = add nuw nsw i16 %inc8.sink14.i, 1 + store i16 %inc8.i, i16* @d6, align 2 + %cmp.i = icmp ult i16 %inc8.i, 6 + br i1 %cmp.i, label %for.body.i, label %test.exit + +for.body6.i: + %c.013.i = phi i32 [ 0, %for.body.i ], [ %inc.i, %for.body6.i ] + %inc.i = add nuw nsw i32 %c.013.i, 1 + %exitcond.i = icmp eq i32 %inc.i, 7 + br i1 %exitcond.i, label %for.cond.cleanup.i, label %for.body6.i + +test.exit: + %conv2.i = sext i16 %1 to i32 + ret i32 0 +} + + + +; CHECK-LABEL: disabled7 +; Has negative output dependency +define void @disabled7(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp127 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp127, %cmp + br i1 %or.cond, label %for.body.preheader, label %for.end12 + +for.body.preheader: + br label %for.body + +for.body: + %i.028 = phi i32 [ %add11, %for.cond3.for.cond.cleanup5_crit_edge ], [ 0, %for.body.preheader ] + %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.028 + store i32 0, i32* %arrayidx, align 4, !tbaa !5 + %sub = add i32 %i.028, -1 + %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %sub + store i32 2, i32* %arrayidx2, align 4, !tbaa !5 + br label %for.body6 + +for.cond3.for.cond.cleanup5_crit_edge: + store i32 %add, i32* %arrayidx, align 4, !tbaa !5 + %add11 = add nuw i32 %i.028, 1 + %exitcond29 = icmp eq i32 %add11, %I + br i1 %exitcond29, label %for.end12, label %for.body + +for.body6: + %0 = phi i32 [ 0, %for.body ], [ %add, %for.body6 ] + %j.026 = phi i32 [ 0, %for.body ], [ %add9, %for.body6 ] + %arrayidx7 = getelementptr inbounds i32, i32* %B, i32 %j.026 + %1 = load i32, i32* %arrayidx7, align 4, !tbaa !5 + %add = add i32 %1, %0 + %add9 = add nuw i32 %j.026, 1 + %exitcond = icmp eq i32 %add9, %J + br i1 %exitcond, label %for.cond3.for.cond.cleanup5_crit_edge, label %for.body6 + +for.end12: + ret void +} + + +; CHECK-LABEL: disabled8 +; Same as above with an extra outer loop nest +define void @disabled8(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp eq i32 %J, 0 + %cmp335 = icmp eq i32 %I, 0 + %or.cond = or i1 %cmp, %cmp335 + br i1 %or.cond, label %for.end18, label %for.body.preheader + +for.body.preheader: + br label %for.body + +for.body: + %x.037 = phi i32 [ %inc, %for.cond.cleanup4 ], [ 0, %for.body.preheader ] + br label %for.outer + +for.cond.cleanup4: + %inc = add nuw nsw i32 %x.037, 1 + %exitcond40 = icmp eq i32 %inc, 5 + br i1 %exitcond40, label %for.end18, label %for.body + +for.outer: + %i.036 = phi i32 [ %add15, %for.latch ], [ 0, %for.body ] + %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.036 + store i32 0, i32* %arrayidx, align 4, !tbaa !5 + %sub = add i32 %i.036, -1 + %arrayidx6 = getelementptr inbounds i32, i32* %A, i32 %sub + store i32 2, i32* %arrayidx6, align 4, !tbaa !5 + br label %for.inner + +for.latch: + store i32 %add, i32* %arrayidx, align 4, !tbaa !5 + %add15 = add nuw i32 %i.036, 1 + %exitcond38 = icmp eq i32 %add15, %I + br i1 %exitcond38, label %for.cond.cleanup4, label %for.outer + +for.inner: + %0 = phi i32 [ 0, %for.outer ], [ %add, %for.inner ] + %j.034 = phi i32 [ 0, %for.outer ], [ %add13, %for.inner ] + %arrayidx11 = getelementptr inbounds i32, i32* %B, i32 %j.034 + %1 = load i32, i32* %arrayidx11, align 4, !tbaa !5 + %add = add i32 %1, %0 + %add13 = add nuw i32 %j.034, 1 + %exitcond = icmp eq i32 %add13, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.end18: + ret void +} + + +; CHECK-LABEL: disabled9 +; Can't prove alias between A and B +define void @disabled9(i32 %I, i32 %J, i32* nocapture %A, i32* nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: disable10 +; Simple call +declare void @f10(i32, i32) local_unnamed_addr #0 +define void @disable10(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + tail call void @f10(i32 %i.us, i32 %j.us) nounwind + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: disable11 +; volatile +define void @disable11(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load volatile i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: disable12 +; Multiple aft blocks +define void @disable12(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch3 ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %cmpl = icmp eq i32 %add.us.lcssa, 10 + br i1 %cmpl, label %for.latch2, label %for.latch3 + +for.latch2: + br label %for.latch3 + +for.latch3: + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: disable13 +; Two subloops +define void @disable13(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.inner2, label %for.inner + +for.inner2: + %j.us2 = phi i32 [ 0, %for.inner ], [ %inc.us2, %for.inner2 ] + %sum1.us2 = phi i32 [ 0, %for.inner ], [ %add.us2, %for.inner2 ] + %arrayidx.us2 = getelementptr inbounds i32, i32* %B, i32 %j.us2 + %l0 = load i32, i32* %arrayidx.us2, align 4, !tbaa !5 + %add.us2 = add i32 %l0, %sum1.us2 + %inc.us2 = add nuw i32 %j.us2, 1 + %exitcond2 = icmp eq i32 %inc.us2, %J + br i1 %exitcond2, label %for.latch, label %for.inner2 + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner2 ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: disable14 +; Multiple exits blocks +define void @disable14(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + %add8.us = add nuw i32 %i.us, 1 + %exitcond23 = icmp eq i32 %add8.us, %I + br i1 %exitcond23, label %for.end.loopexit, label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: disable15 +; Latch != exit +define void @disable15(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + br label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: disable16 +; Latch != exit +define void @disable16(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + %otherphi = phi i32 [ %other, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + %loadarr = getelementptr inbounds i32, i32* %A, i32 %i.us + %load = load i32, i32* %arrayidx6.us, align 4, !tbaa !5 + %other = add i32 %otherphi, %load + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + + +; Function Attrs: argmemonly nounwind +declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #1 + +; Function Attrs: argmemonly nounwind +declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #1 + +attributes #0 = { noinline norecurse nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "denormal-fp-math"="preserve-sign" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="true" "no-jump-tables"="false" "no-nans-fp-math"="true" "no-signed-zeros-fp-math"="true" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="cortex-m33" "target-features"="+d16,+dsp,+fp-armv8,+fp-only-sp,+hwdiv,+thumb-mode,-crc,-dotprod,-hwdiv-arm,-ras" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { argmemonly nounwind } + +!5 = !{!6, !6, i64 0} +!6 = !{!"omnipotent char", !7, i64 0} +!7 = !{!"Simple C/C++ TBAA"} Index: test/Transforms/LoopUnroll/unroll-and-jam-unprofitable.ll =================================================================== --- /dev/null +++ test/Transforms/LoopUnroll/unroll-and-jam-unprofitable.ll @@ -0,0 +1,223 @@ +; RUN: opt -loop-unroll -unroll-and-jam -pass-remarks=loop-unroll < %s -S 2>&1 | FileCheck %s + +target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" +target triple = "thumbv8m.main-arm-none-eabi" + +;; Common check for all tests. None should be unroll and jammed due to profitability +; CHECK-NOT: remark: {{.*}} unroll and jammed + + +; CHECK-LABEL: unprof1 +; Multiple inner loop blocks +define void @unprof1(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner2 ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner2 ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us +br label %for.inner2 + +for.inner2: + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner2 ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: unprof2 +; Constant inner loop count +define void @unprof2(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, 10 + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: unprof3 +; Complex inner loop +define void @unprof3(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %add.us0 = add i32 %0, %sum1.us + %add.us1 = add i32 %0, %sum1.us + %add.us2 = add i32 %0, %sum1.us + %add.us3 = add i32 %0, %sum1.us + %add.us4 = add i32 %0, %sum1.us + %add.us5 = add i32 %0, %sum1.us + %add.us6 = add i32 %0, %sum1.us + %add.us7 = add i32 %0, %sum1.us + %add.us8 = add i32 %0, %sum1.us + %add.us9 = add i32 %0, %sum1.us + %add.us10 = add i32 %0, %sum1.us + %add.us11 = add i32 %0, %sum1.us + %add.us12 = add i32 %0, %sum1.us + %add.us13 = add i32 %0, %sum1.us + %add.us14 = add i32 %0, %sum1.us + %add.us15 = add i32 %0, %sum1.us + %add.us16 = add i32 %0, %sum1.us + %add.us17 = add i32 %0, %sum1.us + %add.us18 = add i32 %0, %sum1.us + %add.us19 = add i32 %0, %sum1.us + %add.us20 = add i32 %0, %sum1.us + %add.us21 = add i32 %0, %sum1.us + %add.us22 = add i32 %0, %sum1.us + %add.us23 = add i32 %0, %sum1.us + %add.us24 = add i32 %0, %sum1.us + %add.us25 = add i32 %0, %sum1.us + %add.us26 = add i32 %0, %sum1.us + %add.us27 = add i32 %0, %sum1.us + %add.us28 = add i32 %0, %sum1.us + %add.us29 = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; CHECK-LABEL: unprof4 +; No loop invariant loads +define void @unprof4(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %j2 = add i32 %j.us, %i.us + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j2 + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + +; Function Attrs: argmemonly nounwind +declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #1 + +; Function Attrs: argmemonly nounwind +declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #1 + +attributes #0 = { noinline norecurse nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "denormal-fp-math"="preserve-sign" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="true" "no-jump-tables"="false" "no-nans-fp-math"="true" "no-signed-zeros-fp-math"="true" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="cortex-m33" "target-features"="+d16,+dsp,+fp-armv8,+fp-only-sp,+hwdiv,+thumb-mode,-crc,-dotprod,-hwdiv-arm,-ras" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { argmemonly nounwind } + +!5 = !{!6, !6, i64 0} +!6 = !{!"omnipotent char", !7, i64 0} +!7 = !{!"Simple C/C++ TBAA"} Index: test/Transforms/LoopUnroll/unroll-and-jam.ll =================================================================== --- /dev/null +++ test/Transforms/LoopUnroll/unroll-and-jam.ll @@ -0,0 +1,699 @@ +; RUN: opt -basicaa -tbaa -loop-unroll -unroll-and-jam -always-unroll-and-jam < %s -S | FileCheck %s + +target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64" +target triple = "thumbv8m.main-arm-none-eabi" + +; CHECK-LABEL: test1 +; Tests for(i) { sum = 0; for(j) sum += B[j]; A[i] = sum; } +; CHECK: entry: +; CHECK: br i1 %or.cond, label %for.outer.preheader, label %for.end +; CHECK: for.outer.preheader: +; CHECK: br i1 %1, label %for.end.loopexit.unr-lcssa, label %for.outer.preheader.new +; CHECK: for.outer.preheader.new: +; CHECK: br label %for.outer +; CHECK: for.outer: +; CHECK: %i.us = phi i32 [ %add8.us.3, %for.latch ], [ 0, %for.outer.preheader.new ] +; CHECK: %niter = phi i32 [ %unroll_iter, %for.outer.preheader.new ], [ %niter.nsub.3, %for.latch ] +; CHECK: %add8.us = add nuw nsw i32 %i.us, 1 +; CHECK: %niter.nsub = sub i32 %niter, 1 +; CHECK: %add8.us.1 = add nuw nsw i32 %add8.us, 1 +; CHECK: %niter.nsub.1 = sub i32 %niter.nsub, 1 +; CHECK: %add8.us.2 = add nuw nsw i32 %add8.us.1, 1 +; CHECK: %niter.nsub.2 = sub i32 %niter.nsub.1, 1 +; CHECK: %add8.us.3 = add nuw i32 %add8.us.2, 1 +; CHECK: %niter.nsub.3 = sub i32 %niter.nsub.2, 1 +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] +; CHECK: %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] +; CHECK: %j.us.1 = phi i32 [ 0, %for.outer ], [ %inc.us.1, %for.inner ] +; CHECK: %sum1.us.1 = phi i32 [ 0, %for.outer ], [ %add.us.1, %for.inner ] +; CHECK: %j.us.2 = phi i32 [ 0, %for.outer ], [ %inc.us.2, %for.inner ] +; CHECK: %sum1.us.2 = phi i32 [ 0, %for.outer ], [ %add.us.2, %for.inner ] +; CHECK: %j.us.3 = phi i32 [ 0, %for.outer ], [ %inc.us.3, %for.inner ] +; CHECK: %sum1.us.3 = phi i32 [ 0, %for.outer ], [ %add.us.3, %for.inner ] +; CHECK: %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us +; CHECK: %2 = load i32, i32* %arrayidx.us, align 4, !tbaa !0 +; CHECK: %add.us = add i32 %2, %sum1.us +; CHECK: %inc.us = add nuw i32 %j.us, 1 +; CHECK: %arrayidx.us.1 = getelementptr inbounds i32, i32* %B, i32 %j.us.1 +; CHECK: %3 = load i32, i32* %arrayidx.us.1, align 4, !tbaa !0 +; CHECK: %add.us.1 = add i32 %3, %sum1.us.1 +; CHECK: %inc.us.1 = add nuw i32 %j.us.1, 1 +; CHECK: %arrayidx.us.2 = getelementptr inbounds i32, i32* %B, i32 %j.us.2 +; CHECK: %4 = load i32, i32* %arrayidx.us.2, align 4, !tbaa !0 +; CHECK: %add.us.2 = add i32 %4, %sum1.us.2 +; CHECK: %inc.us.2 = add nuw i32 %j.us.2, 1 +; CHECK: %arrayidx.us.3 = getelementptr inbounds i32, i32* %B, i32 %j.us.3 +; CHECK: %5 = load i32, i32* %arrayidx.us.3, align 4, !tbaa !0 +; CHECK: %add.us.3 = add i32 %5, %sum1.us.3 +; CHECK: %inc.us.3 = add nuw i32 %j.us.3, 1 +; CHECK: %exitcond.3 = icmp eq i32 %inc.us.3, %J +; CHECK: br i1 %exitcond.3, label %for.latch, label %for.inner +; CHECK: for.latch: +; CHECK: %add.us.lcssa = phi i32 [ %add.us, %for.inner ] +; CHECK: %add.us.lcssa.1 = phi i32 [ %add.us.1, %for.inner ] +; CHECK: %add.us.lcssa.2 = phi i32 [ %add.us.2, %for.inner ] +; CHECK: %add.us.lcssa.3 = phi i32 [ %add.us.3, %for.inner ] +; CHECK: %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us +; CHECK: store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !0 +; CHECK: %arrayidx6.us.1 = getelementptr inbounds i32, i32* %A, i32 %add8.us +; CHECK: store i32 %add.us.lcssa.1, i32* %arrayidx6.us.1, align 4, !tbaa !0 +; CHECK: %arrayidx6.us.2 = getelementptr inbounds i32, i32* %A, i32 %add8.us.1 +; CHECK: store i32 %add.us.lcssa.2, i32* %arrayidx6.us.2, align 4, !tbaa !0 +; CHECK: %arrayidx6.us.3 = getelementptr inbounds i32, i32* %A, i32 %add8.us.2 +; CHECK: store i32 %add.us.lcssa.3, i32* %arrayidx6.us.3, align 4, !tbaa !0 +; CHECK: %niter.ncmp.3 = icmp eq i32 %niter.nsub.3, 0 +; CHECK: br i1 %niter.ncmp.3, label %for.end.loopexit.unr-lcssa.loopexit, label %for.outer +; CHECK: for.end.loopexit.unr-lcssa.loopexit: +; CHECK: %i.us.unr.ph = phi i32 [ %add8.us.3, %for.latch ] +; CHECK: br label %for.end.loopexit.unr-lcssa +; CHECK: for.end.loopexit.unr-lcssa: +; CHECK: br i1 %lcmp.mod, label %for.outer.epil.preheader, label %for.end.loopexit +; CHECK: for.outer.epil.preheader: +; CHECK: br label %for.outer.epil +; CHECK: for.outer.epil: +; CHECK: br label %for.inner.epil +; CHECK: for.inner.epil: +; CHECK: br i1 %exitcond.epil, label %for.latch.epil, label %for.inner.epil +; CHECK: for.latch.epil: +; CHECK: br i1 %epil.iter.cmp, label %for.outer.epil.1, label %for.end.loopexit.epilog-lcssa +; CHECK: for.end.loopexit.epilog-lcssa: +; CHECK: br label %for.end.loopexit +; CHECK: for.end.loopexit: +; CHECK: br label %for.end +; CHECK: for.end: +; CHECK: ret void +; CHECK: for.outer.epil.1: +; CHECK: br label %for.inner.epil.1 +; CHECK: for.inner.epil.1: +; CHECK: br i1 %exitcond.epil.1, label %for.latch.epil.1, label %for.inner.epil.1 +; CHECK: for.latch.epil.1: +; CHECK: br i1 %epil.iter.cmp.1, label %for.outer.epil.2, label %for.end.loopexit.epilog-lcssa +; CHECK: for.outer.epil.2: +; CHECK: br label %for.inner.epil.2 +; CHECK: for.inner.epil.2: +; CHECK: br i1 %exitcond.epil.2, label %for.latch.epil.2, label %for.inner.epil.2 +; CHECK: for.latch.epil.2: +; CHECK: br label %for.end.loopexit.epilog-lcssa +define void @test1(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + %add.us = add i32 %0, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + +; CHECK-LABEL: test2 +; Tests for(i) { sum = A[i]; for(j) sum += B[j]; A[i] = sum; } +; A[i] load/store dependency should not block unroll-and-jam +; CHECK: for.outer: +; CHECK: %i.us = phi i32 [ %add9.us.3, %for.latch ], [ 0, %for.outer.preheader.new ] +; CHECK: %niter = phi i32 [ %unroll_iter, %for.outer.preheader.new ], [ %niter.nsub.3, %for.latch ] +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] +; CHECK: %sum1.us = phi i32 [ %2, %for.outer ], [ %add.us, %for.inner ] +; CHECK: %j.us.1 = phi i32 [ 0, %for.outer ], [ %inc.us.1, %for.inner ] +; CHECK: %sum1.us.1 = phi i32 [ %3, %for.outer ], [ %add.us.1, %for.inner ] +; CHECK: %j.us.2 = phi i32 [ 0, %for.outer ], [ %inc.us.2, %for.inner ] +; CHECK: %sum1.us.2 = phi i32 [ %4, %for.outer ], [ %add.us.2, %for.inner ] +; CHECK: %j.us.3 = phi i32 [ 0, %for.outer ], [ %inc.us.3, %for.inner ] +; CHECK: %sum1.us.3 = phi i32 [ %5, %for.outer ], [ %add.us.3, %for.inner ] +; CHECK: br i1 %exitcond.3, label %for.latch, label %for.inner +; CHECK: for.latch: +; CHECK: %add.us.lcssa = phi i32 [ %add.us, %for.inner ] +; CHECK: %add.us.lcssa.1 = phi i32 [ %add.us.1, %for.inner ] +; CHECK: %add.us.lcssa.2 = phi i32 [ %add.us.2, %for.inner ] +; CHECK: %add.us.lcssa.3 = phi i32 [ %add.us.3, %for.inner ] +; CHECK: br i1 %niter.ncmp.3, label %for.end10.loopexit.unr-lcssa.loopexit, label %for.outer +; CHECK: for.end10.loopexit.unr-lcssa.loopexit: +define void @test2(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp125 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp125 + br i1 %or.cond, label %for.outer.preheader, label %for.end10 + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add9.us, %for.latch ], [ 0, %for.outer.preheader ] + %arrayidx.us = getelementptr inbounds i32, i32* %A, i32 %i.us + %0 = load i32, i32* %arrayidx.us, align 4, !tbaa !5 + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ %0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %B, i32 %j.us + %1 = load i32, i32* %arrayidx6.us, align 4, !tbaa !5 + %add.us = add i32 %1, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + store i32 %add.us.lcssa, i32* %arrayidx.us, align 4, !tbaa !5 + %add9.us = add nuw i32 %i.us, 1 + %exitcond28 = icmp eq i32 %add9.us, %I + br i1 %exitcond28, label %for.end10.loopexit, label %for.outer + +for.end10.loopexit: + br label %for.end10 + +for.end10: + ret void +} + + +; CHECK-LABEL: test3 +; Tests Complete unroll-and-jam of the outer loop +; CHECK: for.outer: +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: %j.021 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] +; CHECK: %sum1.020 = phi i32 [ 0, %for.outer ], [ %add, %for.inner ] +; CHECK: %j.021.1 = phi i32 [ 0, %for.outer ], [ %inc.1, %for.inner ] +; CHECK: %sum1.020.1 = phi i32 [ 0, %for.outer ], [ %add.1, %for.inner ] +; CHECK: %j.021.2 = phi i32 [ 0, %for.outer ], [ %inc.2, %for.inner ] +; CHECK: %sum1.020.2 = phi i32 [ 0, %for.outer ], [ %add.2, %for.inner ] +; CHECK: %j.021.3 = phi i32 [ 0, %for.outer ], [ %inc.3, %for.inner ] +; CHECK: %sum1.020.3 = phi i32 [ 0, %for.outer ], [ %add.3, %for.inner ] +; CHECK: br i1 %exitcond.3, label %for.latch, label %for.inner +; CHECK: for.latch: +; CHECK: %add.lcssa = phi i32 [ %add, %for.inner ] +; CHECK: %add.lcssa.1 = phi i32 [ %add.1, %for.inner ] +; CHECK: %add.lcssa.2 = phi i32 [ %add.2, %for.inner ] +; CHECK: %add.lcssa.3 = phi i32 [ %add.3, %for.inner ] +; CHECK: br label %for.end +; CHECK: for.end: +define void @test3(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp eq i32 %J, 0 + br i1 %cmp, label %for.end, label %for.preheader + +for.preheader: + br label %for.outer + +for.outer: + %i.022 = phi i32 [ %add8, %for.latch ], [ 0, %for.preheader ] + br label %for.inner + +for.inner: + %j.021 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] + %sum1.020 = phi i32 [ 0, %for.outer ], [ %add, %for.inner ] + %arrayidx = getelementptr inbounds i32, i32* %B, i32 %j.021 + %0 = load i32, i32* %arrayidx, align 4, !tbaa !5 + %sub = add i32 %sum1.020, 10 + %add = sub i32 %sub, %0 + %inc = add nuw i32 %j.021, 1 + %exitcond = icmp eq i32 %inc, %J + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.latch: + %arrayidx6 = getelementptr inbounds i32, i32* %A, i32 %i.022 + store i32 %add, i32* %arrayidx6, align 4, !tbaa !5 + %add8 = add nuw nsw i32 %i.022, 1 + %exitcond23 = icmp eq i32 %add8, 4 + br i1 %exitcond23, label %for.end, label %for.outer + +for.end: + ret void +} + +; CHECK-LABEL: test4 +; Tests Complete unroll-and-jam with a trip count of 1 +; CHECK: for.outer: +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: %j.021 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] +; CHECK: %sum1.020 = phi i32 [ 0, %for.outer ], [ %add, %for.inner ] +; CHECK: br i1 %exitcond, label %for.latch, label %for.inner +; CHECK: for.latch: +; CHECK: %add.lcssa = phi i32 [ %add, %for.inner ] +; CHECK: br label %for.end +; CHECK: for.end: +define void @test4(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp eq i32 %J, 0 + br i1 %cmp, label %for.end, label %for.preheader + +for.preheader: + br label %for.outer + +for.outer: + %i.022 = phi i32 [ %add8, %for.latch ], [ 0, %for.preheader ] + br label %for.inner + +for.inner: + %j.021 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] + %sum1.020 = phi i32 [ 0, %for.outer ], [ %add, %for.inner ] + %arrayidx = getelementptr inbounds i32, i32* %B, i32 %j.021 + %0 = load i32, i32* %arrayidx, align 4, !tbaa !5 + %sub = add i32 %sum1.020, 10 + %add = sub i32 %sub, %0 + %inc = add nuw i32 %j.021, 1 + %exitcond = icmp eq i32 %inc, %J + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.latch: + %arrayidx6 = getelementptr inbounds i32, i32* %A, i32 %i.022 + store i32 %add, i32* %arrayidx6, align 4, !tbaa !5 + %add8 = add nuw nsw i32 %i.022, 1 + %exitcond23 = icmp eq i32 %add8, 1 + br i1 %exitcond23, label %for.end, label %for.outer + +for.end: + ret void +} + + + + + +; CHECK-LABEL: test5 +; Multiple SubLoopBlocks +; CHECK: for.outer: +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: %inc8.sink15 = phi i32 [ 0, %for.outer ], [ %inc8, %for.inc.1 ] +; CHECK: %inc8.sink15.1 = phi i32 [ 0, %for.outer ], [ %inc8.1, %for.inc.1 ] +; CHECK: br label %for.inner2 +; CHECK: for.inner2: +; CHECK: br i1 %tobool, label %for.cond4, label %for.inc +; CHECK: for.cond4: +; CHECK: br i1 %tobool.1, label %for.cond4a, label %for.inc +; CHECK: for.cond4a: +; CHECK: br label %for.inc +; CHECK: for.inc: +; CHECK: br i1 %tobool.11, label %for.cond4.1, label %for.inc.1 +; CHECK: for.latch: +; CHECK: br label %for.end +; CHECK: for.end: +; CHECK: ret i32 0 +; CHECK: for.cond4.1: +; CHECK: br i1 %tobool.1.1, label %for.cond4a.1, label %for.inc.1 +; CHECK: for.cond4a.1: +; CHECK: br label %for.inc.1 +; CHECK: for.inc.1: +; CHECK: br i1 %exitcond.1, label %for.latch, label %for.inner +@a = hidden local_unnamed_addr global [1 x i32] zeroinitializer, align 4 +define i32 @test5() local_unnamed_addr #0 { +entry: + br label %for.outer + +for.outer: + %.sink16 = phi i32 [ 0, %entry ], [ %add, %for.latch ] + br label %for.inner + +for.inner: + %inc8.sink15 = phi i32 [ 0, %for.outer ], [ %inc8, %for.inc ] + br label %for.inner2 + +for.inner2: + %l1 = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @a, i32 0, i32 0), align 4 + %tobool = icmp eq i32 %l1, 0 + br i1 %tobool, label %for.cond4, label %for.inc + +for.cond4: + %l0 = load i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @a, i32 1, i32 0), align 4 + %tobool.1 = icmp eq i32 %l0, 0 + br i1 %tobool.1, label %for.cond4a, label %for.inc + +for.cond4a: + br label %for.inc + +for.inc: + %l2 = phi i32 [ 0, %for.inner2 ], [ 1, %for.cond4 ], [ 2, %for.cond4a ] + %inc8 = add nuw nsw i32 %inc8.sink15, 1 + %exitcond = icmp eq i32 %inc8, 3 + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.latch: + %.lcssa = phi i32 [ %l2, %for.inc ] + %conv11 = and i32 %.sink16, 255 + %add = add nuw nsw i32 %conv11, 4 + %cmp = icmp eq i32 %add, 8 + br i1 %cmp, label %for.end, label %for.outer + +for.end: + %.lcssa.lcssa = phi i32 [ %.lcssa, %for.latch ] + ret i32 0 +} + + + + +; CHECK-LABEL: test6 +; Test odd uses of phi nodes +; CHECK: for.outer: +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: br i1 %exitcond.4, label %for.inner, label %for.latch +; CHECK: for.latch: +; CHECK: br label %for.end +; CHECK: for.end: +; CHECK: ret i32 0 +@f = hidden local_unnamed_addr global i32 0, align 4 +define i32 @test6() local_unnamed_addr #0 { +entry: + %f.promoted10 = load i32, i32* @f, align 4, !tbaa !5 + br label %for.outer + +for.outer: + %p0 = phi i32 [ %f.promoted10, %entry ], [ 2, %for.latch ] + %inc5.sink9 = phi i32 [ 2, %entry ], [ %inc5, %for.latch ] + br label %for.inner + +for.inner: + %p1 = phi i32 [ %p0, %for.outer ], [ 2, %for.inner ] + %inc.sink8 = phi i32 [ 0, %for.outer ], [ %inc, %for.inner ] + %inc = add nuw nsw i32 %inc.sink8, 1 + %exitcond = icmp ne i32 %inc, 7 + br i1 %exitcond, label %for.inner, label %for.latch, !llvm.loop !1 + +for.latch: + %.lcssa = phi i32 [ %p1, %for.inner ] + %inc5 = add nuw nsw i32 %inc5.sink9, 1 + %exitcond11 = icmp ne i32 %inc5, 7 + br i1 %exitcond11, label %for.outer, label %for.end + +for.end: + %.lcssa.lcssa = phi i32 [ %.lcssa, %for.latch ] + %inc.lcssa.lcssa = phi i32 [ 7, %for.latch ] + ret i32 0 +} + + + +; CHECK-LABEL: test7 +; Has a positive dependency between two stores. Still valid. +; The negative dependecy is in unroll-and-jam-disabled.ll +; CHECK: for.outer: +; CHECK: %i = phi i32 [ %add.3, %for.latch ], [ 0, %for.preheader.new ] +; CHECK: %niter = phi i32 [ %unroll_iter, %for.preheader.new ], [ %niter.nsub.3, %for.latch ] +; CHECK: br label %for.inner +; CHECK: for.latch: +; CHECK: %add9.lcssa = phi i32 [ %add9, %for.inner ] +; CHECK: %add9.lcssa.1 = phi i32 [ %add9.1, %for.inner ] +; CHECK: %add9.lcssa.2 = phi i32 [ %add9.2, %for.inner ] +; CHECK: %add9.lcssa.3 = phi i32 [ %add9.3, %for.inner ] +; CHECK: br i1 %niter.ncmp.3, label %for.end.loopexit.unr-lcssa.loopexit, label %for.outer +; CHECK: for.inner: +; CHECK: %sum = phi i32 [ 0, %for.outer ], [ %add9, %for.inner ] +; CHECK: %j = phi i32 [ 0, %for.outer ], [ %add10, %for.inner ] +; CHECK: %sum.1 = phi i32 [ 0, %for.outer ], [ %add9.1, %for.inner ] +; CHECK: %j.1 = phi i32 [ 0, %for.outer ], [ %add10.1, %for.inner ] +; CHECK: %sum.2 = phi i32 [ 0, %for.outer ], [ %add9.2, %for.inner ] +; CHECK: %j.2 = phi i32 [ 0, %for.outer ], [ %add10.2, %for.inner ] +; CHECK: %sum.3 = phi i32 [ 0, %for.outer ], [ %add9.3, %for.inner ] +; CHECK: %j.3 = phi i32 [ 0, %for.outer ], [ %add10.3, %for.inner ] +; CHECK: br i1 %exitcond.3, label %for.latch, label %for.inner +; CHECK: for.end.loopexit.unr-lcssa.loopexit: +define void @test7(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp128 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp128, %cmp + br i1 %or.cond, label %for.preheader, label %for.end + +for.preheader: + br label %for.outer + +for.outer: + %i = phi i32 [ %add, %for.latch ], [ 0, %for.preheader ] + %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i + store i32 0, i32* %arrayidx, align 4, !tbaa !5 + %add = add nuw i32 %i, 1 + %arrayidx2 = getelementptr inbounds i32, i32* %A, i32 %add + store i32 2, i32* %arrayidx2, align 4, !tbaa !5 + br label %for.inner + +for.latch: + store i32 %add9, i32* %arrayidx, align 4, !tbaa !5 + %exitcond30 = icmp eq i32 %add, %I + br i1 %exitcond30, label %for.end, label %for.outer + +for.inner: + %sum = phi i32 [ 0, %for.outer ], [ %add9, %for.inner ] + %j = phi i32 [ 0, %for.outer ], [ %add10, %for.inner ] + %arrayidx7 = getelementptr inbounds i32, i32* %B, i32 %j + %l1 = load i32, i32* %arrayidx7, align 4, !tbaa !5 + %add9 = add i32 %l1, %sum + %add10 = add nuw i32 %j, 1 + %exitcond = icmp eq i32 %add10, %J + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.end: + ret void +} + + + +; CHECK-LABEL: test8 +; Same as test7 with an extra outer loop nest +; CHECK: for.outest: +; CHECK: br label %for.outer +; CHECK: for.outer: +; CHECK: %i = phi i32 [ %add.3, %for.latch ], [ 0, %for.outest.new ] +; CHECK: %niter = phi i32 [ %unroll_iter, %for.outest.new ], [ %niter.nsub.3, %for.latch ] +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: %sum = phi i32 [ 0, %for.outer ], [ %add9, %for.inner ] +; CHECK: %j = phi i32 [ 0, %for.outer ], [ %add10, %for.inner ] +; CHECK: %sum.1 = phi i32 [ 0, %for.outer ], [ %add9.1, %for.inner ] +; CHECK: %j.1 = phi i32 [ 0, %for.outer ], [ %add10.1, %for.inner ] +; CHECK: %sum.2 = phi i32 [ 0, %for.outer ], [ %add9.2, %for.inner ] +; CHECK: %j.2 = phi i32 [ 0, %for.outer ], [ %add10.2, %for.inner ] +; CHECK: %sum.3 = phi i32 [ 0, %for.outer ], [ %add9.3, %for.inner ] +; CHECK: %j.3 = phi i32 [ 0, %for.outer ], [ %add10.3, %for.inner ] +; CHECK: br i1 %exitcond.3, label %for.latch, label %for.inner +; CHECK: for.latch: +; CHECK: %add9.lcssa = phi i32 [ %add9, %for.inner ] +; CHECK: %add9.lcssa.1 = phi i32 [ %add9.1, %for.inner ] +; CHECK: %add9.lcssa.2 = phi i32 [ %add9.2, %for.inner ] +; CHECK: %add9.lcssa.3 = phi i32 [ %add9.3, %for.inner ] +; CHECK: br i1 %niter.ncmp.3, label %for.cleanup.unr-lcssa.loopexit, label %for.outer +; CHECK: for.cleanup.epilog-lcssa: +; CHECK: br label %for.cleanup +; CHECK: for.cleanup: +; CHECK: br i1 %exitcond41, label %for.end.loopexit, label %for.outest +; CHECK: for.end.loopexit: +; CHECK: br label %for.end +define void @test8(i32 %I, i32 %J, i32* noalias nocapture %A, i32* noalias nocapture readonly %B) local_unnamed_addr #0 { +entry: + %cmp = icmp eq i32 %J, 0 + %cmp336 = icmp eq i32 %I, 0 + %or.cond = or i1 %cmp, %cmp336 + br i1 %or.cond, label %for.end, label %for.preheader + +for.preheader: + br label %for.outest + +for.outest: + %x.038 = phi i32 [ %inc, %for.cleanup ], [ 0, %for.preheader ] + br label %for.outer + +for.outer: + %i = phi i32 [ %add, %for.latch ], [ 0, %for.outest ] + %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i + store i32 0, i32* %arrayidx, align 4, !tbaa !5 + %add = add nuw i32 %i, 1 + %arrayidx6 = getelementptr inbounds i32, i32* %A, i32 %add + store i32 2, i32* %arrayidx6, align 4, !tbaa !5 + br label %for.inner + +for.inner: + %sum = phi i32 [ 0, %for.outer ], [ %add9, %for.inner ] + %j = phi i32 [ 0, %for.outer ], [ %add10, %for.inner ] + %arrayidx11 = getelementptr inbounds i32, i32* %B, i32 %j + %l1 = load i32, i32* %arrayidx11, align 4, !tbaa !5 + %add9 = add i32 %l1, %sum + %add10 = add nuw i32 %j, 1 + %exitcond = icmp eq i32 %add10, %J + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.latch: + store i32 %add9, i32* %arrayidx, align 4, !tbaa !5 + %exitcond39 = icmp eq i32 %add, %I + br i1 %exitcond39, label %for.cleanup, label %for.outer + +for.cleanup: + %inc = add nuw nsw i32 %x.038, 1 + %exitcond41 = icmp eq i32 %inc, 5 + br i1 %exitcond41, label %for.end, label %for.outest + + +for.end: + ret void +} + +; CHECK-LABEL: test9 +; Same as test1 with tbaa, not noalias +; CHECK: for.outer: +; CHECK: %i.us = phi i32 [ %add8.us.3, %for.latch ], [ 0, %for.outer.preheader.new ] +; CHECK: %niter = phi i32 [ %unroll_iter, %for.outer.preheader.new ], [ %niter.nsub.3, %for.latch ] +; CHECK: br label %for.inner +; CHECK: for.inner: +; CHECK: %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] +; CHECK: %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] +; CHECK: %j.us.1 = phi i32 [ 0, %for.outer ], [ %inc.us.1, %for.inner ] +; CHECK: %sum1.us.1 = phi i32 [ 0, %for.outer ], [ %add.us.1, %for.inner ] +; CHECK: %j.us.2 = phi i32 [ 0, %for.outer ], [ %inc.us.2, %for.inner ] +; CHECK: %sum1.us.2 = phi i32 [ 0, %for.outer ], [ %add.us.2, %for.inner ] +; CHECK: %j.us.3 = phi i32 [ 0, %for.outer ], [ %inc.us.3, %for.inner ] +; CHECK: %sum1.us.3 = phi i32 [ 0, %for.outer ], [ %add.us.3, %for.inner ] +; CHECK: br i1 %exitcond.3, label %for.latch, label %for.inner +; CHECK: for.latch: +; CHECK: %add.us.lcssa = phi i32 [ %add.us, %for.inner ] +; CHECK: %add.us.lcssa.1 = phi i32 [ %add.us.1, %for.inner ] +; CHECK: %add.us.lcssa.2 = phi i32 [ %add.us.2, %for.inner ] +; CHECK: %add.us.lcssa.3 = phi i32 [ %add.us.3, %for.inner ] +; CHECK: br i1 %niter.ncmp.3, label %for.end.loopexit.unr-lcssa.loopexit, label %for.outer +; CHECK: for.end.loopexit.unr-lcssa.loopexit: +define void @test9(i32 %I, i32 %J, i32* nocapture %A, i16* nocapture readonly %B) #0 { +entry: + %cmp = icmp ne i32 %J, 0 + %cmp122 = icmp ne i32 %I, 0 + %or.cond = and i1 %cmp, %cmp122 + br i1 %or.cond, label %for.outer.preheader, label %for.end + +for.outer.preheader: + br label %for.outer + +for.outer: + %i.us = phi i32 [ %add8.us, %for.latch ], [ 0, %for.outer.preheader ] + br label %for.inner + +for.inner: + %j.us = phi i32 [ 0, %for.outer ], [ %inc.us, %for.inner ] + %sum1.us = phi i32 [ 0, %for.outer ], [ %add.us, %for.inner ] + %arrayidx.us = getelementptr inbounds i16, i16* %B, i32 %j.us + %0 = load i16, i16* %arrayidx.us, align 4, !tbaa !9 + %sext = sext i16 %0 to i32 + %add.us = add i32 %sext, %sum1.us + %inc.us = add nuw i32 %j.us, 1 + %exitcond = icmp eq i32 %inc.us, %J + br i1 %exitcond, label %for.latch, label %for.inner, !llvm.loop !1 + +for.latch: + %add.us.lcssa = phi i32 [ %add.us, %for.inner ] + %arrayidx6.us = getelementptr inbounds i32, i32* %A, i32 %i.us + store i32 %add.us.lcssa, i32* %arrayidx6.us, align 4, !tbaa !5 + %add8.us = add nuw i32 %i.us, 1 + %exitcond25 = icmp eq i32 %add8.us, %I + br i1 %exitcond25, label %for.end.loopexit, label %for.outer + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + + + +; CHECK-LABEL: test10 +; Be careful not to incorrectly update the exit phi nodes +; CHECK: %dec19.lcssa.lcssa.lcssa = phi i64 [ 0, %for.inc24 ] +%struct.a = type { i64 } +@g = common local_unnamed_addr global %struct.a zeroinitializer, align 8 +@c = common local_unnamed_addr global [1 x i8] zeroinitializer, align 1 +; Function Attrs: noinline norecurse nounwind uwtable +define signext i16 @test10(i32 %k) local_unnamed_addr #0 { +entry: + %0 = load i8, i8* getelementptr inbounds ([1 x i8], [1 x i8]* @c, i64 0, i64 0), align 1 + %tobool9 = icmp eq i8 %0, 0 + %tobool13 = icmp ne i32 %k, 0 + br label %for.body + +for.body: ; preds = %entry, %for.inc24 + %storemerge82 = phi i64 [ 0, %entry ], [ %inc25, %for.inc24 ] + br label %for.body2 + +for.body2: ; preds = %for.body, %for.inc21 + %storemerge2881 = phi i64 [ 4, %for.body ], [ %dec22, %for.inc21 ] + br i1 %tobool9, label %for.body2.split, label %for.body2.split.us + +for.body2.split.us: ; preds = %for.body2 + br i1 %tobool13, label %for.inc21, label %for.inc21.loopexit83 + +for.body2.split: ; preds = %for.body2 + br i1 %tobool13, label %for.inc21, label %for.inc21.loopexit85 + +for.inc21.loopexit83: ; preds = %for.body2.split.us + %storemerge31.us37.lcssa.lcssa = phi i64 [ 0, %for.body2.split.us ] + br label %for.inc21 + +for.inc21.loopexit85: ; preds = %for.body2.split + %storemerge31.lcssa.lcssa87 = phi i64 [ 0, %for.body2.split ] + %storemerge30.lcssa.lcssa86 = phi i32 [ 0, %for.body2.split ] + br label %for.inc21 + +for.inc21: ; preds = %for.body2.split, %for.body2.split.us, %for.inc21.loopexit85, %for.inc21.loopexit83 + %storemerge31.lcssa.lcssa = phi i64 [ %storemerge31.us37.lcssa.lcssa, %for.inc21.loopexit83 ], [ %storemerge31.lcssa.lcssa87, %for.inc21.loopexit85 ], [ 4, %for.body2.split.us ], [ 4, %for.body2.split ] + %storemerge30.lcssa.lcssa = phi i32 [ 0, %for.inc21.loopexit83 ], [ %storemerge30.lcssa.lcssa86, %for.inc21.loopexit85 ], [ 0, %for.body2.split.us ], [ 0, %for.body2.split ] + %dec22 = add nsw i64 %storemerge2881, -1 + %tobool = icmp eq i64 %dec22, 0 + br i1 %tobool, label %for.inc24, label %for.body2, !llvm.loop !1 + +for.inc24: ; preds = %for.inc21 + %storemerge31.lcssa.lcssa.lcssa = phi i64 [ %storemerge31.lcssa.lcssa, %for.inc21 ] + %storemerge30.lcssa.lcssa.lcssa = phi i32 [ %storemerge30.lcssa.lcssa, %for.inc21 ] + %inc25 = add nuw nsw i64 %storemerge82, 1 + %exitcond = icmp ne i64 %inc25, 5 + br i1 %exitcond, label %for.body, label %for.end26 + +for.end26: ; preds = %for.inc24 + %dec19.lcssa.lcssa.lcssa = phi i64 [ 0, %for.inc24 ] + %storemerge31.lcssa.lcssa.lcssa.lcssa = phi i64 [ %storemerge31.lcssa.lcssa.lcssa, %for.inc24 ] + %storemerge30.lcssa.lcssa.lcssa.lcssa = phi i32 [ %storemerge30.lcssa.lcssa.lcssa, %for.inc24 ] + store i64 %dec19.lcssa.lcssa.lcssa, i64* getelementptr inbounds (%struct.a, %struct.a* @g, i64 0, i32 0), align 8 + ret i16 0 +} + + +attributes #0 = { noinline norecurse nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "denormal-fp-math"="preserve-sign" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="true" "no-jump-tables"="false" "no-nans-fp-math"="true" "no-signed-zeros-fp-math"="true" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="cortex-m33" "target-features"="+d16,+dsp,+fp-armv8,+fp-only-sp,+hwdiv,+thumb-mode,-crc,-dotprod,-hwdiv-arm,-ras" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!1 = !{!1, !2} +!2 = !{!"llvm.loop.unroll.disable"} +!5 = !{!6, !6, i64 0} +!6 = !{!"int", !7, i64 0} +!7 = !{!"omnipotent char", !8, i64 0} +!8 = !{!"Simple C/C++ TBAA"} +!9 = !{!10, !10, i64 0} +!10 = !{!"short", !7, i64 0}