LLVM  14.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"
27 #include "llvm/Transforms/IPO.h"
28 #include "llvm/Transforms/Scalar.h"
29 #include "llvm/Transforms/Utils.h"
32 #include <fstream>
33 #include <set>
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "loop-extract"
37 
38 STATISTIC(NumExtracted, "Number of loops extracted");
39 
40 namespace {
41 struct LoopExtractorLegacyPass : public ModulePass {
42  static char ID; // Pass identification, replacement for typeid
43 
44  unsigned NumLoops;
45 
46  explicit LoopExtractorLegacyPass(unsigned NumLoops = ~0)
47  : ModulePass(ID), NumLoops(NumLoops) {
49  }
50 
51  bool runOnModule(Module &M) override;
52 
53  void getAnalysisUsage(AnalysisUsage &AU) const override {
60  }
61 };
62 
63 struct LoopExtractor {
64  explicit LoopExtractor(
65  unsigned NumLoops,
66  function_ref<DominatorTree &(Function &)> LookupDomTree,
67  function_ref<LoopInfo &(Function &)> LookupLoopInfo,
68  function_ref<AssumptionCache *(Function &)> LookupAssumptionCache)
69  : NumLoops(NumLoops), LookupDomTree(LookupDomTree),
70  LookupLoopInfo(LookupLoopInfo),
71  LookupAssumptionCache(LookupAssumptionCache) {}
72  bool runOnModule(Module &M);
73 
74 private:
75  // The number of natural loops to extract from the program into functions.
76  unsigned NumLoops;
77 
78  function_ref<DominatorTree &(Function &)> LookupDomTree;
79  function_ref<LoopInfo &(Function &)> LookupLoopInfo;
80  function_ref<AssumptionCache *(Function &)> LookupAssumptionCache;
81 
82  bool runOnFunction(Function &F);
83 
84  bool extractLoops(Loop::iterator From, Loop::iterator To, LoopInfo &LI,
85  DominatorTree &DT);
86  bool extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT);
87 };
88 } // namespace
89 
91 INITIALIZE_PASS_BEGIN(LoopExtractorLegacyPass, "loop-extract",
92  "Extract loops into new functions", false, false)
93 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
96 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
97 INITIALIZE_PASS_END(LoopExtractorLegacyPass, "loop-extract",
99 
100 namespace {
101  /// SingleLoopExtractor - For bugpoint.
102 struct SingleLoopExtractor : public LoopExtractorLegacyPass {
103  static char ID; // Pass identification, replacement for typeid
104  SingleLoopExtractor() : LoopExtractorLegacyPass(1) {}
105 };
106 } // End anonymous namespace
107 
108 char SingleLoopExtractor::ID = 0;
109 INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single",
110  "Extract at most one loop into a new function", false, false)
111 
112 // createLoopExtractorPass - This pass extracts all natural loops from the
113 // program into a function if it can.
114 //
115 Pass *llvm::createLoopExtractorPass() { return new LoopExtractorLegacyPass(); }
116 
117 bool LoopExtractorLegacyPass::runOnModule(Module &M) {
118  if (skipModule(M))
119  return false;
120 
121  bool Changed = false;
122  auto LookupDomTree = [this](Function &F) -> DominatorTree & {
123  return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
124  };
125  auto LookupLoopInfo = [this, &Changed](Function &F) -> LoopInfo & {
126  return this->getAnalysis<LoopInfoWrapperPass>(F, &Changed).getLoopInfo();
127  };
128  auto LookupACT = [this](Function &F) -> AssumptionCache * {
129  if (auto *ACT = this->getAnalysisIfAvailable<AssumptionCacheTracker>())
130  return ACT->lookupAssumptionCache(F);
131  return nullptr;
132  };
133  return LoopExtractor(NumLoops, LookupDomTree, LookupLoopInfo, LookupACT)
134  .runOnModule(M) ||
135  Changed;
136 }
137 
138 bool LoopExtractor::runOnModule(Module &M) {
139  if (M.empty())
140  return false;
141 
142  if (!NumLoops)
143  return false;
144 
145  bool Changed = false;
146 
147  // The end of the function list may change (new functions will be added at the
148  // end), so we run from the first to the current last.
149  auto I = M.begin(), E = --M.end();
150  while (true) {
151  Function &F = *I;
152 
153  Changed |= runOnFunction(F);
154  if (!NumLoops)
155  break;
156 
157  // If this is the last function.
158  if (I == E)
159  break;
160 
161  ++I;
162  }
163  return Changed;
164 }
165 
167  // Do not modify `optnone` functions.
168  if (F.hasOptNone())
169  return false;
170 
171  if (F.empty())
172  return false;
173 
174  bool Changed = false;
175  LoopInfo &LI = LookupLoopInfo(F);
176 
177  // If there are no loops in the function.
178  if (LI.empty())
179  return Changed;
180 
181  DominatorTree &DT = LookupDomTree(F);
182 
183  // If there is more than one top-level loop in this function, extract all of
184  // the loops.
185  if (std::next(LI.begin()) != LI.end())
186  return Changed | extractLoops(LI.begin(), LI.end(), LI, DT);
187 
188  // Otherwise there is exactly one top-level loop.
189  Loop *TLL = *LI.begin();
190 
191  // If the loop is in LoopSimplify form, then extract it only if this function
192  // is more than a minimal wrapper around the loop.
193  if (TLL->isLoopSimplifyForm()) {
194  bool ShouldExtractLoop = false;
195 
196  // Extract the loop if the entry block doesn't branch to the loop header.
197  Instruction *EntryTI = F.getEntryBlock().getTerminator();
198  if (!isa<BranchInst>(EntryTI) ||
199  !cast<BranchInst>(EntryTI)->isUnconditional() ||
200  EntryTI->getSuccessor(0) != TLL->getHeader()) {
201  ShouldExtractLoop = true;
202  } else {
203  // Check to see if any exits from the loop are more than just return
204  // blocks.
205  SmallVector<BasicBlock *, 8> ExitBlocks;
206  TLL->getExitBlocks(ExitBlocks);
207  for (auto *ExitBlock : ExitBlocks)
208  if (!isa<ReturnInst>(ExitBlock->getTerminator())) {
209  ShouldExtractLoop = true;
210  break;
211  }
212  }
213 
214  if (ShouldExtractLoop)
215  return Changed | extractLoop(TLL, LI, DT);
216  }
217 
218  // Okay, this function is a minimal container around the specified loop.
219  // If we extract the loop, we will continue to just keep extracting it
220  // infinitely... so don't extract it. However, if the loop contains any
221  // sub-loops, extract them.
222  return Changed | extractLoops(TLL->begin(), TLL->end(), LI, DT);
223 }
224 
225 bool LoopExtractor::extractLoops(Loop::iterator From, Loop::iterator To,
226  LoopInfo &LI, DominatorTree &DT) {
227  bool Changed = false;
229 
230  // Save the list of loops, as it may change.
231  Loops.assign(From, To);
232  for (Loop *L : Loops) {
233  // If LoopSimplify form is not available, stay out of trouble.
234  if (!L->isLoopSimplifyForm())
235  continue;
236 
237  Changed |= extractLoop(L, LI, DT);
238  if (!NumLoops)
239  break;
240  }
241  return Changed;
242 }
243 
244 bool LoopExtractor::extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT) {
245  assert(NumLoops != 0);
246  Function &Func = *L->getHeader()->getParent();
247  AssumptionCache *AC = LookupAssumptionCache(Func);
248  CodeExtractorAnalysisCache CEAC(Func);
249  CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC);
250  if (Extractor.extractCodeRegion(CEAC)) {
251  LI.erase(L);
252  --NumLoops;
253  ++NumExtracted;
254  return true;
255  }
256  return false;
257 }
258 
259 // createSingleLoopExtractorPass - This pass extracts one natural loop from the
260 // program into a function if it can. This is used by bugpoint.
261 //
263  return new SingleLoopExtractor();
264 }
265 
267  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
268  auto LookupDomTree = [&FAM](Function &F) -> DominatorTree & {
270  };
271  auto LookupLoopInfo = [&FAM](Function &F) -> LoopInfo & {
272  return FAM.getResult<LoopAnalysis>(F);
273  };
274  auto LookupAssumptionCache = [&FAM](Function &F) -> AssumptionCache * {
276  };
277  if (!LoopExtractor(NumLoops, LookupDomTree, LookupLoopInfo,
278  LookupAssumptionCache)
279  .runOnModule(M))
280  return PreservedAnalyses::all();
281 
283  PA.preserve<LoopAnalysis>();
284  return PA;
285 }
286 
288  raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
289  static_cast<PassInfoMixin<LoopExtractorPass> *>(this)->printPipeline(
290  OS, MapClassName2PassName);
291  OS << "<";
292  if (NumLoops == 1)
293  OS << "single";
294  OS << ">";
295 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
AssumptionCache.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:62
INITIALIZE_PASS
INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single", "Extract at most one loop into a new function", false, false) Pass *llvm
Definition: LoopExtractor.cpp:109
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
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:785
Scalar.h
llvm::PassInfoMixin< LoopExtractorPass >
false::SingleLoopExtractor
SingleLoopExtractor - For bugpoint.
Definition: LoopExtractor.cpp:102
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:1168
Statistic.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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:1268
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:154
CodeExtractor.h
loops
loops
Definition: LoopInfo.cpp:1175
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:56
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...
CommandLine.h
llvm::createSingleLoopExtractorPass
Pass * createSingleLoopExtractorPass()
createSingleLoopExtractorPass - This pass extracts one natural loop from the program into a function ...
Definition: LoopExtractor.cpp:262
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:155
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
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:53
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
Utils.h
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: STLExtras.h:168
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:478
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
IPO.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
functions
loop Extract loops into new functions
Definition: LoopExtractor.cpp:98
extract
loop extract
Definition: LoopExtractor.cpp:97
llvm::LoopInfo::erase
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:878
llvm::LoopInfoBase::begin
iterator begin() const
Definition: LoopInfo.h:942
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
LoopExtractor.h
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::LoopInfo
Definition: LoopInfo.h:1083
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:41
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:287
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::initializeLoopExtractorLegacyPassPass
void initializeLoopExtractorLegacyPassPass(PassRegistry &)
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:800
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
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:804
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:103
false::SingleLoopExtractor::SingleLoopExtractor
SingleLoopExtractor()
Definition: LoopExtractor.cpp:104
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:252
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:943
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:151
Dominators.h
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:946
llvm::LoopExtractorPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: LoopExtractor.cpp:266
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
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:942
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
BasicBlockUtils.h
InitializePasses.h
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1243
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37