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