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/IR/Constants.h" 17 #include "llvm/IR/DataLayout.h" 18 #include "llvm/IR/DerivedTypes.h" 19 #include "llvm/IR/LLVMContext.h" 20 #include "llvm/IR/LegacyPassManager.h" 21 #include "llvm/IR/Module.h" 22 #include "llvm/IR/Verifier.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Support/CommandLine.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/FileUtilities.h" 27 #include "llvm/Support/Path.h" 28 #include "llvm/Support/Signals.h" 29 #include "llvm/Support/ToolOutputFile.h" 30 #include "llvm/Transforms/IPO.h" 31 #include "llvm/Transforms/Scalar.h" 32 #include "llvm/Transforms/Utils/Cloning.h" 33 #include "llvm/Transforms/Utils/CodeExtractor.h" 34 #include <set> 35 using namespace llvm; 36 37 #define DEBUG_TYPE "bugpoint" 38 39 namespace llvm { 40 bool DisableSimplifyCFG = false; 41 extern cl::opt<std::string> OutputPrefix; 42 } // End llvm namespace 43 44 namespace { 45 cl::opt<bool> 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 Function *globalInitUsesExternalBA(GlobalVariable *GV) { 52 if (!GV->hasInitializer()) 53 return nullptr; 54 55 Constant *I = GV->getInitializer(); 56 57 // walk the values used by the initializer 58 // (and recurse into things like ConstantExpr) 59 std::vector<Constant *> Todo; 60 std::set<Constant *> Done; 61 Todo.push_back(I); 62 63 while (!Todo.empty()) { 64 Constant *V = Todo.back(); 65 Todo.pop_back(); 66 Done.insert(V); 67 68 if (BlockAddress *BA = dyn_cast<BlockAddress>(V)) { 69 Function *F = BA->getFunction(); 70 if (F->isDeclaration()) 71 return F; 72 } 73 74 for (User::op_iterator i = V->op_begin(), e = V->op_end(); i != e; ++i) { 75 Constant *C = dyn_cast<Constant>(*i); 76 if (C && !isa<GlobalValue>(C) && !Done.count(C)) 77 Todo.push_back(C); 78 } 79 } 80 return nullptr; 81 } 82 } // end anonymous namespace 83 84 std::unique_ptr<Module> 85 BugDriver::deleteInstructionFromProgram(const Instruction *I, 86 unsigned Simplification) { 87 // FIXME, use vmap? 88 std::unique_ptr<Module> Clone = CloneModule(*Program); 89 90 const BasicBlock *PBB = I->getParent(); 91 const Function *PF = PBB->getParent(); 92 93 Module::iterator RFI = Clone->begin(); // Get iterator to corresponding fn 94 std::advance( 95 RFI, std::distance(PF->getParent()->begin(), Module::const_iterator(PF))); 96 97 Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 98 std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 99 100 BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 101 std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 102 Instruction *TheInst = &*RI; // Got the corresponding instruction! 103 104 // If this instruction produces a value, replace any users with null values 105 if (!TheInst->getType()->isVoidTy()) 106 TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); 107 108 // Remove the instruction from the program. 109 TheInst->getParent()->getInstList().erase(TheInst); 110 111 // Spiff up the output a little bit. 112 std::vector<std::string> Passes; 113 114 /// Can we get rid of the -disable-* options? 115 if (Simplification > 1 && !NoDCE) 116 Passes.push_back("dce"); 117 if (Simplification && !DisableSimplifyCFG) 118 Passes.push_back("simplifycfg"); // Delete dead control flow 119 120 Passes.push_back("verify"); 121 std::unique_ptr<Module> New = runPassesOn(Clone.get(), Passes); 122 if (!New) { 123 errs() << "Instruction removal failed. Sorry. :( Please report a bug!\n"; 124 exit(1); 125 } 126 return New; 127 } 128 129 std::unique_ptr<Module> 130 BugDriver::performFinalCleanups(std::unique_ptr<Module> M, 131 bool MayModifySemantics) { 132 // Make all functions external, so GlobalDCE doesn't delete them... 133 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 134 I->setLinkage(GlobalValue::ExternalLinkage); 135 136 std::vector<std::string> CleanupPasses; 137 CleanupPasses.push_back("globaldce"); 138 139 if (MayModifySemantics) 140 CleanupPasses.push_back("deadarghaX0r"); 141 else 142 CleanupPasses.push_back("deadargelim"); 143 144 std::unique_ptr<Module> New = runPassesOn(M.get(), CleanupPasses); 145 if (!New) { 146 errs() << "Final cleanups failed. Sorry. :( Please report a bug!\n"; 147 return nullptr; 148 } 149 return New; 150 } 151 152 std::unique_ptr<Module> BugDriver::extractLoop(Module *M) { 153 std::vector<std::string> LoopExtractPasses; 154 LoopExtractPasses.push_back("loop-extract-single"); 155 156 std::unique_ptr<Module> NewM = runPassesOn(M, LoopExtractPasses); 157 if (!NewM) { 158 outs() << "*** Loop extraction failed: "; 159 EmitProgressBitcode(*M, "loopextraction", true); 160 outs() << "*** Sorry. :( Please report a bug!\n"; 161 return nullptr; 162 } 163 164 // Check to see if we created any new functions. If not, no loops were 165 // extracted and we should return null. Limit the number of loops we extract 166 // to avoid taking forever. 167 static unsigned NumExtracted = 32; 168 if (M->size() == NewM->size() || --NumExtracted == 0) { 169 return nullptr; 170 } else { 171 assert(M->size() < NewM->size() && "Loop extract removed functions?"); 172 Module::iterator MI = NewM->begin(); 173 for (unsigned i = 0, e = M->size(); i != e; ++i) 174 ++MI; 175 } 176 177 return NewM; 178 } 179 180 static void eliminateAliases(GlobalValue *GV) { 181 // First, check whether a GlobalAlias references this definition. 182 // GlobalAlias MAY NOT reference declarations. 183 for (;;) { 184 // 1. Find aliases 185 SmallVector<GlobalAlias *, 1> aliases; 186 Module *M = GV->getParent(); 187 for (Module::alias_iterator I = M->alias_begin(), E = M->alias_end(); 188 I != E; ++I) 189 if (I->getAliasee()->stripPointerCasts() == GV) 190 aliases.push_back(&*I); 191 if (aliases.empty()) 192 break; 193 // 2. Resolve aliases 194 for (unsigned i = 0, e = aliases.size(); i < e; ++i) { 195 aliases[i]->replaceAllUsesWith(aliases[i]->getAliasee()); 196 aliases[i]->eraseFromParent(); 197 } 198 // 3. Repeat until no more aliases found; there might 199 // be an alias to an alias... 200 } 201 } 202 203 // 204 // DeleteGlobalInitializer - "Remove" the global variable by deleting its 205 // initializer, 206 // making it external. 207 // 208 void llvm::DeleteGlobalInitializer(GlobalVariable *GV) { 209 eliminateAliases(GV); 210 GV->setInitializer(nullptr); 211 GV->setComdat(nullptr); 212 } 213 214 // DeleteFunctionBody - "Remove" the function by deleting all of its basic 215 // blocks, making it external. 216 // 217 void llvm::DeleteFunctionBody(Function *F) { 218 eliminateAliases(F); 219 // Function declarations can't have comdats. 220 F->setComdat(nullptr); 221 222 // delete the body of the function... 223 F->deleteBody(); 224 assert(F->isDeclaration() && "This didn't make the function external!"); 225 } 226 227 /// GetTorInit - Given a list of entries for static ctors/dtors, return them 228 /// as a constant array. 229 static Constant *GetTorInit(std::vector<std::pair<Function *, int>> &TorList) { 230 assert(!TorList.empty() && "Don't create empty tor list!"); 231 std::vector<Constant *> ArrayElts; 232 Type *Int32Ty = Type::getInt32Ty(TorList[0].first->getContext()); 233 234 StructType *STy = StructType::get(Int32Ty, TorList[0].first->getType()); 235 for (unsigned i = 0, e = TorList.size(); i != e; ++i) { 236 Constant *Elts[] = {ConstantInt::get(Int32Ty, TorList[i].second), 237 TorList[i].first}; 238 ArrayElts.push_back(ConstantStruct::get(STy, Elts)); 239 } 240 return ConstantArray::get( 241 ArrayType::get(ArrayElts[0]->getType(), ArrayElts.size()), ArrayElts); 242 } 243 244 /// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and 245 /// M1 has all of the global variables. If M2 contains any functions that are 246 /// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and 247 /// prune appropriate entries out of M1s list. 248 static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, 249 ValueToValueMapTy &VMap) { 250 GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 251 if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || !GV->use_empty()) 252 return; 253 254 std::vector<std::pair<Function *, int>> M1Tors, M2Tors; 255 ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 256 if (!InitList) 257 return; 258 259 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { 260 if (ConstantStruct *CS = 261 dyn_cast<ConstantStruct>(InitList->getOperand(i))) { 262 if (CS->getNumOperands() != 2) 263 return; // Not array of 2-element structs. 264 265 if (CS->getOperand(1)->isNullValue()) 266 break; // Found a null terminator, stop here. 267 268 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 269 int Priority = CI ? CI->getSExtValue() : 0; 270 271 Constant *FP = CS->getOperand(1); 272 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP)) 273 if (CE->isCast()) 274 FP = CE->getOperand(0); 275 if (Function *F = dyn_cast<Function>(FP)) { 276 if (!F->isDeclaration()) 277 M1Tors.push_back(std::make_pair(F, Priority)); 278 else { 279 // Map to M2's version of the function. 280 F = cast<Function>(VMap[F]); 281 M2Tors.push_back(std::make_pair(F, Priority)); 282 } 283 } 284 } 285 } 286 287 GV->eraseFromParent(); 288 if (!M1Tors.empty()) { 289 Constant *M1Init = GetTorInit(M1Tors); 290 new GlobalVariable(*M1, M1Init->getType(), false, 291 GlobalValue::AppendingLinkage, M1Init, GlobalName); 292 } 293 294 GV = M2->getNamedGlobal(GlobalName); 295 assert(GV && "Not a clone of M1?"); 296 assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 297 298 GV->eraseFromParent(); 299 if (!M2Tors.empty()) { 300 Constant *M2Init = GetTorInit(M2Tors); 301 new GlobalVariable(*M2, M2Init->getType(), false, 302 GlobalValue::AppendingLinkage, M2Init, GlobalName); 303 } 304 } 305 306 std::unique_ptr<Module> 307 llvm::SplitFunctionsOutOfModule(Module *M, const std::vector<Function *> &F, 308 ValueToValueMapTy &VMap) { 309 // Make sure functions & globals are all external so that linkage 310 // between the two modules will work. 311 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 312 I->setLinkage(GlobalValue::ExternalLinkage); 313 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 314 I != E; ++I) { 315 if (I->hasName() && I->getName()[0] == '\01') 316 I->setName(I->getName().substr(1)); 317 I->setLinkage(GlobalValue::ExternalLinkage); 318 } 319 320 ValueToValueMapTy NewVMap; 321 std::unique_ptr<Module> New = CloneModule(*M, NewVMap); 322 323 // Remove the Test functions from the Safe module 324 std::set<Function *> TestFunctions; 325 for (unsigned i = 0, e = F.size(); i != e; ++i) { 326 Function *TNOF = cast<Function>(VMap[F[i]]); 327 LLVM_DEBUG(errs() << "Removing function "); 328 LLVM_DEBUG(TNOF->printAsOperand(errs(), false)); 329 LLVM_DEBUG(errs() << "\n"); 330 TestFunctions.insert(cast<Function>(NewVMap[TNOF])); 331 DeleteFunctionBody(TNOF); // Function is now external in this module! 332 } 333 334 // Remove the Safe functions from the Test module 335 for (Function &I : *New) 336 if (!TestFunctions.count(&I)) 337 DeleteFunctionBody(&I); 338 339 // Try to split the global initializers evenly 340 for (GlobalVariable &I : M->globals()) { 341 GlobalVariable *GV = cast<GlobalVariable>(NewVMap[&I]); 342 if (Function *TestFn = globalInitUsesExternalBA(&I)) { 343 if (Function *SafeFn = globalInitUsesExternalBA(GV)) { 344 errs() << "*** Error: when reducing functions, encountered " 345 "the global '"; 346 GV->printAsOperand(errs(), false); 347 errs() << "' with an initializer that references blockaddresses " 348 "from safe function '" 349 << SafeFn->getName() << "' and from test function '" 350 << TestFn->getName() << "'.\n"; 351 exit(1); 352 } 353 DeleteGlobalInitializer(&I); // Delete the initializer to make it external 354 } else { 355 // If we keep it in the safe module, then delete it in the test module 356 DeleteGlobalInitializer(GV); 357 } 358 } 359 360 // Make sure that there is a global ctor/dtor array in both halves of the 361 // module if they both have static ctor/dtor functions. 362 SplitStaticCtorDtor("llvm.global_ctors", M, New.get(), NewVMap); 363 SplitStaticCtorDtor("llvm.global_dtors", M, New.get(), NewVMap); 364 365 return New; 366 } 367 368 //===----------------------------------------------------------------------===// 369 // Basic Block Extraction Code 370 //===----------------------------------------------------------------------===// 371 372 std::unique_ptr<Module> 373 BugDriver::extractMappedBlocksFromModule(const std::vector<BasicBlock *> &BBs, 374 Module *M) { 375 auto Temp = sys::fs::TempFile::create(OutputPrefix + "-extractblocks%%%%%%%"); 376 if (!Temp) { 377 outs() << "*** Basic Block extraction failed!\n"; 378 errs() << "Error creating temporary file: " << toString(Temp.takeError()) 379 << "\n"; 380 EmitProgressBitcode(*M, "basicblockextractfail", true); 381 return nullptr; 382 } 383 DiscardTemp Discard{*Temp}; 384 385 // Extract all of the blocks except the ones in BBs. 386 SmallVector<BasicBlock *, 32> BlocksToExtract; 387 for (Function &F : *M) 388 for (BasicBlock &BB : F) 389 // Check if this block is going to be extracted. 390 if (std::find(BBs.begin(), BBs.end(), &BB) == BBs.end()) 391 BlocksToExtract.push_back(&BB); 392 393 raw_fd_ostream OS(Temp->FD, /*shouldClose*/ false); 394 for (BasicBlock *BB : BBs) { 395 // If the BB doesn't have a name, give it one so we have something to key 396 // off of. 397 if (!BB->hasName()) 398 BB->setName("tmpbb"); 399 OS << BB->getParent()->getName() << " " << BB->getName() << "\n"; 400 } 401 OS.flush(); 402 if (OS.has_error()) { 403 errs() << "Error writing list of blocks to not extract\n"; 404 EmitProgressBitcode(*M, "basicblockextractfail", true); 405 OS.clear_error(); 406 return nullptr; 407 } 408 409 std::string uniqueFN = "--extract-blocks-file="; 410 uniqueFN += Temp->TmpName; 411 const char *ExtraArg = uniqueFN.c_str(); 412 413 std::vector<std::string> PI; 414 PI.push_back("extract-blocks"); 415 std::unique_ptr<Module> Ret = runPassesOn(M, PI, 1, &ExtraArg); 416 417 if (!Ret) { 418 outs() << "*** Basic Block extraction failed, please report a bug!\n"; 419 EmitProgressBitcode(*M, "basicblockextractfail", true); 420 } 421 return Ret; 422 } 423