DeadArgumentElimination.cpp revision d6d0d8c18d64c5f212cd6c2b42b9bcde5acebf72
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#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" 31#include <set> 32 33namespace { 34 Statistic<> NumArgumentsEliminated("deadargelim", 35 "Number of unread args removed"); 36 Statistic<> NumRetValsEliminated("deadargelim", 37 "Number of unused return values removed"); 38 39 /// DAE - The dead argument elimination pass. 40 /// 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; 45 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). 49 /// 50 enum Liveness { Live, MaybeLive, Dead }; 51 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. 58 /// 59 std::set<Argument*> DeadArguments, MaybeLiveArguments, LiveArguments; 60 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. 67 /// 68 std::set<Function*> DeadRetVal, MaybeLiveRetVal, LiveRetVal; 69 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; 76 77 /// CallSites - Keep track of the call sites of functions that have 78 /// MaybeLive arguments or return values. 79 std::multimap<Function*, CallSite> CallSites; 80 81 public: 82 DAE(bool DFEF = false) : DeleteFromExternalFunctions(DFEF) {} 83 bool run(Module &M); 84 85 private: 86 Liveness getArgumentLiveness(const Argument &A); 87 bool isMaybeLiveArgumentNowLive(Argument *Arg); 88 89 void SurveyFunction(Function &Fn); 90 91 void MarkArgumentLive(Argument *Arg); 92 void MarkRetValLive(Function *F); 93 void MarkReturnInstArgumentLive(ReturnInst *RI); 94 95 void RemoveDeadArgumentsFromFunction(Function *F); 96 }; 97 RegisterOpt<DAE> X("deadargelim", "Dead Argument Elimination"); 98} 99 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). 105/// 106Pass *createDeadArgEliminationPass(bool DeleteFromExternalFunctions) { 107 return new DAE(DeleteFromExternalFunctions); 108} 109 110static inline bool CallPassesValueThoughVararg(Instruction *Call, 111 const Value *Arg) { 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) 119 return true; 120 return false; 121} 122 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 125// Dead (not used). 126DAE::Liveness DAE::getArgumentLiveness(const Argument &A) { 127 if (A.use_empty()) return Dead; // First check, directly dead? 128 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)) 133 continue; 134 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! 138 return Live; 139 } 140 // If it's an indirect call, mark it alive... 141 Function *Callee = CS.getCalledFunction(); 142 if (!Callee) return Live; 143 144 // Check to see if it's passed through a va_arg area: if so, we cannot 145 // remove it. 146 if (CallPassesValueThoughVararg(CS.getInstruction(), &A)) 147 return Live; // If passed through va_arg area, we cannot remove it 148 } 149 150 return MaybeLive; // It must be used, but only as argument to a function 151} 152 153 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. 158// 159// We consider arguments of non-internal functions to be intrinsically alive as 160// well as arguments to functions which have their "address taken". 161// 162void DAE::SurveyFunction(Function &F) { 163 bool FunctionIntrinsicallyLive = false; 164 Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead; 165 166 if (!F.hasInternalLinkage() && !DeleteFromExternalFunctions) 167 FunctionIntrinsicallyLive = true; 168 else 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; 175 break; 176 } 177 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; 189 break; 190 } else { 191 RetValLiveness = MaybeLive; 192 } 193 } else { 194 RetValLiveness = Live; 195 break; 196 } 197 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(); 200 AI != E; ++AI) 201 if (AI->get() == &F) { 202 FunctionIntrinsicallyLive = true; 203 break; 204 } 205 if (FunctionIntrinsicallyLive) break; 206 } 207 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); 213 return; 214 } 215 216 switch (RetValLiveness) { 217 case Live: LiveRetVal.insert(&F); break; 218 case MaybeLive: MaybeLiveRetVal.insert(&F); break; 219 case Dead: DeadRetVal.insert(&F); break; 220 } 221 222 DEBUG(std::cerr << " Inspecting args for fn: " << F.getName() << "\n"); 223 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. 228 // 229 bool AnyMaybeLiveArgs = false; 230 for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI) 231 switch (getArgumentLiveness(*AI)) { 232 case Live: 233 DEBUG(std::cerr << " Arg live by use: " << AI->getName() << "\n"); 234 LiveArguments.insert(AI); 235 break; 236 case Dead: 237 DEBUG(std::cerr << " Arg definitely dead: " <<AI->getName()<<"\n"); 238 DeadArguments.insert(AI); 239 break; 240 case MaybeLive: 241 DEBUG(std::cerr << " Arg only passed to calls: " 242 << AI->getName() << "\n"); 243 AnyMaybeLiveArgs = true; 244 MaybeLiveArguments.insert(AI); 245 break; 246 } 247 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 250 // callees... 251 if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive) 252 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); 253 I != E; ++I) { 254 if (AnyMaybeLiveArgs) 255 CallSites.insert(std::make_pair(&F, CallSite::get(*I))); 256 257 if (RetValLiveness == MaybeLive) 258 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 259 UI != E; ++UI) 260 InstructionsToInspect.push_back(cast<Instruction>(*UI)); 261 } 262} 263 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. 268// 269bool 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; 273 continue; 274 } 275 276 CallSite CS = CallSite::get(*I); 277 278 // We know that this can only be used for direct calls... 279 Function *Callee = CS.getCalledFunction(); 280 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)) 288 return true; 289 } 290 return false; 291} 292 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. 296/// 297void DAE::MarkArgumentLive(Argument *Arg) { 298 std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg); 299 if (It == MaybeLiveArguments.end() || *It != Arg) return; 300 301 DEBUG(std::cerr << " MaybeLive argument now live: " << Arg->getName()<<"\n"); 302 MaybeLiveArguments.erase(It); 303 LiveArguments.insert(Arg); 304 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. 307 // 308 Function *Fn = Arg->getParent(); 309 unsigned ArgNo = std::distance(Fn->abegin(), Function::aiterator(Arg)); 310 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); 317 } else { 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()) 324 MarkRetValLive(Fn); 325 } 326 } 327} 328 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 331/// produce it. 332void DAE::MarkRetValLive(Function *F) { 333 assert(F && "Shame shame, we can't have null pointers here!"); 334 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! 338 339 DEBUG(std::cerr << " MaybeLive retval now live: " << F->getName() << "\n"); 340 341 MaybeLiveRetVal.erase(I); 342 LiveRetVal.insert(F); // It is now known to be live! 343 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); 348} 349 350void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) { 351 Value *Op = RI->getOperand(0); 352 if (Argument *A = dyn_cast<Argument>(Op)) { 353 MarkArgumentLive(A); 354 } else if (CallInst *CI = dyn_cast<CallInst>(Op)) { 355 if (Function *F = CI->getCalledFunction()) 356 MarkRetValLive(F); 357 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) { 358 if (Function *F = II->getCalledFunction()) 359 MarkRetValLive(F); 360 } 361} 362 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. 366// 367void 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; 372 373 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) 374 if (!DeadArguments.count(I)) 375 Params.push_back(I->getType()); 376 377 const Type *RetTy = FTy->getReturnType(); 378 if (DeadRetVal.count(F)) { 379 RetTy = Type::VoidTy; 380 DeadRetVal.erase(F); 381 } 382 383 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 384 // have zero fixed arguments. 385 // 386 // FIXME: once this bug is fixed in the CWriter, this hack should be removed. 387 // 388 bool ExtraArgHack = false; 389 if (Params.empty() && FTy->isVarArg()) { 390 ExtraArgHack = true; 391 Params.push_back(Type::IntTy); 392 } 393 394 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 395 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); 399 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. 402 // 403 std::vector<Value*> Args; 404 while (!F->use_empty()) { 405 CallSite CS = CallSite::get(F->use_back()); 406 Instruction *Call = CS.getInstruction(); 407 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 412 Args.push_back(*AI); 413 414 if (ExtraArgHack) 415 Args.push_back(Constant::getNullValue(Type::IntTy)); 416 417 // Push any varargs arguments on the list 418 for (; AI != CS.arg_end(); ++AI) 419 Args.push_back(*AI); 420 421 Instruction *New; 422 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 423 New = new InvokeInst(NF, II->getNormalDest(), II->getExceptionalDest(), 424 Args, "", Call); 425 } else { 426 New = new CallInst(NF, Args, "", Call); 427 } 428 Args.clear(); 429 430 if (!Call->use_empty()) { 431 if (New->getType() == Type::VoidTy) 432 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 433 else { 434 Call->replaceAllUsesWith(New); 435 std::string Name = Call->getName(); 436 Call->setName(""); 437 New->setName(Name); 438 } 439 } 440 441 // Finally, remove the old call from the program, reducing the use-count of 442 // F. 443 Call->getParent()->getInstList().erase(Call); 444 } 445 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 448 // function empty. 449 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 450 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. 454 // 455 for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin(); 456 I != E; ++I) 457 if (!DeadArguments.count(I)) { 458 // If this is a live argument, move the name and users over to the new 459 // version. 460 I->replaceAllUsesWith(I2); 461 I2->setName(I->getName()); 462 ++I2; 463 } else { 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); 469 } 470 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); 478 } 479 480 // Now that the old function is dead, delete it. 481 F->getParent()->getFunctionList().erase(F); 482} 483 484bool 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). 488 // 489 DEBUG(std::cerr << "DAE - Determining liveness\n"); 490 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 491 SurveyFunction(*I); 492 493 // Loop over the instructions to inspect, propagating liveness among arguments 494 // and return values which are MaybeLive. 495 496 while (!InstructionsToInspect.empty()) { 497 Instruction *I = InstructionsToInspect.back(); 498 InstructionsToInspect.pop_back(); 499 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); 507 508 } else { 509 CallSite CS = CallSite::get(I); 510 assert(CS.getInstruction() && "Unknown instruction for the I2I list!"); 511 512 Function *Callee = CS.getCalledFunction(); 513 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. 517 // 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); 526 } 527 } 528 } 529 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. 534 // 535 // Because elements can be removed from the MaybeLiveArguments set, copy it to 536 // a temporary vector. 537 // 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); 545 } 546 547 // Recover memory early... 548 CallSites.clear(); 549 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 552 // to do. 553 if (MaybeLiveArguments.empty() && DeadArguments.empty() && 554 MaybeLiveRetVal.empty() && DeadRetVal.empty()) 555 return false; 556 557 // Otherwise, compact into one set, and start eliminating the arguments from 558 // the functions. 559 DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end()); 560 MaybeLiveArguments.clear(); 561 DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end()); 562 MaybeLiveRetVal.clear(); 563 564 LiveArguments.clear(); 565 LiveRetVal.clear(); 566 567 NumArgumentsEliminated += DeadArguments.size(); 568 NumRetValsEliminated += DeadRetVal.size(); 569 while (!DeadArguments.empty()) 570 RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent()); 571 572 while (!DeadRetVal.empty()) 573 RemoveDeadArgumentsFromFunction(*DeadRetVal.begin()); 574 return true; 575} 576