X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FDeadArgumentElimination.cpp;h=088269d816d52040ad3d76ac7615b06b5945320c;hb=41e2397b720bc5d917ef614a7a6c257e8a3c8e42;hp=f8aaf35d82f6d103d0500d0096b6355383567b09;hpb=7bc439a4b6c2d99707ebabf8f9b1c13041faa6a6;p=oota-llvm.git diff --git a/lib/Transforms/IPO/DeadArgumentElimination.cpp b/lib/Transforms/IPO/DeadArgumentElimination.cpp index f8aaf35d82f..088269d816d 100644 --- a/lib/Transforms/IPO/DeadArgumentElimination.cpp +++ b/lib/Transforms/IPO/DeadArgumentElimination.cpp @@ -1,126 +1,424 @@ //===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===// // +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// // This pass deletes dead arguments from internal functions. Dead argument // elimination removes arguments which are directly dead, as well as arguments -// only passed into function calls as dead arguments of other functions. +// only passed into function calls as dead arguments of other functions. This +// pass also deletes dead arguments in a similar way. // // This pass is often useful as a cleanup pass to run after aggressive // interprocedural passes, which add possibly-dead arguments. // //===----------------------------------------------------------------------===// +#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/Module.h" #include "llvm/Pass.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Constant.h" -#include "llvm/iOther.h" -#include "llvm/iTerminators.h" +#include "llvm/ParamAttrsList.h" #include "llvm/Support/CallSite.h" -#include "Support/Debug.h" -#include "Support/Statistic.h" -#include "Support/iterator" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/Compiler.h" #include +using namespace llvm; -namespace { - Statistic<> NumArgumentsEliminated("deadargelim", "Number of args removed"); +STATISTIC(NumArgumentsEliminated, "Number of unread args removed"); +STATISTIC(NumRetValsEliminated , "Number of unused return values removed"); - struct DAE : public Pass { - DAE(bool DFEF = false) : DeleteFromExternalFunctions(DFEF) {} - bool run(Module &M); +namespace { + /// DAE - The dead argument elimination pass. + /// + class VISIBILITY_HIDDEN DAE : public ModulePass { + /// Liveness enum - During our initial pass over the program, we determine + /// that things are either definately alive, definately dead, or in need of + /// interprocedural analysis (MaybeLive). + /// + enum Liveness { Live, MaybeLive, Dead }; + + /// LiveArguments, MaybeLiveArguments, DeadArguments - These sets contain + /// all of the arguments in the program. The Dead set contains arguments + /// which are completely dead (never used in the function). The MaybeLive + /// set contains arguments which are only passed into other function calls, + /// thus may be live and may be dead. The Live set contains arguments which + /// are known to be alive. + /// + std::set DeadArguments, MaybeLiveArguments, LiveArguments; + + /// DeadRetVal, MaybeLiveRetVal, LifeRetVal - These sets contain all of the + /// functions in the program. The Dead set contains functions whose return + /// value is known to be dead. The MaybeLive set contains functions whose + /// return values are only used by return instructions, and the Live set + /// contains functions whose return values are used, functions that are + /// external, and functions that already return void. + /// + std::set DeadRetVal, MaybeLiveRetVal, LiveRetVal; + + /// InstructionsToInspect - As we mark arguments and return values + /// MaybeLive, we keep track of which instructions could make the values + /// live here. Once the entire program has had the return value and + /// arguments analyzed, this set is scanned to promote the MaybeLive objects + /// to be Live if they really are used. + std::vector InstructionsToInspect; + + /// CallSites - Keep track of the call sites of functions that have + /// MaybeLive arguments or return values. + std::multimap CallSites; + + public: + static char ID; // Pass identification, replacement for typeid + DAE() : ModulePass((intptr_t)&ID) {} + bool runOnModule(Module &M); + + virtual bool ShouldHackArguments() const { return false; } private: - bool DeleteFromExternalFunctions; - bool FunctionArgumentsIntrinsicallyAlive(const Function &F); - void RemoveDeadArgumentsFromFunction(Function *F, - std::set &DeadArguments); + Liveness getArgumentLiveness(const Argument &A); + bool isMaybeLiveArgumentNowLive(Argument *Arg); + + bool DeleteDeadVarargs(Function &Fn); + void SurveyFunction(Function &Fn); + + void MarkArgumentLive(Argument *Arg); + void MarkRetValLive(Function *F); + void MarkReturnInstArgumentLive(ReturnInst *RI); + + void RemoveDeadArgumentsFromFunction(Function *F); }; - RegisterOpt X("deadargelim", "Dead Argument Elimination"); + char DAE::ID = 0; + RegisterPass X("deadargelim", "Dead Argument Elimination"); + + /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but + /// deletes arguments to functions which are external. This is only for use + /// by bugpoint. + struct DAH : public DAE { + static char ID; + virtual bool ShouldHackArguments() const { return true; } + }; + char DAH::ID = 0; + RegisterPass Y("deadarghaX0r", + "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)"); } /// createDeadArgEliminationPass - This pass removes arguments from functions -/// which are not used by the body of the function. If -/// DeleteFromExternalFunctions is true, the pass will modify functions that -/// have external linkage, which is not usually safe (this is used by bugpoint -/// to reduce testcases). +/// which are not used by the body of the function. /// -Pass *createDeadArgEliminationPass(bool DeleteFromExternalFunctions) { - return new DAE(DeleteFromExternalFunctions); -} +ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } +ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } + +/// DeleteDeadVarargs - If this is an function that takes a ... list, and if +/// llvm.vastart is never called, the varargs list is dead for the function. +bool DAE::DeleteDeadVarargs(Function &Fn) { + assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!"); + if (Fn.isDeclaration() || !Fn.hasInternalLinkage()) return false; + + // Ensure that the function is only directly called. + for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end(); I != E; ++I) { + // If this use is anything other than a call site, give up. + CallSite CS = CallSite::get(*I); + Instruction *TheCall = CS.getInstruction(); + if (!TheCall) return false; // Not a direct call site? + // The addr of this function is passed to the call. + if (I.getOperandNo() != 0) return false; + } -// FunctionArgumentsIntrinsicallyAlive - Return true if the arguments of the -// specified function are intrinsically alive. -// -// We consider arguments of non-internal functions to be intrinsically alive as -// well as arguments to functions which have their "address taken". -// -bool DAE::FunctionArgumentsIntrinsicallyAlive(const Function &F) { - if (!F.hasInternalLinkage() && !DeleteFromExternalFunctions) return true; + // Okay, we know we can transform this function if safe. Scan its body + // looking for 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)) { + if (II->getIntrinsicID() == Intrinsic::vastart) + return false; + } + } + } - for (Value::use_const_iterator I = F.use_begin(), E = F.use_end(); I!=E; ++I){ - // If this use is anything other than a call site, the function is alive. - CallSite CS = CallSite::get(const_cast(*I)); - if (!CS.getInstruction()) return true; // Not a valid call site? + // If we get here, there are no calls to llvm.vastart in the function body, + // remove the "..." and adjust all the calls. + + // Start by computing a new prototype for the function, which is the same as + // the old function, but has fewer arguments. + const 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(); + + // Create the new function body and insert it into the module... + Function *NF = new Function(NFTy, Fn.getLinkage()); + NF->setCallingConv(Fn.getCallingConv()); + NF->setParamAttrs(Fn.getParamAttrs()); + if (Fn.hasCollector()) + NF->setCollector(Fn.getCollector()); + Fn.getParent()->getFunctionList().insert(&Fn, NF); + NF->takeName(&Fn); + + // Loop over all of the callers of the function, transforming the call sites + // 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()); + Instruction *Call = CS.getInstruction(); + + // Pass all the same arguments. + Args.assign(CS.arg_begin(), CS.arg_begin()+NumArgs); + + // Drop any attributes that were on the vararg arguments. + const ParamAttrsList *PAL = CS.getParamAttrs(); + if (PAL && PAL->getParamIndex(PAL->size() - 1) > NumArgs) { + ParamAttrsVector ParamAttrsVec; + for (unsigned i = 0; PAL->getParamIndex(i) <= NumArgs; ++i) { + ParamAttrsWithIndex PAWI; + PAWI = ParamAttrsWithIndex::get(PAL->getParamIndex(i), + PAL->getParamAttrsAtIndex(i)); + ParamAttrsVec.push_back(PAWI); + } + PAL = ParamAttrsList::get(ParamAttrsVec); + } + + Instruction *New; + if (InvokeInst *II = dyn_cast(Call)) { + New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), + Args.begin(), Args.end(), "", Call); + cast(New)->setCallingConv(CS.getCallingConv()); + cast(New)->setParamAttrs(PAL); + } else { + New = new CallInst(NF, Args.begin(), Args.end(), "", Call); + cast(New)->setCallingConv(CS.getCallingConv()); + cast(New)->setParamAttrs(PAL); + if (cast(Call)->isTailCall()) + cast(New)->setTailCall(); + } + Args.clear(); + + if (!Call->use_empty()) + Call->replaceAllUsesWith(New); - // If the function is PASSED IN as an argument, its address has been taken - for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); AI != E; - ++AI) - if (AI->get() == &F) return true; + New->takeName(Call); + + // Finally, remove the old call from the program, reducing the use-count of + // F. + Call->eraseFromParent(); } - return false; + + // Since we have now created the new function, splice the body of the old + // function right into the new function, leaving the old rotting hulk of the + // 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 + // it, remove the dead arguments from the DeadArguments list. + // + for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(), + I2 = NF->arg_begin(); I != E; ++I, ++I2) { + // Move the name and users over to the new version. + I->replaceAllUsesWith(I2); + I2->takeName(I); + } + + // Finally, nuke the old function. + Fn.eraseFromParent(); + return true; } -namespace { - enum ArgumentLiveness { Alive, MaybeLive, Dead }; + +static inline bool CallPassesValueThoughVararg(Instruction *Call, + const Value *Arg) { + CallSite CS = CallSite::get(Call); + const Type *CalledValueTy = CS.getCalledValue()->getType(); + const Type *FTy = cast(CalledValueTy)->getElementType(); + unsigned NumFixedArgs = cast(FTy)->getNumParams(); + for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs; + AI != CS.arg_end(); ++AI) + if (AI->get() == Arg) + return true; + return false; } -// getArgumentLiveness - Inspect an argument, determining if is known Alive +// getArgumentLiveness - Inspect an argument, determining if is known Live // (used in a computation), MaybeLive (only passed as an argument to a call), or // Dead (not used). -static ArgumentLiveness getArgumentLiveness(const Argument &A) { - if (A.use_empty()) return Dead; // First check, directly dead? +DAE::Liveness DAE::getArgumentLiveness(const Argument &A) { + const Function *F = A.getParent(); + + // If this is the return value of a struct function, it's not really dead. + if (F->hasStructRetAttr() && &*(F->arg_begin()) == &A) + return Live; + + if (A.use_empty()) // First check, directly dead? + return Dead; // Scan through all of the uses, looking for non-argument passing uses. for (Value::use_const_iterator I = A.use_begin(), E = A.use_end(); I!=E;++I) { + // Return instructions do not immediately effect liveness. + if (isa(*I)) + continue; + CallSite CS = CallSite::get(const_cast(*I)); if (!CS.getInstruction()) { // If its used by something that is not a call or invoke, it's alive! - return Alive; + return Live; } // If it's an indirect call, mark it alive... Function *Callee = CS.getCalledFunction(); - if (!Callee) return Alive; + if (!Callee) return Live; // Check to see if it's passed through a va_arg area: if so, we cannot // remove it. - unsigned NumFixedArgs = Callee->getFunctionType()->getNumParams(); - for (CallSite::arg_iterator AI = CS.arg_begin()+NumFixedArgs; - AI != CS.arg_end(); ++AI) - if (AI->get() == &A) // If passed through va_arg area, we cannot remove it - return Alive; + if (CallPassesValueThoughVararg(CS.getInstruction(), &A)) + return Live; // If passed through va_arg area, we cannot remove it } return MaybeLive; // It must be used, but only as argument to a function } -// isMaybeLiveArgumentNowAlive - Check to see if Arg is alive. At this point, -// we know that the only uses of Arg are to be passed in as an argument to a -// function call. Check to see if the formal argument passed in is in the -// LiveArguments set. If so, return true. + +// SurveyFunction - This performs the initial survey of the specified function, +// checking out whether or not it uses any of its incoming arguments or whether +// any callers use the return value. This fills in the +// (Dead|MaybeLive|Live)(Arguments|RetVal) sets. +// +// 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) { + bool FunctionIntrinsicallyLive = false; + Liveness RetValLiveness = F.getReturnType() == Type::VoidTy ? Live : Dead; + + if (!F.hasInternalLinkage() && + (!ShouldHackArguments() || F.isIntrinsic())) + FunctionIntrinsicallyLive = true; + else + for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { + // If this use is anything other than a call site, the function is alive. + CallSite CS = CallSite::get(*I); + Instruction *TheCall = CS.getInstruction(); + if (!TheCall) { // Not a direct call site? + FunctionIntrinsicallyLive = true; + break; + } + + // Check to see if the return value is used... + if (RetValLiveness != Live) + for (Value::use_iterator I = TheCall->use_begin(), + E = TheCall->use_end(); I != E; ++I) + if (isa(cast(*I))) { + RetValLiveness = MaybeLive; + } else if (isa(cast(*I)) || + isa(cast(*I))) { + if (CallPassesValueThoughVararg(cast(*I), TheCall) || + !CallSite::get(cast(*I)).getCalledFunction()) { + RetValLiveness = Live; + break; + } else { + RetValLiveness = MaybeLive; + } + } else { + RetValLiveness = Live; + break; + } + + // If the function is PASSED IN as an argument, its address has been taken + for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); + AI != E; ++AI) + if (AI->get() == &F) { + FunctionIntrinsicallyLive = true; + break; + } + if (FunctionIntrinsicallyLive) break; + } + + if (FunctionIntrinsicallyLive) { + DOUT << " Intrinsically live fn: " << F.getName() << "\n"; + for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); + AI != E; ++AI) + LiveArguments.insert(AI); + LiveRetVal.insert(&F); + return; + } + + switch (RetValLiveness) { + case Live: LiveRetVal.insert(&F); break; + case MaybeLive: MaybeLiveRetVal.insert(&F); break; + case Dead: DeadRetVal.insert(&F); break; + } + + DOUT << " Inspecting args for fn: " << F.getName() << "\n"; + + // If it is not intrinsically alive, we know that all users of the + // function are call sites. Mark all of the arguments live which are + // directly used, and keep track of all of the call sites of this function + // if there are any arguments we assume that are dead. + // + bool AnyMaybeLiveArgs = false; + for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); + AI != E; ++AI) + switch (getArgumentLiveness(*AI)) { + case Live: + DOUT << " Arg live by use: " << AI->getName() << "\n"; + LiveArguments.insert(AI); + break; + case Dead: + DOUT << " Arg definitely dead: " << AI->getName() <<"\n"; + DeadArguments.insert(AI); + break; + case MaybeLive: + DOUT << " Arg only passed to calls: " << AI->getName() << "\n"; + AnyMaybeLiveArgs = true; + MaybeLiveArguments.insert(AI); + break; + } + + // If there are any "MaybeLive" arguments, we need to check callees of + // this function when/if they become alive. Record which functions are + // callees... + if (AnyMaybeLiveArgs || RetValLiveness == MaybeLive) + for (Value::use_iterator I = F.use_begin(), E = F.use_end(); + I != E; ++I) { + if (AnyMaybeLiveArgs) + CallSites.insert(std::make_pair(&F, CallSite::get(*I))); + + if (RetValLiveness == MaybeLive) + for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); + UI != E; ++UI) + InstructionsToInspect.push_back(cast(*UI)); + } +} + +// isMaybeLiveArgumentNowLive - Check to see if Arg is alive. At this point, we +// know that the only uses of Arg are to be passed in as an argument to a +// function call or return. Check to see if the formal argument passed in is in +// the LiveArguments set. If so, return true. // -static bool isMaybeLiveArgumentNowAlive(Argument *Arg, - const std::set &LiveArguments) { +bool DAE::isMaybeLiveArgumentNowLive(Argument *Arg) { for (Value::use_iterator I = Arg->use_begin(), E = Arg->use_end(); I!=E; ++I){ + if (isa(*I)) { + if (LiveRetVal.count(Arg->getParent())) return true; + continue; + } + CallSite CS = CallSite::get(*I); // We know that this can only be used for direct calls... - Function *Callee = cast(CS.getCalledValue()); + Function *Callee = CS.getCalledFunction(); // Loop over all of the arguments (because Arg may be passed into the call // multiple times) and check to see if any are now alive... CallSite::arg_iterator CSAI = CS.arg_begin(); - for (Function::aiterator AI = Callee->abegin(), E = Callee->aend(); + for (Function::arg_iterator AI = Callee->arg_begin(), E = Callee->arg_end(); AI != E; ++AI, ++CSAI) // If this is the argument we are looking for, check to see if it's alive if (*CSAI == Arg && LiveArguments.count(AI)) @@ -129,34 +427,73 @@ static bool isMaybeLiveArgumentNowAlive(Argument *Arg, return false; } -// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive. -// Mark it live in the specified sets and recursively mark arguments in callers -// live that are needed to pass in a value. -// -static void MarkArgumentLive(Argument *Arg, - std::set &MaybeLiveArguments, - std::set &LiveArguments, - const std::multimap &CallSites) { - DEBUG(std::cerr << " MaybeLive argument now live: " << Arg->getName()<<"\n"); - assert(MaybeLiveArguments.count(Arg) && !LiveArguments.count(Arg) && - "Arg not MaybeLive?"); - MaybeLiveArguments.erase(Arg); +/// MarkArgumentLive - The MaybeLive argument 'Arg' is now known to be alive. +/// Mark it live in the specified sets and recursively mark arguments in callers +/// live that are needed to pass in a value. +/// +void DAE::MarkArgumentLive(Argument *Arg) { + std::set::iterator It = MaybeLiveArguments.lower_bound(Arg); + if (It == MaybeLiveArguments.end() || *It != Arg) return; + + DOUT << " MaybeLive argument now live: " << Arg->getName() <<"\n"; + MaybeLiveArguments.erase(It); LiveArguments.insert(Arg); - + // Loop over all of the call sites of the function, making any arguments // passed in to provide a value for this argument live as necessary. // Function *Fn = Arg->getParent(); - unsigned ArgNo = std::distance(Fn->abegin(), Function::aiterator(Arg)); + unsigned ArgNo = std::distance(Fn->arg_begin(), Function::arg_iterator(Arg)); - std::multimap::const_iterator I = - CallSites.lower_bound(Fn); + std::multimap::iterator I = CallSites.lower_bound(Fn); for (; I != CallSites.end() && I->first == Fn; ++I) { - const CallSite &CS = I->second; - if (Argument *ActualArg = dyn_cast(*(CS.arg_begin()+ArgNo))) - if (MaybeLiveArguments.count(ActualArg)) - MarkArgumentLive(ActualArg, MaybeLiveArguments, LiveArguments, - CallSites); + CallSite CS = I->second; + Value *ArgVal = *(CS.arg_begin()+ArgNo); + if (Argument *ActualArg = dyn_cast(ArgVal)) { + MarkArgumentLive(ActualArg); + } else { + // If the value passed in at this call site is a return value computed by + // some other call site, make sure to mark the return value at the other + // call site as being needed. + CallSite ArgCS = CallSite::get(ArgVal); + if (ArgCS.getInstruction()) + if (Function *Fn = ArgCS.getCalledFunction()) + MarkRetValLive(Fn); + } + } +} + +/// MarkArgumentLive - The MaybeLive return value for the specified function is +/// now known to be alive. Propagate this fact to the return instructions which +/// produce it. +void DAE::MarkRetValLive(Function *F) { + assert(F && "Shame shame, we can't have null pointers here!"); + + // Check to see if we already knew it was live + std::set::iterator I = MaybeLiveRetVal.lower_bound(F); + if (I == MaybeLiveRetVal.end() || *I != F) return; // It's already alive! + + DOUT << " MaybeLive retval now live: " << F->getName() << "\n"; + + MaybeLiveRetVal.erase(I); + LiveRetVal.insert(F); // It is now known to be live! + + // Loop over all of the functions, noticing that the return value is now live. + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) + if (ReturnInst *RI = dyn_cast(BB->getTerminator())) + MarkReturnInstArgumentLive(RI); +} + +void DAE::MarkReturnInstArgumentLive(ReturnInst *RI) { + Value *Op = RI->getOperand(0); + if (Argument *A = dyn_cast(Op)) { + MarkArgumentLive(A); + } else if (CallInst *CI = dyn_cast(Op)) { + if (Function *F = CI->getCalledFunction()) + MarkRetValLive(F); + } else if (InvokeInst *II = dyn_cast(Op)) { + if (Function *F = II->getCalledFunction()) + MarkRetValLive(F); } } @@ -164,40 +501,139 @@ static void MarkArgumentLive(Argument *Arg, // specified by the DeadArguments list. Transform the function and all of the // callees of the function to not have these arguments. // -void DAE::RemoveDeadArgumentsFromFunction(Function *F, - std::set &DeadArguments){ +void DAE::RemoveDeadArgumentsFromFunction(Function *F) { // Start by computing a new prototype for the function, which is the same as // the old function, but has fewer arguments. const FunctionType *FTy = F->getFunctionType(); std::vector Params; - for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) - if (!DeadArguments.count(I)) + // Set up to build a new list of parameter attributes + ParamAttrsVector ParamAttrsVec; + const ParamAttrsList *PAL = F->getParamAttrs(); + + // The existing function return attributes. + ParameterAttributes RAttrs = PAL ? PAL->getParamAttrs(0) : ParamAttr::None; + + // Make the function return void if the return value is dead. + const Type *RetTy = FTy->getReturnType(); + if (DeadRetVal.count(F)) { + RetTy = Type::VoidTy; + RAttrs &= ~ParamAttr::typeIncompatible(RetTy); + DeadRetVal.erase(F); + } + + if (RAttrs) + ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); + + // Construct the new parameter list from non-dead arguments. Also construct + // a new set of parameter attributes to correspond. + unsigned index = 1; + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; + ++I, ++index) + if (!DeadArguments.count(I)) { Params.push_back(I->getType()); + ParameterAttributes Attrs = PAL ? PAL->getParamAttrs(index) : + ParamAttr::None; + if (Attrs) + ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Params.size(), Attrs)); + } + + // Reconstruct the ParamAttrsList based on the vector we constructed. + PAL = ParamAttrsList::get(ParamAttrsVec); + + // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which + // have zero fixed arguments. + // + bool ExtraArgHack = false; + if (Params.empty() && FTy->isVarArg()) { + ExtraArgHack = true; + Params.push_back(Type::Int32Ty); + } + + // Create the new function type based on the recomputed parameters. + FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); - FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, - FTy->isVarArg()); - // Create the new function body and insert it into the module... - Function *NF = new Function(NFTy, F->getLinkage(), F->getName()); + Function *NF = new Function(NFTy, F->getLinkage()); + NF->setCallingConv(F->getCallingConv()); + NF->setParamAttrs(PAL); + if (F->hasCollector()) + NF->setCollector(F->getCollector()); F->getParent()->getFunctionList().insert(F, NF); + NF->takeName(F); // Loop over all of the callers of the function, transforming the call sites // to pass in a smaller number of arguments into the new function. // + std::vector Args; while (!F->use_empty()) { CallSite CS = CallSite::get(F->use_back()); Instruction *Call = CS.getInstruction(); - CS.setCalledFunction(NF); // Reduce the uses count of F - + ParamAttrsVec.clear(); + PAL = CS.getParamAttrs(); + + // The call return attributes. + ParameterAttributes RAttrs = PAL ? PAL->getParamAttrs(0) : ParamAttr::None; + // Adjust in case the function was changed to return void. + RAttrs &= ~ParamAttr::typeIncompatible(NF->getReturnType()); + if (RAttrs) + ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, RAttrs)); + // Loop over the operands, deleting dead ones... CallSite::arg_iterator AI = CS.arg_begin(); - for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) - if (DeadArguments.count(I)) { // Remove operands for dead arguments - AI = Call->op_erase(AI); - } else { - ++AI; // Leave live operands alone... + index = 1; + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); + I != E; ++I, ++AI, ++index) + if (!DeadArguments.count(I)) { // Remove operands for dead arguments + Args.push_back(*AI); + ParameterAttributes Attrs = PAL ? PAL->getParamAttrs(index) : + ParamAttr::None; + if (Attrs) + ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); } + + if (ExtraArgHack) + Args.push_back(UndefValue::get(Type::Int32Ty)); + + // Push any varargs arguments on the list. Don't forget their attributes. + for (; AI != CS.arg_end(); ++AI) { + Args.push_back(*AI); + ParameterAttributes Attrs = PAL ? PAL->getParamAttrs(index++) : + ParamAttr::None; + if (Attrs) + ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); + } + + // Reconstruct the ParamAttrsList based on the vector we constructed. + PAL = ParamAttrsList::get(ParamAttrsVec); + + Instruction *New; + if (InvokeInst *II = dyn_cast(Call)) { + New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), + Args.begin(), Args.end(), "", Call); + cast(New)->setCallingConv(CS.getCallingConv()); + cast(New)->setParamAttrs(PAL); + } else { + New = new CallInst(NF, Args.begin(), Args.end(), "", Call); + cast(New)->setCallingConv(CS.getCallingConv()); + cast(New)->setParamAttrs(PAL); + if (cast(Call)->isTailCall()) + cast(New)->setTailCall(); + } + Args.clear(); + + if (!Call->use_empty()) { + if (New->getType() == Type::VoidTy) + Call->replaceAllUsesWith(Constant::getNullValue(Call->getType())); + else { + Call->replaceAllUsesWith(New); + New->takeName(Call); + } + } + + // Finally, remove the old call from the program, reducing the use-count of + // F. + Call->getParent()->getInstList().erase(Call); } // Since we have now created the new function, splice the body of the old @@ -209,13 +645,14 @@ void DAE::RemoveDeadArgumentsFromFunction(Function *F, // the new arguments, also transfering over the names as well. While we're at // it, remove the dead arguments from the DeadArguments list. // - for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin(); + for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), + I2 = NF->arg_begin(); I != E; ++I) if (!DeadArguments.count(I)) { // If this is a live argument, move the name and users over to the new // version. I->replaceAllUsesWith(I2); - I2->setName(I->getName()); + I2->takeName(I); ++I2; } else { // If this argument is dead, replace any uses of it with null constants @@ -225,61 +662,73 @@ void DAE::RemoveDeadArgumentsFromFunction(Function *F, DeadArguments.erase(I); } + // If we change the return value of the function we must rewrite any return + // instructions. Check this now. + if (F->getReturnType() != NF->getReturnType()) + for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB) + if (ReturnInst *RI = dyn_cast(BB->getTerminator())) { + new ReturnInst(0, RI); + BB->getInstList().erase(RI); + } + // Now that the old function is dead, delete it. F->getParent()->getFunctionList().erase(F); } -bool DAE::run(Module &M) { - // First phase: loop through the module, determining which arguments are live. +bool DAE::runOnModule(Module &M) { + bool Changed = false; + // 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 + // information computed while surveying other functions. + DOUT << "DAE - Deleting dead varargs\n"; + for (Module::iterator I = M.begin(), E = M.end(); I != E; ) { + Function &F = *I++; + if (F.getFunctionType()->isVarArg()) + Changed |= DeleteDeadVarargs(F); + } + + // Second phase:loop through the module, determining which arguments are live. // We assume all arguments are dead unless proven otherwise (allowing us to - // determing that dead arguments passed into recursive functions are dead). + // determine that dead arguments passed into recursive functions are dead). // - std::set LiveArguments, MaybeLiveArguments, DeadArguments; - std::multimap CallSites; - - DEBUG(std::cerr << "DAE - Determining liveness\n"); - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { - Function &Fn = *I; - // If the function is intrinsically alive, just mark the arguments alive. - if (FunctionArgumentsIntrinsicallyAlive(Fn)) { - for (Function::aiterator AI = Fn.abegin(), E = Fn.aend(); AI != E; ++AI) - LiveArguments.insert(AI); - DEBUG(std::cerr << " Args intrinsically live for fn: " << Fn.getName() - << "\n"); + DOUT << "DAE - Determining liveness\n"; + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + SurveyFunction(*I); + + // Loop over the instructions to inspect, propagating liveness among arguments + // and return values which are MaybeLive. + while (!InstructionsToInspect.empty()) { + Instruction *I = InstructionsToInspect.back(); + InstructionsToInspect.pop_back(); + + if (ReturnInst *RI = dyn_cast(I)) { + // For return instructions, we just have to check to see if the return + // value for the current function is known now to be alive. If so, any + // arguments used by it are now alive, and any call instruction return + // value is alive as well. + if (LiveRetVal.count(RI->getParent()->getParent())) + MarkReturnInstArgumentLive(RI); + } else { - DEBUG(std::cerr << " Inspecting args for fn: " << Fn.getName() << "\n"); + CallSite CS = CallSite::get(I); + assert(CS.getInstruction() && "Unknown instruction for the I2I list!"); - // If it is not intrinsically alive, we know that all users of the - // function are call sites. Mark all of the arguments live which are - // directly used, and keep track of all of the call sites of this function - // if there are any arguments we assume that are dead. - // - bool AnyMaybeLiveArgs = false; - for (Function::aiterator AI = Fn.abegin(), E = Fn.aend(); AI != E; ++AI) - switch (getArgumentLiveness(*AI)) { - case Alive: - DEBUG(std::cerr << " Arg live by use: " << AI->getName() << "\n"); - LiveArguments.insert(AI); - break; - case Dead: - DEBUG(std::cerr << " Arg definitely dead: " <getName()<<"\n"); - DeadArguments.insert(AI); - break; - case MaybeLive: - DEBUG(std::cerr << " Arg only passed to calls: " - << AI->getName() << "\n"); - AnyMaybeLiveArgs = true; - MaybeLiveArguments.insert(AI); - break; - } + Function *Callee = CS.getCalledFunction(); - // If there are any "MaybeLive" arguments, we need to check callees of - // this function when/if they become alive. Record which functions are - // callees... - if (AnyMaybeLiveArgs) - for (Value::use_iterator I = Fn.use_begin(), E = Fn.use_end(); - I != E; ++I) - CallSites.insert(std::make_pair(&Fn, CallSite::get(*I))); + // If we found a call or invoke instruction on this list, that means that + // an argument of the function is a call instruction. If the argument is + // live, then the return value of the called instruction is now live. + // + CallSite::arg_iterator AI = CS.arg_begin(); // ActualIterator + for (Function::arg_iterator FI = Callee->arg_begin(), + E = Callee->arg_end(); FI != E; ++AI, ++FI) { + // If this argument is another call... + CallSite ArgCS = CallSite::get(*AI); + if (ArgCS.getInstruction() && LiveArguments.count(FI)) + if (Function *Callee = ArgCS.getCalledFunction()) + MarkRetValLive(Callee); + } } } @@ -288,17 +737,16 @@ bool DAE::run(Module &M) { // passed into requires them to be live. Of course this could make other // arguments live, so process callers recursively. // - // Because elements can be removed from the MaybeLiveArguments list, copy it - // to a temporary vector. + // Because elements can be removed from the MaybeLiveArguments set, copy it to + // a temporary vector. // std::vector TmpArgList(MaybeLiveArguments.begin(), MaybeLiveArguments.end()); for (unsigned i = 0, e = TmpArgList.size(); i != e; ++i) { Argument *MLA = TmpArgList[i]; if (MaybeLiveArguments.count(MLA) && - isMaybeLiveArgumentNowAlive(MLA, LiveArguments)) { - MarkArgumentLive(MLA, MaybeLiveArguments, LiveArguments, CallSites); - } + isMaybeLiveArgumentNowLive(MLA)) + MarkArgumentLive(MLA); } // Recover memory early... @@ -307,17 +755,26 @@ bool DAE::run(Module &M) { // At this point, we know that all arguments in DeadArguments and // MaybeLiveArguments are dead. If the two sets are empty, there is nothing // to do. - if (MaybeLiveArguments.empty() && DeadArguments.empty()) - return false; - + if (MaybeLiveArguments.empty() && DeadArguments.empty() && + MaybeLiveRetVal.empty() && DeadRetVal.empty()) + return Changed; + // Otherwise, compact into one set, and start eliminating the arguments from // the functions. DeadArguments.insert(MaybeLiveArguments.begin(), MaybeLiveArguments.end()); MaybeLiveArguments.clear(); + DeadRetVal.insert(MaybeLiveRetVal.begin(), MaybeLiveRetVal.end()); + MaybeLiveRetVal.clear(); + + LiveArguments.clear(); + LiveRetVal.clear(); NumArgumentsEliminated += DeadArguments.size(); + NumRetValsEliminated += DeadRetVal.size(); while (!DeadArguments.empty()) - RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent(), - DeadArguments); + RemoveDeadArgumentsFromFunction((*DeadArguments.begin())->getParent()); + + while (!DeadRetVal.empty()) + RemoveDeadArgumentsFromFunction(*DeadRetVal.begin()); return true; }