DeadArgumentElimination.cpp revision 4ee451de366474b9c228b4e5fa573795a715216d
1//===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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#define DEBUG_TYPE "deadargelim" 21#include "llvm/Transforms/IPO.h" 22#include "llvm/CallingConv.h" 23#include "llvm/Constant.h" 24#include "llvm/DerivedTypes.h" 25#include "llvm/Instructions.h" 26#include "llvm/IntrinsicInst.h" 27#include "llvm/Module.h" 28#include "llvm/Pass.h" 29#include "llvm/ParameterAttributes.h" 30#include "llvm/Support/CallSite.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/ADT/Statistic.h" 33#include "llvm/Support/Compiler.h" 34#include <set> 35using namespace llvm; 36 37STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 38STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 39 40namespace { 41 /// DAE - The dead argument elimination pass. 42 /// 43 class VISIBILITY_HIDDEN DAE : public ModulePass { 44 /// Liveness enum - During our initial pass over the program, we determine 45 /// that things are either definately alive, definately dead, or in need of 46 /// interprocedural analysis (MaybeLive). 47 /// 48 enum Liveness { Live, MaybeLive, Dead }; 49 50 /// LiveArguments, MaybeLiveArguments, DeadArguments - These sets contain 51 /// all of the arguments in the program. The Dead set contains arguments 52 /// which are completely dead (never used in the function). The MaybeLive 53 /// set contains arguments which are only passed into other function calls, 54 /// thus may be live and may be dead. The Live set contains arguments which 55 /// are known to be alive. 56 /// 57 std::set<Argument*> DeadArguments, MaybeLiveArguments, LiveArguments; 58 59 /// DeadRetVal, MaybeLiveRetVal, LifeRetVal - These sets contain all of the 60 /// functions in the program. The Dead set contains functions whose return 61 /// value is known to be dead. The MaybeLive set contains functions whose 62 /// return values are only used by return instructions, and the Live set 63 /// contains functions whose return values are used, functions that are 64 /// external, and functions that already return void. 65 /// 66 std::set<Function*> DeadRetVal, MaybeLiveRetVal, LiveRetVal; 67 68 /// InstructionsToInspect - As we mark arguments and return values 69 /// MaybeLive, we keep track of which instructions could make the values 70 /// live here. Once the entire program has had the return value and 71 /// arguments analyzed, this set is scanned to promote the MaybeLive objects 72 /// to be Live if they really are used. 73 std::vector<Instruction*> InstructionsToInspect; 74 75 /// CallSites - Keep track of the call sites of functions that have 76 /// MaybeLive arguments or return values. 77 std::multimap<Function*, CallSite> CallSites; 78 79 public: 80 static char ID; // Pass identification, replacement for typeid 81 DAE() : ModulePass((intptr_t)&ID) {} 82 bool runOnModule(Module &M); 83 84 virtual bool ShouldHackArguments() const { return false; } 85 86 private: 87 Liveness getArgumentLiveness(const Argument &A); 88 bool isMaybeLiveArgumentNowLive(Argument *Arg); 89 90 bool DeleteDeadVarargs(Function &Fn); 91 void SurveyFunction(Function &Fn); 92 93 void MarkArgumentLive(Argument *Arg); 94 void MarkRetValLive(Function *F); 95 void MarkReturnInstArgumentLive(ReturnInst *RI); 96 97 void RemoveDeadArgumentsFromFunction(Function *F); 98 }; 99 char DAE::ID = 0; 100 RegisterPass<DAE> X("deadargelim", "Dead Argument Elimination"); 101 102 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 103 /// deletes arguments to functions which are external. This is only for use 104 /// by bugpoint. 105 struct DAH : public DAE { 106 static char ID; 107 virtual bool ShouldHackArguments() const { return true; } 108 }; 109 char DAH::ID = 0; 110 RegisterPass<DAH> Y("deadarghaX0r", 111 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)"); 112} 113 114/// createDeadArgEliminationPass - This pass removes arguments from functions 115/// which are not used by the body of the function. 116/// 117ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 118ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 119 120/// DeleteDeadVarargs - If this is an function that takes a ... list, and if 121/// llvm.vastart is never called, the varargs list is dead for the function. 122bool DAE::DeleteDeadVarargs(Function &Fn) { 123 assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 124 if (Fn.isDeclaration() || !Fn.hasInternalLinkage()) return false; 125 126 // Ensure that the function is only directly called. 127 for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end(); I != E; ++I) { 128 // If this use is anything other than a call site, give up. 129 CallSite CS = CallSite::get(*I); 130 Instruction *TheCall = CS.getInstruction(); 131 if (!TheCall) return false; // Not a direct call site? 132 133 // The addr of this function is passed to the call. 134 if (I.getOperandNo() != 0) return false; 135 } 136 137 // Okay, we know we can transform this function if safe. Scan its body 138 // looking for calls to llvm.vastart. 139 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 140 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 141 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 142 if (II->getIntrinsicID() == Intrinsic::vastart) 143 return false; 144 } 145 } 146 } 147 148 // If we get here, there are no calls to llvm.vastart in the function body, 149 // remove the "..." and adjust all the calls. 150 151 // Start by computing a new prototype for the function, which is the same as 152 // the old function, but has fewer arguments. 153 const FunctionType *FTy = Fn.getFunctionType(); 154 std::vector<const Type*> Params(FTy->param_begin(), FTy->param_end()); 155 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false); 156 unsigned NumArgs = Params.size(); 157 158 // Create the new function body and insert it into the module... 159 Function *NF = new Function(NFTy, Fn.getLinkage()); 160 NF->setCallingConv(Fn.getCallingConv()); 161 NF->setParamAttrs(Fn.getParamAttrs()); 162 if (Fn.hasCollector()) 163 NF->setCollector(Fn.getCollector()); 164 Fn.getParent()->getFunctionList().insert(&Fn, NF); 165 NF->takeName(&Fn); 166 167 // Loop over all of the callers of the function, transforming the call sites 168 // to pass in a smaller number of arguments into the new function. 169 // 170 std::vector<Value*> Args; 171 while (!Fn.use_empty()) { 172 CallSite CS = CallSite::get(Fn.use_back()); 173 Instruction *Call = CS.getInstruction(); 174 175 // Pass all the same arguments. 176 Args.assign(CS.arg_begin(), CS.arg_begin()+NumArgs); 177 178 Instruction *New; 179 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 180 New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), 181 Args.begin(), Args.end(), "", Call); 182 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 183 cast<InvokeInst>(New)->setParamAttrs(CS.getParamAttrs()); 184 } else { 185 New = new CallInst(NF, Args.begin(), Args.end(), "", Call); 186 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 187 cast<CallInst>(New)->setParamAttrs(CS.getParamAttrs()); 188 if (cast<CallInst>(Call)->isTailCall()) 189 cast<CallInst>(New)->setTailCall(); 190 } 191 Args.clear(); 192 193 if (!Call->use_empty()) 194 Call->replaceAllUsesWith(New); 195 196 New->takeName(Call); 197 198 // Finally, remove the old call from the program, reducing the use-count of 199 // F. 200 Call->eraseFromParent(); 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(), Fn.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::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 213 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 214 // Move the name and users over to the new version. 215 I->replaceAllUsesWith(I2); 216 I2->takeName(I); 217 } 218 219 // Finally, nuke the old function. 220 Fn.eraseFromParent(); 221 return true; 222} 223 224 225static inline bool CallPassesValueThoughVararg(Instruction *Call, 226 const Value *Arg) { 227 CallSite CS = CallSite::get(Call); 228 const Type *CalledValueTy = CS.getCalledValue()->getType(); 229 const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType(); 230 unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams(); 231 for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs; 232 AI != CS.arg_end(); ++AI) 233 if (AI->get() == Arg) 234 return true; 235 return false; 236} 237 238// getArgumentLiveness - Inspect an argument, determining if is known Live 239// (used in a computation), MaybeLive (only passed as an argument to a call), or 240// Dead (not used). 241DAE::Liveness DAE::getArgumentLiveness(const Argument &A) { 242 const Function *F = A.getParent(); 243 244 // If this is the return value of a struct function, it's not really dead. 245 if (F->isStructReturn() && &*(F->arg_begin()) == &A) 246 return Live; 247 248 if (A.use_empty()) // First check, directly dead? 249 return Dead; 250 251 // Scan through all of the uses, looking for non-argument passing uses. 252 for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) { 253 // Return instructions do not immediately effect liveness. 254 if (isa<ReturnInst>(*I)) 255 continue; 256 257 CallSite CS = CallSite::get(const_cast<User*>(*I)); 258 if (!CS.getInstruction()) { 259 // If its used by something that is not a call or invoke, it's alive! 260 return Live; 261 } 262 // If it's an indirect call, mark it alive... 263 Function *Callee = CS.getCalledFunction(); 264 if (!Callee) return Live; 265 266 // Check to see if it's passed through a va_arg area: if so, we cannot 267 // remove it. 268 if (CallPassesValueThoughVararg(CS.getInstruction(), &A)) 269 return Live; // If passed through va_arg area, we cannot remove it 270 } 271 272 return MaybeLive; // It must be used, but only as argument to a function 273} 274 275 276// SurveyFunction - This performs the initial survey of the specified function, 277// checking out whether or not it uses any of its incoming arguments or whether 278// any callers use the return value. This fills in the 279// (Dead|MaybeLive|Live)(Arguments|RetVal) sets. 280// 281// We consider arguments of non-internal functions to be intrinsically alive as 282// well as arguments to functions which have their "address taken". 283// 284void DAE::SurveyFunction(Function &F) { 285 bool FunctionIntrinsicallyLive = false; 286 Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead; 287 288 if (!F.hasInternalLinkage() && 289 (!ShouldHackArguments() || F.isIntrinsic())) 290 FunctionIntrinsicallyLive = true; 291 else 292 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { 293 // If this use is anything other than a call site, the function is alive. 294 CallSite CS = CallSite::get(*I); 295 Instruction *TheCall = CS.getInstruction(); 296 if (!TheCall) { // Not a direct call site? 297 FunctionIntrinsicallyLive = true; 298 break; 299 } 300 301 // Check to see if the return value is used... 302 if (RetValLiveness != Live) 303 for (Value::use_iterator I = TheCall->use_begin(), 304 E = TheCall->use_end(); I != E; ++I) 305 if (isa<ReturnInst>(cast<Instruction>(*I))) { 306 RetValLiveness = MaybeLive; 307 } else if (isa<CallInst>(cast<Instruction>(*I)) || 308 isa<InvokeInst>(cast<Instruction>(*I))) { 309 if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) || 310 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) { 311 RetValLiveness = Live; 312 break; 313 } else { 314 RetValLiveness = MaybeLive; 315 } 316 } else { 317 RetValLiveness = Live; 318 break; 319 } 320 321 // If the function is PASSED IN as an argument, its address has been taken 322 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 323 AI != E; ++AI) 324 if (AI->get() == &F) { 325 FunctionIntrinsicallyLive = true; 326 break; 327 } 328 if (FunctionIntrinsicallyLive) break; 329 } 330 331 if (FunctionIntrinsicallyLive) { 332 DOUT << " Intrinsically live fn: " << F.getName() << "\n"; 333 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 334 AI != E; ++AI) 335 LiveArguments.insert(AI); 336 LiveRetVal.insert(&F); 337 return; 338 } 339 340 switch (RetValLiveness) { 341 case Live: LiveRetVal.insert(&F); break; 342 case MaybeLive: MaybeLiveRetVal.insert(&F); break; 343 case Dead: DeadRetVal.insert(&F); break; 344 } 345 346 DOUT << " Inspecting args for fn: " << F.getName() << "\n"; 347 348 // If it is not intrinsically alive, we know that all users of the 349 // function are call sites. Mark all of the arguments live which are 350 // directly used, and keep track of all of the call sites of this function 351 // if there are any arguments we assume that are dead. 352 // 353 bool AnyMaybeLiveArgs = false; 354 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 355 AI != E; ++AI) 356 switch (getArgumentLiveness(*AI)) { 357 case Live: 358 DOUT << " Arg live by use: " << AI->getName() << "\n"; 359 LiveArguments.insert(AI); 360 break; 361 case Dead: 362 DOUT << " Arg definitely dead: " << AI->getName() <<"\n"; 363 DeadArguments.insert(AI); 364 break; 365 case MaybeLive: 366 DOUT << " Arg only passed to calls: " << AI->getName() << "\n"; 367 AnyMaybeLiveArgs = true; 368 MaybeLiveArguments.insert(AI); 369 break; 370 } 371 372 // If there are any "MaybeLive" arguments, we need to check callees of 373 // this function when/if they become alive. Record which functions are 374 // callees... 375 if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive) 376 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); 377 I != E; ++I) { 378 if (AnyMaybeLiveArgs) 379 CallSites.insert(std::make_pair(&F, CallSite::get(*I))); 380 381 if (RetValLiveness == MaybeLive) 382 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 383 UI != E; ++UI) 384 InstructionsToInspect.push_back(cast<Instruction>(*UI)); 385 } 386} 387 388// isMaybeLiveArgumentNowLive - Check to see if Arg is alive. At this point, we 389// know that the only uses of Arg are to be passed in as an argument to a 390// function call or return. Check to see if the formal argument passed in is in 391// the LiveArguments set. If so, return true. 392// 393bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) { 394 for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){ 395 if (isa<ReturnInst>(*I)) { 396 if (LiveRetVal.count(Arg->getParent())) return true; 397 continue; 398 } 399 400 CallSite CS = CallSite::get(*I); 401 402 // We know that this can only be used for direct calls... 403 Function *Callee = CS.getCalledFunction(); 404 405 // Loop over all of the arguments (because Arg may be passed into the call 406 // multiple times) and check to see if any are now alive... 407 CallSite::arg_iterator CSAI = CS.arg_begin(); 408 for (Function::arg_iterator AI = Callee->arg_begin(), E = Callee->arg_end(); 409 AI != E; ++AI, ++CSAI) 410 // If this is the argument we are looking for, check to see if it's alive 411 if (*CSAI == Arg && LiveArguments.count(AI)) 412 return true; 413 } 414 return false; 415} 416 417/// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive. 418/// Mark it live in the specified sets and recursively mark arguments in callers 419/// live that are needed to pass in a value. 420/// 421void DAE::MarkArgumentLive(Argument *Arg) { 422 std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg); 423 if (It == MaybeLiveArguments.end() || *It != Arg) return; 424 425 DOUT << " MaybeLive argument now live: " << Arg->getName() <<"\n"; 426 MaybeLiveArguments.erase(It); 427 LiveArguments.insert(Arg); 428 429 // Loop over all of the call sites of the function, making any arguments 430 // passed in to provide a value for this argument live as necessary. 431 // 432 Function *Fn = Arg->getParent(); 433 unsigned ArgNo = std::distance(Fn->arg_begin(), Function::arg_iterator(Arg)); 434 435 std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn); 436 for (; I != CallSites.end() && I->first == Fn; ++I) { 437 CallSite CS = I->second; 438 Value *ArgVal = *(CS.arg_begin()+ArgNo); 439 if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) { 440 MarkArgumentLive(ActualArg); 441 } else { 442 // If the value passed in at this call site is a return value computed by 443 // some other call site, make sure to mark the return value at the other 444 // call site as being needed. 445 CallSite ArgCS = CallSite::get(ArgVal); 446 if (ArgCS.getInstruction()) 447 if (Function *Fn = ArgCS.getCalledFunction()) 448 MarkRetValLive(Fn); 449 } 450 } 451} 452 453/// MarkArgumentLive - The MaybeLive return value for the specified function is 454/// now known to be alive. Propagate this fact to the return instructions which 455/// produce it. 456void DAE::MarkRetValLive(Function *F) { 457 assert(F && "Shame shame, we can't have null pointers here!"); 458 459 // Check to see if we already knew it was live 460 std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F); 461 if (I == MaybeLiveRetVal.end() || *I != F) return; // It's already alive! 462 463 DOUT << " MaybeLive retval now live: " << F->getName() << "\n"; 464 465 MaybeLiveRetVal.erase(I); 466 LiveRetVal.insert(F); // It is now known to be live! 467 468 // Loop over all of the functions, noticing that the return value is now live. 469 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 470 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 471 MarkReturnInstArgumentLive(RI); 472} 473 474void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) { 475 Value *Op = RI->getOperand(0); 476 if (Argument *A = dyn_cast<Argument>(Op)) { 477 MarkArgumentLive(A); 478 } else if (CallInst *CI = dyn_cast<CallInst>(Op)) { 479 if (Function *F = CI->getCalledFunction()) 480 MarkRetValLive(F); 481 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) { 482 if (Function *F = II->getCalledFunction()) 483 MarkRetValLive(F); 484 } 485} 486 487// RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as 488// specified by the DeadArguments list. Transform the function and all of the 489// callees of the function to not have these arguments. 490// 491void DAE::RemoveDeadArgumentsFromFunction(Function *F) { 492 // Start by computing a new prototype for the function, which is the same as 493 // the old function, but has fewer arguments. 494 const FunctionType *FTy = F->getFunctionType(); 495 std::vector<const Type*> Params; 496 497 // Set up to build a new list of parameter attributes 498 ParamAttrsVector ParamAttrsVec; 499 const ParamAttrsList *PAL = F->getParamAttrs(); 500 501 // The existing function return attributes. 502 uint16_t RAttrs = PAL ? PAL->getParamAttrs(0) : 0; 503 504 // Make the function return void if the return value is dead. 505 const Type *RetTy = FTy->getReturnType(); 506 if (DeadRetVal.count(F)) { 507 RetTy = Type::VoidTy; 508 RAttrs &= ~ParamAttr::VoidTypeIncompatible; 509 DeadRetVal.erase(F); 510 } 511 512 if (RAttrs) 513 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); 514 515 // Construct the new parameter list from non-dead arguments. Also construct 516 // a new set of parameter attributes to correspond. 517 unsigned index = 1; 518 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 519 ++I, ++index) 520 if (!DeadArguments.count(I)) { 521 Params.push_back(I->getType()); 522 uint16_t Attrs = PAL ? PAL->getParamAttrs(index) : 0; 523 if (Attrs) 524 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Params.size(), Attrs)); 525 } 526 527 // Reconstruct the ParamAttrsList based on the vector we constructed. 528 PAL = ParamAttrsList::get(ParamAttrsVec); 529 530 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 531 // have zero fixed arguments. 532 // 533 bool ExtraArgHack = false; 534 if (Params.empty() && FTy->isVarArg()) { 535 ExtraArgHack = true; 536 Params.push_back(Type::Int32Ty); 537 } 538 539 // Create the new function type based on the recomputed parameters. 540 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 541 542 // Create the new function body and insert it into the module... 543 Function *NF = new Function(NFTy, F->getLinkage()); 544 NF->setCallingConv(F->getCallingConv()); 545 NF->setParamAttrs(PAL); 546 if (F->hasCollector()) 547 NF->setCollector(F->getCollector()); 548 F->getParent()->getFunctionList().insert(F, NF); 549 NF->takeName(F); 550 551 // Loop over all of the callers of the function, transforming the call sites 552 // to pass in a smaller number of arguments into the new function. 553 // 554 std::vector<Value*> Args; 555 while (!F->use_empty()) { 556 CallSite CS = CallSite::get(F->use_back()); 557 Instruction *Call = CS.getInstruction(); 558 ParamAttrsVec.clear(); 559 PAL = CS.getParamAttrs(); 560 561 // The call return attributes. 562 uint16_t RAttrs = PAL ? PAL->getParamAttrs(0) : 0; 563 // Adjust in case the function was changed to return void. 564 if (NF->getReturnType() == Type::VoidTy) 565 RAttrs &= ~ParamAttr::VoidTypeIncompatible; 566 if (RAttrs) 567 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); 568 569 // Loop over the operands, deleting dead ones... 570 CallSite::arg_iterator AI = CS.arg_begin(); 571 index = 1; 572 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 573 I != E; ++I, ++AI, ++index) 574 if (!DeadArguments.count(I)) { // Remove operands for dead arguments 575 Args.push_back(*AI); 576 uint16_t Attrs = PAL ? PAL->getParamAttrs(index) : 0; 577 if (Attrs) 578 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); 579 } 580 581 // Reconstruct the ParamAttrsList based on the vector we constructed. 582 PAL = ParamAttrsList::get(ParamAttrsVec); 583 584 if (ExtraArgHack) 585 Args.push_back(UndefValue::get(Type::Int32Ty)); 586 587 // Push any varargs arguments on the list 588 for (; AI != CS.arg_end(); ++AI) 589 Args.push_back(*AI); 590 591 Instruction *New; 592 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 593 New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), 594 Args.begin(), Args.end(), "", Call); 595 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 596 cast<InvokeInst>(New)->setParamAttrs(PAL); 597 } else { 598 New = new CallInst(NF, Args.begin(), Args.end(), "", Call); 599 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 600 cast<CallInst>(New)->setParamAttrs(PAL); 601 if (cast<CallInst>(Call)->isTailCall()) 602 cast<CallInst>(New)->setTailCall(); 603 } 604 Args.clear(); 605 606 if (!Call->use_empty()) { 607 if (New->getType() == Type::VoidTy) 608 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 609 else { 610 Call->replaceAllUsesWith(New); 611 New->takeName(Call); 612 } 613 } 614 615 // Finally, remove the old call from the program, reducing the use-count of 616 // F. 617 Call->getParent()->getInstList().erase(Call); 618 } 619 620 // Since we have now created the new function, splice the body of the old 621 // function right into the new function, leaving the old rotting hulk of the 622 // function empty. 623 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 624 625 // Loop over the argument list, transfering uses of the old arguments over to 626 // the new arguments, also transfering over the names as well. While we're at 627 // it, remove the dead arguments from the DeadArguments list. 628 // 629 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 630 I2 = NF->arg_begin(); 631 I != E; ++I) 632 if (!DeadArguments.count(I)) { 633 // If this is a live argument, move the name and users over to the new 634 // version. 635 I->replaceAllUsesWith(I2); 636 I2->takeName(I); 637 ++I2; 638 } else { 639 // If this argument is dead, replace any uses of it with null constants 640 // (these are guaranteed to only be operands to call instructions which 641 // will later be simplified). 642 I->replaceAllUsesWith(Constant::getNullValue(I->getType())); 643 DeadArguments.erase(I); 644 } 645 646 // If we change the return value of the function we must rewrite any return 647 // instructions. Check this now. 648 if (F->getReturnType() != NF->getReturnType()) 649 for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB) 650 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 651 new ReturnInst(0, RI); 652 BB->getInstList().erase(RI); 653 } 654 655 // Now that the old function is dead, delete it. 656 F->getParent()->getFunctionList().erase(F); 657} 658 659bool DAE::runOnModule(Module &M) { 660 bool Changed = false; 661 // First pass: Do a simple check to see if any functions can have their "..." 662 // removed. We can do this if they never call va_start. This loop cannot be 663 // fused with the next loop, because deleting a function invalidates 664 // information computed while surveying other functions. 665 DOUT << "DAE - Deleting dead varargs\n"; 666 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 667 Function &F = *I++; 668 if (F.getFunctionType()->isVarArg()) 669 Changed |= DeleteDeadVarargs(F); 670 } 671 672 // Second phase:loop through the module, determining which arguments are live. 673 // We assume all arguments are dead unless proven otherwise (allowing us to 674 // determine that dead arguments passed into recursive functions are dead). 675 // 676 DOUT << "DAE - Determining liveness\n"; 677 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 678 SurveyFunction(*I); 679 680 // Loop over the instructions to inspect, propagating liveness among arguments 681 // and return values which are MaybeLive. 682 while (!InstructionsToInspect.empty()) { 683 Instruction *I = InstructionsToInspect.back(); 684 InstructionsToInspect.pop_back(); 685 686 if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) { 687 // For return instructions, we just have to check to see if the return 688 // value for the current function is known now to be alive. If so, any 689 // arguments used by it are now alive, and any call instruction return 690 // value is alive as well. 691 if (LiveRetVal.count(RI->getParent()->getParent())) 692 MarkReturnInstArgumentLive(RI); 693 694 } else { 695 CallSite CS = CallSite::get(I); 696 assert(CS.getInstruction() && "Unknown instruction for the I2I list!"); 697 698 Function *Callee = CS.getCalledFunction(); 699 700 // If we found a call or invoke instruction on this list, that means that 701 // an argument of the function is a call instruction. If the argument is 702 // live, then the return value of the called instruction is now live. 703 // 704 CallSite::arg_iterator AI = CS.arg_begin(); // ActualIterator 705 for (Function::arg_iterator FI = Callee->arg_begin(), 706 E = Callee->arg_end(); FI != E; ++AI, ++FI) { 707 // If this argument is another call... 708 CallSite ArgCS = CallSite::get(*AI); 709 if (ArgCS.getInstruction() && LiveArguments.count(FI)) 710 if (Function *Callee = ArgCS.getCalledFunction()) 711 MarkRetValLive(Callee); 712 } 713 } 714 } 715 716 // Now we loop over all of the MaybeLive arguments, promoting them to be live 717 // arguments if one of the calls that uses the arguments to the calls they are 718 // passed into requires them to be live. Of course this could make other 719 // arguments live, so process callers recursively. 720 // 721 // Because elements can be removed from the MaybeLiveArguments set, copy it to 722 // a temporary vector. 723 // 724 std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(), 725 MaybeLiveArguments.end()); 726 for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) { 727 Argument *MLA = TmpArgList[i]; 728 if (MaybeLiveArguments.count(MLA) && 729 isMaybeLiveArgumentNowLive(MLA)) 730 MarkArgumentLive(MLA); 731 } 732 733 // Recover memory early... 734 CallSites.clear(); 735 736 // At this point, we know that all arguments in DeadArguments and 737 // MaybeLiveArguments are dead. If the two sets are empty, there is nothing 738 // to do. 739 if (MaybeLiveArguments.empty() && DeadArguments.empty() && 740 MaybeLiveRetVal.empty() && DeadRetVal.empty()) 741 return Changed; 742 743 // Otherwise, compact into one set, and start eliminating the arguments from 744 // the functions. 745 DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end()); 746 MaybeLiveArguments.clear(); 747 DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end()); 748 MaybeLiveRetVal.clear(); 749 750 LiveArguments.clear(); 751 LiveRetVal.clear(); 752 753 NumArgumentsEliminated += DeadArguments.size(); 754 NumRetValsEliminated += DeadRetVal.size(); 755 while (!DeadArguments.empty()) 756 RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent()); 757 758 while (!DeadRetVal.empty()) 759 RemoveDeadArgumentsFromFunction(*DeadRetVal.begin()); 760 return true; 761} 762