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/Module.h"
00023 #include "llvm/Pass.h"
00024 #include "llvm/DerivedTypes.h"
00025 #include "llvm/Constant.h"
00026 #include "llvm/Instructions.h"
00027 #include "llvm/Support/CallSite.h"
00028 #include "llvm/Support/Debug.h"
00029 #include "llvm/ADT/Statistic.h"
00030 #include "llvm/ADT/iterator"
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 (A.use_empty()) return Dead;  // First check, directly dead?
00132 
00133   // Scan through all of the uses, looking for non-argument passing uses.
00134   for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) {
00135     // Return instructions do not immediately effect liveness.
00136     if (isa<ReturnInst>(*I))
00137       continue;
00138 
00139     CallSite CS = CallSite::get(const_cast<User*>(*I));
00140     if (!CS.getInstruction()) {
00141       // If its used by something that is not a call or invoke, it's alive!
00142       return Live;
00143     }
00144     // If it's an indirect call, mark it alive...
00145     Function *Callee = CS.getCalledFunction();
00146     if (!Callee) return Live;
00147 
00148     // Check to see if it's passed through a va_arg area: if so, we cannot
00149     // remove it.
00150     if (CallPassesValueThoughVararg(CS.getInstruction(), &A))
00151       return Live;   // If passed through va_arg area, we cannot remove it
00152   }
00153 
00154   return MaybeLive;  // It must be used, but only as argument to a function
00155 }
00156 
00157 
00158 // SurveyFunction - This performs the initial survey of the specified function,
00159 // checking out whether or not it uses any of its incoming arguments or whether
00160 // any callers use the return value.  This fills in the
00161 // (Dead|MaybeLive|Live)(Arguments|RetVal) sets.
00162 //
00163 // We consider arguments of non-internal functions to be intrinsically alive as
00164 // well as arguments to functions which have their "address taken".
00165 //
00166 void DAE::SurveyFunction(Function &F) {
00167   bool FunctionIntrinsicallyLive = false;
00168   Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead;
00169 
00170   if (!F.hasInternalLinkage() &&
00171       (!ShouldHackArguments() || F.getIntrinsicID()))
00172     FunctionIntrinsicallyLive = true;
00173   else
00174     for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
00175       // If this use is anything other than a call site, the function is alive.
00176       CallSite CS = CallSite::get(*I);
00177       Instruction *TheCall = CS.getInstruction();
00178       if (!TheCall) {   // Not a direct call site?
00179         FunctionIntrinsicallyLive = true;
00180         break;
00181       }
00182 
00183       // Check to see if the return value is used...
00184       if (RetValLiveness != Live)
00185         for (Value::use_iterator I = TheCall->use_begin(),
00186                E = TheCall->use_end(); I != E; ++I)
00187           if (isa<ReturnInst>(cast<Instruction>(*I))) {
00188             RetValLiveness = MaybeLive;
00189           } else if (isa<CallInst>(cast<Instruction>(*I)) ||
00190                      isa<InvokeInst>(cast<Instruction>(*I))) {
00191             if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) ||
00192                 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) {
00193               RetValLiveness = Live;
00194               break;
00195             } else {
00196               RetValLiveness = MaybeLive;
00197             }
00198           } else {
00199             RetValLiveness = Live;
00200             break;
00201           }
00202 
00203       // If the function is PASSED IN as an argument, its address has been taken
00204       for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
00205            AI != E; ++AI)
00206         if (AI->get() == &F) {
00207           FunctionIntrinsicallyLive = true;
00208           break;
00209         }
00210       if (FunctionIntrinsicallyLive) break;
00211     }
00212 
00213   if (FunctionIntrinsicallyLive) {
00214     DEBUG(std::cerr << "  Intrinsically live fn: " << F.getName() << "\n");
00215     for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
00216          AI != E; ++AI)
00217       LiveArguments.insert(AI);
00218     LiveRetVal.insert(&F);
00219     return;
00220   }
00221 
00222   switch (RetValLiveness) {
00223   case Live:      LiveRetVal.insert(&F); break;
00224   case MaybeLive: MaybeLiveRetVal.insert(&F); break;
00225   case Dead:      DeadRetVal.insert(&F); break;
00226   }
00227 
00228   DEBUG(std::cerr << "  Inspecting args for fn: " << F.getName() << "\n");
00229 
00230   // If it is not intrinsically alive, we know that all users of the
00231   // function are call sites.  Mark all of the arguments live which are
00232   // directly used, and keep track of all of the call sites of this function
00233   // if there are any arguments we assume that are dead.
00234   //
00235   bool AnyMaybeLiveArgs = false;
00236   for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end();
00237        AI != E; ++AI)
00238     switch (getArgumentLiveness(*AI)) {
00239     case Live:
00240       DEBUG(std::cerr << "    Arg live by use: " << AI->getName() << "\n");
00241       LiveArguments.insert(AI);
00242       break;
00243     case Dead:
00244       DEBUG(std::cerr << "    Arg definitely dead: " <<AI->getName()<<"\n");
00245       DeadArguments.insert(AI);
00246       break;
00247     case MaybeLive:
00248       DEBUG(std::cerr << "    Arg only passed to calls: "
00249             << AI->getName() << "\n");
00250       AnyMaybeLiveArgs = true;
00251       MaybeLiveArguments.insert(AI);
00252       break;
00253     }
00254 
00255   // If there are any "MaybeLive" arguments, we need to check callees of
00256   // this function when/if they become alive.  Record which functions are
00257   // callees...
00258   if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive)
00259     for (Value::use_iterator I = F.use_begin(), E = F.use_end();
00260          I != E; ++I) {
00261       if (AnyMaybeLiveArgs)
00262         CallSites.insert(std::make_pair(&F, CallSite::get(*I)));
00263 
00264       if (RetValLiveness == MaybeLive)
00265         for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
00266              UI != E; ++UI)
00267           InstructionsToInspect.push_back(cast<Instruction>(*UI));
00268     }
00269 }
00270 
00271 // isMaybeLiveArgumentNowLive - Check to see if Arg is alive.  At this point, we
00272 // know that the only uses of Arg are to be passed in as an argument to a
00273 // function call or return.  Check to see if the formal argument passed in is in
00274 // the LiveArguments set.  If so, return true.
00275 //
00276 bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) {
00277   for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){
00278     if (isa<ReturnInst>(*I)) {
00279       if (LiveRetVal.count(Arg->getParent())) return true;
00280       continue;
00281     }
00282 
00283     CallSite CS = CallSite::get(*I);
00284 
00285     // We know that this can only be used for direct calls...
00286     Function *Callee = CS.getCalledFunction();
00287 
00288     // Loop over all of the arguments (because Arg may be passed into the call
00289     // multiple times) and check to see if any are now alive...
00290     CallSite::arg_iterator CSAI = CS.arg_begin();
00291     for (Function::arg_iterator AI = Callee->arg_begin(), E = Callee->arg_end();
00292          AI != E; ++AI, ++CSAI)
00293       // If this is the argument we are looking for, check to see if it's alive
00294       if (*CSAI == Arg && LiveArguments.count(AI))
00295         return true;
00296   }
00297   return false;
00298 }
00299 
00300 /// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive.
00301 /// Mark it live in the specified sets and recursively mark arguments in callers
00302 /// live that are needed to pass in a value.
00303 ///
00304 void DAE::MarkArgumentLive(Argument *Arg) {
00305   std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg);
00306   if (It == MaybeLiveArguments.end() || *It != Arg) return;
00307 
00308   DEBUG(std::cerr << "  MaybeLive argument now live: " << Arg->getName()<<"\n");
00309   MaybeLiveArguments.erase(It);
00310   LiveArguments.insert(Arg);
00311 
00312   // Loop over all of the call sites of the function, making any arguments
00313   // passed in to provide a value for this argument live as necessary.
00314   //
00315   Function *Fn = Arg->getParent();
00316   unsigned ArgNo = std::distance(Fn->arg_begin(), Function::arg_iterator(Arg));
00317 
00318   std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn);
00319   for (; I != CallSites.end() && I->first == Fn; ++I) {
00320     CallSite CS = I->second;
00321     Value *ArgVal = *(CS.arg_begin()+ArgNo);
00322     if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) {
00323       MarkArgumentLive(ActualArg);
00324     } else {
00325       // If the value passed in at this call site is a return value computed by
00326       // some other call site, make sure to mark the return value at the other
00327       // call site as being needed.
00328       CallSite ArgCS = CallSite::get(ArgVal);
00329       if (ArgCS.getInstruction())
00330         if (Function *Fn = ArgCS.getCalledFunction())
00331           MarkRetValLive(Fn);
00332     }
00333   }
00334 }
00335 
00336 /// MarkArgumentLive - The MaybeLive return value for the specified function is
00337 /// now known to be alive.  Propagate this fact to the return instructions which
00338 /// produce it.
00339 void DAE::MarkRetValLive(Function *F) {
00340   assert(F && "Shame shame, we can't have null pointers here!");
00341 
00342   // Check to see if we already knew it was live
00343   std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F);
00344   if (I == MaybeLiveRetVal.end() || *I != F) return;  // It's already alive!
00345 
00346   DEBUG(std::cerr << "  MaybeLive retval now live: " << F->getName() << "\n");
00347 
00348   MaybeLiveRetVal.erase(I);
00349   LiveRetVal.insert(F);        // It is now known to be live!
00350 
00351   // Loop over all of the functions, noticing that the return value is now live.
00352   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00353     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
00354       MarkReturnInstArgumentLive(RI);
00355 }
00356 
00357 void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) {
00358   Value *Op = RI->getOperand(0);
00359   if (Argument *A = dyn_cast<Argument>(Op)) {
00360     MarkArgumentLive(A);
00361   } else if (CallInst *CI = dyn_cast<CallInst>(Op)) {
00362     if (Function *F = CI->getCalledFunction())
00363       MarkRetValLive(F);
00364   } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
00365     if (Function *F = II->getCalledFunction())
00366       MarkRetValLive(F);
00367   }
00368 }
00369 
00370 // RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as
00371 // specified by the DeadArguments list.  Transform the function and all of the
00372 // callees of the function to not have these arguments.
00373 //
00374 void DAE::RemoveDeadArgumentsFromFunction(Function *F) {
00375   // Start by computing a new prototype for the function, which is the same as
00376   // the old function, but has fewer arguments.
00377   const FunctionType *FTy = F->getFunctionType();
00378   std::vector<const Type*> Params;
00379 
00380   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
00381     if (!DeadArguments.count(I))
00382       Params.push_back(I->getType());
00383 
00384   const Type *RetTy = FTy->getReturnType();
00385   if (DeadRetVal.count(F)) {
00386     RetTy = Type::VoidTy;
00387     DeadRetVal.erase(F);
00388   }
00389 
00390   // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which
00391   // have zero fixed arguments.
00392   //
00393   // FIXME: once this bug is fixed in the CWriter, this hack should be removed.
00394   //
00395   bool ExtraArgHack = false;
00396   if (Params.empty() && FTy->isVarArg()) {
00397     ExtraArgHack = true;
00398     Params.push_back(Type::IntTy);
00399   }
00400 
00401   FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg());
00402 
00403   // Create the new function body and insert it into the module...
00404   Function *NF = new Function(NFTy, F->getLinkage(), F->getName());
00405   NF->setCallingConv(F->getCallingConv());
00406   F->getParent()->getFunctionList().insert(F, NF);
00407 
00408   // Loop over all of the callers of the function, transforming the call sites
00409   // to pass in a smaller number of arguments into the new function.
00410   //
00411   std::vector<Value*> Args;
00412   while (!F->use_empty()) {
00413     CallSite CS = CallSite::get(F->use_back());
00414     Instruction *Call = CS.getInstruction();
00415 
00416     // Loop over the operands, deleting dead ones...
00417     CallSite::arg_iterator AI = CS.arg_begin();
00418     for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
00419          I != E; ++I, ++AI)
00420       if (!DeadArguments.count(I))      // Remove operands for dead arguments
00421         Args.push_back(*AI);
00422 
00423     if (ExtraArgHack)
00424       Args.push_back(Constant::getNullValue(Type::IntTy));
00425 
00426     // Push any varargs arguments on the list
00427     for (; AI != CS.arg_end(); ++AI)
00428       Args.push_back(*AI);
00429 
00430     Instruction *New;
00431     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
00432       New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(),
00433                            Args, "", Call);
00434       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
00435     } else {
00436       New = new CallInst(NF, Args, "", Call);
00437       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
00438       if (cast<CallInst>(Call)->isTailCall())
00439         cast<CallInst>(New)->setTailCall();
00440     }
00441     Args.clear();
00442 
00443     if (!Call->use_empty()) {
00444       if (New->getType() == Type::VoidTy)
00445         Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
00446       else {
00447         Call->replaceAllUsesWith(New);
00448         std::string Name = Call->getName();
00449         Call->setName("");
00450         New->setName(Name);
00451       }
00452     }
00453 
00454     // Finally, remove the old call from the program, reducing the use-count of
00455     // F.
00456     Call->getParent()->getInstList().erase(Call);
00457   }
00458 
00459   // Since we have now created the new function, splice the body of the old
00460   // function right into the new function, leaving the old rotting hulk of the
00461   // function empty.
00462   NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
00463 
00464   // Loop over the argument list, transfering uses of the old arguments over to
00465   // the new arguments, also transfering over the names as well.  While we're at
00466   // it, remove the dead arguments from the DeadArguments list.
00467   //
00468   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
00469          I2 = NF->arg_begin();
00470        I != E; ++I)
00471     if (!DeadArguments.count(I)) {
00472       // If this is a live argument, move the name and users over to the new
00473       // version.
00474       I->replaceAllUsesWith(I2);
00475       I2->setName(I->getName());
00476       ++I2;
00477     } else {
00478       // If this argument is dead, replace any uses of it with null constants
00479       // (these are guaranteed to only be operands to call instructions which
00480       // will later be simplified).
00481       I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
00482       DeadArguments.erase(I);
00483     }
00484 
00485   // If we change the return value of the function we must rewrite any return
00486   // instructions.  Check this now.
00487   if (F->getReturnType() != NF->getReturnType())
00488     for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB)
00489       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
00490         new ReturnInst(0, RI);
00491         BB->getInstList().erase(RI);
00492       }
00493 
00494   // Now that the old function is dead, delete it.
00495   F->getParent()->getFunctionList().erase(F);
00496 }
00497 
00498 bool DAE::runOnModule(Module &M) {
00499   // First phase: loop through the module, determining which arguments are live.
00500   // We assume all arguments are dead unless proven otherwise (allowing us to
00501   // determine that dead arguments passed into recursive functions are dead).
00502   //
00503   DEBUG(std::cerr << "DAE - Determining liveness\n");
00504   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00505     SurveyFunction(*I);
00506 
00507   // Loop over the instructions to inspect, propagating liveness among arguments
00508   // and return values which are MaybeLive.
00509 
00510   while (!InstructionsToInspect.empty()) {
00511     Instruction *I = InstructionsToInspect.back();
00512     InstructionsToInspect.pop_back();
00513 
00514     if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) {
00515       // For return instructions, we just have to check to see if the return
00516       // value for the current function is known now to be alive.  If so, any
00517       // arguments used by it are now alive, and any call instruction return
00518       // value is alive as well.
00519       if (LiveRetVal.count(RI->getParent()->getParent()))
00520         MarkReturnInstArgumentLive(RI);
00521 
00522     } else {
00523       CallSite CS = CallSite::get(I);
00524       assert(CS.getInstruction() && "Unknown instruction for the I2I list!");
00525 
00526       Function *Callee = CS.getCalledFunction();
00527 
00528       // If we found a call or invoke instruction on this list, that means that
00529       // an argument of the function is a call instruction.  If the argument is
00530       // live, then the return value of the called instruction is now live.
00531       //
00532       CallSite::arg_iterator AI = CS.arg_begin();  // ActualIterator
00533       for (Function::arg_iterator FI = Callee->arg_begin(),
00534              E = Callee->arg_end(); FI != E; ++AI, ++FI) {
00535         // If this argument is another call...
00536         CallSite ArgCS = CallSite::get(*AI);
00537         if (ArgCS.getInstruction() && LiveArguments.count(FI))
00538           if (Function *Callee = ArgCS.getCalledFunction())
00539             MarkRetValLive(Callee);
00540       }
00541     }
00542   }
00543 
00544   // Now we loop over all of the MaybeLive arguments, promoting them to be live
00545   // arguments if one of the calls that uses the arguments to the calls they are
00546   // passed into requires them to be live.  Of course this could make other
00547   // arguments live, so process callers recursively.
00548   //
00549   // Because elements can be removed from the MaybeLiveArguments set, copy it to
00550   // a temporary vector.
00551   //
00552   std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(),
00553                                     MaybeLiveArguments.end());
00554   for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) {
00555     Argument *MLA = TmpArgList[i];
00556     if (MaybeLiveArguments.count(MLA) &&
00557         isMaybeLiveArgumentNowLive(MLA))
00558       MarkArgumentLive(MLA);
00559   }
00560 
00561   // Recover memory early...
00562   CallSites.clear();
00563 
00564   // At this point, we know that all arguments in DeadArguments and
00565   // MaybeLiveArguments are dead.  If the two sets are empty, there is nothing
00566   // to do.
00567   if (MaybeLiveArguments.empty() && DeadArguments.empty() &&
00568       MaybeLiveRetVal.empty() && DeadRetVal.empty())
00569     return false;
00570 
00571   // Otherwise, compact into one set, and start eliminating the arguments from
00572   // the functions.
00573   DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end());
00574   MaybeLiveArguments.clear();
00575   DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end());
00576   MaybeLiveRetVal.clear();
00577 
00578   LiveArguments.clear();
00579   LiveRetVal.clear();
00580 
00581   NumArgumentsEliminated += DeadArguments.size();
00582   NumRetValsEliminated   += DeadRetVal.size();
00583   while (!DeadArguments.empty())
00584     RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent());
00585 
00586   while (!DeadRetVal.empty())
00587     RemoveDeadArgumentsFromFunction(*DeadRetVal.begin());
00588   return true;
00589 }