1//===- DeadArgumentElimination.cpp - Eliminate dead arguments -------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This pass deletes dead arguments from internal functions. Dead argument 10// elimination removes arguments which are directly dead, as well as arguments 11// only passed into function calls as dead arguments of other functions. This 12// pass also deletes dead return values in a similar way. 13// 14// This pass is often useful as a cleanup pass to run after aggressive 15// interprocedural passes, which add possibly-dead arguments or return values. 16// 17//===----------------------------------------------------------------------===// 18 19#include "llvm/Transforms/IPO/DeadArgumentElimination.h" 20#include "llvm/ADT/SmallVector.h" 21#include "llvm/ADT/Statistic.h" 22#include "llvm/IR/Argument.h" 23#include "llvm/IR/Attributes.h" 24#include "llvm/IR/BasicBlock.h" 25#include "llvm/IR/Constants.h" 26#include "llvm/IR/DerivedTypes.h" 27#include "llvm/IR/Function.h" 28#include "llvm/IR/IRBuilder.h" 29#include "llvm/IR/InstrTypes.h" 30#include "llvm/IR/Instruction.h" 31#include "llvm/IR/Instructions.h" 32#include "llvm/IR/IntrinsicInst.h" 33#include "llvm/IR/Intrinsics.h" 34#include "llvm/IR/Module.h" 35#include "llvm/IR/NoFolder.h" 36#include "llvm/IR/PassManager.h" 37#include "llvm/IR/Type.h" 38#include "llvm/IR/Use.h" 39#include "llvm/IR/User.h" 40#include "llvm/IR/Value.h" 41#include "llvm/InitializePasses.h" 42#include "llvm/Pass.h" 43#include "llvm/Support/Casting.h" 44#include "llvm/Support/Debug.h" 45#include "llvm/Support/raw_ostream.h" 46#include "llvm/Transforms/IPO.h" 47#include "llvm/Transforms/Utils/BasicBlockUtils.h" 48#include <cassert> 49#include <cstdint> 50#include <utility> 51#include <vector> 52 53using namespace llvm; 54 55#define DEBUG_TYPE "deadargelim" 56 57STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 58STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 59STATISTIC(NumArgumentsReplacedWithUndef, 60 "Number of unread args replaced with undef"); 61 62namespace { 63 64 /// DAE - The dead argument elimination pass. 65 class DAE : public ModulePass { 66 protected: 67 // DAH uses this to specify a different ID. 68 explicit DAE(char &ID) : ModulePass(ID) {} 69 70 public: 71 static char ID; // Pass identification, replacement for typeid 72 73 DAE() : ModulePass(ID) { 74 initializeDAEPass(*PassRegistry::getPassRegistry()); 75 } 76 77 bool runOnModule(Module &M) override { 78 if (skipModule(M)) 79 return false; 80 DeadArgumentEliminationPass DAEP(ShouldHackArguments()); 81 ModuleAnalysisManager DummyMAM; 82 PreservedAnalyses PA = DAEP.run(M, DummyMAM); 83 return !PA.areAllPreserved(); 84 } 85 86 virtual bool ShouldHackArguments() const { return false; } 87 }; 88 89} // end anonymous namespace 90 91char DAE::ID = 0; 92 93INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) 94 95namespace { 96 97 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 98 /// deletes arguments to functions which are external. This is only for use 99 /// by bugpoint. 100 struct DAH : public DAE { 101 static char ID; 102 103 DAH() : DAE(ID) {} 104 105 bool ShouldHackArguments() const override { return true; } 106 }; 107 108} // end anonymous namespace 109 110char DAH::ID = 0; 111 112INITIALIZE_PASS(DAH, "deadarghaX0r", 113 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", 114 false, false) 115 116/// createDeadArgEliminationPass - This pass removes arguments from functions 117/// which are not used by the body of the function. 118ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 119 120ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 121 122/// DeleteDeadVarargs - If this is an function that takes a ... list, and if 123/// llvm.vastart is never called, the varargs list is dead for the function. 124bool DeadArgumentEliminationPass::DeleteDeadVarargs(Function &Fn) { 125 assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 126 if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false; 127 128 // Ensure that the function is only directly called. 129 if (Fn.hasAddressTaken()) 130 return false; 131 132 // Don't touch naked functions. The assembly might be using an argument, or 133 // otherwise rely on the frame layout in a way that this analysis will not 134 // see. 135 if (Fn.hasFnAttribute(Attribute::Naked)) { 136 return false; 137 } 138 139 // Okay, we know we can transform this function if safe. Scan its body 140 // looking for calls marked musttail or calls to llvm.vastart. 141 for (BasicBlock &BB : Fn) { 142 for (Instruction &I : BB) { 143 CallInst *CI = dyn_cast<CallInst>(&I); 144 if (!CI) 145 continue; 146 if (CI->isMustTailCall()) 147 return false; 148 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) { 149 if (II->getIntrinsicID() == Intrinsic::vastart) 150 return false; 151 } 152 } 153 } 154 155 // If we get here, there are no calls to llvm.vastart in the function body, 156 // remove the "..." and adjust all the calls. 157 158 // Start by computing a new prototype for the function, which is the same as 159 // the old function, but doesn't have isVarArg set. 160 FunctionType *FTy = Fn.getFunctionType(); 161 162 std::vector<Type *> Params(FTy->param_begin(), FTy->param_end()); 163 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), 164 Params, false); 165 unsigned NumArgs = Params.size(); 166 167 // Create the new function body and insert it into the module... 168 Function *NF = Function::Create(NFTy, Fn.getLinkage(), Fn.getAddressSpace()); 169 NF->copyAttributesFrom(&Fn); 170 NF->setComdat(Fn.getComdat()); 171 Fn.getParent()->getFunctionList().insert(Fn.getIterator(), NF); 172 NF->takeName(&Fn); 173 174 // Loop over all of the callers of the function, transforming the call sites 175 // to pass in a smaller number of arguments into the new function. 176 // 177 std::vector<Value *> Args; 178 for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) { 179 CallBase *CB = dyn_cast<CallBase>(*I++); 180 if (!CB) 181 continue; 182 183 // Pass all the same arguments. 184 Args.assign(CB->arg_begin(), CB->arg_begin() + NumArgs); 185 186 // Drop any attributes that were on the vararg arguments. 187 AttributeList PAL = CB->getAttributes(); 188 if (!PAL.isEmpty()) { 189 SmallVector<AttributeSet, 8> ArgAttrs; 190 for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) 191 ArgAttrs.push_back(PAL.getParamAttributes(ArgNo)); 192 PAL = AttributeList::get(Fn.getContext(), PAL.getFnAttributes(), 193 PAL.getRetAttributes(), ArgAttrs); 194 } 195 196 SmallVector<OperandBundleDef, 1> OpBundles; 197 CB->getOperandBundlesAsDefs(OpBundles); 198 199 CallBase *NewCB = nullptr; 200 if (InvokeInst *II = dyn_cast<InvokeInst>(CB)) { 201 NewCB = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 202 Args, OpBundles, "", CB); 203 } else { 204 NewCB = CallInst::Create(NF, Args, OpBundles, "", CB); 205 cast<CallInst>(NewCB)->setTailCallKind( 206 cast<CallInst>(CB)->getTailCallKind()); 207 } 208 NewCB->setCallingConv(CB->getCallingConv()); 209 NewCB->setAttributes(PAL); 210 NewCB->copyMetadata(*CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg}); 211 212 Args.clear(); 213 214 if (!CB->use_empty()) 215 CB->replaceAllUsesWith(NewCB); 216 217 NewCB->takeName(CB); 218 219 // Finally, remove the old call from the program, reducing the use-count of 220 // F. 221 CB->eraseFromParent(); 222 } 223 224 // Since we have now created the new function, splice the body of the old 225 // function right into the new function, leaving the old rotting hulk of the 226 // function empty. 227 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 228 229 // Loop over the argument list, transferring uses of the old arguments over to 230 // the new arguments, also transferring over the names as well. While we're at 231 // it, remove the dead arguments from the DeadArguments list. 232 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 233 I2 = NF->arg_begin(); I != E; ++I, ++I2) { 234 // Move the name and users over to the new version. 235 I->replaceAllUsesWith(&*I2); 236 I2->takeName(&*I); 237 } 238 239 // Clone metadatas from the old function, including debug info descriptor. 240 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 241 Fn.getAllMetadata(MDs); 242 for (auto MD : MDs) 243 NF->addMetadata(MD.first, *MD.second); 244 245 // Fix up any BlockAddresses that refer to the function. 246 Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType())); 247 // Delete the bitcast that we just created, so that NF does not 248 // appear to be address-taken. 249 NF->removeDeadConstantUsers(); 250 // Finally, nuke the old function. 251 Fn.eraseFromParent(); 252 return true; 253} 254 255/// RemoveDeadArgumentsFromCallers - Checks if the given function has any 256/// arguments that are unused, and changes the caller parameters to be undefined 257/// instead. 258bool DeadArgumentEliminationPass::RemoveDeadArgumentsFromCallers(Function &Fn) { 259 // We cannot change the arguments if this TU does not define the function or 260 // if the linker may choose a function body from another TU, even if the 261 // nominal linkage indicates that other copies of the function have the same 262 // semantics. In the below example, the dead load from %p may not have been 263 // eliminated from the linker-chosen copy of f, so replacing %p with undef 264 // in callers may introduce undefined behavior. 265 // 266 // define linkonce_odr void @f(i32* %p) { 267 // %v = load i32 %p 268 // ret void 269 // } 270 if (!Fn.hasExactDefinition()) 271 return false; 272 273 // Functions with local linkage should already have been handled, except the 274 // fragile (variadic) ones which we can improve here. 275 if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg()) 276 return false; 277 278 // Don't touch naked functions. The assembly might be using an argument, or 279 // otherwise rely on the frame layout in a way that this analysis will not 280 // see. 281 if (Fn.hasFnAttribute(Attribute::Naked)) 282 return false; 283 284 if (Fn.use_empty()) 285 return false; 286 287 SmallVector<unsigned, 8> UnusedArgs; 288 bool Changed = false; 289 290 for (Argument &Arg : Fn.args()) { 291 if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() && 292 !Arg.hasPassPointeeByValueCopyAttr()) { 293 if (Arg.isUsedByMetadata()) { 294 Arg.replaceAllUsesWith(UndefValue::get(Arg.getType())); 295 Changed = true; 296 } 297 UnusedArgs.push_back(Arg.getArgNo()); 298 Fn.removeParamUndefImplyingAttrs(Arg.getArgNo()); 299 } 300 } 301 302 if (UnusedArgs.empty()) 303 return false; 304 305 for (Use &U : Fn.uses()) { 306 CallBase *CB = dyn_cast<CallBase>(U.getUser()); 307 if (!CB || !CB->isCallee(&U)) 308 continue; 309 310 // Now go through all unused args and replace them with "undef". 311 for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { 312 unsigned ArgNo = UnusedArgs[I]; 313 314 Value *Arg = CB->getArgOperand(ArgNo); 315 CB->setArgOperand(ArgNo, UndefValue::get(Arg->getType())); 316 CB->removeParamUndefImplyingAttrs(ArgNo); 317 318 ++NumArgumentsReplacedWithUndef; 319 Changed = true; 320 } 321 } 322 323 return Changed; 324} 325 326/// Convenience function that returns the number of return values. It returns 0 327/// for void functions and 1 for functions not returning a struct. It returns 328/// the number of struct elements for functions returning a struct. 329static unsigned NumRetVals(const Function *F) { 330 Type *RetTy = F->getReturnType(); 331 if (RetTy->isVoidTy()) 332 return 0; 333 else if (StructType *STy = dyn_cast<StructType>(RetTy)) 334 return STy->getNumElements(); 335 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 336 return ATy->getNumElements(); 337 else 338 return 1; 339} 340 341/// Returns the sub-type a function will return at a given Idx. Should 342/// correspond to the result type of an ExtractValue instruction executed with 343/// just that one Idx (i.e. only top-level structure is considered). 344static Type *getRetComponentType(const Function *F, unsigned Idx) { 345 Type *RetTy = F->getReturnType(); 346 assert(!RetTy->isVoidTy() && "void type has no subtype"); 347 348 if (StructType *STy = dyn_cast<StructType>(RetTy)) 349 return STy->getElementType(Idx); 350 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 351 return ATy->getElementType(); 352 else 353 return RetTy; 354} 355 356/// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not 357/// live, it adds Use to the MaybeLiveUses argument. Returns the determined 358/// liveness of Use. 359DeadArgumentEliminationPass::Liveness 360DeadArgumentEliminationPass::MarkIfNotLive(RetOrArg Use, 361 UseVector &MaybeLiveUses) { 362 // We're live if our use or its Function is already marked as live. 363 if (IsLive(Use)) 364 return Live; 365 366 // We're maybe live otherwise, but remember that we must become live if 367 // Use becomes live. 368 MaybeLiveUses.push_back(Use); 369 return MaybeLive; 370} 371 372/// SurveyUse - This looks at a single use of an argument or return value 373/// and determines if it should be alive or not. Adds this use to MaybeLiveUses 374/// if it causes the used value to become MaybeLive. 375/// 376/// RetValNum is the return value number to use when this use is used in a 377/// return instruction. This is used in the recursion, you should always leave 378/// it at 0. 379DeadArgumentEliminationPass::Liveness 380DeadArgumentEliminationPass::SurveyUse(const Use *U, UseVector &MaybeLiveUses, 381 unsigned RetValNum) { 382 const User *V = U->getUser(); 383 if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { 384 // The value is returned from a function. It's only live when the 385 // function's return value is live. We use RetValNum here, for the case 386 // that U is really a use of an insertvalue instruction that uses the 387 // original Use. 388 const Function *F = RI->getParent()->getParent(); 389 if (RetValNum != -1U) { 390 RetOrArg Use = CreateRet(F, RetValNum); 391 // We might be live, depending on the liveness of Use. 392 return MarkIfNotLive(Use, MaybeLiveUses); 393 } else { 394 DeadArgumentEliminationPass::Liveness Result = MaybeLive; 395 for (unsigned Ri = 0; Ri < NumRetVals(F); ++Ri) { 396 RetOrArg Use = CreateRet(F, Ri); 397 // We might be live, depending on the liveness of Use. If any 398 // sub-value is live, then the entire value is considered live. This 399 // is a conservative choice, and better tracking is possible. 400 DeadArgumentEliminationPass::Liveness SubResult = 401 MarkIfNotLive(Use, MaybeLiveUses); 402 if (Result != Live) 403 Result = SubResult; 404 } 405 return Result; 406 } 407 } 408 if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 409 if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex() 410 && IV->hasIndices()) 411 // The use we are examining is inserted into an aggregate. Our liveness 412 // depends on all uses of that aggregate, but if it is used as a return 413 // value, only index at which we were inserted counts. 414 RetValNum = *IV->idx_begin(); 415 416 // Note that if we are used as the aggregate operand to the insertvalue, 417 // we don't change RetValNum, but do survey all our uses. 418 419 Liveness Result = MaybeLive; 420 for (const Use &UU : IV->uses()) { 421 Result = SurveyUse(&UU, MaybeLiveUses, RetValNum); 422 if (Result == Live) 423 break; 424 } 425 return Result; 426 } 427 428 if (const auto *CB = dyn_cast<CallBase>(V)) { 429 const Function *F = CB->getCalledFunction(); 430 if (F) { 431 // Used in a direct call. 432 433 // The function argument is live if it is used as a bundle operand. 434 if (CB->isBundleOperand(U)) 435 return Live; 436 437 // Find the argument number. We know for sure that this use is an 438 // argument, since if it was the function argument this would be an 439 // indirect call and the we know can't be looking at a value of the 440 // label type (for the invoke instruction). 441 unsigned ArgNo = CB->getArgOperandNo(U); 442 443 if (ArgNo >= F->getFunctionType()->getNumParams()) 444 // The value is passed in through a vararg! Must be live. 445 return Live; 446 447 assert(CB->getArgOperand(ArgNo) == CB->getOperand(U->getOperandNo()) && 448 "Argument is not where we expected it"); 449 450 // Value passed to a normal call. It's only live when the corresponding 451 // argument to the called function turns out live. 452 RetOrArg Use = CreateArg(F, ArgNo); 453 return MarkIfNotLive(Use, MaybeLiveUses); 454 } 455 } 456 // Used in any other way? Value must be live. 457 return Live; 458} 459 460/// SurveyUses - This looks at all the uses of the given value 461/// Returns the Liveness deduced from the uses of this value. 462/// 463/// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If 464/// the result is Live, MaybeLiveUses might be modified but its content should 465/// be ignored (since it might not be complete). 466DeadArgumentEliminationPass::Liveness 467DeadArgumentEliminationPass::SurveyUses(const Value *V, 468 UseVector &MaybeLiveUses) { 469 // Assume it's dead (which will only hold if there are no uses at all..). 470 Liveness Result = MaybeLive; 471 // Check each use. 472 for (const Use &U : V->uses()) { 473 Result = SurveyUse(&U, MaybeLiveUses); 474 if (Result == Live) 475 break; 476 } 477 return Result; 478} 479 480// SurveyFunction - This performs the initial survey of the specified function, 481// checking out whether or not it uses any of its incoming arguments or whether 482// any callers use the return value. This fills in the LiveValues set and Uses 483// map. 484// 485// We consider arguments of non-internal functions to be intrinsically alive as 486// well as arguments to functions which have their "address taken". 487void DeadArgumentEliminationPass::SurveyFunction(const Function &F) { 488 // Functions with inalloca/preallocated parameters are expecting args in a 489 // particular register and memory layout. 490 if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) || 491 F.getAttributes().hasAttrSomewhere(Attribute::Preallocated)) { 492 MarkLive(F); 493 return; 494 } 495 496 // Don't touch naked functions. The assembly might be using an argument, or 497 // otherwise rely on the frame layout in a way that this analysis will not 498 // see. 499 if (F.hasFnAttribute(Attribute::Naked)) { 500 MarkLive(F); 501 return; 502 } 503 504 unsigned RetCount = NumRetVals(&F); 505 506 // Assume all return values are dead 507 using RetVals = SmallVector<Liveness, 5>; 508 509 RetVals RetValLiveness(RetCount, MaybeLive); 510 511 using RetUses = SmallVector<UseVector, 5>; 512 513 // These vectors map each return value to the uses that make it MaybeLive, so 514 // we can add those to the Uses map if the return value really turns out to be 515 // MaybeLive. Initialized to a list of RetCount empty lists. 516 RetUses MaybeLiveRetUses(RetCount); 517 518 bool HasMustTailCalls = false; 519 520 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 521 if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 522 if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 523 != F.getFunctionType()->getReturnType()) { 524 // We don't support old style multiple return values. 525 MarkLive(F); 526 return; 527 } 528 } 529 530 // If we have any returns of `musttail` results - the signature can't 531 // change 532 if (BB->getTerminatingMustTailCall() != nullptr) 533 HasMustTailCalls = true; 534 } 535 536 if (HasMustTailCalls) { 537 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 538 << " has musttail calls\n"); 539 } 540 541 if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { 542 MarkLive(F); 543 return; 544 } 545 546 LLVM_DEBUG( 547 dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: " 548 << F.getName() << "\n"); 549 // Keep track of the number of live retvals, so we can skip checks once all 550 // of them turn out to be live. 551 unsigned NumLiveRetVals = 0; 552 553 bool HasMustTailCallers = false; 554 555 // Loop all uses of the function. 556 for (const Use &U : F.uses()) { 557 // If the function is PASSED IN as an argument, its address has been 558 // taken. 559 const auto *CB = dyn_cast<CallBase>(U.getUser()); 560 if (!CB || !CB->isCallee(&U)) { 561 MarkLive(F); 562 return; 563 } 564 565 // The number of arguments for `musttail` call must match the number of 566 // arguments of the caller 567 if (CB->isMustTailCall()) 568 HasMustTailCallers = true; 569 570 // If we end up here, we are looking at a direct call to our function. 571 572 // Now, check how our return value(s) is/are used in this caller. Don't 573 // bother checking return values if all of them are live already. 574 if (NumLiveRetVals == RetCount) 575 continue; 576 577 // Check all uses of the return value. 578 for (const Use &U : CB->uses()) { 579 if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) { 580 // This use uses a part of our return value, survey the uses of 581 // that part and store the results for this index only. 582 unsigned Idx = *Ext->idx_begin(); 583 if (RetValLiveness[Idx] != Live) { 584 RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 585 if (RetValLiveness[Idx] == Live) 586 NumLiveRetVals++; 587 } 588 } else { 589 // Used by something else than extractvalue. Survey, but assume that the 590 // result applies to all sub-values. 591 UseVector MaybeLiveAggregateUses; 592 if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) { 593 NumLiveRetVals = RetCount; 594 RetValLiveness.assign(RetCount, Live); 595 break; 596 } else { 597 for (unsigned Ri = 0; Ri != RetCount; ++Ri) { 598 if (RetValLiveness[Ri] != Live) 599 MaybeLiveRetUses[Ri].append(MaybeLiveAggregateUses.begin(), 600 MaybeLiveAggregateUses.end()); 601 } 602 } 603 } 604 } 605 } 606 607 if (HasMustTailCallers) { 608 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 609 << " has musttail callers\n"); 610 } 611 612 // Now we've inspected all callers, record the liveness of our return values. 613 for (unsigned Ri = 0; Ri != RetCount; ++Ri) 614 MarkValue(CreateRet(&F, Ri), RetValLiveness[Ri], MaybeLiveRetUses[Ri]); 615 616 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: " 617 << F.getName() << "\n"); 618 619 // Now, check all of our arguments. 620 unsigned ArgI = 0; 621 UseVector MaybeLiveArgUses; 622 for (Function::const_arg_iterator AI = F.arg_begin(), E = F.arg_end(); 623 AI != E; ++AI, ++ArgI) { 624 Liveness Result; 625 if (F.getFunctionType()->isVarArg() || HasMustTailCallers || 626 HasMustTailCalls) { 627 // Variadic functions will already have a va_arg function expanded inside 628 // them, making them potentially very sensitive to ABI changes resulting 629 // from removing arguments entirely, so don't. For example AArch64 handles 630 // register and stack HFAs very differently, and this is reflected in the 631 // IR which has already been generated. 632 // 633 // `musttail` calls to this function restrict argument removal attempts. 634 // The signature of the caller must match the signature of the function. 635 // 636 // `musttail` calls in this function prevents us from changing its 637 // signature 638 Result = Live; 639 } else { 640 // See what the effect of this use is (recording any uses that cause 641 // MaybeLive in MaybeLiveArgUses). 642 Result = SurveyUses(&*AI, MaybeLiveArgUses); 643 } 644 645 // Mark the result. 646 MarkValue(CreateArg(&F, ArgI), Result, MaybeLiveArgUses); 647 // Clear the vector again for the next iteration. 648 MaybeLiveArgUses.clear(); 649 } 650} 651 652/// MarkValue - This function marks the liveness of RA depending on L. If L is 653/// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, 654/// such that RA will be marked live if any use in MaybeLiveUses gets marked 655/// live later on. 656void DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L, 657 const UseVector &MaybeLiveUses) { 658 switch (L) { 659 case Live: 660 MarkLive(RA); 661 break; 662 case MaybeLive: 663 assert(!IsLive(RA) && "Use is already live!"); 664 for (const auto &MaybeLiveUse : MaybeLiveUses) { 665 if (IsLive(MaybeLiveUse)) { 666 // A use is live, so this value is live. 667 MarkLive(RA); 668 break; 669 } else { 670 // Note any uses of this value, so this value can be 671 // marked live whenever one of the uses becomes live. 672 Uses.insert(std::make_pair(MaybeLiveUse, RA)); 673 } 674 } 675 break; 676 } 677} 678 679/// MarkLive - Mark the given Function as alive, meaning that it cannot be 680/// changed in any way. Additionally, 681/// mark any values that are used as this function's parameters or by its return 682/// values (according to Uses) live as well. 683void DeadArgumentEliminationPass::MarkLive(const Function &F) { 684 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: " 685 << F.getName() << "\n"); 686 // Mark the function as live. 687 LiveFunctions.insert(&F); 688 // Mark all arguments as live. 689 for (unsigned ArgI = 0, E = F.arg_size(); ArgI != E; ++ArgI) 690 PropagateLiveness(CreateArg(&F, ArgI)); 691 // Mark all return values as live. 692 for (unsigned Ri = 0, E = NumRetVals(&F); Ri != E; ++Ri) 693 PropagateLiveness(CreateRet(&F, Ri)); 694} 695 696/// MarkLive - Mark the given return value or argument as live. Additionally, 697/// mark any values that are used by this value (according to Uses) live as 698/// well. 699void DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) { 700 if (IsLive(RA)) 701 return; // Already marked Live. 702 703 LiveValues.insert(RA); 704 705 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking " 706 << RA.getDescription() << " live\n"); 707 PropagateLiveness(RA); 708} 709 710bool DeadArgumentEliminationPass::IsLive(const RetOrArg &RA) { 711 return LiveFunctions.count(RA.F) || LiveValues.count(RA); 712} 713 714/// PropagateLiveness - Given that RA is a live value, propagate it's liveness 715/// to any other values it uses (according to Uses). 716void DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) { 717 // We don't use upper_bound (or equal_range) here, because our recursive call 718 // to ourselves is likely to cause the upper_bound (which is the first value 719 // not belonging to RA) to become erased and the iterator invalidated. 720 UseMap::iterator Begin = Uses.lower_bound(RA); 721 UseMap::iterator E = Uses.end(); 722 UseMap::iterator I; 723 for (I = Begin; I != E && I->first == RA; ++I) 724 MarkLive(I->second); 725 726 // Erase RA from the Uses map (from the lower bound to wherever we ended up 727 // after the loop). 728 Uses.erase(Begin, I); 729} 730 731// RemoveDeadStuffFromFunction - Remove any arguments and return values from F 732// that are not in LiveValues. Transform the function and all of the callees of 733// the function to not have these arguments and return values. 734// 735bool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) { 736 // Don't modify fully live functions 737 if (LiveFunctions.count(F)) 738 return false; 739 740 // Start by computing a new prototype for the function, which is the same as 741 // the old function, but has fewer arguments and a different return type. 742 FunctionType *FTy = F->getFunctionType(); 743 std::vector<Type*> Params; 744 745 // Keep track of if we have a live 'returned' argument 746 bool HasLiveReturnedArg = false; 747 748 // Set up to build a new list of parameter attributes. 749 SmallVector<AttributeSet, 8> ArgAttrVec; 750 const AttributeList &PAL = F->getAttributes(); 751 752 // Remember which arguments are still alive. 753 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 754 // Construct the new parameter list from non-dead arguments. Also construct 755 // a new set of parameter attributes to correspond. Skip the first parameter 756 // attribute, since that belongs to the return value. 757 unsigned ArgI = 0; 758 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 759 ++I, ++ArgI) { 760 RetOrArg Arg = CreateArg(F, ArgI); 761 if (LiveValues.erase(Arg)) { 762 Params.push_back(I->getType()); 763 ArgAlive[ArgI] = true; 764 ArgAttrVec.push_back(PAL.getParamAttributes(ArgI)); 765 HasLiveReturnedArg |= PAL.hasParamAttribute(ArgI, Attribute::Returned); 766 } else { 767 ++NumArgumentsEliminated; 768 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument " 769 << ArgI << " (" << I->getName() << ") from " 770 << F->getName() << "\n"); 771 } 772 } 773 774 // Find out the new return value. 775 Type *RetTy = FTy->getReturnType(); 776 Type *NRetTy = nullptr; 777 unsigned RetCount = NumRetVals(F); 778 779 // -1 means unused, other numbers are the new index 780 SmallVector<int, 5> NewRetIdxs(RetCount, -1); 781 std::vector<Type*> RetTypes; 782 783 // If there is a function with a live 'returned' argument but a dead return 784 // value, then there are two possible actions: 785 // 1) Eliminate the return value and take off the 'returned' attribute on the 786 // argument. 787 // 2) Retain the 'returned' attribute and treat the return value (but not the 788 // entire function) as live so that it is not eliminated. 789 // 790 // It's not clear in the general case which option is more profitable because, 791 // even in the absence of explicit uses of the return value, code generation 792 // is free to use the 'returned' attribute to do things like eliding 793 // save/restores of registers across calls. Whether or not this happens is 794 // target and ABI-specific as well as depending on the amount of register 795 // pressure, so there's no good way for an IR-level pass to figure this out. 796 // 797 // Fortunately, the only places where 'returned' is currently generated by 798 // the FE are places where 'returned' is basically free and almost always a 799 // performance win, so the second option can just be used always for now. 800 // 801 // This should be revisited if 'returned' is ever applied more liberally. 802 if (RetTy->isVoidTy() || HasLiveReturnedArg) { 803 NRetTy = RetTy; 804 } else { 805 // Look at each of the original return values individually. 806 for (unsigned Ri = 0; Ri != RetCount; ++Ri) { 807 RetOrArg Ret = CreateRet(F, Ri); 808 if (LiveValues.erase(Ret)) { 809 RetTypes.push_back(getRetComponentType(F, Ri)); 810 NewRetIdxs[Ri] = RetTypes.size() - 1; 811 } else { 812 ++NumRetValsEliminated; 813 LLVM_DEBUG( 814 dbgs() << "DeadArgumentEliminationPass - Removing return value " 815 << Ri << " from " << F->getName() << "\n"); 816 } 817 } 818 if (RetTypes.size() > 1) { 819 // More than one return type? Reduce it down to size. 820 if (StructType *STy = dyn_cast<StructType>(RetTy)) { 821 // Make the new struct packed if we used to return a packed struct 822 // already. 823 NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); 824 } else { 825 assert(isa<ArrayType>(RetTy) && "unexpected multi-value return"); 826 NRetTy = ArrayType::get(RetTypes[0], RetTypes.size()); 827 } 828 } else if (RetTypes.size() == 1) 829 // One return type? Just a simple value then, but only if we didn't use to 830 // return a struct with that simple value before. 831 NRetTy = RetTypes.front(); 832 else if (RetTypes.empty()) 833 // No return types? Make it void, but only if we didn't use to return {}. 834 NRetTy = Type::getVoidTy(F->getContext()); 835 } 836 837 assert(NRetTy && "No new return type found?"); 838 839 // The existing function return attributes. 840 AttrBuilder RAttrs(PAL.getRetAttributes()); 841 842 // Remove any incompatible attributes, but only if we removed all return 843 // values. Otherwise, ensure that we don't have any conflicting attributes 844 // here. Currently, this should not be possible, but special handling might be 845 // required when new return value attributes are added. 846 if (NRetTy->isVoidTy()) 847 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 848 else 849 assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) && 850 "Return attributes no longer compatible?"); 851 852 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 853 854 // Strip allocsize attributes. They might refer to the deleted arguments. 855 AttributeSet FnAttrs = PAL.getFnAttributes().removeAttribute( 856 F->getContext(), Attribute::AllocSize); 857 858 // Reconstruct the AttributesList based on the vector we constructed. 859 assert(ArgAttrVec.size() == Params.size()); 860 AttributeList NewPAL = 861 AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 862 863 // Create the new function type based on the recomputed parameters. 864 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 865 866 // No change? 867 if (NFTy == FTy) 868 return false; 869 870 // Create the new function body and insert it into the module... 871 Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace()); 872 NF->copyAttributesFrom(F); 873 NF->setComdat(F->getComdat()); 874 NF->setAttributes(NewPAL); 875 // Insert the new function before the old function, so we won't be processing 876 // it again. 877 F->getParent()->getFunctionList().insert(F->getIterator(), NF); 878 NF->takeName(F); 879 880 // Loop over all of the callers of the function, transforming the call sites 881 // to pass in a smaller number of arguments into the new function. 882 std::vector<Value*> Args; 883 while (!F->use_empty()) { 884 CallBase &CB = cast<CallBase>(*F->user_back()); 885 886 ArgAttrVec.clear(); 887 const AttributeList &CallPAL = CB.getAttributes(); 888 889 // Adjust the call return attributes in case the function was changed to 890 // return void. 891 AttrBuilder RAttrs(CallPAL.getRetAttributes()); 892 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 893 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 894 895 // Declare these outside of the loops, so we can reuse them for the second 896 // loop, which loops the varargs. 897 auto I = CB.arg_begin(); 898 unsigned Pi = 0; 899 // Loop over those operands, corresponding to the normal arguments to the 900 // original function, and add those that are still alive. 901 for (unsigned E = FTy->getNumParams(); Pi != E; ++I, ++Pi) 902 if (ArgAlive[Pi]) { 903 Args.push_back(*I); 904 // Get original parameter attributes, but skip return attributes. 905 AttributeSet Attrs = CallPAL.getParamAttributes(Pi); 906 if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) { 907 // If the return type has changed, then get rid of 'returned' on the 908 // call site. The alternative is to make all 'returned' attributes on 909 // call sites keep the return value alive just like 'returned' 910 // attributes on function declaration but it's less clearly a win and 911 // this is not an expected case anyway 912 ArgAttrVec.push_back(AttributeSet::get( 913 F->getContext(), 914 AttrBuilder(Attrs).removeAttribute(Attribute::Returned))); 915 } else { 916 // Otherwise, use the original attributes. 917 ArgAttrVec.push_back(Attrs); 918 } 919 } 920 921 // Push any varargs arguments on the list. Don't forget their attributes. 922 for (auto E = CB.arg_end(); I != E; ++I, ++Pi) { 923 Args.push_back(*I); 924 ArgAttrVec.push_back(CallPAL.getParamAttributes(Pi)); 925 } 926 927 // Reconstruct the AttributesList based on the vector we constructed. 928 assert(ArgAttrVec.size() == Args.size()); 929 930 // Again, be sure to remove any allocsize attributes, since their indices 931 // may now be incorrect. 932 AttributeSet FnAttrs = CallPAL.getFnAttributes().removeAttribute( 933 F->getContext(), Attribute::AllocSize); 934 935 AttributeList NewCallPAL = AttributeList::get( 936 F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 937 938 SmallVector<OperandBundleDef, 1> OpBundles; 939 CB.getOperandBundlesAsDefs(OpBundles); 940 941 CallBase *NewCB = nullptr; 942 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { 943 NewCB = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 944 Args, OpBundles, "", CB.getParent()); 945 } else { 946 NewCB = CallInst::Create(NFTy, NF, Args, OpBundles, "", &CB); 947 cast<CallInst>(NewCB)->setTailCallKind( 948 cast<CallInst>(&CB)->getTailCallKind()); 949 } 950 NewCB->setCallingConv(CB.getCallingConv()); 951 NewCB->setAttributes(NewCallPAL); 952 NewCB->copyMetadata(CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg}); 953 Args.clear(); 954 ArgAttrVec.clear(); 955 956 if (!CB.use_empty() || CB.isUsedByMetadata()) { 957 if (NewCB->getType() == CB.getType()) { 958 // Return type not changed? Just replace users then. 959 CB.replaceAllUsesWith(NewCB); 960 NewCB->takeName(&CB); 961 } else if (NewCB->getType()->isVoidTy()) { 962 // If the return value is dead, replace any uses of it with undef 963 // (any non-debug value uses will get removed later on). 964 if (!CB.getType()->isX86_MMXTy()) 965 CB.replaceAllUsesWith(UndefValue::get(CB.getType())); 966 } else { 967 assert((RetTy->isStructTy() || RetTy->isArrayTy()) && 968 "Return type changed, but not into a void. The old return type" 969 " must have been a struct or an array!"); 970 Instruction *InsertPt = &CB; 971 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { 972 BasicBlock *NewEdge = 973 SplitEdge(NewCB->getParent(), II->getNormalDest()); 974 InsertPt = &*NewEdge->getFirstInsertionPt(); 975 } 976 977 // We used to return a struct or array. Instead of doing smart stuff 978 // with all the uses, we will just rebuild it using extract/insertvalue 979 // chaining and let instcombine clean that up. 980 // 981 // Start out building up our return value from undef 982 Value *RetVal = UndefValue::get(RetTy); 983 for (unsigned Ri = 0; Ri != RetCount; ++Ri) 984 if (NewRetIdxs[Ri] != -1) { 985 Value *V; 986 IRBuilder<NoFolder> IRB(InsertPt); 987 if (RetTypes.size() > 1) 988 // We are still returning a struct, so extract the value from our 989 // return value 990 V = IRB.CreateExtractValue(NewCB, NewRetIdxs[Ri], "newret"); 991 else 992 // We are now returning a single element, so just insert that 993 V = NewCB; 994 // Insert the value at the old position 995 RetVal = IRB.CreateInsertValue(RetVal, V, Ri, "oldret"); 996 } 997 // Now, replace all uses of the old call instruction with the return 998 // struct we built 999 CB.replaceAllUsesWith(RetVal); 1000 NewCB->takeName(&CB); 1001 } 1002 } 1003 1004 // Finally, remove the old call from the program, reducing the use-count of 1005 // F. 1006 CB.eraseFromParent(); 1007 } 1008 1009 // Since we have now created the new function, splice the body of the old 1010 // function right into the new function, leaving the old rotting hulk of the 1011 // function empty. 1012 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 1013 1014 // Loop over the argument list, transferring uses of the old arguments over to 1015 // the new arguments, also transferring over the names as well. 1016 ArgI = 0; 1017 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 1018 I2 = NF->arg_begin(); 1019 I != E; ++I, ++ArgI) 1020 if (ArgAlive[ArgI]) { 1021 // If this is a live argument, move the name and users over to the new 1022 // version. 1023 I->replaceAllUsesWith(&*I2); 1024 I2->takeName(&*I); 1025 ++I2; 1026 } else { 1027 // If this argument is dead, replace any uses of it with undef 1028 // (any non-debug value uses will get removed later on). 1029 if (!I->getType()->isX86_MMXTy()) 1030 I->replaceAllUsesWith(UndefValue::get(I->getType())); 1031 } 1032 1033 // If we change the return value of the function we must rewrite any return 1034 // instructions. Check this now. 1035 if (F->getReturnType() != NF->getReturnType()) 1036 for (BasicBlock &BB : *NF) 1037 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) { 1038 IRBuilder<NoFolder> IRB(RI); 1039 Value *RetVal = nullptr; 1040 1041 if (!NFTy->getReturnType()->isVoidTy()) { 1042 assert(RetTy->isStructTy() || RetTy->isArrayTy()); 1043 // The original return value was a struct or array, insert 1044 // extractvalue/insertvalue chains to extract only the values we need 1045 // to return and insert them into our new result. 1046 // This does generate messy code, but we'll let it to instcombine to 1047 // clean that up. 1048 Value *OldRet = RI->getOperand(0); 1049 // Start out building up our return value from undef 1050 RetVal = UndefValue::get(NRetTy); 1051 for (unsigned RetI = 0; RetI != RetCount; ++RetI) 1052 if (NewRetIdxs[RetI] != -1) { 1053 Value *EV = IRB.CreateExtractValue(OldRet, RetI, "oldret"); 1054 1055 if (RetTypes.size() > 1) { 1056 // We're still returning a struct, so reinsert the value into 1057 // our new return value at the new index 1058 1059 RetVal = IRB.CreateInsertValue(RetVal, EV, NewRetIdxs[RetI], 1060 "newret"); 1061 } else { 1062 // We are now only returning a simple value, so just return the 1063 // extracted value. 1064 RetVal = EV; 1065 } 1066 } 1067 } 1068 // Replace the return instruction with one returning the new return 1069 // value (possibly 0 if we became void). 1070 auto *NewRet = ReturnInst::Create(F->getContext(), RetVal, RI); 1071 NewRet->setDebugLoc(RI->getDebugLoc()); 1072 BB.getInstList().erase(RI); 1073 } 1074 1075 // Clone metadatas from the old function, including debug info descriptor. 1076 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 1077 F->getAllMetadata(MDs); 1078 for (auto MD : MDs) 1079 NF->addMetadata(MD.first, *MD.second); 1080 1081 // Now that the old function is dead, delete it. 1082 F->eraseFromParent(); 1083 1084 return true; 1085} 1086 1087PreservedAnalyses DeadArgumentEliminationPass::run(Module &M, 1088 ModuleAnalysisManager &) { 1089 bool Changed = false; 1090 1091 // First pass: Do a simple check to see if any functions can have their "..." 1092 // removed. We can do this if they never call va_start. This loop cannot be 1093 // fused with the next loop, because deleting a function invalidates 1094 // information computed while surveying other functions. 1095 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n"); 1096 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1097 Function &F = *I++; 1098 if (F.getFunctionType()->isVarArg()) 1099 Changed |= DeleteDeadVarargs(F); 1100 } 1101 1102 // Second phase:loop through the module, determining which arguments are live. 1103 // We assume all arguments are dead unless proven otherwise (allowing us to 1104 // determine that dead arguments passed into recursive functions are dead). 1105 // 1106 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n"); 1107 for (auto &F : M) 1108 SurveyFunction(F); 1109 1110 // Now, remove all dead arguments and return values from each function in 1111 // turn. 1112 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1113 // Increment now, because the function will probably get removed (ie. 1114 // replaced by a new one). 1115 Function *F = &*I++; 1116 Changed |= RemoveDeadStuffFromFunction(F); 1117 } 1118 1119 // Finally, look for any unused parameters in functions with non-local 1120 // linkage and replace the passed in parameters with undef. 1121 for (auto &F : M) 1122 Changed |= RemoveDeadArgumentsFromCallers(F); 1123 1124 if (!Changed) 1125 return PreservedAnalyses::all(); 1126 return PreservedAnalyses::none(); 1127} 1128