lib/Transforms/IPO/DeadArgumentElimination.cpp

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