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> 41 using namespace llvm; 42 43 STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 44 STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 45 STATISTIC(NumArgumentsReplacedWithUndef, 46 "Number of unread args replaced with undef"); 47 namespace { 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 170 char DAE::ID = 0; 171 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) 172 173 namespace { 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 185 char DAH::ID = 0; 186 INITIALIZE_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 /// 193 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 194 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 195 196 /// CollectFunctionDIs - Map each function in the module to its debug info 197 /// descriptor. 198 void 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. 225 bool 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.getSlotIndex(PAL.getNumSlots() - 1) > NumArgs) { 276 SmallVector<AttributeSet, 8> AttributesVec; 277 for (unsigned i = 0; PAL.getSlotIndex(i) <= NumArgs; ++i) 278 AttributesVec.push_back(PAL.getSlotAttributes(i)); 279 if (PAL.hasAttributes(AttributeSet::FunctionIndex)) 280 AttributesVec.push_back(AttributeSet::get(Fn.getContext(), 281 PAL.getFnAttributes())); 282 PAL = AttributeSet::get(Fn.getContext(), AttributesVec); 283 } 284 285 Instruction *New; 286 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 287 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 288 Args, "", Call); 289 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 290 cast<InvokeInst>(New)->setAttributes(PAL); 291 } else { 292 New = CallInst::Create(NF, Args, "", Call); 293 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 294 cast<CallInst>(New)->setAttributes(PAL); 295 if (cast<CallInst>(Call)->isTailCall()) 296 cast<CallInst>(New)->setTailCall(); 297 } 298 New->setDebugLoc(Call->getDebugLoc()); 299 300 Args.clear(); 301 302 if (!Call->use_empty()) 303 Call->replaceAllUsesWith(New); 304 305 New->takeName(Call); 306 307 // Finally, remove the old call from the program, reducing the use-count of 308 // F. 309 Call->eraseFromParent(); 310 } 311 312 // Since we have now created the new function, splice the body of the old 313 // function right into the new function, leaving the old rotting hulk of the 314 // function empty. 315 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 316 317 // Loop over the argument list, transferring uses of the old arguments over to 318 // the new arguments, also transferring over the names as well. While we're at 319 // it, remove the dead arguments from the DeadArguments list. 320 // 321 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 322 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 323 // Move the name and users over to the new version. 324 I->replaceAllUsesWith(I2); 325 I2->takeName(I); 326 } 327 328 // Patch the pointer to LLVM function in debug info descriptor. 329 FunctionDIMap::iterator DI = FunctionDIs.find(&Fn); 330 if (DI != FunctionDIs.end()) 331 DI->second.replaceFunction(NF); 332 333 // Finally, nuke the old function. 334 Fn.eraseFromParent(); 335 return true; 336 } 337 338 /// RemoveDeadArgumentsFromCallers - Checks if the given function has any 339 /// arguments that are unused, and changes the caller parameters to be undefined 340 /// instead. 341 bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn) 342 { 343 if (Fn.isDeclaration() || Fn.mayBeOverridden()) 344 return false; 345 346 // Functions with local linkage should already have been handled. 347 if (Fn.hasLocalLinkage()) 348 return false; 349 350 if (Fn.use_empty()) 351 return false; 352 353 SmallVector<unsigned, 8> UnusedArgs; 354 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(); 355 I != E; ++I) { 356 Argument *Arg = I; 357 358 if (Arg->use_empty() && !Arg->hasByValAttr()) 359 UnusedArgs.push_back(Arg->getArgNo()); 360 } 361 362 if (UnusedArgs.empty()) 363 return false; 364 365 bool Changed = false; 366 367 for (Function::use_iterator I = Fn.use_begin(), E = Fn.use_end(); 368 I != E; ++I) { 369 CallSite CS(*I); 370 if (!CS || !CS.isCallee(I)) 371 continue; 372 373 // Now go through all unused args and replace them with "undef". 374 for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { 375 unsigned ArgNo = UnusedArgs[I]; 376 377 Value *Arg = CS.getArgument(ArgNo); 378 CS.setArgument(ArgNo, UndefValue::get(Arg->getType())); 379 ++NumArgumentsReplacedWithUndef; 380 Changed = true; 381 } 382 } 383 384 return Changed; 385 } 386 387 /// Convenience function that returns the number of return values. It returns 0 388 /// for void functions and 1 for functions not returning a struct. It returns 389 /// the number of struct elements for functions returning a struct. 390 static unsigned NumRetVals(const Function *F) { 391 if (F->getReturnType()->isVoidTy()) 392 return 0; 393 else if (StructType *STy = dyn_cast<StructType>(F->getReturnType())) 394 return STy->getNumElements(); 395 else 396 return 1; 397 } 398 399 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not 400 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined 401 /// liveness of Use. 402 DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) { 403 // We're live if our use or its Function is already marked as live. 404 if (LiveFunctions.count(Use.F) || LiveValues.count(Use)) 405 return Live; 406 407 // We're maybe live otherwise, but remember that we must become live if 408 // Use becomes live. 409 MaybeLiveUses.push_back(Use); 410 return MaybeLive; 411 } 412 413 414 /// SurveyUse - This looks at a single use of an argument or return value 415 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses 416 /// if it causes the used value to become MaybeLive. 417 /// 418 /// RetValNum is the return value number to use when this use is used in a 419 /// return instruction. This is used in the recursion, you should always leave 420 /// it at 0. 421 DAE::Liveness DAE::SurveyUse(Value::const_use_iterator U, 422 UseVector &MaybeLiveUses, unsigned RetValNum) { 423 const User *V = *U; 424 if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { 425 // The value is returned from a function. It's only live when the 426 // function's return value is live. We use RetValNum here, for the case 427 // that U is really a use of an insertvalue instruction that uses the 428 // original Use. 429 RetOrArg Use = CreateRet(RI->getParent()->getParent(), RetValNum); 430 // We might be live, depending on the liveness of Use. 431 return MarkIfNotLive(Use, MaybeLiveUses); 432 } 433 if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 434 if (U.getOperandNo() != InsertValueInst::getAggregateOperandIndex() 435 && IV->hasIndices()) 436 // The use we are examining is inserted into an aggregate. Our liveness 437 // depends on all uses of that aggregate, but if it is used as a return 438 // value, only index at which we were inserted counts. 439 RetValNum = *IV->idx_begin(); 440 441 // Note that if we are used as the aggregate operand to the insertvalue, 442 // we don't change RetValNum, but do survey all our uses. 443 444 Liveness Result = MaybeLive; 445 for (Value::const_use_iterator I = IV->use_begin(), 446 E = V->use_end(); I != E; ++I) { 447 Result = SurveyUse(I, MaybeLiveUses, RetValNum); 448 if (Result == Live) 449 break; 450 } 451 return Result; 452 } 453 454 if (ImmutableCallSite CS = V) { 455 const Function *F = CS.getCalledFunction(); 456 if (F) { 457 // Used in a direct call. 458 459 // Find the argument number. We know for sure that this use is an 460 // argument, since if it was the function argument this would be an 461 // indirect call and the we know can't be looking at a value of the 462 // label type (for the invoke instruction). 463 unsigned ArgNo = CS.getArgumentNo(U); 464 465 if (ArgNo >= F->getFunctionType()->getNumParams()) 466 // The value is passed in through a vararg! Must be live. 467 return Live; 468 469 assert(CS.getArgument(ArgNo) 470 == CS->getOperand(U.getOperandNo()) 471 && "Argument is not where we expected it"); 472 473 // Value passed to a normal call. It's only live when the corresponding 474 // argument to the called function turns out live. 475 RetOrArg Use = CreateArg(F, ArgNo); 476 return MarkIfNotLive(Use, MaybeLiveUses); 477 } 478 } 479 // Used in any other way? Value must be live. 480 return Live; 481 } 482 483 /// SurveyUses - This looks at all the uses of the given value 484 /// Returns the Liveness deduced from the uses of this value. 485 /// 486 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If 487 /// the result is Live, MaybeLiveUses might be modified but its content should 488 /// be ignored (since it might not be complete). 489 DAE::Liveness DAE::SurveyUses(const Value *V, UseVector &MaybeLiveUses) { 490 // Assume it's dead (which will only hold if there are no uses at all..). 491 Liveness Result = MaybeLive; 492 // Check each use. 493 for (Value::const_use_iterator I = V->use_begin(), 494 E = V->use_end(); I != E; ++I) { 495 Result = SurveyUse(I, MaybeLiveUses); 496 if (Result == Live) 497 break; 498 } 499 return Result; 500 } 501 502 // SurveyFunction - This performs the initial survey of the specified function, 503 // checking out whether or not it uses any of its incoming arguments or whether 504 // any callers use the return value. This fills in the LiveValues set and Uses 505 // map. 506 // 507 // We consider arguments of non-internal functions to be intrinsically alive as 508 // well as arguments to functions which have their "address taken". 509 // 510 void DAE::SurveyFunction(const Function &F) { 511 unsigned RetCount = NumRetVals(&F); 512 // Assume all return values are dead 513 typedef SmallVector<Liveness, 5> RetVals; 514 RetVals RetValLiveness(RetCount, MaybeLive); 515 516 typedef SmallVector<UseVector, 5> RetUses; 517 // These vectors map each return value to the uses that make it MaybeLive, so 518 // we can add those to the Uses map if the return value really turns out to be 519 // MaybeLive. Initialized to a list of RetCount empty lists. 520 RetUses MaybeLiveRetUses(RetCount); 521 522 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 523 if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) 524 if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 525 != F.getFunctionType()->getReturnType()) { 526 // We don't support old style multiple return values. 527 MarkLive(F); 528 return; 529 } 530 531 if (!F.hasLocalLinkage() && (!ShouldHackArguments() || F.isIntrinsic())) { 532 MarkLive(F); 533 return; 534 } 535 536 DEBUG(dbgs() << "DAE - Inspecting callers for fn: " << F.getName() << "\n"); 537 // Keep track of the number of live retvals, so we can skip checks once all 538 // of them turn out to be live. 539 unsigned NumLiveRetVals = 0; 540 Type *STy = dyn_cast<StructType>(F.getReturnType()); 541 // Loop all uses of the function. 542 for (Value::const_use_iterator I = F.use_begin(), E = F.use_end(); 543 I != E; ++I) { 544 // If the function is PASSED IN as an argument, its address has been 545 // taken. 546 ImmutableCallSite CS(*I); 547 if (!CS || !CS.isCallee(I)) { 548 MarkLive(F); 549 return; 550 } 551 552 // If this use is anything other than a call site, the function is alive. 553 const Instruction *TheCall = CS.getInstruction(); 554 if (!TheCall) { // Not a direct call site? 555 MarkLive(F); 556 return; 557 } 558 559 // If we end up here, we are looking at a direct call to our function. 560 561 // Now, check how our return value(s) is/are used in this caller. Don't 562 // bother checking return values if all of them are live already. 563 if (NumLiveRetVals != RetCount) { 564 if (STy) { 565 // Check all uses of the return value. 566 for (Value::const_use_iterator I = TheCall->use_begin(), 567 E = TheCall->use_end(); I != E; ++I) { 568 const ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I); 569 if (Ext && Ext->hasIndices()) { 570 // This use uses a part of our return value, survey the uses of 571 // that part and store the results for this index only. 572 unsigned Idx = *Ext->idx_begin(); 573 if (RetValLiveness[Idx] != Live) { 574 RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 575 if (RetValLiveness[Idx] == Live) 576 NumLiveRetVals++; 577 } 578 } else { 579 // Used by something else than extractvalue. Mark all return 580 // values as live. 581 for (unsigned i = 0; i != RetCount; ++i ) 582 RetValLiveness[i] = Live; 583 NumLiveRetVals = RetCount; 584 break; 585 } 586 } 587 } else { 588 // Single return value 589 RetValLiveness[0] = SurveyUses(TheCall, MaybeLiveRetUses[0]); 590 if (RetValLiveness[0] == Live) 591 NumLiveRetVals = RetCount; 592 } 593 } 594 } 595 596 // Now we've inspected all callers, record the liveness of our return values. 597 for (unsigned i = 0; i != RetCount; ++i) 598 MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]); 599 600 DEBUG(dbgs() << "DAE - Inspecting args for fn: " << F.getName() << "\n"); 601 602 // Now, check all of our arguments. 603 unsigned i = 0; 604 UseVector MaybeLiveArgUses; 605 for (Function::const_arg_iterator AI = F.arg_begin(), 606 E = F.arg_end(); AI != E; ++AI, ++i) { 607 // See what the effect of this use is (recording any uses that cause 608 // MaybeLive in MaybeLiveArgUses). 609 Liveness Result = SurveyUses(AI, MaybeLiveArgUses); 610 // Mark the result. 611 MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses); 612 // Clear the vector again for the next iteration. 613 MaybeLiveArgUses.clear(); 614 } 615 } 616 617 /// MarkValue - This function marks the liveness of RA depending on L. If L is 618 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, 619 /// such that RA will be marked live if any use in MaybeLiveUses gets marked 620 /// live later on. 621 void DAE::MarkValue(const RetOrArg &RA, Liveness L, 622 const UseVector &MaybeLiveUses) { 623 switch (L) { 624 case Live: MarkLive(RA); break; 625 case MaybeLive: 626 { 627 // Note any uses of this value, so this return value can be 628 // marked live whenever one of the uses becomes live. 629 for (UseVector::const_iterator UI = MaybeLiveUses.begin(), 630 UE = MaybeLiveUses.end(); UI != UE; ++UI) 631 Uses.insert(std::make_pair(*UI, RA)); 632 break; 633 } 634 } 635 } 636 637 /// MarkLive - Mark the given Function as alive, meaning that it cannot be 638 /// changed in any way. Additionally, 639 /// mark any values that are used as this function's parameters or by its return 640 /// values (according to Uses) live as well. 641 void DAE::MarkLive(const Function &F) { 642 DEBUG(dbgs() << "DAE - Intrinsically live fn: " << F.getName() << "\n"); 643 // Mark the function as live. 644 LiveFunctions.insert(&F); 645 // Mark all arguments as live. 646 for (unsigned i = 0, e = F.arg_size(); i != e; ++i) 647 PropagateLiveness(CreateArg(&F, i)); 648 // Mark all return values as live. 649 for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i) 650 PropagateLiveness(CreateRet(&F, i)); 651 } 652 653 /// MarkLive - Mark the given return value or argument as live. Additionally, 654 /// mark any values that are used by this value (according to Uses) live as 655 /// well. 656 void DAE::MarkLive(const RetOrArg &RA) { 657 if (LiveFunctions.count(RA.F)) 658 return; // Function was already marked Live. 659 660 if (!LiveValues.insert(RA).second) 661 return; // We were already marked Live. 662 663 DEBUG(dbgs() << "DAE - Marking " << RA.getDescription() << " live\n"); 664 PropagateLiveness(RA); 665 } 666 667 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness 668 /// to any other values it uses (according to Uses). 669 void DAE::PropagateLiveness(const RetOrArg &RA) { 670 // We don't use upper_bound (or equal_range) here, because our recursive call 671 // to ourselves is likely to cause the upper_bound (which is the first value 672 // not belonging to RA) to become erased and the iterator invalidated. 673 UseMap::iterator Begin = Uses.lower_bound(RA); 674 UseMap::iterator E = Uses.end(); 675 UseMap::iterator I; 676 for (I = Begin; I != E && I->first == RA; ++I) 677 MarkLive(I->second); 678 679 // Erase RA from the Uses map (from the lower bound to wherever we ended up 680 // after the loop). 681 Uses.erase(Begin, I); 682 } 683 684 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F 685 // that are not in LiveValues. Transform the function and all of the callees of 686 // the function to not have these arguments and return values. 687 // 688 bool DAE::RemoveDeadStuffFromFunction(Function *F) { 689 // Don't modify fully live functions 690 if (LiveFunctions.count(F)) 691 return false; 692 693 // Start by computing a new prototype for the function, which is the same as 694 // the old function, but has fewer arguments and a different return type. 695 FunctionType *FTy = F->getFunctionType(); 696 std::vector<Type*> Params; 697 698 // Set up to build a new list of parameter attributes. 699 SmallVector<AttributeSet, 8> AttributesVec; 700 const AttributeSet &PAL = F->getAttributes(); 701 702 // Find out the new return value. 703 Type *RetTy = FTy->getReturnType(); 704 Type *NRetTy = NULL; 705 unsigned RetCount = NumRetVals(F); 706 707 // -1 means unused, other numbers are the new index 708 SmallVector<int, 5> NewRetIdxs(RetCount, -1); 709 std::vector<Type*> RetTypes; 710 if (RetTy->isVoidTy()) { 711 NRetTy = RetTy; 712 } else { 713 StructType *STy = dyn_cast<StructType>(RetTy); 714 if (STy) 715 // Look at each of the original return values individually. 716 for (unsigned i = 0; i != RetCount; ++i) { 717 RetOrArg Ret = CreateRet(F, i); 718 if (LiveValues.erase(Ret)) { 719 RetTypes.push_back(STy->getElementType(i)); 720 NewRetIdxs[i] = RetTypes.size() - 1; 721 } else { 722 ++NumRetValsEliminated; 723 DEBUG(dbgs() << "DAE - Removing return value " << i << " from " 724 << F->getName() << "\n"); 725 } 726 } 727 else 728 // We used to return a single value. 729 if (LiveValues.erase(CreateRet(F, 0))) { 730 RetTypes.push_back(RetTy); 731 NewRetIdxs[0] = 0; 732 } else { 733 DEBUG(dbgs() << "DAE - Removing return value from " << F->getName() 734 << "\n"); 735 ++NumRetValsEliminated; 736 } 737 if (RetTypes.size() > 1) 738 // More than one return type? Return a struct with them. Also, if we used 739 // to return a struct and didn't change the number of return values, 740 // return a struct again. This prevents changing {something} into 741 // something and {} into void. 742 // Make the new struct packed if we used to return a packed struct 743 // already. 744 NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); 745 else if (RetTypes.size() == 1) 746 // One return type? Just a simple value then, but only if we didn't use to 747 // return a struct with that simple value before. 748 NRetTy = RetTypes.front(); 749 else if (RetTypes.size() == 0) 750 // No return types? Make it void, but only if we didn't use to return {}. 751 NRetTy = Type::getVoidTy(F->getContext()); 752 } 753 754 assert(NRetTy && "No new return type found?"); 755 756 // The existing function return attributes. 757 AttributeSet RAttrs = PAL.getRetAttributes(); 758 759 // Remove any incompatible attributes, but only if we removed all return 760 // values. Otherwise, ensure that we don't have any conflicting attributes 761 // here. Currently, this should not be possible, but special handling might be 762 // required when new return value attributes are added. 763 if (NRetTy->isVoidTy()) 764 RAttrs = 765 AttributeSet::get(NRetTy->getContext(), AttributeSet::ReturnIndex, 766 AttrBuilder(RAttrs, AttributeSet::ReturnIndex). 767 removeAttributes(AttributeFuncs:: 768 typeIncompatible(NRetTy, AttributeSet::ReturnIndex), 769 AttributeSet::ReturnIndex)); 770 else 771 assert(!AttrBuilder(RAttrs, AttributeSet::ReturnIndex). 772 hasAttributes(AttributeFuncs:: 773 typeIncompatible(NRetTy, AttributeSet::ReturnIndex), 774 AttributeSet::ReturnIndex) && 775 "Return attributes no longer compatible?"); 776 777 if (RAttrs.hasAttributes(AttributeSet::ReturnIndex)) 778 AttributesVec.push_back(AttributeSet::get(NRetTy->getContext(), RAttrs)); 779 780 // Remember which arguments are still alive. 781 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 782 // Construct the new parameter list from non-dead arguments. Also construct 783 // a new set of parameter attributes to correspond. Skip the first parameter 784 // attribute, since that belongs to the return value. 785 unsigned i = 0; 786 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 787 I != E; ++I, ++i) { 788 RetOrArg Arg = CreateArg(F, i); 789 if (LiveValues.erase(Arg)) { 790 Params.push_back(I->getType()); 791 ArgAlive[i] = true; 792 793 // Get the original parameter attributes (skipping the first one, that is 794 // for the return value. 795 if (PAL.hasAttributes(i + 1)) { 796 AttrBuilder B(PAL, i + 1); 797 AttributesVec. 798 push_back(AttributeSet::get(F->getContext(), Params.size(), B)); 799 } 800 } else { 801 ++NumArgumentsEliminated; 802 DEBUG(dbgs() << "DAE - Removing argument " << i << " (" << I->getName() 803 << ") from " << F->getName() << "\n"); 804 } 805 } 806 807 if (PAL.hasAttributes(AttributeSet::FunctionIndex)) 808 AttributesVec.push_back(AttributeSet::get(F->getContext(), 809 PAL.getFnAttributes())); 810 811 // Reconstruct the AttributesList based on the vector we constructed. 812 AttributeSet NewPAL = AttributeSet::get(F->getContext(), AttributesVec); 813 814 // Create the new function type based on the recomputed parameters. 815 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 816 817 // No change? 818 if (NFTy == FTy) 819 return false; 820 821 // Create the new function body and insert it into the module... 822 Function *NF = Function::Create(NFTy, F->getLinkage()); 823 NF->copyAttributesFrom(F); 824 NF->setAttributes(NewPAL); 825 // Insert the new function before the old function, so we won't be processing 826 // it again. 827 F->getParent()->getFunctionList().insert(F, NF); 828 NF->takeName(F); 829 830 // Loop over all of the callers of the function, transforming the call sites 831 // to pass in a smaller number of arguments into the new function. 832 // 833 std::vector<Value*> Args; 834 while (!F->use_empty()) { 835 CallSite CS(F->use_back()); 836 Instruction *Call = CS.getInstruction(); 837 838 AttributesVec.clear(); 839 const AttributeSet &CallPAL = CS.getAttributes(); 840 841 // The call return attributes. 842 AttributeSet RAttrs = CallPAL.getRetAttributes(); 843 844 // Adjust in case the function was changed to return void. 845 RAttrs = 846 AttributeSet::get(NF->getContext(), AttributeSet::ReturnIndex, 847 AttrBuilder(RAttrs, AttributeSet::ReturnIndex). 848 removeAttributes(AttributeFuncs:: 849 typeIncompatible(NF->getReturnType(), 850 AttributeSet::ReturnIndex), 851 AttributeSet::ReturnIndex)); 852 if (RAttrs.hasAttributes(AttributeSet::ReturnIndex)) 853 AttributesVec.push_back(AttributeSet::get(NF->getContext(), RAttrs)); 854 855 // Declare these outside of the loops, so we can reuse them for the second 856 // loop, which loops the varargs. 857 CallSite::arg_iterator I = CS.arg_begin(); 858 unsigned i = 0; 859 // Loop over those operands, corresponding to the normal arguments to the 860 // original function, and add those that are still alive. 861 for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i) 862 if (ArgAlive[i]) { 863 Args.push_back(*I); 864 // Get original parameter attributes, but skip return attributes. 865 if (CallPAL.hasAttributes(i + 1)) { 866 AttrBuilder B(CallPAL, i + 1); 867 AttributesVec. 868 push_back(AttributeSet::get(F->getContext(), Args.size(), B)); 869 } 870 } 871 872 // Push any varargs arguments on the list. Don't forget their attributes. 873 for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { 874 Args.push_back(*I); 875 if (CallPAL.hasAttributes(i + 1)) { 876 AttrBuilder B(CallPAL, i + 1); 877 AttributesVec. 878 push_back(AttributeSet::get(F->getContext(), Args.size(), B)); 879 } 880 } 881 882 if (CallPAL.hasAttributes(AttributeSet::FunctionIndex)) 883 AttributesVec.push_back(AttributeSet::get(Call->getContext(), 884 CallPAL.getFnAttributes())); 885 886 // Reconstruct the AttributesList based on the vector we constructed. 887 AttributeSet NewCallPAL = AttributeSet::get(F->getContext(), AttributesVec); 888 889 Instruction *New; 890 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 891 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 892 Args, "", Call); 893 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 894 cast<InvokeInst>(New)->setAttributes(NewCallPAL); 895 } else { 896 New = CallInst::Create(NF, Args, "", Call); 897 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 898 cast<CallInst>(New)->setAttributes(NewCallPAL); 899 if (cast<CallInst>(Call)->isTailCall()) 900 cast<CallInst>(New)->setTailCall(); 901 } 902 New->setDebugLoc(Call->getDebugLoc()); 903 904 Args.clear(); 905 906 if (!Call->use_empty()) { 907 if (New->getType() == Call->getType()) { 908 // Return type not changed? Just replace users then. 909 Call->replaceAllUsesWith(New); 910 New->takeName(Call); 911 } else if (New->getType()->isVoidTy()) { 912 // Our return value has uses, but they will get removed later on. 913 // Replace by null for now. 914 if (!Call->getType()->isX86_MMXTy()) 915 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); 916 } else { 917 assert(RetTy->isStructTy() && 918 "Return type changed, but not into a void. The old return type" 919 " must have been a struct!"); 920 Instruction *InsertPt = Call; 921 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 922 BasicBlock::iterator IP = II->getNormalDest()->begin(); 923 while (isa<PHINode>(IP)) ++IP; 924 InsertPt = IP; 925 } 926 927 // We used to return a struct. Instead of doing smart stuff with all the 928 // uses of this struct, we will just rebuild it using 929 // extract/insertvalue chaining and let instcombine clean that up. 930 // 931 // Start out building up our return value from undef 932 Value *RetVal = UndefValue::get(RetTy); 933 for (unsigned i = 0; i != RetCount; ++i) 934 if (NewRetIdxs[i] != -1) { 935 Value *V; 936 if (RetTypes.size() > 1) 937 // We are still returning a struct, so extract the value from our 938 // return value 939 V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret", 940 InsertPt); 941 else 942 // We are now returning a single element, so just insert that 943 V = New; 944 // Insert the value at the old position 945 RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt); 946 } 947 // Now, replace all uses of the old call instruction with the return 948 // struct we built 949 Call->replaceAllUsesWith(RetVal); 950 New->takeName(Call); 951 } 952 } 953 954 // Finally, remove the old call from the program, reducing the use-count of 955 // F. 956 Call->eraseFromParent(); 957 } 958 959 // Since we have now created the new function, splice the body of the old 960 // function right into the new function, leaving the old rotting hulk of the 961 // function empty. 962 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 963 964 // Loop over the argument list, transferring uses of the old arguments over to 965 // the new arguments, also transferring over the names as well. 966 i = 0; 967 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 968 I2 = NF->arg_begin(); I != E; ++I, ++i) 969 if (ArgAlive[i]) { 970 // If this is a live argument, move the name and users over to the new 971 // version. 972 I->replaceAllUsesWith(I2); 973 I2->takeName(I); 974 ++I2; 975 } else { 976 // If this argument is dead, replace any uses of it with null constants 977 // (these are guaranteed to become unused later on). 978 if (!I->getType()->isX86_MMXTy()) 979 I->replaceAllUsesWith(Constant::getNullValue(I->getType())); 980 } 981 982 // If we change the return value of the function we must rewrite any return 983 // instructions. Check this now. 984 if (F->getReturnType() != NF->getReturnType()) 985 for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB) 986 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 987 Value *RetVal; 988 989 if (NFTy->getReturnType()->isVoidTy()) { 990 RetVal = 0; 991 } else { 992 assert (RetTy->isStructTy()); 993 // The original return value was a struct, insert 994 // extractvalue/insertvalue chains to extract only the values we need 995 // to return and insert them into our new result. 996 // This does generate messy code, but we'll let it to instcombine to 997 // clean that up. 998 Value *OldRet = RI->getOperand(0); 999 // Start out building up our return value from undef 1000 RetVal = UndefValue::get(NRetTy); 1001 for (unsigned i = 0; i != RetCount; ++i) 1002 if (NewRetIdxs[i] != -1) { 1003 ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i, 1004 "oldret", RI); 1005 if (RetTypes.size() > 1) { 1006 // We're still returning a struct, so reinsert the value into 1007 // our new return value at the new index 1008 1009 RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i], 1010 "newret", RI); 1011 } else { 1012 // We are now only returning a simple value, so just return the 1013 // extracted value. 1014 RetVal = EV; 1015 } 1016 } 1017 } 1018 // Replace the return instruction with one returning the new return 1019 // value (possibly 0 if we became void). 1020 ReturnInst::Create(F->getContext(), RetVal, RI); 1021 BB->getInstList().erase(RI); 1022 } 1023 1024 // Patch the pointer to LLVM function in debug info descriptor. 1025 FunctionDIMap::iterator DI = FunctionDIs.find(F); 1026 if (DI != FunctionDIs.end()) 1027 DI->second.replaceFunction(NF); 1028 1029 // Now that the old function is dead, delete it. 1030 F->eraseFromParent(); 1031 1032 return true; 1033 } 1034 1035 bool DAE::runOnModule(Module &M) { 1036 bool Changed = false; 1037 1038 // Collect debug info descriptors for functions. 1039 CollectFunctionDIs(M); 1040 1041 // First pass: Do a simple check to see if any functions can have their "..." 1042 // removed. We can do this if they never call va_start. This loop cannot be 1043 // fused with the next loop, because deleting a function invalidates 1044 // information computed while surveying other functions. 1045 DEBUG(dbgs() << "DAE - Deleting dead varargs\n"); 1046 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1047 Function &F = *I++; 1048 if (F.getFunctionType()->isVarArg()) 1049 Changed |= DeleteDeadVarargs(F); 1050 } 1051 1052 // Second phase:loop through the module, determining which arguments are live. 1053 // We assume all arguments are dead unless proven otherwise (allowing us to 1054 // determine that dead arguments passed into recursive functions are dead). 1055 // 1056 DEBUG(dbgs() << "DAE - Determining liveness\n"); 1057 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 1058 SurveyFunction(*I); 1059 1060 // Now, remove all dead arguments and return values from each function in 1061 // turn. 1062 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1063 // Increment now, because the function will probably get removed (ie. 1064 // replaced by a new one). 1065 Function *F = I++; 1066 Changed |= RemoveDeadStuffFromFunction(F); 1067 } 1068 1069 // Finally, look for any unused parameters in functions with non-local 1070 // linkage and replace the passed in parameters with undef. 1071 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 1072 Function& F = *I; 1073 1074 Changed |= RemoveDeadArgumentsFromCallers(F); 1075 } 1076 1077 return Changed; 1078 } 1079