DeadArgumentElimination.cpp revision c9235d2e855c56e9aa157969f8132a05f9ba89d8
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 char DAE::ID = 0; 101 RegisterPass<DAE> X("deadargelim", "Dead Argument Elimination"); 102 103 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 104 /// deletes arguments to functions which are external. This is only for use 105 /// by bugpoint. 106 struct DAH : public DAE { 107 static char ID; 108 virtual bool ShouldHackArguments() const { return true; } 109 }; 110 char DAH::ID = 0; 111 RegisterPass<DAH> Y("deadarghaX0r", 112 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)"); 113} 114 115/// createDeadArgEliminationPass - This pass removes arguments from functions 116/// which are not used by the body of the function. 117/// 118ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 119ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 120 121/// DeleteDeadVarargs - If this is an function that takes a ... list, and if 122/// llvm.vastart is never called, the varargs list is dead for the function. 123bool DAE::DeleteDeadVarargs(Function &Fn) { 124 assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 125 if (Fn.isDeclaration() || !Fn.hasInternalLinkage()) return false; 126 127 // Ensure that the function is only directly called. 128 for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end(); I != E; ++I) { 129 // If this use is anything other than a call site, give up. 130 CallSite CS = CallSite::get(*I); 131 Instruction *TheCall = CS.getInstruction(); 132 if (!TheCall) return false; // Not a direct call site? 133 134 // The addr of this function is passed to the call. 135 if (I.getOperandNo() != 0) return false; 136 } 137 138 // Okay, we know we can transform this function if safe. Scan its body 139 // looking for calls to llvm.vastart. 140 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 141 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 142 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 143 if (II->getIntrinsicID() == Intrinsic::vastart) 144 return false; 145 } 146 } 147 } 148 149 // If we get here, there are no calls to llvm.vastart in the function body, 150 // remove the "..." and adjust all the calls. 151 152 // Start by computing a new prototype for the function, which is the same as 153 // the old function, but has fewer arguments. 154 const FunctionType *FTy = Fn.getFunctionType(); 155 std::vector<const Type*> Params(FTy->param_begin(), FTy->param_end()); 156 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false); 157 unsigned NumArgs = Params.size(); 158 159 // Create the new function body and insert it into the module... 160 Function *NF = new Function(NFTy, Fn.getLinkage()); 161 NF->setCallingConv(Fn.getCallingConv()); 162 NF->setParamAttrs(Fn.getParamAttrs()); 163 if (Fn.hasCollector()) 164 NF->setCollector(Fn.getCollector()); 165 Fn.getParent()->getFunctionList().insert(&Fn, NF); 166 NF->takeName(&Fn); 167 168 // Loop over all of the callers of the function, transforming the call sites 169 // to pass in a smaller number of arguments into the new function. 170 // 171 std::vector<Value*> Args; 172 while (!Fn.use_empty()) { 173 CallSite CS = CallSite::get(Fn.use_back()); 174 Instruction *Call = CS.getInstruction(); 175 176 // Pass all the same arguments. 177 Args.assign(CS.arg_begin(), CS.arg_begin()+NumArgs); 178 179 // Drop any attributes that were on the vararg arguments. 180 PAListPtr PAL = CS.getParamAttrs(); 181 if (!PAL.isEmpty() && PAL.getSlot(PAL.getNumSlots() - 1).Index > NumArgs) { 182 SmallVector<ParamAttrsWithIndex, 8> ParamAttrsVec; 183 for (unsigned i = 0; PAL.getSlot(i).Index <= NumArgs; ++i) 184 ParamAttrsVec.push_back(PAL.getSlot(i)); 185 PAL = PAListPtr::get(ParamAttrsVec.begin(), ParamAttrsVec.end()); 186 } 187 188 Instruction *New; 189 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 190 New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), 191 Args.begin(), Args.end(), "", Call); 192 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 193 cast<InvokeInst>(New)->setParamAttrs(PAL); 194 } else { 195 New = new CallInst(NF, Args.begin(), Args.end(), "", Call); 196 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 197 cast<CallInst>(New)->setParamAttrs(PAL); 198 if (cast<CallInst>(Call)->isTailCall()) 199 cast<CallInst>(New)->setTailCall(); 200 } 201 Args.clear(); 202 203 if (!Call->use_empty()) 204 Call->replaceAllUsesWith(New); 205 206 New->takeName(Call); 207 208 // Finally, remove the old call from the program, reducing the use-count of 209 // F. 210 Call->eraseFromParent(); 211 } 212 213 // Since we have now created the new function, splice the body of the old 214 // function right into the new function, leaving the old rotting hulk of the 215 // function empty. 216 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 217 218 // Loop over the argument list, transfering uses of the old arguments over to 219 // the new arguments, also transfering over the names as well. While we're at 220 // it, remove the dead arguments from the DeadArguments list. 221 // 222 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 223 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 224 // Move the name and users over to the new version. 225 I->replaceAllUsesWith(I2); 226 I2->takeName(I); 227 } 228 229 // Finally, nuke the old function. 230 Fn.eraseFromParent(); 231 return true; 232} 233 234 235static inline bool CallPassesValueThoughVararg(Instruction *Call, 236 const Value *Arg) { 237 CallSite CS = CallSite::get(Call); 238 const Type *CalledValueTy = CS.getCalledValue()->getType(); 239 const Type *FTy = cast<PointerType>(CalledValueTy)->getElementType(); 240 unsigned NumFixedArgs = cast<FunctionType>(FTy)->getNumParams(); 241 for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs; 242 AI != CS.arg_end(); ++AI) 243 if (AI->get() == Arg) 244 return true; 245 return false; 246} 247 248// getArgumentLiveness - Inspect an argument, determining if is known Live 249// (used in a computation), MaybeLive (only passed as an argument to a call), or 250// Dead (not used). 251DAE::Liveness DAE::getArgumentLiveness(const Argument &A) { 252 const Function *F = A.getParent(); 253 254 // If this is the return value of a struct function, it's not really dead. 255 if (F->hasStructRetAttr() && &*(F->arg_begin()) == &A) 256 return Live; 257 258 if (A.use_empty()) // First check, directly dead? 259 return Dead; 260 261 // Scan through all of the uses, looking for non-argument passing uses. 262 for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) { 263 // Return instructions do not immediately effect liveness. 264 if (isa<ReturnInst>(*I)) 265 continue; 266 267 CallSite CS = CallSite::get(const_cast<User*>(*I)); 268 if (!CS.getInstruction()) { 269 // If its used by something that is not a call or invoke, it's alive! 270 return Live; 271 } 272 // If it's an indirect call, mark it alive... 273 Function *Callee = CS.getCalledFunction(); 274 if (!Callee) return Live; 275 276 // Check to see if it's passed through a va_arg area: if so, we cannot 277 // remove it. 278 if (CallPassesValueThoughVararg(CS.getInstruction(), &A)) 279 return Live; // If passed through va_arg area, we cannot remove it 280 } 281 282 return MaybeLive; // It must be used, but only as argument to a function 283} 284 285 286// SurveyFunction - This performs the initial survey of the specified function, 287// checking out whether or not it uses any of its incoming arguments or whether 288// any callers use the return value. This fills in the 289// (Dead|MaybeLive|Live)(Arguments|RetVal) sets. 290// 291// We consider arguments of non-internal functions to be intrinsically alive as 292// well as arguments to functions which have their "address taken". 293// 294void DAE::SurveyFunction(Function &F) { 295 bool FunctionIntrinsicallyLive = false; 296 Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead; 297 298 if (!F.hasInternalLinkage() && 299 (!ShouldHackArguments() || F.isIntrinsic())) 300 FunctionIntrinsicallyLive = true; 301 else 302 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { 303 // If this use is anything other than a call site, the function is alive. 304 CallSite CS = CallSite::get(*I); 305 Instruction *TheCall = CS.getInstruction(); 306 if (!TheCall) { // Not a direct call site? 307 FunctionIntrinsicallyLive = true; 308 break; 309 } 310 311 // Check to see if the return value is used... 312 if (RetValLiveness != Live) 313 for (Value::use_iterator I = TheCall->use_begin(), 314 E = TheCall->use_end(); I != E; ++I) 315 if (isa<ReturnInst>(cast<Instruction>(*I))) { 316 RetValLiveness = MaybeLive; 317 } else if (isa<CallInst>(cast<Instruction>(*I)) || 318 isa<InvokeInst>(cast<Instruction>(*I))) { 319 if (CallPassesValueThoughVararg(cast<Instruction>(*I), TheCall) || 320 !CallSite::get(cast<Instruction>(*I)).getCalledFunction()) { 321 RetValLiveness = Live; 322 break; 323 } else { 324 RetValLiveness = MaybeLive; 325 } 326 } else { 327 RetValLiveness = Live; 328 break; 329 } 330 331 // If the function is PASSED IN as an argument, its address has been taken 332 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); 333 AI != E; ++AI) 334 if (AI->get() == &F) { 335 FunctionIntrinsicallyLive = true; 336 break; 337 } 338 if (FunctionIntrinsicallyLive) break; 339 } 340 341 if (FunctionIntrinsicallyLive) { 342 DOUT << " Intrinsically live fn: " << F.getName() << "\n"; 343 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 344 AI != E; ++AI) 345 LiveArguments.insert(AI); 346 LiveRetVal.insert(&F); 347 return; 348 } 349 350 switch (RetValLiveness) { 351 case Live: LiveRetVal.insert(&F); break; 352 case MaybeLive: MaybeLiveRetVal.insert(&F); break; 353 case Dead: DeadRetVal.insert(&F); break; 354 } 355 356 DOUT << " Inspecting args for fn: " << F.getName() << "\n"; 357 358 // If it is not intrinsically alive, we know that all users of the 359 // function are call sites. Mark all of the arguments live which are 360 // directly used, and keep track of all of the call sites of this function 361 // if there are any arguments we assume that are dead. 362 // 363 bool AnyMaybeLiveArgs = false; 364 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 365 AI != E; ++AI) 366 switch (getArgumentLiveness(*AI)) { 367 case Live: 368 DOUT << " Arg live by use: " << AI->getName() << "\n"; 369 LiveArguments.insert(AI); 370 break; 371 case Dead: 372 DOUT << " Arg definitely dead: " << AI->getName() <<"\n"; 373 DeadArguments.insert(AI); 374 break; 375 case MaybeLive: 376 DOUT << " Arg only passed to calls: " << AI->getName() << "\n"; 377 AnyMaybeLiveArgs = true; 378 MaybeLiveArguments.insert(AI); 379 break; 380 } 381 382 // If there are any "MaybeLive" arguments, we need to check callees of 383 // this function when/if they become alive. Record which functions are 384 // callees... 385 if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive) 386 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); 387 I != E; ++I) { 388 if (AnyMaybeLiveArgs) 389 CallSites.insert(std::make_pair(&F, CallSite::get(*I))); 390 391 if (RetValLiveness == MaybeLive) 392 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 393 UI != E; ++UI) 394 InstructionsToInspect.push_back(cast<Instruction>(*UI)); 395 } 396} 397 398// isMaybeLiveArgumentNowLive - Check to see if Arg is alive. At this point, we 399// know that the only uses of Arg are to be passed in as an argument to a 400// function call or return. Check to see if the formal argument passed in is in 401// the LiveArguments set. If so, return true. 402// 403bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) { 404 for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){ 405 if (isa<ReturnInst>(*I)) { 406 if (LiveRetVal.count(Arg->getParent())) return true; 407 continue; 408 } 409 410 CallSite CS = CallSite::get(*I); 411 412 // We know that this can only be used for direct calls... 413 Function *Callee = CS.getCalledFunction(); 414 415 // Loop over all of the arguments (because Arg may be passed into the call 416 // multiple times) and check to see if any are now alive... 417 CallSite::arg_iterator CSAI = CS.arg_begin(); 418 for (Function::arg_iterator AI = Callee->arg_begin(), E = Callee->arg_end(); 419 AI != E; ++AI, ++CSAI) 420 // If this is the argument we are looking for, check to see if it's alive 421 if (*CSAI == Arg && LiveArguments.count(AI)) 422 return true; 423 } 424 return false; 425} 426 427/// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive. 428/// Mark it live in the specified sets and recursively mark arguments in callers 429/// live that are needed to pass in a value. 430/// 431void DAE::MarkArgumentLive(Argument *Arg) { 432 std::set<Argument*>::iterator It = MaybeLiveArguments.lower_bound(Arg); 433 if (It == MaybeLiveArguments.end() || *It != Arg) return; 434 435 DOUT << " MaybeLive argument now live: " << Arg->getName() <<"\n"; 436 MaybeLiveArguments.erase(It); 437 LiveArguments.insert(Arg); 438 439 // Loop over all of the call sites of the function, making any arguments 440 // passed in to provide a value for this argument live as necessary. 441 // 442 Function *Fn = Arg->getParent(); 443 unsigned ArgNo = std::distance(Fn->arg_begin(), Function::arg_iterator(Arg)); 444 445 std::multimap<Function*, CallSite>::iterator I = CallSites.lower_bound(Fn); 446 for (; I != CallSites.end() && I->first == Fn; ++I) { 447 CallSite CS = I->second; 448 Value *ArgVal = *(CS.arg_begin()+ArgNo); 449 if (Argument *ActualArg = dyn_cast<Argument>(ArgVal)) { 450 MarkArgumentLive(ActualArg); 451 } else { 452 // If the value passed in at this call site is a return value computed by 453 // some other call site, make sure to mark the return value at the other 454 // call site as being needed. 455 CallSite ArgCS = CallSite::get(ArgVal); 456 if (ArgCS.getInstruction()) 457 if (Function *Fn = ArgCS.getCalledFunction()) 458 MarkRetValLive(Fn); 459 } 460 } 461} 462 463/// MarkArgumentLive - The MaybeLive return value for the specified function is 464/// now known to be alive. Propagate this fact to the return instructions which 465/// produce it. 466void DAE::MarkRetValLive(Function *F) { 467 assert(F && "Shame shame, we can't have null pointers here!"); 468 469 // Check to see if we already knew it was live 470 std::set<Function*>::iterator I = MaybeLiveRetVal.lower_bound(F); 471 if (I == MaybeLiveRetVal.end() || *I != F) return; // It's already alive! 472 473 DOUT << " MaybeLive retval now live: " << F->getName() << "\n"; 474 475 MaybeLiveRetVal.erase(I); 476 LiveRetVal.insert(F); // It is now known to be live! 477 478 // Loop over all of the functions, noticing that the return value is now live. 479 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 480 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 481 MarkReturnInstArgumentLive(RI); 482} 483 484void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) { 485 Value *Op = RI->getOperand(0); 486 if (Argument *A = dyn_cast<Argument>(Op)) { 487 MarkArgumentLive(A); 488 } else if (CallInst *CI = dyn_cast<CallInst>(Op)) { 489 if (Function *F = CI->getCalledFunction()) 490 MarkRetValLive(F); 491 } else if (InvokeInst *II = dyn_cast<InvokeInst>(Op)) { 492 if (Function *F = II->getCalledFunction()) 493 MarkRetValLive(F); 494 } 495} 496 497// RemoveDeadArgumentsFromFunction - We know that F has dead arguments, as 498// specified by the DeadArguments list. Transform the function and all of the 499// callees of the function to not have these arguments. 500// 501void DAE::RemoveDeadArgumentsFromFunction(Function *F) { 502 // Start by computing a new prototype for the function, which is the same as 503 // the old function, but has fewer arguments. 504 const FunctionType *FTy = F->getFunctionType(); 505 std::vector<const Type*> Params; 506 507 // Set up to build a new list of parameter attributes 508 SmallVector<ParamAttrsWithIndex, 8> ParamAttrsVec; 509 const PAListPtr &PAL = F->getParamAttrs(); 510 511 // The existing function return attributes. 512 ParameterAttributes RAttrs = PAL.getParamAttrs(0); 513 514 // Make the function return void if the return value is dead. 515 const Type *RetTy = FTy->getReturnType(); 516 if (DeadRetVal.count(F)) { 517 RetTy = Type::VoidTy; 518 RAttrs &= ~ParamAttr::typeIncompatible(RetTy); 519 DeadRetVal.erase(F); 520 } 521 522 if (RAttrs) 523 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); 524 525 // Construct the new parameter list from non-dead arguments. Also construct 526 // a new set of parameter attributes to correspond. 527 unsigned index = 1; 528 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 529 ++I, ++index) 530 if (!DeadArguments.count(I)) { 531 Params.push_back(I->getType()); 532 533 if (ParameterAttributes Attrs = PAL.getParamAttrs(index)) 534 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Params.size(), Attrs)); 535 } 536 537 // Reconstruct the ParamAttrsList based on the vector we constructed. 538 PAListPtr NewPAL = PAListPtr::get(ParamAttrsVec.begin(), ParamAttrsVec.end()); 539 540 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 541 // have zero fixed arguments. 542 // 543 bool ExtraArgHack = false; 544 if (Params.empty() && FTy->isVarArg()) { 545 ExtraArgHack = true; 546 Params.push_back(Type::Int32Ty); 547 } 548 549 // Create the new function type based on the recomputed parameters. 550 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 551 552 // Create the new function body and insert it into the module... 553 Function *NF = new Function(NFTy, F->getLinkage()); 554 NF->setCallingConv(F->getCallingConv()); 555 NF->setParamAttrs(NewPAL); 556 if (F->hasCollector()) 557 NF->setCollector(F->getCollector()); 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 = new InvokeInst(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 = new CallInst(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->getParent()->getInstList().erase(Call); 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 new ReturnInst(0, RI); 664 BB->getInstList().erase(RI); 665 } 666 667 // Now that the old function is dead, delete it. 668 F->getParent()->getFunctionList().erase(F); 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