Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -38,6 +38,8 @@ class DataLayout; class Loop; class LoopInfo; +class MemorySSA; +class MemorySSAUpdater; class OptimizationRemarkEmitter; class PredicatedScalarEvolution; class PredIteratorCache; @@ -437,8 +439,8 @@ /// arguments. Diagnostics is emitted via \p ORE. It returns changed status. bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, - AliasSetTracker *, LoopSafetyInfo *, - OptimizationRemarkEmitter *ORE); + AliasSetTracker *, LoopSafetyInfo *, MemorySSAUpdater *, + MemorySSA *, OptimizationRemarkEmitter *ORE); /// \brief 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 @@ -450,7 +452,8 @@ /// ORE. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - LoopSafetyInfo *, OptimizationRemarkEmitter *ORE); + LoopSafetyInfo *, MemorySSAUpdater *, MemorySSA *, + OptimizationRemarkEmitter *); /// This function deletes dead loops. The caller of this function needs to /// guarantee that the loop is infact dead. @@ -536,6 +539,7 @@ bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE = nullptr); /// Generates a vector reduction using shufflevectors to reduce the value. Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -1,4 +1,4 @@ -//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// + // // The LLVM Compiler Infrastructure // @@ -43,6 +43,7 @@ #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" @@ -89,15 +90,36 @@ cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)")); +// Experimental option to allow imprecision in LICM (use MemorySSA cap) in +// pathological cases, in exchange for faster compile. This is to be removed +// if MemorySSA starts to address the same issue. + +// [Verbose] This flag applies only when LICM uses MemorySSA instead on +// AliasSetTracker. +// When flag is disabled (default), LICM calls MemorySSAWalker's getClobberingMemoryAccess, which gets perfect accuracy. +// When flag is enabled, LICM will call into MemorySSA's +// getDefiningAccess, which may not be precise, since optimizeUses is capped. +// This means that doing sink, hoist and promotion will not incur a performance +// penalty for loops with large load and store count. For the updates done by +// sink/hoist/promotion (insertUse, moveToPlace), we will need to *explicitly* +// call getClobberingMemoryAccesses. This will get perfect +// results for small tests, and imprecise but fast for large ones. +static cl::opt EnableLicmCap( + "enable-licm-cap", cl::init(false), cl::Hidden, + cl::desc("Enable imprecision in LICM (uses MemorySSA cap) in " + "pathological cases, in exchange for faster compile")); + static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI); static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, TargetTransformInfo *TTI, bool &FreeInLoop); static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE); static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE, bool FreeInLoop); static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, @@ -108,10 +130,18 @@ static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, const AAMDNodes &AAInfo, AliasSetTracker *CurAST); +static bool pointerInvalidatedByLoopWithMSSA(Value *V, MemorySSA *MSSA, + MemoryUseOrDef *MUD, + Loop *CurLoop); +static void removeFromMSSA(Instruction *I, MemorySSAUpdater *MSSAUpdater, + MemorySSA *MSSA); +static void removeFromAnalyses(Instruction *I, AliasSetTracker *CurAST, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA); static Instruction * CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, - const LoopSafetyInfo *SafetyInfo); + const LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA); namespace { struct LoopInvariantCodeMotion { @@ -250,7 +280,16 @@ assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."); - AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA); + AliasSetTracker *CurAST = nullptr; + std::unique_ptr MSSAUpdater; + + if (!MSSA) { + DEBUG(dbgs() << "LICM: Using Alias Set Tracker\n"); + CurAST = collectAliasInfoForLoop(L, LI, AA); + } else { + DEBUG(dbgs() << "LICM: Using MemorySSA\n"); + MSSAUpdater = make_unique(MSSA); + } // Get the preheader block to move instructions into... BasicBlock *Preheader = L->getLoopPreheader(); @@ -271,10 +310,10 @@ // if (L->hasDedicatedExits()) Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L, - CurAST, &SafetyInfo, ORE); + CurAST, &SafetyInfo, MSSAUpdater.get(), MSSA, ORE); if (Preheader) Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L, - CurAST, &SafetyInfo, ORE); + CurAST, &SafetyInfo, MSSAUpdater.get(), MSSA, ORE); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can. @@ -303,27 +342,30 @@ bool Promoted = false; - // 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() || - 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); + if (CurAST) { + // 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() || + 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); + } } + // FIXME: Promotion initially disabled when using MemorySSA. // Once we have promoted values across the loop body we have to // recursively reform LCSSA as any nested loop may now have values defined @@ -345,12 +387,14 @@ assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) && "Parent loop not left in LCSSA form after LICM!"); - // If this loop is nested inside of another one, save the alias information - // for when we process the outer loop. - if (L->getParentLoop() && !DeleteAST) - LoopToAliasSetMap[L] = CurAST; - else - delete CurAST; + if (CurAST) { + // If this loop is nested inside of another one, save the alias information + // for when we process the outer loop. + if (L->getParentLoop() && !DeleteAST) + LoopToAliasSetMap[L] = CurAST; + else + delete CurAST; + } if (Changed && SE) SE->forgetLoopDispositions(L); @@ -366,11 +410,14 @@ DominatorTree *DT, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && - CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr && + CurLoop != nullptr && SafetyInfo != nullptr && + "Unexpected input to sinkRegion"); + assert(((CurAST != nullptr) ^ (MSSAUpdater != nullptr && MSSA != nullptr)) && "Unexpected input to sinkRegion"); // We want to visit children before parents. We will enque all the parents @@ -394,7 +441,7 @@ if (isInstructionTriviallyDead(&I, TLI)) { DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); ++II; - CurAST->deleteValue(&I); + removeFromAnalyses(&I, CurAST, MSSAUpdater, MSSA); I.eraseFromParent(); Changed = true; continue; @@ -407,11 +454,13 @@ // bool FreeInLoop = false; if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) && - canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE)) { - if (sink(I, LI, DT, CurLoop, SafetyInfo, ORE, FreeInLoop)) { + canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, + MSSAUpdater, MSSA, ORE)) { + if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAUpdater, MSSA, ORE, + FreeInLoop)) { if (!FreeInLoop) { ++II; - CurAST->deleteValue(&I); + removeFromAnalyses(&I, CurAST, MSSAUpdater, MSSA); I.eraseFromParent(); } Changed = true; @@ -430,10 +479,13 @@ bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && - CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr && + CurLoop != nullptr && SafetyInfo != nullptr && + "Unexpected input to hoistRegion"); + assert(((CurAST != nullptr) ^ (MSSAUpdater != nullptr && MSSA != nullptr)) && "Unexpected input to hoistRegion"); // We want to visit parents before children. We will enque all the parents @@ -454,10 +506,11 @@ if (Constant *C = ConstantFoldInstruction( &I, I.getModule()->getDataLayout(), TLI)) { DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); - CurAST->copyValue(&I, C); + if (CurAST) + CurAST->copyValue(&I, C); I.replaceAllUsesWith(C); if (isInstructionTriviallyDead(&I, TLI)) { - CurAST->deleteValue(&I); + removeFromAnalyses(&I, CurAST, MSSAUpdater, MSSA); I.eraseFromParent(); } Changed = true; @@ -482,7 +535,8 @@ I.replaceAllUsesWith(Product); I.eraseFromParent(); - hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE); + hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, MSSAUpdater, MSSA, + ORE); Changed = true; continue; } @@ -492,11 +546,12 @@ // if it is safe to hoist the instruction. // if (CurLoop->hasLoopInvariantOperands(&I) && - canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) && + canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, + MSSAUpdater, MSSA, ORE) && isSafeToExecuteUnconditionally( I, DT, CurLoop, SafetyInfo, ORE, CurLoop->getLoopPreheader()->getTerminator())) - Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE); + Changed |= hoist(I, DT, CurLoop, SafetyInfo, MSSAUpdater, MSSA, ORE); } } @@ -596,6 +651,7 @@ bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) { // SafetyInfo is nullptr if we are checking for sinking from preheader to // loop body. @@ -627,8 +683,13 @@ AAMDNodes AAInfo; LI->getAAMetadata(AAInfo); - bool Invalidated = - pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST); + bool Invalidated; + if (CurAST) + Invalidated = + pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST); + else + Invalidated = pointerInvalidatedByLoopWithMSSA( + LI->getOperand(0), MSSA, MSSA->getMemoryAccess(LI), CurLoop); // Check loop-invariant address because this may also be a sinkable load // whose address is not necessarily loop-invariant. if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand())) @@ -659,21 +720,35 @@ // writes to this memory in the loop, we can hoist or sink. if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) { for (Value *Op : CI->arg_operands()) - if (Op->getType()->isPointerTy() && - pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize, - AAMDNodes(), CurAST)) - return false; + if (Op->getType()->isPointerTy()) { + bool Invalidated; + if (CurAST) + Invalidated = pointerInvalidatedByLoop( + Op, MemoryLocation::UnknownSize, AAMDNodes(), CurAST); + else + Invalidated = pointerInvalidatedByLoopWithMSSA( + Op, MSSA, MSSA->getMemoryAccess(CI), CurLoop); + if (Invalidated) + return false; + } return true; } // If this call only reads from memory and there are no writes to memory // in the loop, we can hoist or sink the call as appropriate. bool FoundMod = false; - for (AliasSet &AS : *CurAST) { - if (!AS.isForwardingAliasSet() && AS.isMod()) { - FoundMod = true; - break; + if (CurAST) { + for (AliasSet &AS : *CurAST) { + if (!AS.isForwardingAliasSet() && AS.isMod()) { + FoundMod = true; + break; + } } } + else + FoundMod = + llvm::any_of(CurLoop->blocks(), [MSSA](const BasicBlock *BB) { + return MSSA->getBlockDefs(BB) != nullptr; + }); if (!FoundMod) return true; } @@ -780,7 +855,8 @@ static Instruction * CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI, - const LoopSafetyInfo *SafetyInfo) { + const LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA) { Instruction *New; if (auto *CI = dyn_cast(&I)) { const auto &BlockColors = SafetyInfo->BlockColors; @@ -816,6 +892,24 @@ if (!I.getName().empty()) New->setName(I.getName() + ".le"); + MemoryAccess *OldMemAcc; + if (MSSA && (OldMemAcc = MSSA->getMemoryAccess(&I))) { + // Create a new MemoryAccess and let MemorySSA set its defining access. + MemoryAccess *NewMemAcc = MSSAUpdater->createMemoryAccessInBB( + New, nullptr, New->getParent(), MemorySSA::Beginning); + if (NewMemAcc) { + if (auto* MemDef = dyn_cast(NewMemAcc)) + MSSAUpdater->insertDef(MemDef, /*RenameUses=*/true); + else { + auto *MemUse = cast(NewMemAcc); + MSSAUpdater->insertUse(MemUse); + // This is only called to properly update the defining access. + if (EnableLicmCap) + MSSA->getWalker()->getClobberingMemoryAccess(MemUse); + } + } + } + // Build LCSSA PHI nodes for any in-loop operands. Note that this is // particularly cheap because we can rip off the PHI node that we're // replacing for the number and blocks of the predecessors. @@ -841,7 +935,8 @@ static Instruction *sinkThroughTriviallyReplacablePHI( PHINode *TPN, Instruction *I, LoopInfo *LI, SmallDenseMap &SunkCopies, - const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop) { + const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA) { assert(isTriviallyReplacablePHI(*TPN, *I) && "Expect only trivially replacalbe PHI"); BasicBlock *ExitBlock = TPN->getParent(); @@ -850,8 +945,8 @@ if (It != SunkCopies.end()) New = It->second; else - New = SunkCopies[ExitBlock] = - CloneInstructionInExitBlock(*I, *ExitBlock, *TPN, LI, SafetyInfo); + New = SunkCopies[ExitBlock] = CloneInstructionInExitBlock( + *I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAUpdater, MSSA); return New; } @@ -928,6 +1023,7 @@ /// static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE, bool FreeInLoop) { DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); ORE->emit([&]() { @@ -1015,8 +1111,8 @@ assert(ExitBlockSet.count(PN->getParent()) && "The LCSSA PHI is not in an exit block!"); // The PHI must be trivially replacable. - Instruction *New = sinkThroughTriviallyReplacablePHI(PN, &I, LI, SunkCopies, - SafetyInfo, CurLoop); + Instruction *New = sinkThroughTriviallyReplacablePHI( + PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAUpdater, MSSA); PN->replaceAllUsesWith(New); PN->eraseFromParent(); Changed = true; @@ -1029,6 +1125,7 @@ /// static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) { auto *Preheader = CurLoop->getLoopPreheader(); DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I @@ -1051,6 +1148,17 @@ // Move the new node to the Preheader, before its terminator. I.moveBefore(Preheader->getTerminator()); + if (MSSA) { + // If moving, I just moved a load or store, so update MemorySSA. + MemoryUseOrDef *OldMemAcc = + cast_or_null(MSSA->getMemoryAccess(&I)); + if (OldMemAcc) { + MSSAUpdater->moveToPlace(OldMemAcc, Preheader, MemorySSA::End); + // This is only called to properly update the defining access. + if (EnableLicmCap) + MSSA->getWalker()->getClobberingMemoryAccess(OldMemAcc); + } + } // Do not retain debug locations when we are moving instructions to different // basic blocks, because we want to avoid jumpy line tables. Calls, however, @@ -1548,10 +1656,33 @@ static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, const AAMDNodes &AAInfo, AliasSetTracker *CurAST) { + assert(V->getType()->isPointerTy() && "Value tested is not a pointer."); // Check to see if any of the basic blocks in CurLoop invalidate *V. return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod(); } +static bool pointerInvalidatedByLoopWithMSSA(Value *V, MemorySSA *MSSA, + MemoryUseOrDef *MUD, + Loop *CurLoop) { + assert(V->getType()->isPointerTy() && "Value tested is not a pointer."); + if (isa(V)) + return true; + + // MUD is from a LoopInstr or CallInstr, so both Uses. + if (MemoryUse *MU = dyn_cast_or_null(MUD)) { + MemoryAccess *Source; + // See declaration of EnableLicmCap for usage details. + if (EnableLicmCap) + Source = MU->getDefiningAccess(); + else + Source = MSSA->getWalker()->getClobberingMemoryAccess(MU); + if (MSSA->isLiveOnEntryDef(Source) || + !CurLoop->contains(Source->getBlock())) + return false; + } + return true; +} + /// Little predicate that returns true if the specified basic block is in /// a subloop of the current one, not the current one itself. /// @@ -1559,3 +1690,17 @@ assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); return LI->getLoopFor(BB) != CurLoop; } + +static void removeFromMSSA(Instruction *I, MemorySSAUpdater *MSSAUpdater, + MemorySSA *MSSA) { + if (MemoryUseOrDef *AccI = MSSA->getMemoryAccess(I)) + MSSAUpdater->removeMemoryAccess(AccI); +} + +static void removeFromAnalyses(Instruction *I, AliasSetTracker *CurAST, + MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA) { + if (CurAST) + CurAST->deleteValue(I); + else + removeFromMSSA(I, MSSAUpdater, MSSA); +} Index: lib/Transforms/Scalar/LoopSink.cpp =================================================================== --- lib/Transforms/Scalar/LoopSink.cpp +++ lib/Transforms/Scalar/LoopSink.cpp @@ -288,7 +288,8 @@ // No need to check for instruction's operands are loop invariant. assert(L.hasLoopInvariantOperands(I) && "Insts in a loop's preheader should have loop invariant operands!"); - if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr)) + if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, /*MSSA=*/nullptr, + /*MSSAUpdater=*/nullptr, nullptr)) continue; if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI)) Changed = true; Index: test/Transforms/LICM/hoist-bitcast-load.ll =================================================================== --- test/Transforms/LICM/hoist-bitcast-load.ll +++ test/Transforms/LICM/hoist-bitcast-load.ll @@ -1,5 +1,6 @@ ; RUN: opt -S -basicaa -licm < %s | FileCheck %s ; RUN: opt -aa-pipeline=basic-aa -passes='require,loop(simplify-cfg,licm)' -S < %s | FileCheck %s +; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true < %s | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" Index: test/Transforms/LICM/hoist-deref-load.ll =================================================================== --- test/Transforms/LICM/hoist-deref-load.ll +++ test/Transforms/LICM/hoist-deref-load.ll @@ -1,5 +1,6 @@ ; RUN: opt -S -basicaa -licm < %s | FileCheck %s ; RUN: opt -aa-pipeline=basic-aa -passes='require,loop(simplify-cfg,licm)' -S < %s | FileCheck %s +; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true < %s | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" Index: test/Transforms/LICM/hoist-fast-fdiv.ll =================================================================== --- test/Transforms/LICM/hoist-fast-fdiv.ll +++ test/Transforms/LICM/hoist-fast-fdiv.ll @@ -1,4 +1,5 @@ ; RUN: opt -licm -S < %s | FileCheck %s +; RUN: opt -licm -S -enable-mssa-loop-dependency=true < %s | FileCheck %s ; Function Attrs: noinline norecurse nounwind readnone ssp uwtable define zeroext i1 @f(double %v) #0 { Index: test/Transforms/LICM/hoist-invariant-load.ll =================================================================== --- test/Transforms/LICM/hoist-invariant-load.ll +++ test/Transforms/LICM/hoist-invariant-load.ll @@ -1,5 +1,6 @@ ; REQUIRES: asserts ; RUN: opt < %s -licm -disable-basicaa -stats -S 2>&1 | grep "1 licm" +; RUN: opt < %s -licm -disable-basicaa -stats -S -enable-mssa-loop-dependency=true 2>&1 | grep "1 licm" @"\01L_OBJC_METH_VAR_NAME_" = internal global [4 x i8] c"foo\00", section "__TEXT,__objc_methname,cstring_literals", align 1 @"\01L_OBJC_SELECTOR_REFERENCES_" = internal global i8* getelementptr inbounds ([4 x i8], [4 x i8]* @"\01L_OBJC_METH_VAR_NAME_", i32 0, i32 0), section "__DATA, __objc_selrefs, literal_pointers, no_dead_strip" Index: test/Transforms/LICM/hoist-nounwind.ll =================================================================== --- test/Transforms/LICM/hoist-nounwind.ll +++ test/Transforms/LICM/hoist-nounwind.ll @@ -1,5 +1,6 @@ ; RUN: opt -S -basicaa -licm < %s | FileCheck %s ; RUN: opt -aa-pipeline=basic-aa -passes='require,loop(licm)' -S %s | FileCheck %s +; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true < %s | FileCheck %s target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" Index: test/Transforms/LICM/hoist-round.ll =================================================================== --- test/Transforms/LICM/hoist-round.ll +++ test/Transforms/LICM/hoist-round.ll @@ -1,5 +1,6 @@ ; RUN: opt -S -licm < %s | FileCheck %s ; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,require,loop(licm)' -S %s | FileCheck %s +; RUN: opt -S -licm -enable-mssa-loop-dependency=true < %s | FileCheck %s target datalayout = "E-m:e-p:32:32-i8:8:8-i16:16:16-i64:32:32-f64:32:32-v64:32:32-v128:32:32-a0:0:32-n32" Index: test/Transforms/LICM/hoisting.ll =================================================================== --- test/Transforms/LICM/hoisting.ll +++ test/Transforms/LICM/hoisting.ll @@ -1,5 +1,6 @@ ; RUN: opt < %s -licm -S | FileCheck %s ; RUN: opt < %s -aa-pipeline=basic-aa -passes='require,loop(licm)' -S | FileCheck %s +; RUN: opt < %s -licm -enable-mssa-loop-dependency=true -S | FileCheck %s @X = global i32 0 ; [#uses=1] Index: test/Transforms/LICM/sink-promote.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/sink-promote.ll @@ -0,0 +1,47 @@ +; RUN: opt < %s -basicaa -licm -S | FileCheck %s + +; Test moved from sinking.ll, as it tests promotion and sinking. +; Can't sink stores out of exit blocks containing indirectbr instructions +; because loop simplify does not create dedicated exits for such blocks. Test +; that by sinking the store from lab21 to lab22, but not further. +define void @test12() { +; CHECK-LABEL: @test12 + br label %lab4 + +lab4: + br label %lab20 + +lab5: + br label %lab20 + +lab6: + br label %lab4 + +lab7: + br i1 undef, label %lab8, label %lab13 + +lab8: + br i1 undef, label %lab13, label %lab10 + +lab10: + br label %lab7 + +lab13: + ret void + +lab20: + br label %lab21 + +lab21: +; CHECK: lab21: +; CHECK-NOT: store +; CHECK: br i1 false, label %lab21, label %lab22 + store i32 36127957, i32* undef, align 4 + br i1 undef, label %lab21, label %lab22 + +lab22: +; CHECK: lab22: +; CHECK: store +; CHECK-NEXT: indirectbr i8* undef + indirectbr i8* undef, [label %lab5, label %lab6, label %lab7] +} Index: test/Transforms/LICM/sink.ll =================================================================== --- test/Transforms/LICM/sink.ll +++ test/Transforms/LICM/sink.ll @@ -2,6 +2,7 @@ ; RUN: opt -S -licm < %s | opt -S -loop-sink | FileCheck %s --check-prefix=CHECK-SINK ; RUN: opt -S < %s -passes='require,loop(licm),loop-sink' \ ; RUN: | FileCheck %s --check-prefix=CHECK-SINK +; RUN: opt -S -licm -enable-mssa-loop-dependency=true < %s | FileCheck %s --check-prefix=CHECK-LICM ; Original source code: ; int g; Index: test/Transforms/LICM/sinking.ll =================================================================== --- test/Transforms/LICM/sinking.ll +++ test/Transforms/LICM/sinking.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -basicaa -licm -S | FileCheck %s +; RUN: opt < %s -basicaa -licm -S -enable-mssa-loop-dependency=true | FileCheck %s declare i32 @strlen(i8*) readonly nounwind @@ -314,50 +315,7 @@ ret i32 %lcssa } -; Can't sink stores out of exit blocks containing indirectbr instructions -; because loop simplify does not create dedicated exits for such blocks. Test -; that by sinking the store from lab21 to lab22, but not further. -define void @test12() { -; CHECK-LABEL: @test12 - br label %lab4 - -lab4: - br label %lab20 - -lab5: - br label %lab20 - -lab6: - br label %lab4 - -lab7: - br i1 undef, label %lab8, label %lab13 - -lab8: - br i1 undef, label %lab13, label %lab10 - -lab10: - br label %lab7 - -lab13: - ret void - -lab20: - br label %lab21 - -lab21: -; CHECK: lab21: -; CHECK-NOT: store -; CHECK: br i1 false, label %lab21, label %lab22 - store i32 36127957, i32* undef, align 4 - br i1 undef, label %lab21, label %lab22 - -lab22: -; CHECK: lab22: -; CHECK: store -; CHECK-NEXT: indirectbr i8* undef - indirectbr i8* undef, [label %lab5, label %lab6, label %lab7] -} +; @test12 moved to sink-promote.ll, as it tests sinking and promotion. ; Test that we don't crash when trying to sink stores and there's no preheader ; available (which is used for creating loads that may be used by the SSA Index: test/Transforms/LICM/volatile-alias.ll =================================================================== --- test/Transforms/LICM/volatile-alias.ll +++ test/Transforms/LICM/volatile-alias.ll @@ -1,5 +1,6 @@ ; RUN: opt -basicaa -sroa -loop-rotate -licm -S < %s | FileCheck %s ; RUN: opt -basicaa -sroa -loop-rotate %s | opt -aa-pipeline=basic-aa -passes='require,require,require,require,loop(licm)' -S | FileCheck %s +; RUN: opt -basicaa -sroa -loop-rotate -licm -enable-mssa-loop-dependency=true -S < %s | FileCheck %s ; The objects *p and *q are aliased to each other, but even though *q is ; volatile, *p can be considered invariant in the loop. Check if it is moved ; out of the loop.