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 53 using namespace llvm; 54 55 #define DEBUG_TYPE "deadargelim" 56 57 STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 58 STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 59 STATISTIC(NumArgumentsReplacedWithUndef, 60 "Number of unread args replaced with undef"); 61 62 namespace { 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 91 char DAE::ID = 0; 92 93 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) 94 95 namespace { 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 110 char DAH::ID = 0; 111 112 INITIALIZE_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. 118 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 119 120 ModulePass *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. 124 bool 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. 258 bool 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 AttrBuilder UBImplyingAttributes = AttributeFuncs::getUBImplyingAttributes(); 291 for (Argument &Arg : Fn.args()) { 292 if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() && 293 !Arg.hasPassPointeeByValueCopyAttr()) { 294 if (Arg.isUsedByMetadata()) { 295 Arg.replaceAllUsesWith(UndefValue::get(Arg.getType())); 296 Changed = true; 297 } 298 UnusedArgs.push_back(Arg.getArgNo()); 299 Fn.removeParamAttrs(Arg.getArgNo(), UBImplyingAttributes); 300 } 301 } 302 303 if (UnusedArgs.empty()) 304 return false; 305 306 for (Use &U : Fn.uses()) { 307 CallBase *CB = dyn_cast<CallBase>(U.getUser()); 308 if (!CB || !CB->isCallee(&U)) 309 continue; 310 311 // Now go through all unused args and replace them with "undef". 312 for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { 313 unsigned ArgNo = UnusedArgs[I]; 314 315 Value *Arg = CB->getArgOperand(ArgNo); 316 CB->setArgOperand(ArgNo, UndefValue::get(Arg->getType())); 317 CB->removeParamAttrs(ArgNo, UBImplyingAttributes); 318 319 ++NumArgumentsReplacedWithUndef; 320 Changed = true; 321 } 322 } 323 324 return Changed; 325 } 326 327 /// Convenience function that returns the number of return values. It returns 0 328 /// for void functions and 1 for functions not returning a struct. It returns 329 /// the number of struct elements for functions returning a struct. 330 static unsigned NumRetVals(const Function *F) { 331 Type *RetTy = F->getReturnType(); 332 if (RetTy->isVoidTy()) 333 return 0; 334 else if (StructType *STy = dyn_cast<StructType>(RetTy)) 335 return STy->getNumElements(); 336 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 337 return ATy->getNumElements(); 338 else 339 return 1; 340 } 341 342 /// Returns the sub-type a function will return at a given Idx. Should 343 /// correspond to the result type of an ExtractValue instruction executed with 344 /// just that one Idx (i.e. only top-level structure is considered). 345 static Type *getRetComponentType(const Function *F, unsigned Idx) { 346 Type *RetTy = F->getReturnType(); 347 assert(!RetTy->isVoidTy() && "void type has no subtype"); 348 349 if (StructType *STy = dyn_cast<StructType>(RetTy)) 350 return STy->getElementType(Idx); 351 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 352 return ATy->getElementType(); 353 else 354 return RetTy; 355 } 356 357 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not 358 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined 359 /// 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 /// SurveyUse - This looks at a single use of an argument or return value 374 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses 375 /// if it causes the 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 } else { 395 DeadArgumentEliminationPass::Liveness Result = MaybeLive; 396 for (unsigned Ri = 0; Ri < NumRetVals(F); ++Ri) { 397 RetOrArg Use = CreateRet(F, Ri); 398 // We might be live, depending on the liveness of Use. If any 399 // sub-value is live, then the entire value is considered live. This 400 // is a conservative choice, and better tracking is possible. 401 DeadArgumentEliminationPass::Liveness SubResult = 402 MarkIfNotLive(Use, MaybeLiveUses); 403 if (Result != Live) 404 Result = SubResult; 405 } 406 return Result; 407 } 408 } 409 if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 410 if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex() 411 && IV->hasIndices()) 412 // The use we are examining is inserted into an aggregate. Our liveness 413 // depends on all uses of that aggregate, but if it is used as a return 414 // value, only index at which we were inserted counts. 415 RetValNum = *IV->idx_begin(); 416 417 // Note that if we are used as the aggregate operand to the insertvalue, 418 // we don't change RetValNum, but do survey all our uses. 419 420 Liveness Result = MaybeLive; 421 for (const Use &UU : IV->uses()) { 422 Result = SurveyUse(&UU, MaybeLiveUses, RetValNum); 423 if (Result == Live) 424 break; 425 } 426 return Result; 427 } 428 429 if (const auto *CB = dyn_cast<CallBase>(V)) { 430 const Function *F = CB->getCalledFunction(); 431 if (F) { 432 // Used in a direct call. 433 434 // The function argument is live if it is used as a bundle operand. 435 if (CB->isBundleOperand(U)) 436 return Live; 437 438 // Find the argument number. We know for sure that this use is an 439 // argument, since if it was the function argument this would be an 440 // indirect call and the we know can't be looking at a value of the 441 // label type (for the invoke instruction). 442 unsigned ArgNo = CB->getArgOperandNo(U); 443 444 if (ArgNo >= F->getFunctionType()->getNumParams()) 445 // The value is passed in through a vararg! Must be live. 446 return Live; 447 448 assert(CB->getArgOperand(ArgNo) == CB->getOperand(U->getOperandNo()) && 449 "Argument is not where we expected it"); 450 451 // Value passed to a normal call. It's only live when the corresponding 452 // argument to the called function turns out live. 453 RetOrArg Use = CreateArg(F, ArgNo); 454 return MarkIfNotLive(Use, MaybeLiveUses); 455 } 456 } 457 // Used in any other way? Value must be live. 458 return Live; 459 } 460 461 /// SurveyUses - This looks at all the uses of the given value 462 /// Returns the Liveness deduced from the uses of this value. 463 /// 464 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If 465 /// the result is Live, MaybeLiveUses might be modified but its content should 466 /// be ignored (since it might not be complete). 467 DeadArgumentEliminationPass::Liveness 468 DeadArgumentEliminationPass::SurveyUses(const Value *V, 469 UseVector &MaybeLiveUses) { 470 // Assume it's dead (which will only hold if there are no uses at all..). 471 Liveness Result = MaybeLive; 472 // Check each use. 473 for (const Use &U : V->uses()) { 474 Result = SurveyUse(&U, MaybeLiveUses); 475 if (Result == Live) 476 break; 477 } 478 return Result; 479 } 480 481 // SurveyFunction - This performs the initial survey of the specified function, 482 // checking out whether or not it uses any of its incoming arguments or whether 483 // any callers use the return value. This fills in the LiveValues set and Uses 484 // 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 521 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 522 if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 523 if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 524 != F.getFunctionType()->getReturnType()) { 525 // We don't support old style multiple return values. 526 MarkLive(F); 527 return; 528 } 529 } 530 531 // If we have any returns of `musttail` results - the signature can't 532 // change 533 if (BB->getTerminatingMustTailCall() != nullptr) 534 HasMustTailCalls = true; 535 } 536 537 if (HasMustTailCalls) { 538 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 539 << " has musttail calls\n"); 540 } 541 542 if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { 543 MarkLive(F); 544 return; 545 } 546 547 LLVM_DEBUG( 548 dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: " 549 << F.getName() << "\n"); 550 // Keep track of the number of live retvals, so we can skip checks once all 551 // of them turn out to be live. 552 unsigned NumLiveRetVals = 0; 553 554 bool HasMustTailCallers = false; 555 556 // Loop all uses of the function. 557 for (const Use &U : F.uses()) { 558 // If the function is PASSED IN as an argument, its address has been 559 // taken. 560 const auto *CB = dyn_cast<CallBase>(U.getUser()); 561 if (!CB || !CB->isCallee(&U)) { 562 MarkLive(F); 563 return; 564 } 565 566 // The number of arguments for `musttail` call must match the number of 567 // arguments of the caller 568 if (CB->isMustTailCall()) 569 HasMustTailCallers = true; 570 571 // If we end up here, we are looking at a direct call to our function. 572 573 // Now, check how our return value(s) is/are used in this caller. Don't 574 // bother checking return values if all of them are live already. 575 if (NumLiveRetVals == RetCount) 576 continue; 577 578 // Check all uses of the return value. 579 for (const Use &U : CB->uses()) { 580 if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) { 581 // This use uses a part of our return value, survey the uses of 582 // that part and store the results for this index only. 583 unsigned Idx = *Ext->idx_begin(); 584 if (RetValLiveness[Idx] != Live) { 585 RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 586 if (RetValLiveness[Idx] == Live) 587 NumLiveRetVals++; 588 } 589 } else { 590 // Used by something else than extractvalue. Survey, but assume that the 591 // result applies to all sub-values. 592 UseVector MaybeLiveAggregateUses; 593 if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) { 594 NumLiveRetVals = RetCount; 595 RetValLiveness.assign(RetCount, Live); 596 break; 597 } else { 598 for (unsigned Ri = 0; Ri != RetCount; ++Ri) { 599 if (RetValLiveness[Ri] != Live) 600 MaybeLiveRetUses[Ri].append(MaybeLiveAggregateUses.begin(), 601 MaybeLiveAggregateUses.end()); 602 } 603 } 604 } 605 } 606 } 607 608 if (HasMustTailCallers) { 609 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 610 << " has musttail callers\n"); 611 } 612 613 // Now we've inspected all callers, record the liveness of our return values. 614 for (unsigned Ri = 0; Ri != RetCount; ++Ri) 615 MarkValue(CreateRet(&F, Ri), RetValLiveness[Ri], MaybeLiveRetUses[Ri]); 616 617 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: " 618 << F.getName() << "\n"); 619 620 // Now, check all of our arguments. 621 unsigned ArgI = 0; 622 UseVector MaybeLiveArgUses; 623 for (Function::const_arg_iterator AI = F.arg_begin(), E = F.arg_end(); 624 AI != E; ++AI, ++ArgI) { 625 Liveness Result; 626 if (F.getFunctionType()->isVarArg() || HasMustTailCallers || 627 HasMustTailCalls) { 628 // Variadic functions will already have a va_arg function expanded inside 629 // them, making them potentially very sensitive to ABI changes resulting 630 // from removing arguments entirely, so don't. For example AArch64 handles 631 // register and stack HFAs very differently, and this is reflected in the 632 // IR which has already been generated. 633 // 634 // `musttail` calls to this function restrict argument removal attempts. 635 // The signature of the caller must match the signature of the function. 636 // 637 // `musttail` calls in this function prevents us from changing its 638 // signature 639 Result = Live; 640 } else { 641 // See what the effect of this use is (recording any uses that cause 642 // MaybeLive in MaybeLiveArgUses). 643 Result = SurveyUses(&*AI, MaybeLiveArgUses); 644 } 645 646 // Mark the result. 647 MarkValue(CreateArg(&F, ArgI), Result, MaybeLiveArgUses); 648 // Clear the vector again for the next iteration. 649 MaybeLiveArgUses.clear(); 650 } 651 } 652 653 /// MarkValue - This function marks the liveness of RA depending on L. If L is 654 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, 655 /// such that RA will be marked live if any use in MaybeLiveUses gets marked 656 /// live later on. 657 void DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L, 658 const UseVector &MaybeLiveUses) { 659 switch (L) { 660 case Live: 661 MarkLive(RA); 662 break; 663 case MaybeLive: 664 assert(!IsLive(RA) && "Use is already live!"); 665 for (const auto &MaybeLiveUse : MaybeLiveUses) { 666 if (IsLive(MaybeLiveUse)) { 667 // A use is live, so this value is live. 668 MarkLive(RA); 669 break; 670 } else { 671 // Note any uses of this value, so this value can be 672 // marked live whenever one of the uses becomes live. 673 Uses.insert(std::make_pair(MaybeLiveUse, RA)); 674 } 675 } 676 break; 677 } 678 } 679 680 /// MarkLive - Mark the given Function as alive, meaning that it cannot be 681 /// changed in any way. Additionally, 682 /// mark any values that are used as this function's parameters or by its return 683 /// values (according to Uses) live as well. 684 void DeadArgumentEliminationPass::MarkLive(const Function &F) { 685 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: " 686 << F.getName() << "\n"); 687 // Mark the function as live. 688 LiveFunctions.insert(&F); 689 // Mark all arguments as live. 690 for (unsigned ArgI = 0, E = F.arg_size(); ArgI != E; ++ArgI) 691 PropagateLiveness(CreateArg(&F, ArgI)); 692 // Mark all return values as live. 693 for (unsigned Ri = 0, E = NumRetVals(&F); Ri != E; ++Ri) 694 PropagateLiveness(CreateRet(&F, Ri)); 695 } 696 697 /// MarkLive - Mark the given return value or argument as live. Additionally, 698 /// mark any values that are used by this value (according to Uses) live as 699 /// well. 700 void DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) { 701 if (IsLive(RA)) 702 return; // Already marked Live. 703 704 LiveValues.insert(RA); 705 706 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking " 707 << RA.getDescription() << " live\n"); 708 PropagateLiveness(RA); 709 } 710 711 bool DeadArgumentEliminationPass::IsLive(const RetOrArg &RA) { 712 return LiveFunctions.count(RA.F) || LiveValues.count(RA); 713 } 714 715 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness 716 /// to any other values it uses (according to Uses). 717 void DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) { 718 // We don't use upper_bound (or equal_range) here, because our recursive call 719 // to ourselves is likely to cause the upper_bound (which is the first value 720 // not belonging to RA) to become erased and the iterator invalidated. 721 UseMap::iterator Begin = Uses.lower_bound(RA); 722 UseMap::iterator E = Uses.end(); 723 UseMap::iterator I; 724 for (I = Begin; I != E && I->first == RA; ++I) 725 MarkLive(I->second); 726 727 // Erase RA from the Uses map (from the lower bound to wherever we ended up 728 // after the loop). 729 Uses.erase(Begin, I); 730 } 731 732 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F 733 // that are not in LiveValues. Transform the function and all of the callees of 734 // the function to not have these arguments and return values. 735 // 736 bool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) { 737 // Don't modify fully live functions 738 if (LiveFunctions.count(F)) 739 return false; 740 741 // Start by computing a new prototype for the function, which is the same as 742 // the old function, but has fewer arguments and a different return type. 743 FunctionType *FTy = F->getFunctionType(); 744 std::vector<Type*> Params; 745 746 // Keep track of if we have a live 'returned' argument 747 bool HasLiveReturnedArg = false; 748 749 // Set up to build a new list of parameter attributes. 750 SmallVector<AttributeSet, 8> ArgAttrVec; 751 const AttributeList &PAL = F->getAttributes(); 752 753 // Remember which arguments are still alive. 754 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 755 // Construct the new parameter list from non-dead arguments. Also construct 756 // a new set of parameter attributes to correspond. Skip the first parameter 757 // attribute, since that belongs to the return value. 758 unsigned ArgI = 0; 759 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 760 ++I, ++ArgI) { 761 RetOrArg Arg = CreateArg(F, ArgI); 762 if (LiveValues.erase(Arg)) { 763 Params.push_back(I->getType()); 764 ArgAlive[ArgI] = true; 765 ArgAttrVec.push_back(PAL.getParamAttributes(ArgI)); 766 HasLiveReturnedArg |= PAL.hasParamAttribute(ArgI, Attribute::Returned); 767 } else { 768 ++NumArgumentsEliminated; 769 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument " 770 << ArgI << " (" << I->getName() << ") from " 771 << F->getName() << "\n"); 772 } 773 } 774 775 // Find out the new return value. 776 Type *RetTy = FTy->getReturnType(); 777 Type *NRetTy = nullptr; 778 unsigned RetCount = NumRetVals(F); 779 780 // -1 means unused, other numbers are the new index 781 SmallVector<int, 5> NewRetIdxs(RetCount, -1); 782 std::vector<Type*> RetTypes; 783 784 // If there is a function with a live 'returned' argument but a dead return 785 // value, then there are two possible actions: 786 // 1) Eliminate the return value and take off the 'returned' attribute on the 787 // argument. 788 // 2) Retain the 'returned' attribute and treat the return value (but not the 789 // entire function) as live so that it is not eliminated. 790 // 791 // It's not clear in the general case which option is more profitable because, 792 // even in the absence of explicit uses of the return value, code generation 793 // is free to use the 'returned' attribute to do things like eliding 794 // save/restores of registers across calls. Whether or not this happens is 795 // target and ABI-specific as well as depending on the amount of register 796 // pressure, so there's no good way for an IR-level pass to figure this out. 797 // 798 // Fortunately, the only places where 'returned' is currently generated by 799 // the FE are places where 'returned' is basically free and almost always a 800 // performance win, so the second option can just be used always for now. 801 // 802 // This should be revisited if 'returned' is ever applied more liberally. 803 if (RetTy->isVoidTy() || HasLiveReturnedArg) { 804 NRetTy = RetTy; 805 } else { 806 // Look at each of the original return values individually. 807 for (unsigned Ri = 0; Ri != RetCount; ++Ri) { 808 RetOrArg Ret = CreateRet(F, Ri); 809 if (LiveValues.erase(Ret)) { 810 RetTypes.push_back(getRetComponentType(F, Ri)); 811 NewRetIdxs[Ri] = RetTypes.size() - 1; 812 } else { 813 ++NumRetValsEliminated; 814 LLVM_DEBUG( 815 dbgs() << "DeadArgumentEliminationPass - Removing return value " 816 << Ri << " from " << F->getName() << "\n"); 817 } 818 } 819 if (RetTypes.size() > 1) { 820 // More than one return type? Reduce it down to size. 821 if (StructType *STy = dyn_cast<StructType>(RetTy)) { 822 // Make the new struct packed if we used to return a packed struct 823 // already. 824 NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); 825 } else { 826 assert(isa<ArrayType>(RetTy) && "unexpected multi-value return"); 827 NRetTy = ArrayType::get(RetTypes[0], RetTypes.size()); 828 } 829 } else if (RetTypes.size() == 1) 830 // One return type? Just a simple value then, but only if we didn't use to 831 // return a struct with that simple value before. 832 NRetTy = RetTypes.front(); 833 else if (RetTypes.empty()) 834 // No return types? Make it void, but only if we didn't use to return {}. 835 NRetTy = Type::getVoidTy(F->getContext()); 836 } 837 838 assert(NRetTy && "No new return type found?"); 839 840 // The existing function return attributes. 841 AttrBuilder RAttrs(PAL.getRetAttributes()); 842 843 // Remove any incompatible attributes, but only if we removed all return 844 // values. Otherwise, ensure that we don't have any conflicting attributes 845 // here. Currently, this should not be possible, but special handling might be 846 // required when new return value attributes are added. 847 if (NRetTy->isVoidTy()) 848 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 849 else 850 assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) && 851 "Return attributes no longer compatible?"); 852 853 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 854 855 // Strip allocsize attributes. They might refer to the deleted arguments. 856 AttributeSet FnAttrs = PAL.getFnAttributes().removeAttribute( 857 F->getContext(), Attribute::AllocSize); 858 859 // Reconstruct the AttributesList based on the vector we constructed. 860 assert(ArgAttrVec.size() == Params.size()); 861 AttributeList NewPAL = 862 AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 863 864 // Create the new function type based on the recomputed parameters. 865 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 866 867 // No change? 868 if (NFTy == FTy) 869 return false; 870 871 // Create the new function body and insert it into the module... 872 Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace()); 873 NF->copyAttributesFrom(F); 874 NF->setComdat(F->getComdat()); 875 NF->setAttributes(NewPAL); 876 // Insert the new function before the old function, so we won't be processing 877 // it again. 878 F->getParent()->getFunctionList().insert(F->getIterator(), NF); 879 NF->takeName(F); 880 881 // Loop over all of the callers of the function, transforming the call sites 882 // to pass in a smaller number of arguments into the new function. 883 std::vector<Value*> Args; 884 while (!F->use_empty()) { 885 CallBase &CB = cast<CallBase>(*F->user_back()); 886 887 ArgAttrVec.clear(); 888 const AttributeList &CallPAL = CB.getAttributes(); 889 890 // Adjust the call return attributes in case the function was changed to 891 // return void. 892 AttrBuilder RAttrs(CallPAL.getRetAttributes()); 893 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 894 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 895 896 // Declare these outside of the loops, so we can reuse them for the second 897 // loop, which loops the varargs. 898 auto I = CB.arg_begin(); 899 unsigned Pi = 0; 900 // Loop over those operands, corresponding to the normal arguments to the 901 // original function, and add those that are still alive. 902 for (unsigned E = FTy->getNumParams(); Pi != E; ++I, ++Pi) 903 if (ArgAlive[Pi]) { 904 Args.push_back(*I); 905 // Get original parameter attributes, but skip return attributes. 906 AttributeSet Attrs = CallPAL.getParamAttributes(Pi); 907 if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) { 908 // If the return type has changed, then get rid of 'returned' on the 909 // call site. The alternative is to make all 'returned' attributes on 910 // call sites keep the return value alive just like 'returned' 911 // attributes on function declaration but it's less clearly a win and 912 // this is not an expected case anyway 913 ArgAttrVec.push_back(AttributeSet::get( 914 F->getContext(), 915 AttrBuilder(Attrs).removeAttribute(Attribute::Returned))); 916 } else { 917 // Otherwise, use the original attributes. 918 ArgAttrVec.push_back(Attrs); 919 } 920 } 921 922 // Push any varargs arguments on the list. Don't forget their attributes. 923 for (auto E = CB.arg_end(); I != E; ++I, ++Pi) { 924 Args.push_back(*I); 925 ArgAttrVec.push_back(CallPAL.getParamAttributes(Pi)); 926 } 927 928 // Reconstruct the AttributesList based on the vector we constructed. 929 assert(ArgAttrVec.size() == Args.size()); 930 931 // Again, be sure to remove any allocsize attributes, since their indices 932 // may now be incorrect. 933 AttributeSet FnAttrs = CallPAL.getFnAttributes().removeAttribute( 934 F->getContext(), Attribute::AllocSize); 935 936 AttributeList NewCallPAL = AttributeList::get( 937 F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 938 939 SmallVector<OperandBundleDef, 1> OpBundles; 940 CB.getOperandBundlesAsDefs(OpBundles); 941 942 CallBase *NewCB = nullptr; 943 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { 944 NewCB = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 945 Args, OpBundles, "", CB.getParent()); 946 } else { 947 NewCB = CallInst::Create(NFTy, NF, Args, OpBundles, "", &CB); 948 cast<CallInst>(NewCB)->setTailCallKind( 949 cast<CallInst>(&CB)->getTailCallKind()); 950 } 951 NewCB->setCallingConv(CB.getCallingConv()); 952 NewCB->setAttributes(NewCallPAL); 953 NewCB->copyMetadata(CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg}); 954 Args.clear(); 955 ArgAttrVec.clear(); 956 957 if (!CB.use_empty() || CB.isUsedByMetadata()) { 958 if (NewCB->getType() == CB.getType()) { 959 // Return type not changed? Just replace users then. 960 CB.replaceAllUsesWith(NewCB); 961 NewCB->takeName(&CB); 962 } else if (NewCB->getType()->isVoidTy()) { 963 // If the return value is dead, replace any uses of it with undef 964 // (any non-debug value uses will get removed later on). 965 if (!CB.getType()->isX86_MMXTy()) 966 CB.replaceAllUsesWith(UndefValue::get(CB.getType())); 967 } else { 968 assert((RetTy->isStructTy() || RetTy->isArrayTy()) && 969 "Return type changed, but not into a void. The old return type" 970 " must have been a struct or an array!"); 971 Instruction *InsertPt = &CB; 972 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { 973 BasicBlock *NewEdge = 974 SplitEdge(NewCB->getParent(), II->getNormalDest()); 975 InsertPt = &*NewEdge->getFirstInsertionPt(); 976 } 977 978 // We used to return a struct or array. Instead of doing smart stuff 979 // with all the uses, we will just rebuild it using extract/insertvalue 980 // chaining and let instcombine clean that up. 981 // 982 // Start out building up our return value from undef 983 Value *RetVal = UndefValue::get(RetTy); 984 for (unsigned Ri = 0; Ri != RetCount; ++Ri) 985 if (NewRetIdxs[Ri] != -1) { 986 Value *V; 987 IRBuilder<NoFolder> IRB(InsertPt); 988 if (RetTypes.size() > 1) 989 // We are still returning a struct, so extract the value from our 990 // return value 991 V = IRB.CreateExtractValue(NewCB, NewRetIdxs[Ri], "newret"); 992 else 993 // We are now returning a single element, so just insert that 994 V = NewCB; 995 // Insert the value at the old position 996 RetVal = IRB.CreateInsertValue(RetVal, V, Ri, "oldret"); 997 } 998 // Now, replace all uses of the old call instruction with the return 999 // struct we built 1000 CB.replaceAllUsesWith(RetVal); 1001 NewCB->takeName(&CB); 1002 } 1003 } 1004 1005 // Finally, remove the old call from the program, reducing the use-count of 1006 // F. 1007 CB.eraseFromParent(); 1008 } 1009 1010 // Since we have now created the new function, splice the body of the old 1011 // function right into the new function, leaving the old rotting hulk of the 1012 // function empty. 1013 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 1014 1015 // Loop over the argument list, transferring uses of the old arguments over to 1016 // the new arguments, also transferring over the names as well. 1017 ArgI = 0; 1018 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 1019 I2 = NF->arg_begin(); 1020 I != E; ++I, ++ArgI) 1021 if (ArgAlive[ArgI]) { 1022 // If this is a live argument, move the name and users over to the new 1023 // version. 1024 I->replaceAllUsesWith(&*I2); 1025 I2->takeName(&*I); 1026 ++I2; 1027 } else { 1028 // If this argument is dead, replace any uses of it with undef 1029 // (any non-debug value uses will get removed later on). 1030 if (!I->getType()->isX86_MMXTy()) 1031 I->replaceAllUsesWith(UndefValue::get(I->getType())); 1032 } 1033 1034 // If we change the return value of the function we must rewrite any return 1035 // instructions. Check this now. 1036 if (F->getReturnType() != NF->getReturnType()) 1037 for (BasicBlock &BB : *NF) 1038 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) { 1039 IRBuilder<NoFolder> IRB(RI); 1040 Value *RetVal = nullptr; 1041 1042 if (!NFTy->getReturnType()->isVoidTy()) { 1043 assert(RetTy->isStructTy() || RetTy->isArrayTy()); 1044 // The original return value was a struct or array, insert 1045 // extractvalue/insertvalue chains to extract only the values we need 1046 // to return and insert them into our new result. 1047 // This does generate messy code, but we'll let it to instcombine to 1048 // clean that up. 1049 Value *OldRet = RI->getOperand(0); 1050 // Start out building up our return value from undef 1051 RetVal = UndefValue::get(NRetTy); 1052 for (unsigned RetI = 0; RetI != RetCount; ++RetI) 1053 if (NewRetIdxs[RetI] != -1) { 1054 Value *EV = IRB.CreateExtractValue(OldRet, RetI, "oldret"); 1055 1056 if (RetTypes.size() > 1) { 1057 // We're still returning a struct, so reinsert the value into 1058 // our new return value at the new index 1059 1060 RetVal = IRB.CreateInsertValue(RetVal, EV, NewRetIdxs[RetI], 1061 "newret"); 1062 } else { 1063 // We are now only returning a simple value, so just return the 1064 // extracted value. 1065 RetVal = EV; 1066 } 1067 } 1068 } 1069 // Replace the return instruction with one returning the new return 1070 // value (possibly 0 if we became void). 1071 auto *NewRet = ReturnInst::Create(F->getContext(), RetVal, RI); 1072 NewRet->setDebugLoc(RI->getDebugLoc()); 1073 BB.getInstList().erase(RI); 1074 } 1075 1076 // Clone metadatas from the old function, including debug info descriptor. 1077 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 1078 F->getAllMetadata(MDs); 1079 for (auto MD : MDs) 1080 NF->addMetadata(MD.first, *MD.second); 1081 1082 // Now that the old function is dead, delete it. 1083 F->eraseFromParent(); 1084 1085 return true; 1086 } 1087 1088 PreservedAnalyses DeadArgumentEliminationPass::run(Module &M, 1089 ModuleAnalysisManager &) { 1090 bool Changed = false; 1091 1092 // First pass: Do a simple check to see if any functions can have their "..." 1093 // removed. We can do this if they never call va_start. This loop cannot be 1094 // fused with the next loop, because deleting a function invalidates 1095 // information computed while surveying other functions. 1096 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n"); 1097 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1098 Function &F = *I++; 1099 if (F.getFunctionType()->isVarArg()) 1100 Changed |= DeleteDeadVarargs(F); 1101 } 1102 1103 // Second phase:loop through the module, determining which arguments are live. 1104 // We assume all arguments are dead unless proven otherwise (allowing us to 1105 // determine that dead arguments passed into recursive functions are dead). 1106 // 1107 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n"); 1108 for (auto &F : M) 1109 SurveyFunction(F); 1110 1111 // Now, remove all dead arguments and return values from each function in 1112 // turn. 1113 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1114 // Increment now, because the function will probably get removed (ie. 1115 // replaced by a new one). 1116 Function *F = &*I++; 1117 Changed |= RemoveDeadStuffFromFunction(F); 1118 } 1119 1120 // Finally, look for any unused parameters in functions with non-local 1121 // linkage and replace the passed in parameters with undef. 1122 for (auto &F : M) 1123 Changed |= RemoveDeadArgumentsFromCallers(F); 1124 1125 if (!Changed) 1126 return PreservedAnalyses::all(); 1127 return PreservedAnalyses::none(); 1128 } 1129