X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FDeadArgumentElimination.cpp;h=3a333acd473a519448742a87ec32517fc7e4805d;hb=d04a8d4b33ff316ca4cf961e06c9e312eff8e64f;hp=6443dd4f47a65be7800d60c5179568ca0afeb995;hpb=0aa885d3ab800d290198ebe6b6893524f784b002;p=oota-llvm.git diff --git a/lib/Transforms/IPO/DeadArgumentElimination.cpp b/lib/Transforms/IPO/DeadArgumentElimination.cpp index 6443dd4f47a..3a333acd473 100644 --- a/lib/Transforms/IPO/DeadArgumentElimination.cpp +++ b/lib/Transforms/IPO/DeadArgumentElimination.cpp @@ -19,8 +19,14 @@ #define DEBUG_TYPE "deadargelim" #include "llvm/Transforms/IPO.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringExtras.h" #include "llvm/CallingConv.h" #include "llvm/Constant.h" +#include "llvm/DIBuilder.h" +#include "llvm/DebugInfo.h" #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" @@ -30,16 +36,14 @@ #include "llvm/Support/CallSite.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/StringExtras.h" #include #include using namespace llvm; 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,7 +52,7 @@ 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), IsArg(IsArg) {} @@ -73,7 +77,7 @@ namespace { std::string getDescription() const { return std::string((IsArg ? "Argument #" : "Return value #")) - + utostr(Idx) + " of function " + F->getNameStr(); + + utostr(Idx) + " of function " + F->getName().str(); } }; @@ -120,9 +124,25 @@ 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. + typedef DenseMap FunctionDIMap; + FunctionDIMap 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) {} + DAE() : ModulePass(ID) { + initializeDAEPass(*PassRegistry::getPassRegistry()); + } + bool runOnModule(Module &M); virtual bool ShouldHackArguments() const { return false; } @@ -133,6 +153,7 @@ namespace { unsigned RetValNum = 0); Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); + void CollectFunctionDIs(Module &M); void SurveyFunction(const Function &F); void MarkValue(const RetOrArg &RA, Liveness L, const UseVector &MaybeLiveUses); @@ -141,13 +162,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 +176,16 @@ namespace { /// by bugpoint. struct DAH : public DAE { static char ID; + DAH() : DAE(ID) {} + virtual bool ShouldHackArguments() const { 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. @@ -169,6 +193,33 @@ Y("deadarghaX0r", "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)"); ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); } ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); } +/// CollectFunctionDIs - Map each function in the module to its debug info +/// descriptor. +void DAE::CollectFunctionDIs(Module &M) { + FunctionDIs.clear(); + + for (Module::named_metadata_iterator I = M.named_metadata_begin(), + E = M.named_metadata_end(); I != E; ++I) { + NamedMDNode &NMD = *I; + for (unsigned MDIndex = 0, MDNum = NMD.getNumOperands(); + MDIndex < MDNum; ++MDIndex) { + MDNode *Node = NMD.getOperand(MDIndex); + if (!DIDescriptor(Node).isCompileUnit()) + continue; + DICompileUnit CU(Node); + const DIArray &SPs = CU.getSubprograms(); + for (unsigned SPIndex = 0, SPNum = SPs.getNumElements(); + SPIndex < SPNum; ++SPIndex) { + DISubprogram SP(SPs.getElement(SPIndex)); + if (!SP.Verify()) + continue; + if (Function *F = SP.getFunction()) + FunctionDIs[F] = SP; + } + } + } +} + /// 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) { @@ -195,9 +246,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(); + FunctionType *FTy = Fn.getFunctionType(); - std::vector Params(FTy->param_begin(), FTy->param_end()); + std::vector Params(FTy->param_begin(), FTy->param_end()); FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false); unsigned NumArgs = Params.size(); @@ -213,11 +264,11 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { // std::vector Args; while (!Fn.use_empty()) { - CallSite CS = CallSite::get(Fn.use_back()); + CallSite CS(Fn.use_back()); 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(); @@ -225,26 +276,27 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { 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()); + Attributes FnAttrs = PAL.getFnAttributes(); + if (FnAttrs.hasAttributes()) + AttributesVec.push_back(AttributeWithIndex::get(AttrListPtr::FunctionIndex, + FnAttrs)); + PAL = AttrListPtr::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(); } - if (MDNode *N = Call->getDbgMetadata()) - New->setDbgMetadata(N); + New->setDebugLoc(Call->getDebugLoc()); Args.clear(); @@ -263,8 +315,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(), @@ -274,18 +326,72 @@ bool DAE::DeleteDeadVarargs(Function &Fn) { I2->takeName(I); } + // Patch the pointer to LLVM function in debug info descriptor. + FunctionDIMap::iterator DI = FunctionDIs.find(&Fn); + if (DI != FunctionDIs.end()) + DI->second.replaceFunction(NF); + // 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) +{ + if (Fn.isDeclaration() || Fn.mayBeOverridden()) + return false; + + // Functions with local linkage should already have been handled. + if (Fn.hasLocalLinkage()) + return false; + + if (Fn.use_empty()) + return false; + + llvm::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->hasByValAttr()) + UnusedArgs.push_back(Arg->getArgNo()); + } + + if (UnusedArgs.empty()) + return false; + + bool Changed = false; + + for (Function::use_iterator I = Fn.use_begin(), E = Fn.use_end(); + I != E; ++I) { + CallSite CS(*I); + if (!CS || !CS.isCallee(I)) + 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()->isVoidTy()) return 0; - else if (const StructType *STy = dyn_cast(F->getReturnType())) + else if (StructType *STy = dyn_cast(F->getReturnType())) return STy->getNumElements(); else return 1; @@ -320,7 +426,7 @@ DAE::Liveness DAE::SurveyUse(Value::const_use_iterator U, // 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. + // original Use. RetOrArg Use = CreateRet(RI->getParent()->getParent(), RetValNum); // We might be live, depending on the liveness of Use. return MarkIfNotLive(Use, MaybeLiveUses); @@ -432,7 +538,7 @@ void DAE::SurveyFunction(const 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()); + Type *STy = dyn_cast(F.getReturnType()); // Loop all uses of the function. for (Value::const_use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) { @@ -535,14 +641,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, @@ -587,8 +693,8 @@ 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; // Set up to build a new list of parameter attributes. SmallVector AttributesVec; @@ -600,17 +706,17 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // Find out the new return value. - const Type *RetTy = FTy->getReturnType(); - const Type *NRetTy = NULL; + Type *RetTy = FTy->getReturnType(); + Type *NRetTy = NULL; unsigned RetCount = NumRetVals(F); // -1 means unused, other numbers are the new index SmallVector NewRetIdxs(RetCount, -1); - std::vector RetTypes; + std::vector RetTypes; if (RetTy->isVoidTy()) { NRetTy = RetTy; } else { - const StructType *STy = dyn_cast(RetTy); + StructType *STy = dyn_cast(RetTy); if (STy) // Look at each of the original return values individually. for (unsigned i = 0; i != RetCount; ++i) { @@ -658,13 +764,17 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // here. Currently, this should not be possible, but special handling might be // required when new return value attributes are added. if (NRetTy->isVoidTy()) - RAttrs &= ~Attribute::typeIncompatible(NRetTy); + RAttrs = + Attributes::get(NRetTy->getContext(), AttrBuilder(RAttrs). + removeAttributes(Attributes::typeIncompatible(NRetTy))); else - assert((RAttrs & Attribute::typeIncompatible(NRetTy)) == 0 - && "Return attributes no longer compatible?"); + assert(!AttrBuilder(RAttrs). + hasAttributes(Attributes::typeIncompatible(NRetTy)) && + "Return attributes no longer compatible?"); - if (RAttrs) - AttributesVec.push_back(AttributeWithIndex::get(0, RAttrs)); + if (RAttrs.hasAttributes()) + AttributesVec.push_back(AttributeWithIndex::get(AttrListPtr::ReturnIndex, + RAttrs)); // Remember which arguments are still alive. SmallVector ArgAlive(FTy->getNumParams(), false); @@ -681,7 +791,8 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // Get the original parameter attributes (skipping the first one, that is // for the return value. - if (Attributes Attrs = PAL.getParamAttributes(i + 1)) + Attributes Attrs = PAL.getParamAttributes(i + 1); + if (Attrs.hasAttributes()) AttributesVec.push_back(AttributeWithIndex::get(Params.size(), Attrs)); } else { ++NumArgumentsEliminated; @@ -690,12 +801,12 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { } } - if (FnAttrs != Attribute::None) - AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs)); + if (FnAttrs.hasAttributes()) + AttributesVec.push_back(AttributeWithIndex::get(AttrListPtr::FunctionIndex, + FnAttrs)); // Reconstruct the AttributesList based on the vector we constructed. - AttrListPtr NewPAL = AttrListPtr::get(AttributesVec.begin(), - AttributesVec.end()); + AttrListPtr NewPAL = AttrListPtr::get(F->getContext(), AttributesVec); // Create the new function type based on the recomputed parameters. FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg()); @@ -718,7 +829,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { // std::vector Args; while (!F->use_empty()) { - CallSite CS = CallSite::get(F->use_back()); + CallSite CS(F->use_back()); Instruction *Call = CS.getInstruction(); AttributesVec.clear(); @@ -728,9 +839,12 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { Attributes RAttrs = CallPAL.getRetAttributes(); Attributes FnAttrs = CallPAL.getFnAttributes(); // 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 = + Attributes::get(NF->getContext(), AttrBuilder(RAttrs). + removeAttributes(Attributes::typeIncompatible(NF->getReturnType()))); + if (RAttrs.hasAttributes()) + AttributesVec.push_back(AttributeWithIndex::get(AttrListPtr::ReturnIndex, + RAttrs)); // Declare these outside of the loops, so we can reuse them for the second // loop, which loops the varargs. @@ -742,39 +856,40 @@ 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)) + Attributes Attrs = CallPAL.getParamAttributes(i + 1); + if (Attrs.hasAttributes()) AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); } // 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)) + Attributes Attrs = CallPAL.getParamAttributes(i + 1); + if (Attrs.hasAttributes()) AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); } - if (FnAttrs != Attribute::None) - AttributesVec.push_back(AttributeWithIndex::get(~0, FnAttrs)); + if (FnAttrs.hasAttributes()) + AttributesVec.push_back(AttributeWithIndex::get(AttrListPtr::FunctionIndex, + FnAttrs)); // Reconstruct the AttributesList based on the vector we constructed. - AttrListPtr NewCallPAL = AttrListPtr::get(AttributesVec.begin(), - AttributesVec.end()); + AttrListPtr NewCallPAL = AttrListPtr::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(); } - if (MDNode *N = Call->getDbgMetadata()) - New->setDbgMetadata(N); + New->setDebugLoc(Call->getDebugLoc()); Args.clear(); @@ -786,7 +901,8 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { } 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() && "Return type changed, but not into a void. The old return type" @@ -835,8 +951,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) @@ -849,7 +965,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 @@ -859,7 +976,7 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { if (ReturnInst *RI = dyn_cast(BB->getTerminator())) { Value *RetVal; - if (NFTy->getReturnType() == Type::getVoidTy(F->getContext())) { + if (NFTy->getReturnType()->isVoidTy()) { RetVal = 0; } else { assert (RetTy->isStructTy()); @@ -894,6 +1011,11 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { BB->getInstList().erase(RI); } + // Patch the pointer to LLVM function in debug info descriptor. + FunctionDIMap::iterator DI = FunctionDIs.find(F); + if (DI != FunctionDIs.end()) + DI->second.replaceFunction(NF); + // Now that the old function is dead, delete it. F->eraseFromParent(); @@ -903,6 +1025,9 @@ bool DAE::RemoveDeadStuffFromFunction(Function *F) { bool DAE::runOnModule(Module &M) { bool Changed = false; + // Collect debug info descriptors for functions. + CollectFunctionDIs(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 @@ -930,5 +1055,14 @@ bool DAE::runOnModule(Module &M) { 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 (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { + Function& F = *I; + + Changed |= RemoveDeadArgumentsFromCallers(F); + } + return Changed; }