1 //===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
15 // This pass is often useful as a cleanup pass to run after aggressive
16 // interprocedural passes, which add possibly-dead arguments.
18 //===----------------------------------------------------------------------===//
20 #include "llvm/Transforms/IPO.h"
21 #include "llvm/Module.h"
22 #include "llvm/Pass.h"
23 #include "llvm/DerivedTypes.h"
24 #include "llvm/Constant.h"
25 #include "llvm/iOther.h"
26 #include "llvm/iTerminators.h"
27 #include "llvm/Support/CallSite.h"
28 #include "Support/Debug.h"
29 #include "Support/Statistic.h"
30 #include "Support/iterator"
34 Statistic<> NumArgumentsEliminated("deadargelim",
35 "Number of unread args removed");
36 Statistic<> NumRetValsEliminated("deadargelim",
37 "Number of unused return values removed");
39 /// DAE - The dead argument elimination pass.
41 class DAE : public Pass {
42 /// DeleteFromExternalFunctions - Bugpoint sets this flag to indicate that
43 /// it is safe to hack apart functions without internal linkage.
44 bool DeleteFromExternalFunctions;
46 /// Liveness enum - During our initial pass over the program, we determine
47 /// that things are either definately alive, definately dead, or in need of
48 /// interprocedural analysis (MaybeLive).
50 enum Liveness { Live, MaybeLive, Dead };
52 /// LiveArguments, MaybeLiveArguments, DeadArguments - These sets contain
53 /// all of the arguments in the program. The Dead set contains arguments
54 /// which are completely dead (never used in the function). The MaybeLive
55 /// set contains arguments which are only passed into other function calls,
56 /// thus may be live and may be dead. The Live set contains arguments which
57 /// are known to be alive.
59 std::set<Argument*> DeadArguments, MaybeLiveArguments, LiveArguments;
61 /// DeadRetVal, MaybeLiveRetVal, LifeRetVal - These sets contain all of the
62 /// functions in the program. The Dead set contains functions whose return
63 /// value is known to be dead. The MaybeLive set contains functions whose
64 /// return values are only used by return instructions, and the Live set
65 /// contains functions whose return values are used, functions that are
66 /// external, and functions that already return void.
68 std::set<Function*> DeadRetVal, MaybeLiveRetVal, LiveRetVal;
70 /// InstructionsToInspect - As we mark arguments and return values
71 /// MaybeLive, we keep track of which instructions could make the values
72 /// live here. Once the entire program has had the return value and
73 /// arguments analyzed, this set is scanned to promote the MaybeLive objects
74 /// to be Live if they really are used.
75 std::vector<Instruction*> InstructionsToInspect;
77 /// CallSites - Keep track of the call sites of functions that have
78 /// MaybeLive arguments or return values.
79 std::multimap<Function*, CallSite> CallSites;
82 DAE(bool DFEF = false) : DeleteFromExternalFunctions(DFEF) {}
86 Liveness getArgumentLiveness(const Argument &A);
87 bool isMaybeLiveArgumentNowLive(Argument *Arg);
89 void SurveyFunction(Function &Fn);
91 void MarkArgumentLive(Argument *Arg);
92 void MarkRetValLive(Function *F);
93 void MarkReturnInstArgumentLive(ReturnInst *RI);
95 void RemoveDeadArgumentsFromFunction(Function *F);
97 RegisterOpt<DAE> X("deadargelim", "Dead Argument Elimination");
100 /// createDeadArgEliminationPass - This pass removes arguments from functions
101 /// which are not used by the body of the function. If
102 /// DeleteFromExternalFunctions is true, the pass will modify functions that
103 /// have external linkage, which is not usually safe (this is used by bugpoint
104 /// to reduce testcases).
106 Pass *createDeadArgEliminationPass(bool DeleteFromExternalFunctions) {
107 return new DAE(DeleteFromExternalFunctions);
110 static inline bool CallPassesValueThoughVararg(Instruction *Call,
112 CallSite CS = CallSite::get(Call);
113 const Type *CalledValueTy = CS.getCalledValue()->getType();
114 const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType();
115 unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams();
116 for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs;
117 AI != CS.arg_end(); ++AI)
118 if (AI->get() == Arg)
123 // getArgumentLiveness - Inspect an argument, determining if is known Live
124 // (used in a computation), MaybeLive (only passed as an argument to a call), or
126 DAE::Liveness DAE::getArgumentLiveness(const Argument &A) {
127 if (A.use_empty()) return Dead; // First check, directly dead?
129 // Scan through all of the uses, looking for non-argument passing uses.
130 for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) {
131 // Return instructions do not immediately effect liveness.
132 if (isa<ReturnInst>(*I))
135 CallSite CS = CallSite::get(const_cast<User*>(*I));
136 if (!CS.getInstruction()) {
137 // If its used by something that is not a call or invoke, it's alive!
140 // If it's an indirect call, mark it alive...
141 Function *Callee = CS.getCalledFunction();
142 if (!Callee) return Live;
144 // Check to see if it's passed through a va_arg area: if so, we cannot
146 if (CallPassesValueThoughVararg(CS.getInstruction(), &A))
147 return Live; // If passed through va_arg area, we cannot remove it
150 return MaybeLive; // It must be used, but only as argument to a function
154 // SurveyFunction - This performs the initial survey of the specified function,
155 // checking out whether or not it uses any of its incoming arguments or whether
156 // any callers use the return value. This fills in the
157 // (Dead|MaybeLive|Live)(Arguments|RetVal) sets.
159 // We consider arguments of non-internal functions to be intrinsically alive as
160 // well as arguments to functions which have their "address taken".
162 void DAE::SurveyFunction(Function &F) {
163 bool FunctionIntrinsicallyLive = false;
164 Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead;
166 if (!F.hasInternalLinkage() && !DeleteFromExternalFunctions)
167 FunctionIntrinsicallyLive = true;
169 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
170 // If this use is anything other than a call site, the function is alive.
171 CallSite CS = CallSite::get(*I);
172 Instruction *TheCall = CS.getInstruction();
173 if (!TheCall) { // Not a direct call site?
174 FunctionIntrinsicallyLive = true;
178 // Check to see if the return value is used...
179 if (RetValLiveness != Live)
180 for (Value::use_iterator I = TheCall->use_begin(),
181 E = TheCall->use_end(); I != E; ++I)
182 if (isa<ReturnInst>(cast<Instruction>(*I))) {
183 RetValLiveness = MaybeLive;
184 } else if (isa<CallInst>(cast<Instruction>(*I)) ||
185 isa<InvokeInst>(cast<Instruction>(*I))) {
186 if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) ||
187 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) {
188 RetValLiveness = Live;
191 RetValLiveness = MaybeLive;
194 RetValLiveness = Live;
198 // If the function is PASSED IN as an argument, its address has been taken
199 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
201 if (AI->get() == &F) {
202 FunctionIntrinsicallyLive = true;
205 if (FunctionIntrinsicallyLive) break;
208 if (FunctionIntrinsicallyLive) {
209 DEBUG(std::cerr << " Intrinsically live fn: " << F.getName() << "\n");
210 for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI)
211 LiveArguments.insert(AI);
212 LiveRetVal.insert(&F);
216 switch (RetValLiveness) {
217 case Live: LiveRetVal.insert(&F); break;
218 case MaybeLive: MaybeLiveRetVal.insert(&F); break;
219 case Dead: DeadRetVal.insert(&F); break;
222 DEBUG(std::cerr << " Inspecting args for fn: " << F.getName() << "\n");
224 // If it is not intrinsically alive, we know that all users of the
225 // function are call sites. Mark all of the arguments live which are
226 // directly used, and keep track of all of the call sites of this function
227 // if there are any arguments we assume that are dead.
229 bool AnyMaybeLiveArgs = false;
230 for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI)
231 switch (getArgumentLiveness(*AI)) {
233 DEBUG(std::cerr << " Arg live by use: " << AI->getName() << "\n");
234 LiveArguments.insert(AI);
237 DEBUG(std::cerr << " Arg definitely dead: " <<AI->getName()<<"\n");
238 DeadArguments.insert(AI);
241 DEBUG(std::cerr << " Arg only passed to calls: "
242 << AI->getName() << "\n");
243 AnyMaybeLiveArgs = true;
244 MaybeLiveArguments.insert(AI);
248 // If there are any "MaybeLive" arguments, we need to check callees of
249 // this function when/if they become alive. Record which functions are
251 if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive)
252 for (Value::use_iterator I = F.use_begin(), E = F.use_end();
254 if (AnyMaybeLiveArgs)
255 CallSites.insert(std::make_pair(&F, CallSite::get(*I)));
257 if (RetValLiveness == MaybeLive)
258 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
260 InstructionsToInspect.push_back(cast<Instruction>(*UI));
264 // isMaybeLiveArgumentNowLive - Check to see if Arg is alive. At this point, we
265 // know that the only uses of Arg are to be passed in as an argument to a
266 // function call or return. Check to see if the formal argument passed in is in
267 // the LiveArguments set. If so, return true.
269 bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) {
270 for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){
271 if (isa<ReturnInst>(*I)) {
272 if (LiveRetVal.count(Arg->getParent())) return true;
276 CallSite CS = CallSite::get(*I);
278 // We know that this can only be used for direct calls...
279 Function *Callee = CS.getCalledFunction();
281 // Loop over all of the arguments (because Arg may be passed into the call
282 // multiple times) and check to see if any are now alive...
283 CallSite::arg_iterator CSAI = CS.arg_begin();
284 for (Function::aiterator AI = Callee->abegin(), E = Callee->aend();
285 AI != E; ++AI, ++CSAI)
286 // If this is the argument we are looking for, check to see if it's alive
287 if (*CSAI == Arg && LiveArguments.count(AI))
293 /// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive.
294 /// Mark it live in the specified sets and recursively mark arguments in callers
295 /// live that are needed to pass in a value.
297 void DAE::MarkArgumentLive(Argument *Arg) {
298 std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg);
299 if (It == MaybeLiveArguments.end() || *It != Arg) return;
301 DEBUG(std::cerr << " MaybeLive argument now live: " << Arg->getName()<<"\n");
302 MaybeLiveArguments.erase(It);
303 LiveArguments.insert(Arg);
305 // Loop over all of the call sites of the function, making any arguments
306 // passed in to provide a value for this argument live as necessary.
308 Function *Fn = Arg->getParent();
309 unsigned ArgNo = std::distance(Fn->abegin(), Function::aiterator(Arg));
311 std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn);
312 for (; I != CallSites.end() && I->first == Fn; ++I) {
313 CallSite CS = I->second;
314 Value *ArgVal = *(CS.arg_begin()+ArgNo);
315 if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) {
316 MarkArgumentLive(ActualArg);
318 // If the value passed in at this call site is a return value computed by
319 // some other call site, make sure to mark the return value at the other
320 // call site as being needed.
321 CallSite ArgCS = CallSite::get(ArgVal);
322 if (ArgCS.getInstruction())
323 if (Function *Fn = ArgCS.getCalledFunction())
329 /// MarkArgumentLive - The MaybeLive return value for the specified function is
330 /// now known to be alive. Propagate this fact to the return instructions which
332 void DAE::MarkRetValLive(Function *F) {
333 assert(F && "Shame shame, we can't have null pointers here!");
335 // Check to see if we already knew it was live
336 std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F);
337 if (I == MaybeLiveRetVal.end() || *I != F) return; // It's already alive!
339 DEBUG(std::cerr << " MaybeLive retval now live: " << F->getName() << "\n");
341 MaybeLiveRetVal.erase(I);
342 LiveRetVal.insert(F); // It is now known to be live!
344 // Loop over all of the functions, noticing that the return value is now live.
345 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
346 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
347 MarkReturnInstArgumentLive(RI);
350 void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) {
351 Value *Op = RI->getOperand(0);
352 if (Argument *A = dyn_cast<Argument>(Op)) {
354 } else if (CallInst *CI = dyn_cast<CallInst>(Op)) {
355 if (Function *F = CI->getCalledFunction())
357 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) {
358 if (Function *F = II->getCalledFunction())
363 // RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as
364 // specified by the DeadArguments list. Transform the function and all of the
365 // callees of the function to not have these arguments.
367 void DAE::RemoveDeadArgumentsFromFunction(Function *F) {
368 // Start by computing a new prototype for the function, which is the same as
369 // the old function, but has fewer arguments.
370 const FunctionType *FTy = F->getFunctionType();
371 std::vector<const Type*> Params;
373 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
374 if (!DeadArguments.count(I))
375 Params.push_back(I->getType());
377 const Type *RetTy = FTy->getReturnType();
378 if (DeadRetVal.count(F)) {
379 RetTy = Type::VoidTy;
383 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which
384 // have zero fixed arguments.
386 // FIXME: once this bug is fixed in the CWriter, this hack should be removed.
388 bool ExtraArgHack = false;
389 if (Params.empty() && FTy->isVarArg()) {
391 Params.push_back(Type::IntTy);
394 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg());
396 // Create the new function body and insert it into the module...
397 Function *NF = new Function(NFTy, F->getLinkage(), F->getName());
398 F->getParent()->getFunctionList().insert(F, NF);
400 // Loop over all of the callers of the function, transforming the call sites
401 // to pass in a smaller number of arguments into the new function.
403 std::vector<Value*> Args;
404 while (!F->use_empty()) {
405 CallSite CS = CallSite::get(F->use_back());
406 Instruction *Call = CS.getInstruction();
408 // Loop over the operands, deleting dead ones...
409 CallSite::arg_iterator AI = CS.arg_begin();
410 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++AI)
411 if (!DeadArguments.count(I)) // Remove operands for dead arguments
415 Args.push_back(Constant::getNullValue(Type::IntTy));
417 // Push any varargs arguments on the list
418 for (; AI != CS.arg_end(); ++AI)
422 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
423 New = new InvokeInst(NF, II->getNormalDest(), II->getExceptionalDest(),
426 New = new CallInst(NF, Args, "", Call);
430 if (!Call->use_empty()) {
431 if (New->getType() == Type::VoidTy)
432 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
434 Call->replaceAllUsesWith(New);
435 std::string Name = Call->getName();
441 // Finally, remove the old call from the program, reducing the use-count of
443 Call->getParent()->getInstList().erase(Call);
446 // Since we have now created the new function, splice the body of the old
447 // function right into the new function, leaving the old rotting hulk of the
449 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
451 // Loop over the argument list, transfering uses of the old arguments over to
452 // the new arguments, also transfering over the names as well. While we're at
453 // it, remove the dead arguments from the DeadArguments list.
455 for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin();
457 if (!DeadArguments.count(I)) {
458 // If this is a live argument, move the name and users over to the new
460 I->replaceAllUsesWith(I2);
461 I2->setName(I->getName());
464 // If this argument is dead, replace any uses of it with null constants
465 // (these are guaranteed to only be operands to call instructions which
466 // will later be simplified).
467 I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
468 DeadArguments.erase(I);
471 // If we change the return value of the function we must rewrite any return
472 // instructions. Check this now.
473 if (F->getReturnType() != NF->getReturnType())
474 for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB)
475 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
476 new ReturnInst(0, RI);
477 BB->getInstList().erase(RI);
480 // Now that the old function is dead, delete it.
481 F->getParent()->getFunctionList().erase(F);
484 bool DAE::run(Module &M) {
485 // First phase: loop through the module, determining which arguments are live.
486 // We assume all arguments are dead unless proven otherwise (allowing us to
487 // determine that dead arguments passed into recursive functions are dead).
489 DEBUG(std::cerr << "DAE - Determining liveness\n");
490 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
493 // Loop over the instructions to inspect, propagating liveness among arguments
494 // and return values which are MaybeLive.
496 while (!InstructionsToInspect.empty()) {
497 Instruction *I = InstructionsToInspect.back();
498 InstructionsToInspect.pop_back();
500 if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) {
501 // For return instructions, we just have to check to see if the return
502 // value for the current function is known now to be alive. If so, any
503 // arguments used by it are now alive, and any call instruction return
504 // value is alive as well.
505 if (LiveRetVal.count(RI->getParent()->getParent()))
506 MarkReturnInstArgumentLive(RI);
509 CallSite CS = CallSite::get(I);
510 assert(CS.getInstruction() && "Unknown instruction for the I2I list!");
512 Function *Callee = CS.getCalledFunction();
514 // If we found a call or invoke instruction on this list, that means that
515 // an argument of the function is a call instruction. If the argument is
516 // live, then the return value of the called instruction is now live.
518 CallSite::arg_iterator AI = CS.arg_begin(); // ActualIterator
519 for (Function::aiterator FI = Callee->abegin(), E = Callee->aend();
520 FI != E; ++AI, ++FI) {
521 // If this argument is another call...
522 CallSite ArgCS = CallSite::get(*AI);
523 if (ArgCS.getInstruction() && LiveArguments.count(FI))
524 if (Function *Callee = ArgCS.getCalledFunction())
525 MarkRetValLive(Callee);
530 // Now we loop over all of the MaybeLive arguments, promoting them to be live
531 // arguments if one of the calls that uses the arguments to the calls they are
532 // passed into requires them to be live. Of course this could make other
533 // arguments live, so process callers recursively.
535 // Because elements can be removed from the MaybeLiveArguments set, copy it to
536 // a temporary vector.
538 std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(),
539 MaybeLiveArguments.end());
540 for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) {
541 Argument *MLA = TmpArgList[i];
542 if (MaybeLiveArguments.count(MLA) &&
543 isMaybeLiveArgumentNowLive(MLA))
544 MarkArgumentLive(MLA);
547 // Recover memory early...
550 // At this point, we know that all arguments in DeadArguments and
551 // MaybeLiveArguments are dead. If the two sets are empty, there is nothing
553 if (MaybeLiveArguments.empty() && DeadArguments.empty() &&
554 MaybeLiveRetVal.empty() && DeadRetVal.empty())
557 // Otherwise, compact into one set, and start eliminating the arguments from
559 DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end());
560 MaybeLiveArguments.clear();
561 DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end());
562 MaybeLiveRetVal.clear();
564 LiveArguments.clear();
567 NumArgumentsEliminated += DeadArguments.size();
568 NumRetValsEliminated += DeadRetVal.size();
569 while (!DeadArguments.empty())
570 RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent());
572 while (!DeadRetVal.empty())
573 RemoveDeadArgumentsFromFunction(*DeadRetVal.begin());