ExtractFunction.cpp revision e8a469cdb400249ec263c79d1021f953f42f2760
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/Support/raw_ostream.h" 33#include "llvm/System/Path.h" 34#include "llvm/System/Signals.h" 35#include <set> 36using namespace llvm; 37 38namespace llvm { 39 bool DisableSimplifyCFG = false; 40 extern cl::opt<std::string> OutputPrefix; 41} // End llvm namespace 42 43namespace { 44 cl::opt<bool> 45 NoDCE ("disable-dce", 46 cl::desc("Do not use the -dce pass to reduce testcases")); 47 cl::opt<bool, true> 48 NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG), 49 cl::desc("Do not use the -simplifycfg pass to reduce testcases")); 50} 51 52/// deleteInstructionFromProgram - This method clones the current Program and 53/// deletes the specified instruction from the cloned module. It then runs a 54/// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which 55/// depends on the value. The modified module is then returned. 56/// 57Module *BugDriver::deleteInstructionFromProgram(const Instruction *I, 58 unsigned Simplification) const { 59 Module *Result = CloneModule(Program); 60 61 const BasicBlock *PBB = I->getParent(); 62 const Function *PF = PBB->getParent(); 63 64 Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn 65 std::advance(RFI, std::distance(PF->getParent()->begin(), 66 Module::const_iterator(PF))); 67 68 Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 69 std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 70 71 BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 72 std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 73 Instruction *TheInst = RI; // Got the corresponding instruction! 74 75 // If this instruction produces a value, replace any users with null values 76 if (!TheInst->getType()->isVoidTy()) 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 120 if (MayModifySemantics) 121 CleanupPasses.push_back(getPI(createDeadArgHackingPass())); 122 else 123 CleanupPasses.push_back(getPI(createDeadArgEliminationPass())); 124 125 CleanupPasses.push_back(getPI(createDeadTypeEliminationPass())); 126 127 Module *New = runPassesOn(M, CleanupPasses); 128 if (New == 0) { 129 errs() << "Final cleanups failed. Sorry. :( Please report a bug!\n"; 130 return M; 131 } 132 delete M; 133 return New; 134} 135 136 137/// ExtractLoop - Given a module, extract up to one loop from it into a new 138/// function. This returns null if there are no extractable loops in the 139/// program or if the loop extractor crashes. 140Module *BugDriver::ExtractLoop(Module *M) { 141 std::vector<const PassInfo*> LoopExtractPasses; 142 LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass())); 143 144 Module *NewM = runPassesOn(M, LoopExtractPasses); 145 if (NewM == 0) { 146 Module *Old = swapProgramIn(M); 147 outs() << "*** Loop extraction failed: "; 148 EmitProgressBitcode("loopextraction", true); 149 outs() << "*** Sorry. :( Please report a bug!\n"; 150 swapProgramIn(Old); 151 return 0; 152 } 153 154 // Check to see if we created any new functions. If not, no loops were 155 // extracted and we should return null. Limit the number of loops we extract 156 // to avoid taking forever. 157 static unsigned NumExtracted = 32; 158 if (M->size() == NewM->size() || --NumExtracted == 0) { 159 delete NewM; 160 return 0; 161 } else { 162 assert(M->size() < NewM->size() && "Loop extract removed functions?"); 163 Module::iterator MI = NewM->begin(); 164 for (unsigned i = 0, e = M->size(); i != e; ++i) 165 ++MI; 166 } 167 168 return NewM; 169} 170 171 172// DeleteFunctionBody - "Remove" the function by deleting all of its basic 173// blocks, making it external. 174// 175void llvm::DeleteFunctionBody(Function *F) { 176 // delete the body of the function... 177 F->deleteBody(); 178 assert(F->isDeclaration() && "This didn't make the function external!"); 179} 180 181/// GetTorInit - Given a list of entries for static ctors/dtors, return them 182/// as a constant array. 183static Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) { 184 assert(!TorList.empty() && "Don't create empty tor list!"); 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( 189 Type::getInt32Ty(TorList[i].first->getContext()), TorList[i].second)); 190 Elts.push_back(TorList[i].first); 191 ArrayElts.push_back(ConstantStruct::get(TorList[i].first->getContext(), 192 Elts, false)); 193 } 194 return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), 195 ArrayElts.size()), 196 ArrayElts); 197} 198 199/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and 200/// M1 has all of the global variables. If M2 contains any functions that are 201/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and 202/// prune appropriate entries out of M1s list. 203static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, 204 ValueMap<const Value*, Value*> VMap) { 205 GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 206 if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || 207 !GV->use_empty()) return; 208 209 std::vector<std::pair<Function*, int> > M1Tors, M2Tors; 210 ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 211 if (!InitList) return; 212 213 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { 214 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){ 215 if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. 216 217 if (CS->getOperand(1)->isNullValue()) 218 break; // Found a null terminator, stop here. 219 220 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 221 int Priority = CI ? CI->getSExtValue() : 0; 222 223 Constant *FP = CS->getOperand(1); 224 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP)) 225 if (CE->isCast()) 226 FP = CE->getOperand(0); 227 if (Function *F = dyn_cast<Function>(FP)) { 228 if (!F->isDeclaration()) 229 M1Tors.push_back(std::make_pair(F, Priority)); 230 else { 231 // Map to M2's version of the function. 232 F = cast<Function>(VMap[F]); 233 M2Tors.push_back(std::make_pair(F, Priority)); 234 } 235 } 236 } 237 } 238 239 GV->eraseFromParent(); 240 if (!M1Tors.empty()) { 241 Constant *M1Init = GetTorInit(M1Tors); 242 new GlobalVariable(*M1, M1Init->getType(), false, 243 GlobalValue::AppendingLinkage, 244 M1Init, GlobalName); 245 } 246 247 GV = M2->getNamedGlobal(GlobalName); 248 assert(GV && "Not a clone of M1?"); 249 assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 250 251 GV->eraseFromParent(); 252 if (!M2Tors.empty()) { 253 Constant *M2Init = GetTorInit(M2Tors); 254 new GlobalVariable(*M2, M2Init->getType(), false, 255 GlobalValue::AppendingLinkage, 256 M2Init, GlobalName); 257 } 258} 259 260 261/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 262/// module, split the functions OUT of the specified module, and place them in 263/// the new module. 264Module * 265llvm::SplitFunctionsOutOfModule(Module *M, 266 const std::vector<Function*> &F, 267 ValueMap<const Value*, Value*> &VMap) { 268 // Make sure functions & globals are all external so that linkage 269 // between the two modules will work. 270 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 271 I->setLinkage(GlobalValue::ExternalLinkage); 272 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 273 I != E; ++I) { 274 if (I->hasName() && I->getName()[0] == '\01') 275 I->setName(I->getName().substr(1)); 276 I->setLinkage(GlobalValue::ExternalLinkage); 277 } 278 279 ValueMap<const Value*, Value*> NewVMap; 280 Module *New = CloneModule(M, NewVMap); 281 282 // Make sure global initializers exist only in the safe module (CBE->.so) 283 for (Module::global_iterator I = New->global_begin(), E = New->global_end(); 284 I != E; ++I) 285 I->setInitializer(0); // Delete the initializer to make it external 286 287 // Remove the Test functions from the Safe module 288 std::set<Function *> TestFunctions; 289 for (unsigned i = 0, e = F.size(); i != e; ++i) { 290 Function *TNOF = cast<Function>(VMap[F[i]]); 291 DEBUG(errs() << "Removing function "); 292 DEBUG(WriteAsOperand(errs(), TNOF, false)); 293 DEBUG(errs() << "\n"); 294 TestFunctions.insert(cast<Function>(NewVMap[TNOF])); 295 DeleteFunctionBody(TNOF); // Function is now external in this module! 296 } 297 298 299 // Remove the Safe functions from the Test module 300 for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 301 if (!TestFunctions.count(I)) 302 DeleteFunctionBody(I); 303 304 305 // Make sure that there is a global ctor/dtor array in both halves of the 306 // module if they both have static ctor/dtor functions. 307 SplitStaticCtorDtor("llvm.global_ctors", M, New, NewVMap); 308 SplitStaticCtorDtor("llvm.global_dtors", M, New, NewVMap); 309 310 return New; 311} 312 313//===----------------------------------------------------------------------===// 314// Basic Block Extraction Code 315//===----------------------------------------------------------------------===// 316 317/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 318/// into their own functions. The only detail is that M is actually a module 319/// cloned from the one the BBs are in, so some mapping needs to be performed. 320/// If this operation fails for some reason (ie the implementation is buggy), 321/// this function should return null, otherwise it returns a new Module. 322Module *BugDriver::ExtractMappedBlocksFromModule(const 323 std::vector<BasicBlock*> &BBs, 324 Module *M) { 325 sys::Path uniqueFilename(OutputPrefix + "-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(), ErrorInfo); 339 if (!ErrorInfo.empty()) { 340 outs() << "*** Basic Block extraction failed!\n"; 341 errs() << "Error writing list of blocks to not extract: " << ErrorInfo 342 << "\n"; 343 M = swapProgramIn(M); 344 EmitProgressBitcode("basicblockextractfail", true); 345 swapProgramIn(M); 346 return 0; 347 } 348 for (std::vector<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 349 I != E; ++I) { 350 BasicBlock *BB = *I; 351 // If the BB doesn't have a name, give it one so we have something to key 352 // off of. 353 if (!BB->hasName()) BB->setName("tmpbb"); 354 BlocksToNotExtractFile << BB->getParent()->getNameStr() << " " 355 << BB->getName() << "\n"; 356 } 357 BlocksToNotExtractFile.close(); 358 359 std::string uniqueFN = "--extract-blocks-file=" + uniqueFilename.str(); 360 const char *ExtraArg = uniqueFN.c_str(); 361 362 std::vector<const PassInfo*> PI; 363 std::vector<BasicBlock *> EmptyBBs; // This parameter is ignored. 364 PI.push_back(getPI(createBlockExtractorPass(EmptyBBs))); 365 Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg); 366 367 uniqueFilename.eraseFromDisk(); // Free disk space 368 369 if (Ret == 0) { 370 outs() << "*** Basic Block extraction failed, please report a bug!\n"; 371 M = swapProgramIn(M); 372 EmitProgressBitcode("basicblockextractfail", true); 373 swapProgramIn(M); 374 } 375 return Ret; 376} 377