File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp |
Warning: | line 847, column 7 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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" "deadargelim" | |||
56 | ||||
57 | STATISTIC(NumArgumentsEliminated, "Number of unread args removed")static llvm::Statistic NumArgumentsEliminated = {"deadargelim" , "NumArgumentsEliminated", "Number of unread args removed"}; | |||
58 | STATISTIC(NumRetValsEliminated , "Number of unused return values removed")static llvm::Statistic NumRetValsEliminated = {"deadargelim", "NumRetValsEliminated", "Number of unused return values removed" }; | |||
59 | STATISTIC(NumArgumentsReplacedWithUndef,static llvm::Statistic NumArgumentsReplacedWithUndef = {"deadargelim" , "NumArgumentsReplacedWithUndef", "Number of unread args replaced with undef" } | |||
60 | "Number of unread args replaced with undef")static llvm::Statistic NumArgumentsReplacedWithUndef = {"deadargelim" , "NumArgumentsReplacedWithUndef", "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. | |||
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 | } // end anonymous namespace | |||
90 | ||||
91 | char DAE::ID = 0; | |||
92 | ||||
93 | INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false)static void *initializeDAEPassOnce(PassRegistry &Registry ) { PassInfo *PI = new PassInfo( "Dead Argument Elimination", "deadargelim", &DAE::ID, PassInfo::NormalCtor_t(callDefaultCtor <DAE>), false, false); Registry.registerPass(*PI, true) ; return PI; } static llvm::once_flag InitializeDAEPassFlag; void llvm::initializeDAEPass(PassRegistry &Registry) { llvm:: call_once(InitializeDAEPassFlag, initializeDAEPassOnce, std:: ref(Registry)); } | |||
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 | ||||
103 | DAH() : DAE(ID) {} | |||
104 | ||||
105 | bool ShouldHackArguments() const override { return true; } | |||
106 | }; | |||
107 | ||||
108 | } // end anonymous namespace | |||
109 | ||||
110 | char DAH::ID = 0; | |||
111 | ||||
112 | INITIALIZE_PASS(DAH, "deadarghaX0r",static void *initializeDAHPassOnce(PassRegistry &Registry ) { PassInfo *PI = new PassInfo( "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)" , "deadarghaX0r", &DAH::ID, PassInfo::NormalCtor_t(callDefaultCtor <DAH>), false, false); Registry.registerPass(*PI, true) ; return PI; } static llvm::once_flag InitializeDAHPassFlag; void llvm::initializeDAHPass(PassRegistry &Registry) { llvm:: call_once(InitializeDAHPassFlag, initializeDAHPassOnce, std:: ref(Registry)); } | |||
113 | "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",static void *initializeDAHPassOnce(PassRegistry &Registry ) { PassInfo *PI = new PassInfo( "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)" , "deadarghaX0r", &DAH::ID, PassInfo::NormalCtor_t(callDefaultCtor <DAH>), false, false); Registry.registerPass(*PI, true) ; return PI; } static llvm::once_flag InitializeDAHPassFlag; void llvm::initializeDAHPass(PassRegistry &Registry) { llvm:: call_once(InitializeDAHPassFlag, initializeDAHPassOnce, std:: ref(Registry)); } | |||
114 | false, false)static void *initializeDAHPassOnce(PassRegistry &Registry ) { PassInfo *PI = new PassInfo( "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)" , "deadarghaX0r", &DAH::ID, PassInfo::NormalCtor_t(callDefaultCtor <DAH>), false, false); Registry.registerPass(*PI, true) ; return PI; } static llvm::once_flag InitializeDAHPassFlag; void llvm::initializeDAHPass(PassRegistry &Registry) { llvm:: call_once(InitializeDAHPassFlag, initializeDAHPassOnce, std:: ref(Registry)); } | |||
115 | ||||
116 | /// createDeadArgEliminationPass - This pass removes arguments from functions | |||
117 | /// which are not used by the body of the function. | |||
118 | ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } | |||
119 | ||||
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. | |||
124 | bool DeadArgumentEliminationPass::DeleteDeadVarargs(Function &Fn) { | |||
125 | assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!")((void)0); | |||
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. | |||
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 | AttrBuilder UBImplyingAttributes = AttributeFuncs::getUBImplyingAttributes(); | |||
291 | for (Argument &Arg : Fn.args()) { | |||
292 | if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() && | |||
293 | !Arg.hasPassPointeeByValueCopyAttr()) { | |||
294 | if (Arg.isUsedByMetadata()) { | |||
295 | Arg.replaceAllUsesWith(UndefValue::get(Arg.getType())); | |||
296 | Changed = true; | |||
297 | } | |||
298 | UnusedArgs.push_back(Arg.getArgNo()); | |||
299 | Fn.removeParamAttrs(Arg.getArgNo(), UBImplyingAttributes); | |||
300 | } | |||
301 | } | |||
302 | ||||
303 | if (UnusedArgs.empty()) | |||
304 | return false; | |||
305 | ||||
306 | for (Use &U : Fn.uses()) { | |||
307 | CallBase *CB = dyn_cast<CallBase>(U.getUser()); | |||
308 | if (!CB || !CB->isCallee(&U)) | |||
309 | continue; | |||
310 | ||||
311 | // Now go through all unused args and replace them with "undef". | |||
312 | for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { | |||
313 | unsigned ArgNo = UnusedArgs[I]; | |||
314 | ||||
315 | Value *Arg = CB->getArgOperand(ArgNo); | |||
316 | CB->setArgOperand(ArgNo, UndefValue::get(Arg->getType())); | |||
317 | CB->removeParamAttrs(ArgNo, UBImplyingAttributes); | |||
318 | ||||
319 | ++NumArgumentsReplacedWithUndef; | |||
320 | Changed = true; | |||
321 | } | |||
322 | } | |||
323 | ||||
324 | return Changed; | |||
325 | } | |||
326 | ||||
327 | /// Convenience function that returns the number of return values. It returns 0 | |||
328 | /// for void functions and 1 for functions not returning a struct. It returns | |||
329 | /// the number of struct elements for functions returning a struct. | |||
330 | static unsigned NumRetVals(const Function *F) { | |||
331 | Type *RetTy = F->getReturnType(); | |||
332 | if (RetTy->isVoidTy()) | |||
333 | return 0; | |||
334 | else if (StructType *STy = dyn_cast<StructType>(RetTy)) | |||
335 | return STy->getNumElements(); | |||
336 | else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) | |||
337 | return ATy->getNumElements(); | |||
338 | else | |||
339 | return 1; | |||
340 | } | |||
341 | ||||
342 | /// Returns the sub-type a function will return at a given Idx. Should | |||
343 | /// correspond to the result type of an ExtractValue instruction executed with | |||
344 | /// just that one Idx (i.e. only top-level structure is considered). | |||
345 | static Type *getRetComponentType(const Function *F, unsigned Idx) { | |||
346 | Type *RetTy = F->getReturnType(); | |||
347 | assert(!RetTy->isVoidTy() && "void type has no subtype")((void)0); | |||
348 | ||||
349 | if (StructType *STy = dyn_cast<StructType>(RetTy)) | |||
350 | return STy->getElementType(Idx); | |||
351 | else if (ArrayType *ATy = dyn_cast<ArrayType>(RetTy)) | |||
352 | return ATy->getElementType(); | |||
353 | else | |||
354 | return RetTy; | |||
355 | } | |||
356 | ||||
357 | /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not | |||
358 | /// live, it adds Use to the MaybeLiveUses argument. Returns the determined | |||
359 | /// liveness of Use. | |||
360 | DeadArgumentEliminationPass::Liveness | |||
361 | DeadArgumentEliminationPass::MarkIfNotLive(RetOrArg Use, | |||
362 | UseVector &MaybeLiveUses) { | |||
363 | // We're live if our use or its Function is already marked as live. | |||
364 | if (IsLive(Use)) | |||
365 | return Live; | |||
366 | ||||
367 | // We're maybe live otherwise, but remember that we must become live if | |||
368 | // Use becomes live. | |||
369 | MaybeLiveUses.push_back(Use); | |||
370 | return MaybeLive; | |||
371 | } | |||
372 | ||||
373 | /// SurveyUse - This looks at a single use of an argument or return value | |||
374 | /// and determines if it should be alive or not. Adds this use to MaybeLiveUses | |||
375 | /// if it causes the used value to become MaybeLive. | |||
376 | /// | |||
377 | /// RetValNum is the return value number to use when this use is used in a | |||
378 | /// return instruction. This is used in the recursion, you should always leave | |||
379 | /// it at 0. | |||
380 | DeadArgumentEliminationPass::Liveness | |||
381 | DeadArgumentEliminationPass::SurveyUse(const Use *U, UseVector &MaybeLiveUses, | |||
382 | unsigned RetValNum) { | |||
383 | const User *V = U->getUser(); | |||
384 | if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) { | |||
385 | // The value is returned from a function. It's only live when the | |||
386 | // function's return value is live. We use RetValNum here, for the case | |||
387 | // that U is really a use of an insertvalue instruction that uses the | |||
388 | // original Use. | |||
389 | const Function *F = RI->getParent()->getParent(); | |||
390 | if (RetValNum != -1U) { | |||
391 | RetOrArg Use = CreateRet(F, RetValNum); | |||
392 | // We might be live, depending on the liveness of Use. | |||
393 | return MarkIfNotLive(Use, MaybeLiveUses); | |||
394 | } else { | |||
395 | DeadArgumentEliminationPass::Liveness Result = MaybeLive; | |||
396 | for (unsigned Ri = 0; Ri < NumRetVals(F); ++Ri) { | |||
397 | RetOrArg Use = CreateRet(F, Ri); | |||
398 | // We might be live, depending on the liveness of Use. If any | |||
399 | // sub-value is live, then the entire value is considered live. This | |||
400 | // is a conservative choice, and better tracking is possible. | |||
401 | DeadArgumentEliminationPass::Liveness SubResult = | |||
402 | MarkIfNotLive(Use, MaybeLiveUses); | |||
403 | if (Result != Live) | |||
404 | Result = SubResult; | |||
405 | } | |||
406 | return Result; | |||
407 | } | |||
408 | } | |||
409 | if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) { | |||
410 | if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex() | |||
411 | && IV->hasIndices()) | |||
412 | // The use we are examining is inserted into an aggregate. Our liveness | |||
413 | // depends on all uses of that aggregate, but if it is used as a return | |||
414 | // value, only index at which we were inserted counts. | |||
415 | RetValNum = *IV->idx_begin(); | |||
416 | ||||
417 | // Note that if we are used as the aggregate operand to the insertvalue, | |||
418 | // we don't change RetValNum, but do survey all our uses. | |||
419 | ||||
420 | Liveness Result = MaybeLive; | |||
421 | for (const Use &UU : IV->uses()) { | |||
422 | Result = SurveyUse(&UU, MaybeLiveUses, RetValNum); | |||
423 | if (Result == Live) | |||
424 | break; | |||
425 | } | |||
426 | return Result; | |||
427 | } | |||
428 | ||||
429 | if (const auto *CB = dyn_cast<CallBase>(V)) { | |||
430 | const Function *F = CB->getCalledFunction(); | |||
431 | if (F) { | |||
432 | // Used in a direct call. | |||
433 | ||||
434 | // The function argument is live if it is used as a bundle operand. | |||
435 | if (CB->isBundleOperand(U)) | |||
436 | return Live; | |||
437 | ||||
438 | // Find the argument number. We know for sure that this use is an | |||
439 | // argument, since if it was the function argument this would be an | |||
440 | // indirect call and the we know can't be looking at a value of the | |||
441 | // label type (for the invoke instruction). | |||
442 | unsigned ArgNo = CB->getArgOperandNo(U); | |||
443 | ||||
444 | if (ArgNo >= F->getFunctionType()->getNumParams()) | |||
445 | // The value is passed in through a vararg! Must be live. | |||
446 | return Live; | |||
447 | ||||
448 | assert(CB->getArgOperand(ArgNo) == CB->getOperand(U->getOperandNo()) &&((void)0) | |||
449 | "Argument is not where we expected it")((void)0); | |||
450 | ||||
451 | // Value passed to a normal call. It's only live when the corresponding | |||
452 | // argument to the called function turns out live. | |||
453 | RetOrArg Use = CreateArg(F, ArgNo); | |||
454 | return MarkIfNotLive(Use, MaybeLiveUses); | |||
455 | } | |||
456 | } | |||
457 | // Used in any other way? Value must be live. | |||
458 | return Live; | |||
459 | } | |||
460 | ||||
461 | /// SurveyUses - This looks at all the uses of the given value | |||
462 | /// Returns the Liveness deduced from the uses of this value. | |||
463 | /// | |||
464 | /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If | |||
465 | /// the result is Live, MaybeLiveUses might be modified but its content should | |||
466 | /// be ignored (since it might not be complete). | |||
467 | DeadArgumentEliminationPass::Liveness | |||
468 | DeadArgumentEliminationPass::SurveyUses(const Value *V, | |||
469 | UseVector &MaybeLiveUses) { | |||
470 | // Assume it's dead (which will only hold if there are no uses at all..). | |||
471 | Liveness Result = MaybeLive; | |||
472 | // Check each use. | |||
473 | for (const Use &U : V->uses()) { | |||
474 | Result = SurveyUse(&U, MaybeLiveUses); | |||
475 | if (Result == Live) | |||
476 | break; | |||
477 | } | |||
478 | return Result; | |||
479 | } | |||
480 | ||||
481 | // SurveyFunction - This performs the initial survey of the specified function, | |||
482 | // checking out whether or not it uses any of its incoming arguments or whether | |||
483 | // any callers use the return value. This fills in the LiveValues set and Uses | |||
484 | // map. | |||
485 | // | |||
486 | // We consider arguments of non-internal functions to be intrinsically alive as | |||
487 | // well as arguments to functions which have their "address taken". | |||
488 | void DeadArgumentEliminationPass::SurveyFunction(const Function &F) { | |||
489 | // Functions with inalloca/preallocated parameters are expecting args in a | |||
490 | // particular register and memory layout. | |||
491 | if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) || | |||
492 | F.getAttributes().hasAttrSomewhere(Attribute::Preallocated)) { | |||
493 | MarkLive(F); | |||
494 | return; | |||
495 | } | |||
496 | ||||
497 | // Don't touch naked functions. The assembly might be using an argument, or | |||
498 | // otherwise rely on the frame layout in a way that this analysis will not | |||
499 | // see. | |||
500 | if (F.hasFnAttribute(Attribute::Naked)) { | |||
501 | MarkLive(F); | |||
502 | return; | |||
503 | } | |||
504 | ||||
505 | unsigned RetCount = NumRetVals(&F); | |||
506 | ||||
507 | // Assume all return values are dead | |||
508 | using RetVals = SmallVector<Liveness, 5>; | |||
509 | ||||
510 | RetVals RetValLiveness(RetCount, MaybeLive); | |||
511 | ||||
512 | using RetUses = SmallVector<UseVector, 5>; | |||
513 | ||||
514 | // These vectors map each return value to the uses that make it MaybeLive, so | |||
515 | // we can add those to the Uses map if the return value really turns out to be | |||
516 | // MaybeLive. Initialized to a list of RetCount empty lists. | |||
517 | RetUses MaybeLiveRetUses(RetCount); | |||
518 | ||||
519 | bool HasMustTailCalls = false; | |||
520 | ||||
521 | for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { | |||
522 | if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { | |||
523 | if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() | |||
524 | != F.getFunctionType()->getReturnType()) { | |||
525 | // We don't support old style multiple return values. | |||
526 | MarkLive(F); | |||
527 | return; | |||
528 | } | |||
529 | } | |||
530 | ||||
531 | // If we have any returns of `musttail` results - the signature can't | |||
532 | // change | |||
533 | if (BB->getTerminatingMustTailCall() != nullptr) | |||
534 | HasMustTailCalls = true; | |||
535 | } | |||
536 | ||||
537 | if (HasMustTailCalls) { | |||
538 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()do { } while (false) | |||
539 | << " has musttail calls\n")do { } while (false); | |||
540 | } | |||
541 | ||||
542 | if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) { | |||
543 | MarkLive(F); | |||
544 | return; | |||
545 | } | |||
546 | ||||
547 | LLVM_DEBUG(do { } while (false) | |||
548 | dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: "do { } while (false) | |||
549 | << F.getName() << "\n")do { } while (false); | |||
550 | // Keep track of the number of live retvals, so we can skip checks once all | |||
551 | // of them turn out to be live. | |||
552 | unsigned NumLiveRetVals = 0; | |||
553 | ||||
554 | bool HasMustTailCallers = false; | |||
555 | ||||
556 | // Loop all uses of the function. | |||
557 | for (const Use &U : F.uses()) { | |||
558 | // If the function is PASSED IN as an argument, its address has been | |||
559 | // taken. | |||
560 | const auto *CB = dyn_cast<CallBase>(U.getUser()); | |||
561 | if (!CB || !CB->isCallee(&U)) { | |||
562 | MarkLive(F); | |||
563 | return; | |||
564 | } | |||
565 | ||||
566 | // The number of arguments for `musttail` call must match the number of | |||
567 | // arguments of the caller | |||
568 | if (CB->isMustTailCall()) | |||
569 | HasMustTailCallers = true; | |||
570 | ||||
571 | // If we end up here, we are looking at a direct call to our function. | |||
572 | ||||
573 | // Now, check how our return value(s) is/are used in this caller. Don't | |||
574 | // bother checking return values if all of them are live already. | |||
575 | if (NumLiveRetVals == RetCount) | |||
576 | continue; | |||
577 | ||||
578 | // Check all uses of the return value. | |||
579 | for (const Use &U : CB->uses()) { | |||
580 | if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) { | |||
581 | // This use uses a part of our return value, survey the uses of | |||
582 | // that part and store the results for this index only. | |||
583 | unsigned Idx = *Ext->idx_begin(); | |||
584 | if (RetValLiveness[Idx] != Live) { | |||
585 | RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); | |||
586 | if (RetValLiveness[Idx] == Live) | |||
587 | NumLiveRetVals++; | |||
588 | } | |||
589 | } else { | |||
590 | // Used by something else than extractvalue. Survey, but assume that the | |||
591 | // result applies to all sub-values. | |||
592 | UseVector MaybeLiveAggregateUses; | |||
593 | if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) { | |||
594 | NumLiveRetVals = RetCount; | |||
595 | RetValLiveness.assign(RetCount, Live); | |||
596 | break; | |||
597 | } else { | |||
598 | for (unsigned Ri = 0; Ri != RetCount; ++Ri) { | |||
599 | if (RetValLiveness[Ri] != Live) | |||
600 | MaybeLiveRetUses[Ri].append(MaybeLiveAggregateUses.begin(), | |||
601 | MaybeLiveAggregateUses.end()); | |||
602 | } | |||
603 | } | |||
604 | } | |||
605 | } | |||
606 | } | |||
607 | ||||
608 | if (HasMustTailCallers) { | |||
609 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - " << F.getName()do { } while (false) | |||
610 | << " has musttail callers\n")do { } while (false); | |||
611 | } | |||
612 | ||||
613 | // Now we've inspected all callers, record the liveness of our return values. | |||
614 | for (unsigned Ri = 0; Ri != RetCount; ++Ri) | |||
615 | MarkValue(CreateRet(&F, Ri), RetValLiveness[Ri], MaybeLiveRetUses[Ri]); | |||
616 | ||||
617 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Inspecting args for fn: "do { } while (false) | |||
618 | << F.getName() << "\n")do { } while (false); | |||
619 | ||||
620 | // Now, check all of our arguments. | |||
621 | unsigned ArgI = 0; | |||
622 | UseVector MaybeLiveArgUses; | |||
623 | for (Function::const_arg_iterator AI = F.arg_begin(), E = F.arg_end(); | |||
624 | AI != E; ++AI, ++ArgI) { | |||
625 | Liveness Result; | |||
626 | if (F.getFunctionType()->isVarArg() || HasMustTailCallers || | |||
627 | HasMustTailCalls) { | |||
628 | // Variadic functions will already have a va_arg function expanded inside | |||
629 | // them, making them potentially very sensitive to ABI changes resulting | |||
630 | // from removing arguments entirely, so don't. For example AArch64 handles | |||
631 | // register and stack HFAs very differently, and this is reflected in the | |||
632 | // IR which has already been generated. | |||
633 | // | |||
634 | // `musttail` calls to this function restrict argument removal attempts. | |||
635 | // The signature of the caller must match the signature of the function. | |||
636 | // | |||
637 | // `musttail` calls in this function prevents us from changing its | |||
638 | // signature | |||
639 | Result = Live; | |||
640 | } else { | |||
641 | // See what the effect of this use is (recording any uses that cause | |||
642 | // MaybeLive in MaybeLiveArgUses). | |||
643 | Result = SurveyUses(&*AI, MaybeLiveArgUses); | |||
644 | } | |||
645 | ||||
646 | // Mark the result. | |||
647 | MarkValue(CreateArg(&F, ArgI), Result, MaybeLiveArgUses); | |||
648 | // Clear the vector again for the next iteration. | |||
649 | MaybeLiveArgUses.clear(); | |||
650 | } | |||
651 | } | |||
652 | ||||
653 | /// MarkValue - This function marks the liveness of RA depending on L. If L is | |||
654 | /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses, | |||
655 | /// such that RA will be marked live if any use in MaybeLiveUses gets marked | |||
656 | /// live later on. | |||
657 | void DeadArgumentEliminationPass::MarkValue(const RetOrArg &RA, Liveness L, | |||
658 | const UseVector &MaybeLiveUses) { | |||
659 | switch (L) { | |||
660 | case Live: | |||
661 | MarkLive(RA); | |||
662 | break; | |||
663 | case MaybeLive: | |||
664 | assert(!IsLive(RA) && "Use is already live!")((void)0); | |||
665 | for (const auto &MaybeLiveUse : MaybeLiveUses) { | |||
666 | if (IsLive(MaybeLiveUse)) { | |||
667 | // A use is live, so this value is live. | |||
668 | MarkLive(RA); | |||
669 | break; | |||
670 | } else { | |||
671 | // Note any uses of this value, so this value can be | |||
672 | // marked live whenever one of the uses becomes live. | |||
673 | Uses.insert(std::make_pair(MaybeLiveUse, RA)); | |||
674 | } | |||
675 | } | |||
676 | break; | |||
677 | } | |||
678 | } | |||
679 | ||||
680 | /// MarkLive - Mark the given Function as alive, meaning that it cannot be | |||
681 | /// changed in any way. Additionally, | |||
682 | /// mark any values that are used as this function's parameters or by its return | |||
683 | /// values (according to Uses) live as well. | |||
684 | void DeadArgumentEliminationPass::MarkLive(const Function &F) { | |||
685 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Intrinsically live fn: "do { } while (false) | |||
686 | << F.getName() << "\n")do { } while (false); | |||
687 | // Mark the function as live. | |||
688 | LiveFunctions.insert(&F); | |||
689 | // Mark all arguments as live. | |||
690 | for (unsigned ArgI = 0, E = F.arg_size(); ArgI != E; ++ArgI) | |||
691 | PropagateLiveness(CreateArg(&F, ArgI)); | |||
692 | // Mark all return values as live. | |||
693 | for (unsigned Ri = 0, E = NumRetVals(&F); Ri != E; ++Ri) | |||
694 | PropagateLiveness(CreateRet(&F, Ri)); | |||
695 | } | |||
696 | ||||
697 | /// MarkLive - Mark the given return value or argument as live. Additionally, | |||
698 | /// mark any values that are used by this value (according to Uses) live as | |||
699 | /// well. | |||
700 | void DeadArgumentEliminationPass::MarkLive(const RetOrArg &RA) { | |||
701 | if (IsLive(RA)) | |||
702 | return; // Already marked Live. | |||
703 | ||||
704 | LiveValues.insert(RA); | |||
705 | ||||
706 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Marking "do { } while (false) | |||
707 | << RA.getDescription() << " live\n")do { } while (false); | |||
708 | PropagateLiveness(RA); | |||
709 | } | |||
710 | ||||
711 | bool DeadArgumentEliminationPass::IsLive(const RetOrArg &RA) { | |||
712 | return LiveFunctions.count(RA.F) || LiveValues.count(RA); | |||
713 | } | |||
714 | ||||
715 | /// PropagateLiveness - Given that RA is a live value, propagate it's liveness | |||
716 | /// to any other values it uses (according to Uses). | |||
717 | void DeadArgumentEliminationPass::PropagateLiveness(const RetOrArg &RA) { | |||
718 | // We don't use upper_bound (or equal_range) here, because our recursive call | |||
719 | // to ourselves is likely to cause the upper_bound (which is the first value | |||
720 | // not belonging to RA) to become erased and the iterator invalidated. | |||
721 | UseMap::iterator Begin = Uses.lower_bound(RA); | |||
722 | UseMap::iterator E = Uses.end(); | |||
723 | UseMap::iterator I; | |||
724 | for (I = Begin; I != E && I->first == RA; ++I) | |||
725 | MarkLive(I->second); | |||
726 | ||||
727 | // Erase RA from the Uses map (from the lower bound to wherever we ended up | |||
728 | // after the loop). | |||
729 | Uses.erase(Begin, I); | |||
730 | } | |||
731 | ||||
732 | // RemoveDeadStuffFromFunction - Remove any arguments and return values from F | |||
733 | // that are not in LiveValues. Transform the function and all of the callees of | |||
734 | // the function to not have these arguments and return values. | |||
735 | // | |||
736 | bool DeadArgumentEliminationPass::RemoveDeadStuffFromFunction(Function *F) { | |||
737 | // Don't modify fully live functions | |||
738 | if (LiveFunctions.count(F)) | |||
739 | return false; | |||
740 | ||||
741 | // Start by computing a new prototype for the function, which is the same as | |||
742 | // the old function, but has fewer arguments and a different return type. | |||
743 | FunctionType *FTy = F->getFunctionType(); | |||
744 | std::vector<Type*> Params; | |||
745 | ||||
746 | // Keep track of if we have a live 'returned' argument | |||
747 | bool HasLiveReturnedArg = false; | |||
748 | ||||
749 | // Set up to build a new list of parameter attributes. | |||
750 | SmallVector<AttributeSet, 8> ArgAttrVec; | |||
751 | const AttributeList &PAL = F->getAttributes(); | |||
752 | ||||
753 | // Remember which arguments are still alive. | |||
754 | SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false); | |||
755 | // Construct the new parameter list from non-dead arguments. Also construct | |||
756 | // a new set of parameter attributes to correspond. Skip the first parameter | |||
757 | // attribute, since that belongs to the return value. | |||
758 | unsigned ArgI = 0; | |||
759 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; | |||
760 | ++I, ++ArgI) { | |||
761 | RetOrArg Arg = CreateArg(F, ArgI); | |||
762 | if (LiveValues.erase(Arg)) { | |||
763 | Params.push_back(I->getType()); | |||
764 | ArgAlive[ArgI] = true; | |||
765 | ArgAttrVec.push_back(PAL.getParamAttributes(ArgI)); | |||
766 | HasLiveReturnedArg |= PAL.hasParamAttribute(ArgI, Attribute::Returned); | |||
767 | } else { | |||
768 | ++NumArgumentsEliminated; | |||
769 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument "do { } while (false) | |||
770 | << ArgI << " (" << I->getName() << ") from "do { } while (false) | |||
771 | << F->getName() << "\n")do { } while (false); | |||
772 | } | |||
773 | } | |||
774 | ||||
775 | // Find out the new return value. | |||
776 | Type *RetTy = FTy->getReturnType(); | |||
777 | Type *NRetTy = nullptr; | |||
778 | unsigned RetCount = NumRetVals(F); | |||
779 | ||||
780 | // -1 means unused, other numbers are the new index | |||
781 | SmallVector<int, 5> NewRetIdxs(RetCount, -1); | |||
782 | std::vector<Type*> RetTypes; | |||
783 | ||||
784 | // If there is a function with a live 'returned' argument but a dead return | |||
785 | // value, then there are two possible actions: | |||
786 | // 1) Eliminate the return value and take off the 'returned' attribute on the | |||
787 | // argument. | |||
788 | // 2) Retain the 'returned' attribute and treat the return value (but not the | |||
789 | // entire function) as live so that it is not eliminated. | |||
790 | // | |||
791 | // It's not clear in the general case which option is more profitable because, | |||
792 | // even in the absence of explicit uses of the return value, code generation | |||
793 | // is free to use the 'returned' attribute to do things like eliding | |||
794 | // save/restores of registers across calls. Whether or not this happens is | |||
795 | // target and ABI-specific as well as depending on the amount of register | |||
796 | // pressure, so there's no good way for an IR-level pass to figure this out. | |||
797 | // | |||
798 | // Fortunately, the only places where 'returned' is currently generated by | |||
799 | // the FE are places where 'returned' is basically free and almost always a | |||
800 | // performance win, so the second option can just be used always for now. | |||
801 | // | |||
802 | // This should be revisited if 'returned' is ever applied more liberally. | |||
803 | if (RetTy->isVoidTy() || HasLiveReturnedArg
| |||
804 | NRetTy = RetTy; | |||
805 | } else { | |||
806 | // Look at each of the original return values individually. | |||
807 | for (unsigned Ri = 0; Ri != RetCount; ++Ri) { | |||
808 | RetOrArg Ret = CreateRet(F, Ri); | |||
809 | if (LiveValues.erase(Ret)) { | |||
810 | RetTypes.push_back(getRetComponentType(F, Ri)); | |||
811 | NewRetIdxs[Ri] = RetTypes.size() - 1; | |||
812 | } else { | |||
813 | ++NumRetValsEliminated; | |||
814 | LLVM_DEBUG(do { } while (false) | |||
815 | dbgs() << "DeadArgumentEliminationPass - Removing return value "do { } while (false) | |||
816 | << Ri << " from " << F->getName() << "\n")do { } while (false); | |||
817 | } | |||
818 | } | |||
819 | if (RetTypes.size() > 1) { | |||
820 | // More than one return type? Reduce it down to size. | |||
821 | if (StructType *STy = dyn_cast<StructType>(RetTy)) { | |||
822 | // Make the new struct packed if we used to return a packed struct | |||
823 | // already. | |||
824 | NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); | |||
825 | } else { | |||
826 | assert(isa<ArrayType>(RetTy) && "unexpected multi-value return")((void)0); | |||
827 | NRetTy = ArrayType::get(RetTypes[0], RetTypes.size()); | |||
828 | } | |||
829 | } else if (RetTypes.size() == 1) | |||
830 | // One return type? Just a simple value then, but only if we didn't use to | |||
831 | // return a struct with that simple value before. | |||
832 | NRetTy = RetTypes.front(); | |||
833 | else if (RetTypes.empty()) | |||
834 | // No return types? Make it void, but only if we didn't use to return {}. | |||
835 | NRetTy = Type::getVoidTy(F->getContext()); | |||
836 | } | |||
837 | ||||
838 | assert(NRetTy && "No new return type found?")((void)0); | |||
839 | ||||
840 | // The existing function return attributes. | |||
841 | AttrBuilder RAttrs(PAL.getRetAttributes()); | |||
842 | ||||
843 | // Remove any incompatible attributes, but only if we removed all return | |||
844 | // values. Otherwise, ensure that we don't have any conflicting attributes | |||
845 | // here. Currently, this should not be possible, but special handling might be | |||
846 | // required when new return value attributes are added. | |||
847 | if (NRetTy->isVoidTy()) | |||
| ||||
848 | RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); | |||
849 | else | |||
850 | assert(!RAttrs.overlaps(AttributeFuncs::typeIncompatible(NRetTy)) &&((void)0) | |||
851 | "Return attributes no longer compatible?")((void)0); | |||
852 | ||||
853 | AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); | |||
854 | ||||
855 | // Strip allocsize attributes. They might refer to the deleted arguments. | |||
856 | AttributeSet FnAttrs = PAL.getFnAttributes().removeAttribute( | |||
857 | F->getContext(), Attribute::AllocSize); | |||
858 | ||||
859 | // Reconstruct the AttributesList based on the vector we constructed. | |||
860 | assert(ArgAttrVec.size() == Params.size())((void)0); | |||
861 | AttributeList NewPAL = | |||
862 | AttributeList::get(F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); | |||
863 | ||||
864 | // Create the new function type based on the recomputed parameters. | |||
865 | FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); | |||
866 | ||||
867 | // No change? | |||
868 | if (NFTy == FTy) | |||
869 | return false; | |||
870 | ||||
871 | // Create the new function body and insert it into the module... | |||
872 | Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace()); | |||
873 | NF->copyAttributesFrom(F); | |||
874 | NF->setComdat(F->getComdat()); | |||
875 | NF->setAttributes(NewPAL); | |||
876 | // Insert the new function before the old function, so we won't be processing | |||
877 | // it again. | |||
878 | F->getParent()->getFunctionList().insert(F->getIterator(), NF); | |||
879 | NF->takeName(F); | |||
880 | ||||
881 | // Loop over all of the callers of the function, transforming the call sites | |||
882 | // to pass in a smaller number of arguments into the new function. | |||
883 | std::vector<Value*> Args; | |||
884 | while (!F->use_empty()) { | |||
885 | CallBase &CB = cast<CallBase>(*F->user_back()); | |||
886 | ||||
887 | ArgAttrVec.clear(); | |||
888 | const AttributeList &CallPAL = CB.getAttributes(); | |||
889 | ||||
890 | // Adjust the call return attributes in case the function was changed to | |||
891 | // return void. | |||
892 | AttrBuilder RAttrs(CallPAL.getRetAttributes()); | |||
893 | RAttrs.remove(AttributeFuncs::typeIncompatible(NRetTy)); | |||
894 | AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs); | |||
895 | ||||
896 | // Declare these outside of the loops, so we can reuse them for the second | |||
897 | // loop, which loops the varargs. | |||
898 | auto I = CB.arg_begin(); | |||
899 | unsigned Pi = 0; | |||
900 | // Loop over those operands, corresponding to the normal arguments to the | |||
901 | // original function, and add those that are still alive. | |||
902 | for (unsigned E = FTy->getNumParams(); Pi != E; ++I, ++Pi) | |||
903 | if (ArgAlive[Pi]) { | |||
904 | Args.push_back(*I); | |||
905 | // Get original parameter attributes, but skip return attributes. | |||
906 | AttributeSet Attrs = CallPAL.getParamAttributes(Pi); | |||
907 | if (NRetTy != RetTy && Attrs.hasAttribute(Attribute::Returned)) { | |||
908 | // If the return type has changed, then get rid of 'returned' on the | |||
909 | // call site. The alternative is to make all 'returned' attributes on | |||
910 | // call sites keep the return value alive just like 'returned' | |||
911 | // attributes on function declaration but it's less clearly a win and | |||
912 | // this is not an expected case anyway | |||
913 | ArgAttrVec.push_back(AttributeSet::get( | |||
914 | F->getContext(), | |||
915 | AttrBuilder(Attrs).removeAttribute(Attribute::Returned))); | |||
916 | } else { | |||
917 | // Otherwise, use the original attributes. | |||
918 | ArgAttrVec.push_back(Attrs); | |||
919 | } | |||
920 | } | |||
921 | ||||
922 | // Push any varargs arguments on the list. Don't forget their attributes. | |||
923 | for (auto E = CB.arg_end(); I != E; ++I, ++Pi) { | |||
924 | Args.push_back(*I); | |||
925 | ArgAttrVec.push_back(CallPAL.getParamAttributes(Pi)); | |||
926 | } | |||
927 | ||||
928 | // Reconstruct the AttributesList based on the vector we constructed. | |||
929 | assert(ArgAttrVec.size() == Args.size())((void)0); | |||
930 | ||||
931 | // Again, be sure to remove any allocsize attributes, since their indices | |||
932 | // may now be incorrect. | |||
933 | AttributeSet FnAttrs = CallPAL.getFnAttributes().removeAttribute( | |||
934 | F->getContext(), Attribute::AllocSize); | |||
935 | ||||
936 | AttributeList NewCallPAL = AttributeList::get( | |||
937 | F->getContext(), FnAttrs, RetAttrs, ArgAttrVec); | |||
938 | ||||
939 | SmallVector<OperandBundleDef, 1> OpBundles; | |||
940 | CB.getOperandBundlesAsDefs(OpBundles); | |||
941 | ||||
942 | CallBase *NewCB = nullptr; | |||
943 | if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { | |||
944 | NewCB = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), | |||
945 | Args, OpBundles, "", CB.getParent()); | |||
946 | } else { | |||
947 | NewCB = CallInst::Create(NFTy, NF, Args, OpBundles, "", &CB); | |||
948 | cast<CallInst>(NewCB)->setTailCallKind( | |||
949 | cast<CallInst>(&CB)->getTailCallKind()); | |||
950 | } | |||
951 | NewCB->setCallingConv(CB.getCallingConv()); | |||
952 | NewCB->setAttributes(NewCallPAL); | |||
953 | NewCB->copyMetadata(CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg}); | |||
954 | Args.clear(); | |||
955 | ArgAttrVec.clear(); | |||
956 | ||||
957 | if (!CB.use_empty() || CB.isUsedByMetadata()) { | |||
958 | if (NewCB->getType() == CB.getType()) { | |||
959 | // Return type not changed? Just replace users then. | |||
960 | CB.replaceAllUsesWith(NewCB); | |||
961 | NewCB->takeName(&CB); | |||
962 | } else if (NewCB->getType()->isVoidTy()) { | |||
963 | // If the return value is dead, replace any uses of it with undef | |||
964 | // (any non-debug value uses will get removed later on). | |||
965 | if (!CB.getType()->isX86_MMXTy()) | |||
966 | CB.replaceAllUsesWith(UndefValue::get(CB.getType())); | |||
967 | } else { | |||
968 | assert((RetTy->isStructTy() || RetTy->isArrayTy()) &&((void)0) | |||
969 | "Return type changed, but not into a void. The old return type"((void)0) | |||
970 | " must have been a struct or an array!")((void)0); | |||
971 | Instruction *InsertPt = &CB; | |||
972 | if (InvokeInst *II = dyn_cast<InvokeInst>(&CB)) { | |||
973 | BasicBlock *NewEdge = | |||
974 | SplitEdge(NewCB->getParent(), II->getNormalDest()); | |||
975 | InsertPt = &*NewEdge->getFirstInsertionPt(); | |||
976 | } | |||
977 | ||||
978 | // We used to return a struct or array. Instead of doing smart stuff | |||
979 | // with all the uses, we will just rebuild it using extract/insertvalue | |||
980 | // chaining and let instcombine clean that up. | |||
981 | // | |||
982 | // Start out building up our return value from undef | |||
983 | Value *RetVal = UndefValue::get(RetTy); | |||
984 | for (unsigned Ri = 0; Ri != RetCount; ++Ri) | |||
985 | if (NewRetIdxs[Ri] != -1) { | |||
986 | Value *V; | |||
987 | IRBuilder<NoFolder> IRB(InsertPt); | |||
988 | if (RetTypes.size() > 1) | |||
989 | // We are still returning a struct, so extract the value from our | |||
990 | // return value | |||
991 | V = IRB.CreateExtractValue(NewCB, NewRetIdxs[Ri], "newret"); | |||
992 | else | |||
993 | // We are now returning a single element, so just insert that | |||
994 | V = NewCB; | |||
995 | // Insert the value at the old position | |||
996 | RetVal = IRB.CreateInsertValue(RetVal, V, Ri, "oldret"); | |||
997 | } | |||
998 | // Now, replace all uses of the old call instruction with the return | |||
999 | // struct we built | |||
1000 | CB.replaceAllUsesWith(RetVal); | |||
1001 | NewCB->takeName(&CB); | |||
1002 | } | |||
1003 | } | |||
1004 | ||||
1005 | // Finally, remove the old call from the program, reducing the use-count of | |||
1006 | // F. | |||
1007 | CB.eraseFromParent(); | |||
1008 | } | |||
1009 | ||||
1010 | // Since we have now created the new function, splice the body of the old | |||
1011 | // function right into the new function, leaving the old rotting hulk of the | |||
1012 | // function empty. | |||
1013 | NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); | |||
1014 | ||||
1015 | // Loop over the argument list, transferring uses of the old arguments over to | |||
1016 | // the new arguments, also transferring over the names as well. | |||
1017 | ArgI = 0; | |||
1018 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), | |||
1019 | I2 = NF->arg_begin(); | |||
1020 | I != E; ++I, ++ArgI) | |||
1021 | if (ArgAlive[ArgI]) { | |||
1022 | // If this is a live argument, move the name and users over to the new | |||
1023 | // version. | |||
1024 | I->replaceAllUsesWith(&*I2); | |||
1025 | I2->takeName(&*I); | |||
1026 | ++I2; | |||
1027 | } else { | |||
1028 | // If this argument is dead, replace any uses of it with undef | |||
1029 | // (any non-debug value uses will get removed later on). | |||
1030 | if (!I->getType()->isX86_MMXTy()) | |||
1031 | I->replaceAllUsesWith(UndefValue::get(I->getType())); | |||
1032 | } | |||
1033 | ||||
1034 | // If we change the return value of the function we must rewrite any return | |||
1035 | // instructions. Check this now. | |||
1036 | if (F->getReturnType() != NF->getReturnType()) | |||
1037 | for (BasicBlock &BB : *NF) | |||
1038 | if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) { | |||
1039 | IRBuilder<NoFolder> IRB(RI); | |||
1040 | Value *RetVal = nullptr; | |||
1041 | ||||
1042 | if (!NFTy->getReturnType()->isVoidTy()) { | |||
1043 | assert(RetTy->isStructTy() || RetTy->isArrayTy())((void)0); | |||
1044 | // The original return value was a struct or array, insert | |||
1045 | // extractvalue/insertvalue chains to extract only the values we need | |||
1046 | // to return and insert them into our new result. | |||
1047 | // This does generate messy code, but we'll let it to instcombine to | |||
1048 | // clean that up. | |||
1049 | Value *OldRet = RI->getOperand(0); | |||
1050 | // Start out building up our return value from undef | |||
1051 | RetVal = UndefValue::get(NRetTy); | |||
1052 | for (unsigned RetI = 0; RetI != RetCount; ++RetI) | |||
1053 | if (NewRetIdxs[RetI] != -1) { | |||
1054 | Value *EV = IRB.CreateExtractValue(OldRet, RetI, "oldret"); | |||
1055 | ||||
1056 | if (RetTypes.size() > 1) { | |||
1057 | // We're still returning a struct, so reinsert the value into | |||
1058 | // our new return value at the new index | |||
1059 | ||||
1060 | RetVal = IRB.CreateInsertValue(RetVal, EV, NewRetIdxs[RetI], | |||
1061 | "newret"); | |||
1062 | } else { | |||
1063 | // We are now only returning a simple value, so just return the | |||
1064 | // extracted value. | |||
1065 | RetVal = EV; | |||
1066 | } | |||
1067 | } | |||
1068 | } | |||
1069 | // Replace the return instruction with one returning the new return | |||
1070 | // value (possibly 0 if we became void). | |||
1071 | auto *NewRet = ReturnInst::Create(F->getContext(), RetVal, RI); | |||
1072 | NewRet->setDebugLoc(RI->getDebugLoc()); | |||
1073 | BB.getInstList().erase(RI); | |||
1074 | } | |||
1075 | ||||
1076 | // Clone metadatas from the old function, including debug info descriptor. | |||
1077 | SmallVector<std::pair<unsigned, MDNode *>, 1> MDs; | |||
1078 | F->getAllMetadata(MDs); | |||
1079 | for (auto MD : MDs) | |||
1080 | NF->addMetadata(MD.first, *MD.second); | |||
1081 | ||||
1082 | // Now that the old function is dead, delete it. | |||
1083 | F->eraseFromParent(); | |||
1084 | ||||
1085 | return true; | |||
1086 | } | |||
1087 | ||||
1088 | PreservedAnalyses DeadArgumentEliminationPass::run(Module &M, | |||
1089 | ModuleAnalysisManager &) { | |||
1090 | bool Changed = false; | |||
1091 | ||||
1092 | // First pass: Do a simple check to see if any functions can have their "..." | |||
1093 | // removed. We can do this if they never call va_start. This loop cannot be | |||
1094 | // fused with the next loop, because deleting a function invalidates | |||
1095 | // information computed while surveying other functions. | |||
1096 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Deleting dead varargs\n")do { } while (false); | |||
1097 | for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { | |||
1098 | Function &F = *I++; | |||
1099 | if (F.getFunctionType()->isVarArg()) | |||
1100 | Changed |= DeleteDeadVarargs(F); | |||
1101 | } | |||
1102 | ||||
1103 | // Second phase:loop through the module, determining which arguments are live. | |||
1104 | // We assume all arguments are dead unless proven otherwise (allowing us to | |||
1105 | // determine that dead arguments passed into recursive functions are dead). | |||
1106 | // | |||
1107 | LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n")do { } while (false); | |||
1108 | for (auto &F : M) | |||
1109 | SurveyFunction(F); | |||
1110 | ||||
1111 | // Now, remove all dead arguments and return values from each function in | |||
1112 | // turn. | |||
1113 | for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { | |||
1114 | // Increment now, because the function will probably get removed (ie. | |||
1115 | // replaced by a new one). | |||
1116 | Function *F = &*I++; | |||
1117 | Changed |= RemoveDeadStuffFromFunction(F); | |||
1118 | } | |||
1119 | ||||
1120 | // Finally, look for any unused parameters in functions with non-local | |||
1121 | // linkage and replace the passed in parameters with undef. | |||
1122 | for (auto &F : M) | |||
1123 | Changed |= RemoveDeadArgumentsFromCallers(F); | |||
1124 | ||||
1125 | if (!Changed) | |||
1126 | return PreservedAnalyses::all(); | |||
1127 | return PreservedAnalyses::none(); | |||
1128 | } |