1 //===---- TailRecursionElimination.h ----------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file transforms calls of the current function (self recursion) followed 11 // by a return instruction with a branch to the entry of the function, creating 12 // a loop. This pass also implements the following extensions to the basic 13 // algorithm: 14 // 15 // 1. Trivial instructions between the call and return do not prevent the 16 // transformation from taking place, though currently the analysis cannot 17 // support moving any really useful instructions (only dead ones). 18 // 2. This pass transforms functions that are prevented from being tail 19 // recursive by an associative and commutative expression to use an 20 // accumulator variable, thus compiling the typical naive factorial or 21 // 'fib' implementation into efficient code. 22 // 3. TRE is performed if the function returns void, if the return 23 // returns the result returned by the call, or if the function returns a 24 // run-time constant on all exits from the function. It is possible, though 25 // unlikely, that the return returns something else (like constant 0), and 26 // can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in 27 // the function return the exact same value. 28 // 4. If it can prove that callees do not access their caller stack frame, 29 // they are marked as eligible for tail call elimination (by the code 30 // generator). 31 // 32 // There are several improvements that could be made: 33 // 34 // 1. If the function has any alloca instructions, these instructions will be 35 // moved out of the entry block of the function, causing them to be 36 // evaluated each time through the tail recursion. Safely keeping allocas 37 // in the entry block requires analysis to proves that the tail-called 38 // function does not read or write the stack object. 39 // 2. Tail recursion is only performed if the call immediately precedes the 40 // return instruction. It's possible that there could be a jump between 41 // the call and the return. 42 // 3. There can be intervening operations between the call and the return that 43 // prevent the TRE from occurring. For example, there could be GEP's and 44 // stores to memory that will not be read or written by the call. This 45 // requires some substantial analysis (such as with DSA) to prove safe to 46 // move ahead of the call, but doing so could allow many more TREs to be 47 // performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark. 48 // 4. The algorithm we use to detect if callees access their caller stack 49 // frames is very primitive. 50 // 51 //===----------------------------------------------------------------------===// 52 53 #ifndef LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H 54 #define LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H 55 56 #include "llvm/IR/Function.h" 57 #include "llvm/IR/PassManager.h" 58 59 namespace llvm { 60 61 struct TailCallElimPass : PassInfoMixin<TailCallElimPass> { 62 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 63 }; 64 } 65 66 #endif // LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H 67