LLVM 17.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
48 LPMUpdater &) {
49 // Vectorization requires loop-rotation. Use default threshold for loops the
50 // user explicitly marked for vectorization, even when header duplication is
51 // disabled.
52 int Threshold = EnableHeaderDuplication ||
55 : 0;
56 const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
58
59 std::optional<MemorySSAUpdater> MSSAU;
60 if (AR.MSSA)
61 MSSAU = MemorySSAUpdater(AR.MSSA);
62 bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE,
63 MSSAU ? &*MSSAU : nullptr, SQ, false, Threshold,
64 false, PrepareForLTO || PrepareForLTOOption);
65
66 if (!Changed)
68
69 if (AR.MSSA && VerifyMemorySSA)
71
73 if (AR.MSSA)
74 PA.preserve<MemorySSAAnalysis>();
75 return PA;
76}
77
78namespace {
79
80class LoopRotateLegacyPass : public LoopPass {
81 unsigned MaxHeaderSize;
82 bool PrepareForLTO;
83
84public:
85 static char ID; // Pass ID, replacement for typeid
86 LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1,
87 bool PrepareForLTO = false)
88 : LoopPass(ID), PrepareForLTO(PrepareForLTO) {
90 if (SpecifiedMaxHeaderSize == -1)
91 MaxHeaderSize = DefaultRotationThreshold;
92 else
93 MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
94 }
95
96 // LCSSA form makes instruction renaming easier.
97 void getAnalysisUsage(AnalysisUsage &AU) const override {
102
103 // Lazy BFI and BPI are marked as preserved here so LoopRotate
104 // can remain part of the same loop pass manager as LICM.
107 }
108
109 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
110 if (skipLoop(L))
111 return false;
112 Function &F = *L->getHeader()->getParent();
113
114 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
115 const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
116 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
117 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
118 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
119 const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
120 std::optional<MemorySSAUpdater> MSSAU;
121 // Not requiring MemorySSA and getting it only if available will split
122 // the loop pass pipeline when LoopRotate is being run first.
123 auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
124 if (MSSAA)
125 MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
126 // Vectorization requires loop-rotation. Use default threshold for loops the
127 // user explicitly marked for vectorization, even when header duplication is
128 // disabled.
129 int Threshold = hasVectorizeTransformation(L) == TM_ForcedByUser
131 : MaxHeaderSize;
132
133 return LoopRotation(L, LI, TTI, AC, &DT, &SE, MSSAU ? &*MSSAU : nullptr, SQ,
134 false, Threshold, false,
135 PrepareForLTO || PrepareForLTOOption);
136 }
137};
138} // end namespace
139
140char LoopRotateLegacyPass::ID = 0;
141INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
142 false, false)
147INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
148 false)
149
150Pass *llvm::createLoopRotatePass(int MaxHeaderSize, bool PrepareForLTO) {
151 return new LoopRotateLegacyPass(MaxHeaderSize, PrepareForLTO);
152}
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
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)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:936
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:986
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:1862
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
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
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
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:89
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:288
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...