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