include/llvm/Transforms/Scalar/TailRecursionElimination.h

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