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 "ScalarOptions.h"
54#include "llvm/ADT/STLExtras.h"
55#include "llvm/ADT/SmallPtrSet.h"
56#include "llvm/ADT/Statistic.h"
57#include "llvm/Analysis/BlockFrequencyInfo.h"
58#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
59#include "llvm/Analysis/DomTreeUpdater.h"
60#include "llvm/Analysis/GlobalsModRef.h"
61#include "llvm/Analysis/InstructionSimplify.h"
62#include "llvm/Analysis/Loads.h"
63#include "llvm/Analysis/OptimizationRemarkEmitter.h"
64#include "llvm/Analysis/PostDominators.h"
65#include "llvm/Analysis/ProfileSummaryInfo.h"
66#include "llvm/Analysis/TargetTransformInfo.h"
67#include "llvm/Analysis/ValueTracking.h"
68#include "llvm/IR/CFG.h"
69#include "llvm/IR/Constants.h"
70#include "llvm/IR/DataLayout.h"
71#include "llvm/IR/DerivedTypes.h"
72#include "llvm/IR/DiagnosticInfo.h"
73#include "llvm/IR/Dominators.h"
74#include "llvm/IR/Function.h"
75#include "llvm/IR/IRBuilder.h"
76#include "llvm/IR/InstIterator.h"
77#include "llvm/IR/Instructions.h"
78#include "llvm/IR/IntrinsicInst.h"
79#include "llvm/IR/MDBuilder.h"
80#include "llvm/IR/Module.h"
81#include "llvm/IR/ProfDataUtils.h"
82#include "llvm/InitializePasses.h"
83#include "llvm/Pass.h"
84#include "llvm/Support/BlockFrequency.h"
85#include "llvm/Support/Debug.h"
86#include "llvm/Support/raw_ostream.h"
87#include "llvm/Transforms/Scalar.h"
88#include "llvm/Transforms/Utils/BasicBlockUtils.h"
89#include <cmath>
90using namespace llvm;
91
92#define DEBUG_TYPE "tailcallelim"
93
94STATISTIC(NumEliminated, "Number of tail calls removed");
95STATISTIC(NumRetDuped, "Number of return duplicated");
96STATISTIC(NumAccumAdded, "Number of accumulators introduced");
97STATISTIC(NumTREPreventedCold,
98 "Number of tail calls/recursion eliminations prevented due to cold "
99 "calling convention or attribute");
100
101static bool shouldDisableTailCallsForCold(const ScalarOptions &Opts,
102 const CallBase *CB,
103 const Function *Caller,
104 const ProfileSummaryInfo *PSI,
105 BlockFrequencyInfo *BFI) {
106 if (!Opts.disable_tail_call_elim_for_cold_calls)
107 return false;
108
109 if (CB && CB->isMustTailCall())
110 return false;
111
112 if (Caller && (Caller->hasFnAttribute(Kind: Attribute::Cold) ||
113 Caller->getCallingConv() == CallingConv::Cold))
114 return true;
115
116 if (!PSI || !PSI->hasProfileSummary())
117 return false;
118
119 // We require both the function entry and the call site/block/callee to be
120 // cold.
121 // 1. Checking that the function entry is cold ensures we don't disable tail
122 // call elimination in hot functions (with calls on cold conditional
123 // paths), which would force stack frame setup and teardown on hot paths.
124 // 2. Checking that the call site/block/callee is also cold ensures that if a
125 // function has a cold entry count but contains a hot loop, we don't
126 // disable tail call elimination for calls within that hot loop.
127 if (Caller && PSI->isFunctionEntryCold(F: Caller) && CB) {
128 if (CB->hasFnAttr(Kind: Attribute::Cold) ||
129 CB->getCallingConv() == CallingConv::Cold)
130 return true;
131 if (BFI && (PSI->isColdCallSite(CB: *CB, BFI) ||
132 PSI->isColdBlock(BB: CB->getParent(), BFI)))
133 return true;
134 }
135
136 return false;
137}
138
139/// Scan the specified function for alloca instructions.
140/// If it contains any dynamic allocas, returns false.
141static bool canTRE(Function &F) {
142 // TODO: We don't do TRE if dynamic allocas are used.
143 // Dynamic allocas allocate stack space which should be
144 // deallocated before new iteration started. That is
145 // currently not implemented.
146 return llvm::all_of(Range: instructions(F), P: [](Instruction &I) {
147 auto *AI = dyn_cast<AllocaInst>(Val: &I);
148 return !AI || AI->isStaticAlloca();
149 });
150}
151
152namespace {
153struct LocalStackValueTracker {
154 // Start at a root value and walk its use-def chain to mark calls that use the
155 // value or a derived value in LocalStackUsers, and places where it may
156 // escape in EscapePoints.
157 void walk(Value *Root) {
158 SmallVector<Use *, 32> Worklist;
159 SmallPtrSet<Use *, 32> Visited;
160
161 auto AddUsesToWorklist = [&](Value *V) {
162 for (auto &U : V->uses()) {
163 if (!Visited.insert(Ptr: &U).second)
164 continue;
165 Worklist.push_back(Elt: &U);
166 }
167 };
168
169 AddUsesToWorklist(Root);
170
171 while (!Worklist.empty()) {
172 Use *U = Worklist.pop_back_val();
173 Instruction *I = cast<Instruction>(Val: U->getUser());
174
175 switch (I->getOpcode()) {
176 case Instruction::Call:
177 case Instruction::Invoke: {
178 auto &CB = cast<CallBase>(Val&: *I);
179 // llvm.stackrestore does not capture its argument, but it is not marked
180 // nocapture because of its unusual memory semantics. Treating it as an
181 // escape would block tail calls after every VLA scope.
182 if (auto *II = dyn_cast<IntrinsicInst>(Val: I);
183 II && II->getIntrinsicID() == Intrinsic::stackrestore)
184 continue;
185 // If the alloca-derived argument is passed byval it is not an escape
186 // point, or a use of an alloca. Calling with byval copies the contents
187 // of the alloca into argument registers or stack slots, which exist
188 // beyond the lifetime of the current frame.
189 if (CB.isArgOperand(U) && CB.isByValArgument(ArgNo: CB.getArgOperandNo(U)))
190 continue;
191 bool IsNocapture =
192 CB.isDataOperand(U) && CB.doesNotCapture(OpNo: CB.getDataOperandNo(U));
193 callUsesLocalStack(CB, IsNocapture);
194 if (IsNocapture) {
195 // If the alloca-derived argument is passed in as nocapture, then it
196 // can't propagate to the call's return. That would be capturing.
197 continue;
198 }
199 break;
200 }
201 case Instruction::Load: {
202 // The result of a load is not alloca-derived (unless an alloca has
203 // otherwise escaped, but this is a local analysis).
204 continue;
205 }
206 case Instruction::Store: {
207 if (U->getOperandNo() == 0)
208 EscapePoints.insert(Ptr: I);
209 continue; // Stores have no users to analyze.
210 }
211 case Instruction::BitCast:
212 case Instruction::GetElementPtr:
213 case Instruction::PHI:
214 case Instruction::Select:
215 case Instruction::AddrSpaceCast:
216 break;
217 default:
218 EscapePoints.insert(Ptr: I);
219 break;
220 }
221
222 AddUsesToWorklist(I);
223 }
224 }
225
226 void callUsesLocalStack(CallBase &CB, bool IsNocapture) {
227 // Add it to the list of calls that use the local stack.
228 LocalStackUsers.insert(Ptr: &CB);
229
230 // If it's nocapture then it can't capture this alloca.
231 if (IsNocapture)
232 return;
233
234 // If it can write to memory, it can leak the alloca value.
235 if (!CB.onlyReadsMemory())
236 EscapePoints.insert(Ptr: &CB);
237 }
238
239 SmallPtrSet<Instruction *, 32> LocalStackUsers;
240 SmallPtrSet<Instruction *, 32> EscapePoints;
241};
242} // namespace
243
244/// Returns true if \p II returns an address in the current function's frame.
245static bool returnsCurrentFrameAddress(const IntrinsicInst *II) {
246 if (!II)
247 return false;
248 switch (II->getIntrinsicID()) {
249 case Intrinsic::frameaddress:
250 // A non-zero level refers to a caller's frame, which outlives a tail call.
251 return cast<ConstantInt>(Val: II->getArgOperand(i: 0))->isZero();
252 case Intrinsic::addressofreturnaddress:
253 case Intrinsic::eh_dwarf_cfa:
254 case Intrinsic::localaddress:
255 case Intrinsic::sponentry:
256 case Intrinsic::stackaddress:
257 case Intrinsic::stacksave:
258 case Intrinsic::swift_async_context_addr:
259 return true;
260 default:
261 return false;
262 }
263}
264
265static bool markTails(const ScalarOptions &Opts, Function &F,
266 OptimizationRemarkEmitter *ORE, ProfileSummaryInfo *PSI,
267 BlockFrequencyInfo *BFI) {
268 if (F.callsFunctionThatReturnsTwice())
269 return false;
270
271 // The local stack holds allocas and byval arguments, and frame-address
272 // intrinsics point into it.
273 LocalStackValueTracker Tracker;
274 for (Argument &Arg : F.args()) {
275 if (Arg.hasByValAttr())
276 Tracker.walk(Root: &Arg);
277 }
278 for (Instruction &I : instructions(F)) {
279 if (isa<AllocaInst>(Val: &I) ||
280 returnsCurrentFrameAddress(II: dyn_cast<IntrinsicInst>(Val: &I)))
281 Tracker.walk(Root: &I);
282 }
283
284 bool Modified = false;
285
286 // Track whether a block is reachable after an alloca has escaped. Blocks that
287 // contain the escaping instruction will be marked as being visited without an
288 // escaped alloca, since that is how the block began.
289 enum VisitType {
290 UNVISITED,
291 UNESCAPED,
292 ESCAPED
293 };
294 DenseMap<BasicBlock *, VisitType> Visited;
295
296 // We propagate the fact that an alloca has escaped from block to successor.
297 // Visit the blocks that are propagating the escapedness first. To do this, we
298 // maintain two worklists.
299 SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped;
300
301 // We may enter a block and visit it thinking that no alloca has escaped yet,
302 // then see an escape point and go back around a loop edge and come back to
303 // the same block twice. Because of this, we defer setting tail on calls when
304 // we first encounter them in a block. Every entry in this list does not
305 // statically use an alloca via use-def chain analysis, but may find an alloca
306 // through other means if the block turns out to be reachable after an escape
307 // point.
308 SmallVector<CallInst *, 32> DeferredTails;
309
310 BasicBlock *BB = &F.getEntryBlock();
311 VisitType Escaped = UNESCAPED;
312 do {
313 for (auto &I : *BB) {
314 if (Tracker.EscapePoints.count(Ptr: &I))
315 Escaped = ESCAPED;
316
317 CallInst *CI = dyn_cast<CallInst>(Val: &I);
318 // A PseudoProbeInst has the IntrInaccessibleMemOnly tag hence it is
319 // considered accessing memory and will be marked as a tail call if we
320 // don't bail out here.
321 if (!CI || CI->isTailCall() || isa<PseudoProbeInst>(Val: &I))
322 continue;
323
324 // Bail out for intrinsic stackrestore call because it can modify
325 // unescaped allocas.
326 if (auto *II = dyn_cast<IntrinsicInst>(Val: CI))
327 if (II->getIntrinsicID() == Intrinsic::stackrestore)
328 continue;
329
330 // Special-case operand bundles "clang.arc.attachedcall", "ptrauth", and
331 // "kcfi".
332 bool DisableForCold =
333 shouldDisableTailCallsForCold(Opts, CB: CI, Caller: &F, PSI, BFI);
334 bool IsNoTail = CI->isNoTailCall() || DisableForCold ||
335 CI->hasOperandBundlesOtherThan(
336 IDs: {LLVMContext::OB_clang_arc_attachedcall,
337 LLVMContext::OB_ptrauth, LLVMContext::OB_kcfi});
338 if (!CI->isNoTailCall() && DisableForCold)
339 ++NumTREPreventedCold;
340
341 if (!IsNoTail && CI->doesNotAccessMemory()) {
342 // A call to a readnone function whose arguments are all things computed
343 // outside this function can be marked tail. Even if you stored the
344 // alloca address into a global, a readnone function can't load the
345 // global anyhow.
346 //
347 // Note that this runs whether we know an alloca has escaped or not. If
348 // it has, then we can't trust Tracker.LocalStackUsers to be accurate.
349 bool SafeToTail = true;
350 for (auto &Arg : CI->args()) {
351 if (isa<Constant>(Val: Arg.getUser()))
352 continue;
353 if (Argument *A = dyn_cast<Argument>(Val: Arg.getUser()))
354 if (!A->hasByValAttr())
355 continue;
356 SafeToTail = false;
357 break;
358 }
359 if (SafeToTail) {
360 using namespace ore;
361 ORE->emit(RemarkBuilder: [&]() {
362 return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI)
363 << "marked as tail call candidate (readnone)";
364 });
365 CI->setTailCall();
366 Modified = true;
367 continue;
368 }
369 }
370
371 if (!IsNoTail && Escaped == UNESCAPED &&
372 !Tracker.LocalStackUsers.count(Ptr: CI))
373 DeferredTails.push_back(Elt: CI);
374 }
375
376 for (auto *SuccBB : successors(BB)) {
377 auto &State = Visited[SuccBB];
378 if (State < Escaped) {
379 State = Escaped;
380 if (State == ESCAPED)
381 WorklistEscaped.push_back(Elt: SuccBB);
382 else
383 WorklistUnescaped.push_back(Elt: SuccBB);
384 }
385 }
386
387 if (!WorklistEscaped.empty()) {
388 BB = WorklistEscaped.pop_back_val();
389 Escaped = ESCAPED;
390 } else {
391 BB = nullptr;
392 while (!WorklistUnescaped.empty()) {
393 auto *NextBB = WorklistUnescaped.pop_back_val();
394 if (Visited[NextBB] == UNESCAPED) {
395 BB = NextBB;
396 Escaped = UNESCAPED;
397 break;
398 }
399 }
400 }
401 } while (BB);
402
403 for (CallInst *CI : DeferredTails) {
404 if (Visited[CI->getParent()] != ESCAPED) {
405 // If the escape point was part way through the block, calls after the
406 // escape point wouldn't have been put into DeferredTails.
407 LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n");
408 CI->setTailCall();
409 Modified = true;
410 }
411 }
412
413 return Modified;
414}
415
416/// Return true if it is safe to move the specified
417/// instruction from after the call to before the call, assuming that all
418/// instructions between the call and this instruction are movable.
419///
420static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA) {
421 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I))
422 if (II->getIntrinsicID() == Intrinsic::lifetime_end)
423 return true;
424
425 // FIXME: We can move load/store/call/free instructions above the call if the
426 // call does not mod/ref the memory location being processed.
427 if (I->mayHaveSideEffects()) // This also handles volatile loads.
428 return false;
429
430 if (LoadInst *L = dyn_cast<LoadInst>(Val: I)) {
431 // Loads may always be moved above calls without side effects.
432 if (CI->mayHaveSideEffects()) {
433 // Non-volatile loads may be moved above a call with side effects if it
434 // does not write to memory and the load provably won't trap.
435 // Writes to memory only matter if they may alias the pointer
436 // being loaded from.
437 const DataLayout &DL = L->getDataLayout();
438 if (isModSet(MRI: AA->getModRefInfo(I: CI, OptLoc: MemoryLocation::get(LI: L))) ||
439 !isSafeToLoadUnconditionally(V: L->getPointerOperand(), Ty: L->getType(),
440 Alignment: L->getAlign(), SQ: SimplifyQuery(DL, L)))
441 return false;
442 }
443 }
444
445 // Otherwise, if this is a side-effect free instruction, check to make sure
446 // that it does not use the return value of the call. If it doesn't use the
447 // return value of the call, it must only use things that are defined before
448 // the call, or movable instructions between the call and the instruction
449 // itself.
450 return !is_contained(Range: I->operands(), Element: CI);
451}
452
453// Return true if I is a unary accumulator recurrence: a chain of
454// applications of a unary function `g` composed with itself,
455// `g(g(...g(Base)...))`, which is equivalent to a single application of the
456// N-times-composed function when `g` is pure. Neither associative nor
457// commutative, this differs from the ordinary accumulator recurrence handled
458// below, which requires I to be associative and commutative.
459//
460// TODO: Generalize this beyond shifts by a constant amount to arbitrary pure
461// unary functions (e.g., `f(x) = x == 0 ? Base : g(f(x - 1))` for any pure
462// unary `g`).
463static bool isUnaryAccumulatorRecurrence(Instruction *I) {
464 if (!I->isShift())
465 return false;
466
467 // A chain of shifts by a constant amount C is equivalent to a single shift
468 // by the sum of the amounts:
469 // ... (Base << C) << C) ... << C == Base << (C * Iterations)
470 // This relation applies to left shifts as well as arithmetic/logical right
471 // shifts when the shift amount is a constant.
472 return isa<ConstantInt>(Val: I->getOperand(i: 1));
473}
474
475namespace {
476class TailRecursionEliminator {
477 const ScalarOptions &Opts;
478 Function &F;
479 const TargetTransformInfo *TTI;
480 AliasAnalysis *AA;
481 OptimizationRemarkEmitter *ORE;
482 DomTreeUpdater &DTU;
483 BlockFrequencyInfo *const BFI;
484 ProfileSummaryInfo *const PSI;
485 const bool UpdateFunctionEntryCount;
486 const uint64_t OrigEntryBBFreq;
487 const uint64_t OrigEntryCount;
488
489 // The below are shared state we want to have available when eliminating any
490 // calls in the function. There values should be populated by
491 // createTailRecurseLoopHeader the first time we find a call we can eliminate.
492 BasicBlock *HeaderBB = nullptr;
493 SmallVector<PHINode *, 8> ArgumentPHIs;
494
495 // PHI node to store our return value.
496 PHINode *RetPN = nullptr;
497
498 // i1 PHI node to track if we have a valid return value stored in RetPN.
499 PHINode *RetKnownPN = nullptr;
500
501 // Vector of select instructions we insereted. These selects use RetKnownPN
502 // to either propagate RetPN or select a new return value.
503 SmallVector<SelectInst *, 8> RetSelects;
504
505 // Keep track of the sum of frequencies of blocks that have calls eliminated
506 // so we can synthesize branch weights later that require information on
507 // recursion frequency.
508 uint64_t EliminateBlocksFrequencySum = 0;
509
510 // The below are shared state needed when performing accumulator recursion.
511 // There values should be populated by insertAccumulator the first time we
512 // find an elimination that requires an accumulator.
513
514 // PHI node to store our current accumulated value.
515 PHINode *AccPN = nullptr;
516
517 // The instruction doing the accumulating.
518 Instruction *AccumulatorRecursionInstr = nullptr;
519
520 Constant *AccumulatorInitialValue = nullptr;
521
522 TailRecursionEliminator(const ScalarOptions &Opts, Function &F,
523 const TargetTransformInfo *TTI, AliasAnalysis *AA,
524 OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU,
525 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
526 bool UpdateFunctionEntryCount)
527 : Opts(Opts), F(F), TTI(TTI), AA(AA), ORE(ORE), DTU(DTU), BFI(BFI),
528 PSI(PSI), UpdateFunctionEntryCount(UpdateFunctionEntryCount),
529 OrigEntryBBFreq(
530 BFI ? BFI->getBlockFreq(BB: &F.getEntryBlock()).getFrequency() : 0U),
531 OrigEntryCount(F.getEntryCount() ? *F.getEntryCount() : 0) {
532 if (BFI) {
533 // The assert is meant as API documentation for the caller.
534 assert(OrigEntryBBFreq != 0 &&
535 "If a BFI was provided, the function should have an entry "
536 "basic block with a non-zero frequency.");
537 }
538 }
539
540 Constant *findBaseCaseRetConstant(Instruction *AccRecInstr);
541
542 Constant *canTransformAccumulatorRecursion(Instruction *I, CallInst *CI);
543
544 CallInst *findTRECandidate(BasicBlock *BB);
545
546 void createTailRecurseLoopHeader(CallInst *CI);
547
548 void insertAccumulator(Instruction *AccRecInstr);
549
550 bool eliminateCall(CallInst *CI);
551
552 void cleanupAndFinalize();
553
554 bool processBlock(BasicBlock &BB);
555
556 void copyByValueOperandIntoLocalTemp(CallInst *CI, int OpndIdx);
557
558 void copyLocalTempOfByValueOperandIntoArguments(CallInst *CI, int OpndIdx);
559
560public:
561 static bool eliminate(Function &F, const TargetTransformInfo *TTI,
562 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE,
563 DomTreeUpdater &DTU, BlockFrequencyInfo *BFI,
564 ProfileSummaryInfo *PSI, bool UpdateFunctionEntryCount);
565};
566} // namespace
567
568// Find the base-case return value for the function, given the accumulator
569// recursion instruction AccRecInstr that is about to be eliminated. Every
570// return other than the one fed by AccRecInstr survives the transformation and
571// will be rewritten to return the accumulator, so all of them have to yield the
572// same base-case constant. Return that constant, or nullptr on failure.
573//
574// RetSelects are the selects already inserted for call sites eliminated via
575// the "found return value" mechanism instead of the accumulator one. Their
576// original `ret` is gone, so they'd otherwise be invisible to the scan below,
577// but they still have to agree on the same base-case constant.
578//
579// FIXME: There is a room for improvement here in the future, e.g., consider
580// non-constant values and multiple base cases -- e.g., we want to be able to
581// handle code like:
582// ```
583// int f(int x) {
584// if (x == 1) return 1;
585// if (x == 10) return 10;
586// return f(x-1) << 1;
587// }
588// ```
589Constant *
590TailRecursionEliminator::findBaseCaseRetConstant(Instruction *AccRecInstr) {
591 Constant *BaseCaseVal = nullptr;
592
593 // Records C as the base-case constant the first time it's seen, and
594 // otherwise checks that it agrees with the one already on record.
595 auto SetOrMatchBaseCase = [&](Constant *C) {
596 if (!BaseCaseVal)
597 BaseCaseVal = C;
598 return BaseCaseVal == C;
599 };
600
601 for (BasicBlock &BB : F) {
602 auto *RI = dyn_cast<ReturnInst>(Val: BB.getTerminator());
603 if (!RI || !RI->getReturnValue())
604 continue;
605
606 Value *RV = RI->getReturnValue();
607
608 // This is the recursive case being turned into a loop: the return goes
609 // away along with AccRecInstr.
610 if (RV == AccRecInstr)
611 continue;
612
613 // Anything else has to be the base case. In particular a return still
614 // computing from a recursive call (e.g. a second recursion site that is
615 // not eliminated) must be rejected: returning the accumulator in its place
616 // would drop that computation.
617 auto *C = dyn_cast<Constant>(Val: RV);
618 if (!C || !SetOrMatchBaseCase(C))
619 return nullptr;
620 }
621
622 for (SelectInst *SI : RetSelects) {
623 auto *C = dyn_cast<Constant>(Val: SI->getFalseValue());
624 if (!C || !SetOrMatchBaseCase(C))
625 return nullptr;
626 }
627
628 return BaseCaseVal;
629}
630
631// This function checks whether the instruction I can be used
632// to perform accumulator recursion elimination for the
633// call instruction CI.
634Constant *
635TailRecursionEliminator::canTransformAccumulatorRecursion(Instruction *I,
636 CallInst *CI) {
637 bool IsUnaryAccumulatorRecurrence = isUnaryAccumulatorRecurrence(I);
638 if ((!I->isAssociative() || !I->isCommutative()) &&
639 !IsUnaryAccumulatorRecurrence)
640 return nullptr;
641
642 assert(I->getNumOperands() >= 2 &&
643 "Associative/commutative operations should have at least 2 args!");
644
645 Constant *AccInitVal = nullptr;
646 if (IsUnaryAccumulatorRecurrence) {
647 // For unary accumulator recurrences, we require that the recursive call
648 // is always on the first operand.
649 if (I->getOperand(i: 0) != CI)
650 return nullptr;
651
652 // findTRECandidate guarantees CI is a recursive call to its own
653 // function, so scan the enclosing function for the base-case return.
654 AccInitVal = findBaseCaseRetConstant(/*AccRecInstr=*/I);
655 if (!AccInitVal)
656 return nullptr;
657 } else {
658 AccInitVal = ConstantExpr::getIdentity(I, Ty: I->getType());
659 if (!AccInitVal)
660 return nullptr;
661
662 // Exactly one operand should be the result of the call instruction.
663 if ((I->getOperand(i: 0) == CI && I->getOperand(i: 1) == CI) ||
664 (I->getOperand(i: 0) != CI && I->getOperand(i: 1) != CI))
665 return nullptr;
666 }
667
668 // The only user of this instruction we allow is a single return instruction.
669 if (!I->hasOneUse() || !isa<ReturnInst>(Val: I->user_back()))
670 return nullptr;
671
672 return AccInitVal;
673}
674
675CallInst *TailRecursionEliminator::findTRECandidate(BasicBlock *BB) {
676 Instruction *TI = BB->getTerminator();
677
678 if (&BB->front() == TI) // Make sure there is something before the terminator.
679 return nullptr;
680
681 // Scan backwards from the return, checking to see if there is a tail call in
682 // this block. If so, set CI to it.
683 CallInst *CI = nullptr;
684 BasicBlock::iterator BBI(TI);
685 while (true) {
686 CI = dyn_cast<CallInst>(Val&: BBI);
687 if (CI && CI->getCalledFunction() == &F)
688 break;
689
690 if (BBI == BB->begin())
691 return nullptr; // Didn't find a potential tail call.
692 --BBI;
693 }
694
695 assert((!CI->isTailCall() || !CI->isNoTailCall()) &&
696 "Incompatible call site attributes(Tail,NoTail)");
697 if (!CI->isTailCall() ||
698 shouldDisableTailCallsForCold(Opts, CB: CI, Caller: &F, PSI, BFI))
699 return nullptr;
700
701 // As a special case, detect code like this:
702 // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
703 // and disable this xform in this case, because the code generator will
704 // lower the call to fabs into inline code.
705 if (BB == &F.getEntryBlock() && &BB->front() == CI &&
706 &*std::next(x: BB->begin()) == TI && CI->getCalledFunction() &&
707 !TTI->isLoweredToCall(F: CI->getCalledFunction())) {
708 // A single-block function with just a call and a return. Check that
709 // the arguments match.
710 auto I = CI->arg_begin(), E = CI->arg_end();
711 Function::arg_iterator FI = F.arg_begin(), FE = F.arg_end();
712 for (; I != E && FI != FE; ++I, ++FI)
713 if (*I != &*FI) break;
714 if (I == E && FI == FE)
715 return nullptr;
716 }
717
718 return CI;
719}
720
721void TailRecursionEliminator::createTailRecurseLoopHeader(CallInst *CI) {
722 HeaderBB = &F.getEntryBlock();
723 BasicBlock *NewEntry = BasicBlock::Create(Context&: F.getContext(), Name: "", Parent: &F, InsertBefore: HeaderBB);
724 NewEntry->takeName(V: HeaderBB);
725 HeaderBB->setName("tailrecurse");
726 auto *BI = UncondBrInst::Create(Target: HeaderBB, InsertBefore: NewEntry);
727 BI->setDebugLoc(DebugLoc::getCompilerGenerated());
728 // If the new branch preserves the debug location of CI, it could result in
729 // misleading stepping, if CI is located in a conditional branch.
730 // So, here we don't give any debug location to the new branch.
731
732 // Move all fixed sized allocas from HeaderBB to NewEntry.
733 for (BasicBlock::iterator OEBI = HeaderBB->begin(), E = HeaderBB->end(),
734 NEBI = NewEntry->begin();
735 OEBI != E;)
736 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: OEBI++))
737 if (isa<ConstantInt>(Val: AI->getArraySize()))
738 AI->moveBefore(InsertPos: NEBI);
739
740 // Now that we have created a new block, which jumps to the entry
741 // block, insert a PHI node for each argument of the function.
742 // For now, we initialize each PHI to only have the real arguments
743 // which are passed in.
744 BasicBlock::iterator InsertPos = HeaderBB->begin();
745 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
746 PHINode *PN = PHINode::Create(Ty: I->getType(), NumReservedValues: 2, NameStr: I->getName() + ".tr");
747 PN->insertBefore(InsertPos);
748 I->replaceAllUsesWith(V: PN); // Everyone use the PHI node now!
749 PN->addIncoming(V: &*I, BB: NewEntry);
750 ArgumentPHIs.push_back(Elt: PN);
751 }
752
753 // If the function doen't return void, create the RetPN and RetKnownPN PHI
754 // nodes to track our return value. We initialize RetPN with poison and
755 // RetKnownPN with false since we can't know our return value at function
756 // entry.
757 Type *RetType = F.getReturnType();
758 if (!RetType->isVoidTy()) {
759 Type *BoolType = Type::getInt1Ty(C&: F.getContext());
760 RetPN = PHINode::Create(Ty: RetType, NumReservedValues: 2, NameStr: "ret.tr");
761 RetPN->insertBefore(InsertPos);
762 RetKnownPN = PHINode::Create(Ty: BoolType, NumReservedValues: 2, NameStr: "ret.known.tr");
763 RetKnownPN->insertBefore(InsertPos);
764
765 RetPN->addIncoming(V: PoisonValue::get(T: RetType), BB: NewEntry);
766 RetKnownPN->addIncoming(V: ConstantInt::getFalse(Ty: BoolType), BB: NewEntry);
767 }
768
769 // The entry block was changed from HeaderBB to NewEntry.
770 // The forward DominatorTree needs to be recalculated when the EntryBB is
771 // changed. In this corner-case we recalculate the entire tree.
772 DTU.recalculate(F&: *NewEntry->getParent());
773}
774
775void TailRecursionEliminator::insertAccumulator(Instruction *AccRecInstr) {
776 assert(!AccPN && "Trying to insert multiple accumulators");
777
778 AccumulatorRecursionInstr = AccRecInstr;
779
780 // Start by inserting a new PHI node for the accumulator.
781 pred_iterator PB = pred_begin(BB: HeaderBB), PE = pred_end(BB: HeaderBB);
782 AccPN = PHINode::Create(Ty: F.getReturnType(), NumReservedValues: std::distance(first: PB, last: PE) + 1,
783 NameStr: "accumulator.tr");
784 AccPN->insertBefore(InsertPos: HeaderBB->begin());
785
786 // Loop over all of the predecessors of the tail recursion block. For the
787 // real entry into the function we seed the PHI with the identity constant for
788 // the accumulation operation. For any other existing branches to this block
789 // (due to other tail recursions eliminated) the accumulator is not modified.
790 // Because we haven't added the branch in the current block to HeaderBB yet,
791 // it will not show up as a predecessor.
792 for (pred_iterator PI = PB; PI != PE; ++PI) {
793 BasicBlock *P = *PI;
794 if (P == &F.getEntryBlock()) {
795 AccPN->addIncoming(V: AccumulatorInitialValue, BB: P);
796 } else {
797 AccPN->addIncoming(V: AccPN, BB: P);
798 }
799 }
800
801 ++NumAccumAdded;
802}
803
804// Creates a copy of contents of ByValue operand of the specified
805// call instruction into the newly created temporarily variable.
806void TailRecursionEliminator::copyByValueOperandIntoLocalTemp(CallInst *CI,
807 int OpndIdx) {
808 Type *AggTy = CI->getParamByValType(ArgNo: OpndIdx);
809 assert(AggTy);
810 const DataLayout &DL = F.getDataLayout();
811
812 // Get alignment of byVal operand.
813 Align Alignment(CI->getParamAlign(ArgNo: OpndIdx).valueOrOne());
814
815 // Create alloca for temporarily byval operands.
816 // Put alloca into the entry block.
817 Value *NewAlloca = new AllocaInst(
818 AggTy, DL.getAllocaAddrSpace(), nullptr, Alignment,
819 CI->getArgOperand(i: OpndIdx)->getName(), F.getEntryBlock().begin());
820
821 IRBuilder<> Builder(CI);
822 Value *Size = Builder.getInt64(C: DL.getTypeAllocSize(Ty: AggTy));
823
824 // Copy data from byvalue operand into the temporarily variable.
825 Builder.CreateMemCpy(Dst: NewAlloca, /*DstAlign*/ Alignment,
826 Src: CI->getArgOperand(i: OpndIdx),
827 /*SrcAlign*/ Alignment, Size);
828 CI->setArgOperand(i: OpndIdx, v: NewAlloca);
829}
830
831// Creates a copy from temporarily variable(keeping value of ByVal argument)
832// into the corresponding function argument location.
833void TailRecursionEliminator::copyLocalTempOfByValueOperandIntoArguments(
834 CallInst *CI, int OpndIdx) {
835 Type *AggTy = CI->getParamByValType(ArgNo: OpndIdx);
836 assert(AggTy);
837 const DataLayout &DL = F.getDataLayout();
838
839 // Get alignment of byVal operand.
840 Align Alignment(CI->getParamAlign(ArgNo: OpndIdx).valueOrOne());
841
842 IRBuilder<> Builder(CI);
843 Value *Size = Builder.getInt64(C: DL.getTypeAllocSize(Ty: AggTy));
844
845 // Copy data from the temporarily variable into corresponding
846 // function argument location.
847 Builder.CreateMemCpy(Dst: F.getArg(i: OpndIdx), /*DstAlign*/ Alignment,
848 Src: CI->getArgOperand(i: OpndIdx),
849 /*SrcAlign*/ Alignment, Size);
850}
851
852bool TailRecursionEliminator::eliminateCall(CallInst *CI) {
853 ReturnInst *Ret = cast<ReturnInst>(Val: CI->getParent()->getTerminator());
854
855 // Ok, we found a potential tail call. We can currently only transform the
856 // tail call if all of the instructions between the call and the return are
857 // movable to above the call itself, leaving the call next to the return.
858 // Check that this is the case now.
859 Instruction *AccRecInstr = nullptr;
860 BasicBlock::iterator BBI(CI);
861 for (++BBI; &*BBI != Ret; ++BBI) {
862 if (canMoveAboveCall(I: &*BBI, CI, AA))
863 continue;
864
865 // If we can't move the instruction above the call, it might be because it
866 // is an (associative and commutative) or unary accumulator recurrence
867 // arithmetic operation that could be transformed using accumulator
868 // recursion elimination. Check to see if this is the case, and if so,
869 // remember which instruction accumulates for later.
870 Constant *AccInitVal = canTransformAccumulatorRecursion(I: &*BBI, CI);
871
872 if (AccPN || !AccInitVal)
873 return false; // We cannot eliminate the tail recursion!
874
875 // Yes, this is accumulator recursion. Remember which instruction
876 // accumulates.
877 AccRecInstr = &*BBI;
878
879 // Keep track of the base case (i.e., initial value) of the accumulator
880 // return value if any.
881 AccumulatorInitialValue = AccInitVal;
882 }
883
884 BasicBlock *BB = Ret->getParent();
885
886 if (BFI)
887 EliminateBlocksFrequencySum += BFI->getBlockFreq(BB).getFrequency();
888
889 using namespace ore;
890 ORE->emit(RemarkBuilder: [&]() {
891 return OptimizationRemark(DEBUG_TYPE, "tailcall-recursion", CI)
892 << "transforming tail recursion into loop";
893 });
894
895 // OK! We can transform this tail call. If this is the first one found,
896 // create the new entry block, allowing us to branch back to the old entry.
897 if (!HeaderBB)
898 createTailRecurseLoopHeader(CI);
899
900 // Copy values of ByVal operands into local temporarily variables.
901 for (unsigned I = 0, E = CI->arg_size(); I != E; ++I) {
902 if (CI->isByValArgument(ArgNo: I))
903 copyByValueOperandIntoLocalTemp(CI, OpndIdx: I);
904 }
905
906 // Ok, now that we know we have a pseudo-entry block WITH all of the
907 // required PHI nodes, add entries into the PHI node for the actual
908 // parameters passed into the tail-recursive call.
909 for (unsigned I = 0, E = CI->arg_size(); I != E; ++I) {
910 if (CI->isByValArgument(ArgNo: I)) {
911 copyLocalTempOfByValueOperandIntoArguments(CI, OpndIdx: I);
912 // When eliminating a tail call, we modify the values of the arguments.
913 // Therefore, if the byval parameter has a readonly attribute, we have to
914 // remove it. It is safe because, from the perspective of a caller, the
915 // byval parameter is always treated as "readonly," even if the readonly
916 // attribute is removed.
917 F.removeParamAttr(ArgNo: I, Kind: Attribute::ReadOnly);
918 ArgumentPHIs[I]->addIncoming(V: F.getArg(i: I), BB);
919 } else
920 ArgumentPHIs[I]->addIncoming(V: CI->getArgOperand(i: I), BB);
921 }
922
923 if (AccRecInstr) {
924 insertAccumulator(AccRecInstr);
925
926 // Rewrite the accumulator recursion instruction so that it does not use
927 // the result of the call anymore, instead, use the PHI node we just
928 // inserted.
929 AccRecInstr->setOperand(i: AccRecInstr->getOperand(i: 0) != CI, Val: AccPN);
930
931 // Reassociating into the loop reorders the operands, so flags from the
932 // original order (nsw/nuw/exact/...) may no longer hold.
933 AccRecInstr->dropPoisonGeneratingFlags();
934 }
935
936 // Update our return value tracking
937 if (RetPN) {
938 if (Ret->getReturnValue() == CI || AccRecInstr) {
939 // Defer selecting a return value
940 RetPN->addIncoming(V: RetPN, BB);
941 RetKnownPN->addIncoming(V: RetKnownPN, BB);
942 } else {
943 // We found a return value we want to use, insert a select instruction to
944 // select it if we don't already know what our return value will be and
945 // store the result in our return value PHI node.
946 SelectInst *SI =
947 SelectInst::Create(C: RetKnownPN, S1: RetPN, S2: Ret->getReturnValue(),
948 NameStr: "current.ret.tr", InsertBefore: Ret->getIterator());
949 SI->setDebugLoc(Ret->getDebugLoc());
950 RetSelects.push_back(Elt: SI);
951
952 RetPN->addIncoming(V: SI, BB);
953 RetKnownPN->addIncoming(V: ConstantInt::getTrue(Ty: RetKnownPN->getType()), BB);
954 }
955
956 if (AccPN)
957 AccPN->addIncoming(V: AccRecInstr ? AccRecInstr : AccPN, BB);
958 }
959
960 // Now that all of the PHI nodes are in place, remove the call and
961 // ret instructions, replacing them with an unconditional branch.
962 UncondBrInst *NewBI = UncondBrInst::Create(Target: HeaderBB, InsertBefore: Ret->getIterator());
963 NewBI->setDebugLoc(CI->getDebugLoc());
964
965 Ret->eraseFromParent(); // Remove return.
966 CI->eraseFromParent(); // Remove call.
967 DTU.applyUpdates(Updates: {{DominatorTree::Insert, BB, HeaderBB}});
968 ++NumEliminated;
969 if (!Opts.tre_disable_entrycount_recompute && UpdateFunctionEntryCount &&
970 OrigEntryBBFreq) {
971 assert(F.getEntryCount().has_value());
972 // This pass is not expected to remove BBs, only add an entry BB. For that
973 // reason, and because the BB here isn't the new entry BB, the BFI lookup is
974 // expected to succeed.
975 assert(&F.getEntryBlock() != BB);
976 auto RelativeBBFreq =
977 static_cast<double>(BFI->getBlockFreq(BB).getFrequency()) /
978 static_cast<double>(OrigEntryBBFreq);
979 auto ToSubtract =
980 static_cast<uint64_t>(std::round(x: RelativeBBFreq * OrigEntryCount));
981 auto OldEntryCount = *F.getEntryCount();
982 if (OldEntryCount <= ToSubtract) {
983 LLVM_DEBUG(
984 errs() << "[TRE] The entrycount attributable to the recursive call, "
985 << ToSubtract
986 << ", should be strictly lower than the function entry count, "
987 << OldEntryCount << "\n");
988 } else {
989 F.setEntryCount(Count: OldEntryCount - ToSubtract);
990 }
991 }
992 return true;
993}
994
995void TailRecursionEliminator::cleanupAndFinalize() {
996 // If we eliminated any tail recursions, it's possible that we inserted some
997 // silly PHI nodes which just merge an initial value (the incoming operand)
998 // with themselves. Check to see if we did and clean up our mess if so. This
999 // occurs when a function passes an argument straight through to its tail
1000 // call.
1001 for (PHINode *PN : ArgumentPHIs) {
1002 // If the PHI Node is a dynamic constant, replace it with the value it is.
1003 if (Value *PNV = simplifyInstruction(I: PN, Q: F.getDataLayout())) {
1004 PN->replaceAllUsesWith(V: PNV);
1005 PN->eraseFromParent();
1006 }
1007 }
1008
1009 if (RetPN) {
1010 Instruction *AccRecInstr = AccumulatorRecursionInstr;
1011 auto MaterializeAccumulator = [&](Value *OtherVal,
1012 BasicBlock::iterator InsertPt) {
1013 Instruction *New = AccRecInstr->clone();
1014 New->setName("accumulator.ret.tr");
1015 New->setOperand(i: AccRecInstr->getOperand(i: 0) == AccPN, Val: OtherVal);
1016 New->insertBefore(InsertPos: InsertPt);
1017 New->dropLocation();
1018 return New;
1019 };
1020
1021 if (RetSelects.empty()) {
1022 // If we didn't insert any select instructions, then we know we didn't
1023 // store a return value and we can remove the PHI nodes we inserted.
1024 RetPN->dropAllReferences();
1025 RetPN->eraseFromParent();
1026
1027 RetKnownPN->dropAllReferences();
1028 RetKnownPN->eraseFromParent();
1029
1030 if (AccPN) {
1031 // We need to insert a copy of our accumulator instruction before any
1032 // return in the function, and return its result instead.
1033 for (BasicBlock &BB : F) {
1034 ReturnInst *RI = dyn_cast<ReturnInst>(Val: BB.getTerminator());
1035 if (!RI)
1036 continue;
1037
1038 if (isUnaryAccumulatorRecurrence(I: AccRecInstr)) {
1039 // Base-case initialization: the accumulator PHI already holds the
1040 // final result, so return it directly.
1041 RI->setOperand(i_nocapture: 0, Val_nocapture: AccPN);
1042 } else {
1043 // Since the accumulator starts with the identity value, before the
1044 // return we need to apply the accumulation instruction one more
1045 // time to combine the last value with the result of the recursive
1046 // call.
1047 RI->setOperand(i_nocapture: 0, Val_nocapture: MaterializeAccumulator(RI->getOperand(i_nocapture: 0),
1048 RI->getIterator()));
1049 }
1050 }
1051 }
1052 } else {
1053 // We need to insert a select instruction before any return left in the
1054 // function to select our stored return value if we have one.
1055 for (BasicBlock &BB : F) {
1056 ReturnInst *RI = dyn_cast<ReturnInst>(Val: BB.getTerminator());
1057 if (!RI)
1058 continue;
1059
1060 SelectInst *SI =
1061 SelectInst::Create(C: RetKnownPN, S1: RetPN, S2: RI->getOperand(i_nocapture: 0),
1062 NameStr: "current.ret.tr", InsertBefore: RI->getIterator());
1063 SI->setDebugLoc(DebugLoc::getCompilerGenerated());
1064 RetSelects.push_back(Elt: SI);
1065 RI->setOperand(i_nocapture: 0, Val_nocapture: SI);
1066 }
1067
1068 if (AccPN) {
1069 // We need to insert a copy of our accumulator instruction before any
1070 // of the selects we inserted, and select its result instead.
1071 for (SelectInst *SI : RetSelects) {
1072 if (isUnaryAccumulatorRecurrence(I: AccRecInstr)) {
1073 SI->setFalseValue(AccPN);
1074 } else {
1075 SI->setFalseValue(
1076 MaterializeAccumulator(SI->getFalseValue(), SI->getIterator()));
1077 }
1078 }
1079 }
1080 }
1081
1082 if (BFI) {
1083 uint64_t BaseCaseBlocksFrequencySum = 0;
1084 for (BasicBlock &BB : F)
1085 if (isa<ReturnInst>(Val: BB.getTerminator()))
1086 BaseCaseBlocksFrequencySum += BFI->getBlockFreq(BB: &BB).getFrequency();
1087
1088 if (EliminateBlocksFrequencySum + BaseCaseBlocksFrequencySum == 0)
1089 return;
1090 SmallVector<uint32_t> Testing = fitWeights(Weights: {EliminateBlocksFrequencySum, BaseCaseBlocksFrequencySum});
1091 MDBuilder MDB(F.getContext());
1092 MDNode *BranchWeights = MDB.createBranchWeights(
1093 Weights: {Testing[0], Testing[1]},
1094 IsExpected: false);
1095 for (SelectInst *SI : RetSelects)
1096 SI->setMetadata(KindID: LLVMContext::MD_prof, Node: BranchWeights);
1097 }
1098 }
1099}
1100
1101bool TailRecursionEliminator::processBlock(BasicBlock &BB) {
1102 Instruction *TI = BB.getTerminator();
1103
1104 if (UncondBrInst *BI = dyn_cast<UncondBrInst>(Val: TI)) {
1105 BasicBlock *Succ = BI->getSuccessor();
1106 ReturnInst *Ret = dyn_cast<ReturnInst>(Val: Succ->getFirstNonPHIOrDbg(SkipPseudoOp: true));
1107
1108 if (!Ret)
1109 return false;
1110
1111 CallInst *CI = findTRECandidate(BB: &BB);
1112
1113 if (!CI)
1114 return false;
1115
1116 LLVM_DEBUG(dbgs() << "FOLDING: " << *Succ
1117 << "INTO UNCOND BRANCH PRED: " << BB);
1118 FoldReturnIntoUncondBranch(RI: Ret, BB: Succ, Pred: &BB, DTU: &DTU);
1119 ++NumRetDuped;
1120
1121 // If all predecessors of Succ have been eliminated by
1122 // FoldReturnIntoUncondBranch, delete it. It is important to empty it,
1123 // because the ret instruction in there is still using a value which
1124 // eliminateCall will attempt to remove. This block can only contain
1125 // instructions that can't have uses, therefore it is safe to remove.
1126 if (pred_empty(BB: Succ))
1127 DTU.deleteBB(DelBB: Succ);
1128
1129 eliminateCall(CI);
1130 return true;
1131 }
1132
1133 if (isa<ReturnInst>(Val: TI)) {
1134 CallInst *CI = findTRECandidate(BB: &BB);
1135
1136 if (CI)
1137 return eliminateCall(CI);
1138 }
1139
1140 return false;
1141}
1142
1143bool TailRecursionEliminator::eliminate(
1144 Function &F, const TargetTransformInfo *TTI, AliasAnalysis *AA,
1145 OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU,
1146 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
1147 bool UpdateFunctionEntryCount) {
1148 if (F.getFnAttribute(Kind: "disable-tail-calls").getValueAsBool())
1149 return false;
1150
1151 const ScalarOptions &Opts = ScalarOptions::Global;
1152 bool MadeChange = false;
1153 MadeChange |= markTails(Opts, F, ORE, PSI, BFI);
1154
1155 // If this function is a varargs function, we won't be able to PHI the args
1156 // right, so don't even try to convert it...
1157 if (F.getFunctionType()->isVarArg())
1158 return MadeChange;
1159
1160 if (!canTRE(F))
1161 return MadeChange;
1162
1163 // Change any tail recursive calls to loops.
1164 TailRecursionEliminator TRE(Opts, F, TTI, AA, ORE, DTU, BFI, PSI,
1165 UpdateFunctionEntryCount);
1166
1167 for (BasicBlock &BB : F)
1168 MadeChange |= TRE.processBlock(BB);
1169
1170 TRE.cleanupAndFinalize();
1171
1172 return MadeChange;
1173}
1174
1175namespace {
1176struct TailCallElim : public FunctionPass {
1177 static char ID; // Pass identification, replacement for typeid
1178 TailCallElim() : FunctionPass(ID) {
1179 initializeTailCallElimPass(*PassRegistry::getPassRegistry());
1180 }
1181
1182 void getAnalysisUsage(AnalysisUsage &AU) const override {
1183 AU.addRequired<TargetTransformInfoWrapperPass>();
1184 AU.addRequired<AAResultsWrapperPass>();
1185 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
1186 AU.addPreserved<GlobalsAAWrapperPass>();
1187 AU.addPreserved<DominatorTreeWrapperPass>();
1188 AU.addPreserved<PostDominatorTreeWrapperPass>();
1189 }
1190
1191 bool runOnFunction(Function &F) override {
1192 if (skipFunction(F))
1193 return false;
1194
1195 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1196 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
1197 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
1198 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
1199 // There is no noticable performance difference here between Lazy and Eager
1200 // UpdateStrategy based on some test results. It is feasible to switch the
1201 // UpdateStrategy to Lazy if we find it profitable later.
1202 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
1203
1204 return TailRecursionEliminator::eliminate(
1205 F, TTI: &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
1206 AA: &getAnalysis<AAResultsWrapperPass>().getAAResults(),
1207 ORE: &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU,
1208 /*BFI=*/nullptr, /*PSI=*/nullptr, /*UpdateFunctionEntryCount=*/false);
1209 }
1210};
1211} // namespace
1212
1213char TailCallElim::ID = 0;
1214INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",
1215 false, false)
1216INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1217INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
1218INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination",
1219 false, false)
1220
1221// Public interface to the TailCallElimination pass
1222FunctionPass *llvm::createTailCallEliminationPass() {
1223 return new TailCallElim();
1224}
1225
1226PreservedAnalyses TailCallElimPass::run(Function &F,
1227 FunctionAnalysisManager &AM) {
1228
1229 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
1230 AliasAnalysis &AA = AM.getResult<AAManager>(IR&: F);
1231 // This must come first. It needs the 2 analyses, meaning, if it came after
1232 // the lines asking for the cached result, should they be nullptr (which, in
1233 // the case of the PDT, is likely), updates to the trees would be missed.
1234 auto *BFI = F.getEntryCount().has_value()
1235 ? &AM.getResult<BlockFrequencyAnalysis>(IR&: F)
1236 : nullptr;
1237 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
1238 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
1239 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
1240 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
1241 auto *PDT = AM.getCachedResult<PostDominatorTreeAnalysis>(IR&: F);
1242 // There is no noticable performance difference here between Lazy and Eager
1243 // UpdateStrategy based on some test results. It is feasible to switch the
1244 // UpdateStrategy to Lazy if we find it profitable later.
1245 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
1246 bool Changed = TailRecursionEliminator::eliminate(
1247 F, TTI: &TTI, AA: &AA, ORE: &ORE, DTU, BFI, PSI, UpdateFunctionEntryCount);
1248
1249 if (!Changed)
1250 return PreservedAnalyses::all();
1251 PreservedAnalyses PA;
1252 PA.preserve<DominatorTreeAnalysis>();
1253 PA.preserve<PostDominatorTreeAnalysis>();
1254 return PA;
1255}
1256