1139 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This pass deletes dead arguments from internal functions. Dead argument10// elimination removes arguments which are directly dead, as well as arguments11// only passed into function calls as dead arguments of other functions. This12// pass also deletes dead return values in a similar way.13//14// This pass is often useful as a cleanup pass to run after aggressive15// 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/Analysis/OptimizationRemarkEmitter.h"23#include "llvm/IR/Argument.h"24#include "llvm/IR/AttributeMask.h"25#include "llvm/IR/Attributes.h"26#include "llvm/IR/BasicBlock.h"27#include "llvm/IR/Constants.h"28#include "llvm/IR/DIBuilder.h"29#include "llvm/IR/DerivedTypes.h"30#include "llvm/IR/Function.h"31#include "llvm/IR/IRBuilder.h"32#include "llvm/IR/InstrTypes.h"33#include "llvm/IR/Instructions.h"34#include "llvm/IR/IntrinsicInst.h"35#include "llvm/IR/Intrinsics.h"36#include "llvm/IR/Module.h"37#include "llvm/IR/NoFolder.h"38#include "llvm/IR/PassManager.h"39#include "llvm/IR/Type.h"40#include "llvm/IR/Use.h"41#include "llvm/IR/User.h"42#include "llvm/IR/Value.h"43#include "llvm/InitializePasses.h"44#include "llvm/Pass.h"45#include "llvm/Support/Casting.h"46#include "llvm/Support/Debug.h"47#include "llvm/Support/raw_ostream.h"48#include "llvm/Transforms/IPO.h"49#include "llvm/Transforms/Utils/BasicBlockUtils.h"50#include <cassert>51#include <utility>52#include <vector>53 54using namespace llvm;55 56#define DEBUG_TYPE "deadargelim"57 58STATISTIC(NumArgumentsEliminated, "Number of unread args removed");59STATISTIC(NumRetValsEliminated, "Number of unused return values removed");60STATISTIC(NumArgumentsReplacedWithPoison,61 "Number of unread args replaced with poison");62 63namespace {64 65/// The dead argument elimination pass.66class DAE : public ModulePass {67protected:68 // DAH uses this to specify a different ID.69 explicit DAE(char &ID) : ModulePass(ID) {}70 71public:72 static char ID; // Pass identification, replacement for typeid73 74 DAE() : ModulePass(ID) {75 initializeDAEPass(*PassRegistry::getPassRegistry());76 }77 78 bool runOnModule(Module &M) override {79 if (skipModule(M))80 return false;81 DeadArgumentEliminationPass DAEP(shouldHackArguments());82 ModuleAnalysisManager DummyMAM;83 PreservedAnalyses PA = DAEP.run(M, DummyMAM);84 return !PA.areAllPreserved();85 }86 87 virtual bool shouldHackArguments() const { return false; }88};89 90} // end anonymous namespace91 92char DAE::ID = 0;93 94INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false)95 96namespace {97 98/// The DeadArgumentHacking pass, same as dead argument elimination, but deletes99/// arguments to functions which are external. This is only for use by bugpoint.100struct 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 namespace109 110char DAH::ID = 0;111 112INITIALIZE_PASS(DAH, "deadarghaX0r",113 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", false,114 false)115 116/// This pass removes arguments from functions which are not used by the body of117/// the function.118ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }119 120ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); }121 122/// If this is an function that takes a ... list, and if llvm.vastart is never123/// called, the varargs list is dead for the function.124bool DeadArgumentEliminationPass::deleteDeadVarargs(Function &F) {125 assert(F.getFunctionType()->isVarArg() && "Function isn't varargs!");126 if (F.isDeclaration() || !F.hasLocalLinkage())127 return false;128 129 // Ensure that the function is only directly called.130 if (F.hasAddressTaken())131 return false;132 133 // Don't touch naked functions. The assembly might be using an argument, or134 // otherwise rely on the frame layout in a way that this analysis will not135 // see.136 if (F.hasFnAttribute(Attribute::Naked)) {137 return false;138 }139 140 // Okay, we know we can transform this function if safe. Scan its body141 // looking for calls marked musttail or calls to llvm.vastart.142 for (BasicBlock &BB : F) {143 for (Instruction &I : BB) {144 CallInst *CI = dyn_cast<CallInst>(&I);145 if (!CI)146 continue;147 if (CI->isMustTailCall())148 return false;149 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {150 if (II->getIntrinsicID() == Intrinsic::vastart)151 return false;152 }153 }154 }155 156 // If we get here, there are no calls to llvm.vastart in the function body,157 // remove the "..." and adjust all the calls.158 159 // Start by computing a new prototype for the function, which is the same as160 // the old function, but doesn't have isVarArg set.161 FunctionType *FTy = F.getFunctionType();162 163 std::vector<Type *> Params(FTy->param_begin(), FTy->param_end());164 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), 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, F.getLinkage(), F.getAddressSpace());169 NF->copyAttributesFrom(&F);170 NF->setComdat(F.getComdat());171 F.getParent()->getFunctionList().insert(F.getIterator(), NF);172 NF->takeName(&F);173 174 // Loop over all the callers of the function, transforming the call sites175 // to pass in a smaller number of arguments into the new function.176 //177 std::vector<Value *> Args;178 for (User *U : llvm::make_early_inc_range(F.users())) {179 CallBase *CB = dyn_cast<CallBase>(U);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.getParamAttrs(ArgNo));192 PAL = AttributeList::get(F.getContext(), PAL.getFnAttrs(),193 PAL.getRetAttrs(), 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->getIterator());203 } else {204 NewCB = CallInst::Create(NF, Args, OpBundles, "", CB->getIterator());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 of220 // F.221 CB->eraseFromParent();222 }223 224 // Since we have now created the new function, splice the body of the old225 // function right into the new function, leaving the old rotting hulk of the226 // function empty.227 NF->splice(NF->begin(), &F);228 229 // Loop over the argument list, transferring uses of the old arguments over to230 // the new arguments, also transferring over the names as well. While we're231 // at it, remove the dead arguments from the DeadArguments list.232 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(),233 I2 = NF->arg_begin();234 I != E; ++I, ++I2) {235 // Move the name and users over to the new version.236 I->replaceAllUsesWith(&*I2);237 I2->takeName(&*I);238 }239 240 // Clone metadata from the old function, including debug info descriptor.241 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;242 F.getAllMetadata(MDs);243 for (auto [KindID, Node] : MDs)244 NF->addMetadata(KindID, *Node);245 246 // Fix up any BlockAddresses that refer to the function.247 F.replaceAllUsesWith(NF);248 // Delete the bitcast that we just created, so that NF does not249 // appear to be address-taken.250 NF->removeDeadConstantUsers();251 // Finally, nuke the old function.252 F.eraseFromParent();253 return true;254}255 256/// Checks if the given function has any arguments that are unused, and changes257/// the caller parameters to be poison instead.258bool DeadArgumentEliminationPass::removeDeadArgumentsFromCallers(Function &F) {259 // We cannot change the arguments if this TU does not define the function or260 // if the linker may choose a function body from another TU, even if the261 // nominal linkage indicates that other copies of the function have the same262 // semantics. In the below example, the dead load from %p may not have been263 // eliminated from the linker-chosen copy of f, so replacing %p with poison264 // in callers may introduce undefined behavior.265 //266 // define linkonce_odr void @f(i32* %p) {267 // %v = load i32 %p268 // ret void269 // }270 if (!F.hasExactDefinition())271 return false;272 273 // Functions with local linkage should already have been handled, except if274 // they are fully alive (e.g., called indirectly) and except for the fragile275 // (variadic) ones. In these cases, we may still be able to improve their276 // statically known call sites.277 if ((F.hasLocalLinkage() && !FrozenFunctions.count(&F)) &&278 !F.getFunctionType()->isVarArg())279 return false;280 281 // Don't touch naked functions. The assembly might be using an argument, or282 // otherwise rely on the frame layout in a way that this analysis will not283 // see.284 if (F.hasFnAttribute(Attribute::Naked))285 return false;286 287 if (F.use_empty())288 return false;289 290 SmallVector<unsigned, 8> UnusedArgs;291 bool Changed = false;292 293 AttributeMask UBImplyingAttributes =294 AttributeFuncs::getUBImplyingAttributes();295 for (Argument &Arg : F.args()) {296 if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() &&297 !Arg.hasPassPointeeByValueCopyAttr()) {298 if (Arg.isUsedByMetadata()) {299 Arg.replaceAllUsesWith(PoisonValue::get(Arg.getType()));300 Changed = true;301 }302 UnusedArgs.push_back(Arg.getArgNo());303 F.removeParamAttrs(Arg.getArgNo(), UBImplyingAttributes);304 }305 }306 307 if (UnusedArgs.empty())308 return false;309 310 for (Use &U : F.uses()) {311 CallBase *CB = dyn_cast<CallBase>(U.getUser());312 if (!CB || !CB->isCallee(&U) ||313 CB->getFunctionType() != F.getFunctionType())314 continue;315 316 // Now go through all unused args and replace them with poison.317 for (unsigned ArgNo : UnusedArgs) {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 0331/// for void functions and 1 for functions not returning a struct. It returns332/// the number of struct elements for functions returning a struct.333static 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. Should345/// correspond to the result type of an ExtractValue instruction executed with346/// just that one Idx (i.e. only top-level structure is considered).347static 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 to359/// the MaybeLiveUses argument. Returns the determined liveness of Use.360DeadArgumentEliminationPass::Liveness361DeadArgumentEliminationPass::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 if368 // 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 it374/// should be alive or not. Adds this use to MaybeLiveUses if it causes the375/// used value to become MaybeLive.376///377/// RetValNum is the return value number to use when this use is used in a378/// return instruction. This is used in the recursion, you should always leave379/// it at 0.380DeadArgumentEliminationPass::Liveness381DeadArgumentEliminationPass::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 the386 // function's return value is live. We use RetValNum here, for the case387 // that U is really a use of an insertvalue instruction that uses the388 // 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 any400 // sub-value is live, then the entire value is considered live. This401 // 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 liveness414 // depends on all uses of that aggregate, but if it is used as a return415 // 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 an440 // argument, since if it was the function argument this would be an441 // indirect call and that we know can't be looking at a value of the442 // 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 corresponding453 // 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 value463/// Returns the Liveness deduced from the uses of this value.464///465/// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If466/// the result is Live, MaybeLiveUses might be modified but its content should467/// be ignored (since it might not be complete).468DeadArgumentEliminationPass::Liveness469DeadArgumentEliminationPass::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 whether483/// it uses any of its incoming arguments or whether any callers use the return484/// value. This fills in the LiveValues set and Uses map.485///486/// We consider arguments of non-internal functions to be intrinsically alive as487/// well as arguments to functions which have their "address taken".488void DeadArgumentEliminationPass::surveyFunction(const Function &F) {489 // Functions with inalloca/preallocated parameters are expecting args in a490 // particular register and memory layout.491 if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) ||492 F.getAttributes().hasAttrSomewhere(Attribute::Preallocated)) {493 markFrozen(F);494 return;495 }496 497 // Don't touch naked functions. The assembly might be using an argument, or498 // otherwise rely on the frame layout in a way that this analysis will not499 // see.500 if (F.hasFnAttribute(Attribute::Naked)) {501 markFrozen(F);502 return;503 }504 505 unsigned RetCount = numRetVals(&F);506 507 // Assume all return values are dead508 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, so515 // we can add those to the Uses map if the return value really turns out to be516 // MaybeLive. Initialized to a list of RetCount empty lists.517 RetUses MaybeLiveRetUses(RetCount);518 519 for (const BasicBlock &BB : F) {520 if (BB.getTerminatingMustTailCall()) {521 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()522 << " has musttail calls\n");523 if (markFnOrRetTyFrozenOnMusttail(F))524 return;525 }526 }527 528 if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) {529 markFrozen(F);530 return;531 }532 533 LLVM_DEBUG(534 dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: "535 << F.getName() << "\n");536 // Keep track of the number of live retvals, so we can skip checks once all537 // of them turn out to be live.538 unsigned NumLiveRetVals = 0;539 540 // Loop all uses of the function.541 for (const Use &U : F.uses()) {542 // If the function is PASSED IN as an argument, its address has been543 // taken.544 const auto *CB = dyn_cast<CallBase>(U.getUser());545 if (!CB || !CB->isCallee(&U) ||546 CB->getFunctionType() != F.getFunctionType()) {547 markFrozen(F);548 return;549 }550 551 if (CB->isMustTailCall()) {552 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()553 << " has musttail callers\n");554 if (markFnOrRetTyFrozenOnMusttail(F))555 return;556 }557 558 // If we end up here, we are looking at a direct call to our function.559 560 // Now, check how our return value(s) is/are used in this caller. Don't561 // bother checking return values if all of them are live already.562 if (NumLiveRetVals == RetCount)563 continue;564 565 // Check all uses of the return value.566 for (const Use &UU : CB->uses()) {567 if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(UU.getUser())) {568 // This use uses a part of our return value, survey the uses of569 // that part and store the results for this index only.570 unsigned Idx = *Ext->idx_begin();571 if (RetValLiveness[Idx] != Live) {572 RetValLiveness[Idx] = surveyUses(Ext, MaybeLiveRetUses[Idx]);573 if (RetValLiveness[Idx] == Live)574 NumLiveRetVals++;575 }576 } else {577 // Used by something else than extractvalue. Survey, but assume that the578 // result applies to all sub-values.579 UseVector MaybeLiveAggregateUses;580 if (surveyUse(&UU, MaybeLiveAggregateUses) == Live) {581 NumLiveRetVals = RetCount;582 RetValLiveness.assign(RetCount, Live);583 break;584 }585 586 for (unsigned Ri = 0; Ri != RetCount; ++Ri) {587 if (RetValLiveness[Ri] != Live)588 MaybeLiveRetUses[Ri].append(MaybeLiveAggregateUses.begin(),589 MaybeLiveAggregateUses.end());590 }591 }592 }593 }594 595 // Now we've inspected all callers, record the liveness of our return values.596 for (unsigned Ri = 0; Ri != RetCount; ++Ri)597 markValue(createRet(&F, Ri), RetValLiveness[Ri], MaybeLiveRetUses[Ri]);598 599 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: "600 << F.getName() << "\n");601 602 // Now, check all of our arguments.603 unsigned ArgI = 0;604 UseVector MaybeLiveArgUses;605 for (Function::const_arg_iterator AI = F.arg_begin(), E = F.arg_end();606 AI != E; ++AI, ++ArgI) {607 Liveness Result;608 if (F.getFunctionType()->isVarArg()) {609 // Variadic functions will already have a va_arg function expanded inside610 // them, making them potentially very sensitive to ABI changes resulting611 // from removing arguments entirely, so don't. For example AArch64 handles612 // register and stack HFAs very differently, and this is reflected in the613 // IR which has already been generated.614 Result = Live;615 } else {616 // See what the effect of this use is (recording any uses that cause617 // MaybeLive in MaybeLiveArgUses).618 Result = surveyUses(&*AI, MaybeLiveArgUses);619 }620 621 // Mark the result.622 markValue(createArg(&F, ArgI), Result, MaybeLiveArgUses);623 // Clear the vector again for the next iteration.624 MaybeLiveArgUses.clear();625 }626}627 628/// Marks the liveness of RA depending on L. If L is MaybeLive, it also takes629/// all uses in MaybeLiveUses and records them in Uses, such that RA will be630/// marked live if any use in MaybeLiveUses gets marked live later on.631void DeadArgumentEliminationPass::markValue(const RetOrArg &RA, Liveness L,632 const UseVector &MaybeLiveUses) {633 switch (L) {634 case Live:635 markLive(RA);636 break;637 case MaybeLive:638 assert(!isLive(RA) && "Use is already live!");639 for (const auto &MaybeLiveUse : MaybeLiveUses) {640 if (isLive(MaybeLiveUse)) {641 // A use is live, so this value is live.642 markLive(RA);643 break;644 }645 // Note any uses of this value, so this value can be646 // marked live whenever one of the uses becomes live.647 Uses.emplace(MaybeLiveUse, RA);648 }649 break;650 }651}652 653/// Return true if we freeze the whole function.654/// If the calling convention is not swifttailcc or tailcc, the caller and655/// callee of musttail must have exactly the same signature. Otherwise we656/// only needs to guarantee they have the same return type.657bool DeadArgumentEliminationPass::markFnOrRetTyFrozenOnMusttail(658 const Function &F) {659 if (F.getCallingConv() != CallingConv::SwiftTail ||660 F.getCallingConv() != CallingConv::Tail) {661 markFrozen(F);662 return true;663 } else {664 markRetTyFrozen(F);665 return false;666 }667}668 669/// Mark the given Function as alive, meaning that it cannot be changed in any670/// way. Additionally, mark any values that are used as this function's671/// parameters or by its return values (according to Uses) live as well.672void DeadArgumentEliminationPass::markFrozen(const Function &F) {673 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - frozen fn: "674 << F.getName() << "\n");675 // Mark the function as frozen.676 FrozenFunctions.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 685void DeadArgumentEliminationPass::markRetTyFrozen(const Function &F) {686 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - frozen return type fn: "687 << F.getName() << "\n");688 FrozenRetTyFunctions.insert(&F);689}690 691/// Mark the given return value or argument as live. Additionally, mark any692/// values that are used by this value (according to Uses) live as well.693void DeadArgumentEliminationPass::markLive(const RetOrArg &RA) {694 if (isLive(RA))695 return; // Already marked Live.696 697 LiveValues.insert(RA);698 699 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking "700 << RA.getDescription() << " live\n");701 propagateLiveness(RA);702}703 704bool DeadArgumentEliminationPass::isLive(const RetOrArg &RA) {705 return FrozenFunctions.count(RA.F) || LiveValues.count(RA);706}707 708/// Given that RA is a live value, propagate it's liveness to any other values709/// it uses (according to Uses).710void DeadArgumentEliminationPass::propagateLiveness(const RetOrArg &RA) {711 // We don't use upper_bound (or equal_range) here, because our recursive call712 // to ourselves is likely to cause the upper_bound (which is the first value713 // not belonging to RA) to become erased and the iterator invalidated.714 UseMap::iterator Begin = Uses.lower_bound(RA);715 UseMap::iterator E = Uses.end();716 UseMap::iterator I;717 for (I = Begin; I != E && I->first == RA; ++I)718 markLive(I->second);719 720 // Erase RA from the Uses map (from the lower bound to wherever we ended up721 // after the loop).722 Uses.erase(Begin, I);723}724 725/// Remove any arguments and return values from F that are not in LiveValues.726/// Transform the function and all the callees of the function to not have these727/// arguments and return values.728bool DeadArgumentEliminationPass::removeDeadStuffFromFunction(Function *F) {729 // Don't modify frozen functions730 if (FrozenFunctions.count(F))731 return false;732 733 // Start by computing a new prototype for the function, which is the same as734 // the old function, but has fewer arguments and a different return type.735 FunctionType *FTy = F->getFunctionType();736 std::vector<Type *> Params;737 738 // Keep track of if we have a live 'returned' argument739 bool HasLiveReturnedArg = false;740 741 // Set up to build a new list of parameter attributes.742 SmallVector<AttributeSet, 8> ArgAttrVec;743 const AttributeList &PAL = F->getAttributes();744 OptimizationRemarkEmitter ORE(F);745 746 // Remember which arguments are still alive.747 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false);748 // Construct the new parameter list from non-dead arguments. Also construct749 // a new set of parameter attributes to correspond. Skip the first parameter750 // attribute, since that belongs to the return value.751 unsigned ArgI = 0;752 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;753 ++I, ++ArgI) {754 RetOrArg Arg = createArg(F, ArgI);755 if (LiveValues.erase(Arg)) {756 Params.push_back(I->getType());757 ArgAlive[ArgI] = true;758 ArgAttrVec.push_back(PAL.getParamAttrs(ArgI));759 HasLiveReturnedArg |= PAL.hasParamAttr(ArgI, Attribute::Returned);760 } else {761 ++NumArgumentsEliminated;762 763 ORE.emit([&]() {764 return OptimizationRemark(DEBUG_TYPE, "ArgumentRemoved", F)765 << "eliminating argument " << ore::NV("ArgName", I->getName())766 << "(" << ore::NV("ArgIndex", ArgI) << ")";767 });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 index780 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 return784 // value, then there are two possible actions:785 // 1) Eliminate the return value and take off the 'returned' attribute on the786 // argument.787 // 2) Retain the 'returned' attribute and treat the return value (but not the788 // 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 generation792 // is free to use the 'returned' attribute to do things like eliding793 // save/restores of registers across calls. Whether this happens is target and794 // ABI-specific as well as depending on the amount of register pressure, so795 // 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 by798 // the FE are places where 'returned' is basically free and almost always a799 // 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 FrozenRetTyFunctions.count(F)) {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 815 ORE.emit([&]() {816 return OptimizationRemark(DEBUG_TYPE, "ReturnValueRemoved", F)817 << "removing return value " << std::to_string(Ri);818 });819 LLVM_DEBUG(820 dbgs() << "DeadArgumentEliminationPass - Removing return value "821 << Ri << " from " << F->getName() << "\n");822 }823 }824 if (RetTypes.size() > 1) {825 // More than one return type? Reduce it down to size.826 if (StructType *STy = dyn_cast<StructType>(RetTy)) {827 // Make the new struct packed if we used to return a packed struct828 // already.829 NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked());830 } else {831 assert(isa<ArrayType>(RetTy) && "unexpected multi-value return");832 NRetTy = ArrayType::get(RetTypes[0], RetTypes.size());833 }834 } else if (RetTypes.size() == 1)835 // One return type? Just a simple value then, but only if we didn't use to836 // return a struct with that simple value before.837 NRetTy = RetTypes.front();838 else if (RetTypes.empty())839 // No return types? Make it void, but only if we didn't use to return {}.840 NRetTy = Type::getVoidTy(F->getContext());841 }842 843 assert(NRetTy && "No new return type found?");844 845 // The existing function return attributes.846 AttrBuilder RAttrs(F->getContext(), PAL.getRetAttrs());847 848 // Remove any incompatible attributes, but only if we removed all return849 // values. Otherwise, ensure that we don't have any conflicting attributes850 // here. Currently, this should not be possible, but special handling might be851 // required when new return value attributes are added.852 if (NRetTy->isVoidTy())853 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy, PAL.getRetAttrs()));854 else855 assert(!RAttrs.overlaps(856 AttributeFuncs::typeIncompatible(NRetTy, PAL.getRetAttrs())) &&857 "Return attributes no longer compatible?");858 859 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs);860 861 // Strip allocsize attributes. They might refer to the deleted arguments.862 AttributeSet FnAttrs =863 PAL.getFnAttrs().removeAttribute(F->getContext(), Attribute::AllocSize);864 865 // Reconstruct the AttributesList based on the vector we constructed.866 assert(ArgAttrVec.size() == Params.size());867 AttributeList NewPAL =868 AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec);869 870 // Create the new function type based on the recomputed parameters.871 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg());872 873 // No change?874 if (NFTy == FTy)875 return false;876 877 // Create the new function body and insert it into the module...878 Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace());879 NF->copyAttributesFrom(F);880 NF->setComdat(F->getComdat());881 NF->setAttributes(NewPAL);882 // Insert the new function before the old function, so we won't be processing883 // it again.884 F->getParent()->getFunctionList().insert(F->getIterator(), NF);885 NF->takeName(F);886 887 // Loop over all the callers of the function, transforming the call sites to888 // pass in a smaller number of arguments into the new function.889 std::vector<Value *> Args;890 while (!F->use_empty()) {891 CallBase &CB = cast<CallBase>(*F->user_back());892 893 ArgAttrVec.clear();894 const AttributeList &CallPAL = CB.getAttributes();895 896 // Adjust the call return attributes in case the function was changed to897 // return void.898 AttrBuilder RAttrs(F->getContext(), CallPAL.getRetAttrs());899 RAttrs.remove(900 AttributeFuncs::typeIncompatible(NRetTy, CallPAL.getRetAttrs()));901 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs);902 903 // Declare these outside of the loops, so we can reuse them for the second904 // loop, which loops the varargs.905 auto *I = CB.arg_begin();906 unsigned Pi = 0;907 // Loop over those operands, corresponding to the normal arguments to the908 // original function, and add those that are still alive.909 for (unsigned E = FTy->getNumParams(); Pi != E; ++I, ++Pi)910 if (ArgAlive[Pi]) {911 Args.push_back(*I);912 // Get original parameter attributes, but skip return attributes.913 AttributeSet Attrs = CallPAL.getParamAttrs(Pi);914 if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) {915 // If the return type has changed, then get rid of 'returned' on the916 // call site. The alternative is to make all 'returned' attributes on917 // call sites keep the return value alive just like 'returned'918 // attributes on function declaration, but it's less clearly a win and919 // this is not an expected case anyway920 ArgAttrVec.push_back(AttributeSet::get(921 F->getContext(), AttrBuilder(F->getContext(), Attrs)922 .removeAttribute(Attribute::Returned)));923 } else {924 // Otherwise, use the original attributes.925 ArgAttrVec.push_back(Attrs);926 }927 }928 929 // Push any varargs arguments on the list. Don't forget their attributes.930 for (auto *E = CB.arg_end(); I != E; ++I, ++Pi) {931 Args.push_back(*I);932 ArgAttrVec.push_back(CallPAL.getParamAttrs(Pi));933 }934 935 // Reconstruct the AttributesList based on the vector we constructed.936 assert(ArgAttrVec.size() == Args.size());937 938 // Again, be sure to remove any allocsize attributes, since their indices939 // may now be incorrect.940 AttributeSet FnAttrs = CallPAL.getFnAttrs().removeAttribute(941 F->getContext(), Attribute::AllocSize);942 943 AttributeList NewCallPAL =944 AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec);945 946 SmallVector<OperandBundleDef, 1> OpBundles;947 CB.getOperandBundlesAsDefs(OpBundles);948 949 CallBase *NewCB = nullptr;950 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {951 NewCB = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),952 Args, OpBundles, "", CB.getParent());953 } else {954 NewCB = CallInst::Create(NFTy, NF, Args, OpBundles, "", CB.getIterator());955 cast<CallInst>(NewCB)->setTailCallKind(956 cast<CallInst>(&CB)->getTailCallKind());957 }958 NewCB->setCallingConv(CB.getCallingConv());959 NewCB->setAttributes(NewCallPAL);960 NewCB->copyMetadata(CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});961 Args.clear();962 ArgAttrVec.clear();963 964 if (!CB.use_empty() || CB.isUsedByMetadata()) {965 if (NewCB->getType() == CB.getType()) {966 // Return type not changed? Just replace users then.967 CB.replaceAllUsesWith(NewCB);968 NewCB->takeName(&CB);969 } else if (NewCB->getType()->isVoidTy()) {970 // If the return value is dead, replace any uses of it with poison971 // (any non-debug value uses will get removed later on).972 CB.replaceAllUsesWith(PoisonValue::get(CB.getType()));973 } else {974 assert((RetTy->isStructTy() || RetTy->isArrayTy()) &&975 "Return type changed, but not into a void. The old return type"976 " must have been a struct or an array!");977 Instruction *InsertPt = &CB;978 if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {979 BasicBlock *NewEdge =980 SplitEdge(NewCB->getParent(), II->getNormalDest());981 InsertPt = &*NewEdge->getFirstInsertionPt();982 }983 984 // We used to return a struct or array. Instead of doing smart stuff985 // with all the uses, we will just rebuild it using extract/insertvalue986 // chaining and let instcombine clean that up.987 //988 // Start out building up our return value from poison989 Value *RetVal = PoisonValue::get(RetTy);990 for (unsigned Ri = 0; Ri != RetCount; ++Ri)991 if (NewRetIdxs[Ri] != -1) {992 Value *V;993 IRBuilder<NoFolder> IRB(InsertPt);994 if (RetTypes.size() > 1)995 // We are still returning a struct, so extract the value from our996 // return value997 V = IRB.CreateExtractValue(NewCB, NewRetIdxs[Ri], "newret");998 else999 // We are now returning a single element, so just insert that1000 V = NewCB;1001 // Insert the value at the old position1002 RetVal = IRB.CreateInsertValue(RetVal, V, Ri, "oldret");1003 }1004 // Now, replace all uses of the old call instruction with the return1005 // struct we built1006 CB.replaceAllUsesWith(RetVal);1007 NewCB->takeName(&CB);1008 }1009 }1010 1011 // Finally, remove the old call from the program, reducing the use-count of1012 // F.1013 CB.eraseFromParent();1014 }1015 1016 // Since we have now created the new function, splice the body of the old1017 // function right into the new function, leaving the old rotting hulk of the1018 // function empty.1019 NF->splice(NF->begin(), F);1020 1021 // Loop over the argument list, transferring uses of the old arguments over to1022 // the new arguments, also transferring over the names as well.1023 ArgI = 0;1024 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),1025 I2 = NF->arg_begin();1026 I != E; ++I, ++ArgI)1027 if (ArgAlive[ArgI]) {1028 // If this is a live argument, move the name and users over to the new1029 // version.1030 I->replaceAllUsesWith(&*I2);1031 I2->takeName(&*I);1032 ++I2;1033 } else {1034 // If this argument is dead, replace any uses of it with poison1035 // (any non-debug value uses will get removed later on).1036 I->replaceAllUsesWith(PoisonValue::get(I->getType()));1037 }1038 1039 // If we change the return value of the function we must rewrite any return1040 // instructions. Check this now.1041 if (F->getReturnType() != NF->getReturnType())1042 for (BasicBlock &BB : *NF)1043 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {1044 IRBuilder<NoFolder> IRB(RI);1045 Value *RetVal = nullptr;1046 1047 if (!NFTy->getReturnType()->isVoidTy()) {1048 assert(RetTy->isStructTy() || RetTy->isArrayTy());1049 // The original return value was a struct or array, insert1050 // extractvalue/insertvalue chains to extract only the values we need1051 // to return and insert them into our new result.1052 // This does generate messy code, but we'll let it to instcombine to1053 // clean that up.1054 Value *OldRet = RI->getOperand(0);1055 // Start out building up our return value from poison1056 RetVal = PoisonValue::get(NRetTy);1057 for (unsigned RetI = 0; RetI != RetCount; ++RetI)1058 if (NewRetIdxs[RetI] != -1) {1059 Value *EV = IRB.CreateExtractValue(OldRet, RetI, "oldret");1060 1061 if (RetTypes.size() > 1) {1062 // We're still returning a struct, so reinsert the value into1063 // our new return value at the new index1064 1065 RetVal = IRB.CreateInsertValue(RetVal, EV, NewRetIdxs[RetI],1066 "newret");1067 } else {1068 // We are now only returning a simple value, so just return the1069 // extracted value.1070 RetVal = EV;1071 }1072 }1073 }1074 // Replace the return instruction with one returning the new return1075 // value (possibly 0 if we became void).1076 auto *NewRet =1077 ReturnInst::Create(F->getContext(), RetVal, RI->getIterator());1078 NewRet->setDebugLoc(RI->getDebugLoc());1079 RI->eraseFromParent();1080 }1081 1082 // Clone metadata from the old function, including debug info descriptor.1083 SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;1084 F->getAllMetadata(MDs);1085 for (auto [KindID, Node] : MDs)1086 NF->addMetadata(KindID, *Node);1087 1088 // If either the return value(s) or argument(s) are removed, then probably the1089 // function does not follow standard calling conventions anymore. Hence, add1090 // DW_CC_nocall to DISubroutineType to inform debugger that it may not be safe1091 // to call this function or try to interpret the return value.1092 if (NFTy != FTy && NF->getSubprogram()) {1093 DISubprogram *SP = NF->getSubprogram();1094 auto Temp = SP->getType()->cloneWithCC(llvm::dwarf::DW_CC_nocall);1095 SP->replaceType(MDNode::replaceWithPermanent(std::move(Temp)));1096 }1097 1098 // Now that the old function is dead, delete it.1099 F->eraseFromParent();1100 1101 return true;1102}1103 1104PreservedAnalyses DeadArgumentEliminationPass::run(Module &M,1105 ModuleAnalysisManager &) {1106 bool Changed = false;1107 1108 // First pass: Do a simple check to see if any functions can have their "..."1109 // removed. We can do this if they never call va_start. This loop cannot be1110 // fused with the next loop, because deleting a function invalidates1111 // information computed while surveying other functions.1112 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n");1113 for (Function &F : llvm::make_early_inc_range(M))1114 if (F.getFunctionType()->isVarArg())1115 Changed |= deleteDeadVarargs(F);1116 1117 // Second phase: Loop through the module, determining which arguments are1118 // live. We assume all arguments are dead unless proven otherwise (allowing us1119 // to determine that dead arguments passed into recursive functions are dead).1120 LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n");1121 for (auto &F : M)1122 surveyFunction(F);1123 1124 // Now, remove all dead arguments and return values from each function in1125 // turn. We use make_early_inc_range here because functions will probably get1126 // removed (i.e. replaced by new ones).1127 for (Function &F : llvm::make_early_inc_range(M))1128 Changed |= removeDeadStuffFromFunction(&F);1129 1130 // Finally, look for any unused parameters in functions with non-local1131 // linkage and replace the passed in parameters with poison.1132 for (auto &F : M)1133 Changed |= removeDeadArgumentsFromCallers(F);1134 1135 if (!Changed)1136 return PreservedAnalyses::all();1137 return PreservedAnalyses::none();1138}1139