Index: llvm/lib/Transforms/Scalar/LICM.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LICM.cpp +++ llvm/lib/Transforms/Scalar/LICM.cpp @@ -176,6 +176,9 @@ ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater *MSSAU, ScalarEvolution *SE); +static SmallVector, 0> +collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L); + namespace { struct LoopInvariantCodeMotion { bool runOnLoop(Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT, @@ -194,9 +197,6 @@ std::unique_ptr collectAliasInfoForLoop(Loop *L, LoopInfo *LI, AAResults *AA); - std::unique_ptr - collectAliasInfoForLoopWithMSSA(Loop *L, AAResults *AA, - MemorySSAUpdater *MSSAU); }; struct LegacyLICMPass : public LoopPass { @@ -405,31 +405,35 @@ PredIteratorCache PIC; bool Promoted = false; - - // Build an AST using MSSA. - if (!CurAST.get()) - CurAST = collectAliasInfoForLoopWithMSSA(L, AA, MSSAU.get()); - - // Loop over all of the alias sets in the tracker object. - 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() || - !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, MSSAInsertPts, PIC, LI, - DT, TLI, L, CurAST.get(), MSSAU.get(), &SafetyInfo, ORE); + if (CurAST.get()) { + // Loop over all of the alias sets in the tracker object. + 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() || + !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, MSSAInsertPts, PIC, LI, + DT, TLI, L, CurAST.get(), MSSAU.get(), &SafetyInfo, ORE); + } + } else { + for (const SmallSetVector &PointerMustAliases : + collectPromotionCandidates(MSSA, AA, L)) { + Promoted |= promoteLoopAccessesToScalars( + PointerMustAliases, ExitBlocks, InsertPts, MSSAInsertPts, PIC, LI, + DT, TLI, L, CurAST.get(), MSSAU.get(), &SafetyInfo, ORE); + } } // Once we have promoted values across the loop body we have to @@ -1782,7 +1786,7 @@ SmallVectorImpl &LoopInsertPts; SmallVectorImpl &MSSAInsertPts; PredIteratorCache &PredCache; - AliasSetTracker &AST; + AliasSetTracker *AST; MemorySSAUpdater *MSSAU; LoopInfo &LI; DebugLoc DL; @@ -1812,7 +1816,7 @@ SmallVectorImpl &LEB, SmallVectorImpl &LIP, SmallVectorImpl &MSSAIP, PredIteratorCache &PIC, - AliasSetTracker &ast, MemorySSAUpdater *MSSAU, LoopInfo &li, + AliasSetTracker *ast, MemorySSAUpdater *MSSAU, LoopInfo &li, DebugLoc dl, int alignment, bool UnorderedAtomic, const AAMDNodes &AATags, ICFLoopSafetyInfo &SafetyInfo) : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA), @@ -1869,11 +1873,13 @@ void replaceLoadWithValue(LoadInst *LI, Value *V) const override { // Update alias analysis. - AST.copyValue(LI, V); + if (AST) + AST->copyValue(LI, V); } void instructionDeleted(Instruction *I) const override { SafetyInfo.removeInstruction(I); - AST.deleteValue(I); + if (AST) + AST->deleteValue(I); if (MSSAU) MSSAU->removeMemoryAccess(I); } @@ -1919,7 +1925,7 @@ ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { // Verify inputs. assert(LI != nullptr && DT != nullptr && CurLoop != nullptr && - CurAST != nullptr && SafetyInfo != nullptr && + SafetyInfo != nullptr && "Unexpected Input to promoteLoopAccessesToScalars"); Value *SomePtr = *PointerMustAliases.begin(); @@ -2147,7 +2153,7 @@ SmallVector NewPHIs; SSAUpdater SSA(&NewPHIs); LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks, - InsertPts, MSSAInsertPts, PIC, *CurAST, MSSAU, *LI, DL, + InsertPts, MSSAInsertPts, PIC, CurAST, MSSAU, *LI, DL, Alignment.value(), SawUnorderedAtomic, AATags, *SafetyInfo); @@ -2186,6 +2192,64 @@ return true; } +static SmallVector, 0> +collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, Loop *L) { + AliasSetTracker AST(*AA); + + auto IsPotentiallyPromotable = [L](const Instruction *I) { + if (const auto *SI = dyn_cast(I)) + return L->isLoopInvariant(SI->getPointerOperand()); + if (const auto *LI = dyn_cast(I)) + return L->isLoopInvariant(LI->getPointerOperand()); + return false; + }; + + // Populate AST with potentially promotable accesses. + for (const BasicBlock *BB : L->blocks()) + if (const auto *Accesses = MSSA->getBlockAccesses(BB)) + for (const auto &Access : *Accesses) + if (const auto *MUD = dyn_cast(&Access)) + if (IsPotentiallyPromotable(MUD->getMemoryInst())) + AST.add(MUD->getMemoryInst()); + + // We're only interested in must-alias sets that contain a mod. + SmallVector Sets; + for (AliasSet &AS : AST) + if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias()) + Sets.push_back(&AS); + + // Discard any sets for which there is an aliasing non-promotable access. + auto CheckAccess = [&](Instruction *I) { + if (Optional Loc = MemoryLocation::getOrNone(I)) { + Sets.erase(llvm::remove_if(Sets, [&](const AliasSet *AS) { + return AS->aliasesPointer(Loc->Ptr, Loc->Size, Loc->AATags, *AA) + != NoAlias; + }), Sets.end()); + } else { + Sets.erase(llvm::remove_if(Sets, [&](const AliasSet *AS) { + return AS->aliasesUnknownInst(I, *AA); + }), Sets.end()); + } + }; + + for (const BasicBlock *BB : L->blocks()) + if (const auto *Accesses = MSSA->getBlockAccesses(BB)) + for (const auto &Access : *Accesses) + if (const auto *MUD = dyn_cast(&Access)) + if (!IsPotentiallyPromotable(MUD->getMemoryInst())) + CheckAccess(MUD->getMemoryInst()); + + SmallVector, 0> Result; + for (const AliasSet *Set : Sets) { + SmallSetVector PointerMustAliases; + for (const auto &ASI : *Set) + PointerMustAliases.insert(ASI.getValue()); + Result.push_back(std::move(PointerMustAliases)); + } + + return Result; +} + /// Returns an owning pointer to an alias set which incorporates aliasing info /// from L and all subloops of L. std::unique_ptr @@ -2206,15 +2270,6 @@ return CurAST; } -std::unique_ptr -LoopInvariantCodeMotion::collectAliasInfoForLoopWithMSSA( - Loop *L, AAResults *AA, MemorySSAUpdater *MSSAU) { - auto *MSSA = MSSAU->getMemorySSA(); - auto CurAST = std::make_unique(*AA, MSSA, L); - CurAST->addAllInstructionsInLoopUsingMSSA(); - return CurAST; -} - static bool pointerInvalidatedByLoop(MemoryLocation MemLoc, AliasSetTracker *CurAST, Loop *CurLoop, AAResults *AA) { Index: llvm/test/Transforms/LICM/2011-04-06-PromoteResultOfPromotion.ll =================================================================== --- llvm/test/Transforms/LICM/2011-04-06-PromoteResultOfPromotion.ll +++ llvm/test/Transforms/LICM/2011-04-06-PromoteResultOfPromotion.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -tbaa -licm -S | FileCheck %s +; RUN: opt < %s -tbaa -licm -enable-mssa-loop-dependency=0 -S | FileCheck %s --check-prefixes=CHECK,AST +; RUN: opt < %s -tbaa -licm -S | FileCheck %s --check-prefixes=CHECK,MSSA ; PR9634 @g_58 = common global i32 0, align 4 @@ -8,8 +9,11 @@ ; CHECK: entry: ; CHECK: alloca [9 x i16] -; CHECK: load i32, i32* @g_58 +; AST: load i32, i32* @g_58 ; CHECK: br label %for.body +; CHECK: for.end: +; CHECK: store i32* @g_58, i32** @g_116 +; AST: store i32 %or.lcssa, i32* @g_58 entry: %l_87.i = alloca [9 x i16], align 16