Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -14,6 +14,8 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H +#include "llvm/Analysis/AliasSetTracker.h" +#include "llvm/IR/PredIteratorCache.h" namespace llvm { class AliasAnalysis; class AssumptionCache; @@ -63,6 +65,37 @@ /// Returns true if any modifications are made to the loop. bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE = nullptr); + +/// SinkRegion - Walk the specified region of the CFG (defined by all blocks +/// dominated by the specified block, and that are in the current loop) in +/// reverse depth first order w.r.t the DominatorTree. This allows us to visit +/// uses before definitions, allowing us to sink a loop body in one pass without +/// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, +/// DataLayout, TargetLibraryInfo, Loop, AliasSetTracker, MayThrow and +/// HeaderMayThrow as argument and returns changed starts. +bool SinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, + const DataLayout *, TargetLibraryInfo *, Loop *, + AliasSetTracker *, bool , bool); + +/// HoistRegion - Walk the specified region of the CFG (defined by all blocks +/// dominated by the specified block, and that are in the current loop) in depth +/// first order w.r.t the DominatorTree. This allows us to visit definitions +/// before uses, allowing us to hoist a loop body in one pass without iteration. +/// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout, +/// TargetLibraryInfo, Loop, AliasSetTracker, MayThrow and HeaderMayThrow +/// as argument and returns changed starts. +bool HoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, + const DataLayout *, TargetLibraryInfo *, Loop *, + AliasSetTracker *, bool, bool); + +/// PromoteAliasSet - Try to promote memory values to scalars by sinking +/// stores out of the loop and moving loads to before the loop. We do this by +/// looping over the stores in the loop, looking for stores to Must pointers +/// which are loop invariant. +bool PromoteAliasSet(AliasSet &, SmallVectorImpl &, + SmallVectorImpl &, + PredIteratorCache &, LoopInfo *, DominatorTree *, + Loop *, AliasSetTracker *, bool, bool); } #endif Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -71,6 +71,28 @@ DisablePromotion("disable-licm-promotion", cl::Hidden, cl::desc("Disable memory promotion in LICM pass")); +static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI); +static bool isNotUsedInLoop(Instruction &I, Loop *CurLoop); +static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, + DominatorTree *DT, const DataLayout *DL, + Loop *CurLoop, AliasSetTracker *CurAST, + bool MayThrow, bool HeaderMayThrow); +static bool hoist(Instruction &I, BasicBlock *Preheader); +static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, + Loop *CurLoop, AliasSetTracker *CurAST ); +static bool isSafeToExecuteUnconditionally(Instruction &Inst,DominatorTree *DT, + const DataLayout *DL, Loop *CurLoop, + bool MayThrow, bool HeaderMayThrow); +static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, + const AAMDNodes &AAInfo, + AliasSetTracker *CurAST); +static bool isGuaranteedToExecute(Instruction &Inst, DominatorTree *DT, + Loop *CurLoop, bool MayThrow, + bool HeaderMayThrow); +static Instruction *CloneInstructionInExitBlock(Instruction &I, + BasicBlock &ExitBlock, + PHINode &PN, LoopInfo *LI); + namespace { struct LICM : public LoopPass { static char ID; // Pass identification, replacement for typeid @@ -133,77 +155,6 @@ /// Simple Analysis hook. Delete loop L from alias set map. void deleteAnalysisLoop(Loop *L) override; - - /// SinkRegion - Walk the specified region of the CFG (defined by all blocks - /// dominated by the specified block, and that are in the current loop) in - /// reverse depth first order w.r.t the DominatorTree. This allows us to - /// visit uses before definitions, allowing us to sink a loop body in one - /// pass without iteration. - /// - void SinkRegion(DomTreeNode *N); - - /// HoistRegion - Walk the specified region of the CFG (defined by all - /// blocks dominated by the specified block, and that are in the current - /// loop) in depth first order w.r.t the DominatorTree. This allows us to - /// visit definitions before uses, allowing us to hoist a loop body in one - /// pass without iteration. - /// - void HoistRegion(DomTreeNode *N); - - /// inSubLoop - Little predicate that returns true if the specified basic - /// block is in a subloop of the current one, not the current one itself. - /// - bool inSubLoop(BasicBlock *BB) { - assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); - return LI->getLoopFor(BB) != CurLoop; - } - - /// sink - When an instruction is found to only be used outside of the loop, - /// this function moves it to the exit blocks and patches up SSA form as - /// needed. - /// - void sink(Instruction &I); - - /// hoist - When an instruction is found to only use loop invariant operands - /// that is safe to hoist, this instruction is called to do the dirty work. - /// - void hoist(Instruction &I); - - /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it - /// is not a trapping instruction or if it is a trapping instruction and is - /// guaranteed to execute. - /// - bool isSafeToExecuteUnconditionally(Instruction &I); - - /// isGuaranteedToExecute - Check that the instruction is guaranteed to - /// execute. - /// - bool isGuaranteedToExecute(Instruction &I); - - /// pointerInvalidatedByLoop - Return true if the body of this loop may - /// store into the memory location pointed to by V. - /// - bool pointerInvalidatedByLoop(Value *V, uint64_t Size, - const AAMDNodes &AAInfo) { - // Check to see if any of the basic blocks in CurLoop invalidate *V. - return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod(); - } - - bool canSinkOrHoistInst(Instruction &I); - bool isNotUsedInLoop(Instruction &I); - - void PromoteAliasSet(AliasSet &AS, - SmallVectorImpl &ExitBlocks, - SmallVectorImpl &InsertPts, - PredIteratorCache &PIC); - - /// \brief Create a copy of the instruction in the exit block and patch up - /// SSA. - /// PN is a user of I in ExitBlock that can be used to get the number and - /// list of predecessors fast. - Instruction *CloneInstructionInExitBlock(Instruction &I, - BasicBlock &ExitBlock, - PHINode &PN); }; } @@ -299,9 +250,11 @@ // instructions, we perform another pass to hoist them out of the loop. // if (L->hasDedicatedExits()) - SinkRegion(DT->getNode(L->getHeader())); + Changed |= SinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, DL, TLI, + CurLoop, CurAST, MayThrow, HeaderMayThrow); if (Preheader) - HoistRegion(DT->getNode(L->getHeader())); + Changed |= HoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, DL, TLI, + CurLoop, CurAST, MayThrow, HeaderMayThrow); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can. @@ -313,7 +266,8 @@ // Loop over all of the alias sets in the tracker object. for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); I != E; ++I) - PromoteAliasSet(*I, ExitBlocks, InsertPts, PIC); + PromoteAliasSet(*I, ExitBlocks, InsertPts, PIC, LI, DT, + CurLoop, CurAST, MayThrow, HeaderMayThrow); // Once we have promoted values across the loop body we have to recursively // reform LCSSA as any nested loop may now have values defined within the @@ -352,21 +306,32 @@ /// uses before definitions, allowing us to sink a loop body in one pass without /// iteration. /// -void LICM::SinkRegion(DomTreeNode *N) { - assert(N != nullptr && "Null dominator tree node?"); +bool llvm::SinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, + DominatorTree *DT, const DataLayout *DL, + TargetLibraryInfo *TLI, Loop *CurLoop, + AliasSetTracker *CurAST, + bool MayThrow, bool HeaderMayThrow) { + + // Verify inputs. + assert(N != nullptr && AA != nullptr && LI != nullptr && + DT != nullptr && CurLoop != nullptr && + CurAST != nullptr && "Unexpected input to SinkRegion"); + + // Initially set Changed status to false. + bool Changed = false; BasicBlock *BB = N->getBlock(); // If this subregion is not in the top level loop at all, exit. - if (!CurLoop->contains(BB)) return; + if (!CurLoop->contains(BB)) return Changed; // We are processing blocks in reverse dfo, so process children first. const std::vector &Children = N->getChildren(); for (unsigned i = 0, e = Children.size(); i != e; ++i) - SinkRegion(Children[i]); - + Changed |= SinkRegion(Children[i], AA, LI, DT, DL, TLI, CurLoop, + CurAST, MayThrow, HeaderMayThrow); // Only need to process the contents of this block if it is not part of a // subloop (which would already have been processed). - if (inSubLoop(BB)) return; + if (inSubLoop(BB,CurLoop,LI)) return Changed; for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { Instruction &I = *--II; @@ -387,11 +352,14 @@ // outside of the loop. In this case, it doesn't even matter if the // operands of the instruction are loop invariant. // - if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { + if (isNotUsedInLoop(I, CurLoop) && + canSinkOrHoistInst(I, AA, DT, DL, CurLoop, + CurAST, MayThrow, HeaderMayThrow)) { ++II; - sink(I); + Changed |= sink(I, LI, DT, CurLoop, CurAST); } } + return Changed; } /// HoistRegion - Walk the specified region of the CFG (defined by all blocks @@ -399,16 +367,24 @@ /// first order w.r.t the DominatorTree. This allows us to visit definitions /// before uses, allowing us to hoist a loop body in one pass without iteration. /// -void LICM::HoistRegion(DomTreeNode *N) { - assert(N != nullptr && "Null dominator tree node?"); +bool llvm::HoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, + DominatorTree *DT, const DataLayout *DL, + TargetLibraryInfo *TLI, Loop *CurLoop, + AliasSetTracker *CurAST, + bool MayThrow, bool HeaderMayThrow) { + // Verify inputs. + assert(N != nullptr && AA != nullptr && LI != nullptr && + DT != nullptr && CurLoop != nullptr && + CurAST != nullptr && "Unexpected input to HoistRegion"); + // Initially set Changed status to false. + bool Changed = false; BasicBlock *BB = N->getBlock(); - // If this subregion is not in the top level loop at all, exit. - if (!CurLoop->contains(BB)) return; + if (!CurLoop->contains(BB)) return Changed; // Only need to process the contents of this block if it is not part of a // subloop (which would already have been processed). - if (!inSubLoop(BB)) + if (!inSubLoop(BB, CurLoop, LI)) for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { Instruction &I = *II++; @@ -428,20 +404,28 @@ // if all of the operands of the instruction are loop invariant and if it // is safe to hoist the instruction. // - if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I) && - isSafeToExecuteUnconditionally(I)) - hoist(I); + if (CurLoop->hasLoopInvariantOperands(&I) && + canSinkOrHoistInst(I, AA, DT, DL, CurLoop, CurAST, + MayThrow, HeaderMayThrow) && + isSafeToExecuteUnconditionally(I, DT, DL, CurLoop, + MayThrow, HeaderMayThrow)) + Changed |= hoist(I, CurLoop->getLoopPreheader()); } const std::vector &Children = N->getChildren(); for (unsigned i = 0, e = Children.size(); i != e; ++i) - HoistRegion(Children[i]); + Changed |= HoistRegion(Children[i], AA, LI, DT, DL, TLI, CurLoop, CurAST, + MayThrow, HeaderMayThrow); + return Changed; } /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this /// instruction. /// -bool LICM::canSinkOrHoistInst(Instruction &I) { +static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT, + const DataLayout *DL, Loop *CurLoop, + AliasSetTracker *CurAST, bool MayThrow, + bool HeaderMayThrow) { // Loads have extra constraints we have to verify before we can hoist them. if (LoadInst *LI = dyn_cast(&I)) { if (!LI->isUnordered()) @@ -462,7 +446,7 @@ AAMDNodes AAInfo; LI->getAAMetadata(AAInfo); - return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo); + return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST); } else if (CallInst *CI = dyn_cast(&I)) { // Don't sink or hoist dbg info; it's legal, but not useful. if (isa(I)) @@ -501,7 +485,8 @@ !isa(I)) return false; - return isSafeToExecuteUnconditionally(I); + return isSafeToExecuteUnconditionally(I, DT, DL, CurLoop, + MayThrow, HeaderMayThrow); } /// \brief Returns true if a PHINode is a trivially replaceable with an @@ -521,7 +506,7 @@ /// outside of the loop. If this is true, we can sink the instruction to the /// exit blocks of the loop. /// -bool LICM::isNotUsedInLoop(Instruction &I) { +static bool isNotUsedInLoop(Instruction &I, Loop *CurLoop) { for (User *U : I.users()) { Instruction *UI = cast(U); if (PHINode *PN = dyn_cast(UI)) { @@ -552,9 +537,9 @@ return true; } -Instruction *LICM::CloneInstructionInExitBlock(Instruction &I, - BasicBlock &ExitBlock, - PHINode &PN) { +static Instruction *CloneInstructionInExitBlock(Instruction &I, + BasicBlock &ExitBlock, + PHINode &PN, LoopInfo *LI) { Instruction *New = I.clone(); ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New); if (!I.getName().empty()) New->setName(I.getName() + ".le"); @@ -586,9 +571,10 @@ /// This method is guaranteed to remove the original instruction from its /// position, and may either delete it or move it to outside of the loop. /// -void LICM::sink(Instruction &I) { +static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, + Loop *CurLoop, AliasSetTracker *CurAST ) { DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); - + bool Changed = false; if (isa(I)) ++NumMovedLoads; else if (isa(I)) ++NumMovedCalls; ++NumSunk; @@ -625,7 +611,7 @@ New = It->second; else New = SunkCopies[ExitBlock] = - CloneInstructionInExitBlock(I, *ExitBlock, *PN); + CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI); PN->replaceAllUsesWith(New); PN->eraseFromParent(); @@ -633,37 +619,41 @@ CurAST->deleteValue(&I); I.eraseFromParent(); + return Changed; } /// hoist - When an instruction is found to only use loop invariant operands /// that is safe to hoist, this instruction is called to do the dirty work. /// -void LICM::hoist(Instruction &I) { +static bool hoist(Instruction &I, BasicBlock *Preheader) { DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I << "\n"); - // Move the new node to the Preheader, before its terminator. I.moveBefore(Preheader->getTerminator()); if (isa(I)) ++NumMovedLoads; else if (isa(I)) ++NumMovedCalls; ++NumHoisted; - Changed = true; + return true; } /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is /// not a trapping instruction or if it is a trapping instruction and is /// guaranteed to execute. /// -bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { +static bool isSafeToExecuteUnconditionally(Instruction &Inst, DominatorTree *DT, + const DataLayout *DL, Loop *CurLoop, + bool MayThrow, bool HeaderMayThrow) { // If it is not a trapping instruction, it is always safe to hoist. if (isSafeToSpeculativelyExecute(&Inst, DL)) return true; - return isGuaranteedToExecute(Inst); + return isGuaranteedToExecute(Inst, DT, CurLoop, MayThrow, HeaderMayThrow); } -bool LICM::isGuaranteedToExecute(Instruction &Inst) { +static bool isGuaranteedToExecute(Instruction &Inst, DominatorTree *DT, + Loop *CurLoop, bool MayThrow, + bool HeaderMayThrow) { // We have to check to make sure that the instruction dominates all // of the exit blocks. If it doesn't, then there is a path out of the loop @@ -782,20 +772,29 @@ /// looping over the stores in the loop, looking for stores to Must pointers /// which are loop invariant. /// -void LICM::PromoteAliasSet(AliasSet &AS, - SmallVectorImpl &ExitBlocks, - SmallVectorImpl &InsertPts, - PredIteratorCache &PIC) { +bool llvm::PromoteAliasSet(AliasSet &AS, + SmallVectorImpl &ExitBlocks, + SmallVectorImpl &InsertPts, + PredIteratorCache &PIC, LoopInfo *LI, + DominatorTree *DT, Loop *CurLoop, + AliasSetTracker *CurAST, bool MayThrow, + bool HeaderMayThrow) { + // Verify inputs. + assert(LI != nullptr && DT != nullptr && CurLoop != nullptr && + CurAST != nullptr && "Unexpected Input to PromoteAliasSet"); + // Initially set Changed status to false. + bool Changed = false; // We can promote this alias set if it has a store, if it is a "Must" alias // set, if the pointer is loop invariant, and if we are not eliminating any // volatile loads or stores. if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) - return; + return Changed; assert(!AS.empty() && "Must alias set should have at least one pointer element in it!"); Value *SomePtr = AS.begin()->getValue(); + BasicBlock * Preheader = CurLoop->getLoopPreheader(); // It isn't safe to promote a load/store from the loop if the load/store is // conditional. For example, turning: @@ -832,7 +831,7 @@ // cannot (yet) promote a memory location that is loaded and stored in // different sizes. if (SomePtr->getType() != ASIV->getType()) - return; + return Changed; for (User *U : ASIV->users()) { // Ignore instructions that are outside the loop. @@ -845,7 +844,7 @@ if (LoadInst *load = dyn_cast(UI)) { assert(!load->isVolatile() && "AST broken"); if (!load->isSimple()) - return; + return Changed; } else if (StoreInst *store = dyn_cast(UI)) { // Stores *of* the pointer are not interesting, only stores *to* the // pointer. @@ -853,14 +852,14 @@ continue; assert(!store->isVolatile() && "AST broken"); if (!store->isSimple()) - return; + return Changed; // Don't sink stores from loops without dedicated block exits. Exits // containing indirect branches are not transformed by loop simplify, // make sure we catch that. An additional load may be generated in the // preheader for SSA updater, so also avoid sinking when no preheader // is available. if (!HasDedicatedExits || !Preheader) - return; + return Changed; // Note that we only check GuaranteedToExecute inside the store case // so that we do not introduce stores where they did not exist before @@ -872,16 +871,17 @@ // Larger is better, with the exception of 0 being the best alignment. unsigned InstAlignment = store->getAlignment(); if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0) - if (isGuaranteedToExecute(*UI)) { + if (isGuaranteedToExecute(*UI, DT, CurLoop, MayThrow, HeaderMayThrow)) { GuaranteedToExecute = true; Alignment = InstAlignment; } if (!GuaranteedToExecute) - GuaranteedToExecute = isGuaranteedToExecute(*UI); + GuaranteedToExecute = isGuaranteedToExecute(*UI, DT, CurLoop, + MayThrow, HeaderMayThrow); } else - return; // Not a load or store. + return Changed; // Not a load or store. // Merge the AA tags. if (LoopUses.empty()) { @@ -897,7 +897,7 @@ // If there isn't a guaranteed-to-execute instruction, we can't promote. if (!GuaranteedToExecute) - return; + return Changed; // Otherwise, this is safe to promote, lets do it! DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n'); @@ -942,8 +942,9 @@ // If the SSAUpdater didn't use the load in the preheader, just zap it now. if (PreheaderLoad->use_empty()) PreheaderLoad->eraseFromParent(); -} + return Changed; +} /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { @@ -973,3 +974,22 @@ delete AST; LoopToAliasSetMap.erase(L); } + + +/// pointerInvalidatedByLoop - Return true if the body of this loop may +/// store into the memory location pointed to by V. +/// +static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, + const AAMDNodes &AAInfo, AliasSetTracker *CurAST) { + // Check to see if any of the basic blocks in CurLoop invalidate *V. + return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod(); +} + +/// inSubLoop - Little predicate that returns true if the specified basic +/// block is in a subloop of the current one, not the current one itself. +/// +static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) { + assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); + return LI->getLoopFor(BB) != CurLoop; +} +