DeadArgumentElimination.cpp revision 0d51e7ec0d2dcbea9e304fd58deb05f37eb75635
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 // Drop any attributes that were on the vararg arguments. 179 const ParamAttrsList *PAL = CS.getParamAttrs(); 180 if (PAL && PAL->getParamIndex(PAL->size() - 1) > NumArgs) { 181 ParamAttrsVector ParamAttrsVec; 182 for (unsigned i = 0; PAL->getParamIndex(i) <= NumArgs; ++i) { 183 ParamAttrsWithIndex PAWI; 184 PAWI = ParamAttrsWithIndex::get(PAL->getParamIndex(i), 185 PAL->getParamAttrsAtIndex(i)); 186 ParamAttrsVec.push_back(PAWI); 187 } 188 PAL = ParamAttrsList::get(ParamAttrsVec); 189 } 190 191 Instruction *New; 192 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 193 New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), 194 Args.begin(), Args.end(), "", Call); 195 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 196 cast<InvokeInst>(New)->setParamAttrs(PAL); 197 } else { 198 New = new CallInst(NF, Args.begin(), Args.end(), "", Call); 199 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 200 cast<CallInst>(New)->setParamAttrs(PAL); 201 if (cast<CallInst>(Call)->isTailCall()) 202 cast<CallInst>(New)->setTailCall(); 203 } 204 Args.clear(); 205 206 if (!Call->use_empty()) 207 Call->replaceAllUsesWith(New); 208 209 New->takeName(Call); 210 211 // Finally, remove the old call from the program, reducing the use-count of 212 // F. 213 Call->eraseFromParent(); 214 } 215 216 // Since we have now created the new function, splice the body of the old 217 // function right into the new function, leaving the old rotting hulk of the 218 // function empty. 219 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 220 221 // Loop over the argument list, transfering uses of the old arguments over to 222 // the new arguments, also transfering over the names as well. While we're at 223 // it, remove the dead arguments from the DeadArguments list. 224 // 225 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 226 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 227 // Move the name and users over to the new version. 228 I->replaceAllUsesWith(I2); 229 I2->takeName(I); 230 } 231 232 // Finally, nuke the old function. 233 Fn.eraseFromParent(); 234 return true; 235} 236 237 238static inline bool CallPassesValueThoughVararg(Instruction *Call, 239 const Value *Arg) { 240 CallSite CS = CallSite::get(Call); 241 const Type *CalledValueTy = CS.getCalledValue()->getType(); 242 const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType(); 243 unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams(); 244 for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs; 245 AI != CS.arg_end(); ++AI) 246 if (AI->get() == Arg) 247 return true; 248 return false; 249} 250 251// getArgumentLiveness - Inspect an argument, determining if is known Live 252// (used in a computation), MaybeLive (only passed as an argument to a call), or 253// Dead (not used). 254DAE::Liveness DAE::getArgumentLiveness(const Argument &A) { 255 const Function *F = A.getParent(); 256 257 // If this is the return value of a struct function, it's not really dead. 258 if (F->isStructReturn() && &*(F->arg_begin()) == &A) 259 return Live; 260 261 if (A.use_empty()) // First check, directly dead? 262 return Dead; 263 264 // Scan through all of the uses, looking for non-argument passing uses. 265 for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) { 266 // Return instructions do not immediately effect liveness. 267 if (isa<ReturnInst>(*I)) 268 continue; 269 270 CallSite CS = CallSite::get(const_cast<User*>(*I)); 271 if (!CS.getInstruction()) { 272 // If its used by something that is not a call or invoke, it's alive! 273 return Live; 274 } 275 // If it's an indirect call, mark it alive... 276 Function *Callee = CS.getCalledFunction(); 277 if (!Callee) return Live; 278 279 // Check to see if it's passed through a va_arg area: if so, we cannot 280 // remove it. 281 if (CallPassesValueThoughVararg(CS.getInstruction(), &A)) 282 return Live; // If passed through va_arg area, we cannot remove it 283 } 284 285 return MaybeLive; // It must be used, but only as argument to a function 286} 287 288 289// SurveyFunction - This performs the initial survey of the specified function, 290// checking out whether or not it uses any of its incoming arguments or whether 291// any callers use the return value. This fills in the 292// (Dead|MaybeLive|Live)(Arguments|RetVal) sets. 293// 294// We consider arguments of non-internal functions to be intrinsically alive as 295// well as arguments to functions which have their "address taken". 296// 297void DAE::SurveyFunction(Function &F) { 298 bool FunctionIntrinsicallyLive = false; 299 Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead; 300 301 if (!F.hasInternalLinkage() && 302 (!ShouldHackArguments() || F.isIntrinsic())) 303 FunctionIntrinsicallyLive = true; 304 else 305 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { 306 // If this use is anything other than a call site, the function is alive. 307 CallSite CS = CallSite::get(*I); 308 Instruction *TheCall = CS.getInstruction(); 309 if (!TheCall) { // Not a direct call site? 310 FunctionIntrinsicallyLive = true; 311 break; 312 } 313 314 // Check to see if the return value is used... 315 if (RetValLiveness != Live) 316 for (Value::use_iterator I = TheCall->use_begin(), 317 E = TheCall->use_end(); I != E; ++I) 318 if (isa<ReturnInst>(cast<Instruction>(*I))) { 319 RetValLiveness = MaybeLive; 320 } else if (isa<CallInst>(cast<Instruction>(*I)) || 321 isa<InvokeInst>(cast<Instruction>(*I))) { 322 if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) || 323 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) { 324 RetValLiveness = Live; 325 break; 326 } else { 327 RetValLiveness = MaybeLive; 328 } 329 } else { 330 RetValLiveness = Live; 331 break; 332 } 333 334 // If the function is PASSED IN as an argument, its address has been taken 335 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 336 AI != E; ++AI) 337 if (AI->get() == &F) { 338 FunctionIntrinsicallyLive = true; 339 break; 340 } 341 if (FunctionIntrinsicallyLive) break; 342 } 343 344 if (FunctionIntrinsicallyLive) { 345 DOUT << " Intrinsically live fn: " << F.getName() << "\n"; 346 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 347 AI != E; ++AI) 348 LiveArguments.insert(AI); 349 LiveRetVal.insert(&F); 350 return; 351 } 352 353 switch (RetValLiveness) { 354 case Live: LiveRetVal.insert(&F); break; 355 case MaybeLive: MaybeLiveRetVal.insert(&F); break; 356 case Dead: DeadRetVal.insert(&F); break; 357 } 358 359 DOUT << " Inspecting args for fn: " << F.getName() << "\n"; 360 361 // If it is not intrinsically alive, we know that all users of the 362 // function are call sites. Mark all of the arguments live which are 363 // directly used, and keep track of all of the call sites of this function 364 // if there are any arguments we assume that are dead. 365 // 366 bool AnyMaybeLiveArgs = false; 367 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 368 AI != E; ++AI) 369 switch (getArgumentLiveness(*AI)) { 370 case Live: 371 DOUT << " Arg live by use: " << AI->getName() << "\n"; 372 LiveArguments.insert(AI); 373 break; 374 case Dead: 375 DOUT << " Arg definitely dead: " << AI->getName() <<"\n"; 376 DeadArguments.insert(AI); 377 break; 378 case MaybeLive: 379 DOUT << " Arg only passed to calls: " << AI->getName() << "\n"; 380 AnyMaybeLiveArgs = true; 381 MaybeLiveArguments.insert(AI); 382 break; 383 } 384 385 // If there are any "MaybeLive" arguments, we need to check callees of 386 // this function when/if they become alive. Record which functions are 387 // callees... 388 if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive) 389 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); 390 I != E; ++I) { 391 if (AnyMaybeLiveArgs) 392 CallSites.insert(std::make_pair(&F, CallSite::get(*I))); 393 394 if (RetValLiveness == MaybeLive) 395 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 396 UI != E; ++UI) 397 InstructionsToInspect.push_back(cast<Instruction>(*UI)); 398 } 399} 400 401// isMaybeLiveArgumentNowLive - Check to see if Arg is alive. At this point, we 402// know that the only uses of Arg are to be passed in as an argument to a 403// function call or return. Check to see if the formal argument passed in is in 404// the LiveArguments set. If so, return true. 405// 406bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) { 407 for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){ 408 if (isa<ReturnInst>(*I)) { 409 if (LiveRetVal.count(Arg->getParent())) return true; 410 continue; 411 } 412 413 CallSite CS = CallSite::get(*I); 414 415 // We know that this can only be used for direct calls... 416 Function *Callee = CS.getCalledFunction(); 417 418 // Loop over all of the arguments (because Arg may be passed into the call 419 // multiple times) and check to see if any are now alive... 420 CallSite::arg_iterator CSAI = CS.arg_begin(); 421 for (Function::arg_iterator AI = Callee->arg_begin(), E = Callee->arg_end(); 422 AI != E; ++AI, ++CSAI) 423 // If this is the argument we are looking for, check to see if it's alive 424 if (*CSAI == Arg && LiveArguments.count(AI)) 425 return true; 426 } 427 return false; 428} 429 430/// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive. 431/// Mark it live in the specified sets and recursively mark arguments in callers 432/// live that are needed to pass in a value. 433/// 434void DAE::MarkArgumentLive(Argument *Arg) { 435 std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg); 436 if (It == MaybeLiveArguments.end() || *It != Arg) return; 437 438 DOUT << " MaybeLive argument now live: " << Arg->getName() <<"\n"; 439 MaybeLiveArguments.erase(It); 440 LiveArguments.insert(Arg); 441 442 // Loop over all of the call sites of the function, making any arguments 443 // passed in to provide a value for this argument live as necessary. 444 // 445 Function *Fn = Arg->getParent(); 446 unsigned ArgNo = std::distance(Fn->arg_begin(), Function::arg_iterator(Arg)); 447 448 std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn); 449 for (; I != CallSites.end() && I->first == Fn; ++I) { 450 CallSite CS = I->second; 451 Value *ArgVal = *(CS.arg_begin()+ArgNo); 452 if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) { 453 MarkArgumentLive(ActualArg); 454 } else { 455 // If the value passed in at this call site is a return value computed by 456 // some other call site, make sure to mark the return value at the other 457 // call site as being needed. 458 CallSite ArgCS = CallSite::get(ArgVal); 459 if (ArgCS.getInstruction()) 460 if (Function *Fn = ArgCS.getCalledFunction()) 461 MarkRetValLive(Fn); 462 } 463 } 464} 465 466/// MarkArgumentLive - The MaybeLive return value for the specified function is 467/// now known to be alive. Propagate this fact to the return instructions which 468/// produce it. 469void DAE::MarkRetValLive(Function *F) { 470 assert(F && "Shame shame, we can't have null pointers here!"); 471 472 // Check to see if we already knew it was live 473 std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F); 474 if (I == MaybeLiveRetVal.end() || *I != F) return; // It's already alive! 475 476 DOUT << " MaybeLive retval now live: " << F->getName() << "\n"; 477 478 MaybeLiveRetVal.erase(I); 479 LiveRetVal.insert(F); // It is now known to be live! 480 481 // Loop over all of the functions, noticing that the return value is now live. 482 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 483 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 484 MarkReturnInstArgumentLive(RI); 485} 486 487void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) { 488 Value *Op = RI->getOperand(0); 489 if (Argument *A = dyn_cast<Argument>(Op)) { 490 MarkArgumentLive(A); 491 } else if (CallInst *CI = dyn_cast<CallInst>(Op)) { 492 if (Function *F = CI->getCalledFunction()) 493 MarkRetValLive(F); 494 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) { 495 if (Function *F = II->getCalledFunction()) 496 MarkRetValLive(F); 497 } 498} 499 500// RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as 501// specified by the DeadArguments list. Transform the function and all of the 502// callees of the function to not have these arguments. 503// 504void DAE::RemoveDeadArgumentsFromFunction(Function *F) { 505 // Start by computing a new prototype for the function, which is the same as 506 // the old function, but has fewer arguments. 507 const FunctionType *FTy = F->getFunctionType(); 508 std::vector<const Type*> Params; 509 510 // Set up to build a new list of parameter attributes 511 ParamAttrsVector ParamAttrsVec; 512 const ParamAttrsList *PAL = F->getParamAttrs(); 513 514 // The existing function return attributes. 515 ParameterAttributes RAttrs = PAL ? PAL->getParamAttrs(0) : ParamAttr::None; 516 517 // Make the function return void if the return value is dead. 518 const Type *RetTy = FTy->getReturnType(); 519 if (DeadRetVal.count(F)) { 520 RetTy = Type::VoidTy; 521 RAttrs &= ~ParamAttr::typeIncompatible(RetTy); 522 DeadRetVal.erase(F); 523 } 524 525 if (RAttrs) 526 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); 527 528 // Construct the new parameter list from non-dead arguments. Also construct 529 // a new set of parameter attributes to correspond. 530 unsigned index = 1; 531 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 532 ++I, ++index) 533 if (!DeadArguments.count(I)) { 534 Params.push_back(I->getType()); 535 ParameterAttributes Attrs = PAL ? PAL->getParamAttrs(index) : 536 ParamAttr::None; 537 if (Attrs) 538 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Params.size(), Attrs)); 539 } 540 541 // Reconstruct the ParamAttrsList based on the vector we constructed. 542 PAL = ParamAttrsList::get(ParamAttrsVec); 543 544 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 545 // have zero fixed arguments. 546 // 547 bool ExtraArgHack = false; 548 if (Params.empty() && FTy->isVarArg()) { 549 ExtraArgHack = true; 550 Params.push_back(Type::Int32Ty); 551 } 552 553 // Create the new function type based on the recomputed parameters. 554 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 555 556 // Create the new function body and insert it into the module... 557 Function *NF = new Function(NFTy, F->getLinkage()); 558 NF->setCallingConv(F->getCallingConv()); 559 NF->setParamAttrs(PAL); 560 if (F->hasCollector()) 561 NF->setCollector(F->getCollector()); 562 F->getParent()->getFunctionList().insert(F, NF); 563 NF->takeName(F); 564 565 // Loop over all of the callers of the function, transforming the call sites 566 // to pass in a smaller number of arguments into the new function. 567 // 568 std::vector<Value*> Args; 569 while (!F->use_empty()) { 570 CallSite CS = CallSite::get(F->use_back()); 571 Instruction *Call = CS.getInstruction(); 572 ParamAttrsVec.clear(); 573 PAL = CS.getParamAttrs(); 574 575 // The call return attributes. 576 ParameterAttributes RAttrs = PAL ? PAL->getParamAttrs(0) : ParamAttr::None; 577 // Adjust in case the function was changed to return void. 578 RAttrs &= ~ParamAttr::typeIncompatible(NF->getReturnType()); 579 if (RAttrs) 580 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); 581 582 // Loop over the operands, deleting dead ones... 583 CallSite::arg_iterator AI = CS.arg_begin(); 584 index = 1; 585 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 586 I != E; ++I, ++AI, ++index) 587 if (!DeadArguments.count(I)) { // Remove operands for dead arguments 588 Args.push_back(*AI); 589 ParameterAttributes Attrs = PAL ? PAL->getParamAttrs(index) : 590 ParamAttr::None; 591 if (Attrs) 592 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); 593 } 594 595 if (ExtraArgHack) 596 Args.push_back(UndefValue::get(Type::Int32Ty)); 597 598 // Push any varargs arguments on the list. Don't forget their attributes. 599 for (; AI != CS.arg_end(); ++AI) { 600 Args.push_back(*AI); 601 ParameterAttributes Attrs = PAL ? PAL->getParamAttrs(index++) : 602 ParamAttr::None; 603 if (Attrs) 604 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); 605 } 606 607 // Reconstruct the ParamAttrsList based on the vector we constructed. 608 PAL = ParamAttrsList::get(ParamAttrsVec); 609 610 Instruction *New; 611 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 612 New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), 613 Args.begin(), Args.end(), "", Call); 614 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 615 cast<InvokeInst>(New)->setParamAttrs(PAL); 616 } else { 617 New = new CallInst(NF, Args.begin(), Args.end(), "", Call); 618 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 619 cast<CallInst>(New)->setParamAttrs(PAL); 620 if (cast<CallInst>(Call)->isTailCall()) 621 cast<CallInst>(New)->setTailCall(); 622 } 623 Args.clear(); 624 625 if (!Call->use_empty()) { 626 if (New->getType() == Type::VoidTy) 627 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 628 else { 629 Call->replaceAllUsesWith(New); 630 New->takeName(Call); 631 } 632 } 633 634 // Finally, remove the old call from the program, reducing the use-count of 635 // F. 636 Call->getParent()->getInstList().erase(Call); 637 } 638 639 // Since we have now created the new function, splice the body of the old 640 // function right into the new function, leaving the old rotting hulk of the 641 // function empty. 642 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 643 644 // Loop over the argument list, transfering uses of the old arguments over to 645 // the new arguments, also transfering over the names as well. While we're at 646 // it, remove the dead arguments from the DeadArguments list. 647 // 648 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 649 I2 = NF->arg_begin(); 650 I != E; ++I) 651 if (!DeadArguments.count(I)) { 652 // If this is a live argument, move the name and users over to the new 653 // version. 654 I->replaceAllUsesWith(I2); 655 I2->takeName(I); 656 ++I2; 657 } else { 658 // If this argument is dead, replace any uses of it with null constants 659 // (these are guaranteed to only be operands to call instructions which 660 // will later be simplified). 661 I->replaceAllUsesWith(Constant::getNullValue(I->getType())); 662 DeadArguments.erase(I); 663 } 664 665 // If we change the return value of the function we must rewrite any return 666 // instructions. Check this now. 667 if (F->getReturnType() != NF->getReturnType()) 668 for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB) 669 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 670 new ReturnInst(0, RI); 671 BB->getInstList().erase(RI); 672 } 673 674 // Now that the old function is dead, delete it. 675 F->getParent()->getFunctionList().erase(F); 676} 677 678bool DAE::runOnModule(Module &M) { 679 bool Changed = false; 680 // First pass: Do a simple check to see if any functions can have their "..." 681 // removed. We can do this if they never call va_start. This loop cannot be 682 // fused with the next loop, because deleting a function invalidates 683 // information computed while surveying other functions. 684 DOUT << "DAE - Deleting dead varargs\n"; 685 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 686 Function &F = *I++; 687 if (F.getFunctionType()->isVarArg()) 688 Changed |= DeleteDeadVarargs(F); 689 } 690 691 // Second phase:loop through the module, determining which arguments are live. 692 // We assume all arguments are dead unless proven otherwise (allowing us to 693 // determine that dead arguments passed into recursive functions are dead). 694 // 695 DOUT << "DAE - Determining liveness\n"; 696 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 697 SurveyFunction(*I); 698 699 // Loop over the instructions to inspect, propagating liveness among arguments 700 // and return values which are MaybeLive. 701 while (!InstructionsToInspect.empty()) { 702 Instruction *I = InstructionsToInspect.back(); 703 InstructionsToInspect.pop_back(); 704 705 if (ReturnInst *RI = dyn_cast<ReturnInst>(I)) { 706 // For return instructions, we just have to check to see if the return 707 // value for the current function is known now to be alive. If so, any 708 // arguments used by it are now alive, and any call instruction return 709 // value is alive as well. 710 if (LiveRetVal.count(RI->getParent()->getParent())) 711 MarkReturnInstArgumentLive(RI); 712 713 } else { 714 CallSite CS = CallSite::get(I); 715 assert(CS.getInstruction() && "Unknown instruction for the I2I list!"); 716 717 Function *Callee = CS.getCalledFunction(); 718 719 // If we found a call or invoke instruction on this list, that means that 720 // an argument of the function is a call instruction. If the argument is 721 // live, then the return value of the called instruction is now live. 722 // 723 CallSite::arg_iterator AI = CS.arg_begin(); // ActualIterator 724 for (Function::arg_iterator FI = Callee->arg_begin(), 725 E = Callee->arg_end(); FI != E; ++AI, ++FI) { 726 // If this argument is another call... 727 CallSite ArgCS = CallSite::get(*AI); 728 if (ArgCS.getInstruction() && LiveArguments.count(FI)) 729 if (Function *Callee = ArgCS.getCalledFunction()) 730 MarkRetValLive(Callee); 731 } 732 } 733 } 734 735 // Now we loop over all of the MaybeLive arguments, promoting them to be live 736 // arguments if one of the calls that uses the arguments to the calls they are 737 // passed into requires them to be live. Of course this could make other 738 // arguments live, so process callers recursively. 739 // 740 // Because elements can be removed from the MaybeLiveArguments set, copy it to 741 // a temporary vector. 742 // 743 std::vector<Argument*> TmpArgList(MaybeLiveArguments.begin(), 744 MaybeLiveArguments.end()); 745 for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) { 746 Argument *MLA = TmpArgList[i]; 747 if (MaybeLiveArguments.count(MLA) && 748 isMaybeLiveArgumentNowLive(MLA)) 749 MarkArgumentLive(MLA); 750 } 751 752 // Recover memory early... 753 CallSites.clear(); 754 755 // At this point, we know that all arguments in DeadArguments and 756 // MaybeLiveArguments are dead. If the two sets are empty, there is nothing 757 // to do. 758 if (MaybeLiveArguments.empty() && DeadArguments.empty() && 759 MaybeLiveRetVal.empty() && DeadRetVal.empty()) 760 return Changed; 761 762 // Otherwise, compact into one set, and start eliminating the arguments from 763 // the functions. 764 DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end()); 765 MaybeLiveArguments.clear(); 766 DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end()); 767 MaybeLiveRetVal.clear(); 768 769 LiveArguments.clear(); 770 LiveRetVal.clear(); 771 772 NumArgumentsEliminated += DeadArguments.size(); 773 NumRetValsEliminated += DeadRetVal.size(); 774 while (!DeadArguments.empty()) 775 RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent()); 776 777 while (!DeadRetVal.empty()) 778 RemoveDeadArgumentsFromFunction(*DeadRetVal.begin()); 779 return true; 780} 781