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