TaWeiTu updated this revision to Diff 281881. TaWeiTu added a comment. Herald added a reviewer: bollu.
Fix several pre-merge checks. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D84886/new/ https://reviews.llvm.org/D84886 Files: clang/lib/CodeGen/BackendUtil.cpp llvm/include/llvm/Analysis/LoopNestAnalysis.h llvm/include/llvm/Analysis/LoopNestAnalysisManager.h llvm/include/llvm/Passes/PassBuilder.h llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h llvm/include/llvm/Transforms/Scalar/LoopPassManager.h llvm/include/llvm/Transforms/Utils/LoopUtils.h llvm/lib/Analysis/CMakeLists.txt llvm/lib/Analysis/LoopNestAnalysis.cpp llvm/lib/Analysis/LoopNestAnalysisManager.cpp llvm/lib/LTO/LTOBackend.cpp llvm/lib/Passes/PassBuilder.cpp llvm/lib/Passes/PassRegistry.def llvm/lib/Transforms/Scalar/CMakeLists.txt llvm/lib/Transforms/Scalar/LoopNestPassManager.cpp llvm/lib/Transforms/Utils/LoopUtils.cpp llvm/test/Transforms/LICM/assume.ll llvm/test/Transforms/LoopDeletion/invalidation.ll llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll llvm/test/Transforms/LoopNest/print.ll llvm/test/Transforms/LoopRotate/basic.ll llvm/test/Transforms/LoopRotate/freeze-crash.ll llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll llvm/test/Transforms/LoopRotate/pr35210.ll llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp llvm/tools/opt/NewPMDriver.cpp llvm/unittests/IR/PassBuilderCallbacksTest.cpp llvm/unittests/Transforms/Scalar/LICMTest.cpp polly/unittests/ScopPassManager/PassManagerTest.cpp
Index: polly/unittests/ScopPassManager/PassManagerTest.cpp =================================================================== --- polly/unittests/ScopPassManager/PassManagerTest.cpp +++ polly/unittests/ScopPassManager/PassManagerTest.cpp @@ -16,6 +16,7 @@ protected: ModuleAnalysisManager MAM; FunctionAnalysisManager FAM; + LoopNestAnalysisManager LNAM; LoopAnalysisManager LAM; CGSCCAnalysisManager CGAM; ScopAnalysisManager SAM; @@ -26,13 +27,14 @@ ScopPassRegistry(const ScopPassRegistry &) = delete; ScopPassRegistry &operator=(ScopPassRegistry &&) = delete; ScopPassRegistry &operator=(const ScopPassRegistry &) = delete; - ScopPassRegistry() { + ScopPassRegistry() : LNAM(LAM) { PassBuilder PB; AM = PB.buildDefaultAAPipeline(); PB.registerModuleAnalyses(MAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); + PB.registerLoopNestAnalyses(LNAM); PB.registerCGSCCAnalyses(CGAM); FAM.registerPass([] { return ScopAnalysis(); }); @@ -43,7 +45,7 @@ // SAM.registerPass([] { return DependenceAnalysis(); }); SAM.registerPass([this] { return FunctionAnalysisManagerScopProxy(FAM); }); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); } }; Index: llvm/unittests/Transforms/Scalar/LICMTest.cpp =================================================================== --- llvm/unittests/Transforms/Scalar/LICMTest.cpp +++ llvm/unittests/Transforms/Scalar/LICMTest.cpp @@ -22,6 +22,7 @@ ModulePassManager MPM; PassBuilder PB; LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModuleAnalysisManager MAM; @@ -30,7 +31,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); StringRef PipelineStr = "require<opt-remark-emit>,loop(licm)"; ASSERT_THAT_ERROR(PB.parsePassPipeline(MPM, PipelineStr), Succeeded()); Index: llvm/unittests/IR/PassBuilderCallbacksTest.cpp =================================================================== --- llvm/unittests/IR/PassBuilderCallbacksTest.cpp +++ llvm/unittests/IR/PassBuilderCallbacksTest.cpp @@ -174,6 +174,24 @@ MockPassHandle() { setDefaults(); } }; +template <> +struct MockPassHandle<LoopNest> + : MockPassHandleBase<MockPassHandle<LoopNest>, LoopNest, + LoopNestAnalysisManager, LoopStandardAnalysisResults &, + LNPMUpdater &> { + MOCK_METHOD4(run, + PreservedAnalyses(LoopNest &, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, LNPMUpdater &)); + + static void invalidateLoopNest(LoopNest &LN, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, + LNPMUpdater &Updater) { + Updater.markLoopNestAsDeleted(LN, LN.getName()); + } + + MockPassHandle() { setDefaults(); } +}; + template <> struct MockPassHandle<Function> : MockPassHandleBase<MockPassHandle<Function>, Function> { @@ -226,6 +244,20 @@ MockAnalysisHandle<Loop>() { this->setDefaults(); } }; +template <> +struct MockAnalysisHandle<LoopNest> + : MockAnalysisHandleBase<MockAnalysisHandle<LoopNest>, Loop, + LoopAnalysisManager, + LoopStandardAnalysisResults &> { + MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &, + LoopStandardAnalysisResults &)); + + MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &, + LoopAnalysisManager::Invalidator &)); + + MockAnalysisHandle<LoopNest>() { this->setDefaults(); } +}; + template <> struct MockAnalysisHandle<Function> : MockAnalysisHandleBase<MockAnalysisHandle<Function>, Function> { @@ -282,6 +314,8 @@ return any_cast<const Module *>(WrappedIR)->getName().str(); if (any_isa<const Function *>(WrappedIR)) return any_cast<const Function *>(WrappedIR)->getName().str(); + if (any_isa<const LoopNest *>(WrappedIR)) + return any_cast<const LoopNest *>(WrappedIR)->getName().str(); if (any_isa<const Loop *>(WrappedIR)) return any_cast<const Loop *>(WrappedIR)->getName().str(); if (any_isa<const LazyCallGraph::SCC *>(WrappedIR)) @@ -395,6 +429,7 @@ PassBuilder PB; ModulePassManager PM; LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM; FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModuleAnalysisManager AM; @@ -426,7 +461,7 @@ "}\n")), CallbacksHandle(), PB(nullptr, PipelineTuningOptions(), None, &CallbacksHandle.Callbacks), - PM(true), LAM(true), FAM(true), CGAM(true), AM(true) { + PM(true), LAM(true), LNAM(LAM), FAM(true), CGAM(true), AM(true) { EXPECT_TRUE(&CallbacksHandle.Callbacks == PB.getPassInstrumentationCallbacks()); @@ -469,13 +504,15 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, AM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, AM); } }; using ModuleCallbacksTest = PassBuilderCallbacksTest<ModulePassManager>; using CGSCCCallbacksTest = PassBuilderCallbacksTest<CGSCCPassManager>; using FunctionCallbacksTest = PassBuilderCallbacksTest<FunctionPassManager>; +using LoopNestCallbacksTest = PassBuilderCallbacksTest<LoopNestPassManager>; using LoopCallbacksTest = PassBuilderCallbacksTest<LoopPassManager>; /// Test parsing of the name of our mock pass for all IRUnits. @@ -731,6 +768,144 @@ PM.run(*M, AM); } +TEST_F(LoopNestCallbacksTest, Passes) { + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) + .WillOnce(WithArgs<0, 1, 2>(Invoke(getAnalysisResult))); + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + +TEST_F(LoopNestCallbacksTest, InstrumentedPasses) { + CallbacksHandle.registerPassInstrumentation(); + // Non-mock instrumentation not specifically mentioned below can be ignored. + CallbacksHandle.ignoreNonMockPassInstrumentation("<string>"); + CallbacksHandle.ignoreNonMockPassInstrumentation("foo"); + CallbacksHandle.ignoreNonMockPassInstrumentation("loop"); + + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) + .WillOnce(WithArgs<0, 1, 2>(Invoke(getAnalysisResult))); + + // PassInstrumentation calls should happen in-sequence, in the same order + // as passes/analyses are scheduled. + ::testing::Sequence PISequence; + EXPECT_CALL(CallbacksHandle, + runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeNonSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL(CallbacksHandle, + runAfterPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + + // Our mock pass does not invalidate IR. + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("MockPassHandle"))) + .Times(0); + + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + +TEST_F(LoopNestCallbacksTest, InstrumentedInvalidatingPasses) { + CallbacksHandle.registerPassInstrumentation(); + // Non-mock instrumentation not specifically mentioned below can be ignored. + CallbacksHandle.ignoreNonMockPassInstrumentation("<string>"); + CallbacksHandle.ignoreNonMockPassInstrumentation("foo"); + CallbacksHandle.ignoreNonMockPassInstrumentation("loop"); + + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) + .WillOnce( + DoAll(WithArgs<0, 1, 2, 3>(Invoke(PassHandle.invalidateLoopNest)), + WithArgs<0, 1, 2>(Invoke(getAnalysisResult)))); + + // PassInstrumentation calls should happen in-sequence, in the same order + // as passes/analyses are scheduled. + ::testing::Sequence PISequence; + EXPECT_CALL(CallbacksHandle, + runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeNonSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("MockPassHandle"))) + .InSequence(PISequence); + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("^PassManager"))) + .InSequence(PISequence); + + // Our mock pass invalidates IR, thus normal runAfterPass is never called. + EXPECT_CALL(CallbacksHandle, + runAfterPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .Times(0); + + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + +TEST_F(LoopNestCallbacksTest, InstrumentedSkippedPasses) { + CallbacksHandle.registerPassInstrumentation(); + // Non-mock instrumentation run here can safely be ignored. + CallbacksHandle.ignoreNonMockPassInstrumentation("<string>"); + CallbacksHandle.ignoreNonMockPassInstrumentation("foo"); + CallbacksHandle.ignoreNonMockPassInstrumentation("loop"); + + // Skip the pass by returning false. + EXPECT_CALL(CallbacksHandle, + runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .WillOnce(Return(false)); + + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)).Times(0); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)).Times(0); + + // As the pass is skipped there is no afterPass, beforeAnalysis/afterAnalysis + // as well. + EXPECT_CALL(CallbacksHandle, runAfterPass(HasNameRegex("MockPassHandle"), _)) + .Times(0); + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("MockPassHandle"))) + .Times(0); + EXPECT_CALL(CallbacksHandle, + runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), _)) + .Times(0); + EXPECT_CALL(CallbacksHandle, + runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), _)) + .Times(0); + + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + TEST_F(LoopCallbacksTest, Passes) { EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) Index: llvm/tools/opt/NewPMDriver.cpp =================================================================== --- llvm/tools/opt/NewPMDriver.cpp +++ llvm/tools/opt/NewPMDriver.cpp @@ -18,6 +18,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" #include "llvm/Bitcode/BitcodeWriterPass.h" #include "llvm/Config/llvm-config.h" #include "llvm/IR/Dominators.h" @@ -348,6 +349,7 @@ } LoopAnalysisManager LAM(DebugPM); + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM(DebugPM); CGSCCAnalysisManager CGAM(DebugPM); ModuleAnalysisManager MAM(DebugPM); @@ -360,7 +362,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM(DebugPM); if (VK > VK_NoVerifier) Index: llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp =================================================================== --- llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp +++ llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp @@ -136,6 +136,7 @@ PassBuilder PB(TM.get()); LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModulePassManager MPM; @@ -146,7 +147,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); auto Err = PB.parsePassPipeline(MPM, PassPipeline, false, false); assert(!Err && "Should have been checked during fuzzer initialization"); Index: llvm/test/Transforms/LoopRotate/pr35210.ll =================================================================== --- llvm/test/Transforms/LoopRotate/pr35210.ll +++ llvm/test/Transforms/LoopRotate/pr35210.ll @@ -1,5 +1,7 @@ ;RUN: opt %s -passes='adce,loop(rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate 2>&1 | FileCheck %s ;RUN: opt %s -passes='adce,loop-mssa(rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate -verify-memoryssa 2>&1 | FileCheck %s --check-prefix=MSSA +;RUN: opt %s -passes='adce,loop-nest(loop(rotate)),adce' -S -debug-pass-manager -debug-only=loop-rotate 2>&1 | FileCheck %s +;RUN: opt %s -passes='adce,loop-nest-mssa(loop-mssa(rotate)),adce' -S -debug-pass-manager -debug-only=loop-rotate -verify-memoryssa 2>&1 | FileCheck %s --check-prefix=MSSA ;REQUIRES: asserts ; This test is to make sure we invalidate the post dominator pass after loop rotate simplifies the loop latch. Index: llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll =================================================================== --- llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll +++ llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll @@ -1,6 +1,7 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -S < %s -loop-rotate -loop-rotate-multi=true | FileCheck %s ; RUN: opt -S < %s -passes='loop(rotate)' -loop-rotate-multi=true | FileCheck %s +; RUN: opt -S < %s -passes='loop-nest(loop(rotate))' -loop-rotate-multi=true | FileCheck %s ; Test loop rotation with multiple exits, some of them - deoptimizing. ; We should end up with a latch which exit is non-deoptimizing, so we should rotate Index: llvm/test/Transforms/LoopRotate/freeze-crash.ll =================================================================== --- llvm/test/Transforms/LoopRotate/freeze-crash.ll +++ llvm/test/Transforms/LoopRotate/freeze-crash.ll @@ -1,5 +1,6 @@ ; RUN: opt -loop-rotate -disable-output %s ; RUN: opt -passes=rotate -disable-output %s +; RUN: opt -passes='loop-nest(loop(rotate))' -disable-output %s ; Make sure we don't crash on this test. define void @foo(i32* %arg) { Index: llvm/test/Transforms/LoopRotate/basic.ll =================================================================== --- llvm/test/Transforms/LoopRotate/basic.ll +++ llvm/test/Transforms/LoopRotate/basic.ll @@ -2,6 +2,8 @@ ; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s ; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop(rotate)' < %s | FileCheck %s ; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop-mssa(rotate)' -verify-memoryssa < %s | FileCheck %s +; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop-nest(loop(rotate))' < %s | FileCheck %s +; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop-nest(loop-mssa(rotate))' -verify-memoryssa < %s | FileCheck %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" target triple = "x86_64-apple-darwin10.0.0" Index: llvm/test/Transforms/LoopNest/print.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopNest/print.ll @@ -0,0 +1,84 @@ +; RUN: opt -S -passes='loop-nest(print)' < %s 2>&1 >/dev/null | FileCheck %s + +; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.cond, Loops: ( for.cond ) +define i32 @f1(i32 %n) #0 { +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %res.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ] + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, %n + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %add = add nsw i32 %res.0, %i.0 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +for.end: ; preds = %for.cond + %res.0.lcssa = phi i32 [ %res.0, %for.cond ] + ret i32 %res.0.lcssa +} + +; CHECH: IsPerfect=false, Depth=2, OutermostLoop: for.cond, Loops: ( for.cond for.cond1 for.cond5 ) +define i32 @f4(i32 %n) #0 { +entry: + br label %for.cond + +for.cond: ; preds = %for.inc12, %entry + %i.0 = phi i32 [ 0, %entry ], [ %inc13, %for.inc12 ] + %res.0 = phi i32 [ 0, %entry ], [ %res.2.lcssa, %for.inc12 ] + %cmp = icmp slt i32 %i.0, %n + br i1 %cmp, label %for.body, label %for.end14 + +for.body: ; preds = %for.cond + br label %for.cond1 + +for.cond1: ; preds = %for.inc, %for.body + %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] + %res.1 = phi i32 [ %res.0, %for.body ], [ %add, %for.inc ] + %cmp2 = icmp slt i32 %j.0, %n + br i1 %cmp2, label %for.body3, label %for.end + +for.body3: ; preds = %for.cond1 + %add = add nsw i32 %res.1, %i.0 + br label %for.inc + +for.inc: ; preds = %for.body3 + %inc = add nsw i32 %j.0, 1 + br label %for.cond1 + +for.end: ; preds = %for.cond1 + %res.1.lcssa = phi i32 [ %res.1, %for.cond1 ] + br label %for.cond5 + +for.cond5: ; preds = %for.inc9, %for.end + %res.2 = phi i32 [ %res.1.lcssa, %for.end ], [ %add8, %for.inc9 ] + %j4.0 = phi i32 [ 0, %for.end ], [ %inc10, %for.inc9 ] + %cmp6 = icmp slt i32 %j4.0, %n + br i1 %cmp6, label %for.body7, label %for.end11 + +for.body7: ; preds = %for.cond5 + %add8 = add nsw i32 %res.2, %j4.0 + br label %for.inc9 + +for.inc9: ; preds = %for.body7 + %inc10 = add nsw i32 %j4.0, 1 + br label %for.cond5 + +for.end11: ; preds = %for.cond5 + %res.2.lcssa = phi i32 [ %res.2, %for.cond5 ] + br label %for.inc12 + +for.inc12: ; preds = %for.end11 + %inc13 = add nsw i32 %i.0, 1 + br label %for.cond + +for.end14: ; preds = %for.cond + %res.0.lcssa = phi i32 [ %res.0, %for.cond ] + ret i32 %res.0.lcssa +} Index: llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll +++ llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll @@ -1,5 +1,6 @@ ; RUN: opt < %s -loop-deletion -S | FileCheck %s ; RUN: opt < %s -passes='loop(loop-deletion)' -S | FileCheck %s +; RUN: opt < %s -passes='loop-nest(loop(loop-deletion))' -S | FileCheck %s ; ScalarEvolution can prove the loop iteration is finite, even though ; it can't represent the exact trip count as an expression. That's Index: llvm/test/Transforms/LoopDeletion/invalidation.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/invalidation.ll +++ llvm/test/Transforms/LoopDeletion/invalidation.ll @@ -4,8 +4,12 @@ ; ; RUN: opt < %s -passes='require<iv-users>,no-op-loop,require<iv-users>' -S \ ; RUN: | FileCheck %s --check-prefixes=CHECK,BEFORE +; RUN: opt < %s -passes='loop-nest(loop(require<iv-users>,no-op-loop,require<iv-users>))' -S \ +; RUN: | FileCheck %s --check-prefixes=CHECK,BEFORE ; RUN: opt < %s -passes='require<iv-users>,loop-deletion,require<iv-users>' -S \ ; RUN: | FileCheck %s --check-prefixes=CHECK,AFTER +; RUN: opt < %s -passes='loop-nest(loop(require<iv-users>,loop-deletion,require<iv-users>))' -S \ +; RUN: | FileCheck %s --check-prefixes=CHECK,AFTER define void @foo(i64 %n, i64 %m) nounwind { Index: llvm/test/Transforms/LICM/assume.ll =================================================================== --- llvm/test/Transforms/LICM/assume.ll +++ llvm/test/Transforms/LICM/assume.ll @@ -1,5 +1,6 @@ ; RUN: opt -licm -basic-aa < %s -S | FileCheck %s ; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop-nest(loop(licm))' < %s -S | FileCheck %s define void @f_0(i1 %p) nounwind ssp { ; CHECK-LABEL: @f_0( Index: llvm/lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- llvm/lib/Transforms/Utils/LoopUtils.cpp +++ llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -1537,6 +1537,12 @@ appendReversedLoopsToWorklist(LI, Worklist); } +void llvm::appendLoopNestToWorklist( + Loop &Root, SmallPriorityWorklist<Loop *, 4> &Worklist) { + Worklist.insert(&Root); + appendLoopsToWorklist(Root, Worklist); +} + Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM) { Loop &New = *LI->AllocateLoop(); Index: llvm/lib/Transforms/Scalar/LoopNestPassManager.cpp =================================================================== --- /dev/null +++ llvm/lib/Transforms/Scalar/LoopNestPassManager.cpp @@ -0,0 +1,106 @@ +//===- LoopNestPassManager.cpp - Loop nest pass management ----------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/LoopNestPassManager.h" + +namespace llvm { + +template <> +PreservedAnalyses +PassManager<LoopNest, LoopNestAnalysisManager, LoopStandardAnalysisResults &, + LNPMUpdater &>::run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LNPMUpdater &U) { + PreservedAnalyses PA = PreservedAnalyses::all(); + + // Request PassInstrumentation from analysis manager, will use it to run + // instrumenting callbacks for the passes later. + PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(LN, AR); + + if (DebugLogging) + dbgs() << "Starting LoopNest pass manager run.\n"; + + for (unsigned I = 0, E = Passes.size(); I != E; ++I) { + auto *Pass = Passes[I].get(); + + // Check the PassInstrumentation's BeforePass callbacks before running the + // pass, skip its execution completely if asked to (callback returns + // false). + if (!PI.runBeforePass<LoopNest>(*Pass, LN)) + continue; + + if (DebugLogging) + dbgs() << "Running pass: " << Pass->name() << " on " << LN.getName() + << "\n"; + + PreservedAnalyses PassPA; + { + TimeTraceScope TimeScope(Pass->name(), LN.getName()); + PassPA = Pass->run(LN, AM, AR, U); + } + + // Do not pass deleted LoopNest into the instrumentation + if (U.skipCurrentLoopNest()) + PI.runAfterPassInvalidated<LoopNest>(*Pass); + else + PI.runAfterPass<LoopNest>(*Pass, LN); + + // We shouldn't allow invalidating LoopNestAnalysis in AM since otherwise + // LN will be dangling. Currently the loop nest passes cannot explicitly + // update the LoopNest structure, so we must first check whether + // LoopNestAnalysis is preserved, and mark it as preserved + // regardlessly afterward. If the analysis is not preserved in the first + // place, we would have to manually reconstruct the LoopNest. + // FIXME: This is quite inefficient. Consider reimplementing LoopNest to + // allow dynamic modifications by the loop nest passes to avoid + // reconstructing it every time. + bool IsLoopNestPreserved = + PassPA.getChecker<LoopNestAnalysis>().preserved(); + + // No need to invalidate other loop nest analyses since they are running on + // Loop and hence can be updated dynamically. + PassPA.preserve<LoopNestAnalysis>(); + if (!U.skipCurrentLoopNest()) + AM.invalidate(LN, PassPA); + + if (!IsLoopNestPreserved) + // The LoopNest structure had been altered, reconstruct it here. + LN.reconstructInplace(AR.SE); + PA.intersect(std::move(PassPA)); + } + + // Invalidation for the current loop nest should be handled above, and other + // loop nest analysis results shouldn't be impacted by runs over this loop + // nest. Therefore, the remaining analysis results in the AnalysisManager are + // preserved. We mark this with a set so that we don't need to inspect each + // one individually. + assert(PA.getChecker<LoopNestAnalysis>().preserved()); + PA.preserveSet<AllAnalysesOn<LoopNest>>(); + + if (DebugLogging) + dbgs() << "Finished LoopNest pass manager run.\n"; + + return PA; +} + +template class PassManager<LoopNest, LoopNestAnalysisManager, + LoopStandardAnalysisResults &, LNPMUpdater &>; + +PrintLoopNestPass::PrintLoopNestPass() : OS(dbgs()) {} +PrintLoopNestPass::PrintLoopNestPass(raw_ostream &OS, const std::string &Banner) + : OS(OS), Banner(Banner) {} + +PreservedAnalyses PrintLoopNestPass::run(LoopNest &LN, + LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, + LNPMUpdater &) { + OS << LN << "\n"; + return PreservedAnalyses::all(); +} + +} // namespace llvm Index: llvm/lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- llvm/lib/Transforms/Scalar/CMakeLists.txt +++ llvm/lib/Transforms/Scalar/CMakeLists.txt @@ -33,6 +33,7 @@ LoopInstSimplify.cpp LoopInterchange.cpp LoopLoadElimination.cpp + LoopNestPassManager.cpp LoopPassManager.cpp LoopPredication.cpp LoopRerollPass.cpp Index: llvm/lib/Passes/PassRegistry.def =================================================================== --- llvm/lib/Passes/PassRegistry.def +++ llvm/lib/Passes/PassRegistry.def @@ -321,6 +321,7 @@ LOOP_ANALYSIS("access-info", LoopAccessAnalysis()) LOOP_ANALYSIS("ddg", DDGAnalysis()) LOOP_ANALYSIS("iv-users", IVUsersAnalysis()) +LOOP_ANALYSIS("loop-nest", LoopNestAnalysis()) LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC)) #undef LOOP_ANALYSIS @@ -359,3 +360,27 @@ }, parseLoopUnswitchOptions) #undef LOOP_PASS_WITH_PARAMS + +#ifndef LOOP_NEST_ANALYSIS +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) +#endif +#undef LOOP_NEST_ANALYSIS + +#ifndef LOOP_NEST_PASS +#define LOOP_NEST_PASS(NAME, CREATE_PASS) +#endif +LOOP_NEST_PASS("no-op-loop-nest", NoOpLoopNestPass()) +LOOP_NEST_PASS("print", PrintLoopNestPass()) +#undef LOOP_NEST_PASS + +#ifndef LOOP_NEST_PASS_WITH_PARAMS +#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS) +#endif +#undef LOOP_NEST_PASS_WITH_PARAMS + +#ifndef LOOP_NEST_ANALYSIS +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) +#endif +LOOP_NEST_ANALYSIS("no-op-loop-nest", NoOpLoopNestAnalysis()) +LOOP_NEST_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC)) +#undef LOOP_NEST_ANALYSIS Index: llvm/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/lib/Passes/PassBuilder.cpp +++ llvm/lib/Passes/PassBuilder.cpp @@ -143,6 +143,7 @@ #include "llvm/Transforms/Scalar/LoopIdiomRecognize.h" #include "llvm/Transforms/Scalar/LoopInstSimplify.h" #include "llvm/Transforms/Scalar/LoopLoadElimination.h" +#include "llvm/Transforms/Scalar/LoopNestPassManager.h" #include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Transforms/Scalar/LoopPredication.h" #include "llvm/Transforms/Scalar/LoopRotation.h" @@ -386,9 +387,32 @@ static StringRef name() { return "NoOpLoopAnalysis"; } }; +/// No-op loop nest pass which does nothing. +struct NoOpLoopNestPass : PassInfoMixin<NoOpLoopNestPass> { + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, LNPMUpdater &) { + return PreservedAnalyses::all(); + } + static StringRef name() { return "NoOpLoopNestPass"; } +}; + +/// No-op loop nest analysis. +class NoOpLoopNestAnalysis : public AnalysisInfoMixin<NoOpLoopNestAnalysis> { + friend AnalysisInfoMixin<NoOpLoopNestAnalysis>; + static AnalysisKey Key; + +public: + struct Result {}; + Result run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &) { + return Result(); + } + static StringRef name() { return "NoOpLoopNestAnalysis"; } +}; + AnalysisKey NoOpModuleAnalysis::Key; AnalysisKey NoOpCGSCCAnalysis::Key; AnalysisKey NoOpFunctionAnalysis::Key; +AnalysisKey NoOpLoopNestAnalysis::Key; AnalysisKey NoOpLoopAnalysis::Key; } // namespace @@ -435,6 +459,15 @@ C(LAM); } +void PassBuilder::registerLoopNestAnalyses(LoopNestAnalysisManager &LNAM) { +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + LNAM.registerPass([&] { return CREATE_PASS; }); +#include "PassRegistry.def" + + for (auto &C : LoopNestAnalysisRegistrationCallbacks) + C(LNAM); +} + // TODO: Investigate the cost/benefit of tail call elimination on debugging. FunctionPassManager PassBuilder::buildO1FunctionSimplificationPipeline( OptimizationLevel Level, ThinLTOPhase Phase, bool DebugLogging) { @@ -2006,6 +2039,30 @@ return callbacksAcceptPassName<FunctionPassManager>(Name, Callbacks); } +template <typename CallbacksT> +static bool isLoopNestPassName(StringRef Name, CallbacksT &Callbacks) { + // Explicitly handle pass manager names. + if (Name == "loop-nest" || Name == "loop-nest-mssa") + return true; + + // Explicitly handle custom-parsed pass names. + if (parseRepeatPassName(Name)) + return true; + +#define LOOP_NEST_PASS(NAME, CREATE_PASS) \ + if (Name == NAME) \ + return true; +#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \ + if (checkParametrizedPassName(Name, NAME)) \ + return true; +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \ + return true; +#include "PassRegistry.def" + + return callbacksAcceptPassName<LoopNestPassManager>(Name, Callbacks); +} + template <typename CallbacksT> static bool isLoopPassName(StringRef Name, CallbacksT &Callbacks) { // Explicitly handle pass manager names. @@ -2398,6 +2455,16 @@ FPM.addPass(std::move(NestedFPM)); return Error::success(); } + if (Name == "loop-nest" || Name == "loop-nest-mssa") { + LoopNestPassManager LNPM(DebugLogging); + if (auto Err = parseLoopNestPassPipeline(LNPM, InnerPipeline, + VerifyEachPass, DebugLogging)) + return Err; + bool UseMemorySSA = (Name == "loop-nest-mssa"); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + std::move(LNPM), UseMemorySSA, DebugLogging)); + return Error::success(); + } if (Name == "loop" || Name == "loop-mssa") { LoopPassManager LPM(DebugLogging); if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass, @@ -2483,6 +2550,92 @@ inconvertibleErrorCode()); } +Error PassBuilder::parseLoopNestPass(LoopNestPassManager &LNPM, + const PipelineElement &E, + bool VerifyEachPass, bool DebugLogging) { + StringRef Name = E.Name; + const auto &InnerPipeline = E.InnerPipeline; + + // First handle complex passes like the pass managers which carry pipelines. + if (!InnerPipeline.empty()) { + if (Name == "loop-nest") { + LoopNestPassManager NestedLNPM(DebugLogging); + if (auto Err = parseLoopNestPassPipeline(NestedLNPM, InnerPipeline, + VerifyEachPass, DebugLogging)) + return Err; + // Add the nested pass manager with the appropriate adaptor. + LNPM.addPass(std::move(NestedLNPM)); + return Error::success(); + } + // Loop passes can be wrapped in a loop nest pass via \c + // LoopNestToLoopPassAdaptor. + if (Name == "loop" || Name == "loop-mssa") { + dbgs() << "wrapping loop passes in loop nest pass" + << "\n"; + LoopPassManager LPM(DebugLogging); + if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass, + DebugLogging)) + return Err; + // bool UseMemorySSA = (Name == "loop-mssa"); + LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM))); + return Error::success(); + } + if (auto Count = parseRepeatPassName(Name)) { + LoopNestPassManager NestedLNPM(DebugLogging); + if (auto Err = parseLoopNestPassPipeline(NestedLNPM, InnerPipeline, + VerifyEachPass, DebugLogging)) + return Err; + LNPM.addPass(createRepeatedPass(*Count, std::move(NestedLNPM))); + return Error::success(); + } + + for (auto &C : LoopNestPipelineParsingCallbacks) + if (C(Name, LNPM, InnerPipeline)) + return Error::success(); + + // Normal passes can't have pipelines. + return make_error<StringError>( + formatv("invalid use of '{0}' pass as loop pipeline", Name).str(), + inconvertibleErrorCode()); + } + +// Now expand the basic registered passes from the .inc file. +#define LOOP_NEST_PASS(NAME, CREATE_PASS) \ + if (Name == NAME) { \ + LNPM.addPass(CREATE_PASS); \ + return Error::success(); \ + } +#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \ + if (checkParametrizedPassName(Name, NAME)) { \ + auto Params = parsePassParameters(PARSER, Name, NAME); \ + if (!Params) \ + return Params.takeError(); \ + LNPM.addPass(CREATE_PASS(Params.get())); \ + return Error::success(); \ + } +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + if (Name == "require<" NAME ">") { \ + LNPM.addPass(RequireAnalysisPass< \ + std::remove_reference<decltype(CREATE_PASS)>::type, LoopNest, \ + LoopNestAnalysisManager, LoopStandardAnalysisResult &, \ + LNPMUpdater &>()); \ + return Error::success(); \ + } \ + if (Name == "invalidate<" NAME ">") { \ + LNPM.addPass(InvalidateAnalysisPass < \ + std::remove_reference<decltype(CREATE_PASS)>::type()); \ + return Error::success(); \ + } +#include "PassRegistry.def" + + for (auto &C : LoopNestPipelineParsingCallbacks) + if (C(Name, LNPM, InnerPipeline)) + return Error::success(); + return make_error<StringError>( + formatv("unknown loop nest pass '{0}'", Name).str(), + inconvertibleErrorCode()); +} + Error PassBuilder::parseLoopPass(LoopPassManager &LPM, const PipelineElement &E, bool VerifyEachPass, bool DebugLogging) { StringRef Name = E.Name; @@ -2575,6 +2728,19 @@ return false; } +Error PassBuilder::parseLoopNestPassPipeline(LoopNestPassManager &LNPM, + ArrayRef<PipelineElement> Pipeline, + bool VerifyEachPass, + bool DebugLogging) { + for (const auto &Element : Pipeline) { + if (auto Err = + parseLoopNestPass(LNPM, Element, VerifyEachPass, DebugLogging)) + return Err; + // FIXME: No verifier support for LoopNest passes! + } + return Error::success(); +} + Error PassBuilder::parseLoopPassPipeline(LoopPassManager &LPM, ArrayRef<PipelineElement> Pipeline, bool VerifyEachPass, @@ -2614,6 +2780,7 @@ } void PassBuilder::crossRegisterProxies(LoopAnalysisManager &LAM, + LoopNestAnalysisManager &LNAM, FunctionAnalysisManager &FAM, CGSCCAnalysisManager &CGAM, ModuleAnalysisManager &MAM) { @@ -2622,6 +2789,7 @@ CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); }); FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); }); FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); + FAM.registerPass([&] { return LoopNestAnalysisManagerFunctionProxy(LNAM); }); FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); }); LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); }); } @@ -2661,6 +2829,9 @@ } else if (isFunctionPassName(FirstName, FunctionPipelineParsingCallbacks)) { Pipeline = {{"function", std::move(*Pipeline)}}; + } else if (isLoopNestPassName(FirstName, + LoopNestPipelineParsingCallbacks)) { + Pipeline = {{"function", {{"loop-nest", std::move(*Pipeline)}}}}; } else if (isLoopPassName(FirstName, LoopPipelineParsingCallbacks)) { Pipeline = {{"function", {{"loop", std::move(*Pipeline)}}}}; } else { @@ -2788,6 +2959,9 @@ #define LOOP_ANALYSIS(NAME, CREATE_PASS) \ if (PassName == NAME) \ return true; +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + if (PassName == NAME) \ + return true; #define CGSSC_ANALYSIS(NAME, CREATE_PASS) \ if (PassName == NAME) \ return true; Index: llvm/lib/LTO/LTOBackend.cpp =================================================================== --- llvm/lib/LTO/LTOBackend.cpp +++ llvm/lib/LTO/LTOBackend.cpp @@ -16,6 +16,7 @@ #include "llvm/LTO/LTOBackend.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" @@ -209,6 +210,7 @@ RegisterPassPlugins(Conf.PassPlugins, PB); LoopAnalysisManager LAM(Conf.DebugPassManager); + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM(Conf.DebugPassManager); CGSCCAnalysisManager CGAM(Conf.DebugPassManager); ModuleAnalysisManager MAM(Conf.DebugPassManager); @@ -221,7 +223,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM(Conf.DebugPassManager); // FIXME (davide): verify the input. @@ -271,6 +274,7 @@ RegisterPassPlugins(Conf.PassPlugins, PB); LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModuleAnalysisManager MAM; @@ -283,7 +287,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM; Index: llvm/lib/Analysis/LoopNestAnalysisManager.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/LoopNestAnalysisManager.cpp @@ -0,0 +1,114 @@ +//===- LoopNestAnalysisManager.cpp - LoopNest analysis management ---------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopNestAnalysisManager.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/PassManagerImpl.h" + +using namespace llvm; + +namespace llvm { + +template class AnalysisManager<LoopNest>; +template class InnerAnalysisManagerProxy<LoopNestAnalysisManager, Function>; +template class InnerAnalysisManagerProxy<LoopAnalysisManager, LoopNest>; +template class OuterAnalysisManagerProxy<FunctionAnalysisManager, LoopNest, + LoopStandardAnalysisResults &>; + +bool LoopNestAnalysisManagerFunctionProxy::Result::invalidate( + Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { + // If literally everything is preserved, we're done. + if (PA.areAllPreserved()) + return false; // This is still a valid proxy. + + const std::vector<Loop *> &Loops = LI->getTopLevelLoops(); + + auto PAC = PA.getChecker<LoopNestAnalysisManagerFunctionProxy>(); + bool InvalidateMemorySSAAnalysis = false; + if (MSSAUsed) + InvalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA); + if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>()) { + if (Inv.invalidate<AAManager>(F, PA) || + Inv.invalidate<AssumptionAnalysis>(F, PA) || + Inv.invalidate<DominatorTreeAnalysis>(F, PA) || + Inv.invalidate<LoopAnalysis>(F, PA) || + Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) || + InvalidateMemorySSAAnalysis) { + // Note that the LoopInfo may be stale at this point, however the loop + // objects themselves remain the only viable keys that could be in the + // analysis manager's cache. So we just walk the keys and forcibly clear + // those results. Note that the order doesn't matter here as this will + // just directly destroy the results without calling methods on them. + // + // Though we're dealing with loop nests here, the analysis results can + // still be cleared via the root loops. + for (Loop *L : Loops) + InnerAM->clear(*L, "<possibly invalidated loop>"); + InnerAM = nullptr; + return true; + } + } + + // Directly check if the relevant set is preserved. + bool AreLoopNestAnalysesPreserved = + PA.allAnalysesInSetPreserved<AllAnalysesOn<LoopNest>>(); + + for (Loop *L : Loops) { + Optional<PreservedAnalyses> LoopNestPA; + + // Check to see whether the preserved set needs to be pruned based on + // function-level analysis invalidation that triggers deferred invalidation + // registered with the outer analysis manager proxy for this loop nest. + if (auto *OuterProxy = + InnerAM->getCachedResult<FunctionAnalysisManagerLoopNestProxy>( + *L)) { + for (const auto &OuterInvalidationPair : + OuterProxy->getOuterInvalidations()) { + AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; + const auto &InnerAnalysisIDs = OuterInvalidationPair.second; + if (Inv.invalidate(OuterAnalysisID, F, PA)) { + if (!LoopNestPA) + LoopNestPA = PA; + for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) + LoopNestPA->abandon(InnerAnalysisID); + } + } + } + + // Check if we needed a custom PA set, and if so we'll need to run the + // inner invalidation. + if (LoopNestPA) { + InnerAM->invalidate(*L, *LoopNestPA); + continue; + } + + // Otherwise we only need to do invalidation if the original PA set didn't + // preserve all loop nest analyses. + if (!AreLoopNestAnalysesPreserved) + InnerAM->invalidate(*L, PA); + } + + // Return false to indicate that this result is still a valid proxy. + return false; +} + +template <> +LoopNestAnalysisManagerFunctionProxy::Result +LoopNestAnalysisManagerFunctionProxy::run(Function &F, + FunctionAnalysisManager &AM) { + return Result(*InnerAM, AM.getResult<LoopAnalysis>(F)); +} + +} // namespace llvm Index: llvm/lib/Analysis/LoopNestAnalysis.cpp =================================================================== --- llvm/lib/Analysis/LoopNestAnalysis.cpp +++ llvm/lib/Analysis/LoopNestAnalysis.cpp @@ -206,6 +206,15 @@ return CurrentDepth; } +void LoopNest::reconstructInplace(ScalarEvolution &SE) { + assert(!Loops.empty() && "Loop nest should contain the root loop."); + Loop *Root = Loops[0]; + MaxPerfectDepth = getMaxPerfectDepth(*Root, SE); + Loops.clear(); + for (Loop *L : breadth_first(Root)) + Loops.push_back(L); +} + static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { // The inner loop must be the only outer loop's child. @@ -282,6 +291,13 @@ return OS; } +AnalysisKey LoopNestAnalysis::Key; + +LoopNest LoopNestAnalysis::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR) { + return LoopNest(L, AR.SE); +} + //===----------------------------------------------------------------------===// // LoopNestPrinterPass implementation // Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -75,6 +75,7 @@ LoopAnalysisManager.cpp LoopCacheAnalysis.cpp LoopNestAnalysis.cpp + LoopNestAnalysisManager.cpp LoopUnrollAnalyzer.cpp LoopInfo.cpp LoopPass.cpp Index: llvm/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -427,6 +427,12 @@ /// FIXME: Consider changing the order in LoopInfo. void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist<Loop *, 4> &); +/// Utility that implements appending of all loops in a loop nest (rooted at \p +/// Root) onto a worklist. Since appendLoopsToWorklist(Loop &) only pushes +/// subloops, the root loop will be pushed into the worklist first in this +/// function. +void appendLoopNestToWorklist(Loop &Root, SmallPriorityWorklist<Loop *, 4> &); + /// Recursively clone the specified loop and all of its children, /// mapping the blocks with the specified map. Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, Index: llvm/include/llvm/Transforms/Scalar/LoopPassManager.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/LoopPassManager.h +++ llvm/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -104,6 +104,7 @@ LoopStandardAnalysisResults &, LPMUpdater &>; template <typename LoopPassT> class FunctionToLoopPassAdaptor; +template <typename LoopPassT> class LoopNestToLoopPassAdaptor; /// This class provides an interface for updating the loop pass manager based /// on mutations to the loop nest. @@ -199,6 +200,7 @@ private: template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor; + template <typename LoopPassT> friend class llvm::LoopNestToLoopPassAdaptor; /// The \c FunctionToLoopPassAdaptor's worklist of loops to process. SmallPriorityWorklist<Loop *, 4> &Worklist; @@ -220,6 +222,30 @@ : Worklist(Worklist), LAM(LAM) {} }; +namespace detail { + +/// Helper function for preserving the standard analyses on loops. +inline void preserveLoopStandardAnalysisResults(PreservedAnalyses &PA, + bool UseMemorySSA) { + PA.preserve<DominatorTreeAnalysis>(); + PA.preserve<LoopAnalysis>(); + PA.preserve<ScalarEvolutionAnalysis>(); + if (UseMemorySSA) + PA.preserve<MemorySSAAnalysis>(); +} + +/// Helper function for preserving AA category. +inline void preserveAACategory(PreservedAnalyses &PA) { + // FIXME: What we really want to do here is preserve an AA category, but + // that concept doesn't exist yet. + PA.preserve<AAManager>(); + PA.preserve<BasicAA>(); + PA.preserve<GlobalsAA>(); + PA.preserve<SCEVAA>(); +} + +} // namespace detail + /// Adaptor that maps from a function to its loops. /// /// Designed to allow composition of a LoopPass(Manager) and a @@ -352,17 +378,8 @@ PA.preserveSet<AllAnalysesOn<Loop>>(); PA.preserve<LoopAnalysisManagerFunctionProxy>(); // We also preserve the set of standard analyses. - PA.preserve<DominatorTreeAnalysis>(); - PA.preserve<LoopAnalysis>(); - PA.preserve<ScalarEvolutionAnalysis>(); - if (UseMemorySSA) - PA.preserve<MemorySSAAnalysis>(); - // FIXME: What we really want to do here is preserve an AA category, but - // that concept doesn't exist yet. - PA.preserve<AAManager>(); - PA.preserve<BasicAA>(); - PA.preserve<GlobalsAA>(); - PA.preserve<SCEVAA>(); + detail::preserveLoopStandardAnalysisResults(PA, UseMemorySSA); + detail::preserveAACategory(PA); return PA; } Index: llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h =================================================================== --- /dev/null +++ llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h @@ -0,0 +1,351 @@ +//===- LoopNestPassManager.h - Loop nest pass management -----------------*- C++ +//-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H +#define LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H + +#include "llvm/ADT/PriorityWorklist.h" +#include "llvm/Analysis/LoopNestAnalysis.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +class LNPMUpdater; + +template <> +PreservedAnalyses +PassManager<LoopNest, LoopNestAnalysisManager, LoopStandardAnalysisResults &, + LNPMUpdater &>::run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LNPMUpdater &U); + +extern template class PassManager<LoopNest, LoopNestAnalysisManager, + LoopStandardAnalysisResults &, LNPMUpdater &>; + +using LoopNestPassManager = + PassManager<LoopNest, LoopNestAnalysisManager, + LoopStandardAnalysisResults &, LNPMUpdater &>; + +/// A partial specialization of the require analysis template pass to forward +/// the extra parameters from a transformation's run method to the +/// AnalysisManager's getResult. +template <typename AnalysisT> +struct RequireAnalysisPass<AnalysisT, LoopNest, LoopNestAnalysisManager, + LoopStandardAnalysisResults &, LNPMUpdater &> + : PassInfoMixin< + RequireAnalysisPass<AnalysisT, LoopNest, LoopNestAnalysisManager, + LoopStandardAnalysisResults &, LNPMUpdater &>> { + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LNPMUpdater &) { + (void)AM.template getResult<AnalysisT>(LN, AR); + return PreservedAnalyses::all(); + } +}; + +/// This class provides an interface for updating the loop nest pass manager +/// based on mutations to the loop nest. +/// +/// A reference to an instance of this class is passed as an argument to each +/// LoopNest pass, and LoopNest passes should use it to update LNPM +/// infrastructure if they modify the loop nest structure. +class LNPMUpdater { +public: + /// This can be queried by loop nest passes which run other loop nest passes + /// (like pass managers) to know whether the loop nest needs to be skipped due + /// to updates to the loop nest. + /// + /// If this returns true, the loop nest object may have been deleted, so + /// passes should take care not to touch the object. + bool skipCurrentLoopNest() const { return SkipCurrentLoopNest; } + + void markLoopNestAsDeleted(LoopNest &LN, llvm::StringRef Name) { + LNAM.clear(LN, Name); + assert(&LN.getOutermostLoop() == CurrentLoopNest && + "Cannot delete loop nests other than the current one"); + SkipCurrentLoopNest = true; + } + + /// Loop nest passes should use this method to indicate they have added new + /// loop nests to the current function. + /// + /// \p NewLoopNests must only contain top-level loops. + void addNewLoopNests(ArrayRef<Loop *> NewLoopNests) { + for (Loop *NewL : NewLoopNests) { +#ifndef NDEBUG + assert(!NewL->getParentLoop() && + "All of the new loops must be top-level!"); +#endif + Worklist.insert(NewL); + } + } + + void revisitCurrentLoopNest() { + SkipCurrentLoopNest = true; + Worklist.insert(CurrentLoopNest); + } + +private: + template <typename LoopNestPassT> friend class FunctionToLoopNestPassAdaptor; + + LNPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist, + LoopNestAnalysisManager &LNAM) + : Worklist(Worklist), LNAM(LNAM) {} + + /// The \c FunctionToLoopNestPassAdaptor's worklist of loops to process. + SmallPriorityWorklist<Loop *, 4> &Worklist; + + /// The analysis manager for use in the current loop nest; + LoopNestAnalysisManager &LNAM; + + Loop *CurrentLoopNest; + bool SkipCurrentLoopNest; +}; + +/// Adaptor that maps from a function to its loop nests. +/// +/// Designed to allow composition of a LoopNestPass(Manager) and a +/// FunctionPassManager. Note that if this pass is constructed with a \c +/// FunctionAnalysisManager it will run the \c +/// LoopNestAnalysisManagerFunctionProxy analysis prior to running the loop +/// passes over the function to enable a \c LoopNestAnalysisManager to be used +/// within this run safely. +template <typename LoopNestPassT> +class FunctionToLoopNestPassAdaptor + : public PassInfoMixin<FunctionToLoopNestPassAdaptor<LoopNestPassT>> { +public: + explicit FunctionToLoopNestPassAdaptor(LoopNestPassT Pass, + bool UseMemorySSA = false, + bool DebugLogging = false) + : Pass(std::move(Pass)), UseMemorySSA(UseMemorySSA), + LoopCanonicalizationFPM(DebugLogging) { + LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); + LoopCanonicalizationFPM.addPass(LCSSAPass()); + } + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { + // Before we even compute any loop nest analyses, first run a miniature + // function pass pipeline to put loops into their canonical form. Note that + // we can directly build up function analyses after this as the function + // pass manager handles all the invalidation at that layer. + PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F); + + PreservedAnalyses PA = PreservedAnalyses::all(); + if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) { + PA = LoopCanonicalizationFPM.run(F, AM); + PI.runAfterPass<Function>(LoopCanonicalizationFPM, F); + } + + // Get the loop structure for this function + LoopInfo &LI = AM.getResult<LoopAnalysis>(F); + + // If there are no loops, there is nothing to do here. + if (LI.empty()) + return PA; + + // Get the analysis results needed by loop nest passes. + MemorySSA *MSSA = UseMemorySSA + ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) + : nullptr; + LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F), + AM.getResult<AssumptionAnalysis>(F), + AM.getResult<DominatorTreeAnalysis>(F), + AM.getResult<LoopAnalysis>(F), + AM.getResult<ScalarEvolutionAnalysis>(F), + AM.getResult<TargetLibraryAnalysis>(F), + AM.getResult<TargetIRAnalysis>(F), + MSSA}; + + // Setup the loop nest analysis manager from its proxy. It is important that + // this is only done when there are loops to process and we have built the + // LoopStandardAnalysisResults object. The loop nest analyses cached in this + // manager have access to those analysis results and so it must invalidate + // itself when they go away. + auto &LNAMFP = AM.getResult<LoopNestAnalysisManagerFunctionProxy>(F); + if (UseMemorySSA) + LNAMFP.markMSSAUsed(); + LoopNestAnalysisManager &LNAM = LNAMFP.getManager(); + + // The worklist of loop nests in the function. The loop nests are + // represented by their root loops and the actual LoopNest object will be + // constructed lazily when needed. + SmallPriorityWorklist<Loop *, 4> Worklist; + LNPMUpdater Updater(Worklist, LNAM); + + // Append all outer-most loops in the function into the worklist. + for (Loop *L : LI.getTopLevelLoops()) + Worklist.insert(L); + + do { + Loop *L = Worklist.pop_back_val(); + + // Reset the update structure for this loop nest. + Updater.CurrentLoopNest = L; + Updater.SkipCurrentLoopNest = false; + + LoopNest &LN = LNAM.getLoopNest(*L, LAR); + // Check the PassInstrumentation's BeforePass callbacks before running the + // pass, skip its execution completely if asked to (callback returns + // false). + if (!PI.runBeforePass<LoopNest>(Pass, LN)) + continue; + + PreservedAnalyses PassPA; + { + TimeTraceScope TimeScope(Pass.name()); + PassPA = Pass.run(LN, LNAM, LAR, Updater); + } + + // Do not pass deleted LoopNest into the instrumentation. + if (Updater.skipCurrentLoopNest()) + PI.runAfterPassInvalidated<LoopNest>(Pass); + else + PI.runAfterPass<LoopNest>(Pass, LN); + + if (!Updater.skipCurrentLoopNest()) + // We know that the loop nest pass couldn't have invalidated any other + // loop nest's analyses (that's the contract of a loop nest pass), so + // directly handle the loop nest analysis manager's invalidation here. + LNAM.invalidate(LN, PassPA); + + // Then intersect the preserved set so that invalidation of loop nest + // analyses will eventually occur when the loop nest pass completes. + PA.intersect(std::move(PassPA)); + } while (!Worklist.empty()); + + // By definition we preserve the proxy. We also preserve all analyses on + // LoopNests. This precludes *any* invalidation of loop nest analyses by the + // proxy, but that's OK because we've taken care to invalidate analyses in + // the loop nest analysis manager incrementally above. + PA.preserveSet<AllAnalysesOn<LoopNest>>(); + PA.preserve<LoopNestAnalysisManagerFunctionProxy>(); + // We also preserve the set of standard analyses. + detail::preserveLoopStandardAnalysisResults(PA, UseMemorySSA); + detail::preserveAACategory(PA); + return PA; + } + +private: + LoopNestPassT Pass; + bool UseMemorySSA; + FunctionPassManager LoopCanonicalizationFPM; +}; + +/// A function to deduce a loop nest pass type and wrap it in the templated +/// adaptor. +template <typename LoopNestPassT> +FunctionToLoopNestPassAdaptor<LoopNestPassT> +createFunctionToLoopNestPassAdaptor(LoopNestPassT Pass, + bool UseMemorySSA = false, + bool DebugLogging = false) { + return FunctionToLoopNestPassAdaptor<LoopNestPassT>( + std::move(Pass), UseMemorySSA, DebugLogging); +} + +/// Pass for printing a loop nest's property. This is similar to +/// \c LoopNestPrinterPass in \file LoopNestAnalysis.h but implemented as a +/// LoopNestPass. +class PrintLoopNestPass : public PassInfoMixin<PrintLoopNestPass> { + raw_ostream &OS; + std::string Banner; + +public: + PrintLoopNestPass(); + explicit PrintLoopNestPass(raw_ostream &OS, const std::string &Banner = ""); + + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, LNPMUpdater &U); +}; + +/// Adaptor that maps from a loop nest to its loops. +template <typename LoopPassT> +class LoopNestToLoopPassAdaptor + : public PassInfoMixin<LoopNestToLoopPassAdaptor<LoopPassT>> { +public: + explicit LoopNestToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {} + + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LNPMUpdater &U) { + PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(LN, AR); + PreservedAnalyses PA = PreservedAnalyses::all(); + + // Get the loop analysis manager from the loop nest analysis manager. No + // need to set up proxy here since currently the latter is simply a wrapper + // around the former. + LoopAnalysisManager &LAM = AM.getLoopAnalysisManager(); + + SmallPriorityWorklist<Loop *, 4> Worklist; + LPMUpdater Updater(Worklist, LAM); + appendLoopNestToWorklist(LN.getOutermostLoop(), Worklist); + + assert(!Worklist.empty() && + "Worklist should be non-empty since we're running on a LoopNest"); + do { + Loop *L = Worklist.pop_back_val(); + Updater.CurrentL = L; + Updater.SkipCurrentLoop = false; + +#ifndef NDEBUG + // Save a parent loop pointer for asserts. + Updater.ParentL = L->getParentLoop(); + + // Verify the loop structure and LCSSA form. + L->verifyLoop(); + assert(L->isRecursivelyLCSSAForm(AR.DT, AR.LI) && + "Loops must remain in LCSSA form!"); +#endif + + // Check the PassInstrumentation's BeforePass callbacks. + if (!PI.runBeforePass<Loop>(Pass, *L)) + continue; + + PreservedAnalyses PassPA; + { + TimeTraceScope TimeScope(Pass.name()); + PassPA = Pass.run(*L, LAM, AR, Updater); + } + + // Do not pass deleted Loop into the instrumentation. + if (Updater.skipCurrentLoop()) + PI.runAfterPassInvalidated<Loop>(Pass); + else + PI.runAfterPass<Loop>(Pass, *L); + + if (!Updater.SkipCurrentLoop) + // Invalidate the loop analysis results here. + LAM.invalidate(*L, PassPA); + + PA.intersect(std::move(PassPA)); + } while (!Worklist.empty()); + + // We don't have to explicitly mark the loop standard analysis results as + // preserved here since this will eventually be handled by the \c + // FunctionToLoopNestPassAdaptor. + PA.preserveSet<AllAnalysesOn<Loop>>(); + // FIXME: We should check whether the loop nest structure is preserved or + // not. + return PA; + } + +private: + LoopPassT Pass; +}; + +/// A function to deduce a loop pass type and wrap it in the templated +/// adaptor. +template <typename LoopPassT> +LoopNestToLoopPassAdaptor<LoopPassT> +createLoopNestToLoopPassAdaptor(LoopPassT Pass) { + return LoopNestToLoopPassAdaptor<LoopPassT>(std::move(Pass)); +} + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H Index: llvm/include/llvm/Passes/PassBuilder.h =================================================================== --- llvm/include/llvm/Passes/PassBuilder.h +++ llvm/include/llvm/Passes/PassBuilder.h @@ -17,10 +17,12 @@ #include "llvm/ADT/Optional.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/Error.h" #include "llvm/Transforms/IPO/Inliner.h" #include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Scalar/LoopNestPassManager.h" #include "llvm/Transforms/Scalar/LoopPassManager.h" #include <vector> @@ -270,6 +272,7 @@ /// This is an interface that can be used to cross register each /// AnalysisManager with all the others analysis managers. void crossRegisterProxies(LoopAnalysisManager &LAM, + LoopNestAnalysisManager &LNAM, FunctionAnalysisManager &FAM, CGSCCAnalysisManager &CGAM, ModuleAnalysisManager &MAM); @@ -305,6 +308,13 @@ /// additional analyses. void registerLoopAnalyses(LoopAnalysisManager &LAM); + /// Registers all available loop nest analysis passes. + /// + /// This is an interface that can be used to populate a \c + /// LoopNestAnalysisManager with all registered loop nest analyses. Callers + /// can still manually register any additional analyses. + void registerLoopNestAnalyses(LoopNestAnalysisManager &LNAM); + /// Construct the core LLVM function canonicalization and simplification /// pipeline. /// @@ -507,6 +517,9 @@ Error parsePassPipeline(LoopPassManager &LPM, StringRef PipelineText, bool VerifyEachPass = true, bool DebugLogging = false); + Error parsePassPipeline(LoopNestPassManager &LPM, StringRef PipelineText, + bool VerifyEachPass = true, + bool DebugLogging = false); /// @}} /// Parse a textual alias analysis pipeline into the provided AA manager. @@ -643,6 +656,10 @@ const std::function<void(LoopAnalysisManager &)> &C) { LoopAnalysisRegistrationCallbacks.push_back(C); } + void registerAnalysisRegistrationCallback( + const std::function<void(LoopNestAnalysisManager &)> &C) { + LoopNestAnalysisRegistrationCallbacks.push_back(C); + } void registerAnalysisRegistrationCallback( const std::function<void(ModuleAnalysisManager &)> &C) { ModuleAnalysisRegistrationCallbacks.push_back(C); @@ -668,6 +685,11 @@ ArrayRef<PipelineElement>)> &C) { LoopPipelineParsingCallbacks.push_back(C); } + void registerPipelineParsingCallback( + const std::function<bool(StringRef Name, LoopNestPassManager &, + ArrayRef<PipelineElement>)> &C) { + LoopNestPipelineParsingCallbacks.push_back(C); + } void registerPipelineParsingCallback( const std::function<bool(StringRef Name, ModulePassManager &, ArrayRef<PipelineElement>)> &C) { @@ -715,11 +737,16 @@ bool VerifyEachPass, bool DebugLogging); Error parseLoopPass(LoopPassManager &LPM, const PipelineElement &E, bool VerifyEachPass, bool DebugLogging); + Error parseLoopNestPass(LoopNestPassManager &LNPM, const PipelineElement &E, + bool VerifyEachPass, bool DebugLogging); bool parseAAPassName(AAManager &AA, StringRef Name); Error parseLoopPassPipeline(LoopPassManager &LPM, ArrayRef<PipelineElement> Pipeline, bool VerifyEachPass, bool DebugLogging); + Error parseLoopNestPassPipeline(LoopNestPassManager &LNPM, + ArrayRef<PipelineElement> Pipeline, + bool VerifyEachPass, bool DebugLogging); Error parseFunctionPassPipeline(FunctionPassManager &FPM, ArrayRef<PipelineElement> Pipeline, bool VerifyEachPass, bool DebugLogging); @@ -785,6 +812,13 @@ ArrayRef<PipelineElement>)>, 2> LoopPipelineParsingCallbacks; + // LoopNest callbacks + SmallVector<std::function<void(LoopNestAnalysisManager &)>, 2> + LoopNestAnalysisRegistrationCallbacks; + SmallVector<std::function<bool(StringRef, LoopNestPassManager &, + ArrayRef<PipelineElement>)>, + 2> + LoopNestPipelineParsingCallbacks; // AA callbacks SmallVector<std::function<bool(StringRef Name, AAManager &AA)>, 2> AAParsingCallbacks; Index: llvm/include/llvm/Analysis/LoopNestAnalysisManager.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/LoopNestAnalysisManager.h @@ -0,0 +1,210 @@ +//===- LoopNestAnalysisManager.h - LoopNest analysis management ---------*- C++ +//-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H +#define LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H + +#include "llvm/Analysis/LoopNestAnalysis.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LNPMUpdater; + +/// The loop nest analysis manager. +/// +/// The loop nest analyses should run on \Loop instead of LoopNests since +/// \c LoopNest are constantly invalidated by both loop nest passes and loop +/// passes. Generally speaking, the passes should update the analysis results +/// dynamically when possible, and running on Loops prevent the analyses from +/// being invalidated when the loop structures change. +/// +/// \c LoopNestAnalysisManager is a wrapper around \c LoopAnalysisManager and +/// provide all the public APIs that \c AnalysisManager has so that is seems to +/// be operating on \c LoopNest. \c LoopNestAnalysisManager also provides the +/// ability to construct \c LoopNest from the top-level \c Loop. The loop nest +/// analyses can also obtain the \c LoopNest object from the \c +/// LoopAnalysisManager. +/// +/// The \c LoopNest object will be invalidated after the loop nest passes unless +/// \c LoopNestAnalysis is explicitly marked as preserved. +template <> class AnalysisManager<LoopNest, LoopStandardAnalysisResults &> { +public: + class Invalidator { + public: + /// The following methods should never be called because the + /// invalidation in \c LoopNestAnalysisManager will be passed to the + /// internal \c LoopAnalysisManager. The only purpose of these methods is to + /// satisfy the requirements of being an \c AnalysisManager. + template <typename PassT> + bool invalidate(LoopNest &, const PreservedAnalyses &) { + assert(false && "This method should never be called."); + return false; + } + + bool invalidate(AnalysisKey *, LoopNest &, const PreservedAnalyses &) { + assert(false && "This method should never be called."); + return false; + } + }; + + AnalysisManager(LoopAnalysisManager &LAM) : InternalLAM(LAM) {} + + bool empty() const { return InternalLAM.empty(); }; + + void clear(LoopNest &LN, llvm::StringRef Name) { + InternalLAM.clear(LN.getOutermostLoop(), Name); + } + void clear(Loop &L, llvm::StringRef Name) { InternalLAM.clear(L, Name); } + void clear() { InternalLAM.clear(); } + + LoopNest &getLoopNest(Loop &Root, LoopStandardAnalysisResults &LAR) { + return InternalLAM.getResult<LoopNestAnalysis>(Root, LAR); + } + + /// Get the result of an analysis pass for a given LoopNest. + /// + /// Runs the analysis if a cached result is not available. + template <typename PassT> + typename PassT::Result &getResult(LoopNest &LN, + LoopStandardAnalysisResults &LAR) { + return InternalLAM.getResult<PassT>(LN.getOutermostLoop(), LAR); + } + template <typename PassT> + typename PassT::Result &getResult(Loop &L, LoopStandardAnalysisResults &LAR) { + return InternalLAM.getResult<PassT>(L, LAR); + } + + /// Get the cached result of an analysis pass for a given LoopNest. + /// + /// This method never runs the analysis. + /// + /// \returns null if there is no cached result. + template <typename PassT> + typename PassT::Result *getCachedResult(LoopNest &LN) const { + return InternalLAM.getCachedResult<PassT>(LN.getOutermostLoop()); + } + template <typename PassT> + typename PassT::Result *getCachedResult(Loop &L) const { + return InternalLAM.getCachedResult<PassT>(L); + } + + template <typename PassT> + void verifyNotInvalidated(LoopNest &LN, + typename PassT::Result *Result) const { + InternalLAM.verifyNotInvalidated<PassT>(LN.getOutermostLoop(), Result); + } + template <typename PassT> + void verifyNotInvalidated(Loop &L, typename PassT::Result *Result) const { + InternalLAM.verifyNotInvalidated<PassT>(L, Result); + } + + template <typename PassBuilderT> + bool registerPass(PassBuilderT &&PassBuilder) { + return InternalLAM.registerPass(std::forward<PassBuilderT>(PassBuilder)); + } + + void invalidate(LoopNest &LN, const PreservedAnalyses &PA) { + InternalLAM.invalidate(LN.getOutermostLoop(), PA); + } + void invalidate(Loop &L, const PreservedAnalyses &PA) { + InternalLAM.invalidate(L, PA); + } + + LoopAnalysisManager &getLoopAnalysisManager() { return InternalLAM; } + +private: + LoopAnalysisManager &InternalLAM; + friend class InnerAnalysisManagerProxy< + AnalysisManager<LoopNest, LoopStandardAnalysisResults &>, Function>; +}; + +using LoopNestAnalysisManager = + AnalysisManager<LoopNest, LoopStandardAnalysisResults &>; + +using LoopNestAnalysisManagerFunctionProxy = + InnerAnalysisManagerProxy<LoopNestAnalysisManager, Function>; + +/// A specialized result for the \c LoopNestAnalysisManagerFunctionProxy which +/// retains a \c LoopInfo reference. +/// +/// This allows it to collect loop nest objects for which analysis results may +/// be cached in the \c LoopNestAnalysisManager. +template <> class LoopNestAnalysisManagerFunctionProxy::Result { +public: + explicit Result(LoopNestAnalysisManager &InnerAM, LoopInfo &LI) + : InnerAM(&InnerAM), LI(&LI), MSSAUsed(false) {} + Result(Result &&Arg) + : InnerAM(std::move(Arg.InnerAM)), LI(Arg.LI), MSSAUsed(Arg.MSSAUsed) { + // We have to null out the analysis manager in the moved-from state + // because we are taking ownership of the responsibilty to clear the + // analysis state. + Arg.InnerAM = nullptr; + } + Result &operator=(Result &&RHS) { + InnerAM = RHS.InnerAM; + LI = RHS.LI; + MSSAUsed = RHS.MSSAUsed; + // We have to null out the analysis manager in the moved-from state + // because we are taking ownership of the responsibilty to clear the + // analysis state. + RHS.InnerAM = nullptr; + return *this; + } + ~Result() { + // InnerAM is cleared in a moved from state where there is nothing to do. + if (!InnerAM) + return; + + // Clear out the analysis manager if we're being destroyed -- it means we + // didn't even see an invalidate call when we got invalidated. + InnerAM->clear(); + } + + /// Mark MemorySSA as used so we can invalidate self if MSSA is invalidated. + void markMSSAUsed() { MSSAUsed = true; } + + /// Accessor for the analysis manager. + LoopNestAnalysisManager &getManager() { return *InnerAM; } + + /// Handler for invalidation of the proxy for a particular function. + /// + /// If the proxy, \c LoopInfo, and associated analyses are preserved, this + /// will merely forward the invalidation event to any cached loop analysis + /// results for loops within this function. + /// + /// If the necessary loop infrastructure is not preserved, this will forcibly + /// clear all of the cached analysis results that are keyed on the \c + /// LoopInfo for this function. + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv); + +private: + LoopNestAnalysisManager *InnerAM; + LoopInfo *LI; + bool MSSAUsed; +}; + +template <> +LoopNestAnalysisManagerFunctionProxy::Result +LoopNestAnalysisManagerFunctionProxy::run(Function &F, + FunctionAnalysisManager &AM); + +extern template class InnerAnalysisManagerProxy<LoopNestAnalysisManager, + Function>; + +extern template class OuterAnalysisManagerProxy< + FunctionAnalysisManager, LoopNest, LoopStandardAnalysisResults &>; +using FunctionAnalysisManagerLoopNestProxy = + OuterAnalysisManagerProxy<FunctionAnalysisManager, LoopNest, + LoopStandardAnalysisResults &>; + +} // namespace llvm + +#endif // LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H Index: llvm/include/llvm/Analysis/LoopNestAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/LoopNestAnalysis.h +++ llvm/include/llvm/Analysis/LoopNestAnalysis.h @@ -16,6 +16,7 @@ #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" namespace llvm { @@ -128,8 +129,16 @@ [](const Loop *L) { return L->isLoopSimplifyForm(); }); } + StringRef getName() const { + Loop &Root = getOutermostLoop(); + return Root.getName(); + } + + /// Reconstruct the loop nest inplace. + void reconstructInplace(ScalarEvolution &SE); + protected: - const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. + unsigned MaxPerfectDepth; // maximum perfect nesting depth level. LoopVectorTy Loops; // the loops in the nest (in breadth first order). }; Index: clang/lib/CodeGen/BackendUtil.cpp =================================================================== --- clang/lib/CodeGen/BackendUtil.cpp +++ clang/lib/CodeGen/BackendUtil.cpp @@ -1174,6 +1174,7 @@ #include "llvm/Support/Extension.def" LoopAnalysisManager LAM(CodeGenOpts.DebugPassManager); + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM(CodeGenOpts.DebugPassManager); CGSCCAnalysisManager CGAM(CodeGenOpts.DebugPassManager); ModuleAnalysisManager MAM(CodeGenOpts.DebugPassManager); @@ -1193,7 +1194,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM(CodeGenOpts.DebugPassManager);
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits