LLVM API Documentation

DeadArgumentElimination.cpp
Go to the documentation of this file.
00001 //===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass deletes dead arguments from internal functions.  Dead argument
00011 // elimination removes arguments which are directly dead, as well as arguments
00012 // only passed into function calls as dead arguments of other functions.  This
00013 // pass also deletes dead return values in a similar way.
00014 //
00015 // This pass is often useful as a cleanup pass to run after aggressive
00016 // interprocedural passes, which add possibly-dead arguments or return values.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #include "llvm/Transforms/IPO.h"
00021 #include "llvm/ADT/DenseMap.h"
00022 #include "llvm/ADT/SmallVector.h"
00023 #include "llvm/ADT/Statistic.h"
00024 #include "llvm/ADT/StringExtras.h"
00025 #include "llvm/IR/CallSite.h"
00026 #include "llvm/IR/CallingConv.h"
00027 #include "llvm/IR/Constant.h"
00028 #include "llvm/IR/DIBuilder.h"
00029 #include "llvm/IR/DebugInfo.h"
00030 #include "llvm/IR/DerivedTypes.h"
00031 #include "llvm/IR/Instructions.h"
00032 #include "llvm/IR/IntrinsicInst.h"
00033 #include "llvm/IR/LLVMContext.h"
00034 #include "llvm/IR/Module.h"
00035 #include "llvm/Pass.h"
00036 #include "llvm/Support/Debug.h"
00037 #include "llvm/Support/raw_ostream.h"
00038 #include <map>
00039 #include <set>
00040 #include <tuple>
00041 using namespace llvm;
00042 
00043 #define DEBUG_TYPE "deadargelim"
00044 
00045 STATISTIC(NumArgumentsEliminated, "Number of unread args removed");
00046 STATISTIC(NumRetValsEliminated  , "Number of unused return values removed");
00047 STATISTIC(NumArgumentsReplacedWithUndef, 
00048           "Number of unread args replaced with undef");
00049 namespace {
00050   /// DAE - The dead argument elimination pass.
00051   ///
00052   class DAE : public ModulePass {
00053   public:
00054 
00055     /// Struct that represents (part of) either a return value or a function
00056     /// argument.  Used so that arguments and return values can be used
00057     /// interchangeably.
00058     struct RetOrArg {
00059       RetOrArg(const Function *F, unsigned Idx, bool IsArg) : F(F), Idx(Idx),
00060                IsArg(IsArg) {}
00061       const Function *F;
00062       unsigned Idx;
00063       bool IsArg;
00064 
00065       /// Make RetOrArg comparable, so we can put it into a map.
00066       bool operator<(const RetOrArg &O) const {
00067         return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg);
00068       }
00069 
00070       /// Make RetOrArg comparable, so we can easily iterate the multimap.
00071       bool operator==(const RetOrArg &O) const {
00072         return F == O.F && Idx == O.Idx && IsArg == O.IsArg;
00073       }
00074 
00075       std::string getDescription() const {
00076         return std::string((IsArg ? "Argument #" : "Return value #"))
00077                + utostr(Idx) + " of function " + F->getName().str();
00078       }
00079     };
00080 
00081     /// Liveness enum - During our initial pass over the program, we determine
00082     /// that things are either alive or maybe alive. We don't mark anything
00083     /// explicitly dead (even if we know they are), since anything not alive
00084     /// with no registered uses (in Uses) will never be marked alive and will
00085     /// thus become dead in the end.
00086     enum Liveness { Live, MaybeLive };
00087 
00088     /// Convenience wrapper
00089     RetOrArg CreateRet(const Function *F, unsigned Idx) {
00090       return RetOrArg(F, Idx, false);
00091     }
00092     /// Convenience wrapper
00093     RetOrArg CreateArg(const Function *F, unsigned Idx) {
00094       return RetOrArg(F, Idx, true);
00095     }
00096 
00097     typedef std::multimap<RetOrArg, RetOrArg> UseMap;
00098     /// This maps a return value or argument to any MaybeLive return values or
00099     /// arguments it uses. This allows the MaybeLive values to be marked live
00100     /// when any of its users is marked live.
00101     /// For example (indices are left out for clarity):
00102     ///  - Uses[ret F] = ret G
00103     ///    This means that F calls G, and F returns the value returned by G.
00104     ///  - Uses[arg F] = ret G
00105     ///    This means that some function calls G and passes its result as an
00106     ///    argument to F.
00107     ///  - Uses[ret F] = arg F
00108     ///    This means that F returns one of its own arguments.
00109     ///  - Uses[arg F] = arg G
00110     ///    This means that G calls F and passes one of its own (G's) arguments
00111     ///    directly to F.
00112     UseMap Uses;
00113 
00114     typedef std::set<RetOrArg> LiveSet;
00115     typedef std::set<const Function*> LiveFuncSet;
00116 
00117     /// This set contains all values that have been determined to be live.
00118     LiveSet LiveValues;
00119     /// This set contains all values that are cannot be changed in any way.
00120     LiveFuncSet LiveFunctions;
00121 
00122     typedef SmallVector<RetOrArg, 5> UseVector;
00123 
00124     // Map each LLVM function to corresponding metadata with debug info. If
00125     // the function is replaced with another one, we should patch the pointer
00126     // to LLVM function in metadata.
00127     // As the code generation for module is finished (and DIBuilder is
00128     // finalized) we assume that subprogram descriptors won't be changed, and
00129     // they are stored in map for short duration anyway.
00130     DenseMap<const Function *, DISubprogram> FunctionDIs;
00131 
00132   protected:
00133     // DAH uses this to specify a different ID.
00134     explicit DAE(char &ID) : ModulePass(ID) {}
00135 
00136   public:
00137     static char ID; // Pass identification, replacement for typeid
00138     DAE() : ModulePass(ID) {
00139       initializeDAEPass(*PassRegistry::getPassRegistry());
00140     }
00141 
00142     bool runOnModule(Module &M) override;
00143 
00144     virtual bool ShouldHackArguments() const { return false; }
00145 
00146   private:
00147     Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
00148     Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses,
00149                        unsigned RetValNum = 0);
00150     Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses);
00151 
00152     void SurveyFunction(const Function &F);
00153     void MarkValue(const RetOrArg &RA, Liveness L,
00154                    const UseVector &MaybeLiveUses);
00155     void MarkLive(const RetOrArg &RA);
00156     void MarkLive(const Function &F);
00157     void PropagateLiveness(const RetOrArg &RA);
00158     bool RemoveDeadStuffFromFunction(Function *F);
00159     bool DeleteDeadVarargs(Function &Fn);
00160     bool RemoveDeadArgumentsFromCallers(Function &Fn);
00161   };
00162 }
00163 
00164 
00165 char DAE::ID = 0;
00166 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false)
00167 
00168 namespace {
00169   /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but
00170   /// deletes arguments to functions which are external.  This is only for use
00171   /// by bugpoint.
00172   struct DAH : public DAE {
00173     static char ID;
00174     DAH() : DAE(ID) {}
00175 
00176     bool ShouldHackArguments() const override { return true; }
00177   };
00178 }
00179 
00180 char DAH::ID = 0;
00181 INITIALIZE_PASS(DAH, "deadarghaX0r", 
00182                 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",
00183                 false, false)
00184 
00185 /// createDeadArgEliminationPass - This pass removes arguments from functions
00186 /// which are not used by the body of the function.
00187 ///
00188 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }
00189 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); }
00190 
00191 /// DeleteDeadVarargs - If this is an function that takes a ... list, and if
00192 /// llvm.vastart is never called, the varargs list is dead for the function.
00193 bool DAE::DeleteDeadVarargs(Function &Fn) {
00194   assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!");
00195   if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false;
00196 
00197   // Ensure that the function is only directly called.
00198   if (Fn.hasAddressTaken())
00199     return false;
00200 
00201   // Okay, we know we can transform this function if safe.  Scan its body
00202   // looking for calls to llvm.vastart.
00203   for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
00204     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
00205       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
00206         if (II->getIntrinsicID() == Intrinsic::vastart)
00207           return false;
00208       }
00209     }
00210   }
00211 
00212   // If we get here, there are no calls to llvm.vastart in the function body,
00213   // remove the "..." and adjust all the calls.
00214 
00215   // Start by computing a new prototype for the function, which is the same as
00216   // the old function, but doesn't have isVarArg set.
00217   FunctionType *FTy = Fn.getFunctionType();
00218 
00219   std::vector<Type*> Params(FTy->param_begin(), FTy->param_end());
00220   FunctionType *NFTy = FunctionType::get(FTy->getReturnType(),
00221                                                 Params, false);
00222   unsigned NumArgs = Params.size();
00223 
00224   // Create the new function body and insert it into the module...
00225   Function *NF = Function::Create(NFTy, Fn.getLinkage());
00226   NF->copyAttributesFrom(&Fn);
00227   Fn.getParent()->getFunctionList().insert(&Fn, NF);
00228   NF->takeName(&Fn);
00229 
00230   // Loop over all of the callers of the function, transforming the call sites
00231   // to pass in a smaller number of arguments into the new function.
00232   //
00233   std::vector<Value*> Args;
00234   for (Value::user_iterator I = Fn.user_begin(), E = Fn.user_end(); I != E; ) {
00235     CallSite CS(*I++);
00236     if (!CS)
00237       continue;
00238     Instruction *Call = CS.getInstruction();
00239 
00240     // Pass all the same arguments.
00241     Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs);
00242 
00243     // Drop any attributes that were on the vararg arguments.
00244     AttributeSet PAL = CS.getAttributes();
00245     if (!PAL.isEmpty() && PAL.getSlotIndex(PAL.getNumSlots() - 1) > NumArgs) {
00246       SmallVector<AttributeSet, 8> AttributesVec;
00247       for (unsigned i = 0; PAL.getSlotIndex(i) <= NumArgs; ++i)
00248         AttributesVec.push_back(PAL.getSlotAttributes(i));
00249       if (PAL.hasAttributes(AttributeSet::FunctionIndex))
00250         AttributesVec.push_back(AttributeSet::get(Fn.getContext(),
00251                                                   PAL.getFnAttributes()));
00252       PAL = AttributeSet::get(Fn.getContext(), AttributesVec);
00253     }
00254 
00255     Instruction *New;
00256     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
00257       New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
00258                                Args, "", Call);
00259       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
00260       cast<InvokeInst>(New)->setAttributes(PAL);
00261     } else {
00262       New = CallInst::Create(NF, Args, "", Call);
00263       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
00264       cast<CallInst>(New)->setAttributes(PAL);
00265       if (cast<CallInst>(Call)->isTailCall())
00266         cast<CallInst>(New)->setTailCall();
00267     }
00268     New->setDebugLoc(Call->getDebugLoc());
00269 
00270     Args.clear();
00271 
00272     if (!Call->use_empty())
00273       Call->replaceAllUsesWith(New);
00274 
00275     New->takeName(Call);
00276 
00277     // Finally, remove the old call from the program, reducing the use-count of
00278     // F.
00279     Call->eraseFromParent();
00280   }
00281 
00282   // Since we have now created the new function, splice the body of the old
00283   // function right into the new function, leaving the old rotting hulk of the
00284   // function empty.
00285   NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList());
00286 
00287   // Loop over the argument list, transferring uses of the old arguments over to
00288   // the new arguments, also transferring over the names as well.  While we're at
00289   // it, remove the dead arguments from the DeadArguments list.
00290   //
00291   for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(),
00292        I2 = NF->arg_begin(); I != E; ++I, ++I2) {
00293     // Move the name and users over to the new version.
00294     I->replaceAllUsesWith(I2);
00295     I2->takeName(I);
00296   }
00297 
00298   // Patch the pointer to LLVM function in debug info descriptor.
00299   auto DI = FunctionDIs.find(&Fn);
00300   if (DI != FunctionDIs.end())
00301     DI->second.replaceFunction(NF);
00302 
00303   // Fix up any BlockAddresses that refer to the function.
00304   Fn.replaceAllUsesWith(ConstantExpr::getBitCast(NF, Fn.getType()));
00305   // Delete the bitcast that we just created, so that NF does not
00306   // appear to be address-taken.
00307   NF->removeDeadConstantUsers();
00308   // Finally, nuke the old function.
00309   Fn.eraseFromParent();
00310   return true;
00311 }
00312 
00313 /// RemoveDeadArgumentsFromCallers - Checks if the given function has any 
00314 /// arguments that are unused, and changes the caller parameters to be undefined
00315 /// instead.
00316 bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn)
00317 {
00318   if (Fn.isDeclaration() || Fn.mayBeOverridden())
00319     return false;
00320 
00321   // Functions with local linkage should already have been handled, except the
00322   // fragile (variadic) ones which we can improve here.
00323   if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg())
00324     return false;
00325 
00326   // If a function seen at compile time is not necessarily the one linked to
00327   // the binary being built, it is illegal to change the actual arguments
00328   // passed to it. These functions can be captured by isWeakForLinker().
00329   // *NOTE* that mayBeOverridden() is insufficient for this purpose as it
00330   // doesn't include linkage types like AvailableExternallyLinkage and
00331   // LinkOnceODRLinkage. Take link_odr* as an example, it indicates a set of
00332   // *EQUIVALENT* globals that can be merged at link-time. However, the
00333   // semantic of *EQUIVALENT*-functions includes parameters. Changing
00334   // parameters breaks this assumption.
00335   //
00336   if (Fn.isWeakForLinker())
00337     return false;
00338 
00339   if (Fn.use_empty())
00340     return false;
00341 
00342   SmallVector<unsigned, 8> UnusedArgs;
00343   for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(); 
00344        I != E; ++I) {
00345     Argument *Arg = I;
00346 
00347     if (Arg->use_empty() && !Arg->hasByValOrInAllocaAttr())
00348       UnusedArgs.push_back(Arg->getArgNo());
00349   }
00350 
00351   if (UnusedArgs.empty())
00352     return false;
00353 
00354   bool Changed = false;
00355 
00356   for (Use &U : Fn.uses()) {
00357     CallSite CS(U.getUser());
00358     if (!CS || !CS.isCallee(&U))
00359       continue;
00360 
00361     // Now go through all unused args and replace them with "undef".
00362     for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) {
00363       unsigned ArgNo = UnusedArgs[I];
00364 
00365       Value *Arg = CS.getArgument(ArgNo);
00366       CS.setArgument(ArgNo, UndefValue::get(Arg->getType()));
00367       ++NumArgumentsReplacedWithUndef;
00368       Changed = true;
00369     }
00370   }
00371 
00372   return Changed;
00373 }
00374 
00375 /// Convenience function that returns the number of return values. It returns 0
00376 /// for void functions and 1 for functions not returning a struct. It returns
00377 /// the number of struct elements for functions returning a struct.
00378 static unsigned NumRetVals(const Function *F) {
00379   if (F->getReturnType()->isVoidTy())
00380     return 0;
00381   else if (StructType *STy = dyn_cast<StructType>(F->getReturnType()))
00382     return STy->getNumElements();
00383   else
00384     return 1;
00385 }
00386 
00387 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not
00388 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined
00389 /// liveness of Use.
00390 DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) {
00391   // We're live if our use or its Function is already marked as live.
00392   if (LiveFunctions.count(Use.F) || LiveValues.count(Use))
00393     return Live;
00394 
00395   // We're maybe live otherwise, but remember that we must become live if
00396   // Use becomes live.
00397   MaybeLiveUses.push_back(Use);
00398   return MaybeLive;
00399 }
00400 
00401 
00402 /// SurveyUse - This looks at a single use of an argument or return value
00403 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses
00404 /// if it causes the used value to become MaybeLive.
00405 ///
00406 /// RetValNum is the return value number to use when this use is used in a
00407 /// return instruction. This is used in the recursion, you should always leave
00408 /// it at 0.
00409 DAE::Liveness DAE::SurveyUse(const Use *U,
00410                              UseVector &MaybeLiveUses, unsigned RetValNum) {
00411     const User *V = U->getUser();
00412     if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) {
00413       // The value is returned from a function. It's only live when the
00414       // function's return value is live. We use RetValNum here, for the case
00415       // that U is really a use of an insertvalue instruction that uses the
00416       // original Use.
00417       RetOrArg Use = CreateRet(RI->getParent()->getParent(), RetValNum);
00418       // We might be live, depending on the liveness of Use.
00419       return MarkIfNotLive(Use, MaybeLiveUses);
00420     }
00421     if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) {
00422       if (U->getOperandNo() != InsertValueInst::getAggregateOperandIndex()
00423           && IV->hasIndices())
00424         // The use we are examining is inserted into an aggregate. Our liveness
00425         // depends on all uses of that aggregate, but if it is used as a return
00426         // value, only index at which we were inserted counts.
00427         RetValNum = *IV->idx_begin();
00428 
00429       // Note that if we are used as the aggregate operand to the insertvalue,
00430       // we don't change RetValNum, but do survey all our uses.
00431 
00432       Liveness Result = MaybeLive;
00433       for (const Use &UU : IV->uses()) {
00434         Result = SurveyUse(&UU, MaybeLiveUses, RetValNum);
00435         if (Result == Live)
00436           break;
00437       }
00438       return Result;
00439     }
00440 
00441     if (ImmutableCallSite CS = V) {
00442       const Function *F = CS.getCalledFunction();
00443       if (F) {
00444         // Used in a direct call.
00445 
00446         // Find the argument number. We know for sure that this use is an
00447         // argument, since if it was the function argument this would be an
00448         // indirect call and the we know can't be looking at a value of the
00449         // label type (for the invoke instruction).
00450         unsigned ArgNo = CS.getArgumentNo(U);
00451 
00452         if (ArgNo >= F->getFunctionType()->getNumParams())
00453           // The value is passed in through a vararg! Must be live.
00454           return Live;
00455 
00456         assert(CS.getArgument(ArgNo)
00457                == CS->getOperand(U->getOperandNo())
00458                && "Argument is not where we expected it");
00459 
00460         // Value passed to a normal call. It's only live when the corresponding
00461         // argument to the called function turns out live.
00462         RetOrArg Use = CreateArg(F, ArgNo);
00463         return MarkIfNotLive(Use, MaybeLiveUses);
00464       }
00465     }
00466     // Used in any other way? Value must be live.
00467     return Live;
00468 }
00469 
00470 /// SurveyUses - This looks at all the uses of the given value
00471 /// Returns the Liveness deduced from the uses of this value.
00472 ///
00473 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If
00474 /// the result is Live, MaybeLiveUses might be modified but its content should
00475 /// be ignored (since it might not be complete).
00476 DAE::Liveness DAE::SurveyUses(const Value *V, UseVector &MaybeLiveUses) {
00477   // Assume it's dead (which will only hold if there are no uses at all..).
00478   Liveness Result = MaybeLive;
00479   // Check each use.
00480   for (const Use &U : V->uses()) {
00481     Result = SurveyUse(&U, MaybeLiveUses);
00482     if (Result == Live)
00483       break;
00484   }
00485   return Result;
00486 }
00487 
00488 // SurveyFunction - This performs the initial survey of the specified function,
00489 // checking out whether or not it uses any of its incoming arguments or whether
00490 // any callers use the return value.  This fills in the LiveValues set and Uses
00491 // map.
00492 //
00493 // We consider arguments of non-internal functions to be intrinsically alive as
00494 // well as arguments to functions which have their "address taken".
00495 //
00496 void DAE::SurveyFunction(const Function &F) {
00497   // Functions with inalloca parameters are expecting args in a particular
00498   // register and memory layout.
00499   if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) {
00500     MarkLive(F);
00501     return;
00502   }
00503 
00504   unsigned RetCount = NumRetVals(&F);
00505   // Assume all return values are dead
00506   typedef SmallVector<Liveness, 5> RetVals;
00507   RetVals RetValLiveness(RetCount, MaybeLive);
00508 
00509   typedef SmallVector<UseVector, 5> RetUses;
00510   // These vectors map each return value to the uses that make it MaybeLive, so
00511   // we can add those to the Uses map if the return value really turns out to be
00512   // MaybeLive. Initialized to a list of RetCount empty lists.
00513   RetUses MaybeLiveRetUses(RetCount);
00514 
00515   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00516     if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
00517       if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType()
00518           != F.getFunctionType()->getReturnType()) {
00519         // We don't support old style multiple return values.
00520         MarkLive(F);
00521         return;
00522       }
00523 
00524   if (!F.hasLocalLinkage() && (!ShouldHackArguments() || F.isIntrinsic())) {
00525     MarkLive(F);
00526     return;
00527   }
00528 
00529   DEBUG(dbgs() << "DAE - Inspecting callers for fn: " << F.getName() << "\n");
00530   // Keep track of the number of live retvals, so we can skip checks once all
00531   // of them turn out to be live.
00532   unsigned NumLiveRetVals = 0;
00533   Type *STy = dyn_cast<StructType>(F.getReturnType());
00534   // Loop all uses of the function.
00535   for (const Use &U : F.uses()) {
00536     // If the function is PASSED IN as an argument, its address has been
00537     // taken.
00538     ImmutableCallSite CS(U.getUser());
00539     if (!CS || !CS.isCallee(&U)) {
00540       MarkLive(F);
00541       return;
00542     }
00543 
00544     // If this use is anything other than a call site, the function is alive.
00545     const Instruction *TheCall = CS.getInstruction();
00546     if (!TheCall) {   // Not a direct call site?
00547       MarkLive(F);
00548       return;
00549     }
00550 
00551     // If we end up here, we are looking at a direct call to our function.
00552 
00553     // Now, check how our return value(s) is/are used in this caller. Don't
00554     // bother checking return values if all of them are live already.
00555     if (NumLiveRetVals != RetCount) {
00556       if (STy) {
00557         // Check all uses of the return value.
00558         for (const User *U : TheCall->users()) {
00559           const ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U);
00560           if (Ext && Ext->hasIndices()) {
00561             // This use uses a part of our return value, survey the uses of
00562             // that part and store the results for this index only.
00563             unsigned Idx = *Ext->idx_begin();
00564             if (RetValLiveness[Idx] != Live) {
00565               RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]);
00566               if (RetValLiveness[Idx] == Live)
00567                 NumLiveRetVals++;
00568             }
00569           } else {
00570             // Used by something else than extractvalue. Mark all return
00571             // values as live.
00572             for (unsigned i = 0; i != RetCount; ++i )
00573               RetValLiveness[i] = Live;
00574             NumLiveRetVals = RetCount;
00575             break;
00576           }
00577         }
00578       } else {
00579         // Single return value
00580         RetValLiveness[0] = SurveyUses(TheCall, MaybeLiveRetUses[0]);
00581         if (RetValLiveness[0] == Live)
00582           NumLiveRetVals = RetCount;
00583       }
00584     }
00585   }
00586 
00587   // Now we've inspected all callers, record the liveness of our return values.
00588   for (unsigned i = 0; i != RetCount; ++i)
00589     MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]);
00590 
00591   DEBUG(dbgs() << "DAE - Inspecting args for fn: " << F.getName() << "\n");
00592 
00593   // Now, check all of our arguments.
00594   unsigned i = 0;
00595   UseVector MaybeLiveArgUses;
00596   for (Function::const_arg_iterator AI = F.arg_begin(),
00597        E = F.arg_end(); AI != E; ++AI, ++i) {
00598     Liveness Result;
00599     if (F.getFunctionType()->isVarArg()) {
00600       // Variadic functions will already have a va_arg function expanded inside
00601       // them, making them potentially very sensitive to ABI changes resulting
00602       // from removing arguments entirely, so don't. For example AArch64 handles
00603       // register and stack HFAs very differently, and this is reflected in the
00604       // IR which has already been generated.
00605       Result = Live;
00606     } else {
00607       // See what the effect of this use is (recording any uses that cause
00608       // MaybeLive in MaybeLiveArgUses). 
00609       Result = SurveyUses(AI, MaybeLiveArgUses);
00610     }
00611 
00612     // Mark the result.
00613     MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses);
00614     // Clear the vector again for the next iteration.
00615     MaybeLiveArgUses.clear();
00616   }
00617 }
00618 
00619 /// MarkValue - This function marks the liveness of RA depending on L. If L is
00620 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses,
00621 /// such that RA will be marked live if any use in MaybeLiveUses gets marked
00622 /// live later on.
00623 void DAE::MarkValue(const RetOrArg &RA, Liveness L,
00624                     const UseVector &MaybeLiveUses) {
00625   switch (L) {
00626     case Live: MarkLive(RA); break;
00627     case MaybeLive:
00628     {
00629       // Note any uses of this value, so this return value can be
00630       // marked live whenever one of the uses becomes live.
00631       for (UseVector::const_iterator UI = MaybeLiveUses.begin(),
00632            UE = MaybeLiveUses.end(); UI != UE; ++UI)
00633         Uses.insert(std::make_pair(*UI, RA));
00634       break;
00635     }
00636   }
00637 }
00638 
00639 /// MarkLive - Mark the given Function as alive, meaning that it cannot be
00640 /// changed in any way. Additionally,
00641 /// mark any values that are used as this function's parameters or by its return
00642 /// values (according to Uses) live as well.
00643 void DAE::MarkLive(const Function &F) {
00644   DEBUG(dbgs() << "DAE - Intrinsically live fn: " << F.getName() << "\n");
00645   // Mark the function as live.
00646   LiveFunctions.insert(&F);
00647   // Mark all arguments as live.
00648   for (unsigned i = 0, e = F.arg_size(); i != e; ++i)
00649     PropagateLiveness(CreateArg(&F, i));
00650   // Mark all return values as live.
00651   for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i)
00652     PropagateLiveness(CreateRet(&F, i));
00653 }
00654 
00655 /// MarkLive - Mark the given return value or argument as live. Additionally,
00656 /// mark any values that are used by this value (according to Uses) live as
00657 /// well.
00658 void DAE::MarkLive(const RetOrArg &RA) {
00659   if (LiveFunctions.count(RA.F))
00660     return; // Function was already marked Live.
00661 
00662   if (!LiveValues.insert(RA).second)
00663     return; // We were already marked Live.
00664 
00665   DEBUG(dbgs() << "DAE - Marking " << RA.getDescription() << " live\n");
00666   PropagateLiveness(RA);
00667 }
00668 
00669 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness
00670 /// to any other values it uses (according to Uses).
00671 void DAE::PropagateLiveness(const RetOrArg &RA) {
00672   // We don't use upper_bound (or equal_range) here, because our recursive call
00673   // to ourselves is likely to cause the upper_bound (which is the first value
00674   // not belonging to RA) to become erased and the iterator invalidated.
00675   UseMap::iterator Begin = Uses.lower_bound(RA);
00676   UseMap::iterator E = Uses.end();
00677   UseMap::iterator I;
00678   for (I = Begin; I != E && I->first == RA; ++I)
00679     MarkLive(I->second);
00680 
00681   // Erase RA from the Uses map (from the lower bound to wherever we ended up
00682   // after the loop).
00683   Uses.erase(Begin, I);
00684 }
00685 
00686 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F
00687 // that are not in LiveValues. Transform the function and all of the callees of
00688 // the function to not have these arguments and return values.
00689 //
00690 bool DAE::RemoveDeadStuffFromFunction(Function *F) {
00691   // Don't modify fully live functions
00692   if (LiveFunctions.count(F))
00693     return false;
00694 
00695   // Start by computing a new prototype for the function, which is the same as
00696   // the old function, but has fewer arguments and a different return type.
00697   FunctionType *FTy = F->getFunctionType();
00698   std::vector<Type*> Params;
00699 
00700   // Keep track of if we have a live 'returned' argument
00701   bool HasLiveReturnedArg = false;
00702 
00703   // Set up to build a new list of parameter attributes.
00704   SmallVector<AttributeSet, 8> AttributesVec;
00705   const AttributeSet &PAL = F->getAttributes();
00706 
00707   // Remember which arguments are still alive.
00708   SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false);
00709   // Construct the new parameter list from non-dead arguments. Also construct
00710   // a new set of parameter attributes to correspond. Skip the first parameter
00711   // attribute, since that belongs to the return value.
00712   unsigned i = 0;
00713   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
00714        I != E; ++I, ++i) {
00715     RetOrArg Arg = CreateArg(F, i);
00716     if (LiveValues.erase(Arg)) {
00717       Params.push_back(I->getType());
00718       ArgAlive[i] = true;
00719 
00720       // Get the original parameter attributes (skipping the first one, that is
00721       // for the return value.
00722       if (PAL.hasAttributes(i + 1)) {
00723         AttrBuilder B(PAL, i + 1);
00724         if (B.contains(Attribute::Returned))
00725           HasLiveReturnedArg = true;
00726         AttributesVec.
00727           push_back(AttributeSet::get(F->getContext(), Params.size(), B));
00728       }
00729     } else {
00730       ++NumArgumentsEliminated;
00731       DEBUG(dbgs() << "DAE - Removing argument " << i << " (" << I->getName()
00732             << ") from " << F->getName() << "\n");
00733     }
00734   }
00735 
00736   // Find out the new return value.
00737   Type *RetTy = FTy->getReturnType();
00738   Type *NRetTy = nullptr;
00739   unsigned RetCount = NumRetVals(F);
00740 
00741   // -1 means unused, other numbers are the new index
00742   SmallVector<int, 5> NewRetIdxs(RetCount, -1);
00743   std::vector<Type*> RetTypes;
00744 
00745   // If there is a function with a live 'returned' argument but a dead return
00746   // value, then there are two possible actions:
00747   // 1) Eliminate the return value and take off the 'returned' attribute on the
00748   //    argument.
00749   // 2) Retain the 'returned' attribute and treat the return value (but not the
00750   //    entire function) as live so that it is not eliminated.
00751   // 
00752   // It's not clear in the general case which option is more profitable because,
00753   // even in the absence of explicit uses of the return value, code generation
00754   // is free to use the 'returned' attribute to do things like eliding
00755   // save/restores of registers across calls. Whether or not this happens is
00756   // target and ABI-specific as well as depending on the amount of register
00757   // pressure, so there's no good way for an IR-level pass to figure this out.
00758   //
00759   // Fortunately, the only places where 'returned' is currently generated by
00760   // the FE are places where 'returned' is basically free and almost always a
00761   // performance win, so the second option can just be used always for now.
00762   //
00763   // This should be revisited if 'returned' is ever applied more liberally.
00764   if (RetTy->isVoidTy() || HasLiveReturnedArg) {
00765     NRetTy = RetTy;
00766   } else {
00767     StructType *STy = dyn_cast<StructType>(RetTy);
00768     if (STy)
00769       // Look at each of the original return values individually.
00770       for (unsigned i = 0; i != RetCount; ++i) {
00771         RetOrArg Ret = CreateRet(F, i);
00772         if (LiveValues.erase(Ret)) {
00773           RetTypes.push_back(STy->getElementType(i));
00774           NewRetIdxs[i] = RetTypes.size() - 1;
00775         } else {
00776           ++NumRetValsEliminated;
00777           DEBUG(dbgs() << "DAE - Removing return value " << i << " from "
00778                 << F->getName() << "\n");
00779         }
00780       }
00781     else
00782       // We used to return a single value.
00783       if (LiveValues.erase(CreateRet(F, 0))) {
00784         RetTypes.push_back(RetTy);
00785         NewRetIdxs[0] = 0;
00786       } else {
00787         DEBUG(dbgs() << "DAE - Removing return value from " << F->getName()
00788               << "\n");
00789         ++NumRetValsEliminated;
00790       }
00791     if (RetTypes.size() > 1)
00792       // More than one return type? Return a struct with them. Also, if we used
00793       // to return a struct and didn't change the number of return values,
00794       // return a struct again. This prevents changing {something} into
00795       // something and {} into void.
00796       // Make the new struct packed if we used to return a packed struct
00797       // already.
00798       NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked());
00799     else if (RetTypes.size() == 1)
00800       // One return type? Just a simple value then, but only if we didn't use to
00801       // return a struct with that simple value before.
00802       NRetTy = RetTypes.front();
00803     else if (RetTypes.size() == 0)
00804       // No return types? Make it void, but only if we didn't use to return {}.
00805       NRetTy = Type::getVoidTy(F->getContext());
00806   }
00807 
00808   assert(NRetTy && "No new return type found?");
00809 
00810   // The existing function return attributes.
00811   AttributeSet RAttrs = PAL.getRetAttributes();
00812 
00813   // Remove any incompatible attributes, but only if we removed all return
00814   // values. Otherwise, ensure that we don't have any conflicting attributes
00815   // here. Currently, this should not be possible, but special handling might be
00816   // required when new return value attributes are added.
00817   if (NRetTy->isVoidTy())
00818     RAttrs =
00819       AttributeSet::get(NRetTy->getContext(), AttributeSet::ReturnIndex,
00820                         AttrBuilder(RAttrs, AttributeSet::ReturnIndex).
00821          removeAttributes(AttributeFuncs::
00822                           typeIncompatible(NRetTy, AttributeSet::ReturnIndex),
00823                           AttributeSet::ReturnIndex));
00824   else
00825     assert(!AttrBuilder(RAttrs, AttributeSet::ReturnIndex).
00826              hasAttributes(AttributeFuncs::
00827                            typeIncompatible(NRetTy, AttributeSet::ReturnIndex),
00828                            AttributeSet::ReturnIndex) &&
00829            "Return attributes no longer compatible?");
00830 
00831   if (RAttrs.hasAttributes(AttributeSet::ReturnIndex))
00832     AttributesVec.push_back(AttributeSet::get(NRetTy->getContext(), RAttrs));
00833 
00834   if (PAL.hasAttributes(AttributeSet::FunctionIndex))
00835     AttributesVec.push_back(AttributeSet::get(F->getContext(),
00836                                               PAL.getFnAttributes()));
00837 
00838   // Reconstruct the AttributesList based on the vector we constructed.
00839   AttributeSet NewPAL = AttributeSet::get(F->getContext(), AttributesVec);
00840 
00841   // Create the new function type based on the recomputed parameters.
00842   FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg());
00843 
00844   // No change?
00845   if (NFTy == FTy)
00846     return false;
00847 
00848   // Create the new function body and insert it into the module...
00849   Function *NF = Function::Create(NFTy, F->getLinkage());
00850   NF->copyAttributesFrom(F);
00851   NF->setAttributes(NewPAL);
00852   // Insert the new function before the old function, so we won't be processing
00853   // it again.
00854   F->getParent()->getFunctionList().insert(F, NF);
00855   NF->takeName(F);
00856 
00857   // Loop over all of the callers of the function, transforming the call sites
00858   // to pass in a smaller number of arguments into the new function.
00859   //
00860   std::vector<Value*> Args;
00861   while (!F->use_empty()) {
00862     CallSite CS(F->user_back());
00863     Instruction *Call = CS.getInstruction();
00864 
00865     AttributesVec.clear();
00866     const AttributeSet &CallPAL = CS.getAttributes();
00867 
00868     // The call return attributes.
00869     AttributeSet RAttrs = CallPAL.getRetAttributes();
00870 
00871     // Adjust in case the function was changed to return void.
00872     RAttrs =
00873       AttributeSet::get(NF->getContext(), AttributeSet::ReturnIndex,
00874                         AttrBuilder(RAttrs, AttributeSet::ReturnIndex).
00875         removeAttributes(AttributeFuncs::
00876                          typeIncompatible(NF->getReturnType(),
00877                                           AttributeSet::ReturnIndex),
00878                          AttributeSet::ReturnIndex));
00879     if (RAttrs.hasAttributes(AttributeSet::ReturnIndex))
00880       AttributesVec.push_back(AttributeSet::get(NF->getContext(), RAttrs));
00881 
00882     // Declare these outside of the loops, so we can reuse them for the second
00883     // loop, which loops the varargs.
00884     CallSite::arg_iterator I = CS.arg_begin();
00885     unsigned i = 0;
00886     // Loop over those operands, corresponding to the normal arguments to the
00887     // original function, and add those that are still alive.
00888     for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i)
00889       if (ArgAlive[i]) {
00890         Args.push_back(*I);
00891         // Get original parameter attributes, but skip return attributes.
00892         if (CallPAL.hasAttributes(i + 1)) {
00893           AttrBuilder B(CallPAL, i + 1);
00894           // If the return type has changed, then get rid of 'returned' on the
00895           // call site. The alternative is to make all 'returned' attributes on
00896           // call sites keep the return value alive just like 'returned'
00897           // attributes on function declaration but it's less clearly a win
00898           // and this is not an expected case anyway
00899           if (NRetTy != RetTy && B.contains(Attribute::Returned))
00900             B.removeAttribute(Attribute::Returned);
00901           AttributesVec.
00902             push_back(AttributeSet::get(F->getContext(), Args.size(), B));
00903         }
00904       }
00905 
00906     // Push any varargs arguments on the list. Don't forget their attributes.
00907     for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) {
00908       Args.push_back(*I);
00909       if (CallPAL.hasAttributes(i + 1)) {
00910         AttrBuilder B(CallPAL, i + 1);
00911         AttributesVec.
00912           push_back(AttributeSet::get(F->getContext(), Args.size(), B));
00913       }
00914     }
00915 
00916     if (CallPAL.hasAttributes(AttributeSet::FunctionIndex))
00917       AttributesVec.push_back(AttributeSet::get(Call->getContext(),
00918                                                 CallPAL.getFnAttributes()));
00919 
00920     // Reconstruct the AttributesList based on the vector we constructed.
00921     AttributeSet NewCallPAL = AttributeSet::get(F->getContext(), AttributesVec);
00922 
00923     Instruction *New;
00924     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
00925       New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
00926                                Args, "", Call);
00927       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
00928       cast<InvokeInst>(New)->setAttributes(NewCallPAL);
00929     } else {
00930       New = CallInst::Create(NF, Args, "", Call);
00931       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
00932       cast<CallInst>(New)->setAttributes(NewCallPAL);
00933       if (cast<CallInst>(Call)->isTailCall())
00934         cast<CallInst>(New)->setTailCall();
00935     }
00936     New->setDebugLoc(Call->getDebugLoc());
00937 
00938     Args.clear();
00939 
00940     if (!Call->use_empty()) {
00941       if (New->getType() == Call->getType()) {
00942         // Return type not changed? Just replace users then.
00943         Call->replaceAllUsesWith(New);
00944         New->takeName(Call);
00945       } else if (New->getType()->isVoidTy()) {
00946         // Our return value has uses, but they will get removed later on.
00947         // Replace by null for now.
00948         if (!Call->getType()->isX86_MMXTy())
00949           Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
00950       } else {
00951         assert(RetTy->isStructTy() &&
00952                "Return type changed, but not into a void. The old return type"
00953                " must have been a struct!");
00954         Instruction *InsertPt = Call;
00955         if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
00956           BasicBlock::iterator IP = II->getNormalDest()->begin();
00957           while (isa<PHINode>(IP)) ++IP;
00958           InsertPt = IP;
00959         }
00960 
00961         // We used to return a struct. Instead of doing smart stuff with all the
00962         // uses of this struct, we will just rebuild it using
00963         // extract/insertvalue chaining and let instcombine clean that up.
00964         //
00965         // Start out building up our return value from undef
00966         Value *RetVal = UndefValue::get(RetTy);
00967         for (unsigned i = 0; i != RetCount; ++i)
00968           if (NewRetIdxs[i] != -1) {
00969             Value *V;
00970             if (RetTypes.size() > 1)
00971               // We are still returning a struct, so extract the value from our
00972               // return value
00973               V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret",
00974                                            InsertPt);
00975             else
00976               // We are now returning a single element, so just insert that
00977               V = New;
00978             // Insert the value at the old position
00979             RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt);
00980           }
00981         // Now, replace all uses of the old call instruction with the return
00982         // struct we built
00983         Call->replaceAllUsesWith(RetVal);
00984         New->takeName(Call);
00985       }
00986     }
00987 
00988     // Finally, remove the old call from the program, reducing the use-count of
00989     // F.
00990     Call->eraseFromParent();
00991   }
00992 
00993   // Since we have now created the new function, splice the body of the old
00994   // function right into the new function, leaving the old rotting hulk of the
00995   // function empty.
00996   NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
00997 
00998   // Loop over the argument list, transferring uses of the old arguments over to
00999   // the new arguments, also transferring over the names as well.
01000   i = 0;
01001   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
01002        I2 = NF->arg_begin(); I != E; ++I, ++i)
01003     if (ArgAlive[i]) {
01004       // If this is a live argument, move the name and users over to the new
01005       // version.
01006       I->replaceAllUsesWith(I2);
01007       I2->takeName(I);
01008       ++I2;
01009     } else {
01010       // If this argument is dead, replace any uses of it with null constants
01011       // (these are guaranteed to become unused later on).
01012       if (!I->getType()->isX86_MMXTy())
01013         I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
01014     }
01015 
01016   // If we change the return value of the function we must rewrite any return
01017   // instructions.  Check this now.
01018   if (F->getReturnType() != NF->getReturnType())
01019     for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB)
01020       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
01021         Value *RetVal;
01022 
01023         if (NFTy->getReturnType()->isVoidTy()) {
01024           RetVal = nullptr;
01025         } else {
01026           assert (RetTy->isStructTy());
01027           // The original return value was a struct, insert
01028           // extractvalue/insertvalue chains to extract only the values we need
01029           // to return and insert them into our new result.
01030           // This does generate messy code, but we'll let it to instcombine to
01031           // clean that up.
01032           Value *OldRet = RI->getOperand(0);
01033           // Start out building up our return value from undef
01034           RetVal = UndefValue::get(NRetTy);
01035           for (unsigned i = 0; i != RetCount; ++i)
01036             if (NewRetIdxs[i] != -1) {
01037               ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i,
01038                                                               "oldret", RI);
01039               if (RetTypes.size() > 1) {
01040                 // We're still returning a struct, so reinsert the value into
01041                 // our new return value at the new index
01042 
01043                 RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i],
01044                                                  "newret", RI);
01045               } else {
01046                 // We are now only returning a simple value, so just return the
01047                 // extracted value.
01048                 RetVal = EV;
01049               }
01050             }
01051         }
01052         // Replace the return instruction with one returning the new return
01053         // value (possibly 0 if we became void).
01054         ReturnInst::Create(F->getContext(), RetVal, RI);
01055         BB->getInstList().erase(RI);
01056       }
01057 
01058   // Patch the pointer to LLVM function in debug info descriptor.
01059   auto DI = FunctionDIs.find(F);
01060   if (DI != FunctionDIs.end())
01061     DI->second.replaceFunction(NF);
01062 
01063   // Now that the old function is dead, delete it.
01064   F->eraseFromParent();
01065 
01066   return true;
01067 }
01068 
01069 bool DAE::runOnModule(Module &M) {
01070   bool Changed = false;
01071 
01072   // Collect debug info descriptors for functions.
01073   FunctionDIs = makeSubprogramMap(M);
01074 
01075   // First pass: Do a simple check to see if any functions can have their "..."
01076   // removed.  We can do this if they never call va_start.  This loop cannot be
01077   // fused with the next loop, because deleting a function invalidates
01078   // information computed while surveying other functions.
01079   DEBUG(dbgs() << "DAE - Deleting dead varargs\n");
01080   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
01081     Function &F = *I++;
01082     if (F.getFunctionType()->isVarArg())
01083       Changed |= DeleteDeadVarargs(F);
01084   }
01085 
01086   // Second phase:loop through the module, determining which arguments are live.
01087   // We assume all arguments are dead unless proven otherwise (allowing us to
01088   // determine that dead arguments passed into recursive functions are dead).
01089   //
01090   DEBUG(dbgs() << "DAE - Determining liveness\n");
01091   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
01092     SurveyFunction(*I);
01093 
01094   // Now, remove all dead arguments and return values from each function in
01095   // turn.
01096   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
01097     // Increment now, because the function will probably get removed (ie.
01098     // replaced by a new one).
01099     Function *F = I++;
01100     Changed |= RemoveDeadStuffFromFunction(F);
01101   }
01102 
01103   // Finally, look for any unused parameters in functions with non-local
01104   // linkage and replace the passed in parameters with undef.
01105   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
01106     Function& F = *I;
01107 
01108     Changed |= RemoveDeadArgumentsFromCallers(F);
01109   }
01110 
01111   return Changed;
01112 }