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