1 //===-- DeadArgumentElimination.cpp - Eliminate dead arguments ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
18 //===----------------------------------------------------------------------===//
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"
40 STATISTIC(NumArgumentsEliminated
, "Number of unread args removed");
41 STATISTIC(NumRetValsEliminated
, "Number of unused return values removed");
44 /// DAE - The dead argument elimination pass.
46 class DAE
: public ModulePass
{
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
53 RetOrArg(const Function
*F
, unsigned Idx
, bool IsArg
) : F(F
), Idx(Idx
),
59 /// Make RetOrArg comparable, so we can put it into a map.
60 bool operator<(const RetOrArg
&O
) const {
63 else if (Idx
!= O
.Idx
)
66 return IsArg
< O
.IsArg
;
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
;
74 std::string
getDescription() const {
75 return std::string((IsArg
? "Argument #" : "Return value #"))
76 + utostr(Idx
) + " of function " + F
->getNameStr();
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
};
87 /// Convenience wrapper
88 RetOrArg
CreateRet(const Function
*F
, unsigned Idx
) {
89 return RetOrArg(F
, Idx
, false);
91 /// Convenience wrapper
92 RetOrArg
CreateArg(const Function
*F
, unsigned Idx
) {
93 return RetOrArg(F
, Idx
, true);
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
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
113 typedef std::set
<RetOrArg
> LiveSet
;
114 typedef std::set
<const Function
*> LiveFuncSet
;
116 /// This set contains all values that have been determined to be live.
118 /// This set contains all values that are cannot be changed in any way.
119 LiveFuncSet LiveFunctions
;
121 typedef SmallVector
<RetOrArg
, 5> UseVector
;
124 // DAH uses this to specify a different ID.
125 explicit DAE(char &ID
) : ModulePass(ID
) {}
128 static char ID
; // Pass identification, replacement for typeid
129 DAE() : ModulePass(ID
) {}
131 bool runOnModule(Module
&M
);
133 virtual bool ShouldHackArguments() const { return false; }
136 Liveness
MarkIfNotLive(RetOrArg Use
, UseVector
&MaybeLiveUses
);
137 Liveness
SurveyUse(Value::const_use_iterator U
, UseVector
&MaybeLiveUses
,
138 unsigned RetValNum
= 0);
139 Liveness
SurveyUses(const Value
*V
, UseVector
&MaybeLiveUses
);
141 void SurveyFunction(const Function
&F
);
142 void MarkValue(const RetOrArg
&RA
, Liveness L
,
143 const UseVector
&MaybeLiveUses
);
144 void MarkLive(const RetOrArg
&RA
);
145 void MarkLive(const Function
&F
);
146 void PropagateLiveness(const RetOrArg
&RA
);
147 bool RemoveDeadStuffFromFunction(Function
*F
);
148 bool DeleteDeadVarargs(Function
&Fn
);
154 INITIALIZE_PASS(DAE
, "deadargelim", "Dead Argument Elimination", false, false);
157 /// DAH - DeadArgumentHacking pass - Same as dead argument elimination, but
158 /// deletes arguments to functions which are external. This is only for use
160 struct DAH
: public DAE
{
164 virtual bool ShouldHackArguments() const { return true; }
169 INITIALIZE_PASS(DAH
, "deadarghaX0r",
170 "Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE)",
173 /// createDeadArgEliminationPass - This pass removes arguments from functions
174 /// which are not used by the body of the function.
176 ModulePass
*llvm::createDeadArgEliminationPass() { return new DAE(); }
177 ModulePass
*llvm::createDeadArgHackingPass() { return new DAH(); }
179 /// DeleteDeadVarargs - If this is an function that takes a ... list, and if
180 /// llvm.vastart is never called, the varargs list is dead for the function.
181 bool DAE::DeleteDeadVarargs(Function
&Fn
) {
182 assert(Fn
.getFunctionType()->isVarArg() && "Function isn't varargs!");
183 if (Fn
.isDeclaration() || !Fn
.hasLocalLinkage()) return false;
185 // Ensure that the function is only directly called.
186 if (Fn
.hasAddressTaken())
189 // Okay, we know we can transform this function if safe. Scan its body
190 // looking for calls to llvm.vastart.
191 for (Function::iterator BB
= Fn
.begin(), E
= Fn
.end(); BB
!= E
; ++BB
) {
192 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->end(); I
!= E
; ++I
) {
193 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(I
)) {
194 if (II
->getIntrinsicID() == Intrinsic::vastart
)
200 // If we get here, there are no calls to llvm.vastart in the function body,
201 // remove the "..." and adjust all the calls.
203 // Start by computing a new prototype for the function, which is the same as
204 // the old function, but doesn't have isVarArg set.
205 const FunctionType
*FTy
= Fn
.getFunctionType();
207 std::vector
<const Type
*> Params(FTy
->param_begin(), FTy
->param_end());
208 FunctionType
*NFTy
= FunctionType::get(FTy
->getReturnType(),
210 unsigned NumArgs
= Params
.size();
212 // Create the new function body and insert it into the module...
213 Function
*NF
= Function::Create(NFTy
, Fn
.getLinkage());
214 NF
->copyAttributesFrom(&Fn
);
215 Fn
.getParent()->getFunctionList().insert(&Fn
, NF
);
218 // Loop over all of the callers of the function, transforming the call sites
219 // to pass in a smaller number of arguments into the new function.
221 std::vector
<Value
*> Args
;
222 while (!Fn
.use_empty()) {
223 CallSite
CS(Fn
.use_back());
224 Instruction
*Call
= CS
.getInstruction();
226 // Pass all the same arguments.
227 Args
.assign(CS
.arg_begin(), CS
.arg_begin() + NumArgs
);
229 // Drop any attributes that were on the vararg arguments.
230 AttrListPtr PAL
= CS
.getAttributes();
231 if (!PAL
.isEmpty() && PAL
.getSlot(PAL
.getNumSlots() - 1).Index
> NumArgs
) {
232 SmallVector
<AttributeWithIndex
, 8> AttributesVec
;
233 for (unsigned i
= 0; PAL
.getSlot(i
).Index
<= NumArgs
; ++i
)
234 AttributesVec
.push_back(PAL
.getSlot(i
));
235 if (Attributes FnAttrs
= PAL
.getFnAttributes())
236 AttributesVec
.push_back(AttributeWithIndex::get(~0, FnAttrs
));
237 PAL
= AttrListPtr::get(AttributesVec
.begin(), AttributesVec
.end());
241 if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(Call
)) {
242 New
= InvokeInst::Create(NF
, II
->getNormalDest(), II
->getUnwindDest(),
243 Args
.begin(), Args
.end(), "", Call
);
244 cast
<InvokeInst
>(New
)->setCallingConv(CS
.getCallingConv());
245 cast
<InvokeInst
>(New
)->setAttributes(PAL
);
247 New
= CallInst::Create(NF
, Args
.begin(), Args
.end(), "", Call
);
248 cast
<CallInst
>(New
)->setCallingConv(CS
.getCallingConv());
249 cast
<CallInst
>(New
)->setAttributes(PAL
);
250 if (cast
<CallInst
>(Call
)->isTailCall())
251 cast
<CallInst
>(New
)->setTailCall();
253 New
->setDebugLoc(Call
->getDebugLoc());
257 if (!Call
->use_empty())
258 Call
->replaceAllUsesWith(New
);
262 // Finally, remove the old call from the program, reducing the use-count of
264 Call
->eraseFromParent();
267 // Since we have now created the new function, splice the body of the old
268 // function right into the new function, leaving the old rotting hulk of the
270 NF
->getBasicBlockList().splice(NF
->begin(), Fn
.getBasicBlockList());
272 // Loop over the argument list, transfering uses of the old arguments over to
273 // the new arguments, also transfering over the names as well. While we're at
274 // it, remove the dead arguments from the DeadArguments list.
276 for (Function::arg_iterator I
= Fn
.arg_begin(), E
= Fn
.arg_end(),
277 I2
= NF
->arg_begin(); I
!= E
; ++I
, ++I2
) {
278 // Move the name and users over to the new version.
279 I
->replaceAllUsesWith(I2
);
283 // Finally, nuke the old function.
284 Fn
.eraseFromParent();
288 /// Convenience function that returns the number of return values. It returns 0
289 /// for void functions and 1 for functions not returning a struct. It returns
290 /// the number of struct elements for functions returning a struct.
291 static unsigned NumRetVals(const Function
*F
) {
292 if (F
->getReturnType()->isVoidTy())
294 else if (const StructType
*STy
= dyn_cast
<StructType
>(F
->getReturnType()))
295 return STy
->getNumElements();
300 /// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not
301 /// live, it adds Use to the MaybeLiveUses argument. Returns the determined
303 DAE::Liveness
DAE::MarkIfNotLive(RetOrArg Use
, UseVector
&MaybeLiveUses
) {
304 // We're live if our use or its Function is already marked as live.
305 if (LiveFunctions
.count(Use
.F
) || LiveValues
.count(Use
))
308 // We're maybe live otherwise, but remember that we must become live if
310 MaybeLiveUses
.push_back(Use
);
315 /// SurveyUse - This looks at a single use of an argument or return value
316 /// and determines if it should be alive or not. Adds this use to MaybeLiveUses
317 /// if it causes the used value to become MaybeLive.
319 /// RetValNum is the return value number to use when this use is used in a
320 /// return instruction. This is used in the recursion, you should always leave
322 DAE::Liveness
DAE::SurveyUse(Value::const_use_iterator U
,
323 UseVector
&MaybeLiveUses
, unsigned RetValNum
) {
325 if (const ReturnInst
*RI
= dyn_cast
<ReturnInst
>(V
)) {
326 // The value is returned from a function. It's only live when the
327 // function's return value is live. We use RetValNum here, for the case
328 // that U is really a use of an insertvalue instruction that uses the
330 RetOrArg Use
= CreateRet(RI
->getParent()->getParent(), RetValNum
);
331 // We might be live, depending on the liveness of Use.
332 return MarkIfNotLive(Use
, MaybeLiveUses
);
334 if (const InsertValueInst
*IV
= dyn_cast
<InsertValueInst
>(V
)) {
335 if (U
.getOperandNo() != InsertValueInst::getAggregateOperandIndex()
337 // The use we are examining is inserted into an aggregate. Our liveness
338 // depends on all uses of that aggregate, but if it is used as a return
339 // value, only index at which we were inserted counts.
340 RetValNum
= *IV
->idx_begin();
342 // Note that if we are used as the aggregate operand to the insertvalue,
343 // we don't change RetValNum, but do survey all our uses.
345 Liveness Result
= MaybeLive
;
346 for (Value::const_use_iterator I
= IV
->use_begin(),
347 E
= V
->use_end(); I
!= E
; ++I
) {
348 Result
= SurveyUse(I
, MaybeLiveUses
, RetValNum
);
355 if (ImmutableCallSite CS
= V
) {
356 const Function
*F
= CS
.getCalledFunction();
358 // Used in a direct call.
360 // Find the argument number. We know for sure that this use is an
361 // argument, since if it was the function argument this would be an
362 // indirect call and the we know can't be looking at a value of the
363 // label type (for the invoke instruction).
364 unsigned ArgNo
= CS
.getArgumentNo(U
);
366 if (ArgNo
>= F
->getFunctionType()->getNumParams())
367 // The value is passed in through a vararg! Must be live.
370 assert(CS
.getArgument(ArgNo
)
371 == CS
->getOperand(U
.getOperandNo())
372 && "Argument is not where we expected it");
374 // Value passed to a normal call. It's only live when the corresponding
375 // argument to the called function turns out live.
376 RetOrArg Use
= CreateArg(F
, ArgNo
);
377 return MarkIfNotLive(Use
, MaybeLiveUses
);
380 // Used in any other way? Value must be live.
384 /// SurveyUses - This looks at all the uses of the given value
385 /// Returns the Liveness deduced from the uses of this value.
387 /// Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses. If
388 /// the result is Live, MaybeLiveUses might be modified but its content should
389 /// be ignored (since it might not be complete).
390 DAE::Liveness
DAE::SurveyUses(const Value
*V
, UseVector
&MaybeLiveUses
) {
391 // Assume it's dead (which will only hold if there are no uses at all..).
392 Liveness Result
= MaybeLive
;
394 for (Value::const_use_iterator I
= V
->use_begin(),
395 E
= V
->use_end(); I
!= E
; ++I
) {
396 Result
= SurveyUse(I
, MaybeLiveUses
);
403 // SurveyFunction - This performs the initial survey of the specified function,
404 // checking out whether or not it uses any of its incoming arguments or whether
405 // any callers use the return value. This fills in the LiveValues set and Uses
408 // We consider arguments of non-internal functions to be intrinsically alive as
409 // well as arguments to functions which have their "address taken".
411 void DAE::SurveyFunction(const Function
&F
) {
412 unsigned RetCount
= NumRetVals(&F
);
413 // Assume all return values are dead
414 typedef SmallVector
<Liveness
, 5> RetVals
;
415 RetVals
RetValLiveness(RetCount
, MaybeLive
);
417 typedef SmallVector
<UseVector
, 5> RetUses
;
418 // These vectors map each return value to the uses that make it MaybeLive, so
419 // we can add those to the Uses map if the return value really turns out to be
420 // MaybeLive. Initialized to a list of RetCount empty lists.
421 RetUses
MaybeLiveRetUses(RetCount
);
423 for (Function::const_iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
; ++BB
)
424 if (const ReturnInst
*RI
= dyn_cast
<ReturnInst
>(BB
->getTerminator()))
425 if (RI
->getNumOperands() != 0 && RI
->getOperand(0)->getType()
426 != F
.getFunctionType()->getReturnType()) {
427 // We don't support old style multiple return values.
432 if (!F
.hasLocalLinkage() && (!ShouldHackArguments() || F
.isIntrinsic())) {
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::const_use_iterator I
= F
.use_begin(), E
= F
.use_end();
445 // If the function is PASSED IN as an argument, its address has been
447 ImmutableCallSite
CS(*I
);
448 if (!CS
|| !CS
.isCallee(I
)) {
453 // If this use is anything other than a call site, the function is alive.
454 const Instruction
*TheCall
= CS
.getInstruction();
455 if (!TheCall
) { // Not a direct call site?
460 // If we end up here, we are looking at a direct call to our function.
462 // Now, check how our return value(s) is/are used in this caller. Don't
463 // bother checking return values if all of them are live already.
464 if (NumLiveRetVals
!= RetCount
) {
466 // Check all uses of the return value.
467 for (Value::const_use_iterator I
= TheCall
->use_begin(),
468 E
= TheCall
->use_end(); I
!= E
; ++I
) {
469 const ExtractValueInst
*Ext
= dyn_cast
<ExtractValueInst
>(*I
);
470 if (Ext
&& Ext
->hasIndices()) {
471 // This use uses a part of our return value, survey the uses of
472 // that part and store the results for this index only.
473 unsigned Idx
= *Ext
->idx_begin();
474 if (RetValLiveness
[Idx
] != Live
) {
475 RetValLiveness
[Idx
] = SurveyUses(Ext
, MaybeLiveRetUses
[Idx
]);
476 if (RetValLiveness
[Idx
] == Live
)
480 // Used by something else than extractvalue. Mark all return
482 for (unsigned i
= 0; i
!= RetCount
; ++i
)
483 RetValLiveness
[i
] = Live
;
484 NumLiveRetVals
= RetCount
;
489 // Single return value
490 RetValLiveness
[0] = SurveyUses(TheCall
, MaybeLiveRetUses
[0]);
491 if (RetValLiveness
[0] == Live
)
492 NumLiveRetVals
= RetCount
;
497 // Now we've inspected all callers, record the liveness of our return values.
498 for (unsigned i
= 0; i
!= RetCount
; ++i
)
499 MarkValue(CreateRet(&F
, i
), RetValLiveness
[i
], MaybeLiveRetUses
[i
]);
501 DEBUG(dbgs() << "DAE - Inspecting args for fn: " << F
.getName() << "\n");
503 // Now, check all of our arguments.
505 UseVector MaybeLiveArgUses
;
506 for (Function::const_arg_iterator AI
= F
.arg_begin(),
507 E
= F
.arg_end(); AI
!= E
; ++AI
, ++i
) {
508 // See what the effect of this use is (recording any uses that cause
509 // MaybeLive in MaybeLiveArgUses).
510 Liveness Result
= SurveyUses(AI
, MaybeLiveArgUses
);
512 MarkValue(CreateArg(&F
, i
), Result
, MaybeLiveArgUses
);
513 // Clear the vector again for the next iteration.
514 MaybeLiveArgUses
.clear();
518 /// MarkValue - This function marks the liveness of RA depending on L. If L is
519 /// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses,
520 /// such that RA will be marked live if any use in MaybeLiveUses gets marked
522 void DAE::MarkValue(const RetOrArg
&RA
, Liveness L
,
523 const UseVector
&MaybeLiveUses
) {
525 case Live
: MarkLive(RA
); break;
528 // Note any uses of this value, so this return value can be
529 // marked live whenever one of the uses becomes live.
530 for (UseVector::const_iterator UI
= MaybeLiveUses
.begin(),
531 UE
= MaybeLiveUses
.end(); UI
!= UE
; ++UI
)
532 Uses
.insert(std::make_pair(*UI
, RA
));
538 /// MarkLive - Mark the given Function as alive, meaning that it cannot be
539 /// changed in any way. Additionally,
540 /// mark any values that are used as this function's parameters or by its return
541 /// values (according to Uses) live as well.
542 void DAE::MarkLive(const Function
&F
) {
543 DEBUG(dbgs() << "DAE - Intrinsically live fn: " << F
.getName() << "\n");
544 // Mark the function as live.
545 LiveFunctions
.insert(&F
);
546 // Mark all arguments as live.
547 for (unsigned i
= 0, e
= F
.arg_size(); i
!= e
; ++i
)
548 PropagateLiveness(CreateArg(&F
, i
));
549 // Mark all return values as live.
550 for (unsigned i
= 0, e
= NumRetVals(&F
); i
!= e
; ++i
)
551 PropagateLiveness(CreateRet(&F
, i
));
554 /// MarkLive - Mark the given return value or argument as live. Additionally,
555 /// mark any values that are used by this value (according to Uses) live as
557 void DAE::MarkLive(const RetOrArg
&RA
) {
558 if (LiveFunctions
.count(RA
.F
))
559 return; // Function was already marked Live.
561 if (!LiveValues
.insert(RA
).second
)
562 return; // We were already marked Live.
564 DEBUG(dbgs() << "DAE - Marking " << RA
.getDescription() << " live\n");
565 PropagateLiveness(RA
);
568 /// PropagateLiveness - Given that RA is a live value, propagate it's liveness
569 /// to any other values it uses (according to Uses).
570 void DAE::PropagateLiveness(const RetOrArg
&RA
) {
571 // We don't use upper_bound (or equal_range) here, because our recursive call
572 // to ourselves is likely to cause the upper_bound (which is the first value
573 // not belonging to RA) to become erased and the iterator invalidated.
574 UseMap::iterator Begin
= Uses
.lower_bound(RA
);
575 UseMap::iterator E
= Uses
.end();
577 for (I
= Begin
; I
!= E
&& I
->first
== RA
; ++I
)
580 // Erase RA from the Uses map (from the lower bound to wherever we ended up
582 Uses
.erase(Begin
, I
);
585 // RemoveDeadStuffFromFunction - Remove any arguments and return values from F
586 // that are not in LiveValues. Transform the function and all of the callees of
587 // the function to not have these arguments and return values.
589 bool DAE::RemoveDeadStuffFromFunction(Function
*F
) {
590 // Don't modify fully live functions
591 if (LiveFunctions
.count(F
))
594 // Start by computing a new prototype for the function, which is the same as
595 // the old function, but has fewer arguments and a different return type.
596 const FunctionType
*FTy
= F
->getFunctionType();
597 std::vector
<const Type
*> Params
;
599 // Set up to build a new list of parameter attributes.
600 SmallVector
<AttributeWithIndex
, 8> AttributesVec
;
601 const AttrListPtr
&PAL
= F
->getAttributes();
603 // The existing function return attributes.
604 Attributes RAttrs
= PAL
.getRetAttributes();
605 Attributes FnAttrs
= PAL
.getFnAttributes();
607 // Find out the new return value.
609 const Type
*RetTy
= FTy
->getReturnType();
610 const Type
*NRetTy
= NULL
;
611 unsigned RetCount
= NumRetVals(F
);
613 // -1 means unused, other numbers are the new index
614 SmallVector
<int, 5> NewRetIdxs(RetCount
, -1);
615 std::vector
<const Type
*> RetTypes
;
616 if (RetTy
->isVoidTy()) {
619 const StructType
*STy
= dyn_cast
<StructType
>(RetTy
);
621 // Look at each of the original return values individually.
622 for (unsigned i
= 0; i
!= RetCount
; ++i
) {
623 RetOrArg Ret
= CreateRet(F
, i
);
624 if (LiveValues
.erase(Ret
)) {
625 RetTypes
.push_back(STy
->getElementType(i
));
626 NewRetIdxs
[i
] = RetTypes
.size() - 1;
628 ++NumRetValsEliminated
;
629 DEBUG(dbgs() << "DAE - Removing return value " << i
<< " from "
630 << F
->getName() << "\n");
634 // We used to return a single value.
635 if (LiveValues
.erase(CreateRet(F
, 0))) {
636 RetTypes
.push_back(RetTy
);
639 DEBUG(dbgs() << "DAE - Removing return value from " << F
->getName()
641 ++NumRetValsEliminated
;
643 if (RetTypes
.size() > 1)
644 // More than one return type? Return a struct with them. Also, if we used
645 // to return a struct and didn't change the number of return values,
646 // return a struct again. This prevents changing {something} into
647 // something and {} into void.
648 // Make the new struct packed if we used to return a packed struct
650 NRetTy
= StructType::get(STy
->getContext(), RetTypes
, STy
->isPacked());
651 else if (RetTypes
.size() == 1)
652 // One return type? Just a simple value then, but only if we didn't use to
653 // return a struct with that simple value before.
654 NRetTy
= RetTypes
.front();
655 else if (RetTypes
.size() == 0)
656 // No return types? Make it void, but only if we didn't use to return {}.
657 NRetTy
= Type::getVoidTy(F
->getContext());
660 assert(NRetTy
&& "No new return type found?");
662 // Remove any incompatible attributes, but only if we removed all return
663 // values. Otherwise, ensure that we don't have any conflicting attributes
664 // here. Currently, this should not be possible, but special handling might be
665 // required when new return value attributes are added.
666 if (NRetTy
->isVoidTy())
667 RAttrs
&= ~Attribute::typeIncompatible(NRetTy
);
669 assert((RAttrs
& Attribute::typeIncompatible(NRetTy
)) == 0
670 && "Return attributes no longer compatible?");
673 AttributesVec
.push_back(AttributeWithIndex::get(0, RAttrs
));
675 // Remember which arguments are still alive.
676 SmallVector
<bool, 10> ArgAlive(FTy
->getNumParams(), false);
677 // Construct the new parameter list from non-dead arguments. Also construct
678 // a new set of parameter attributes to correspond. Skip the first parameter
679 // attribute, since that belongs to the return value.
681 for (Function::arg_iterator I
= F
->arg_begin(), E
= F
->arg_end();
683 RetOrArg Arg
= CreateArg(F
, i
);
684 if (LiveValues
.erase(Arg
)) {
685 Params
.push_back(I
->getType());
688 // Get the original parameter attributes (skipping the first one, that is
689 // for the return value.
690 if (Attributes Attrs
= PAL
.getParamAttributes(i
+ 1))
691 AttributesVec
.push_back(AttributeWithIndex::get(Params
.size(), Attrs
));
693 ++NumArgumentsEliminated
;
694 DEBUG(dbgs() << "DAE - Removing argument " << i
<< " (" << I
->getName()
695 << ") from " << F
->getName() << "\n");
699 if (FnAttrs
!= Attribute::None
)
700 AttributesVec
.push_back(AttributeWithIndex::get(~0, FnAttrs
));
702 // Reconstruct the AttributesList based on the vector we constructed.
703 AttrListPtr NewPAL
= AttrListPtr::get(AttributesVec
.begin(),
704 AttributesVec
.end());
706 // Create the new function type based on the recomputed parameters.
707 FunctionType
*NFTy
= FunctionType::get(NRetTy
, Params
, FTy
->isVarArg());
713 // Create the new function body and insert it into the module...
714 Function
*NF
= Function::Create(NFTy
, F
->getLinkage());
715 NF
->copyAttributesFrom(F
);
716 NF
->setAttributes(NewPAL
);
717 // Insert the new function before the old function, so we won't be processing
719 F
->getParent()->getFunctionList().insert(F
, NF
);
722 // Loop over all of the callers of the function, transforming the call sites
723 // to pass in a smaller number of arguments into the new function.
725 std::vector
<Value
*> Args
;
726 while (!F
->use_empty()) {
727 CallSite
CS(F
->use_back());
728 Instruction
*Call
= CS
.getInstruction();
730 AttributesVec
.clear();
731 const AttrListPtr
&CallPAL
= CS
.getAttributes();
733 // The call return attributes.
734 Attributes RAttrs
= CallPAL
.getRetAttributes();
735 Attributes FnAttrs
= CallPAL
.getFnAttributes();
736 // Adjust in case the function was changed to return void.
737 RAttrs
&= ~Attribute::typeIncompatible(NF
->getReturnType());
739 AttributesVec
.push_back(AttributeWithIndex::get(0, RAttrs
));
741 // Declare these outside of the loops, so we can reuse them for the second
742 // loop, which loops the varargs.
743 CallSite::arg_iterator I
= CS
.arg_begin();
745 // Loop over those operands, corresponding to the normal arguments to the
746 // original function, and add those that are still alive.
747 for (unsigned e
= FTy
->getNumParams(); i
!= e
; ++I
, ++i
)
750 // Get original parameter attributes, but skip return attributes.
751 if (Attributes Attrs
= CallPAL
.getParamAttributes(i
+ 1))
752 AttributesVec
.push_back(AttributeWithIndex::get(Args
.size(), Attrs
));
755 // Push any varargs arguments on the list. Don't forget their attributes.
756 for (CallSite::arg_iterator E
= CS
.arg_end(); I
!= E
; ++I
, ++i
) {
758 if (Attributes Attrs
= CallPAL
.getParamAttributes(i
+ 1))
759 AttributesVec
.push_back(AttributeWithIndex::get(Args
.size(), Attrs
));
762 if (FnAttrs
!= Attribute::None
)
763 AttributesVec
.push_back(AttributeWithIndex::get(~0, FnAttrs
));
765 // Reconstruct the AttributesList based on the vector we constructed.
766 AttrListPtr NewCallPAL
= AttrListPtr::get(AttributesVec
.begin(),
767 AttributesVec
.end());
770 if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(Call
)) {
771 New
= InvokeInst::Create(NF
, II
->getNormalDest(), II
->getUnwindDest(),
772 Args
.begin(), Args
.end(), "", Call
);
773 cast
<InvokeInst
>(New
)->setCallingConv(CS
.getCallingConv());
774 cast
<InvokeInst
>(New
)->setAttributes(NewCallPAL
);
776 New
= CallInst::Create(NF
, Args
.begin(), Args
.end(), "", Call
);
777 cast
<CallInst
>(New
)->setCallingConv(CS
.getCallingConv());
778 cast
<CallInst
>(New
)->setAttributes(NewCallPAL
);
779 if (cast
<CallInst
>(Call
)->isTailCall())
780 cast
<CallInst
>(New
)->setTailCall();
782 New
->setDebugLoc(Call
->getDebugLoc());
786 if (!Call
->use_empty()) {
787 if (New
->getType() == Call
->getType()) {
788 // Return type not changed? Just replace users then.
789 Call
->replaceAllUsesWith(New
);
791 } else if (New
->getType()->isVoidTy()) {
792 // Our return value has uses, but they will get removed later on.
793 // Replace by null for now.
794 Call
->replaceAllUsesWith(Constant::getNullValue(Call
->getType()));
796 assert(RetTy
->isStructTy() &&
797 "Return type changed, but not into a void. The old return type"
798 " must have been a struct!");
799 Instruction
*InsertPt
= Call
;
800 if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(Call
)) {
801 BasicBlock::iterator IP
= II
->getNormalDest()->begin();
802 while (isa
<PHINode
>(IP
)) ++IP
;
806 // We used to return a struct. Instead of doing smart stuff with all the
807 // uses of this struct, we will just rebuild it using
808 // extract/insertvalue chaining and let instcombine clean that up.
810 // Start out building up our return value from undef
811 Value
*RetVal
= UndefValue::get(RetTy
);
812 for (unsigned i
= 0; i
!= RetCount
; ++i
)
813 if (NewRetIdxs
[i
] != -1) {
815 if (RetTypes
.size() > 1)
816 // We are still returning a struct, so extract the value from our
818 V
= ExtractValueInst::Create(New
, NewRetIdxs
[i
], "newret",
821 // We are now returning a single element, so just insert that
823 // Insert the value at the old position
824 RetVal
= InsertValueInst::Create(RetVal
, V
, i
, "oldret", InsertPt
);
826 // Now, replace all uses of the old call instruction with the return
828 Call
->replaceAllUsesWith(RetVal
);
833 // Finally, remove the old call from the program, reducing the use-count of
835 Call
->eraseFromParent();
838 // Since we have now created the new function, splice the body of the old
839 // function right into the new function, leaving the old rotting hulk of the
841 NF
->getBasicBlockList().splice(NF
->begin(), F
->getBasicBlockList());
843 // Loop over the argument list, transfering uses of the old arguments over to
844 // the new arguments, also transfering over the names as well.
846 for (Function::arg_iterator I
= F
->arg_begin(), E
= F
->arg_end(),
847 I2
= NF
->arg_begin(); I
!= E
; ++I
, ++i
)
849 // If this is a live argument, move the name and users over to the new
851 I
->replaceAllUsesWith(I2
);
855 // If this argument is dead, replace any uses of it with null constants
856 // (these are guaranteed to become unused later on).
857 I
->replaceAllUsesWith(Constant::getNullValue(I
->getType()));
860 // If we change the return value of the function we must rewrite any return
861 // instructions. Check this now.
862 if (F
->getReturnType() != NF
->getReturnType())
863 for (Function::iterator BB
= NF
->begin(), E
= NF
->end(); BB
!= E
; ++BB
)
864 if (ReturnInst
*RI
= dyn_cast
<ReturnInst
>(BB
->getTerminator())) {
867 if (NFTy
->getReturnType()->isVoidTy()) {
870 assert (RetTy
->isStructTy());
871 // The original return value was a struct, insert
872 // extractvalue/insertvalue chains to extract only the values we need
873 // to return and insert them into our new result.
874 // This does generate messy code, but we'll let it to instcombine to
876 Value
*OldRet
= RI
->getOperand(0);
877 // Start out building up our return value from undef
878 RetVal
= UndefValue::get(NRetTy
);
879 for (unsigned i
= 0; i
!= RetCount
; ++i
)
880 if (NewRetIdxs
[i
] != -1) {
881 ExtractValueInst
*EV
= ExtractValueInst::Create(OldRet
, i
,
883 if (RetTypes
.size() > 1) {
884 // We're still returning a struct, so reinsert the value into
885 // our new return value at the new index
887 RetVal
= InsertValueInst::Create(RetVal
, EV
, NewRetIdxs
[i
],
890 // We are now only returning a simple value, so just return the
896 // Replace the return instruction with one returning the new return
897 // value (possibly 0 if we became void).
898 ReturnInst::Create(F
->getContext(), RetVal
, RI
);
899 BB
->getInstList().erase(RI
);
902 // Now that the old function is dead, delete it.
903 F
->eraseFromParent();
908 bool DAE::runOnModule(Module
&M
) {
909 bool Changed
= false;
911 // First pass: Do a simple check to see if any functions can have their "..."
912 // removed. We can do this if they never call va_start. This loop cannot be
913 // fused with the next loop, because deleting a function invalidates
914 // information computed while surveying other functions.
915 DEBUG(dbgs() << "DAE - Deleting dead varargs\n");
916 for (Module::iterator I
= M
.begin(), E
= M
.end(); I
!= E
; ) {
918 if (F
.getFunctionType()->isVarArg())
919 Changed
|= DeleteDeadVarargs(F
);
922 // Second phase:loop through the module, determining which arguments are live.
923 // We assume all arguments are dead unless proven otherwise (allowing us to
924 // determine that dead arguments passed into recursive functions are dead).
926 DEBUG(dbgs() << "DAE - Determining liveness\n");
927 for (Module::iterator I
= M
.begin(), E
= M
.end(); I
!= E
; ++I
)
930 // Now, remove all dead arguments and return values from each function in
932 for (Module::iterator I
= M
.begin(), E
= M
.end(); I
!= E
; ) {
933 // Increment now, because the function will probably get removed (ie.
934 // replaced by a new one).
936 Changed
|= RemoveDeadStuffFromFunction(F
);