lib/Transforms/IPO/DeadArgumentElimination.cpp

   1 //===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass deletes dead arguments from internal functions.  Dead argument
  11 // elimination removes arguments which are directly dead, as well as arguments
  12 // only passed into function calls as dead arguments of other functions.  This
  13 // pass also deletes dead return values in a similar way.
  14 //
  15 // This pass is often useful as a cleanup pass to run after aggressive
  16 // interprocedural passes, which add possibly-dead arguments or return values.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "deadargelim"
  21 #include "llvm/Transforms/IPO.h"
  22 #include "llvm/ADT/DenseMap.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/ADT/StringExtras.h"
  26 #include "llvm/DIBuilder.h"
  27 #include "llvm/DebugInfo.h"
  28 #include "llvm/IR/CallingConv.h"
  29 #include "llvm/IR/Constant.h"
  30 #include "llvm/IR/DerivedTypes.h"
  31 #include "llvm/IR/Instructions.h"
  32 #include "llvm/IR/IntrinsicInst.h"
  33 #include "llvm/IR/LLVMContext.h"
  34 #include "llvm/IR/Module.h"
  35 #include "llvm/Pass.h"
  36 #include "llvm/Support/CallSite.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include "llvm/Transforms/Utils/Local.h"
  40 #include <map>
  41 #include <set>
  42 using namespace llvm;
  43
  44 STATISTIC(NumArgumentsEliminated , "Number of unread args removed");
  45 STATISTIC(NumRetValsEliminated   , "Number of unused return values removed");
  46 STATISTIC(NumParametersEliminated, "Number of parameters replaced with undef");
  47 STATISTIC(NumArgumentsReplacedWithUndef,
  48           "Number of unread args replaced with undef");
  49 namespace {
  50   /// DAE - The dead argument elimination pass.
  51   ///
  52   class DAE : public ModulePass {
  53   public:
  54
  55     /// Struct that represents (part of) either a return value or a function
  56     /// argument.  Used so that arguments and return values can be used
  57     /// interchangeably.
  58     struct RetOrArg {
  59       RetOrArg(const Function *F, unsigned Idx, bool IsArg) : F(F), Idx(Idx),
  60                IsArg(IsArg) {}
  61       const Function *F;
  62       unsigned Idx;
  63       bool IsArg;
  64
  65       /// Make RetOrArg comparable, so we can put it into a map.
  66       bool operator<(const RetOrArg &O) const {
  67         if (F != O.F)
  68           return F < O.F;
  69         else if (Idx != O.Idx)
  70           return Idx < O.Idx;
  71         else
  72           return IsArg < O.IsArg;
  73       }
  74
  75       /// Make RetOrArg comparable, so we can easily iterate the multimap.
  76       bool operator==(const RetOrArg &O) const {
  77         return F == O.F && Idx == O.Idx && IsArg == O.IsArg;
  78       }
  79
  80       std::string getDescription() const {
  81         return std::string((IsArg ? "Argument #" : "Return value #"))
  82                + utostr(Idx) + " of function " + F->getName().str();
  83       }
  84     };
  85
  86     /// Liveness enum - During our initial pass over the program, we determine
  87     /// that things are either alive or maybe alive. We don't mark anything
  88     /// explicitly dead (even if we know they are), since anything not alive
  89     /// with no registered uses (in Uses) will never be marked alive and will
  90     /// thus become dead in the end.
  91     enum Liveness { Live, MaybeLive };
  92
  93     /// Convenience wrapper
  94     RetOrArg CreateRet(const Function *F, unsigned Idx) {
  95       return RetOrArg(F, Idx, false);
  96     }
  97     /// Convenience wrapper
  98     RetOrArg CreateArg(const Function *F, unsigned Idx) {
  99       return RetOrArg(F, Idx, true);
 100     }
 101
 102     typedef std::multimap<RetOrArg, RetOrArg> UseMap;
 103     /// This maps a return value or argument to any MaybeLive return values or
 104     /// arguments it uses. This allows the MaybeLive values to be marked live
 105     /// when any of its users is marked live.
 106     /// For example (indices are left out for clarity):
 107     ///  - Uses[ret F] = ret G
 108     ///    This means that F calls G, and F returns the value returned by G.
 109     ///  - Uses[arg F] = ret G
 110     ///    This means that some function calls G and passes its result as an
 111     ///    argument to F.
 112     ///  - Uses[ret F] = arg F
 113     ///    This means that F returns one of its own arguments.
 114     ///  - Uses[arg F] = arg G
 115     ///    This means that G calls F and passes one of its own (G's) arguments
 116     ///    directly to F.
 117     UseMap Uses;
 118
 119     typedef std::set<RetOrArg> LiveSet;
 120     typedef std::set<const Function*> LiveFuncSet;
 121
 122     /// This set contains all values that have been determined to be live.
 123     LiveSet LiveValues;
 124     /// This set contains all values that are cannot be changed in any way.
 125     LiveFuncSet LiveFunctions;
 126
 127     typedef SmallVector<RetOrArg, 5> UseVector;
 128
 129     // Map each LLVM function to corresponding metadata with debug info. If
 130     // the function is replaced with another one, we should patch the pointer
 131     // to LLVM function in metadata.
 132     // As the code generation for module is finished (and DIBuilder is
 133     // finalized) we assume that subprogram descriptors won't be changed, and
 134     // they are stored in map for short duration anyway.
 135     typedef DenseMap<Function*, DISubprogram> FunctionDIMap;
 136     FunctionDIMap FunctionDIs;
 137
 138   protected:
 139     // DAH uses this to specify a different ID.
 140     explicit DAE(char &ID) : ModulePass(ID) {}
 141
 142   public:
 143     static char ID; // Pass identification, replacement for typeid
 144     DAE() : ModulePass(ID) {
 145       initializeDAEPass(*PassRegistry::getPassRegistry());
 146     }
 147
 148     bool runOnModule(Module &M);
 149
 150     virtual bool ShouldHackArguments() const { return false; }
 151
 152   private:
 153     Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses);
 154     Liveness SurveyUse(Value::const_use_iterator U, UseVector &MaybeLiveUses,
 155                        unsigned RetValNum = 0);
 156     Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses);
 157
 158     void CollectFunctionDIs(Module &M);
 159     void SurveyFunction(const Function &F);
 160     void MarkValue(const RetOrArg &RA, Liveness L,
 161                    const UseVector &MaybeLiveUses);
 162     void MarkLive(const RetOrArg &RA);
 163     void MarkLive(const Function &F);
 164     void PropagateLiveness(const RetOrArg &RA);
 165     bool RemoveDeadStuffFromFunction(Function *F);
 166     bool RemoveDeadParamsFromCallersOf(Function *F);
 167     bool DeleteDeadVarargs(Function &Fn);
 168     bool RemoveDeadArgumentsFromCallers(Function &Fn);
 169   };
 170 }
 171
 172
 173 char DAE::ID = 0;
 174 INITIALIZE_PASS(DAE, "deadargelim", "Dead Argument Elimination", false, false)
 175
 176 namespace {
 177   /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but
 178   /// deletes arguments to functions which are external.  This is only for use
 179   /// by bugpoint.
 180   struct DAH : public DAE {
 181     static char ID;
 182     DAH() : DAE(ID) {}
 183
 184     virtual bool ShouldHackArguments() const { return true; }
 185   };
 186 }
 187
 188 char DAH::ID = 0;
 189 INITIALIZE_PASS(DAH, "deadarghaX0r",
 190                 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",
 191                 false, false)
 192
 193 /// createDeadArgEliminationPass - This pass removes arguments from functions
 194 /// which are not used by the body of the function.
 195 ///
 196 ModulePass *llvm::createDeadArgEliminationPass() { return new DAE(); }
 197 ModulePass *llvm::createDeadArgHackingPass() { return new DAH(); }
 198
 199 /// CollectFunctionDIs - Map each function in the module to its debug info
 200 /// descriptor.
 201 void DAE::CollectFunctionDIs(Module &M) {
 202   FunctionDIs.clear();
 203
 204   for (Module::named_metadata_iterator I = M.named_metadata_begin(),
 205        E = M.named_metadata_end(); I != E; ++I) {
 206     NamedMDNode &NMD = *I;
 207     for (unsigned MDIndex = 0, MDNum = NMD.getNumOperands();
 208          MDIndex < MDNum; ++MDIndex) {
 209       MDNode *Node = NMD.getOperand(MDIndex);
 210       if (!DIDescriptor(Node).isCompileUnit())
 211         continue;
 212       DICompileUnit CU(Node);
 213       const DIArray &SPs = CU.getSubprograms();
 214       for (unsigned SPIndex = 0, SPNum = SPs.getNumElements();
 215            SPIndex < SPNum; ++SPIndex) {
 216         DISubprogram SP(SPs.getElement(SPIndex));
 217         if (!SP.Verify())
 218           continue;
 219         if (Function *F = SP.getFunction())
 220           FunctionDIs[F] = SP;
 221       }
 222     }
 223   }
 224 }
 225
 226 /// DeleteDeadVarargs - If this is an function that takes a ... list, and if
 227 /// llvm.vastart is never called, the varargs list is dead for the function.
 228 bool DAE::DeleteDeadVarargs(Function &Fn) {
 229   assert(Fn.getFunctionType()->isVarArg() && "Function isn't varargs!");
 230   if (Fn.isDeclaration() || !Fn.hasLocalLinkage()) return false;
 231
 232   // Ensure that the function is only directly called.
 233   if (Fn.hasAddressTaken())
 234     return false;
 235
 236   // Okay, we know we can transform this function if safe.  Scan its body
 237   // looking for calls to llvm.vastart.
 238   for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
 239     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
 240       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 241         if (II->getIntrinsicID() == Intrinsic::vastart)
 242           return false;
 243       }
 244     }
 245   }
 246
 247   // If we get here, there are no calls to llvm.vastart in the function body,
 248   // remove the "..." and adjust all the calls.
 249
 250   // Start by computing a new prototype for the function, which is the same as
 251   // the old function, but doesn't have isVarArg set.
 252   FunctionType *FTy = Fn.getFunctionType();
 253
 254   std::vector<Type*> Params(FTy->param_begin(), FTy->param_end());
 255   FunctionType *NFTy = FunctionType::get(FTy->getReturnType(), Params, false);
 256   unsigned NumArgs = Params.size();
 257
 258   // Create the new function body and insert it into the module...
 259   Function *NF = Function::Create(NFTy, Fn.getLinkage());
 260   NF->copyAttributesFrom(&Fn);
 261   Fn.getParent()->getFunctionList().insert(&Fn, NF);
 262   NF->takeName(&Fn);
 263
 264   // Loop over all of the callers of the function, transforming the call sites
 265   // to pass in a smaller number of arguments into the new function.
 266   //
 267   std::vector<Value*> Args;
 268   while (!Fn.use_empty()) {
 269     CallSite CS(Fn.use_back());
 270     Instruction *Call = CS.getInstruction();
 271
 272     // Pass all the same arguments.
 273     Args.assign(CS.arg_begin(), CS.arg_begin() + NumArgs);
 274
 275     // Drop any attributes that were on the vararg arguments.
 276     AttributeSet PAL = CS.getAttributes();
 277     if (!PAL.isEmpty() && PAL.getSlotIndex(PAL.getNumSlots() - 1) > NumArgs) {
 278       SmallVector<AttributeSet, 8> AttributesVec;
 279       for (unsigned i = 0; PAL.getSlotIndex(i) <= NumArgs; ++i)
 280         AttributesVec.push_back(PAL.getSlotAttributes(i));
 281       if (PAL.hasAttributes(AttributeSet::FunctionIndex))
 282         AttributesVec.push_back(AttributeSet::get(Fn.getContext(),
 283                                                   PAL.getFnAttributes()));
 284       PAL = AttributeSet::get(Fn.getContext(), AttributesVec);
 285     }
 286
 287     Instruction *New;
 288     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
 289       New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
 290                                Args, "", Call);
 291       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
 292       cast<InvokeInst>(New)->setAttributes(PAL);
 293     } else {
 294       New = CallInst::Create(NF, Args, "", Call);
 295       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
 296       cast<CallInst>(New)->setAttributes(PAL);
 297       if (cast<CallInst>(Call)->isTailCall())
 298         cast<CallInst>(New)->setTailCall();
 299     }
 300     New->setDebugLoc(Call->getDebugLoc());
 301
 302     Args.clear();
 303
 304     if (!Call->use_empty())
 305       Call->replaceAllUsesWith(New);
 306
 307     New->takeName(Call);
 308
 309     // Finally, remove the old call from the program, reducing the use-count of
 310     // F.
 311     Call->eraseFromParent();
 312   }
 313
 314   // Since we have now created the new function, splice the body of the old
 315   // function right into the new function, leaving the old rotting hulk of the
 316   // function empty.
 317   NF->getBasicBlockList().splice(NF->begin(), Fn.getBasicBlockList());
 318
 319   // Loop over the argument list, transferring uses of the old arguments over to
 320   // the new arguments, also transferring over the names as well.  While we're at
 321   // it, remove the dead arguments from the DeadArguments list.
 322   //
 323   for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(),
 324        I2 = NF->arg_begin(); I != E; ++I, ++I2) {
 325     // Move the name and users over to the new version.
 326     I->replaceAllUsesWith(I2);
 327     I2->takeName(I);
 328   }
 329
 330   // Patch the pointer to LLVM function in debug info descriptor.
 331   FunctionDIMap::iterator DI = FunctionDIs.find(&Fn);
 332   if (DI != FunctionDIs.end())
 333     DI->second.replaceFunction(NF);
 334
 335   // Finally, nuke the old function.
 336   Fn.eraseFromParent();
 337   return true;
 338 }
 339
 340 /// RemoveDeadArgumentsFromCallers - Checks if the given function has any
 341 /// arguments that are unused, and changes the caller parameters to be undefined
 342 /// instead.
 343 bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn)
 344 {
 345   if (Fn.isDeclaration() || Fn.mayBeOverridden())
 346     return false;
 347
 348   // Functions with local linkage should already have been handled.
 349   if (Fn.hasLocalLinkage())
 350     return false;
 351
 352   if (Fn.use_empty())
 353     return false;
 354
 355   SmallVector<unsigned, 8> UnusedArgs;
 356   for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end();
 357        I != E; ++I) {
 358     Argument *Arg = I;
 359
 360     if (Arg->use_empty() && !Arg->hasByValAttr())
 361       UnusedArgs.push_back(Arg->getArgNo());
 362   }
 363
 364   if (UnusedArgs.empty())
 365     return false;
 366
 367   bool Changed = false;
 368
 369   for (Function::use_iterator I = Fn.use_begin(), E = Fn.use_end();
 370        I != E; ++I) {
 371     CallSite CS(*I);
 372     if (!CS || !CS.isCallee(I))
 373       continue;
 374
 375     // Now go through all unused args and replace them with "undef".
 376     for (unsigned I = 0, E = UnusedArgs.size(); I != E; ++I) {
 377       unsigned ArgNo = UnusedArgs[I];
 378
 379       Value *Arg = CS.getArgument(ArgNo);
 380       CS.setArgument(ArgNo, UndefValue::get(Arg->getType()));
 381       ++NumArgumentsReplacedWithUndef;
 382       Changed = true;
 383     }
 384   }
 385
 386   return Changed;
 387 }
 388
 389 /// Convenience function that returns the number of return values. It returns 0
 390 /// for void functions and 1 for functions not returning a struct. It returns
 391 /// the number of struct elements for functions returning a struct.
 392 static unsigned NumRetVals(const Function *F) {
 393   if (F->getReturnType()->isVoidTy())
 394     return 0;
 395   else if (StructType *STy = dyn_cast<StructType>(F->getReturnType()))
 396     return STy->getNumElements();
 397   else
 398     return 1;
 399 }
 400
 401 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not
 402 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined
 403 /// liveness of Use.
 404 DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) {
 405   // We're live if our use or its Function is already marked as live.
 406   if (LiveFunctions.count(Use.F) || LiveValues.count(Use))
 407     return Live;
 408
 409   // We're maybe live otherwise, but remember that we must become live if
 410   // Use becomes live.
 411   MaybeLiveUses.push_back(Use);
 412   return MaybeLive;
 413 }
 414
 415
 416 /// SurveyUse - This looks at a single use of an argument or return value
 417 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses
 418 /// if it causes the used value to become MaybeLive.
 419 ///
 420 /// RetValNum is the return value number to use when this use is used in a
 421 /// return instruction. This is used in the recursion, you should always leave
 422 /// it at 0.
 423 DAE::Liveness DAE::SurveyUse(Value::const_use_iterator U,
 424                              UseVector &MaybeLiveUses, unsigned RetValNum) {
 425     const User *V = *U;
 426     if (const ReturnInst *RI = dyn_cast<ReturnInst>(V)) {
 427       // The value is returned from a function. It's only live when the
 428       // function's return value is live. We use RetValNum here, for the case
 429       // that U is really a use of an insertvalue instruction that uses the
 430       // original Use.
 431       RetOrArg Use = CreateRet(RI->getParent()->getParent(), RetValNum);
 432       // We might be live, depending on the liveness of Use.
 433       return MarkIfNotLive(Use, MaybeLiveUses);
 434     }
 435     if (const InsertValueInst *IV = dyn_cast<InsertValueInst>(V)) {
 436       if (U.getOperandNo() != InsertValueInst::getAggregateOperandIndex()
 437           && IV->hasIndices())
 438         // The use we are examining is inserted into an aggregate. Our liveness
 439         // depends on all uses of that aggregate, but if it is used as a return
 440         // value, only index at which we were inserted counts.
 441         RetValNum = *IV->idx_begin();
 442
 443       // Note that if we are used as the aggregate operand to the insertvalue,
 444       // we don't change RetValNum, but do survey all our uses.
 445
 446       Liveness Result = MaybeLive;
 447       for (Value::const_use_iterator I = IV->use_begin(),
 448            E = V->use_end(); I != E; ++I) {
 449         Result = SurveyUse(I, MaybeLiveUses, RetValNum);
 450         if (Result == Live)
 451           break;
 452       }
 453       return Result;
 454     }
 455
 456     if (ImmutableCallSite CS = V) {
 457       const Function *F = CS.getCalledFunction();
 458       if (F) {
 459         // Used in a direct call.
 460
 461         // Find the argument number. We know for sure that this use is an
 462         // argument, since if it was the function argument this would be an
 463         // indirect call and the we know can't be looking at a value of the
 464         // label type (for the invoke instruction).
 465         unsigned ArgNo = CS.getArgumentNo(U);
 466
 467         if (ArgNo >= F->getFunctionType()->getNumParams())
 468           // The value is passed in through a vararg! Must be live.
 469           return Live;
 470
 471         assert(CS.getArgument(ArgNo)
 472                == CS->getOperand(U.getOperandNo())
 473                && "Argument is not where we expected it");
 474
 475         // Value passed to a normal call. It's only live when the corresponding
 476         // argument to the called function turns out live.
 477         RetOrArg Use = CreateArg(F, ArgNo);
 478         return MarkIfNotLive(Use, MaybeLiveUses);
 479       }
 480     }
 481     // Used in any other way? Value must be live.
 482     return Live;
 483 }
 484
 485 /// SurveyUses - This looks at all the uses of the given value
 486 /// Returns the Liveness deduced from the uses of this value.
 487 ///
 488 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If
 489 /// the result is Live, MaybeLiveUses might be modified but its content should
 490 /// be ignored (since it might not be complete).
 491 DAE::Liveness DAE::SurveyUses(const Value *V, UseVector &MaybeLiveUses) {
 492   // Assume it's dead (which will only hold if there are no uses at all..).
 493   Liveness Result = MaybeLive;
 494   // Check each use.
 495   for (Value::const_use_iterator I = V->use_begin(),
 496        E = V->use_end(); I != E; ++I) {
 497     Result = SurveyUse(I, MaybeLiveUses);
 498     if (Result == Live)
 499       break;
 500   }
 501   return Result;
 502 }
 503
 504 // SurveyFunction - This performs the initial survey of the specified function,
 505 // checking out whether or not it uses any of its incoming arguments or whether
 506 // any callers use the return value.  This fills in the LiveValues set and Uses
 507 // map.
 508 //
 509 // We consider arguments of non-internal functions to be intrinsically alive as
 510 // well as arguments to functions which have their "address taken". Externally
 511 // visible functions are assumed to only have their return values intrinsically
 512 // alive, permitting removal of parameters to unused arguments in callers.
 513 //
 514 void DAE::SurveyFunction(const Function &F) {
 515   unsigned RetCount = NumRetVals(&F);
 516   // Assume all return values are dead
 517   typedef SmallVector<Liveness, 5> RetVals;
 518   RetVals RetValLiveness(RetCount, MaybeLive);
 519
 520   typedef SmallVector<UseVector, 5> RetUses;
 521   // These vectors map each return value to the uses that make it MaybeLive, so
 522   // we can add those to the Uses map if the return value really turns out to be
 523   // MaybeLive. Initialized to a list of RetCount empty lists.
 524   RetUses MaybeLiveRetUses(RetCount);
 525
 526   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 527     if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
 528       if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType()
 529           != F.getFunctionType()->getReturnType()) {
 530         // We don't support old style multiple return values.
 531         MarkLive(F);
 532         return;
 533       }
 534
 535   if (F.hasExternalLinkage() && !F.isDeclaration()) {
 536     DEBUG(dbgs() << "DAE - Intrinsically live return from " << F.getName()
 537                  << "\n");
 538     // Mark the return values alive.
 539     for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i)
 540       MarkLive(CreateRet(&F, i));
 541   } else if (!F.hasLocalLinkage() &&
 542              (!ShouldHackArguments() || F.isIntrinsic())) {
 543     MarkLive(F);
 544     return;
 545   }
 546
 547   DEBUG(dbgs() << "DAE - Inspecting callers for fn: " << F.getName() << "\n");
 548   // Keep track of the number of live retvals, so we can skip checks once all
 549   // of them turn out to be live.
 550   unsigned NumLiveRetVals = 0;
 551   Type *STy = dyn_cast<StructType>(F.getReturnType());
 552   // Loop all uses of the function.
 553   for (Value::const_use_iterator I = F.use_begin(), E = F.use_end();
 554        I != E; ++I) {
 555     // If the function is PASSED IN as an argument, its address has been
 556     // taken.
 557     ImmutableCallSite CS(*I);
 558     if (!CS || !CS.isCallee(I)) {
 559       MarkLive(F);
 560       return;
 561     }
 562
 563     // If this use is anything other than a call site, the function is alive.
 564     const Instruction *TheCall = CS.getInstruction();
 565     if (!TheCall) {   // Not a direct call site?
 566       MarkLive(F);
 567       return;
 568     }
 569
 570     // If we end up here, we are looking at a direct call to our function.
 571
 572     // Now, check how our return value(s) is/are used in this caller. Don't
 573     // bother checking return values if all of them are live already.
 574     if (NumLiveRetVals != RetCount) {
 575       if (STy) {
 576         // Check all uses of the return value.
 577         for (Value::const_use_iterator I = TheCall->use_begin(),
 578              E = TheCall->use_end(); I != E; ++I) {
 579           const ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I);
 580           if (Ext && Ext->hasIndices()) {
 581             // This use uses a part of our return value, survey the uses of
 582             // that part and store the results for this index only.
 583             unsigned Idx = *Ext->idx_begin();
 584             if (RetValLiveness[Idx] != Live) {
 585               RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]);
 586               if (RetValLiveness[Idx] == Live)
 587                 NumLiveRetVals++;
 588             }
 589           } else {
 590             // Used by something else than extractvalue. Mark all return
 591             // values as live.
 592             for (unsigned i = 0; i != RetCount; ++i )
 593               RetValLiveness[i] = Live;
 594             NumLiveRetVals = RetCount;
 595             break;
 596           }
 597         }
 598       } else {
 599         // Single return value
 600         RetValLiveness[0] = SurveyUses(TheCall, MaybeLiveRetUses[0]);
 601         if (RetValLiveness[0] == Live)
 602           NumLiveRetVals = RetCount;
 603       }
 604     }
 605   }
 606
 607   // Now we've inspected all callers, record the liveness of our return values.
 608   for (unsigned i = 0; i != RetCount; ++i)
 609     MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]);
 610
 611   DEBUG(dbgs() << "DAE - Inspecting args for fn: " << F.getName() << "\n");
 612
 613   // Now, check all of our arguments.
 614   unsigned i = 0;
 615   UseVector MaybeLiveArgUses;
 616   for (Function::const_arg_iterator AI = F.arg_begin(),
 617        E = F.arg_end(); AI != E; ++AI, ++i) {
 618     // See what the effect of this use is (recording any uses that cause
 619     // MaybeLive in MaybeLiveArgUses).
 620     Liveness Result = SurveyUses(AI, MaybeLiveArgUses);
 621     // Mark the result.
 622     MarkValue(CreateArg(&F, i), Result, MaybeLiveArgUses);
 623     // Clear the vector again for the next iteration.
 624     MaybeLiveArgUses.clear();
 625   }
 626 }
 627
 628 /// MarkValue - This function marks the liveness of RA depending on L. If L is
 629 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses,
 630 /// such that RA will be marked live if any use in MaybeLiveUses gets marked
 631 /// live later on.
 632 void DAE::MarkValue(const RetOrArg &RA, Liveness L,
 633                     const UseVector &MaybeLiveUses) {
 634   switch (L) {
 635     case Live: MarkLive(RA); break;
 636     case MaybeLive:
 637     {
 638       // Note any uses of this value, so this return value can be
 639       // marked live whenever one of the uses becomes live.
 640       for (UseVector::const_iterator UI = MaybeLiveUses.begin(),
 641            UE = MaybeLiveUses.end(); UI != UE; ++UI)
 642         Uses.insert(std::make_pair(*UI, RA));
 643       break;
 644     }
 645   }
 646 }
 647
 648 /// MarkLive - Mark the given Function as alive, meaning that it cannot be
 649 /// changed in any way. Additionally,
 650 /// mark any values that are used as this function's parameters or by its return
 651 /// values (according to Uses) live as well.
 652 void DAE::MarkLive(const Function &F) {
 653   DEBUG(dbgs() << "DAE - Intrinsically live fn: " << F.getName() << "\n");
 654   // Mark the function as live.
 655   LiveFunctions.insert(&F);
 656   // Mark all arguments as live.
 657   for (unsigned i = 0, e = F.arg_size(); i != e; ++i)
 658     PropagateLiveness(CreateArg(&F, i));
 659   // Mark all return values as live.
 660   for (unsigned i = 0, e = NumRetVals(&F); i != e; ++i)
 661     PropagateLiveness(CreateRet(&F, i));
 662 }
 663
 664 /// MarkLive - Mark the given return value or argument as live. Additionally,
 665 /// mark any values that are used by this value (according to Uses) live as
 666 /// well.
 667 void DAE::MarkLive(const RetOrArg &RA) {
 668   if (LiveFunctions.count(RA.F))
 669     return; // Function was already marked Live.
 670
 671   if (!LiveValues.insert(RA).second)
 672     return; // We were already marked Live.
 673
 674   DEBUG(dbgs() << "DAE - Marking " << RA.getDescription() << " live\n");
 675   PropagateLiveness(RA);
 676 }
 677
 678 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness
 679 /// to any other values it uses (according to Uses).
 680 void DAE::PropagateLiveness(const RetOrArg &RA) {
 681   // We don't use upper_bound (or equal_range) here, because our recursive call
 682   // to ourselves is likely to cause the upper_bound (which is the first value
 683   // not belonging to RA) to become erased and the iterator invalidated.
 684   UseMap::iterator Begin = Uses.lower_bound(RA);
 685   UseMap::iterator E = Uses.end();
 686   UseMap::iterator I;
 687   for (I = Begin; I != E && I->first == RA; ++I)
 688     MarkLive(I->second);
 689
 690   // Erase RA from the Uses map (from the lower bound to wherever we ended up
 691   // after the loop).
 692   Uses.erase(Begin, I);
 693 }
 694
 695 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F
 696 // that are not in LiveValues. Transform the function and all of the callees of
 697 // the function to not have these arguments and return values.
 698 //
 699 bool DAE::RemoveDeadStuffFromFunction(Function *F) {
 700   // Don't modify fully live functions
 701   if (LiveFunctions.count(F))
 702     return false;
 703
 704   // Start by computing a new prototype for the function, which is the same as
 705   // the old function, but has fewer arguments and a different return type.
 706   FunctionType *FTy = F->getFunctionType();
 707   std::vector<Type*> Params;
 708
 709   // Set up to build a new list of parameter attributes.
 710   SmallVector<AttributeSet, 8> AttributesVec;
 711   const AttributeSet &PAL = F->getAttributes();
 712
 713   // Find out the new return value.
 714   Type *RetTy = FTy->getReturnType();
 715   Type *NRetTy = NULL;
 716   unsigned RetCount = NumRetVals(F);
 717
 718   // -1 means unused, other numbers are the new index
 719   SmallVector<int, 5> NewRetIdxs(RetCount, -1);
 720   std::vector<Type*> RetTypes;
 721   if (RetTy->isVoidTy()) {
 722     NRetTy = RetTy;
 723   } else {
 724     StructType *STy = dyn_cast<StructType>(RetTy);
 725     if (STy)
 726       // Look at each of the original return values individually.
 727       for (unsigned i = 0; i != RetCount; ++i) {
 728         RetOrArg Ret = CreateRet(F, i);
 729         if (LiveValues.erase(Ret)) {
 730           RetTypes.push_back(STy->getElementType(i));
 731           NewRetIdxs[i] = RetTypes.size() - 1;
 732         } else {
 733           ++NumRetValsEliminated;
 734           DEBUG(dbgs() << "DAE - Removing return value " << i << " from "
 735                 << F->getName() << "\n");
 736         }
 737       }
 738     else
 739       // We used to return a single value.
 740       if (LiveValues.erase(CreateRet(F, 0))) {
 741         RetTypes.push_back(RetTy);
 742         NewRetIdxs[0] = 0;
 743       } else {
 744         DEBUG(dbgs() << "DAE - Removing return value from " << F->getName()
 745               << "\n");
 746         ++NumRetValsEliminated;
 747       }
 748     if (RetTypes.size() > 1)
 749       // More than one return type? Return a struct with them. Also, if we used
 750       // to return a struct and didn't change the number of return values,
 751       // return a struct again. This prevents changing {something} into
 752       // something and {} into void.
 753       // Make the new struct packed if we used to return a packed struct
 754       // already.
 755       NRetTy = StructType::get(STy->getContext(), RetTypes, STy->isPacked());
 756     else if (RetTypes.size() == 1)
 757       // One return type? Just a simple value then, but only if we didn't use to
 758       // return a struct with that simple value before.
 759       NRetTy = RetTypes.front();
 760     else if (RetTypes.size() == 0)
 761       // No return types? Make it void, but only if we didn't use to return {}.
 762       NRetTy = Type::getVoidTy(F->getContext());
 763   }
 764
 765   assert(NRetTy && "No new return type found?");
 766
 767   // The existing function return attributes.
 768   AttributeSet RAttrs = PAL.getRetAttributes();
 769
 770   // Remove any incompatible attributes, but only if we removed all return
 771   // values. Otherwise, ensure that we don't have any conflicting attributes
 772   // here. Currently, this should not be possible, but special handling might be
 773   // required when new return value attributes are added.
 774   if (NRetTy->isVoidTy())
 775     RAttrs =
 776       AttributeSet::get(NRetTy->getContext(), AttributeSet::ReturnIndex,
 777                         AttrBuilder(RAttrs, AttributeSet::ReturnIndex).
 778          removeAttributes(AttributeFuncs::
 779                           typeIncompatible(NRetTy, AttributeSet::ReturnIndex),
 780                           AttributeSet::ReturnIndex));
 781   else
 782     assert(!AttrBuilder(RAttrs, AttributeSet::ReturnIndex).
 783              hasAttributes(AttributeFuncs::
 784                            typeIncompatible(NRetTy, AttributeSet::ReturnIndex),
 785                            AttributeSet::ReturnIndex) &&
 786            "Return attributes no longer compatible?");
 787
 788   if (RAttrs.hasAttributes(AttributeSet::ReturnIndex))
 789     AttributesVec.push_back(AttributeSet::get(NRetTy->getContext(), RAttrs));
 790
 791   // Remember which arguments are still alive.
 792   SmallVector<bool, 10> ArgAlive(FTy->getNumParams(), false);
 793   // Construct the new parameter list from non-dead arguments. Also construct
 794   // a new set of parameter attributes to correspond. Skip the first parameter
 795   // attribute, since that belongs to the return value.
 796   unsigned i = 0;
 797   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
 798        I != E; ++I, ++i) {
 799     RetOrArg Arg = CreateArg(F, i);
 800     if (LiveValues.erase(Arg)) {
 801       Params.push_back(I->getType());
 802       ArgAlive[i] = true;
 803
 804       // Get the original parameter attributes (skipping the first one, that is
 805       // for the return value.
 806       if (PAL.hasAttributes(i + 1)) {
 807         AttrBuilder B(PAL, i + 1);
 808         AttributesVec.
 809           push_back(AttributeSet::get(F->getContext(), Params.size(), B));
 810       }
 811     } else {
 812       ++NumArgumentsEliminated;
 813       DEBUG(dbgs() << "DAE - Removing argument " << i << " (" << I->getName()
 814             << ") from " << F->getName() << "\n");
 815     }
 816   }
 817
 818   if (PAL.hasAttributes(AttributeSet::FunctionIndex))
 819     AttributesVec.push_back(AttributeSet::get(F->getContext(),
 820                                               PAL.getFnAttributes()));
 821
 822   // Reconstruct the AttributesList based on the vector we constructed.
 823   AttributeSet NewPAL = AttributeSet::get(F->getContext(), AttributesVec);
 824
 825   // Create the new function type based on the recomputed parameters.
 826   FunctionType *NFTy = FunctionType::get(NRetTy, Params, FTy->isVarArg());
 827
 828   // No change?
 829   if (NFTy == FTy)
 830     return false;
 831
 832   // Create the new function body and insert it into the module...
 833   Function *NF = Function::Create(NFTy, F->getLinkage());
 834   NF->copyAttributesFrom(F);
 835   NF->setAttributes(NewPAL);
 836   // Insert the new function before the old function, so we won't be processing
 837   // it again.
 838   F->getParent()->getFunctionList().insert(F, NF);
 839   NF->takeName(F);
 840
 841   // Loop over all of the callers of the function, transforming the call sites
 842   // to pass in a smaller number of arguments into the new function.
 843   //
 844   std::vector<Value*> Args;
 845   while (!F->use_empty()) {
 846     CallSite CS(F->use_back());
 847     Instruction *Call = CS.getInstruction();
 848
 849     AttributesVec.clear();
 850     const AttributeSet &CallPAL = CS.getAttributes();
 851
 852     // The call return attributes.
 853     AttributeSet RAttrs = CallPAL.getRetAttributes();
 854
 855     // Adjust in case the function was changed to return void.
 856     RAttrs =
 857       AttributeSet::get(NF->getContext(), AttributeSet::ReturnIndex,
 858                         AttrBuilder(RAttrs, AttributeSet::ReturnIndex).
 859         removeAttributes(AttributeFuncs::
 860                          typeIncompatible(NF->getReturnType(),
 861                                           AttributeSet::ReturnIndex),
 862                          AttributeSet::ReturnIndex));
 863     if (RAttrs.hasAttributes(AttributeSet::ReturnIndex))
 864       AttributesVec.push_back(AttributeSet::get(NF->getContext(), RAttrs));
 865
 866     // Declare these outside of the loops, so we can reuse them for the second
 867     // loop, which loops the varargs.
 868     CallSite::arg_iterator I = CS.arg_begin();
 869     unsigned i = 0;
 870     // Loop over those operands, corresponding to the normal arguments to the
 871     // original function, and add those that are still alive.
 872     for (unsigned e = FTy->getNumParams(); i != e; ++I, ++i)
 873       if (ArgAlive[i]) {
 874         Args.push_back(*I);
 875         // Get original parameter attributes, but skip return attributes.
 876         if (CallPAL.hasAttributes(i + 1)) {
 877           AttrBuilder B(CallPAL, i + 1);
 878           AttributesVec.
 879             push_back(AttributeSet::get(F->getContext(), Args.size(), B));
 880         }
 881       }
 882
 883     // Push any varargs arguments on the list. Don't forget their attributes.
 884     for (CallSite::arg_iterator E = CS.arg_end(); I != E; ++I, ++i) {
 885       Args.push_back(*I);
 886       if (CallPAL.hasAttributes(i + 1)) {
 887         AttrBuilder B(CallPAL, i + 1);
 888         AttributesVec.
 889           push_back(AttributeSet::get(F->getContext(), Args.size(), B));
 890       }
 891     }
 892
 893     if (CallPAL.hasAttributes(AttributeSet::FunctionIndex))
 894       AttributesVec.push_back(AttributeSet::get(Call->getContext(),
 895                                                 CallPAL.getFnAttributes()));
 896
 897     // Reconstruct the AttributesList based on the vector we constructed.
 898     AttributeSet NewCallPAL = AttributeSet::get(F->getContext(), AttributesVec);
 899
 900     Instruction *New;
 901     if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
 902       New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
 903                                Args, "", Call);
 904       cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
 905       cast<InvokeInst>(New)->setAttributes(NewCallPAL);
 906     } else {
 907       New = CallInst::Create(NF, Args, "", Call);
 908       cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
 909       cast<CallInst>(New)->setAttributes(NewCallPAL);
 910       if (cast<CallInst>(Call)->isTailCall())
 911         cast<CallInst>(New)->setTailCall();
 912     }
 913     New->setDebugLoc(Call->getDebugLoc());
 914
 915     Args.clear();
 916
 917     if (!Call->use_empty()) {
 918       if (New->getType() == Call->getType()) {
 919         // Return type not changed? Just replace users then.
 920         Call->replaceAllUsesWith(New);
 921         New->takeName(Call);
 922       } else if (New->getType()->isVoidTy()) {
 923         // Our return value has uses, but they will get removed later on.
 924         // Replace by null for now.
 925         if (!Call->getType()->isX86_MMXTy())
 926           Call->replaceAllUsesWith(Constant::getNullValue(Call->getType()));
 927       } else {
 928         assert(RetTy->isStructTy() &&
 929                "Return type changed, but not into a void. The old return type"
 930                " must have been a struct!");
 931         Instruction *InsertPt = Call;
 932         if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
 933           BasicBlock::iterator IP = II->getNormalDest()->begin();
 934           while (isa<PHINode>(IP)) ++IP;
 935           InsertPt = IP;
 936         }
 937
 938         // We used to return a struct. Instead of doing smart stuff with all the
 939         // uses of this struct, we will just rebuild it using
 940         // extract/insertvalue chaining and let instcombine clean that up.
 941         //
 942         // Start out building up our return value from undef
 943         Value *RetVal = UndefValue::get(RetTy);
 944         for (unsigned i = 0; i != RetCount; ++i)
 945           if (NewRetIdxs[i] != -1) {
 946             Value *V;
 947             if (RetTypes.size() > 1)
 948               // We are still returning a struct, so extract the value from our
 949               // return value
 950               V = ExtractValueInst::Create(New, NewRetIdxs[i], "newret",
 951                                            InsertPt);
 952             else
 953               // We are now returning a single element, so just insert that
 954               V = New;
 955             // Insert the value at the old position
 956             RetVal = InsertValueInst::Create(RetVal, V, i, "oldret", InsertPt);
 957           }
 958         // Now, replace all uses of the old call instruction with the return
 959         // struct we built
 960         Call->replaceAllUsesWith(RetVal);
 961         New->takeName(Call);
 962       }
 963     }
 964
 965     // Finally, remove the old call from the program, reducing the use-count of
 966     // F.
 967     Call->eraseFromParent();
 968   }
 969
 970   // Since we have now created the new function, splice the body of the old
 971   // function right into the new function, leaving the old rotting hulk of the
 972   // function empty.
 973   NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
 974
 975   // Loop over the argument list, transferring uses of the old arguments over to
 976   // the new arguments, also transferring over the names as well.
 977   i = 0;
 978   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
 979        I2 = NF->arg_begin(); I != E; ++I, ++i)
 980     if (ArgAlive[i]) {
 981       // If this is a live argument, move the name and users over to the new
 982       // version.
 983       I->replaceAllUsesWith(I2);
 984       I2->takeName(I);
 985       ++I2;
 986     } else {
 987       // If this argument is dead, replace any uses of it with null constants
 988       // (these are guaranteed to become unused later on).
 989       if (!I->getType()->isX86_MMXTy())
 990         I->replaceAllUsesWith(Constant::getNullValue(I->getType()));
 991     }
 992
 993   // If we change the return value of the function we must rewrite any return
 994   // instructions.  Check this now.
 995   if (F->getReturnType() != NF->getReturnType())
 996     for (Function::iterator BB = NF->begin(), E = NF->end(); BB != E; ++BB)
 997       if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
 998         Value *RetVal;
 999
1000         if (NFTy->getReturnType()->isVoidTy()) {
1001           RetVal = 0;
1002         } else {
1003           assert (RetTy->isStructTy());
1004           // The original return value was a struct, insert
1005           // extractvalue/insertvalue chains to extract only the values we need
1006           // to return and insert them into our new result.
1007           // This does generate messy code, but we'll let it to instcombine to
1008           // clean that up.
1009           Value *OldRet = RI->getOperand(0);
1010           // Start out building up our return value from undef
1011           RetVal = UndefValue::get(NRetTy);
1012           for (unsigned i = 0; i != RetCount; ++i)
1013             if (NewRetIdxs[i] != -1) {
1014               ExtractValueInst *EV = ExtractValueInst::Create(OldRet, i,
1015                                                               "oldret", RI);
1016               if (RetTypes.size() > 1) {
1017                 // We're still returning a struct, so reinsert the value into
1018                 // our new return value at the new index
1019
1020                 RetVal = InsertValueInst::Create(RetVal, EV, NewRetIdxs[i],
1021                                                  "newret", RI);
1022               } else {
1023                 // We are now only returning a simple value, so just return the
1024                 // extracted value.
1025                 RetVal = EV;
1026               }
1027             }
1028         }
1029         // Replace the return instruction with one returning the new return
1030         // value (possibly 0 if we became void).
1031         ReturnInst::Create(F->getContext(), RetVal, RI);
1032         BB->getInstList().erase(RI);
1033       }
1034
1035   // Patch the pointer to LLVM function in debug info descriptor.
1036   FunctionDIMap::iterator DI = FunctionDIs.find(F);
1037   if (DI != FunctionDIs.end())
1038     DI->second.replaceFunction(NF);
1039
1040   // Now that the old function is dead, delete it.
1041   F->eraseFromParent();
1042
1043   return true;
1044 }
1045
1046 // RemoveDeadParamsFromCallersOf - Replace any parameters that are never used
1047 // by the callee with undef.
1048 //
1049 bool DAE::RemoveDeadParamsFromCallersOf(Function *F) {
1050   // Don't modify fully live functions
1051   if (LiveFunctions.count(F))
1052     return false;
1053
1054   // Make a list of the dead arguments.
1055   SmallVector<int, 10> ArgDead;
1056   unsigned i = 0;
1057   for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
1058        I != E; ++I, ++i) {
1059     RetOrArg Arg = CreateArg(F, i);
1060     if (!LiveValues.count(Arg))
1061       ArgDead.push_back(i);
1062   }
1063   if (ArgDead.empty())
1064     return false;
1065
1066   bool MadeChange = false;
1067   for (Function::use_iterator I = F->use_begin(), E = F->use_end();
1068        I != E; ++I) {
1069     CallSite CS = CallSite(*I);
1070     if (CS.getInstruction() && CS.isCallee(I)) {
1071       for (unsigned i = 0, e = ArgDead.size(); i != e; ++i) {
1072         Value *A = CS.getArgument(ArgDead[i]);
1073         if (!isa<UndefValue>(A)) {
1074           ++NumParametersEliminated;
1075           MadeChange = true;
1076           CS.setArgument(ArgDead[i], UndefValue::get(A->getType()));
1077           RecursivelyDeleteTriviallyDeadInstructions(A);
1078         }
1079       }
1080     }
1081   }
1082
1083   return MadeChange;
1084 }
1085
1086 bool DAE::runOnModule(Module &M) {
1087   bool Changed = false;
1088
1089   // Collect debug info descriptors for functions.
1090   CollectFunctionDIs(M);
1091
1092   // First pass: Do a simple check to see if any functions can have their "..."
1093   // removed.  We can do this if they never call va_start.  This loop cannot be
1094   // fused with the next loop, because deleting a function invalidates
1095   // information computed while surveying other functions.
1096   DEBUG(dbgs() << "DAE - Deleting dead varargs\n");
1097   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
1098     Function &F = *I++;
1099     if (F.getFunctionType()->isVarArg())
1100       Changed |= DeleteDeadVarargs(F);
1101   }
1102
1103   // Second phase:loop through the module, determining which arguments are live.
1104   // We assume all arguments are dead unless proven otherwise (allowing us to
1105   // determine that dead arguments passed into recursive functions are dead).
1106   //
1107   DEBUG(dbgs() << "DAE - Determining liveness\n");
1108   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1109     SurveyFunction(*I);
1110
1111   // Now, remove all dead arguments and return values from each function in
1112   // turn.
1113   for (Module::iterator I = M.begin(), E = M.end(); I != E; ) {
1114     // Increment now, because the function will probably get removed (ie.
1115     // replaced by a new one).
1116     Function *F = I++;
1117     if (F->hasExternalLinkage() && !F->isDeclaration())
1118       Changed |= RemoveDeadParamsFromCallersOf(F);
1119     else
1120       Changed |= RemoveDeadStuffFromFunction(F);
1121   }
1122
1123   // Finally, look for any unused parameters in functions with non-local
1124   // linkage and replace the passed in parameters with undef.
1125   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
1126     Function& F = *I;
1127
1128     Changed |= RemoveDeadArgumentsFromCallers(F);
1129   }
1130
1131   return Changed;
1132 }