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