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