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