1//===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file transforms calls of the current function (self recursion) followed
10// by a return instruction with a branch to the entry of the function, creating
11// a loop. This pass also implements the following extensions to the basic
12// algorithm:
13//
14// 1. Trivial instructions between the call and return do not prevent the
15// transformation from taking place, though currently the analysis cannot
16// support moving any really useful instructions (only dead ones).
17// 2. This pass transforms functions that are prevented from being tail
18// recursive by an associative and commutative expression to use an
19// accumulator variable, thus compiling the typical naive factorial or
20// 'fib' implementation into efficient code.
21// 3. TRE is performed if the function returns void, if the return
22// returns the result returned by the call, or if the function returns a
23// run-time constant on all exits from the function. It is possible, though
24// unlikely, that the return returns something else (like constant 0), and
25// can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in
26// the function return the exact same value.
27// 4. If it can prove that callees do not access their caller stack frame,
28// they are marked as eligible for tail call elimination (by the code
29// generator).
30//
31// There are several improvements that could be made:
32//
33// 1. If the function has any alloca instructions, these instructions will be
34// moved out of the entry block of the function, causing them to be
35// evaluated each time through the tail recursion. Safely keeping allocas
36// in the entry block requires analysis to proves that the tail-called
37// function does not read or write the stack object.
38// 2. Tail recursion is only performed if the call immediately precedes the
39// return instruction. It's possible that there could be a jump between
40// the call and the return.
41// 3. There can be intervening operations between the call and the return that
42// prevent the TRE from occurring. For example, there could be GEP's and
43// stores to memory that will not be read or written by the call. This
44// requires some substantial analysis (such as with DSA) to prove safe to
45// move ahead of the call, but doing so could allow many more TREs to be
46// performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark.
47// 4. The algorithm we use to detect if callees access their caller stack
48// frames is very primitive.
49//
50//===----------------------------------------------------------------------===//
51
52#include "llvm/Transforms/Scalar/TailRecursionElimination.h"
53#include "llvm/ADT/STLExtras.h"
54#include "llvm/ADT/SmallPtrSet.h"
55#include "llvm/ADT/Statistic.h"
56#include "llvm/Analysis/BlockFrequencyInfo.h"
57#include "llvm/Analysis/DomTreeUpdater.h"
58#include "llvm/Analysis/GlobalsModRef.h"
59#include "llvm/Analysis/InstructionSimplify.h"
60#include "llvm/Analysis/Loads.h"
61#include "llvm/Analysis/OptimizationRemarkEmitter.h"
62#include "llvm/Analysis/PostDominators.h"
63#include "llvm/Analysis/ProfileSummaryInfo.h"
64#include "llvm/Analysis/TargetTransformInfo.h"
65#include "llvm/Analysis/ValueTracking.h"
66#include "llvm/IR/CFG.h"
67#include "llvm/IR/Constants.h"
68#include "llvm/IR/DataLayout.h"
69#include "llvm/IR/DerivedTypes.h"
70#include "llvm/IR/DiagnosticInfo.h"
71#include "llvm/IR/Dominators.h"
72#include "llvm/IR/Function.h"
73#include "llvm/IR/IRBuilder.h"
74#include "llvm/IR/InstIterator.h"
75#include "llvm/IR/Instructions.h"
76#include "llvm/IR/IntrinsicInst.h"
77#include "llvm/IR/Module.h"
78#include "llvm/InitializePasses.h"
79#include "llvm/Pass.h"
80#include "llvm/Support/CommandLine.h"
81#include "llvm/Support/Debug.h"
82#include "llvm/Support/raw_ostream.h"
83#include "llvm/Transforms/Scalar.h"
84#include "llvm/Transforms/Utils/BasicBlockUtils.h"
85#include <cmath>
86using namespace llvm;
87
88#define DEBUG_TYPE "tailcallelim"
89
90STATISTIC(NumEliminated, "Number of tail calls removed");
91STATISTIC(NumRetDuped, "Number of return duplicated");
92STATISTIC(NumAccumAdded, "Number of accumulators introduced");
93STATISTIC(NumTREPreventedCold,
94 "Number of tail calls/recursion eliminations prevented due to cold "
95 "calling convention or attribute");
96
97static cl::opt<bool> DisableEntryCountRecompute(
98 "tre-disable-entrycount-recompute", cl::init(Val: false), cl::Hidden,
99 cl::desc("Force disabling recomputing of function entry count, on "
100 "successful tail recursion elimination."));
101
102static cl::opt<bool> DisableTailCallElimForColdCalls(
103 "disable-tail-call-elim-for-cold-calls", cl::Hidden, cl::init(Val: false),
104 cl::desc("Disable tail call elimination and optimization for cold calls or "
105 "in cold functions"));
106
107static bool shouldDisableTailCallsForCold(const CallBase *CB,
108 const Function *Caller,
109 const ProfileSummaryInfo *PSI,
110 BlockFrequencyInfo *BFI) {
111 if (!DisableTailCallElimForColdCalls)
112 return false;
113
114 if (CB && CB->isMustTailCall())
115 return false;
116
117 if (CB && (CB->hasFnAttr(Kind: Attribute::Cold) ||
118 CB->getCallingConv() == CallingConv::Cold))
119 return true;
120
121 if (Caller && (Caller->hasFnAttribute(Kind: Attribute::Cold) ||
122 Caller->getCallingConv() == CallingConv::Cold))
123 return true;
124
125 if (!PSI || !PSI->hasProfileSummary())
126 return false;
127
128 if (CB && BFI &&
129 (PSI->isColdCallSite(CB: *CB, BFI) || PSI->isColdBlock(BB: CB->getParent(), BFI)))
130 return true;
131
132 return false;
133}
134
135/// Scan the specified function for alloca instructions.
136/// If it contains any dynamic allocas, returns false.
137static bool canTRE(Function &F) {
138 // TODO: We don't do TRE if dynamic allocas are used.
139 // Dynamic allocas allocate stack space which should be
140 // deallocated before new iteration started. That is
141 // currently not implemented.
142 return llvm::all_of(Range: instructions(F), P: [](Instruction &I) {
143 auto *AI = dyn_cast<AllocaInst>(Val: &I);
144 return !AI || AI->isStaticAlloca();
145 });
146}
147
148namespace {
149struct AllocaDerivedValueTracker {
150 // Start at a root value and walk its use-def chain to mark calls that use the
151 // value or a derived value in AllocaUsers, and places where it may escape in
152 // EscapePoints.
153 void walk(Value *Root) {
154 SmallVector<Use *, 32> Worklist;
155 SmallPtrSet<Use *, 32> Visited;
156
157 auto AddUsesToWorklist = [&](Value *V) {
158 for (auto &U : V->uses()) {
159 if (!Visited.insert(Ptr: &U).second)
160 continue;
161 Worklist.push_back(Elt: &U);
162 }
163 };
164
165 AddUsesToWorklist(Root);
166
167 while (!Worklist.empty()) {
168 Use *U = Worklist.pop_back_val();
169 Instruction *I = cast<Instruction>(Val: U->getUser());
170
171 switch (I->getOpcode()) {
172 case Instruction::Call:
173 case Instruction::Invoke: {
174 auto &CB = cast<CallBase>(Val&: *I);
175 // If the alloca-derived argument is passed byval it is not an escape
176 // point, or a use of an alloca. Calling with byval copies the contents
177 // of the alloca into argument registers or stack slots, which exist
178 // beyond the lifetime of the current frame.
179 if (CB.isArgOperand(U) && CB.isByValArgument(ArgNo: CB.getArgOperandNo(U)))
180 continue;
181 bool IsNocapture =
182 CB.isDataOperand(U) && CB.doesNotCapture(OpNo: CB.getDataOperandNo(U));
183 callUsesLocalStack(CB, IsNocapture);
184 if (IsNocapture) {
185 // If the alloca-derived argument is passed in as nocapture, then it
186 // can't propagate to the call's return. That would be capturing.
187 continue;
188 }
189 break;
190 }
191 case Instruction::Load: {
192 // The result of a load is not alloca-derived (unless an alloca has
193 // otherwise escaped, but this is a local analysis).
194 continue;
195 }
196 case Instruction::Store: {
197 if (U->getOperandNo() == 0)
198 EscapePoints.insert(Ptr: I);
199 continue; // Stores have no users to analyze.
200 }
201 case Instruction::BitCast:
202 case Instruction::GetElementPtr:
203 case Instruction::PHI:
204 case Instruction::Select:
205 case Instruction::AddrSpaceCast:
206 break;
207 default:
208 EscapePoints.insert(Ptr: I);
209 break;
210 }
211
212 AddUsesToWorklist(I);
213 }
214 }
215
216 void callUsesLocalStack(CallBase &CB, bool IsNocapture) {
217 // Add it to the list of alloca users.
218 AllocaUsers.insert(Ptr: &CB);
219
220 // If it's nocapture then it can't capture this alloca.
221 if (IsNocapture)
222 return;
223
224 // If it can write to memory, it can leak the alloca value.
225 if (!CB.onlyReadsMemory())
226 EscapePoints.insert(Ptr: &CB);
227 }
228
229 SmallPtrSet<Instruction *, 32> AllocaUsers;
230 SmallPtrSet<Instruction *, 32> EscapePoints;
231};
232} // namespace
233
234static bool markTails(Function &F, OptimizationRemarkEmitter *ORE,
235 ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
236 if (F.callsFunctionThatReturnsTwice())
237 return false;
238
239 // The local stack holds all alloca instructions and all byval arguments.
240 AllocaDerivedValueTracker Tracker;
241 for (Argument &Arg : F.args()) {
242 if (Arg.hasByValAttr())
243 Tracker.walk(Root: &Arg);
244 }
245 for (auto &BB : F) {
246 for (auto &I : BB)
247 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: &I))
248 Tracker.walk(Root: AI);
249 }
250
251 bool Modified = false;
252
253 // Track whether a block is reachable after an alloca has escaped. Blocks that
254 // contain the escaping instruction will be marked as being visited without an
255 // escaped alloca, since that is how the block began.
256 enum VisitType {
257 UNVISITED,
258 UNESCAPED,
259 ESCAPED
260 };
261 DenseMap<BasicBlock *, VisitType> Visited;
262
263 // We propagate the fact that an alloca has escaped from block to successor.
264 // Visit the blocks that are propagating the escapedness first. To do this, we
265 // maintain two worklists.
266 SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped;
267
268 // We may enter a block and visit it thinking that no alloca has escaped yet,
269 // then see an escape point and go back around a loop edge and come back to
270 // the same block twice. Because of this, we defer setting tail on calls when
271 // we first encounter them in a block. Every entry in this list does not
272 // statically use an alloca via use-def chain analysis, but may find an alloca
273 // through other means if the block turns out to be reachable after an escape
274 // point.
275 SmallVector<CallInst *, 32> DeferredTails;
276
277 BasicBlock *BB = &F.getEntryBlock();
278 VisitType Escaped = UNESCAPED;
279 do {
280 for (auto &I : *BB) {
281 if (Tracker.EscapePoints.count(Ptr: &I))
282 Escaped = ESCAPED;
283
284 CallInst *CI = dyn_cast<CallInst>(Val: &I);
285 // A PseudoProbeInst has the IntrInaccessibleMemOnly tag hence it is
286 // considered accessing memory and will be marked as a tail call if we
287 // don't bail out here.
288 if (!CI || CI->isTailCall() || isa<PseudoProbeInst>(Val: &I))
289 continue;
290
291 // Bail out for intrinsic stackrestore call because it can modify
292 // unescaped allocas.
293 if (auto *II = dyn_cast<IntrinsicInst>(Val: CI))
294 if (II->getIntrinsicID() == Intrinsic::stackrestore)
295 continue;
296
297 // Special-case operand bundles "clang.arc.attachedcall", "ptrauth", and
298 // "kcfi".
299 bool DisableForCold = shouldDisableTailCallsForCold(CB: CI, Caller: &F, PSI, BFI);
300 bool IsNoTail = CI->isNoTailCall() || DisableForCold ||
301 CI->hasOperandBundlesOtherThan(
302 IDs: {LLVMContext::OB_clang_arc_attachedcall,
303 LLVMContext::OB_ptrauth, LLVMContext::OB_kcfi});
304 if (!CI->isNoTailCall() && DisableForCold)
305 ++NumTREPreventedCold;
306
307 if (!IsNoTail && CI->doesNotAccessMemory()) {
308 // A call to a readnone function whose arguments are all things computed
309 // outside this function can be marked tail. Even if you stored the
310 // alloca address into a global, a readnone function can't load the
311 // global anyhow.
312 //
313 // Note that this runs whether we know an alloca has escaped or not. If
314 // it has, then we can't trust Tracker.AllocaUsers to be accurate.
315 bool SafeToTail = true;
316 for (auto &Arg : CI->args()) {
317 if (isa<Constant>(Val: Arg.getUser()))
318 continue;
319 if (Argument *A = dyn_cast<Argument>(Val: Arg.getUser()))
320 if (!A->hasByValAttr())
321 continue;
322 SafeToTail = false;
323 break;
324 }
325 if (SafeToTail) {
326 using namespace ore;
327 ORE->emit(RemarkBuilder: [&]() {
328 return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI)
329 << "marked as tail call candidate (readnone)";
330 });
331 CI->setTailCall();
332 Modified = true;
333 continue;
334 }
335 }
336
337 if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(Ptr: CI))
338 DeferredTails.push_back(Elt: CI);
339 }
340
341 for (auto *SuccBB : successors(BB)) {
342 auto &State = Visited[SuccBB];
343 if (State < Escaped) {
344 State = Escaped;
345 if (State == ESCAPED)
346 WorklistEscaped.push_back(Elt: SuccBB);
347 else
348 WorklistUnescaped.push_back(Elt: SuccBB);
349 }
350 }
351
352 if (!WorklistEscaped.empty()) {
353 BB = WorklistEscaped.pop_back_val();
354 Escaped = ESCAPED;
355 } else {
356 BB = nullptr;
357 while (!WorklistUnescaped.empty()) {
358 auto *NextBB = WorklistUnescaped.pop_back_val();
359 if (Visited[NextBB] == UNESCAPED) {
360 BB = NextBB;
361 Escaped = UNESCAPED;
362 break;
363 }
364 }
365 }
366 } while (BB);
367
368 for (CallInst *CI : DeferredTails) {
369 if (Visited[CI->getParent()] != ESCAPED) {
370 // If the escape point was part way through the block, calls after the
371 // escape point wouldn't have been put into DeferredTails.
372 LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n");
373 CI->setTailCall();
374 Modified = true;
375 }
376 }
377
378 return Modified;
379}
380
381/// Return true if it is safe to move the specified
382/// instruction from after the call to before the call, assuming that all
383/// instructions between the call and this instruction are movable.
384///
385static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA) {
386 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I))
387 if (II->getIntrinsicID() == Intrinsic::lifetime_end)
388 return true;
389
390 // FIXME: We can move load/store/call/free instructions above the call if the
391 // call does not mod/ref the memory location being processed.
392 if (I->mayHaveSideEffects()) // This also handles volatile loads.
393 return false;
394
395 if (LoadInst *L = dyn_cast<LoadInst>(Val: I)) {
396 // Loads may always be moved above calls without side effects.
397 if (CI->mayHaveSideEffects()) {
398 // Non-volatile loads may be moved above a call with side effects if it
399 // does not write to memory and the load provably won't trap.
400 // Writes to memory only matter if they may alias the pointer
401 // being loaded from.
402 const DataLayout &DL = L->getDataLayout();
403 if (isModSet(MRI: AA->getModRefInfo(I: CI, OptLoc: MemoryLocation::get(LI: L))) ||
404 !isSafeToLoadUnconditionally(V: L->getPointerOperand(), Ty: L->getType(),
405 Alignment: L->getAlign(), DL, ScanFrom: L))
406 return false;
407 }
408 }
409
410 // Otherwise, if this is a side-effect free instruction, check to make sure
411 // that it does not use the return value of the call. If it doesn't use the
412 // return value of the call, it must only use things that are defined before
413 // the call, or movable instructions between the call and the instruction
414 // itself.
415 return !is_contained(Range: I->operands(), Element: CI);
416}
417
418static bool canTransformAccumulatorRecursion(Instruction *I, CallInst *CI) {
419 if (!I->isAssociative() || !I->isCommutative())
420 return false;
421
422 assert(I->getNumOperands() >= 2 &&
423 "Associative/commutative operations should have at least 2 args!");
424
425 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
426 // Accumulators must have an identity.
427 if (!ConstantExpr::getIntrinsicIdentity(II->getIntrinsicID(), Ty: I->getType()))
428 return false;
429 }
430
431 // Exactly one operand should be the result of the call instruction.
432 if ((I->getOperand(i: 0) == CI && I->getOperand(i: 1) == CI) ||
433 (I->getOperand(i: 0) != CI && I->getOperand(i: 1) != CI))
434 return false;
435
436 // The only user of this instruction we allow is a single return instruction.
437 if (!I->hasOneUse() || !isa<ReturnInst>(Val: I->user_back()))
438 return false;
439
440 return true;
441}
442
443namespace {
444class TailRecursionEliminator {
445 Function &F;
446 const TargetTransformInfo *TTI;
447 AliasAnalysis *AA;
448 OptimizationRemarkEmitter *ORE;
449 DomTreeUpdater &DTU;
450 BlockFrequencyInfo *const BFI;
451 ProfileSummaryInfo *const PSI;
452 const bool UpdateFunctionEntryCount;
453 const uint64_t OrigEntryBBFreq;
454 const uint64_t OrigEntryCount;
455
456 // The below are shared state we want to have available when eliminating any
457 // calls in the function. There values should be populated by
458 // createTailRecurseLoopHeader the first time we find a call we can eliminate.
459 BasicBlock *HeaderBB = nullptr;
460 SmallVector<PHINode *, 8> ArgumentPHIs;
461
462 // PHI node to store our return value.
463 PHINode *RetPN = nullptr;
464
465 // i1 PHI node to track if we have a valid return value stored in RetPN.
466 PHINode *RetKnownPN = nullptr;
467
468 // Vector of select instructions we insereted. These selects use RetKnownPN
469 // to either propagate RetPN or select a new return value.
470 SmallVector<SelectInst *, 8> RetSelects;
471
472 // The below are shared state needed when performing accumulator recursion.
473 // There values should be populated by insertAccumulator the first time we
474 // find an elimination that requires an accumulator.
475
476 // PHI node to store our current accumulated value.
477 PHINode *AccPN = nullptr;
478
479 // The instruction doing the accumulating.
480 Instruction *AccumulatorRecursionInstr = nullptr;
481
482 TailRecursionEliminator(Function &F, const TargetTransformInfo *TTI,
483 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE,
484 DomTreeUpdater &DTU, BlockFrequencyInfo *BFI,
485 ProfileSummaryInfo *PSI,
486 bool UpdateFunctionEntryCount)
487 : F(F), TTI(TTI), AA(AA), ORE(ORE), DTU(DTU), BFI(BFI), PSI(PSI),
488 UpdateFunctionEntryCount(UpdateFunctionEntryCount),
489 OrigEntryBBFreq(
490 BFI ? BFI->getBlockFreq(BB: &F.getEntryBlock()).getFrequency() : 0U),
491 OrigEntryCount(F.getEntryCount() ? *F.getEntryCount() : 0) {
492 if (BFI) {
493 // The assert is meant as API documentation for the caller.
494 assert(OrigEntryBBFreq != 0 &&
495 "If a BFI was provided, the function should have an entry "
496 "basic block with a non-zero frequency.");
497 }
498 }
499
500 CallInst *findTRECandidate(BasicBlock *BB);
501
502 void createTailRecurseLoopHeader(CallInst *CI);
503
504 void insertAccumulator(Instruction *AccRecInstr);
505
506 bool eliminateCall(CallInst *CI);
507
508 void cleanupAndFinalize();
509
510 bool processBlock(BasicBlock &BB);
511
512 void copyByValueOperandIntoLocalTemp(CallInst *CI, int OpndIdx);
513
514 void copyLocalTempOfByValueOperandIntoArguments(CallInst *CI, int OpndIdx);
515
516public:
517 static bool eliminate(Function &F, const TargetTransformInfo *TTI,
518 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE,
519 DomTreeUpdater &DTU, BlockFrequencyInfo *BFI,
520 ProfileSummaryInfo *PSI, bool UpdateFunctionEntryCount);
521};
522} // namespace
523
524CallInst *TailRecursionEliminator::findTRECandidate(BasicBlock *BB) {
525 Instruction *TI = BB->getTerminator();
526
527 if (&BB->front() == TI) // Make sure there is something before the terminator.
528 return nullptr;
529
530 // Scan backwards from the return, checking to see if there is a tail call in
531 // this block. If so, set CI to it.
532 CallInst *CI = nullptr;
533 BasicBlock::iterator BBI(TI);
534 while (true) {
535 CI = dyn_cast<CallInst>(Val&: BBI);
536 if (CI && CI->getCalledFunction() == &F)
537 break;
538
539 if (BBI == BB->begin())
540 return nullptr; // Didn't find a potential tail call.
541 --BBI;
542 }
543
544 assert((!CI->isTailCall() || !CI->isNoTailCall()) &&
545 "Incompatible call site attributes(Tail,NoTail)");
546 if (!CI->isTailCall() || shouldDisableTailCallsForCold(CB: CI, Caller: &F, PSI, BFI))
547 return nullptr;
548
549 // As a special case, detect code like this:
550 // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
551 // and disable this xform in this case, because the code generator will
552 // lower the call to fabs into inline code.
553 if (BB == &F.getEntryBlock() && &BB->front() == CI &&
554 &*std::next(x: BB->begin()) == TI && CI->getCalledFunction() &&
555 !TTI->isLoweredToCall(F: CI->getCalledFunction())) {
556 // A single-block function with just a call and a return. Check that
557 // the arguments match.
558 auto I = CI->arg_begin(), E = CI->arg_end();
559 Function::arg_iterator FI = F.arg_begin(), FE = F.arg_end();
560 for (; I != E && FI != FE; ++I, ++FI)
561 if (*I != &*FI) break;
562 if (I == E && FI == FE)
563 return nullptr;
564 }
565
566 return CI;
567}
568
569void TailRecursionEliminator::createTailRecurseLoopHeader(CallInst *CI) {
570 HeaderBB = &F.getEntryBlock();
571 BasicBlock *NewEntry = BasicBlock::Create(Context&: F.getContext(), Name: "", Parent: &F, InsertBefore: HeaderBB);
572 NewEntry->takeName(V: HeaderBB);
573 HeaderBB->setName("tailrecurse");
574 auto *BI = UncondBrInst::Create(Target: HeaderBB, InsertBefore: NewEntry);
575 BI->setDebugLoc(DebugLoc::getCompilerGenerated());
576 // If the new branch preserves the debug location of CI, it could result in
577 // misleading stepping, if CI is located in a conditional branch.
578 // So, here we don't give any debug location to the new branch.
579
580 // Move all fixed sized allocas from HeaderBB to NewEntry.
581 for (BasicBlock::iterator OEBI = HeaderBB->begin(), E = HeaderBB->end(),
582 NEBI = NewEntry->begin();
583 OEBI != E;)
584 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: OEBI++))
585 if (isa<ConstantInt>(Val: AI->getArraySize()))
586 AI->moveBefore(InsertPos: NEBI);
587
588 // Now that we have created a new block, which jumps to the entry
589 // block, insert a PHI node for each argument of the function.
590 // For now, we initialize each PHI to only have the real arguments
591 // which are passed in.
592 BasicBlock::iterator InsertPos = HeaderBB->begin();
593 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
594 PHINode *PN = PHINode::Create(Ty: I->getType(), NumReservedValues: 2, NameStr: I->getName() + ".tr");
595 PN->insertBefore(InsertPos);
596 I->replaceAllUsesWith(V: PN); // Everyone use the PHI node now!
597 PN->addIncoming(V: &*I, BB: NewEntry);
598 ArgumentPHIs.push_back(Elt: PN);
599 }
600
601 // If the function doen't return void, create the RetPN and RetKnownPN PHI
602 // nodes to track our return value. We initialize RetPN with poison and
603 // RetKnownPN with false since we can't know our return value at function
604 // entry.
605 Type *RetType = F.getReturnType();
606 if (!RetType->isVoidTy()) {
607 Type *BoolType = Type::getInt1Ty(C&: F.getContext());
608 RetPN = PHINode::Create(Ty: RetType, NumReservedValues: 2, NameStr: "ret.tr");
609 RetPN->insertBefore(InsertPos);
610 RetKnownPN = PHINode::Create(Ty: BoolType, NumReservedValues: 2, NameStr: "ret.known.tr");
611 RetKnownPN->insertBefore(InsertPos);
612
613 RetPN->addIncoming(V: PoisonValue::get(T: RetType), BB: NewEntry);
614 RetKnownPN->addIncoming(V: ConstantInt::getFalse(Ty: BoolType), BB: NewEntry);
615 }
616
617 // The entry block was changed from HeaderBB to NewEntry.
618 // The forward DominatorTree needs to be recalculated when the EntryBB is
619 // changed. In this corner-case we recalculate the entire tree.
620 DTU.recalculate(F&: *NewEntry->getParent());
621}
622
623void TailRecursionEliminator::insertAccumulator(Instruction *AccRecInstr) {
624 assert(!AccPN && "Trying to insert multiple accumulators");
625
626 AccumulatorRecursionInstr = AccRecInstr;
627
628 // Start by inserting a new PHI node for the accumulator.
629 pred_iterator PB = pred_begin(BB: HeaderBB), PE = pred_end(BB: HeaderBB);
630 AccPN = PHINode::Create(Ty: F.getReturnType(), NumReservedValues: std::distance(first: PB, last: PE) + 1,
631 NameStr: "accumulator.tr");
632 AccPN->insertBefore(InsertPos: HeaderBB->begin());
633
634 // Loop over all of the predecessors of the tail recursion block. For the
635 // real entry into the function we seed the PHI with the identity constant for
636 // the accumulation operation. For any other existing branches to this block
637 // (due to other tail recursions eliminated) the accumulator is not modified.
638 // Because we haven't added the branch in the current block to HeaderBB yet,
639 // it will not show up as a predecessor.
640 for (pred_iterator PI = PB; PI != PE; ++PI) {
641 BasicBlock *P = *PI;
642 if (P == &F.getEntryBlock()) {
643 Constant *Identity =
644 ConstantExpr::getIdentity(I: AccRecInstr, Ty: AccRecInstr->getType());
645 AccPN->addIncoming(V: Identity, BB: P);
646 } else {
647 AccPN->addIncoming(V: AccPN, BB: P);
648 }
649 }
650
651 ++NumAccumAdded;
652}
653
654// Creates a copy of contents of ByValue operand of the specified
655// call instruction into the newly created temporarily variable.
656void TailRecursionEliminator::copyByValueOperandIntoLocalTemp(CallInst *CI,
657 int OpndIdx) {
658 Type *AggTy = CI->getParamByValType(ArgNo: OpndIdx);
659 assert(AggTy);
660 const DataLayout &DL = F.getDataLayout();
661
662 // Get alignment of byVal operand.
663 Align Alignment(CI->getParamAlign(ArgNo: OpndIdx).valueOrOne());
664
665 // Create alloca for temporarily byval operands.
666 // Put alloca into the entry block.
667 Value *NewAlloca = new AllocaInst(
668 AggTy, DL.getAllocaAddrSpace(), nullptr, Alignment,
669 CI->getArgOperand(i: OpndIdx)->getName(), F.getEntryBlock().begin());
670
671 IRBuilder<> Builder(CI);
672 Value *Size = Builder.getInt64(C: DL.getTypeAllocSize(Ty: AggTy));
673
674 // Copy data from byvalue operand into the temporarily variable.
675 Builder.CreateMemCpy(Dst: NewAlloca, /*DstAlign*/ Alignment,
676 Src: CI->getArgOperand(i: OpndIdx),
677 /*SrcAlign*/ Alignment, Size);
678 CI->setArgOperand(i: OpndIdx, v: NewAlloca);
679}
680
681// Creates a copy from temporarily variable(keeping value of ByVal argument)
682// into the corresponding function argument location.
683void TailRecursionEliminator::copyLocalTempOfByValueOperandIntoArguments(
684 CallInst *CI, int OpndIdx) {
685 Type *AggTy = CI->getParamByValType(ArgNo: OpndIdx);
686 assert(AggTy);
687 const DataLayout &DL = F.getDataLayout();
688
689 // Get alignment of byVal operand.
690 Align Alignment(CI->getParamAlign(ArgNo: OpndIdx).valueOrOne());
691
692 IRBuilder<> Builder(CI);
693 Value *Size = Builder.getInt64(C: DL.getTypeAllocSize(Ty: AggTy));
694
695 // Copy data from the temporarily variable into corresponding
696 // function argument location.
697 Builder.CreateMemCpy(Dst: F.getArg(i: OpndIdx), /*DstAlign*/ Alignment,
698 Src: CI->getArgOperand(i: OpndIdx),
699 /*SrcAlign*/ Alignment, Size);
700}
701
702bool TailRecursionEliminator::eliminateCall(CallInst *CI) {
703 ReturnInst *Ret = cast<ReturnInst>(Val: CI->getParent()->getTerminator());
704
705 // Ok, we found a potential tail call. We can currently only transform the
706 // tail call if all of the instructions between the call and the return are
707 // movable to above the call itself, leaving the call next to the return.
708 // Check that this is the case now.
709 Instruction *AccRecInstr = nullptr;
710 BasicBlock::iterator BBI(CI);
711 for (++BBI; &*BBI != Ret; ++BBI) {
712 if (canMoveAboveCall(I: &*BBI, CI, AA))
713 continue;
714
715 // If we can't move the instruction above the call, it might be because it
716 // is an associative and commutative operation that could be transformed
717 // using accumulator recursion elimination. Check to see if this is the
718 // case, and if so, remember which instruction accumulates for later.
719 if (AccPN || !canTransformAccumulatorRecursion(I: &*BBI, CI))
720 return false; // We cannot eliminate the tail recursion!
721
722 // Yes, this is accumulator recursion. Remember which instruction
723 // accumulates.
724 AccRecInstr = &*BBI;
725 }
726
727 BasicBlock *BB = Ret->getParent();
728
729 using namespace ore;
730 ORE->emit(RemarkBuilder: [&]() {
731 return OptimizationRemark(DEBUG_TYPE, "tailcall-recursion", CI)
732 << "transforming tail recursion into loop";
733 });
734
735 // OK! We can transform this tail call. If this is the first one found,
736 // create the new entry block, allowing us to branch back to the old entry.
737 if (!HeaderBB)
738 createTailRecurseLoopHeader(CI);
739
740 // Copy values of ByVal operands into local temporarily variables.
741 for (unsigned I = 0, E = CI->arg_size(); I != E; ++I) {
742 if (CI->isByValArgument(ArgNo: I))
743 copyByValueOperandIntoLocalTemp(CI, OpndIdx: I);
744 }
745
746 // Ok, now that we know we have a pseudo-entry block WITH all of the
747 // required PHI nodes, add entries into the PHI node for the actual
748 // parameters passed into the tail-recursive call.
749 for (unsigned I = 0, E = CI->arg_size(); I != E; ++I) {
750 if (CI->isByValArgument(ArgNo: I)) {
751 copyLocalTempOfByValueOperandIntoArguments(CI, OpndIdx: I);
752 // When eliminating a tail call, we modify the values of the arguments.
753 // Therefore, if the byval parameter has a readonly attribute, we have to
754 // remove it. It is safe because, from the perspective of a caller, the
755 // byval parameter is always treated as "readonly," even if the readonly
756 // attribute is removed.
757 F.removeParamAttr(ArgNo: I, Kind: Attribute::ReadOnly);
758 ArgumentPHIs[I]->addIncoming(V: F.getArg(i: I), BB);
759 } else
760 ArgumentPHIs[I]->addIncoming(V: CI->getArgOperand(i: I), BB);
761 }
762
763 if (AccRecInstr) {
764 insertAccumulator(AccRecInstr);
765
766 // Rewrite the accumulator recursion instruction so that it does not use
767 // the result of the call anymore, instead, use the PHI node we just
768 // inserted.
769 AccRecInstr->setOperand(i: AccRecInstr->getOperand(i: 0) != CI, Val: AccPN);
770
771 // Reassociating into the loop reorders the operands, so flags from the
772 // original order (nsw/nuw/exact/...) may no longer hold.
773 AccRecInstr->dropPoisonGeneratingFlags();
774 }
775
776 // Update our return value tracking
777 if (RetPN) {
778 if (Ret->getReturnValue() == CI || AccRecInstr) {
779 // Defer selecting a return value
780 RetPN->addIncoming(V: RetPN, BB);
781 RetKnownPN->addIncoming(V: RetKnownPN, BB);
782 } else {
783 // We found a return value we want to use, insert a select instruction to
784 // select it if we don't already know what our return value will be and
785 // store the result in our return value PHI node.
786 SelectInst *SI =
787 SelectInst::Create(C: RetKnownPN, S1: RetPN, S2: Ret->getReturnValue(),
788 NameStr: "current.ret.tr", InsertBefore: Ret->getIterator());
789 SI->setDebugLoc(Ret->getDebugLoc());
790 RetSelects.push_back(Elt: SI);
791
792 RetPN->addIncoming(V: SI, BB);
793 RetKnownPN->addIncoming(V: ConstantInt::getTrue(Ty: RetKnownPN->getType()), BB);
794 }
795
796 if (AccPN)
797 AccPN->addIncoming(V: AccRecInstr ? AccRecInstr : AccPN, BB);
798 }
799
800 // Now that all of the PHI nodes are in place, remove the call and
801 // ret instructions, replacing them with an unconditional branch.
802 UncondBrInst *NewBI = UncondBrInst::Create(Target: HeaderBB, InsertBefore: Ret->getIterator());
803 NewBI->setDebugLoc(CI->getDebugLoc());
804
805 Ret->eraseFromParent(); // Remove return.
806 CI->eraseFromParent(); // Remove call.
807 DTU.applyUpdates(Updates: {{DominatorTree::Insert, BB, HeaderBB}});
808 ++NumEliminated;
809 if (!DisableEntryCountRecompute && UpdateFunctionEntryCount &&
810 OrigEntryBBFreq) {
811 assert(F.getEntryCount().has_value());
812 // This pass is not expected to remove BBs, only add an entry BB. For that
813 // reason, and because the BB here isn't the new entry BB, the BFI lookup is
814 // expected to succeed.
815 assert(&F.getEntryBlock() != BB);
816 auto RelativeBBFreq =
817 static_cast<double>(BFI->getBlockFreq(BB).getFrequency()) /
818 static_cast<double>(OrigEntryBBFreq);
819 auto ToSubtract =
820 static_cast<uint64_t>(std::round(x: RelativeBBFreq * OrigEntryCount));
821 auto OldEntryCount = *F.getEntryCount();
822 if (OldEntryCount <= ToSubtract) {
823 LLVM_DEBUG(
824 errs() << "[TRE] The entrycount attributable to the recursive call, "
825 << ToSubtract
826 << ", should be strictly lower than the function entry count, "
827 << OldEntryCount << "\n");
828 } else {
829 F.setEntryCount(Count: OldEntryCount - ToSubtract);
830 }
831 }
832 return true;
833}
834
835void TailRecursionEliminator::cleanupAndFinalize() {
836 // If we eliminated any tail recursions, it's possible that we inserted some
837 // silly PHI nodes which just merge an initial value (the incoming operand)
838 // with themselves. Check to see if we did and clean up our mess if so. This
839 // occurs when a function passes an argument straight through to its tail
840 // call.
841 for (PHINode *PN : ArgumentPHIs) {
842 // If the PHI Node is a dynamic constant, replace it with the value it is.
843 if (Value *PNV = simplifyInstruction(I: PN, Q: F.getDataLayout())) {
844 PN->replaceAllUsesWith(V: PNV);
845 PN->eraseFromParent();
846 }
847 }
848
849 if (RetPN) {
850 if (RetSelects.empty()) {
851 // If we didn't insert any select instructions, then we know we didn't
852 // store a return value and we can remove the PHI nodes we inserted.
853 RetPN->dropAllReferences();
854 RetPN->eraseFromParent();
855
856 RetKnownPN->dropAllReferences();
857 RetKnownPN->eraseFromParent();
858
859 if (AccPN) {
860 // We need to insert a copy of our accumulator instruction before any
861 // return in the function, and return its result instead.
862 Instruction *AccRecInstr = AccumulatorRecursionInstr;
863 for (BasicBlock &BB : F) {
864 ReturnInst *RI = dyn_cast<ReturnInst>(Val: BB.getTerminator());
865 if (!RI)
866 continue;
867
868 Instruction *AccRecInstrNew = AccRecInstr->clone();
869 AccRecInstrNew->setName("accumulator.ret.tr");
870 AccRecInstrNew->setOperand(i: AccRecInstr->getOperand(i: 0) == AccPN,
871 Val: RI->getOperand(i_nocapture: 0));
872 AccRecInstrNew->insertBefore(InsertPos: RI->getIterator());
873 AccRecInstrNew->dropLocation();
874 RI->setOperand(i_nocapture: 0, Val_nocapture: AccRecInstrNew);
875 }
876 }
877 } else {
878 // We need to insert a select instruction before any return left in the
879 // function to select our stored return value if we have one.
880 for (BasicBlock &BB : F) {
881 ReturnInst *RI = dyn_cast<ReturnInst>(Val: BB.getTerminator());
882 if (!RI)
883 continue;
884
885 SelectInst *SI =
886 SelectInst::Create(C: RetKnownPN, S1: RetPN, S2: RI->getOperand(i_nocapture: 0),
887 NameStr: "current.ret.tr", InsertBefore: RI->getIterator());
888 SI->setDebugLoc(DebugLoc::getCompilerGenerated());
889 RetSelects.push_back(Elt: SI);
890 RI->setOperand(i_nocapture: 0, Val_nocapture: SI);
891 }
892
893 if (AccPN) {
894 // We need to insert a copy of our accumulator instruction before any
895 // of the selects we inserted, and select its result instead.
896 Instruction *AccRecInstr = AccumulatorRecursionInstr;
897 for (SelectInst *SI : RetSelects) {
898 Instruction *AccRecInstrNew = AccRecInstr->clone();
899 AccRecInstrNew->setName("accumulator.ret.tr");
900 AccRecInstrNew->setOperand(i: AccRecInstr->getOperand(i: 0) == AccPN,
901 Val: SI->getFalseValue());
902 AccRecInstrNew->insertBefore(InsertPos: SI->getIterator());
903 AccRecInstrNew->dropLocation();
904 SI->setFalseValue(AccRecInstrNew);
905 }
906 }
907 }
908 }
909}
910
911bool TailRecursionEliminator::processBlock(BasicBlock &BB) {
912 Instruction *TI = BB.getTerminator();
913
914 if (UncondBrInst *BI = dyn_cast<UncondBrInst>(Val: TI)) {
915 BasicBlock *Succ = BI->getSuccessor();
916 ReturnInst *Ret = dyn_cast<ReturnInst>(Val: Succ->getFirstNonPHIOrDbg(SkipPseudoOp: true));
917
918 if (!Ret)
919 return false;
920
921 CallInst *CI = findTRECandidate(BB: &BB);
922
923 if (!CI)
924 return false;
925
926 LLVM_DEBUG(dbgs() << "FOLDING: " << *Succ
927 << "INTO UNCOND BRANCH PRED: " << BB);
928 FoldReturnIntoUncondBranch(RI: Ret, BB: Succ, Pred: &BB, DTU: &DTU);
929 ++NumRetDuped;
930
931 // If all predecessors of Succ have been eliminated by
932 // FoldReturnIntoUncondBranch, delete it. It is important to empty it,
933 // because the ret instruction in there is still using a value which
934 // eliminateCall will attempt to remove. This block can only contain
935 // instructions that can't have uses, therefore it is safe to remove.
936 if (pred_empty(BB: Succ))
937 DTU.deleteBB(DelBB: Succ);
938
939 eliminateCall(CI);
940 return true;
941 } else if (isa<ReturnInst>(Val: TI)) {
942 CallInst *CI = findTRECandidate(BB: &BB);
943
944 if (CI)
945 return eliminateCall(CI);
946 }
947
948 return false;
949}
950
951bool TailRecursionEliminator::eliminate(
952 Function &F, const TargetTransformInfo *TTI, AliasAnalysis *AA,
953 OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU,
954 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
955 bool UpdateFunctionEntryCount) {
956 if (F.getFnAttribute(Kind: "disable-tail-calls").getValueAsBool())
957 return false;
958
959 bool MadeChange = false;
960 MadeChange |= markTails(F, ORE, PSI, BFI);
961
962 // If this function is a varargs function, we won't be able to PHI the args
963 // right, so don't even try to convert it...
964 if (F.getFunctionType()->isVarArg())
965 return MadeChange;
966
967 if (!canTRE(F))
968 return MadeChange;
969
970 // Change any tail recursive calls to loops.
971 TailRecursionEliminator TRE(F, TTI, AA, ORE, DTU, BFI, PSI,
972 UpdateFunctionEntryCount);
973
974 for (BasicBlock &BB : F)
975 MadeChange |= TRE.processBlock(BB);
976
977 TRE.cleanupAndFinalize();
978
979 return MadeChange;
980}
981
982namespace {
983struct TailCallElim : public FunctionPass {
984 static char ID; // Pass identification, replacement for typeid
985 TailCallElim() : FunctionPass(ID) {
986 initializeTailCallElimPass(*PassRegistry::getPassRegistry());
987 }
988
989 void getAnalysisUsage(AnalysisUsage &AU) const override {
990 AU.addRequired<TargetTransformInfoWrapperPass>();
991 AU.addRequired<AAResultsWrapperPass>();
992 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
993 AU.addPreserved<GlobalsAAWrapperPass>();
994 AU.addPreserved<DominatorTreeWrapperPass>();
995 AU.addPreserved<PostDominatorTreeWrapperPass>();
996 }
997
998 bool runOnFunction(Function &F) override {
999 if (skipFunction(F))
1000 return false;
1001
1002 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1003 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
1004 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
1005 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
1006 // There is no noticable performance difference here between Lazy and Eager
1007 // UpdateStrategy based on some test results. It is feasible to switch the
1008 // UpdateStrategy to Lazy if we find it profitable later.
1009 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
1010
1011 return TailRecursionEliminator::eliminate(
1012 F, TTI: &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
1013 AA: &getAnalysis<AAResultsWrapperPass>().getAAResults(),
1014 ORE: &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU,
1015 /*BFI=*/nullptr, /*PSI=*/nullptr, /*UpdateFunctionEntryCount=*/false);
1016 }
1017};
1018} // namespace
1019
1020char TailCallElim::ID = 0;
1021INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",
1022 false, false)
1023INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1024INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
1025INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination",
1026 false, false)
1027
1028// Public interface to the TailCallElimination pass
1029FunctionPass *llvm::createTailCallEliminationPass() {
1030 return new TailCallElim();
1031}
1032
1033PreservedAnalyses TailCallElimPass::run(Function &F,
1034 FunctionAnalysisManager &AM) {
1035
1036 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
1037 AliasAnalysis &AA = AM.getResult<AAManager>(IR&: F);
1038 // This must come first. It needs the 2 analyses, meaning, if it came after
1039 // the lines asking for the cached result, should they be nullptr (which, in
1040 // the case of the PDT, is likely), updates to the trees would be missed.
1041 auto *BFI = F.getEntryCount().has_value()
1042 ? &AM.getResult<BlockFrequencyAnalysis>(IR&: F)
1043 : nullptr;
1044 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
1045 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
1046 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
1047 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
1048 auto *PDT = AM.getCachedResult<PostDominatorTreeAnalysis>(IR&: F);
1049 // There is no noticable performance difference here between Lazy and Eager
1050 // UpdateStrategy based on some test results. It is feasible to switch the
1051 // UpdateStrategy to Lazy if we find it profitable later.
1052 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
1053 bool Changed = TailRecursionEliminator::eliminate(
1054 F, TTI: &TTI, AA: &AA, ORE: &ORE, DTU, BFI, PSI, UpdateFunctionEntryCount);
1055
1056 if (!Changed)
1057 return PreservedAnalyses::all();
1058 PreservedAnalyses PA;
1059 PA.preserve<DominatorTreeAnalysis>();
1060 PA.preserve<PostDominatorTreeAnalysis>();
1061 return PA;
1062}
1063