DeadArgumentElimination.cpp revision 7bc439a4b6c2d99707ebabf8f9b1c13041faa6a6
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 25namespace { 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/// 47Pass *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// 58bool 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 74namespace { 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). 81static 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// 112static 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// 136static 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// 167void 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 232bool 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 // determing 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} 324