Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -163,7 +163,7 @@ void initializeIntervalPartitionPass(PassRegistry&); void initializeIRTranslatorPass(PassRegistry &); void initializeJumpThreadingPass(PassRegistry&); -void initializeLCSSAPass(PassRegistry&); +void initializeLCSSAWrapperPassPass(PassRegistry &); void initializeLICMPass(PassRegistry&); void initializeLazyValueInfoPass(PassRegistry&); void initializeLintPass(PassRegistry&); Index: include/llvm/Transforms/Utils/LCSSA.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Utils/LCSSA.h @@ -0,0 +1,44 @@ +//===- LCSSA.h - Loop-closed SSA transform 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 transforms loops by placing phi nodes at the end of the loops for +// all values that are live across the loop boundary. For example, it turns +// the left into the right code: +// +// for (...) for (...) +// if (c) if (c) +// X1 = ... X1 = ... +// else else +// X2 = ... X2 = ... +// X3 = phi(X1, X2) X3 = phi(X1, X2) +// ... = X3 + 4 X4 = phi(X3) +// ... = X4 + 4 +// +// This is still valid LLVM; the extra phi nodes are purely redundant, and will +// be trivially eliminated by InstCombine. The major benefit of this +// transformation is that it makes many other loop optimizations, such as +// LoopUnswitching, simpler. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_LCSSA_H +#define LLVM_TRANSFORMS_UTILS_LCSSA_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Converts loops into loop-closed SSA form. +class LCSSAPass: public PassInfoMixin { +public: + PreservedAnalyses run(Function &F, AnalysisManager &AM); +}; +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LCSSA_H Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -83,6 +83,7 @@ #include "llvm/Transforms/Scalar/SROA.h" #include "llvm/Transforms/Scalar/SimplifyCFG.h" #include "llvm/Transforms/Scalar/Sink.h" +#include "llvm/Transforms/Utils/LCSSA.h" #include "llvm/Transforms/Utils/MemorySSA.h" #include Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -127,6 +127,7 @@ FUNCTION_PASS("guard-widening", GuardWideningPass()) FUNCTION_PASS("gvn", GVN()) FUNCTION_PASS("partially-inline-libcalls", PartiallyInlineLibCallsPass()) +FUNCTION_PASS("lcssa", LCSSAPass()) FUNCTION_PASS("print", PrintFunctionPass(dbgs())) FUNCTION_PASS("print", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print", BlockFrequencyPrinterPass(dbgs())) Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -1300,7 +1300,7 @@ INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) -INITIALIZE_PASS_DEPENDENCY(LCSSA) +INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_END(LoopInterchange, "loop-interchange", Index: lib/Transforms/Scalar/LoopVersioningLICM.cpp =================================================================== --- lib/Transforms/Scalar/LoopVersioningLICM.cpp +++ lib/Transforms/Scalar/LoopVersioningLICM.cpp @@ -585,7 +585,7 @@ INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) -INITIALIZE_PASS_DEPENDENCY(LCSSA) +INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) Index: lib/Transforms/Utils/LCSSA.cpp =================================================================== --- lib/Transforms/Utils/LCSSA.cpp +++ lib/Transforms/Utils/LCSSA.cpp @@ -27,7 +27,7 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/LCSSA.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" @@ -42,6 +42,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/PredIteratorCache.h" #include "llvm/Pass.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/SSAUpdater.h" using namespace llvm; @@ -270,11 +271,20 @@ return Changed; } +/// Process all loops in the function, inner-most out. +static bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT, + ScalarEvolution *SE) { + bool Changed = false; + for (auto &L : *LI) + Changed |= formLCSSARecursively(*L, DT, LI, SE); + return Changed; +} + namespace { -struct LCSSA : public FunctionPass { +struct LCSSAWrapperPass : public FunctionPass { static char ID; // Pass identification, replacement for typeid - LCSSA() : FunctionPass(ID) { - initializeLCSSAPass(*PassRegistry::getPassRegistry()); + LCSSAWrapperPass() : FunctionPass(ID) { + initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry()); } // Cached analysis information for the current function. @@ -302,28 +312,44 @@ }; } -char LCSSA::ID = 0; -INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) +char LCSSAWrapperPass::ID = 0; +INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", + false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) -INITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) - -Pass *llvm::createLCSSAPass() { return new LCSSA(); } -char &llvm::LCSSAID = LCSSA::ID; +INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", + false, false) +Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); } +char &llvm::LCSSAID = LCSSAWrapperPass::ID; -/// Process all loops in the function, inner-most out. -bool LCSSA::runOnFunction(Function &F) { - bool Changed = false; +/// Transform \p F into loop-closed SSA form. +bool LCSSAWrapperPass::runOnFunction(Function &F) { LI = &getAnalysis().getLoopInfo(); DT = &getAnalysis().getDomTree(); auto *SEWP = getAnalysisIfAvailable(); SE = SEWP ? &SEWP->getSE() : nullptr; - // Simplify each loop nest in the function. - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) - Changed |= formLCSSARecursively(**I, *DT, LI, SE); - - return Changed; + return formLCSSAOnAllLoops(LI, *DT, SE); } +PreservedAnalyses LCSSAPass::run(Function &F, AnalysisManager &AM) { + auto &LI = AM.getResult(F); + auto &DT = AM.getResult(F); + auto *SE = AM.getCachedResult(F); + if (!formLCSSAOnAllLoops(&LI, DT, SE)) + return PreservedAnalyses::all(); + + // FIXME: The legacy pass preserves LoopSimplify pass. That pass is not yet + // ported to the new PM and the legacy LoopSimplify pass has a call to + // mustPreserveAnalysisID(LCSSAID) in its runOnFunction method. So, for now, + // we are not preserving LoopSimplify. + // FIXME: There is no setPreservesCFG in the new PM. When that becomes + // available, it should be used here. + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; +} Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -880,7 +880,7 @@ INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) - INITIALIZE_PASS_DEPENDENCY(LCSSA) + INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) Index: lib/Transforms/Utils/Utils.cpp =================================================================== --- lib/Transforms/Utils/Utils.cpp +++ lib/Transforms/Utils/Utils.cpp @@ -24,7 +24,7 @@ initializeAddDiscriminatorsPass(Registry); initializeBreakCriticalEdgesPass(Registry); initializeInstNamerPass(Registry); - initializeLCSSAPass(Registry); + initializeLCSSAWrapperPassPass(Registry); initializeLoopSimplifyPass(Registry); initializeLowerInvokePass(Registry); initializeLowerSwitchPass(Registry); Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -6191,7 +6191,7 @@ INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) -INITIALIZE_PASS_DEPENDENCY(LCSSA) +INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis) Index: test/Transforms/LCSSA/2006-06-03-IncorrectIDFPhis.ll =================================================================== --- test/Transforms/LCSSA/2006-06-03-IncorrectIDFPhis.ll +++ test/Transforms/LCSSA/2006-06-03-IncorrectIDFPhis.ll @@ -1,15 +1,16 @@ -; RUN: opt < %s -loop-simplify -lcssa -S | \ -; RUN: grep "%%SJE.0.0.lcssa = phi .struct.SetJmpMapEntry" +; RUN: opt < %s -loop-simplify -lcssa -S | FileCheck %s %struct.SetJmpMapEntry = type { i8*, i32, %struct.SetJmpMapEntry* } define void @__llvm_sjljeh_try_catching_longjmp_exception() { +; CHECK-LABEL: @__llvm_sjljeh_try_catching_longjmp_exception entry: br i1 false, label %UnifiedReturnBlock, label %no_exit no_exit: ; preds = %endif, %entry %SJE.0.0 = phi %struct.SetJmpMapEntry* [ %tmp.24, %endif ], [ null, %entry ] ; <%struct.SetJmpMapEntry*> [#uses=1] br i1 false, label %then, label %endif then: ; preds = %no_exit +; CHECK: %SJE.0.0.lcssa = phi %struct.SetJmpMapEntry %tmp.20 = getelementptr %struct.SetJmpMapEntry, %struct.SetJmpMapEntry* %SJE.0.0, i32 0, i32 1 ; [#uses=0] ret void endif: ; preds = %no_exit Index: test/Transforms/LCSSA/2006-06-12-MultipleExitsSameBlock.ll =================================================================== --- test/Transforms/LCSSA/2006-06-12-MultipleExitsSameBlock.ll +++ test/Transforms/LCSSA/2006-06-12-MultipleExitsSameBlock.ll @@ -1,13 +1,12 @@ -; RUN: opt < %s -lcssa -S | \ -; RUN: grep "%X.1.lcssa" -; RUN: opt < %s -lcssa -S | \ -; RUN: not grep "%X.1.lcssa1" +; RUN: opt < %s -lcssa -S | FileCheck %s +; RUN: opt < %s -passes=lcssa -S | FileCheck %s declare i1 @c1() declare i1 @c2() define i32 @foo() { +; CHECK-LABEL: @foo entry: br label %loop_begin loop_begin: ; preds = %loop_body.2, %entry @@ -20,8 +19,10 @@ %rel.2 = call i1 @c2( ) ; [#uses=1] br i1 %rel.2, label %loop_exit, label %loop_begin loop_exit: ; preds = %loop_body.2, %loop_body.1 +; CHECK: %X.1.lcssa = phi ret i32 %X.1 loop_exit2: ; preds = %loop_begin ret i32 1 +; CHECK-NOT: %X.1.lcssa1 } Index: test/Transforms/LCSSA/2006-07-09-NoDominator.ll =================================================================== --- test/Transforms/LCSSA/2006-07-09-NoDominator.ll +++ test/Transforms/LCSSA/2006-07-09-NoDominator.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -lcssa +; RUN: opt < %s -passes=lcssa %struct.SetJmpMapEntry = type { i8*, i32, %struct.SetJmpMapEntry* } Index: test/Transforms/LCSSA/2006-10-31-UnreachableBlock.ll =================================================================== --- test/Transforms/LCSSA/2006-10-31-UnreachableBlock.ll +++ test/Transforms/LCSSA/2006-10-31-UnreachableBlock.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -lcssa -disable-output +; RUN: opt < %s -passes=lcssa -disable-output ; PR977 ; END. Index: test/Transforms/LCSSA/basictest.ll =================================================================== --- test/Transforms/LCSSA/basictest.ll +++ test/Transforms/LCSSA/basictest.ll @@ -1,9 +1,8 @@ -; RUN: opt < %s -lcssa -S | \ -; RUN: grep "X3.lcssa = phi i32" -; RUN: opt < %s -lcssa -S | \ -; RUN: grep "X4 = add i32 3, %X3.lcssa" +; RUN: opt < %s -lcssa -S | FileCheck %s +; RUN: opt < %s -passes=lcssa -S | FileCheck %s define void @lcssa(i1 %S2) { +; CHECK-LABEL: @lcssa entry: br label %loop.interior loop.interior: ; preds = %post.if, %entry @@ -18,6 +17,8 @@ %X3 = phi i32 [ %X1, %if.true ], [ %X2, %if.false ] ; [#uses=1] br i1 %S2, label %loop.exit, label %loop.interior loop.exit: ; preds = %post.if +; CHECK: %X3.lcssa = phi i32 +; CHECK: %X4 = add i32 3, %X3.lcssa %X4 = add i32 3, %X3 ; [#uses=0] ret void } Index: test/Transforms/LCSSA/invoke-dest.ll =================================================================== --- test/Transforms/LCSSA/invoke-dest.ll +++ test/Transforms/LCSSA/invoke-dest.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -lcssa +; RUN: opt < %s -passes=lcssa target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32" Index: test/Transforms/LCSSA/mixed-catch.ll =================================================================== --- test/Transforms/LCSSA/mixed-catch.ll +++ test/Transforms/LCSSA/mixed-catch.ll @@ -1,4 +1,5 @@ ; RUN: opt -lcssa -S < %s | FileCheck %s +; RUN: opt -passes=lcssa -S < %s | FileCheck %s ; This test is based on the following C++ code: ; Index: test/Transforms/LCSSA/unused-phis.ll =================================================================== --- test/Transforms/LCSSA/unused-phis.ll +++ test/Transforms/LCSSA/unused-phis.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -lcssa -S | FileCheck %s +; RUN: opt < %s -passes=lcssa -S | FileCheck %s ; CHECK: exit1: ; CHECK: .lcssa = ; CHECK: exit2: