Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -159,7 +159,7 @@ void initializeIntervalPartitionPass(PassRegistry&); void initializeJumpThreadingPass(PassRegistry&); void initializeLCSSAWrapperPassPass(PassRegistry &); -void initializeLICMPass(PassRegistry&); +void initializeLegacyLICMPassPass(PassRegistry&); void initializeLazyValueInfoWrapperPassPass(PassRegistry&); void initializeLintPass(PassRegistry&); void initializeLiveDebugValuesPass(PassRegistry&); Index: include/llvm/Transforms/Scalar/LICM.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/LICM.h @@ -0,0 +1,48 @@ +//===- LICM.h - Loop Invariant Code Motion Pass -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs loop invariant code motion, attempting to remove as much +// code from the body of a loop as possible. It does this by either hoisting +// code into the preheader block, or by sinking code to the exit blocks if it is +// safe. This pass also promotes must-aliased memory locations in the loop to +// live in registers, thus hoisting and sinking "invariant" loads and stores. +// +// This pass uses alias analysis for two purposes: +// +// 1. Moving loop invariant loads and calls out of loops. If we can determine +// that a load or call inside of a loop never aliases anything stored to, +// we can hoist it or sink it like any other instruction. +// 2. Scalar Promotion of Memory - If there is a store instruction inside of +// the loop, we try to move the store to happen AFTER the loop instead of +// inside of the loop. This can only happen if a few conditions are true: +// A. The pointer stored through is loop invariant +// B. There are no stores or loads in the loop which _may_ alias the +// pointer. There are no calls in the loop which mod/ref the pointer. +// If these conditions are true, we can promote the loads and stores in the +// loop of the pointer to use a temporary alloca'd variable. We then use +// the SSAUpdater to construct the appropriate SSA form for the value. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LICM_H +#define LLVM_TRANSFORMS_SCALAR_LICM_H + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Performs Loop Invariant Code Motion Pass. +class LICMPass : public PassInfoMixin { +public: + PreservedAnalyses run(Loop &L, AnalysisManager &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LICM_H Index: lib/LTO/LTOCodeGenerator.cpp =================================================================== --- lib/LTO/LTOCodeGenerator.cpp +++ lib/LTO/LTOCodeGenerator.cpp @@ -122,7 +122,7 @@ initializePostOrderFunctionAttrsLegacyPassPass(R); initializeReversePostOrderFunctionAttrsLegacyPassPass(R); initializeGlobalsAAWrapperPassPass(R); - initializeLICMPass(R); + initializeLegacyLICMPassPass(R); initializeMergedLoadStoreMotionLegacyPassPass(R); initializeGVNLegacyPassPass(R); initializeMemCpyOptLegacyPassPass(R); Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -30,6 +30,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/LICM.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" @@ -40,6 +41,7 @@ #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/LoopPassManager.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" @@ -104,13 +106,39 @@ LoopSafetyInfo *SafetyInfo); namespace { -struct LICM : public LoopPass { +struct LoopInvariantCodeMotion { + bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, + TargetLibraryInfo *TLI, ScalarEvolution *SE, bool DeleteAST); + + DenseMap &getLoopToAliasSetMap() { + return LoopToAliasSetMap; + } + +private: + DenseMap LoopToAliasSetMap; + + AliasSetTracker *collectAliasInfoForLoop(Loop *L, LoopInfo *LI, + AliasAnalysis *AA); +}; + +struct LegacyLICMPass : public LoopPass { static char ID; // Pass identification, replacement for typeid - LICM() : LoopPass(ID) { - initializeLICMPass(*PassRegistry::getPassRegistry()); + LegacyLICMPass() : LoopPass(ID) { + initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry()); } - bool runOnLoop(Loop *L, LPPassManager &LPM) override; + bool runOnLoop(Loop *L, LPPassManager &LPM) override { + if (skipLoop(L)) + return false; + + auto *SE = getAnalysisIfAvailable(); + return LICM.runOnLoop(L, + &getAnalysis().getAAResults(), + &getAnalysis().getLoopInfo(), + &getAnalysis().getDomTree(), + &getAnalysis().getTLI(), + SE ? &SE->getSE() : nullptr, false); + } /// This transformation requires natural loop information & requires that /// loop preheaders be inserted into the CFG... @@ -124,23 +152,13 @@ using llvm::Pass::doFinalization; bool doFinalization() override { - assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets"); + assert(LICM.getLoopToAliasSetMap().empty() && + "Didn't free loop alias sets"); return false; } private: - AliasAnalysis *AA; // Current AliasAnalysis information - LoopInfo *LI; // Current LoopInfo - DominatorTree *DT; // Dominator Tree for the current Loop. - - TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding. - - // State that is updated as we process loops. - bool Changed; // Set to true when we change anything. - BasicBlock *Preheader; // The preheader block of the current loop... - Loop *CurLoop; // The current loop we are working on... - AliasSetTracker *CurAST; // AliasSet information for the current loop... - DenseMap LoopToAliasSetMap; + LoopInvariantCodeMotion LICM; /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, @@ -152,48 +170,65 @@ /// Simple Analysis hook. Delete loop L from alias set map. void deleteAnalysisLoop(Loop *L) override; - - AliasSetTracker *collectAliasInfoForLoop(Loop *L); }; } -char LICM::ID = 0; -INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) +PreservedAnalyses LICMPass::run(Loop &L, AnalysisManager &AM) { + // FIXME: Check if loop should be skipped. + + const auto &FAM = + AM.getResult(L).getManager(); + Function *F = L.getHeader()->getParent(); + + auto *AA = FAM.getCachedResult(*F); + auto *LI = FAM.getCachedResult(*F); + auto *DT = FAM.getCachedResult(*F); + auto *TLI = FAM.getCachedResult(*F); + auto *SE = FAM.getCachedResult(*F); + assert((AA && LI && DT && TLI && SE) && "Analyses for LICM not available"); + + LoopInvariantCodeMotion LICM; + + if (!LICM.runOnLoop(&L, AA, LI, DT, TLI, SE, true)) + return PreservedAnalyses::all(); + + // FIXME: There is no setPreservesCFG in the new PM. When that becomes + // available, it should be used here. + return getLoopPassPreservedAnalyses(); +} + +char LegacyLICMPass::ID = 0; +INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion", + false, false) INITIALIZE_PASS_DEPENDENCY(LoopPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false) +INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false, + false) -Pass *llvm::createLICMPass() { return new LICM(); } +Pass *llvm::createLICMPass() { return new LegacyLICMPass(); } /// Hoist expressions out of the specified loop. Note, alias info for inner /// loop is not preserved so it is not a good idea to run LICM multiple /// times on one loop. +/// We should delete AST for inner loops in the new pass manager to avoid +/// memory leak. /// -bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { - if (skipLoop(L)) - return false; - - Changed = false; - - // Get our Loop and Alias Analysis information... - LI = &getAnalysis().getLoopInfo(); - AA = &getAnalysis().getAAResults(); - DT = &getAnalysis().getDomTree(); - - TLI = &getAnalysis().getTLI(); +bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA, + LoopInfo *LI, DominatorTree *DT, + TargetLibraryInfo *TLI, + ScalarEvolution *SE, bool DeleteAST) { + bool Changed = false; assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."); - CurAST = collectAliasInfoForLoop(L); - - CurLoop = L; + AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA); // Get the preheader block to move instructions into... - Preheader = L->getLoopPreheader(); + BasicBlock *Preheader = L->getLoopPreheader(); // Compute loop safety information. LoopSafetyInfo SafetyInfo; - computeLoopSafetyInfo(&SafetyInfo, CurLoop); + computeLoopSafetyInfo(&SafetyInfo, L); // We want to visit all of the instructions in this loop... that are not parts // of our subloops (they have already had their invariants hoisted out of @@ -206,11 +241,11 @@ // instructions, we perform another pass to hoist them out of the loop. // if (L->hasDedicatedExits()) - Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop, + Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L, CurAST, &SafetyInfo); if (Preheader) - Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, - CurLoop, CurAST, &SafetyInfo); + Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L, + CurAST, &SafetyInfo); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can. @@ -221,9 +256,8 @@ // Loop over all of the alias sets in the tracker object. for (AliasSet &AS : *CurAST) - Changed |= - promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts, PIC, LI, DT, - TLI, CurLoop, CurAST, &SafetyInfo); + Changed |= promoteLoopAccessesToScalars( + AS, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L, CurAST, &SafetyInfo); // 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 @@ -232,8 +266,7 @@ // SSAUpdater strategy during promotion that was LCSSA aware and reformed // it as it went. if (Changed) { - auto *SEWP = getAnalysisIfAvailable(); - formLCSSARecursively(*L, *DT, LI, SEWP ? &SEWP->getSE() : nullptr); + formLCSSARecursively(*L, *DT, LI, SE); } } @@ -244,20 +277,15 @@ assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) && "Parent loop not left in LCSSA form after LICM!"); - // Clear out loops state information for the next iteration - CurLoop = nullptr; - Preheader = nullptr; - // If this loop is nested inside of another one, save the alias information // for when we process the outer loop. - if (L->getParentLoop()) + if (L->getParentLoop() && !DeleteAST) LoopToAliasSetMap[L] = CurAST; else delete CurAST; - if (Changed) - if (auto *SEWP = getAnalysisIfAvailable()) - SEWP->getSE().forgetLoopDispositions(L); + if (Changed && SE) + SE->forgetLoopDispositions(L); return Changed; } @@ -387,7 +415,8 @@ // 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->HeaderMayThrow |= + !isGuaranteedToTransferExecutionToSuccessor(&*I); SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow; // Iterate over loop instructions and compute safety info. @@ -1042,7 +1071,13 @@ /// Returns an owning pointer to an alias set which incorporates aliasing info /// from L and all subloops of L. -AliasSetTracker *LICM::collectAliasInfoForLoop(Loop *L) { +/// FIXME: In new pass manager, there is no helper functions to handle loop +/// analysis such as cloneBasicBlockAnalysis. So the AST needs to be recompute +/// from scratch for every loop. Hook up with the helper functions when +/// available in the new pass manager to avoid redundant computation. +AliasSetTracker * +LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI, + AliasAnalysis *AA) { AliasSetTracker *CurAST = nullptr; SmallVector RecomputeLoops; for (Loop *InnerL : L->getSubLoops()) { @@ -1092,8 +1127,9 @@ /// Simple analysis hook. Clone alias set info. /// -void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { - AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); +void LegacyLICMPass::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, + Loop *L) { + AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L); if (!AST) return; @@ -1102,8 +1138,8 @@ /// Simple Analysis hook. Delete value V from alias set /// -void LICM::deleteAnalysisValue(Value *V, Loop *L) { - AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); +void LegacyLICMPass::deleteAnalysisValue(Value *V, Loop *L) { + AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L); if (!AST) return; @@ -1112,13 +1148,13 @@ /// Simple Analysis hook. Delete value L from alias set map. /// -void LICM::deleteAnalysisLoop(Loop *L) { - AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); +void LegacyLICMPass::deleteAnalysisLoop(Loop *L) { + AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L); if (!AST) return; delete AST; - LoopToAliasSetMap.erase(L); + LICM.getLoopToAliasSetMap().erase(L); } /// Return true if the body of this loop may store into the memory Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -48,7 +48,7 @@ initializeInductiveRangeCheckEliminationPass(Registry); initializeIndVarSimplifyLegacyPassPass(Registry); initializeJumpThreadingPass(Registry); - initializeLICMPass(Registry); + initializeLegacyLICMPassPass(Registry); initializeLoopDataPrefetchPass(Registry); initializeLoopDeletionPass(Registry); initializeLoopAccessLegacyAnalysisPass(Registry); Index: test/Transforms/LICM/argmemonly-call.ll =================================================================== --- test/Transforms/LICM/argmemonly-call.ll +++ test/Transforms/LICM/argmemonly-call.ll @@ -1,4 +1,5 @@ ; RUN: opt -S -basicaa -licm %s | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,loop(licm)' < %s -S | FileCheck %s declare i32 @foo() readonly argmemonly nounwind declare i32 @foo2() readonly nounwind declare i32 @bar(i32* %loc2) readonly argmemonly nounwind Index: test/Transforms/LICM/assume.ll =================================================================== --- test/Transforms/LICM/assume.ll +++ test/Transforms/LICM/assume.ll @@ -1,4 +1,5 @@ ; RUN: opt -licm -basicaa < %s -S | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,loop(licm)' < %s -S | FileCheck %s define void @f_0(i1 %p) nounwind ssp { ; CHECK-LABEL: @f_0( Index: test/Transforms/LICM/atomics.ll =================================================================== --- test/Transforms/LICM/atomics.ll +++ test/Transforms/LICM/atomics.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -S -basicaa -licm | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -passes='lcssa,require,require,require,loop(licm)' < %s -S | FileCheck %s ; Check that we can hoist unordered loads define i32 @test1(i32* nocapture %y) nounwind uwtable ssp { Index: test/Transforms/LICM/basictest.ll =================================================================== --- test/Transforms/LICM/basictest.ll +++ test/Transforms/LICM/basictest.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -licm | llvm-dis +; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,loop(licm)' < %s | llvm-dis define void @testfunc(i32 %i) { ;