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