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.
14 // This pass is often useful as a cleanup pass to run after aggressive
15 // interprocedural passes, which add possibly-dead arguments.
17 //===----------------------------------------------------------------------===//
19 #include "llvm/Transforms/IPO.h"
20 #include "llvm/Module.h"
21 #include "llvm/Pass.h"
22 #include "llvm/DerivedTypes.h"
23 #include "llvm/Constant.h"
24 #include "llvm/iOther.h"
25 #include "llvm/iTerminators.h"
26 #include "llvm/Support/CallSite.h"
27 #include "Support/Debug.h"
28 #include "Support/Statistic.h"
29 #include "Support/iterator"
33 Statistic<> NumArgumentsEliminated("deadargelim", "Number of args removed");
35 struct DAE : public Pass {
36 DAE(bool DFEF = false) : DeleteFromExternalFunctions(DFEF) {}
40 bool DeleteFromExternalFunctions;
41 bool FunctionArgumentsIntrinsicallyAlive(const Function &F);
42 void RemoveDeadArgumentsFromFunction(Function *F,
43 std::set<Argument*> &DeadArguments);
45 RegisterOpt<DAE> X("deadargelim", "Dead Argument Elimination");
48 /// createDeadArgEliminationPass - This pass removes arguments from functions
49 /// which are not used by the body of the function. If
50 /// DeleteFromExternalFunctions is true, the pass will modify functions that
51 /// have external linkage, which is not usually safe (this is used by bugpoint
52 /// to reduce testcases).
54 Pass *createDeadArgEliminationPass(bool DeleteFromExternalFunctions) {
55 return new DAE(DeleteFromExternalFunctions);
59 // FunctionArgumentsIntrinsicallyAlive - Return true if the arguments of the
60 // specified function are intrinsically alive.
62 // We consider arguments of non-internal functions to be intrinsically alive as
63 // well as arguments to functions which have their "address taken".
65 bool DAE::FunctionArgumentsIntrinsicallyAlive(const Function &F) {
66 if (!F.hasInternalLinkage() && !DeleteFromExternalFunctions) return true;
68 for (Value::use_const_iterator I = F.use_begin(), E = F.use_end(); I!=E; ++I){
69 // If this use is anything other than a call site, the function is alive.
70 CallSite CS = CallSite::get(const_cast<User*>(*I));
71 if (!CS.getInstruction()) return true; // Not a valid call site?
73 // If the function is PASSED IN as an argument, its address has been taken
74 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); AI != E;
76 if (AI->get() == &F) return true;
82 enum ArgumentLiveness { Alive, MaybeLive, Dead };
85 // getArgumentLiveness - Inspect an argument, determining if is known Alive
86 // (used in a computation), MaybeLive (only passed as an argument to a call), or
88 static ArgumentLiveness getArgumentLiveness(const Argument &A) {
89 if (A.use_empty()) return Dead; // First check, directly dead?
91 // Scan through all of the uses, looking for non-argument passing uses.
92 for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) {
93 CallSite CS = CallSite::get(const_cast<User*>(*I));
94 if (!CS.getInstruction()) {
95 // If its used by something that is not a call or invoke, it's alive!
98 // If it's an indirect call, mark it alive...
99 Function *Callee = CS.getCalledFunction();
100 if (!Callee) return Alive;
102 // Check to see if it's passed through a va_arg area: if so, we cannot
104 unsigned NumFixedArgs = Callee->getFunctionType()->getNumParams();
105 for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs;
106 AI != CS.arg_end(); ++AI)
107 if (AI->get() == &A) // If passed through va_arg area, we cannot remove it
111 return MaybeLive; // It must be used, but only as argument to a function
114 // isMaybeLiveArgumentNowAlive - Check to see if Arg is alive. At this point,
115 // we know that the only uses of Arg are to be passed in as an argument to a
116 // function call. Check to see if the formal argument passed in is in the
117 // LiveArguments set. If so, return true.
119 static bool isMaybeLiveArgumentNowAlive(Argument *Arg,
120 const std::set<Argument*> &LiveArguments) {
121 for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){
122 CallSite CS = CallSite::get(*I);
124 // We know that this can only be used for direct calls...
125 Function *Callee = cast<Function>(CS.getCalledValue());
127 // Loop over all of the arguments (because Arg may be passed into the call
128 // multiple times) and check to see if any are now alive...
129 CallSite::arg_iterator CSAI = CS.arg_begin();
130 for (Function::aiterator AI = Callee->abegin(), E = Callee->aend();
131 AI != E; ++AI, ++CSAI)
132 // If this is the argument we are looking for, check to see if it's alive
133 if (*CSAI == Arg && LiveArguments.count(AI))
139 // MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive.
140 // Mark it live in the specified sets and recursively mark arguments in callers
141 // live that are needed to pass in a value.
143 static void MarkArgumentLive(Argument *Arg,
144 std::set<Argument*> &MaybeLiveArguments,
145 std::set<Argument*> &LiveArguments,
146 const std::multimap<Function*, CallSite> &CallSites) {
147 DEBUG(std::cerr << " MaybeLive argument now live: " << Arg->getName()<<"\n");
148 assert(MaybeLiveArguments.count(Arg) && !LiveArguments.count(Arg) &&
149 "Arg not MaybeLive?");
150 MaybeLiveArguments.erase(Arg);
151 LiveArguments.insert(Arg);
153 // Loop over all of the call sites of the function, making any arguments
154 // passed in to provide a value for this argument live as necessary.
156 Function *Fn = Arg->getParent();
157 unsigned ArgNo = std::distance(Fn->abegin(), Function::aiterator(Arg));
159 std::multimap<Function*, CallSite>::const_iterator I =
160 CallSites.lower_bound(Fn);
161 for (; I != CallSites.end() && I->first == Fn; ++I) {
162 const CallSite &CS = I->second;
163 if (Argument *ActualArg = dyn_cast<Argument>(*(CS.arg_begin()+ArgNo)))
164 if (MaybeLiveArguments.count(ActualArg))
165 MarkArgumentLive(ActualArg, MaybeLiveArguments, LiveArguments,
170 // RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as
171 // specified by the DeadArguments list. Transform the function and all of the
172 // callees of the function to not have these arguments.
174 void DAE::RemoveDeadArgumentsFromFunction(Function *F,
175 std::set<Argument*> &DeadArguments){
176 // Start by computing a new prototype for the function, which is the same as
177 // the old function, but has fewer arguments.
178 const FunctionType *FTy = F->getFunctionType();
179 std::vector<const Type*> Params;
181 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
182 if (!DeadArguments.count(I))
183 Params.push_back(I->getType());
185 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params,
188 // Create the new function body and insert it into the module...
189 Function *NF = new Function(NFTy, F->getLinkage(), F->getName());
190 F->getParent()->getFunctionList().insert(F, NF);
192 // Loop over all of the callers of the function, transforming the call sites
193 // to pass in a smaller number of arguments into the new function.
195 while (!F->use_empty()) {
196 CallSite CS = CallSite::get(F->use_back());
197 Instruction *Call = CS.getInstruction();
198 CS.setCalledFunction(NF); // Reduce the uses count of F
200 // Loop over the operands, deleting dead ones...
201 CallSite::arg_iterator AI = CS.arg_begin();
202 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
203 if (DeadArguments.count(I)) { // Remove operands for dead arguments
204 AI = Call->op_erase(AI);
206 ++AI; // Leave live operands alone...
210 // Since we have now created the new function, splice the body of the old
211 // function right into the new function, leaving the old rotting hulk of the
213 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
215 // Loop over the argument list, transfering uses of the old arguments over to
216 // the new arguments, also transfering over the names as well. While we're at
217 // it, remove the dead arguments from the DeadArguments list.
219 for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin();
221 if (!DeadArguments.count(I)) {
222 // If this is a live argument, move the name and users over to the new
224 I->replaceAllUsesWith(I2);
225 I2->setName(I->getName());
228 // If this argument is dead, replace any uses of it with null constants
229 // (these are guaranteed to only be operands to call instructions which
230 // will later be simplified).
231 I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
232 DeadArguments.erase(I);
235 // Now that the old function is dead, delete it.
236 F->getParent()->getFunctionList().erase(F);
239 bool DAE::run(Module &M) {
240 // First phase: loop through the module, determining which arguments are live.
241 // We assume all arguments are dead unless proven otherwise (allowing us to
242 // determine that dead arguments passed into recursive functions are dead).
244 std::set<Argument*> LiveArguments, MaybeLiveArguments, DeadArguments;
245 std::multimap<Function*, CallSite> CallSites;
247 DEBUG(std::cerr << "DAE - Determining liveness\n");
248 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
250 // If the function is intrinsically alive, just mark the arguments alive.
251 if (FunctionArgumentsIntrinsicallyAlive(Fn)) {
252 for (Function::aiterator AI = Fn.abegin(), E = Fn.aend(); AI != E; ++AI)
253 LiveArguments.insert(AI);
254 DEBUG(std::cerr << " Args intrinsically live for fn: " << Fn.getName()
257 DEBUG(std::cerr << " Inspecting args for fn: " << Fn.getName() << "\n");
259 // If it is not intrinsically alive, we know that all users of the
260 // function are call sites. Mark all of the arguments live which are
261 // directly used, and keep track of all of the call sites of this function
262 // if there are any arguments we assume that are dead.
264 bool AnyMaybeLiveArgs = false;
265 for (Function::aiterator AI = Fn.abegin(), E = Fn.aend(); AI != E; ++AI)
266 switch (getArgumentLiveness(*AI)) {
268 DEBUG(std::cerr << " Arg live by use: " << AI->getName() << "\n");
269 LiveArguments.insert(AI);
272 DEBUG(std::cerr << " Arg definitely dead: " <<AI->getName()<<"\n");
273 DeadArguments.insert(AI);
276 DEBUG(std::cerr << " Arg only passed to calls: "
277 << AI->getName() << "\n");
278 AnyMaybeLiveArgs = true;
279 MaybeLiveArguments.insert(AI);
283 // If there are any "MaybeLive" arguments, we need to check callees of
284 // this function when/if they become alive. Record which functions are
286 if (AnyMaybeLiveArgs)
287 for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end();
289 CallSites.insert(std::make_pair(&Fn, CallSite::get(*I)));
293 // Now we loop over all of the MaybeLive arguments, promoting them to be live
294 // arguments if one of the calls that uses the arguments to the calls they are
295 // passed into requires them to be live. Of course this could make other
296 // arguments live, so process callers recursively.
298 // Because elements can be removed from the MaybeLiveArguments list, copy it
299 // to a temporary vector.
301 std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(),
302 MaybeLiveArguments.end());
303 for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) {
304 Argument *MLA = TmpArgList[i];
305 if (MaybeLiveArguments.count(MLA) &&
306 isMaybeLiveArgumentNowAlive(MLA, LiveArguments)) {
307 MarkArgumentLive(MLA, MaybeLiveArguments, LiveArguments, CallSites);
311 // Recover memory early...
314 // At this point, we know that all arguments in DeadArguments and
315 // MaybeLiveArguments are dead. If the two sets are empty, there is nothing
317 if (MaybeLiveArguments.empty() && DeadArguments.empty())
320 // Otherwise, compact into one set, and start eliminating the arguments from
322 DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end());
323 MaybeLiveArguments.clear();
325 NumArgumentsEliminated += DeadArguments.size();
326 while (!DeadArguments.empty())
327 RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent(),