ExtractFunction.cpp revision 5cbf985dcbc89fba3208e7baf8b6f488b06d3ec9
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/Constants.h" 17#include "llvm/DerivedTypes.h" 18#include "llvm/Module.h" 19#include "llvm/PassManager.h" 20#include "llvm/Pass.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 "llvm/Support/CommandLine.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/Support/FileUtilities.h" 30#include <set> 31#include <iostream> 32using namespace llvm; 33 34namespace llvm { 35 bool DisableSimplifyCFG = false; 36} // End llvm namespace 37 38namespace { 39 cl::opt<bool> 40 NoDCE ("disable-dce", 41 cl::desc("Do not use the -dce pass to reduce testcases")); 42 cl::opt<bool, true> 43 NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG), 44 cl::desc("Do not use the -simplifycfg pass to reduce testcases")); 45} 46 47/// deleteInstructionFromProgram - This method clones the current Program and 48/// deletes the specified instruction from the cloned module. It then runs a 49/// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which 50/// depends on the value. The modified module is then returned. 51/// 52Module *BugDriver::deleteInstructionFromProgram(const Instruction *I, 53 unsigned Simplification) const { 54 Module *Result = CloneModule(Program); 55 56 const BasicBlock *PBB = I->getParent(); 57 const Function *PF = PBB->getParent(); 58 59 Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn 60 std::advance(RFI, std::distance(PF->getParent()->begin(), 61 Module::const_iterator(PF))); 62 63 Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 64 std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 65 66 BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 67 std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 68 Instruction *TheInst = RI; // Got the corresponding instruction! 69 70 // If this instruction produces a value, replace any users with null values 71 if (TheInst->getType() != Type::VoidTy) 72 TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); 73 74 // Remove the instruction from the program. 75 TheInst->getParent()->getInstList().erase(TheInst); 76 77 78 //writeProgramToFile("current.bc", Result); 79 80 // Spiff up the output a little bit. 81 PassManager Passes; 82 // Make sure that the appropriate target data is always used... 83 Passes.add(new TargetData(Result)); 84 85 /// FIXME: If this used runPasses() like the methods below, we could get rid 86 /// of the -disable-* options! 87 if (Simplification > 1 && !NoDCE) 88 Passes.add(createDeadCodeEliminationPass()); 89 if (Simplification && !DisableSimplifyCFG) 90 Passes.add(createCFGSimplificationPass()); // Delete dead control flow 91 92 Passes.add(createVerifierPass()); 93 Passes.run(*Result); 94 return Result; 95} 96 97static const PassInfo *getPI(Pass *P) { 98 const PassInfo *PI = P->getPassInfo(); 99 delete P; 100 return PI; 101} 102 103/// performFinalCleanups - This method clones the current Program and performs 104/// a series of cleanups intended to get rid of extra cruft on the module 105/// before handing it to the user. 106/// 107Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { 108 // Make all functions external, so GlobalDCE doesn't delete them... 109 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 110 I->setLinkage(GlobalValue::ExternalLinkage); 111 112 std::vector<const PassInfo*> CleanupPasses; 113 CleanupPasses.push_back(getPI(createFunctionResolvingPass())); 114 CleanupPasses.push_back(getPI(createGlobalDCEPass())); 115 CleanupPasses.push_back(getPI(createDeadTypeEliminationPass())); 116 117 if (MayModifySemantics) 118 CleanupPasses.push_back(getPI(createDeadArgHackingPass())); 119 else 120 CleanupPasses.push_back(getPI(createDeadArgEliminationPass())); 121 122 Module *New = runPassesOn(M, CleanupPasses); 123 if (New == 0) { 124 std::cerr << "Final cleanups failed. Sorry. :( Please report a bug!\n"; 125 return M; 126 } 127 delete M; 128 return New; 129} 130 131 132/// ExtractLoop - Given a module, extract up to one loop from it into a new 133/// function. This returns null if there are no extractable loops in the 134/// program or if the loop extractor crashes. 135Module *BugDriver::ExtractLoop(Module *M) { 136 std::vector<const PassInfo*> LoopExtractPasses; 137 LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass())); 138 139 Module *NewM = runPassesOn(M, LoopExtractPasses); 140 if (NewM == 0) { 141 Module *Old = swapProgramIn(M); 142 std::cout << "*** Loop extraction failed: "; 143 EmitProgressBytecode("loopextraction", true); 144 std::cout << "*** Sorry. :( Please report a bug!\n"; 145 swapProgramIn(Old); 146 return 0; 147 } 148 149 // Check to see if we created any new functions. If not, no loops were 150 // extracted and we should return null. Limit the number of loops we extract 151 // to avoid taking forever. 152 static unsigned NumExtracted = 32; 153 if (M->size() == NewM->size() || --NumExtracted == 0) { 154 delete NewM; 155 return 0; 156 } else { 157 assert(M->size() < NewM->size() && "Loop extract removed functions?"); 158 Module::iterator MI = NewM->begin(); 159 for (unsigned i = 0, e = M->size(); i != e; ++i) 160 ++MI; 161 } 162 163 return NewM; 164} 165 166 167// DeleteFunctionBody - "Remove" the function by deleting all of its basic 168// blocks, making it external. 169// 170void llvm::DeleteFunctionBody(Function *F) { 171 // delete the body of the function... 172 F->deleteBody(); 173 assert(F->isDeclaration() && "This didn't make the function external!"); 174} 175 176/// GetTorInit - Given a list of entries for static ctors/dtors, return them 177/// as a constant array. 178static Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) { 179 assert(!TorList.empty() && "Don't create empty tor list!"); 180 std::vector<Constant*> ArrayElts; 181 for (unsigned i = 0, e = TorList.size(); i != e; ++i) { 182 std::vector<Constant*> Elts; 183 Elts.push_back(ConstantInt::get(Type::Int32Ty, TorList[i].second)); 184 Elts.push_back(TorList[i].first); 185 ArrayElts.push_back(ConstantStruct::get(Elts)); 186 } 187 return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), 188 ArrayElts.size()), 189 ArrayElts); 190} 191 192/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and 193/// M1 has all of the global variables. If M2 contains any functions that are 194/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and 195/// prune appropriate entries out of M1s list. 196static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2){ 197 GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 198 if (!GV || GV->isDeclaration() || GV->hasInternalLinkage() || 199 !GV->use_empty()) return; 200 201 std::vector<std::pair<Function*, int> > M1Tors, M2Tors; 202 ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 203 if (!InitList) return; 204 205 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { 206 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){ 207 if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. 208 209 if (CS->getOperand(1)->isNullValue()) 210 break; // Found a null terminator, stop here. 211 212 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 213 int Priority = CI ? CI->getSExtValue() : 0; 214 215 Constant *FP = CS->getOperand(1); 216 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP)) 217 if (CE->isCast()) 218 FP = CE->getOperand(0); 219 if (Function *F = dyn_cast<Function>(FP)) { 220 if (!F->isDeclaration()) 221 M1Tors.push_back(std::make_pair(F, Priority)); 222 else { 223 // Map to M2's version of the function. 224 F = M2->getFunction(F->getName(), F->getFunctionType()); 225 M2Tors.push_back(std::make_pair(F, Priority)); 226 } 227 } 228 } 229 } 230 231 GV->eraseFromParent(); 232 if (!M1Tors.empty()) { 233 Constant *M1Init = GetTorInit(M1Tors); 234 new GlobalVariable(M1Init->getType(), false, GlobalValue::AppendingLinkage, 235 M1Init, GlobalName, M1); 236 } 237 238 GV = M2->getNamedGlobal(GlobalName); 239 assert(GV && "Not a clone of M1?"); 240 assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 241 242 GV->eraseFromParent(); 243 if (!M2Tors.empty()) { 244 Constant *M2Init = GetTorInit(M2Tors); 245 new GlobalVariable(M2Init->getType(), false, GlobalValue::AppendingLinkage, 246 M2Init, GlobalName, M2); 247 } 248} 249 250 251/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 252/// module, split the functions OUT of the specified module, and place them in 253/// the new module. 254Module *llvm::SplitFunctionsOutOfModule(Module *M, 255 const std::vector<Function*> &F) { 256 // Make sure functions & globals are all external so that linkage 257 // between the two modules will work. 258 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 259 I->setLinkage(GlobalValue::ExternalLinkage); 260 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 261 I != E; ++I) 262 I->setLinkage(GlobalValue::ExternalLinkage); 263 264 Module *New = CloneModule(M); 265 266 // Make sure global initializers exist only in the safe module (CBE->.so) 267 for (Module::global_iterator I = New->global_begin(), E = New->global_end(); 268 I != E; ++I) 269 I->setInitializer(0); // Delete the initializer to make it external 270 271 // Remove the Test functions from the Safe module 272 std::set<std::pair<std::string, const PointerType*> > TestFunctions; 273 for (unsigned i = 0, e = F.size(); i != e; ++i) { 274 TestFunctions.insert(std::make_pair(F[i]->getName(), F[i]->getType())); 275 Function *TNOF = M->getFunction(F[i]->getName(), F[i]->getFunctionType()); 276 DEBUG(std::cerr << "Removing function " << F[i]->getName() << "\n"); 277 assert(TNOF && "Function doesn't exist in module!"); 278 DeleteFunctionBody(TNOF); // Function is now external in this module! 279 } 280 281 282 // Remove the Safe functions from the Test module 283 for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 284 if (!TestFunctions.count(std::make_pair(I->getName(), I->getType()))) 285 DeleteFunctionBody(I); 286 287 288 // Make sure that there is a global ctor/dtor array in both halves of the 289 // module if they both have static ctor/dtor functions. 290 SplitStaticCtorDtor("llvm.global_ctors", M, New); 291 SplitStaticCtorDtor("llvm.global_dtors", M, New); 292 293 return New; 294} 295 296//===----------------------------------------------------------------------===// 297// Basic Block Extraction Code 298//===----------------------------------------------------------------------===// 299 300namespace { 301 std::vector<BasicBlock*> BlocksToNotExtract; 302 303 /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 304 /// from the module into their own functions except for those specified by the 305 /// BlocksToNotExtract list. 306 class BlockExtractorPass : public ModulePass { 307 bool runOnModule(Module &M); 308 }; 309 RegisterPass<BlockExtractorPass> 310 XX("extract-bbs", "Extract Basic Blocks From Module (for bugpoint use)"); 311} 312 313bool BlockExtractorPass::runOnModule(Module &M) { 314 std::set<BasicBlock*> TranslatedBlocksToNotExtract; 315 for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 316 BasicBlock *BB = BlocksToNotExtract[i]; 317 Function *F = BB->getParent(); 318 319 // Map the corresponding function in this module. 320 Function *MF = M.getFunction(F->getName(), F->getFunctionType()); 321 322 // Figure out which index the basic block is in its function. 323 Function::iterator BBI = MF->begin(); 324 std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 325 TranslatedBlocksToNotExtract.insert(BBI); 326 } 327 328 // Now that we know which blocks to not extract, figure out which ones we WANT 329 // to extract. 330 std::vector<BasicBlock*> BlocksToExtract; 331 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 332 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 333 if (!TranslatedBlocksToNotExtract.count(BB)) 334 BlocksToExtract.push_back(BB); 335 336 for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) 337 ExtractBasicBlock(BlocksToExtract[i]); 338 339 return !BlocksToExtract.empty(); 340} 341 342/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 343/// into their own functions. The only detail is that M is actually a module 344/// cloned from the one the BBs are in, so some mapping needs to be performed. 345/// If this operation fails for some reason (ie the implementation is buggy), 346/// this function should return null, otherwise it returns a new Module. 347Module *BugDriver::ExtractMappedBlocksFromModule(const 348 std::vector<BasicBlock*> &BBs, 349 Module *M) { 350 // Set the global list so that pass will be able to access it. 351 BlocksToNotExtract = BBs; 352 353 std::vector<const PassInfo*> PI; 354 PI.push_back(getPI(new BlockExtractorPass())); 355 Module *Ret = runPassesOn(M, PI); 356 BlocksToNotExtract.clear(); 357 if (Ret == 0) { 358 std::cout << "*** Basic Block extraction failed, please report a bug!\n"; 359 M = swapProgramIn(M); 360 EmitProgressBytecode("basicblockextractfail", true); 361 swapProgramIn(M); 362 } 363 return Ret; 364} 365