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 
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",
98  "Extract loops into new functions", false, false)
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 & {
269  return FAM.getResult<DominatorTreeAnalysis>(F);
270  };
271  auto LookupLoopInfo = [&FAM](Function &F) -> LoopInfo & {
272  return FAM.getResult<LoopAnalysis>(F);
273  };
274  auto LookupAssumptionCache = [&FAM](Function &F) -> AssumptionCache * {
275  return FAM.getCachedResult<AssumptionAnalysis>(F);
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 }
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
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:942
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
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")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:249
F(f)
AnalysisUsage & addRequired()
Hexagon Hardware Loops
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:880
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1224
BlockT * getHeader() const
Definition: LoopInfo.h:104
std::vector< Loop * >::const_iterator iterator
Definition: LoopInfo.h:151
SingleLoopExtractor - For bugpoint.
loop Extract loops into new functions
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
static bool runOnFunction(Function &F, bool PostInlining)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
char & BreakCriticalEdgesID
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
iterator end() const
Definition: LoopInfo.h:939
Represent the analysis usage information of a pass.
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:61
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
char & LoopSimplifyID
A function analysis which provides an AssumptionCache.
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
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 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1116
Module.h This file contains the declarations for the Module class.
iterator begin() const
Definition: LoopInfo.h:154
Pass * createLoopExtractorPass()
createLoopExtractorPass - This pass extracts all natural loops from the program into a function if it...
iterator begin() const
Definition: LoopInfo.h:938
loop extract
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:471
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
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:238
iterator end() const
Definition: LoopInfo.h:155
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
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's analysis pass to compute loop information.
Definition: LoopInfo.h:1249
A container for analyses that lazily runs them and caches their results.
INITIALIZE_PASS_BEGIN(LoopExtractorLegacyPass, "loop-extract", "Extract loops into new functions", false, false) INITIALIZE_PASS_END(LoopExtractorLegacyPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
This header defines various interfaces for pass management in LLVM.
void initializeLoopExtractorLegacyPassPass(PassRegistry &)
loops
Definition: LoopInfo.cpp:1084
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:969