X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=tools%2Fbugpoint%2FExtractFunction.cpp;h=73b65ca94f70c5cbe2c3466d01710afb22387725;hb=adf01b3f18442ae8db6b8948e70d82d9df415119;hp=ecc2652556eb342aa5c20d0f5927a621f1aa440c;hpb=5e783ab0b5fc3407ec59f1a598fdb9ef3b96b287;p=oota-llvm.git diff --git a/tools/bugpoint/ExtractFunction.cpp b/tools/bugpoint/ExtractFunction.cpp index ecc2652556e..73b65ca94f7 100644 --- a/tools/bugpoint/ExtractFunction.cpp +++ b/tools/bugpoint/ExtractFunction.cpp @@ -1,10 +1,10 @@ //===- ExtractFunction.cpp - Extract a function from Program --------------===// -// +// // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // // This file implements several methods that are used to extract functions, @@ -13,25 +13,31 @@ //===----------------------------------------------------------------------===// #include "BugDriver.h" -#include "llvm/Constant.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/PassManager.h" #include "llvm/Pass.h" -#include "llvm/Type.h" #include "llvm/Analysis/Verifier.h" +#include "llvm/Assembly/Writer.h" #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/FunctionUtils.h" #include "llvm/Target/TargetData.h" -#include "Support/CommandLine.h" -#include "Support/Debug.h" -#include "Support/FileUtilities.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/Support/ToolOutputFile.h" +#include "llvm/Support/Path.h" +#include "llvm/Support/Signals.h" #include using namespace llvm; namespace llvm { bool DisableSimplifyCFG = false; + extern cl::opt OutputPrefix; } // End llvm namespace namespace { @@ -49,13 +55,14 @@ namespace { /// depends on the value. The modified module is then returned. /// Module *BugDriver::deleteInstructionFromProgram(const Instruction *I, - unsigned Simplification) const { - Module *Result = CloneModule(Program); + unsigned Simplification) { + // FIXME, use vmap? + Module *Clone = CloneModule(Program); const BasicBlock *PBB = I->getParent(); const Function *PF = PBB->getParent(); - Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn + Module::iterator RFI = Clone->begin(); // Get iterator to corresponding fn std::advance(RFI, std::distance(PF->getParent()->begin(), Module::const_iterator(PF))); @@ -67,57 +74,52 @@ Module *BugDriver::deleteInstructionFromProgram(const Instruction *I, Instruction *TheInst = RI; // Got the corresponding instruction! // If this instruction produces a value, replace any users with null values - if (TheInst->getType() != Type::VoidTy) + if (!TheInst->getType()->isVoidTy()) TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); // Remove the instruction from the program. TheInst->getParent()->getInstList().erase(TheInst); // Spiff up the output a little bit. - PassManager Passes; - // Make sure that the appropriate target data is always used... - Passes.add(new TargetData("bugpoint", Result)); + std::vector Passes; - /// FIXME: If this used runPasses() like the methods below, we could get rid - /// of the -disable-* options! + /// Can we get rid of the -disable-* options? if (Simplification > 1 && !NoDCE) - Passes.add(createDeadCodeEliminationPass()); + Passes.push_back("dce"); if (Simplification && !DisableSimplifyCFG) - Passes.add(createCFGSimplificationPass()); // Delete dead control flow - - Passes.add(createVerifierPass()); - Passes.run(*Result); - return Result; -} - -static const PassInfo *getPI(Pass *P) { - const PassInfo *PI = P->getPassInfo(); - delete P; - return PI; + Passes.push_back("simplifycfg"); // Delete dead control flow + + Passes.push_back("verify"); + Module *New = runPassesOn(Clone, Passes); + delete Clone; + if (!New) { + errs() << "Instruction removal failed. Sorry. :( Please report a bug!\n"; + exit(1); + } + return New; } /// performFinalCleanups - This method clones the current Program and performs /// a series of cleanups intended to get rid of extra cruft on the module -/// before handing it to the user... +/// before handing it to the user. /// Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { // Make all functions external, so GlobalDCE doesn't delete them... for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) I->setLinkage(GlobalValue::ExternalLinkage); - - std::vector CleanupPasses; - CleanupPasses.push_back(getPI(createFunctionResolvingPass())); - CleanupPasses.push_back(getPI(createGlobalDCEPass())); - CleanupPasses.push_back(getPI(createDeadTypeEliminationPass())); + + std::vector CleanupPasses; + CleanupPasses.push_back("globaldce"); if (MayModifySemantics) - CleanupPasses.push_back(getPI(createDeadArgHackingPass())); + CleanupPasses.push_back("deadarghaX0r"); else - CleanupPasses.push_back(getPI(createDeadArgEliminationPass())); + CleanupPasses.push_back("deadargelim"); Module *New = runPassesOn(M, CleanupPasses); if (New == 0) { - std::cerr << "Final cleanups failed. Sorry. :( Please report a bug!\n"; + errs() << "Final cleanups failed. Sorry. :( Please report a bug!\n"; + return M; } delete M; return New; @@ -128,26 +130,31 @@ Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { /// function. This returns null if there are no extractable loops in the /// program or if the loop extractor crashes. Module *BugDriver::ExtractLoop(Module *M) { - std::vector LoopExtractPasses; - LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass())); + std::vector LoopExtractPasses; + LoopExtractPasses.push_back("loop-extract-single"); Module *NewM = runPassesOn(M, LoopExtractPasses); if (NewM == 0) { - Module *Old = swapProgramIn(M); - std::cout << "*** Loop extraction failed: "; - EmitProgressBytecode("loopextraction", true); - std::cout << "*** Sorry. :( Please report a bug!\n"; - swapProgramIn(Old); + outs() << "*** Loop extraction failed: "; + EmitProgressBitcode(M, "loopextraction", true); + outs() << "*** Sorry. :( Please report a bug!\n"; return 0; } // Check to see if we created any new functions. If not, no loops were - // extracted and we should return null. - if (M->size() == NewM->size()) { + // extracted and we should return null. Limit the number of loops we extract + // to avoid taking forever. + static unsigned NumExtracted = 32; + if (M->size() == NewM->size() || --NumExtracted == 0) { delete NewM; return 0; + } else { + assert(M->size() < NewM->size() && "Loop extract removed functions?"); + Module::iterator MI = NewM->begin(); + for (unsigned i = 0, e = M->size(); i != e; ++i) + ++MI; } - + return NewM; } @@ -158,46 +165,141 @@ Module *BugDriver::ExtractLoop(Module *M) { void llvm::DeleteFunctionBody(Function *F) { // delete the body of the function... F->deleteBody(); - assert(F->isExternal() && "This didn't make the function external!"); + assert(F->isDeclaration() && "This didn't make the function external!"); +} + +/// GetTorInit - Given a list of entries for static ctors/dtors, return them +/// as a constant array. +static Constant *GetTorInit(std::vector > &TorList) { + assert(!TorList.empty() && "Don't create empty tor list!"); + std::vector ArrayElts; + Type *Int32Ty = Type::getInt32Ty(TorList[0].first->getContext()); + + StructType *STy = + StructType::get(Int32Ty, TorList[0].first->getType(), NULL); + for (unsigned i = 0, e = TorList.size(); i != e; ++i) { + Constant *Elts[] = { + ConstantInt::get(Int32Ty, TorList[i].second), + TorList[i].first + }; + ArrayElts.push_back(ConstantStruct::get(STy, Elts)); + } + return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), + ArrayElts.size()), + ArrayElts); +} + +/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and +/// M1 has all of the global variables. If M2 contains any functions that are +/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and +/// prune appropriate entries out of M1s list. +static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, + ValueToValueMapTy &VMap) { + GlobalVariable *GV = M1->getNamedGlobal(GlobalName); + if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || + !GV->use_empty()) return; + + std::vector > M1Tors, M2Tors; + ConstantArray *InitList = dyn_cast(GV->getInitializer()); + if (!InitList) return; + + for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { + if (ConstantStruct *CS = dyn_cast(InitList->getOperand(i))){ + if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. + + if (CS->getOperand(1)->isNullValue()) + break; // Found a null terminator, stop here. + + ConstantInt *CI = dyn_cast(CS->getOperand(0)); + int Priority = CI ? CI->getSExtValue() : 0; + + Constant *FP = CS->getOperand(1); + if (ConstantExpr *CE = dyn_cast(FP)) + if (CE->isCast()) + FP = CE->getOperand(0); + if (Function *F = dyn_cast(FP)) { + if (!F->isDeclaration()) + M1Tors.push_back(std::make_pair(F, Priority)); + else { + // Map to M2's version of the function. + F = cast(VMap[F]); + M2Tors.push_back(std::make_pair(F, Priority)); + } + } + } + } + + GV->eraseFromParent(); + if (!M1Tors.empty()) { + Constant *M1Init = GetTorInit(M1Tors); + new GlobalVariable(*M1, M1Init->getType(), false, + GlobalValue::AppendingLinkage, + M1Init, GlobalName); + } + + GV = M2->getNamedGlobal(GlobalName); + assert(GV && "Not a clone of M1?"); + assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); + + GV->eraseFromParent(); + if (!M2Tors.empty()) { + Constant *M2Init = GetTorInit(M2Tors); + new GlobalVariable(*M2, M2Init->getType(), false, + GlobalValue::AppendingLinkage, + M2Init, GlobalName); + } } + /// SplitFunctionsOutOfModule - Given a module and a list of functions in the /// module, split the functions OUT of the specified module, and place them in /// the new module. -/// -/// FIXME: this could be made DRAMATICALLY more efficient for large programs if -/// we just MOVED functions from one module to the other, instead of cloning the -/// whole module, then proceeding to delete an entire module's worth of stuff. -/// -Module *llvm::SplitFunctionsOutOfModule(Module *M, - const std::vector &F) { +Module * +llvm::SplitFunctionsOutOfModule(Module *M, + const std::vector &F, + ValueToValueMapTy &VMap) { // Make sure functions & globals are all external so that linkage // between the two modules will work. for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) I->setLinkage(GlobalValue::ExternalLinkage); - for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) + for (Module::global_iterator I = M->global_begin(), E = M->global_end(); + I != E; ++I) { + if (I->hasName() && I->getName()[0] == '\01') + I->setName(I->getName().substr(1)); I->setLinkage(GlobalValue::ExternalLinkage); + } - Module *New = CloneModule(M); + ValueToValueMapTy NewVMap; + Module *New = CloneModule(M, NewVMap); // Make sure global initializers exist only in the safe module (CBE->.so) - for (Module::giterator I = New->gbegin(), E = New->gend(); I != E; ++I) + for (Module::global_iterator I = New->global_begin(), E = New->global_end(); + I != E; ++I) I->setInitializer(0); // Delete the initializer to make it external // Remove the Test functions from the Safe module - std::set > TestFunctions; + std::set TestFunctions; for (unsigned i = 0, e = F.size(); i != e; ++i) { - TestFunctions.insert(std::make_pair(F[i]->getName(), F[i]->getType())); - Function *TNOF = M->getFunction(F[i]->getName(), F[i]->getFunctionType()); - DEBUG(std::cerr << "Removing function " << F[i]->getName() << "\n"); - assert(TNOF && "Function doesn't exist in module!"); + Function *TNOF = cast(VMap[F[i]]); + DEBUG(errs() << "Removing function "); + DEBUG(WriteAsOperand(errs(), TNOF, false)); + DEBUG(errs() << "\n"); + TestFunctions.insert(cast(NewVMap[TNOF])); DeleteFunctionBody(TNOF); // Function is now external in this module! } + // Remove the Safe functions from the Test module for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) - if (!TestFunctions.count(std::make_pair(I->getName(), I->getType()))) + if (!TestFunctions.count(I)) DeleteFunctionBody(I); + + + // Make sure that there is a global ctor/dtor array in both halves of the + // module if they both have static ctor/dtor functions. + SplitStaticCtorDtor("llvm.global_ctors", M, New, NewVMap); + SplitStaticCtorDtor("llvm.global_dtors", M, New, NewVMap); + return New; } @@ -205,48 +307,6 @@ Module *llvm::SplitFunctionsOutOfModule(Module *M, // Basic Block Extraction Code //===----------------------------------------------------------------------===// -namespace { - std::vector BlocksToNotExtract; - - /// 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 Pass { - bool run(Module &M); - }; - RegisterOpt - XX("extract-bbs", "Extract Basic Blocks From Module (for bugpoint use)"); -} - -bool BlockExtractorPass::run(Module &M) { - 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(), F->getFunctionType()); - - // 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); - } - - // Now that we know which blocks to not extract, figure out which ones we WANT - // to extract. - std::vector BlocksToExtract; - for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - if (!TranslatedBlocksToNotExtract.count(BB)) - BlocksToExtract.push_back(BB); - - for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) - ExtractBasicBlock(BlocksToExtract[i]); - - return !BlocksToExtract.empty(); -} - /// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks /// into their own functions. The only detail is that M is actually a module /// cloned from the one the BBs are in, so some mapping needs to be performed. @@ -255,14 +315,56 @@ bool BlockExtractorPass::run(Module &M) { Module *BugDriver::ExtractMappedBlocksFromModule(const std::vector &BBs, Module *M) { - // Set the global list so that pass will be able to access it. - BlocksToNotExtract = BBs; - - std::vector PI; - PI.push_back(getPI(new BlockExtractorPass())); - Module *Ret = runPassesOn(M, PI); - BlocksToNotExtract.clear(); - if (Ret == 0) - std::cout << "*** Basic Block extraction failed, please report a bug!\n"; + sys::Path uniqueFilename(OutputPrefix + "-extractblocks"); + std::string ErrMsg; + if (uniqueFilename.createTemporaryFileOnDisk(true, &ErrMsg)) { + outs() << "*** Basic Block extraction failed!\n"; + errs() << "Error creating temporary file: " << ErrMsg << "\n"; + EmitProgressBitcode(M, "basicblockextractfail", true); + return 0; + } + sys::RemoveFileOnSignal(uniqueFilename); + + std::string ErrorInfo; + tool_output_file BlocksToNotExtractFile(uniqueFilename.c_str(), ErrorInfo); + if (!ErrorInfo.empty()) { + outs() << "*** Basic Block extraction failed!\n"; + errs() << "Error writing list of blocks to not extract: " << ErrorInfo + << "\n"; + EmitProgressBitcode(M, "basicblockextractfail", true); + return 0; + } + for (std::vector::const_iterator I = BBs.begin(), E = BBs.end(); + I != E; ++I) { + BasicBlock *BB = *I; + // If the BB doesn't have a name, give it one so we have something to key + // off of. + if (!BB->hasName()) BB->setName("tmpbb"); + BlocksToNotExtractFile.os() << BB->getParent()->getNameStr() << " " + << BB->getName() << "\n"; + } + BlocksToNotExtractFile.os().close(); + if (BlocksToNotExtractFile.os().has_error()) { + errs() << "Error writing list of blocks to not extract: " << ErrorInfo + << "\n"; + EmitProgressBitcode(M, "basicblockextractfail", true); + BlocksToNotExtractFile.os().clear_error(); + return 0; + } + BlocksToNotExtractFile.keep(); + + std::string uniqueFN = "--extract-blocks-file=" + uniqueFilename.str(); + const char *ExtraArg = uniqueFN.c_str(); + + std::vector PI; + PI.push_back("extract-blocks"); + Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg); + + uniqueFilename.eraseFromDisk(); // Free disk space + + if (Ret == 0) { + outs() << "*** Basic Block extraction failed, please report a bug!\n"; + EmitProgressBitcode(M, "basicblockextractfail", true); + } return Ret; }