← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

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