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