DeadArgumentElimination.cpp revision aeb2a1d70807aa626f335fb23d47bc604ffeaa15
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> 32using namespace llvm; 33 34namespace { 35 Statistic<> NumArgumentsEliminated("deadargelim", 36 "Number of unread args removed"); 37 Statistic<> NumRetValsEliminated("deadargelim", 38 "Number of unused return values removed"); 39 40 /// DAE - The dead argument elimination pass. 41 /// 42 class DAE : public Pass { 43 /// Liveness enum - During our initial pass over the program, we determine 44 /// that things are either definately alive, definately dead, or in need of 45 /// interprocedural analysis (MaybeLive). 46 /// 47 enum Liveness { Live, MaybeLive, Dead }; 48 49 /// LiveArguments, MaybeLiveArguments, DeadArguments - These sets contain 50 /// all of the arguments in the program. The Dead set contains arguments 51 /// which are completely dead (never used in the function). The MaybeLive 52 /// set contains arguments which are only passed into other function calls, 53 /// thus may be live and may be dead. The Live set contains arguments which 54 /// are known to be alive. 55 /// 56 std::set<Argument*> DeadArguments, MaybeLiveArguments, LiveArguments; 57 58 /// DeadRetVal, MaybeLiveRetVal, LifeRetVal - These sets contain all of the 59 /// functions in the program. The Dead set contains functions whose return 60 /// value is known to be dead. The MaybeLive set contains functions whose 61 /// return values are only used by return instructions, and the Live set 62 /// contains functions whose return values are used, functions that are 63 /// external, and functions that already return void. 64 /// 65 std::set<Function*> DeadRetVal, MaybeLiveRetVal, LiveRetVal; 66 67 /// InstructionsToInspect - As we mark arguments and return values 68 /// MaybeLive, we keep track of which instructions could make the values 69 /// live here. Once the entire program has had the return value and 70 /// arguments analyzed, this set is scanned to promote the MaybeLive objects 71 /// to be Live if they really are used. 72 std::vector<Instruction*> InstructionsToInspect; 73 74 /// CallSites - Keep track of the call sites of functions that have 75 /// MaybeLive arguments or return values. 76 std::multimap<Function*, CallSite> CallSites; 77 78 public: 79 bool run(Module &M); 80 81 virtual bool ShouldHackArguments() const { return false; } 82 83 private: 84 Liveness getArgumentLiveness(const Argument &A); 85 bool isMaybeLiveArgumentNowLive(Argument *Arg); 86 87 void SurveyFunction(Function &Fn); 88 89 void MarkArgumentLive(Argument *Arg); 90 void MarkRetValLive(Function *F); 91 void MarkReturnInstArgumentLive(ReturnInst *RI); 92 93 void RemoveDeadArgumentsFromFunction(Function *F); 94 }; 95 RegisterOpt<DAE> X("deadargelim", "Dead Argument Elimination"); 96 97 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 98 /// deletes arguments to functions which are external. This is only for use 99 /// by bugpoint. 100 struct DAH : public DAE { 101 virtual bool ShouldHackArguments() const { return true; } 102 }; 103 RegisterPass<DAH> Y("deadarghaX0r", 104 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)"); 105} 106 107/// createDeadArgEliminationPass - This pass removes arguments from functions 108/// which are not used by the body of the function. 109/// 110Pass *llvm::createDeadArgEliminationPass() { return new DAE(); } 111Pass *llvm::createDeadArgHackingPass() { return new DAH(); } 112 113static inline bool CallPassesValueThoughVararg(Instruction *Call, 114 const Value *Arg) { 115 CallSite CS = CallSite::get(Call); 116 const Type *CalledValueTy = CS.getCalledValue()->getType(); 117 const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType(); 118 unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams(); 119 for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs; 120 AI != CS.arg_end(); ++AI) 121 if (AI->get() == Arg) 122 return true; 123 return false; 124} 125 126// getArgumentLiveness - Inspect an argument, determining if is known Live 127// (used in a computation), MaybeLive (only passed as an argument to a call), or 128// Dead (not used). 129DAE::Liveness DAE::getArgumentLiveness(const Argument &A) { 130 if (A.use_empty()) return Dead; // First check, directly dead? 131 132 // Scan through all of the uses, looking for non-argument passing uses. 133 for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) { 134 // Return instructions do not immediately effect liveness. 135 if (isa<ReturnInst>(*I)) 136 continue; 137 138 CallSite CS = CallSite::get(const_cast<User*>(*I)); 139 if (!CS.getInstruction()) { 140 // If its used by something that is not a call or invoke, it's alive! 141 return Live; 142 } 143 // If it's an indirect call, mark it alive... 144 Function *Callee = CS.getCalledFunction(); 145 if (!Callee) return Live; 146 147 // Check to see if it's passed through a va_arg area: if so, we cannot 148 // remove it. 149 if (CallPassesValueThoughVararg(CS.getInstruction(), &A)) 150 return Live; // If passed through va_arg area, we cannot remove it 151 } 152 153 return MaybeLive; // It must be used, but only as argument to a function 154} 155 156 157// SurveyFunction - This performs the initial survey of the specified function, 158// checking out whether or not it uses any of its incoming arguments or whether 159// any callers use the return value. This fills in the 160// (Dead|MaybeLive|Live)(Arguments|RetVal) sets. 161// 162// We consider arguments of non-internal functions to be intrinsically alive as 163// well as arguments to functions which have their "address taken". 164// 165void DAE::SurveyFunction(Function &F) { 166 bool FunctionIntrinsicallyLive = false; 167 Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead; 168 169 if (!F.hasInternalLinkage() && 170 (!ShouldHackArguments() || F.getIntrinsicID())) 171 FunctionIntrinsicallyLive = true; 172 else 173 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { 174 // If this use is anything other than a call site, the function is alive. 175 CallSite CS = CallSite::get(*I); 176 Instruction *TheCall = CS.getInstruction(); 177 if (!TheCall) { // Not a direct call site? 178 FunctionIntrinsicallyLive = true; 179 break; 180 } 181 182 // Check to see if the return value is used... 183 if (RetValLiveness != Live) 184 for (Value::use_iterator I = TheCall->use_begin(), 185 E = TheCall->use_end(); I != E; ++I) 186 if (isa<ReturnInst>(cast<Instruction>(*I))) { 187 RetValLiveness = MaybeLive; 188 } else if (isa<CallInst>(cast<Instruction>(*I)) || 189 isa<InvokeInst>(cast<Instruction>(*I))) { 190 if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) || 191 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) { 192 RetValLiveness = Live; 193 break; 194 } else { 195 RetValLiveness = MaybeLive; 196 } 197 } else { 198 RetValLiveness = Live; 199 break; 200 } 201 202 // If the function is PASSED IN as an argument, its address has been taken 203 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 204 AI != E; ++AI) 205 if (AI->get() == &F) { 206 FunctionIntrinsicallyLive = true; 207 break; 208 } 209 if (FunctionIntrinsicallyLive) break; 210 } 211 212 if (FunctionIntrinsicallyLive) { 213 DEBUG(std::cerr << " Intrinsically live fn: " << F.getName() << "\n"); 214 for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI) 215 LiveArguments.insert(AI); 216 LiveRetVal.insert(&F); 217 return; 218 } 219 220 switch (RetValLiveness) { 221 case Live: LiveRetVal.insert(&F); break; 222 case MaybeLive: MaybeLiveRetVal.insert(&F); break; 223 case Dead: DeadRetVal.insert(&F); break; 224 } 225 226 DEBUG(std::cerr << " Inspecting args for fn: " << F.getName() << "\n"); 227 228 // If it is not intrinsically alive, we know that all users of the 229 // function are call sites. Mark all of the arguments live which are 230 // directly used, and keep track of all of the call sites of this function 231 // if there are any arguments we assume that are dead. 232 // 233 bool AnyMaybeLiveArgs = false; 234 for (Function::aiterator AI = F.abegin(), E = F.aend(); AI != E; ++AI) 235 switch (getArgumentLiveness(*AI)) { 236 case Live: 237 DEBUG(std::cerr << " Arg live by use: " << AI->getName() << "\n"); 238 LiveArguments.insert(AI); 239 break; 240 case Dead: 241 DEBUG(std::cerr << " Arg definitely dead: " <<AI->getName()<<"\n"); 242 DeadArguments.insert(AI); 243 break; 244 case MaybeLive: 245 DEBUG(std::cerr << " Arg only passed to calls: " 246 << AI->getName() << "\n"); 247 AnyMaybeLiveArgs = true; 248 MaybeLiveArguments.insert(AI); 249 break; 250 } 251 252 // If there are any "MaybeLive" arguments, we need to check callees of 253 // this function when/if they become alive. Record which functions are 254 // callees... 255 if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive) 256 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); 257 I != E; ++I) { 258 if (AnyMaybeLiveArgs) 259 CallSites.insert(std::make_pair(&F, CallSite::get(*I))); 260 261 if (RetValLiveness == MaybeLive) 262 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 263 UI != E; ++UI) 264 InstructionsToInspect.push_back(cast<Instruction>(*UI)); 265 } 266} 267 268// isMaybeLiveArgumentNowLive - Check to see if Arg is alive. At this point, we 269// know that the only uses of Arg are to be passed in as an argument to a 270// function call or return. Check to see if the formal argument passed in is in 271// the LiveArguments set. If so, return true. 272// 273bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) { 274 for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){ 275 if (isa<ReturnInst>(*I)) { 276 if (LiveRetVal.count(Arg->getParent())) return true; 277 continue; 278 } 279 280 CallSite CS = CallSite::get(*I); 281 282 // We know that this can only be used for direct calls... 283 Function *Callee = CS.getCalledFunction(); 284 285 // Loop over all of the arguments (because Arg may be passed into the call 286 // multiple times) and check to see if any are now alive... 287 CallSite::arg_iterator CSAI = CS.arg_begin(); 288 for (Function::aiterator AI = Callee->abegin(), E = Callee->aend(); 289 AI != E; ++AI, ++CSAI) 290 // If this is the argument we are looking for, check to see if it's alive 291 if (*CSAI == Arg && LiveArguments.count(AI)) 292 return true; 293 } 294 return false; 295} 296 297/// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive. 298/// Mark it live in the specified sets and recursively mark arguments in callers 299/// live that are needed to pass in a value. 300/// 301void DAE::MarkArgumentLive(Argument *Arg) { 302 std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg); 303 if (It == MaybeLiveArguments.end() || *It != Arg) return; 304 305 DEBUG(std::cerr << " MaybeLive argument now live: " << Arg->getName()<<"\n"); 306 MaybeLiveArguments.erase(It); 307 LiveArguments.insert(Arg); 308 309 // Loop over all of the call sites of the function, making any arguments 310 // passed in to provide a value for this argument live as necessary. 311 // 312 Function *Fn = Arg->getParent(); 313 unsigned ArgNo = std::distance(Fn->abegin(), Function::aiterator(Arg)); 314 315 std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn); 316 for (; I != CallSites.end() && I->first == Fn; ++I) { 317 CallSite CS = I->second; 318 Value *ArgVal = *(CS.arg_begin()+ArgNo); 319 if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) { 320 MarkArgumentLive(ActualArg); 321 } else { 322 // If the value passed in at this call site is a return value computed by 323 // some other call site, make sure to mark the return value at the other 324 // call site as being needed. 325 CallSite ArgCS = CallSite::get(ArgVal); 326 if (ArgCS.getInstruction()) 327 if (Function *Fn = ArgCS.getCalledFunction()) 328 MarkRetValLive(Fn); 329 } 330 } 331} 332 333/// MarkArgumentLive - The MaybeLive return value for the specified function is 334/// now known to be alive. Propagate this fact to the return instructions which 335/// produce it. 336void DAE::MarkRetValLive(Function *F) { 337 assert(F && "Shame shame, we can't have null pointers here!"); 338 339 // Check to see if we already knew it was live 340 std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F); 341 if (I == MaybeLiveRetVal.end() || *I != F) return; // It's already alive! 342 343 DEBUG(std::cerr << " MaybeLive retval now live: " << F->getName() << "\n"); 344 345 MaybeLiveRetVal.erase(I); 346 LiveRetVal.insert(F); // It is now known to be live! 347 348 // Loop over all of the functions, noticing that the return value is now live. 349 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 350 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 351 MarkReturnInstArgumentLive(RI); 352} 353 354void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) { 355 Value *Op = RI->getOperand(0); 356 if (Argument *A = dyn_cast<Argument>(Op)) { 357 MarkArgumentLive(A); 358 } else if (CallInst *CI = dyn_cast<CallInst>(Op)) { 359 if (Function *F = CI->getCalledFunction()) 360 MarkRetValLive(F); 361 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) { 362 if (Function *F = II->getCalledFunction()) 363 MarkRetValLive(F); 364 } 365} 366 367// RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as 368// specified by the DeadArguments list. Transform the function and all of the 369// callees of the function to not have these arguments. 370// 371void DAE::RemoveDeadArgumentsFromFunction(Function *F) { 372 // Start by computing a new prototype for the function, which is the same as 373 // the old function, but has fewer arguments. 374 const FunctionType *FTy = F->getFunctionType(); 375 std::vector<const Type*> Params; 376 377 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) 378 if (!DeadArguments.count(I)) 379 Params.push_back(I->getType()); 380 381 const Type *RetTy = FTy->getReturnType(); 382 if (DeadRetVal.count(F)) { 383 RetTy = Type::VoidTy; 384 DeadRetVal.erase(F); 385 } 386 387 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 388 // have zero fixed arguments. 389 // 390 // FIXME: once this bug is fixed in the CWriter, this hack should be removed. 391 // 392 bool ExtraArgHack = false; 393 if (Params.empty() && FTy->isVarArg()) { 394 ExtraArgHack = true; 395 Params.push_back(Type::IntTy); 396 } 397 398 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 399 400 // Create the new function body and insert it into the module... 401 Function *NF = new Function(NFTy, F->getLinkage(), F->getName()); 402 F->getParent()->getFunctionList().insert(F, NF); 403 404 // Loop over all of the callers of the function, transforming the call sites 405 // to pass in a smaller number of arguments into the new function. 406 // 407 std::vector<Value*> Args; 408 while (!F->use_empty()) { 409 CallSite CS = CallSite::get(F->use_back()); 410 Instruction *Call = CS.getInstruction(); 411 412 // Loop over the operands, deleting dead ones... 413 CallSite::arg_iterator AI = CS.arg_begin(); 414 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++AI) 415 if (!DeadArguments.count(I)) // Remove operands for dead arguments 416 Args.push_back(*AI); 417 418 if (ExtraArgHack) 419 Args.push_back(Constant::getNullValue(Type::IntTy)); 420 421 // Push any varargs arguments on the list 422 for (; AI != CS.arg_end(); ++AI) 423 Args.push_back(*AI); 424 425 Instruction *New; 426 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 427 New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), 428 Args, "", Call); 429 } else { 430 New = new CallInst(NF, Args, "", Call); 431 } 432 Args.clear(); 433 434 if (!Call->use_empty()) { 435 if (New->getType() == Type::VoidTy) 436 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 437 else { 438 Call->replaceAllUsesWith(New); 439 std::string Name = Call->getName(); 440 Call->setName(""); 441 New->setName(Name); 442 } 443 } 444 445 // Finally, remove the old call from the program, reducing the use-count of 446 // F. 447 Call->getParent()->getInstList().erase(Call); 448 } 449 450 // Since we have now created the new function, splice the body of the old 451 // function right into the new function, leaving the old rotting hulk of the 452 // function empty. 453 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 454 455 // Loop over the argument list, transfering uses of the old arguments over to 456 // the new arguments, also transfering over the names as well. While we're at 457 // it, remove the dead arguments from the DeadArguments list. 458 // 459 for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin(); 460 I != E; ++I) 461 if (!DeadArguments.count(I)) { 462 // If this is a live argument, move the name and users over to the new 463 // version. 464 I->replaceAllUsesWith(I2); 465 I2->setName(I->getName()); 466 ++I2; 467 } else { 468 // If this argument is dead, replace any uses of it with null constants 469 // (these are guaranteed to only be operands to call instructions which 470 // will later be simplified). 471 I->replaceAllUsesWith(Constant::getNullValue(I->getType())); 472 DeadArguments.erase(I); 473 } 474 475 // If we change the return value of the function we must rewrite any return 476 // instructions. Check this now. 477 if (F->getReturnType() != NF->getReturnType()) 478 for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB) 479 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 480 new ReturnInst(0, RI); 481 BB->getInstList().erase(RI); 482 } 483 484 // Now that the old function is dead, delete it. 485 F->getParent()->getFunctionList().erase(F); 486} 487 488bool DAE::run(Module &M) { 489 // First phase: loop through the module, determining which arguments are live. 490 // We assume all arguments are dead unless proven otherwise (allowing us to 491 // determine that dead arguments passed into recursive functions are dead). 492 // 493 DEBUG(std::cerr << "DAE - Determining liveness\n"); 494 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 495 SurveyFunction(*I); 496 497 // Loop over the instructions to inspect, propagating liveness among arguments 498 // and return values which are MaybeLive. 499 500 while (!InstructionsToInspect.empty()) { 501 Instruction *I = InstructionsToInspect.back(); 502 InstructionsToInspect.pop_back(); 503 504 if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) { 505 // For return instructions, we just have to check to see if the return 506 // value for the current function is known now to be alive. If so, any 507 // arguments used by it are now alive, and any call instruction return 508 // value is alive as well. 509 if (LiveRetVal.count(RI->getParent()->getParent())) 510 MarkReturnInstArgumentLive(RI); 511 512 } else { 513 CallSite CS = CallSite::get(I); 514 assert(CS.getInstruction() && "Unknown instruction for the I2I list!"); 515 516 Function *Callee = CS.getCalledFunction(); 517 518 // If we found a call or invoke instruction on this list, that means that 519 // an argument of the function is a call instruction. If the argument is 520 // live, then the return value of the called instruction is now live. 521 // 522 CallSite::arg_iterator AI = CS.arg_begin(); // ActualIterator 523 for (Function::aiterator FI = Callee->abegin(), E = Callee->aend(); 524 FI != E; ++AI, ++FI) { 525 // If this argument is another call... 526 CallSite ArgCS = CallSite::get(*AI); 527 if (ArgCS.getInstruction() && LiveArguments.count(FI)) 528 if (Function *Callee = ArgCS.getCalledFunction()) 529 MarkRetValLive(Callee); 530 } 531 } 532 } 533 534 // Now we loop over all of the MaybeLive arguments, promoting them to be live 535 // arguments if one of the calls that uses the arguments to the calls they are 536 // passed into requires them to be live. Of course this could make other 537 // arguments live, so process callers recursively. 538 // 539 // Because elements can be removed from the MaybeLiveArguments set, copy it to 540 // a temporary vector. 541 // 542 std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(), 543 MaybeLiveArguments.end()); 544 for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) { 545 Argument *MLA = TmpArgList[i]; 546 if (MaybeLiveArguments.count(MLA) && 547 isMaybeLiveArgumentNowLive(MLA)) 548 MarkArgumentLive(MLA); 549 } 550 551 // Recover memory early... 552 CallSites.clear(); 553 554 // At this point, we know that all arguments in DeadArguments and 555 // MaybeLiveArguments are dead. If the two sets are empty, there is nothing 556 // to do. 557 if (MaybeLiveArguments.empty() && DeadArguments.empty() && 558 MaybeLiveRetVal.empty() && DeadRetVal.empty()) 559 return false; 560 561 // Otherwise, compact into one set, and start eliminating the arguments from 562 // the functions. 563 DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end()); 564 MaybeLiveArguments.clear(); 565 DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end()); 566 MaybeLiveRetVal.clear(); 567 568 LiveArguments.clear(); 569 LiveRetVal.clear(); 570 571 NumArgumentsEliminated += DeadArguments.size(); 572 NumRetValsEliminated += DeadRetVal.size(); 573 while (!DeadArguments.empty()) 574 RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent()); 575 576 while (!DeadRetVal.empty()) 577 RemoveDeadArgumentsFromFunction(*DeadRetVal.begin()); 578 return true; 579} 580