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 | |
57 | namespace llvm { |
58 | |
59 | class Function; |
60 | |
61 | struct TailCallElimPass : PassInfoMixin<TailCallElimPass> { |
62 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
63 | }; |
64 | } |
65 | |
66 | #endif // LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H |
67 | |