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 precedes 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 #include "llvm/Transforms/Scalar.h"
54 #include "llvm/ADT/STLExtras.h"
55 #include "llvm/ADT/SmallPtrSet.h"
56 #include "llvm/ADT/Statistic.h"
57 #include "llvm/Analysis/CaptureTracking.h"
58 #include "llvm/Analysis/CFG.h"
59 #include "llvm/Analysis/InlineCost.h"
60 #include "llvm/Analysis/InstructionSimplify.h"
61 #include "llvm/Analysis/Loads.h"
62 #include "llvm/Analysis/TargetTransformInfo.h"
63 #include "llvm/IR/CFG.h"
64 #include "llvm/IR/CallSite.h"
65 #include "llvm/IR/Constants.h"
66 #include "llvm/IR/DataLayout.h"
67 #include "llvm/IR/DerivedTypes.h"
68 #include "llvm/IR/DiagnosticInfo.h"
69 #include "llvm/IR/Function.h"
70 #include "llvm/IR/Instructions.h"
71 #include "llvm/IR/IntrinsicInst.h"
72 #include "llvm/IR/Module.h"
73 #include "llvm/IR/ValueHandle.h"
74 #include "llvm/Pass.h"
75 #include "llvm/Support/Debug.h"
76 #include "llvm/Support/raw_ostream.h"
77 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
78 #include "llvm/Transforms/Utils/Local.h"
81 #define DEBUG_TYPE "tailcallelim"
83 STATISTIC(NumEliminated
, "Number of tail calls removed");
84 STATISTIC(NumRetDuped
, "Number of return duplicated");
85 STATISTIC(NumAccumAdded
, "Number of accumulators introduced");
88 struct TailCallElim
: public FunctionPass
{
89 const TargetTransformInfo
*TTI
;
92 static char ID
; // Pass identification, replacement for typeid
93 TailCallElim() : FunctionPass(ID
) {
94 initializeTailCallElimPass(*PassRegistry::getPassRegistry());
97 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
99 bool runOnFunction(Function
&F
) override
;
102 bool runTRE(Function
&F
);
103 bool markTails(Function
&F
, bool &AllCallsAreTailCalls
);
105 CallInst
*FindTRECandidate(Instruction
*I
,
106 bool CannotTailCallElimCallsMarkedTail
);
107 bool EliminateRecursiveTailCall(CallInst
*CI
, ReturnInst
*Ret
,
108 BasicBlock
*&OldEntry
,
109 bool &TailCallsAreMarkedTail
,
110 SmallVectorImpl
<PHINode
*> &ArgumentPHIs
,
111 bool CannotTailCallElimCallsMarkedTail
);
112 bool FoldReturnAndProcessPred(BasicBlock
*BB
,
113 ReturnInst
*Ret
, BasicBlock
*&OldEntry
,
114 bool &TailCallsAreMarkedTail
,
115 SmallVectorImpl
<PHINode
*> &ArgumentPHIs
,
116 bool CannotTailCallElimCallsMarkedTail
);
117 bool ProcessReturningBlock(ReturnInst
*RI
, BasicBlock
*&OldEntry
,
118 bool &TailCallsAreMarkedTail
,
119 SmallVectorImpl
<PHINode
*> &ArgumentPHIs
,
120 bool CannotTailCallElimCallsMarkedTail
);
121 bool CanMoveAboveCall(Instruction
*I
, CallInst
*CI
);
122 Value
*CanTransformAccumulatorRecursion(Instruction
*I
, CallInst
*CI
);
126 char TailCallElim::ID
= 0;
127 INITIALIZE_PASS_BEGIN(TailCallElim
, "tailcallelim",
128 "Tail Call Elimination", false, false)
129 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo
)
130 INITIALIZE_PASS_END(TailCallElim
, "tailcallelim",
131 "Tail Call Elimination", false, false)
133 // Public interface to the TailCallElimination pass
134 FunctionPass
*llvm::createTailCallEliminationPass() {
135 return new TailCallElim();
138 void TailCallElim::getAnalysisUsage(AnalysisUsage
&AU
) const {
139 AU
.addRequired
<TargetTransformInfo
>();
142 /// \brief Scan the specified function for alloca instructions.
143 /// If it contains any dynamic allocas, returns false.
144 static bool CanTRE(Function
&F
) {
145 // Because of PR962, we don't TRE dynamic allocas.
148 if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(&I
)) {
149 if (!AI
->isStaticAlloca())
158 bool TailCallElim::runOnFunction(Function
&F
) {
159 if (skipOptnoneFunction(F
))
162 DL
= F
.getParent()->getDataLayout();
164 bool AllCallsAreTailCalls
= false;
165 bool Modified
= markTails(F
, AllCallsAreTailCalls
);
166 if (AllCallsAreTailCalls
)
167 Modified
|= runTRE(F
);
172 struct AllocaDerivedValueTracker
{
173 // Start at a root value and walk its use-def chain to mark calls that use the
174 // value or a derived value in AllocaUsers, and places where it may escape in
176 void walk(Value
*Root
) {
177 SmallVector
<Use
*, 32> Worklist
;
178 SmallPtrSet
<Use
*, 32> Visited
;
180 auto AddUsesToWorklist
= [&](Value
*V
) {
181 for (auto &U
: V
->uses()) {
182 if (!Visited
.insert(&U
).second
)
184 Worklist
.push_back(&U
);
188 AddUsesToWorklist(Root
);
190 while (!Worklist
.empty()) {
191 Use
*U
= Worklist
.pop_back_val();
192 Instruction
*I
= cast
<Instruction
>(U
->getUser());
194 switch (I
->getOpcode()) {
195 case Instruction::Call
:
196 case Instruction::Invoke
: {
198 bool IsNocapture
= !CS
.isCallee(U
) &&
199 CS
.doesNotCapture(CS
.getArgumentNo(U
));
200 callUsesLocalStack(CS
, IsNocapture
);
202 // If the alloca-derived argument is passed in as nocapture, then it
203 // can't propagate to the call's return. That would be capturing.
208 case Instruction::Load
: {
209 // The result of a load is not alloca-derived (unless an alloca has
210 // otherwise escaped, but this is a local analysis).
213 case Instruction::Store
: {
214 if (U
->getOperandNo() == 0)
215 EscapePoints
.insert(I
);
216 continue; // Stores have no users to analyze.
218 case Instruction::BitCast
:
219 case Instruction::GetElementPtr
:
220 case Instruction::PHI
:
221 case Instruction::Select
:
222 case Instruction::AddrSpaceCast
:
225 EscapePoints
.insert(I
);
229 AddUsesToWorklist(I
);
233 void callUsesLocalStack(CallSite CS
, bool IsNocapture
) {
234 // Add it to the list of alloca users.
235 AllocaUsers
.insert(CS
.getInstruction());
237 // If it's nocapture then it can't capture this alloca.
241 // If it can write to memory, it can leak the alloca value.
242 if (!CS
.onlyReadsMemory())
243 EscapePoints
.insert(CS
.getInstruction());
246 SmallPtrSet
<Instruction
*, 32> AllocaUsers
;
247 SmallPtrSet
<Instruction
*, 32> EscapePoints
;
251 bool TailCallElim::markTails(Function
&F
, bool &AllCallsAreTailCalls
) {
252 if (F
.callsFunctionThatReturnsTwice())
254 AllCallsAreTailCalls
= true;
256 // The local stack holds all alloca instructions and all byval arguments.
257 AllocaDerivedValueTracker Tracker
;
258 for (Argument
&Arg
: F
.args()) {
259 if (Arg
.hasByValAttr())
264 if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(&I
))
268 bool Modified
= false;
270 // Track whether a block is reachable after an alloca has escaped. Blocks that
271 // contain the escaping instruction will be marked as being visited without an
272 // escaped alloca, since that is how the block began.
278 DenseMap
<BasicBlock
*, VisitType
> Visited
;
280 // We propagate the fact that an alloca has escaped from block to successor.
281 // Visit the blocks that are propagating the escapedness first. To do this, we
282 // maintain two worklists.
283 SmallVector
<BasicBlock
*, 32> WorklistUnescaped
, WorklistEscaped
;
285 // We may enter a block and visit it thinking that no alloca has escaped yet,
286 // then see an escape point and go back around a loop edge and come back to
287 // the same block twice. Because of this, we defer setting tail on calls when
288 // we first encounter them in a block. Every entry in this list does not
289 // statically use an alloca via use-def chain analysis, but may find an alloca
290 // through other means if the block turns out to be reachable after an escape
292 SmallVector
<CallInst
*, 32> DeferredTails
;
294 BasicBlock
*BB
= &F
.getEntryBlock();
295 VisitType Escaped
= UNESCAPED
;
297 for (auto &I
: *BB
) {
298 if (Tracker
.EscapePoints
.count(&I
))
301 CallInst
*CI
= dyn_cast
<CallInst
>(&I
);
302 if (!CI
|| CI
->isTailCall())
305 if (CI
->doesNotAccessMemory()) {
306 // A call to a readnone function whose arguments are all things computed
307 // outside this function can be marked tail. Even if you stored the
308 // alloca address into a global, a readnone function can't load the
311 // Note that this runs whether we know an alloca has escaped or not. If
312 // it has, then we can't trust Tracker.AllocaUsers to be accurate.
313 bool SafeToTail
= true;
314 for (auto &Arg
: CI
->arg_operands()) {
315 if (isa
<Constant
>(Arg
.getUser()))
317 if (Argument
*A
= dyn_cast
<Argument
>(Arg
.getUser()))
318 if (!A
->hasByValAttr())
324 emitOptimizationRemark(
325 F
.getContext(), "tailcallelim", F
, CI
->getDebugLoc(),
326 "marked this readnone call a tail call candidate");
333 if (Escaped
== UNESCAPED
&& !Tracker
.AllocaUsers
.count(CI
)) {
334 DeferredTails
.push_back(CI
);
336 AllCallsAreTailCalls
= false;
340 for (auto *SuccBB
: make_range(succ_begin(BB
), succ_end(BB
))) {
341 auto &State
= Visited
[SuccBB
];
342 if (State
< Escaped
) {
344 if (State
== ESCAPED
)
345 WorklistEscaped
.push_back(SuccBB
);
347 WorklistUnescaped
.push_back(SuccBB
);
351 if (!WorklistEscaped
.empty()) {
352 BB
= WorklistEscaped
.pop_back_val();
356 while (!WorklistUnescaped
.empty()) {
357 auto *NextBB
= WorklistUnescaped
.pop_back_val();
358 if (Visited
[NextBB
] == UNESCAPED
) {
367 for (CallInst
*CI
: DeferredTails
) {
368 if (Visited
[CI
->getParent()] != ESCAPED
) {
369 // If the escape point was part way through the block, calls after the
370 // escape point wouldn't have been put into DeferredTails.
371 emitOptimizationRemark(F
.getContext(), "tailcallelim", F
,
373 "marked this call a tail call candidate");
377 AllCallsAreTailCalls
= false;
384 bool TailCallElim::runTRE(Function
&F
) {
385 // If this function is a varargs function, we won't be able to PHI the args
386 // right, so don't even try to convert it...
387 if (F
.getFunctionType()->isVarArg()) return false;
389 TTI
= &getAnalysis
<TargetTransformInfo
>();
390 BasicBlock
*OldEntry
= nullptr;
391 bool TailCallsAreMarkedTail
= false;
392 SmallVector
<PHINode
*, 8> ArgumentPHIs
;
393 bool MadeChange
= false;
395 // CanTRETailMarkedCall - If false, we cannot perform TRE on tail calls
396 // marked with the 'tail' attribute, because doing so would cause the stack
397 // size to increase (real TRE would deallocate variable sized allocas, TRE
399 bool CanTRETailMarkedCall
= CanTRE(F
);
401 // Change any tail recursive calls to loops.
403 // FIXME: The code generator produces really bad code when an 'escaping
404 // alloca' is changed from being a static alloca to being a dynamic alloca.
405 // Until this is resolved, disable this transformation if that would ever
406 // happen. This bug is PR962.
407 SmallVector
<BasicBlock
*, 8> BBToErase
;
408 for (Function::iterator BB
= F
.begin(), E
= F
.end(); BB
!= E
; ++BB
) {
409 if (ReturnInst
*Ret
= dyn_cast
<ReturnInst
>(BB
->getTerminator())) {
410 bool Change
= ProcessReturningBlock(Ret
, OldEntry
, TailCallsAreMarkedTail
,
411 ArgumentPHIs
, !CanTRETailMarkedCall
);
412 if (!Change
&& BB
->getFirstNonPHIOrDbg() == Ret
) {
413 Change
= FoldReturnAndProcessPred(BB
, Ret
, OldEntry
,
414 TailCallsAreMarkedTail
, ArgumentPHIs
,
415 !CanTRETailMarkedCall
);
416 // FoldReturnAndProcessPred may have emptied some BB. Remember to
418 if (Change
&& BB
->empty())
419 BBToErase
.push_back(BB
);
422 MadeChange
|= Change
;
426 for (auto BB
: BBToErase
)
427 BB
->eraseFromParent();
429 // If we eliminated any tail recursions, it's possible that we inserted some
430 // silly PHI nodes which just merge an initial value (the incoming operand)
431 // with themselves. Check to see if we did and clean up our mess if so. This
432 // occurs when a function passes an argument straight through to its tail
434 for (unsigned i
= 0, e
= ArgumentPHIs
.size(); i
!= e
; ++i
) {
435 PHINode
*PN
= ArgumentPHIs
[i
];
437 // If the PHI Node is a dynamic constant, replace it with the value it is.
438 if (Value
*PNV
= SimplifyInstruction(PN
)) {
439 PN
->replaceAllUsesWith(PNV
);
440 PN
->eraseFromParent();
448 /// CanMoveAboveCall - Return true if it is safe to move the specified
449 /// instruction from after the call to before the call, assuming that all
450 /// instructions between the call and this instruction are movable.
452 bool TailCallElim::CanMoveAboveCall(Instruction
*I
, CallInst
*CI
) {
453 // FIXME: We can move load/store/call/free instructions above the call if the
454 // call does not mod/ref the memory location being processed.
455 if (I
->mayHaveSideEffects()) // This also handles volatile loads.
458 if (LoadInst
*L
= dyn_cast
<LoadInst
>(I
)) {
459 // Loads may always be moved above calls without side effects.
460 if (CI
->mayHaveSideEffects()) {
461 // Non-volatile loads may be moved above a call with side effects if it
462 // does not write to memory and the load provably won't trap.
463 // FIXME: Writes to memory only matter if they may alias the pointer
464 // being loaded from.
465 if (CI
->mayWriteToMemory() ||
466 !isSafeToLoadUnconditionally(L
->getPointerOperand(), L
,
467 L
->getAlignment(), DL
))
472 // Otherwise, if this is a side-effect free instruction, check to make sure
473 // that it does not use the return value of the call. If it doesn't use the
474 // return value of the call, it must only use things that are defined before
475 // the call, or movable instructions between the call and the instruction
477 for (unsigned i
= 0, e
= I
->getNumOperands(); i
!= e
; ++i
)
478 if (I
->getOperand(i
) == CI
)
483 // isDynamicConstant - Return true if the specified value is the same when the
484 // return would exit as it was when the initial iteration of the recursive
485 // function was executed.
487 // We currently handle static constants and arguments that are not modified as
488 // part of the recursion.
490 static bool isDynamicConstant(Value
*V
, CallInst
*CI
, ReturnInst
*RI
) {
491 if (isa
<Constant
>(V
)) return true; // Static constants are always dyn consts
493 // Check to see if this is an immutable argument, if so, the value
494 // will be available to initialize the accumulator.
495 if (Argument
*Arg
= dyn_cast
<Argument
>(V
)) {
496 // Figure out which argument number this is...
498 Function
*F
= CI
->getParent()->getParent();
499 for (Function::arg_iterator AI
= F
->arg_begin(); &*AI
!= Arg
; ++AI
)
502 // If we are passing this argument into call as the corresponding
503 // argument operand, then the argument is dynamically constant.
504 // Otherwise, we cannot transform this function safely.
505 if (CI
->getArgOperand(ArgNo
) == Arg
)
509 // Switch cases are always constant integers. If the value is being switched
510 // on and the return is only reachable from one of its cases, it's
511 // effectively constant.
512 if (BasicBlock
*UniquePred
= RI
->getParent()->getUniquePredecessor())
513 if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(UniquePred
->getTerminator()))
514 if (SI
->getCondition() == V
)
515 return SI
->getDefaultDest() != RI
->getParent();
517 // Not a constant or immutable argument, we can't safely transform.
521 // getCommonReturnValue - Check to see if the function containing the specified
522 // tail call consistently returns the same runtime-constant value at all exit
523 // points except for IgnoreRI. If so, return the returned value.
525 static Value
*getCommonReturnValue(ReturnInst
*IgnoreRI
, CallInst
*CI
) {
526 Function
*F
= CI
->getParent()->getParent();
527 Value
*ReturnedValue
= nullptr;
529 for (Function::iterator BBI
= F
->begin(), E
= F
->end(); BBI
!= E
; ++BBI
) {
530 ReturnInst
*RI
= dyn_cast
<ReturnInst
>(BBI
->getTerminator());
531 if (RI
== nullptr || RI
== IgnoreRI
) continue;
533 // We can only perform this transformation if the value returned is
534 // evaluatable at the start of the initial invocation of the function,
535 // instead of at the end of the evaluation.
537 Value
*RetOp
= RI
->getOperand(0);
538 if (!isDynamicConstant(RetOp
, CI
, RI
))
541 if (ReturnedValue
&& RetOp
!= ReturnedValue
)
542 return nullptr; // Cannot transform if differing values are returned.
543 ReturnedValue
= RetOp
;
545 return ReturnedValue
;
548 /// CanTransformAccumulatorRecursion - If the specified instruction can be
549 /// transformed using accumulator recursion elimination, return the constant
550 /// which is the start of the accumulator value. Otherwise return null.
552 Value
*TailCallElim::CanTransformAccumulatorRecursion(Instruction
*I
,
554 if (!I
->isAssociative() || !I
->isCommutative()) return nullptr;
555 assert(I
->getNumOperands() == 2 &&
556 "Associative/commutative operations should have 2 args!");
558 // Exactly one operand should be the result of the call instruction.
559 if ((I
->getOperand(0) == CI
&& I
->getOperand(1) == CI
) ||
560 (I
->getOperand(0) != CI
&& I
->getOperand(1) != CI
))
563 // The only user of this instruction we allow is a single return instruction.
564 if (!I
->hasOneUse() || !isa
<ReturnInst
>(I
->user_back()))
567 // Ok, now we have to check all of the other return instructions in this
568 // function. If they return non-constants or differing values, then we cannot
569 // transform the function safely.
570 return getCommonReturnValue(cast
<ReturnInst
>(I
->user_back()), CI
);
573 static Instruction
*FirstNonDbg(BasicBlock::iterator I
) {
574 while (isa
<DbgInfoIntrinsic
>(I
))
580 TailCallElim::FindTRECandidate(Instruction
*TI
,
581 bool CannotTailCallElimCallsMarkedTail
) {
582 BasicBlock
*BB
= TI
->getParent();
583 Function
*F
= BB
->getParent();
585 if (&BB
->front() == TI
) // Make sure there is something before the terminator.
588 // Scan backwards from the return, checking to see if there is a tail call in
589 // this block. If so, set CI to it.
590 CallInst
*CI
= nullptr;
591 BasicBlock::iterator BBI
= TI
;
593 CI
= dyn_cast
<CallInst
>(BBI
);
594 if (CI
&& CI
->getCalledFunction() == F
)
597 if (BBI
== BB
->begin())
598 return nullptr; // Didn't find a potential tail call.
602 // If this call is marked as a tail call, and if there are dynamic allocas in
603 // the function, we cannot perform this optimization.
604 if (CI
->isTailCall() && CannotTailCallElimCallsMarkedTail
)
607 // As a special case, detect code like this:
608 // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
609 // and disable this xform in this case, because the code generator will
610 // lower the call to fabs into inline code.
611 if (BB
== &F
->getEntryBlock() &&
612 FirstNonDbg(BB
->front()) == CI
&&
613 FirstNonDbg(std::next(BB
->begin())) == TI
&&
614 CI
->getCalledFunction() &&
615 !TTI
->isLoweredToCall(CI
->getCalledFunction())) {
616 // A single-block function with just a call and a return. Check that
617 // the arguments match.
618 CallSite::arg_iterator I
= CallSite(CI
).arg_begin(),
619 E
= CallSite(CI
).arg_end();
620 Function::arg_iterator FI
= F
->arg_begin(),
622 for (; I
!= E
&& FI
!= FE
; ++I
, ++FI
)
623 if (*I
!= &*FI
) break;
624 if (I
== E
&& FI
== FE
)
631 bool TailCallElim::EliminateRecursiveTailCall(CallInst
*CI
, ReturnInst
*Ret
,
632 BasicBlock
*&OldEntry
,
633 bool &TailCallsAreMarkedTail
,
634 SmallVectorImpl
<PHINode
*> &ArgumentPHIs
,
635 bool CannotTailCallElimCallsMarkedTail
) {
636 // If we are introducing accumulator recursion to eliminate operations after
637 // the call instruction that are both associative and commutative, the initial
638 // value for the accumulator is placed in this variable. If this value is set
639 // then we actually perform accumulator recursion elimination instead of
640 // simple tail recursion elimination. If the operation is an LLVM instruction
641 // (eg: "add") then it is recorded in AccumulatorRecursionInstr. If not, then
642 // we are handling the case when the return instruction returns a constant C
643 // which is different to the constant returned by other return instructions
644 // (which is recorded in AccumulatorRecursionEliminationInitVal). This is a
645 // special case of accumulator recursion, the operation being "return C".
646 Value
*AccumulatorRecursionEliminationInitVal
= nullptr;
647 Instruction
*AccumulatorRecursionInstr
= nullptr;
649 // Ok, we found a potential tail call. We can currently only transform the
650 // tail call if all of the instructions between the call and the return are
651 // movable to above the call itself, leaving the call next to the return.
652 // Check that this is the case now.
653 BasicBlock::iterator BBI
= CI
;
654 for (++BBI
; &*BBI
!= Ret
; ++BBI
) {
655 if (CanMoveAboveCall(BBI
, CI
)) continue;
657 // If we can't move the instruction above the call, it might be because it
658 // is an associative and commutative operation that could be transformed
659 // using accumulator recursion elimination. Check to see if this is the
660 // case, and if so, remember the initial accumulator value for later.
661 if ((AccumulatorRecursionEliminationInitVal
=
662 CanTransformAccumulatorRecursion(BBI
, CI
))) {
663 // Yes, this is accumulator recursion. Remember which instruction
665 AccumulatorRecursionInstr
= BBI
;
667 return false; // Otherwise, we cannot eliminate the tail recursion!
671 // We can only transform call/return pairs that either ignore the return value
672 // of the call and return void, ignore the value of the call and return a
673 // constant, return the value returned by the tail call, or that are being
674 // accumulator recursion variable eliminated.
675 if (Ret
->getNumOperands() == 1 && Ret
->getReturnValue() != CI
&&
676 !isa
<UndefValue
>(Ret
->getReturnValue()) &&
677 AccumulatorRecursionEliminationInitVal
== nullptr &&
678 !getCommonReturnValue(nullptr, CI
)) {
679 // One case remains that we are able to handle: the current return
680 // instruction returns a constant, and all other return instructions
681 // return a different constant.
682 if (!isDynamicConstant(Ret
->getReturnValue(), CI
, Ret
))
683 return false; // Current return instruction does not return a constant.
684 // Check that all other return instructions return a common constant. If
685 // so, record it in AccumulatorRecursionEliminationInitVal.
686 AccumulatorRecursionEliminationInitVal
= getCommonReturnValue(Ret
, CI
);
687 if (!AccumulatorRecursionEliminationInitVal
)
691 BasicBlock
*BB
= Ret
->getParent();
692 Function
*F
= BB
->getParent();
694 emitOptimizationRemark(F
->getContext(), "tailcallelim", *F
, CI
->getDebugLoc(),
695 "transforming tail recursion to loop");
697 // OK! We can transform this tail call. If this is the first one found,
698 // create the new entry block, allowing us to branch back to the old entry.
700 OldEntry
= &F
->getEntryBlock();
701 BasicBlock
*NewEntry
= BasicBlock::Create(F
->getContext(), "", F
, OldEntry
);
702 NewEntry
->takeName(OldEntry
);
703 OldEntry
->setName("tailrecurse");
704 BranchInst::Create(OldEntry
, NewEntry
);
706 // If this tail call is marked 'tail' and if there are any allocas in the
707 // entry block, move them up to the new entry block.
708 TailCallsAreMarkedTail
= CI
->isTailCall();
709 if (TailCallsAreMarkedTail
)
710 // Move all fixed sized allocas from OldEntry to NewEntry.
711 for (BasicBlock::iterator OEBI
= OldEntry
->begin(), E
= OldEntry
->end(),
712 NEBI
= NewEntry
->begin(); OEBI
!= E
; )
713 if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(OEBI
++))
714 if (isa
<ConstantInt
>(AI
->getArraySize()))
715 AI
->moveBefore(NEBI
);
717 // Now that we have created a new block, which jumps to the entry
718 // block, insert a PHI node for each argument of the function.
719 // For now, we initialize each PHI to only have the real arguments
720 // which are passed in.
721 Instruction
*InsertPos
= OldEntry
->begin();
722 for (Function::arg_iterator I
= F
->arg_begin(), E
= F
->arg_end();
724 PHINode
*PN
= PHINode::Create(I
->getType(), 2,
725 I
->getName() + ".tr", InsertPos
);
726 I
->replaceAllUsesWith(PN
); // Everyone use the PHI node now!
727 PN
->addIncoming(I
, NewEntry
);
728 ArgumentPHIs
.push_back(PN
);
732 // If this function has self recursive calls in the tail position where some
733 // are marked tail and some are not, only transform one flavor or another. We
734 // have to choose whether we move allocas in the entry block to the new entry
735 // block or not, so we can't make a good choice for both. NOTE: We could do
736 // slightly better here in the case that the function has no entry block
738 if (TailCallsAreMarkedTail
&& !CI
->isTailCall())
741 // Ok, now that we know we have a pseudo-entry block WITH all of the
742 // required PHI nodes, add entries into the PHI node for the actual
743 // parameters passed into the tail-recursive call.
744 for (unsigned i
= 0, e
= CI
->getNumArgOperands(); i
!= e
; ++i
)
745 ArgumentPHIs
[i
]->addIncoming(CI
->getArgOperand(i
), BB
);
747 // If we are introducing an accumulator variable to eliminate the recursion,
748 // do so now. Note that we _know_ that no subsequent tail recursion
749 // eliminations will happen on this function because of the way the
750 // accumulator recursion predicate is set up.
752 if (AccumulatorRecursionEliminationInitVal
) {
753 Instruction
*AccRecInstr
= AccumulatorRecursionInstr
;
754 // Start by inserting a new PHI node for the accumulator.
755 pred_iterator PB
= pred_begin(OldEntry
), PE
= pred_end(OldEntry
);
757 PHINode::Create(AccumulatorRecursionEliminationInitVal
->getType(),
758 std::distance(PB
, PE
) + 1,
759 "accumulator.tr", OldEntry
->begin());
761 // Loop over all of the predecessors of the tail recursion block. For the
762 // real entry into the function we seed the PHI with the initial value,
763 // computed earlier. For any other existing branches to this block (due to
764 // other tail recursions eliminated) the accumulator is not modified.
765 // Because we haven't added the branch in the current block to OldEntry yet,
766 // it will not show up as a predecessor.
767 for (pred_iterator PI
= PB
; PI
!= PE
; ++PI
) {
769 if (P
== &F
->getEntryBlock())
770 AccPN
->addIncoming(AccumulatorRecursionEliminationInitVal
, P
);
772 AccPN
->addIncoming(AccPN
, P
);
776 // Add an incoming argument for the current block, which is computed by
777 // our associative and commutative accumulator instruction.
778 AccPN
->addIncoming(AccRecInstr
, BB
);
780 // Next, rewrite the accumulator recursion instruction so that it does not
781 // use the result of the call anymore, instead, use the PHI node we just
783 AccRecInstr
->setOperand(AccRecInstr
->getOperand(0) != CI
, AccPN
);
785 // Add an incoming argument for the current block, which is just the
786 // constant returned by the current return instruction.
787 AccPN
->addIncoming(Ret
->getReturnValue(), BB
);
790 // Finally, rewrite any return instructions in the program to return the PHI
791 // node instead of the "initval" that they do currently. This loop will
792 // actually rewrite the return value we are destroying, but that's ok.
793 for (Function::iterator BBI
= F
->begin(), E
= F
->end(); BBI
!= E
; ++BBI
)
794 if (ReturnInst
*RI
= dyn_cast
<ReturnInst
>(BBI
->getTerminator()))
795 RI
->setOperand(0, AccPN
);
799 // Now that all of the PHI nodes are in place, remove the call and
800 // ret instructions, replacing them with an unconditional branch.
801 BranchInst
*NewBI
= BranchInst::Create(OldEntry
, Ret
);
802 NewBI
->setDebugLoc(CI
->getDebugLoc());
804 BB
->getInstList().erase(Ret
); // Remove return.
805 BB
->getInstList().erase(CI
); // Remove call.
810 bool TailCallElim::FoldReturnAndProcessPred(BasicBlock
*BB
,
811 ReturnInst
*Ret
, BasicBlock
*&OldEntry
,
812 bool &TailCallsAreMarkedTail
,
813 SmallVectorImpl
<PHINode
*> &ArgumentPHIs
,
814 bool CannotTailCallElimCallsMarkedTail
) {
817 // If the return block contains nothing but the return and PHI's,
818 // there might be an opportunity to duplicate the return in its
819 // predecessors and perform TRC there. Look for predecessors that end
820 // in unconditional branch and recursive call(s).
821 SmallVector
<BranchInst
*, 8> UncondBranchPreds
;
822 for (pred_iterator PI
= pred_begin(BB
), E
= pred_end(BB
); PI
!= E
; ++PI
) {
823 BasicBlock
*Pred
= *PI
;
824 TerminatorInst
*PTI
= Pred
->getTerminator();
825 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(PTI
))
826 if (BI
->isUnconditional())
827 UncondBranchPreds
.push_back(BI
);
830 while (!UncondBranchPreds
.empty()) {
831 BranchInst
*BI
= UncondBranchPreds
.pop_back_val();
832 BasicBlock
*Pred
= BI
->getParent();
833 if (CallInst
*CI
= FindTRECandidate(BI
, CannotTailCallElimCallsMarkedTail
)){
834 DEBUG(dbgs() << "FOLDING: " << *BB
835 << "INTO UNCOND BRANCH PRED: " << *Pred
);
836 ReturnInst
*RI
= FoldReturnIntoUncondBranch(Ret
, BB
, Pred
);
838 // Cleanup: if all predecessors of BB have been eliminated by
839 // FoldReturnIntoUncondBranch, we would like to delete it, but we
840 // can not just nuke it as it is being used as an iterator by our caller.
841 // Just empty it, and the caller will erase it when it is safe to do so.
842 // It is important to empty it, because the ret instruction in there is
843 // still using a value which EliminateRecursiveTailCall will attempt
845 if (!BB
->hasAddressTaken() && pred_begin(BB
) == pred_end(BB
))
846 BB
->getInstList().clear();
848 EliminateRecursiveTailCall(CI
, RI
, OldEntry
, TailCallsAreMarkedTail
,
850 CannotTailCallElimCallsMarkedTail
);
860 TailCallElim::ProcessReturningBlock(ReturnInst
*Ret
, BasicBlock
*&OldEntry
,
861 bool &TailCallsAreMarkedTail
,
862 SmallVectorImpl
<PHINode
*> &ArgumentPHIs
,
863 bool CannotTailCallElimCallsMarkedTail
) {
864 CallInst
*CI
= FindTRECandidate(Ret
, CannotTailCallElimCallsMarkedTail
);
868 return EliminateRecursiveTailCall(CI
, Ret
, OldEntry
, TailCallsAreMarkedTail
,
870 CannotTailCallElimCallsMarkedTail
);