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