ExtractFunction.cpp revision 203954
1227825Stheraven//===- ExtractFunction.cpp - Extract a function from Program --------------===// 2227825Stheraven// 3227825Stheraven// The LLVM Compiler Infrastructure 4227825Stheraven// 5227825Stheraven// This file is distributed under the University of Illinois Open Source 6227825Stheraven// License. See LICENSE.TXT for details. 7227825Stheraven// 8227825Stheraven//===----------------------------------------------------------------------===// 9227825Stheraven// 10227825Stheraven// This file implements several methods that are used to extract functions, 11227825Stheraven// loops, or portions of a module from the rest of the module. 12227825Stheraven// 13227825Stheraven//===----------------------------------------------------------------------===// 14227825Stheraven 15227825Stheraven#include "BugDriver.h" 16227825Stheraven#include "llvm/Constants.h" 17227825Stheraven#include "llvm/DerivedTypes.h" 18227825Stheraven#include "llvm/LLVMContext.h" 19227825Stheraven#include "llvm/Module.h" 20227825Stheraven#include "llvm/PassManager.h" 21227825Stheraven#include "llvm/Pass.h" 22262801Sdim#include "llvm/Analysis/Verifier.h" 23227825Stheraven#include "llvm/Assembly/Writer.h" 24262801Sdim#include "llvm/Transforms/IPO.h" 25262801Sdim#include "llvm/Transforms/Scalar.h" 26227825Stheraven#include "llvm/Transforms/Utils/Cloning.h" 27227825Stheraven#include "llvm/Transforms/Utils/FunctionUtils.h" 28227825Stheraven#include "llvm/Target/TargetData.h" 29227825Stheraven#include "llvm/Support/CommandLine.h" 30227825Stheraven#include "llvm/Support/Debug.h" 31227825Stheraven#include "llvm/Support/FileUtilities.h" 32227825Stheraven#include "llvm/Support/raw_ostream.h" 33227825Stheraven#include "llvm/System/Path.h" 34227825Stheraven#include "llvm/System/Signals.h" 35227825Stheraven#include <set> 36227825Stheravenusing namespace llvm; 37227825Stheraven 38227825Stheravennamespace llvm { 39227825Stheraven bool DisableSimplifyCFG = false; 40227825Stheraven extern cl::opt<std::string> OutputPrefix; 41227825Stheraven} // End llvm namespace 42227825Stheraven 43241903Sdimnamespace { 44241903Sdim cl::opt<bool> 45227825Stheraven NoDCE ("disable-dce", 46241903Sdim cl::desc("Do not use the -dce pass to reduce testcases")); 47227825Stheraven cl::opt<bool, true> 48227825Stheraven NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG), 49227825Stheraven cl::desc("Do not use the -simplifycfg pass to reduce testcases")); 50227825Stheraven} 51227825Stheraven 52227825Stheraven/// deleteInstructionFromProgram - This method clones the current Program and 53227825Stheraven/// deletes the specified instruction from the cloned module. It then runs a 54241903Sdim/// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which 55241903Sdim/// depends on the value. The modified module is then returned. 56227825Stheraven/// 57227825StheravenModule *BugDriver::deleteInstructionFromProgram(const Instruction *I, 58227825Stheraven unsigned Simplification) const { 59227825Stheraven Module *Result = CloneModule(Program); 60227825Stheraven 61227825Stheraven const BasicBlock *PBB = I->getParent(); 62227825Stheraven const Function *PF = PBB->getParent(); 63227825Stheraven 64227825Stheraven Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn 65241903Sdim std::advance(RFI, std::distance(PF->getParent()->begin(), 66227825Stheraven Module::const_iterator(PF))); 67227825Stheraven 68227825Stheraven Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 69227825Stheraven std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 70241903Sdim 71227825Stheraven BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 72241903Sdim std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 73227825Stheraven Instruction *TheInst = RI; // Got the corresponding instruction! 74227825Stheraven 75227825Stheraven // If this instruction produces a value, replace any users with null values 76227825Stheraven if (isa<StructType>(TheInst->getType())) 77227825Stheraven TheInst->replaceAllUsesWith(UndefValue::get(TheInst->getType())); 78227825Stheraven else if (TheInst->getType() != Type::getVoidTy(I->getContext())) 79227825Stheraven TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); 80227825Stheraven 81227825Stheraven // Remove the instruction from the program. 82227825Stheraven TheInst->getParent()->getInstList().erase(TheInst); 83227825Stheraven 84227825Stheraven 85227825Stheraven //writeProgramToFile("current.bc", Result); 86227825Stheraven 87227825Stheraven // Spiff up the output a little bit. 88227825Stheraven PassManager Passes; 89227825Stheraven // Make sure that the appropriate target data is always used... 90227825Stheraven Passes.add(new TargetData(Result)); 91227825Stheraven 92227825Stheraven /// FIXME: If this used runPasses() like the methods below, we could get rid 93227825Stheraven /// of the -disable-* options! 94227825Stheraven if (Simplification > 1 && !NoDCE) 95241903Sdim Passes.add(createDeadCodeEliminationPass()); 96227825Stheraven if (Simplification && !DisableSimplifyCFG) 97227825Stheraven Passes.add(createCFGSimplificationPass()); // Delete dead control flow 98227825Stheraven 99227825Stheraven Passes.add(createVerifierPass()); 100241903Sdim Passes.run(*Result); 101227825Stheraven return Result; 102241903Sdim} 103227825Stheraven 104227825Stheravenstatic const PassInfo *getPI(Pass *P) { 105227825Stheraven const PassInfo *PI = P->getPassInfo(); 106227825Stheraven delete P; 107227825Stheraven return PI; 108227825Stheraven} 109227825Stheraven 110227825Stheraven/// performFinalCleanups - This method clones the current Program and performs 111227825Stheraven/// a series of cleanups intended to get rid of extra cruft on the module 112227825Stheraven/// before handing it to the user. 113227825Stheraven/// 114227825StheravenModule *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { 115227825Stheraven // Make all functions external, so GlobalDCE doesn't delete them... 116227825Stheraven for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 117227825Stheraven I->setLinkage(GlobalValue::ExternalLinkage); 118227825Stheraven 119227825Stheraven std::vector<const PassInfo*> CleanupPasses; 120227825Stheraven CleanupPasses.push_back(getPI(createGlobalDCEPass())); 121227825Stheraven CleanupPasses.push_back(getPI(createDeadTypeEliminationPass())); 122227825Stheraven 123241903Sdim if (MayModifySemantics) 124227825Stheraven CleanupPasses.push_back(getPI(createDeadArgHackingPass())); 125227825Stheraven else 126227825Stheraven CleanupPasses.push_back(getPI(createDeadArgEliminationPass())); 127227825Stheraven 128241903Sdim Module *New = runPassesOn(M, CleanupPasses); 129227825Stheraven if (New == 0) { 130241903Sdim errs() << "Final cleanups failed. Sorry. :( Please report a bug!\n"; 131227825Stheraven return M; 132227825Stheraven } 133227825Stheraven delete M; 134227825Stheraven return New; 135227825Stheraven} 136227825Stheraven 137227825Stheraven 138227825Stheraven/// ExtractLoop - Given a module, extract up to one loop from it into a new 139227825Stheraven/// function. This returns null if there are no extractable loops in the 140227825Stheraven/// program or if the loop extractor crashes. 141227825StheravenModule *BugDriver::ExtractLoop(Module *M) { 142227825Stheraven std::vector<const PassInfo*> LoopExtractPasses; 143227825Stheraven LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass())); 144241903Sdim 145227825Stheraven Module *NewM = runPassesOn(M, LoopExtractPasses); 146227825Stheraven if (NewM == 0) { 147227825Stheraven Module *Old = swapProgramIn(M); 148227825Stheraven outs() << "*** Loop extraction failed: "; 149227825Stheraven EmitProgressBitcode("loopextraction", true); 150227825Stheraven outs() << "*** Sorry. :( Please report a bug!\n"; 151227825Stheraven swapProgramIn(Old); 152227825Stheraven return 0; 153241903Sdim } 154241903Sdim 155227825Stheraven // Check to see if we created any new functions. If not, no loops were 156227825Stheraven // extracted and we should return null. Limit the number of loops we extract 157227825Stheraven // to avoid taking forever. 158241903Sdim static unsigned NumExtracted = 32; 159241903Sdim if (M->size() == NewM->size() || --NumExtracted == 0) { 160227825Stheraven delete NewM; 161227825Stheraven return 0; 162227825Stheraven } else { 163227825Stheraven assert(M->size() < NewM->size() && "Loop extract removed functions?"); 164227825Stheraven Module::iterator MI = NewM->begin(); 165241903Sdim for (unsigned i = 0, e = M->size(); i != e; ++i) 166227825Stheraven ++MI; 167227825Stheraven } 168227825Stheraven 169227825Stheraven return NewM; 170227825Stheraven} 171227825Stheraven 172227825Stheraven 173227825Stheraven// DeleteFunctionBody - "Remove" the function by deleting all of its basic 174227825Stheraven// blocks, making it external. 175227825Stheraven// 176227825Stheravenvoid llvm::DeleteFunctionBody(Function *F) { 177227825Stheraven // delete the body of the function... 178227825Stheraven F->deleteBody(); 179227825Stheraven assert(F->isDeclaration() && "This didn't make the function external!"); 180241903Sdim} 181241903Sdim 182227825Stheraven/// GetTorInit - Given a list of entries for static ctors/dtors, return them 183227825Stheraven/// as a constant array. 184227825Stheravenstatic Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) { 185241903Sdim assert(!TorList.empty() && "Don't create empty tor list!"); 186241903Sdim std::vector<Constant*> ArrayElts; 187227825Stheraven for (unsigned i = 0, e = TorList.size(); i != e; ++i) { 188227825Stheraven std::vector<Constant*> Elts; 189227825Stheraven Elts.push_back(ConstantInt::get( 190227825Stheraven Type::getInt32Ty(TorList[i].first->getContext()), TorList[i].second)); 191227825Stheraven Elts.push_back(TorList[i].first); 192241903Sdim ArrayElts.push_back(ConstantStruct::get(TorList[i].first->getContext(), 193227825Stheraven Elts, false)); 194227825Stheraven } 195227825Stheraven return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), 196227825Stheraven ArrayElts.size()), 197227825Stheraven ArrayElts); 198227825Stheraven} 199227825Stheraven 200227825Stheraven/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and 201227825Stheraven/// M1 has all of the global variables. If M2 contains any functions that are 202227825Stheraven/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and 203227825Stheraven/// prune appropriate entries out of M1s list. 204227825Stheravenstatic void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, 205227825Stheraven DenseMap<const Value*, Value*> ValueMap) { 206227825Stheraven GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 207241903Sdim if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || 208241903Sdim !GV->use_empty()) return; 209227825Stheraven 210227825Stheraven std::vector<std::pair<Function*, int> > M1Tors, M2Tors; 211227825Stheraven ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 212241903Sdim if (!InitList) return; 213241903Sdim 214227825Stheraven for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { 215227825Stheraven if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){ 216227825Stheraven if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. 217227825Stheraven 218227825Stheraven if (CS->getOperand(1)->isNullValue()) 219241903Sdim break; // Found a null terminator, stop here. 220227825Stheraven 221227825Stheraven ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 222227825Stheraven int Priority = CI ? CI->getSExtValue() : 0; 223227825Stheraven 224227825Stheraven Constant *FP = CS->getOperand(1); 225227825Stheraven if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP)) 226227825Stheraven if (CE->isCast()) 227227825Stheraven FP = CE->getOperand(0); 228227825Stheraven if (Function *F = dyn_cast<Function>(FP)) { 229227825Stheraven if (!F->isDeclaration()) 230227825Stheraven M1Tors.push_back(std::make_pair(F, Priority)); 231227825Stheraven else { 232227825Stheraven // Map to M2's version of the function. 233227825Stheraven F = cast<Function>(ValueMap[F]); 234241903Sdim M2Tors.push_back(std::make_pair(F, Priority)); 235227825Stheraven } 236241903Sdim } 237241903Sdim } 238227825Stheraven } 239227825Stheraven 240241903Sdim GV->eraseFromParent(); 241227825Stheraven if (!M1Tors.empty()) { 242227825Stheraven Constant *M1Init = GetTorInit(M1Tors); 243227825Stheraven new GlobalVariable(*M1, M1Init->getType(), false, 244227825Stheraven GlobalValue::AppendingLinkage, 245227825Stheraven M1Init, GlobalName); 246241903Sdim } 247227825Stheraven 248227825Stheraven GV = M2->getNamedGlobal(GlobalName); 249227825Stheraven assert(GV && "Not a clone of M1?"); 250227825Stheraven assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 251227825Stheraven 252227825Stheraven GV->eraseFromParent(); 253227825Stheraven if (!M2Tors.empty()) { 254227825Stheraven Constant *M2Init = GetTorInit(M2Tors); 255227825Stheraven new GlobalVariable(*M2, M2Init->getType(), false, 256227825Stheraven GlobalValue::AppendingLinkage, 257227825Stheraven M2Init, GlobalName); 258227825Stheraven } 259227825Stheraven} 260227825Stheraven 261241903Sdim 262227825Stheraven/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 263241903Sdim/// module, split the functions OUT of the specified module, and place them in 264241903Sdim/// the new module. 265227825StheravenModule * 266227825Stheravenllvm::SplitFunctionsOutOfModule(Module *M, 267241903Sdim const std::vector<Function*> &F, 268227825Stheraven DenseMap<const Value*, Value*> &ValueMap) { 269227825Stheraven // Make sure functions & globals are all external so that linkage 270227825Stheraven // between the two modules will work. 271227825Stheraven for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 272227825Stheraven I->setLinkage(GlobalValue::ExternalLinkage); 273241903Sdim for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 274227825Stheraven I != E; ++I) { 275227825Stheraven if (I->hasName() && I->getName()[0] == '\01') 276227825Stheraven I->setName(I->getName().substr(1)); 277227825Stheraven I->setLinkage(GlobalValue::ExternalLinkage); 278227825Stheraven } 279227825Stheraven 280227825Stheraven DenseMap<const Value*, Value*> NewValueMap; 281227825Stheraven Module *New = CloneModule(M, NewValueMap); 282227825Stheraven 283227825Stheraven // Make sure global initializers exist only in the safe module (CBE->.so) 284227825Stheraven for (Module::global_iterator I = New->global_begin(), E = New->global_end(); 285227825Stheraven I != E; ++I) 286227825Stheraven I->setInitializer(0); // Delete the initializer to make it external 287227825Stheraven 288241903Sdim // Remove the Test functions from the Safe module 289227825Stheraven std::set<Function *> TestFunctions; 290241903Sdim for (unsigned i = 0, e = F.size(); i != e; ++i) { 291241903Sdim Function *TNOF = cast<Function>(ValueMap[F[i]]); 292227825Stheraven DEBUG(errs() << "Removing function "); 293227825Stheraven DEBUG(WriteAsOperand(errs(), TNOF, false)); 294241903Sdim DEBUG(errs() << "\n"); 295227825Stheraven TestFunctions.insert(cast<Function>(NewValueMap[TNOF])); 296227825Stheraven DeleteFunctionBody(TNOF); // Function is now external in this module! 297227825Stheraven } 298227825Stheraven 299227825Stheraven 300241903Sdim // Remove the Safe functions from the Test module 301227825Stheraven for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 302227825Stheraven if (!TestFunctions.count(I)) 303227825Stheraven DeleteFunctionBody(I); 304227825Stheraven 305227825Stheraven 306227825Stheraven // Make sure that there is a global ctor/dtor array in both halves of the 307227825Stheraven // module if they both have static ctor/dtor functions. 308227825Stheraven SplitStaticCtorDtor("llvm.global_ctors", M, New, NewValueMap); 309227825Stheraven SplitStaticCtorDtor("llvm.global_dtors", M, New, NewValueMap); 310227825Stheraven 311227825Stheraven return New; 312262801Sdim} 313227825Stheraven 314227825Stheraven//===----------------------------------------------------------------------===// 315227825Stheraven// Basic Block Extraction Code 316262801Sdim//===----------------------------------------------------------------------===// 317227825Stheraven 318227825Stheraven/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 319227825Stheraven/// into their own functions. The only detail is that M is actually a module 320227825Stheraven/// cloned from the one the BBs are in, so some mapping needs to be performed. 321227825Stheraven/// If this operation fails for some reason (ie the implementation is buggy), 322227825Stheraven/// this function should return null, otherwise it returns a new Module. 323227825StheravenModule *BugDriver::ExtractMappedBlocksFromModule(const 324227825Stheraven std::vector<BasicBlock*> &BBs, 325227825Stheraven Module *M) { 326227825Stheraven sys::Path uniqueFilename(OutputPrefix + "-extractblocks"); 327227825Stheraven std::string ErrMsg; 328241903Sdim if (uniqueFilename.createTemporaryFileOnDisk(true, &ErrMsg)) { 329227825Stheraven outs() << "*** Basic Block extraction failed!\n"; 330227825Stheraven errs() << "Error creating temporary file: " << ErrMsg << "\n"; 331227825Stheraven M = swapProgramIn(M); 332227825Stheraven EmitProgressBitcode("basicblockextractfail", true); 333227825Stheraven swapProgramIn(M); 334227825Stheraven return 0; 335227825Stheraven } 336241903Sdim sys::RemoveFileOnSignal(uniqueFilename); 337241903Sdim 338227825Stheraven std::string ErrorInfo; 339227825Stheraven raw_fd_ostream BlocksToNotExtractFile(uniqueFilename.c_str(), ErrorInfo); 340241903Sdim if (!ErrorInfo.empty()) { 341241903Sdim outs() << "*** Basic Block extraction failed!\n"; 342241903Sdim errs() << "Error writing list of blocks to not extract: " << ErrorInfo 343227825Stheraven << "\n"; 344241903Sdim M = swapProgramIn(M); 345227825Stheraven EmitProgressBitcode("basicblockextractfail", true); 346227825Stheraven swapProgramIn(M); 347227825Stheraven return 0; 348227825Stheraven } 349227825Stheraven for (std::vector<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 350227825Stheraven I != E; ++I) { 351227825Stheraven BasicBlock *BB = *I; 352227825Stheraven // If the BB doesn't have a name, give it one so we have something to key 353227825Stheraven // off of. 354227825Stheraven if (!BB->hasName()) BB->setName("tmpbb"); 355227825Stheraven BlocksToNotExtractFile << BB->getParent()->getNameStr() << " " 356227825Stheraven << BB->getName() << "\n"; 357241903Sdim } 358227825Stheraven BlocksToNotExtractFile.close(); 359227825Stheraven 360227825Stheraven std::string uniqueFN = "--extract-blocks-file=" + uniqueFilename.str(); 361227825Stheraven const char *ExtraArg = uniqueFN.c_str(); 362227825Stheraven 363227825Stheraven std::vector<const PassInfo*> PI; 364227825Stheraven std::vector<BasicBlock *> EmptyBBs; // This parameter is ignored. 365227825Stheraven PI.push_back(getPI(createBlockExtractorPass(EmptyBBs))); 366227825Stheraven Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg); 367227825Stheraven 368227825Stheraven if (uniqueFilename.exists()) 369227825Stheraven uniqueFilename.eraseFromDisk(); // Free disk space 370227825Stheraven 371227825Stheraven if (Ret == 0) { 372227825Stheraven outs() << "*** Basic Block extraction failed, please report a bug!\n"; 373227825Stheraven M = swapProgramIn(M); 374227825Stheraven EmitProgressBitcode("basicblockextractfail", true); 375227825Stheraven swapProgramIn(M); 376227825Stheraven } 377278724Sdim return Ret; 378278724Sdim} 379278724Sdim