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