1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- LoopExtractor.cpp - Extract each loop into a new function ----------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// A pass wrapper around the ExtractLoop() scalar transformation to extract each 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// top-level loop into its own new function. If the loop is the ONLY loop in a 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// given function, it is not touched. This is a pass most useful for debugging 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// via bugpoint. 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "loop-extract" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/IPO.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instructions.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Module.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Pass.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/Dominators.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Analysis/LoopPass.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CommandLine.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Scalar.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/FunctionUtils.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/Statistic.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <fstream> 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <set> 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumExtracted, "Number of loops extracted"); 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct LoopExtractor : public LoopPass { 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumLoops; 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit LoopExtractor(unsigned numLoops = ~0) 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : LoopPass(ID), NumLoops(numLoops) { 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeLoopExtractorPass(*PassRegistry::getPassRegistry()); 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequiredID(BreakCriticalEdgesID); 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequiredID(LoopSimplifyID); 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequired<DominatorTree>(); 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar LoopExtractor::ID = 0; 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_BEGIN(LoopExtractor, "loop-extract", 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Extract loops into new functions", false, false) 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges) 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(DominatorTree) 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_END(LoopExtractor, "loop-extract", 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Extract loops into new functions", false, false) 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SingleLoopExtractor - For bugpoint. 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct SingleLoopExtractor : public LoopExtractor { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SingleLoopExtractor() : LoopExtractor(1) {} 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // End anonymous namespace 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar SingleLoopExtractor::ID = 0; 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanINITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single", 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Extract at most one loop into a new function", false, false) 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// createLoopExtractorPass - This pass extracts all natural loops from the 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// program into a function if it can. 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanPass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) { 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Only visit top-level loops. 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (L->getParentLoop()) 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If LoopSimplify form is not available, stay out of trouble. 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!L->isLoopSimplifyForm()) 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DominatorTree &DT = getAnalysis<DominatorTree>(); 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there is more than one top-level loop in this function, extract all of 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the loops. Otherwise there is exactly one top-level loop; in this case if 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this function is more than a minimal wrapper around the loop, extract 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the loop. 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool ShouldExtractLoop = false; 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Extract the loop if the entry block doesn't branch to the loop header. 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TerminatorInst *EntryTI = 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->getHeader()->getParent()->getEntryBlock().getTerminator(); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isa<BranchInst>(EntryTI) || 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !cast<BranchInst>(EntryTI)->isUnconditional() || 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EntryTI->getSuccessor(0) != L->getHeader()) { 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ShouldExtractLoop = true; 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if any exits from the loop are more than just return 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // blocks. 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<BasicBlock*, 8> ExitBlocks; 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman L->getExitBlocks(ExitBlocks); 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isa<ReturnInst>(ExitBlocks[i]->getTerminator())) { 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ShouldExtractLoop = true; 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ShouldExtractLoop) { 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We must omit landing pads. Landing pads must accompany the invoke 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // instruction. But this would result in a loop in the extracted 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // function. An infinite cycle occurs when it tries to extract that loop as 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // well. 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<BasicBlock*, 8> ExitBlocks; 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman L->getExitBlocks(ExitBlocks); 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ExitBlocks[i]->isLandingPad()) { 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ShouldExtractLoop = false; 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ShouldExtractLoop) { 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumLoops == 0) return Changed; 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumLoops; 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ExtractLoop(DT, L) != 0) { 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // After extraction, the loop is replaced by a function call, so 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // we shouldn't try to run any more loop passes on it. 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LPM.deleteLoopFromQueue(L); 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumExtracted; 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// createSingleLoopExtractorPass - This pass extracts one natural loop from the 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// program into a function if it can. This is used by bugpoint. 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanPass *llvm::createSingleLoopExtractorPass() { 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return new SingleLoopExtractor(); 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// BlockFile - A file which contains a list of blocks that should not be 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// extracted. 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic cl::opt<std::string> 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanBlockFile("extract-blocks-file", cl::value_desc("filename"), 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cl::desc("A file containing list of basic blocks to not extract"), 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cl::Hidden); 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// from the module into their own functions except for those specified by the 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BlocksToNotExtract list. 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class BlockExtractorPass : public ModulePass { 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void LoadFile(const char *Filename); 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void SplitLandingPadPreds(Function *F); 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<BasicBlock*> BlocksToNotExtract; 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<std::pair<std::string, std::string> > BlocksToNotExtractByName; 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification, replacement for typeid 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlockExtractorPass() : ModulePass(ID) { 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BlockFile.empty()) 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LoadFile(BlockFile.c_str()); 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool runOnModule(Module &M); 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar BlockExtractorPass::ID = 0; 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanINITIALIZE_PASS(BlockExtractorPass, "extract-blocks", 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Extract Basic Blocks From Module (for bugpoint use)", 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman false, false) 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// createBlockExtractorPass - This pass extracts all blocks (except those 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// specified in the argument list) from the functions in the module. 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanModulePass *llvm::createBlockExtractorPass() { 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return new BlockExtractorPass(); 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid BlockExtractorPass::LoadFile(const char *Filename) { 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Load the BlockFile... 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::ifstream In(Filename); 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!In.good()) { 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman errs() << "WARNING: BlockExtractor couldn't load file '" << Filename 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << "'!\n"; 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (In) { 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string FunctionName, BlockName; 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman In >> FunctionName; 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman In >> BlockName; 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!BlockName.empty()) 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlocksToNotExtractByName.push_back( 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::make_pair(FunctionName, BlockName)); 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// SplitLandingPadPreds - The landing pad needs to be extracted with the invoke 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// instruction. The critical edge breaker will refuse to break critical edges 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// to a landing pad. So do them here. After this method runs, all landing pads 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// should have only one predecessor. 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid BlockExtractorPass::SplitLandingPadPreds(Function *F) { 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InvokeInst *II = dyn_cast<InvokeInst>(I); 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!II) continue; 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *Parent = II->getParent(); 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *LPad = II->getUnwindDest(); 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Look through the landing pad's predecessors. If one of them ends in an 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 'invoke', then we want to split the landing pad. 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Split = false; 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (pred_iterator 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PI = pred_begin(LPad), PE = pred_end(LPad); PI != PE; ++PI) { 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BasicBlock *BB = *PI; 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BB->isLandingPad() && BB != Parent && 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isa<InvokeInst>(Parent->getTerminator())) { 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Split = true; 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Split) continue; 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<BasicBlock*, 2> NewBBs; 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitLandingPadPredecessors(LPad, Parent, ".1", ".2", 0, NewBBs); 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool BlockExtractorPass::runOnModule(Module &M) { 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::set<BasicBlock*> TranslatedBlocksToNotExtract; 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *BB = BlocksToNotExtract[i]; 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *F = BB->getParent(); 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Map the corresponding function in this module. 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function *MF = M.getFunction(F->getName()); 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(MF->getFunctionType() == F->getFunctionType() && "Wrong function?"); 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Figure out which index the basic block is in its function. 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function::iterator BBI = MF->begin(); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TranslatedBlocksToNotExtract.insert(BBI); 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (!BlocksToNotExtractByName.empty()) { 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // There's no way to find BBs by name without looking at every BB inside 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // every Function. Fortunately, this is always empty except when used by 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // bugpoint in which case correctness is more important than performance. 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string &FuncName = BlocksToNotExtractByName.back().first; 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string &BlockName = BlocksToNotExtractByName.back().second; 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) { 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Function &F = *FI; 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (F.getName() != FuncName) continue; 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock &BB = *BI; 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BB.getName() != BlockName) continue; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TranslatedBlocksToNotExtract.insert(BI); 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlocksToNotExtractByName.pop_back(); 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we know which blocks to not extract, figure out which ones we WANT 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to extract. 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<BasicBlock*> BlocksToExtract; 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitLandingPadPreds(&*F); 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!TranslatedBlocksToNotExtract.count(BB)) 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BlocksToExtract.push_back(BB); 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) { 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<BasicBlock*, 2> BlocksToExtractVec; 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlocksToExtractVec.push_back(BlocksToExtract[i]); 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const InvokeInst *II = 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dyn_cast<InvokeInst>(BlocksToExtract[i]->getTerminator())) 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlocksToExtractVec.push_back(II->getUnwindDest()); 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ExtractBasicBlock(BlocksToExtractVec); 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return !BlocksToExtract.empty(); 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 304