1 //===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===//
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 file transforms calls of the current function (self recursion) followed
11 // by a return instruction with a branch to the entry of the function, creating
12 // a loop. This pass also implements the following extensions to the basic
15 // 1. Trivial instructions between the call and return do not prevent the
16 // transformation from taking place, though currently the analysis cannot
17 // support moving any really useful instructions (only dead ones).
18 // 2. This pass transforms functions that are prevented from being tail
19 // recursive by an associative and commutative expression to use an
20 // accumulator variable, thus compiling the typical naive factorial or
21 // 'fib' implementation into efficient code.
22 // 3. TRE is performed if the function returns void, if the return
23 // returns the result returned by the call, or if the function returns a
24 // run-time constant on all exits from the function. It is possible, though
25 // unlikely, that the return returns something else (like constant 0), and
26 // can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in
27 // the function return the exact same value.
28 // 4. If it can prove that callees do not access their caller stack frame,
29 // they are marked as eligible for tail call elimination (by the code
32 // There are several improvements that could be made:
34 // 1. If the function has any alloca instructions, these instructions will be
35 // moved out of the entry block of the function, causing them to be
36 // evaluated each time through the tail recursion. Safely keeping allocas
37 // in the entry block requires analysis to proves that the tail-called
38 // function does not read or write the stack object.
39 // 2. Tail recursion is only performed if the call immediately preceeds the
40 // return instruction. It's possible that there could be a jump between
41 // the call and the return.
42 // 3. There can be intervening operations between the call and the return that
43 // prevent the TRE from occurring. For example, there could be GEP's and
44 // stores to memory that will not be read or written by the call. This
45 // requires some substantial analysis (such as with DSA) to prove safe to
46 // move ahead of the call, but doing so could allow many more TREs to be
47 // performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark.
48 // 4. The algorithm we use to detect if callees access their caller stack
49 // frames is very primitive.
51 //===----------------------------------------------------------------------===//
53 #define DEBUG_TYPE "tailcallelim"
54 #include "llvm/Transforms/Scalar.h"
55 #include "llvm/Transforms/Utils/Local.h"
56 #include "llvm/Constants.h"
57 #include "llvm/DerivedTypes.h"
58 #include "llvm/Function.h"
59 #include "llvm/Instructions.h"
60 #include "llvm/Pass.h"
61 #include "llvm/Analysis/CaptureTracking.h"
62 #include "llvm/Analysis/InlineCost.h"
63 #include "llvm/Analysis/InstructionSimplify.h"
64 #include "llvm/Analysis/Loads.h"
65 #include "llvm/Support/CallSite.h"
66 #include "llvm/Support/CFG.h"
67 #include "llvm/ADT/Statistic.h"
70 STATISTIC(NumEliminated
, "Number of tail calls removed");
71 STATISTIC(NumAccumAdded
, "Number of accumulators introduced");
74 struct TailCallElim
: public FunctionPass
{
75 static char ID
; // Pass identification, replacement for typeid
76 TailCallElim() : FunctionPass(ID
) {
77 initializeTailCallElimPass(*PassRegistry::getPassRegistry());
80 virtual bool runOnFunction(Function
&F
);
83 bool ProcessReturningBlock(ReturnInst
*RI
, BasicBlock
*&OldEntry
,
84 bool &TailCallsAreMarkedTail
,
85 SmallVector
<PHINode
*, 8> &ArgumentPHIs
,
86 bool CannotTailCallElimCallsMarkedTail
);
87 bool CanMoveAboveCall(Instruction
*I
, CallInst
*CI
);
88 Value
*CanTransformAccumulatorRecursion(Instruction
*I
, CallInst
*CI
);
92 char TailCallElim::ID
= 0;
93 INITIALIZE_PASS(TailCallElim
, "tailcallelim",
94 "Tail Call Elimination", false, false)
96 // Public interface to the TailCallElimination pass
97 FunctionPass
*llvm::createTailCallEliminationPass() {
98 return new TailCallElim();
101 /// AllocaMightEscapeToCalls - Return true if this alloca may be accessed by
102 /// callees of this function. We only do very simple analysis right now, this
103 /// could be expanded in the future to use mod/ref information for particular
104 /// call sites if desired.
105 static bool AllocaMightEscapeToCalls(AllocaInst
*AI
) {
106 // FIXME: do simple 'address taken' analysis.
110 /// CheckForEscapingAllocas - Scan the specified basic block for alloca
111 /// instructions. If it contains any that might be accessed by calls, return
113 static bool CheckForEscapingAllocas(BasicBlock
*BB
,
114 bool &CannotTCETailMarkedCall
) {
116 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->end(); I
!= E
; ++I
)
117 if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(I
)) {
118 RetVal
|= AllocaMightEscapeToCalls(AI
);
120 // If this alloca is in the body of the function, or if it is a variable
121 // sized allocation, we cannot tail call eliminate calls marked 'tail'
122 // with this mechanism.
123 if (BB
!= &BB
->getParent()->getEntryBlock() ||
124 !isa
<ConstantInt
>(AI
->getArraySize()))
125 CannotTCETailMarkedCall
= true;
130 bool TailCallElim::runOnFunction(Function
&F
) {
131 // If this function is a varargs function, we won't be able to PHI the args
132 // right, so don't even try to convert it...
133 if (F
.getFunctionType()->isVarArg()) return false;
135 BasicBlock
*OldEntry
= 0;
136 bool TailCallsAreMarkedTail
= false;
137 SmallVector
<PHINode
*, 8> ArgumentPHIs
;
138 bool MadeChange
= false;
140 bool FunctionContainsEscapingAllocas
= false;
142 // CannotTCETailMarkedCall - If true, we cannot perform TCE on tail calls
143 // marked with the 'tail' attribute, because doing so would cause the stack
144 // size to increase (real TCE would deallocate variable sized allocas, TCE
146 bool CannotTCETailMarkedCall
= false;
148 // Loop over the function, looking for any returning blocks, and keeping track
149 // of whether this function has any non-trivially used allocas.
150 for (Function::iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
; ++BB
) {
151 if (FunctionContainsEscapingAllocas
&& CannotTCETailMarkedCall
)
154 FunctionContainsEscapingAllocas
|=
155 CheckForEscapingAllocas(BB
, CannotTCETailMarkedCall
);
158 /// FIXME: The code generator produces really bad code when an 'escaping
159 /// alloca' is changed from being a static alloca to being a dynamic alloca.
160 /// Until this is resolved, disable this transformation if that would ever
161 /// happen. This bug is PR962.
162 if (FunctionContainsEscapingAllocas
)
165 // Second pass, change any tail calls to loops.
166 for (Function::iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
; ++BB
)
167 if (ReturnInst
*Ret
= dyn_cast
<ReturnInst
>(BB
->getTerminator()))
168 MadeChange
|= ProcessReturningBlock(Ret
, OldEntry
, TailCallsAreMarkedTail
,
169 ArgumentPHIs
,CannotTCETailMarkedCall
);
171 // If we eliminated any tail recursions, it's possible that we inserted some
172 // silly PHI nodes which just merge an initial value (the incoming operand)
173 // with themselves. Check to see if we did and clean up our mess if so. This
174 // occurs when a function passes an argument straight through to its tail
176 if (!ArgumentPHIs
.empty()) {
177 for (unsigned i
= 0, e
= ArgumentPHIs
.size(); i
!= e
; ++i
) {
178 PHINode
*PN
= ArgumentPHIs
[i
];
180 // If the PHI Node is a dynamic constant, replace it with the value it is.
181 if (Value
*PNV
= SimplifyInstruction(PN
)) {
182 PN
->replaceAllUsesWith(PNV
);
183 PN
->eraseFromParent();
188 // Finally, if this function contains no non-escaping allocas, mark all calls
189 // in the function as eligible for tail calls (there is no stack memory for
191 if (!FunctionContainsEscapingAllocas
)
192 for (Function::iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
; ++BB
)
193 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->end(); I
!= E
; ++I
)
194 if (CallInst
*CI
= dyn_cast
<CallInst
>(I
)) {
203 /// CanMoveAboveCall - Return true if it is safe to move the specified
204 /// instruction from after the call to before the call, assuming that all
205 /// instructions between the call and this instruction are movable.
207 bool TailCallElim::CanMoveAboveCall(Instruction
*I
, CallInst
*CI
) {
208 // FIXME: We can move load/store/call/free instructions above the call if the
209 // call does not mod/ref the memory location being processed.
210 if (I
->mayHaveSideEffects()) // This also handles volatile loads.
213 if (LoadInst
*L
= dyn_cast
<LoadInst
>(I
)) {
214 // Loads may always be moved above calls without side effects.
215 if (CI
->mayHaveSideEffects()) {
216 // Non-volatile loads may be moved above a call with side effects if it
217 // does not write to memory and the load provably won't trap.
218 // FIXME: Writes to memory only matter if they may alias the pointer
219 // being loaded from.
220 if (CI
->mayWriteToMemory() ||
221 !isSafeToLoadUnconditionally(L
->getPointerOperand(), L
,
227 // Otherwise, if this is a side-effect free instruction, check to make sure
228 // that it does not use the return value of the call. If it doesn't use the
229 // return value of the call, it must only use things that are defined before
230 // the call, or movable instructions between the call and the instruction
232 for (unsigned i
= 0, e
= I
->getNumOperands(); i
!= e
; ++i
)
233 if (I
->getOperand(i
) == CI
)
238 // isDynamicConstant - Return true if the specified value is the same when the
239 // return would exit as it was when the initial iteration of the recursive
240 // function was executed.
242 // We currently handle static constants and arguments that are not modified as
243 // part of the recursion.
245 static bool isDynamicConstant(Value
*V
, CallInst
*CI
, ReturnInst
*RI
) {
246 if (isa
<Constant
>(V
)) return true; // Static constants are always dyn consts
248 // Check to see if this is an immutable argument, if so, the value
249 // will be available to initialize the accumulator.
250 if (Argument
*Arg
= dyn_cast
<Argument
>(V
)) {
251 // Figure out which argument number this is...
253 Function
*F
= CI
->getParent()->getParent();
254 for (Function::arg_iterator AI
= F
->arg_begin(); &*AI
!= Arg
; ++AI
)
257 // If we are passing this argument into call as the corresponding
258 // argument operand, then the argument is dynamically constant.
259 // Otherwise, we cannot transform this function safely.
260 if (CI
->getArgOperand(ArgNo
) == Arg
)
264 // Switch cases are always constant integers. If the value is being switched
265 // on and the return is only reachable from one of its cases, it's
266 // effectively constant.
267 if (BasicBlock
*UniquePred
= RI
->getParent()->getUniquePredecessor())
268 if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(UniquePred
->getTerminator()))
269 if (SI
->getCondition() == V
)
270 return SI
->getDefaultDest() != RI
->getParent();
272 // Not a constant or immutable argument, we can't safely transform.
276 // getCommonReturnValue - Check to see if the function containing the specified
277 // tail call consistently returns the same runtime-constant value at all exit
278 // points except for IgnoreRI. If so, return the returned value.
280 static Value
*getCommonReturnValue(ReturnInst
*IgnoreRI
, CallInst
*CI
) {
281 Function
*F
= CI
->getParent()->getParent();
282 Value
*ReturnedValue
= 0;
284 for (Function::iterator BBI
= F
->begin(), E
= F
->end(); BBI
!= E
; ++BBI
) {
285 ReturnInst
*RI
= dyn_cast
<ReturnInst
>(BBI
->getTerminator());
286 if (RI
== 0 || RI
== IgnoreRI
) continue;
288 // We can only perform this transformation if the value returned is
289 // evaluatable at the start of the initial invocation of the function,
290 // instead of at the end of the evaluation.
292 Value
*RetOp
= RI
->getOperand(0);
293 if (!isDynamicConstant(RetOp
, CI
, RI
))
296 if (ReturnedValue
&& RetOp
!= ReturnedValue
)
297 return 0; // Cannot transform if differing values are returned.
298 ReturnedValue
= RetOp
;
300 return ReturnedValue
;
303 /// CanTransformAccumulatorRecursion - If the specified instruction can be
304 /// transformed using accumulator recursion elimination, return the constant
305 /// which is the start of the accumulator value. Otherwise return null.
307 Value
*TailCallElim::CanTransformAccumulatorRecursion(Instruction
*I
,
309 if (!I
->isAssociative() || !I
->isCommutative()) return 0;
310 assert(I
->getNumOperands() == 2 &&
311 "Associative/commutative operations should have 2 args!");
313 // Exactly one operand should be the result of the call instruction.
314 if ((I
->getOperand(0) == CI
&& I
->getOperand(1) == CI
) ||
315 (I
->getOperand(0) != CI
&& I
->getOperand(1) != CI
))
318 // The only user of this instruction we allow is a single return instruction.
319 if (!I
->hasOneUse() || !isa
<ReturnInst
>(I
->use_back()))
322 // Ok, now we have to check all of the other return instructions in this
323 // function. If they return non-constants or differing values, then we cannot
324 // transform the function safely.
325 return getCommonReturnValue(cast
<ReturnInst
>(I
->use_back()), CI
);
328 bool TailCallElim::ProcessReturningBlock(ReturnInst
*Ret
, BasicBlock
*&OldEntry
,
329 bool &TailCallsAreMarkedTail
,
330 SmallVector
<PHINode
*, 8> &ArgumentPHIs
,
331 bool CannotTailCallElimCallsMarkedTail
) {
332 BasicBlock
*BB
= Ret
->getParent();
333 Function
*F
= BB
->getParent();
335 if (&BB
->front() == Ret
) // Make sure there is something before the ret...
338 // Scan backwards from the return, checking to see if there is a tail call in
339 // this block. If so, set CI to it.
341 BasicBlock::iterator BBI
= Ret
;
343 CI
= dyn_cast
<CallInst
>(BBI
);
344 if (CI
&& CI
->getCalledFunction() == F
)
347 if (BBI
== BB
->begin())
348 return false; // Didn't find a potential tail call.
352 // If this call is marked as a tail call, and if there are dynamic allocas in
353 // the function, we cannot perform this optimization.
354 if (CI
->isTailCall() && CannotTailCallElimCallsMarkedTail
)
357 // As a special case, detect code like this:
358 // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
359 // and disable this xform in this case, because the code generator will
360 // lower the call to fabs into inline code.
361 if (BB
== &F
->getEntryBlock() &&
362 &BB
->front() == CI
&& &*++BB
->begin() == Ret
&&
364 // A single-block function with just a call and a return. Check that
365 // the arguments match.
366 CallSite::arg_iterator I
= CallSite(CI
).arg_begin(),
367 E
= CallSite(CI
).arg_end();
368 Function::arg_iterator FI
= F
->arg_begin(),
370 for (; I
!= E
&& FI
!= FE
; ++I
, ++FI
)
371 if (*I
!= &*FI
) break;
372 if (I
== E
&& FI
== FE
)
376 // If we are introducing accumulator recursion to eliminate operations after
377 // the call instruction that are both associative and commutative, the initial
378 // value for the accumulator is placed in this variable. If this value is set
379 // then we actually perform accumulator recursion elimination instead of
380 // simple tail recursion elimination. If the operation is an LLVM instruction
381 // (eg: "add") then it is recorded in AccumulatorRecursionInstr. If not, then
382 // we are handling the case when the return instruction returns a constant C
383 // which is different to the constant returned by other return instructions
384 // (which is recorded in AccumulatorRecursionEliminationInitVal). This is a
385 // special case of accumulator recursion, the operation being "return C".
386 Value
*AccumulatorRecursionEliminationInitVal
= 0;
387 Instruction
*AccumulatorRecursionInstr
= 0;
389 // Ok, we found a potential tail call. We can currently only transform the
390 // tail call if all of the instructions between the call and the return are
391 // movable to above the call itself, leaving the call next to the return.
392 // Check that this is the case now.
393 for (BBI
= CI
, ++BBI
; &*BBI
!= Ret
; ++BBI
) {
394 if (CanMoveAboveCall(BBI
, CI
)) continue;
396 // If we can't move the instruction above the call, it might be because it
397 // is an associative and commutative operation that could be tranformed
398 // using accumulator recursion elimination. Check to see if this is the
399 // case, and if so, remember the initial accumulator value for later.
400 if ((AccumulatorRecursionEliminationInitVal
=
401 CanTransformAccumulatorRecursion(BBI
, CI
))) {
402 // Yes, this is accumulator recursion. Remember which instruction
404 AccumulatorRecursionInstr
= BBI
;
406 return false; // Otherwise, we cannot eliminate the tail recursion!
410 // We can only transform call/return pairs that either ignore the return value
411 // of the call and return void, ignore the value of the call and return a
412 // constant, return the value returned by the tail call, or that are being
413 // accumulator recursion variable eliminated.
414 if (Ret
->getNumOperands() == 1 && Ret
->getReturnValue() != CI
&&
415 !isa
<UndefValue
>(Ret
->getReturnValue()) &&
416 AccumulatorRecursionEliminationInitVal
== 0 &&
417 !getCommonReturnValue(0, CI
)) {
418 // One case remains that we are able to handle: the current return
419 // instruction returns a constant, and all other return instructions
420 // return a different constant.
421 if (!isDynamicConstant(Ret
->getReturnValue(), CI
, Ret
))
422 return false; // Current return instruction does not return a constant.
423 // Check that all other return instructions return a common constant. If
424 // so, record it in AccumulatorRecursionEliminationInitVal.
425 AccumulatorRecursionEliminationInitVal
= getCommonReturnValue(Ret
, CI
);
426 if (!AccumulatorRecursionEliminationInitVal
)
430 // OK! We can transform this tail call. If this is the first one found,
431 // create the new entry block, allowing us to branch back to the old entry.
433 OldEntry
= &F
->getEntryBlock();
434 BasicBlock
*NewEntry
= BasicBlock::Create(F
->getContext(), "", F
, OldEntry
);
435 NewEntry
->takeName(OldEntry
);
436 OldEntry
->setName("tailrecurse");
437 BranchInst::Create(OldEntry
, NewEntry
);
439 // If this tail call is marked 'tail' and if there are any allocas in the
440 // entry block, move them up to the new entry block.
441 TailCallsAreMarkedTail
= CI
->isTailCall();
442 if (TailCallsAreMarkedTail
)
443 // Move all fixed sized allocas from OldEntry to NewEntry.
444 for (BasicBlock::iterator OEBI
= OldEntry
->begin(), E
= OldEntry
->end(),
445 NEBI
= NewEntry
->begin(); OEBI
!= E
; )
446 if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(OEBI
++))
447 if (isa
<ConstantInt
>(AI
->getArraySize()))
448 AI
->moveBefore(NEBI
);
450 // Now that we have created a new block, which jumps to the entry
451 // block, insert a PHI node for each argument of the function.
452 // For now, we initialize each PHI to only have the real arguments
453 // which are passed in.
454 Instruction
*InsertPos
= OldEntry
->begin();
455 for (Function::arg_iterator I
= F
->arg_begin(), E
= F
->arg_end();
457 PHINode
*PN
= PHINode::Create(I
->getType(),
458 I
->getName() + ".tr", InsertPos
);
459 I
->replaceAllUsesWith(PN
); // Everyone use the PHI node now!
460 PN
->addIncoming(I
, NewEntry
);
461 ArgumentPHIs
.push_back(PN
);
465 // If this function has self recursive calls in the tail position where some
466 // are marked tail and some are not, only transform one flavor or another. We
467 // have to choose whether we move allocas in the entry block to the new entry
468 // block or not, so we can't make a good choice for both. NOTE: We could do
469 // slightly better here in the case that the function has no entry block
471 if (TailCallsAreMarkedTail
&& !CI
->isTailCall())
474 // Ok, now that we know we have a pseudo-entry block WITH all of the
475 // required PHI nodes, add entries into the PHI node for the actual
476 // parameters passed into the tail-recursive call.
477 for (unsigned i
= 0, e
= CI
->getNumArgOperands(); i
!= e
; ++i
)
478 ArgumentPHIs
[i
]->addIncoming(CI
->getArgOperand(i
), BB
);
480 // If we are introducing an accumulator variable to eliminate the recursion,
481 // do so now. Note that we _know_ that no subsequent tail recursion
482 // eliminations will happen on this function because of the way the
483 // accumulator recursion predicate is set up.
485 if (AccumulatorRecursionEliminationInitVal
) {
486 Instruction
*AccRecInstr
= AccumulatorRecursionInstr
;
487 // Start by inserting a new PHI node for the accumulator.
489 PHINode::Create(AccumulatorRecursionEliminationInitVal
->getType(),
490 "accumulator.tr", OldEntry
->begin());
492 // Loop over all of the predecessors of the tail recursion block. For the
493 // real entry into the function we seed the PHI with the initial value,
494 // computed earlier. For any other existing branches to this block (due to
495 // other tail recursions eliminated) the accumulator is not modified.
496 // Because we haven't added the branch in the current block to OldEntry yet,
497 // it will not show up as a predecessor.
498 for (pred_iterator PI
= pred_begin(OldEntry
), PE
= pred_end(OldEntry
);
501 if (P
== &F
->getEntryBlock())
502 AccPN
->addIncoming(AccumulatorRecursionEliminationInitVal
, P
);
504 AccPN
->addIncoming(AccPN
, P
);
508 // Add an incoming argument for the current block, which is computed by
509 // our associative and commutative accumulator instruction.
510 AccPN
->addIncoming(AccRecInstr
, BB
);
512 // Next, rewrite the accumulator recursion instruction so that it does not
513 // use the result of the call anymore, instead, use the PHI node we just
515 AccRecInstr
->setOperand(AccRecInstr
->getOperand(0) != CI
, AccPN
);
517 // Add an incoming argument for the current block, which is just the
518 // constant returned by the current return instruction.
519 AccPN
->addIncoming(Ret
->getReturnValue(), BB
);
522 // Finally, rewrite any return instructions in the program to return the PHI
523 // node instead of the "initval" that they do currently. This loop will
524 // actually rewrite the return value we are destroying, but that's ok.
525 for (Function::iterator BBI
= F
->begin(), E
= F
->end(); BBI
!= E
; ++BBI
)
526 if (ReturnInst
*RI
= dyn_cast
<ReturnInst
>(BBI
->getTerminator()))
527 RI
->setOperand(0, AccPN
);
531 // Now that all of the PHI nodes are in place, remove the call and
532 // ret instructions, replacing them with an unconditional branch.
533 BranchInst::Create(OldEntry
, Ret
);
534 BB
->getInstList().erase(Ret
); // Remove return.
535 BB
->getInstList().erase(CI
); // Remove call.