DeadArgumentElimination.cpp revision 353358
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" 40193323Sed#include "llvm/Pass.h" 41327952Sdim#include "llvm/Support/Casting.h" 42193323Sed#include "llvm/Support/Debug.h" 43198090Srdivacky#include "llvm/Support/raw_ostream.h" 44309124Sdim#include "llvm/Transforms/IPO.h" 45296417Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 46327952Sdim#include <cassert> 47327952Sdim#include <cstdint> 48327952Sdim#include <utility> 49327952Sdim#include <vector> 50327952Sdim 51193323Sedusing namespace llvm; 52193323Sed 53276479Sdim#define DEBUG_TYPE "deadargelim" 54276479Sdim 55193323SedSTATISTIC(NumArgumentsEliminated, "Number of unread args removed"); 56193323SedSTATISTIC(NumRetValsEliminated , "Number of unused return values removed"); 57341825SdimSTATISTIC(NumArgumentsReplacedWithUndef, 58218893Sdim "Number of unread args replaced with undef"); 59327952Sdim 60193323Sednamespace { 61327952Sdim 62193323Sed /// DAE - The dead argument elimination pass. 63198892Srdivacky class DAE : public ModulePass { 64210299Sed protected: 65210299Sed // DAH uses this to specify a different ID. 66212904Sdim explicit DAE(char &ID) : ModulePass(ID) {} 67210299Sed 68193323Sed public: 69193323Sed static char ID; // Pass identification, replacement for typeid 70327952Sdim 71218893Sdim DAE() : ModulePass(ID) { 72218893Sdim initializeDAEPass(*PassRegistry::getPassRegistry()); 73218893Sdim } 74210299Sed 75309124Sdim bool runOnModule(Module &M) override { 76309124Sdim if (skipModule(M)) 77309124Sdim return false; 78309124Sdim DeadArgumentEliminationPass DAEP(ShouldHackArguments()); 79309124Sdim ModuleAnalysisManager DummyMAM; 80309124Sdim PreservedAnalyses PA = DAEP.run(M, DummyMAM); 81309124Sdim return !PA.areAllPreserved(); 82309124Sdim } 83193323Sed 84193323Sed virtual bool ShouldHackArguments() const { return false; } 85193323Sed }; 86193323Sed 87327952Sdim} // end anonymous namespace 88193323Sed 89193323Sedchar DAE::ID = 0; 90327952Sdim 91218893SdimINITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) 92193323Sed 93193323Sednamespace { 94327952Sdim 95193323Sed /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but 96193323Sed /// deletes arguments to functions which are external. This is only for use 97193323Sed /// by bugpoint. 98193323Sed struct DAH : public DAE { 99193323Sed static char ID; 100327952Sdim 101212904Sdim DAH() : DAE(ID) {} 102210299Sed 103276479Sdim bool ShouldHackArguments() const override { return true; } 104193323Sed }; 105193323Sed 106327952Sdim} // end anonymous namespace 107327952Sdim 108193323Sedchar DAH::ID = 0; 109327952Sdim 110341825SdimINITIALIZE_PASS(DAH, "deadarghaX0r", 111212904Sdim "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", 112218893Sdim false, false) 113193323Sed 114193323Sed/// createDeadArgEliminationPass - This pass removes arguments from functions 115193323Sed/// which are not used by the body of the function. 116193323SedModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } 117327952Sdim 118193323SedModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } 119193323Sed 120193323Sed/// DeleteDeadVarargs - If this is an function that takes a ... list, and if 121193323Sed/// llvm.vastart is never called, the varargs list is dead for the function. 122309124Sdimbool DeadArgumentEliminationPass::DeleteDeadVarargs(Function &Fn) { 123193323Sed assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); 124193323Sed if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false; 125193323Sed 126193323Sed // Ensure that the function is only directly called. 127194178Sed if (Fn.hasAddressTaken()) 128194178Sed return false; 129193323Sed 130296417Sdim // Don't touch naked functions. The assembly might be using an argument, or 131296417Sdim // otherwise rely on the frame layout in a way that this analysis will not 132296417Sdim // see. 133296417Sdim if (Fn.hasFnAttribute(Attribute::Naked)) { 134296417Sdim return false; 135296417Sdim } 136296417Sdim 137193323Sed // Okay, we know we can transform this function if safe. Scan its body 138280031Sdim // looking for calls marked musttail or calls to llvm.vastart. 139309124Sdim for (BasicBlock &BB : Fn) { 140309124Sdim for (Instruction &I : BB) { 141309124Sdim CallInst *CI = dyn_cast<CallInst>(&I); 142280031Sdim if (!CI) 143280031Sdim continue; 144280031Sdim if (CI->isMustTailCall()) 145280031Sdim return false; 146280031Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) { 147193323Sed if (II->getIntrinsicID() == Intrinsic::vastart) 148193323Sed return false; 149193323Sed } 150193323Sed } 151193323Sed } 152193323Sed 153193323Sed // If we get here, there are no calls to llvm.vastart in the function body, 154193323Sed // remove the "..." and adjust all the calls. 155193323Sed 156193323Sed // Start by computing a new prototype for the function, which is the same as 157193323Sed // the old function, but doesn't have isVarArg set. 158226633Sdim FunctionType *FTy = Fn.getFunctionType(); 159206083Srdivacky 160327952Sdim std::vector<Type *> Params(FTy->param_begin(), FTy->param_end()); 161198090Srdivacky FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), 162198090Srdivacky Params, false); 163193323Sed unsigned NumArgs = Params.size(); 164193323Sed 165193323Sed // Create the new function body and insert it into the module... 166344779Sdim Function *NF = Function::Create(NFTy, Fn.getLinkage(), Fn.getAddressSpace()); 167193323Sed NF->copyAttributesFrom(&Fn); 168309124Sdim NF->setComdat(Fn.getComdat()); 169296417Sdim Fn.getParent()->getFunctionList().insert(Fn.getIterator(), NF); 170193323Sed NF->takeName(&Fn); 171193323Sed 172193323Sed // Loop over all of the callers of the function, transforming the call sites 173193323Sed // to pass in a smaller number of arguments into the new function. 174193323Sed // 175327952Sdim std::vector<Value *> Args; 176276479Sdim for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) { 177261991Sdim CallSite CS(*I++); 178261991Sdim if (!CS) 179261991Sdim continue; 180193323Sed Instruction *Call = CS.getInstruction(); 181193323Sed 182193323Sed // Pass all the same arguments. 183212904Sdim Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs); 184193323Sed 185193323Sed // Drop any attributes that were on the vararg arguments. 186321369Sdim AttributeList PAL = CS.getAttributes(); 187321369Sdim if (!PAL.isEmpty()) { 188321369Sdim SmallVector<AttributeSet, 8> ArgAttrs; 189321369Sdim for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) 190321369Sdim ArgAttrs.push_back(PAL.getParamAttributes(ArgNo)); 191321369Sdim PAL = AttributeList::get(Fn.getContext(), PAL.getFnAttributes(), 192321369Sdim PAL.getRetAttributes(), ArgAttrs); 193193323Sed } 194193323Sed 195309124Sdim SmallVector<OperandBundleDef, 1> OpBundles; 196309124Sdim CS.getOperandBundlesAsDefs(OpBundles); 197309124Sdim 198321369Sdim CallSite NewCS; 199193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 200321369Sdim NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 201321369Sdim Args, OpBundles, "", Call); 202193323Sed } else { 203321369Sdim NewCS = CallInst::Create(NF, Args, OpBundles, "", Call); 204321369Sdim cast<CallInst>(NewCS.getInstruction()) 205321369Sdim ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind()); 206193323Sed } 207321369Sdim NewCS.setCallingConv(CS.getCallingConv()); 208321369Sdim NewCS.setAttributes(PAL); 209321369Sdim NewCS->setDebugLoc(Call->getDebugLoc()); 210321369Sdim uint64_t W; 211321369Sdim if (Call->extractProfTotalWeight(W)) 212321369Sdim NewCS->setProfWeight(W); 213207618Srdivacky 214193323Sed Args.clear(); 215193323Sed 216193323Sed if (!Call->use_empty()) 217321369Sdim Call->replaceAllUsesWith(NewCS.getInstruction()); 218193323Sed 219321369Sdim NewCS->takeName(Call); 220193323Sed 221193323Sed // Finally, remove the old call from the program, reducing the use-count of 222193323Sed // F. 223193323Sed Call->eraseFromParent(); 224193323Sed } 225193323Sed 226193323Sed // Since we have now created the new function, splice the body of the old 227193323Sed // function right into the new function, leaving the old rotting hulk of the 228193323Sed // function empty. 229193323Sed NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); 230193323Sed 231221345Sdim // Loop over the argument list, transferring uses of the old arguments over to 232221345Sdim // the new arguments, also transferring over the names as well. While we're at 233193323Sed // it, remove the dead arguments from the DeadArguments list. 234193323Sed for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), 235193323Sed I2 = NF->arg_begin(); I != E; ++I, ++I2) { 236193323Sed // Move the name and users over to the new version. 237296417Sdim I->replaceAllUsesWith(&*I2); 238296417Sdim I2->takeName(&*I); 239193323Sed } 240193323Sed 241341825Sdim // Clone metadatas from the old function, including debug info descriptor. 242341825Sdim SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 243341825Sdim Fn.getAllMetadata(MDs); 244341825Sdim for (auto MD : MDs) 245341825Sdim NF->addMetadata(MD.first, *MD.second); 246243830Sdim 247261991Sdim // Fix up any BlockAddresses that refer to the function. 248261991Sdim Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType())); 249261991Sdim // Delete the bitcast that we just created, so that NF does not 250261991Sdim // appear to be address-taken. 251261991Sdim NF->removeDeadConstantUsers(); 252193323Sed // Finally, nuke the old function. 253193323Sed Fn.eraseFromParent(); 254193323Sed return true; 255193323Sed} 256193323Sed 257341825Sdim/// RemoveDeadArgumentsFromCallers - Checks if the given function has any 258218893Sdim/// arguments that are unused, and changes the caller parameters to be undefined 259218893Sdim/// instead. 260309124Sdimbool DeadArgumentEliminationPass::RemoveDeadArgumentsFromCallers(Function &Fn) { 261288943Sdim // We cannot change the arguments if this TU does not define the function or 262288943Sdim // if the linker may choose a function body from another TU, even if the 263288943Sdim // nominal linkage indicates that other copies of the function have the same 264288943Sdim // semantics. In the below example, the dead load from %p may not have been 265288943Sdim // eliminated from the linker-chosen copy of f, so replacing %p with undef 266288943Sdim // in callers may introduce undefined behavior. 267288943Sdim // 268288943Sdim // define linkonce_odr void @f(i32* %p) { 269288943Sdim // %v = load i32 %p 270288943Sdim // ret void 271288943Sdim // } 272309124Sdim if (!Fn.hasExactDefinition()) 273218893Sdim return false; 274218893Sdim 275261991Sdim // Functions with local linkage should already have been handled, except the 276261991Sdim // fragile (variadic) ones which we can improve here. 277261991Sdim if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg()) 278218893Sdim return false; 279218893Sdim 280296417Sdim // Don't touch naked functions. The assembly might be using an argument, or 281296417Sdim // otherwise rely on the frame layout in a way that this analysis will not 282296417Sdim // see. 283296417Sdim if (Fn.hasFnAttribute(Attribute::Naked)) 284296417Sdim return false; 285296417Sdim 286218893Sdim if (Fn.use_empty()) 287218893Sdim return false; 288218893Sdim 289249423Sdim SmallVector<unsigned, 8> UnusedArgs; 290344779Sdim bool Changed = false; 291344779Sdim 292296417Sdim for (Argument &Arg : Fn.args()) { 293344779Sdim if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() && !Arg.hasByValOrInAllocaAttr()) { 294344779Sdim if (Arg.isUsedByMetadata()) { 295344779Sdim Arg.replaceAllUsesWith(UndefValue::get(Arg.getType())); 296344779Sdim Changed = true; 297344779Sdim } 298296417Sdim UnusedArgs.push_back(Arg.getArgNo()); 299344779Sdim } 300218893Sdim } 301218893Sdim 302218893Sdim if (UnusedArgs.empty()) 303218893Sdim return false; 304218893Sdim 305276479Sdim for (Use &U : Fn.uses()) { 306276479Sdim CallSite CS(U.getUser()); 307276479Sdim if (!CS || !CS.isCallee(&U)) 308218893Sdim continue; 309218893Sdim 310218893Sdim // Now go through all unused args and replace them with "undef". 311218893Sdim for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { 312218893Sdim unsigned ArgNo = UnusedArgs[I]; 313218893Sdim 314218893Sdim Value *Arg = CS.getArgument(ArgNo); 315218893Sdim CS.setArgument(ArgNo, UndefValue::get(Arg->getType())); 316218893Sdim ++NumArgumentsReplacedWithUndef; 317218893Sdim Changed = true; 318218893Sdim } 319218893Sdim } 320218893Sdim 321218893Sdim return Changed; 322218893Sdim} 323218893Sdim 324193323Sed/// Convenience function that returns the number of return values. It returns 0 325193323Sed/// for void functions and 1 for functions not returning a struct. It returns 326193323Sed/// the number of struct elements for functions returning a struct. 327193323Sedstatic unsigned NumRetVals(const Function *F) { 328288943Sdim Type *RetTy = F->getReturnType(); 329288943Sdim if (RetTy->isVoidTy()) 330193323Sed return 0; 331288943Sdim else if (StructType *STy = dyn_cast<StructType>(RetTy)) 332193323Sed return STy->getNumElements(); 333288943Sdim else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 334288943Sdim return ATy->getNumElements(); 335193323Sed else 336193323Sed return 1; 337193323Sed} 338193323Sed 339288943Sdim/// Returns the sub-type a function will return at a given Idx. Should 340288943Sdim/// correspond to the result type of an ExtractValue instruction executed with 341288943Sdim/// just that one Idx (i.e. only top-level structure is considered). 342288943Sdimstatic Type *getRetComponentType(const Function *F, unsigned Idx) { 343288943Sdim Type *RetTy = F->getReturnType(); 344288943Sdim assert(!RetTy->isVoidTy() && "void type has no subtype"); 345288943Sdim 346288943Sdim if (StructType *STy = dyn_cast<StructType>(RetTy)) 347288943Sdim return STy->getElementType(Idx); 348288943Sdim else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) 349288943Sdim return ATy->getElementType(); 350288943Sdim else 351288943Sdim return RetTy; 352288943Sdim} 353288943Sdim 354193323Sed/// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not 355193323Sed/// live, it adds Use to the MaybeLiveUses argument. Returns the determined 356193323Sed/// liveness of Use. 357309124SdimDeadArgumentEliminationPass::Liveness 358309124SdimDeadArgumentEliminationPass::MarkIfNotLive(RetOrArg Use, 359309124Sdim UseVector &MaybeLiveUses) { 360193323Sed // We're live if our use or its Function is already marked as live. 361193323Sed if (LiveFunctions.count(Use.F) || LiveValues.count(Use)) 362193323Sed return Live; 363193323Sed 364193323Sed // We're maybe live otherwise, but remember that we must become live if 365193323Sed // Use becomes live. 366193323Sed MaybeLiveUses.push_back(Use); 367193323Sed return MaybeLive; 368193323Sed} 369193323Sed 370193323Sed/// SurveyUse - This looks at a single use of an argument or return value 371193323Sed/// and determines if it should be alive or not. Adds this use to MaybeLiveUses 372206083Srdivacky/// if it causes the used value to become MaybeLive. 373193323Sed/// 374193323Sed/// RetValNum is the return value number to use when this use is used in a 375193323Sed/// return instruction. This is used in the recursion, you should always leave 376193323Sed/// it at 0. 377309124SdimDeadArgumentEliminationPass::Liveness 378309124SdimDeadArgumentEliminationPass::SurveyUse(const Use *U, UseVector &MaybeLiveUses, 379309124Sdim unsigned RetValNum) { 380276479Sdim const User *V = U->getUser(); 381206083Srdivacky if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { 382193323Sed // The value is returned from a function. It's only live when the 383193323Sed // function's return value is live. We use RetValNum here, for the case 384193323Sed // that U is really a use of an insertvalue instruction that uses the 385221345Sdim // original Use. 386288943Sdim const Function *F = RI->getParent()->getParent(); 387288943Sdim if (RetValNum != -1U) { 388288943Sdim RetOrArg Use = CreateRet(F, RetValNum); 389288943Sdim // We might be live, depending on the liveness of Use. 390288943Sdim return MarkIfNotLive(Use, MaybeLiveUses); 391288943Sdim } else { 392309124Sdim DeadArgumentEliminationPass::Liveness Result = MaybeLive; 393288943Sdim for (unsigned i = 0; i < NumRetVals(F); ++i) { 394288943Sdim RetOrArg Use = CreateRet(F, i); 395288943Sdim // We might be live, depending on the liveness of Use. If any 396288943Sdim // sub-value is live, then the entire value is considered live. This 397288943Sdim // is a conservative choice, and better tracking is possible. 398309124Sdim DeadArgumentEliminationPass::Liveness SubResult = 399309124Sdim MarkIfNotLive(Use, MaybeLiveUses); 400288943Sdim if (Result != Live) 401288943Sdim Result = SubResult; 402288943Sdim } 403288943Sdim return Result; 404288943Sdim } 405193323Sed } 406206083Srdivacky if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { 407276479Sdim if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex() 408193323Sed && IV->hasIndices()) 409193323Sed // The use we are examining is inserted into an aggregate. Our liveness 410193323Sed // depends on all uses of that aggregate, but if it is used as a return 411193323Sed // value, only index at which we were inserted counts. 412193323Sed RetValNum = *IV->idx_begin(); 413193323Sed 414193323Sed // Note that if we are used as the aggregate operand to the insertvalue, 415193323Sed // we don't change RetValNum, but do survey all our uses. 416193323Sed 417193323Sed Liveness Result = MaybeLive; 418276479Sdim for (const Use &UU : IV->uses()) { 419276479Sdim Result = SurveyUse(&UU, MaybeLiveUses, RetValNum); 420193323Sed if (Result == Live) 421193323Sed break; 422193323Sed } 423193323Sed return Result; 424193323Sed } 425206083Srdivacky 426288943Sdim if (auto CS = ImmutableCallSite(V)) { 427206083Srdivacky const Function *F = CS.getCalledFunction(); 428193323Sed if (F) { 429193323Sed // Used in a direct call. 430206083Srdivacky 431296417Sdim // The function argument is live if it is used as a bundle operand. 432296417Sdim if (CS.isBundleOperand(U)) 433296417Sdim return Live; 434296417Sdim 435193323Sed // Find the argument number. We know for sure that this use is an 436193323Sed // argument, since if it was the function argument this would be an 437193323Sed // indirect call and the we know can't be looking at a value of the 438193323Sed // label type (for the invoke instruction). 439206083Srdivacky unsigned ArgNo = CS.getArgumentNo(U); 440193323Sed 441193323Sed if (ArgNo >= F->getFunctionType()->getNumParams()) 442193323Sed // The value is passed in through a vararg! Must be live. 443193323Sed return Live; 444193323Sed 445206083Srdivacky assert(CS.getArgument(ArgNo) 446276479Sdim == CS->getOperand(U->getOperandNo()) 447193323Sed && "Argument is not where we expected it"); 448193323Sed 449193323Sed // Value passed to a normal call. It's only live when the corresponding 450193323Sed // argument to the called function turns out live. 451193323Sed RetOrArg Use = CreateArg(F, ArgNo); 452193323Sed return MarkIfNotLive(Use, MaybeLiveUses); 453193323Sed } 454193323Sed } 455193323Sed // Used in any other way? Value must be live. 456193323Sed return Live; 457193323Sed} 458193323Sed 459193323Sed/// SurveyUses - This looks at all the uses of the given value 460193323Sed/// Returns the Liveness deduced from the uses of this value. 461193323Sed/// 462193323Sed/// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If 463193323Sed/// the result is Live, MaybeLiveUses might be modified but its content should 464193323Sed/// be ignored (since it might not be complete). 465309124SdimDeadArgumentEliminationPass::Liveness 466309124SdimDeadArgumentEliminationPass::SurveyUses(const Value *V, 467309124Sdim UseVector &MaybeLiveUses) { 468193323Sed // Assume it's dead (which will only hold if there are no uses at all..). 469193323Sed Liveness Result = MaybeLive; 470193323Sed // Check each use. 471276479Sdim for (const Use &U : V->uses()) { 472276479Sdim Result = SurveyUse(&U, MaybeLiveUses); 473193323Sed if (Result == Live) 474193323Sed break; 475193323Sed } 476193323Sed return Result; 477193323Sed} 478193323Sed 479193323Sed// SurveyFunction - This performs the initial survey of the specified function, 480193323Sed// checking out whether or not it uses any of its incoming arguments or whether 481193323Sed// any callers use the return value. This fills in the LiveValues set and Uses 482193323Sed// map. 483193323Sed// 484193323Sed// We consider arguments of non-internal functions to be intrinsically alive as 485193323Sed// well as arguments to functions which have their "address taken". 486309124Sdimvoid DeadArgumentEliminationPass::SurveyFunction(const Function &F) { 487276479Sdim // Functions with inalloca parameters are expecting args in a particular 488276479Sdim // register and memory layout. 489276479Sdim if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) { 490276479Sdim MarkLive(F); 491276479Sdim return; 492276479Sdim } 493276479Sdim 494296417Sdim // Don't touch naked functions. The assembly might be using an argument, or 495296417Sdim // otherwise rely on the frame layout in a way that this analysis will not 496296417Sdim // see. 497296417Sdim if (F.hasFnAttribute(Attribute::Naked)) { 498296417Sdim MarkLive(F); 499296417Sdim return; 500296417Sdim } 501296417Sdim 502193323Sed unsigned RetCount = NumRetVals(&F); 503327952Sdim 504193323Sed // Assume all return values are dead 505327952Sdim using RetVals = SmallVector<Liveness, 5>; 506327952Sdim 507193323Sed RetVals RetValLiveness(RetCount, MaybeLive); 508193323Sed 509327952Sdim using RetUses = SmallVector<UseVector, 5>; 510327952Sdim 511193323Sed // These vectors map each return value to the uses that make it MaybeLive, so 512193323Sed // we can add those to the Uses map if the return value really turns out to be 513193323Sed // MaybeLive. Initialized to a list of RetCount empty lists. 514193323Sed RetUses MaybeLiveRetUses(RetCount); 515193323Sed 516335799Sdim bool HasMustTailCalls = false; 517335799Sdim 518335799Sdim for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 519335799Sdim if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 520193323Sed if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() 521193323Sed != F.getFunctionType()->getReturnType()) { 522193323Sed // We don't support old style multiple return values. 523193323Sed MarkLive(F); 524193323Sed return; 525193323Sed } 526335799Sdim } 527193323Sed 528335799Sdim // If we have any returns of `musttail` results - the signature can't 529335799Sdim // change 530335799Sdim if (BB->getTerminatingMustTailCall() != nullptr) 531335799Sdim HasMustTailCalls = true; 532335799Sdim } 533335799Sdim 534335799Sdim if (HasMustTailCalls) { 535341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 536341825Sdim << " has musttail calls\n"); 537335799Sdim } 538335799Sdim 539309124Sdim if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { 540193323Sed MarkLive(F); 541193323Sed return; 542193323Sed } 543193323Sed 544341825Sdim LLVM_DEBUG( 545341825Sdim dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: " 546341825Sdim << F.getName() << "\n"); 547193323Sed // Keep track of the number of live retvals, so we can skip checks once all 548193323Sed // of them turn out to be live. 549193323Sed unsigned NumLiveRetVals = 0; 550335799Sdim 551335799Sdim bool HasMustTailCallers = false; 552335799Sdim 553193323Sed // Loop all uses of the function. 554276479Sdim for (const Use &U : F.uses()) { 555193323Sed // If the function is PASSED IN as an argument, its address has been 556193323Sed // taken. 557276479Sdim ImmutableCallSite CS(U.getUser()); 558276479Sdim if (!CS || !CS.isCallee(&U)) { 559193323Sed MarkLive(F); 560193323Sed return; 561193323Sed } 562193323Sed 563335799Sdim // The number of arguments for `musttail` call must match the number of 564335799Sdim // arguments of the caller 565335799Sdim if (CS.isMustTailCall()) 566335799Sdim HasMustTailCallers = true; 567335799Sdim 568193323Sed // If this use is anything other than a call site, the function is alive. 569206083Srdivacky const Instruction *TheCall = CS.getInstruction(); 570193323Sed if (!TheCall) { // Not a direct call site? 571193323Sed MarkLive(F); 572193323Sed return; 573193323Sed } 574193323Sed 575193323Sed // If we end up here, we are looking at a direct call to our function. 576193323Sed 577193323Sed // Now, check how our return value(s) is/are used in this caller. Don't 578193323Sed // bother checking return values if all of them are live already. 579288943Sdim if (NumLiveRetVals == RetCount) 580288943Sdim continue; 581288943Sdim 582288943Sdim // Check all uses of the return value. 583288943Sdim for (const Use &U : TheCall->uses()) { 584288943Sdim if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) { 585288943Sdim // This use uses a part of our return value, survey the uses of 586288943Sdim // that part and store the results for this index only. 587288943Sdim unsigned Idx = *Ext->idx_begin(); 588288943Sdim if (RetValLiveness[Idx] != Live) { 589288943Sdim RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); 590288943Sdim if (RetValLiveness[Idx] == Live) 591288943Sdim NumLiveRetVals++; 592193323Sed } 593193323Sed } else { 594288943Sdim // Used by something else than extractvalue. Survey, but assume that the 595288943Sdim // result applies to all sub-values. 596288943Sdim UseVector MaybeLiveAggregateUses; 597288943Sdim if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) { 598193323Sed NumLiveRetVals = RetCount; 599288943Sdim RetValLiveness.assign(RetCount, Live); 600288943Sdim break; 601288943Sdim } else { 602288943Sdim for (unsigned i = 0; i != RetCount; ++i) { 603288943Sdim if (RetValLiveness[i] != Live) 604288943Sdim MaybeLiveRetUses[i].append(MaybeLiveAggregateUses.begin(), 605288943Sdim MaybeLiveAggregateUses.end()); 606288943Sdim } 607288943Sdim } 608193323Sed } 609193323Sed } 610193323Sed } 611193323Sed 612335799Sdim if (HasMustTailCallers) { 613341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName() 614341825Sdim << " has musttail callers\n"); 615335799Sdim } 616335799Sdim 617193323Sed // Now we've inspected all callers, record the liveness of our return values. 618193323Sed for (unsigned i = 0; i != RetCount; ++i) 619193323Sed MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]); 620193323Sed 621341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: " 622341825Sdim << F.getName() << "\n"); 623193323Sed 624193323Sed // Now, check all of our arguments. 625193323Sed unsigned i = 0; 626193323Sed UseVector MaybeLiveArgUses; 627206083Srdivacky for (Function::const_arg_iterator AI = F.arg_begin(), 628193323Sed E = F.arg_end(); AI != E; ++AI, ++i) { 629261991Sdim Liveness Result; 630335799Sdim if (F.getFunctionType()->isVarArg() || HasMustTailCallers || 631335799Sdim HasMustTailCalls) { 632261991Sdim // Variadic functions will already have a va_arg function expanded inside 633261991Sdim // them, making them potentially very sensitive to ABI changes resulting 634261991Sdim // from removing arguments entirely, so don't. For example AArch64 handles 635261991Sdim // register and stack HFAs very differently, and this is reflected in the 636261991Sdim // IR which has already been generated. 637335799Sdim // 638335799Sdim // `musttail` calls to this function restrict argument removal attempts. 639335799Sdim // The signature of the caller must match the signature of the function. 640335799Sdim // 641335799Sdim // `musttail` calls in this function prevents us from changing its 642335799Sdim // signature 643261991Sdim Result = Live; 644261991Sdim } else { 645261991Sdim // See what the effect of this use is (recording any uses that cause 646341825Sdim // MaybeLive in MaybeLiveArgUses). 647296417Sdim Result = SurveyUses(&*AI, MaybeLiveArgUses); 648261991Sdim } 649261991Sdim 650193323Sed // Mark the result. 651193323Sed MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses); 652193323Sed // Clear the vector again for the next iteration. 653193323Sed MaybeLiveArgUses.clear(); 654193323Sed } 655193323Sed} 656193323Sed 657193323Sed/// MarkValue - This function marks the liveness of RA depending on L. If L is 658193323Sed/// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, 659193323Sed/// such that RA will be marked live if any use in MaybeLiveUses gets marked 660193323Sed/// live later on. 661309124Sdimvoid DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L, 662309124Sdim const UseVector &MaybeLiveUses) { 663193323Sed switch (L) { 664327952Sdim case Live: 665327952Sdim MarkLive(RA); 666327952Sdim break; 667193323Sed case MaybeLive: 668193323Sed // Note any uses of this value, so this return value can be 669193323Sed // marked live whenever one of the uses becomes live. 670309124Sdim for (const auto &MaybeLiveUse : MaybeLiveUses) 671309124Sdim Uses.insert(std::make_pair(MaybeLiveUse, RA)); 672193323Sed break; 673193323Sed } 674193323Sed} 675193323Sed 676193323Sed/// MarkLive - Mark the given Function as alive, meaning that it cannot be 677193323Sed/// changed in any way. Additionally, 678193323Sed/// mark any values that are used as this function's parameters or by its return 679193323Sed/// values (according to Uses) live as well. 680309124Sdimvoid DeadArgumentEliminationPass::MarkLive(const Function &F) { 681341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: " 682341825Sdim << F.getName() << "\n"); 683208599Srdivacky // Mark the function as live. 684208599Srdivacky LiveFunctions.insert(&F); 685208599Srdivacky // Mark all arguments as live. 686208599Srdivacky for (unsigned i = 0, e = F.arg_size(); i != e; ++i) 687208599Srdivacky PropagateLiveness(CreateArg(&F, i)); 688208599Srdivacky // Mark all return values as live. 689208599Srdivacky for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i) 690208599Srdivacky PropagateLiveness(CreateRet(&F, i)); 691193323Sed} 692193323Sed 693193323Sed/// MarkLive - Mark the given return value or argument as live. Additionally, 694193323Sed/// mark any values that are used by this value (according to Uses) live as 695193323Sed/// well. 696309124Sdimvoid DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) { 697193323Sed if (LiveFunctions.count(RA.F)) 698193323Sed return; // Function was already marked Live. 699193323Sed 700193323Sed if (!LiveValues.insert(RA).second) 701193323Sed return; // We were already marked Live. 702193323Sed 703341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking " 704341825Sdim << RA.getDescription() << " live\n"); 705193323Sed PropagateLiveness(RA); 706193323Sed} 707193323Sed 708193323Sed/// PropagateLiveness - Given that RA is a live value, propagate it's liveness 709193323Sed/// to any other values it uses (according to Uses). 710309124Sdimvoid DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) { 711193323Sed // We don't use upper_bound (or equal_range) here, because our recursive call 712193323Sed // to ourselves is likely to cause the upper_bound (which is the first value 713193323Sed // not belonging to RA) to become erased and the iterator invalidated. 714193323Sed UseMap::iterator Begin = Uses.lower_bound(RA); 715193323Sed UseMap::iterator E = Uses.end(); 716193323Sed UseMap::iterator I; 717193323Sed for (I = Begin; I != E && I->first == RA; ++I) 718193323Sed MarkLive(I->second); 719193323Sed 720193323Sed // Erase RA from the Uses map (from the lower bound to wherever we ended up 721193323Sed // after the loop). 722193323Sed Uses.erase(Begin, I); 723193323Sed} 724193323Sed 725193323Sed// RemoveDeadStuffFromFunction - Remove any arguments and return values from F 726193323Sed// that are not in LiveValues. Transform the function and all of the callees of 727193323Sed// the function to not have these arguments and return values. 728193323Sed// 729309124Sdimbool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) { 730193323Sed // Don't modify fully live functions 731193323Sed if (LiveFunctions.count(F)) 732193323Sed return false; 733193323Sed 734193323Sed // Start by computing a new prototype for the function, which is the same as 735193323Sed // the old function, but has fewer arguments and a different return type. 736226633Sdim FunctionType *FTy = F->getFunctionType(); 737224145Sdim std::vector<Type*> Params; 738193323Sed 739261991Sdim // Keep track of if we have a live 'returned' argument 740261991Sdim bool HasLiveReturnedArg = false; 741261991Sdim 742193323Sed // Set up to build a new list of parameter attributes. 743321369Sdim SmallVector<AttributeSet, 8> ArgAttrVec; 744321369Sdim const AttributeList &PAL = F->getAttributes(); 745193323Sed 746261991Sdim // Remember which arguments are still alive. 747261991Sdim SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); 748261991Sdim // Construct the new parameter list from non-dead arguments. Also construct 749261991Sdim // a new set of parameter attributes to correspond. Skip the first parameter 750261991Sdim // attribute, since that belongs to the return value. 751261991Sdim unsigned i = 0; 752261991Sdim for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 753261991Sdim I != E; ++I, ++i) { 754261991Sdim RetOrArg Arg = CreateArg(F, i); 755261991Sdim if (LiveValues.erase(Arg)) { 756261991Sdim Params.push_back(I->getType()); 757261991Sdim ArgAlive[i] = true; 758321369Sdim ArgAttrVec.push_back(PAL.getParamAttributes(i)); 759321369Sdim HasLiveReturnedArg |= PAL.hasParamAttribute(i, Attribute::Returned); 760261991Sdim } else { 761261991Sdim ++NumArgumentsEliminated; 762341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument " 763341825Sdim << i << " (" << I->getName() << ") from " 764341825Sdim << F->getName() << "\n"); 765261991Sdim } 766261991Sdim } 767261991Sdim 768193323Sed // Find out the new return value. 769224145Sdim Type *RetTy = FTy->getReturnType(); 770276479Sdim Type *NRetTy = nullptr; 771193323Sed unsigned RetCount = NumRetVals(F); 772206083Srdivacky 773193323Sed // -1 means unused, other numbers are the new index 774193323Sed SmallVector<int, 5> NewRetIdxs(RetCount, -1); 775224145Sdim std::vector<Type*> RetTypes; 776261991Sdim 777261991Sdim // If there is a function with a live 'returned' argument but a dead return 778261991Sdim // value, then there are two possible actions: 779261991Sdim // 1) Eliminate the return value and take off the 'returned' attribute on the 780261991Sdim // argument. 781261991Sdim // 2) Retain the 'returned' attribute and treat the return value (but not the 782261991Sdim // entire function) as live so that it is not eliminated. 783341825Sdim // 784261991Sdim // It's not clear in the general case which option is more profitable because, 785261991Sdim // even in the absence of explicit uses of the return value, code generation 786261991Sdim // is free to use the 'returned' attribute to do things like eliding 787261991Sdim // save/restores of registers across calls. Whether or not this happens is 788261991Sdim // target and ABI-specific as well as depending on the amount of register 789261991Sdim // pressure, so there's no good way for an IR-level pass to figure this out. 790261991Sdim // 791261991Sdim // Fortunately, the only places where 'returned' is currently generated by 792261991Sdim // the FE are places where 'returned' is basically free and almost always a 793261991Sdim // performance win, so the second option can just be used always for now. 794261991Sdim // 795261991Sdim // This should be revisited if 'returned' is ever applied more liberally. 796261991Sdim if (RetTy->isVoidTy() || HasLiveReturnedArg) { 797206083Srdivacky NRetTy = RetTy; 798193323Sed } else { 799288943Sdim // Look at each of the original return values individually. 800288943Sdim for (unsigned i = 0; i != RetCount; ++i) { 801288943Sdim RetOrArg Ret = CreateRet(F, i); 802288943Sdim if (LiveValues.erase(Ret)) { 803288943Sdim RetTypes.push_back(getRetComponentType(F, i)); 804288943Sdim NewRetIdxs[i] = RetTypes.size() - 1; 805193323Sed } else { 806193323Sed ++NumRetValsEliminated; 807341825Sdim LLVM_DEBUG( 808341825Sdim dbgs() << "DeadArgumentEliminationPass - Removing return value " 809341825Sdim << i << " from " << F->getName() << "\n"); 810193323Sed } 811288943Sdim } 812288943Sdim if (RetTypes.size() > 1) { 813288943Sdim // More than one return type? Reduce it down to size. 814288943Sdim if (StructType *STy = dyn_cast<StructType>(RetTy)) { 815288943Sdim // Make the new struct packed if we used to return a packed struct 816288943Sdim // already. 817288943Sdim NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); 818288943Sdim } else { 819288943Sdim assert(isa<ArrayType>(RetTy) && "unexpected multi-value return"); 820288943Sdim NRetTy = ArrayType::get(RetTypes[0], RetTypes.size()); 821288943Sdim } 822288943Sdim } else if (RetTypes.size() == 1) 823193323Sed // One return type? Just a simple value then, but only if we didn't use to 824193323Sed // return a struct with that simple value before. 825193323Sed NRetTy = RetTypes.front(); 826327952Sdim else if (RetTypes.empty()) 827193323Sed // No return types? Make it void, but only if we didn't use to return {}. 828198090Srdivacky NRetTy = Type::getVoidTy(F->getContext()); 829193323Sed } 830193323Sed 831193323Sed assert(NRetTy && "No new return type found?"); 832193323Sed 833249423Sdim // The existing function return attributes. 834321369Sdim AttrBuilder RAttrs(PAL.getRetAttributes()); 835249423Sdim 836193323Sed // Remove any incompatible attributes, but only if we removed all return 837193323Sed // values. Otherwise, ensure that we don't have any conflicting attributes 838193323Sed // here. Currently, this should not be possible, but special handling might be 839193323Sed // required when new return value attributes are added. 840206083Srdivacky if (NRetTy->isVoidTy()) 841321369Sdim RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 842193323Sed else 843321369Sdim assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) && 844243830Sdim "Return attributes no longer compatible?"); 845193323Sed 846321369Sdim AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 847193323Sed 848341825Sdim // Strip allocsize attributes. They might refer to the deleted arguments. 849341825Sdim AttributeSet FnAttrs = PAL.getFnAttributes().removeAttribute( 850341825Sdim F->getContext(), Attribute::AllocSize); 851341825Sdim 852193323Sed // Reconstruct the AttributesList based on the vector we constructed. 853321369Sdim assert(ArgAttrVec.size() == Params.size()); 854341825Sdim AttributeList NewPAL = 855341825Sdim AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 856193323Sed 857193323Sed // Create the new function type based on the recomputed parameters. 858206083Srdivacky FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); 859193323Sed 860193323Sed // No change? 861193323Sed if (NFTy == FTy) 862193323Sed return false; 863193323Sed 864193323Sed // Create the new function body and insert it into the module... 865344779Sdim Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace()); 866193323Sed NF->copyAttributesFrom(F); 867309124Sdim NF->setComdat(F->getComdat()); 868193323Sed NF->setAttributes(NewPAL); 869193323Sed // Insert the new function before the old function, so we won't be processing 870193323Sed // it again. 871296417Sdim F->getParent()->getFunctionList().insert(F->getIterator(), NF); 872193323Sed NF->takeName(F); 873193323Sed 874193323Sed // Loop over all of the callers of the function, transforming the call sites 875193323Sed // to pass in a smaller number of arguments into the new function. 876193323Sed std::vector<Value*> Args; 877193323Sed while (!F->use_empty()) { 878276479Sdim CallSite CS(F->user_back()); 879193323Sed Instruction *Call = CS.getInstruction(); 880193323Sed 881321369Sdim ArgAttrVec.clear(); 882321369Sdim const AttributeList &CallPAL = CS.getAttributes(); 883193323Sed 884321369Sdim // Adjust the call return attributes in case the function was changed to 885321369Sdim // return void. 886321369Sdim AttrBuilder RAttrs(CallPAL.getRetAttributes()); 887321369Sdim RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); 888321369Sdim AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); 889249423Sdim 890193323Sed // Declare these outside of the loops, so we can reuse them for the second 891193323Sed // loop, which loops the varargs. 892193323Sed CallSite::arg_iterator I = CS.arg_begin(); 893193323Sed unsigned i = 0; 894193323Sed // Loop over those operands, corresponding to the normal arguments to the 895193323Sed // original function, and add those that are still alive. 896193323Sed for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i) 897193323Sed if (ArgAlive[i]) { 898193323Sed Args.push_back(*I); 899193323Sed // Get original parameter attributes, but skip return attributes. 900321369Sdim AttributeSet Attrs = CallPAL.getParamAttributes(i); 901321369Sdim if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) { 902261991Sdim // If the return type has changed, then get rid of 'returned' on the 903261991Sdim // call site. The alternative is to make all 'returned' attributes on 904261991Sdim // call sites keep the return value alive just like 'returned' 905321369Sdim // attributes on function declaration but it's less clearly a win and 906321369Sdim // this is not an expected case anyway 907321369Sdim ArgAttrVec.push_back(AttributeSet::get( 908321369Sdim F->getContext(), 909321369Sdim AttrBuilder(Attrs).removeAttribute(Attribute::Returned))); 910321369Sdim } else { 911321369Sdim // Otherwise, use the original attributes. 912321369Sdim ArgAttrVec.push_back(Attrs); 913249423Sdim } 914193323Sed } 915193323Sed 916193323Sed // Push any varargs arguments on the list. Don't forget their attributes. 917193323Sed for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { 918193323Sed Args.push_back(*I); 919321369Sdim ArgAttrVec.push_back(CallPAL.getParamAttributes(i)); 920193323Sed } 921193323Sed 922193323Sed // Reconstruct the AttributesList based on the vector we constructed. 923321369Sdim assert(ArgAttrVec.size() == Args.size()); 924341825Sdim 925341825Sdim // Again, be sure to remove any allocsize attributes, since their indices 926341825Sdim // may now be incorrect. 927341825Sdim AttributeSet FnAttrs = CallPAL.getFnAttributes().removeAttribute( 928341825Sdim F->getContext(), Attribute::AllocSize); 929341825Sdim 930321369Sdim AttributeList NewCallPAL = AttributeList::get( 931341825Sdim F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); 932193323Sed 933309124Sdim SmallVector<OperandBundleDef, 1> OpBundles; 934309124Sdim CS.getOperandBundlesAsDefs(OpBundles); 935309124Sdim 936321369Sdim CallSite NewCS; 937193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 938321369Sdim NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 939321369Sdim Args, OpBundles, "", Call->getParent()); 940193323Sed } else { 941353358Sdim NewCS = CallInst::Create(NFTy, NF, Args, OpBundles, "", Call); 942321369Sdim cast<CallInst>(NewCS.getInstruction()) 943321369Sdim ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind()); 944193323Sed } 945321369Sdim NewCS.setCallingConv(CS.getCallingConv()); 946321369Sdim NewCS.setAttributes(NewCallPAL); 947321369Sdim NewCS->setDebugLoc(Call->getDebugLoc()); 948321369Sdim uint64_t W; 949321369Sdim if (Call->extractProfTotalWeight(W)) 950321369Sdim NewCS->setProfWeight(W); 951193323Sed Args.clear(); 952321369Sdim ArgAttrVec.clear(); 953193323Sed 954321369Sdim Instruction *New = NewCS.getInstruction(); 955344779Sdim if (!Call->use_empty() || Call->isUsedByMetadata()) { 956193323Sed if (New->getType() == Call->getType()) { 957193323Sed // Return type not changed? Just replace users then. 958193323Sed Call->replaceAllUsesWith(New); 959193323Sed New->takeName(Call); 960206083Srdivacky } else if (New->getType()->isVoidTy()) { 961344779Sdim // If the return value is dead, replace any uses of it with undef 962344779Sdim // (any non-debug value uses will get removed later on). 963218893Sdim if (!Call->getType()->isX86_MMXTy()) 964344779Sdim Call->replaceAllUsesWith(UndefValue::get(Call->getType())); 965193323Sed } else { 966288943Sdim assert((RetTy->isStructTy() || RetTy->isArrayTy()) && 967193323Sed "Return type changed, but not into a void. The old return type" 968288943Sdim " must have been a struct or an array!"); 969193323Sed Instruction *InsertPt = Call; 970193323Sed if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 971296417Sdim BasicBlock *NewEdge = SplitEdge(New->getParent(), II->getNormalDest()); 972296417Sdim InsertPt = &*NewEdge->getFirstInsertionPt(); 973193323Sed } 974206083Srdivacky 975288943Sdim // We used to return a struct or array. Instead of doing smart stuff 976288943Sdim // with all the uses, we will just rebuild it using extract/insertvalue 977288943Sdim // chaining and let instcombine clean that up. 978193323Sed // 979193323Sed // Start out building up our return value from undef 980198090Srdivacky Value *RetVal = UndefValue::get(RetTy); 981193323Sed for (unsigned i = 0; i != RetCount; ++i) 982193323Sed if (NewRetIdxs[i] != -1) { 983193323Sed Value *V; 984193323Sed if (RetTypes.size() > 1) 985193323Sed // We are still returning a struct, so extract the value from our 986193323Sed // return value 987193323Sed V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret", 988193323Sed InsertPt); 989193323Sed else 990193323Sed // We are now returning a single element, so just insert that 991193323Sed V = New; 992193323Sed // Insert the value at the old position 993193323Sed RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt); 994193323Sed } 995193323Sed // Now, replace all uses of the old call instruction with the return 996193323Sed // struct we built 997193323Sed Call->replaceAllUsesWith(RetVal); 998193323Sed New->takeName(Call); 999193323Sed } 1000193323Sed } 1001193323Sed 1002193323Sed // Finally, remove the old call from the program, reducing the use-count of 1003193323Sed // F. 1004193323Sed Call->eraseFromParent(); 1005193323Sed } 1006193323Sed 1007193323Sed // Since we have now created the new function, splice the body of the old 1008193323Sed // function right into the new function, leaving the old rotting hulk of the 1009193323Sed // function empty. 1010193323Sed NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 1011193323Sed 1012221345Sdim // Loop over the argument list, transferring uses of the old arguments over to 1013221345Sdim // the new arguments, also transferring over the names as well. 1014193323Sed i = 0; 1015193323Sed for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 1016193323Sed I2 = NF->arg_begin(); I != E; ++I, ++i) 1017193323Sed if (ArgAlive[i]) { 1018193323Sed // If this is a live argument, move the name and users over to the new 1019193323Sed // version. 1020296417Sdim I->replaceAllUsesWith(&*I2); 1021296417Sdim I2->takeName(&*I); 1022193323Sed ++I2; 1023193323Sed } else { 1024344779Sdim // If this argument is dead, replace any uses of it with undef 1025344779Sdim // (any non-debug value uses will get removed later on). 1026218893Sdim if (!I->getType()->isX86_MMXTy()) 1027344779Sdim I->replaceAllUsesWith(UndefValue::get(I->getType())); 1028193323Sed } 1029193323Sed 1030193323Sed // If we change the return value of the function we must rewrite any return 1031193323Sed // instructions. Check this now. 1032193323Sed if (F->getReturnType() != NF->getReturnType()) 1033309124Sdim for (BasicBlock &BB : *NF) 1034309124Sdim if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) { 1035193323Sed Value *RetVal; 1036193323Sed 1037208599Srdivacky if (NFTy->getReturnType()->isVoidTy()) { 1038276479Sdim RetVal = nullptr; 1039193323Sed } else { 1040288943Sdim assert(RetTy->isStructTy() || RetTy->isArrayTy()); 1041288943Sdim // The original return value was a struct or array, insert 1042193323Sed // extractvalue/insertvalue chains to extract only the values we need 1043193323Sed // to return and insert them into our new result. 1044193323Sed // This does generate messy code, but we'll let it to instcombine to 1045193323Sed // clean that up. 1046193323Sed Value *OldRet = RI->getOperand(0); 1047193323Sed // Start out building up our return value from undef 1048198090Srdivacky RetVal = UndefValue::get(NRetTy); 1049193323Sed for (unsigned i = 0; i != RetCount; ++i) 1050193323Sed if (NewRetIdxs[i] != -1) { 1051193323Sed ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i, 1052193323Sed "oldret", RI); 1053193323Sed if (RetTypes.size() > 1) { 1054193323Sed // We're still returning a struct, so reinsert the value into 1055193323Sed // our new return value at the new index 1056193323Sed 1057193323Sed RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i], 1058193323Sed "newret", RI); 1059193323Sed } else { 1060193323Sed // We are now only returning a simple value, so just return the 1061193323Sed // extracted value. 1062193323Sed RetVal = EV; 1063193323Sed } 1064193323Sed } 1065193323Sed } 1066193323Sed // Replace the return instruction with one returning the new return 1067193323Sed // value (possibly 0 if we became void). 1068198090Srdivacky ReturnInst::Create(F->getContext(), RetVal, RI); 1069309124Sdim BB.getInstList().erase(RI); 1070193323Sed } 1071193323Sed 1072341825Sdim // Clone metadatas from the old function, including debug info descriptor. 1073341825Sdim SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; 1074341825Sdim F->getAllMetadata(MDs); 1075341825Sdim for (auto MD : MDs) 1076341825Sdim NF->addMetadata(MD.first, *MD.second); 1077243830Sdim 1078193323Sed // Now that the old function is dead, delete it. 1079193323Sed F->eraseFromParent(); 1080193323Sed 1081193323Sed return true; 1082193323Sed} 1083193323Sed 1084309124SdimPreservedAnalyses DeadArgumentEliminationPass::run(Module &M, 1085309124Sdim ModuleAnalysisManager &) { 1086193323Sed bool Changed = false; 1087193323Sed 1088193323Sed // First pass: Do a simple check to see if any functions can have their "..." 1089193323Sed // removed. We can do this if they never call va_start. This loop cannot be 1090193323Sed // fused with the next loop, because deleting a function invalidates 1091193323Sed // information computed while surveying other functions. 1092341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n"); 1093193323Sed for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1094193323Sed Function &F = *I++; 1095193323Sed if (F.getFunctionType()->isVarArg()) 1096193323Sed Changed |= DeleteDeadVarargs(F); 1097193323Sed } 1098193323Sed 1099193323Sed // Second phase:loop through the module, determining which arguments are live. 1100193323Sed // We assume all arguments are dead unless proven otherwise (allowing us to 1101193323Sed // determine that dead arguments passed into recursive functions are dead). 1102193323Sed // 1103341825Sdim LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n"); 1104280031Sdim for (auto &F : M) 1105280031Sdim SurveyFunction(F); 1106206083Srdivacky 1107193323Sed // Now, remove all dead arguments and return values from each function in 1108206083Srdivacky // turn. 1109193323Sed for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { 1110206083Srdivacky // Increment now, because the function will probably get removed (ie. 1111193323Sed // replaced by a new one). 1112296417Sdim Function *F = &*I++; 1113193323Sed Changed |= RemoveDeadStuffFromFunction(F); 1114193323Sed } 1115218893Sdim 1116218893Sdim // Finally, look for any unused parameters in functions with non-local 1117218893Sdim // linkage and replace the passed in parameters with undef. 1118280031Sdim for (auto &F : M) 1119218893Sdim Changed |= RemoveDeadArgumentsFromCallers(F); 1120218893Sdim 1121309124Sdim if (!Changed) 1122309124Sdim return PreservedAnalyses::all(); 1123309124Sdim return PreservedAnalyses::none(); 1124193323Sed} 1125