ExtractFunction.cpp revision 193323
1234285Sdim//===- ExtractFunction.cpp - Extract a function from Program --------------===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file implements several methods that are used to extract functions, 11234285Sdim// loops, or portions of a module from the rest of the module. 12234285Sdim// 13234285Sdim//===----------------------------------------------------------------------===// 14234285Sdim 15234285Sdim#include "BugDriver.h" 16234285Sdim#include "llvm/Constants.h" 17234285Sdim#include "llvm/DerivedTypes.h" 18263508Sdim#include "llvm/Module.h" 19263508Sdim#include "llvm/PassManager.h" 20263508Sdim#include "llvm/Pass.h" 21263508Sdim#include "llvm/Analysis/Verifier.h" 22234285Sdim#include "llvm/Transforms/IPO.h" 23234285Sdim#include "llvm/Transforms/Scalar.h" 24234285Sdim#include "llvm/Transforms/Utils/Cloning.h" 25234285Sdim#include "llvm/Transforms/Utils/FunctionUtils.h" 26234285Sdim#include "llvm/Target/TargetData.h" 27234285Sdim#include "llvm/Support/CommandLine.h" 28234285Sdim#include "llvm/Support/Debug.h" 29234285Sdim#include "llvm/Support/FileUtilities.h" 30243830Sdim#include "llvm/System/Path.h" 31234285Sdim#include "llvm/System/Signals.h" 32234285Sdim#include <set> 33234285Sdim#include <fstream> 34234285Sdim#include <iostream> 35234285Sdimusing namespace llvm; 36249423Sdim 37234285Sdimnamespace llvm { 38234285Sdim bool DisableSimplifyCFG = false; 39234285Sdim} // 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(UndefValue::get(TheInst->getType())); 76 else if (TheInst->getType() != Type::VoidTy) 77 TheInst->replaceAllUsesWith(Constant::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 std::cerr << "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 std::cout << "*** Loop extraction failed: "; 147 EmitProgressBitcode("loopextraction", true); 148 std::cout << "*** 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 std::vector<Constant*> ArrayElts; 185 for (unsigned i = 0, e = TorList.size(); i != e; ++i) { 186 std::vector<Constant*> Elts; 187 Elts.push_back(ConstantInt::get(Type::Int32Ty, TorList[i].second)); 188 Elts.push_back(TorList[i].first); 189 ArrayElts.push_back(ConstantStruct::get(Elts)); 190 } 191 return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), 192 ArrayElts.size()), 193 ArrayElts); 194} 195 196/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and 197/// M1 has all of the global variables. If M2 contains any functions that are 198/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and 199/// prune appropriate entries out of M1s list. 200static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, 201 DenseMap<const Value*, Value*> ValueMap) { 202 GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 203 if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || 204 !GV->use_empty()) return; 205 206 std::vector<std::pair<Function*, int> > M1Tors, M2Tors; 207 ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 208 if (!InitList) return; 209 210 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { 211 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){ 212 if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. 213 214 if (CS->getOperand(1)->isNullValue()) 215 break; // Found a null terminator, stop here. 216 217 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 218 int Priority = CI ? CI->getSExtValue() : 0; 219 220 Constant *FP = CS->getOperand(1); 221 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP)) 222 if (CE->isCast()) 223 FP = CE->getOperand(0); 224 if (Function *F = dyn_cast<Function>(FP)) { 225 if (!F->isDeclaration()) 226 M1Tors.push_back(std::make_pair(F, Priority)); 227 else { 228 // Map to M2's version of the function. 229 F = cast<Function>(ValueMap[F]); 230 M2Tors.push_back(std::make_pair(F, Priority)); 231 } 232 } 233 } 234 } 235 236 GV->eraseFromParent(); 237 if (!M1Tors.empty()) { 238 Constant *M1Init = GetTorInit(M1Tors); 239 new GlobalVariable(M1Init->getType(), false, GlobalValue::AppendingLinkage, 240 M1Init, GlobalName, M1); 241 } 242 243 GV = M2->getNamedGlobal(GlobalName); 244 assert(GV && "Not a clone of M1?"); 245 assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 246 247 GV->eraseFromParent(); 248 if (!M2Tors.empty()) { 249 Constant *M2Init = GetTorInit(M2Tors); 250 new GlobalVariable(M2Init->getType(), false, GlobalValue::AppendingLinkage, 251 M2Init, GlobalName, M2); 252 } 253} 254 255 256/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 257/// module, split the functions OUT of the specified module, and place them in 258/// the new module. 259Module * 260llvm::SplitFunctionsOutOfModule(Module *M, 261 const std::vector<Function*> &F, 262 DenseMap<const Value*, Value*> &ValueMap) { 263 // Make sure functions & globals are all external so that linkage 264 // between the two modules will work. 265 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 266 I->setLinkage(GlobalValue::ExternalLinkage); 267 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 268 I != E; ++I) { 269 if (I->hasName() && *I->getNameStart() == '\01') 270 I->setName(I->getNameStart()+1, I->getNameLen()-1); 271 I->setLinkage(GlobalValue::ExternalLinkage); 272 } 273 274 DenseMap<const Value*, Value*> NewValueMap; 275 Module *New = CloneModule(M, NewValueMap); 276 277 // Make sure global initializers exist only in the safe module (CBE->.so) 278 for (Module::global_iterator I = New->global_begin(), E = New->global_end(); 279 I != E; ++I) 280 I->setInitializer(0); // Delete the initializer to make it external 281 282 // Remove the Test functions from the Safe module 283 std::set<Function *> TestFunctions; 284 for (unsigned i = 0, e = F.size(); i != e; ++i) { 285 Function *TNOF = cast<Function>(ValueMap[F[i]]); 286 DEBUG(std::cerr << "Removing function "); 287 DEBUG(WriteAsOperand(std::cerr, TNOF, false)); 288 DEBUG(std::cerr << "\n"); 289 TestFunctions.insert(cast<Function>(NewValueMap[TNOF])); 290 DeleteFunctionBody(TNOF); // Function is now external in this module! 291 } 292 293 294 // Remove the Safe functions from the Test module 295 for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 296 if (!TestFunctions.count(I)) 297 DeleteFunctionBody(I); 298 299 300 // Make sure that there is a global ctor/dtor array in both halves of the 301 // module if they both have static ctor/dtor functions. 302 SplitStaticCtorDtor("llvm.global_ctors", M, New, NewValueMap); 303 SplitStaticCtorDtor("llvm.global_dtors", M, New, NewValueMap); 304 305 return New; 306} 307 308//===----------------------------------------------------------------------===// 309// Basic Block Extraction Code 310//===----------------------------------------------------------------------===// 311 312/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 313/// into their own functions. The only detail is that M is actually a module 314/// cloned from the one the BBs are in, so some mapping needs to be performed. 315/// If this operation fails for some reason (ie the implementation is buggy), 316/// this function should return null, otherwise it returns a new Module. 317Module *BugDriver::ExtractMappedBlocksFromModule(const 318 std::vector<BasicBlock*> &BBs, 319 Module *M) { 320 char *ExtraArg = NULL; 321 322 sys::Path uniqueFilename("bugpoint-extractblocks"); 323 std::string ErrMsg; 324 if (uniqueFilename.createTemporaryFileOnDisk(true, &ErrMsg)) { 325 std::cout << "*** Basic Block extraction failed!\n"; 326 std::cerr << "Error creating temporary file: " << ErrMsg << "\n"; 327 M = swapProgramIn(M); 328 EmitProgressBitcode("basicblockextractfail", true); 329 swapProgramIn(M); 330 return 0; 331 } 332 sys::RemoveFileOnSignal(uniqueFilename); 333 334 std::ofstream BlocksToNotExtractFile(uniqueFilename.c_str()); 335 if (!BlocksToNotExtractFile) { 336 std::cout << "*** Basic Block extraction failed!\n"; 337 std::cerr << "Error writing list of blocks to not extract: " << ErrMsg 338 << "\n"; 339 M = swapProgramIn(M); 340 EmitProgressBitcode("basicblockextractfail", true); 341 swapProgramIn(M); 342 return 0; 343 } 344 for (std::vector<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 345 I != E; ++I) { 346 BasicBlock *BB = *I; 347 // If the BB doesn't have a name, give it one so we have something to key 348 // off of. 349 if (!BB->hasName()) BB->setName("tmpbb"); 350 BlocksToNotExtractFile << BB->getParent()->getName() << " " 351 << BB->getName() << "\n"; 352 } 353 BlocksToNotExtractFile.close(); 354 355 const char *uniqueFN = uniqueFilename.c_str(); 356 ExtraArg = (char*)malloc(23 + strlen(uniqueFN)); 357 strcat(strcpy(ExtraArg, "--extract-blocks-file="), uniqueFN); 358 359 std::vector<const PassInfo*> PI; 360 std::vector<BasicBlock *> EmptyBBs; // This parameter is ignored. 361 PI.push_back(getPI(createBlockExtractorPass(EmptyBBs))); 362 Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg); 363 364 if (uniqueFilename.exists()) 365 uniqueFilename.eraseFromDisk(); // Free disk space 366 free(ExtraArg); 367 368 if (Ret == 0) { 369 std::cout << "*** Basic Block extraction failed, please report a bug!\n"; 370 M = swapProgramIn(M); 371 EmitProgressBitcode("basicblockextractfail", true); 372 swapProgramIn(M); 373 } 374 return Ret; 375} 376