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