55#define DEBUG_TYPE "deadargelim"
57STATISTIC(NumArgumentsEliminated,
"Number of unread args removed");
58STATISTIC(NumRetValsEliminated,
"Number of unused return values removed");
60 "Number of unread args replaced with poison");
86 virtual bool shouldHackArguments()
const {
return false; }
89bool isMustTailCalleeAnalyzable(
const CallBase &CB) {
98INITIALIZE_PASS(DAE,
"deadargelim",
"Dead Argument Elimination",
false,
false)
104struct DAH :
public DAE {
109 bool shouldHackArguments()
const override {
return true; }
117 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",
false,
128bool DeadArgumentEliminationPass::deleteDeadVarargs(
Function &
F) {
129 assert(
F.getFunctionType()->isVarArg() &&
"Function isn't varargs!");
130 if (
F.isDeclaration() || !
F.hasLocalLinkage())
134 if (
F.hasAddressTaken())
140 if (
F.hasFnAttribute(Attribute::Naked)) {
154 if (II->getIntrinsicID() == Intrinsic::vastart)
167 std::vector<Type *> Params(FTy->param_begin(), FTy->param_end());
169 unsigned NumArgs = Params.size();
175 F.getParent()->getFunctionList().insert(
F.getIterator(), NF);
182 std::vector<Value *>
Args;
184 CallBase *CB = dyn_cast<CallBase>(U);
195 for (
unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo)
205 if (
InvokeInst *II = dyn_cast<InvokeInst>(CB)) {
210 cast<CallInst>(NewCB)->setTailCallKind(
211 cast<CallInst>(CB)->getTailCallKind());
215 NewCB->
copyMetadata(*CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
241 I->replaceAllUsesWith(&*I2);
247 F.getAllMetadata(MDs);
248 for (
auto [KindID,
Node] : MDs)
252 F.replaceAllUsesWith(NF);
263bool DeadArgumentEliminationPass::removeDeadArgumentsFromCallers(
Function &
F) {
275 if (!
F.hasExactDefinition())
283 !
F.getFunctionType()->isVarArg())
289 if (
F.hasFnAttribute(Attribute::Naked))
296 bool Changed =
false;
301 if (!Arg.hasSwiftErrorAttr() && Arg.use_empty() &&
302 !Arg.hasPassPointeeByValueCopyAttr()) {
303 if (Arg.isUsedByMetadata()) {
308 F.removeParamAttrs(Arg.getArgNo(), UBImplyingAttributes);
312 if (UnusedArgs.
empty())
315 for (
Use &U :
F.uses()) {
316 CallBase *CB = dyn_cast<CallBase>(
U.getUser());
322 for (
unsigned I = 0,
E = UnusedArgs.
size();
I !=
E; ++
I) {
323 unsigned ArgNo = UnusedArgs[
I];
329 ++NumArgumentsReplacedWithPoison;
342 if (
RetTy->isVoidTy())
345 return STy->getNumElements();
347 return ATy->getNumElements();
359 return STy->getElementType(
Idx);
361 return ATy->getElementType();
368DeadArgumentEliminationPass::markIfNotLive(RetOrArg
Use,
369 UseVector &MaybeLiveUses) {
376 MaybeLiveUses.push_back(
Use);
388DeadArgumentEliminationPass::surveyUse(
const Use *U, UseVector &MaybeLiveUses,
389 unsigned RetValNum) {
390 const User *V = U->getUser();
391 if (
const ReturnInst *RI = dyn_cast<ReturnInst>(V)) {
396 const Function *
F = RI->getParent()->getParent();
397 if (RetValNum != -1U) {
400 return markIfNotLive(
Use, MaybeLiveUses);
410 markIfNotLive(
Use, MaybeLiveUses);
423 RetValNum = *
IV->idx_begin();
429 for (
const Use &UU :
IV->uses()) {
430 Result = surveyUse(&UU, MaybeLiveUses, RetValNum);
437 if (
const auto *CB = dyn_cast<CallBase>(V)) {
452 if (ArgNo >=
F->getFunctionType()->getNumParams())
457 "Argument is not where we expected it");
462 return markIfNotLive(
Use, MaybeLiveUses);
476DeadArgumentEliminationPass::surveyUses(
const Value *V,
477 UseVector &MaybeLiveUses) {
481 for (
const Use &U : V->uses()) {
482 Result = surveyUse(&U, MaybeLiveUses);
495void DeadArgumentEliminationPass::surveyFunction(
const Function &
F) {
498 if (
F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) ||
499 F.getAttributes().hasAttrSomewhere(Attribute::Preallocated)) {
507 if (
F.hasFnAttribute(Attribute::Naked)) {
517 RetVals RetValLiveness(RetCount,
MaybeLive);
524 RetUses MaybeLiveRetUses(RetCount);
526 bool HasMustTailCalls =
false;
530 if (
const auto *TC = BB.getTerminatingMustTailCall()) {
531 HasMustTailCalls =
true;
535 if (!isMustTailCalleeAnalyzable(*TC)) {
542 if (HasMustTailCalls) {
544 <<
" has musttail calls\n");
553 dbgs() <<
"DeadArgumentEliminationPass - Inspecting callers for fn: "
554 <<
F.getName() <<
"\n");
557 unsigned NumLiveRetVals = 0;
559 bool HasMustTailCallers =
false;
562 for (
const Use &U :
F.uses()) {
565 const auto *CB = dyn_cast<CallBase>(U.getUser());
575 HasMustTailCallers =
true;
581 if (NumLiveRetVals == RetCount)
585 for (
const Use &UU : CB->
uses()) {
589 unsigned Idx = *Ext->idx_begin();
590 if (RetValLiveness[
Idx] !=
Live) {
591 RetValLiveness[
Idx] = surveyUses(Ext, MaybeLiveRetUses[
Idx]);
592 if (RetValLiveness[
Idx] ==
Live)
599 if (surveyUse(&UU, MaybeLiveAggregateUses) ==
Live) {
600 NumLiveRetVals = RetCount;
601 RetValLiveness.assign(RetCount,
Live);
605 for (
unsigned Ri = 0; Ri != RetCount; ++Ri) {
606 if (RetValLiveness[Ri] !=
Live)
607 MaybeLiveRetUses[Ri].append(MaybeLiveAggregateUses.begin(),
608 MaybeLiveAggregateUses.end());
614 if (HasMustTailCallers) {
616 <<
" has musttail callers\n");
620 for (
unsigned Ri = 0; Ri != RetCount; ++Ri)
621 markValue(
createRet(&
F, Ri), RetValLiveness[Ri], MaybeLiveRetUses[Ri]);
623 LLVM_DEBUG(
dbgs() <<
"DeadArgumentEliminationPass - Inspecting args for fn: "
624 <<
F.getName() <<
"\n");
630 AI !=
E; ++AI, ++ArgI) {
632 if (
F.getFunctionType()->isVarArg() || HasMustTailCallers ||
649 Result = surveyUses(&*AI, MaybeLiveArgUses);
653 markValue(
createArg(&
F, ArgI), Result, MaybeLiveArgUses);
655 MaybeLiveArgUses.clear();
662void DeadArgumentEliminationPass::markValue(
const RetOrArg &
RA, Liveness L,
663 const UseVector &MaybeLiveUses) {
669 assert(!isLive(
RA) &&
"Use is already live!");
670 for (
const auto &MaybeLiveUse : MaybeLiveUses) {
671 if (isLive(MaybeLiveUse)) {
678 Uses.emplace(MaybeLiveUse,
RA);
687void DeadArgumentEliminationPass::markLive(
const Function &
F) {
688 LLVM_DEBUG(
dbgs() <<
"DeadArgumentEliminationPass - Intrinsically live fn: "
689 <<
F.getName() <<
"\n");
693 for (
unsigned ArgI = 0,
E =
F.arg_size(); ArgI !=
E; ++ArgI)
702void DeadArgumentEliminationPass::markLive(
const RetOrArg &
RA) {
709 <<
RA.getDescription() <<
" live\n");
710 propagateLiveness(
RA);
713bool DeadArgumentEliminationPass::isLive(
const RetOrArg &
RA) {
719void DeadArgumentEliminationPass::propagateLiveness(
const RetOrArg &
RA) {
723 UseMap::iterator Begin =
Uses.lower_bound(
RA);
724 UseMap::iterator
E =
Uses.end();
726 for (
I = Begin;
I !=
E &&
I->first ==
RA; ++
I)
731 Uses.erase(Begin,
I);
737bool DeadArgumentEliminationPass::removeDeadStuffFromFunction(
Function *
F) {
745 std::vector<Type *> Params;
748 bool HasLiveReturnedArg =
false;
764 Params.push_back(
I->getType());
765 ArgAlive[ArgI] =
true;
767 HasLiveReturnedArg |= PAL.
hasParamAttr(ArgI, Attribute::Returned);
769 ++NumArgumentsEliminated;
770 LLVM_DEBUG(
dbgs() <<
"DeadArgumentEliminationPass - Removing argument "
771 << ArgI <<
" (" <<
I->getName() <<
") from "
772 <<
F->getName() <<
"\n");
778 Type *NRetTy =
nullptr;
783 std::vector<Type *> RetTypes;
804 if (
RetTy->isVoidTy() || HasLiveReturnedArg) {
808 for (
unsigned Ri = 0; Ri != RetCount; ++Ri) {
811 RetTypes.push_back(getRetComponentType(
F, Ri));
812 NewRetIdxs[Ri] = RetTypes.size() - 1;
814 ++NumRetValsEliminated;
816 dbgs() <<
"DeadArgumentEliminationPass - Removing return value "
817 << Ri <<
" from " <<
F->getName() <<
"\n");
820 if (RetTypes.size() > 1) {
825 NRetTy =
StructType::get(STy->getContext(), RetTypes, STy->isPacked());
827 assert(isa<ArrayType>(
RetTy) &&
"unexpected multi-value return");
830 }
else if (RetTypes.size() == 1)
833 NRetTy = RetTypes.front();
834 else if (RetTypes.empty())
839 assert(NRetTy &&
"No new return type found?");
852 "Return attributes no longer compatible?");
879 F->getParent()->getFunctionList().insert(
F->getIterator(), NF);
885 std::vector<Value *>
Args;
886 while (!
F->use_empty()) {
887 CallBase &CB = cast<CallBase>(*
F->user_back());
904 for (
unsigned E = FTy->getNumParams(); Pi !=
E; ++
I, ++Pi)
909 if (NRetTy !=
RetTy &&
Attrs.hasAttribute(Attribute::Returned)) {
936 F->getContext(), Attribute::AllocSize);
945 if (
InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {
950 cast<CallInst>(NewCB)->setTailCallKind(
951 cast<CallInst>(&CB)->getTailCallKind());
955 NewCB->
copyMetadata(CB, {LLVMContext::MD_prof, LLVMContext::MD_dbg});
971 "Return type changed, but not into a void. The old return type"
972 " must have been a struct or an array!");
974 if (
InvokeInst *II = dyn_cast<InvokeInst>(&CB)) {
986 for (
unsigned Ri = 0; Ri != RetCount; ++Ri)
987 if (NewRetIdxs[Ri] != -1) {
990 if (RetTypes.size() > 1)
993 V = IRB.CreateExtractValue(NewCB, NewRetIdxs[Ri],
"newret");
998 RetVal = IRB.CreateInsertValue(RetVal, V, Ri,
"oldret");
1022 I !=
E; ++
I, ++ArgI)
1023 if (ArgAlive[ArgI]) {
1026 I->replaceAllUsesWith(&*I2);
1032 if (!
I->getType()->isX86_MMXTy())
1040 if (
ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
1042 Value *RetVal =
nullptr;
1044 if (!NFTy->getReturnType()->isVoidTy()) {
1051 Value *OldRet = RI->getOperand(0);
1054 for (
unsigned RetI = 0; RetI != RetCount; ++RetI)
1055 if (NewRetIdxs[RetI] != -1) {
1056 Value *EV = IRB.CreateExtractValue(OldRet, RetI,
"oldret");
1058 if (RetTypes.size() > 1) {
1062 RetVal = IRB.CreateInsertValue(RetVal, EV, NewRetIdxs[RetI],
1075 NewRet->setDebugLoc(RI->getDebugLoc());
1076 RI->eraseFromParent();
1081 F->getAllMetadata(MDs);
1082 for (
auto [KindID,
Node] : MDs)
1083 NF->addMetadata(KindID, *
Node);
1089 if (NFTy != FTy && NF->getSubprogram()) {
1091 auto Temp = SP->getType()->cloneWithCC(llvm::dwarf::DW_CC_nocall);
1096 F->eraseFromParent();
1101void DeadArgumentEliminationPass::propagateVirtMustcallLiveness(
1106 while (!NewLiveFuncs.empty()) {
1108 for (
const auto *
F : NewLiveFuncs)
1109 for (
const auto *U :
F->users())
1110 if (
const auto *CB = dyn_cast<CallBase>(U))
1114 NewLiveFuncs.clear();
1115 NewLiveFuncs.insert(Temp.begin(), Temp.end());
1116 for (
const auto *
F : Temp)
1123 bool Changed =
false;
1129 LLVM_DEBUG(
dbgs() <<
"DeadArgumentEliminationPass - Deleting dead varargs\n");
1131 if (
F.getFunctionType()->isVarArg())
1132 Changed |= deleteDeadVarargs(
F);
1137 LLVM_DEBUG(
dbgs() <<
"DeadArgumentEliminationPass - Determining liveness\n");
1141 propagateVirtMustcallLiveness(M);
1147 Changed |= removeDeadStuffFromFunction(&
F);
1152 Changed |= removeDeadArgumentsFromCallers(
F);
This file contains the simple types necessary to represent the attributes associated with functions a...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
assert(!RetTy->isVoidTy() &&"void type has no subtype")
Convenience function that returns the number of return values It returns for void functions and for functions not returning a struct It returns the number of struct elements for functions returning a struct static unsigned numRetVals(const Function *F)
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
static const uint32_t IV[8]
A container for analyses that lazily runs them and caches their results.
This class represents an incoming formal argument to a Function.
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
AttrBuilder & removeAttribute(Attribute::AttrKind Val)
Remove an attribute from the builder.
AttributeSet getFnAttrs() const
The function attributes are returned.
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute > > Attrs)
Create an AttributeList with the specified parameters in it.
bool isEmpty() const
Return true if there are no attributes.
AttributeSet getRetAttrs() const
The attributes for the ret value are returned.
bool hasParamAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the attribute exists for the given argument.
AttributeSet getParamAttrs(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
AttributeSet removeAttribute(LLVMContext &C, Attribute::AttrKind Kind) const
Remove the specified attribute from this set.
static AttributeSet get(LLVMContext &C, const AttrBuilder &B)
LLVM Basic Block Representation.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
void setCallingConv(CallingConv::ID CC)
void removeParamAttrs(unsigned ArgNo, const AttributeMask &AttrsToRemove)
Removes the attributes from the given argument.
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
CallingConv::ID getCallingConv() const
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
bool isBundleOperand(unsigned Idx) const
Return true if the operand at index Idx is a bundle operand.
FunctionType * getFunctionType() const
unsigned getArgOperandNo(const Use *U) const
Given a use for a arg operand, get the arg operand number that corresponds to it.
AttributeList getAttributes() const
Return the parameter attributes for this call.
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr, BasicBlock::iterator InsertBefore)
bool isMustTailCall() const
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Eliminate dead arguments (and return values) from functions.
SmallVector< RetOrArg, 5 > UseVector
std::set< const Function * > LiveFuncSet
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Liveness
During our initial pass over the program, we determine that things are either alive or maybe alive.
LiveSet LiveValues
This set contains all values that have been determined to be live.
RetOrArg createRet(const Function *F, unsigned Idx)
Convenience wrapper.
RetOrArg createArg(const Function *F, unsigned Idx)
Convenience wrapper.
bool ShouldHackArguments
This allows this pass to do double-duty as the dead arg hacking pass (used only by bugpoint).
LiveFuncSet LiveFunctions
This set contains all values that are cannot be changed in any way.
UseMap Uses
This maps a return value or argument to any MaybeLive return values or arguments it uses.
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
void splice(Function::iterator ToIt, Function *FromF)
Transfer all blocks from FromF to this function at ToIt.
bool IsNewDbgInfoFormat
Is this function using intrinsics to record the position of debugging information,...
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
Type * getReturnType() const
Returns the type of the ret val.
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
void setComdat(Comdat *C)
void addMetadata(unsigned KindID, MDNode &MD)
Add a metadata attachment.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
This instruction inserts a struct field of array element value into an aggregate value.
static unsigned getAggregateOperandIndex()
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
A wrapper class for inspecting calls to intrinsic functions.
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, BasicBlock::iterator InsertBefore)
static std::enable_if_t< std::is_base_of< MDNode, T >::value, T * > replaceWithPermanent(std::unique_ptr< T, TempMDNodeDeleter > N)
Replace a temporary node with a permanent one.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
bool skipModule(Module &M) const
Optional passes call this function to check whether the pass should be skipped.
virtual bool runOnModule(Module &M)=0
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Return a value (possibly void), from a function.
static ReturnInst * Create(LLVMContext &C, Value *retVal, BasicBlock::iterator InsertBefore)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
static StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isX86_MMXTy() const
Return true if this is X86 MMX.
static Type * getVoidTy(LLVMContext &C)
bool isVoidTy() const
Return true if this is 'void'.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
bool isUsedByMetadata() const
Return true if there is metadata referencing this value.
iterator_range< use_iterator > uses()
void takeName(Value *V)
Transfer the name from V to this value.
self_iterator getIterator()
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
AttributeMask getUBImplyingAttributes()
Get param/return attributes which imply immediate undefined behavior if an invalid value is passed.
AttributeMask typeIncompatible(Type *Ty, AttributeSafetyKind ASK=ASK_ALL)
Which attributes cannot be applied to a type.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
ModulePass * createDeadArgEliminationPass()
createDeadArgEliminationPass - This pass removes arguments from functions which are not used by the b...
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...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void initializeDAEPass(PassRegistry &)
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...
ModulePass * createDeadArgHackingPass()
DeadArgHacking pass - Same as DAE, but delete arguments of external functions as well.