19401deb32079a855d291d041901c57bd332bfa87Misha Brukman//===- LoopExtractor.cpp - Extract each loop into a new function ----------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3efddcfa0df921ebca3e316120480df7df3e6e405Chris Lattner// The LLVM Compiler Infrastructure 4efddcfa0df921ebca3e316120480df7df3e6e405Chris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8efddcfa0df921ebca3e316120480df7df3e6e405Chris Lattner//===----------------------------------------------------------------------===// 99401deb32079a855d291d041901c57bd332bfa87Misha Brukman// 109401deb32079a855d291d041901c57bd332bfa87Misha Brukman// A pass wrapper around the ExtractLoop() scalar transformation to extract each 119401deb32079a855d291d041901c57bd332bfa87Misha Brukman// top-level loop into its own new function. If the loop is the ONLY loop in a 1238b8fd107816b94df1cd5b89123964103498767cMisha Brukman// given function, it is not touched. This is a pass most useful for debugging 1338b8fd107816b94df1cd5b89123964103498767cMisha Brukman// via bugpoint. 149401deb32079a855d291d041901c57bd332bfa87Misha Brukman// 159401deb32079a855d291d041901c57bd332bfa87Misha Brukman//===----------------------------------------------------------------------===// 169401deb32079a855d291d041901c57bd332bfa87Misha Brukman 1786453c52ba02e743d29c08456e51006500041456Chris Lattner#define DEBUG_TYPE "loop-extract" 181e3cb34753a0cf6b8d99ebf3ada17c87dcebed79Chris Lattner#include "llvm/Transforms/IPO.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Dominators.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/LoopPass.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 249401deb32079a855d291d041901c57bd332bfa87Misha Brukman#include "llvm/Pass.h" 256fa98b13206583e6eb90b8304758b35548914944Nick Lewycky#include "llvm/Support/CommandLine.h" 2616d0eb04688d283dc70a8f4a9905cb19d8636cd2Chris Lattner#include "llvm/Transforms/Scalar.h" 272f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling#include "llvm/Transforms/Utils/BasicBlockUtils.h" 2899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#include "llvm/Transforms/Utils/CodeExtractor.h" 296fa98b13206583e6eb90b8304758b35548914944Nick Lewycky#include <fstream> 306fa98b13206583e6eb90b8304758b35548914944Nick Lewycky#include <set> 319401deb32079a855d291d041901c57bd332bfa87Misha Brukmanusing namespace llvm; 329401deb32079a855d291d041901c57bd332bfa87Misha Brukman 3386453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumExtracted, "Number of loops extracted"); 34fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3586453c52ba02e743d29c08456e51006500041456Chris Lattnernamespace { 366726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct LoopExtractor : public LoopPass { 37ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 3841bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner unsigned NumLoops; 3941bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner 40c2bbfc18e9adbbdcf5b3375d8d25e2452f7df7f1Dan Gohman explicit LoopExtractor(unsigned numLoops = ~0) 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson : LoopPass(ID), NumLoops(numLoops) { 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLoopExtractorPass(*PassRegistry::getPassRegistry()); 43081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 4441bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner 45d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 46fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 47efddcfa0df921ebca3e316120480df7df3e6e405Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 48fdded9f95ae6233ec553fd54acc11f2dac1aee9dChris Lattner AU.addRequiredID(BreakCriticalEdgesID); 49fdded9f95ae6233ec553fd54acc11f2dac1aee9dChris Lattner AU.addRequiredID(LoopSimplifyID); 50c6fcf29e81f54b68146fb8d375c347d2c689566dOwen Anderson AU.addRequired<DominatorTree>(); 51efddcfa0df921ebca3e316120480df7df3e6e405Chris Lattner } 52efddcfa0df921ebca3e316120480df7df3e6e405Chris Lattner }; 53844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 54efddcfa0df921ebca3e316120480df7df3e6e405Chris Lattner 55844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopExtractor::ID = 0; 562ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract", 572f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling "Extract loops into new functions", false, false) 582ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) 592ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 602ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 612ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LoopExtractor, "loop-extract", 622f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling "Extract loops into new functions", false, false) 6341bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner 64844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 6541bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner /// SingleLoopExtractor - For bugpoint. 6641bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner struct SingleLoopExtractor : public LoopExtractor { 67ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 6841bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner SingleLoopExtractor() : LoopExtractor(1) {} 6941bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner }; 70fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman} // End anonymous namespace 719401deb32079a855d291d041901c57bd332bfa87Misha Brukman 72844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar SingleLoopExtractor::ID = 0; 73d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single", 74ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Extract at most one loop into a new function", false, false) 75844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 76bf65268def058af3e1d35aba233d5f0fd5a80fceJeff Cohen// createLoopExtractorPass - This pass extracts all natural loops from the 77bf65268def058af3e1d35aba233d5f0fd5a80fceJeff Cohen// program into a function if it can. 78bf65268def058af3e1d35aba233d5f0fd5a80fceJeff Cohen// 79d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanPass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } 80bf65268def058af3e1d35aba233d5f0fd5a80fceJeff Cohen 81d84db1133345234738b646c70b907bf8a0983ac9Dan Gohmanbool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) { 82d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Only visit top-level loops. 83d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (L->getParentLoop()) 849401deb32079a855d291d041901c57bd332bfa87Misha Brukman return false; 859401deb32079a855d291d041901c57bd332bfa87Misha Brukman 8603e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman // If LoopSimplify form is not available, stay out of trouble. 8703e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman if (!L->isLoopSimplifyForm()) 8803e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman return false; 8903e896bd6073efc4523d8bcd0239d6ed62126db7Dan Gohman 90c6fcf29e81f54b68146fb8d375c347d2c689566dOwen Anderson DominatorTree &DT = getAnalysis<DominatorTree>(); 919401deb32079a855d291d041901c57bd332bfa87Misha Brukman bool Changed = false; 92fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 93d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // If there is more than one top-level loop in this function, extract all of 94d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // the loops. Otherwise there is exactly one top-level loop; in this case if 95d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // this function is more than a minimal wrapper around the loop, extract 96d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // the loop. 97d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman bool ShouldExtractLoop = false; 98d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman 99d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Extract the loop if the entry block doesn't branch to the loop header. 100d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman TerminatorInst *EntryTI = 101d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman L->getHeader()->getParent()->getEntryBlock().getTerminator(); 102d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (!isa<BranchInst>(EntryTI) || 103d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman !cast<BranchInst>(EntryTI)->isUnconditional() || 10484b6706d9003f6078a81ed7d84f4e49ee70f7ef8Bill Wendling EntryTI->getSuccessor(0) != L->getHeader()) { 105d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman ShouldExtractLoop = true; 10684b6706d9003f6078a81ed7d84f4e49ee70f7ef8Bill Wendling } else { 107d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // Check to see if any exits from the loop are more than just return 108b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling // blocks. 109b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling SmallVector<BasicBlock*, 8> ExitBlocks; 110b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling L->getExitBlocks(ExitBlocks); 111b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 112b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) { 113b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling ShouldExtractLoop = true; 114b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling break; 115b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling } 116b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling } 117b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling 118b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling if (ShouldExtractLoop) { 119b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling // We must omit landing pads. Landing pads must accompany the invoke 120b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling // instruction. But this would result in a loop in the extracted 12184b6706d9003f6078a81ed7d84f4e49ee70f7ef8Bill Wendling // function. An infinite cycle occurs when it tries to extract that loop as 12284b6706d9003f6078a81ed7d84f4e49ee70f7ef8Bill Wendling // well. 123d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman SmallVector<BasicBlock*, 8> ExitBlocks; 124d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman L->getExitBlocks(ExitBlocks); 125b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 12684b6706d9003f6078a81ed7d84f4e49ee70f7ef8Bill Wendling if (ExitBlocks[i]->isLandingPad()) { 12784b6706d9003f6078a81ed7d84f4e49ee70f7ef8Bill Wendling ShouldExtractLoop = false; 128d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman break; 1295156c39d6419c891b3004da505487091c418bf63Chris Lattner } 130d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman } 131b7e807f9a9a74d743547856c4275a320f7b5b15eBill Wendling 132d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (ShouldExtractLoop) { 133d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman if (NumLoops == 0) return Changed; 134d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman --NumLoops; 13599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth CodeExtractor Extractor(DT, *L); 13699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Extractor.extractCodeRegion() != 0) { 137d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman Changed = true; 138d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // After extraction, the loop is replaced by a function call, so 139d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman // we shouldn't try to run any more loop passes on it. 140d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman LPM.deleteLoopFromQueue(L); 1415156c39d6419c891b3004da505487091c418bf63Chris Lattner } 142d84db1133345234738b646c70b907bf8a0983ac9Dan Gohman ++NumExtracted; 14341bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner } 1449401deb32079a855d291d041901c57bd332bfa87Misha Brukman 1459401deb32079a855d291d041901c57bd332bfa87Misha Brukman return Changed; 1469401deb32079a855d291d041901c57bd332bfa87Misha Brukman} 1479401deb32079a855d291d041901c57bd332bfa87Misha Brukman 14841bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner// createSingleLoopExtractorPass - This pass extracts one natural loop from the 14941bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner// program into a function if it can. This is used by bugpoint. 15041bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner// 151d84db1133345234738b646c70b907bf8a0983ac9Dan GohmanPass *llvm::createSingleLoopExtractorPass() { 15241bc0b069c74afa05e92a97ff2c5d3cfa7426505Chris Lattner return new SingleLoopExtractor(); 1539401deb32079a855d291d041901c57bd332bfa87Misha Brukman} 1548528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 1558528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 156844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// BlockFile - A file which contains a list of blocks that should not be 157844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// extracted. 158844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<std::string> 159844731a7f1909f55935e3514c9e713a62d67662eDan GohmanBlockFile("extract-blocks-file", cl::value_desc("filename"), 160844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::desc("A file containing list of basic blocks to not extract"), 161844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::Hidden); 1626fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 163844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1648528672e7eef90086726bbf69568f74defb6fae2Chris Lattner /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 1658528672e7eef90086726bbf69568f74defb6fae2Chris Lattner /// from the module into their own functions except for those specified by the 1668528672e7eef90086726bbf69568f74defb6fae2Chris Lattner /// BlocksToNotExtract list. 167b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattner class BlockExtractorPass : public ModulePass { 1686fa98b13206583e6eb90b8304758b35548914944Nick Lewycky void LoadFile(const char *Filename); 1692f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling void SplitLandingPadPreds(Function *F); 1706fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 1718528672e7eef90086726bbf69568f74defb6fae2Chris Lattner std::vector<BasicBlock*> BlocksToNotExtract; 1726fa98b13206583e6eb90b8304758b35548914944Nick Lewycky std::vector<std::pair<std::string, std::string> > BlocksToNotExtractByName; 1738528672e7eef90086726bbf69568f74defb6fae2Chris Lattner public: 174ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 17590c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson BlockExtractorPass() : ModulePass(ID) { 1766fa98b13206583e6eb90b8304758b35548914944Nick Lewycky if (!BlockFile.empty()) 1776fa98b13206583e6eb90b8304758b35548914944Nick Lewycky LoadFile(BlockFile.c_str()); 1786fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 1798528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 180b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattner bool runOnModule(Module &M); 1818528672e7eef90086726bbf69568f74defb6fae2Chris Lattner }; 1828528672e7eef90086726bbf69568f74defb6fae2Chris Lattner} 1838528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 184844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar BlockExtractorPass::ID = 0; 185d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(BlockExtractorPass, "extract-blocks", 186d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen Anderson "Extract Basic Blocks From Module (for bugpoint use)", 187ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson false, false) 188844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1898528672e7eef90086726bbf69568f74defb6fae2Chris Lattner// createBlockExtractorPass - This pass extracts all blocks (except those 1908528672e7eef90086726bbf69568f74defb6fae2Chris Lattner// specified in the argument list) from the functions in the module. 1918528672e7eef90086726bbf69568f74defb6fae2Chris Lattner// 1922f1cd85598d260e5567804460e87f8bee0c5e1e5Bill WendlingModulePass *llvm::createBlockExtractorPass() { 193d720670393434effa832b686b4a482b736bd9c4dRafael Espindola return new BlockExtractorPass(); 1948528672e7eef90086726bbf69568f74defb6fae2Chris Lattner} 1958528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 1966fa98b13206583e6eb90b8304758b35548914944Nick Lewyckyvoid BlockExtractorPass::LoadFile(const char *Filename) { 1976fa98b13206583e6eb90b8304758b35548914944Nick Lewycky // Load the BlockFile... 1986fa98b13206583e6eb90b8304758b35548914944Nick Lewycky std::ifstream In(Filename); 1996fa98b13206583e6eb90b8304758b35548914944Nick Lewycky if (!In.good()) { 200103289e9383ad1eb66caf28c9b166aebce963a35Chris Lattner errs() << "WARNING: BlockExtractor couldn't load file '" << Filename 201103289e9383ad1eb66caf28c9b166aebce963a35Chris Lattner << "'!\n"; 2026fa98b13206583e6eb90b8304758b35548914944Nick Lewycky return; 2036fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 2046fa98b13206583e6eb90b8304758b35548914944Nick Lewycky while (In) { 2056fa98b13206583e6eb90b8304758b35548914944Nick Lewycky std::string FunctionName, BlockName; 2066fa98b13206583e6eb90b8304758b35548914944Nick Lewycky In >> FunctionName; 2076fa98b13206583e6eb90b8304758b35548914944Nick Lewycky In >> BlockName; 2086fa98b13206583e6eb90b8304758b35548914944Nick Lewycky if (!BlockName.empty()) 2096fa98b13206583e6eb90b8304758b35548914944Nick Lewycky BlocksToNotExtractByName.push_back( 2106fa98b13206583e6eb90b8304758b35548914944Nick Lewycky std::make_pair(FunctionName, BlockName)); 2116fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 2126fa98b13206583e6eb90b8304758b35548914944Nick Lewycky} 2136fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 2142f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling/// SplitLandingPadPreds - The landing pad needs to be extracted with the invoke 2152f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling/// instruction. The critical edge breaker will refuse to break critical edges 2162f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling/// to a landing pad. So do them here. After this method runs, all landing pads 2172f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling/// should have only one predecessor. 2182f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendlingvoid BlockExtractorPass::SplitLandingPadPreds(Function *F) { 2192f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 2202f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling InvokeInst *II = dyn_cast<InvokeInst>(I); 2212f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling if (!II) continue; 2222f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling BasicBlock *Parent = II->getParent(); 2232f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling BasicBlock *LPad = II->getUnwindDest(); 2242f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling 2252f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling // Look through the landing pad's predecessors. If one of them ends in an 2262f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling // 'invoke', then we want to split the landing pad. 2272f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling bool Split = false; 2282f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling for (pred_iterator 2292f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling PI = pred_begin(LPad), PE = pred_end(LPad); PI != PE; ++PI) { 2302f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling BasicBlock *BB = *PI; 2312f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling if (BB->isLandingPad() && BB != Parent && 2322f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling isa<InvokeInst>(Parent->getTerminator())) { 2332f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling Split = true; 2342f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling break; 2352f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling } 2362f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling } 2372f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling 2382f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling if (!Split) continue; 2392f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling 2402f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling SmallVector<BasicBlock*, 2> NewBBs; 2412f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling SplitLandingPadPredecessors(LPad, Parent, ".1", ".2", 0, NewBBs); 2422f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling } 2432f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling} 2442f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling 245b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattnerbool BlockExtractorPass::runOnModule(Module &M) { 2468528672e7eef90086726bbf69568f74defb6fae2Chris Lattner std::set<BasicBlock*> TranslatedBlocksToNotExtract; 2478528672e7eef90086726bbf69568f74defb6fae2Chris Lattner for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 2488528672e7eef90086726bbf69568f74defb6fae2Chris Lattner BasicBlock *BB = BlocksToNotExtract[i]; 2498528672e7eef90086726bbf69568f74defb6fae2Chris Lattner Function *F = BB->getParent(); 2508528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 2518528672e7eef90086726bbf69568f74defb6fae2Chris Lattner // Map the corresponding function in this module. 252ef9b9a793949469cdaa4ab6d0173136229dcab7bReid Spencer Function *MF = M.getFunction(F->getName()); 253ef9b9a793949469cdaa4ab6d0173136229dcab7bReid Spencer assert(MF->getFunctionType() == F->getFunctionType() && "Wrong function?"); 2548528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 2558528672e7eef90086726bbf69568f74defb6fae2Chris Lattner // Figure out which index the basic block is in its function. 2568528672e7eef90086726bbf69568f74defb6fae2Chris Lattner Function::iterator BBI = MF->begin(); 2578528672e7eef90086726bbf69568f74defb6fae2Chris Lattner std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 2588528672e7eef90086726bbf69568f74defb6fae2Chris Lattner TranslatedBlocksToNotExtract.insert(BBI); 2598528672e7eef90086726bbf69568f74defb6fae2Chris Lattner } 2608528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 2616fa98b13206583e6eb90b8304758b35548914944Nick Lewycky while (!BlocksToNotExtractByName.empty()) { 2626fa98b13206583e6eb90b8304758b35548914944Nick Lewycky // There's no way to find BBs by name without looking at every BB inside 2636fa98b13206583e6eb90b8304758b35548914944Nick Lewycky // every Function. Fortunately, this is always empty except when used by 2646fa98b13206583e6eb90b8304758b35548914944Nick Lewycky // bugpoint in which case correctness is more important than performance. 2656fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 2666fa98b13206583e6eb90b8304758b35548914944Nick Lewycky std::string &FuncName = BlocksToNotExtractByName.back().first; 2676fa98b13206583e6eb90b8304758b35548914944Nick Lewycky std::string &BlockName = BlocksToNotExtractByName.back().second; 2686fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 2696fa98b13206583e6eb90b8304758b35548914944Nick Lewycky for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) { 2706fa98b13206583e6eb90b8304758b35548914944Nick Lewycky Function &F = *FI; 2716fa98b13206583e6eb90b8304758b35548914944Nick Lewycky if (F.getName() != FuncName) continue; 2726fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 2736fa98b13206583e6eb90b8304758b35548914944Nick Lewycky for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { 2746fa98b13206583e6eb90b8304758b35548914944Nick Lewycky BasicBlock &BB = *BI; 2756fa98b13206583e6eb90b8304758b35548914944Nick Lewycky if (BB.getName() != BlockName) continue; 2766fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 2776fa98b13206583e6eb90b8304758b35548914944Nick Lewycky TranslatedBlocksToNotExtract.insert(BI); 2786fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 2796fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 2806fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 2816fa98b13206583e6eb90b8304758b35548914944Nick Lewycky BlocksToNotExtractByName.pop_back(); 2826fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 2836fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 2848528672e7eef90086726bbf69568f74defb6fae2Chris Lattner // Now that we know which blocks to not extract, figure out which ones we WANT 2858528672e7eef90086726bbf69568f74defb6fae2Chris Lattner // to extract. 2868528672e7eef90086726bbf69568f74defb6fae2Chris Lattner std::vector<BasicBlock*> BlocksToExtract; 2872f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 2882f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling SplitLandingPadPreds(&*F); 2898528672e7eef90086726bbf69568f74defb6fae2Chris Lattner for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 2908528672e7eef90086726bbf69568f74defb6fae2Chris Lattner if (!TranslatedBlocksToNotExtract.count(BB)) 2918528672e7eef90086726bbf69568f74defb6fae2Chris Lattner BlocksToExtract.push_back(BB); 2922f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling } 2938528672e7eef90086726bbf69568f74defb6fae2Chris Lattner 2942f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) { 2952f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling SmallVector<BasicBlock*, 2> BlocksToExtractVec; 2962f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling BlocksToExtractVec.push_back(BlocksToExtract[i]); 2978c93d5b602377e9860c32a1367fc697d9684e3eeBill Wendling if (const InvokeInst *II = 2988c93d5b602377e9860c32a1367fc697d9684e3eeBill Wendling dyn_cast<InvokeInst>(BlocksToExtract[i]->getTerminator())) 2992f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling BlocksToExtractVec.push_back(II->getUnwindDest()); 30099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth CodeExtractor(BlocksToExtractVec).extractCodeRegion(); 3012f1cd85598d260e5567804460e87f8bee0c5e1e5Bill Wendling } 302fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3038528672e7eef90086726bbf69568f74defb6fae2Chris Lattner return !BlocksToExtract.empty(); 3048528672e7eef90086726bbf69568f74defb6fae2Chris Lattner} 305