LLVM 19.0.0git
LoopExtractor.cpp
Go to the documentation of this file.
1//===- LoopExtractor.cpp - Extract each loop into a new function ----------===//
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// A pass wrapper around the ExtractLoop() scalar transformation to extract each
10// top-level loop into its own new function. If the loop is the ONLY loop in a
11// given function, it is not touched. This is a pass most useful for debugging
12// via bugpoint.
13//
14//===----------------------------------------------------------------------===//
15
17#include "llvm/ADT/Statistic.h"
20#include "llvm/IR/Dominators.h"
22#include "llvm/IR/Module.h"
23#include "llvm/IR/PassManager.h"
25#include "llvm/Pass.h"
26#include "llvm/Transforms/IPO.h"
29using namespace llvm;
30
31#define DEBUG_TYPE "loop-extract"
32
33STATISTIC(NumExtracted, "Number of loops extracted");
34
35namespace {
36struct LoopExtractorLegacyPass : public ModulePass {
37 static char ID; // Pass identification, replacement for typeid
38
39 unsigned NumLoops;
40
41 explicit LoopExtractorLegacyPass(unsigned NumLoops = ~0)
42 : ModulePass(ID), NumLoops(NumLoops) {
44 }
45
46 bool runOnModule(Module &M) override;
47
48 void getAnalysisUsage(AnalysisUsage &AU) const override {
55 }
56};
57
58struct LoopExtractor {
59 explicit LoopExtractor(
60 unsigned NumLoops,
61 function_ref<DominatorTree &(Function &)> LookupDomTree,
62 function_ref<LoopInfo &(Function &)> LookupLoopInfo,
63 function_ref<AssumptionCache *(Function &)> LookupAssumptionCache)
64 : NumLoops(NumLoops), LookupDomTree(LookupDomTree),
65 LookupLoopInfo(LookupLoopInfo),
66 LookupAssumptionCache(LookupAssumptionCache) {}
67 bool runOnModule(Module &M);
68
69private:
70 // The number of natural loops to extract from the program into functions.
71 unsigned NumLoops;
72
73 function_ref<DominatorTree &(Function &)> LookupDomTree;
74 function_ref<LoopInfo &(Function &)> LookupLoopInfo;
75 function_ref<AssumptionCache *(Function &)> LookupAssumptionCache;
76
78
79 bool extractLoops(Loop::iterator From, Loop::iterator To, LoopInfo &LI,
80 DominatorTree &DT);
81 bool extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT);
82};
83} // namespace
84
85char LoopExtractorLegacyPass::ID = 0;
86INITIALIZE_PASS_BEGIN(LoopExtractorLegacyPass, "loop-extract",
87 "Extract loops into new functions", false, false)
88INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
92INITIALIZE_PASS_END(LoopExtractorLegacyPass, "loop-extract",
93 "Extract loops into new functions", false, false)
94
95namespace {
96 /// SingleLoopExtractor - For bugpoint.
97struct SingleLoopExtractor : public LoopExtractorLegacyPass {
98 static char ID; // Pass identification, replacement for typeid
99 SingleLoopExtractor() : LoopExtractorLegacyPass(1) {}
100};
101} // End anonymous namespace
102
103char SingleLoopExtractor::ID = 0;
104INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single",
105 "Extract at most one loop into a new function", false, false)
106
107// createLoopExtractorPass - This pass extracts all natural loops from the
108// program into a function if it can.
109//
110Pass *llvm::createLoopExtractorPass() { return new LoopExtractorLegacyPass(); }
111
112bool LoopExtractorLegacyPass::runOnModule(Module &M) {
113 if (skipModule(M))
114 return false;
115
116 bool Changed = false;
117 auto LookupDomTree = [this](Function &F) -> DominatorTree & {
118 return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
119 };
120 auto LookupLoopInfo = [this, &Changed](Function &F) -> LoopInfo & {
121 return this->getAnalysis<LoopInfoWrapperPass>(F, &Changed).getLoopInfo();
122 };
123 auto LookupACT = [this](Function &F) -> AssumptionCache * {
124 if (auto *ACT = this->getAnalysisIfAvailable<AssumptionCacheTracker>())
125 return ACT->lookupAssumptionCache(F);
126 return nullptr;
127 };
128 return LoopExtractor(NumLoops, LookupDomTree, LookupLoopInfo, LookupACT)
129 .runOnModule(M) ||
130 Changed;
131}
132
133bool LoopExtractor::runOnModule(Module &M) {
134 if (M.empty())
135 return false;
136
137 if (!NumLoops)
138 return false;
139
140 bool Changed = false;
141
142 // The end of the function list may change (new functions will be added at the
143 // end), so we run from the first to the current last.
144 auto I = M.begin(), E = --M.end();
145 while (true) {
146 Function &F = *I;
147
148 Changed |= runOnFunction(F);
149 if (!NumLoops)
150 break;
151
152 // If this is the last function.
153 if (I == E)
154 break;
155
156 ++I;
157 }
158 return Changed;
159}
160
161bool LoopExtractor::runOnFunction(Function &F) {
162 // Do not modify `optnone` functions.
163 if (F.hasOptNone())
164 return false;
165
166 if (F.empty())
167 return false;
168
169 bool Changed = false;
170 LoopInfo &LI = LookupLoopInfo(F);
171
172 // If there are no loops in the function.
173 if (LI.empty())
174 return Changed;
175
176 DominatorTree &DT = LookupDomTree(F);
177
178 // If there is more than one top-level loop in this function, extract all of
179 // the loops.
180 if (std::next(LI.begin()) != LI.end())
181 return Changed | extractLoops(LI.begin(), LI.end(), LI, DT);
182
183 // Otherwise there is exactly one top-level loop.
184 Loop *TLL = *LI.begin();
185
186 // If the loop is in LoopSimplify form, then extract it only if this function
187 // is more than a minimal wrapper around the loop.
188 if (TLL->isLoopSimplifyForm()) {
189 bool ShouldExtractLoop = false;
190
191 // Extract the loop if the entry block doesn't branch to the loop header.
192 Instruction *EntryTI = F.getEntryBlock().getTerminator();
193 if (!isa<BranchInst>(EntryTI) ||
194 !cast<BranchInst>(EntryTI)->isUnconditional() ||
195 EntryTI->getSuccessor(0) != TLL->getHeader()) {
196 ShouldExtractLoop = true;
197 } else {
198 // Check to see if any exits from the loop are more than just return
199 // blocks.
201 TLL->getExitBlocks(ExitBlocks);
202 for (auto *ExitBlock : ExitBlocks)
203 if (!isa<ReturnInst>(ExitBlock->getTerminator())) {
204 ShouldExtractLoop = true;
205 break;
206 }
207 }
208
209 if (ShouldExtractLoop)
210 return Changed | extractLoop(TLL, LI, DT);
211 }
212
213 // Okay, this function is a minimal container around the specified loop.
214 // If we extract the loop, we will continue to just keep extracting it
215 // infinitely... so don't extract it. However, if the loop contains any
216 // sub-loops, extract them.
217 return Changed | extractLoops(TLL->begin(), TLL->end(), LI, DT);
218}
219
220bool LoopExtractor::extractLoops(Loop::iterator From, Loop::iterator To,
221 LoopInfo &LI, DominatorTree &DT) {
222 bool Changed = false;
224
225 // Save the list of loops, as it may change.
226 Loops.assign(From, To);
227 for (Loop *L : Loops) {
228 // If LoopSimplify form is not available, stay out of trouble.
229 if (!L->isLoopSimplifyForm())
230 continue;
231
232 Changed |= extractLoop(L, LI, DT);
233 if (!NumLoops)
234 break;
235 }
236 return Changed;
237}
238
239bool LoopExtractor::extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT) {
240 assert(NumLoops != 0);
241 Function &Func = *L->getHeader()->getParent();
242 AssumptionCache *AC = LookupAssumptionCache(Func);
244 CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC);
245 if (Extractor.extractCodeRegion(CEAC)) {
246 LI.erase(L);
247 --NumLoops;
248 ++NumExtracted;
249 return true;
250 }
251 return false;
252}
253
254// createSingleLoopExtractorPass - This pass extracts one natural loop from the
255// program into a function if it can. This is used by bugpoint.
256//
258 return new SingleLoopExtractor();
259}
260
262 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
263 auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
265 };
266 auto LookupLoopInfo = [&FAM](Function &F) -> LoopInfo & {
267 return FAM.getResult<LoopAnalysis>(F);
268 };
269 auto LookupAssumptionCache = [&FAM](Function &F) -> AssumptionCache * {
271 };
272 if (!LoopExtractor(NumLoops, LookupDomTree, LookupLoopInfo,
273 LookupAssumptionCache)
274 .runOnModule(M))
275 return PreservedAnalyses::all();
276
279 return PA;
280}
281
283 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
285 OS, MapClassName2PassName);
286 OS << '<';
287 if (NumLoops == 1)
288 OS << "single";
289 OS << '>';
290}
BlockVerifier::State From
static bool runOnFunction(Function &F, bool PostInlining)
Hexagon Hardware Loops
loop extract
loop Extract loops into new functions
loops
Definition: LoopInfo.cpp:1177
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
#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
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:283
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:658
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
BlockT * getHeader() const
std::vector< Loop * >::const_iterator iterator
iterator end() const
iterator begin() const
iterator end() const
iterator begin() const
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:875
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:479
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:251
virtual bool runOnModule(Module &M)=0
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
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
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
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
NodeAddr< FuncNode * > Func
Definition: RDFGraph.h:393
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void initializeLoopExtractorLegacyPassPass(PassRegistry &)
char & LoopSimplifyID
Pass * createLoopExtractorPass()
createLoopExtractorPass - This pass extracts all natural loops from the program into a function if it...
Pass * createSingleLoopExtractorPass()
createSingleLoopExtractorPass - This pass extracts one natural loop from the program into a function ...
char & BreakCriticalEdgesID
SingleLoopExtractor - For bugpoint.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:91