DeadArgumentElimination.cpp revision 0b8c9a80f20772c3793201ab5b251d3520b9cea3
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/ADT/DenseMap.h" 23#include "llvm/ADT/SmallVector.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/ADT/StringExtras.h" 26#include "llvm/DIBuilder.h" 27#include "llvm/DebugInfo.h" 28#include "llvm/IR/CallingConv.h" 29#include "llvm/IR/Constant.h" 30#include "llvm/IR/DerivedTypes.h" 31#include "llvm/IR/Instructions.h" 32#include "llvm/IR/IntrinsicInst.h" 33#include "llvm/IR/LLVMContext.h" 34#include "llvm/IR/Module.h" 35#include "llvm/Pass.h" 36#include "llvm/Support/CallSite.h" 37#include "llvm/Support/Debug.h" 38#include "llvm/Support/raw_ostream.h" 39#include <map> 40#include <set> 41using namespace llvm; 42 43STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 44STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 45STATISTIC(NumArgumentsReplacedWithUndef, 46 "Number of unread args replaced with undef"); 47namespace { 48 /// DAE - The dead argument elimination pass. 49 /// 50 class DAE : public ModulePass { 51 public: 52 53 /// Struct that represents (part of) either a return value or a function 54 /// argument. Used so that arguments and return values can be used 55 /// interchangeably. 56 struct RetOrArg { 57 RetOrArg(const Function *F, unsigned Idx, bool IsArg) : F(F), Idx(Idx), 58 IsArg(IsArg) {} 59 const Function *F; 60 unsigned Idx; 61 bool IsArg; 62 63 /// Make RetOrArg comparable, so we can put it into a map. 64 bool operator<(const RetOrArg &O) const { 65 if (F != O.F) 66 return F < O.F; 67 else if (Idx != O.Idx) 68 return Idx < O.Idx; 69 else 70 return IsArg < O.IsArg; 71 } 72 73 /// Make RetOrArg comparable, so we can easily iterate the multimap. 74 bool operator==(const RetOrArg &O) const { 75 return F == O.F && Idx == O.Idx && IsArg == O.IsArg; 76 } 77 78 std::string getDescription() const { 79 return std::string((IsArg ? "Argument #" : "Return value #")) 80 + utostr(Idx) + " of function " + F->getName().str(); 81 } 82 }; 83 84 /// Liveness enum - During our initial pass over the program, we determine 85 /// that things are either alive or maybe alive. We don't mark anything 86 /// explicitly dead (even if we know they are), since anything not alive 87 /// with no registered uses (in Uses) will never be marked alive and will 88 /// thus become dead in the end. 89 enum Liveness { Live, MaybeLive }; 90 91 /// Convenience wrapper 92 RetOrArg CreateRet(const Function *F, unsigned Idx) { 93 return RetOrArg(F, Idx, false); 94 } 95 /// Convenience wrapper 96 RetOrArg CreateArg(const Function *F, unsigned Idx) { 97 return RetOrArg(F, Idx, true); 98 } 99 100 typedef std::multimap<RetOrArg, RetOrArg> UseMap; 101 /// This maps a return value or argument to any MaybeLive return values or 102 /// arguments it uses. This allows the MaybeLive values to be marked live 103 /// when any of its users is marked live. 104 /// For example (indices are left out for clarity): 105 /// - Uses[ret F] = ret G 106 /// This means that F calls G, and F returns the value returned by G. 107 /// - Uses[arg F] = ret G 108 /// This means that some function calls G and passes its result as an 109 /// argument to F. 110 /// - Uses[ret F] = arg F 111 /// This means that F returns one of its own arguments. 112 /// - Uses[arg F] = arg G 113 /// This means that G calls F and passes one of its own (G's) arguments 114 /// directly to F. 115 UseMap Uses; 116 117 typedef std::set<RetOrArg> LiveSet; 118 typedef std::set<const Function*> LiveFuncSet; 119 120 /// This set contains all values that have been determined to be live. 121 LiveSet LiveValues; 122 /// This set contains all values that are cannot be changed in any way. 123 LiveFuncSet LiveFunctions; 124 125 typedef SmallVector<RetOrArg, 5> UseVector; 126 127 // Map each LLVM function to corresponding metadata with debug info. If 128 // the function is replaced with another one, we should patch the pointer 129 // to LLVM function in metadata. 130 // As the code generation for module is finished (and DIBuilder is 131 // finalized) we assume that subprogram descriptors won't be changed, and 132 // they are stored in map for short duration anyway. 133 typedef DenseMap<Function*, DISubprogram> FunctionDIMap; 134 FunctionDIMap FunctionDIs; 135 136 protected: 137 // DAH uses this to specify a different ID. 138 explicit DAE(char &ID) : ModulePass(ID) {} 139 140 public: 141 static char ID; // Pass identification, replacement for typeid 142 DAE() : ModulePass(ID) { 143 initializeDAEPass(*PassRegistry::getPassRegistry()); 144 } 145 146 bool runOnModule(Module &M); 147 148 virtual bool ShouldHackArguments() const { return false; } 149 150 private: 151 Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); 152 Liveness SurveyUse(Value::const_use_iterator U, UseVector &MaybeLiveUses, 153 unsigned RetValNum = 0); 154 Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); 155 156 void CollectFunctionDIs(Module &M); 157 void SurveyFunction(const Function &F); 158 void MarkValue(const RetOrArg &RA, Liveness L, 159 const UseVector &MaybeLiveUses); 160 void MarkLive(const RetOrArg &RA); 161 void MarkLive(const Function &F); 162 void PropagateLiveness(const RetOrArg &RA); 163 bool RemoveDeadStuffFromFunction(Function *F); 164 bool DeleteDeadVarargs(Function &Fn); 165 bool RemoveDeadArgumentsFromCallers(Function &Fn); 166 }; 167} 168 169 170char DAE::ID = 0; 171INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) 172 173namespace { 174 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 175 /// deletes arguments to functions which are external. This is only for use 176 /// by bugpoint. 177 struct DAH : public DAE { 178 static char ID; 179 DAH() : DAE(ID) {} 180 181 virtual bool ShouldHackArguments() const { return true; } 182 }; 183} 184 185char DAH::ID = 0; 186INITIALIZE_PASS(DAH, "deadarghaX0r", 187 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", 188 false, false) 189 190/// createDeadArgEliminationPass - This pass removes arguments from functions 191/// which are not used by the body of the function. 192/// 193ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 194ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 195 196/// CollectFunctionDIs - Map each function in the module to its debug info 197/// descriptor. 198void DAE::CollectFunctionDIs(Module &M) { 199 FunctionDIs.clear(); 200 201 for (Module::named_metadata_iterator I = M.named_metadata_begin(), 202 E = M.named_metadata_end(); I != E; ++I) { 203 NamedMDNode &NMD = *I; 204 for (unsigned MDIndex = 0, MDNum = NMD.getNumOperands(); 205 MDIndex < MDNum; ++MDIndex) { 206 MDNode *Node = NMD.getOperand(MDIndex); 207 if (!DIDescriptor(Node).isCompileUnit()) 208 continue; 209 DICompileUnit CU(Node); 210 const DIArray &SPs = CU.getSubprograms(); 211 for (unsigned SPIndex = 0, SPNum = SPs.getNumElements(); 212 SPIndex < SPNum; ++SPIndex) { 213 DISubprogram SP(SPs.getElement(SPIndex)); 214 if (!SP.Verify()) 215 continue; 216 if (Function *F = SP.getFunction()) 217 FunctionDIs[F] = SP; 218 } 219 } 220 } 221} 222 223/// DeleteDeadVarargs - If this is an function that takes a ... list, and if 224/// llvm.vastart is never called, the varargs list is dead for the function. 225bool DAE::DeleteDeadVarargs(Function &Fn) { 226 assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 227 if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false; 228 229 // Ensure that the function is only directly called. 230 if (Fn.hasAddressTaken()) 231 return false; 232 233 // Okay, we know we can transform this function if safe. Scan its body 234 // looking for calls to llvm.vastart. 235 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 236 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 237 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 238 if (II->getIntrinsicID() == Intrinsic::vastart) 239 return false; 240 } 241 } 242 } 243 244 // If we get here, there are no calls to llvm.vastart in the function body, 245 // remove the "..." and adjust all the calls. 246 247 // Start by computing a new prototype for the function, which is the same as 248 // the old function, but doesn't have isVarArg set. 249 FunctionType *FTy = Fn.getFunctionType(); 250 251 std::vector<Type*> Params(FTy->param_begin(), FTy->param_end()); 252 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), 253 Params, false); 254 unsigned NumArgs = Params.size(); 255 256 // Create the new function body and insert it into the module... 257 Function *NF = Function::Create(NFTy, Fn.getLinkage()); 258 NF->copyAttributesFrom(&Fn); 259 Fn.getParent()->getFunctionList().insert(&Fn, NF); 260 NF->takeName(&Fn); 261 262 // Loop over all of the callers of the function, transforming the call sites 263 // to pass in a smaller number of arguments into the new function. 264 // 265 std::vector<Value*> Args; 266 while (!Fn.use_empty()) { 267 CallSite CS(Fn.use_back()); 268 Instruction *Call = CS.getInstruction(); 269 270 // Pass all the same arguments. 271 Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs); 272 273 // Drop any attributes that were on the vararg arguments. 274 AttributeSet PAL = CS.getAttributes(); 275 if (!PAL.isEmpty() && PAL.getSlot(PAL.getNumSlots() - 1).Index > NumArgs) { 276 SmallVector<AttributeWithIndex, 8> AttributesVec; 277 for (unsigned i = 0; PAL.getSlot(i).Index <= NumArgs; ++i) 278 AttributesVec.push_back(PAL.getSlot(i)); 279 Attribute FnAttrs = PAL.getFnAttributes(); 280 if (FnAttrs.hasAttributes()) 281 AttributesVec.push_back(AttributeWithIndex::get(AttributeSet::FunctionIndex, 282 FnAttrs)); 283 PAL = AttributeSet::get(Fn.getContext(), AttributesVec); 284 } 285 286 Instruction *New; 287 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 288 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 289 Args, "", Call); 290 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 291 cast<InvokeInst>(New)->setAttributes(PAL); 292 } else { 293 New = CallInst::Create(NF, Args, "", Call); 294 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 295 cast<CallInst>(New)->setAttributes(PAL); 296 if (cast<CallInst>(Call)->isTailCall()) 297 cast<CallInst>(New)->setTailCall(); 298 } 299 New->setDebugLoc(Call->getDebugLoc()); 300 301 Args.clear(); 302 303 if (!Call->use_empty()) 304 Call->replaceAllUsesWith(New); 305 306 New->takeName(Call); 307 308 // Finally, remove the old call from the program, reducing the use-count of 309 // F. 310 Call->eraseFromParent(); 311 } 312 313 // Since we have now created the new function, splice the body of the old 314 // function right into the new function, leaving the old rotting hulk of the 315 // function empty. 316 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 317 318 // Loop over the argument list, transferring uses of the old arguments over to 319 // the new arguments, also transferring over the names as well. While we're at 320 // it, remove the dead arguments from the DeadArguments list. 321 // 322 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 323 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 324 // Move the name and users over to the new version. 325 I->replaceAllUsesWith(I2); 326 I2->takeName(I); 327 } 328 329 // Patch the pointer to LLVM function in debug info descriptor. 330 FunctionDIMap::iterator DI = FunctionDIs.find(&Fn); 331 if (DI != FunctionDIs.end()) 332 DI->second.replaceFunction(NF); 333 334 // Finally, nuke the old function. 335 Fn.eraseFromParent(); 336 return true; 337} 338 339/// RemoveDeadArgumentsFromCallers - Checks if the given function has any 340/// arguments that are unused, and changes the caller parameters to be undefined 341/// instead. 342bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn) 343{ 344 if (Fn.isDeclaration() || Fn.mayBeOverridden()) 345 return false; 346 347 // Functions with local linkage should already have been handled. 348 if (Fn.hasLocalLinkage()) 349 return false; 350 351 if (Fn.use_empty()) 352 return false; 353 354 llvm::SmallVector<unsigned, 8> UnusedArgs; 355 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(); 356 I != E; ++I) { 357 Argument *Arg = I; 358 359 if (Arg->use_empty() && !Arg->hasByValAttr()) 360 UnusedArgs.push_back(Arg->getArgNo()); 361 } 362 363 if (UnusedArgs.empty()) 364 return false; 365 366 bool Changed = false; 367 368 for (Function::use_iterator I = Fn.use_begin(), E = Fn.use_end(); 369 I != E; ++I) { 370 CallSite CS(*I); 371 if (!CS || !CS.isCallee(I)) 372 continue; 373 374 // Now go through all unused args and replace them with "undef". 375 for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { 376 unsigned ArgNo = UnusedArgs[I]; 377 378 Value *Arg = CS.getArgument(ArgNo); 379 CS.setArgument(ArgNo, UndefValue::get(Arg->getType())); 380 ++NumArgumentsReplacedWithUndef; 381 Changed = true; 382 } 383 } 384 385 return Changed; 386} 387 388/// Convenience function that returns the number of return values. It returns 0 389/// for void functions and 1 for functions not returning a struct. It returns 390/// the number of struct elements for functions returning a struct. 391static unsigned NumRetVals(const Function *F) { 392 if (F->getReturnType()->isVoidTy()) 393 return 0; 394 else if (StructType *STy = dyn_cast<StructType>(F->getReturnType())) 395 return STy->getNumElements(); 396 else 397 return 1; 398} 399 400/// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not 401/// live, it adds Use to the MaybeLiveUses argument. Returns the determined 402/// liveness of Use. 403DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) { 404 // We're live if our use or its Function is already marked as live. 405 if (LiveFunctions.count(Use.F) || LiveValues.count(Use)) 406 return Live; 407 408 // We're maybe live otherwise, but remember that we must become live if 409 // Use becomes live. 410 MaybeLiveUses.push_back(Use); 411 return MaybeLive; 412} 413 414 415/// SurveyUse - This looks at a single use of an argument or return value 416/// and determines if it should be alive or not. Adds this use to MaybeLiveUses 417/// if it causes the used value to become MaybeLive. 418/// 419/// RetValNum is the return value number to use when this use is used in a 420/// return instruction. This is used in the recursion, you should always leave 421/// it at 0. 422DAE::Liveness DAE::SurveyUse(Value::const_use_iterator U, 423 UseVector &MaybeLiveUses, unsigned RetValNum) { 424 const User *V = *U; 425 if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { 426 // The value is returned from a function. It's only live when the 427 // function's return value is live. We use RetValNum here, for the case 428 // that U is really a use of an insertvalue instruction that uses the 429 // original Use. 430 RetOrArg Use = CreateRet(RI->getParent()->getParent(), RetValNum); 431 // We might be live, depending on the liveness of Use. 432 return MarkIfNotLive(Use, MaybeLiveUses); 433 } 434 if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 435 if (U.getOperandNo() != InsertValueInst::getAggregateOperandIndex() 436 && IV->hasIndices()) 437 // The use we are examining is inserted into an aggregate. Our liveness 438 // depends on all uses of that aggregate, but if it is used as a return 439 // value, only index at which we were inserted counts. 440 RetValNum = *IV->idx_begin(); 441 442 // Note that if we are used as the aggregate operand to the insertvalue, 443 // we don't change RetValNum, but do survey all our uses. 444 445 Liveness Result = MaybeLive; 446 for (Value::const_use_iterator I = IV->use_begin(), 447 E = V->use_end(); I != E; ++I) { 448 Result = SurveyUse(I, MaybeLiveUses, RetValNum); 449 if (Result == Live) 450 break; 451 } 452 return Result; 453 } 454 455 if (ImmutableCallSite CS = V) { 456 const Function *F = CS.getCalledFunction(); 457 if (F) { 458 // Used in a direct call. 459 460 // Find the argument number. We know for sure that this use is an 461 // argument, since if it was the function argument this would be an 462 // indirect call and the we know can't be looking at a value of the 463 // label type (for the invoke instruction). 464 unsigned ArgNo = CS.getArgumentNo(U); 465 466 if (ArgNo >= F->getFunctionType()->getNumParams()) 467 // The value is passed in through a vararg! Must be live. 468 return Live; 469 470 assert(CS.getArgument(ArgNo) 471 == CS->getOperand(U.getOperandNo()) 472 && "Argument is not where we expected it"); 473 474 // Value passed to a normal call. It's only live when the corresponding 475 // argument to the called function turns out live. 476 RetOrArg Use = CreateArg(F, ArgNo); 477 return MarkIfNotLive(Use, MaybeLiveUses); 478 } 479 } 480 // Used in any other way? Value must be live. 481 return Live; 482} 483 484/// SurveyUses - This looks at all the uses of the given value 485/// Returns the Liveness deduced from the uses of this value. 486/// 487/// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If 488/// the result is Live, MaybeLiveUses might be modified but its content should 489/// be ignored (since it might not be complete). 490DAE::Liveness DAE::SurveyUses(const Value *V, UseVector &MaybeLiveUses) { 491 // Assume it's dead (which will only hold if there are no uses at all..). 492 Liveness Result = MaybeLive; 493 // Check each use. 494 for (Value::const_use_iterator I = V->use_begin(), 495 E = V->use_end(); I != E; ++I) { 496 Result = SurveyUse(I, MaybeLiveUses); 497 if (Result == Live) 498 break; 499 } 500 return Result; 501} 502 503// SurveyFunction - This performs the initial survey of the specified function, 504// checking out whether or not it uses any of its incoming arguments or whether 505// any callers use the return value. This fills in the LiveValues set and Uses 506// map. 507// 508// We consider arguments of non-internal functions to be intrinsically alive as 509// well as arguments to functions which have their "address taken". 510// 511void DAE::SurveyFunction(const Function &F) { 512 unsigned RetCount = NumRetVals(&F); 513 // Assume all return values are dead 514 typedef SmallVector<Liveness, 5> RetVals; 515 RetVals RetValLiveness(RetCount, MaybeLive); 516 517 typedef SmallVector<UseVector, 5> RetUses; 518 // These vectors map each return value to the uses that make it MaybeLive, so 519 // we can add those to the Uses map if the return value really turns out to be 520 // MaybeLive. Initialized to a list of RetCount empty lists. 521 RetUses MaybeLiveRetUses(RetCount); 522 523 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 524 if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 525 if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 526 != F.getFunctionType()->getReturnType()) { 527 // We don't support old style multiple return values. 528 MarkLive(F); 529 return; 530 } 531 532 if (!F.hasLocalLinkage() && (!ShouldHackArguments() || F.isIntrinsic())) { 533 MarkLive(F); 534 return; 535 } 536 537 DEBUG(dbgs() << "DAE - Inspecting callers for fn: " << F.getName() << "\n"); 538 // Keep track of the number of live retvals, so we can skip checks once all 539 // of them turn out to be live. 540 unsigned NumLiveRetVals = 0; 541 Type *STy = dyn_cast<StructType>(F.getReturnType()); 542 // Loop all uses of the function. 543 for (Value::const_use_iterator I = F.use_begin(), E = F.use_end(); 544 I != E; ++I) { 545 // If the function is PASSED IN as an argument, its address has been 546 // taken. 547 ImmutableCallSite CS(*I); 548 if (!CS || !CS.isCallee(I)) { 549 MarkLive(F); 550 return; 551 } 552 553 // If this use is anything other than a call site, the function is alive. 554 const Instruction *TheCall = CS.getInstruction(); 555 if (!TheCall) { // Not a direct call site? 556 MarkLive(F); 557 return; 558 } 559 560 // If we end up here, we are looking at a direct call to our function. 561 562 // Now, check how our return value(s) is/are used in this caller. Don't 563 // bother checking return values if all of them are live already. 564 if (NumLiveRetVals != RetCount) { 565 if (STy) { 566 // Check all uses of the return value. 567 for (Value::const_use_iterator I = TheCall->use_begin(), 568 E = TheCall->use_end(); I != E; ++I) { 569 const ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I); 570 if (Ext && Ext->hasIndices()) { 571 // This use uses a part of our return value, survey the uses of 572 // that part and store the results for this index only. 573 unsigned Idx = *Ext->idx_begin(); 574 if (RetValLiveness[Idx] != Live) { 575 RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 576 if (RetValLiveness[Idx] == Live) 577 NumLiveRetVals++; 578 } 579 } else { 580 // Used by something else than extractvalue. Mark all return 581 // values as live. 582 for (unsigned i = 0; i != RetCount; ++i ) 583 RetValLiveness[i] = Live; 584 NumLiveRetVals = RetCount; 585 break; 586 } 587 } 588 } else { 589 // Single return value 590 RetValLiveness[0] = SurveyUses(TheCall, MaybeLiveRetUses[0]); 591 if (RetValLiveness[0] == Live) 592 NumLiveRetVals = RetCount; 593 } 594 } 595 } 596 597 // Now we've inspected all callers, record the liveness of our return values. 598 for (unsigned i = 0; i != RetCount; ++i) 599 MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]); 600 601 DEBUG(dbgs() << "DAE - Inspecting args for fn: " << F.getName() << "\n"); 602 603 // Now, check all of our arguments. 604 unsigned i = 0; 605 UseVector MaybeLiveArgUses; 606 for (Function::const_arg_iterator AI = F.arg_begin(), 607 E = F.arg_end(); AI != E; ++AI, ++i) { 608 // See what the effect of this use is (recording any uses that cause 609 // MaybeLive in MaybeLiveArgUses). 610 Liveness Result = SurveyUses(AI, MaybeLiveArgUses); 611 // Mark the result. 612 MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses); 613 // Clear the vector again for the next iteration. 614 MaybeLiveArgUses.clear(); 615 } 616} 617 618/// MarkValue - This function marks the liveness of RA depending on L. If L is 619/// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, 620/// such that RA will be marked live if any use in MaybeLiveUses gets marked 621/// live later on. 622void DAE::MarkValue(const RetOrArg &RA, Liveness L, 623 const UseVector &MaybeLiveUses) { 624 switch (L) { 625 case Live: MarkLive(RA); break; 626 case MaybeLive: 627 { 628 // Note any uses of this value, so this return value can be 629 // marked live whenever one of the uses becomes live. 630 for (UseVector::const_iterator UI = MaybeLiveUses.begin(), 631 UE = MaybeLiveUses.end(); UI != UE; ++UI) 632 Uses.insert(std::make_pair(*UI, RA)); 633 break; 634 } 635 } 636} 637 638/// MarkLive - Mark the given Function as alive, meaning that it cannot be 639/// changed in any way. Additionally, 640/// mark any values that are used as this function's parameters or by its return 641/// values (according to Uses) live as well. 642void DAE::MarkLive(const Function &F) { 643 DEBUG(dbgs() << "DAE - Intrinsically live fn: " << F.getName() << "\n"); 644 // Mark the function as live. 645 LiveFunctions.insert(&F); 646 // Mark all arguments as live. 647 for (unsigned i = 0, e = F.arg_size(); i != e; ++i) 648 PropagateLiveness(CreateArg(&F, i)); 649 // Mark all return values as live. 650 for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i) 651 PropagateLiveness(CreateRet(&F, i)); 652} 653 654/// MarkLive - Mark the given return value or argument as live. Additionally, 655/// mark any values that are used by this value (according to Uses) live as 656/// well. 657void DAE::MarkLive(const RetOrArg &RA) { 658 if (LiveFunctions.count(RA.F)) 659 return; // Function was already marked Live. 660 661 if (!LiveValues.insert(RA).second) 662 return; // We were already marked Live. 663 664 DEBUG(dbgs() << "DAE - Marking " << RA.getDescription() << " live\n"); 665 PropagateLiveness(RA); 666} 667 668/// PropagateLiveness - Given that RA is a live value, propagate it's liveness 669/// to any other values it uses (according to Uses). 670void DAE::PropagateLiveness(const RetOrArg &RA) { 671 // We don't use upper_bound (or equal_range) here, because our recursive call 672 // to ourselves is likely to cause the upper_bound (which is the first value 673 // not belonging to RA) to become erased and the iterator invalidated. 674 UseMap::iterator Begin = Uses.lower_bound(RA); 675 UseMap::iterator E = Uses.end(); 676 UseMap::iterator I; 677 for (I = Begin; I != E && I->first == RA; ++I) 678 MarkLive(I->second); 679 680 // Erase RA from the Uses map (from the lower bound to wherever we ended up 681 // after the loop). 682 Uses.erase(Begin, I); 683} 684 685// RemoveDeadStuffFromFunction - Remove any arguments and return values from F 686// that are not in LiveValues. Transform the function and all of the callees of 687// the function to not have these arguments and return values. 688// 689bool DAE::RemoveDeadStuffFromFunction(Function *F) { 690 // Don't modify fully live functions 691 if (LiveFunctions.count(F)) 692 return false; 693 694 // Start by computing a new prototype for the function, which is the same as 695 // the old function, but has fewer arguments and a different return type. 696 FunctionType *FTy = F->getFunctionType(); 697 std::vector<Type*> Params; 698 699 // Set up to build a new list of parameter attributes. 700 SmallVector<AttributeWithIndex, 8> AttributesVec; 701 const AttributeSet &PAL = F->getAttributes(); 702 703 // The existing function return attributes. 704 Attribute RAttrs = PAL.getRetAttributes(); 705 Attribute FnAttrs = PAL.getFnAttributes(); 706 707 // Find out the new return value. 708 709 Type *RetTy = FTy->getReturnType(); 710 Type *NRetTy = NULL; 711 unsigned RetCount = NumRetVals(F); 712 713 // -1 means unused, other numbers are the new index 714 SmallVector<int, 5> NewRetIdxs(RetCount, -1); 715 std::vector<Type*> RetTypes; 716 if (RetTy->isVoidTy()) { 717 NRetTy = RetTy; 718 } else { 719 StructType *STy = dyn_cast<StructType>(RetTy); 720 if (STy) 721 // Look at each of the original return values individually. 722 for (unsigned i = 0; i != RetCount; ++i) { 723 RetOrArg Ret = CreateRet(F, i); 724 if (LiveValues.erase(Ret)) { 725 RetTypes.push_back(STy->getElementType(i)); 726 NewRetIdxs[i] = RetTypes.size() - 1; 727 } else { 728 ++NumRetValsEliminated; 729 DEBUG(dbgs() << "DAE - Removing return value " << i << " from " 730 << F->getName() << "\n"); 731 } 732 } 733 else 734 // We used to return a single value. 735 if (LiveValues.erase(CreateRet(F, 0))) { 736 RetTypes.push_back(RetTy); 737 NewRetIdxs[0] = 0; 738 } else { 739 DEBUG(dbgs() << "DAE - Removing return value from " << F->getName() 740 << "\n"); 741 ++NumRetValsEliminated; 742 } 743 if (RetTypes.size() > 1) 744 // More than one return type? Return a struct with them. Also, if we used 745 // to return a struct and didn't change the number of return values, 746 // return a struct again. This prevents changing {something} into 747 // something and {} into void. 748 // Make the new struct packed if we used to return a packed struct 749 // already. 750 NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); 751 else if (RetTypes.size() == 1) 752 // One return type? Just a simple value then, but only if we didn't use to 753 // return a struct with that simple value before. 754 NRetTy = RetTypes.front(); 755 else if (RetTypes.size() == 0) 756 // No return types? Make it void, but only if we didn't use to return {}. 757 NRetTy = Type::getVoidTy(F->getContext()); 758 } 759 760 assert(NRetTy && "No new return type found?"); 761 762 // Remove any incompatible attributes, but only if we removed all return 763 // values. Otherwise, ensure that we don't have any conflicting attributes 764 // here. Currently, this should not be possible, but special handling might be 765 // required when new return value attributes are added. 766 if (NRetTy->isVoidTy()) 767 RAttrs = 768 Attribute::get(NRetTy->getContext(), AttrBuilder(RAttrs). 769 removeAttributes(Attribute::typeIncompatible(NRetTy))); 770 else 771 assert(!AttrBuilder(RAttrs). 772 hasAttributes(Attribute::typeIncompatible(NRetTy)) && 773 "Return attributes no longer compatible?"); 774 775 if (RAttrs.hasAttributes()) 776 AttributesVec.push_back(AttributeWithIndex::get(AttributeSet::ReturnIndex, 777 RAttrs)); 778 779 // Remember which arguments are still alive. 780 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 781 // Construct the new parameter list from non-dead arguments. Also construct 782 // a new set of parameter attributes to correspond. Skip the first parameter 783 // attribute, since that belongs to the return value. 784 unsigned i = 0; 785 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 786 I != E; ++I, ++i) { 787 RetOrArg Arg = CreateArg(F, i); 788 if (LiveValues.erase(Arg)) { 789 Params.push_back(I->getType()); 790 ArgAlive[i] = true; 791 792 // Get the original parameter attributes (skipping the first one, that is 793 // for the return value. 794 Attribute Attrs = PAL.getParamAttributes(i + 1); 795 if (Attrs.hasAttributes()) 796 AttributesVec.push_back(AttributeWithIndex::get(Params.size(), Attrs)); 797 } else { 798 ++NumArgumentsEliminated; 799 DEBUG(dbgs() << "DAE - Removing argument " << i << " (" << I->getName() 800 << ") from " << F->getName() << "\n"); 801 } 802 } 803 804 if (FnAttrs.hasAttributes()) 805 AttributesVec.push_back(AttributeWithIndex::get(AttributeSet::FunctionIndex, 806 FnAttrs)); 807 808 // Reconstruct the AttributesList based on the vector we constructed. 809 AttributeSet NewPAL = AttributeSet::get(F->getContext(), AttributesVec); 810 811 // Create the new function type based on the recomputed parameters. 812 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 813 814 // No change? 815 if (NFTy == FTy) 816 return false; 817 818 // Create the new function body and insert it into the module... 819 Function *NF = Function::Create(NFTy, F->getLinkage()); 820 NF->copyAttributesFrom(F); 821 NF->setAttributes(NewPAL); 822 // Insert the new function before the old function, so we won't be processing 823 // it again. 824 F->getParent()->getFunctionList().insert(F, NF); 825 NF->takeName(F); 826 827 // Loop over all of the callers of the function, transforming the call sites 828 // to pass in a smaller number of arguments into the new function. 829 // 830 std::vector<Value*> Args; 831 while (!F->use_empty()) { 832 CallSite CS(F->use_back()); 833 Instruction *Call = CS.getInstruction(); 834 835 AttributesVec.clear(); 836 const AttributeSet &CallPAL = CS.getAttributes(); 837 838 // The call return attributes. 839 Attribute RAttrs = CallPAL.getRetAttributes(); 840 Attribute FnAttrs = CallPAL.getFnAttributes(); 841 // Adjust in case the function was changed to return void. 842 RAttrs = 843 Attribute::get(NF->getContext(), AttrBuilder(RAttrs). 844 removeAttributes(Attribute::typeIncompatible(NF->getReturnType()))); 845 if (RAttrs.hasAttributes()) 846 AttributesVec.push_back(AttributeWithIndex::get(AttributeSet::ReturnIndex, 847 RAttrs)); 848 849 // Declare these outside of the loops, so we can reuse them for the second 850 // loop, which loops the varargs. 851 CallSite::arg_iterator I = CS.arg_begin(); 852 unsigned i = 0; 853 // Loop over those operands, corresponding to the normal arguments to the 854 // original function, and add those that are still alive. 855 for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i) 856 if (ArgAlive[i]) { 857 Args.push_back(*I); 858 // Get original parameter attributes, but skip return attributes. 859 Attribute Attrs = CallPAL.getParamAttributes(i + 1); 860 if (Attrs.hasAttributes()) 861 AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); 862 } 863 864 // Push any varargs arguments on the list. Don't forget their attributes. 865 for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { 866 Args.push_back(*I); 867 Attribute Attrs = CallPAL.getParamAttributes(i + 1); 868 if (Attrs.hasAttributes()) 869 AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); 870 } 871 872 if (FnAttrs.hasAttributes()) 873 AttributesVec.push_back(AttributeWithIndex::get(AttributeSet::FunctionIndex, 874 FnAttrs)); 875 876 // Reconstruct the AttributesList based on the vector we constructed. 877 AttributeSet NewCallPAL = AttributeSet::get(F->getContext(), AttributesVec); 878 879 Instruction *New; 880 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 881 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 882 Args, "", Call); 883 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 884 cast<InvokeInst>(New)->setAttributes(NewCallPAL); 885 } else { 886 New = CallInst::Create(NF, Args, "", Call); 887 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 888 cast<CallInst>(New)->setAttributes(NewCallPAL); 889 if (cast<CallInst>(Call)->isTailCall()) 890 cast<CallInst>(New)->setTailCall(); 891 } 892 New->setDebugLoc(Call->getDebugLoc()); 893 894 Args.clear(); 895 896 if (!Call->use_empty()) { 897 if (New->getType() == Call->getType()) { 898 // Return type not changed? Just replace users then. 899 Call->replaceAllUsesWith(New); 900 New->takeName(Call); 901 } else if (New->getType()->isVoidTy()) { 902 // Our return value has uses, but they will get removed later on. 903 // Replace by null for now. 904 if (!Call->getType()->isX86_MMXTy()) 905 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 906 } else { 907 assert(RetTy->isStructTy() && 908 "Return type changed, but not into a void. The old return type" 909 " must have been a struct!"); 910 Instruction *InsertPt = Call; 911 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 912 BasicBlock::iterator IP = II->getNormalDest()->begin(); 913 while (isa<PHINode>(IP)) ++IP; 914 InsertPt = IP; 915 } 916 917 // We used to return a struct. Instead of doing smart stuff with all the 918 // uses of this struct, we will just rebuild it using 919 // extract/insertvalue chaining and let instcombine clean that up. 920 // 921 // Start out building up our return value from undef 922 Value *RetVal = UndefValue::get(RetTy); 923 for (unsigned i = 0; i != RetCount; ++i) 924 if (NewRetIdxs[i] != -1) { 925 Value *V; 926 if (RetTypes.size() > 1) 927 // We are still returning a struct, so extract the value from our 928 // return value 929 V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret", 930 InsertPt); 931 else 932 // We are now returning a single element, so just insert that 933 V = New; 934 // Insert the value at the old position 935 RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt); 936 } 937 // Now, replace all uses of the old call instruction with the return 938 // struct we built 939 Call->replaceAllUsesWith(RetVal); 940 New->takeName(Call); 941 } 942 } 943 944 // Finally, remove the old call from the program, reducing the use-count of 945 // F. 946 Call->eraseFromParent(); 947 } 948 949 // Since we have now created the new function, splice the body of the old 950 // function right into the new function, leaving the old rotting hulk of the 951 // function empty. 952 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 953 954 // Loop over the argument list, transferring uses of the old arguments over to 955 // the new arguments, also transferring over the names as well. 956 i = 0; 957 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 958 I2 = NF->arg_begin(); I != E; ++I, ++i) 959 if (ArgAlive[i]) { 960 // If this is a live argument, move the name and users over to the new 961 // version. 962 I->replaceAllUsesWith(I2); 963 I2->takeName(I); 964 ++I2; 965 } else { 966 // If this argument is dead, replace any uses of it with null constants 967 // (these are guaranteed to become unused later on). 968 if (!I->getType()->isX86_MMXTy()) 969 I->replaceAllUsesWith(Constant::getNullValue(I->getType())); 970 } 971 972 // If we change the return value of the function we must rewrite any return 973 // instructions. Check this now. 974 if (F->getReturnType() != NF->getReturnType()) 975 for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB) 976 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 977 Value *RetVal; 978 979 if (NFTy->getReturnType()->isVoidTy()) { 980 RetVal = 0; 981 } else { 982 assert (RetTy->isStructTy()); 983 // The original return value was a struct, insert 984 // extractvalue/insertvalue chains to extract only the values we need 985 // to return and insert them into our new result. 986 // This does generate messy code, but we'll let it to instcombine to 987 // clean that up. 988 Value *OldRet = RI->getOperand(0); 989 // Start out building up our return value from undef 990 RetVal = UndefValue::get(NRetTy); 991 for (unsigned i = 0; i != RetCount; ++i) 992 if (NewRetIdxs[i] != -1) { 993 ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i, 994 "oldret", RI); 995 if (RetTypes.size() > 1) { 996 // We're still returning a struct, so reinsert the value into 997 // our new return value at the new index 998 999 RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i], 1000 "newret", RI); 1001 } else { 1002 // We are now only returning a simple value, so just return the 1003 // extracted value. 1004 RetVal = EV; 1005 } 1006 } 1007 } 1008 // Replace the return instruction with one returning the new return 1009 // value (possibly 0 if we became void). 1010 ReturnInst::Create(F->getContext(), RetVal, RI); 1011 BB->getInstList().erase(RI); 1012 } 1013 1014 // Patch the pointer to LLVM function in debug info descriptor. 1015 FunctionDIMap::iterator DI = FunctionDIs.find(F); 1016 if (DI != FunctionDIs.end()) 1017 DI->second.replaceFunction(NF); 1018 1019 // Now that the old function is dead, delete it. 1020 F->eraseFromParent(); 1021 1022 return true; 1023} 1024 1025bool DAE::runOnModule(Module &M) { 1026 bool Changed = false; 1027 1028 // Collect debug info descriptors for functions. 1029 CollectFunctionDIs(M); 1030 1031 // First pass: Do a simple check to see if any functions can have their "..." 1032 // removed. We can do this if they never call va_start. This loop cannot be 1033 // fused with the next loop, because deleting a function invalidates 1034 // information computed while surveying other functions. 1035 DEBUG(dbgs() << "DAE - Deleting dead varargs\n"); 1036 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1037 Function &F = *I++; 1038 if (F.getFunctionType()->isVarArg()) 1039 Changed |= DeleteDeadVarargs(F); 1040 } 1041 1042 // Second phase:loop through the module, determining which arguments are live. 1043 // We assume all arguments are dead unless proven otherwise (allowing us to 1044 // determine that dead arguments passed into recursive functions are dead). 1045 // 1046 DEBUG(dbgs() << "DAE - Determining liveness\n"); 1047 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 1048 SurveyFunction(*I); 1049 1050 // Now, remove all dead arguments and return values from each function in 1051 // turn. 1052 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1053 // Increment now, because the function will probably get removed (ie. 1054 // replaced by a new one). 1055 Function *F = I++; 1056 Changed |= RemoveDeadStuffFromFunction(F); 1057 } 1058 1059 // Finally, look for any unused parameters in functions with non-local 1060 // linkage and replace the passed in parameters with undef. 1061 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 1062 Function& F = *I; 1063 1064 Changed |= RemoveDeadArgumentsFromCallers(F); 1065 } 1066 1067 return Changed; 1068} 1069