xref: /netbsd-src/external/apache2/llvm/dist/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp (revision 82d56013d7b633d116a93943de88e08335357a7c)
1 //===- DeadArgumentElimination.cpp - Eliminate dead arguments -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass deletes dead arguments from internal functions.  Dead argument
10 // elimination removes arguments which are directly dead, as well as arguments
11 // only passed into function calls as dead arguments of other functions.  This
12 // pass also deletes dead return values in a similar way.
13 //
14 // This pass is often useful as a cleanup pass to run after aggressive
15 // interprocedural passes, which add possibly-dead arguments or return values.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "llvm/Transforms/IPO/DeadArgumentElimination.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/Argument.h"
23 #include "llvm/IR/Attributes.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/IRBuilder.h"
29 #include "llvm/IR/InstrTypes.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Intrinsics.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/IR/NoFolder.h"
36 #include "llvm/IR/PassManager.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Use.h"
39 #include "llvm/IR/User.h"
40 #include "llvm/IR/Value.h"
41 #include "llvm/InitializePasses.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/raw_ostream.h"
46 #include "llvm/Transforms/IPO.h"
47 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
48 #include <cassert>
49 #include <cstdint>
50 #include <utility>
51 #include <vector>
52 
53 using namespace llvm;
54 
55 #define DEBUG_TYPE "deadargelim"
56 
57 STATISTIC(NumArgumentsEliminated, "Number of unread args removed");
58 STATISTIC(NumRetValsEliminated  , "Number of unused return values removed");
59 STATISTIC(NumArgumentsReplacedWithUndef,
60           "Number of unread args replaced with undef");
61 
62 namespace {
63 
64   /// DAE - The dead argument elimination pass.
65   class DAE : public ModulePass {
66   protected:
67     // DAH uses this to specify a different ID.
DAE(char & ID)68     explicit DAE(char &ID) : ModulePass(ID) {}
69 
70   public:
71     static char ID; // Pass identification, replacement for typeid
72 
DAE()73     DAE() : ModulePass(ID) {
74       initializeDAEPass(*PassRegistry::getPassRegistry());
75     }
76 
runOnModule(Module & M)77     bool runOnModule(Module &M) override {
78       if (skipModule(M))
79         return false;
80       DeadArgumentEliminationPass DAEP(ShouldHackArguments());
81       ModuleAnalysisManager DummyMAM;
82       PreservedAnalyses PA = DAEP.run(M, DummyMAM);
83       return !PA.areAllPreserved();
84     }
85 
ShouldHackArguments() const86     virtual bool ShouldHackArguments() const { return false; }
87   };
88 
89 } // end anonymous namespace
90 
91 char DAE::ID = 0;
92 
93 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false)
94 
95 namespace {
96 
97   /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but
98   /// deletes arguments to functions which are external.  This is only for use
99   /// by bugpoint.
100   struct DAH : public DAE {
101     static char ID;
102 
DAH__anon22be61fa0211::DAH103     DAH() : DAE(ID) {}
104 
ShouldHackArguments__anon22be61fa0211::DAH105     bool ShouldHackArguments() const override { return true; }
106   };
107 
108 } // end anonymous namespace
109 
110 char DAH::ID = 0;
111 
112 INITIALIZE_PASS(DAH, "deadarghaX0r",
113                 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",
114                 false, false)
115 
116 /// createDeadArgEliminationPass - This pass removes arguments from functions
117 /// which are not used by the body of the function.
createDeadArgEliminationPass()118 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }
119 
createDeadArgHackingPass()120 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); }
121 
122 /// DeleteDeadVarargs - If this is an function that takes a ... list, and if
123 /// llvm.vastart is never called, the varargs list is dead for the function.
DeleteDeadVarargs(Function & Fn)124 bool DeadArgumentEliminationPass::DeleteDeadVarargs(Function &Fn) {
125   assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!");
126   if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false;
127 
128   // Ensure that the function is only directly called.
129   if (Fn.hasAddressTaken())
130     return false;
131 
132   // Don't touch naked functions. The assembly might be using an argument, or
133   // otherwise rely on the frame layout in a way that this analysis will not
134   // see.
135   if (Fn.hasFnAttribute(Attribute::Naked)) {
136     return false;
137   }
138 
139   // Okay, we know we can transform this function if safe.  Scan its body
140   // looking for calls marked musttail or calls to llvm.vastart.
141   for (BasicBlock &BB : Fn) {
142     for (Instruction &I : BB) {
143       CallInst *CI = dyn_cast<CallInst>(&I);
144       if (!CI)
145         continue;
146       if (CI->isMustTailCall())
147         return false;
148       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CI)) {
149         if (II->getIntrinsicID() == Intrinsic::vastart)
150           return false;
151       }
152     }
153   }
154 
155   // If we get here, there are no calls to llvm.vastart in the function body,
156   // remove the "..." and adjust all the calls.
157 
158   // Start by computing a new prototype for the function, which is the same as
159   // the old function, but doesn't have isVarArg set.
160   FunctionType *FTy = Fn.getFunctionType();
161 
162   std::vector<Type *> Params(FTy->param_begin(), FTy->param_end());
163   FunctionType *NFTy = FunctionType::get(FTy->getReturnType(),
164                                                 Params, false);
165   unsigned NumArgs = Params.size();
166 
167   // Create the new function body and insert it into the module...
168   Function *NF = Function::Create(NFTy, Fn.getLinkage(), Fn.getAddressSpace());
169   NF->copyAttributesFrom(&Fn);
170   NF->setComdat(Fn.getComdat());
171   Fn.getParent()->getFunctionList().insert(Fn.getIterator(), NF);
172   NF->takeName(&Fn);
173 
174   // Loop over all of the callers of the function, transforming the call sites
175   // to pass in a smaller number of arguments into the new function.
176   //
177   std::vector<Value *> Args;
178   for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) {
179     CallBase *CB = dyn_cast<CallBase>(*I++);
180     if (!CB)
181       continue;
182 
183     // Pass all the same arguments.
184     Args.assign(CB->arg_begin(), CB->arg_begin() + NumArgs);
185 
186     // Drop any attributes that were on the vararg arguments.
187     AttributeList PAL = CB->getAttributes();
188     if (!PAL.isEmpty()) {
189       SmallVector<AttributeSet, 8> ArgAttrs;
190       for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo)
191         ArgAttrs.push_back(PAL.getParamAttributes(ArgNo));
192       PAL = AttributeList::get(Fn.getContext(), PAL.getFnAttributes(),
193                                PAL.getRetAttributes(), ArgAttrs);
194     }
195 
196     SmallVector<OperandBundleDef, 1> OpBundles;
197     CB->getOperandBundlesAsDefs(OpBundles);
198 
199     CallBase *NewCB = nullptr;
200     if (InvokeInst *II = dyn_cast<InvokeInst>(CB)) {
201       NewCB = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
202                                  Args, OpBundles, "", CB);
203     } else {
204       NewCB = CallInst::Create(NF, Args, OpBundles, "", CB);
205       cast<CallInst>(NewCB)->setTailCallKind(
206           cast<CallInst>(CB)->getTailCallKind());
207     }
208     NewCB->setCallingConv(CB->getCallingConv());
209     NewCB->setAttributes(PAL);
210     NewCB->copyMetadata(*CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
211 
212     Args.clear();
213 
214     if (!CB->use_empty())
215       CB->replaceAllUsesWith(NewCB);
216 
217     NewCB->takeName(CB);
218 
219     // Finally, remove the old call from the program, reducing the use-count of
220     // F.
221     CB->eraseFromParent();
222   }
223 
224   // Since we have now created the new function, splice the body of the old
225   // function right into the new function, leaving the old rotting hulk of the
226   // function empty.
227   NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList());
228 
229   // Loop over the argument list, transferring uses of the old arguments over to
230   // the new arguments, also transferring over the names as well.  While we're at
231   // it, remove the dead arguments from the DeadArguments list.
232   for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(),
233        I2 = NF->arg_begin(); I != E; ++I, ++I2) {
234     // Move the name and users over to the new version.
235     I->replaceAllUsesWith(&*I2);
236     I2->takeName(&*I);
237   }
238 
239   // Clone metadatas from the old function, including debug info descriptor.
240   SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
241   Fn.getAllMetadata(MDs);
242   for (auto MD : MDs)
243     NF->addMetadata(MD.first, *MD.second);
244 
245   // Fix up any BlockAddresses that refer to the function.
246   Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType()));
247   // Delete the bitcast that we just created, so that NF does not
248   // appear to be address-taken.
249   NF->removeDeadConstantUsers();
250   // Finally, nuke the old function.
251   Fn.eraseFromParent();
252   return true;
253 }
254 
255 /// RemoveDeadArgumentsFromCallers - Checks if the given function has any
256 /// arguments that are unused, and changes the caller parameters to be undefined
257 /// instead.
RemoveDeadArgumentsFromCallers(Function & Fn)258 bool DeadArgumentEliminationPass::RemoveDeadArgumentsFromCallers(Function &Fn) {
259   // We cannot change the arguments if this TU does not define the function or
260   // if the linker may choose a function body from another TU, even if the
261   // nominal linkage indicates that other copies of the function have the same
262   // semantics. In the below example, the dead load from %p may not have been
263   // eliminated from the linker-chosen copy of f, so replacing %p with undef
264   // in callers may introduce undefined behavior.
265   //
266   // define linkonce_odr void @f(i32* %p) {
267   //   %v = load i32 %p
268   //   ret void
269   // }
270   if (!Fn.hasExactDefinition())
271     return false;
272 
273   // Functions with local linkage should already have been handled, except the
274   // fragile (variadic) ones which we can improve here.
275   if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg())
276     return false;
277 
278   // Don't touch naked functions. The assembly might be using an argument, or
279   // otherwise rely on the frame layout in a way that this analysis will not
280   // see.
281   if (Fn.hasFnAttribute(Attribute::Naked))
282     return false;
283 
284   if (Fn.use_empty())
285     return false;
286 
287   SmallVector<unsigned, 8> UnusedArgs;
288   bool Changed = false;
289 
290   for (Argument &Arg : Fn.args()) {
291     if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() &&
292         !Arg.hasPassPointeeByValueCopyAttr()) {
293       if (Arg.isUsedByMetadata()) {
294         Arg.replaceAllUsesWith(UndefValue::get(Arg.getType()));
295         Changed = true;
296       }
297       UnusedArgs.push_back(Arg.getArgNo());
298       Fn.removeParamUndefImplyingAttrs(Arg.getArgNo());
299     }
300   }
301 
302   if (UnusedArgs.empty())
303     return false;
304 
305   for (Use &U : Fn.uses()) {
306     CallBase *CB = dyn_cast<CallBase>(U.getUser());
307     if (!CB || !CB->isCallee(&U))
308       continue;
309 
310     // Now go through all unused args and replace them with "undef".
311     for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) {
312       unsigned ArgNo = UnusedArgs[I];
313 
314       Value *Arg = CB->getArgOperand(ArgNo);
315       CB->setArgOperand(ArgNo, UndefValue::get(Arg->getType()));
316       CB->removeParamUndefImplyingAttrs(ArgNo);
317 
318       ++NumArgumentsReplacedWithUndef;
319       Changed = true;
320     }
321   }
322 
323   return Changed;
324 }
325 
326 /// Convenience function that returns the number of return values. It returns 0
327 /// for void functions and 1 for functions not returning a struct. It returns
328 /// the number of struct elements for functions returning a struct.
NumRetVals(const Function * F)329 static unsigned NumRetVals(const Function *F) {
330   Type *RetTy = F->getReturnType();
331   if (RetTy->isVoidTy())
332     return 0;
333   else if (StructType *STy = dyn_cast<StructType>(RetTy))
334     return STy->getNumElements();
335   else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy))
336     return ATy->getNumElements();
337   else
338     return 1;
339 }
340 
341 /// Returns the sub-type a function will return at a given Idx. Should
342 /// correspond to the result type of an ExtractValue instruction executed with
343 /// just that one Idx (i.e. only top-level structure is considered).
getRetComponentType(const Function * F,unsigned Idx)344 static Type *getRetComponentType(const Function *F, unsigned Idx) {
345   Type *RetTy = F->getReturnType();
346   assert(!RetTy->isVoidTy() && "void type has no subtype");
347 
348   if (StructType *STy = dyn_cast<StructType>(RetTy))
349     return STy->getElementType(Idx);
350   else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy))
351     return ATy->getElementType();
352   else
353     return RetTy;
354 }
355 
356 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not
357 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined
358 /// liveness of Use.
359 DeadArgumentEliminationPass::Liveness
MarkIfNotLive(RetOrArg Use,UseVector & MaybeLiveUses)360 DeadArgumentEliminationPass::MarkIfNotLive(RetOrArg Use,
361                                            UseVector &MaybeLiveUses) {
362   // We're live if our use or its Function is already marked as live.
363   if (IsLive(Use))
364     return Live;
365 
366   // We're maybe live otherwise, but remember that we must become live if
367   // Use becomes live.
368   MaybeLiveUses.push_back(Use);
369   return MaybeLive;
370 }
371 
372 /// SurveyUse - This looks at a single use of an argument or return value
373 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses
374 /// if it causes the used value to become MaybeLive.
375 ///
376 /// RetValNum is the return value number to use when this use is used in a
377 /// return instruction. This is used in the recursion, you should always leave
378 /// it at 0.
379 DeadArgumentEliminationPass::Liveness
SurveyUse(const Use * U,UseVector & MaybeLiveUses,unsigned RetValNum)380 DeadArgumentEliminationPass::SurveyUse(const Use *U, UseVector &MaybeLiveUses,
381                                        unsigned RetValNum) {
382     const User *V = U->getUser();
383     if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) {
384       // The value is returned from a function. It's only live when the
385       // function's return value is live. We use RetValNum here, for the case
386       // that U is really a use of an insertvalue instruction that uses the
387       // original Use.
388       const Function *F = RI->getParent()->getParent();
389       if (RetValNum != -1U) {
390         RetOrArg Use = CreateRet(F, RetValNum);
391         // We might be live, depending on the liveness of Use.
392         return MarkIfNotLive(Use, MaybeLiveUses);
393       } else {
394         DeadArgumentEliminationPass::Liveness Result = MaybeLive;
395         for (unsigned Ri = 0; Ri < NumRetVals(F); ++Ri) {
396           RetOrArg Use = CreateRet(F, Ri);
397           // We might be live, depending on the liveness of Use. If any
398           // sub-value is live, then the entire value is considered live. This
399           // is a conservative choice, and better tracking is possible.
400           DeadArgumentEliminationPass::Liveness SubResult =
401               MarkIfNotLive(Use, MaybeLiveUses);
402           if (Result != Live)
403             Result = SubResult;
404         }
405         return Result;
406       }
407     }
408     if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) {
409       if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex()
410           && IV->hasIndices())
411         // The use we are examining is inserted into an aggregate. Our liveness
412         // depends on all uses of that aggregate, but if it is used as a return
413         // value, only index at which we were inserted counts.
414         RetValNum = *IV->idx_begin();
415 
416       // Note that if we are used as the aggregate operand to the insertvalue,
417       // we don't change RetValNum, but do survey all our uses.
418 
419       Liveness Result = MaybeLive;
420       for (const Use &UU : IV->uses()) {
421         Result = SurveyUse(&UU, MaybeLiveUses, RetValNum);
422         if (Result == Live)
423           break;
424       }
425       return Result;
426     }
427 
428     if (const auto *CB = dyn_cast<CallBase>(V)) {
429       const Function *F = CB->getCalledFunction();
430       if (F) {
431         // Used in a direct call.
432 
433         // The function argument is live if it is used as a bundle operand.
434         if (CB->isBundleOperand(U))
435           return Live;
436 
437         // Find the argument number. We know for sure that this use is an
438         // argument, since if it was the function argument this would be an
439         // indirect call and the we know can't be looking at a value of the
440         // label type (for the invoke instruction).
441         unsigned ArgNo = CB->getArgOperandNo(U);
442 
443         if (ArgNo >= F->getFunctionType()->getNumParams())
444           // The value is passed in through a vararg! Must be live.
445           return Live;
446 
447         assert(CB->getArgOperand(ArgNo) == CB->getOperand(U->getOperandNo()) &&
448                "Argument is not where we expected it");
449 
450         // Value passed to a normal call. It's only live when the corresponding
451         // argument to the called function turns out live.
452         RetOrArg Use = CreateArg(F, ArgNo);
453         return MarkIfNotLive(Use, MaybeLiveUses);
454       }
455     }
456     // Used in any other way? Value must be live.
457     return Live;
458 }
459 
460 /// SurveyUses - This looks at all the uses of the given value
461 /// Returns the Liveness deduced from the uses of this value.
462 ///
463 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If
464 /// the result is Live, MaybeLiveUses might be modified but its content should
465 /// be ignored (since it might not be complete).
466 DeadArgumentEliminationPass::Liveness
SurveyUses(const Value * V,UseVector & MaybeLiveUses)467 DeadArgumentEliminationPass::SurveyUses(const Value *V,
468                                         UseVector &MaybeLiveUses) {
469   // Assume it's dead (which will only hold if there are no uses at all..).
470   Liveness Result = MaybeLive;
471   // Check each use.
472   for (const Use &U : V->uses()) {
473     Result = SurveyUse(&U, MaybeLiveUses);
474     if (Result == Live)
475       break;
476   }
477   return Result;
478 }
479 
480 // SurveyFunction - This performs the initial survey of the specified function,
481 // checking out whether or not it uses any of its incoming arguments or whether
482 // any callers use the return value.  This fills in the LiveValues set and Uses
483 // map.
484 //
485 // We consider arguments of non-internal functions to be intrinsically alive as
486 // well as arguments to functions which have their "address taken".
SurveyFunction(const Function & F)487 void DeadArgumentEliminationPass::SurveyFunction(const Function &F) {
488   // Functions with inalloca/preallocated parameters are expecting args in a
489   // particular register and memory layout.
490   if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) ||
491       F.getAttributes().hasAttrSomewhere(Attribute::Preallocated)) {
492     MarkLive(F);
493     return;
494   }
495 
496   // Don't touch naked functions. The assembly might be using an argument, or
497   // otherwise rely on the frame layout in a way that this analysis will not
498   // see.
499   if (F.hasFnAttribute(Attribute::Naked)) {
500     MarkLive(F);
501     return;
502   }
503 
504   unsigned RetCount = NumRetVals(&F);
505 
506   // Assume all return values are dead
507   using RetVals = SmallVector<Liveness, 5>;
508 
509   RetVals RetValLiveness(RetCount, MaybeLive);
510 
511   using RetUses = SmallVector<UseVector, 5>;
512 
513   // These vectors map each return value to the uses that make it MaybeLive, so
514   // we can add those to the Uses map if the return value really turns out to be
515   // MaybeLive. Initialized to a list of RetCount empty lists.
516   RetUses MaybeLiveRetUses(RetCount);
517 
518   bool HasMustTailCalls = false;
519 
520   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
521     if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
522       if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType()
523           != F.getFunctionType()->getReturnType()) {
524         // We don't support old style multiple return values.
525         MarkLive(F);
526         return;
527       }
528     }
529 
530     // If we have any returns of `musttail` results - the signature can't
531     // change
532     if (BB->getTerminatingMustTailCall() != nullptr)
533       HasMustTailCalls = true;
534   }
535 
536   if (HasMustTailCalls) {
537     LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()
538                       << " has musttail calls\n");
539   }
540 
541   if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) {
542     MarkLive(F);
543     return;
544   }
545 
546   LLVM_DEBUG(
547       dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: "
548              << F.getName() << "\n");
549   // Keep track of the number of live retvals, so we can skip checks once all
550   // of them turn out to be live.
551   unsigned NumLiveRetVals = 0;
552 
553   bool HasMustTailCallers = false;
554 
555   // Loop all uses of the function.
556   for (const Use &U : F.uses()) {
557     // If the function is PASSED IN as an argument, its address has been
558     // taken.
559     const auto *CB = dyn_cast<CallBase>(U.getUser());
560     if (!CB || !CB->isCallee(&U)) {
561       MarkLive(F);
562       return;
563     }
564 
565     // The number of arguments for `musttail` call must match the number of
566     // arguments of the caller
567     if (CB->isMustTailCall())
568       HasMustTailCallers = true;
569 
570     // If we end up here, we are looking at a direct call to our function.
571 
572     // Now, check how our return value(s) is/are used in this caller. Don't
573     // bother checking return values if all of them are live already.
574     if (NumLiveRetVals == RetCount)
575       continue;
576 
577     // Check all uses of the return value.
578     for (const Use &U : CB->uses()) {
579       if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) {
580         // This use uses a part of our return value, survey the uses of
581         // that part and store the results for this index only.
582         unsigned Idx = *Ext->idx_begin();
583         if (RetValLiveness[Idx] != Live) {
584           RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]);
585           if (RetValLiveness[Idx] == Live)
586             NumLiveRetVals++;
587         }
588       } else {
589         // Used by something else than extractvalue. Survey, but assume that the
590         // result applies to all sub-values.
591         UseVector MaybeLiveAggregateUses;
592         if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) {
593           NumLiveRetVals = RetCount;
594           RetValLiveness.assign(RetCount, Live);
595           break;
596         } else {
597           for (unsigned Ri = 0; Ri != RetCount; ++Ri) {
598             if (RetValLiveness[Ri] != Live)
599               MaybeLiveRetUses[Ri].append(MaybeLiveAggregateUses.begin(),
600                                           MaybeLiveAggregateUses.end());
601           }
602         }
603       }
604     }
605   }
606 
607   if (HasMustTailCallers) {
608     LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()
609                       << " has musttail callers\n");
610   }
611 
612   // Now we've inspected all callers, record the liveness of our return values.
613   for (unsigned Ri = 0; Ri != RetCount; ++Ri)
614     MarkValue(CreateRet(&F, Ri), RetValLiveness[Ri], MaybeLiveRetUses[Ri]);
615 
616   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: "
617                     << F.getName() << "\n");
618 
619   // Now, check all of our arguments.
620   unsigned ArgI = 0;
621   UseVector MaybeLiveArgUses;
622   for (Function::const_arg_iterator AI = F.arg_begin(), E = F.arg_end();
623        AI != E; ++AI, ++ArgI) {
624     Liveness Result;
625     if (F.getFunctionType()->isVarArg() || HasMustTailCallers ||
626         HasMustTailCalls) {
627       // Variadic functions will already have a va_arg function expanded inside
628       // them, making them potentially very sensitive to ABI changes resulting
629       // from removing arguments entirely, so don't. For example AArch64 handles
630       // register and stack HFAs very differently, and this is reflected in the
631       // IR which has already been generated.
632       //
633       // `musttail` calls to this function restrict argument removal attempts.
634       // The signature of the caller must match the signature of the function.
635       //
636       // `musttail` calls in this function prevents us from changing its
637       // signature
638       Result = Live;
639     } else {
640       // See what the effect of this use is (recording any uses that cause
641       // MaybeLive in MaybeLiveArgUses).
642       Result = SurveyUses(&*AI, MaybeLiveArgUses);
643     }
644 
645     // Mark the result.
646     MarkValue(CreateArg(&F, ArgI), Result, MaybeLiveArgUses);
647     // Clear the vector again for the next iteration.
648     MaybeLiveArgUses.clear();
649   }
650 }
651 
652 /// MarkValue - This function marks the liveness of RA depending on L. If L is
653 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses,
654 /// such that RA will be marked live if any use in MaybeLiveUses gets marked
655 /// live later on.
MarkValue(const RetOrArg & RA,Liveness L,const UseVector & MaybeLiveUses)656 void DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L,
657                                             const UseVector &MaybeLiveUses) {
658   switch (L) {
659     case Live:
660       MarkLive(RA);
661       break;
662     case MaybeLive:
663       assert(!IsLive(RA) && "Use is already live!");
664       for (const auto &MaybeLiveUse : MaybeLiveUses) {
665         if (IsLive(MaybeLiveUse)) {
666           // A use is live, so this value is live.
667           MarkLive(RA);
668           break;
669         } else {
670           // Note any uses of this value, so this value can be
671           // marked live whenever one of the uses becomes live.
672           Uses.insert(std::make_pair(MaybeLiveUse, RA));
673         }
674       }
675       break;
676   }
677 }
678 
679 /// MarkLive - Mark the given Function as alive, meaning that it cannot be
680 /// changed in any way. Additionally,
681 /// mark any values that are used as this function's parameters or by its return
682 /// values (according to Uses) live as well.
MarkLive(const Function & F)683 void DeadArgumentEliminationPass::MarkLive(const Function &F) {
684   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: "
685                     << F.getName() << "\n");
686   // Mark the function as live.
687   LiveFunctions.insert(&F);
688   // Mark all arguments as live.
689   for (unsigned ArgI = 0, E = F.arg_size(); ArgI != E; ++ArgI)
690     PropagateLiveness(CreateArg(&F, ArgI));
691   // Mark all return values as live.
692   for (unsigned Ri = 0, E = NumRetVals(&F); Ri != E; ++Ri)
693     PropagateLiveness(CreateRet(&F, Ri));
694 }
695 
696 /// MarkLive - Mark the given return value or argument as live. Additionally,
697 /// mark any values that are used by this value (according to Uses) live as
698 /// well.
MarkLive(const RetOrArg & RA)699 void DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) {
700   if (IsLive(RA))
701     return; // Already marked Live.
702 
703   LiveValues.insert(RA);
704 
705   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking "
706                     << RA.getDescription() << " live\n");
707   PropagateLiveness(RA);
708 }
709 
IsLive(const RetOrArg & RA)710 bool DeadArgumentEliminationPass::IsLive(const RetOrArg &RA) {
711   return LiveFunctions.count(RA.F) || LiveValues.count(RA);
712 }
713 
714 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness
715 /// to any other values it uses (according to Uses).
PropagateLiveness(const RetOrArg & RA)716 void DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) {
717   // We don't use upper_bound (or equal_range) here, because our recursive call
718   // to ourselves is likely to cause the upper_bound (which is the first value
719   // not belonging to RA) to become erased and the iterator invalidated.
720   UseMap::iterator Begin = Uses.lower_bound(RA);
721   UseMap::iterator E = Uses.end();
722   UseMap::iterator I;
723   for (I = Begin; I != E && I->first == RA; ++I)
724     MarkLive(I->second);
725 
726   // Erase RA from the Uses map (from the lower bound to wherever we ended up
727   // after the loop).
728   Uses.erase(Begin, I);
729 }
730 
731 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F
732 // that are not in LiveValues. Transform the function and all of the callees of
733 // the function to not have these arguments and return values.
734 //
RemoveDeadStuffFromFunction(Function * F)735 bool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) {
736   // Don't modify fully live functions
737   if (LiveFunctions.count(F))
738     return false;
739 
740   // Start by computing a new prototype for the function, which is the same as
741   // the old function, but has fewer arguments and a different return type.
742   FunctionType *FTy = F->getFunctionType();
743   std::vector<Type*> Params;
744 
745   // Keep track of if we have a live 'returned' argument
746   bool HasLiveReturnedArg = false;
747 
748   // Set up to build a new list of parameter attributes.
749   SmallVector<AttributeSet, 8> ArgAttrVec;
750   const AttributeList &PAL = F->getAttributes();
751 
752   // Remember which arguments are still alive.
753   SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false);
754   // Construct the new parameter list from non-dead arguments. Also construct
755   // a new set of parameter attributes to correspond. Skip the first parameter
756   // attribute, since that belongs to the return value.
757   unsigned ArgI = 0;
758   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
759        ++I, ++ArgI) {
760     RetOrArg Arg = CreateArg(F, ArgI);
761     if (LiveValues.erase(Arg)) {
762       Params.push_back(I->getType());
763       ArgAlive[ArgI] = true;
764       ArgAttrVec.push_back(PAL.getParamAttributes(ArgI));
765       HasLiveReturnedArg |= PAL.hasParamAttribute(ArgI, Attribute::Returned);
766     } else {
767       ++NumArgumentsEliminated;
768       LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument "
769                         << ArgI << " (" << I->getName() << ") from "
770                         << F->getName() << "\n");
771     }
772   }
773 
774   // Find out the new return value.
775   Type *RetTy = FTy->getReturnType();
776   Type *NRetTy = nullptr;
777   unsigned RetCount = NumRetVals(F);
778 
779   // -1 means unused, other numbers are the new index
780   SmallVector<int, 5> NewRetIdxs(RetCount, -1);
781   std::vector<Type*> RetTypes;
782 
783   // If there is a function with a live 'returned' argument but a dead return
784   // value, then there are two possible actions:
785   // 1) Eliminate the return value and take off the 'returned' attribute on the
786   //    argument.
787   // 2) Retain the 'returned' attribute and treat the return value (but not the
788   //    entire function) as live so that it is not eliminated.
789   //
790   // It's not clear in the general case which option is more profitable because,
791   // even in the absence of explicit uses of the return value, code generation
792   // is free to use the 'returned' attribute to do things like eliding
793   // save/restores of registers across calls. Whether or not this happens is
794   // target and ABI-specific as well as depending on the amount of register
795   // pressure, so there's no good way for an IR-level pass to figure this out.
796   //
797   // Fortunately, the only places where 'returned' is currently generated by
798   // the FE are places where 'returned' is basically free and almost always a
799   // performance win, so the second option can just be used always for now.
800   //
801   // This should be revisited if 'returned' is ever applied more liberally.
802   if (RetTy->isVoidTy() || HasLiveReturnedArg) {
803     NRetTy = RetTy;
804   } else {
805     // Look at each of the original return values individually.
806     for (unsigned Ri = 0; Ri != RetCount; ++Ri) {
807       RetOrArg Ret = CreateRet(F, Ri);
808       if (LiveValues.erase(Ret)) {
809         RetTypes.push_back(getRetComponentType(F, Ri));
810         NewRetIdxs[Ri] = RetTypes.size() - 1;
811       } else {
812         ++NumRetValsEliminated;
813         LLVM_DEBUG(
814             dbgs() << "DeadArgumentEliminationPass - Removing return value "
815                    << Ri << " from " << F->getName() << "\n");
816       }
817     }
818     if (RetTypes.size() > 1) {
819       // More than one return type? Reduce it down to size.
820       if (StructType *STy = dyn_cast<StructType>(RetTy)) {
821         // Make the new struct packed if we used to return a packed struct
822         // already.
823         NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked());
824       } else {
825         assert(isa<ArrayType>(RetTy) && "unexpected multi-value return");
826         NRetTy = ArrayType::get(RetTypes[0], RetTypes.size());
827       }
828     } else if (RetTypes.size() == 1)
829       // One return type? Just a simple value then, but only if we didn't use to
830       // return a struct with that simple value before.
831       NRetTy = RetTypes.front();
832     else if (RetTypes.empty())
833       // No return types? Make it void, but only if we didn't use to return {}.
834       NRetTy = Type::getVoidTy(F->getContext());
835   }
836 
837   assert(NRetTy && "No new return type found?");
838 
839   // The existing function return attributes.
840   AttrBuilder RAttrs(PAL.getRetAttributes());
841 
842   // Remove any incompatible attributes, but only if we removed all return
843   // values. Otherwise, ensure that we don't have any conflicting attributes
844   // here. Currently, this should not be possible, but special handling might be
845   // required when new return value attributes are added.
846   if (NRetTy->isVoidTy())
847     RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy));
848   else
849     assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) &&
850            "Return attributes no longer compatible?");
851 
852   AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs);
853 
854   // Strip allocsize attributes. They might refer to the deleted arguments.
855   AttributeSet FnAttrs = PAL.getFnAttributes().removeAttribute(
856       F->getContext(), Attribute::AllocSize);
857 
858   // Reconstruct the AttributesList based on the vector we constructed.
859   assert(ArgAttrVec.size() == Params.size());
860   AttributeList NewPAL =
861       AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec);
862 
863   // Create the new function type based on the recomputed parameters.
864   FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg());
865 
866   // No change?
867   if (NFTy == FTy)
868     return false;
869 
870   // Create the new function body and insert it into the module...
871   Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace());
872   NF->copyAttributesFrom(F);
873   NF->setComdat(F->getComdat());
874   NF->setAttributes(NewPAL);
875   // Insert the new function before the old function, so we won't be processing
876   // it again.
877   F->getParent()->getFunctionList().insert(F->getIterator(), NF);
878   NF->takeName(F);
879 
880   // Loop over all of the callers of the function, transforming the call sites
881   // to pass in a smaller number of arguments into the new function.
882   std::vector<Value*> Args;
883   while (!F->use_empty()) {
884     CallBase &CB = cast<CallBase>(*F->user_back());
885 
886     ArgAttrVec.clear();
887     const AttributeList &CallPAL = CB.getAttributes();
888 
889     // Adjust the call return attributes in case the function was changed to
890     // return void.
891     AttrBuilder RAttrs(CallPAL.getRetAttributes());
892     RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy));
893     AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs);
894 
895     // Declare these outside of the loops, so we can reuse them for the second
896     // loop, which loops the varargs.
897     auto I = CB.arg_begin();
898     unsigned Pi = 0;
899     // Loop over those operands, corresponding to the normal arguments to the
900     // original function, and add those that are still alive.
901     for (unsigned E = FTy->getNumParams(); Pi != E; ++I, ++Pi)
902       if (ArgAlive[Pi]) {
903         Args.push_back(*I);
904         // Get original parameter attributes, but skip return attributes.
905         AttributeSet Attrs = CallPAL.getParamAttributes(Pi);
906         if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) {
907           // If the return type has changed, then get rid of 'returned' on the
908           // call site. The alternative is to make all 'returned' attributes on
909           // call sites keep the return value alive just like 'returned'
910           // attributes on function declaration but it's less clearly a win and
911           // this is not an expected case anyway
912           ArgAttrVec.push_back(AttributeSet::get(
913               F->getContext(),
914               AttrBuilder(Attrs).removeAttribute(Attribute::Returned)));
915         } else {
916           // Otherwise, use the original attributes.
917           ArgAttrVec.push_back(Attrs);
918         }
919       }
920 
921     // Push any varargs arguments on the list. Don't forget their attributes.
922     for (auto E = CB.arg_end(); I != E; ++I, ++Pi) {
923       Args.push_back(*I);
924       ArgAttrVec.push_back(CallPAL.getParamAttributes(Pi));
925     }
926 
927     // Reconstruct the AttributesList based on the vector we constructed.
928     assert(ArgAttrVec.size() == Args.size());
929 
930     // Again, be sure to remove any allocsize attributes, since their indices
931     // may now be incorrect.
932     AttributeSet FnAttrs = CallPAL.getFnAttributes().removeAttribute(
933         F->getContext(), Attribute::AllocSize);
934 
935     AttributeList NewCallPAL = AttributeList::get(
936         F->getContext(), FnAttrs, RetAttrs, ArgAttrVec);
937 
938     SmallVector<OperandBundleDef, 1> OpBundles;
939     CB.getOperandBundlesAsDefs(OpBundles);
940 
941     CallBase *NewCB = nullptr;
942     if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {
943       NewCB = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
944                                  Args, OpBundles, "", CB.getParent());
945     } else {
946       NewCB = CallInst::Create(NFTy, NF, Args, OpBundles, "", &CB);
947       cast<CallInst>(NewCB)->setTailCallKind(
948           cast<CallInst>(&CB)->getTailCallKind());
949     }
950     NewCB->setCallingConv(CB.getCallingConv());
951     NewCB->setAttributes(NewCallPAL);
952     NewCB->copyMetadata(CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
953     Args.clear();
954     ArgAttrVec.clear();
955 
956     if (!CB.use_empty() || CB.isUsedByMetadata()) {
957       if (NewCB->getType() == CB.getType()) {
958         // Return type not changed? Just replace users then.
959         CB.replaceAllUsesWith(NewCB);
960         NewCB->takeName(&CB);
961       } else if (NewCB->getType()->isVoidTy()) {
962         // If the return value is dead, replace any uses of it with undef
963         // (any non-debug value uses will get removed later on).
964         if (!CB.getType()->isX86_MMXTy())
965           CB.replaceAllUsesWith(UndefValue::get(CB.getType()));
966       } else {
967         assert((RetTy->isStructTy() || RetTy->isArrayTy()) &&
968                "Return type changed, but not into a void. The old return type"
969                " must have been a struct or an array!");
970         Instruction *InsertPt = &CB;
971         if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {
972           BasicBlock *NewEdge =
973               SplitEdge(NewCB->getParent(), II->getNormalDest());
974           InsertPt = &*NewEdge->getFirstInsertionPt();
975         }
976 
977         // We used to return a struct or array. Instead of doing smart stuff
978         // with all the uses, we will just rebuild it using extract/insertvalue
979         // chaining and let instcombine clean that up.
980         //
981         // Start out building up our return value from undef
982         Value *RetVal = UndefValue::get(RetTy);
983         for (unsigned Ri = 0; Ri != RetCount; ++Ri)
984           if (NewRetIdxs[Ri] != -1) {
985             Value *V;
986             IRBuilder<NoFolder> IRB(InsertPt);
987             if (RetTypes.size() > 1)
988               // We are still returning a struct, so extract the value from our
989               // return value
990               V = IRB.CreateExtractValue(NewCB, NewRetIdxs[Ri], "newret");
991             else
992               // We are now returning a single element, so just insert that
993               V = NewCB;
994             // Insert the value at the old position
995             RetVal = IRB.CreateInsertValue(RetVal, V, Ri, "oldret");
996           }
997         // Now, replace all uses of the old call instruction with the return
998         // struct we built
999         CB.replaceAllUsesWith(RetVal);
1000         NewCB->takeName(&CB);
1001       }
1002     }
1003 
1004     // Finally, remove the old call from the program, reducing the use-count of
1005     // F.
1006     CB.eraseFromParent();
1007   }
1008 
1009   // Since we have now created the new function, splice the body of the old
1010   // function right into the new function, leaving the old rotting hulk of the
1011   // function empty.
1012   NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
1013 
1014   // Loop over the argument list, transferring uses of the old arguments over to
1015   // the new arguments, also transferring over the names as well.
1016   ArgI = 0;
1017   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
1018                               I2 = NF->arg_begin();
1019        I != E; ++I, ++ArgI)
1020     if (ArgAlive[ArgI]) {
1021       // If this is a live argument, move the name and users over to the new
1022       // version.
1023       I->replaceAllUsesWith(&*I2);
1024       I2->takeName(&*I);
1025       ++I2;
1026     } else {
1027       // If this argument is dead, replace any uses of it with undef
1028       // (any non-debug value uses will get removed later on).
1029       if (!I->getType()->isX86_MMXTy())
1030         I->replaceAllUsesWith(UndefValue::get(I->getType()));
1031     }
1032 
1033   // If we change the return value of the function we must rewrite any return
1034   // instructions.  Check this now.
1035   if (F->getReturnType() != NF->getReturnType())
1036     for (BasicBlock &BB : *NF)
1037       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
1038         IRBuilder<NoFolder> IRB(RI);
1039         Value *RetVal = nullptr;
1040 
1041         if (!NFTy->getReturnType()->isVoidTy()) {
1042           assert(RetTy->isStructTy() || RetTy->isArrayTy());
1043           // The original return value was a struct or array, insert
1044           // extractvalue/insertvalue chains to extract only the values we need
1045           // to return and insert them into our new result.
1046           // This does generate messy code, but we'll let it to instcombine to
1047           // clean that up.
1048           Value *OldRet = RI->getOperand(0);
1049           // Start out building up our return value from undef
1050           RetVal = UndefValue::get(NRetTy);
1051           for (unsigned RetI = 0; RetI != RetCount; ++RetI)
1052             if (NewRetIdxs[RetI] != -1) {
1053               Value *EV = IRB.CreateExtractValue(OldRet, RetI, "oldret");
1054 
1055               if (RetTypes.size() > 1) {
1056                 // We're still returning a struct, so reinsert the value into
1057                 // our new return value at the new index
1058 
1059                 RetVal = IRB.CreateInsertValue(RetVal, EV, NewRetIdxs[RetI],
1060                                                "newret");
1061               } else {
1062                 // We are now only returning a simple value, so just return the
1063                 // extracted value.
1064                 RetVal = EV;
1065               }
1066             }
1067         }
1068         // Replace the return instruction with one returning the new return
1069         // value (possibly 0 if we became void).
1070         auto *NewRet = ReturnInst::Create(F->getContext(), RetVal, RI);
1071         NewRet->setDebugLoc(RI->getDebugLoc());
1072         BB.getInstList().erase(RI);
1073       }
1074 
1075   // Clone metadatas from the old function, including debug info descriptor.
1076   SmallVector<std::pair<unsigned, MDNode *>, 1> MDs;
1077   F->getAllMetadata(MDs);
1078   for (auto MD : MDs)
1079     NF->addMetadata(MD.first, *MD.second);
1080 
1081   // Now that the old function is dead, delete it.
1082   F->eraseFromParent();
1083 
1084   return true;
1085 }
1086 
run(Module & M,ModuleAnalysisManager &)1087 PreservedAnalyses DeadArgumentEliminationPass::run(Module &M,
1088                                                    ModuleAnalysisManager &) {
1089   bool Changed = false;
1090 
1091   // First pass: Do a simple check to see if any functions can have their "..."
1092   // removed.  We can do this if they never call va_start.  This loop cannot be
1093   // fused with the next loop, because deleting a function invalidates
1094   // information computed while surveying other functions.
1095   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n");
1096   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
1097     Function &F = *I++;
1098     if (F.getFunctionType()->isVarArg())
1099       Changed |= DeleteDeadVarargs(F);
1100   }
1101 
1102   // Second phase:loop through the module, determining which arguments are live.
1103   // We assume all arguments are dead unless proven otherwise (allowing us to
1104   // determine that dead arguments passed into recursive functions are dead).
1105   //
1106   LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n");
1107   for (auto &F : M)
1108     SurveyFunction(F);
1109 
1110   // Now, remove all dead arguments and return values from each function in
1111   // turn.
1112   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
1113     // Increment now, because the function will probably get removed (ie.
1114     // replaced by a new one).
1115     Function *F = &*I++;
1116     Changed |= RemoveDeadStuffFromFunction(F);
1117   }
1118 
1119   // Finally, look for any unused parameters in functions with non-local
1120   // linkage and replace the passed in parameters with undef.
1121   for (auto &F : M)
1122     Changed |= RemoveDeadArgumentsFromCallers(F);
1123 
1124   if (!Changed)
1125     return PreservedAnalyses::all();
1126   return PreservedAnalyses::none();
1127 }
1128