tools/bugpoint/ExtractFunction.cpp

   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/SymbolTable.h"
  22 #include "llvm/Analysis/Verifier.h"
  23 #include "llvm/Transforms/IPO.h"
  24 #include "llvm/Transforms/Scalar.h"
  25 #include "llvm/Transforms/Utils/Cloning.h"
  26 #include "llvm/Transforms/Utils/FunctionUtils.h"
  27 #include "llvm/Target/TargetData.h"
  28 #include "llvm/Support/CommandLine.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/FileUtilities.h"
  31 #include <set>
  32 #include <iostream>
  33 using namespace llvm;
  34
  35 namespace llvm {
  36   bool DisableSimplifyCFG = false;
  37 } // End llvm namespace
  38
  39 namespace {
  40   cl::opt<bool>
  41   NoDCE ("disable-dce",
  42          cl::desc("Do not use the -dce pass to reduce testcases"));
  43   cl::opt<bool, true>
  44   NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG),
  45          cl::desc("Do not use the -simplifycfg pass to reduce testcases"));
  46 }
  47
  48 /// deleteInstructionFromProgram - This method clones the current Program and
  49 /// deletes the specified instruction from the cloned module.  It then runs a
  50 /// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which
  51 /// depends on the value.  The modified module is then returned.
  52 ///
  53 Module *BugDriver::deleteInstructionFromProgram(const Instruction *I,
  54                                                 unsigned Simplification) const {
  55   Module *Result = CloneModule(Program);
  56
  57   const BasicBlock *PBB = I->getParent();
  58   const Function *PF = PBB->getParent();
  59
  60   Module::iterator RFI = Result->begin(); // Get iterator to corresponding fn
  61   std::advance(RFI, std::distance(PF->getParent()->begin(),
  62                                   Module::const_iterator(PF)));
  63
  64   Function::iterator RBI = RFI->begin();  // Get iterator to corresponding BB
  65   std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB)));
  66
  67   BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst
  68   std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I)));
  69   Instruction *TheInst = RI;              // Got the corresponding instruction!
  70
  71   // If this instruction produces a value, replace any users with null values
  72   if (TheInst->getType() != Type::VoidTy)
  73     TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType()));
  74
  75   // Remove the instruction from the program.
  76   TheInst->getParent()->getInstList().erase(TheInst);
  77
  78
  79   //writeProgramToFile("current.bc", Result);
  80
  81   // Spiff up the output a little bit.
  82   PassManager Passes;
  83   // Make sure that the appropriate target data is always used...
  84   Passes.add(new TargetData(Result));
  85
  86   /// FIXME: If this used runPasses() like the methods below, we could get rid
  87   /// of the -disable-* options!
  88   if (Simplification > 1 && !NoDCE)
  89     Passes.add(createDeadCodeEliminationPass());
  90   if (Simplification && !DisableSimplifyCFG)
  91     Passes.add(createCFGSimplificationPass());      // Delete dead control flow
  92
  93   Passes.add(createVerifierPass());
  94   Passes.run(*Result);
  95   return Result;
  96 }
  97
  98 static const PassInfo *getPI(Pass *P) {
  99   const PassInfo *PI = P->getPassInfo();
 100   delete P;
 101   return PI;
 102 }
 103
 104 /// performFinalCleanups - This method clones the current Program and performs
 105 /// a series of cleanups intended to get rid of extra cruft on the module
 106 /// before handing it to the user.
 107 ///
 108 Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) {
 109   // Make all functions external, so GlobalDCE doesn't delete them...
 110   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
 111     I->setLinkage(GlobalValue::ExternalLinkage);
 112
 113   std::vector<const PassInfo*> CleanupPasses;
 114   CleanupPasses.push_back(getPI(createFunctionResolvingPass()));
 115   CleanupPasses.push_back(getPI(createGlobalDCEPass()));
 116   CleanupPasses.push_back(getPI(createDeadTypeEliminationPass()));
 117
 118   if (MayModifySemantics)
 119     CleanupPasses.push_back(getPI(createDeadArgHackingPass()));
 120   else
 121     CleanupPasses.push_back(getPI(createDeadArgEliminationPass()));
 122
 123   Module *New = runPassesOn(M, CleanupPasses);
 124   if (New == 0) {
 125     std::cerr << "Final cleanups failed.  Sorry. :(  Please report a bug!\n";
 126     return M;
 127   }
 128   delete M;
 129   return New;
 130 }
 131
 132
 133 /// ExtractLoop - Given a module, extract up to one loop from it into a new
 134 /// function.  This returns null if there are no extractable loops in the
 135 /// program or if the loop extractor crashes.
 136 Module *BugDriver::ExtractLoop(Module *M) {
 137   std::vector<const PassInfo*> LoopExtractPasses;
 138   LoopExtractPasses.push_back(getPI(createSingleLoopExtractorPass()));
 139
 140   Module *NewM = runPassesOn(M, LoopExtractPasses);
 141   if (NewM == 0) {
 142     Module *Old = swapProgramIn(M);
 143     std::cout << "*** Loop extraction failed: ";
 144     EmitProgressBytecode("loopextraction", true);
 145     std::cout << "*** Sorry. :(  Please report a bug!\n";
 146     swapProgramIn(Old);
 147     return 0;
 148   }
 149
 150   // Check to see if we created any new functions.  If not, no loops were
 151   // extracted and we should return null.  Limit the number of loops we extract
 152   // to avoid taking forever.
 153   static unsigned NumExtracted = 32;
 154   if (M->size() == NewM->size() || --NumExtracted == 0) {
 155     delete NewM;
 156     return 0;
 157   } else {
 158     assert(M->size() < NewM->size() && "Loop extract removed functions?");
 159     Module::iterator MI = NewM->begin();
 160     for (unsigned i = 0, e = M->size(); i != e; ++i)
 161       ++MI;
 162   }
 163
 164   return NewM;
 165 }
 166
 167
 168 // DeleteFunctionBody - "Remove" the function by deleting all of its basic
 169 // blocks, making it external.
 170 //
 171 void llvm::DeleteFunctionBody(Function *F) {
 172   // delete the body of the function...
 173   F->deleteBody();
 174   assert(F->isExternal() && "This didn't make the function external!");
 175 }
 176
 177 /// GetTorInit - Given a list of entries for static ctors/dtors, return them
 178 /// as a constant array.
 179 static Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) {
 180   assert(!TorList.empty() && "Don't create empty tor list!");
 181   std::vector<Constant*> ArrayElts;
 182   for (unsigned i = 0, e = TorList.size(); i != e; ++i) {
 183     std::vector<Constant*> Elts;
 184     Elts.push_back(ConstantSInt::get(Type::IntTy, TorList[i].second));
 185     Elts.push_back(TorList[i].first);
 186     ArrayElts.push_back(ConstantStruct::get(Elts));
 187   }
 188   return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(),
 189                                            ArrayElts.size()),
 190                             ArrayElts);
 191 }
 192
 193 /// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and
 194 /// M1 has all of the global variables.  If M2 contains any functions that are
 195 /// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and
 196 /// prune appropriate entries out of M1s list.
 197 static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2){
 198   GlobalVariable *GV = M1->getNamedGlobal(GlobalName);
 199   if (!GV || GV->isExternal() || GV->hasInternalLinkage() ||
 200       !GV->use_empty()) return;
 201
 202   std::vector<std::pair<Function*, int> > M1Tors, M2Tors;
 203   ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer());
 204   if (!InitList) return;
 205
 206   for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) {
 207     if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){
 208       if (CS->getNumOperands() != 2) return;  // Not array of 2-element structs.
 209
 210       if (CS->getOperand(1)->isNullValue())
 211         break;  // Found a null terminator, stop here.
 212
 213       ConstantSInt *CI = dyn_cast<ConstantSInt>(CS->getOperand(0));
 214       int Priority = CI ? CI->getValue() : 0;
 215
 216       Constant *FP = CS->getOperand(1);
 217       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP))
 218         if (CE->getOpcode() == Instruction::Cast)
 219           FP = CE->getOperand(0);
 220       if (Function *F = dyn_cast<Function>(FP)) {
 221         if (!F->isExternal())
 222           M1Tors.push_back(std::make_pair(F, Priority));
 223         else {
 224           // Map to M2's version of the function.
 225           F = M2->getFunction(F->getName(), F->getFunctionType());
 226           M2Tors.push_back(std::make_pair(F, Priority));
 227         }
 228       }
 229     }
 230   }
 231
 232   GV->eraseFromParent();
 233   if (!M1Tors.empty()) {
 234     Constant *M1Init = GetTorInit(M1Tors);
 235     new GlobalVariable(M1Init->getType(), false, GlobalValue::AppendingLinkage,
 236                        M1Init, GlobalName, M1);
 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(M2Init->getType(), false, GlobalValue::AppendingLinkage,
 247                        M2Init, GlobalName, M2);
 248   }
 249 }
 250
 251 //// RewriteUsesInNewModule - takes a Module and a reference to a globalvalue
 252 //// (OrigVal) in that module and changes the reference to a different
 253 //// globalvalue (NewVal) in a seperate module.
 254 static void RewriteUsesInNewModule(Constant *OrigVal, Constant *NewVal,
 255                                    Module *TargetMod) {
 256   assert(OrigVal->getType() == NewVal->getType() &&
 257          "Can't replace something with a different type");
 258   for (Value::use_iterator UI = OrigVal->use_begin(), E = OrigVal->use_end();
 259        UI != E; ) {
 260     Value::use_iterator TmpUI = UI++;
 261     User *U = *TmpUI;
 262     if (Instruction *Inst = dyn_cast<Instruction>(U)) {
 263       Module *InstM = Inst->getParent()->getParent()->getParent();
 264       if (InstM != TargetMod) {
 265          TmpUI.getUse() = NewVal;
 266       }
 267     } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(U)) {
 268       if (GV->getParent() != TargetMod) {
 269         TmpUI.getUse() = NewVal;
 270       }
 271     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 272       // If nothing uses this, don't bother making a copy.
 273       if (CE->use_empty()) continue;
 274       Constant *NewCE = CE->getWithOperandReplaced(TmpUI.getOperandNo(),
 275                                                    NewVal);
 276       RewriteUsesInNewModule(CE, NewCE, TargetMod);
 277     } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(U)) {
 278       // If nothing uses this, don't bother making a copy.
 279       if (CS->use_empty()) continue;
 280       unsigned OpNo = TmpUI.getOperandNo();
 281       std::vector<Constant*> Ops;
 282       for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i)
 283         Ops.push_back(i == OpNo ? NewVal : CS->getOperand(i));
 284       Constant *NewStruct = ConstantStruct::get(Ops);
 285       RewriteUsesInNewModule(CS, NewStruct, TargetMod);
 286      } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(U)) {
 287       // If nothing uses this, don't bother making a copy.
 288       if (CP->use_empty()) continue;
 289       unsigned OpNo = TmpUI.getOperandNo();
 290       std::vector<Constant*> Ops;
 291       for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i)
 292         Ops.push_back(i == OpNo ? NewVal : CP->getOperand(i));
 293       Constant *NewPacked = ConstantPacked::get(Ops);
 294       RewriteUsesInNewModule(CP, NewPacked, TargetMod);
 295     } else if (ConstantArray *CA = dyn_cast<ConstantArray>(U)) {
 296       // If nothing uses this, don't bother making a copy.
 297       if (CA->use_empty()) continue;
 298       unsigned OpNo = TmpUI.getOperandNo();
 299       std::vector<Constant*> Ops;
 300       for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
 301         Ops.push_back(i == OpNo ? NewVal : CA->getOperand(i));
 302       }
 303       Constant *NewArray = ConstantArray::get(CA->getType(), Ops);
 304       RewriteUsesInNewModule(CA, NewArray, TargetMod);
 305     } else {
 306       assert(0 && "Unexpected user");
 307     }
 308   }
 309 }
 310
 311
 312 /// SplitFunctionsOutOfModule - Given a module and a list of functions in the
 313 /// module, split the functions OUT of the specified module, and place them in
 314 /// the new module.
 315 Module *llvm::SplitFunctionsOutOfModule(Module *M,
 316                                         const std::vector<Function*> &F) {
 317   // Make sure functions & globals are all external so that linkage
 318   // between the two modules will work.
 319   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
 320     I->setLinkage(GlobalValue::ExternalLinkage);
 321   for (Module::global_iterator I = M->global_begin(), E = M->global_end();
 322        I != E; ++I)
 323     I->setLinkage(GlobalValue::ExternalLinkage);
 324
 325   // First off, we need to create the new module...
 326   Module *New = new Module(M->getModuleIdentifier());
 327   New->setEndianness(M->getEndianness());
 328   New->setPointerSize(M->getPointerSize());
 329   New->setTargetTriple(M->getTargetTriple());
 330   New->setModuleInlineAsm(M->getModuleInlineAsm());
 331
 332   // Copy all of the dependent libraries over.
 333   for (Module::lib_iterator I = M->lib_begin(), E = M->lib_end(); I != E; ++I)
 334     New->addLibrary(*I);
 335
 336   // build a set of the functions to search later...
 337   std::set<std::pair<std::string, const PointerType*> > TestFunctions;
 338   for (unsigned i = 0, e = F.size(); i != e; ++i) {
 339     TestFunctions.insert(std::make_pair(F[i]->getName(), F[i]->getType()));
 340   }
 341
 342   std::map<GlobalValue*, GlobalValue*> GlobalToPrototypeMap;
 343   std::vector<GlobalValue*> OrigGlobals;
 344
 345   // Adding specified functions to new module...
 346   for (Module::iterator I = M->begin(), E = M->end(); I != E;) {
 347     OrigGlobals.push_back(I);
 348     if(TestFunctions.count(std::make_pair(I->getName(), I->getType()))) {
 349       Module::iterator tempI = I;
 350       I++;
 351       Function * func = new Function(tempI->getFunctionType(),
 352                                     GlobalValue::ExternalLinkage);
 353       M->getFunctionList().insert(tempI, func);
 354       New->getFunctionList().splice(New->end(),
 355                                     M->getFunctionList(),
 356                                     tempI);
 357       func->setName(tempI->getName());
 358       func->setCallingConv(tempI->getCallingConv());
 359       GlobalToPrototypeMap[tempI] = func;
 360       // NEW TO OLD
 361     } else {
 362       Function * func = new Function(I->getFunctionType(),
 363                                     GlobalValue::ExternalLinkage,
 364                                     I->getName(),
 365                                     New);
 366       func->setCallingConv(I->getCallingConv());
 367       GlobalToPrototypeMap[I] = func;
 368       // NEW TO OLD
 369       I++;
 370     }
 371   }
 372
 373   //copy over global list
 374   for (Module::global_iterator I = M->global_begin(),
 375        E = M->global_end(); I != E; ++I) {
 376     OrigGlobals.push_back(I);
 377     GlobalVariable  *glob = new GlobalVariable (I->getType()->getElementType(),
 378                                                 I->isConstant(),
 379                                                 GlobalValue::ExternalLinkage,
 380                                                 0,
 381                                                 I->getName(),
 382                                                 New);
 383     GlobalToPrototypeMap[I] = glob;
 384   }
 385
 386   // Copy all of the type symbol table entries over.
 387   const SymbolTable &SymTab = M->getSymbolTable();
 388   SymbolTable::type_const_iterator TypeI = SymTab.type_begin();
 389   SymbolTable::type_const_iterator TypeE = SymTab.type_end();
 390   for (; TypeI != TypeE; ++TypeI)
 391     New->addTypeName(TypeI->first, TypeI->second);
 392
 393   // Loop over globals, rewriting uses in the module the prototype is in to use
 394   // the prototype.
 395   for (unsigned i = 0, e = OrigGlobals.size(); i != e; ++i) {
 396     assert(OrigGlobals[i]->getName() ==
 397            GlobalToPrototypeMap[OrigGlobals[i]]->getName());
 398     RewriteUsesInNewModule(OrigGlobals[i], GlobalToPrototypeMap[OrigGlobals[i]],
 399                            OrigGlobals[i]->getParent());
 400   }
 401
 402   // Make sure that there is a global ctor/dtor array in both halves of the
 403   // module if they both have static ctor/dtor functions.
 404   SplitStaticCtorDtor("llvm.global_ctors", M, New);
 405   SplitStaticCtorDtor("llvm.global_dtors", M, New);
 406
 407   return New;
 408 }
 409
 410 //===----------------------------------------------------------------------===//
 411 // Basic Block Extraction Code
 412 //===----------------------------------------------------------------------===//
 413
 414 namespace {
 415   std::vector<BasicBlock*> BlocksToNotExtract;
 416
 417   /// BlockExtractorPass - This pass is used by bugpoint to extract all blocks
 418   /// from the module into their own functions except for those specified by the
 419   /// BlocksToNotExtract list.
 420   class BlockExtractorPass : public ModulePass {
 421     bool runOnModule(Module &M);
 422   };
 423   RegisterPass<BlockExtractorPass>
 424   XX("extract-bbs", "Extract Basic Blocks From Module (for bugpoint use)");
 425 }
 426
 427 bool BlockExtractorPass::runOnModule(Module &M) {
 428   std::set<BasicBlock*> TranslatedBlocksToNotExtract;
 429   for (unsigned i = 0, e = BlocksToNotExtract.size(); i != e; ++i) {
 430     BasicBlock *BB = BlocksToNotExtract[i];
 431     Function *F = BB->getParent();
 432
 433     // Map the corresponding function in this module.
 434     Function *MF = M.getFunction(F->getName(), F->getFunctionType());
 435
 436     // Figure out which index the basic block is in its function.
 437     Function::iterator BBI = MF->begin();
 438     std::advance(BBI, std::distance(F->begin(), Function::iterator(BB)));
 439     TranslatedBlocksToNotExtract.insert(BBI);
 440   }
 441
 442   // Now that we know which blocks to not extract, figure out which ones we WANT
 443   // to extract.
 444   std::vector<BasicBlock*> BlocksToExtract;
 445   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
 446     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 447       if (!TranslatedBlocksToNotExtract.count(BB))
 448         BlocksToExtract.push_back(BB);
 449
 450   for (unsigned i = 0, e = BlocksToExtract.size(); i != e; ++i)
 451     ExtractBasicBlock(BlocksToExtract[i]);
 452
 453   return !BlocksToExtract.empty();
 454 }
 455
 456 /// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks
 457 /// into their own functions.  The only detail is that M is actually a module
 458 /// cloned from the one the BBs are in, so some mapping needs to be performed.
 459 /// If this operation fails for some reason (ie the implementation is buggy),
 460 /// this function should return null, otherwise it returns a new Module.
 461 Module *BugDriver::ExtractMappedBlocksFromModule(const
 462                                                  std::vector<BasicBlock*> &BBs,
 463                                                  Module *M) {
 464   // Set the global list so that pass will be able to access it.
 465   BlocksToNotExtract = BBs;
 466
 467   std::vector<const PassInfo*> PI;
 468   PI.push_back(getPI(new BlockExtractorPass()));
 469   Module *Ret = runPassesOn(M, PI);
 470   BlocksToNotExtract.clear();
 471   if (Ret == 0) {
 472     std::cout << "*** Basic Block extraction failed, please report a bug!\n";
 473     M = swapProgramIn(M);
 474     EmitProgressBytecode("basicblockextractfail", true);
 475     swapProgramIn(M);
 476   }
 477   return Ret;
 478 }