Index: llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h @@ -16,6 +16,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" @@ -441,12 +442,13 @@ /// \brief 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. It takes AliasSet, Loop exit blocks vector, loop exit blocks -/// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop, -/// AliasSet information for all instructions of the loop and loop safety -/// information as arguments. Diagnostics is emitted via \p ORE. It returns -/// changed status. -bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl &, +/// loop invariant. It takes a set of must-alias values, Loop exit blocks +/// vector, loop exit blocks insertion point vector, PredIteratorCache, +/// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions +/// of the loop and loop safety information as arguments. +/// Diagnostics is emitted via \p ORE. It returns changed status. +bool promoteLoopAccessesToScalars(const SmallSetVector &, + SmallVectorImpl &, SmallVectorImpl &, PredIteratorCache &, LoopInfo *, DominatorTree *, const TargetLibraryInfo *, Index: llvm/trunk/lib/Transforms/Scalar/LICM.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LICM.cpp +++ llvm/trunk/lib/Transforms/Scalar/LICM.cpp @@ -189,7 +189,7 @@ /// Simple Analysis hook. Delete loop L from alias set map. void deleteAnalysisLoop(Loop *L) override; }; -} +} // namespace PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &) { @@ -292,10 +292,26 @@ bool Promoted = false; // Loop over all of the alias sets in the tracker object. - for (AliasSet &AS : *CurAST) - Promoted |= - promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts, PIC, LI, DT, - TLI, L, CurAST, &SafetyInfo, ORE); + for (AliasSet &AS : *CurAST) { + // 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() || !L->isLoopInvariant(AS.begin()->getValue())) + continue; + + assert( + !AS.empty() && + "Must alias set should have at least one pointer element in it!"); + + SmallSetVector PointerMustAliases; + for (const auto &ASI : AS) + PointerMustAliases.insert(ASI.getValue()); + + Promoted |= promoteLoopAccessesToScalars(PointerMustAliases, ExitBlocks, + InsertPts, PIC, LI, DT, TLI, L, + CurAST, &SafetyInfo, ORE); + } // Once we have promoted values across the loop body we have to // recursively reform LCSSA as any nested loop may now have values defined @@ -383,8 +399,8 @@ for (BasicBlock::iterator II = BB->end(); II != BB->begin();) { Instruction &I = *--II; - // If the instruction is dead, we would try to sink it because it isn't used - // in the loop, instead, just delete it. + // If the instruction is dead, we would try to sink it because it isn't + // used in the loop, instead, just delete it. if (isInstructionTriviallyDead(&I, TLI)) { DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); ++II; @@ -509,7 +525,8 @@ // 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"); + 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) @@ -527,9 +544,9 @@ } // 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 invariant.start -// has no uses. +// CurLoop is dominated by an invariant.start representing the same memory +// location and size as the memory location LI loads from, and also the +// invariant.start has no uses. static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT, Loop *CurLoop) { Value *Addr = LI->getOperand(0); @@ -950,7 +967,7 @@ namespace { class LoopPromoter : public LoadAndStorePromoter { Value *SomePtr; // Designated pointer to store to. - SmallPtrSetImpl &PointerMustAliases; + const SmallSetVector &PointerMustAliases; SmallVectorImpl &LoopExitBlocks; SmallVectorImpl &LoopInsertPts; PredIteratorCache &PredCache; @@ -978,7 +995,7 @@ public: LoopPromoter(Value *SP, ArrayRef Insts, SSAUpdater &S, - SmallPtrSetImpl &PMA, + const SmallSetVector &PMA, SmallVectorImpl &LEB, SmallVectorImpl &LIP, PredIteratorCache &PIC, AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment, @@ -986,7 +1003,7 @@ : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA), LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast), LI(li), DL(std::move(dl)), Alignment(alignment), - UnorderedAtomic(UnorderedAtomic),AATags(AATags) {} + UnorderedAtomic(UnorderedAtomic), AATags(AATags) {} bool isInstInList(Instruction *I, const SmallVectorImpl &) const override { @@ -1025,7 +1042,7 @@ } void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); } }; -} // end anon namespace +} // namespace /// 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 @@ -1033,7 +1050,8 @@ /// loop invariant. /// bool llvm::promoteLoopAccessesToScalars( - AliasSet &AS, SmallVectorImpl &ExitBlocks, + const SmallSetVector &PointerMustAliases, + SmallVectorImpl &ExitBlocks, SmallVectorImpl &InsertPts, PredIteratorCache &PIC, LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, @@ -1043,17 +1061,7 @@ CurAST != nullptr && SafetyInfo != nullptr && "Unexpected Input to promoteLoopAccessesToScalars"); - // 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 false; - - assert(!AS.empty() && - "Must alias set should have at least one pointer element in it!"); - - Value *SomePtr = AS.begin()->getValue(); + Value *SomePtr = *PointerMustAliases.begin(); BasicBlock *Preheader = CurLoop->getLoopPreheader(); // It isn't safe to promote a load/store from the loop if the load/store is @@ -1082,8 +1090,8 @@ // is safe (i.e. proving dereferenceability on all paths through the loop). We // can use any access within the alias set to prove dereferenceability, // since they're all must alias. - // - // There are two ways establish (p2): + // + // There are two ways establish (p2): // a) Prove the location is thread-local. In this case the memory model // requirement does not apply, and stores are safe to insert. // b) Prove a store dominates every exit block. In this case, if an exit @@ -1097,13 +1105,12 @@ bool SafeToInsertStore = false; SmallVector LoopUses; - SmallPtrSet PointerMustAliases; // We start with an alignment of one and try to find instructions that allow // us to prove better alignment. unsigned Alignment = 1; // Keep track of which types of access we see - bool SawUnorderedAtomic = false; + bool SawUnorderedAtomic = false; bool SawNotAtomic = false; AAMDNodes AATags; @@ -1124,15 +1131,16 @@ // If this is a base pointer we do not understand, simply bail. // We only handle alloca and return value from alloc-like fn right now. if (!isa(Object)) { - if (!isAllocLikeFn(Object, TLI)) - return false; - // If this is an alloc like fn. There are more constraints we need to verify. - // More specifically, we must make sure that the pointer can not escape. + if (!isAllocLikeFn(Object, TLI)) + return false; + // If this is an alloc like fn. There are more constraints we need to + // verify. More specifically, we must make sure that the pointer can not + // escape. // - // NOTE: PointerMayBeCaptured is not enough as the pointer may have escaped - // even though its not captured by the enclosing function. Standard allocation - // functions like malloc, calloc, and operator new return values which can - // be assumed not to have previously escaped. + // NOTE: PointerMayBeCaptured is not enough as the pointer may have + // escaped even though its not captured by the enclosing function. + // Standard allocation functions like malloc, calloc, and operator new + // return values which can be assumed not to have previously escaped. if (PointerMayBeCaptured(Object, true, true)) return false; IsKnownNonEscapingObject = true; @@ -1142,10 +1150,7 @@ // Check that all of the pointers in the alias set have the same type. We // cannot (yet) promote a memory location that is loaded and stored in // different sizes. While we are at it, collect alignment and AA info. - for (const auto &ASI : AS) { - Value *ASIV = ASI.getValue(); - PointerMustAliases.insert(ASIV); - + for (Value *ASIV : PointerMustAliases) { // Check that all of the pointers in the alias set have the same type. We // cannot (yet) promote a memory location that is loaded and stored in // different sizes. @@ -1164,7 +1169,7 @@ assert(!Load->isVolatile() && "AST broken"); if (!Load->isUnordered()) return false; - + SawUnorderedAtomic |= Load->isAtomic(); SawNotAtomic |= !Load->isAtomic(); @@ -1257,8 +1262,8 @@ else { Value *Object = GetUnderlyingObject(SomePtr, MDL); SafeToInsertStore = - (isAllocLikeFn(Object, TLI) || isa(Object)) && - !PointerMayBeCaptured(Object, true, true); + (isAllocLikeFn(Object, TLI) || isa(Object)) && + !PointerMayBeCaptured(Object, true, true); } } @@ -1350,7 +1355,7 @@ auto mergeLoop = [&](Loop *L) { // Loop over the body of this loop, looking for calls, invokes, and stores. for (BasicBlock *BB : L->blocks()) - CurAST->add(*BB); // Incorporate the specified basic block + CurAST->add(*BB); // Incorporate the specified basic block }; // Add everything from the sub loops that are no longer directly available.