DeadArgumentElimination.cpp revision 59962670e6e8d53f0d86e54def85ab01fbb69c89
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 return values 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 or return values. 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 public: 46 47 /// Struct that represent either a (part of a) return value or a function 48 /// argument. Used so that arguments and return values can be used 49 /// interchangably. 50 struct RetOrArg { 51 RetOrArg(const Function* F, unsigned Idx, bool IsArg) : F(F), Idx(Idx), 52 IsArg(IsArg) {} 53 const Function *F; 54 unsigned Idx; 55 bool IsArg; 56 57 /// Make RetOrArg comparable, so we can put it into a map 58 bool operator<(const RetOrArg &O) const { 59 if (F != O.F) 60 return F < O.F; 61 else if (Idx != O.Idx) 62 return Idx < O.Idx; 63 else 64 return IsArg < O.IsArg; 65 } 66 67 /// Make RetOrArg comparable, so we can easily iterate the multimap 68 bool operator==(const RetOrArg &O) const { 69 return F == O.F && Idx == O.Idx && IsArg == O.IsArg; 70 } 71 }; 72 73 /// Liveness enum - During our initial pass over the program, we determine 74 /// that things are either alive or maybe alive. We don't mark anything 75 /// explicitly dead (even if we know they are), since anything not alive 76 /// with no registered uses (in Uses) will never be marked alive and will 77 /// thus become dead in the end. 78 enum Liveness { Live, MaybeLive }; 79 80 /// Convenience wrapper 81 RetOrArg CreateRet(const Function *F, unsigned Idx) { 82 return RetOrArg(F, Idx, false); 83 } 84 /// Convenience wrapper 85 RetOrArg CreateArg(const Function *F, unsigned Idx) { 86 return RetOrArg(F, Idx, true); 87 } 88 89 typedef std::multimap<RetOrArg, RetOrArg> UseMap; 90 /// This map maps a return value or argument to all return values or 91 /// arguments it uses. 92 /// For example (indices are left out for clarity): 93 /// - Uses[ret F] = ret G 94 /// This means that F calls G, and F returns the value returned by G. 95 /// - Uses[arg F] = ret G 96 /// This means that some function calls G and passes its result as an 97 /// argument to F. 98 /// - Uses[ret F] = arg F 99 /// This means that F returns one of its own arguments. 100 /// - Uses[arg F] = arg G 101 /// This means that G calls F and passes one of its own (G's) arguments 102 /// directly to F. 103 UseMap Uses; 104 105 typedef std::set<RetOrArg> LiveSet; 106 107 /// This set contains all values that have been determined to be live 108 LiveSet LiveValues; 109 110 typedef SmallVector<RetOrArg, 5> UseVector; 111 112 public: 113 static char ID; // Pass identification, replacement for typeid 114 DAE() : ModulePass((intptr_t)&ID) {} 115 bool runOnModule(Module &M); 116 117 virtual bool ShouldHackArguments() const { return false; } 118 119 private: 120 Liveness IsMaybeLive(RetOrArg Use, UseVector &MaybeLiveUses); 121 Liveness SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, 122 unsigned RetValNum = 0); 123 Liveness SurveyUses(Value *V, UseVector &MaybeLiveUses); 124 125 void SurveyFunction(Function &F); 126 void MarkValue(const RetOrArg &RA, Liveness L, 127 const UseVector &MaybeLiveUses); 128 void MarkLive(RetOrArg RA); 129 bool RemoveDeadStuffFromFunction(Function *F); 130 bool DeleteDeadVarargs(Function &Fn); 131 }; 132} 133 134 135char DAE::ID = 0; 136static RegisterPass<DAE> 137X("deadargelim", "Dead Argument Elimination"); 138 139namespace { 140 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 141 /// deletes arguments to functions which are external. This is only for use 142 /// by bugpoint. 143 struct DAH : public DAE { 144 static char ID; 145 virtual bool ShouldHackArguments() const { return true; } 146 }; 147} 148 149char DAH::ID = 0; 150static RegisterPass<DAH> 151Y("deadarghaX0r", "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)"); 152 153/// createDeadArgEliminationPass - This pass removes arguments from functions 154/// which are not used by the body of the function. 155/// 156ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 157ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 158 159/// DeleteDeadVarargs - If this is an function that takes a ... list, and if 160/// llvm.vastart is never called, the varargs list is dead for the function. 161bool DAE::DeleteDeadVarargs(Function &Fn) { 162 assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 163 if (Fn.isDeclaration() || !Fn.hasInternalLinkage()) return false; 164 165 // Ensure that the function is only directly called. 166 for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end(); I != E; ++I) { 167 // If this use is anything other than a call site, give up. 168 CallSite CS = CallSite::get(*I); 169 Instruction *TheCall = CS.getInstruction(); 170 if (!TheCall) return false; // Not a direct call site? 171 172 // The addr of this function is passed to the call. 173 if (I.getOperandNo() != 0) return false; 174 } 175 176 // Okay, we know we can transform this function if safe. Scan its body 177 // looking for calls to llvm.vastart. 178 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 179 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 180 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 181 if (II->getIntrinsicID() == Intrinsic::vastart) 182 return false; 183 } 184 } 185 } 186 187 // If we get here, there are no calls to llvm.vastart in the function body, 188 // remove the "..." and adjust all the calls. 189 190 // Start by computing a new prototype for the function, which is the same as 191 // the old function, but doesn't have isVarArg set. 192 const FunctionType *FTy = Fn.getFunctionType(); 193 std::vector<const Type*> Params(FTy->param_begin(), FTy->param_end()); 194 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false); 195 unsigned NumArgs = Params.size(); 196 197 // Create the new function body and insert it into the module... 198 Function *NF = Function::Create(NFTy, Fn.getLinkage()); 199 NF->copyAttributesFrom(&Fn); 200 Fn.getParent()->getFunctionList().insert(&Fn, NF); 201 NF->takeName(&Fn); 202 203 // Loop over all of the callers of the function, transforming the call sites 204 // to pass in a smaller number of arguments into the new function. 205 // 206 std::vector<Value*> Args; 207 while (!Fn.use_empty()) { 208 CallSite CS = CallSite::get(Fn.use_back()); 209 Instruction *Call = CS.getInstruction(); 210 211 // Pass all the same arguments. 212 Args.assign(CS.arg_begin(), CS.arg_begin()+NumArgs); 213 214 // Drop any attributes that were on the vararg arguments. 215 PAListPtr PAL = CS.getParamAttrs(); 216 if (!PAL.isEmpty() && PAL.getSlot(PAL.getNumSlots() - 1).Index > NumArgs) { 217 SmallVector<ParamAttrsWithIndex, 8> ParamAttrsVec; 218 for (unsigned i = 0; PAL.getSlot(i).Index <= NumArgs; ++i) 219 ParamAttrsVec.push_back(PAL.getSlot(i)); 220 PAL = PAListPtr::get(ParamAttrsVec.begin(), ParamAttrsVec.end()); 221 } 222 223 Instruction *New; 224 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 225 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 226 Args.begin(), Args.end(), "", Call); 227 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 228 cast<InvokeInst>(New)->setParamAttrs(PAL); 229 } else { 230 New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); 231 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 232 cast<CallInst>(New)->setParamAttrs(PAL); 233 if (cast<CallInst>(Call)->isTailCall()) 234 cast<CallInst>(New)->setTailCall(); 235 } 236 Args.clear(); 237 238 if (!Call->use_empty()) 239 Call->replaceAllUsesWith(New); 240 241 New->takeName(Call); 242 243 // Finally, remove the old call from the program, reducing the use-count of 244 // F. 245 Call->eraseFromParent(); 246 } 247 248 // Since we have now created the new function, splice the body of the old 249 // function right into the new function, leaving the old rotting hulk of the 250 // function empty. 251 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 252 253 // Loop over the argument list, transfering uses of the old arguments over to 254 // the new arguments, also transfering over the names as well. While we're at 255 // it, remove the dead arguments from the DeadArguments list. 256 // 257 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 258 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 259 // Move the name and users over to the new version. 260 I->replaceAllUsesWith(I2); 261 I2->takeName(I); 262 } 263 264 // Finally, nuke the old function. 265 Fn.eraseFromParent(); 266 return true; 267} 268 269/// Convenience function that returns the number of return values. It returns 0 270/// for void functions and 1 for functions not returning a struct. It returns 271/// the number of struct elements for functions returning a struct. 272static unsigned NumRetVals(const Function *F) { 273 if (F->getReturnType() == Type::VoidTy) 274 return 0; 275 else if (const StructType *STy = dyn_cast<StructType>(F->getReturnType())) 276 return STy->getNumElements(); 277 else 278 return 1; 279} 280 281/// IsMaybeAlive - This checks Use for liveness. If Use is live, returns Live, 282/// else returns MaybeLive. Also, adds Use to MaybeLiveUses in the latter case. 283DAE::Liveness DAE::IsMaybeLive(RetOrArg Use, UseVector &MaybeLiveUses) { 284 // We're live if our use is already marked as live 285 if (LiveValues.count(Use)) 286 return Live; 287 288 // We're maybe live otherwise, but remember that we must become live if 289 // Use becomes live. 290 MaybeLiveUses.push_back(Use); 291 return MaybeLive; 292} 293 294 295/// SurveyUse - This looks at a single use of an argument or return value 296/// and determines if it should be alive or not. Adds this use to MaybeLiveUses 297/// if it causes the used value to become MaybeAlive. 298/// 299/// RetValNum is the return value number to use when this use is used in a 300/// return instruction. This is used in the recursion, you should always leave 301/// it at 0. 302DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, 303 unsigned RetValNum) { 304 Value *V = *U; 305 if (ReturnInst *RI = dyn_cast<ReturnInst>(V)) { 306 // The value is returned from another function. It's only live when the 307 // caller's return value is live 308 RetOrArg Use = CreateRet(RI->getParent()->getParent(), RetValNum); 309 // We might be live, depending on the liveness of Use 310 return IsMaybeLive(Use, MaybeLiveUses); 311 } 312 if (InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 313 if (U.getOperandNo() != InsertValueInst::getAggregateOperandIndex() 314 && IV->hasIndices()) 315 // The use we are examining is inserted into an aggregate. Our liveness 316 // depends on all uses of that aggregate, but if it is used as a return 317 // value, only index at which we were inserted counts. 318 RetValNum = *IV->idx_begin(); 319 320 // Note that if we are used as the aggregate operand to the insertvalue, 321 // we don't change RetValNum, but do survey all our uses. 322 323 Liveness Result = MaybeLive; 324 for (Value::use_iterator I = IV->use_begin(), 325 E = V->use_end(); I != E; ++I) { 326 Result = SurveyUse(I, MaybeLiveUses, RetValNum); 327 if (Result == Live) 328 break; 329 } 330 return Result; 331 } 332 CallSite CS = CallSite::get(V); 333 if (CS.getInstruction()) { 334 Function *F = CS.getCalledFunction(); 335 if (F) { 336 // Used in a direct call 337 338 // Check for vararg. Do - 1 to skip the first operand to call (the 339 // function itself). 340 if (U.getOperandNo() - 1 >= F->getFunctionType()->getNumParams()) 341 // The value is passed in through a vararg! Must be live. 342 return Live; 343 344 // Value passed to a normal call. It's only live when the corresponding 345 // argument (operand number - 1 to skip the function pointer operand) to 346 // the called function turns out live 347 RetOrArg Use = CreateArg(F, U.getOperandNo() - 1); 348 return IsMaybeLive(Use, MaybeLiveUses); 349 } else { 350 // Used in any other way? Value must be live. 351 return Live; 352 } 353 } 354 // Used in any other way? Value must be live. 355 return Live; 356} 357 358/// SurveyUses - This looks at all the uses of the given return value 359/// (possibly a partial return value from a function returning a struct). 360/// Returns the Liveness deduced from the uses of this value. 361/// 362/// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. 363DAE::Liveness DAE::SurveyUses(Value *V, UseVector &MaybeLiveUses) { 364 // Assume it's dead (which will only hold if there are no uses at all..) 365 Liveness Result = MaybeLive; 366 // Check each use 367 for (Value::use_iterator I = V->use_begin(), 368 E = V->use_end(); I != E; ++I) { 369 Result = SurveyUse(I, MaybeLiveUses); 370 if (Result == Live) 371 break; 372 } 373 return Result; 374} 375 376// SurveyFunction - This performs the initial survey of the specified function, 377// checking out whether or not it uses any of its incoming arguments or whether 378// any callers use the return value. This fills in the 379// LiveValues set and Uses map. 380// 381// We consider arguments of non-internal functions to be intrinsically alive as 382// well as arguments to functions which have their "address taken". 383// 384void DAE::SurveyFunction(Function &F) { 385 bool FunctionIntrinsicallyLive = false; 386 unsigned RetCount = NumRetVals(&F); 387 // Assume all return values are dead 388 typedef SmallVector<Liveness, 5> RetVals; 389 RetVals RetValLiveness(RetCount, MaybeLive); 390 391 // These vectors maps each return value to the uses that make it MaybeLive, so 392 // we can add those to the MaybeLiveRetVals list if the return value 393 // really turns out to be MaybeLive. Initializes to RetCount empty vectors 394 typedef SmallVector<UseVector, 5> RetUses; 395 // Intialized to a list of RetCount empty lists 396 RetUses MaybeLiveRetUses(RetCount); 397 398 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 399 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 400 if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 401 != F.getFunctionType()->getReturnType()) { 402 // We don't support old style multiple return values 403 FunctionIntrinsicallyLive = true; 404 break; 405 } 406 407 if (!F.hasInternalLinkage() && (!ShouldHackArguments() || F.isIntrinsic())) 408 FunctionIntrinsicallyLive = true; 409 410 if (!FunctionIntrinsicallyLive) { 411 DOUT << "DAE - Inspecting callers for fn: " << F.getName() << "\n"; 412 // Keep track of the number of live retvals, so we can skip checks once all 413 // of them turn out to be live. 414 unsigned NumLiveRetVals = 0; 415 const Type *STy = dyn_cast<StructType>(F.getReturnType()); 416 // Loop all uses of the function 417 for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { 418 // If the function is PASSED IN as an argument, its address has been taken 419 if (I.getOperandNo() != 0) { 420 FunctionIntrinsicallyLive = true; 421 break; 422 } 423 424 // If this use is anything other than a call site, the function is alive. 425 CallSite CS = CallSite::get(*I); 426 Instruction *TheCall = CS.getInstruction(); 427 if (!TheCall) { // Not a direct call site? 428 FunctionIntrinsicallyLive = true; 429 break; 430 } 431 432 // If we end up here, we are looking at a direct call to our function. 433 434 // Now, check how our return value(s) is/are used in this caller. Don't 435 // bother checking return values if all of them are live already 436 if (NumLiveRetVals != RetCount) { 437 if (STy) { 438 // Check all uses of the return value 439 for (Value::use_iterator I = TheCall->use_begin(), 440 E = TheCall->use_end(); I != E; ++I) { 441 ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I); 442 if (Ext && Ext->hasIndices()) { 443 // This use uses a part of our return value, survey the uses of 444 // that part and store the results for this index only. 445 unsigned Idx = *Ext->idx_begin(); 446 if (RetValLiveness[Idx] != Live) { 447 RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 448 if (RetValLiveness[Idx] == Live) 449 NumLiveRetVals++; 450 } 451 } else { 452 // Used by something else than extractvalue. Mark all 453 // return values as live. 454 for (unsigned i = 0; i != RetCount; ++i ) 455 RetValLiveness[i] = Live; 456 NumLiveRetVals = RetCount; 457 break; 458 } 459 } 460 } else { 461 // Single return value 462 RetValLiveness[0] = SurveyUses(TheCall, MaybeLiveRetUses[0]); 463 if (RetValLiveness[0] == Live) 464 NumLiveRetVals = RetCount; 465 } 466 } 467 } 468 } 469 if (FunctionIntrinsicallyLive) { 470 DOUT << "DAE - Intrinsically live fn: " << F.getName() << "\n"; 471 // Mark all arguments as live 472 unsigned i = 0; 473 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 474 AI != E; ++AI, ++i) 475 MarkLive(CreateArg(&F, i)); 476 // Mark all return values as live 477 i = 0; 478 for (unsigned i = 0, e = RetValLiveness.size(); i != e; ++i) 479 MarkLive(CreateRet(&F, i)); 480 return; 481 } 482 483 // Now we've inspected all callers, record the liveness of our return values. 484 for (unsigned i = 0, e = RetValLiveness.size(); i != e; ++i) { 485 RetOrArg Ret = CreateRet(&F, i); 486 // Mark the result down 487 MarkValue(Ret, RetValLiveness[i], MaybeLiveRetUses[i]); 488 } 489 DOUT << "DAE - Inspecting args for fn: " << F.getName() << "\n"; 490 491 // Now, check all of our arguments 492 unsigned i = 0; 493 UseVector MaybeLiveArgUses; 494 for (Function::arg_iterator AI = F.arg_begin(), 495 E = F.arg_end(); AI != E; ++AI, ++i) { 496 // See what the effect of this use is (recording any uses that cause 497 // MaybeLive in MaybeLiveArgUses) 498 Liveness Result = SurveyUses(AI, MaybeLiveArgUses); 499 RetOrArg Arg = CreateArg(&F, i); 500 // Mark the result down 501 MarkValue(Arg, Result, MaybeLiveArgUses); 502 // Clear the vector again for the next iteration 503 MaybeLiveArgUses.clear(); 504 } 505} 506 507/// MarkValue - This function marks the liveness of RA depending on L. If L is 508/// MaybeLive, it also records any uses in MaybeLiveUses such that RA will be 509/// marked live if any use in MaybeLiveUses gets marked live later on. 510void DAE::MarkValue(const RetOrArg &RA, Liveness L, 511 const UseVector &MaybeLiveUses) { 512 switch (L) { 513 case Live: MarkLive(RA); break; 514 case MaybeLive: 515 { 516 // Note any uses of this value, so this return value can be 517 // marked live whenever one of the uses becomes live. 518 UseMap::iterator Where = Uses.begin(); 519 for (UseVector::const_iterator UI = MaybeLiveUses.begin(), 520 UE = MaybeLiveUses.end(); UI != UE; ++UI) 521 Where = Uses.insert(Where, UseMap::value_type(*UI, RA)); 522 break; 523 } 524 } 525} 526 527/// MarkLive - Mark the given return value or argument as live. Additionally, 528/// mark any values that are used by this value (according to Uses) live as 529/// well. 530void DAE::MarkLive(RetOrArg RA) { 531 if (!LiveValues.insert(RA).second) 532 return; // We were already marked Live 533 534 if (RA.IsArg) 535 DOUT << "DAE - Marking argument " << RA.Idx << " to function " 536 << RA.F->getNameStart() << " live\n"; 537 else 538 DOUT << "DAE - Marking return value " << RA.Idx << " of function " 539 << RA.F->getNameStart() << " live\n"; 540 541 // We don't use upper_bound (or equal_range) here, because our recursive call 542 // to ourselves is likely to mark the upper_bound (which is the first value 543 // not belonging to RA) to become erased and the iterator invalidated. 544 UseMap::iterator Begin = Uses.lower_bound(RA); 545 UseMap::iterator E = Uses.end(); 546 UseMap::iterator I; 547 for (I = Begin; I != E && I->first == RA; ++I) 548 MarkLive(I->second); 549 550 // Erase RA from the Uses map (from the lower bound to wherever we ended up 551 // after the loop). 552 Uses.erase(Begin, I); 553} 554 555// RemoveDeadStuffFromFunction - Remove any arguments and return values from F 556// that are not in LiveValues. This function is a noop for any Function created 557// by this function before, or any function that was not inspected for liveness. 558// specified by the DeadArguments list. Transform the function and all of the 559// callees of the function to not have these arguments. 560// 561bool DAE::RemoveDeadStuffFromFunction(Function *F) { 562 // Quick exit path for external functions 563 if (!F->hasInternalLinkage() && (!ShouldHackArguments() || F->isIntrinsic())) 564 return false; 565 566 // Start by computing a new prototype for the function, which is the same as 567 // the old function, but has fewer arguments and a different return type. 568 const FunctionType *FTy = F->getFunctionType(); 569 std::vector<const Type*> Params; 570 571 // Set up to build a new list of parameter attributes 572 SmallVector<ParamAttrsWithIndex, 8> ParamAttrsVec; 573 const PAListPtr &PAL = F->getParamAttrs(); 574 575 // The existing function return attributes. 576 ParameterAttributes RAttrs = PAL.getParamAttrs(0); 577 578 579 // Find out the new return value 580 581 const Type *RetTy = FTy->getReturnType(); 582 const Type *NRetTy; 583 unsigned RetCount = NumRetVals(F); 584 // Explicitely track if anything changed, for debugging 585 bool Changed = false; 586 // -1 means unused, other numbers are the new index 587 SmallVector<int, 5> NewRetIdxs(RetCount, -1); 588 std::vector<const Type*> RetTypes; 589 if (RetTy != Type::VoidTy) { 590 const StructType *STy = dyn_cast<StructType>(RetTy); 591 if (STy) 592 // Look at each of the original return values individually 593 for (unsigned i = 0; i != RetCount; ++i) { 594 RetOrArg Ret = CreateRet(F, i); 595 if (LiveValues.erase(Ret)) { 596 RetTypes.push_back(STy->getElementType(i)); 597 NewRetIdxs[i] = RetTypes.size() - 1; 598 } else { 599 ++NumRetValsEliminated; 600 DOUT << "DAE - Removing return value " << i << " from " 601 << F->getNameStart() << "\n"; 602 Changed = true; 603 } 604 } 605 else 606 // We used to return a single value 607 if (LiveValues.erase(CreateRet(F, 0))) { 608 RetTypes.push_back(RetTy); 609 NewRetIdxs[0] = 0; 610 } else { 611 DOUT << "DAE - Removing return value from " << F->getNameStart() 612 << "\n"; 613 ++NumRetValsEliminated; 614 Changed = true; 615 } 616 if (RetTypes.size() > 1 || STy && STy->getNumElements() == RetTypes.size()) 617 // More than one return type? Return a struct with them. Also, if we used 618 // to return a struct and didn't change the number of return values, 619 // return a struct again. This prevents changing {something} into something 620 // and {} into void. 621 // Make the new struct packed if we used to return a packed struct 622 // already. 623 NRetTy = StructType::get(RetTypes, STy->isPacked()); 624 else if (RetTypes.size() == 1) 625 // One return type? Just a simple value then, but only if we didn't use to 626 // return a struct with that simple value before. 627 NRetTy = RetTypes.front(); 628 else if (RetTypes.size() == 0) 629 // No return types? Make it void, but only if we didn't use to return {}. 630 NRetTy = Type::VoidTy; 631 } else { 632 NRetTy = Type::VoidTy; 633 } 634 635 // Remove any incompatible attributes 636 RAttrs &= ~ParamAttr::typeIncompatible(NRetTy); 637 if (RAttrs) 638 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); 639 640 // Remember which arguments are still alive 641 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 642 // Construct the new parameter list from non-dead arguments. Also construct 643 // a new set of parameter attributes to correspond. Skip the first parameter 644 // attribute, since that belongs to the return value. 645 unsigned i = 0; 646 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 647 I != E; ++I, ++i) { 648 RetOrArg Arg = CreateArg(F, i); 649 if (LiveValues.erase(Arg)) { 650 Params.push_back(I->getType()); 651 ArgAlive[i] = true; 652 653 // Get the original parameter attributes (skipping the first one, that is 654 // for the return value 655 if (ParameterAttributes Attrs = PAL.getParamAttrs(i + 1)) 656 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Params.size(), Attrs)); 657 } else { 658 ++NumArgumentsEliminated; 659 DOUT << "DAE - Removing argument " << i << " (" << I->getNameStart() 660 << ") from " << F->getNameStart() << "\n"; 661 Changed = true; 662 } 663 } 664 665 // Reconstruct the ParamAttrsList based on the vector we constructed. 666 PAListPtr NewPAL = PAListPtr::get(ParamAttrsVec.begin(), ParamAttrsVec.end()); 667 668 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 669 // have zero fixed arguments. 670 // 671 // Not that we apply this hack for a vararg fuction that does not have any 672 // arguments anymore, but did have them before (so don't bother fixing 673 // functions that were already broken wrt CWriter). 674 bool ExtraArgHack = false; 675 if (Params.empty() && FTy->isVarArg() && FTy->getNumParams() != 0) { 676 ExtraArgHack = true; 677 Params.push_back(Type::Int32Ty); 678 } 679 680 // Create the new function type based on the recomputed parameters. 681 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 682 683 // No change? 684 if (NFTy == FTy) 685 return false; 686 687 // The function type is only allowed to be different if we actually left out 688 // an argument or return value. 689 assert(Changed && "Function type changed while no arguments or return values" 690 "were removed!"); 691 692 // Create the new function body and insert it into the module... 693 Function *NF = Function::Create(NFTy, F->getLinkage()); 694 NF->copyAttributesFrom(F); 695 NF->setParamAttrs(NewPAL); 696 // Insert the new function before the old function, so we won't be processing 697 // it again. 698 F->getParent()->getFunctionList().insert(F, NF); 699 NF->takeName(F); 700 701 // Loop over all of the callers of the function, transforming the call sites 702 // to pass in a smaller number of arguments into the new function. 703 // 704 std::vector<Value*> Args; 705 while (!F->use_empty()) { 706 CallSite CS = CallSite::get(F->use_back()); 707 Instruction *Call = CS.getInstruction(); 708 709 ParamAttrsVec.clear(); 710 const PAListPtr &CallPAL = CS.getParamAttrs(); 711 712 // The call return attributes. 713 ParameterAttributes RAttrs = CallPAL.getParamAttrs(0); 714 // Adjust in case the function was changed to return void. 715 RAttrs &= ~ParamAttr::typeIncompatible(NF->getReturnType()); 716 if (RAttrs) 717 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); 718 719 // Declare these outside of the loops, so we can reuse them for the second 720 // loop, which loops the varargs 721 CallSite::arg_iterator I = CS.arg_begin(); 722 unsigned i = 0; 723 // Loop over those operands, corresponding to the normal arguments to the 724 // original function, and add those that are still alive. 725 for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i) 726 if (ArgAlive[i]) { 727 Args.push_back(*I); 728 // Get original parameter attributes, but skip return attributes 729 if (ParameterAttributes Attrs = CallPAL.getParamAttrs(i + 1)) 730 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); 731 } 732 733 if (ExtraArgHack) 734 Args.push_back(UndefValue::get(Type::Int32Ty)); 735 736 // Push any varargs arguments on the list. Don't forget their attributes. 737 for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { 738 Args.push_back(*I); 739 if (ParameterAttributes Attrs = CallPAL.getParamAttrs(i + 1)) 740 ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); 741 } 742 743 // Reconstruct the ParamAttrsList based on the vector we constructed. 744 PAListPtr NewCallPAL = PAListPtr::get(ParamAttrsVec.begin(), 745 ParamAttrsVec.end()); 746 747 Instruction *New; 748 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 749 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 750 Args.begin(), Args.end(), "", Call); 751 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 752 cast<InvokeInst>(New)->setParamAttrs(NewCallPAL); 753 } else { 754 New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); 755 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 756 cast<CallInst>(New)->setParamAttrs(NewCallPAL); 757 if (cast<CallInst>(Call)->isTailCall()) 758 cast<CallInst>(New)->setTailCall(); 759 } 760 Args.clear(); 761 762 if (!Call->use_empty()) { 763 if (New->getType() == Call->getType()) { 764 // Return type not changed? Just replace users then 765 Call->replaceAllUsesWith(New); 766 New->takeName(Call); 767 } else if (New->getType() == Type::VoidTy) { 768 // Our return value has uses, but they will get removed later on. 769 // Replace by null for now. 770 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 771 } else { 772 assert(isa<StructType>(RetTy) && "Return type changed, but not into a" 773 "void. The old return type must have" 774 "been a struct!"); 775 // The original return value was a struct, update all uses (which are 776 // all extractvalue instructions). 777 for (Value::use_iterator I = Call->use_begin(), E = Call->use_end(); 778 I != E;) { 779 assert(isa<ExtractValueInst>(*I) && "Return value not only used by" 780 "extractvalue?"); 781 ExtractValueInst *EV = cast<ExtractValueInst>(*I); 782 // Increment now, since we're about to throw away this use. 783 ++I; 784 assert(EV->hasIndices() && "Return value used by extractvalue without" 785 "indices?"); 786 unsigned Idx = *EV->idx_begin(); 787 if (NewRetIdxs[Idx] != -1) { 788 if (RetTypes.size() > 1) { 789 // We're still returning a struct, create a new extractvalue 790 // instruction with the first index updated 791 std::vector<unsigned> NewIdxs(EV->idx_begin(), EV->idx_end()); 792 NewIdxs[0] = NewRetIdxs[Idx]; 793 Value *NEV = ExtractValueInst::Create(New, NewIdxs.begin(), 794 NewIdxs.end(), "retval", 795 EV); 796 EV->replaceAllUsesWith(NEV); 797 EV->eraseFromParent(); 798 } else { 799 // We are now only returning a simple value, remove the 800 // extractvalue 801 EV->replaceAllUsesWith(New); 802 EV->eraseFromParent(); 803 } 804 } else { 805 // Value unused, replace uses by null for now, they will get removed 806 // later on 807 EV->replaceAllUsesWith(Constant::getNullValue(EV->getType())); 808 EV->eraseFromParent(); 809 } 810 } 811 New->takeName(Call); 812 } 813 } 814 815 // Finally, remove the old call from the program, reducing the use-count of 816 // F. 817 Call->eraseFromParent(); 818 } 819 820 // Since we have now created the new function, splice the body of the old 821 // function right into the new function, leaving the old rotting hulk of the 822 // function empty. 823 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 824 825 // Loop over the argument list, transfering uses of the old arguments over to 826 // the new arguments, also transfering over the names as well. 827 i = 0; 828 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 829 I2 = NF->arg_begin(); I != E; ++I, ++i) 830 if (ArgAlive[i]) { 831 // If this is a live argument, move the name and users over to the new 832 // version. 833 I->replaceAllUsesWith(I2); 834 I2->takeName(I); 835 ++I2; 836 } else { 837 // If this argument is dead, replace any uses of it with null constants 838 // (these are guaranteed to become unused later on) 839 I->replaceAllUsesWith(Constant::getNullValue(I->getType())); 840 } 841 842 // If we change the return value of the function we must rewrite any return 843 // instructions. Check this now. 844 if (F->getReturnType() != NF->getReturnType()) 845 for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB) 846 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 847 Value *RetVal; 848 849 if (NFTy->getReturnType() == Type::VoidTy) { 850 RetVal = 0; 851 } else { 852 assert (isa<StructType>(RetTy)); 853 // The original return value was a struct, insert 854 // extractvalue/insertvalue chains to extract only the values we need 855 // to return and insert them into our new result. 856 // This does generate messy code, but we'll let it to instcombine to 857 // clean that up 858 Value *OldRet = RI->getOperand(0); 859 // Start out building up our return value from undef 860 RetVal = llvm::UndefValue::get(NRetTy); 861 for (unsigned i = 0; i != RetCount; ++i) 862 if (NewRetIdxs[i] != -1) { 863 ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i, 864 "newret", RI); 865 if (RetTypes.size() > 1) { 866 // We're still returning a struct, so reinsert the value into 867 // our new return value at the new index 868 869 RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i], 870 "oldret"); 871 } else { 872 // We are now only returning a simple value, so just return the 873 // extracted value 874 RetVal = EV; 875 } 876 } 877 } 878 // Replace the return instruction with one returning the new return 879 // value (possibly 0 if we became void). 880 ReturnInst::Create(RetVal, RI); 881 BB->getInstList().erase(RI); 882 } 883 884 // Now that the old function is dead, delete it. 885 F->eraseFromParent(); 886 887 return true; 888} 889 890bool DAE::runOnModule(Module &M) { 891 bool Changed = false; 892 // First pass: Do a simple check to see if any functions can have their "..." 893 // removed. We can do this if they never call va_start. This loop cannot be 894 // fused with the next loop, because deleting a function invalidates 895 // information computed while surveying other functions. 896 DOUT << "DAE - Deleting dead varargs\n"; 897 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 898 Function &F = *I++; 899 if (F.getFunctionType()->isVarArg()) 900 Changed |= DeleteDeadVarargs(F); 901 } 902 903 // Second phase:loop through the module, determining which arguments are live. 904 // We assume all arguments are dead unless proven otherwise (allowing us to 905 // determine that dead arguments passed into recursive functions are dead). 906 // 907 DOUT << "DAE - Determining liveness\n"; 908 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 909 SurveyFunction(*I); 910 911 // Now, remove all dead arguments and return values from each function in 912 // turn 913 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 914 // Increment now, because the function will probably get removed (ie 915 // replaced by a new one) 916 Function *F = I++; 917 Changed |= RemoveDeadStuffFromFunction(F); 918 } 919 920 return Changed; 921} 922