Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -73,7 +73,7 @@ void initializeBDCELegacyPassPass(PassRegistry&); void initializeBarrierNoopPass(PassRegistry&); void initializeBasicAAWrapperPassPass(PassRegistry&); -void initializeBlockExtractorPassPass(PassRegistry&); +void initializeBlockExtractorPass(PassRegistry &); void initializeBlockFrequencyInfoWrapperPassPass(PassRegistry&); void initializeBoundsCheckingLegacyPassPass(PassRegistry&); void initializeBranchFolderPassPass(PassRegistry&); Index: include/llvm/Transforms/IPO.h =================================================================== --- include/llvm/Transforms/IPO.h +++ include/llvm/Transforms/IPO.h @@ -179,10 +179,13 @@ /// Pass *createSingleLoopExtractorPass(); -/// createBlockExtractorPass - This pass extracts all blocks (except those -/// specified in the argument list) from the functions in the module. +/// createBlockExtractorPass - This pass extracts all the specified blocks +/// from the functions in the module. /// ModulePass *createBlockExtractorPass(); +ModulePass * +createBlockExtractorPass(const SmallVectorImpl &BlocksToExtract, + bool EraseFunctions); /// createStripDeadPrototypesPass - This pass removes any function declarations /// (prototypes) that are not used. Index: lib/Transforms/IPO/BlockExtractor.cpp =================================================================== --- /dev/null +++ lib/Transforms/IPO/BlockExtractor.cpp @@ -0,0 +1,174 @@ +//===- BlockExtractor.cpp - Extracts blocks into their own functions ------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass extracts the specified basic blocks from the module into their +// own functions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/CodeExtractor.h" +using namespace llvm; + +#define DEBUG_TYPE "block-extractor" + +STATISTIC(NumExtracted, "Number of basic blocks extracted"); + +static cl::opt BlockExtractorFile( + "extract-blocks-file", cl::value_desc("filename"), + cl::desc("A file containing list of basic blocks to extract"), cl::Hidden); + +cl::opt BlockExtractorEraseFuncs("extract-blocks-erase-funcs", + cl::desc("Erase the existing functions"), + cl::Hidden); + +namespace { +class BlockExtractor : public ModulePass { + SmallVector Blocks; + bool EraseFunctions; + SmallVector, 32> BlocksByName; + +public: + static char ID; + BlockExtractor(const SmallVectorImpl &BlocksToExtract, + bool EraseFunctions) + : ModulePass(ID), Blocks(BlocksToExtract.begin(), BlocksToExtract.end()), + EraseFunctions(EraseFunctions) { + if (!BlockExtractorFile.empty()) + loadFile(); + } + BlockExtractor() : BlockExtractor(SmallVector(), false) {} + bool runOnModule(Module &M) override; + +private: + void loadFile(); + void splitLandingPadPreds(Function &F); +}; +} // end anonymous namespace + +char BlockExtractor::ID = 0; +INITIALIZE_PASS(BlockExtractor, "extract-blocks", + "Extract basic blocks from module", false, false) + +ModulePass *llvm::createBlockExtractorPass() { return new BlockExtractor(); } +ModulePass *llvm::createBlockExtractorPass( + const SmallVectorImpl &BlocksToExtract, bool EraseFunctions) { + return new BlockExtractor(BlocksToExtract, EraseFunctions); +} + +/// Gets all of the blocks specified in the input file. +void BlockExtractor::loadFile() { + auto ErrOrBuf = MemoryBuffer::getFile(BlockExtractorFile); + if (std::error_code EC = ErrOrBuf.getError()) + report_fatal_error("BlockExtractor couldn't load the file."); + // Read the file. + auto &Buf = *ErrOrBuf; + SmallVector Lines; + Buf->getBuffer().split(Lines, '\n', /*MaxSplit=*/-1, + /*KeepEmpty=*/false); + for (const auto &Line : Lines) { + auto FBPair = Line.split(' '); + BlocksByName.push_back({FBPair.first, FBPair.second}); + } +} + +/// Extracts the landing pads to make sure all of them have only one +/// predecessor. +void BlockExtractor::splitLandingPadPreds(Function &F) { + for (BasicBlock &BB : F) { + for (Instruction &I : BB) { + if (!isa(&I)) + continue; + InvokeInst *II = cast(&I); + BasicBlock *Parent = II->getParent(); + BasicBlock *LPad = II->getUnwindDest(); + + // Look through the landing pad's predecessors. If one of them ends in an + // 'invoke', then we want to split the landing pad. + bool Split = false; + for (auto PredBB : predecessors(LPad)) { + if (PredBB->isLandingPad() && PredBB != Parent && + isa(Parent->getTerminator())) { + Split = true; + break; + } + } + + if (!Split) + continue; + + SmallVector NewBBs; + SplitLandingPadPredecessors(LPad, Parent, ".1", ".2", NewBBs); + } + } +} + +bool BlockExtractor::runOnModule(Module &M) { + + bool Changed = false; + + // Get all the functions. + SmallVector Functions; + for (Function &F : M) { + splitLandingPadPreds(F); + Functions.push_back(&F); + } + + // Get all the blocks specified in the input file. + for (const auto &BInfo : BlocksByName) { + Function *F = M.getFunction(BInfo.first); + if (!F) + report_fatal_error("Invalid function name specified in the input file"); + auto Res = llvm::find_if(*F, [&](const BasicBlock &BB) { + return BB.getName().equals(BInfo.second); + }); + if (Res == F->end()) + report_fatal_error("Invalid block name specified in the input file"); + Blocks.push_back(&*Res); + } + + // Extract basic blocks. + for (BasicBlock *BB : Blocks) { + // Check if the module contains BB. + if (BB->getParent()->getParent() != &M) + report_fatal_error("Invalid basic block"); + DEBUG(dbgs() << "BlockExtractor: Extracting " << BB->getParent()->getName() + << ":" << BB->getName() << "\n"); + SmallVector BlocksToExtractVec; + BlocksToExtractVec.push_back(BB); + if (const InvokeInst *II = dyn_cast(BB->getTerminator())) + BlocksToExtractVec.push_back(II->getUnwindDest()); + CodeExtractor(BlocksToExtractVec).extractCodeRegion(); + ++NumExtracted; + Changed = true; + } + + // Erase the functions. + if (EraseFunctions || BlockExtractorEraseFuncs) { + for (Function *F : Functions) { + DEBUG(dbgs() << "BlockExtractor: Deleting " << F->getName() << "\n"); + F->eraseFromParent(); + } + // Set linkage as ExternalLinkage to avoid erasing unreachable functions. + for (Function &F : M) + F.setLinkage(GlobalValue::ExternalLinkage); + Changed = true; + } + + return Changed; +} Index: lib/Transforms/IPO/CMakeLists.txt =================================================================== --- lib/Transforms/IPO/CMakeLists.txt +++ lib/Transforms/IPO/CMakeLists.txt @@ -2,6 +2,7 @@ AlwaysInliner.cpp ArgumentPromotion.cpp BarrierNoopPass.cpp + BlockExtractor.cpp CalledValuePropagation.cpp ConstantMerge.cpp CrossDSOCFI.cpp Index: lib/Transforms/IPO/IPO.cpp =================================================================== --- lib/Transforms/IPO/IPO.cpp +++ lib/Transforms/IPO/IPO.cpp @@ -40,7 +40,7 @@ initializeInferFunctionAttrsLegacyPassPass(Registry); initializeInternalizeLegacyPassPass(Registry); initializeLoopExtractorPass(Registry); - initializeBlockExtractorPassPass(Registry); + initializeBlockExtractorPass(Registry); initializeSingleLoopExtractorPass(Registry); initializeLowerTypeTestsPass(Registry); initializeMergeFunctionsPass(Registry); Index: lib/Transforms/IPO/LoopExtractor.cpp =================================================================== --- lib/Transforms/IPO/LoopExtractor.cpp +++ lib/Transforms/IPO/LoopExtractor.cpp @@ -158,155 +158,3 @@ Pass *llvm::createSingleLoopExtractorPass() { return new SingleLoopExtractor(); } - - -// BlockFile - A file which contains a list of blocks that should not be -// extracted. -static cl::opt -BlockFile("extract-blocks-file", cl::value_desc("filename"), - cl::desc("A file containing list of basic blocks to not extract"), - cl::Hidden); - -namespace { - /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks - /// from the module into their own functions except for those specified by the - /// BlocksToNotExtract list. - class BlockExtractorPass : public ModulePass { - void LoadFile(const char *Filename); - void SplitLandingPadPreds(Function *F); - - std::vector BlocksToNotExtract; - std::vector > BlocksToNotExtractByName; - public: - static char ID; // Pass identification, replacement for typeid - BlockExtractorPass() : ModulePass(ID) { - if (!BlockFile.empty()) - LoadFile(BlockFile.c_str()); - } - - bool runOnModule(Module &M) override; - }; -} - -char BlockExtractorPass::ID = 0; -INITIALIZE_PASS(BlockExtractorPass, "extract-blocks", - "Extract Basic Blocks From Module (for bugpoint use)", - false, false) - -// createBlockExtractorPass - This pass extracts all blocks (except those -// specified in the argument list) from the functions in the module. -// -ModulePass *llvm::createBlockExtractorPass() { - return new BlockExtractorPass(); -} - -void BlockExtractorPass::LoadFile(const char *Filename) { - // Load the BlockFile... - std::ifstream In(Filename); - if (!In.good()) { - errs() << "WARNING: BlockExtractor couldn't load file '" << Filename - << "'!\n"; - return; - } - while (In) { - std::string FunctionName, BlockName; - In >> FunctionName; - In >> BlockName; - if (!BlockName.empty()) - BlocksToNotExtractByName.push_back( - std::make_pair(FunctionName, BlockName)); - } -} - -/// SplitLandingPadPreds - The landing pad needs to be extracted with the invoke -/// instruction. The critical edge breaker will refuse to break critical edges -/// to a landing pad. So do them here. After this method runs, all landing pads -/// should have only one predecessor. -void BlockExtractorPass::SplitLandingPadPreds(Function *F) { - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { - InvokeInst *II = dyn_cast(I); - if (!II) continue; - BasicBlock *Parent = II->getParent(); - BasicBlock *LPad = II->getUnwindDest(); - - // Look through the landing pad's predecessors. If one of them ends in an - // 'invoke', then we want to split the landing pad. - bool Split = false; - for (pred_iterator - PI = pred_begin(LPad), PE = pred_end(LPad); PI != PE; ++PI) { - BasicBlock *BB = *PI; - if (BB->isLandingPad() && BB != Parent && - isa(Parent->getTerminator())) { - Split = true; - break; - } - } - - if (!Split) continue; - - SmallVector NewBBs; - SplitLandingPadPredecessors(LPad, Parent, ".1", ".2", NewBBs); - } -} - -bool BlockExtractorPass::runOnModule(Module &M) { - if (skipModule(M)) - return false; - - std::set TranslatedBlocksToNotExtract; - for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { - BasicBlock *BB = BlocksToNotExtract[i]; - Function *F = BB->getParent(); - - // Map the corresponding function in this module. - Function *MF = M.getFunction(F->getName()); - assert(MF->getFunctionType() == F->getFunctionType() && "Wrong function?"); - - // Figure out which index the basic block is in its function. - Function::iterator BBI = MF->begin(); - std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); - TranslatedBlocksToNotExtract.insert(&*BBI); - } - - while (!BlocksToNotExtractByName.empty()) { - // There's no way to find BBs by name without looking at every BB inside - // every Function. Fortunately, this is always empty except when used by - // bugpoint in which case correctness is more important than performance. - - std::string &FuncName = BlocksToNotExtractByName.back().first; - std::string &BlockName = BlocksToNotExtractByName.back().second; - - for (Function &F : M) { - if (F.getName() != FuncName) continue; - - for (BasicBlock &BB : F) { - if (BB.getName() != BlockName) continue; - - TranslatedBlocksToNotExtract.insert(&BB); - } - } - - BlocksToNotExtractByName.pop_back(); - } - - // Now that we know which blocks to not extract, figure out which ones we WANT - // to extract. - std::vector BlocksToExtract; - for (Function &F : M) { - SplitLandingPadPreds(&F); - for (BasicBlock &BB : F) - if (!TranslatedBlocksToNotExtract.count(&BB)) - BlocksToExtract.push_back(&BB); - } - - for (BasicBlock *BlockToExtract : BlocksToExtract) { - SmallVector BlocksToExtractVec; - BlocksToExtractVec.push_back(BlockToExtract); - if (const InvokeInst *II = - dyn_cast(BlockToExtract->getTerminator())) - BlocksToExtractVec.push_back(II->getUnwindDest()); - CodeExtractor(BlocksToExtractVec).extractCodeRegion(); - } - - return !BlocksToExtract.empty(); -} Index: test/Transforms/BlockExtractor/extract-blocks.ll =================================================================== --- /dev/null +++ test/Transforms/BlockExtractor/extract-blocks.ll @@ -0,0 +1,43 @@ +; RUN: echo 'foo bb9' > %t +; RUN: echo 'foo bb20' >> %t +; RUN: opt -S -extract-blocks -extract-blocks-file=%t %s | FileCheck %s --check-prefix=CHECK-NO-ERASE +; RUN: opt -S -extract-blocks -extract-blocks-file=%t -extract-blocks-erase-funcs %s | FileCheck %s --check-prefix=CHECK-ERASE + +; CHECK-NO-ERASE: @foo( +; CHECK-NO-ERASE: @foo_bb9( +; CHECK-NO-ERASE: @foo_bb20( +; CHECK-ERASE-NOT: @foo( +; CHECK-ERASE: @foo_bb9( +; CHECK-ERASE: @foo_bb20( +define i32 @foo(i32 %arg, i32 %arg1) { +bb: + %tmp5 = icmp sgt i32 %arg, 0 + %tmp8 = icmp sgt i32 %arg1, 0 + %or.cond = and i1 %tmp5, %tmp8 + br i1 %or.cond, label %bb9, label %bb14 + +bb9: ; preds = %bb + %tmp12 = shl i32 %arg1, 2 + %tmp13 = add nsw i32 %tmp12, %arg + br label %bb30 + +bb14: ; preds = %bb + %0 = and i32 %arg1, %arg + %1 = icmp slt i32 %0, 0 + br i1 %1, label %bb20, label %bb26 + +bb20: ; preds = %bb14 + %tmp22 = mul nsw i32 %arg, 3 + %tmp24 = sdiv i32 %arg1, 6 + %tmp25 = add nsw i32 %tmp24, %tmp22 + br label %bb30 + +bb26: ; preds = %bb14 + %tmp29 = sub nsw i32 %arg, %arg1 + br label %bb30 + +bb30: ; preds = %bb26, %bb20, %bb9 + %tmp.0 = phi i32 [ %tmp13, %bb9 ], [ %tmp25, %bb20 ], [ %tmp29, %bb26 ] + ret i32 %tmp.0 +} + Index: test/Transforms/BlockExtractor/invalid-block.ll =================================================================== --- /dev/null +++ test/Transforms/BlockExtractor/invalid-block.ll @@ -0,0 +1,9 @@ +; RUN: echo 'bar invalidbb' > %t +; RUN: not opt -S -extract-blocks -extract-blocks-file=%t %s 2>&1 | FileCheck %s + +; CHECK: Invalid block +define void @bar() { +bb: + ret void +} + Index: test/Transforms/BlockExtractor/invalid-function.ll =================================================================== --- /dev/null +++ test/Transforms/BlockExtractor/invalid-function.ll @@ -0,0 +1,9 @@ +; RUN: echo 'foo bb' > %t +; RUN: not opt -S -extract-blocks -extract-blocks-file=%t %s 2>&1 | FileCheck %s + +; CHECK: Invalid function +define void @bar() { +bb: + ret void +} + Index: test/tools/llvm-extract/extract-block.ll =================================================================== --- /dev/null +++ test/tools/llvm-extract/extract-block.ll @@ -0,0 +1,29 @@ +; RUN: llvm-extract -S -bb foo:bb4 %s | FileCheck %s + +; CHECK: @foo_bb4 +; CHECK: %tmp5 +define i32 @foo(i32 %arg) { +bb: + %tmp = alloca i32, align 4 + %tmp1 = alloca i32, align 4 + store i32 %arg, i32* %tmp1, align 4 + %tmp2 = load i32, i32* %tmp1, align 4 + %tmp3 = icmp sgt i32 %tmp2, 0 + br i1 %tmp3, label %bb4, label %bb7 + +bb4: ; preds = %bb + %tmp5 = load i32, i32* %tmp1, align 4 + %tmp6 = add nsw i32 %tmp5, 1 + store i32 %tmp6, i32* %tmp1, align 4 + store i32 %tmp6, i32* %tmp, align 4 + br label %bb8 + +bb7: ; preds = %bb + store i32 0, i32* %tmp, align 4 + br label %bb8 + +bb8: ; preds = %bb7, %bb4 + %tmp9 = load i32, i32* %tmp, align 4 + ret i32 %tmp9 +} + Index: test/tools/llvm-extract/extract-invalid-block.ll =================================================================== --- /dev/null +++ test/tools/llvm-extract/extract-invalid-block.ll @@ -0,0 +1,28 @@ +; RUN: not llvm-extract -S -bb foo:invalidbb %s 2>&1 | FileCheck %s + +; CHECK: function foo doesn't contain a basic block named 'invalidbb'! +define i32 @foo(i32 %arg) { +bb: + %tmp = alloca i32, align 4 + %tmp1 = alloca i32, align 4 + store i32 %arg, i32* %tmp1, align 4 + %tmp2 = load i32, i32* %tmp1, align 4 + %tmp3 = icmp sgt i32 %tmp2, 0 + br i1 %tmp3, label %bb4, label %bb7 + +bb4: ; preds = %bb + %tmp5 = load i32, i32* %tmp1, align 4 + %tmp6 = add nsw i32 %tmp5, 1 + store i32 %tmp6, i32* %tmp1, align 4 + store i32 %tmp6, i32* %tmp, align 4 + br label %bb8 + +bb7: ; preds = %bb + store i32 0, i32* %tmp, align 4 + br label %bb8 + +bb8: ; preds = %bb7, %bb4 + %tmp9 = load i32, i32* %tmp, align 4 + ret i32 %tmp9 +} + Index: test/tools/llvm-extract/extract-multiple-blocks.ll =================================================================== --- /dev/null +++ test/tools/llvm-extract/extract-multiple-blocks.ll @@ -0,0 +1,29 @@ +; RUN: llvm-extract -S -bb foo:bb4 -bb foo:bb7 %s | FileCheck %s + +; CHECK: @foo_bb4 +; CHECK: @foo_bb7 +define i32 @foo(i32 %arg) { +bb: + %tmp = alloca i32, align 4 + %tmp1 = alloca i32, align 4 + store i32 %arg, i32* %tmp1, align 4 + %tmp2 = load i32, i32* %tmp1, align 4 + %tmp3 = icmp sgt i32 %tmp2, 0 + br i1 %tmp3, label %bb4, label %bb7 + +bb4: ; preds = %bb + %tmp5 = load i32, i32* %tmp1, align 4 + %tmp6 = add nsw i32 %tmp5, 1 + store i32 %tmp6, i32* %tmp1, align 4 + store i32 %tmp6, i32* %tmp, align 4 + br label %bb8 + +bb7: ; preds = %bb + store i32 0, i32* %tmp, align 4 + br label %bb8 + +bb8: ; preds = %bb7, %bb4 + %tmp9 = load i32, i32* %tmp, align 4 + ret i32 %tmp9 +} + Index: tools/bugpoint/ExtractFunction.cpp =================================================================== --- tools/bugpoint/ExtractFunction.cpp +++ tools/bugpoint/ExtractFunction.cpp @@ -383,10 +383,16 @@ } DiscardTemp Discard{*Temp}; + // Extract all of the blocks except the ones in BBs. + SmallVector BlocksToExtract; + for (Function &F : *M) + for (BasicBlock &BB : F) + // Check if this block is going to be extracted. + if (std::find(BBs.begin(), BBs.end(), &BB) == BBs.end()) + BlocksToExtract.push_back(&BB); + raw_fd_ostream OS(Temp->FD, /*shouldClose*/ false); - for (std::vector::const_iterator I = BBs.begin(), E = BBs.end(); - I != E; ++I) { - BasicBlock *BB = *I; + for (BasicBlock *BB : BBs) { // If the BB doesn't have a name, give it one so we have something to key // off of. if (!BB->hasName()) Index: tools/llvm-extract/llvm-extract.cpp =================================================================== --- tools/llvm-extract/llvm-extract.cpp +++ tools/llvm-extract/llvm-extract.cpp @@ -67,6 +67,12 @@ "regular expression"), cl::ZeroOrMore, cl::value_desc("rfunction")); +// ExtractBlocks - The blocks to extract from the module. +static cl::list + ExtractBlocks("bb", + cl::desc("Specify pairs to extract"), + cl::ZeroOrMore, cl::value_desc("function:bb")); + // ExtractAlias - The alias to extract from the module. static cl::list ExtractAliases("alias", cl::desc("Specify alias to extract"), @@ -228,6 +234,32 @@ } } + // Figure out which BasicBlocks we should extract. + SmallVector BBs; + for (StringRef StrPair : ExtractBlocks) { + auto BBInfo = StrPair.split(':'); + // Get the function. + Function *F = M->getFunction(BBInfo.first); + if (!F) { + errs() << argv[0] << ": program doesn't contain a function named '" + << BBInfo.first << "'!\n"; + return 1; + } + // Do not materialize this function. + GVs.insert(F); + // Get the basic block. + auto Res = llvm::find_if(*F, [&](const BasicBlock &BB) { + return BB.getName().equals(BBInfo.second); + }); + if (Res == F->end()) { + errs() << argv[0] << ": function " << F->getName() + << " doesn't contain a basic block named '" << BBInfo.second + << "'!\n"; + return 1; + } + BBs.push_back(&*Res); + } + // Use *argv instead of argv[0] to work around a wrong GCC warning. ExitOnError ExitOnErr(std::string(*argv) + ": error reading input: "); @@ -286,6 +318,14 @@ ExitOnErr(M->materializeAll()); } + // Extract the specified basic blocks from the module and erase the existing + // functions. + if (!ExtractBlocks.empty()) { + legacy::PassManager PM; + PM.add(createBlockExtractorPass(BBs, true)); + PM.run(*M); + } + // In addition to deleting all other functions, we also want to spiff it // up a little bit. Do this now. legacy::PassManager Passes;