LLVM 18.0.0git
LoopRotation.cpp
Go to the documentation of this file.
1//===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements Loop Rotation Pass.
10//
11//===----------------------------------------------------------------------===//
12
28#include <optional>
29using namespace llvm;
30
31#define DEBUG_TYPE "loop-rotate"
32
34 "rotation-max-header-size", cl::init(16), cl::Hidden,
35 cl::desc("The default maximum header size for automatic loop rotation"));
36
38 "rotation-prepare-for-lto", cl::init(false), cl::Hidden,
39 cl::desc("Run loop-rotation in the prepare-for-lto stage. This option "
40 "should be used for testing only."));
41
42LoopRotatePass::LoopRotatePass(bool EnableHeaderDuplication, bool PrepareForLTO)
43 : EnableHeaderDuplication(EnableHeaderDuplication),
44 PrepareForLTO(PrepareForLTO) {}
45
47 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
48 static_cast<PassInfoMixin<LoopRotatePass> *>(this)->printPipeline(
49 OS, MapClassName2PassName);
50 OS << "<";
51 if (!EnableHeaderDuplication)
52 OS << "no-";
53 OS << "header-duplication;";
54
55 if (!PrepareForLTO)
56 OS << "no-";
57 OS << "prepare-for-lto";
58 OS << ">";
59}
60
63 LPMUpdater &) {
64 // Vectorization requires loop-rotation. Use default threshold for loops the
65 // user explicitly marked for vectorization, even when header duplication is
66 // disabled.
67 int Threshold = EnableHeaderDuplication ||
70 : 0;
71 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
73
74 std::optional<MemorySSAUpdater> MSSAU;
75 if (AR.MSSA)
76 MSSAU = MemorySSAUpdater(AR.MSSA);
77 bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE,
78 MSSAU ? &*MSSAU : nullptr, SQ, false, Threshold,
79 false, PrepareForLTO || PrepareForLTOOption);
80
81 if (!Changed)
83
84 if (AR.MSSA && VerifyMemorySSA)
86
88 if (AR.MSSA)
89 PA.preserve<MemorySSAAnalysis>();
90 return PA;
91}
92
93namespace {
94
95class LoopRotateLegacyPass : public LoopPass {
96 unsigned MaxHeaderSize;
97 bool PrepareForLTO;
98
99public:
100 static char ID; // Pass ID, replacement for typeid
101 LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1,
102 bool PrepareForLTO = false)
103 : LoopPass(ID), PrepareForLTO(PrepareForLTO) {
105 if (SpecifiedMaxHeaderSize == -1)
106 MaxHeaderSize = DefaultRotationThreshold;
107 else
108 MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
109 }
110
111 // LCSSA form makes instruction renaming easier.
112 void getAnalysisUsage(AnalysisUsage &AU) const override {
117
118 // Lazy BFI and BPI are marked as preserved here so LoopRotate
119 // can remain part of the same loop pass manager as LICM.
122 }
123
124 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
125 if (skipLoop(L))
126 return false;
127 Function &F = *L->getHeader()->getParent();
128
129 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
130 const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
131 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
132 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
133 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
134 const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
135 std::optional<MemorySSAUpdater> MSSAU;
136 // Not requiring MemorySSA and getting it only if available will split
137 // the loop pass pipeline when LoopRotate is being run first.
138 auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
139 if (MSSAA)
140 MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
141 // Vectorization requires loop-rotation. Use default threshold for loops the
142 // user explicitly marked for vectorization, even when header duplication is
143 // disabled.
144 int Threshold = hasVectorizeTransformation(L) == TM_ForcedByUser
146 : MaxHeaderSize;
147
148 return LoopRotation(L, LI, TTI, AC, &DT, &SE, MSSAU ? &*MSSAU : nullptr, SQ,
149 false, Threshold, false,
150 PrepareForLTO || PrepareForLTOOption);
151 }
152};
153} // end namespace
154
155char LoopRotateLegacyPass::ID = 0;
156INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
157 false, false)
162INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
163 false)
164
165Pass *llvm::createLoopRotatePass(int MaxHeaderSize, bool PrepareForLTO) {
166 return new LoopRotateLegacyPass(MaxHeaderSize, PrepareForLTO);
167}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Hexagon Hardware Loops
static cl::opt< unsigned > DefaultRotationThreshold("rotation-max-header-size", cl::init(16), cl::Hidden, cl::desc("The default maximum header size for automatic loop rotation"))
static cl::opt< bool > PrepareForLTOOption("rotation-prepare-for-lto", cl::init(false), cl::Hidden, cl::desc("Run loop-rotation in the prepare-for-lto stage. This option " "should be used for testing only."))
loop rotate
#define F(x, y, z)
Definition: MD5.cpp:55
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
raw_pwrite_stream & OS
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
An immutable pass that tracks lazily created AssumptionCache objects.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
This is an alternative analysis pass to BranchProbabilityInfoWrapperPass.
LoopRotatePass(bool EnableHeaderDuplication=true, bool PrepareForLTO=false)
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:975
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1857
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Pass * createLoopRotatePass(int MaxHeaderSize=-1, bool PrepareForLTO=false)
TransformationMode hasVectorizeTransformation(const Loop *L)
Definition: LoopUtils.cpp:391
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:141
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:292
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
void initializeLoopRotateLegacyPassPass(PassRegistry &)
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, bool RotationOnly, unsigned Threshold, bool IsUtilMode, bool PrepareForLTO=false)
Convert a loop into a loop with bottom test.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371