LLVM  14.0.0git
DeadArgumentElimination.cpp
Go to the documentation of this file.
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 
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"
46 #include "llvm/Transforms/IPO.h"
48 #include <cassert>
49 #include <cstdint>
50 #include <utility>
51 #include <vector>
52 
53 using namespace llvm;
54 
55 #define DEBUG_TYPE "deadargelim"
56 
57 STATISTIC(NumArgumentsEliminated, "Number of unread args removed");
58 STATISTIC(NumRetValsEliminated , "Number of unused return values removed");
59 STATISTIC(NumArgumentsReplacedWithUndef,
60  "Number of unread args replaced with undef");
61 
62 namespace {
63 
64  /// DAE - The dead argument elimination pass.
65  class DAE : public ModulePass {
66  protected:
67  // DAH uses this to specify a different ID.
68  explicit DAE(char &ID) : ModulePass(ID) {}
69 
70  public:
71  static char ID; // Pass identification, replacement for typeid
72 
73  DAE() : ModulePass(ID) {
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)
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",
113  "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",
114  false, false)
115 
116 /// createDeadArgEliminationPass - This pass removes arguments from functions
117 /// which are not used by the body of the function.
118 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }
119 
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!");
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());
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()) {
190  for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo)
191  ArgAttrs.push_back(PAL.getParamAttrs(ArgNo));
192  PAL = AttributeList::get(Fn.getContext(), PAL.getFnAttrs(),
193  PAL.getRetAttrs(), ArgAttrs);
194  }
195 
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.
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.
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");
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.
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.
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 {
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.
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 
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()) &&
449  "Argument is not where we expected it");
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).
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..).
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()
539  << " has musttail calls\n");
540  }
541 
542  if (!F.hasLocalLinkage() && (!ShouldHackArguments || F.isIntrinsic())) {
543  MarkLive(F);
544  return;
545  }
546 
547  LLVM_DEBUG(
548  dbgs() << "DeadArgumentEliminationPass - Inspecting callers for fn: "
549  << F.getName() << "\n");
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()
610  << " has musttail callers\n");
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: "
618  << F.getName() << "\n");
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) {
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!");
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: "
686  << F.getName() << "\n");
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 "
707  << RA.getDescription() << " live\n");
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.getParamAttrs(ArgI));
766  HasLiveReturnedArg |= PAL.hasParamAttr(ArgI, Attribute::Returned);
767  } else {
768  ++NumArgumentsEliminated;
769  LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Removing argument "
770  << ArgI << " (" << I->getName() << ") from "
771  << F->getName() << "\n");
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(
815  dbgs() << "DeadArgumentEliminationPass - Removing return value "
816  << Ri << " from " << F->getName() << "\n");
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");
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?");
839 
840  // The existing function return attributes.
841  AttrBuilder RAttrs(PAL.getRetAttrs());
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)) &&
851  "Return attributes no longer compatible?");
852 
853  AttributeSet RetAttrs = AttributeSet::get(F->getContext(), RAttrs);
854 
855  // Strip allocsize attributes. They might refer to the deleted arguments.
856  AttributeSet FnAttrs =
857  PAL.getFnAttrs().removeAttribute(F->getContext(), Attribute::AllocSize);
858 
859  // Reconstruct the AttributesList based on the vector we constructed.
860  assert(ArgAttrVec.size() == Params.size());
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.getRetAttrs());
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.getParamAttrs(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.getParamAttrs(Pi));
926  }
927 
928  // Reconstruct the AttributesList based on the vector we constructed.
929  assert(ArgAttrVec.size() == Args.size());
930 
931  // Again, be sure to remove any allocsize attributes, since their indices
932  // may now be incorrect.
933  AttributeSet FnAttrs = CallPAL.getFnAttrs().removeAttribute(
934  F->getContext(), Attribute::AllocSize);
935 
936  AttributeList NewCallPAL = AttributeList::get(
937  F->getContext(), FnAttrs, RetAttrs, ArgAttrVec);
938 
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())
967  } else {
968  assert((RetTy->isStructTy() || RetTy->isArrayTy()) &&
969  "Return type changed, but not into a void. The old return type"
970  " must have been a struct or an array!");
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());
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.
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 
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");
1098  if (F.getFunctionType()->isVarArg())
1099  Changed |= DeleteDeadVarargs(F);
1100 
1101  // Second phase:loop through the module, determining which arguments are live.
1102  // We assume all arguments are dead unless proven otherwise (allowing us to
1103  // determine that dead arguments passed into recursive functions are dead).
1104  //
1105  LLVM_DEBUG(dbgs() << "DeadArgumentEliminationPass - Determining liveness\n");
1106  for (auto &F : M)
1107  SurveyFunction(F);
1108 
1109  // Now, remove all dead arguments and return values from each function in
1110  // turn. We use make_early_inc_range here because functions will probably get
1111  // removed (i.e. replaced by new ones).
1113  Changed |= RemoveDeadStuffFromFunction(&F);
1114 
1115  // Finally, look for any unused parameters in functions with non-local
1116  // linkage and replace the passed in parameters with undef.
1117  for (auto &F : M)
1118  Changed |= RemoveDeadArgumentsFromCallers(F);
1119 
1120  if (!Changed)
1121  return PreservedAnalyses::all();
1122  return PreservedAnalyses::none();
1123 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
llvm::AttributeFuncs::getUBImplyingAttributes
AttrBuilder getUBImplyingAttributes()
Get param/return attributes which imply immediate undefined behavior if an invalid value is passed.
Definition: Attributes.cpp:1926
DeadArgumentElimination.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::CallBase::getOperandBundlesAsDefs
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Definition: Instructions.cpp:363
llvm::InvokeInst::Create
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3785
llvm::Function::args
iterator_range< arg_iterator > args()
Definition: Function.h:772
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2978
NoFolder.h
llvm::StructType::get
static StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
Definition: Type.cpp:370
llvm::DeadArgumentEliminationPass::Live
@ Live
Definition: DeadArgumentElimination.h:74
llvm::DeadArgumentEliminationPass::Uses
UseMap Uses
This maps a return value or argument to any MaybeLive return values or arguments it uses.
Definition: DeadArgumentElimination.h:107
llvm::Type::isX86_MMXTy
bool isX86_MMXTy() const
Return true if this is X86 MMX.
Definition: Type.h:183
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
IntrinsicInst.h
llvm::Function::getBasicBlockList
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:710
llvm::DeadArgumentEliminationPass::CreateRet
RetOrArg CreateRet(const Function *F, unsigned Idx)
Convenience wrapper.
Definition: DeadArgumentElimination.h:82
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::IRBuilder
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2647
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2208
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:325
llvm::AttributeList::get
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:1040
llvm::AttributeFuncs::typeIncompatible
AttrBuilder typeIncompatible(Type *Ty)
Which attributes cannot be applied to a type.
Definition: Attributes.cpp:1892
llvm::createDeadArgEliminationPass
ModulePass * createDeadArgEliminationPass()
createDeadArgEliminationPass - This pass removes arguments from functions which are not used by the b...
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
llvm::AttributeList
Definition: Attributes.h:398
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1468
llvm::CallBase::isCallee
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
Definition: InstrTypes.h:1401
llvm::AttributeList::getFnAttrs
AttributeSet getFnAttrs() const
The function attributes are returned.
Definition: Attributes.cpp:1391
llvm::CallBase::isMustTailCall
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: Instructions.cpp:298
llvm::Instruction::copyMetadata
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
Definition: Instruction.cpp:829
llvm::FunctionType::getNumParams
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:139
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::CallBase::arg_begin
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1303
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::CallBase::removeParamAttrs
void removeParamAttrs(unsigned ArgNo, const AttrBuilder &AttrsToRemove)
Removes the attributes from the given argument.
Definition: InstrTypes.h:1574
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::FunctionType::isVarArg
bool isVarArg() const
Definition: DerivedTypes.h:123
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
Instruction.h
llvm::Type::isArrayTy
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:225
llvm::GlobalValue::hasExactDefinition
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:415
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::GlobalValue::isDeclaration
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:228
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
Intrinsics.h
llvm::FunctionType::param_end
param_iterator param_end() const
Definition: DerivedTypes.h:129
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1472
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1518
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
llvm::BasicBlock::getFirstInsertionPt
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:249
llvm::DeadArgumentEliminationPass::CreateArg
RetOrArg CreateArg(const Function *F, unsigned Idx)
Convenience wrapper.
Definition: DeadArgumentElimination.h:87
llvm::FunctionType::param_begin
param_iterator param_begin() const
Definition: DerivedTypes.h:128
llvm::Instruction
Definition: Instruction.h:45
llvm::DeadArgumentEliminationPass::Liveness
Liveness
Liveness enum - During our initial pass over the program, we determine that things are either alive o...
Definition: DeadArgumentElimination.h:74
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Function::copyAttributesFrom
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:712
llvm::GlobalObject::addMetadata
void addMetadata(unsigned KindID, MDNode &MD)
Add a metadata attachment.
Definition: Metadata.cpp:1268
llvm::DeadArgumentEliminationPass::LiveValues
LiveSet LiveValues
This set contains all values that have been determined to be live.
Definition: DeadArgumentElimination.h:113
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
llvm::createDeadArgHackingPass
ModulePass * createDeadArgHackingPass()
DeadArgHacking pass - Same as DAE, but delete arguments of external functions as well.
Definition: DeadArgumentElimination.cpp:120
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
llvm::DeadArgumentEliminationPass::UseVector
SmallVector< RetOrArg, 5 > UseVector
Definition: DeadArgumentElimination.h:118
llvm::CallBase::getCallingConv
CallingConv::ID getCallingConv() const
Definition: InstrTypes.h:1449
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
Type.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3741
NumRetVals
static unsigned NumRetVals(const Function *F)
Convenience function that returns the number of return values.
Definition: DeadArgumentElimination.cpp:330
llvm::Function::hasFnAttribute
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.cpp:626
BasicBlock.h
INITIALIZE_PASS
INITIALIZE_PASS(DAH, "deadarghaX0r", "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", false, false) ModulePass *llvm
createDeadArgEliminationPass - This pass removes arguments from functions which are not used by the b...
Definition: DeadArgumentElimination.cpp:112
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:156
llvm::AttributeList::getRetAttrs
AttributeSet getRetAttrs() const
The attributes for the ret value are returned.
Definition: Attributes.cpp:1387
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::Function::getReturnType
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:181
getRetComponentType
static Type * getRetComponentType(const Function *F, unsigned Idx)
Returns the sub-type a function will return at a given Idx.
Definition: DeadArgumentElimination.cpp:345
llvm::AttributeSet::get
static AttributeSet get(LLVMContext &C, const AttrBuilder &B)
Definition: Attributes.cpp:590
IPO.h
llvm::Function::removeParamAttrs
void removeParamAttrs(unsigned ArgNo, const AttrBuilder &Attrs)
removes the attribute from the list of attributes.
Definition: Function.cpp:616
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::AttrBuilder
Definition: Attributes.h:907
llvm::GlobalObject::setComdat
void setComdat(Comdat *C)
Definition: GlobalObject.h:125
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:572
llvm::DeadArgumentEliminationPass
Eliminate dead arguments (and return values) from functions.
Definition: DeadArgumentElimination.h:38
llvm::DeadArgumentEliminationPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: DeadArgumentElimination.cpp:1088
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:138
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::GlobalValue::hasLocalLinkage
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
llvm::DeadArgumentEliminationPass::LiveFunctions
LiveFuncSet LiveFunctions
This set contains all values that are cannot be changed in any way.
Definition: DeadArgumentElimination.h:116
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:138
llvm::AttributeSet::removeAttribute
LLVM_NODISCARD AttributeSet removeAttribute(LLVMContext &C, Attribute::AttrKind Kind) const
Remove the specified attribute from this set.
Definition: Attributes.cpp:628
llvm::ArrayType::get
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:602
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
llvm::CallBase::arg_end
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1309
llvm::Constant::removeDeadConstantUsers
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:741
llvm::DeadArgumentEliminationPass::ShouldHackArguments
bool ShouldHackArguments
This allows this pass to do double-duty as the dead arg hacking pass (used only by bugpoint).
Definition: DeadArgumentElimination.h:122
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::PreservedAnalyses::areAllPreserved
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
Definition: PassManager.h:330
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
llvm::DeadArgumentEliminationPass::MaybeLive
@ MaybeLive
Definition: DeadArgumentElimination.h:74
llvm::CallInst::isMustTailCall
bool isMustTailCall() const
Definition: Instructions.h:1674
llvm::Function::hasAddressTaken
bool hasAddressTaken(const User **=nullptr, bool IgnoreCallbackUses=false, bool IgnoreAssumeLikeCalls=true, bool IngoreLLVMUsed=false, bool IgnoreARCAttachedCall=false) const
hasAddressTaken - returns true if there are any uses of this function other than direct calls or invo...
Definition: Function.cpp:1738
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1343
llvm::Function::begin
iterator begin()
Definition: Function.h:733
Argument.h
Attributes.h
llvm::SplitEdge
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Definition: BasicBlockUtils.cpp:493
llvm::CallBase::isBundleOperand
bool isBundleOperand(unsigned Idx) const
Return true if the operand at index Idx is a bundle operand.
Definition: InstrTypes.h:1920
llvm::Value::user_iterator
user_iterator_impl< User > user_iterator
Definition: Value.h:391
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2372
Casting.h
Function.h
PassManager.h
llvm::ReturnInst::Create
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3005
llvm::Function::getFunctionType
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:176
llvm::CallBase::getArgOperandNo
unsigned getArgOperandNo(const Use *U) const
Given a use for a arg operand, get the arg operand number that corresponds to it.
Definition: InstrTypes.h:1369
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:748
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:45
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:186
Instructions.h
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:222
llvm::AttributeSet
Definition: Attributes.h:266
SmallVector.h
User.h
llvm::Value::isUsedByMetadata
bool isUsedByMetadata() const
Return true if there is metadata referencing this value.
Definition: Value.h:551
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1338
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
DerivedTypes.h
llvm::InsertValueInst::getAggregateOperandIndex
static unsigned getAggregateOperandIndex()
Definition: Instructions.h:2553
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:370
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::initializeDAEPass
void initializeDAEPass(PassRegistry &)
raw_ostream.h
llvm::AttributeList::hasParamAttr
bool hasParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the attribute exists for the given argument.
Definition: Attributes.h:721
llvm::AttributeList::getParamAttrs
AttributeSet getParamAttrs(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
Definition: Attributes.cpp:1383
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2483
BasicBlockUtils.h
Value.h
llvm::Function::setAttributes
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
Definition: Function.h:329
InitializePasses.h
llvm::FunctionType::getReturnType
Type * getReturnType() const
Definition: DerivedTypes.h:124
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::AttributeList::isEmpty
bool isEmpty() const
Return true if there are no attributes.
Definition: Attributes.h:868
llvm::Function::const_iterator
BasicBlockListType::const_iterator const_iterator
Definition: Function.h:68
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1453
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37