1327952Sdim//===- DeadArgumentElimination.cpp - Eliminate dead arguments -------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This pass deletes dead arguments from internal functions. Dead argument 10193323Sed// elimination removes arguments which are directly dead, as well as arguments 11193323Sed// only passed into function calls as dead arguments of other functions. This 12193323Sed// pass also deletes dead return values in a similar way. 13193323Sed// 14193323Sed// This pass is often useful as a cleanup pass to run after aggressive 15193323Sed// interprocedural passes, which add possibly-dead arguments or return values. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19309124Sdim#include "llvm/Transforms/IPO/DeadArgumentElimination.h" 20249423Sdim#include "llvm/ADT/SmallVector.h" 21249423Sdim#include "llvm/ADT/Statistic.h" 22327952Sdim#include "llvm/IR/Argument.h" 23327952Sdim#include "llvm/IR/Attributes.h" 24327952Sdim#include "llvm/IR/BasicBlock.h" 25276479Sdim#include "llvm/IR/CallSite.h" 26327952Sdim#include "llvm/IR/Constants.h" 27249423Sdim#include "llvm/IR/DerivedTypes.h" 28327952Sdim#include "llvm/IR/Function.h" 29327952Sdim#include "llvm/IR/InstrTypes.h" 30327952Sdim#include "llvm/IR/Instruction.h" 31249423Sdim#include "llvm/IR/Instructions.h" 32249423Sdim#include "llvm/IR/IntrinsicInst.h" 33327952Sdim#include "llvm/IR/Intrinsics.h" 34249423Sdim#include "llvm/IR/Module.h" 35327952Sdim#include "llvm/IR/PassManager.h" 36327952Sdim#include "llvm/IR/Type.h" 37327952Sdim#include "llvm/IR/Use.h" 38327952Sdim#include "llvm/IR/User.h" 39327952Sdim#include "llvm/IR/Value.h" 40360784Sdim#include "llvm/InitializePasses.h" 41193323Sed#include "llvm/Pass.h" 42327952Sdim#include "llvm/Support/Casting.h" 43193323Sed#include "llvm/Support/Debug.h" 44198090Srdivacky#include "llvm/Support/raw_ostream.h" 45309124Sdim#include "llvm/Transforms/IPO.h" 46296417Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 47327952Sdim#include <cassert> 48327952Sdim#include <cstdint> 49327952Sdim#include <utility> 50327952Sdim#include <vector> 51327952Sdim 52193323Sedusing namespace llvm; 53193323Sed 54276479Sdim#define DEBUG_TYPE "deadargelim" 55276479Sdim 56193323SedSTATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 57193323SedSTATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 58341825SdimSTATISTIC(NumArgumentsReplacedWithUndef, 59218893Sdim "Number of unread args replaced with undef"); 60327952Sdim 61193323Sednamespace { 62327952Sdim 63193323Sed /// DAE - The dead argument elimination pass. 64198892Srdivacky class DAE : public ModulePass { 65210299Sed protected: 66210299Sed // DAH uses this to specify a different ID. 67212904Sdim explicit DAE(char &ID) : ModulePass(ID) {} 68210299Sed 69193323Sed public: 70193323Sed static char ID; // Pass identification, replacement for typeid 71327952Sdim 72218893Sdim DAE() : ModulePass(ID) { 73218893Sdim initializeDAEPass(*PassRegistry::getPassRegistry()); 74218893Sdim } 75210299Sed 76309124Sdim bool runOnModule(Module &M) override { 77309124Sdim if (skipModule(M)) 78309124Sdim return false; 79309124Sdim DeadArgumentEliminationPass DAEP(ShouldHackArguments()); 80309124Sdim ModuleAnalysisManager DummyMAM; 81309124Sdim PreservedAnalyses PA = DAEP.run(M, DummyMAM); 82309124Sdim return !PA.areAllPreserved(); 83309124Sdim } 84193323Sed 85193323Sed virtual bool ShouldHackArguments() const { return false; } 86193323Sed }; 87193323Sed 88327952Sdim} // end anonymous namespace 89193323Sed 90193323Sedchar DAE::ID = 0; 91327952Sdim 92218893SdimINITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) 93193323Sed 94193323Sednamespace { 95327952Sdim 96193323Sed /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 97193323Sed /// deletes arguments to functions which are external. This is only for use 98193323Sed /// by bugpoint. 99193323Sed struct DAH : public DAE { 100193323Sed static char ID; 101327952Sdim 102212904Sdim DAH() : DAE(ID) {} 103210299Sed 104276479Sdim bool ShouldHackArguments() const override { return true; } 105193323Sed }; 106193323Sed 107327952Sdim} // end anonymous namespace 108327952Sdim 109193323Sedchar DAH::ID = 0; 110327952Sdim 111341825SdimINITIALIZE_PASS(DAH, "deadarghaX0r", 112212904Sdim "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", 113218893Sdim false, false) 114193323Sed 115193323Sed/// createDeadArgEliminationPass - This pass removes arguments from functions 116193323Sed/// which are not used by the body of the function. 117193323SedModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 118327952Sdim 119193323SedModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 120193323Sed 121193323Sed/// DeleteDeadVarargs - If this is an function that takes a ... list, and if 122193323Sed/// llvm.vastart is never called, the varargs list is dead for the function. 123309124Sdimbool DeadArgumentEliminationPass::DeleteDeadVarargs(Function &Fn) { 124193323Sed assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 125193323Sed if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false; 126193323Sed 127193323Sed // Ensure that the function is only directly called. 128194178Sed if (Fn.hasAddressTaken()) 129194178Sed return false; 130193323Sed 131296417Sdim // Don't touch naked functions. The assembly might be using an argument, or 132296417Sdim // otherwise rely on the frame layout in a way that this analysis will not 133296417Sdim // see. 134296417Sdim if (Fn.hasFnAttribute(Attribute::Naked)) { 135296417Sdim return false; 136296417Sdim } 137296417Sdim 138193323Sed // Okay, we know we can transform this function if safe. Scan its body 139280031Sdim // looking for calls marked musttail or calls to llvm.vastart. 140309124Sdim for (BasicBlock &BB : Fn) { 141309124Sdim for (Instruction &I : BB) { 142309124Sdim CallInst *CI = dyn_cast<CallInst>(&I); 143280031Sdim if (!CI) 144280031Sdim continue; 145280031Sdim if (CI->isMustTailCall()) 146280031Sdim return false; 147280031Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) { 148193323Sed if (II->getIntrinsicID() == Intrinsic::vastart) 149193323Sed return false; 150193323Sed } 151193323Sed } 152193323Sed } 153193323Sed 154193323Sed // If we get here, there are no calls to llvm.vastart in the function body, 155193323Sed // remove the "..." and adjust all the calls. 156193323Sed 157193323Sed // Start by computing a new prototype for the function, which is the same as 158193323Sed // the old function, but doesn't have isVarArg set. 159226633Sdim FunctionType *FTy = Fn.getFunctionType(); 160206083Srdivacky 161327952Sdim std::vector<Type *> Params(FTy->param_begin(), FTy->param_end()); 162198090Srdivacky FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), 163198090Srdivacky Params, false); 164193323Sed unsigned NumArgs = Params.size(); 165193323Sed 166193323Sed // Create the new function body and insert it into the module... 167344779Sdim Function *NF = Function::Create(NFTy, Fn.getLinkage(), Fn.getAddressSpace()); 168193323Sed NF->copyAttributesFrom(&Fn); 169309124Sdim NF->setComdat(Fn.getComdat()); 170296417Sdim Fn.getParent()->getFunctionList().insert(Fn.getIterator(), NF); 171193323Sed NF->takeName(&Fn); 172193323Sed 173193323Sed // Loop over all of the callers of the function, transforming the call sites 174193323Sed // to pass in a smaller number of arguments into the new function. 175193323Sed // 176327952Sdim std::vector<Value *> Args; 177276479Sdim for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) { 178261991Sdim CallSite CS(*I++); 179261991Sdim if (!CS) 180261991Sdim continue; 181193323Sed Instruction *Call = CS.getInstruction(); 182193323Sed 183193323Sed // Pass all the same arguments. 184212904Sdim Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs); 185193323Sed 186193323Sed // Drop any attributes that were on the vararg arguments. 187321369Sdim AttributeList PAL = CS.getAttributes(); 188321369Sdim if (!PAL.isEmpty()) { 189321369Sdim SmallVector<AttributeSet, 8> ArgAttrs; 190321369Sdim for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) 191321369Sdim ArgAttrs.push_back(PAL.getParamAttributes(ArgNo)); 192321369Sdim PAL = AttributeList::get(Fn.getContext(), PAL.getFnAttributes(), 193321369Sdim PAL.getRetAttributes(), ArgAttrs); 194193323Sed } 195193323Sed 196309124Sdim SmallVector<OperandBundleDef, 1> OpBundles; 197309124Sdim CS.getOperandBundlesAsDefs(OpBundles); 198309124Sdim 199321369Sdim CallSite NewCS; 200193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 201321369Sdim NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 202321369Sdim Args, OpBundles, "", Call); 203193323Sed } else { 204321369Sdim NewCS = CallInst::Create(NF, Args, OpBundles, "", Call); 205321369Sdim cast<CallInst>(NewCS.getInstruction()) 206321369Sdim ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind()); 207193323Sed } 208321369Sdim NewCS.setCallingConv(CS.getCallingConv()); 209321369Sdim NewCS.setAttributes(PAL); 210321369Sdim NewCS->setDebugLoc(Call->getDebugLoc()); 211321369Sdim uint64_t W; 212321369Sdim if (Call->extractProfTotalWeight(W)) 213321369Sdim NewCS->setProfWeight(W); 214207618Srdivacky 215193323Sed Args.clear(); 216193323Sed 217193323Sed if (!Call->use_empty()) 218321369Sdim Call->replaceAllUsesWith(NewCS.getInstruction()); 219193323Sed 220321369Sdim NewCS->takeName(Call); 221193323Sed 222193323Sed // Finally, remove the old call from the program, reducing the use-count of 223193323Sed // F. 224193323Sed Call->eraseFromParent(); 225193323Sed } 226193323Sed 227193323Sed // Since we have now created the new function, splice the body of the old 228193323Sed // function right into the new function, leaving the old rotting hulk of the 229193323Sed // function empty. 230193323Sed NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 231193323Sed 232221345Sdim // Loop over the argument list, transferring uses of the old arguments over to 233221345Sdim // the new arguments, also transferring over the names as well. While we're at 234193323Sed // it, remove the dead arguments from the DeadArguments list. 235193323Sed for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 236193323Sed I2 = NF->arg_begin(); I != E; ++I, ++I2) { 237193323Sed // Move the name and users over to the new version. 238296417Sdim I->replaceAllUsesWith(&*I2); 239296417Sdim I2->takeName(&*I); 240193323Sed } 241193323Sed 242341825Sdim // Clone metadatas from the old function, including debug info descriptor. 243341825Sdim SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 244341825Sdim Fn.getAllMetadata(MDs); 245341825Sdim for (auto MD : MDs) 246341825Sdim NF->addMetadata(MD.first, *MD.second); 247243830Sdim 248261991Sdim // Fix up any BlockAddresses that refer to the function. 249261991Sdim Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType())); 250261991Sdim // Delete the bitcast that we just created, so that NF does not 251261991Sdim // appear to be address-taken. 252261991Sdim NF->removeDeadConstantUsers(); 253193323Sed // Finally, nuke the old function. 254193323Sed Fn.eraseFromParent(); 255193323Sed return true; 256193323Sed} 257193323Sed 258341825Sdim/// RemoveDeadArgumentsFromCallers - Checks if the given function has any 259218893Sdim/// arguments that are unused, and changes the caller parameters to be undefined 260218893Sdim/// instead. 261309124Sdimbool DeadArgumentEliminationPass::RemoveDeadArgumentsFromCallers(Function &Fn) { 262288943Sdim // We cannot change the arguments if this TU does not define the function or 263288943Sdim // if the linker may choose a function body from another TU, even if the 264288943Sdim // nominal linkage indicates that other copies of the function have the same 265288943Sdim // semantics. In the below example, the dead load from %p may not have been 266288943Sdim // eliminated from the linker-chosen copy of f, so replacing %p with undef 267288943Sdim // in callers may introduce undefined behavior. 268288943Sdim // 269288943Sdim // define linkonce_odr void @f(i32* %p) { 270288943Sdim // %v = load i32 %p 271288943Sdim // ret void 272288943Sdim // } 273309124Sdim if (!Fn.hasExactDefinition()) 274218893Sdim return false; 275218893Sdim 276261991Sdim // Functions with local linkage should already have been handled, except the 277261991Sdim // fragile (variadic) ones which we can improve here. 278261991Sdim if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg()) 279218893Sdim return false; 280218893Sdim 281296417Sdim // Don't touch naked functions. The assembly might be using an argument, or 282296417Sdim // otherwise rely on the frame layout in a way that this analysis will not 283296417Sdim // see. 284296417Sdim if (Fn.hasFnAttribute(Attribute::Naked)) 285296417Sdim return false; 286296417Sdim 287218893Sdim if (Fn.use_empty()) 288218893Sdim return false; 289218893Sdim 290249423Sdim SmallVector<unsigned, 8> UnusedArgs; 291344779Sdim bool Changed = false; 292344779Sdim 293296417Sdim for (Argument &Arg : Fn.args()) { 294344779Sdim if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() && !Arg.hasByValOrInAllocaAttr()) { 295344779Sdim if (Arg.isUsedByMetadata()) { 296344779Sdim Arg.replaceAllUsesWith(UndefValue::get(Arg.getType())); 297344779Sdim Changed = true; 298344779Sdim } 299296417Sdim UnusedArgs.push_back(Arg.getArgNo()); 300344779Sdim } 301218893Sdim } 302218893Sdim 303218893Sdim if (UnusedArgs.empty()) 304218893Sdim return false; 305218893Sdim 306276479Sdim for (Use &U : Fn.uses()) { 307276479Sdim CallSite CS(U.getUser()); 308276479Sdim if (!CS || !CS.isCallee(&U)) 309218893Sdim continue; 310218893Sdim 311218893Sdim // Now go through all unused args and replace them with "undef". 312218893Sdim for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { 313218893Sdim unsigned ArgNo = UnusedArgs[I]; 314218893Sdim 315218893Sdim Value *Arg = CS.getArgument(ArgNo); 316218893Sdim CS.setArgument(ArgNo, UndefValue::get(Arg->getType())); 317218893Sdim ++NumArgumentsReplacedWithUndef; 318218893Sdim Changed = true; 319218893Sdim } 320218893Sdim } 321218893Sdim 322218893Sdim return Changed; 323218893Sdim} 324218893Sdim 325193323Sed/// Convenience function that returns the number of return values. It returns 0 326193323Sed/// for void functions and 1 for functions not returning a struct. It returns 327193323Sed/// the number of struct elements for functions returning a struct. 328193323Sedstatic unsigned NumRetVals(const Function *F) { 329288943Sdim Type *RetTy = F->getReturnType(); 330288943Sdim if (RetTy->isVoidTy()) 331193323Sed return 0; 332288943Sdim else if (StructType *STy = dyn_cast<StructType>(RetTy)) 333193323Sed return STy->getNumElements(); 334288943Sdim else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 335288943Sdim return ATy->getNumElements(); 336193323Sed else 337193323Sed return 1; 338193323Sed} 339193323Sed 340288943Sdim/// Returns the sub-type a function will return at a given Idx. Should 341288943Sdim/// correspond to the result type of an ExtractValue instruction executed with 342288943Sdim/// just that one Idx (i.e. only top-level structure is considered). 343288943Sdimstatic Type *getRetComponentType(const Function *F, unsigned Idx) { 344288943Sdim Type *RetTy = F->getReturnType(); 345288943Sdim assert(!RetTy->isVoidTy() && "void type has no subtype"); 346288943Sdim 347288943Sdim if (StructType *STy = dyn_cast<StructType>(RetTy)) 348288943Sdim return STy->getElementType(Idx); 349288943Sdim else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 350288943Sdim return ATy->getElementType(); 351288943Sdim else 352288943Sdim return RetTy; 353288943Sdim} 354288943Sdim 355193323Sed/// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not 356193323Sed/// live, it adds Use to the MaybeLiveUses argument. Returns the determined 357193323Sed/// liveness of Use. 358309124SdimDeadArgumentEliminationPass::Liveness 359309124SdimDeadArgumentEliminationPass::MarkIfNotLive(RetOrArg Use, 360309124Sdim UseVector &MaybeLiveUses) { 361193323Sed // We're live if our use or its Function is already marked as live. 362193323Sed if (LiveFunctions.count(Use.F) || LiveValues.count(Use)) 363193323Sed return Live; 364193323Sed 365193323Sed // We're maybe live otherwise, but remember that we must become live if 366193323Sed // Use becomes live. 367193323Sed MaybeLiveUses.push_back(Use); 368193323Sed return MaybeLive; 369193323Sed} 370193323Sed 371193323Sed/// SurveyUse - This looks at a single use of an argument or return value 372193323Sed/// and determines if it should be alive or not. Adds this use to MaybeLiveUses 373206083Srdivacky/// if it causes the used value to become MaybeLive. 374193323Sed/// 375193323Sed/// RetValNum is the return value number to use when this use is used in a 376193323Sed/// return instruction. This is used in the recursion, you should always leave 377193323Sed/// it at 0. 378309124SdimDeadArgumentEliminationPass::Liveness 379309124SdimDeadArgumentEliminationPass::SurveyUse(const Use *U, UseVector &MaybeLiveUses, 380309124Sdim unsigned RetValNum) { 381276479Sdim const User *V = U->getUser(); 382206083Srdivacky if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { 383193323Sed // The value is returned from a function. It's only live when the 384193323Sed // function's return value is live. We use RetValNum here, for the case 385193323Sed // that U is really a use of an insertvalue instruction that uses the 386221345Sdim // original Use. 387288943Sdim const Function *F = RI->getParent()->getParent(); 388288943Sdim if (RetValNum != -1U) { 389288943Sdim RetOrArg Use = CreateRet(F, RetValNum); 390288943Sdim // We might be live, depending on the liveness of Use. 391288943Sdim return MarkIfNotLive(Use, MaybeLiveUses); 392288943Sdim } else { 393309124Sdim DeadArgumentEliminationPass::Liveness Result = MaybeLive; 394288943Sdim for (unsigned i = 0; i < NumRetVals(F); ++i) { 395288943Sdim RetOrArg Use = CreateRet(F, i); 396288943Sdim // We might be live, depending on the liveness of Use. If any 397288943Sdim // sub-value is live, then the entire value is considered live. This 398288943Sdim // is a conservative choice, and better tracking is possible. 399309124Sdim DeadArgumentEliminationPass::Liveness SubResult = 400309124Sdim MarkIfNotLive(Use, MaybeLiveUses); 401288943Sdim if (Result != Live) 402288943Sdim Result = SubResult; 403288943Sdim } 404288943Sdim return Result; 405288943Sdim } 406193323Sed } 407206083Srdivacky if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 408276479Sdim if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex() 409193323Sed && IV->hasIndices()) 410193323Sed // The use we are examining is inserted into an aggregate. Our liveness 411193323Sed // depends on all uses of that aggregate, but if it is used as a return 412193323Sed // value, only index at which we were inserted counts. 413193323Sed RetValNum = *IV->idx_begin(); 414193323Sed 415193323Sed // Note that if we are used as the aggregate operand to the insertvalue, 416193323Sed // we don't change RetValNum, but do survey all our uses. 417193323Sed 418193323Sed Liveness Result = MaybeLive; 419276479Sdim for (const Use &UU : IV->uses()) { 420276479Sdim Result = SurveyUse(&UU, MaybeLiveUses, RetValNum); 421193323Sed if (Result == Live) 422193323Sed break; 423193323Sed } 424193323Sed return Result; 425193323Sed } 426206083Srdivacky 427288943Sdim if (auto CS = ImmutableCallSite(V)) { 428206083Srdivacky const Function *F = CS.getCalledFunction(); 429193323Sed if (F) { 430193323Sed // Used in a direct call. 431206083Srdivacky 432296417Sdim // The function argument is live if it is used as a bundle operand. 433296417Sdim if (CS.isBundleOperand(U)) 434296417Sdim return Live; 435296417Sdim 436193323Sed // Find the argument number. We know for sure that this use is an 437193323Sed // argument, since if it was the function argument this would be an 438193323Sed // indirect call and the we know can't be looking at a value of the 439193323Sed // label type (for the invoke instruction). 440206083Srdivacky unsigned ArgNo = CS.getArgumentNo(U); 441193323Sed 442193323Sed if (ArgNo >= F->getFunctionType()->getNumParams()) 443193323Sed // The value is passed in through a vararg! Must be live. 444193323Sed return Live; 445193323Sed 446206083Srdivacky assert(CS.getArgument(ArgNo) 447276479Sdim == CS->getOperand(U->getOperandNo()) 448193323Sed && "Argument is not where we expected it"); 449193323Sed 450193323Sed // Value passed to a normal call. It's only live when the corresponding 451193323Sed // argument to the called function turns out live. 452193323Sed RetOrArg Use = CreateArg(F, ArgNo); 453193323Sed return MarkIfNotLive(Use, MaybeLiveUses); 454193323Sed } 455193323Sed } 456193323Sed // Used in any other way? Value must be live. 457193323Sed return Live; 458193323Sed} 459193323Sed 460193323Sed/// SurveyUses - This looks at all the uses of the given value 461193323Sed/// Returns the Liveness deduced from the uses of this value. 462193323Sed/// 463193323Sed/// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If 464193323Sed/// the result is Live, MaybeLiveUses might be modified but its content should 465193323Sed/// be ignored (since it might not be complete). 466309124SdimDeadArgumentEliminationPass::Liveness 467309124SdimDeadArgumentEliminationPass::SurveyUses(const Value *V, 468309124Sdim UseVector &MaybeLiveUses) { 469193323Sed // Assume it's dead (which will only hold if there are no uses at all..). 470193323Sed Liveness Result = MaybeLive; 471193323Sed // Check each use. 472276479Sdim for (const Use &U : V->uses()) { 473276479Sdim Result = SurveyUse(&U, MaybeLiveUses); 474193323Sed if (Result == Live) 475193323Sed break; 476193323Sed } 477193323Sed return Result; 478193323Sed} 479193323Sed 480193323Sed// SurveyFunction - This performs the initial survey of the specified function, 481193323Sed// checking out whether or not it uses any of its incoming arguments or whether 482193323Sed// any callers use the return value. This fills in the LiveValues set and Uses 483193323Sed// map. 484193323Sed// 485193323Sed// We consider arguments of non-internal functions to be intrinsically alive as 486193323Sed// well as arguments to functions which have their "address taken". 487309124Sdimvoid DeadArgumentEliminationPass::SurveyFunction(const Function &F) { 488276479Sdim // Functions with inalloca parameters are expecting args in a particular 489276479Sdim // register and memory layout. 490276479Sdim if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) { 491276479Sdim MarkLive(F); 492276479Sdim return; 493276479Sdim } 494276479Sdim 495296417Sdim // Don't touch naked functions. The assembly might be using an argument, or 496296417Sdim // otherwise rely on the frame layout in a way that this analysis will not 497296417Sdim // see. 498296417Sdim if (F.hasFnAttribute(Attribute::Naked)) { 499296417Sdim MarkLive(F); 500296417Sdim return; 501296417Sdim } 502296417Sdim 503193323Sed unsigned RetCount = NumRetVals(&F); 504327952Sdim 505193323Sed // Assume all return values are dead 506327952Sdim using RetVals = SmallVector<Liveness, 5>; 507327952Sdim 508193323Sed RetVals RetValLiveness(RetCount, MaybeLive); 509193323Sed 510327952Sdim using RetUses = SmallVector<UseVector, 5>; 511327952Sdim 512193323Sed // These vectors map each return value to the uses that make it MaybeLive, so 513193323Sed // we can add those to the Uses map if the return value really turns out to be 514193323Sed // MaybeLive. Initialized to a list of RetCount empty lists. 515193323Sed RetUses MaybeLiveRetUses(RetCount); 516193323Sed 517335799Sdim bool HasMustTailCalls = false; 518335799Sdim 519335799Sdim for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 520335799Sdim if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 521193323Sed if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 522193323Sed != F.getFunctionType()->getReturnType()) { 523193323Sed // We don't support old style multiple return values. 524193323Sed MarkLive(F); 525193323Sed return; 526193323Sed } 527335799Sdim } 528193323Sed 529335799Sdim // If we have any returns of `musttail` results - the signature can't 530335799Sdim // change 531335799Sdim if (BB->getTerminatingMustTailCall() != nullptr) 532335799Sdim HasMustTailCalls = true; 533335799Sdim } 534335799Sdim 535335799Sdim if (HasMustTailCalls) { 536341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 537341825Sdim << " has musttail calls\n"); 538335799Sdim } 539335799Sdim 540309124Sdim if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { 541193323Sed MarkLive(F); 542193323Sed return; 543193323Sed } 544193323Sed 545341825Sdim LLVM_DEBUG( 546341825Sdim dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: " 547341825Sdim << F.getName() << "\n"); 548193323Sed // Keep track of the number of live retvals, so we can skip checks once all 549193323Sed // of them turn out to be live. 550193323Sed unsigned NumLiveRetVals = 0; 551335799Sdim 552335799Sdim bool HasMustTailCallers = false; 553335799Sdim 554193323Sed // Loop all uses of the function. 555276479Sdim for (const Use &U : F.uses()) { 556193323Sed // If the function is PASSED IN as an argument, its address has been 557193323Sed // taken. 558276479Sdim ImmutableCallSite CS(U.getUser()); 559276479Sdim if (!CS || !CS.isCallee(&U)) { 560193323Sed MarkLive(F); 561193323Sed return; 562193323Sed } 563193323Sed 564335799Sdim // The number of arguments for `musttail` call must match the number of 565335799Sdim // arguments of the caller 566335799Sdim if (CS.isMustTailCall()) 567335799Sdim HasMustTailCallers = true; 568335799Sdim 569193323Sed // If this use is anything other than a call site, the function is alive. 570206083Srdivacky const Instruction *TheCall = CS.getInstruction(); 571193323Sed if (!TheCall) { // Not a direct call site? 572193323Sed MarkLive(F); 573193323Sed return; 574193323Sed } 575193323Sed 576193323Sed // If we end up here, we are looking at a direct call to our function. 577193323Sed 578193323Sed // Now, check how our return value(s) is/are used in this caller. Don't 579193323Sed // bother checking return values if all of them are live already. 580288943Sdim if (NumLiveRetVals == RetCount) 581288943Sdim continue; 582288943Sdim 583288943Sdim // Check all uses of the return value. 584288943Sdim for (const Use &U : TheCall->uses()) { 585288943Sdim if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) { 586288943Sdim // This use uses a part of our return value, survey the uses of 587288943Sdim // that part and store the results for this index only. 588288943Sdim unsigned Idx = *Ext->idx_begin(); 589288943Sdim if (RetValLiveness[Idx] != Live) { 590288943Sdim RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 591288943Sdim if (RetValLiveness[Idx] == Live) 592288943Sdim NumLiveRetVals++; 593193323Sed } 594193323Sed } else { 595288943Sdim // Used by something else than extractvalue. Survey, but assume that the 596288943Sdim // result applies to all sub-values. 597288943Sdim UseVector MaybeLiveAggregateUses; 598288943Sdim if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) { 599193323Sed NumLiveRetVals = RetCount; 600288943Sdim RetValLiveness.assign(RetCount, Live); 601288943Sdim break; 602288943Sdim } else { 603288943Sdim for (unsigned i = 0; i != RetCount; ++i) { 604288943Sdim if (RetValLiveness[i] != Live) 605288943Sdim MaybeLiveRetUses[i].append(MaybeLiveAggregateUses.begin(), 606288943Sdim MaybeLiveAggregateUses.end()); 607288943Sdim } 608288943Sdim } 609193323Sed } 610193323Sed } 611193323Sed } 612193323Sed 613335799Sdim if (HasMustTailCallers) { 614341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 615341825Sdim << " has musttail callers\n"); 616335799Sdim } 617335799Sdim 618193323Sed // Now we've inspected all callers, record the liveness of our return values. 619193323Sed for (unsigned i = 0; i != RetCount; ++i) 620193323Sed MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]); 621193323Sed 622341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: " 623341825Sdim << F.getName() << "\n"); 624193323Sed 625193323Sed // Now, check all of our arguments. 626193323Sed unsigned i = 0; 627193323Sed UseVector MaybeLiveArgUses; 628206083Srdivacky for (Function::const_arg_iterator AI = F.arg_begin(), 629193323Sed E = F.arg_end(); AI != E; ++AI, ++i) { 630261991Sdim Liveness Result; 631335799Sdim if (F.getFunctionType()->isVarArg() || HasMustTailCallers || 632335799Sdim HasMustTailCalls) { 633261991Sdim // Variadic functions will already have a va_arg function expanded inside 634261991Sdim // them, making them potentially very sensitive to ABI changes resulting 635261991Sdim // from removing arguments entirely, so don't. For example AArch64 handles 636261991Sdim // register and stack HFAs very differently, and this is reflected in the 637261991Sdim // IR which has already been generated. 638335799Sdim // 639335799Sdim // `musttail` calls to this function restrict argument removal attempts. 640335799Sdim // The signature of the caller must match the signature of the function. 641335799Sdim // 642335799Sdim // `musttail` calls in this function prevents us from changing its 643335799Sdim // signature 644261991Sdim Result = Live; 645261991Sdim } else { 646261991Sdim // See what the effect of this use is (recording any uses that cause 647341825Sdim // MaybeLive in MaybeLiveArgUses). 648296417Sdim Result = SurveyUses(&*AI, MaybeLiveArgUses); 649261991Sdim } 650261991Sdim 651193323Sed // Mark the result. 652193323Sed MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses); 653193323Sed // Clear the vector again for the next iteration. 654193323Sed MaybeLiveArgUses.clear(); 655193323Sed } 656193323Sed} 657193323Sed 658193323Sed/// MarkValue - This function marks the liveness of RA depending on L. If L is 659193323Sed/// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, 660193323Sed/// such that RA will be marked live if any use in MaybeLiveUses gets marked 661193323Sed/// live later on. 662309124Sdimvoid DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L, 663309124Sdim const UseVector &MaybeLiveUses) { 664193323Sed switch (L) { 665327952Sdim case Live: 666327952Sdim MarkLive(RA); 667327952Sdim break; 668193323Sed case MaybeLive: 669193323Sed // Note any uses of this value, so this return value can be 670193323Sed // marked live whenever one of the uses becomes live. 671309124Sdim for (const auto &MaybeLiveUse : MaybeLiveUses) 672309124Sdim Uses.insert(std::make_pair(MaybeLiveUse, RA)); 673193323Sed break; 674193323Sed } 675193323Sed} 676193323Sed 677193323Sed/// MarkLive - Mark the given Function as alive, meaning that it cannot be 678193323Sed/// changed in any way. Additionally, 679193323Sed/// mark any values that are used as this function's parameters or by its return 680193323Sed/// values (according to Uses) live as well. 681309124Sdimvoid DeadArgumentEliminationPass::MarkLive(const Function &F) { 682341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: " 683341825Sdim << F.getName() << "\n"); 684208599Srdivacky // Mark the function as live. 685208599Srdivacky LiveFunctions.insert(&F); 686208599Srdivacky // Mark all arguments as live. 687208599Srdivacky for (unsigned i = 0, e = F.arg_size(); i != e; ++i) 688208599Srdivacky PropagateLiveness(CreateArg(&F, i)); 689208599Srdivacky // Mark all return values as live. 690208599Srdivacky for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i) 691208599Srdivacky PropagateLiveness(CreateRet(&F, i)); 692193323Sed} 693193323Sed 694193323Sed/// MarkLive - Mark the given return value or argument as live. Additionally, 695193323Sed/// mark any values that are used by this value (according to Uses) live as 696193323Sed/// well. 697309124Sdimvoid DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) { 698193323Sed if (LiveFunctions.count(RA.F)) 699193323Sed return; // Function was already marked Live. 700193323Sed 701193323Sed if (!LiveValues.insert(RA).second) 702193323Sed return; // We were already marked Live. 703193323Sed 704341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking " 705341825Sdim << RA.getDescription() << " live\n"); 706193323Sed PropagateLiveness(RA); 707193323Sed} 708193323Sed 709193323Sed/// PropagateLiveness - Given that RA is a live value, propagate it's liveness 710193323Sed/// to any other values it uses (according to Uses). 711309124Sdimvoid DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) { 712193323Sed // We don't use upper_bound (or equal_range) here, because our recursive call 713193323Sed // to ourselves is likely to cause the upper_bound (which is the first value 714193323Sed // not belonging to RA) to become erased and the iterator invalidated. 715193323Sed UseMap::iterator Begin = Uses.lower_bound(RA); 716193323Sed UseMap::iterator E = Uses.end(); 717193323Sed UseMap::iterator I; 718193323Sed for (I = Begin; I != E && I->first == RA; ++I) 719193323Sed MarkLive(I->second); 720193323Sed 721193323Sed // Erase RA from the Uses map (from the lower bound to wherever we ended up 722193323Sed // after the loop). 723193323Sed Uses.erase(Begin, I); 724193323Sed} 725193323Sed 726193323Sed// RemoveDeadStuffFromFunction - Remove any arguments and return values from F 727193323Sed// that are not in LiveValues. Transform the function and all of the callees of 728193323Sed// the function to not have these arguments and return values. 729193323Sed// 730309124Sdimbool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) { 731193323Sed // Don't modify fully live functions 732193323Sed if (LiveFunctions.count(F)) 733193323Sed return false; 734193323Sed 735193323Sed // Start by computing a new prototype for the function, which is the same as 736193323Sed // the old function, but has fewer arguments and a different return type. 737226633Sdim FunctionType *FTy = F->getFunctionType(); 738224145Sdim std::vector<Type*> Params; 739193323Sed 740261991Sdim // Keep track of if we have a live 'returned' argument 741261991Sdim bool HasLiveReturnedArg = false; 742261991Sdim 743193323Sed // Set up to build a new list of parameter attributes. 744321369Sdim SmallVector<AttributeSet, 8> ArgAttrVec; 745321369Sdim const AttributeList &PAL = F->getAttributes(); 746193323Sed 747261991Sdim // Remember which arguments are still alive. 748261991Sdim SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 749261991Sdim // Construct the new parameter list from non-dead arguments. Also construct 750261991Sdim // a new set of parameter attributes to correspond. Skip the first parameter 751261991Sdim // attribute, since that belongs to the return value. 752261991Sdim unsigned i = 0; 753261991Sdim for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 754261991Sdim I != E; ++I, ++i) { 755261991Sdim RetOrArg Arg = CreateArg(F, i); 756261991Sdim if (LiveValues.erase(Arg)) { 757261991Sdim Params.push_back(I->getType()); 758261991Sdim ArgAlive[i] = true; 759321369Sdim ArgAttrVec.push_back(PAL.getParamAttributes(i)); 760321369Sdim HasLiveReturnedArg |= PAL.hasParamAttribute(i, Attribute::Returned); 761261991Sdim } else { 762261991Sdim ++NumArgumentsEliminated; 763341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument " 764341825Sdim << i << " (" << I->getName() << ") from " 765341825Sdim << F->getName() << "\n"); 766261991Sdim } 767261991Sdim } 768261991Sdim 769193323Sed // Find out the new return value. 770224145Sdim Type *RetTy = FTy->getReturnType(); 771276479Sdim Type *NRetTy = nullptr; 772193323Sed unsigned RetCount = NumRetVals(F); 773206083Srdivacky 774193323Sed // -1 means unused, other numbers are the new index 775193323Sed SmallVector<int, 5> NewRetIdxs(RetCount, -1); 776224145Sdim std::vector<Type*> RetTypes; 777261991Sdim 778261991Sdim // If there is a function with a live 'returned' argument but a dead return 779261991Sdim // value, then there are two possible actions: 780261991Sdim // 1) Eliminate the return value and take off the 'returned' attribute on the 781261991Sdim // argument. 782261991Sdim // 2) Retain the 'returned' attribute and treat the return value (but not the 783261991Sdim // entire function) as live so that it is not eliminated. 784341825Sdim // 785261991Sdim // It's not clear in the general case which option is more profitable because, 786261991Sdim // even in the absence of explicit uses of the return value, code generation 787261991Sdim // is free to use the 'returned' attribute to do things like eliding 788261991Sdim // save/restores of registers across calls. Whether or not this happens is 789261991Sdim // target and ABI-specific as well as depending on the amount of register 790261991Sdim // pressure, so there's no good way for an IR-level pass to figure this out. 791261991Sdim // 792261991Sdim // Fortunately, the only places where 'returned' is currently generated by 793261991Sdim // the FE are places where 'returned' is basically free and almost always a 794261991Sdim // performance win, so the second option can just be used always for now. 795261991Sdim // 796261991Sdim // This should be revisited if 'returned' is ever applied more liberally. 797261991Sdim if (RetTy->isVoidTy() || HasLiveReturnedArg) { 798206083Srdivacky NRetTy = RetTy; 799193323Sed } else { 800288943Sdim // Look at each of the original return values individually. 801288943Sdim for (unsigned i = 0; i != RetCount; ++i) { 802288943Sdim RetOrArg Ret = CreateRet(F, i); 803288943Sdim if (LiveValues.erase(Ret)) { 804288943Sdim RetTypes.push_back(getRetComponentType(F, i)); 805288943Sdim NewRetIdxs[i] = RetTypes.size() - 1; 806193323Sed } else { 807193323Sed ++NumRetValsEliminated; 808341825Sdim LLVM_DEBUG( 809341825Sdim dbgs() << "DeadArgumentEliminationPass - Removing return value " 810341825Sdim << i << " from " << F->getName() << "\n"); 811193323Sed } 812288943Sdim } 813288943Sdim if (RetTypes.size() > 1) { 814288943Sdim // More than one return type? Reduce it down to size. 815288943Sdim if (StructType *STy = dyn_cast<StructType>(RetTy)) { 816288943Sdim // Make the new struct packed if we used to return a packed struct 817288943Sdim // already. 818288943Sdim NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); 819288943Sdim } else { 820288943Sdim assert(isa<ArrayType>(RetTy) && "unexpected multi-value return"); 821288943Sdim NRetTy = ArrayType::get(RetTypes[0], RetTypes.size()); 822288943Sdim } 823288943Sdim } else if (RetTypes.size() == 1) 824193323Sed // One return type? Just a simple value then, but only if we didn't use to 825193323Sed // return a struct with that simple value before. 826193323Sed NRetTy = RetTypes.front(); 827327952Sdim else if (RetTypes.empty()) 828193323Sed // No return types? Make it void, but only if we didn't use to return {}. 829198090Srdivacky NRetTy = Type::getVoidTy(F->getContext()); 830193323Sed } 831193323Sed 832193323Sed assert(NRetTy && "No new return type found?"); 833193323Sed 834249423Sdim // The existing function return attributes. 835321369Sdim AttrBuilder RAttrs(PAL.getRetAttributes()); 836249423Sdim 837193323Sed // Remove any incompatible attributes, but only if we removed all return 838193323Sed // values. Otherwise, ensure that we don't have any conflicting attributes 839193323Sed // here. Currently, this should not be possible, but special handling might be 840193323Sed // required when new return value attributes are added. 841206083Srdivacky if (NRetTy->isVoidTy()) 842321369Sdim RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 843193323Sed else 844321369Sdim assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) && 845243830Sdim "Return attributes no longer compatible?"); 846193323Sed 847321369Sdim AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 848193323Sed 849341825Sdim // Strip allocsize attributes. They might refer to the deleted arguments. 850341825Sdim AttributeSet FnAttrs = PAL.getFnAttributes().removeAttribute( 851341825Sdim F->getContext(), Attribute::AllocSize); 852341825Sdim 853193323Sed // Reconstruct the AttributesList based on the vector we constructed. 854321369Sdim assert(ArgAttrVec.size() == Params.size()); 855341825Sdim AttributeList NewPAL = 856341825Sdim AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 857193323Sed 858193323Sed // Create the new function type based on the recomputed parameters. 859206083Srdivacky FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 860193323Sed 861193323Sed // No change? 862193323Sed if (NFTy == FTy) 863193323Sed return false; 864193323Sed 865193323Sed // Create the new function body and insert it into the module... 866344779Sdim Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace()); 867193323Sed NF->copyAttributesFrom(F); 868309124Sdim NF->setComdat(F->getComdat()); 869193323Sed NF->setAttributes(NewPAL); 870193323Sed // Insert the new function before the old function, so we won't be processing 871193323Sed // it again. 872296417Sdim F->getParent()->getFunctionList().insert(F->getIterator(), NF); 873193323Sed NF->takeName(F); 874193323Sed 875193323Sed // Loop over all of the callers of the function, transforming the call sites 876193323Sed // to pass in a smaller number of arguments into the new function. 877193323Sed std::vector<Value*> Args; 878193323Sed while (!F->use_empty()) { 879276479Sdim CallSite CS(F->user_back()); 880193323Sed Instruction *Call = CS.getInstruction(); 881193323Sed 882321369Sdim ArgAttrVec.clear(); 883321369Sdim const AttributeList &CallPAL = CS.getAttributes(); 884193323Sed 885321369Sdim // Adjust the call return attributes in case the function was changed to 886321369Sdim // return void. 887321369Sdim AttrBuilder RAttrs(CallPAL.getRetAttributes()); 888321369Sdim RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 889321369Sdim AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 890249423Sdim 891193323Sed // Declare these outside of the loops, so we can reuse them for the second 892193323Sed // loop, which loops the varargs. 893193323Sed CallSite::arg_iterator I = CS.arg_begin(); 894193323Sed unsigned i = 0; 895193323Sed // Loop over those operands, corresponding to the normal arguments to the 896193323Sed // original function, and add those that are still alive. 897193323Sed for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i) 898193323Sed if (ArgAlive[i]) { 899193323Sed Args.push_back(*I); 900193323Sed // Get original parameter attributes, but skip return attributes. 901321369Sdim AttributeSet Attrs = CallPAL.getParamAttributes(i); 902321369Sdim if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) { 903261991Sdim // If the return type has changed, then get rid of 'returned' on the 904261991Sdim // call site. The alternative is to make all 'returned' attributes on 905261991Sdim // call sites keep the return value alive just like 'returned' 906321369Sdim // attributes on function declaration but it's less clearly a win and 907321369Sdim // this is not an expected case anyway 908321369Sdim ArgAttrVec.push_back(AttributeSet::get( 909321369Sdim F->getContext(), 910321369Sdim AttrBuilder(Attrs).removeAttribute(Attribute::Returned))); 911321369Sdim } else { 912321369Sdim // Otherwise, use the original attributes. 913321369Sdim ArgAttrVec.push_back(Attrs); 914249423Sdim } 915193323Sed } 916193323Sed 917193323Sed // Push any varargs arguments on the list. Don't forget their attributes. 918193323Sed for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { 919193323Sed Args.push_back(*I); 920321369Sdim ArgAttrVec.push_back(CallPAL.getParamAttributes(i)); 921193323Sed } 922193323Sed 923193323Sed // Reconstruct the AttributesList based on the vector we constructed. 924321369Sdim assert(ArgAttrVec.size() == Args.size()); 925341825Sdim 926341825Sdim // Again, be sure to remove any allocsize attributes, since their indices 927341825Sdim // may now be incorrect. 928341825Sdim AttributeSet FnAttrs = CallPAL.getFnAttributes().removeAttribute( 929341825Sdim F->getContext(), Attribute::AllocSize); 930341825Sdim 931321369Sdim AttributeList NewCallPAL = AttributeList::get( 932341825Sdim F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 933193323Sed 934309124Sdim SmallVector<OperandBundleDef, 1> OpBundles; 935309124Sdim CS.getOperandBundlesAsDefs(OpBundles); 936309124Sdim 937321369Sdim CallSite NewCS; 938193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 939321369Sdim NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 940321369Sdim Args, OpBundles, "", Call->getParent()); 941193323Sed } else { 942353358Sdim NewCS = CallInst::Create(NFTy, NF, Args, OpBundles, "", Call); 943321369Sdim cast<CallInst>(NewCS.getInstruction()) 944321369Sdim ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind()); 945193323Sed } 946321369Sdim NewCS.setCallingConv(CS.getCallingConv()); 947321369Sdim NewCS.setAttributes(NewCallPAL); 948321369Sdim NewCS->setDebugLoc(Call->getDebugLoc()); 949321369Sdim uint64_t W; 950321369Sdim if (Call->extractProfTotalWeight(W)) 951321369Sdim NewCS->setProfWeight(W); 952193323Sed Args.clear(); 953321369Sdim ArgAttrVec.clear(); 954193323Sed 955321369Sdim Instruction *New = NewCS.getInstruction(); 956344779Sdim if (!Call->use_empty() || Call->isUsedByMetadata()) { 957193323Sed if (New->getType() == Call->getType()) { 958193323Sed // Return type not changed? Just replace users then. 959193323Sed Call->replaceAllUsesWith(New); 960193323Sed New->takeName(Call); 961206083Srdivacky } else if (New->getType()->isVoidTy()) { 962344779Sdim // If the return value is dead, replace any uses of it with undef 963344779Sdim // (any non-debug value uses will get removed later on). 964218893Sdim if (!Call->getType()->isX86_MMXTy()) 965344779Sdim Call->replaceAllUsesWith(UndefValue::get(Call->getType())); 966193323Sed } else { 967288943Sdim assert((RetTy->isStructTy() || RetTy->isArrayTy()) && 968193323Sed "Return type changed, but not into a void. The old return type" 969288943Sdim " must have been a struct or an array!"); 970193323Sed Instruction *InsertPt = Call; 971193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 972296417Sdim BasicBlock *NewEdge = SplitEdge(New->getParent(), II->getNormalDest()); 973296417Sdim InsertPt = &*NewEdge->getFirstInsertionPt(); 974193323Sed } 975206083Srdivacky 976288943Sdim // We used to return a struct or array. Instead of doing smart stuff 977288943Sdim // with all the uses, we will just rebuild it using extract/insertvalue 978288943Sdim // chaining and let instcombine clean that up. 979193323Sed // 980193323Sed // Start out building up our return value from undef 981198090Srdivacky Value *RetVal = UndefValue::get(RetTy); 982193323Sed for (unsigned i = 0; i != RetCount; ++i) 983193323Sed if (NewRetIdxs[i] != -1) { 984193323Sed Value *V; 985193323Sed if (RetTypes.size() > 1) 986193323Sed // We are still returning a struct, so extract the value from our 987193323Sed // return value 988193323Sed V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret", 989193323Sed InsertPt); 990193323Sed else 991193323Sed // We are now returning a single element, so just insert that 992193323Sed V = New; 993193323Sed // Insert the value at the old position 994193323Sed RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt); 995193323Sed } 996193323Sed // Now, replace all uses of the old call instruction with the return 997193323Sed // struct we built 998193323Sed Call->replaceAllUsesWith(RetVal); 999193323Sed New->takeName(Call); 1000193323Sed } 1001193323Sed } 1002193323Sed 1003193323Sed // Finally, remove the old call from the program, reducing the use-count of 1004193323Sed // F. 1005193323Sed Call->eraseFromParent(); 1006193323Sed } 1007193323Sed 1008193323Sed // Since we have now created the new function, splice the body of the old 1009193323Sed // function right into the new function, leaving the old rotting hulk of the 1010193323Sed // function empty. 1011193323Sed NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 1012193323Sed 1013221345Sdim // Loop over the argument list, transferring uses of the old arguments over to 1014221345Sdim // the new arguments, also transferring over the names as well. 1015193323Sed i = 0; 1016193323Sed for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 1017193323Sed I2 = NF->arg_begin(); I != E; ++I, ++i) 1018193323Sed if (ArgAlive[i]) { 1019193323Sed // If this is a live argument, move the name and users over to the new 1020193323Sed // version. 1021296417Sdim I->replaceAllUsesWith(&*I2); 1022296417Sdim I2->takeName(&*I); 1023193323Sed ++I2; 1024193323Sed } else { 1025344779Sdim // If this argument is dead, replace any uses of it with undef 1026344779Sdim // (any non-debug value uses will get removed later on). 1027218893Sdim if (!I->getType()->isX86_MMXTy()) 1028344779Sdim I->replaceAllUsesWith(UndefValue::get(I->getType())); 1029193323Sed } 1030193323Sed 1031193323Sed // If we change the return value of the function we must rewrite any return 1032193323Sed // instructions. Check this now. 1033193323Sed if (F->getReturnType() != NF->getReturnType()) 1034309124Sdim for (BasicBlock &BB : *NF) 1035309124Sdim if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) { 1036193323Sed Value *RetVal; 1037193323Sed 1038208599Srdivacky if (NFTy->getReturnType()->isVoidTy()) { 1039276479Sdim RetVal = nullptr; 1040193323Sed } else { 1041288943Sdim assert(RetTy->isStructTy() || RetTy->isArrayTy()); 1042288943Sdim // The original return value was a struct or array, insert 1043193323Sed // extractvalue/insertvalue chains to extract only the values we need 1044193323Sed // to return and insert them into our new result. 1045193323Sed // This does generate messy code, but we'll let it to instcombine to 1046193323Sed // clean that up. 1047193323Sed Value *OldRet = RI->getOperand(0); 1048193323Sed // Start out building up our return value from undef 1049198090Srdivacky RetVal = UndefValue::get(NRetTy); 1050193323Sed for (unsigned i = 0; i != RetCount; ++i) 1051193323Sed if (NewRetIdxs[i] != -1) { 1052193323Sed ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i, 1053193323Sed "oldret", RI); 1054193323Sed if (RetTypes.size() > 1) { 1055193323Sed // We're still returning a struct, so reinsert the value into 1056193323Sed // our new return value at the new index 1057193323Sed 1058193323Sed RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i], 1059193323Sed "newret", RI); 1060193323Sed } else { 1061193323Sed // We are now only returning a simple value, so just return the 1062193323Sed // extracted value. 1063193323Sed RetVal = EV; 1064193323Sed } 1065193323Sed } 1066193323Sed } 1067193323Sed // Replace the return instruction with one returning the new return 1068193323Sed // value (possibly 0 if we became void). 1069198090Srdivacky ReturnInst::Create(F->getContext(), RetVal, RI); 1070309124Sdim BB.getInstList().erase(RI); 1071193323Sed } 1072193323Sed 1073341825Sdim // Clone metadatas from the old function, including debug info descriptor. 1074341825Sdim SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 1075341825Sdim F->getAllMetadata(MDs); 1076341825Sdim for (auto MD : MDs) 1077341825Sdim NF->addMetadata(MD.first, *MD.second); 1078243830Sdim 1079193323Sed // Now that the old function is dead, delete it. 1080193323Sed F->eraseFromParent(); 1081193323Sed 1082193323Sed return true; 1083193323Sed} 1084193323Sed 1085309124SdimPreservedAnalyses DeadArgumentEliminationPass::run(Module &M, 1086309124Sdim ModuleAnalysisManager &) { 1087193323Sed bool Changed = false; 1088193323Sed 1089193323Sed // First pass: Do a simple check to see if any functions can have their "..." 1090193323Sed // removed. We can do this if they never call va_start. This loop cannot be 1091193323Sed // fused with the next loop, because deleting a function invalidates 1092193323Sed // information computed while surveying other functions. 1093341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n"); 1094193323Sed for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1095193323Sed Function &F = *I++; 1096193323Sed if (F.getFunctionType()->isVarArg()) 1097193323Sed Changed |= DeleteDeadVarargs(F); 1098193323Sed } 1099193323Sed 1100193323Sed // Second phase:loop through the module, determining which arguments are live. 1101193323Sed // We assume all arguments are dead unless proven otherwise (allowing us to 1102193323Sed // determine that dead arguments passed into recursive functions are dead). 1103193323Sed // 1104341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n"); 1105280031Sdim for (auto &F : M) 1106280031Sdim SurveyFunction(F); 1107206083Srdivacky 1108193323Sed // Now, remove all dead arguments and return values from each function in 1109206083Srdivacky // turn. 1110193323Sed for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1111206083Srdivacky // Increment now, because the function will probably get removed (ie. 1112193323Sed // replaced by a new one). 1113296417Sdim Function *F = &*I++; 1114193323Sed Changed |= RemoveDeadStuffFromFunction(F); 1115193323Sed } 1116218893Sdim 1117218893Sdim // Finally, look for any unused parameters in functions with non-local 1118218893Sdim // linkage and replace the passed in parameters with undef. 1119280031Sdim for (auto &F : M) 1120218893Sdim Changed |= RemoveDeadArgumentsFromCallers(F); 1121218893Sdim 1122309124Sdim if (!Changed) 1123309124Sdim return PreservedAnalyses::all(); 1124309124Sdim return PreservedAnalyses::none(); 1125193323Sed} 1126