12240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner//===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 92240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 107152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// This file transforms calls of the current function (self recursion) followed 117152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// by a return instruction with a branch to the entry of the function, creating 127152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// a loop. This pass also implements the following extensions to the basic 137152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// algorithm: 142240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 157152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// 1. Trivial instructions between the call and return do not prevent the 167152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// transformation from taking place, though currently the analysis cannot 177152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// support moving any really useful instructions (only dead ones). 18543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner// 2. This pass transforms functions that are prevented from being tail 1924080a98786cf393740cd035e27dd16c12827892Duncan Sands// recursive by an associative and commutative expression to use an 2024080a98786cf393740cd035e27dd16c12827892Duncan Sands// accumulator variable, thus compiling the typical naive factorial or 2124080a98786cf393740cd035e27dd16c12827892Duncan Sands// 'fib' implementation into efficient code. 22d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 3. TRE is performed if the function returns void, if the return 23d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// returns the result returned by the call, or if the function returns a 24d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// run-time constant on all exits from the function. It is possible, though 25d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// unlikely, that the return returns something else (like constant 0), and 26d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in 27d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// the function return the exact same value. 280cade261322242132905914f613d25d16e1a9ff6Nick Lewycky// 4. If it can prove that callees do not access their caller stack frame, 297f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner// they are marked as eligible for tail call elimination (by the code 307f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner// generator). 312240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 327152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// There are several improvements that could be made: 337152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// 347152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// 1. If the function has any alloca instructions, these instructions will be 357152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// moved out of the entry block of the function, causing them to be 367152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// evaluated each time through the tail recursion. Safely keeping allocas 377152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// in the entry block requires analysis to proves that the tail-called 387152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// function does not read or write the stack object. 397a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner// 2. Tail recursion is only performed if the call immediately precedes the 407152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// return instruction. It's possible that there could be a jump between 417152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// the call and the return. 42d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 3. There can be intervening operations between the call and the return that 437152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// prevent the TRE from occurring. For example, there could be GEP's and 447152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// stores to memory that will not be read or written by the call. This 457152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// requires some substantial analysis (such as with DSA) to prove safe to 467152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// move ahead of the call, but doing so could allow many more TREs to be 477152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark. 487f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner// 4. The algorithm we use to detect if callees access their caller stack 497f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner// frames is very primitive. 502240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 512240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner//===----------------------------------------------------------------------===// 522240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 533fc6ef1bb96d9a3194cef667a2d3cbc94e3fb189Chris Lattner#include "llvm/Transforms/Scalar.h" 54d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 5503fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman#include "llvm/ADT/SmallPtrSet.h" 56d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 57d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/CaptureTracking.h" 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Analysis/CFG.h" 59d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InlineCost.h" 60d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 61d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/Loads.h" 6213086a658ae06046ded902229f9918b8bad505bdChandler Carruth#include "llvm/Analysis/TargetTransformInfo.h" 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CallSite.h" 650b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 660b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/IR/DiagnosticInfo.h" 680b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 690b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 700b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 710b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ValueHandle.h" 732240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/Pass.h" 74c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng#include "llvm/Support/Debug.h" 75337c0811381a48b75aec204d96090779fec6606eFrancois Pichet#include "llvm/Support/raw_ostream.h" 76d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/BasicBlockUtils.h" 77d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/Local.h" 78f8485c643412dbff46fe87ea2867445169a5c28eChris Lattnerusing namespace llvm; 79d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "tailcallelim" 81dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 820e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumEliminated, "Number of tail calls removed"); 8360f5ad46c2147af79035a43e5745e46376124780Evan ChengSTATISTIC(NumRetDuped, "Number of return duplicated"); 840e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumAccumAdded, "Number of accumulators introduced"); 852240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 860e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 873e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct TailCallElim : public FunctionPass { 8813086a658ae06046ded902229f9918b8bad505bdChandler Carruth const TargetTransformInfo *TTI; 8913086a658ae06046ded902229f9918b8bad505bdChandler Carruth 90ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 91081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson TailCallElim() : FunctionPass(ID) { 92081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeTailCallElimPass(*PassRegistry::getPassRegistry()); 93081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 94794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 9613086a658ae06046ded902229f9918b8bad505bdChandler Carruth 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 987152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 997152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner private: 100dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool runTRE(Function &F); 101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool markTails(Function &F, bool &AllCallsAreTailCalls); 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 103c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng CallInst *FindTRECandidate(Instruction *I, 104c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool CannotTailCallElimCallsMarkedTail); 105c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, 106c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock *&OldEntry, 107c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool &TailCallsAreMarkedTail, 108a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<PHINode *> &ArgumentPHIs, 109c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool CannotTailCallElimCallsMarkedTail); 110c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool FoldReturnAndProcessPred(BasicBlock *BB, 111c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng ReturnInst *Ret, BasicBlock *&OldEntry, 112c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool &TailCallsAreMarkedTail, 113a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<PHINode *> &ArgumentPHIs, 114c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool CannotTailCallElimCallsMarkedTail); 1157152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner bool ProcessReturningBlock(ReturnInst *RI, BasicBlock *&OldEntry, 116ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner bool &TailCallsAreMarkedTail, 117a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<PHINode *> &ArgumentPHIs, 118ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner bool CannotTailCallElimCallsMarkedTail); 1197152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner bool CanMoveAboveCall(Instruction *I, CallInst *CI); 120543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner Value *CanTransformAccumulatorRecursion(Instruction *I, CallInst *CI); 1212240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner }; 1222240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner} 1232240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 124844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar TailCallElim::ID = 0; 12513086a658ae06046ded902229f9918b8bad505bdChandler CarruthINITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", 12613086a658ae06046ded902229f9918b8bad505bdChandler Carruth "Tail Call Elimination", false, false) 12713086a658ae06046ded902229f9918b8bad505bdChandler CarruthINITIALIZE_AG_DEPENDENCY(TargetTransformInfo) 12813086a658ae06046ded902229f9918b8bad505bdChandler CarruthINITIALIZE_PASS_END(TailCallElim, "tailcallelim", 12913086a658ae06046ded902229f9918b8bad505bdChandler Carruth "Tail Call Elimination", false, false) 130844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 131d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the TailCallElimination pass 132f8485c643412dbff46fe87ea2867445169a5c28eChris LattnerFunctionPass *llvm::createTailCallEliminationPass() { 133f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner return new TailCallElim(); 134f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner} 1353fc6ef1bb96d9a3194cef667a2d3cbc94e3fb189Chris Lattner 13613086a658ae06046ded902229f9918b8bad505bdChandler Carruthvoid TailCallElim::getAnalysisUsage(AnalysisUsage &AU) const { 13713086a658ae06046ded902229f9918b8bad505bdChandler Carruth AU.addRequired<TargetTransformInfo>(); 13813086a658ae06046ded902229f9918b8bad505bdChandler Carruth} 13913086a658ae06046ded902229f9918b8bad505bdChandler Carruth 140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Scan the specified function for alloca instructions. 141dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// If it contains any dynamic allocas, returns false. 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic bool CanTRE(Function &F) { 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Because of PR962, we don't TRE dynamic allocas. 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &BB : F) { 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &I : BB) { 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (AllocaInst *AI = dyn_cast<AllocaInst>(&I)) { 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!AI->isStaticAlloca()) 148dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 151dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 152dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 154cb19438f63019eb557c1fbaeae8a6de78b03c584Nick Lewycky} 155cb19438f63019eb557c1fbaeae8a6de78b03c584Nick Lewycky 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool TailCallElim::runOnFunction(Function &F) { 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (skipOptnoneFunction(F)) 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 1590b06e2331eb549b53ac1e96d4878dfb0910b98f0Argyrios Kyrtzidis 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool AllCallsAreTailCalls = false; 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool Modified = markTails(F, AllCallsAreTailCalls); 162dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (AllCallsAreTailCalls) 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Modified |= runTRE(F); 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Modified; 165dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 16603fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman 167dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesnamespace { 168dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstruct AllocaDerivedValueTracker { 169dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Start at a root value and walk its use-def chain to mark calls that use the 170dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // value or a derived value in AllocaUsers, and places where it may escape in 171dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // EscapePoints. 172dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void walk(Value *Root) { 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallVector<Use *, 32> Worklist; 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallPtrSet<Use *, 32> Visited; 175dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 176dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto AddUsesToWorklist = [&](Value *V) { 177dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &U : V->uses()) { 178dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Visited.insert(&U)) 179dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 180dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Worklist.push_back(&U); 181dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 182dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines }; 183dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 184dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AddUsesToWorklist(Root); 185dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 186dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (!Worklist.empty()) { 187dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Use *U = Worklist.pop_back_val(); 188dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *I = cast<Instruction>(U->getUser()); 189dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 190dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines switch (I->getOpcode()) { 191dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::Call: 192dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::Invoke: { 193dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CallSite CS(I); 194dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool IsNocapture = !CS.isCallee(U) && 195dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CS.doesNotCapture(CS.getArgumentNo(U)); 196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines callUsesLocalStack(CS, IsNocapture); 197dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (IsNocapture) { 198dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If the alloca-derived argument is passed in as nocapture, then it 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // can't propagate to the call's return. That would be capturing. 200dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 201dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 202dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 203dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 204dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::Load: { 205dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // The result of a load is not alloca-derived (unless an alloca has 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // otherwise escaped, but this is a local analysis). 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 208dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::Store: { 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (U->getOperandNo() == 0) 211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EscapePoints.insert(I); 212dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; // Stores have no users to analyze. 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 214dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::BitCast: 215dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::GetElementPtr: 216dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::PHI: 217dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::Select: 218dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines case Instruction::AddrSpaceCast: 219dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 220dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines default: 221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EscapePoints.insert(I); 222dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 223dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 225dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AddUsesToWorklist(I); 226dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 22703fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman } 22803fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman 229dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void callUsesLocalStack(CallSite CS, bool IsNocapture) { 230dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Add it to the list of alloca users. If it's already there, skip further 231dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // processing. 232dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!AllocaUsers.insert(CS.getInstruction())) 233dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 234dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 235dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If it's nocapture then it can't capture the alloca. 236dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (IsNocapture) 237dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 238dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 239dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If it can write to memory, it can leak the alloca value. 240dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CS.onlyReadsMemory()) 241dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EscapePoints.insert(CS.getInstruction()); 24203fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman } 24303fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallPtrSet<Instruction *, 32> AllocaUsers; 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallPtrSet<Instruction *, 32> EscapePoints; 24603fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman}; 247dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 2487f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner 249dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool TailCallElim::markTails(Function &F, bool &AllCallsAreTailCalls) { 250dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (F.callsFunctionThatReturnsTwice()) 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 252dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AllCallsAreTailCalls = true; 253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // The local stack holds all alloca instructions and all byval arguments. 255dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AllocaDerivedValueTracker Tracker; 256dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (Argument &Arg : F.args()) { 257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Arg.hasByValAttr()) 258dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Tracker.walk(&Arg); 259dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 260dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &BB : F) { 261dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &I : BB) 262dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (AllocaInst *AI = dyn_cast<AllocaInst>(&I)) 263dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Tracker.walk(AI); 264dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 266dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool Modified = false; 267dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 268dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Track whether a block is reachable after an alloca has escaped. Blocks that 269dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // contain the escaping instruction will be marked as being visited without an 270dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // escaped alloca, since that is how the block began. 271dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines enum VisitType { 272dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines UNVISITED, 273dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines UNESCAPED, 274dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ESCAPED 275dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines }; 276dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DenseMap<BasicBlock *, VisitType> Visited; 277dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 278dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // We propagate the fact that an alloca has escaped from block to successor. 279dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Visit the blocks that are propagating the escapedness first. To do this, we 280dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // maintain two worklists. 281dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped; 282dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 283dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // We may enter a block and visit it thinking that no alloca has escaped yet, 284dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // then see an escape point and go back around a loop edge and come back to 285dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // the same block twice. Because of this, we defer setting tail on calls when 286dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // we first encounter them in a block. Every entry in this list does not 287dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // statically use an alloca via use-def chain analysis, but may find an alloca 288dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // through other means if the block turns out to be reachable after an escape 289dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // point. 290dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallVector<CallInst *, 32> DeferredTails; 291dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 292dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *BB = &F.getEntryBlock(); 293dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VisitType Escaped = UNESCAPED; 294dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines do { 295dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &I : *BB) { 296dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Tracker.EscapePoints.count(&I)) 297dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Escaped = ESCAPED; 298dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 299dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CallInst *CI = dyn_cast<CallInst>(&I); 300dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!CI || CI->isTailCall()) 301dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 302dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 303dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (CI->doesNotAccessMemory()) { 304dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // A call to a readnone function whose arguments are all things computed 305dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // outside this function can be marked tail. Even if you stored the 306dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // alloca address into a global, a readnone function can't load the 307dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // global anyhow. 308dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // 309dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Note that this runs whether we know an alloca has escaped or not. If 310dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // it has, then we can't trust Tracker.AllocaUsers to be accurate. 311dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool SafeToTail = true; 312dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &Arg : CI->arg_operands()) { 313dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (isa<Constant>(Arg.getUser())) 314dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 315dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Argument *A = dyn_cast<Argument>(Arg.getUser())) 316dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!A->hasByValAttr()) 317dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 318dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SafeToTail = false; 319dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 320dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (SafeToTail) { 322dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines emitOptimizationRemark( 323dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines F.getContext(), "tailcallelim", F, CI->getDebugLoc(), 324dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "marked this readnone call a tail call candidate"); 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CI->setTailCall(); 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Modified = true; 327dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 328dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 329dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 330dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 331dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) { 332dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DeferredTails.push_back(CI); 333dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else { 334dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AllCallsAreTailCalls = false; 335dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 336dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 337dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 338dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto *SuccBB : make_range(succ_begin(BB), succ_end(BB))) { 339dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto &State = Visited[SuccBB]; 340dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (State < Escaped) { 341dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines State = Escaped; 342dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (State == ESCAPED) 343dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines WorklistEscaped.push_back(SuccBB); 344dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines else 345dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines WorklistUnescaped.push_back(SuccBB); 346dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 347dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 348dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 349dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!WorklistEscaped.empty()) { 350dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BB = WorklistEscaped.pop_back_val(); 351dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Escaped = ESCAPED; 352dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else { 353dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BB = nullptr; 354dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (!WorklistUnescaped.empty()) { 355dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto *NextBB = WorklistUnescaped.pop_back_val(); 356dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Visited[NextBB] == UNESCAPED) { 357dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BB = NextBB; 358dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Escaped = UNESCAPED; 359dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 360dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 361dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 362dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 363dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } while (BB); 364dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (CallInst *CI : DeferredTails) { 366dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Visited[CI->getParent()] != ESCAPED) { 367dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If the escape point was part way through the block, calls after the 368dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // escape point wouldn't have been put into DeferredTails. 369dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines emitOptimizationRemark(F.getContext(), "tailcallelim", F, 370dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CI->getDebugLoc(), 371dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "marked this call a tail call candidate"); 372dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CI->setTailCall(); 373dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Modified = true; 374dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else { 375dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AllCallsAreTailCalls = false; 376dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 378dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 379dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Modified; 380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 382dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool TailCallElim::runTRE(Function &F) { 3832240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // If this function is a varargs function, we won't be able to PHI the args 3842240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // right, so don't even try to convert it... 3852240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (F.getFunctionType()->isVarArg()) return false; 3862240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 38713086a658ae06046ded902229f9918b8bad505bdChandler Carruth TTI = &getAnalysis<TargetTransformInfo>(); 388dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BasicBlock *OldEntry = nullptr; 389ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner bool TailCallsAreMarkedTail = false; 3900cade261322242132905914f613d25d16e1a9ff6Nick Lewycky SmallVector<PHINode*, 8> ArgumentPHIs; 3912240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner bool MadeChange = false; 3927f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner 39303fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman // CanTRETailMarkedCall - If false, we cannot perform TRE on tail calls 394ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // marked with the 'tail' attribute, because doing so would cause the stack 39503fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman // size to increase (real TRE would deallocate variable sized allocas, TRE 396ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // doesn't). 397dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool CanTRETailMarkedCall = CanTRE(F); 398a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 399dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Change any tail recursive calls to loops. 40003fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman // 40103fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman // FIXME: The code generator produces really bad code when an 'escaping 40203fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman // alloca' is changed from being a static alloca to being a dynamic alloca. 40303fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman // Until this is resolved, disable this transformation if that would ever 40403fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman // happen. This bug is PR962. 405dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 406dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) { 407dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool Change = ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, 408dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ArgumentPHIs, !CanTRETailMarkedCall); 409dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Change && BB->getFirstNonPHIOrDbg() == Ret) 410dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Change = FoldReturnAndProcessPred(BB, Ret, OldEntry, 411dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TailCallsAreMarkedTail, ArgumentPHIs, 412dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines !CanTRETailMarkedCall); 413dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MadeChange |= Change; 414c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng } 415c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng } 416ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner 417cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // If we eliminated any tail recursions, it's possible that we inserted some 418cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // silly PHI nodes which just merge an initial value (the incoming operand) 419cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // with themselves. Check to see if we did and clean up our mess if so. This 420cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // occurs when a function passes an argument straight through to its tail 421cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // call. 422dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) { 423dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PHINode *PN = ArgumentPHIs[i]; 424cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner 425dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If the PHI Node is a dynamic constant, replace it with the value it is. 426dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *PNV = SimplifyInstruction(PN)) { 427dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PN->replaceAllUsesWith(PNV); 428dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PN->eraseFromParent(); 42903fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman } 43003fddb710e1db886dc158fd6ac6decf8201fe4aaMichael Gottesman } 4317f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner 4322240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner return MadeChange; 4332240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner} 4347152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 4350b06e2331eb549b53ac1e96d4878dfb0910b98f0Argyrios Kyrtzidis 436543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// CanMoveAboveCall - Return true if it is safe to move the specified 437543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// instruction from after the call to before the call, assuming that all 438543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// instructions between the call and this instruction are movable. 439543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// 4407152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattnerbool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { 4417152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // FIXME: We can move load/store/call/free instructions above the call if the 4427152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // call does not mod/ref the memory location being processed. 4436a35b40250735a50efe66c88414cdd3b79185019Chris Lattner if (I->mayHaveSideEffects()) // This also handles volatile loads. 4447152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return false; 445a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 4460cade261322242132905914f613d25d16e1a9ff6Nick Lewycky if (LoadInst *L = dyn_cast<LoadInst>(I)) { 4476a35b40250735a50efe66c88414cdd3b79185019Chris Lattner // Loads may always be moved above calls without side effects. 4486a35b40250735a50efe66c88414cdd3b79185019Chris Lattner if (CI->mayHaveSideEffects()) { 4496a35b40250735a50efe66c88414cdd3b79185019Chris Lattner // Non-volatile loads may be moved above a call with side effects if it 4506a35b40250735a50efe66c88414cdd3b79185019Chris Lattner // does not write to memory and the load provably won't trap. 4516a35b40250735a50efe66c88414cdd3b79185019Chris Lattner // FIXME: Writes to memory only matter if they may alias the pointer 4526a35b40250735a50efe66c88414cdd3b79185019Chris Lattner // being loaded from. 4536a35b40250735a50efe66c88414cdd3b79185019Chris Lattner if (CI->mayWriteToMemory() || 45449db68fba01722ca032dc5170f8248a9d25f0199Bob Wilson !isSafeToLoadUnconditionally(L->getPointerOperand(), L, 45549db68fba01722ca032dc5170f8248a9d25f0199Bob Wilson L->getAlignment())) 4566a35b40250735a50efe66c88414cdd3b79185019Chris Lattner return false; 4576a35b40250735a50efe66c88414cdd3b79185019Chris Lattner } 4586a35b40250735a50efe66c88414cdd3b79185019Chris Lattner } 4597152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 4607152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Otherwise, if this is a side-effect free instruction, check to make sure 4617152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // that it does not use the return value of the call. If it doesn't use the 4627152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // return value of the call, it must only use things that are defined before 4637152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // the call, or movable instructions between the call and the instruction 4647152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // itself. 4657152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 4667152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (I->getOperand(i) == CI) 4677152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return false; 4687152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return true; 4697152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner} 4707152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 471d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// isDynamicConstant - Return true if the specified value is the same when the 472d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// return would exit as it was when the initial iteration of the recursive 473d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// function was executed. 474d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 475d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// We currently handle static constants and arguments that are not modified as 476d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// part of the recursion. 477d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 478f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewyckystatic bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) { 479d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (isa<Constant>(V)) return true; // Static constants are always dyn consts 480d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 481d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Check to see if this is an immutable argument, if so, the value 482d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // will be available to initialize the accumulator. 483d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (Argument *Arg = dyn_cast<Argument>(V)) { 484d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Figure out which argument number this is... 485d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner unsigned ArgNo = 0; 486d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner Function *F = CI->getParent()->getParent(); 487e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator AI = F->arg_begin(); &*AI != Arg; ++AI) 488d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner ++ArgNo; 489fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 490d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // If we are passing this argument into call as the corresponding 491d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // argument operand, then the argument is dynamically constant. 492d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Otherwise, we cannot transform this function safely. 493de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif if (CI->getArgOperand(ArgNo) == Arg) 494d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return true; 495d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner } 496f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky 497f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky // Switch cases are always constant integers. If the value is being switched 498f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky // on and the return is only reachable from one of its cases, it's 499f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky // effectively constant. 500f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky if (BasicBlock *UniquePred = RI->getParent()->getUniquePredecessor()) 501f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky if (SwitchInst *SI = dyn_cast<SwitchInst>(UniquePred->getTerminator())) 502f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky if (SI->getCondition() == V) 503f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky return SI->getDefaultDest() != RI->getParent(); 504f80fcd00b3590626a6110fe5fbe9b5fd2a8be1aeNick Lewycky 505d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Not a constant or immutable argument, we can't safely transform. 506d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return false; 507d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner} 508d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 509d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// getCommonReturnValue - Check to see if the function containing the specified 510d50e9e2566479301e687fc81e16dab7e3c2b50eaDuncan Sands// tail call consistently returns the same runtime-constant value at all exit 511d50e9e2566479301e687fc81e16dab7e3c2b50eaDuncan Sands// points except for IgnoreRI. If so, return the returned value. 512d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 513d50e9e2566479301e687fc81e16dab7e3c2b50eaDuncan Sandsstatic Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { 514d50e9e2566479301e687fc81e16dab7e3c2b50eaDuncan Sands Function *F = CI->getParent()->getParent(); 515dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *ReturnedValue = nullptr; 516d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 517b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) { 518b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator()); 519dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (RI == nullptr || RI == IgnoreRI) continue; 520b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner 521b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // We can only perform this transformation if the value returned is 522b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // evaluatable at the start of the initial invocation of the function, 523b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // instead of at the end of the evaluation. 524b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // 525b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner Value *RetOp = RI->getOperand(0); 526b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner if (!isDynamicConstant(RetOp, CI, RI)) 527dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 528b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner 529b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner if (ReturnedValue && RetOp != ReturnedValue) 530dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; // Cannot transform if differing values are returned. 531b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner ReturnedValue = RetOp; 532b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner } 533d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return ReturnedValue; 534d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner} 5357152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 536543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// CanTransformAccumulatorRecursion - If the specified instruction can be 537543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// transformed using accumulator recursion elimination, return the constant 538543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// which is the start of the accumulator value. Otherwise return null. 539543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// 540543d622ef7505910c1cdc09ada0ab797c3437590Chris LattnerValue *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I, 541543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner CallInst *CI) { 542dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!I->isAssociative() || !I->isCommutative()) return nullptr; 543543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner assert(I->getNumOperands() == 2 && 54424080a98786cf393740cd035e27dd16c12827892Duncan Sands "Associative/commutative operations should have 2 args!"); 545543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 546b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // Exactly one operand should be the result of the call instruction. 54707e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov if ((I->getOperand(0) == CI && I->getOperand(1) == CI) || 54807e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov (I->getOperand(0) != CI && I->getOperand(1) != CI)) 549dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 550543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 551543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // The only user of this instruction we allow is a single return instruction. 55236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!I->hasOneUse() || !isa<ReturnInst>(I->user_back())) 553dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 554543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 555543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Ok, now we have to check all of the other return instructions in this 556543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // function. If they return non-constants or differing values, then we cannot 557543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // transform the function safely. 55836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return getCommonReturnValue(cast<ReturnInst>(I->user_back()), CI); 559543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner} 560543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 561c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Chengstatic Instruction *FirstNonDbg(BasicBlock::iterator I) { 562c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng while (isa<DbgInfoIntrinsic>(I)) 563c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng ++I; 564c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return &*I; 565c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng} 566c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 567c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan ChengCallInst* 568c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan ChengTailCallElim::FindTRECandidate(Instruction *TI, 569c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool CannotTailCallElimCallsMarkedTail) { 570c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock *BB = TI->getParent(); 5717152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner Function *F = BB->getParent(); 5727152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 573c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (&BB->front() == TI) // Make sure there is something before the terminator. 574dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 575a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5767152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Scan backwards from the return, checking to see if there is a tail call in 5777152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // this block. If so, set CI to it. 578dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CallInst *CI = nullptr; 579c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock::iterator BBI = TI; 580c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng while (true) { 5817152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner CI = dyn_cast<CallInst>(BBI); 5827152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (CI && CI->getCalledFunction() == F) 5837152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner break; 5847152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 5857152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (BBI == BB->begin()) 586dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; // Didn't find a potential tail call. 5877152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner --BBI; 5887152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner } 5897152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 590ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // If this call is marked as a tail call, and if there are dynamic allocas in 591ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // the function, we cannot perform this optimization. 592ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner if (CI->isTailCall() && CannotTailCallElimCallsMarkedTail) 593dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 594ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner 595ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman // As a special case, detect code like this: 596ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call 597ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman // and disable this xform in this case, because the code generator will 598ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman // lower the call to fabs into inline code. 599a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem if (BB == &F->getEntryBlock() && 600c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng FirstNonDbg(BB->front()) == CI && 60136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FirstNonDbg(std::next(BB->begin())) == TI && 60213086a658ae06046ded902229f9918b8bad505bdChandler Carruth CI->getCalledFunction() && 60313086a658ae06046ded902229f9918b8bad505bdChandler Carruth !TTI->isLoweredToCall(CI->getCalledFunction())) { 604ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman // A single-block function with just a call and a return. Check that 605ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman // the arguments match. 606ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman CallSite::arg_iterator I = CallSite(CI).arg_begin(), 607ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman E = CallSite(CI).arg_end(); 608ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman Function::arg_iterator FI = F->arg_begin(), 609ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman FE = F->arg_end(); 610ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman for (; I != E && FI != FE; ++I, ++FI) 611ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman if (*I != &*FI) break; 612ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman if (I == E && FI == FE) 613dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 614ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman } 615ea25b48af33be42e19236d8eac26bd42b45bcc1bDan Gohman 616c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return CI; 617c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng} 618c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 619c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Chengbool TailCallElim::EliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, 620c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock *&OldEntry, 621c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool &TailCallsAreMarkedTail, 622a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<PHINode *> &ArgumentPHIs, 623c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool CannotTailCallElimCallsMarkedTail) { 62424080a98786cf393740cd035e27dd16c12827892Duncan Sands // If we are introducing accumulator recursion to eliminate operations after 62524080a98786cf393740cd035e27dd16c12827892Duncan Sands // the call instruction that are both associative and commutative, the initial 62624080a98786cf393740cd035e27dd16c12827892Duncan Sands // value for the accumulator is placed in this variable. If this value is set 62724080a98786cf393740cd035e27dd16c12827892Duncan Sands // then we actually perform accumulator recursion elimination instead of 628d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // simple tail recursion elimination. If the operation is an LLVM instruction 629d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // (eg: "add") then it is recorded in AccumulatorRecursionInstr. If not, then 630d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // we are handling the case when the return instruction returns a constant C 631d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // which is different to the constant returned by other return instructions 632d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // (which is recorded in AccumulatorRecursionEliminationInitVal). This is a 633d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // special case of accumulator recursion, the operation being "return C". 634dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *AccumulatorRecursionEliminationInitVal = nullptr; 635dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *AccumulatorRecursionInstr = nullptr; 636543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 6377152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Ok, we found a potential tail call. We can currently only transform the 6387152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // tail call if all of the instructions between the call and the return are 6397152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // movable to above the call itself, leaving the call next to the return. 6407152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Check that this is the case now. 641c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock::iterator BBI = CI; 642c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng for (++BBI; &*BBI != Ret; ++BBI) { 643b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner if (CanMoveAboveCall(BBI, CI)) continue; 644a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 645b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // If we can't move the instruction above the call, it might be because it 6467a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // is an associative and commutative operation that could be transformed 647b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // using accumulator recursion elimination. Check to see if this is the 648b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // case, and if so, remember the initial accumulator value for later. 649b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner if ((AccumulatorRecursionEliminationInitVal = 650b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner CanTransformAccumulatorRecursion(BBI, CI))) { 651b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // Yes, this is accumulator recursion. Remember which instruction 652b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner // accumulates. 653b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner AccumulatorRecursionInstr = BBI; 654b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner } else { 655b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner return false; // Otherwise, we cannot eliminate the tail recursion! 656543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } 657b5d84d13bc338efc4eeed87d19c49dfaed38e036Chris Lattner } 6587152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 6597152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // We can only transform call/return pairs that either ignore the return value 660d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // of the call and return void, ignore the value of the call and return a 661d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // constant, return the value returned by the tail call, or that are being 662d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // accumulator recursion variable eliminated. 663826c49132a9cba1e08a5fce78d05561d9a3746ceDevang Patel if (Ret->getNumOperands() == 1 && Ret->getReturnValue() != CI && 6643b5f45042b17ad52815e3dd6c0c1df99f196dd04Chris Lattner !isa<UndefValue>(Ret->getReturnValue()) && 665dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AccumulatorRecursionEliminationInitVal == nullptr && 666dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines !getCommonReturnValue(nullptr, CI)) { 667d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // One case remains that we are able to handle: the current return 668d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // instruction returns a constant, and all other return instructions 669d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // return a different constant. 670d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands if (!isDynamicConstant(Ret->getReturnValue(), CI, Ret)) 671d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands return false; // Current return instruction does not return a constant. 672d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // Check that all other return instructions return a common constant. If 673d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // so, record it in AccumulatorRecursionEliminationInitVal. 674d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands AccumulatorRecursionEliminationInitVal = getCommonReturnValue(Ret, CI); 675d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands if (!AccumulatorRecursionEliminationInitVal) 676d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands return false; 677d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands } 6787152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 679c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock *BB = Ret->getParent(); 680c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng Function *F = BB->getParent(); 681c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 682dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines emitOptimizationRemark(F->getContext(), "tailcallelim", *F, CI->getDebugLoc(), 683dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "transforming tail recursion to loop"); 684dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 6857152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // OK! We can transform this tail call. If this is the first one found, 6867152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // create the new entry block, allowing us to branch back to the old entry. 687dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!OldEntry) { 6887152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner OldEntry = &F->getEntryBlock(); 6891d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *NewEntry = BasicBlock::Create(F->getContext(), "", F, OldEntry); 6906934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner NewEntry->takeName(OldEntry); 6916934a04a8c15e9971cd1ea4d5c8df2d7afdd5be5Chris Lattner OldEntry->setName("tailrecurse"); 692051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(OldEntry, NewEntry); 693fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 694ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // If this tail call is marked 'tail' and if there are any allocas in the 695ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // entry block, move them up to the new entry block. 696ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner TailCallsAreMarkedTail = CI->isTailCall(); 697ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner if (TailCallsAreMarkedTail) 698ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // Move all fixed sized allocas from OldEntry to NewEntry. 699ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner for (BasicBlock::iterator OEBI = OldEntry->begin(), E = OldEntry->end(), 700ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner NEBI = NewEntry->begin(); OEBI != E; ) 701ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++)) 702ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner if (isa<ConstantInt>(AI->getArraySize())) 7034bc5f8071a28b6fc4f4c2207dd03a5f747d0d84bChris Lattner AI->moveBefore(NEBI); 704ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner 7057152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Now that we have created a new block, which jumps to the entry 7067152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // block, insert a PHI node for each argument of the function. 7077152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // For now, we initialize each PHI to only have the real arguments 7087152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // which are passed in. 7097152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner Instruction *InsertPos = OldEntry->begin(); 7107f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 7117f78f218fdb3515a61b995ac64f909bfd8ee84a7Chris Lattner I != E; ++I) { 7123ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *PN = PHINode::Create(I->getType(), 2, 713b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif I->getName() + ".tr", InsertPos); 7147152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner I->replaceAllUsesWith(PN); // Everyone use the PHI node now! 7157152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner PN->addIncoming(I, NewEntry); 7167152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner ArgumentPHIs.push_back(PN); 7177152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner } 7187152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner } 719fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 720ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // If this function has self recursive calls in the tail position where some 721ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // are marked tail and some are not, only transform one flavor or another. We 722ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // have to choose whether we move allocas in the entry block to the new entry 723ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // block or not, so we can't make a good choice for both. NOTE: We could do 724ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // slightly better here in the case that the function has no entry block 725ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner // allocas. 726ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner if (TailCallsAreMarkedTail && !CI->isTailCall()) 727ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner return false; 728ce869ee05bfcb9d4750a3d0919a8260a727841c3Chris Lattner 7297152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Ok, now that we know we have a pseudo-entry block WITH all of the 7307152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // required PHI nodes, add entries into the PHI node for the actual 7317152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // parameters passed into the tail-recursive call. 732407014f9a5f05f5a5867e5992a036358acc4a441Gabor Greif for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) 733de9f5452d3ae894bb7fdd455cec5af50e2560aa5Gabor Greif ArgumentPHIs[i]->addIncoming(CI->getArgOperand(i), BB); 734fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 735543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // If we are introducing an accumulator variable to eliminate the recursion, 736543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // do so now. Note that we _know_ that no subsequent tail recursion 737543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // eliminations will happen on this function because of the way the 738543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // accumulator recursion predicate is set up. 739543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // 740543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (AccumulatorRecursionEliminationInitVal) { 741543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner Instruction *AccRecInstr = AccumulatorRecursionInstr; 742543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Start by inserting a new PHI node for the accumulator. 743d8b4fb4aab4d6fedb2b14bed1b846451b17bde7cJay Foad pred_iterator PB = pred_begin(OldEntry), PE = pred_end(OldEntry); 744d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands PHINode *AccPN = 745d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands PHINode::Create(AccumulatorRecursionEliminationInitVal->getType(), 7463ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad std::distance(PB, PE) + 1, 747d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands "accumulator.tr", OldEntry->begin()); 748543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 749543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Loop over all of the predecessors of the tail recursion block. For the 750543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // real entry into the function we seed the PHI with the initial value, 751543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // computed earlier. For any other existing branches to this block (due to 752543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // other tail recursions eliminated) the accumulator is not modified. 753543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Because we haven't added the branch in the current block to OldEntry yet, 754543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // it will not show up as a predecessor. 755d8b4fb4aab4d6fedb2b14bed1b846451b17bde7cJay Foad for (pred_iterator PI = PB; PI != PE; ++PI) { 756a8b9df7bd96e0b0bc6dec448d30b7d72180b6595Gabor Greif BasicBlock *P = *PI; 757a8b9df7bd96e0b0bc6dec448d30b7d72180b6595Gabor Greif if (P == &F->getEntryBlock()) 758a8b9df7bd96e0b0bc6dec448d30b7d72180b6595Gabor Greif AccPN->addIncoming(AccumulatorRecursionEliminationInitVal, P); 759543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner else 760a8b9df7bd96e0b0bc6dec448d30b7d72180b6595Gabor Greif AccPN->addIncoming(AccPN, P); 761543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } 762543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 763d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands if (AccRecInstr) { 764d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // Add an incoming argument for the current block, which is computed by 765d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // our associative and commutative accumulator instruction. 766d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands AccPN->addIncoming(AccRecInstr, BB); 767d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands 768d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // Next, rewrite the accumulator recursion instruction so that it does not 769d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // use the result of the call anymore, instead, use the PHI node we just 770d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // inserted. 771d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN); 772d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands } else { 773d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // Add an incoming argument for the current block, which is just the 774d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands // constant returned by the current return instruction. 775d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands AccPN->addIncoming(Ret->getReturnValue(), BB); 776d0d3ccc827de69de3d9f666aa922f5f191219a06Duncan Sands } 777543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 778543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Finally, rewrite any return instructions in the program to return the PHI 779543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // node instead of the "initval" that they do currently. This loop will 780543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // actually rewrite the return value we are destroying, but that's ok. 781543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) 782543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator())) 783543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner RI->setOperand(0, AccPN); 784543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner ++NumAccumAdded; 785543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } 786543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 7877152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Now that all of the PHI nodes are in place, remove the call and 7887152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // ret instructions, replacing them with an unconditional branch. 78981199d2545112fcff5a6e055eb71e2a4950192a7Devang Patel BranchInst *NewBI = BranchInst::Create(OldEntry, Ret); 79081199d2545112fcff5a6e055eb71e2a4950192a7Devang Patel NewBI->setDebugLoc(CI->getDebugLoc()); 79181199d2545112fcff5a6e055eb71e2a4950192a7Devang Patel 7927152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner BB->getInstList().erase(Ret); // Remove return. 7937152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner BB->getInstList().erase(CI); // Remove call. 794543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner ++NumEliminated; 7957152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return true; 7967152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner} 797c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 798c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Chengbool TailCallElim::FoldReturnAndProcessPred(BasicBlock *BB, 799c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng ReturnInst *Ret, BasicBlock *&OldEntry, 800c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool &TailCallsAreMarkedTail, 801a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<PHINode *> &ArgumentPHIs, 802c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool CannotTailCallElimCallsMarkedTail) { 803c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng bool Change = false; 804c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 805c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // If the return block contains nothing but the return and PHI's, 806c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // there might be an opportunity to duplicate the return in its 807c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // predecessors and perform TRC there. Look for predecessors that end 808c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng // in unconditional branch and recursive call(s). 809c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng SmallVector<BranchInst*, 8> UncondBranchPreds; 810c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 811c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock *Pred = *PI; 812c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng TerminatorInst *PTI = Pred->getTerminator(); 813c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 814c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (BI->isUnconditional()) 815c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng UncondBranchPreds.push_back(BI); 816c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng } 817c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 818c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng while (!UncondBranchPreds.empty()) { 819c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BranchInst *BI = UncondBranchPreds.pop_back_val(); 820c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng BasicBlock *Pred = BI->getParent(); 821c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (CallInst *CI = FindTRECandidate(BI, CannotTailCallElimCallsMarkedTail)){ 822c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng DEBUG(dbgs() << "FOLDING: " << *BB 823c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng << "INTO UNCOND BRANCH PRED: " << *Pred); 824c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng EliminateRecursiveTailCall(CI, FoldReturnIntoUncondBranch(Ret, BB, Pred), 825c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng OldEntry, TailCallsAreMarkedTail, ArgumentPHIs, 826c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng CannotTailCallElimCallsMarkedTail); 82760f5ad46c2147af79035a43e5745e46376124780Evan Cheng ++NumRetDuped; 828c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng Change = true; 829c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng } 830c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng } 831c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 832c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return Change; 833c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng} 834c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 835a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topperbool 836a0ec3f9b7b826b9b40b80199923b664bad808cceCraig TopperTailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, 837a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper bool &TailCallsAreMarkedTail, 838a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper SmallVectorImpl<PHINode *> &ArgumentPHIs, 839a0ec3f9b7b826b9b40b80199923b664bad808cceCraig Topper bool CannotTailCallElimCallsMarkedTail) { 840c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng CallInst *CI = FindTRECandidate(Ret, CannotTailCallElimCallsMarkedTail); 841c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng if (!CI) 842c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return false; 843c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng 844c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng return EliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail, 845c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng ArgumentPHIs, 846c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng CannotTailCallElimCallsMarkedTail); 847c3f507f98a0747bd256e1c13536060b6fc5c4b62Evan Cheng} 848