LLVM  15.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"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/IR/PassManager.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Transforms/IPO.h"
27 #include "llvm/Transforms/Utils.h"
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "loop-extract"
32 
33 STATISTIC(NumExtracted, "Number of loops extracted");
34 
35 namespace {
36 struct 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 
58 struct 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 
69 private:
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 
77  bool runOnFunction(Function &F);
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 
86 INITIALIZE_PASS_BEGIN(LoopExtractorLegacyPass, "loop-extract",
87  "Extract loops into new functions", false, false)
88 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
91 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
92 INITIALIZE_PASS_END(LoopExtractorLegacyPass, "loop-extract",
94 
95 namespace {
96  /// SingleLoopExtractor - For bugpoint.
97 struct SingleLoopExtractor : public LoopExtractorLegacyPass {
98  static char ID; // Pass identification, replacement for typeid
99  SingleLoopExtractor() : LoopExtractorLegacyPass(1) {}
100 };
101 } // End anonymous namespace
102 
103 char SingleLoopExtractor::ID = 0;
104 INITIALIZE_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 //
110 Pass *llvm::createLoopExtractorPass() { return new LoopExtractorLegacyPass(); }
111 
112 bool 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 
133 bool 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 
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.
200  SmallVector<BasicBlock *, 8> ExitBlocks;
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 
220 bool 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 
239 bool LoopExtractor::extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT) {
240  assert(NumLoops != 0);
241  Function &Func = *L->getHeader()->getParent();
242  AssumptionCache *AC = LookupAssumptionCache(Func);
243  CodeExtractorAnalysisCache CEAC(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 
278  PA.preserve<LoopAnalysis>();
279  return PA;
280 }
281 
283  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
284  static_cast<PassInfoMixin<LoopExtractorPass> *>(this)->printPipeline(
285  OS, MapClassName2PassName);
286  OS << "<";
287  if (NumLoops == 1)
288  OS << "single";
289  OS << ">";
290 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
AssumptionCache.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::LoopBase::getExitBlocks
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:61
INITIALIZE_PASS
INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single", "Extract at most one loop into a new function", false, false) Pass *llvm
Definition: LoopExtractor.cpp:104
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:248
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
llvm::PassInfoMixin< LoopExtractorPass >
false::SingleLoopExtractor
SingleLoopExtractor - For bugpoint.
Definition: LoopExtractor.cpp:97
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
Pass.h
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1287
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:170
CodeExtractor.h
loops
loops
Definition: LoopInfo.cpp:1176
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
F
#define F(x, y, z)
Definition: MD5.cpp:55
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::createLoopExtractorPass
Pass * createLoopExtractorPass()
createLoopExtractorPass - This pass extracts all natural loops from the program into a function if it...
llvm::createSingleLoopExtractorPass
Pass * createSingleLoopExtractorPass()
createSingleLoopExtractorPass - This pass extracts one natural loop from the program into a function ...
Definition: LoopExtractor.cpp:257
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:171
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
Utils.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
into
Clang compiles this into
Definition: README.txt:504
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:475
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
IPO.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
functions
loop Extract loops into new functions
Definition: LoopExtractor.cpp:93
extract
loop extract
Definition: LoopExtractor.cpp:92
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:875
llvm::LoopInfoBase::begin
iterator begin() const
Definition: LoopInfo.h:961
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
LoopExtractor.h
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:202
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::CodeExtractor
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
llvm::ifs::IFSSymbolType::Func
@ Func
llvm::LoopExtractorPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: LoopExtractor.cpp:282
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::initializeLoopExtractorLegacyPassPass
void initializeLoopExtractorLegacyPassPass(PassRegistry &)
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:794
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:799
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopExtractorLegacyPass, "loop-extract", "Extract loops into new functions", false, false) INITIALIZE_PASS_END(LoopExtractorLegacyPass
PassManager.h
false::SingleLoopExtractor::ID
static char ID
Definition: LoopExtractor.cpp:98
false::SingleLoopExtractor::SingleLoopExtractor
SingleLoopExtractor()
Definition: LoopExtractor.cpp:99
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::CodeExtractorAnalysisCache
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:962
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
llvm::LoopBase< BasicBlock, Loop >::iterator
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:167
Dominators.h
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:965
llvm::LoopExtractorPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: LoopExtractor.cpp:261
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::AnalysisUsage::addUsedIfAvailable
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
Definition: PassAnalysisSupport.h:117
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:937
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:277
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
InitializePasses.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38