LLVM 20.0.0git
TailRecursionElimination.h
Go to the documentation of this file.
1//===---- TailRecursionElimination.h ----------------------------*- C++ -*-===//
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#ifndef LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H
53#define LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H
54
55#include "llvm/IR/PassManager.h"
56
57namespace llvm {
58
59class Function;
60
61struct TailCallElimPass : PassInfoMixin<TailCallElimPass> {
63};
64}
65
66#endif // LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H
#define F(x, y, z)
Definition: MD5.cpp:55
This header defines various interfaces for pass management in LLVM.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)