/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/IPO/LoopExtractor.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- LoopExtractor.cpp - Extract each loop into a new function ----------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // A pass wrapper around the ExtractLoop() scalar transformation to extract each |
11 | | // top-level loop into its own new function. If the loop is the ONLY loop in a |
12 | | // given function, it is not touched. This is a pass most useful for debugging |
13 | | // via bugpoint. |
14 | | // |
15 | | //===----------------------------------------------------------------------===// |
16 | | |
17 | | #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" |
23 | | #include "llvm/Support/CommandLine.h" |
24 | | #include "llvm/Transforms/IPO.h" |
25 | | #include "llvm/Transforms/Scalar.h" |
26 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
27 | | #include "llvm/Transforms/Utils/CodeExtractor.h" |
28 | | #include <fstream> |
29 | | #include <set> |
30 | | using namespace llvm; |
31 | | |
32 | | #define DEBUG_TYPE "loop-extract" |
33 | | |
34 | | STATISTIC(NumExtracted, "Number of loops extracted"); |
35 | | |
36 | | namespace { |
37 | | struct LoopExtractor : public LoopPass { |
38 | | static char ID; // Pass identification, replacement for typeid |
39 | | unsigned NumLoops; |
40 | | |
41 | | explicit LoopExtractor(unsigned numLoops = ~0) |
42 | 9 | : LoopPass(ID), NumLoops(numLoops) { |
43 | 9 | initializeLoopExtractorPass(*PassRegistry::getPassRegistry()); |
44 | 9 | } |
45 | | |
46 | | bool runOnLoop(Loop *L, LPPassManager &) override; |
47 | | |
48 | 9 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
49 | 9 | AU.addRequiredID(BreakCriticalEdgesID); |
50 | 9 | AU.addRequiredID(LoopSimplifyID); |
51 | 9 | AU.addRequired<DominatorTreeWrapperPass>(); |
52 | 9 | AU.addRequired<LoopInfoWrapperPass>(); |
53 | 9 | } |
54 | | }; |
55 | | } |
56 | | |
57 | | char LoopExtractor::ID = 0; |
58 | 7.91k | INITIALIZE_PASS_BEGIN7.91k (LoopExtractor, "loop-extract",
|
59 | 7.91k | "Extract loops into new functions", false, false) |
60 | 7.91k | INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) |
61 | 7.91k | INITIALIZE_PASS_DEPENDENCY(LoopSimplify) |
62 | 7.91k | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
63 | 7.91k | INITIALIZE_PASS_END(LoopExtractor, "loop-extract", |
64 | | "Extract loops into new functions", false, false) |
65 | | |
66 | | namespace { |
67 | | /// SingleLoopExtractor - For bugpoint. |
68 | | struct SingleLoopExtractor : public LoopExtractor { |
69 | | static char ID; // Pass identification, replacement for typeid |
70 | 2 | SingleLoopExtractor() : LoopExtractor(1) {} |
71 | | }; |
72 | | } // End anonymous namespace |
73 | | |
74 | | char SingleLoopExtractor::ID = 0; |
75 | | INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single", |
76 | | "Extract at most one loop into a new function", false, false) |
77 | | |
78 | | // createLoopExtractorPass - This pass extracts all natural loops from the |
79 | | // program into a function if it can. |
80 | | // |
81 | 0 | Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } |
82 | | |
83 | 76 | bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) { |
84 | 76 | if (skipLoop(L)) |
85 | 0 | return false; |
86 | 76 | |
87 | 76 | // Only visit top-level loops. |
88 | 76 | if (76 L->getParentLoop()76 ) |
89 | 38 | return false; |
90 | 38 | |
91 | 38 | // If LoopSimplify form is not available, stay out of trouble. |
92 | 38 | if (38 !L->isLoopSimplifyForm()38 ) |
93 | 0 | return false; |
94 | 38 | |
95 | 38 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
96 | 38 | LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
97 | 38 | bool Changed = false; |
98 | 38 | |
99 | 38 | // If there is more than one top-level loop in this function, extract all of |
100 | 38 | // the loops. Otherwise there is exactly one top-level loop; in this case if |
101 | 38 | // this function is more than a minimal wrapper around the loop, extract |
102 | 38 | // the loop. |
103 | 38 | bool ShouldExtractLoop = false; |
104 | 38 | |
105 | 38 | // Extract the loop if the entry block doesn't branch to the loop header. |
106 | 38 | TerminatorInst *EntryTI = |
107 | 38 | L->getHeader()->getParent()->getEntryBlock().getTerminator(); |
108 | 38 | if (!isa<BranchInst>(EntryTI) || |
109 | 37 | !cast<BranchInst>(EntryTI)->isUnconditional() || |
110 | 38 | EntryTI->getSuccessor(0) != L->getHeader()13 ) { |
111 | 28 | ShouldExtractLoop = true; |
112 | 38 | } else { |
113 | 10 | // Check to see if any exits from the loop are more than just return |
114 | 10 | // blocks. |
115 | 10 | SmallVector<BasicBlock*, 8> ExitBlocks; |
116 | 10 | L->getExitBlocks(ExitBlocks); |
117 | 23 | for (unsigned i = 0, e = ExitBlocks.size(); i != e23 ; ++i13 ) |
118 | 16 | if (16 !isa<ReturnInst>(ExitBlocks[i]->getTerminator())16 ) { |
119 | 3 | ShouldExtractLoop = true; |
120 | 3 | break; |
121 | 3 | } |
122 | 10 | } |
123 | 38 | |
124 | 38 | if (ShouldExtractLoop38 ) { |
125 | 31 | // We must omit EH pads. EH pads must accompany the invoke |
126 | 31 | // instruction. But this would result in a loop in the extracted |
127 | 31 | // function. An infinite cycle occurs when it tries to extract that loop as |
128 | 31 | // well. |
129 | 31 | SmallVector<BasicBlock*, 8> ExitBlocks; |
130 | 31 | L->getExitBlocks(ExitBlocks); |
131 | 82 | for (unsigned i = 0, e = ExitBlocks.size(); i != e82 ; ++i51 ) |
132 | 52 | if (52 ExitBlocks[i]->isEHPad()52 ) { |
133 | 1 | ShouldExtractLoop = false; |
134 | 1 | break; |
135 | 1 | } |
136 | 31 | } |
137 | 38 | |
138 | 38 | if (ShouldExtractLoop38 ) { |
139 | 30 | if (NumLoops == 030 ) return Changed21 ; |
140 | 9 | --NumLoops; |
141 | 9 | CodeExtractor Extractor(DT, *L); |
142 | 9 | if (Extractor.extractCodeRegion() != nullptr9 ) { |
143 | 7 | Changed = true; |
144 | 7 | // After extraction, the loop is replaced by a function call, so |
145 | 7 | // we shouldn't try to run any more loop passes on it. |
146 | 7 | LPM.markLoopAsDeleted(*L); |
147 | 7 | LI.erase(L); |
148 | 7 | } |
149 | 30 | ++NumExtracted; |
150 | 30 | } |
151 | 38 | |
152 | 17 | return Changed; |
153 | 76 | } |
154 | | |
155 | | // createSingleLoopExtractorPass - This pass extracts one natural loop from the |
156 | | // program into a function if it can. This is used by bugpoint. |
157 | | // |
158 | 0 | Pass *llvm::createSingleLoopExtractorPass() { |
159 | 0 | return new SingleLoopExtractor(); |
160 | 0 | } |
161 | | |
162 | | |
163 | | // BlockFile - A file which contains a list of blocks that should not be |
164 | | // extracted. |
165 | | static cl::opt<std::string> |
166 | | BlockFile("extract-blocks-file", cl::value_desc("filename"), |
167 | | cl::desc("A file containing list of basic blocks to not extract"), |
168 | | cl::Hidden); |
169 | | |
170 | | namespace { |
171 | | /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks |
172 | | /// from the module into their own functions except for those specified by the |
173 | | /// BlocksToNotExtract list. |
174 | | class BlockExtractorPass : public ModulePass { |
175 | | void LoadFile(const char *Filename); |
176 | | void SplitLandingPadPreds(Function *F); |
177 | | |
178 | | std::vector<BasicBlock*> BlocksToNotExtract; |
179 | | std::vector<std::pair<std::string, std::string> > BlocksToNotExtractByName; |
180 | | public: |
181 | | static char ID; // Pass identification, replacement for typeid |
182 | 2 | BlockExtractorPass() : ModulePass(ID) { |
183 | 2 | if (!BlockFile.empty()) |
184 | 0 | LoadFile(BlockFile.c_str()); |
185 | 2 | } |
186 | | |
187 | | bool runOnModule(Module &M) override; |
188 | | }; |
189 | | } |
190 | | |
191 | | char BlockExtractorPass::ID = 0; |
192 | | INITIALIZE_PASS(BlockExtractorPass, "extract-blocks", |
193 | | "Extract Basic Blocks From Module (for bugpoint use)", |
194 | | false, false) |
195 | | |
196 | | // createBlockExtractorPass - This pass extracts all blocks (except those |
197 | | // specified in the argument list) from the functions in the module. |
198 | | // |
199 | 0 | ModulePass *llvm::createBlockExtractorPass() { |
200 | 0 | return new BlockExtractorPass(); |
201 | 0 | } |
202 | | |
203 | 0 | void BlockExtractorPass::LoadFile(const char *Filename) { |
204 | 0 | // Load the BlockFile... |
205 | 0 | std::ifstream In(Filename); |
206 | 0 | if (!In.good()0 ) { |
207 | 0 | errs() << "WARNING: BlockExtractor couldn't load file '" << Filename |
208 | 0 | << "'!\n"; |
209 | 0 | return; |
210 | 0 | } |
211 | 0 | while (0 In0 ) { |
212 | 0 | std::string FunctionName, BlockName; |
213 | 0 | In >> FunctionName; |
214 | 0 | In >> BlockName; |
215 | 0 | if (!BlockName.empty()) |
216 | 0 | BlocksToNotExtractByName.push_back( |
217 | 0 | std::make_pair(FunctionName, BlockName)); |
218 | 0 | } |
219 | 0 | } |
220 | | |
221 | | /// SplitLandingPadPreds - The landing pad needs to be extracted with the invoke |
222 | | /// instruction. The critical edge breaker will refuse to break critical edges |
223 | | /// to a landing pad. So do them here. After this method runs, all landing pads |
224 | | /// should have only one predecessor. |
225 | 4 | void BlockExtractorPass::SplitLandingPadPreds(Function *F) { |
226 | 13 | for (Function::iterator I = F->begin(), E = F->end(); I != E13 ; ++I9 ) { |
227 | 9 | InvokeInst *II = dyn_cast<InvokeInst>(I); |
228 | 9 | if (!II9 ) continue9 ; |
229 | 0 | BasicBlock *Parent = II->getParent(); |
230 | 0 | BasicBlock *LPad = II->getUnwindDest(); |
231 | 0 |
|
232 | 0 | // Look through the landing pad's predecessors. If one of them ends in an |
233 | 0 | // 'invoke', then we want to split the landing pad. |
234 | 0 | bool Split = false; |
235 | 0 | for (pred_iterator |
236 | 0 | PI = pred_begin(LPad), PE = pred_end(LPad); PI != PE0 ; ++PI0 ) { |
237 | 0 | BasicBlock *BB = *PI; |
238 | 0 | if (BB->isLandingPad() && 0 BB != Parent0 && |
239 | 0 | isa<InvokeInst>(Parent->getTerminator())0 ) { |
240 | 0 | Split = true; |
241 | 0 | break; |
242 | 0 | } |
243 | 0 | } |
244 | 0 |
|
245 | 0 | if (!Split0 ) continue0 ; |
246 | 0 |
|
247 | 0 | SmallVector<BasicBlock*, 2> NewBBs; |
248 | 0 | SplitLandingPadPredecessors(LPad, Parent, ".1", ".2", NewBBs); |
249 | 0 | } |
250 | 4 | } |
251 | | |
252 | 2 | bool BlockExtractorPass::runOnModule(Module &M) { |
253 | 2 | if (skipModule(M)) |
254 | 0 | return false; |
255 | 2 | |
256 | 2 | std::set<BasicBlock*> TranslatedBlocksToNotExtract; |
257 | 2 | for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e2 ; ++i0 ) { |
258 | 0 | BasicBlock *BB = BlocksToNotExtract[i]; |
259 | 0 | Function *F = BB->getParent(); |
260 | 0 |
|
261 | 0 | // Map the corresponding function in this module. |
262 | 0 | Function *MF = M.getFunction(F->getName()); |
263 | 0 | assert(MF->getFunctionType() == F->getFunctionType() && "Wrong function?"); |
264 | 0 |
|
265 | 0 | // Figure out which index the basic block is in its function. |
266 | 0 | Function::iterator BBI = MF->begin(); |
267 | 0 | std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); |
268 | 0 | TranslatedBlocksToNotExtract.insert(&*BBI); |
269 | 0 | } |
270 | 2 | |
271 | 2 | while (!BlocksToNotExtractByName.empty()2 ) { |
272 | 0 | // There's no way to find BBs by name without looking at every BB inside |
273 | 0 | // every Function. Fortunately, this is always empty except when used by |
274 | 0 | // bugpoint in which case correctness is more important than performance. |
275 | 0 |
|
276 | 0 | std::string &FuncName = BlocksToNotExtractByName.back().first; |
277 | 0 | std::string &BlockName = BlocksToNotExtractByName.back().second; |
278 | 0 |
|
279 | 0 | for (Function &F : M) { |
280 | 0 | if (F.getName() != FuncName0 ) continue0 ; |
281 | 0 |
|
282 | 0 | for (BasicBlock &BB : F) 0 { |
283 | 0 | if (BB.getName() != BlockName0 ) continue0 ; |
284 | 0 |
|
285 | 0 | TranslatedBlocksToNotExtract.insert(&BB); |
286 | 0 | } |
287 | 0 | } |
288 | 0 |
|
289 | 0 | BlocksToNotExtractByName.pop_back(); |
290 | 0 | } |
291 | 2 | |
292 | 2 | // Now that we know which blocks to not extract, figure out which ones we WANT |
293 | 2 | // to extract. |
294 | 2 | std::vector<BasicBlock*> BlocksToExtract; |
295 | 4 | for (Function &F : M) { |
296 | 4 | SplitLandingPadPreds(&F); |
297 | 4 | for (BasicBlock &BB : F) |
298 | 9 | if (9 !TranslatedBlocksToNotExtract.count(&BB)9 ) |
299 | 9 | BlocksToExtract.push_back(&BB); |
300 | 4 | } |
301 | 2 | |
302 | 9 | for (BasicBlock *BlockToExtract : BlocksToExtract) { |
303 | 9 | SmallVector<BasicBlock*, 2> BlocksToExtractVec; |
304 | 9 | BlocksToExtractVec.push_back(BlockToExtract); |
305 | 9 | if (const InvokeInst *II = |
306 | 9 | dyn_cast<InvokeInst>(BlockToExtract->getTerminator())) |
307 | 1 | BlocksToExtractVec.push_back(II->getUnwindDest()); |
308 | 9 | CodeExtractor(BlocksToExtractVec).extractCodeRegion(); |
309 | 9 | } |
310 | 2 | |
311 | 2 | return !BlocksToExtract.empty(); |
312 | 2 | } |