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