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