ExtractFunction.cpp revision 891150f0b2a124a75c9f31516182ce864ae69ef8
1//===- ExtractFunction.cpp - Extract a function from Program --------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements several methods that are used to extract functions, 11// loops, or portions of a module from the rest of the module. 12// 13//===----------------------------------------------------------------------===// 14 15#include "BugDriver.h" 16#include "llvm/Constant.h" 17#include "llvm/Module.h" 18#include "llvm/PassManager.h" 19#include "llvm/Pass.h" 20#include "llvm/Type.h" 21#include "llvm/Analysis/Verifier.h" 22#include "llvm/Transforms/IPO.h" 23#include "llvm/Transforms/Scalar.h" 24#include "llvm/Transforms/Utils/Cloning.h" 25#include "llvm/Transforms/Utils/FunctionUtils.h" 26#include "llvm/Target/TargetData.h" 27#include "Support/CommandLine.h" 28#include "Support/Debug.h" 29#include "Support/FileUtilities.h" 30#include <set> 31using namespace llvm; 32 33namespace llvm { 34 bool DisableSimplifyCFG = false; 35} // End llvm namespace 36 37namespace { 38 cl::opt<bool> 39 NoDCE ("disable-dce", 40 cl::desc("Do not use the -dce pass to reduce testcases")); 41 cl::opt<bool, true> 42 NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG), 43 cl::desc("Do not use the -simplifycfg pass to reduce testcases")); 44} 45 46/// deleteInstructionFromProgram - This method clones the current Program and 47/// deletes the specified instruction from the cloned module. It then runs a 48/// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which 49/// depends on the value. The modified module is then returned. 50/// 51Module *BugDriver::deleteInstructionFromProgram(const Instruction *I, 52 unsigned Simplification) const { 53 Module *Result = CloneModule(Program); 54 55 const BasicBlock *PBB = I->getParent(); 56 const Function *PF = PBB->getParent(); 57 58 Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn 59 std::advance(RFI, std::distance(PF->getParent()->begin(), 60 Module::const_iterator(PF))); 61 62 Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 63 std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 64 65 BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 66 std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 67 Instruction *TheInst = RI; // Got the corresponding instruction! 68 69 // If this instruction produces a value, replace any users with null values 70 if (TheInst->getType() != Type::VoidTy) 71 TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); 72 73 // Remove the instruction from the program. 74 TheInst->getParent()->getInstList().erase(TheInst); 75 76 // Spiff up the output a little bit. 77 PassManager Passes; 78 // Make sure that the appropriate target data is always used... 79 Passes.add(new TargetData("bugpoint", Result)); 80 81 /// FIXME: If this used runPasses() like the methods below, we could get rid 82 /// of the -disable-* options! 83 if (Simplification > 1 && !NoDCE) 84 Passes.add(createDeadCodeEliminationPass()); 85 if (Simplification && !DisableSimplifyCFG) 86 Passes.add(createCFGSimplificationPass()); // Delete dead control flow 87 88 Passes.add(createVerifierPass()); 89 Passes.run(*Result); 90 return Result; 91} 92 93static const PassInfo *getPI(Pass *P) { 94 const PassInfo *PI = P->getPassInfo(); 95 delete P; 96 return PI; 97} 98 99/// performFinalCleanups - This method clones the current Program and performs 100/// a series of cleanups intended to get rid of extra cruft on the module 101/// before handing it to the user... 102/// 103Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { 104 // Make all functions external, so GlobalDCE doesn't delete them... 105 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 106 I->setLinkage(GlobalValue::ExternalLinkage); 107 108 std::vector<const PassInfo*> CleanupPasses; 109 CleanupPasses.push_back(getPI(createFunctionResolvingPass())); 110 CleanupPasses.push_back(getPI(createGlobalDCEPass())); 111 CleanupPasses.push_back(getPI(createDeadTypeEliminationPass())); 112 113 if (MayModifySemantics) 114 CleanupPasses.push_back(getPI(createDeadArgHackingPass())); 115 else 116 CleanupPasses.push_back(getPI(createDeadArgEliminationPass())); 117 118 Module *New = runPassesOn(M, CleanupPasses); 119 if (New == 0) { 120 std::cerr << "Final cleanups failed. Sorry. :( Please report a bug!\n"; 121 } 122 delete M; 123 return New; 124} 125 126 127/// ExtractLoop - Given a module, extract up to one loop from it into a new 128/// function. This returns null if there are no extractable loops in the 129/// program or if the loop extractor crashes. 130Module *BugDriver::ExtractLoop(Module *M) { 131 std::vector<const PassInfo*> LoopExtractPasses; 132 LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass())); 133 134 Module *NewM = runPassesOn(M, LoopExtractPasses); 135 if (NewM == 0) { 136 Module *Old = swapProgramIn(M); 137 std::cout << "*** Loop extraction failed: "; 138 EmitProgressBytecode("loopextraction", true); 139 std::cout << "*** Sorry. :( Please report a bug!\n"; 140 swapProgramIn(Old); 141 return 0; 142 } 143 144 // Check to see if we created any new functions. If not, no loops were 145 // extracted and we should return null. 146 if (M->size() == NewM->size()) { 147 delete NewM; 148 return 0; 149 } 150 151 return NewM; 152} 153 154 155// DeleteFunctionBody - "Remove" the function by deleting all of its basic 156// blocks, making it external. 157// 158void llvm::DeleteFunctionBody(Function *F) { 159 // delete the body of the function... 160 F->deleteBody(); 161 assert(F->isExternal() && "This didn't make the function external!"); 162} 163 164/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 165/// module, split the functions OUT of the specified module, and place them in 166/// the new module. 167/// 168/// FIXME: this could be made DRAMATICALLY more efficient for large programs if 169/// we just MOVED functions from one module to the other, instead of cloning the 170/// whole module, then proceeding to delete an entire module's worth of stuff. 171/// 172Module *llvm::SplitFunctionsOutOfModule(Module *M, 173 const std::vector<Function*> &F) { 174 // Make sure functions & globals are all external so that linkage 175 // between the two modules will work. 176 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 177 I->setLinkage(GlobalValue::ExternalLinkage); 178 for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I) 179 I->setLinkage(GlobalValue::ExternalLinkage); 180 181 Module *New = CloneModule(M); 182 183 // Make sure global initializers exist only in the safe module (CBE->.so) 184 for (Module::giterator I = New->gbegin(), E = New->gend(); I != E; ++I) 185 I->setInitializer(0); // Delete the initializer to make it external 186 187 // Remove the Test functions from the Safe module 188 std::set<std::pair<std::string, const PointerType*> > TestFunctions; 189 for (unsigned i = 0, e = F.size(); i != e; ++i) { 190 TestFunctions.insert(std::make_pair(F[i]->getName(), F[i]->getType())); 191 Function *TNOF = M->getFunction(F[i]->getName(), F[i]->getFunctionType()); 192 DEBUG(std::cerr << "Removing function " << F[i]->getName() << "\n"); 193 assert(TNOF && "Function doesn't exist in module!"); 194 DeleteFunctionBody(TNOF); // Function is now external in this module! 195 } 196 197 // Remove the Safe functions from the Test module 198 for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 199 if (!TestFunctions.count(std::make_pair(I->getName(), I->getType()))) 200 DeleteFunctionBody(I); 201 return New; 202} 203 204//===----------------------------------------------------------------------===// 205// Basic Block Extraction Code 206//===----------------------------------------------------------------------===// 207 208namespace { 209 std::vector<BasicBlock*> BlocksToNotExtract; 210 211 /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 212 /// from the module into their own functions except for those specified by the 213 /// BlocksToNotExtract list. 214 class BlockExtractorPass : public Pass { 215 bool run(Module &M); 216 }; 217 RegisterOpt<BlockExtractorPass> 218 XX("extract-bbs", "Extract Basic Blocks From Module (for bugpoint use)"); 219} 220 221bool BlockExtractorPass::run(Module &M) { 222 std::set<BasicBlock*> TranslatedBlocksToNotExtract; 223 for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 224 BasicBlock *BB = BlocksToNotExtract[i]; 225 Function *F = BB->getParent(); 226 227 // Map the corresponding function in this module. 228 Function *MF = M.getFunction(F->getName(), F->getFunctionType()); 229 230 // Figure out which index the basic block is in its function. 231 Function::iterator BBI = MF->begin(); 232 std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 233 TranslatedBlocksToNotExtract.insert(BBI); 234 } 235 236 // Now that we know which blocks to not extract, figure out which ones we WANT 237 // to extract. 238 std::vector<BasicBlock*> BlocksToExtract; 239 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 240 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 241 if (!TranslatedBlocksToNotExtract.count(BB)) 242 BlocksToExtract.push_back(BB); 243 244 for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) 245 ExtractBasicBlock(BlocksToExtract[i]); 246 247 return !BlocksToExtract.empty(); 248} 249 250/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 251/// into their own functions. The only detail is that M is actually a module 252/// cloned from the one the BBs are in, so some mapping needs to be performed. 253/// If this operation fails for some reason (ie the implementation is buggy), 254/// this function should return null, otherwise it returns a new Module. 255Module *BugDriver::ExtractMappedBlocksFromModule(const 256 std::vector<BasicBlock*> &BBs, 257 Module *M) { 258 // Set the global list so that pass will be able to access it. 259 BlocksToNotExtract = BBs; 260 261 std::vector<const PassInfo*> PI; 262 PI.push_back(getPI(new BlockExtractorPass())); 263 Module *Ret = runPassesOn(M, PI); 264 BlocksToNotExtract.clear(); 265 if (Ret == 0) { 266 std::cout << "*** Basic Block extraction failed, please report a bug!\n"; 267 M = swapProgramIn(M); 268 EmitProgressBytecode("basicblockextractfail", true); 269 M = swapProgramIn(M); 270 } 271 return Ret; 272} 273