LLVM  10.0.0svn
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/LoopPass.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/Pass.h"
24 #include "llvm/Transforms/IPO.h"
25 #include "llvm/Transforms/Scalar.h"
26 #include "llvm/Transforms/Utils.h"
29 #include <fstream>
30 #include <set>
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "loop-extract"
34 
35 STATISTIC(NumExtracted, "Number of loops extracted");
36 
37 namespace {
38  struct LoopExtractor : public LoopPass {
39  static char ID; // Pass identification, replacement for typeid
40  unsigned NumLoops;
41 
42  explicit LoopExtractor(unsigned numLoops = ~0)
43  : LoopPass(ID), NumLoops(numLoops) {
45  }
46 
47  bool runOnLoop(Loop *L, LPPassManager &) override;
48 
49  void getAnalysisUsage(AnalysisUsage &AU) const override {
55  }
56  };
57 }
58 
59 char LoopExtractor::ID = 0;
60 INITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract",
61  "Extract loops into new functions", false, false)
62 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
63 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
65 INITIALIZE_PASS_END(LoopExtractor, "loop-extract",
66  "Extract loops into new functions", false, false)
67 
68 namespace {
69  /// SingleLoopExtractor - For bugpoint.
70  struct SingleLoopExtractor : public LoopExtractor {
71  static char ID; // Pass identification, replacement for typeid
72  SingleLoopExtractor() : LoopExtractor(1) {}
73  };
74 } // End anonymous namespace
75 
77 INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single",
78  "Extract at most one loop into a new function", false, false)
79 
80 // createLoopExtractorPass - This pass extracts all natural loops from the
81 // program into a function if it can.
82 //
83 Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); }
84 
85 bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) {
86  if (skipLoop(L))
87  return false;
88 
89  // Only visit top-level loops.
90  if (L->getParentLoop())
91  return false;
92 
93  // If LoopSimplify form is not available, stay out of trouble.
94  if (!L->isLoopSimplifyForm())
95  return false;
96 
97  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
98  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
99  bool Changed = false;
100 
101  // If there is more than one top-level loop in this function, extract all of
102  // the loops. Otherwise there is exactly one top-level loop; in this case if
103  // this function is more than a minimal wrapper around the loop, extract
104  // the loop.
105  bool ShouldExtractLoop = false;
106 
107  // Extract the loop if the entry block doesn't branch to the loop header.
108  Instruction *EntryTI =
110  if (!isa<BranchInst>(EntryTI) ||
111  !cast<BranchInst>(EntryTI)->isUnconditional() ||
112  EntryTI->getSuccessor(0) != L->getHeader()) {
113  ShouldExtractLoop = true;
114  } else {
115  // Check to see if any exits from the loop are more than just return
116  // blocks.
117  SmallVector<BasicBlock*, 8> ExitBlocks;
118  L->getExitBlocks(ExitBlocks);
119  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
120  if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) {
121  ShouldExtractLoop = true;
122  break;
123  }
124  }
125 
126  if (ShouldExtractLoop) {
127  // We must omit EH pads. EH pads must accompany the invoke
128  // instruction. But this would result in a loop in the extracted
129  // function. An infinite cycle occurs when it tries to extract that loop as
130  // well.
131  SmallVector<BasicBlock*, 8> ExitBlocks;
132  L->getExitBlocks(ExitBlocks);
133  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
134  if (ExitBlocks[i]->isEHPad()) {
135  ShouldExtractLoop = false;
136  break;
137  }
138  }
139 
140  if (ShouldExtractLoop) {
141  if (NumLoops == 0) return Changed;
142  --NumLoops;
143  AssumptionCache *AC = nullptr;
144  Function &Func = *L->getHeader()->getParent();
145  if (auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>())
146  AC = ACT->lookupAssumptionCache(Func);
147  CodeExtractorAnalysisCache CEAC(Func);
148  CodeExtractor Extractor(DT, *L, false, nullptr, nullptr, AC);
149  if (Extractor.extractCodeRegion(CEAC) != nullptr) {
150  Changed = true;
151  // After extraction, the loop is replaced by a function call, so
152  // we shouldn't try to run any more loop passes on it.
153  LPM.markLoopAsDeleted(*L);
154  LI.erase(L);
155  }
156  ++NumExtracted;
157  }
158 
159  return Changed;
160 }
161 
162 // createSingleLoopExtractorPass - This pass extracts one natural loop from the
163 // program into a function if it can. This is used by bugpoint.
164 //
166  return new SingleLoopExtractor();
167 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void initializeLoopExtractorPass(PassRegistry &)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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")
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:144
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
void erase(Loop *L)
Update LoopInfo after removing the last backedge from a loop.
Definition: LoopInfo.cpp:857
BlockT * getHeader() const
Definition: LoopInfo.h:105
void getExitBlocks(SmallVectorImpl< BlockT *> &ExitBlocks) const
Return all of the successor blocks of this loop.
Definition: LoopInfoImpl.h:62
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:144
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
char & BreakCriticalEdgesID
Represent the analysis usage information of a pass.
constexpr double e
Definition: MathExtras.h:57
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
size_t size() const
Definition: SmallVector.h:52
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
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:314
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
INITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract", "Extract loops into new functions", false, false) INITIALIZE_PASS_END(LoopExtractor
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:143
Pass * createLoopExtractorPass()
createLoopExtractorPass - This pass extracts all natural loops from the program into a function if it...
loop extract
Function * extractCodeRegion(const CodeExtractorAnalysisCache &CEAC)
Perform the extraction, returning the new function.
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to...
Definition: LoopInfo.cpp:464
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
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:1208
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
loops
Definition: LoopInfo.cpp:1058