X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FDeadArgumentElimination.cpp;h=d0447640259e4e55dc6224a00f0e36ca73237727;hb=ce2b45bd7dc5dc17de6b50234f8d24ef1fed1d3b;hp=f386ed78b5f54e2b97c18b83701474f90b2368c9;hpb=cc52ed0c4feec63e7a127462b78fd4a6b217f469;p=oota-llvm.git diff --git a/lib/Transforms/IPO/DeadArgumentElimination.cpp b/lib/Transforms/IPO/DeadArgumentElimination.cpp index f386ed78b5f..d0447640259 100644 --- a/lib/Transforms/IPO/DeadArgumentElimination.cpp +++ b/lib/Transforms/IPO/DeadArgumentElimination.cpp @@ -17,29 +17,35 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "deadargelim" #include "llvm/Transforms/IPO.h" -#include "llvm/CallingConv.h" -#include "llvm/Constant.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/LLVMContext.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/CallSite.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/CallingConv.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/DIBuilder.h" +#include "llvm/IR/DebugInfo.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include #include +#include using namespace llvm; +#define DEBUG_TYPE "deadargelim" + STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); - +STATISTIC(NumArgumentsReplacedWithUndef, + "Number of unread args replaced with undef"); namespace { /// DAE - The dead argument elimination pass. /// @@ -48,9 +54,9 @@ namespace { /// Struct that represents (part of) either a return value or a function /// argument. Used so that arguments and return values can be used - /// interchangably. + /// interchangeably. struct RetOrArg { - RetOrArg(const Function* F, unsigned Idx, bool IsArg) : F(F), Idx(Idx), + RetOrArg(const Function *F, unsigned Idx, bool IsArg) : F(F), Idx(Idx), IsArg(IsArg) {} const Function *F; unsigned Idx; @@ -58,12 +64,7 @@ namespace { /// Make RetOrArg comparable, so we can put it into a map. bool operator<(const RetOrArg &O) const { - if (F != O.F) - return F < O.F; - else if (Idx != O.Idx) - return Idx < O.Idx; - else - return IsArg < O.IsArg; + return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg); } /// Make RetOrArg comparable, so we can easily iterate the multimap. @@ -72,8 +73,8 @@ namespace { } std::string getDescription() const { - return std::string((IsArg ? "Argument #" : "Return value #")) - + utostr(Idx) + " of function " + F->getNameStr(); + return (Twine(IsArg ? "Argument #" : "Return value #") + utostr(Idx) + + " of function " + F->getName()).str(); } }; @@ -120,20 +121,35 @@ namespace { typedef SmallVector UseVector; + // Map each LLVM function to corresponding metadata with debug info. If + // the function is replaced with another one, we should patch the pointer + // to LLVM function in metadata. + // As the code generation for module is finished (and DIBuilder is + // finalized) we assume that subprogram descriptors won't be changed, and + // they are stored in map for short duration anyway. + DenseMap FunctionDIs; + + protected: + // DAH uses this to specify a different ID. + explicit DAE(char &ID) : ModulePass(ID) {} + public: static char ID; // Pass identification, replacement for typeid - DAE() : ModulePass(&ID) {} - bool runOnModule(Module &M); + DAE() : ModulePass(ID) { + initializeDAEPass(*PassRegistry::getPassRegistry()); + } + + bool runOnModule(Module &M) override; virtual bool ShouldHackArguments() const { return false; } private: Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); - Liveness SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, - unsigned RetValNum = 0); - Liveness SurveyUses(Value *V, UseVector &MaybeLiveUses); + Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses, + unsigned RetValNum = -1U); + Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); - void SurveyFunction(Function &F); + void SurveyFunction(const Function &F); void MarkValue(const RetOrArg &RA, Liveness L, const UseVector &MaybeLiveUses); void MarkLive(const RetOrArg &RA); @@ -141,13 +157,13 @@ namespace { void PropagateLiveness(const RetOrArg &RA); bool RemoveDeadStuffFromFunction(Function *F); bool DeleteDeadVarargs(Function &Fn); + bool RemoveDeadArgumentsFromCallers(Function &Fn); }; } char DAE::ID = 0; -static RegisterPass -X("deadargelim", "Dead Argument Elimination"); +INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false) namespace { /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but @@ -155,13 +171,16 @@ namespace { /// by bugpoint. struct DAH : public DAE { static char ID; - virtual bool ShouldHackArguments() const { return true; } + DAH() : DAE(ID) {} + + bool ShouldHackArguments() const override { return true; } }; } char DAH::ID = 0; -static RegisterPass -Y("deadarghaX0r", "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)"); +INITIALIZE_PASS(DAH, "deadarghaX0r", + "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)", + false, false) /// createDeadArgEliminationPass - This pass removes arguments from functions /// which are not used by the body of the function. @@ -180,10 +199,15 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { return false; // Okay, we know we can transform this function if safe. Scan its body - // looking for calls to llvm.vastart. + // looking for calls marked musttail or calls to llvm.vastart. for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { - if (IntrinsicInst *II = dyn_cast(I)) { + CallInst *CI = dyn_cast(I); + if (!CI) + continue; + if (CI->isMustTailCall()) + return false; + if (IntrinsicInst *II = dyn_cast(CI)) { if (II->getIntrinsicID() == Intrinsic::vastart) return false; } @@ -195,9 +219,9 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { // Start by computing a new prototype for the function, which is the same as // the old function, but doesn't have isVarArg set. - const FunctionType *FTy = Fn.getFunctionType(); - - std::vector Params(FTy->param_begin(), FTy->param_end()); + FunctionType *FTy = Fn.getFunctionType(); + + std::vector Params(FTy->param_begin(), FTy->param_end()); FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false); unsigned NumArgs = Params.size(); @@ -212,37 +236,42 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { // to pass in a smaller number of arguments into the new function. // std::vector Args; - while (!Fn.use_empty()) { - CallSite CS = CallSite::get(Fn.use_back()); + for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) { + CallSite CS(*I++); + if (!CS) + continue; Instruction *Call = CS.getInstruction(); // Pass all the same arguments. - Args.assign(CS.arg_begin(), CS.arg_begin()+NumArgs); + Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs); // Drop any attributes that were on the vararg arguments. - AttrListPtr PAL = CS.getAttributes(); - if (!PAL.isEmpty() && PAL.getSlot(PAL.getNumSlots() - 1).Index > NumArgs) { - SmallVector AttributesVec; - for (unsigned i = 0; PAL.getSlot(i).Index <= NumArgs; ++i) - AttributesVec.push_back(PAL.getSlot(i)); - if (Attributes FnAttrs = PAL.getFnAttributes()) - AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs)); - PAL = AttrListPtr::get(AttributesVec.begin(), AttributesVec.end()); + AttributeSet PAL = CS.getAttributes(); + if (!PAL.isEmpty() && PAL.getSlotIndex(PAL.getNumSlots() - 1) > NumArgs) { + SmallVector AttributesVec; + for (unsigned i = 0; PAL.getSlotIndex(i) <= NumArgs; ++i) + AttributesVec.push_back(PAL.getSlotAttributes(i)); + if (PAL.hasAttributes(AttributeSet::FunctionIndex)) + AttributesVec.push_back(AttributeSet::get(Fn.getContext(), + PAL.getFnAttributes())); + PAL = AttributeSet::get(Fn.getContext(), AttributesVec); } Instruction *New; if (InvokeInst *II = dyn_cast(Call)) { New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), - Args.begin(), Args.end(), "", Call); + Args, "", Call); cast(New)->setCallingConv(CS.getCallingConv()); cast(New)->setAttributes(PAL); } else { - New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); + New = CallInst::Create(NF, Args, "", Call); cast(New)->setCallingConv(CS.getCallingConv()); cast(New)->setAttributes(PAL); if (cast(Call)->isTailCall()) cast(New)->setTailCall(); } + New->setDebugLoc(Call->getDebugLoc()); + Args.clear(); if (!Call->use_empty()) @@ -260,8 +289,8 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { // function empty. NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList()); - // Loop over the argument list, transfering uses of the old arguments over to - // the new arguments, also transfering over the names as well. While we're at + // Loop over the argument list, transferring uses of the old arguments over to + // the new arguments, also transferring over the names as well. While we're at // it, remove the dead arguments from the DeadArguments list. // for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), @@ -271,23 +300,117 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { I2->takeName(I); } + // Patch the pointer to LLVM function in debug info descriptor. + auto DI = FunctionDIs.find(&Fn); + if (DI != FunctionDIs.end()) { + DISubprogram *SP = DI->second; + SP->replaceFunction(NF); + // Ensure the map is updated so it can be reused on non-varargs argument + // eliminations of the same function. + FunctionDIs.erase(DI); + FunctionDIs[NF] = SP; + } + + // Fix up any BlockAddresses that refer to the function. + Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType())); + // Delete the bitcast that we just created, so that NF does not + // appear to be address-taken. + NF->removeDeadConstantUsers(); // Finally, nuke the old function. Fn.eraseFromParent(); return true; } +/// RemoveDeadArgumentsFromCallers - Checks if the given function has any +/// arguments that are unused, and changes the caller parameters to be undefined +/// instead. +bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn) +{ + // We cannot change the arguments if this TU does not define the function or + // if the linker may choose a function body from another TU, even if the + // nominal linkage indicates that other copies of the function have the same + // semantics. In the below example, the dead load from %p may not have been + // eliminated from the linker-chosen copy of f, so replacing %p with undef + // in callers may introduce undefined behavior. + // + // define linkonce_odr void @f(i32* %p) { + // %v = load i32 %p + // ret void + // } + if (!Fn.isStrongDefinitionForLinker()) + return false; + + // Functions with local linkage should already have been handled, except the + // fragile (variadic) ones which we can improve here. + if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg()) + return false; + + if (Fn.use_empty()) + return false; + + SmallVector UnusedArgs; + for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(); + I != E; ++I) { + Argument *Arg = I; + + if (Arg->use_empty() && !Arg->hasByValOrInAllocaAttr()) + UnusedArgs.push_back(Arg->getArgNo()); + } + + if (UnusedArgs.empty()) + return false; + + bool Changed = false; + + for (Use &U : Fn.uses()) { + CallSite CS(U.getUser()); + if (!CS || !CS.isCallee(&U)) + continue; + + // Now go through all unused args and replace them with "undef". + for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) { + unsigned ArgNo = UnusedArgs[I]; + + Value *Arg = CS.getArgument(ArgNo); + CS.setArgument(ArgNo, UndefValue::get(Arg->getType())); + ++NumArgumentsReplacedWithUndef; + Changed = true; + } + } + + return Changed; +} + /// Convenience function that returns the number of return values. It returns 0 /// for void functions and 1 for functions not returning a struct. It returns /// the number of struct elements for functions returning a struct. static unsigned NumRetVals(const Function *F) { - if (F->getReturnType() == Type::getVoidTy(F->getContext())) + Type *RetTy = F->getReturnType(); + if (RetTy->isVoidTy()) return 0; - else if (const StructType *STy = dyn_cast(F->getReturnType())) + else if (StructType *STy = dyn_cast(RetTy)) return STy->getNumElements(); + else if (ArrayType *ATy = dyn_cast(RetTy)) + return ATy->getNumElements(); else return 1; } +/// 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 Idx (i.e. only top-level structure is considered). +static Type *getRetComponentType(const Function *F, unsigned Idx) { + Type *RetTy = F->getReturnType(); + assert(!RetTy->isVoidTy() && "void type has no subtype"); + + if (StructType *STy = dyn_cast(RetTy)) + return STy->getElementType(Idx); + else if (ArrayType *ATy = dyn_cast(RetTy)) + return ATy->getElementType(); + else + return RetTy; +} + /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not /// live, it adds Use to the MaybeLiveUses argument. Returns the determined /// liveness of Use. @@ -305,25 +428,40 @@ DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) { /// SurveyUse - This looks at a single use of an argument or return value /// and determines if it should be alive or not. Adds this use to MaybeLiveUses -/// if it causes the used value to become MaybeAlive. +/// if it causes the used value to become MaybeLive. /// /// RetValNum is the return value number to use when this use is used in a /// return instruction. This is used in the recursion, you should always leave /// it at 0. -DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, - unsigned RetValNum) { - Value *V = *U; - if (ReturnInst *RI = dyn_cast(V)) { +DAE::Liveness DAE::SurveyUse(const Use *U, + UseVector &MaybeLiveUses, unsigned RetValNum) { + const User *V = U->getUser(); + if (const ReturnInst *RI = dyn_cast(V)) { // The value is returned from a function. It's only live when the // function's return value is live. We use RetValNum here, for the case // that U is really a use of an insertvalue instruction that uses the - // orginal Use. - RetOrArg Use = CreateRet(RI->getParent()->getParent(), RetValNum); - // We might be live, depending on the liveness of Use. - return MarkIfNotLive(Use, MaybeLiveUses); + // original Use. + const Function *F = RI->getParent()->getParent(); + if (RetValNum != -1U) { + RetOrArg Use = CreateRet(F, RetValNum); + // We might be live, depending on the liveness of Use. + return MarkIfNotLive(Use, MaybeLiveUses); + } else { + DAE::Liveness Result = MaybeLive; + for (unsigned i = 0; i < NumRetVals(F); ++i) { + RetOrArg Use = CreateRet(F, i); + // We might be live, depending on the liveness of Use. If any + // sub-value is live, then the entire value is considered live. This + // is a conservative choice, and better tracking is possible. + DAE::Liveness SubResult = MarkIfNotLive(Use, MaybeLiveUses); + if (Result != Live) + Result = SubResult; + } + return Result; + } } - if (InsertValueInst *IV = dyn_cast(V)) { - if (U.getOperandNo() != InsertValueInst::getAggregateOperandIndex() + if (const InsertValueInst *IV = dyn_cast(V)) { + if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex() && IV->hasIndices()) // The use we are examining is inserted into an aggregate. Our liveness // depends on all uses of that aggregate, but if it is used as a return @@ -334,32 +472,31 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, // we don't change RetValNum, but do survey all our uses. Liveness Result = MaybeLive; - for (Value::use_iterator I = IV->use_begin(), - E = V->use_end(); I != E; ++I) { - Result = SurveyUse(I, MaybeLiveUses, RetValNum); + for (const Use &UU : IV->uses()) { + Result = SurveyUse(&UU, MaybeLiveUses, RetValNum); if (Result == Live) break; } return Result; } - CallSite CS = CallSite::get(V); - if (CS.getInstruction()) { - Function *F = CS.getCalledFunction(); + + if (auto CS = ImmutableCallSite(V)) { + const Function *F = CS.getCalledFunction(); if (F) { // Used in a direct call. - + // Find the argument number. We know for sure that this use is an // argument, since if it was the function argument this would be an // indirect call and the we know can't be looking at a value of the // label type (for the invoke instruction). - unsigned ArgNo = CS.getArgumentNo(U.getOperandNo()); + unsigned ArgNo = CS.getArgumentNo(U); if (ArgNo >= F->getFunctionType()->getNumParams()) // The value is passed in through a vararg! Must be live. return Live; - assert(CS.getArgument(ArgNo) - == CS.getInstruction()->getOperand(U.getOperandNo()) + assert(CS.getArgument(ArgNo) + == CS->getOperand(U->getOperandNo()) && "Argument is not where we expected it"); // Value passed to a normal call. It's only live when the corresponding @@ -378,13 +515,12 @@ DAE::Liveness DAE::SurveyUse(Value::use_iterator U, UseVector &MaybeLiveUses, /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If /// the result is Live, MaybeLiveUses might be modified but its content should /// be ignored (since it might not be complete). -DAE::Liveness DAE::SurveyUses(Value *V, UseVector &MaybeLiveUses) { +DAE::Liveness DAE::SurveyUses(const Value *V, UseVector &MaybeLiveUses) { // Assume it's dead (which will only hold if there are no uses at all..). Liveness Result = MaybeLive; // Check each use. - for (Value::use_iterator I = V->use_begin(), - E = V->use_end(); I != E; ++I) { - Result = SurveyUse(I, MaybeLiveUses); + for (const Use &U : V->uses()) { + Result = SurveyUse(&U, MaybeLiveUses); if (Result == Live) break; } @@ -399,7 +535,14 @@ DAE::Liveness DAE::SurveyUses(Value *V, UseVector &MaybeLiveUses) { // We consider arguments of non-internal functions to be intrinsically alive as // well as arguments to functions which have their "address taken". // -void DAE::SurveyFunction(Function &F) { +void DAE::SurveyFunction(const Function &F) { + // Functions with inalloca parameters are expecting args in a particular + // register and memory layout. + if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) { + MarkLive(F); + return; + } + unsigned RetCount = NumRetVals(&F); // Assume all return values are dead typedef SmallVector RetVals; @@ -411,8 +554,8 @@ void DAE::SurveyFunction(Function &F) { // MaybeLive. Initialized to a list of RetCount empty lists. RetUses MaybeLiveRetUses(RetCount); - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - if (ReturnInst *RI = dyn_cast(BB->getTerminator())) + for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + if (const ReturnInst *RI = dyn_cast(BB->getTerminator())) if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType() != F.getFunctionType()->getReturnType()) { // We don't support old style multiple return values. @@ -429,19 +572,18 @@ void DAE::SurveyFunction(Function &F) { // Keep track of the number of live retvals, so we can skip checks once all // of them turn out to be live. unsigned NumLiveRetVals = 0; - const Type *STy = dyn_cast(F.getReturnType()); // Loop all uses of the function. - for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { + for (const Use &U : F.uses()) { // If the function is PASSED IN as an argument, its address has been // taken. - CallSite CS = CallSite::get(*I); - if (!CS.getInstruction() || !CS.isCallee(I)) { + ImmutableCallSite CS(U.getUser()); + if (!CS || !CS.isCallee(&U)) { MarkLive(F); return; } // If this use is anything other than a call site, the function is alive. - Instruction *TheCall = CS.getInstruction(); + const Instruction *TheCall = CS.getInstruction(); if (!TheCall) { // Not a direct call site? MarkLive(F); return; @@ -451,35 +593,35 @@ void DAE::SurveyFunction(Function &F) { // Now, check how our return value(s) is/are used in this caller. Don't // bother checking return values if all of them are live already. - if (NumLiveRetVals != RetCount) { - if (STy) { - // Check all uses of the return value. - for (Value::use_iterator I = TheCall->use_begin(), - E = TheCall->use_end(); I != E; ++I) { - ExtractValueInst *Ext = dyn_cast(*I); - if (Ext && Ext->hasIndices()) { - // This use uses a part of our return value, survey the uses of - // that part and store the results for this index only. - unsigned Idx = *Ext->idx_begin(); - if (RetValLiveness[Idx] != Live) { - RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); - if (RetValLiveness[Idx] == Live) - NumLiveRetVals++; - } - } else { - // Used by something else than extractvalue. Mark all return - // values as live. - for (unsigned i = 0; i != RetCount; ++i ) - RetValLiveness[i] = Live; - NumLiveRetVals = RetCount; - break; - } + if (NumLiveRetVals == RetCount) + continue; + + // Check all uses of the return value. + for (const Use &U : TheCall->uses()) { + if (ExtractValueInst *Ext = dyn_cast(U.getUser())) { + // This use uses a part of our return value, survey the uses of + // that part and store the results for this index only. + unsigned Idx = *Ext->idx_begin(); + if (RetValLiveness[Idx] != Live) { + RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]); + if (RetValLiveness[Idx] == Live) + NumLiveRetVals++; } } else { - // Single return value - RetValLiveness[0] = SurveyUses(TheCall, MaybeLiveRetUses[0]); - if (RetValLiveness[0] == Live) + // Used by something else than extractvalue. Survey, but assume that the + // result applies to all sub-values. + UseVector MaybeLiveAggregateUses; + if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) { NumLiveRetVals = RetCount; + RetValLiveness.assign(RetCount, Live); + break; + } else { + for (unsigned i = 0; i != RetCount; ++i) { + if (RetValLiveness[i] != Live) + MaybeLiveRetUses[i].append(MaybeLiveAggregateUses.begin(), + MaybeLiveAggregateUses.end()); + } + } } } } @@ -493,11 +635,22 @@ void DAE::SurveyFunction(Function &F) { // Now, check all of our arguments. unsigned i = 0; UseVector MaybeLiveArgUses; - for (Function::arg_iterator AI = F.arg_begin(), + for (Function::const_arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI, ++i) { - // See what the effect of this use is (recording any uses that cause - // MaybeLive in MaybeLiveArgUses). - Liveness Result = SurveyUses(AI, MaybeLiveArgUses); + Liveness Result; + if (F.getFunctionType()->isVarArg()) { + // Variadic functions will already have a va_arg function expanded inside + // them, making them potentially very sensitive to ABI changes resulting + // from removing arguments entirely, so don't. For example AArch64 handles + // register and stack HFAs very differently, and this is reflected in the + // IR which has already been generated. + Result = Live; + } else { + // See what the effect of this use is (recording any uses that cause + // MaybeLive in MaybeLiveArgUses). + Result = SurveyUses(AI, MaybeLiveArgUses); + } + // Mark the result. MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses); // Clear the vector again for the next iteration. @@ -531,14 +684,14 @@ void DAE::MarkValue(const RetOrArg &RA, Liveness L, /// values (according to Uses) live as well. void DAE::MarkLive(const Function &F) { DEBUG(dbgs() << "DAE - Intrinsically live fn: " << F.getName() << "\n"); - // Mark the function as live. - LiveFunctions.insert(&F); - // Mark all arguments as live. - for (unsigned i = 0, e = F.arg_size(); i != e; ++i) - PropagateLiveness(CreateArg(&F, i)); - // Mark all return values as live. - for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i) - PropagateLiveness(CreateRet(&F, i)); + // Mark the function as live. + LiveFunctions.insert(&F); + // Mark all arguments as live. + for (unsigned i = 0, e = F.arg_size(); i != e; ++i) + PropagateLiveness(CreateArg(&F, i)); + // Mark all return values as live. + for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i) + PropagateLiveness(CreateRet(&F, i)); } /// MarkLive - Mark the given return value or argument as live. Additionally, @@ -583,62 +736,99 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // Start by computing a new prototype for the function, which is the same as // the old function, but has fewer arguments and a different return type. - const FunctionType *FTy = F->getFunctionType(); - std::vector Params; + FunctionType *FTy = F->getFunctionType(); + std::vector Params; + + // Keep track of if we have a live 'returned' argument + bool HasLiveReturnedArg = false; // Set up to build a new list of parameter attributes. - SmallVector AttributesVec; - const AttrListPtr &PAL = F->getAttributes(); + SmallVector AttributesVec; + const AttributeSet &PAL = F->getAttributes(); - // The existing function return attributes. - Attributes RAttrs = PAL.getRetAttributes(); - Attributes FnAttrs = PAL.getFnAttributes(); + // Remember which arguments are still alive. + SmallVector ArgAlive(FTy->getNumParams(), false); + // Construct the new parameter list from non-dead arguments. Also construct + // a new set of parameter attributes to correspond. Skip the first parameter + // attribute, since that belongs to the return value. + unsigned i = 0; + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); + I != E; ++I, ++i) { + RetOrArg Arg = CreateArg(F, i); + if (LiveValues.erase(Arg)) { + Params.push_back(I->getType()); + ArgAlive[i] = true; - // Find out the new return value. + // Get the original parameter attributes (skipping the first one, that is + // for the return value. + if (PAL.hasAttributes(i + 1)) { + AttrBuilder B(PAL, i + 1); + if (B.contains(Attribute::Returned)) + HasLiveReturnedArg = true; + AttributesVec. + push_back(AttributeSet::get(F->getContext(), Params.size(), B)); + } + } else { + ++NumArgumentsEliminated; + DEBUG(dbgs() << "DAE - Removing argument " << i << " (" << I->getName() + << ") from " << F->getName() << "\n"); + } + } - const Type *RetTy = FTy->getReturnType(); - const Type *NRetTy = NULL; + // Find out the new return value. + Type *RetTy = FTy->getReturnType(); + Type *NRetTy = nullptr; unsigned RetCount = NumRetVals(F); - + // -1 means unused, other numbers are the new index SmallVector NewRetIdxs(RetCount, -1); - std::vector RetTypes; - if (RetTy == Type::getVoidTy(F->getContext())) { - NRetTy = Type::getVoidTy(F->getContext()); + std::vector RetTypes; + + // If there is a function with a live 'returned' argument but a dead return + // value, then there are two possible actions: + // 1) Eliminate the return value and take off the 'returned' attribute on the + // argument. + // 2) Retain the 'returned' attribute and treat the return value (but not the + // entire function) as live so that it is not eliminated. + // + // It's not clear in the general case which option is more profitable because, + // even in the absence of explicit uses of the return value, code generation + // is free to use the 'returned' attribute to do things like eliding + // save/restores of registers across calls. Whether or not this happens is + // target and ABI-specific as well as depending on the amount of register + // pressure, so there's no good way for an IR-level pass to figure this out. + // + // Fortunately, the only places where 'returned' is currently generated by + // the FE are places where 'returned' is basically free and almost always a + // performance win, so the second option can just be used always for now. + // + // This should be revisited if 'returned' is ever applied more liberally. + if (RetTy->isVoidTy() || HasLiveReturnedArg) { + NRetTy = RetTy; } else { - const StructType *STy = dyn_cast(RetTy); - if (STy) - // Look at each of the original return values individually. - for (unsigned i = 0; i != RetCount; ++i) { - RetOrArg Ret = CreateRet(F, i); - if (LiveValues.erase(Ret)) { - RetTypes.push_back(STy->getElementType(i)); - NewRetIdxs[i] = RetTypes.size() - 1; - } else { - ++NumRetValsEliminated; - DEBUG(dbgs() << "DAE - Removing return value " << i << " from " - << F->getName() << "\n"); - } - } - else - // We used to return a single value. - if (LiveValues.erase(CreateRet(F, 0))) { - RetTypes.push_back(RetTy); - NewRetIdxs[0] = 0; + // Look at each of the original return values individually. + for (unsigned i = 0; i != RetCount; ++i) { + RetOrArg Ret = CreateRet(F, i); + if (LiveValues.erase(Ret)) { + RetTypes.push_back(getRetComponentType(F, i)); + NewRetIdxs[i] = RetTypes.size() - 1; } else { - DEBUG(dbgs() << "DAE - Removing return value from " << F->getName() - << "\n"); ++NumRetValsEliminated; + DEBUG(dbgs() << "DAE - Removing return value " << i << " from " + << F->getName() << "\n"); } - if (RetTypes.size() > 1) - // More than one return type? Return a struct with them. Also, if we used - // to return a struct and didn't change the number of return values, - // return a struct again. This prevents changing {something} into - // something and {} into void. - // Make the new struct packed if we used to return a packed struct - // already. - NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); - else if (RetTypes.size() == 1) + } + if (RetTypes.size() > 1) { + // More than one return type? Reduce it down to size. + if (StructType *STy = dyn_cast(RetTy)) { + // Make the new struct packed if we used to return a packed struct + // already. + NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked()); + } else { + assert(isa(RetTy) && "unexpected multi-value return"); + NRetTy = ArrayType::get(RetTypes[0], RetTypes.size()); + } + } else if (RetTypes.size() == 1) // One return type? Just a simple value then, but only if we didn't use to // return a struct with that simple value before. NRetTy = RetTypes.front(); @@ -649,64 +839,34 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { assert(NRetTy && "No new return type found?"); + // The existing function return attributes. + AttributeSet RAttrs = PAL.getRetAttributes(); + // Remove any incompatible attributes, but only if we removed all return // values. Otherwise, ensure that we don't have any conflicting attributes // here. Currently, this should not be possible, but special handling might be // required when new return value attributes are added. - if (NRetTy == Type::getVoidTy(F->getContext())) - RAttrs &= ~Attribute::typeIncompatible(NRetTy); + if (NRetTy->isVoidTy()) + RAttrs = RAttrs.removeAttributes(NRetTy->getContext(), + AttributeSet::ReturnIndex, + AttributeFuncs::typeIncompatible(NRetTy)); else - assert((RAttrs & Attribute::typeIncompatible(NRetTy)) == 0 - && "Return attributes no longer compatible?"); + assert(!AttrBuilder(RAttrs, AttributeSet::ReturnIndex). + overlaps(AttributeFuncs::typeIncompatible(NRetTy)) && + "Return attributes no longer compatible?"); - if (RAttrs) - AttributesVec.push_back(AttributeWithIndex::get(0, RAttrs)); + if (RAttrs.hasAttributes(AttributeSet::ReturnIndex)) + AttributesVec.push_back(AttributeSet::get(NRetTy->getContext(), RAttrs)); - // Remember which arguments are still alive. - SmallVector ArgAlive(FTy->getNumParams(), false); - // Construct the new parameter list from non-dead arguments. Also construct - // a new set of parameter attributes to correspond. Skip the first parameter - // attribute, since that belongs to the return value. - unsigned i = 0; - for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); - I != E; ++I, ++i) { - RetOrArg Arg = CreateArg(F, i); - if (LiveValues.erase(Arg)) { - Params.push_back(I->getType()); - ArgAlive[i] = true; - - // Get the original parameter attributes (skipping the first one, that is - // for the return value. - if (Attributes Attrs = PAL.getParamAttributes(i + 1)) - AttributesVec.push_back(AttributeWithIndex::get(Params.size(), Attrs)); - } else { - ++NumArgumentsEliminated; - DEBUG(dbgs() << "DAE - Removing argument " << i << " (" << I->getName() - << ") from " << F->getName() << "\n"); - } - } - - if (FnAttrs != Attribute::None) - AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs)); + if (PAL.hasAttributes(AttributeSet::FunctionIndex)) + AttributesVec.push_back(AttributeSet::get(F->getContext(), + PAL.getFnAttributes())); // Reconstruct the AttributesList based on the vector we constructed. - AttrListPtr NewPAL = AttrListPtr::get(AttributesVec.begin(), AttributesVec.end()); - - // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which - // have zero fixed arguments. - // - // Note that we apply this hack for a vararg fuction that does not have any - // arguments anymore, but did have them before (so don't bother fixing - // functions that were already broken wrt CWriter). - bool ExtraArgHack = false; - if (Params.empty() && FTy->isVarArg() && FTy->getNumParams() != 0) { - ExtraArgHack = true; - Params.push_back(Type::getInt32Ty(F->getContext())); - } + AttributeSet NewPAL = AttributeSet::get(F->getContext(), AttributesVec); // Create the new function type based on the recomputed parameters. - FunctionType *NFTy = FunctionType::get(NRetTy, Params, - FTy->isVarArg()); + FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); // No change? if (NFTy == FTy) @@ -726,19 +886,21 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // std::vector Args; while (!F->use_empty()) { - CallSite CS = CallSite::get(F->use_back()); + CallSite CS(F->user_back()); Instruction *Call = CS.getInstruction(); AttributesVec.clear(); - const AttrListPtr &CallPAL = CS.getAttributes(); + const AttributeSet &CallPAL = CS.getAttributes(); // The call return attributes. - Attributes RAttrs = CallPAL.getRetAttributes(); - Attributes FnAttrs = CallPAL.getFnAttributes(); + AttributeSet RAttrs = CallPAL.getRetAttributes(); + // Adjust in case the function was changed to return void. - RAttrs &= ~Attribute::typeIncompatible(NF->getReturnType()); - if (RAttrs) - AttributesVec.push_back(AttributeWithIndex::get(0, RAttrs)); + RAttrs = RAttrs.removeAttributes(NRetTy->getContext(), + AttributeSet::ReturnIndex, + AttributeFuncs::typeIncompatible(NF->getReturnType())); + if (RAttrs.hasAttributes(AttributeSet::ReturnIndex)) + AttributesVec.push_back(AttributeSet::get(NF->getContext(), RAttrs)); // Declare these outside of the loops, so we can reuse them for the second // loop, which loops the varargs. @@ -750,40 +912,52 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { if (ArgAlive[i]) { Args.push_back(*I); // Get original parameter attributes, but skip return attributes. - if (Attributes Attrs = CallPAL.getParamAttributes(i + 1)) - AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); + if (CallPAL.hasAttributes(i + 1)) { + AttrBuilder B(CallPAL, i + 1); + // If the return type has changed, then get rid of 'returned' on the + // call site. The alternative is to make all 'returned' attributes on + // call sites keep the return value alive just like 'returned' + // attributes on function declaration but it's less clearly a win + // and this is not an expected case anyway + if (NRetTy != RetTy && B.contains(Attribute::Returned)) + B.removeAttribute(Attribute::Returned); + AttributesVec. + push_back(AttributeSet::get(F->getContext(), Args.size(), B)); + } } - if (ExtraArgHack) - Args.push_back(UndefValue::get(Type::getInt32Ty(F->getContext()))); - // Push any varargs arguments on the list. Don't forget their attributes. for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) { Args.push_back(*I); - if (Attributes Attrs = CallPAL.getParamAttributes(i + 1)) - AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); + if (CallPAL.hasAttributes(i + 1)) { + AttrBuilder B(CallPAL, i + 1); + AttributesVec. + push_back(AttributeSet::get(F->getContext(), Args.size(), B)); + } } - if (FnAttrs != Attribute::None) - AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs)); + if (CallPAL.hasAttributes(AttributeSet::FunctionIndex)) + AttributesVec.push_back(AttributeSet::get(Call->getContext(), + CallPAL.getFnAttributes())); // Reconstruct the AttributesList based on the vector we constructed. - AttrListPtr NewCallPAL = AttrListPtr::get(AttributesVec.begin(), - AttributesVec.end()); + AttributeSet NewCallPAL = AttributeSet::get(F->getContext(), AttributesVec); Instruction *New; if (InvokeInst *II = dyn_cast(Call)) { New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), - Args.begin(), Args.end(), "", Call); + Args, "", Call); cast(New)->setCallingConv(CS.getCallingConv()); cast(New)->setAttributes(NewCallPAL); } else { - New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); + New = CallInst::Create(NF, Args, "", Call); cast(New)->setCallingConv(CS.getCallingConv()); cast(New)->setAttributes(NewCallPAL); if (cast(Call)->isTailCall()) cast(New)->setTailCall(); } + New->setDebugLoc(Call->getDebugLoc()); + Args.clear(); if (!Call->use_empty()) { @@ -791,24 +965,25 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // Return type not changed? Just replace users then. Call->replaceAllUsesWith(New); New->takeName(Call); - } else if (New->getType() == Type::getVoidTy(F->getContext())) { + } else if (New->getType()->isVoidTy()) { // Our return value has uses, but they will get removed later on. // Replace by null for now. - Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); + if (!Call->getType()->isX86_MMXTy()) + Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); } else { - assert(RetTy->isStructTy() && + assert((RetTy->isStructTy() || RetTy->isArrayTy()) && "Return type changed, but not into a void. The old return type" - " must have been a struct!"); + " must have been a struct or an array!"); Instruction *InsertPt = Call; if (InvokeInst *II = dyn_cast(Call)) { BasicBlock::iterator IP = II->getNormalDest()->begin(); while (isa(IP)) ++IP; InsertPt = IP; } - - // We used to return a struct. Instead of doing smart stuff with all the - // uses of this struct, we will just rebuild it using - // extract/insertvalue chaining and let instcombine clean that up. + + // We used to return a struct or array. Instead of doing smart stuff + // with all the uses, we will just rebuild it using extract/insertvalue + // chaining and let instcombine clean that up. // // Start out building up our return value from undef Value *RetVal = UndefValue::get(RetTy); @@ -843,8 +1018,8 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // function empty. NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); - // Loop over the argument list, transfering uses of the old arguments over to - // the new arguments, also transfering over the names as well. + // Loop over the argument list, transferring uses of the old arguments over to + // the new arguments, also transferring over the names as well. i = 0; for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), I2 = NF->arg_begin(); I != E; ++I, ++i) @@ -857,7 +1032,8 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { } else { // If this argument is dead, replace any uses of it with null constants // (these are guaranteed to become unused later on). - I->replaceAllUsesWith(Constant::getNullValue(I->getType())); + if (!I->getType()->isX86_MMXTy()) + I->replaceAllUsesWith(Constant::getNullValue(I->getType())); } // If we change the return value of the function we must rewrite any return @@ -867,11 +1043,11 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { if (ReturnInst *RI = dyn_cast(BB->getTerminator())) { Value *RetVal; - if (NFTy->getReturnType() == Type::getVoidTy(F->getContext())) { - RetVal = 0; + if (NFTy->getReturnType()->isVoidTy()) { + RetVal = nullptr; } else { - assert (RetTy->isStructTy()); - // The original return value was a struct, insert + assert(RetTy->isStructTy() || RetTy->isArrayTy()); + // The original return value was a struct or array, insert // extractvalue/insertvalue chains to extract only the values we need // to return and insert them into our new result. // This does generate messy code, but we'll let it to instcombine to @@ -902,6 +1078,11 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { BB->getInstList().erase(RI); } + // Patch the pointer to LLVM function in debug info descriptor. + auto DI = FunctionDIs.find(F); + if (DI != FunctionDIs.end()) + DI->second->replaceFunction(NF); + // Now that the old function is dead, delete it. F->eraseFromParent(); @@ -911,6 +1092,9 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { bool DAE::runOnModule(Module &M) { bool Changed = false; + // Collect debug info descriptors for functions. + FunctionDIs = makeSubprogramMap(M); + // First pass: Do a simple check to see if any functions can have their "..." // removed. We can do this if they never call va_start. This loop cannot be // fused with the next loop, because deleting a function invalidates @@ -927,16 +1111,22 @@ bool DAE::runOnModule(Module &M) { // determine that dead arguments passed into recursive functions are dead). // DEBUG(dbgs() << "DAE - Determining liveness\n"); - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - SurveyFunction(*I); - + for (auto &F : M) + SurveyFunction(F); + // Now, remove all dead arguments and return values from each function in - // turn + // turn. for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { - // Increment now, because the function will probably get removed (ie + // Increment now, because the function will probably get removed (ie. // replaced by a new one). Function *F = I++; Changed |= RemoveDeadStuffFromFunction(F); } + + // Finally, look for any unused parameters in functions with non-local + // linkage and replace the passed in parameters with undef. + for (auto &F : M) + Changed |= RemoveDeadArgumentsFromCallers(F); + return Changed; }