1 //===- DeadArgumentElimination.cpp - Eliminate dead arguments -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass deletes dead arguments from internal functions. Dead argument
11 // elimination removes arguments which are directly dead, as well as arguments
12 // only passed into function calls as dead arguments of other functions. This
13 // pass also deletes dead return values in a similar way.
15 // This pass is often useful as a cleanup pass to run after aggressive
16 // interprocedural passes, which add possibly-dead arguments or return values.
18 //===----------------------------------------------------------------------===//
20 #include "llvm/Transforms/IPO/DeadArgumentElimination.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/IR/Argument.h"
24 #include "llvm/IR/Attributes.h"
25 #include "llvm/IR/BasicBlock.h"
26 #include "llvm/IR/CallSite.h"
27 #include "llvm/IR/Constant.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DerivedTypes.h"
30 #include "llvm/IR/Function.h"
31 #include "llvm/IR/InstrTypes.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/IR/Module.h"
37 #include "llvm/IR/PassManager.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/IR/Use.h"
40 #include "llvm/IR/User.h"
41 #include "llvm/IR/Value.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/raw_ostream.h"
46 #include "llvm/Transforms/IPO.h"
47 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
55 #define DEBUG_TYPE "deadargelim"
57 STATISTIC(NumArgumentsEliminated, "Number of unread args removed");
58 STATISTIC(NumRetValsEliminated , "Number of unused return values removed");
59 STATISTIC(NumArgumentsReplacedWithUndef,
60 "Number of unread args replaced with undef");
64 /// DAE - The dead argument elimination pass.
65 class DAE : public ModulePass {
67 // DAH uses this to specify a different ID.
68 explicit DAE(char &ID) : ModulePass(ID) {}
71 static char ID; // Pass identification, replacement for typeid
73 DAE() : ModulePass(ID) {
74 initializeDAEPass(*PassRegistry::getPassRegistry());
77 bool runOnModule(Module &M) override {
80 DeadArgumentEliminationPass DAEP(ShouldHackArguments());
81 ModuleAnalysisManager DummyMAM;
82 PreservedAnalyses PA = DAEP.run(M, DummyMAM);
83 return !PA.areAllPreserved();
86 virtual bool ShouldHackArguments() const { return false; }
89 } // end anonymous namespace
93 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false)
97 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but
98 /// deletes arguments to functions which are external. This is only for use
100 struct DAH : public DAE {
105 bool ShouldHackArguments() const override { return true; }
108 } // end anonymous namespace
112 INITIALIZE_PASS(DAH, "deadarghaX0r",
113 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",
116 /// createDeadArgEliminationPass - This pass removes arguments from functions
117 /// which are not used by the body of the function.
118 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }
120 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); }
122 /// DeleteDeadVarargs - If this is an function that takes a ... list, and if
123 /// llvm.vastart is never called, the varargs list is dead for the function.
124 bool DeadArgumentEliminationPass::DeleteDeadVarargs(Function &Fn) {
125 assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!");
126 if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false;
128 // Ensure that the function is only directly called.
129 if (Fn.hasAddressTaken())
132 // Don't touch naked functions. The assembly might be using an argument, or
133 // otherwise rely on the frame layout in a way that this analysis will not
135 if (Fn.hasFnAttribute(Attribute::Naked)) {
139 // Okay, we know we can transform this function if safe. Scan its body
140 // looking for calls marked musttail or calls to llvm.vastart.
141 for (BasicBlock &BB : Fn) {
142 for (Instruction &I : BB) {
143 CallInst *CI = dyn_cast<CallInst>(&I);
146 if (CI->isMustTailCall())
148 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
149 if (II->getIntrinsicID() == Intrinsic::vastart)
155 // If we get here, there are no calls to llvm.vastart in the function body,
156 // remove the "..." and adjust all the calls.
158 // Start by computing a new prototype for the function, which is the same as
159 // the old function, but doesn't have isVarArg set.
160 FunctionType *FTy = Fn.getFunctionType();
162 std::vector<Type *> Params(FTy->param_begin(), FTy->param_end());
163 FunctionType *NFTy = FunctionType::get(FTy->getReturnType(),
165 unsigned NumArgs = Params.size();
167 // Create the new function body and insert it into the module...
168 Function *NF = Function::Create(NFTy, Fn.getLinkage());
169 NF->copyAttributesFrom(&Fn);
170 NF->setComdat(Fn.getComdat());
171 Fn.getParent()->getFunctionList().insert(Fn.getIterator(), NF);
174 // Loop over all of the callers of the function, transforming the call sites
175 // to pass in a smaller number of arguments into the new function.
177 std::vector<Value *> Args;
178 for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) {
182 Instruction *Call = CS.getInstruction();
184 // Pass all the same arguments.
185 Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs);
187 // Drop any attributes that were on the vararg arguments.
188 AttributeList PAL = CS.getAttributes();
189 if (!PAL.isEmpty()) {
190 SmallVector<AttributeSet, 8> ArgAttrs;
191 for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo)
192 ArgAttrs.push_back(PAL.getParamAttributes(ArgNo));
193 PAL = AttributeList::get(Fn.getContext(), PAL.getFnAttributes(),
194 PAL.getRetAttributes(), ArgAttrs);
197 SmallVector<OperandBundleDef, 1> OpBundles;
198 CS.getOperandBundlesAsDefs(OpBundles);
201 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
202 NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
203 Args, OpBundles, "", Call);
205 NewCS = CallInst::Create(NF, Args, OpBundles, "", Call);
206 cast<CallInst>(NewCS.getInstruction())
207 ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind());
209 NewCS.setCallingConv(CS.getCallingConv());
210 NewCS.setAttributes(PAL);
211 NewCS->setDebugLoc(Call->getDebugLoc());
213 if (Call->extractProfTotalWeight(W))
214 NewCS->setProfWeight(W);
218 if (!Call->use_empty())
219 Call->replaceAllUsesWith(NewCS.getInstruction());
221 NewCS->takeName(Call);
223 // Finally, remove the old call from the program, reducing the use-count of
225 Call->eraseFromParent();
228 // Since we have now created the new function, splice the body of the old
229 // function right into the new function, leaving the old rotting hulk of the
231 NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList());
233 // Loop over the argument list, transferring uses of the old arguments over to
234 // the new arguments, also transferring over the names as well. While we're at
235 // it, remove the dead arguments from the DeadArguments list.
236 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(),
237 I2 = NF->arg_begin(); I != E; ++I, ++I2) {
238 // Move the name and users over to the new version.
239 I->replaceAllUsesWith(&*I2);
243 // Patch the pointer to LLVM function in debug info descriptor.
244 NF->setSubprogram(Fn.getSubprogram());
246 // Fix up any BlockAddresses that refer to the function.
247 Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType()));
248 // Delete the bitcast that we just created, so that NF does not
249 // appear to be address-taken.
250 NF->removeDeadConstantUsers();
251 // Finally, nuke the old function.
252 Fn.eraseFromParent();
256 /// RemoveDeadArgumentsFromCallers - Checks if the given function has any
257 /// arguments that are unused, and changes the caller parameters to be undefined
259 bool DeadArgumentEliminationPass::RemoveDeadArgumentsFromCallers(Function &Fn) {
260 // We cannot change the arguments if this TU does not define the function or
261 // if the linker may choose a function body from another TU, even if the
262 // nominal linkage indicates that other copies of the function have the same
263 // semantics. In the below example, the dead load from %p may not have been
264 // eliminated from the linker-chosen copy of f, so replacing %p with undef
265 // in callers may introduce undefined behavior.
267 // define linkonce_odr void @f(i32* %p) {
271 if (!Fn.hasExactDefinition())
274 // Functions with local linkage should already have been handled, except the
275 // fragile (variadic) ones which we can improve here.
276 if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg())
279 // Don't touch naked functions. The assembly might be using an argument, or
280 // otherwise rely on the frame layout in a way that this analysis will not
282 if (Fn.hasFnAttribute(Attribute::Naked))
288 SmallVector<unsigned, 8> UnusedArgs;
289 for (Argument &Arg : Fn.args()) {
290 if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() && !Arg.hasByValOrInAllocaAttr())
291 UnusedArgs.push_back(Arg.getArgNo());
294 if (UnusedArgs.empty())
297 bool Changed = false;
299 for (Use &U : Fn.uses()) {
300 CallSite CS(U.getUser());
301 if (!CS || !CS.isCallee(&U))
304 // Now go through all unused args and replace them with "undef".
305 for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) {
306 unsigned ArgNo = UnusedArgs[I];
308 Value *Arg = CS.getArgument(ArgNo);
309 CS.setArgument(ArgNo, UndefValue::get(Arg->getType()));
310 ++NumArgumentsReplacedWithUndef;
318 /// Convenience function that returns the number of return values. It returns 0
319 /// for void functions and 1 for functions not returning a struct. It returns
320 /// the number of struct elements for functions returning a struct.
321 static unsigned NumRetVals(const Function *F) {
322 Type *RetTy = F->getReturnType();
323 if (RetTy->isVoidTy())
325 else if (StructType *STy = dyn_cast<StructType>(RetTy))
326 return STy->getNumElements();
327 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy))
328 return ATy->getNumElements();
333 /// Returns the sub-type a function will return at a given Idx. Should
334 /// correspond to the result type of an ExtractValue instruction executed with
335 /// just that one Idx (i.e. only top-level structure is considered).
336 static Type *getRetComponentType(const Function *F, unsigned Idx) {
337 Type *RetTy = F->getReturnType();
338 assert(!RetTy->isVoidTy() && "void type has no subtype");
340 if (StructType *STy = dyn_cast<StructType>(RetTy))
341 return STy->getElementType(Idx);
342 else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy))
343 return ATy->getElementType();
348 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not
349 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined
351 DeadArgumentEliminationPass::Liveness
352 DeadArgumentEliminationPass::MarkIfNotLive(RetOrArg Use,
353 UseVector &MaybeLiveUses) {
354 // We're live if our use or its Function is already marked as live.
355 if (LiveFunctions.count(Use.F) || LiveValues.count(Use))
358 // We're maybe live otherwise, but remember that we must become live if
360 MaybeLiveUses.push_back(Use);
364 /// SurveyUse - This looks at a single use of an argument or return value
365 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses
366 /// if it causes the used value to become MaybeLive.
368 /// RetValNum is the return value number to use when this use is used in a
369 /// return instruction. This is used in the recursion, you should always leave
371 DeadArgumentEliminationPass::Liveness
372 DeadArgumentEliminationPass::SurveyUse(const Use *U, UseVector &MaybeLiveUses,
373 unsigned RetValNum) {
374 const User *V = U->getUser();
375 if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) {
376 // The value is returned from a function. It's only live when the
377 // function's return value is live. We use RetValNum here, for the case
378 // that U is really a use of an insertvalue instruction that uses the
380 const Function *F = RI->getParent()->getParent();
381 if (RetValNum != -1U) {
382 RetOrArg Use = CreateRet(F, RetValNum);
383 // We might be live, depending on the liveness of Use.
384 return MarkIfNotLive(Use, MaybeLiveUses);
386 DeadArgumentEliminationPass::Liveness Result = MaybeLive;
387 for (unsigned i = 0; i < NumRetVals(F); ++i) {
388 RetOrArg Use = CreateRet(F, i);
389 // We might be live, depending on the liveness of Use. If any
390 // sub-value is live, then the entire value is considered live. This
391 // is a conservative choice, and better tracking is possible.
392 DeadArgumentEliminationPass::Liveness SubResult =
393 MarkIfNotLive(Use, MaybeLiveUses);
400 if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) {
401 if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex()
403 // The use we are examining is inserted into an aggregate. Our liveness
404 // depends on all uses of that aggregate, but if it is used as a return
405 // value, only index at which we were inserted counts.
406 RetValNum = *IV->idx_begin();
408 // Note that if we are used as the aggregate operand to the insertvalue,
409 // we don't change RetValNum, but do survey all our uses.
411 Liveness Result = MaybeLive;
412 for (const Use &UU : IV->uses()) {
413 Result = SurveyUse(&UU, MaybeLiveUses, RetValNum);
420 if (auto CS = ImmutableCallSite(V)) {
421 const Function *F = CS.getCalledFunction();
423 // Used in a direct call.
425 // The function argument is live if it is used as a bundle operand.
426 if (CS.isBundleOperand(U))
429 // Find the argument number. We know for sure that this use is an
430 // argument, since if it was the function argument this would be an
431 // indirect call and the we know can't be looking at a value of the
432 // label type (for the invoke instruction).
433 unsigned ArgNo = CS.getArgumentNo(U);
435 if (ArgNo >= F->getFunctionType()->getNumParams())
436 // The value is passed in through a vararg! Must be live.
439 assert(CS.getArgument(ArgNo)
440 == CS->getOperand(U->getOperandNo())
441 && "Argument is not where we expected it");
443 // Value passed to a normal call. It's only live when the corresponding
444 // argument to the called function turns out live.
445 RetOrArg Use = CreateArg(F, ArgNo);
446 return MarkIfNotLive(Use, MaybeLiveUses);
449 // Used in any other way? Value must be live.
453 /// SurveyUses - This looks at all the uses of the given value
454 /// Returns the Liveness deduced from the uses of this value.
456 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If
457 /// the result is Live, MaybeLiveUses might be modified but its content should
458 /// be ignored (since it might not be complete).
459 DeadArgumentEliminationPass::Liveness
460 DeadArgumentEliminationPass::SurveyUses(const Value *V,
461 UseVector &MaybeLiveUses) {
462 // Assume it's dead (which will only hold if there are no uses at all..).
463 Liveness Result = MaybeLive;
465 for (const Use &U : V->uses()) {
466 Result = SurveyUse(&U, MaybeLiveUses);
473 // SurveyFunction - This performs the initial survey of the specified function,
474 // checking out whether or not it uses any of its incoming arguments or whether
475 // any callers use the return value. This fills in the LiveValues set and Uses
478 // We consider arguments of non-internal functions to be intrinsically alive as
479 // well as arguments to functions which have their "address taken".
480 void DeadArgumentEliminationPass::SurveyFunction(const Function &F) {
481 // Functions with inalloca parameters are expecting args in a particular
482 // register and memory layout.
483 if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) {
488 // Don't touch naked functions. The assembly might be using an argument, or
489 // otherwise rely on the frame layout in a way that this analysis will not
491 if (F.hasFnAttribute(Attribute::Naked)) {
496 unsigned RetCount = NumRetVals(&F);
498 // Assume all return values are dead
499 using RetVals = SmallVector<Liveness, 5>;
501 RetVals RetValLiveness(RetCount, MaybeLive);
503 using RetUses = SmallVector<UseVector, 5>;
505 // These vectors map each return value to the uses that make it MaybeLive, so
506 // we can add those to the Uses map if the return value really turns out to be
507 // MaybeLive. Initialized to a list of RetCount empty lists.
508 RetUses MaybeLiveRetUses(RetCount);
510 for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
511 if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
512 if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType()
513 != F.getFunctionType()->getReturnType()) {
514 // We don't support old style multiple return values.
519 if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) {
524 DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: "
525 << F.getName() << "\n");
526 // Keep track of the number of live retvals, so we can skip checks once all
527 // of them turn out to be live.
528 unsigned NumLiveRetVals = 0;
529 // Loop all uses of the function.
530 for (const Use &U : F.uses()) {
531 // If the function is PASSED IN as an argument, its address has been
533 ImmutableCallSite CS(U.getUser());
534 if (!CS || !CS.isCallee(&U)) {
539 // If this use is anything other than a call site, the function is alive.
540 const Instruction *TheCall = CS.getInstruction();
541 if (!TheCall) { // Not a direct call site?
546 // If we end up here, we are looking at a direct call to our function.
548 // Now, check how our return value(s) is/are used in this caller. Don't
549 // bother checking return values if all of them are live already.
550 if (NumLiveRetVals == RetCount)
553 // Check all uses of the return value.
554 for (const Use &U : TheCall->uses()) {
555 if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) {
556 // This use uses a part of our return value, survey the uses of
557 // that part and store the results for this index only.
558 unsigned Idx = *Ext->idx_begin();
559 if (RetValLiveness[Idx] != Live) {
560 RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]);
561 if (RetValLiveness[Idx] == Live)
565 // Used by something else than extractvalue. Survey, but assume that the
566 // result applies to all sub-values.
567 UseVector MaybeLiveAggregateUses;
568 if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) {
569 NumLiveRetVals = RetCount;
570 RetValLiveness.assign(RetCount, Live);
573 for (unsigned i = 0; i != RetCount; ++i) {
574 if (RetValLiveness[i] != Live)
575 MaybeLiveRetUses[i].append(MaybeLiveAggregateUses.begin(),
576 MaybeLiveAggregateUses.end());
583 // Now we've inspected all callers, record the liveness of our return values.
584 for (unsigned i = 0; i != RetCount; ++i)
585 MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]);
587 DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: "
588 << F.getName() << "\n");
590 // Now, check all of our arguments.
592 UseVector MaybeLiveArgUses;
593 for (Function::const_arg_iterator AI = F.arg_begin(),
594 E = F.arg_end(); AI != E; ++AI, ++i) {
596 if (F.getFunctionType()->isVarArg()) {
597 // Variadic functions will already have a va_arg function expanded inside
598 // them, making them potentially very sensitive to ABI changes resulting
599 // from removing arguments entirely, so don't. For example AArch64 handles
600 // register and stack HFAs very differently, and this is reflected in the
601 // IR which has already been generated.
604 // See what the effect of this use is (recording any uses that cause
605 // MaybeLive in MaybeLiveArgUses).
606 Result = SurveyUses(&*AI, MaybeLiveArgUses);
610 MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses);
611 // Clear the vector again for the next iteration.
612 MaybeLiveArgUses.clear();
616 /// MarkValue - This function marks the liveness of RA depending on L. If L is
617 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses,
618 /// such that RA will be marked live if any use in MaybeLiveUses gets marked
620 void DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L,
621 const UseVector &MaybeLiveUses) {
627 // Note any uses of this value, so this return value can be
628 // marked live whenever one of the uses becomes live.
629 for (const auto &MaybeLiveUse : MaybeLiveUses)
630 Uses.insert(std::make_pair(MaybeLiveUse, RA));
635 /// MarkLive - Mark the given Function as alive, meaning that it cannot be
636 /// changed in any way. Additionally,
637 /// mark any values that are used as this function's parameters or by its return
638 /// values (according to Uses) live as well.
639 void DeadArgumentEliminationPass::MarkLive(const Function &F) {
640 DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: "
641 << F.getName() << "\n");
642 // Mark the function as live.
643 LiveFunctions.insert(&F);
644 // Mark all arguments as live.
645 for (unsigned i = 0, e = F.arg_size(); i != e; ++i)
646 PropagateLiveness(CreateArg(&F, i));
647 // Mark all return values as live.
648 for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i)
649 PropagateLiveness(CreateRet(&F, i));
652 /// MarkLive - Mark the given return value or argument as live. Additionally,
653 /// mark any values that are used by this value (according to Uses) live as
655 void DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) {
656 if (LiveFunctions.count(RA.F))
657 return; // Function was already marked Live.
659 if (!LiveValues.insert(RA).second)
660 return; // We were already marked Live.
662 DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking "
663 << RA.getDescription() << " live\n");
664 PropagateLiveness(RA);
667 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness
668 /// to any other values it uses (according to Uses).
669 void DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) {
670 // We don't use upper_bound (or equal_range) here, because our recursive call
671 // to ourselves is likely to cause the upper_bound (which is the first value
672 // not belonging to RA) to become erased and the iterator invalidated.
673 UseMap::iterator Begin = Uses.lower_bound(RA);
674 UseMap::iterator E = Uses.end();
676 for (I = Begin; I != E && I->first == RA; ++I)
679 // Erase RA from the Uses map (from the lower bound to wherever we ended up
681 Uses.erase(Begin, I);
684 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F
685 // that are not in LiveValues. Transform the function and all of the callees of
686 // the function to not have these arguments and return values.
688 bool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) {
689 // Don't modify fully live functions
690 if (LiveFunctions.count(F))
693 // Start by computing a new prototype for the function, which is the same as
694 // the old function, but has fewer arguments and a different return type.
695 FunctionType *FTy = F->getFunctionType();
696 std::vector<Type*> Params;
698 // Keep track of if we have a live 'returned' argument
699 bool HasLiveReturnedArg = false;
701 // Set up to build a new list of parameter attributes.
702 SmallVector<AttributeSet, 8> ArgAttrVec;
703 const AttributeList &PAL = F->getAttributes();
705 // Remember which arguments are still alive.
706 SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false);
707 // Construct the new parameter list from non-dead arguments. Also construct
708 // a new set of parameter attributes to correspond. Skip the first parameter
709 // attribute, since that belongs to the return value.
711 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
713 RetOrArg Arg = CreateArg(F, i);
714 if (LiveValues.erase(Arg)) {
715 Params.push_back(I->getType());
717 ArgAttrVec.push_back(PAL.getParamAttributes(i));
718 HasLiveReturnedArg |= PAL.hasParamAttribute(i, Attribute::Returned);
720 ++NumArgumentsEliminated;
721 DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument " << i
722 << " (" << I->getName() << ") from " << F->getName()
727 // Find out the new return value.
728 Type *RetTy = FTy->getReturnType();
729 Type *NRetTy = nullptr;
730 unsigned RetCount = NumRetVals(F);
732 // -1 means unused, other numbers are the new index
733 SmallVector<int, 5> NewRetIdxs(RetCount, -1);
734 std::vector<Type*> RetTypes;
736 // If there is a function with a live 'returned' argument but a dead return
737 // value, then there are two possible actions:
738 // 1) Eliminate the return value and take off the 'returned' attribute on the
740 // 2) Retain the 'returned' attribute and treat the return value (but not the
741 // entire function) as live so that it is not eliminated.
743 // It's not clear in the general case which option is more profitable because,
744 // even in the absence of explicit uses of the return value, code generation
745 // is free to use the 'returned' attribute to do things like eliding
746 // save/restores of registers across calls. Whether or not this happens is
747 // target and ABI-specific as well as depending on the amount of register
748 // pressure, so there's no good way for an IR-level pass to figure this out.
750 // Fortunately, the only places where 'returned' is currently generated by
751 // the FE are places where 'returned' is basically free and almost always a
752 // performance win, so the second option can just be used always for now.
754 // This should be revisited if 'returned' is ever applied more liberally.
755 if (RetTy->isVoidTy() || HasLiveReturnedArg) {
758 // Look at each of the original return values individually.
759 for (unsigned i = 0; i != RetCount; ++i) {
760 RetOrArg Ret = CreateRet(F, i);
761 if (LiveValues.erase(Ret)) {
762 RetTypes.push_back(getRetComponentType(F, i));
763 NewRetIdxs[i] = RetTypes.size() - 1;
765 ++NumRetValsEliminated;
766 DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing return value "
767 << i << " from " << F->getName() << "\n");
770 if (RetTypes.size() > 1) {
771 // More than one return type? Reduce it down to size.
772 if (StructType *STy = dyn_cast<StructType>(RetTy)) {
773 // Make the new struct packed if we used to return a packed struct
775 NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked());
777 assert(isa<ArrayType>(RetTy) && "unexpected multi-value return");
778 NRetTy = ArrayType::get(RetTypes[0], RetTypes.size());
780 } else if (RetTypes.size() == 1)
781 // One return type? Just a simple value then, but only if we didn't use to
782 // return a struct with that simple value before.
783 NRetTy = RetTypes.front();
784 else if (RetTypes.empty())
785 // No return types? Make it void, but only if we didn't use to return {}.
786 NRetTy = Type::getVoidTy(F->getContext());
789 assert(NRetTy && "No new return type found?");
791 // The existing function return attributes.
792 AttrBuilder RAttrs(PAL.getRetAttributes());
794 // Remove any incompatible attributes, but only if we removed all return
795 // values. Otherwise, ensure that we don't have any conflicting attributes
796 // here. Currently, this should not be possible, but special handling might be
797 // required when new return value attributes are added.
798 if (NRetTy->isVoidTy())
799 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy));
801 assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) &&
802 "Return attributes no longer compatible?");
804 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs);
806 // Reconstruct the AttributesList based on the vector we constructed.
807 assert(ArgAttrVec.size() == Params.size());
808 AttributeList NewPAL = AttributeList::get(
809 F->getContext(), PAL.getFnAttributes(), RetAttrs, ArgAttrVec);
811 // Create the new function type based on the recomputed parameters.
812 FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg());
818 // Create the new function body and insert it into the module...
819 Function *NF = Function::Create(NFTy, F->getLinkage());
820 NF->copyAttributesFrom(F);
821 NF->setComdat(F->getComdat());
822 NF->setAttributes(NewPAL);
823 // Insert the new function before the old function, so we won't be processing
825 F->getParent()->getFunctionList().insert(F->getIterator(), NF);
828 // Loop over all of the callers of the function, transforming the call sites
829 // to pass in a smaller number of arguments into the new function.
830 std::vector<Value*> Args;
831 while (!F->use_empty()) {
832 CallSite CS(F->user_back());
833 Instruction *Call = CS.getInstruction();
836 const AttributeList &CallPAL = CS.getAttributes();
838 // Adjust the call return attributes in case the function was changed to
840 AttrBuilder RAttrs(CallPAL.getRetAttributes());
841 RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy));
842 AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs);
844 // Declare these outside of the loops, so we can reuse them for the second
845 // loop, which loops the varargs.
846 CallSite::arg_iterator I = CS.arg_begin();
848 // Loop over those operands, corresponding to the normal arguments to the
849 // original function, and add those that are still alive.
850 for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i)
853 // Get original parameter attributes, but skip return attributes.
854 AttributeSet Attrs = CallPAL.getParamAttributes(i);
855 if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) {
856 // If the return type has changed, then get rid of 'returned' on the
857 // call site. The alternative is to make all 'returned' attributes on
858 // call sites keep the return value alive just like 'returned'
859 // attributes on function declaration but it's less clearly a win and
860 // this is not an expected case anyway
861 ArgAttrVec.push_back(AttributeSet::get(
863 AttrBuilder(Attrs).removeAttribute(Attribute::Returned)));
865 // Otherwise, use the original attributes.
866 ArgAttrVec.push_back(Attrs);
870 // Push any varargs arguments on the list. Don't forget their attributes.
871 for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) {
873 ArgAttrVec.push_back(CallPAL.getParamAttributes(i));
876 // Reconstruct the AttributesList based on the vector we constructed.
877 assert(ArgAttrVec.size() == Args.size());
878 AttributeList NewCallPAL = AttributeList::get(
879 F->getContext(), CallPAL.getFnAttributes(), RetAttrs, ArgAttrVec);
881 SmallVector<OperandBundleDef, 1> OpBundles;
882 CS.getOperandBundlesAsDefs(OpBundles);
885 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
886 NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
887 Args, OpBundles, "", Call->getParent());
889 NewCS = CallInst::Create(NF, Args, OpBundles, "", Call);
890 cast<CallInst>(NewCS.getInstruction())
891 ->setTailCallKind(cast<CallInst>(Call)->getTailCallKind());
893 NewCS.setCallingConv(CS.getCallingConv());
894 NewCS.setAttributes(NewCallPAL);
895 NewCS->setDebugLoc(Call->getDebugLoc());
897 if (Call->extractProfTotalWeight(W))
898 NewCS->setProfWeight(W);
902 Instruction *New = NewCS.getInstruction();
903 if (!Call->use_empty()) {
904 if (New->getType() == Call->getType()) {
905 // Return type not changed? Just replace users then.
906 Call->replaceAllUsesWith(New);
908 } else if (New->getType()->isVoidTy()) {
909 // Our return value has uses, but they will get removed later on.
910 // Replace by null for now.
911 if (!Call->getType()->isX86_MMXTy())
912 Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
914 assert((RetTy->isStructTy() || RetTy->isArrayTy()) &&
915 "Return type changed, but not into a void. The old return type"
916 " must have been a struct or an array!");
917 Instruction *InsertPt = Call;
918 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
919 BasicBlock *NewEdge = SplitEdge(New->getParent(), II->getNormalDest());
920 InsertPt = &*NewEdge->getFirstInsertionPt();
923 // We used to return a struct or array. Instead of doing smart stuff
924 // with all the uses, we will just rebuild it using extract/insertvalue
925 // chaining and let instcombine clean that up.
927 // Start out building up our return value from undef
928 Value *RetVal = UndefValue::get(RetTy);
929 for (unsigned i = 0; i != RetCount; ++i)
930 if (NewRetIdxs[i] != -1) {
932 if (RetTypes.size() > 1)
933 // We are still returning a struct, so extract the value from our
935 V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret",
938 // We are now returning a single element, so just insert that
940 // Insert the value at the old position
941 RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt);
943 // Now, replace all uses of the old call instruction with the return
945 Call->replaceAllUsesWith(RetVal);
950 // Finally, remove the old call from the program, reducing the use-count of
952 Call->eraseFromParent();
955 // Since we have now created the new function, splice the body of the old
956 // function right into the new function, leaving the old rotting hulk of the
958 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
960 // Loop over the argument list, transferring uses of the old arguments over to
961 // the new arguments, also transferring over the names as well.
963 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
964 I2 = NF->arg_begin(); I != E; ++I, ++i)
966 // If this is a live argument, move the name and users over to the new
968 I->replaceAllUsesWith(&*I2);
972 // If this argument is dead, replace any uses of it with null constants
973 // (these are guaranteed to become unused later on).
974 if (!I->getType()->isX86_MMXTy())
975 I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
978 // If we change the return value of the function we must rewrite any return
979 // instructions. Check this now.
980 if (F->getReturnType() != NF->getReturnType())
981 for (BasicBlock &BB : *NF)
982 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
985 if (NFTy->getReturnType()->isVoidTy()) {
988 assert(RetTy->isStructTy() || RetTy->isArrayTy());
989 // The original return value was a struct or array, insert
990 // extractvalue/insertvalue chains to extract only the values we need
991 // to return and insert them into our new result.
992 // This does generate messy code, but we'll let it to instcombine to
994 Value *OldRet = RI->getOperand(0);
995 // Start out building up our return value from undef
996 RetVal = UndefValue::get(NRetTy);
997 for (unsigned i = 0; i != RetCount; ++i)
998 if (NewRetIdxs[i] != -1) {
999 ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i,
1001 if (RetTypes.size() > 1) {
1002 // We're still returning a struct, so reinsert the value into
1003 // our new return value at the new index
1005 RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i],
1008 // We are now only returning a simple value, so just return the
1014 // Replace the return instruction with one returning the new return
1015 // value (possibly 0 if we became void).
1016 ReturnInst::Create(F->getContext(), RetVal, RI);
1017 BB.getInstList().erase(RI);
1020 // Patch the pointer to LLVM function in debug info descriptor.
1021 NF->setSubprogram(F->getSubprogram());
1023 // Now that the old function is dead, delete it.
1024 F->eraseFromParent();
1029 PreservedAnalyses DeadArgumentEliminationPass::run(Module &M,
1030 ModuleAnalysisManager &) {
1031 bool Changed = false;
1033 // First pass: Do a simple check to see if any functions can have their "..."
1034 // removed. We can do this if they never call va_start. This loop cannot be
1035 // fused with the next loop, because deleting a function invalidates
1036 // information computed while surveying other functions.
1037 DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n");
1038 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
1040 if (F.getFunctionType()->isVarArg())
1041 Changed |= DeleteDeadVarargs(F);
1044 // Second phase:loop through the module, determining which arguments are live.
1045 // We assume all arguments are dead unless proven otherwise (allowing us to
1046 // determine that dead arguments passed into recursive functions are dead).
1048 DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n");
1052 // Now, remove all dead arguments and return values from each function in
1054 for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
1055 // Increment now, because the function will probably get removed (ie.
1056 // replaced by a new one).
1057 Function *F = &*I++;
1058 Changed |= RemoveDeadStuffFromFunction(F);
1061 // Finally, look for any unused parameters in functions with non-local
1062 // linkage and replace the passed in parameters with undef.
1064 Changed |= RemoveDeadArgumentsFromCallers(F);
1067 return PreservedAnalyses::all();
1068 return PreservedAnalyses::none();