ExtractFunction.cpp revision 212793
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) { 59 // FIXME, use vmap? 60 Module *Clone = CloneModule(Program); 61 62 const BasicBlock *PBB = I->getParent(); 63 const Function *PF = PBB->getParent(); 64 65 Module::iterator RFI = Clone->begin(); // Get iterator to corresponding fn 66 std::advance(RFI, std::distance(PF->getParent()->begin(), 67 Module::const_iterator(PF))); 68 69 Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 70 std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 71 72 BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 73 std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 74 Instruction *TheInst = RI; // Got the corresponding instruction! 75 76 // If this instruction produces a value, replace any users with null values 77 if (!TheInst->getType()->isVoidTy()) 78 TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); 79 80 // Remove the instruction from the program. 81 TheInst->getParent()->getInstList().erase(TheInst); 82 83 // Spiff up the output a little bit. 84 std::vector<std::string> Passes; 85 86 /// Can we get rid of the -disable-* options? 87 if (Simplification > 1 && !NoDCE) 88 Passes.push_back("dce"); 89 if (Simplification && !DisableSimplifyCFG) 90 Passes.push_back("simplifycfg"); // Delete dead control flow 91 92 Passes.push_back("verify"); 93 Module *New = runPassesOn(Clone, Passes); 94 delete Clone; 95 if (!New) { 96 errs() << "Instruction removal failed. Sorry. :( Please report a bug!\n"; 97 exit(1); 98 } 99 return New; 100} 101 102/// performFinalCleanups - This method clones the current Program and performs 103/// a series of cleanups intended to get rid of extra cruft on the module 104/// before handing it to the user. 105/// 106Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { 107 // Make all functions external, so GlobalDCE doesn't delete them... 108 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 109 I->setLinkage(GlobalValue::ExternalLinkage); 110 111 std::vector<std::string> CleanupPasses; 112 CleanupPasses.push_back("globaldce"); 113 114 if (MayModifySemantics) 115 CleanupPasses.push_back("deadarghaX0r"); 116 else 117 CleanupPasses.push_back("deadargelim"); 118 119 CleanupPasses.push_back("deadtypeelim"); 120 121 Module *New = runPassesOn(M, CleanupPasses); 122 if (New == 0) { 123 errs() << "Final cleanups failed. Sorry. :( Please report a bug!\n"; 124 return M; 125 } 126 delete M; 127 return New; 128} 129 130 131/// ExtractLoop - Given a module, extract up to one loop from it into a new 132/// function. This returns null if there are no extractable loops in the 133/// program or if the loop extractor crashes. 134Module *BugDriver::ExtractLoop(Module *M) { 135 std::vector<std::string> LoopExtractPasses; 136 LoopExtractPasses.push_back("loop-extract-single"); 137 138 Module *NewM = runPassesOn(M, LoopExtractPasses); 139 if (NewM == 0) { 140 outs() << "*** Loop extraction failed: "; 141 EmitProgressBitcode(M, "loopextraction", true); 142 outs() << "*** Sorry. :( Please report a bug!\n"; 143 return 0; 144 } 145 146 // Check to see if we created any new functions. If not, no loops were 147 // extracted and we should return null. Limit the number of loops we extract 148 // to avoid taking forever. 149 static unsigned NumExtracted = 32; 150 if (M->size() == NewM->size() || --NumExtracted == 0) { 151 delete NewM; 152 return 0; 153 } else { 154 assert(M->size() < NewM->size() && "Loop extract removed functions?"); 155 Module::iterator MI = NewM->begin(); 156 for (unsigned i = 0, e = M->size(); i != e; ++i) 157 ++MI; 158 } 159 160 return NewM; 161} 162 163 164// DeleteFunctionBody - "Remove" the function by deleting all of its basic 165// blocks, making it external. 166// 167void llvm::DeleteFunctionBody(Function *F) { 168 // delete the body of the function... 169 F->deleteBody(); 170 assert(F->isDeclaration() && "This didn't make the function external!"); 171} 172 173/// GetTorInit - Given a list of entries for static ctors/dtors, return them 174/// as a constant array. 175static Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) { 176 assert(!TorList.empty() && "Don't create empty tor list!"); 177 std::vector<Constant*> ArrayElts; 178 for (unsigned i = 0, e = TorList.size(); i != e; ++i) { 179 std::vector<Constant*> Elts; 180 Elts.push_back(ConstantInt::get( 181 Type::getInt32Ty(TorList[i].first->getContext()), TorList[i].second)); 182 Elts.push_back(TorList[i].first); 183 ArrayElts.push_back(ConstantStruct::get(TorList[i].first->getContext(), 184 Elts, false)); 185 } 186 return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), 187 ArrayElts.size()), 188 ArrayElts); 189} 190 191/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and 192/// M1 has all of the global variables. If M2 contains any functions that are 193/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and 194/// prune appropriate entries out of M1s list. 195static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, 196 ValueMap<const Value*, Value*> &VMap) { 197 GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 198 if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || 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 = cast<Function>(VMap[F]); 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(*M1, M1Init->getType(), false, 235 GlobalValue::AppendingLinkage, 236 M1Init, GlobalName); 237 } 238 239 GV = M2->getNamedGlobal(GlobalName); 240 assert(GV && "Not a clone of M1?"); 241 assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 242 243 GV->eraseFromParent(); 244 if (!M2Tors.empty()) { 245 Constant *M2Init = GetTorInit(M2Tors); 246 new GlobalVariable(*M2, M2Init->getType(), false, 247 GlobalValue::AppendingLinkage, 248 M2Init, GlobalName); 249 } 250} 251 252 253/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 254/// module, split the functions OUT of the specified module, and place them in 255/// the new module. 256Module * 257llvm::SplitFunctionsOutOfModule(Module *M, 258 const std::vector<Function*> &F, 259 ValueMap<const Value*, Value*> &VMap) { 260 // Make sure functions & globals are all external so that linkage 261 // between the two modules will work. 262 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 263 I->setLinkage(GlobalValue::ExternalLinkage); 264 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 265 I != E; ++I) { 266 if (I->hasName() && I->getName()[0] == '\01') 267 I->setName(I->getName().substr(1)); 268 I->setLinkage(GlobalValue::ExternalLinkage); 269 } 270 271 ValueMap<const Value*, Value*> NewVMap; 272 Module *New = CloneModule(M, NewVMap); 273 274 // Make sure global initializers exist only in the safe module (CBE->.so) 275 for (Module::global_iterator I = New->global_begin(), E = New->global_end(); 276 I != E; ++I) 277 I->setInitializer(0); // Delete the initializer to make it external 278 279 // Remove the Test functions from the Safe module 280 std::set<Function *> TestFunctions; 281 for (unsigned i = 0, e = F.size(); i != e; ++i) { 282 Function *TNOF = cast<Function>(VMap[F[i]]); 283 DEBUG(errs() << "Removing function "); 284 DEBUG(WriteAsOperand(errs(), TNOF, false)); 285 DEBUG(errs() << "\n"); 286 TestFunctions.insert(cast<Function>(NewVMap[TNOF])); 287 DeleteFunctionBody(TNOF); // Function is now external in this module! 288 } 289 290 291 // Remove the Safe functions from the Test module 292 for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 293 if (!TestFunctions.count(I)) 294 DeleteFunctionBody(I); 295 296 297 // Make sure that there is a global ctor/dtor array in both halves of the 298 // module if they both have static ctor/dtor functions. 299 SplitStaticCtorDtor("llvm.global_ctors", M, New, NewVMap); 300 SplitStaticCtorDtor("llvm.global_dtors", M, New, NewVMap); 301 302 return New; 303} 304 305//===----------------------------------------------------------------------===// 306// Basic Block Extraction Code 307//===----------------------------------------------------------------------===// 308 309/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 310/// into their own functions. The only detail is that M is actually a module 311/// cloned from the one the BBs are in, so some mapping needs to be performed. 312/// If this operation fails for some reason (ie the implementation is buggy), 313/// this function should return null, otherwise it returns a new Module. 314Module *BugDriver::ExtractMappedBlocksFromModule(const 315 std::vector<BasicBlock*> &BBs, 316 Module *M) { 317 sys::Path uniqueFilename(OutputPrefix + "-extractblocks"); 318 std::string ErrMsg; 319 if (uniqueFilename.createTemporaryFileOnDisk(true, &ErrMsg)) { 320 outs() << "*** Basic Block extraction failed!\n"; 321 errs() << "Error creating temporary file: " << ErrMsg << "\n"; 322 EmitProgressBitcode(M, "basicblockextractfail", true); 323 return 0; 324 } 325 sys::RemoveFileOnSignal(uniqueFilename); 326 327 std::string ErrorInfo; 328 tool_output_file BlocksToNotExtractFile(uniqueFilename.c_str(), ErrorInfo); 329 if (!ErrorInfo.empty()) { 330 outs() << "*** Basic Block extraction failed!\n"; 331 errs() << "Error writing list of blocks to not extract: " << ErrorInfo 332 << "\n"; 333 EmitProgressBitcode(M, "basicblockextractfail", true); 334 return 0; 335 } 336 for (std::vector<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 337 I != E; ++I) { 338 BasicBlock *BB = *I; 339 // If the BB doesn't have a name, give it one so we have something to key 340 // off of. 341 if (!BB->hasName()) BB->setName("tmpbb"); 342 BlocksToNotExtractFile.os() << BB->getParent()->getNameStr() << " " 343 << BB->getName() << "\n"; 344 } 345 BlocksToNotExtractFile.os().close(); 346 if (BlocksToNotExtractFile.os().has_error()) { 347 errs() << "Error writing list of blocks to not extract: " << ErrorInfo 348 << "\n"; 349 EmitProgressBitcode(M, "basicblockextractfail", true); 350 BlocksToNotExtractFile.os().clear_error(); 351 return 0; 352 } 353 BlocksToNotExtractFile.keep(); 354 355 std::string uniqueFN = "--extract-blocks-file=" + uniqueFilename.str(); 356 const char *ExtraArg = uniqueFN.c_str(); 357 358 std::vector<std::string> PI; 359 PI.push_back("extract-blocks"); 360 Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg); 361 362 uniqueFilename.eraseFromDisk(); // Free disk space 363 364 if (Ret == 0) { 365 outs() << "*** Basic Block extraction failed, please report a bug!\n"; 366 EmitProgressBitcode(M, "basicblockextractfail", true); 367 } 368 return Ret; 369} 370