LLVM API Documentation

DeadArgumentElimination.cpp

Go to the documentation of this file.
00001 //===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass deletes dead arguments from internal functions.  Dead argument
00011 // elimination removes arguments which are directly dead, as well as arguments
00012 // only passed into function calls as dead arguments of other functions.  This
00013 // pass also deletes dead arguments in a similar way.
00014 //
00015 // This pass is often useful as a cleanup pass to run after aggressive
00016 // interprocedural passes, which add possibly-dead arguments.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #define DEBUG_TYPE "deadargelim"
00021 #include "llvm/Transforms/IPO.h"
00022 #include "llvm/CallingConv.h"
00023 #include "llvm/Constant.h"
00024 #include "llvm/DerivedTypes.h"
00025 #include "llvm/Instructions.h"
00026 #include "llvm/Module.h"
00027 #include "llvm/Pass.h"
00028 #include "llvm/Support/CallSite.h"
00029 #include "llvm/Support/Debug.h"
00030 #include "llvm/ADT/Statistic.h"
00031 #include <iostream>
00032 #include <set>
00033 using namespace llvm;
00034 
00035 namespace {
00036   Statistic<> NumArgumentsEliminated("deadargelim",
00037                                      "Number of unread args removed");
00038   Statistic<> NumRetValsEliminated("deadargelim",
00039                                    "Number of unused return values removed");
00040 
00041   /// DAE - The dead argument elimination pass.
00042   ///
00043   class DAE : public ModulePass {
00044     /// Liveness enum - During our initial pass over the program, we determine
00045     /// that things are either definately alive, definately dead, or in need of
00046     /// interprocedural analysis (MaybeLive).
00047     ///
00048     enum Liveness { Live, MaybeLive, Dead };
00049 
00050     /// LiveArguments, MaybeLiveArguments, DeadArguments - These sets contain
00051     /// all of the arguments in the program.  The Dead set contains arguments
00052     /// which are completely dead (never used in the function).  The MaybeLive
00053     /// set contains arguments which are only passed into other function calls,
00054     /// thus may be live and may be dead.  The Live set contains arguments which
00055     /// are known to be alive.
00056     ///
00057     std::set<Argument*> DeadArguments, MaybeLiveArguments, LiveArguments;
00058 
00059     /// DeadRetVal, MaybeLiveRetVal, LifeRetVal - These sets contain all of the
00060     /// functions in the program.  The Dead set contains functions whose return
00061     /// value is known to be dead.  The MaybeLive set contains functions whose
00062     /// return values are only used by return instructions, and the Live set
00063     /// contains functions whose return values are used, functions that are
00064     /// external, and functions that already return void.
00065     ///
00066     std::set<Function*> DeadRetVal, MaybeLiveRetVal, LiveRetVal;
00067 
00068     /// InstructionsToInspect - As we mark arguments and return values
00069     /// MaybeLive, we keep track of which instructions could make the values
00070     /// live here.  Once the entire program has had the return value and
00071     /// arguments analyzed, this set is scanned to promote the MaybeLive objects
00072     /// to be Live if they really are used.
00073     std::vector<Instruction*> InstructionsToInspect;
00074 
00075     /// CallSites - Keep track of the call sites of functions that have
00076     /// MaybeLive arguments or return values.
00077     std::multimap<Function*, CallSite> CallSites;
00078 
00079   public:
00080     bool runOnModule(Module &M);
00081 
00082     virtual bool ShouldHackArguments() const { return false; }
00083 
00084   private:
00085     Liveness getArgumentLiveness(const Argument &A);
00086     bool isMaybeLiveArgumentNowLive(Argument *Arg);
00087 
00088     void SurveyFunction(Function &Fn);
00089 
00090     void MarkArgumentLive(Argument *Arg);
00091     void MarkRetValLive(Function *F);
00092     void MarkReturnInstArgumentLive(ReturnInst *RI);
00093 
00094     void RemoveDeadArgumentsFromFunction(Function *F);
00095   };
00096   RegisterOpt<DAE> X("deadargelim", "Dead Argument Elimination");
00097 
00098   /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but
00099   /// deletes arguments to functions which are external.  This is only for use
00100   /// by bugpoint.
00101   struct DAH : public DAE {
00102     virtual bool ShouldHackArguments() const { return true; }
00103   };
00104   RegisterPass<DAH> Y("deadarghaX0r",
00105                       "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)");
00106 }
00107 
00108 /// createDeadArgEliminationPass - This pass removes arguments from functions
00109 /// which are not used by the body of the function.
00110 ///
00111 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }
00112 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); }
00113 
00114 static inline bool CallPassesValueThoughVararg(Instruction *Call,
00115                                                const Value *Arg) {
00116   CallSite CS = CallSite::get(Call);
00117   const Type *CalledValueTy = CS.getCalledValue()->getType();
00118   const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType();
00119   unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams();
00120   for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs;
00121        AI != CS.arg_end(); ++AI)
00122     if (AI->get() == Arg)
00123       return true;
00124   return false;
00125 }
00126 
00127 // getArgumentLiveness - Inspect an argument, determining if is known Live
00128 // (used in a computation), MaybeLive (only passed as an argument to a call), or
00129 // Dead (not used).
00130 DAE::Liveness DAE::getArgumentLiveness(const Argument &A) {
00131   // If this is the return value of a csret function, it's not really dead.
00132   if (A.getParent()->getCallingConv() == CallingConv::CSRet &&
00133       &*A.getParent()->arg_begin() == &A)
00134     return Live;
00135   
00136   if (A.use_empty())  // First check, directly dead?
00137     return Dead;
00138 
00139   // Scan through all of the uses, looking for non-argument passing uses.
00140   for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) {
00141     // Return instructions do not immediately effect liveness.
00142     if (isa<ReturnInst>(*I))
00143       continue;
00144 
00145     CallSite CS = CallSite::get(const_cast<User*>(*I));
00146     if (!CS.getInstruction()) {
00147       // If its used by something that is not a call or invoke, it's alive!
00148       return Live;
00149     }
00150     // If it's an indirect call, mark it alive...
00151     Function *Callee = CS.getCalledFunction();
00152     if (!Callee) return Live;
00153 
00154     // Check to see if it's passed through a va_arg area: if so, we cannot
00155     // remove it.
00156     if (CallPassesValueThoughVararg(CS.getInstruction(), &A))
00157       return Live;   // If passed through va_arg area, we cannot remove it
00158   }
00159 
00160   return MaybeLive;  // It must be used, but only as argument to a function
00161 }
00162 
00163 
00164 // SurveyFunction - This performs the initial survey of the specified function,
00165 // checking out whether or not it uses any of its incoming arguments or whether
00166 // any callers use the return value.  This fills in the
00167 // (Dead|MaybeLive|Live)(Arguments|RetVal) sets.
00168 //
00169 // We consider arguments of non-internal functions to be intrinsically alive as
00170 // well as arguments to functions which have their "address taken".
00171 //
00172 void DAE::SurveyFunction(Function &F) {
00173   bool FunctionIntrinsicallyLive = false;
00174   Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead;
00175 
00176   if (!F.hasInternalLinkage() &&
00177       (!ShouldHackArguments() || F.getIntrinsicID()))
00178     FunctionIntrinsicallyLive = true;
00179   else
00180     for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
00181       // If this use is anything other than a call site, the function is alive.
00182       CallSite CS = CallSite::get(*I);
00183       Instruction *TheCall = CS.getInstruction();
00184       if (!TheCall) {   // Not a direct call site?
00185         FunctionIntrinsicallyLive = true;
00186         break;
00187       }
00188 
00189       // Check to see if the return value is used...
00190       if (RetValLiveness != Live)
00191         for (Value::use_iterator I = TheCall->use_begin(),
00192                E = TheCall->use_end(); I != E; ++I)
00193           if (isa<ReturnInst>(cast<Instruction>(*I))) {
00194             RetValLiveness = MaybeLive;
00195           } else if (isa<CallInst>(cast<Instruction>(*I)) ||
00196                      isa<InvokeInst>(cast<Instruction>(*I))) {
00197             if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) ||
00198                 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) {
00199               RetValLiveness = Live;
00200               break;
00201             } else {
00202               RetValLiveness = MaybeLive;
00203             }
00204           } else {
00205             RetValLiveness = Live;
00206             break;
00207           }
00208 
00209       // If the function is PASSED IN as an argument, its address has been taken
00210       for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
00211            AI != E; ++AI)
00212         if (AI->get() == &F) {
00213           FunctionIntrinsicallyLive = true;
00214           break;
00215         }
00216       if (FunctionIntrinsicallyLive) break;
00217     }
00218 
00219   if (FunctionIntrinsicallyLive) {
00220     DEBUG(std::cerr << "  Intrinsically live fn: " << F.getName() << "\n");
00221     for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
00222          AI != E; ++AI)
00223       LiveArguments.insert(AI);
00224     LiveRetVal.insert(&F);
00225     return;
00226   }
00227 
00228   switch (RetValLiveness) {
00229   case Live:      LiveRetVal.insert(&F); break;
00230   case MaybeLive: MaybeLiveRetVal.insert(&F); break;
00231   case Dead:      DeadRetVal.insert(&F); break;
00232   }
00233 
00234   DEBUG(std::cerr << "  Inspecting args for fn: " << F.getName() << "\n");
00235 
00236   // If it is not intrinsically alive, we know that all users of the
00237   // function are call sites.  Mark all of the arguments live which are
00238   // directly used, and keep track of all of the call sites of this function
00239   // if there are any arguments we assume that are dead.
00240   //
00241   bool AnyMaybeLiveArgs = false;
00242   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
00243        AI != E; ++AI)
00244     switch (getArgumentLiveness(*AI)) {
00245     case Live:
00246       DEBUG(std::cerr << "    Arg live by use: " << AI->getName() << "\n");
00247       LiveArguments.insert(AI);
00248       break;
00249     case Dead:
00250       DEBUG(std::cerr << "    Arg definitely dead: " <<AI->getName()<<"\n");
00251       DeadArguments.insert(AI);
00252       break;
00253     case MaybeLive:
00254       DEBUG(std::cerr << "    Arg only passed to calls: "
00255             << AI->getName() << "\n");
00256       AnyMaybeLiveArgs = true;
00257       MaybeLiveArguments.insert(AI);
00258       break;
00259     }
00260 
00261   // If there are any "MaybeLive" arguments, we need to check callees of
00262   // this function when/if they become alive.  Record which functions are
00263   // callees...
00264   if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive)
00265     for (Value::use_iterator I = F.use_begin(), E = F.use_end();
00266          I != E; ++I) {
00267       if (AnyMaybeLiveArgs)
00268         CallSites.insert(std::make_pair(&F, CallSite::get(*I)));
00269 
00270       if (RetValLiveness == MaybeLive)
00271         for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
00272              UI != E; ++UI)
00273           InstructionsToInspect.push_back(cast<Instruction>(*UI));
00274     }
00275 }
00276 
00277 // isMaybeLiveArgumentNowLive - Check to see if Arg is alive.  At this point, we
00278 // know that the only uses of Arg are to be passed in as an argument to a
00279 // function call or return.  Check to see if the formal argument passed in is in
00280 // the LiveArguments set.  If so, return true.
00281 //
00282 bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) {
00283   for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){
00284     if (isa<ReturnInst>(*I)) {
00285       if (LiveRetVal.count(Arg->getParent())) return true;
00286       continue;
00287     }
00288 
00289     CallSite CS = CallSite::get(*I);
00290 
00291     // We know that this can only be used for direct calls...
00292     Function *Callee = CS.getCalledFunction();
00293 
00294     // Loop over all of the arguments (because Arg may be passed into the call
00295     // multiple times) and check to see if any are now alive...
00296     CallSite::arg_iterator CSAI = CS.arg_begin();
00297     for (Function::arg_iterator AI = Callee->arg_begin(), E = Callee->arg_end();
00298          AI != E; ++AI, ++CSAI)
00299       // If this is the argument we are looking for, check to see if it's alive
00300       if (*CSAI == Arg && LiveArguments.count(AI))
00301         return true;
00302   }
00303   return false;
00304 }
00305 
00306 /// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive.
00307 /// Mark it live in the specified sets and recursively mark arguments in callers
00308 /// live that are needed to pass in a value.
00309 ///
00310 void DAE::MarkArgumentLive(Argument *Arg) {
00311   std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg);
00312   if (It == MaybeLiveArguments.end() || *It != Arg) return;
00313 
00314   DEBUG(std::cerr << "  MaybeLive argument now live: " << Arg->getName()<<"\n");
00315   MaybeLiveArguments.erase(It);
00316   LiveArguments.insert(Arg);
00317 
00318   // Loop over all of the call sites of the function, making any arguments
00319   // passed in to provide a value for this argument live as necessary.
00320   //
00321   Function *Fn = Arg->getParent();
00322   unsigned ArgNo = std::distance(Fn->arg_begin(), Function::arg_iterator(Arg));
00323 
00324   std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn);
00325   for (; I != CallSites.end() && I->first == Fn; ++I) {
00326     CallSite CS = I->second;
00327     Value *ArgVal = *(CS.arg_begin()+ArgNo);
00328     if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) {
00329       MarkArgumentLive(ActualArg);
00330     } else {
00331       // If the value passed in at this call site is a return value computed by
00332       // some other call site, make sure to mark the return value at the other
00333       // call site as being needed.
00334       CallSite ArgCS = CallSite::get(ArgVal);
00335       if (ArgCS.getInstruction())
00336         if (Function *Fn = ArgCS.getCalledFunction())
00337           MarkRetValLive(Fn);
00338     }
00339   }
00340 }
00341 
00342 /// MarkArgumentLive - The MaybeLive return value for the specified function is
00343 /// now known to be alive.  Propagate this fact to the return instructions which
00344 /// produce it.
00345 void DAE::MarkRetValLive(Function *F) {
00346   assert(F && "Shame shame, we can't have null pointers here!");
00347 
00348   // Check to see if we already knew it was live
00349   std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F);
00350   if (I == MaybeLiveRetVal.end() || *I != F) return;  // It's already alive!
00351 
00352   DEBUG(std::cerr << "  MaybeLive retval now live: " << F->getName() << "\n");
00353 
00354   MaybeLiveRetVal.erase(I);
00355   LiveRetVal.insert(F);        // It is now known to be live!
00356 
00357   // Loop over all of the functions, noticing that the return value is now live.
00358   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00359     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
00360       MarkReturnInstArgumentLive(RI);
00361 }
00362 
00363 void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) {
00364   Value *Op = RI->getOperand(0);
00365   if (Argument *A = dyn_cast<Argument>(Op)) {
00366     MarkArgumentLive(A);
00367   } else if (CallInst *CI = dyn_cast<CallInst>(Op)) {
00368     if (Function *F = CI->getCalledFunction())
00369       MarkRetValLive(F);
00370   } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
00371     if (Function *F = II->getCalledFunction())
00372       MarkRetValLive(F);
00373   }
00374 }
00375 
00376 // RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as
00377 // specified by the DeadArguments list.  Transform the function and all of the
00378 // callees of the function to not have these arguments.
00379 //
00380 void DAE::RemoveDeadArgumentsFromFunction(Function *F) {
00381   // Start by computing a new prototype for the function, which is the same as
00382   // the old function, but has fewer arguments.
00383   const FunctionType *FTy = F->getFunctionType();
00384   std::vector<const Type*> Params;
00385 
00386   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
00387     if (!DeadArguments.count(I))
00388       Params.push_back(I->getType());
00389 
00390   const Type *RetTy = FTy->getReturnType();
00391   if (DeadRetVal.count(F)) {
00392     RetTy = Type::VoidTy;
00393     DeadRetVal.erase(F);
00394   }
00395 
00396   // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which
00397   // have zero fixed arguments.
00398   //
00399   // FIXME: once this bug is fixed in the CWriter, this hack should be removed.
00400   //
00401   bool ExtraArgHack = false;
00402   if (Params.empty() && FTy->isVarArg()) {
00403     ExtraArgHack = true;
00404     Params.push_back(Type::IntTy);
00405   }
00406 
00407   FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg());
00408 
00409   // Create the new function body and insert it into the module...
00410   Function *NF = new Function(NFTy, F->getLinkage(), F->getName());
00411   NF->setCallingConv(F->getCallingConv());
00412   F->getParent()->getFunctionList().insert(F, NF);
00413 
00414   // Loop over all of the callers of the function, transforming the call sites
00415   // to pass in a smaller number of arguments into the new function.
00416   //
00417   std::vector<Value*> Args;
00418   while (!F->use_empty()) {
00419     CallSite CS = CallSite::get(F->use_back());
00420     Instruction *Call = CS.getInstruction();
00421 
00422     // Loop over the operands, deleting dead ones...
00423     CallSite::arg_iterator AI = CS.arg_begin();
00424     for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
00425          I != E; ++I, ++AI)
00426       if (!DeadArguments.count(I))      // Remove operands for dead arguments
00427         Args.push_back(*AI);
00428 
00429     if (ExtraArgHack)
00430       Args.push_back(Constant::getNullValue(Type::IntTy));
00431 
00432     // Push any varargs arguments on the list
00433     for (; AI != CS.arg_end(); ++AI)
00434       Args.push_back(*AI);
00435 
00436     Instruction *New;
00437     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
00438       New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(),
00439                            Args, "", Call);
00440       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
00441     } else {
00442       New = new CallInst(NF, Args, "", Call);
00443       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
00444       if (cast<CallInst>(Call)->isTailCall())
00445         cast<CallInst>(New)->setTailCall();
00446     }
00447     Args.clear();
00448 
00449     if (!Call->use_empty()) {
00450       if (New->getType() == Type::VoidTy)
00451         Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
00452       else {
00453         Call->replaceAllUsesWith(New);
00454         std::string Name = Call->getName();
00455         Call->setName("");
00456         New->setName(Name);
00457       }
00458     }
00459 
00460     // Finally, remove the old call from the program, reducing the use-count of
00461     // F.
00462     Call->getParent()->getInstList().erase(Call);
00463   }
00464 
00465   // Since we have now created the new function, splice the body of the old
00466   // function right into the new function, leaving the old rotting hulk of the
00467   // function empty.
00468   NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
00469 
00470   // Loop over the argument list, transfering uses of the old arguments over to
00471   // the new arguments, also transfering over the names as well.  While we're at
00472   // it, remove the dead arguments from the DeadArguments list.
00473   //
00474   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
00475          I2 = NF->arg_begin();
00476        I != E; ++I)
00477     if (!DeadArguments.count(I)) {
00478       // If this is a live argument, move the name and users over to the new
00479       // version.
00480       I->replaceAllUsesWith(I2);
00481       I2->setName(I->getName());
00482       ++I2;
00483     } else {
00484       // If this argument is dead, replace any uses of it with null constants
00485       // (these are guaranteed to only be operands to call instructions which
00486       // will later be simplified).
00487       I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
00488       DeadArguments.erase(I);
00489     }
00490 
00491   // If we change the return value of the function we must rewrite any return
00492   // instructions.  Check this now.
00493   if (F->getReturnType() != NF->getReturnType())
00494     for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB)
00495       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
00496         new ReturnInst(0, RI);
00497         BB->getInstList().erase(RI);
00498       }
00499 
00500   // Now that the old function is dead, delete it.
00501   F->getParent()->getFunctionList().erase(F);
00502 }
00503 
00504 bool DAE::runOnModule(Module &M) {
00505   // First phase: loop through the module, determining which arguments are live.
00506   // We assume all arguments are dead unless proven otherwise (allowing us to
00507   // determine that dead arguments passed into recursive functions are dead).
00508   //
00509   DEBUG(std::cerr << "DAE - Determining liveness\n");
00510   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00511     SurveyFunction(*I);
00512 
00513   // Loop over the instructions to inspect, propagating liveness among arguments
00514   // and return values which are MaybeLive.
00515 
00516   while (!InstructionsToInspect.empty()) {
00517     Instruction *I = InstructionsToInspect.back();
00518     InstructionsToInspect.pop_back();
00519 
00520     if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) {
00521       // For return instructions, we just have to check to see if the return
00522       // value for the current function is known now to be alive.  If so, any
00523       // arguments used by it are now alive, and any call instruction return
00524       // value is alive as well.
00525       if (LiveRetVal.count(RI->getParent()->getParent()))
00526         MarkReturnInstArgumentLive(RI);
00527 
00528     } else {
00529       CallSite CS = CallSite::get(I);
00530       assert(CS.getInstruction() && "Unknown instruction for the I2I list!");
00531 
00532       Function *Callee = CS.getCalledFunction();
00533 
00534       // If we found a call or invoke instruction on this list, that means that
00535       // an argument of the function is a call instruction.  If the argument is
00536       // live, then the return value of the called instruction is now live.
00537       //
00538       CallSite::arg_iterator AI = CS.arg_begin();  // ActualIterator
00539       for (Function::arg_iterator FI = Callee->arg_begin(),
00540              E = Callee->arg_end(); FI != E; ++AI, ++FI) {
00541         // If this argument is another call...
00542         CallSite ArgCS = CallSite::get(*AI);
00543         if (ArgCS.getInstruction() && LiveArguments.count(FI))
00544           if (Function *Callee = ArgCS.getCalledFunction())
00545             MarkRetValLive(Callee);
00546       }
00547     }
00548   }
00549 
00550   // Now we loop over all of the MaybeLive arguments, promoting them to be live
00551   // arguments if one of the calls that uses the arguments to the calls they are
00552   // passed into requires them to be live.  Of course this could make other
00553   // arguments live, so process callers recursively.
00554   //
00555   // Because elements can be removed from the MaybeLiveArguments set, copy it to
00556   // a temporary vector.
00557   //
00558   std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(),
00559                                     MaybeLiveArguments.end());
00560   for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) {
00561     Argument *MLA = TmpArgList[i];
00562     if (MaybeLiveArguments.count(MLA) &&
00563         isMaybeLiveArgumentNowLive(MLA))
00564       MarkArgumentLive(MLA);
00565   }
00566 
00567   // Recover memory early...
00568   CallSites.clear();
00569 
00570   // At this point, we know that all arguments in DeadArguments and
00571   // MaybeLiveArguments are dead.  If the two sets are empty, there is nothing
00572   // to do.
00573   if (MaybeLiveArguments.empty() && DeadArguments.empty() &&
00574       MaybeLiveRetVal.empty() && DeadRetVal.empty())
00575     return false;
00576 
00577   // Otherwise, compact into one set, and start eliminating the arguments from
00578   // the functions.
00579   DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end());
00580   MaybeLiveArguments.clear();
00581   DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end());
00582   MaybeLiveRetVal.clear();
00583 
00584   LiveArguments.clear();
00585   LiveRetVal.clear();
00586 
00587   NumArgumentsEliminated += DeadArguments.size();
00588   NumRetValsEliminated   += DeadRetVal.size();
00589   while (!DeadArguments.empty())
00590     RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent());
00591 
00592   while (!DeadRetVal.empty())
00593     RemoveDeadArgumentsFromFunction(*DeadRetVal.begin());
00594   return true;
00595 }