Home | History | Annotate | Download | only in bugpoint 
      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/Constants.h"
     17 #include "llvm/DerivedTypes.h"
     18 #include "llvm/LLVMContext.h"
     19 #include "llvm/Module.h"
     20 #include "llvm/PassManager.h"
     21 #include "llvm/Pass.h"
     22 #include "llvm/Analysis/Verifier.h"
     23 #include "llvm/Assembly/Writer.h"
     24 #include "llvm/Transforms/IPO.h"
     25 #include "llvm/Transforms/Scalar.h"
     26 #include "llvm/Transforms/Utils/Cloning.h"
     27 #include "llvm/Transforms/Utils/FunctionUtils.h"
     28 #include "llvm/Target/TargetData.h"
     29 #include "llvm/Support/CommandLine.h"
     30 #include "llvm/Support/Debug.h"
     31 #include "llvm/Support/FileUtilities.h"
     32 #include "llvm/Support/ToolOutputFile.h"
     33 #include "llvm/Support/Path.h"
     34 #include "llvm/Support/Signals.h"
     35 #include <set>
     36 using namespace llvm;
     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>
     45   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 0;
     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 0;
     81   }
     82 }  // end anonymous namespace
     83 
     84 /// deleteInstructionFromProgram - This method clones the current Program and
     85 /// deletes the specified instruction from the cloned module.  It then runs a
     86 /// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which
     87 /// depends on the value.  The modified module is then returned.
     88 ///
     89 Module *BugDriver::deleteInstructionFromProgram(const Instruction *I,
     90                                                 unsigned Simplification) {
     91   // FIXME, use vmap?
     92   Module *Clone = CloneModule(Program);
     93 
     94   const BasicBlock *PBB = I->getParent();
     95   const Function *PF = PBB->getParent();
     96 
     97   Module::iterator RFI = Clone->begin(); // Get iterator to corresponding fn
     98   std::advance(RFI, std::distance(PF->getParent()->begin(),
     99                                   Module::const_iterator(PF)));
    100 
    101   Function::iterator RBI = RFI->begin();  // Get iterator to corresponding BB
    102   std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB)));
    103 
    104   BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst
    105   std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I)));
    106   Instruction *TheInst = RI;              // Got the corresponding instruction!
    107 
    108   // If this instruction produces a value, replace any users with null values
    109   if (!TheInst->getType()->isVoidTy())
    110     TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType()));
    111 
    112   // Remove the instruction from the program.
    113   TheInst->getParent()->getInstList().erase(TheInst);
    114 
    115   // Spiff up the output a little bit.
    116   std::vector<std::string> Passes;
    117 
    118   /// Can we get rid of the -disable-* options?
    119   if (Simplification > 1 && !NoDCE)
    120     Passes.push_back("dce");
    121   if (Simplification && !DisableSimplifyCFG)
    122     Passes.push_back("simplifycfg");      // Delete dead control flow
    123 
    124   Passes.push_back("verify");
    125   Module *New = runPassesOn(Clone, Passes);
    126   delete Clone;
    127   if (!New) {
    128     errs() << "Instruction removal failed.  Sorry. :(  Please report a bug!\n";
    129     exit(1);
    130   }
    131   return New;
    132 }
    133 
    134 /// performFinalCleanups - This method clones the current Program and performs
    135 /// a series of cleanups intended to get rid of extra cruft on the module
    136 /// before handing it to the user.
    137 ///
    138 Module *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) {
    139   // Make all functions external, so GlobalDCE doesn't delete them...
    140   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
    141     I->setLinkage(GlobalValue::ExternalLinkage);
    142 
    143   std::vector<std::string> CleanupPasses;
    144   CleanupPasses.push_back("globaldce");
    145 
    146   if (MayModifySemantics)
    147     CleanupPasses.push_back("deadarghaX0r");
    148   else
    149     CleanupPasses.push_back("deadargelim");
    150 
    151   Module *New = runPassesOn(M, CleanupPasses);
    152   if (New == 0) {
    153     errs() << "Final cleanups failed.  Sorry. :(  Please report a bug!\n";
    154     return M;
    155   }
    156   delete M;
    157   return New;
    158 }
    159 
    160 
    161 /// ExtractLoop - Given a module, extract up to one loop from it into a new
    162 /// function.  This returns null if there are no extractable loops in the
    163 /// program or if the loop extractor crashes.
    164 Module *BugDriver::ExtractLoop(Module *M) {
    165   std::vector<std::string> LoopExtractPasses;
    166   LoopExtractPasses.push_back("loop-extract-single");
    167 
    168   Module *NewM = runPassesOn(M, LoopExtractPasses);
    169   if (NewM == 0) {
    170     outs() << "*** Loop extraction failed: ";
    171     EmitProgressBitcode(M, "loopextraction", true);
    172     outs() << "*** Sorry. :(  Please report a bug!\n";
    173     return 0;
    174   }
    175 
    176   // Check to see if we created any new functions.  If not, no loops were
    177   // extracted and we should return null.  Limit the number of loops we extract
    178   // to avoid taking forever.
    179   static unsigned NumExtracted = 32;
    180   if (M->size() == NewM->size() || --NumExtracted == 0) {
    181     delete NewM;
    182     return 0;
    183   } else {
    184     assert(M->size() < NewM->size() && "Loop extract removed functions?");
    185     Module::iterator MI = NewM->begin();
    186     for (unsigned i = 0, e = M->size(); i != e; ++i)
    187       ++MI;
    188   }
    189 
    190   return NewM;
    191 }
    192 
    193 
    194 // DeleteFunctionBody - "Remove" the function by deleting all of its basic
    195 // blocks, making it external.
    196 //
    197 void llvm::DeleteFunctionBody(Function *F) {
    198   // delete the body of the function...
    199   F->deleteBody();
    200   assert(F->isDeclaration() && "This didn't make the function external!");
    201 }
    202 
    203 /// GetTorInit - Given a list of entries for static ctors/dtors, return them
    204 /// as a constant array.
    205 static Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) {
    206   assert(!TorList.empty() && "Don't create empty tor list!");
    207   std::vector<Constant*> ArrayElts;
    208   Type *Int32Ty = Type::getInt32Ty(TorList[0].first->getContext());
    209 
    210   StructType *STy =
    211     StructType::get(Int32Ty, TorList[0].first->getType(), NULL);
    212   for (unsigned i = 0, e = TorList.size(); i != e; ++i) {
    213     Constant *Elts[] = {
    214       ConstantInt::get(Int32Ty, TorList[i].second),
    215       TorList[i].first
    216     };
    217     ArrayElts.push_back(ConstantStruct::get(STy, Elts));
    218   }
    219   return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(),
    220                                            ArrayElts.size()),
    221                             ArrayElts);
    222 }
    223 
    224 /// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and
    225 /// M1 has all of the global variables.  If M2 contains any functions that are
    226 /// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and
    227 /// prune appropriate entries out of M1s list.
    228 static void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2,
    229                                 ValueToValueMapTy &VMap) {
    230   GlobalVariable *GV = M1->getNamedGlobal(GlobalName);
    231   if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() ||
    232       !GV->use_empty()) return;
    233 
    234   std::vector<std::pair<Function*, int> > M1Tors, M2Tors;
    235   ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer());
    236   if (!InitList) return;
    237 
    238   for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) {
    239     if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){
    240       if (CS->getNumOperands() != 2) return;  // Not array of 2-element structs.
    241 
    242       if (CS->getOperand(1)->isNullValue())
    243         break;  // Found a null terminator, stop here.
    244 
    245       ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0));
    246       int Priority = CI ? CI->getSExtValue() : 0;
    247 
    248       Constant *FP = CS->getOperand(1);
    249       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP))
    250         if (CE->isCast())
    251           FP = CE->getOperand(0);
    252       if (Function *F = dyn_cast<Function>(FP)) {
    253         if (!F->isDeclaration())
    254           M1Tors.push_back(std::make_pair(F, Priority));
    255         else {
    256           // Map to M2's version of the function.
    257           F = cast<Function>(VMap[F]);
    258           M2Tors.push_back(std::make_pair(F, Priority));
    259         }
    260       }
    261     }
    262   }
    263 
    264   GV->eraseFromParent();
    265   if (!M1Tors.empty()) {
    266     Constant *M1Init = GetTorInit(M1Tors);
    267     new GlobalVariable(*M1, M1Init->getType(), false,
    268                        GlobalValue::AppendingLinkage,
    269                        M1Init, GlobalName);
    270   }
    271 
    272   GV = M2->getNamedGlobal(GlobalName);
    273   assert(GV && "Not a clone of M1?");
    274   assert(GV->use_empty() && "llvm.ctors shouldn't have uses!");
    275 
    276   GV->eraseFromParent();
    277   if (!M2Tors.empty()) {
    278     Constant *M2Init = GetTorInit(M2Tors);
    279     new GlobalVariable(*M2, M2Init->getType(), false,
    280                        GlobalValue::AppendingLinkage,
    281                        M2Init, GlobalName);
    282   }
    283 }
    284 
    285 
    286 /// SplitFunctionsOutOfModule - Given a module and a list of functions in the
    287 /// module, split the functions OUT of the specified module, and place them in
    288 /// the new module.
    289 Module *
    290 llvm::SplitFunctionsOutOfModule(Module *M,
    291                                 const std::vector<Function*> &F,
    292                                 ValueToValueMapTy &VMap) {
    293   // Make sure functions & globals are all external so that linkage
    294   // between the two modules will work.
    295   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
    296     I->setLinkage(GlobalValue::ExternalLinkage);
    297   for (Module::global_iterator I = M->global_begin(), E = M->global_end();
    298        I != E; ++I) {
    299     if (I->hasName() && I->getName()[0] == '\01')
    300       I->setName(I->getName().substr(1));
    301     I->setLinkage(GlobalValue::ExternalLinkage);
    302   }
    303 
    304   ValueToValueMapTy NewVMap;
    305   Module *New = CloneModule(M, NewVMap);
    306 
    307   // Remove the Test functions from the Safe module
    308   std::set<Function *> TestFunctions;
    309   for (unsigned i = 0, e = F.size(); i != e; ++i) {
    310     Function *TNOF = cast<Function>(VMap[F[i]]);
    311     DEBUG(errs() << "Removing function ");
    312     DEBUG(WriteAsOperand(errs(), TNOF, false));
    313     DEBUG(errs() << "\n");
    314     TestFunctions.insert(cast<Function>(NewVMap[TNOF]));
    315     DeleteFunctionBody(TNOF);       // Function is now external in this module!
    316   }
    317 
    318 
    319   // Remove the Safe functions from the Test module
    320   for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I)
    321     if (!TestFunctions.count(I))
    322       DeleteFunctionBody(I);
    323 
    324 
    325   // Try to split the global initializers evenly
    326   for (Module::global_iterator I = M->global_begin(), E = M->global_end();
    327        I != E; ++I) {
    328     GlobalVariable *GV = cast<GlobalVariable>(NewVMap[I]);
    329     if (Function *TestFn = globalInitUsesExternalBA(I)) {
    330       if (Function *SafeFn = globalInitUsesExternalBA(GV)) {
    331         errs() << "*** Error: when reducing functions, encountered "
    332                   "the global '";
    333         WriteAsOperand(errs(), GV, false);
    334         errs() << "' with an initializer that references blockaddresses "
    335                   "from safe function '" << SafeFn->getName()
    336                << "' and from test function '" << TestFn->getName() << "'.\n";
    337         exit(1);
    338       }
    339       I->setInitializer(0);  // Delete the initializer to make it external
    340     } else {
    341       // If we keep it in the safe module, then delete it in the test module
    342       GV->setInitializer(0);
    343     }
    344   }
    345 
    346   // Make sure that there is a global ctor/dtor array in both halves of the
    347   // module if they both have static ctor/dtor functions.
    348   SplitStaticCtorDtor("llvm.global_ctors", M, New, NewVMap);
    349   SplitStaticCtorDtor("llvm.global_dtors", M, New, NewVMap);
    350 
    351   return New;
    352 }
    353 
    354 //===----------------------------------------------------------------------===//
    355 // Basic Block Extraction Code
    356 //===----------------------------------------------------------------------===//
    357 
    358 /// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks
    359 /// into their own functions.  The only detail is that M is actually a module
    360 /// cloned from the one the BBs are in, so some mapping needs to be performed.
    361 /// If this operation fails for some reason (ie the implementation is buggy),
    362 /// this function should return null, otherwise it returns a new Module.
    363 Module *BugDriver::ExtractMappedBlocksFromModule(const
    364                                                  std::vector<BasicBlock*> &BBs,
    365                                                  Module *M) {
    366   sys::Path uniqueFilename(OutputPrefix + "-extractblocks");
    367   std::string ErrMsg;
    368   if (uniqueFilename.createTemporaryFileOnDisk(true, &ErrMsg)) {
    369     outs() << "*** Basic Block extraction failed!\n";
    370     errs() << "Error creating temporary file: " << ErrMsg << "\n";
    371     EmitProgressBitcode(M, "basicblockextractfail", true);
    372     return 0;
    373   }
    374   sys::RemoveFileOnSignal(uniqueFilename);
    375 
    376   std::string ErrorInfo;
    377   tool_output_file BlocksToNotExtractFile(uniqueFilename.c_str(), ErrorInfo);
    378   if (!ErrorInfo.empty()) {
    379     outs() << "*** Basic Block extraction failed!\n";
    380     errs() << "Error writing list of blocks to not extract: " << ErrorInfo
    381            << "\n";
    382     EmitProgressBitcode(M, "basicblockextractfail", true);
    383     return 0;
    384   }
    385   for (std::vector<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
    386        I != E; ++I) {
    387     BasicBlock *BB = *I;
    388     // If the BB doesn't have a name, give it one so we have something to key
    389     // off of.
    390     if (!BB->hasName()) BB->setName("tmpbb");
    391     BlocksToNotExtractFile.os() << BB->getParent()->getName() << " "
    392                                 << BB->getName() << "\n";
    393   }
    394   BlocksToNotExtractFile.os().close();
    395   if (BlocksToNotExtractFile.os().has_error()) {
    396     errs() << "Error writing list of blocks to not extract: " << ErrorInfo
    397            << "\n";
    398     EmitProgressBitcode(M, "basicblockextractfail", true);
    399     BlocksToNotExtractFile.os().clear_error();
    400     return 0;
    401   }
    402   BlocksToNotExtractFile.keep();
    403 
    404   std::string uniqueFN = "--extract-blocks-file=" + uniqueFilename.str();
    405   const char *ExtraArg = uniqueFN.c_str();
    406 
    407   std::vector<std::string> PI;
    408   PI.push_back("extract-blocks");
    409   Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg);
    410 
    411   uniqueFilename.eraseFromDisk(); // Free disk space
    412 
    413   if (Ret == 0) {
    414     outs() << "*** Basic Block extraction failed, please report a bug!\n";
    415     EmitProgressBitcode(M, "basicblockextractfail", true);
    416   }
    417   return Ret;
    418 }
    419