From f79d978b96168a0155772936fd75eab7527c4124 Mon Sep 17 00:00:00 2001 From: Sean Silva Date: Wed, 6 Jul 2016 23:48:41 +0000 Subject: [PATCH] [PM] Port TailCallElim git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@274708 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Transforms/Scalar/TailRecursionElimination.h | 66 ++++++++++++++++++++++ lib/Passes/PassBuilder.cpp | 1 + lib/Passes/PassRegistry.def | 1 + lib/Transforms/Scalar/TailRecursionElimination.cpp | 21 ++++++- test/Transforms/TailCallElim/accum_recursion.ll | 1 + 5 files changed, 88 insertions(+), 2 deletions(-) create mode 100644 include/llvm/Transforms/Scalar/TailRecursionElimination.h diff --git a/include/llvm/Transforms/Scalar/TailRecursionElimination.h b/include/llvm/Transforms/Scalar/TailRecursionElimination.h new file mode 100644 index 00000000000..793f9bc152e --- /dev/null +++ b/include/llvm/Transforms/Scalar/TailRecursionElimination.h @@ -0,0 +1,66 @@ +//===---- TailRecursionElimination.h ----------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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 { + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_TAILRECURSIONELIMINATION_H diff --git a/lib/Passes/PassBuilder.cpp b/lib/Passes/PassBuilder.cpp index 421b6ab53ae..58bd55b92f9 100644 --- a/lib/Passes/PassBuilder.cpp +++ b/lib/Passes/PassBuilder.cpp @@ -98,6 +98,7 @@ #include "llvm/Transforms/Scalar/SROA.h" #include "llvm/Transforms/Scalar/SimplifyCFG.h" #include "llvm/Transforms/Scalar/Sink.h" +#include "llvm/Transforms/Scalar/TailRecursionElimination.h" #include "llvm/Transforms/Utils/AddDiscriminators.h" #include "llvm/Transforms/Utils/LCSSA.h" #include "llvm/Transforms/Utils/Mem2Reg.h" diff --git a/lib/Passes/PassRegistry.def b/lib/Passes/PassRegistry.def index 71307a960bc..a970ef466d7 100644 --- a/lib/Passes/PassRegistry.def +++ b/lib/Passes/PassRegistry.def @@ -163,6 +163,7 @@ FUNCTION_PASS("simplify-cfg", SimplifyCFGPass()) FUNCTION_PASS("sink", SinkingPass()) FUNCTION_PASS("slp-vectorizer", SLPVectorizerPass()) FUNCTION_PASS("sroa", SROA()) +FUNCTION_PASS("tailcallelim", TailCallElimPass()) FUNCTION_PASS("verify", VerifierPass()) FUNCTION_PASS("verify", DominatorTreeVerifierPass()) FUNCTION_PASS("verify", MemorySSAVerifierPass()) diff --git a/lib/Transforms/Scalar/TailRecursionElimination.cpp b/lib/Transforms/Scalar/TailRecursionElimination.cpp index 4126cd67f69..d5ff9975037 100644 --- a/lib/Transforms/Scalar/TailRecursionElimination.cpp +++ b/lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -50,6 +50,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Scalar/TailRecursionElimination.h" #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" @@ -731,6 +732,9 @@ static bool processReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, } static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI) { + if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true") + return false; + bool MadeChange = false; bool AllCallsAreTailCalls = false; MadeChange |= markTails(F, AllCallsAreTailCalls); @@ -800,8 +804,7 @@ struct TailCallElim : public FunctionPass { } bool runOnFunction(Function &F) override { - if (skipFunction(F) || - F.getFnAttribute("disable-tail-calls").getValueAsString() == "true") + if (skipFunction(F)) return false; return eliminateTailRecursion( @@ -821,3 +824,17 @@ INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination", FunctionPass *llvm::createTailCallEliminationPass() { return new TailCallElim(); } + +PreservedAnalyses TailCallElimPass::run(Function &F, + FunctionAnalysisManager &AM) { + + TargetTransformInfo &TTI = AM.getResult(F); + + bool Changed = eliminateTailRecursion(F, &TTI); + + if (!Changed) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + PA.preserve(); + return PA; +} diff --git a/test/Transforms/TailCallElim/accum_recursion.ll b/test/Transforms/TailCallElim/accum_recursion.ll index c95bfe6aeed..1175d581722 100644 --- a/test/Transforms/TailCallElim/accum_recursion.ll +++ b/test/Transforms/TailCallElim/accum_recursion.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -tailcallelim -S | FileCheck %s +; RUN: opt < %s -passes=tailcallelim -S | FileCheck %s define i32 @test1_factorial(i32 %x) { entry: -- 2.11.0