lib/Transforms/IPO/DeadArgumentElimination.cpp

   1 //===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
   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 pass deletes dead arguments from internal functions.  Dead argument
  11 // elimination removes arguments which are directly dead, as well as arguments
  12 // only passed into function calls as dead arguments of other functions.  This
  13 // pass also deletes dead arguments in a similar way.
  14 //
  15 // This pass is often useful as a cleanup pass to run after aggressive
  16 // interprocedural passes, which add possibly-dead arguments.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "deadargelim"
  21 #include "llvm/Transforms/IPO.h"
  22 #include "llvm/CallingConv.h"
  23 #include "llvm/Constant.h"
  24 #include "llvm/DerivedTypes.h"
  25 #include "llvm/Instructions.h"
  26 #include "llvm/IntrinsicInst.h"
  27 #include "llvm/Module.h"
  28 #include "llvm/Pass.h"
  29 #include "llvm/ParameterAttributes.h"
  30 #include "llvm/Support/CallSite.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/Support/Compiler.h"
  34 #include <set>
  35 using namespace llvm;
  36
  37 STATISTIC(NumArgumentsEliminated, "Number of unread args removed");
  38 STATISTIC(NumRetValsEliminated  , "Number of unused return values removed");
  39
  40 namespace {
  41   /// DAE - The dead argument elimination pass.
  42   ///
  43   class VISIBILITY_HIDDEN DAE : public ModulePass {
  44     /// Liveness enum - During our initial pass over the program, we determine
  45     /// that things are either definately alive, definately dead, or in need of
  46     /// interprocedural analysis (MaybeLive).
  47     ///
  48     enum Liveness { Live, MaybeLive, Dead };
  49
  50     /// LiveArguments, MaybeLiveArguments, DeadArguments - These sets contain
  51     /// all of the arguments in the program.  The Dead set contains arguments
  52     /// which are completely dead (never used in the function).  The MaybeLive
  53     /// set contains arguments which are only passed into other function calls,
  54     /// thus may be live and may be dead.  The Live set contains arguments which
  55     /// are known to be alive.
  56     ///
  57     std::set<Argument*> DeadArguments, MaybeLiveArguments, LiveArguments;
  58
  59     /// DeadRetVal, MaybeLiveRetVal, LifeRetVal - These sets contain all of the
  60     /// functions in the program.  The Dead set contains functions whose return
  61     /// value is known to be dead.  The MaybeLive set contains functions whose
  62     /// return values are only used by return instructions, and the Live set
  63     /// contains functions whose return values are used, functions that are
  64     /// external, and functions that already return void.
  65     ///
  66     std::set<Function*> DeadRetVal, MaybeLiveRetVal, LiveRetVal;
  67
  68     /// InstructionsToInspect - As we mark arguments and return values
  69     /// MaybeLive, we keep track of which instructions could make the values
  70     /// live here.  Once the entire program has had the return value and
  71     /// arguments analyzed, this set is scanned to promote the MaybeLive objects
  72     /// to be Live if they really are used.
  73     std::vector<Instruction*> InstructionsToInspect;
  74
  75     /// CallSites - Keep track of the call sites of functions that have
  76     /// MaybeLive arguments or return values.
  77     std::multimap<Function*, CallSite> CallSites;
  78
  79   public:
  80     static char ID; // Pass identification, replacement for typeid
  81     DAE() : ModulePass((intptr_t)&ID) {}
  82     bool runOnModule(Module &M);
  83
  84     virtual bool ShouldHackArguments() const { return false; }
  85
  86   private:
  87     Liveness getArgumentLiveness(const Argument &A);
  88     bool isMaybeLiveArgumentNowLive(Argument *Arg);
  89
  90     bool DeleteDeadVarargs(Function &Fn);
  91     void SurveyFunction(Function &Fn);
  92
  93     void MarkArgumentLive(Argument *Arg);
  94     void MarkRetValLive(Function *F);
  95     void MarkReturnInstArgumentLive(ReturnInst *RI);
  96
  97     void RemoveDeadArgumentsFromFunction(Function *F);
  98   };
  99   char DAE::ID = 0;
 100   RegisterPass<DAE> X("deadargelim", "Dead Argument Elimination");
 101
 102   /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but
 103   /// deletes arguments to functions which are external.  This is only for use
 104   /// by bugpoint.
 105   struct DAH : public DAE {
 106     static char ID;
 107     virtual bool ShouldHackArguments() const { return true; }
 108   };
 109   char DAH::ID = 0;
 110   RegisterPass<DAH> Y("deadarghaX0r",
 111                       "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)");
 112 }
 113
 114 /// createDeadArgEliminationPass - This pass removes arguments from functions
 115 /// which are not used by the body of the function.
 116 ///
 117 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }
 118 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); }
 119
 120 /// DeleteDeadVarargs - If this is an function that takes a ... list, and if
 121 /// llvm.vastart is never called, the varargs list is dead for the function.
 122 bool DAE::DeleteDeadVarargs(Function &Fn) {
 123   assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!");
 124   if (Fn.isDeclaration() || !Fn.hasInternalLinkage()) return false;
 125
 126   // Ensure that the function is only directly called.
 127   for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end(); I != E; ++I) {
 128     // If this use is anything other than a call site, give up.
 129     CallSite CS = CallSite::get(*I);
 130     Instruction *TheCall = CS.getInstruction();
 131     if (!TheCall) return false;   // Not a direct call site?
 132
 133     // The addr of this function is passed to the call.
 134     if (I.getOperandNo() != 0) return false;
 135   }
 136
 137   // Okay, we know we can transform this function if safe.  Scan its body
 138   // looking for calls to llvm.vastart.
 139   for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
 140     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
 141       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 142         if (II->getIntrinsicID() == Intrinsic::vastart)
 143           return false;
 144       }
 145     }
 146   }
 147
 148   // If we get here, there are no calls to llvm.vastart in the function body,
 149   // remove the "..." and adjust all the calls.
 150
 151   // Start by computing a new prototype for the function, which is the same as
 152   // the old function, but has fewer arguments.
 153   const FunctionType *FTy = Fn.getFunctionType();
 154   std::vector<const Type*> Params(FTy->param_begin(), FTy->param_end());
 155   FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false);
 156   unsigned NumArgs = Params.size();
 157
 158   // Create the new function body and insert it into the module...
 159   Function *NF = new Function(NFTy, Fn.getLinkage());
 160   NF->setCallingConv(Fn.getCallingConv());
 161   NF->setParamAttrs(Fn.getParamAttrs());
 162   if (Fn.hasCollector())
 163     NF->setCollector(Fn.getCollector());
 164   Fn.getParent()->getFunctionList().insert(&Fn, NF);
 165   NF->takeName(&Fn);
 166
 167   // Loop over all of the callers of the function, transforming the call sites
 168   // to pass in a smaller number of arguments into the new function.
 169   //
 170   std::vector<Value*> Args;
 171   while (!Fn.use_empty()) {
 172     CallSite CS = CallSite::get(Fn.use_back());
 173     Instruction *Call = CS.getInstruction();
 174
 175     // Pass all the same arguments.
 176     Args.assign(CS.arg_begin(), CS.arg_begin()+NumArgs);
 177
 178     // Drop any attributes that were on the vararg arguments.
 179     const ParamAttrsList *PAL = CS.getParamAttrs();
 180     if (PAL && PAL->getParamIndex(PAL->size() - 1) > NumArgs) {
 181       ParamAttrsVector ParamAttrsVec;
 182       for (unsigned i = 0; PAL->getParamIndex(i) <= NumArgs; ++i) {
 183         ParamAttrsWithIndex PAWI;
 184         PAWI = ParamAttrsWithIndex::get(PAL->getParamIndex(i),
 185                                         PAL->getParamAttrsAtIndex(i));
 186         ParamAttrsVec.push_back(PAWI);
 187       }
 188       PAL = ParamAttrsList::get(ParamAttrsVec);
 189     }
 190
 191     Instruction *New;
 192     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
 193       New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(),
 194                            Args.begin(), Args.end(), "", Call);
 195       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
 196       cast<InvokeInst>(New)->setParamAttrs(PAL);
 197     } else {
 198       New = new CallInst(NF, Args.begin(), Args.end(), "", Call);
 199       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
 200       cast<CallInst>(New)->setParamAttrs(PAL);
 201       if (cast<CallInst>(Call)->isTailCall())
 202         cast<CallInst>(New)->setTailCall();
 203     }
 204     Args.clear();
 205
 206     if (!Call->use_empty())
 207       Call->replaceAllUsesWith(New);
 208
 209     New->takeName(Call);
 210
 211     // Finally, remove the old call from the program, reducing the use-count of
 212     // F.
 213     Call->eraseFromParent();
 214   }
 215
 216   // Since we have now created the new function, splice the body of the old
 217   // function right into the new function, leaving the old rotting hulk of the
 218   // function empty.
 219   NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList());
 220
 221   // Loop over the argument list, transfering uses of the old arguments over to
 222   // the new arguments, also transfering over the names as well.  While we're at
 223   // it, remove the dead arguments from the DeadArguments list.
 224   //
 225   for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(),
 226        I2 = NF->arg_begin(); I != E; ++I, ++I2) {
 227     // Move the name and users over to the new version.
 228     I->replaceAllUsesWith(I2);
 229     I2->takeName(I);
 230   }
 231
 232   // Finally, nuke the old function.
 233   Fn.eraseFromParent();
 234   return true;
 235 }
 236
 237
 238 static inline bool CallPassesValueThoughVararg(Instruction *Call,
 239                                                const Value *Arg) {
 240   CallSite CS = CallSite::get(Call);
 241   const Type *CalledValueTy = CS.getCalledValue()->getType();
 242   const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType();
 243   unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams();
 244   for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs;
 245        AI != CS.arg_end(); ++AI)
 246     if (AI->get() == Arg)
 247       return true;
 248   return false;
 249 }
 250
 251 // getArgumentLiveness - Inspect an argument, determining if is known Live
 252 // (used in a computation), MaybeLive (only passed as an argument to a call), or
 253 // Dead (not used).
 254 DAE::Liveness DAE::getArgumentLiveness(const Argument &A) {
 255   const Function *F = A.getParent();
 256
 257   // If this is the return value of a struct function, it's not really dead.
 258   if (F->isStructReturn() && &*(F->arg_begin()) == &A)
 259     return Live;
 260
 261   if (A.use_empty())  // First check, directly dead?
 262     return Dead;
 263
 264   // Scan through all of the uses, looking for non-argument passing uses.
 265   for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) {
 266     // Return instructions do not immediately effect liveness.
 267     if (isa<ReturnInst>(*I))
 268       continue;
 269
 270     CallSite CS = CallSite::get(const_cast<User*>(*I));
 271     if (!CS.getInstruction()) {
 272       // If its used by something that is not a call or invoke, it's alive!
 273       return Live;
 274     }
 275     // If it's an indirect call, mark it alive...
 276     Function *Callee = CS.getCalledFunction();
 277     if (!Callee) return Live;
 278
 279     // Check to see if it's passed through a va_arg area: if so, we cannot
 280     // remove it.
 281     if (CallPassesValueThoughVararg(CS.getInstruction(), &A))
 282       return Live;   // If passed through va_arg area, we cannot remove it
 283   }
 284
 285   return MaybeLive;  // It must be used, but only as argument to a function
 286 }
 287
 288
 289 // SurveyFunction - This performs the initial survey of the specified function,
 290 // checking out whether or not it uses any of its incoming arguments or whether
 291 // any callers use the return value.  This fills in the
 292 // (Dead|MaybeLive|Live)(Arguments|RetVal) sets.
 293 //
 294 // We consider arguments of non-internal functions to be intrinsically alive as
 295 // well as arguments to functions which have their "address taken".
 296 //
 297 void DAE::SurveyFunction(Function &F) {
 298   bool FunctionIntrinsicallyLive = false;
 299   Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead;
 300
 301   if (!F.hasInternalLinkage() &&
 302       (!ShouldHackArguments() || F.isIntrinsic()))
 303     FunctionIntrinsicallyLive = true;
 304   else
 305     for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
 306       // If this use is anything other than a call site, the function is alive.
 307       CallSite CS = CallSite::get(*I);
 308       Instruction *TheCall = CS.getInstruction();
 309       if (!TheCall) {   // Not a direct call site?
 310         FunctionIntrinsicallyLive = true;
 311         break;
 312       }
 313
 314       // Check to see if the return value is used...
 315       if (RetValLiveness != Live)
 316         for (Value::use_iterator I = TheCall->use_begin(),
 317                E = TheCall->use_end(); I != E; ++I)
 318           if (isa<ReturnInst>(cast<Instruction>(*I))) {
 319             RetValLiveness = MaybeLive;
 320           } else if (isa<CallInst>(cast<Instruction>(*I)) ||
 321                      isa<InvokeInst>(cast<Instruction>(*I))) {
 322             if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) ||
 323                 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) {
 324               RetValLiveness = Live;
 325               break;
 326             } else {
 327               RetValLiveness = MaybeLive;
 328             }
 329           } else {
 330             RetValLiveness = Live;
 331             break;
 332           }
 333
 334       // If the function is PASSED IN as an argument, its address has been taken
 335       for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
 336            AI != E; ++AI)
 337         if (AI->get() == &F) {
 338           FunctionIntrinsicallyLive = true;
 339           break;
 340         }
 341       if (FunctionIntrinsicallyLive) break;
 342     }
 343
 344   if (FunctionIntrinsicallyLive) {
 345     DOUT << "  Intrinsically live fn: " << F.getName() << "\n";
 346     for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
 347          AI != E; ++AI)
 348       LiveArguments.insert(AI);
 349     LiveRetVal.insert(&F);
 350     return;
 351   }
 352
 353   switch (RetValLiveness) {
 354   case Live:      LiveRetVal.insert(&F); break;
 355   case MaybeLive: MaybeLiveRetVal.insert(&F); break;
 356   case Dead:      DeadRetVal.insert(&F); break;
 357   }
 358
 359   DOUT << "  Inspecting args for fn: " << F.getName() << "\n";
 360
 361   // If it is not intrinsically alive, we know that all users of the
 362   // function are call sites.  Mark all of the arguments live which are
 363   // directly used, and keep track of all of the call sites of this function
 364   // if there are any arguments we assume that are dead.
 365   //
 366   bool AnyMaybeLiveArgs = false;
 367   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
 368        AI != E; ++AI)
 369     switch (getArgumentLiveness(*AI)) {
 370     case Live:
 371       DOUT << "    Arg live by use: " << AI->getName() << "\n";
 372       LiveArguments.insert(AI);
 373       break;
 374     case Dead:
 375       DOUT << "    Arg definitely dead: " << AI->getName() <<"\n";
 376       DeadArguments.insert(AI);
 377       break;
 378     case MaybeLive:
 379       DOUT << "    Arg only passed to calls: " << AI->getName() << "\n";
 380       AnyMaybeLiveArgs = true;
 381       MaybeLiveArguments.insert(AI);
 382       break;
 383     }
 384
 385   // If there are any "MaybeLive" arguments, we need to check callees of
 386   // this function when/if they become alive.  Record which functions are
 387   // callees...
 388   if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive)
 389     for (Value::use_iterator I = F.use_begin(), E = F.use_end();
 390          I != E; ++I) {
 391       if (AnyMaybeLiveArgs)
 392         CallSites.insert(std::make_pair(&F, CallSite::get(*I)));
 393
 394       if (RetValLiveness == MaybeLive)
 395         for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 396              UI != E; ++UI)
 397           InstructionsToInspect.push_back(cast<Instruction>(*UI));
 398     }
 399 }
 400
 401 // isMaybeLiveArgumentNowLive - Check to see if Arg is alive.  At this point, we
 402 // know that the only uses of Arg are to be passed in as an argument to a
 403 // function call or return.  Check to see if the formal argument passed in is in
 404 // the LiveArguments set.  If so, return true.
 405 //
 406 bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) {
 407   for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){
 408     if (isa<ReturnInst>(*I)) {
 409       if (LiveRetVal.count(Arg->getParent())) return true;
 410       continue;
 411     }
 412
 413     CallSite CS = CallSite::get(*I);
 414
 415     // We know that this can only be used for direct calls...
 416     Function *Callee = CS.getCalledFunction();
 417
 418     // Loop over all of the arguments (because Arg may be passed into the call
 419     // multiple times) and check to see if any are now alive...
 420     CallSite::arg_iterator CSAI = CS.arg_begin();
 421     for (Function::arg_iterator AI = Callee->arg_begin(), E = Callee->arg_end();
 422          AI != E; ++AI, ++CSAI)
 423       // If this is the argument we are looking for, check to see if it's alive
 424       if (*CSAI == Arg && LiveArguments.count(AI))
 425         return true;
 426   }
 427   return false;
 428 }
 429
 430 /// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive.
 431 /// Mark it live in the specified sets and recursively mark arguments in callers
 432 /// live that are needed to pass in a value.
 433 ///
 434 void DAE::MarkArgumentLive(Argument *Arg) {
 435   std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg);
 436   if (It == MaybeLiveArguments.end() || *It != Arg) return;
 437
 438   DOUT << "  MaybeLive argument now live: " << Arg->getName() <<"\n";
 439   MaybeLiveArguments.erase(It);
 440   LiveArguments.insert(Arg);
 441
 442   // Loop over all of the call sites of the function, making any arguments
 443   // passed in to provide a value for this argument live as necessary.
 444   //
 445   Function *Fn = Arg->getParent();
 446   unsigned ArgNo = std::distance(Fn->arg_begin(), Function::arg_iterator(Arg));
 447
 448   std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn);
 449   for (; I != CallSites.end() && I->first == Fn; ++I) {
 450     CallSite CS = I->second;
 451     Value *ArgVal = *(CS.arg_begin()+ArgNo);
 452     if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) {
 453       MarkArgumentLive(ActualArg);
 454     } else {
 455       // If the value passed in at this call site is a return value computed by
 456       // some other call site, make sure to mark the return value at the other
 457       // call site as being needed.
 458       CallSite ArgCS = CallSite::get(ArgVal);
 459       if (ArgCS.getInstruction())
 460         if (Function *Fn = ArgCS.getCalledFunction())
 461           MarkRetValLive(Fn);
 462     }
 463   }
 464 }
 465
 466 /// MarkArgumentLive - The MaybeLive return value for the specified function is
 467 /// now known to be alive.  Propagate this fact to the return instructions which
 468 /// produce it.
 469 void DAE::MarkRetValLive(Function *F) {
 470   assert(F && "Shame shame, we can't have null pointers here!");
 471
 472   // Check to see if we already knew it was live
 473   std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F);
 474   if (I == MaybeLiveRetVal.end() || *I != F) return;  // It's already alive!
 475
 476   DOUT << "  MaybeLive retval now live: " << F->getName() << "\n";
 477
 478   MaybeLiveRetVal.erase(I);
 479   LiveRetVal.insert(F);        // It is now known to be live!
 480
 481   // Loop over all of the functions, noticing that the return value is now live.
 482   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 483     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
 484       MarkReturnInstArgumentLive(RI);
 485 }
 486
 487 void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) {
 488   Value *Op = RI->getOperand(0);
 489   if (Argument *A = dyn_cast<Argument>(Op)) {
 490     MarkArgumentLive(A);
 491   } else if (CallInst *CI = dyn_cast<CallInst>(Op)) {
 492     if (Function *F = CI->getCalledFunction())
 493       MarkRetValLive(F);
 494   } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
 495     if (Function *F = II->getCalledFunction())
 496       MarkRetValLive(F);
 497   }
 498 }
 499
 500 // RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as
 501 // specified by the DeadArguments list.  Transform the function and all of the
 502 // callees of the function to not have these arguments.
 503 //
 504 void DAE::RemoveDeadArgumentsFromFunction(Function *F) {
 505   // Start by computing a new prototype for the function, which is the same as
 506   // the old function, but has fewer arguments.
 507   const FunctionType *FTy = F->getFunctionType();
 508   std::vector<const Type*> Params;
 509
 510   // Set up to build a new list of parameter attributes
 511   ParamAttrsVector ParamAttrsVec;
 512   const ParamAttrsList *PAL = F->getParamAttrs();
 513
 514   // The existing function return attributes.
 515   uint16_t RAttrs = PAL ? PAL->getParamAttrs(0) : 0;
 516
 517   // Make the function return void if the return value is dead.
 518   const Type *RetTy = FTy->getReturnType();
 519   if (DeadRetVal.count(F)) {
 520     RetTy = Type::VoidTy;
 521     RAttrs &= ~ParamAttr::typeIncompatible(RetTy);
 522     DeadRetVal.erase(F);
 523   }
 524
 525   if (RAttrs)
 526     ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs));
 527
 528   // Construct the new parameter list from non-dead arguments. Also construct
 529   // a new set of parameter attributes to correspond.
 530   unsigned index = 1;
 531   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
 532        ++I, ++index)
 533     if (!DeadArguments.count(I)) {
 534       Params.push_back(I->getType());
 535       uint16_t Attrs = PAL ? PAL->getParamAttrs(index) : 0;
 536       if (Attrs)
 537         ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Params.size(), Attrs));
 538     }
 539
 540   // Reconstruct the ParamAttrsList based on the vector we constructed.
 541   PAL = ParamAttrsList::get(ParamAttrsVec);
 542
 543   // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which
 544   // have zero fixed arguments.
 545   //
 546   bool ExtraArgHack = false;
 547   if (Params.empty() && FTy->isVarArg()) {
 548     ExtraArgHack = true;
 549     Params.push_back(Type::Int32Ty);
 550   }
 551
 552   // Create the new function type based on the recomputed parameters.
 553   FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg());
 554
 555   // Create the new function body and insert it into the module...
 556   Function *NF = new Function(NFTy, F->getLinkage());
 557   NF->setCallingConv(F->getCallingConv());
 558   NF->setParamAttrs(PAL);
 559   if (F->hasCollector())
 560     NF->setCollector(F->getCollector());
 561   F->getParent()->getFunctionList().insert(F, NF);
 562   NF->takeName(F);
 563
 564   // Loop over all of the callers of the function, transforming the call sites
 565   // to pass in a smaller number of arguments into the new function.
 566   //
 567   std::vector<Value*> Args;
 568   while (!F->use_empty()) {
 569     CallSite CS = CallSite::get(F->use_back());
 570     Instruction *Call = CS.getInstruction();
 571     ParamAttrsVec.clear();
 572     PAL = CS.getParamAttrs();
 573
 574     // The call return attributes.
 575     uint16_t RAttrs = PAL ? PAL->getParamAttrs(0) : 0;
 576     // Adjust in case the function was changed to return void.
 577     RAttrs &= ~ParamAttr::typeIncompatible(NF->getReturnType());
 578     if (RAttrs)
 579       ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs));
 580
 581     // Loop over the operands, deleting dead ones...
 582     CallSite::arg_iterator AI = CS.arg_begin();
 583     index = 1;
 584     for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
 585          I != E; ++I, ++AI, ++index)
 586       if (!DeadArguments.count(I)) {    // Remove operands for dead arguments
 587         Args.push_back(*AI);
 588         uint16_t Attrs = PAL ? PAL->getParamAttrs(index) : 0;
 589         if (Attrs)
 590           ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs));
 591       }
 592
 593     if (ExtraArgHack)
 594       Args.push_back(UndefValue::get(Type::Int32Ty));
 595
 596     // Push any varargs arguments on the list. Don't forget their attributes.
 597     for (; AI != CS.arg_end(); ++AI) {
 598       Args.push_back(*AI);
 599       uint16_t Attrs = PAL ? PAL->getParamAttrs(index++) : 0;
 600       if (Attrs)
 601         ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs));
 602     }
 603
 604     // Reconstruct the ParamAttrsList based on the vector we constructed.
 605     PAL = ParamAttrsList::get(ParamAttrsVec);
 606
 607     Instruction *New;
 608     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
 609       New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(),
 610                            Args.begin(), Args.end(), "", Call);
 611       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
 612       cast<InvokeInst>(New)->setParamAttrs(PAL);
 613     } else {
 614       New = new CallInst(NF, Args.begin(), Args.end(), "", Call);
 615       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
 616       cast<CallInst>(New)->setParamAttrs(PAL);
 617       if (cast<CallInst>(Call)->isTailCall())
 618         cast<CallInst>(New)->setTailCall();
 619     }
 620     Args.clear();
 621
 622     if (!Call->use_empty()) {
 623       if (New->getType() == Type::VoidTy)
 624         Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
 625       else {
 626         Call->replaceAllUsesWith(New);
 627         New->takeName(Call);
 628       }
 629     }
 630
 631     // Finally, remove the old call from the program, reducing the use-count of
 632     // F.
 633     Call->getParent()->getInstList().erase(Call);
 634   }
 635
 636   // Since we have now created the new function, splice the body of the old
 637   // function right into the new function, leaving the old rotting hulk of the
 638   // function empty.
 639   NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
 640
 641   // Loop over the argument list, transfering uses of the old arguments over to
 642   // the new arguments, also transfering over the names as well.  While we're at
 643   // it, remove the dead arguments from the DeadArguments list.
 644   //
 645   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
 646          I2 = NF->arg_begin();
 647        I != E; ++I)
 648     if (!DeadArguments.count(I)) {
 649       // If this is a live argument, move the name and users over to the new
 650       // version.
 651       I->replaceAllUsesWith(I2);
 652       I2->takeName(I);
 653       ++I2;
 654     } else {
 655       // If this argument is dead, replace any uses of it with null constants
 656       // (these are guaranteed to only be operands to call instructions which
 657       // will later be simplified).
 658       I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
 659       DeadArguments.erase(I);
 660     }
 661
 662   // If we change the return value of the function we must rewrite any return
 663   // instructions.  Check this now.
 664   if (F->getReturnType() != NF->getReturnType())
 665     for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB)
 666       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
 667         new ReturnInst(0, RI);
 668         BB->getInstList().erase(RI);
 669       }
 670
 671   // Now that the old function is dead, delete it.
 672   F->getParent()->getFunctionList().erase(F);
 673 }
 674
 675 bool DAE::runOnModule(Module &M) {
 676   bool Changed = false;
 677   // First pass: Do a simple check to see if any functions can have their "..."
 678   // removed.  We can do this if they never call va_start.  This loop cannot be
 679   // fused with the next loop, because deleting a function invalidates
 680   // information computed while surveying other functions.
 681   DOUT << "DAE - Deleting dead varargs\n";
 682   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
 683     Function &F = *I++;
 684     if (F.getFunctionType()->isVarArg())
 685       Changed |= DeleteDeadVarargs(F);
 686   }
 687
 688   // Second phase:loop through the module, determining which arguments are live.
 689   // We assume all arguments are dead unless proven otherwise (allowing us to
 690   // determine that dead arguments passed into recursive functions are dead).
 691   //
 692   DOUT << "DAE - Determining liveness\n";
 693   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 694     SurveyFunction(*I);
 695
 696   // Loop over the instructions to inspect, propagating liveness among arguments
 697   // and return values which are MaybeLive.
 698   while (!InstructionsToInspect.empty()) {
 699     Instruction *I = InstructionsToInspect.back();
 700     InstructionsToInspect.pop_back();
 701
 702     if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) {
 703       // For return instructions, we just have to check to see if the return
 704       // value for the current function is known now to be alive.  If so, any
 705       // arguments used by it are now alive, and any call instruction return
 706       // value is alive as well.
 707       if (LiveRetVal.count(RI->getParent()->getParent()))
 708         MarkReturnInstArgumentLive(RI);
 709
 710     } else {
 711       CallSite CS = CallSite::get(I);
 712       assert(CS.getInstruction() && "Unknown instruction for the I2I list!");
 713
 714       Function *Callee = CS.getCalledFunction();
 715
 716       // If we found a call or invoke instruction on this list, that means that
 717       // an argument of the function is a call instruction.  If the argument is
 718       // live, then the return value of the called instruction is now live.
 719       //
 720       CallSite::arg_iterator AI = CS.arg_begin();  // ActualIterator
 721       for (Function::arg_iterator FI = Callee->arg_begin(),
 722              E = Callee->arg_end(); FI != E; ++AI, ++FI) {
 723         // If this argument is another call...
 724         CallSite ArgCS = CallSite::get(*AI);
 725         if (ArgCS.getInstruction() && LiveArguments.count(FI))
 726           if (Function *Callee = ArgCS.getCalledFunction())
 727             MarkRetValLive(Callee);
 728       }
 729     }
 730   }
 731
 732   // Now we loop over all of the MaybeLive arguments, promoting them to be live
 733   // arguments if one of the calls that uses the arguments to the calls they are
 734   // passed into requires them to be live.  Of course this could make other
 735   // arguments live, so process callers recursively.
 736   //
 737   // Because elements can be removed from the MaybeLiveArguments set, copy it to
 738   // a temporary vector.
 739   //
 740   std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(),
 741                                     MaybeLiveArguments.end());
 742   for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) {
 743     Argument *MLA = TmpArgList[i];
 744     if (MaybeLiveArguments.count(MLA) &&
 745         isMaybeLiveArgumentNowLive(MLA))
 746       MarkArgumentLive(MLA);
 747   }
 748
 749   // Recover memory early...
 750   CallSites.clear();
 751
 752   // At this point, we know that all arguments in DeadArguments and
 753   // MaybeLiveArguments are dead.  If the two sets are empty, there is nothing
 754   // to do.
 755   if (MaybeLiveArguments.empty() && DeadArguments.empty() &&
 756       MaybeLiveRetVal.empty() && DeadRetVal.empty())
 757     return Changed;
 758
 759   // Otherwise, compact into one set, and start eliminating the arguments from
 760   // the functions.
 761   DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end());
 762   MaybeLiveArguments.clear();
 763   DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end());
 764   MaybeLiveRetVal.clear();
 765
 766   LiveArguments.clear();
 767   LiveRetVal.clear();
 768
 769   NumArgumentsEliminated += DeadArguments.size();
 770   NumRetValsEliminated   += DeadRetVal.size();
 771   while (!DeadArguments.empty())
 772     RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent());
 773
 774   while (!DeadRetVal.empty())
 775     RemoveDeadArgumentsFromFunction(*DeadRetVal.begin());
 776   return true;
 777 }