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