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