66 lines
3.3 KiB
C
66 lines
3.3 KiB
C
|
//===---- TailRecursionElimination.h ----------------------------*- C++ -*-===//
|
||
|
|
//
|
||
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
||
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
||
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
||
|
|
//
|
||
|
|
//===----------------------------------------------------------------------===//
|
||
|
|
//
|
||
|
|
// This file transforms calls of the current function (self recursion) followed
|
||
|
|
// by a return instruction with a branch to the entry of the function, creating
|
||
|
|
// a loop. This pass also implements the following extensions to the basic
|
||
|
|
// algorithm:
|
||
|
|
//
|
||
|
|
// 1. Trivial instructions between the call and return do not prevent the
|
||
|
|
// transformation from taking place, though currently the analysis cannot
|
||
|
|
// support moving any really useful instructions (only dead ones).
|
||
|
|
// 2. This pass transforms functions that are prevented from being tail
|
||
|
|
// recursive by an associative and commutative expression to use an
|
||
|
|
// accumulator variable, thus compiling the typical naive factorial or
|
||
|
|
// 'fib' implementation into efficient code.
|
||
|
|
// 3. TRE is performed if the function returns void, if the return
|
||
|
|
// returns the result returned by the call, or if the function returns a
|
||
|
|
// run-time constant on all exits from the function. It is possible, though
|
||
|
|
// unlikely, that the return returns something else (like constant 0), and
|
||
|
|
// can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in
|
||
|
|
// the function return the exact same value.
|
||
|
|
// 4. If it can prove that callees do not access their caller stack frame,
|
||
|
|
// they are marked as eligible for tail call elimination (by the code
|
||
|
|
// generator).
|
||
|
|
//
|
||
|
|
// There are several improvements that could be made:
|
||
|
|
//
|
||
|
|
// 1. If the function has any alloca instructions, these instructions will be
|
||
|
|
// moved out of the entry block of the function, causing them to be
|
||
|
|
// evaluated each time through the tail recursion. Safely keeping allocas
|
||
|
|
// in the entry block requires analysis to proves that the tail-called
|
||
|
|
// function does not read or write the stack object.
|
||
|
|
// 2. Tail recursion is only performed if the call immediately precedes the
|
||
|
|
// return instruction. It's possible that there could be a jump between
|
||
|
|
// the call and the return.
|
||
|
|
// 3. There can be intervening operations between the call and the return that
|
||
|
|
// prevent the TRE from occurring. For example, there could be GEP's and
|
||
|
|
// stores to memory that will not be read or written by the call. This
|
||
|
|
// requires some substantial analysis (such as with DSA) to prove safe to
|
||
|
|
// move ahead of the call, but doing so could allow many more TREs to be
|
||
|
|
// performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark.
|
||
|
|
// 4. The algorithm we use to detect if callees access their caller stack
|
||
|
|
// frames is very primitive.
|
||
|
|
//
|
||
|
|
//===----------------------------------------------------------------------===//
|
||
|
|
|
||
|
|
#ifndef LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H
|
||
|
|
#define LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H
|
||
|
|
|
||
|
|
#include "llvm/IR/Function.h"
|
||
|
|
#include "llvm/IR/PassManager.h"
|
||
|
|
|
||
|
|
namespace llvm {
|
||
|
|
|
||
|
|
struct TailCallElimPass : PassInfoMixin<TailCallElimPass> {
|
||
|
|
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
|
||
|
|
};
|
||
|
|
}
|
||
|
|
|
||
|
|
#endif // LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H
|