TaWeiTu created this revision.
TaWeiTu added reviewers: Whitney, etiotto, fedor.sergeev, chandlerc.
Herald added subscribers: llvm-commits, cfe-commits, asbirlea, dexonsmith,
steven_wu, hiraditya, mgorny.
Herald added projects: clang, LLVM.
TaWeiTu requested review of this revision.
Per http://llvm.org/OpenProjects.html#llvm_loopnest
<http://llvm.org/OpenProjects.html#llvm_loopnest>, the goal of this patch is to
create facilities that allow implementing loop nest passes that run on
top-level loop nests for the New Pass Manager.
Under the design, the loop nest passes will have a `run` method with the
following signature:
PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM,
LoopStandardAnalysisResults &AR, LNPMUpdater &U);
`LNPMUpdater` (short for loop nest pass manager updater) supports invalidating
loop nests (`markLoopNestAsDeleted`), re-visiting the current loop nest
(`revisitCurrentLoopNest`) and adding new top-level loop nests to the function
(`addNewLoopNests`).
The loop nest passes can be grouped together by `LoopNestPassManager`, and then
embedded into an `FPM` via `FunctionToLoopNestPassAdaptor`. Since both
`FunctionToLoopNestPassAdaptor` and `FunctionToLoopPassAdaptor` require loop
canonicalization passes to be run first, the `LoopNestToLoopPassAdaptor` is
also introduced in the patch.
The intended usage of the adaptor is to group the loop passes together into an
`LPM` first, and then embed the `LPM` into `LoopNestPassManager`. With this,
the loop canonicalization phase will be run only once for both loop and loop
nest passes.
Currently, the `LoopNestAnalysisManager` is nothing but a wrapper around
`LoopAnalysisManager` that provides the APIs on `LoopNest` and forwards the
requests to the internal LPM. That is, the loop nest analyses should still be
implemented as loop analyses.
The reason behind the design is that we do not support updating the `LoopNest`
object dynamically yet. That means the `LoopNest` object will be constantly
invalidated by the loop nest passes and loop passes, and invalidating a
`LoopNest` structure means that we have to invalidate all analyses associated
with it. This is quite inefficient since the analyses might have the ability to
be maintained online.
Other facilities like parsing the pipeline, the proxies between analysis
managers, are also implemented in this patch. The `PassBuilderCallbacksTest`
has also been applied to loop-nest-related infrastructures. The actual
functionalities of the components, however, are not tested yet. Still,
embedding loop passes into LNPM seems to be working as I've modified some
existing loop-pass related tests to verify the results. Also, all the existing
unit-tests and regression-tests work, so at least this is not breaking anything
now.
Though we definitely need more testing on the functionalities, I would like the
submit the diff earlier to see what you think about the patch and the design.
Fine-grained tests will be added later.
Please kindly provide feedbacks and comments on the patch. Thank you very much!
Repository:
rG LLVM Github Monorepo
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
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,136 @@
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,
+ 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,
+ 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,78 @@
+; 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
+}
+
+
+; CHECK: IsPerfect=true, Depth=2, OutermostLoop: for.cond, Loops: ( for.cond for.cond1 )
+define i32 @f2(i32 %n) #0 {
+entry:
+ %cmp4 = icmp slt i32 0, %n
+ br i1 %cmp4, label %for.body.lr.ph, label %for.end6
+
+for.body.lr.ph: ; preds = %entry
+ br label %for.body
+
+for.body: ; preds = %for.body.lr.ph, %for.inc4
+ %res.06 = phi i32 [ 0, %for.body.lr.ph ], [ %res.1.lcssa, %for.inc4 ]
+ %i.05 = phi i32 [ 0, %for.body.lr.ph ], [ %inc5, %for.inc4 ]
+ %cmp21 = icmp slt i32 0, %n
+ br i1 %cmp21, label %for.body3.lr.ph, label %for.end
+
+for.body3.lr.ph: ; preds = %for.body
+ br label %for.body3
+
+for.body3: ; preds = %for.body3.lr.ph, %for.inc
+ %j.03 = phi i32 [ 0, %for.body3.lr.ph ], [ %inc, %for.inc ]
+ %res.12 = phi i32 [ %res.06, %for.body3.lr.ph ], [ %add, %for.inc ]
+ %add = add nsw i32 %res.12, %i.05
+ br label %for.inc
+
+for.inc: ; preds = %for.body3
+ %inc = add nsw i32 %j.03, 1
+ %cmp2 = icmp slt i32 %inc, %n
+ br i1 %cmp2, label %for.body3, label %for.cond1.for.end_crit_edge
+
+for.cond1.for.end_crit_edge: ; preds = %for.inc
+ %split = phi i32 [ %add, %for.inc ]
+ br label %for.end
+
+for.end: ; preds = %for.cond1.for.end_crit_edge, %for.body
+ %res.1.lcssa = phi i32 [ %split, %for.cond1.for.end_crit_edge ], [ %res.06, %for.body ]
+ br label %for.inc4
+
+for.inc4: ; preds = %for.end
+ %inc5 = add nsw i32 %i.05, 1
+ %cmp = icmp slt i32 %inc5, %n
+ br i1 %cmp, label %for.body, label %for.cond.for.end6_crit_edge
+
+for.cond.for.end6_crit_edge: ; preds = %for.inc4
+ %split7 = phi i32 [ %res.1.lcssa, %for.inc4 ]
+ br label %for.end6
+
+for.end6: ; preds = %for.cond.for.end6_crit_edge, %entry
+ %res.0.lcssa = phi i32 [ %split7, %for.cond.for.end6_crit_edge ], [ 0, %entry ]
+ 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,26 @@
},
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("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,6 +387,29 @@
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(LoopNest &, LoopNestAnalysisManager &,
+ LoopStandardAnalysisResults &) {
+ return Result();
+ }
+ static StringRef name() { return "NoOpLoopNestAnalysis"; }
+};
+
AnalysisKey NoOpModuleAnalysis::Key;
AnalysisKey NoOpCGSCCAnalysis::Key;
AnalysisKey NoOpFunctionAnalysis::Key;
@@ -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;
+ 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;
Index: llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h
===================================================================
--- /dev/null
+++ llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h
@@ -0,0 +1,345 @@
+//===- 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 needs to be skipped due
+ /// to updates to the loop nest.
+ ///
+ /// If this returns true, the loop 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.
+ 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 module
+ // analyses will eventually occur when the module 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.
+ 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>();
+ 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 &LAR, LNPMUpdater &U) {
+ PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(LN, LAR);
+ 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;
+
+ if (!PI.runBeforePass<Loop>(Pass, *L))
+ continue;
+
+ PreservedAnalyses PassPA;
+ {
+ TimeTraceScope TimeScope(Pass.name());
+ PassPA = Pass.run(*L, LAM, LAR, Updater);
+ }
+
+ if (Updater.skipCurrentLoop())
+ PI.runAfterPassInvalidated<Loop>(Pass);
+ else
+ PI.runAfterPass<Loop>(Pass, *L);
+
+ if (!Updater.SkipCurrentLoop)
+ 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>>();
+ 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,11 +17,13 @@
#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/LoopPassManager.h"
+#include "llvm/Transforms/Scalar/LoopNestPassManager.h"
#include <vector>
namespace llvm {
@@ -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(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
