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