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