LLVM  12.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 
16 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/InitializePasses.h"
23 #include "llvm/Pass.h"
25 #include "llvm/Transforms/IPO.h"
26 #include "llvm/Transforms/Scalar.h"
27 #include "llvm/Transforms/Utils.h"
30 #include <fstream>
31 #include <set>
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "loop-extract"
35 
36 STATISTIC(NumExtracted, "Number of loops extracted");
37 
38 namespace {
39  struct LoopExtractor : public ModulePass {
40  static char ID; // Pass identification, replacement for typeid
41 
42  // The number of natural loops to extract from the program into functions.
43  unsigned NumLoops;
44 
45  explicit LoopExtractor(unsigned numLoops = ~0)
46  : ModulePass(ID), NumLoops(numLoops) {
48  }
49 
50  bool runOnModule(Module &M) override;
51  bool runOnFunction(Function &F);
52 
53  bool extractLoops(Loop::iterator From, Loop::iterator To, LoopInfo &LI,
54  DominatorTree &DT);
55  bool extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT);
56 
57  void getAnalysisUsage(AnalysisUsage &AU) const override {
64  }
65  };
66 }
67 
68 char LoopExtractor::ID = 0;
69 INITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract",
70  "Extract loops into new functions", false, false)
71 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
74 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
75 INITIALIZE_PASS_END(LoopExtractor, "loop-extract",
76  "Extract loops into new functions", false, false)
77 
78 namespace {
79  /// SingleLoopExtractor - For bugpoint.
80  struct SingleLoopExtractor : public LoopExtractor {
81  static char ID; // Pass identification, replacement for typeid
82  SingleLoopExtractor() : LoopExtractor(1) {}
83  };
84 } // End anonymous namespace
85 
87 INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single",
88  "Extract at most one loop into a new function", false, false)
89 
90 // createLoopExtractorPass - This pass extracts all natural loops from the
91 // program into a function if it can.
92 //
93 Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); }
94 
95 bool LoopExtractor::runOnModule(Module &M) {
96  if (skipModule(M))
97  return false;
98 
99  if (M.empty())
100  return false;
101 
102  if (!NumLoops)
103  return false;
104 
105  bool Changed = false;
106 
107  // The end of the function list may change (new functions will be added at the
108  // end), so we run from the first to the current last.
109  auto I = M.begin(), E = --M.end();
110  while (true) {
111  Function &F = *I;
112 
113  Changed |= runOnFunction(F);
114  if (!NumLoops)
115  break;
116 
117  // If this is the last function.
118  if (I == E)
119  break;
120 
121  ++I;
122  }
123  return Changed;
124 }
125 
127  // Do not modify `optnone` functions.
128  if (F.hasOptNone())
129  return false;
130 
131  if (F.empty())
132  return false;
133 
134  bool Changed = false;
135  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>(F, &Changed).getLoopInfo();
136 
137  // If there are no loops in the function.
138  if (LI.empty())
139  return Changed;
140 
141  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
142 
143  // If there is more than one top-level loop in this function, extract all of
144  // the loops.
145  if (std::next(LI.begin()) != LI.end())
146  return Changed | extractLoops(LI.begin(), LI.end(), LI, DT);
147 
148  // Otherwise there is exactly one top-level loop.
149  Loop *TLL = *LI.begin();
150 
151  // If the loop is in LoopSimplify form, then extract it only if this function
152  // is more than a minimal wrapper around the loop.
153  if (TLL->isLoopSimplifyForm()) {
154  bool ShouldExtractLoop = false;
155 
156  // Extract the loop if the entry block doesn't branch to the loop header.
157  Instruction *EntryTI = F.getEntryBlock().getTerminator();
158  if (!isa<BranchInst>(EntryTI) ||
159  !cast<BranchInst>(EntryTI)->isUnconditional() ||
160  EntryTI->getSuccessor(0) != TLL->getHeader()) {
161  ShouldExtractLoop = true;
162  } else {
163  // Check to see if any exits from the loop are more than just return
164  // blocks.
165  SmallVector<BasicBlock *, 8> ExitBlocks;
166  TLL->getExitBlocks(ExitBlocks);
167  for (auto *ExitBlock : ExitBlocks)
168  if (!isa<ReturnInst>(ExitBlock->getTerminator())) {
169  ShouldExtractLoop = true;
170  break;
171  }
172  }
173 
174  if (ShouldExtractLoop)
175  return Changed | extractLoop(TLL, LI, DT);
176  }
177 
178  // Okay, this function is a minimal container around the specified loop.
179  // If we extract the loop, we will continue to just keep extracting it
180  // infinitely... so don't extract it. However, if the loop contains any
181  // sub-loops, extract them.
182  return Changed | extractLoops(TLL->begin(), TLL->end(), LI, DT);
183 }
184 
185 bool LoopExtractor::extractLoops(Loop::iterator From, Loop::iterator To,
186  LoopInfo &LI, DominatorTree &DT) {
187  bool Changed = false;
189 
190  // Save the list of loops, as it may change.
191  Loops.assign(From, To);
192  for (Loop *L : Loops) {
193  // If LoopSimplify form is not available, stay out of trouble.
194  if (!L->isLoopSimplifyForm())
195  continue;
196 
197  Changed |= extractLoop(L, LI, DT);
198  if (!NumLoops)
199  break;
200  }
201  return Changed;
202 }
203 
204 bool LoopExtractor::extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT) {
205  assert(NumLoops != 0);
206  AssumptionCache *AC = nullptr;
207  Function &Func = *L->getHeader()->getParent();
208  if (auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>())
209  AC = ACT->lookupAssumptionCache(Func);
210  CodeExtractorAnalysisCache CEAC(Func);
211  CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC);
212  if (Extractor.extractCodeRegion(CEAC)) {
213  LI.erase(L);
214  --NumLoops;
215  ++NumExtracted;
216  return true;
217  }
218  return false;
219 }
220 
221 // createSingleLoopExtractorPass - This pass extracts one natural loop from the
222 // program into a function if it can. This is used by bugpoint.
223 //
225  return new SingleLoopExtractor();
226 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:77
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
bool empty() const
Definition: Function.h:711
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool empty() const
Definition: LoopInfo.h:926
void initializeLoopExtractorPass(PassRegistry &)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:641
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
Pass * createSingleLoopExtractorPass()
createSingleLoopExtractorPass - This pass extracts one natural loop from the program into a function ...
STATISTIC(NumFunctions, "Total number of functions")
F(f)
AnalysisUsage & addRequired()
Hexagon Hardware Loops
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:859
BlockT * getHeader() const
Definition: LoopInfo.h:104
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:458
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:61
std::vector< Loop *>::const_iterator iterator
Definition: LoopInfo.h:151
SingleLoopExtractor - For bugpoint.
bool empty() const
Definition: Module.h:619
loop Extract loops into new functions
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static bool runOnFunction(Function &F, bool PostInlining)
char & BreakCriticalEdgesID
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
iterator end() const
Definition: LoopInfo.h:923
Represent the analysis usage information of a pass.
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
char & LoopSimplifyID
INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single", "Extract at most one loop into a new function", false, false) Pass *llvm
BlockVerifier::State From
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:266
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Module.h This file contains the declarations for the Module class.
iterator begin() const
Definition: LoopInfo.h:154
INITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract", "Extract loops into new functions", false, false) INITIALIZE_PASS_END(LoopExtractor
Pass * createLoopExtractorPass()
createLoopExtractorPass - This pass extracts all natural loops from the program into a function if it...
iterator begin() const
Definition: LoopInfo.h:922
loop extract
Function * extractCodeRegion(const CodeExtractorAnalysisCache &CEAC)
Perform the extraction, returning the new function.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:466
iterator end()
Definition: Module.h:612
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:516
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:59
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
iterator begin()
Definition: Module.h:610
iterator end() const
Definition: LoopInfo.h:155
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1233
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:262
loops
Definition: LoopInfo.cpp:1064
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)