ExtractFunction.cpp revision 1997473cf72957d0e70322e2fe6fe2ab141c58a6
1//===- ExtractFunction.cpp - Extract a function from Program --------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Module.h" 19#include "llvm/PassManager.h" 20#include "llvm/Pass.h" 21#include "llvm/Analysis/Verifier.h" 22#include "llvm/Transforms/IPO.h" 23#include "llvm/Transforms/Scalar.h" 24#include "llvm/Transforms/Utils/Cloning.h" 25#include "llvm/Transforms/Utils/FunctionUtils.h" 26#include "llvm/Target/TargetData.h" 27#include "llvm/Support/CommandLine.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/Support/FileUtilities.h" 30#include <set> 31#include <iostream> 32using namespace llvm; 33 34namespace llvm { 35 bool DisableSimplifyCFG = false; 36} // End llvm namespace 37 38namespace { 39 cl::opt<bool> 40 NoDCE ("disable-dce", 41 cl::desc("Do not use the -dce pass to reduce testcases")); 42 cl::opt<bool, true> 43 NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG), 44 cl::desc("Do not use the -simplifycfg pass to reduce testcases")); 45} 46 47/// deleteInstructionFromProgram - This method clones the current Program and 48/// deletes the specified instruction from the cloned module. It then runs a 49/// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which 50/// depends on the value. The modified module is then returned. 51/// 52Module *BugDriver::deleteInstructionFromProgram(const Instruction *I, 53 unsigned Simplification) const { 54 Module *Result = CloneModule(Program); 55 56 const BasicBlock *PBB = I->getParent(); 57 const Function *PF = PBB->getParent(); 58 59 Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn 60 std::advance(RFI, std::distance(PF->getParent()->begin(), 61 Module::const_iterator(PF))); 62 63 Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 64 std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 65 66 BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 67 std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 68 Instruction *TheInst = RI; // Got the corresponding instruction! 69 70 // If this instruction produces a value, replace any users with null values 71 if (TheInst->getType() != Type::VoidTy) 72 TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); 73 74 // Remove the instruction from the program. 75 TheInst->getParent()->getInstList().erase(TheInst); 76 77 78 //writeProgramToFile("current.bc", Result); 79 80 // Spiff up the output a little bit. 81 PassManager Passes; 82 // Make sure that the appropriate target data is always used... 83 Passes.add(new TargetData(Result)); 84 85 /// FIXME: If this used runPasses() like the methods below, we could get rid 86 /// of the -disable-* options! 87 if (Simplification > 1 && !NoDCE) 88 Passes.add(createDeadCodeEliminationPass()); 89 if (Simplification && !DisableSimplifyCFG) 90 Passes.add(createCFGSimplificationPass()); // Delete dead control flow 91 92 Passes.add(createVerifierPass()); 93 Passes.run(*Result); 94 return Result; 95} 96 97static const PassInfo *getPI(Pass *P) { 98 const PassInfo *PI = P->getPassInfo(); 99 delete P; 100 return PI; 101} 102 103/// performFinalCleanups - This method clones the current Program and performs 104/// a series of cleanups intended to get rid of extra cruft on the module 105/// before handing it to the user. 106/// 107Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { 108 // Make all functions external, so GlobalDCE doesn't delete them... 109 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 110 I->setLinkage(GlobalValue::ExternalLinkage); 111 112 std::vector<const PassInfo*> CleanupPasses; 113 CleanupPasses.push_back(getPI(createGlobalDCEPass())); 114 CleanupPasses.push_back(getPI(createDeadTypeEliminationPass())); 115 116 if (MayModifySemantics) 117 CleanupPasses.push_back(getPI(createDeadArgHackingPass())); 118 else 119 CleanupPasses.push_back(getPI(createDeadArgEliminationPass())); 120 121 Module *New = runPassesOn(M, CleanupPasses); 122 if (New == 0) { 123 std::cerr << "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<const PassInfo*> LoopExtractPasses; 136 LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass())); 137 138 Module *NewM = runPassesOn(M, LoopExtractPasses); 139 if (NewM == 0) { 140 Module *Old = swapProgramIn(M); 141 std::cout << "*** Loop extraction failed: "; 142 EmitProgressBytecode("loopextraction", true); 143 std::cout << "*** Sorry. :( Please report a bug!\n"; 144 swapProgramIn(Old); 145 return 0; 146 } 147 148 // Check to see if we created any new functions. If not, no loops were 149 // extracted and we should return null. Limit the number of loops we extract 150 // to avoid taking forever. 151 static unsigned NumExtracted = 32; 152 if (M->size() == NewM->size() || --NumExtracted == 0) { 153 delete NewM; 154 return 0; 155 } else { 156 assert(M->size() < NewM->size() && "Loop extract removed functions?"); 157 Module::iterator MI = NewM->begin(); 158 for (unsigned i = 0, e = M->size(); i != e; ++i) 159 ++MI; 160 } 161 162 return NewM; 163} 164 165 166// DeleteFunctionBody - "Remove" the function by deleting all of its basic 167// blocks, making it external. 168// 169void llvm::DeleteFunctionBody(Function *F) { 170 // delete the body of the function... 171 F->deleteBody(); 172 assert(F->isDeclaration() && "This didn't make the function external!"); 173} 174 175/// GetTorInit - Given a list of entries for static ctors/dtors, return them 176/// as a constant array. 177static Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) { 178 assert(!TorList.empty() && "Don't create empty tor list!"); 179 std::vector<Constant*> ArrayElts; 180 for (unsigned i = 0, e = TorList.size(); i != e; ++i) { 181 std::vector<Constant*> Elts; 182 Elts.push_back(ConstantInt::get(Type::Int32Ty, TorList[i].second)); 183 Elts.push_back(TorList[i].first); 184 ArrayElts.push_back(ConstantStruct::get(Elts)); 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 GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 197 if (!GV || GV->isDeclaration() || GV->hasInternalLinkage() || 198 !GV->use_empty()) return; 199 200 std::vector<std::pair<Function*, int> > M1Tors, M2Tors; 201 ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 202 if (!InitList) return; 203 204 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { 205 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){ 206 if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. 207 208 if (CS->getOperand(1)->isNullValue()) 209 break; // Found a null terminator, stop here. 210 211 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 212 int Priority = CI ? CI->getSExtValue() : 0; 213 214 Constant *FP = CS->getOperand(1); 215 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP)) 216 if (CE->isCast()) 217 FP = CE->getOperand(0); 218 if (Function *F = dyn_cast<Function>(FP)) { 219 if (!F->isDeclaration()) 220 M1Tors.push_back(std::make_pair(F, Priority)); 221 else { 222 // Map to M2's version of the function. 223 F = M2->getFunction(F->getName()); 224 M2Tors.push_back(std::make_pair(F, Priority)); 225 } 226 } 227 } 228 } 229 230 GV->eraseFromParent(); 231 if (!M1Tors.empty()) { 232 Constant *M1Init = GetTorInit(M1Tors); 233 new GlobalVariable(M1Init->getType(), false, GlobalValue::AppendingLinkage, 234 M1Init, GlobalName, M1); 235 } 236 237 GV = M2->getNamedGlobal(GlobalName); 238 assert(GV && "Not a clone of M1?"); 239 assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 240 241 GV->eraseFromParent(); 242 if (!M2Tors.empty()) { 243 Constant *M2Init = GetTorInit(M2Tors); 244 new GlobalVariable(M2Init->getType(), false, GlobalValue::AppendingLinkage, 245 M2Init, GlobalName, M2); 246 } 247} 248 249 250/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 251/// module, split the functions OUT of the specified module, and place them in 252/// the new module. 253Module *llvm::SplitFunctionsOutOfModule(Module *M, 254 const std::vector<Function*> &F) { 255 // Make sure functions & globals are all external so that linkage 256 // between the two modules will work. 257 for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 258 I->setLinkage(GlobalValue::ExternalLinkage); 259 for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 260 I != E; ++I) 261 I->setLinkage(GlobalValue::ExternalLinkage); 262 263 Module *New = CloneModule(M); 264 265 // Make sure global initializers exist only in the safe module (CBE->.so) 266 for (Module::global_iterator I = New->global_begin(), E = New->global_end(); 267 I != E; ++I) 268 I->setInitializer(0); // Delete the initializer to make it external 269 270 // Remove the Test functions from the Safe module 271 std::set<std::pair<std::string, const PointerType*> > TestFunctions; 272 for (unsigned i = 0, e = F.size(); i != e; ++i) { 273 TestFunctions.insert(std::make_pair(F[i]->getName(), F[i]->getType())); 274 Function *TNOF = M->getFunction(F[i]->getName()); 275 assert(TNOF && "Function doesn't exist in module!"); 276 assert(TNOF->getFunctionType() == F[i]->getFunctionType() && "wrong type?"); 277 DEBUG(std::cerr << "Removing function " << F[i]->getName() << "\n"); 278 DeleteFunctionBody(TNOF); // Function is now external in this module! 279 } 280 281 282 // Remove the Safe functions from the Test module 283 for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 284 if (!TestFunctions.count(std::make_pair(I->getName(), I->getType()))) 285 DeleteFunctionBody(I); 286 287 288 // Make sure that there is a global ctor/dtor array in both halves of the 289 // module if they both have static ctor/dtor functions. 290 SplitStaticCtorDtor("llvm.global_ctors", M, New); 291 SplitStaticCtorDtor("llvm.global_dtors", M, New); 292 293 return New; 294} 295 296//===----------------------------------------------------------------------===// 297// Basic Block Extraction Code 298//===----------------------------------------------------------------------===// 299 300namespace { 301 std::vector<BasicBlock*> BlocksToNotExtract; 302 303 /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks 304 /// from the module into their own functions except for those specified by the 305 /// BlocksToNotExtract list. 306 class BlockExtractorPass : public ModulePass { 307 bool runOnModule(Module &M); 308 public: 309 static char ID; // Pass ID, replacement for typeid 310 BlockExtractorPass() : ModulePass((intptr_t)&ID) {} 311 }; 312 char BlockExtractorPass::ID = 0; 313 RegisterPass<BlockExtractorPass> 314 XX("extract-bbs", "Extract Basic Blocks From Module (for bugpoint use)"); 315} 316 317bool BlockExtractorPass::runOnModule(Module &M) { 318 std::set<BasicBlock*> TranslatedBlocksToNotExtract; 319 for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) { 320 BasicBlock *BB = BlocksToNotExtract[i]; 321 Function *F = BB->getParent(); 322 323 // Map the corresponding function in this module. 324 Function *MF = M.getFunction(F->getName()); 325 326 // Figure out which index the basic block is in its function. 327 Function::iterator BBI = MF->begin(); 328 std::advance(BBI, std::distance(F->begin(), Function::iterator(BB))); 329 TranslatedBlocksToNotExtract.insert(BBI); 330 } 331 332 // Now that we know which blocks to not extract, figure out which ones we WANT 333 // to extract. 334 std::vector<BasicBlock*> BlocksToExtract; 335 for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) 336 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 337 if (!TranslatedBlocksToNotExtract.count(BB)) 338 BlocksToExtract.push_back(BB); 339 340 for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i) 341 ExtractBasicBlock(BlocksToExtract[i]); 342 343 return !BlocksToExtract.empty(); 344} 345 346/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 347/// into their own functions. The only detail is that M is actually a module 348/// cloned from the one the BBs are in, so some mapping needs to be performed. 349/// If this operation fails for some reason (ie the implementation is buggy), 350/// this function should return null, otherwise it returns a new Module. 351Module *BugDriver::ExtractMappedBlocksFromModule(const 352 std::vector<BasicBlock*> &BBs, 353 Module *M) { 354 // Set the global list so that pass will be able to access it. 355 BlocksToNotExtract = BBs; 356 357 std::vector<const PassInfo*> PI; 358 PI.push_back(getPI(new BlockExtractorPass())); 359 Module *Ret = runPassesOn(M, PI); 360 BlocksToNotExtract.clear(); 361 if (Ret == 0) { 362 std::cout << "*** Basic Block extraction failed, please report a bug!\n"; 363 M = swapProgramIn(M); 364 EmitProgressBytecode("basicblockextractfail", true); 365 swapProgramIn(M); 366 } 367 return Ret; 368} 369