TailRecursionElimination.cpp revision fd93908ae8b9684fe71c239e3c6cfe13ff6a2663
12240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner//===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source 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 19543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner// recursive by an associative expression to use an accumulator variable, 20543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner// thus compiling the typical naive factorial or 'fib' implementation into 21543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner// 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. 282240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 297152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// There are several improvements that could be made: 307152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// 317152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// 1. If the function has any alloca instructions, these instructions will be 327152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// moved out of the entry block of the function, causing them to be 337152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// evaluated each time through the tail recursion. Safely keeping allocas 347152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// in the entry block requires analysis to proves that the tail-called 357152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// function does not read or write the stack object. 362240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 2. Tail recursion is only performed if the call immediately preceeds the 377152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// return instruction. It's possible that there could be a jump between 387152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// the call and the return. 39d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 3. There can be intervening operations between the call and the return that 407152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// prevent the TRE from occurring. For example, there could be GEP's and 417152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// stores to memory that will not be read or written by the call. This 427152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// requires some substantial analysis (such as with DSA) to prove safe to 437152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// move ahead of the call, but doing so could allow many more TREs to be 447152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner// performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark. 452240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 462240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner//===----------------------------------------------------------------------===// 472240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 483fc6ef1bb96d9a3194cef667a2d3cbc94e3fb189Chris Lattner#include "llvm/Transforms/Scalar.h" 492240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/DerivedTypes.h" 502240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/Function.h" 512240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/Instructions.h" 522240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/Pass.h" 53543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner#include "llvm/Support/CFG.h" 54551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 55f8485c643412dbff46fe87ea2867445169a5c28eChris Lattnerusing namespace llvm; 56d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 572240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattnernamespace { 582240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner Statistic<> NumEliminated("tailcallelim", "Number of tail calls removed"); 59543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner Statistic<> NumAccumAdded("tailcallelim","Number of accumulators introduced"); 602240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 612240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner struct TailCallElim : public FunctionPass { 622240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner virtual bool runOnFunction(Function &F); 637152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 647152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner private: 657152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner bool ProcessReturningBlock(ReturnInst *RI, BasicBlock *&OldEntry, 667152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner std::vector<PHINode*> &ArgumentPHIs); 677152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner bool CanMoveAboveCall(Instruction *I, CallInst *CI); 68543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner Value *CanTransformAccumulatorRecursion(Instruction *I, CallInst *CI); 692240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner }; 702240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner RegisterOpt<TailCallElim> X("tailcallelim", "Tail Call Elimination"); 712240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner} 722240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 73d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the TailCallElimination pass 74f8485c643412dbff46fe87ea2867445169a5c28eChris LattnerFunctionPass *llvm::createTailCallEliminationPass() { 75f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner return new TailCallElim(); 76f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner} 773fc6ef1bb96d9a3194cef667a2d3cbc94e3fb189Chris Lattner 782240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 792240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattnerbool TailCallElim::runOnFunction(Function &F) { 802240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // If this function is a varargs function, we won't be able to PHI the args 812240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // right, so don't even try to convert it... 822240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (F.getFunctionType()->isVarArg()) return false; 832240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 842240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner BasicBlock *OldEntry = 0; 852240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner std::vector<PHINode*> ArgumentPHIs; 862240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner bool MadeChange = false; 872240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 882240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Loop over the function, looking for any returning blocks... 892240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 902240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) 917152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner MadeChange |= ProcessReturningBlock(Ret, OldEntry, ArgumentPHIs); 92fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 93cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // If we eliminated any tail recursions, it's possible that we inserted some 94cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // silly PHI nodes which just merge an initial value (the incoming operand) 95cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // with themselves. Check to see if we did and clean up our mess if so. This 96cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // occurs when a function passes an argument straight through to its tail 97cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // call. 98cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner if (!ArgumentPHIs.empty()) { 99cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner unsigned NumIncoming = ArgumentPHIs[0]->getNumIncomingValues(); 100cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) { 101cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner PHINode *PN = ArgumentPHIs[i]; 102cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner Value *V = 0; 103cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner for (unsigned op = 0, e = NumIncoming; op != e; ++op) { 104cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner Value *Op = PN->getIncomingValue(op); 105cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner if (Op != PN) { 106cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner if (V == 0) { 107cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner V = Op; // First value seen? 108cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner } else if (V != Op) { 109cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner V = 0; 110cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner break; 111cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner } 112cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner } 113cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner } 114cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner 115cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner // If the PHI Node is a dynamic constant, replace it with the value it is. 116cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner if (V) { 117cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner PN->replaceAllUsesWith(V); 118cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner PN->getParent()->getInstList().erase(PN); 119cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner } 120cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner } 121cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner } 122cf2f89251d45bc9783917874adb9029f71d50068Chris Lattner 1232240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner return MadeChange; 1242240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner} 1257152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 1267152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 127543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// CanMoveAboveCall - Return true if it is safe to move the specified 128543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// instruction from after the call to before the call, assuming that all 129543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// instructions between the call and this instruction are movable. 130543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// 1317152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattnerbool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { 1327152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // FIXME: We can move load/store/call/free instructions above the call if the 1337152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // call does not mod/ref the memory location being processed. 1347152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (I->mayWriteToMemory() || isa<LoadInst>(I)) 1357152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return false; 1367152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 1377152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Otherwise, if this is a side-effect free instruction, check to make sure 1387152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // that it does not use the return value of the call. If it doesn't use the 1397152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // return value of the call, it must only use things that are defined before 1407152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // the call, or movable instructions between the call and the instruction 1417152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // itself. 1427152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 1437152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (I->getOperand(i) == CI) 1447152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return false; 1457152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return true; 1467152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner} 1477152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 148d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// isDynamicConstant - Return true if the specified value is the same when the 149d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// return would exit as it was when the initial iteration of the recursive 150d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// function was executed. 151d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 152d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// We currently handle static constants and arguments that are not modified as 153d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// part of the recursion. 154d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 155d64152a70842b2f4186aa912938e69ca09c1434cChris Lattnerstatic bool isDynamicConstant(Value *V, CallInst *CI) { 156d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (isa<Constant>(V)) return true; // Static constants are always dyn consts 157d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 158d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Check to see if this is an immutable argument, if so, the value 159d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // will be available to initialize the accumulator. 160d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (Argument *Arg = dyn_cast<Argument>(V)) { 161d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Figure out which argument number this is... 162d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner unsigned ArgNo = 0; 163d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner Function *F = CI->getParent()->getParent(); 164e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator AI = F->arg_begin(); &*AI != Arg; ++AI) 165d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner ++ArgNo; 166fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 167d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // If we are passing this argument into call as the corresponding 168d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // argument operand, then the argument is dynamically constant. 169d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Otherwise, we cannot transform this function safely. 170d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (CI->getOperand(ArgNo+1) == Arg) 171d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return true; 172d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner } 173d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // Not a constant or immutable argument, we can't safely transform. 174d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return false; 175d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner} 176d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 177d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// getCommonReturnValue - Check to see if the function containing the specified 178d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// return instruction and tail call consistently returns the same 179d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// runtime-constant value at all exit points. If so, return the returned value. 180d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner// 181d64152a70842b2f4186aa912938e69ca09c1434cChris Lattnerstatic Value *getCommonReturnValue(ReturnInst *TheRI, CallInst *CI) { 182d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner Function *F = TheRI->getParent()->getParent(); 183d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner Value *ReturnedValue = 0; 184d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 185d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) 186d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator())) 187d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (RI != TheRI) { 188d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner Value *RetOp = RI->getOperand(0); 189d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 190d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // We can only perform this transformation if the value returned is 191d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // evaluatable at the start of the initial invocation of the function, 192d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // instead of at the end of the evaluation. 193d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // 194d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (!isDynamicConstant(RetOp, CI)) 195d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return 0; 196d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner 197d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner if (ReturnedValue && RetOp != ReturnedValue) 198d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return 0; // Cannot transform if differing values are returned. 199d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner ReturnedValue = RetOp; 200d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner } 201d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return ReturnedValue; 202d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner} 2037152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 204543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// CanTransformAccumulatorRecursion - If the specified instruction can be 205543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// transformed using accumulator recursion elimination, return the constant 206543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// which is the start of the accumulator value. Otherwise return null. 207543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner/// 208543d622ef7505910c1cdc09ada0ab797c3437590Chris LattnerValue *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I, 209543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner CallInst *CI) { 210543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (!I->isAssociative()) return 0; 211543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner assert(I->getNumOperands() == 2 && 212543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner "Associative operations should have 2 args!"); 213543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 214543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Exactly one operand should be the result of the call instruction... 215543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (I->getOperand(0) == CI && I->getOperand(1) == CI || 216543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner I->getOperand(0) != CI && I->getOperand(1) != CI) 217543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner return 0; 218543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 219543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // The only user of this instruction we allow is a single return instruction. 220543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (!I->hasOneUse() || !isa<ReturnInst>(I->use_back())) 221543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner return 0; 222543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 223543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Ok, now we have to check all of the other return instructions in this 224543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // function. If they return non-constants or differing values, then we cannot 225543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // transform the function safely. 226d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner return getCommonReturnValue(cast<ReturnInst>(I->use_back()), CI); 227543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner} 228543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 2297152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattnerbool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, 2307152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner std::vector<PHINode*> &ArgumentPHIs) { 2317152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner BasicBlock *BB = Ret->getParent(); 2327152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner Function *F = BB->getParent(); 2337152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 2347152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (&BB->front() == Ret) // Make sure there is something before the ret... 2357152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return false; 2367152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 2377152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Scan backwards from the return, checking to see if there is a tail call in 2387152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // this block. If so, set CI to it. 2397152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner CallInst *CI; 2407152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner BasicBlock::iterator BBI = Ret; 2417152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner while (1) { 2427152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner CI = dyn_cast<CallInst>(BBI); 2437152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (CI && CI->getCalledFunction() == F) 2447152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner break; 2457152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 2467152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (BBI == BB->begin()) 2477152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return false; // Didn't find a potential tail call. 2487152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner --BBI; 2497152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner } 2507152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 251543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // If we are introducing accumulator recursion to eliminate associative 252543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // operations after the call instruction, this variable contains the initial 253543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // value for the accumulator. If this value is set, we actually perform 254543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // accumulator recursion elimination instead of simple tail recursion 255543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // elimination. 256543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner Value *AccumulatorRecursionEliminationInitVal = 0; 257543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner Instruction *AccumulatorRecursionInstr = 0; 258543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 2597152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Ok, we found a potential tail call. We can currently only transform the 2607152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // tail call if all of the instructions between the call and the return are 2617152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // movable to above the call itself, leaving the call next to the return. 2627152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Check that this is the case now. 2637152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner for (BBI = CI, ++BBI; &*BBI != Ret; ++BBI) 264543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (!CanMoveAboveCall(BBI, CI)) { 265543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // If we can't move the instruction above the call, it might be because it 266543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // is an associative operation that could be tranformed using accumulator 267543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // recursion elimination. Check to see if this is the case, and if so, 268543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // remember the initial accumulator value for later. 269543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if ((AccumulatorRecursionEliminationInitVal = 270543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner CanTransformAccumulatorRecursion(BBI, CI))) { 271543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Yes, this is accumulator recursion. Remember which instruction 272543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // accumulates. 273543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner AccumulatorRecursionInstr = BBI; 274543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } else { 275543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner return false; // Otherwise, we cannot eliminate the tail recursion! 276543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } 277543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } 2787152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 2797152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // We can only transform call/return pairs that either ignore the return value 280d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // of the call and return void, ignore the value of the call and return a 281d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // constant, return the value returned by the tail call, or that are being 282d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner // accumulator recursion variable eliminated. 283543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (Ret->getNumOperands() != 0 && Ret->getReturnValue() != CI && 284d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner AccumulatorRecursionEliminationInitVal == 0 && 285d64152a70842b2f4186aa912938e69ca09c1434cChris Lattner !getCommonReturnValue(Ret, CI)) 2867152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return false; 2877152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner 2887152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // OK! We can transform this tail call. If this is the first one found, 2897152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // create the new entry block, allowing us to branch back to the old entry. 2907152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner if (OldEntry == 0) { 2917152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner OldEntry = &F->getEntryBlock(); 2927152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner std::string OldName = OldEntry->getName(); OldEntry->setName("tailrecurse"); 293c24a076c6a22a932e4fc2b745fd748fe7ee3cb15Chris Lattner BasicBlock *NewEntry = new BasicBlock(OldName, F, OldEntry); 2947152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner new BranchInst(OldEntry, NewEntry); 295fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 2967152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Now that we have created a new block, which jumps to the entry 2977152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // block, insert a PHI node for each argument of the function. 2987152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // For now, we initialize each PHI to only have the real arguments 2997152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // which are passed in. 3007152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner Instruction *InsertPos = OldEntry->begin(); 301e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I) { 3027152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner PHINode *PN = new PHINode(I->getType(), I->getName()+".tr", InsertPos); 3037152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner I->replaceAllUsesWith(PN); // Everyone use the PHI node now! 3047152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner PN->addIncoming(I, NewEntry); 3057152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner ArgumentPHIs.push_back(PN); 3067152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner } 3077152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner } 308fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3097152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Ok, now that we know we have a pseudo-entry block WITH all of the 3107152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // required PHI nodes, add entries into the PHI node for the actual 3117152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // parameters passed into the tail-recursive call. 3127152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner for (unsigned i = 0, e = CI->getNumOperands()-1; i != e; ++i) 3137152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner ArgumentPHIs[i]->addIncoming(CI->getOperand(i+1), BB); 314fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 315543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // If we are introducing an accumulator variable to eliminate the recursion, 316543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // do so now. Note that we _know_ that no subsequent tail recursion 317543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // eliminations will happen on this function because of the way the 318543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // accumulator recursion predicate is set up. 319543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // 320543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (AccumulatorRecursionEliminationInitVal) { 321543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner Instruction *AccRecInstr = AccumulatorRecursionInstr; 322543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Start by inserting a new PHI node for the accumulator. 323543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner PHINode *AccPN = new PHINode(AccRecInstr->getType(), "accumulator.tr", 324543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner OldEntry->begin()); 325543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 326543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Loop over all of the predecessors of the tail recursion block. For the 327543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // real entry into the function we seed the PHI with the initial value, 328543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // computed earlier. For any other existing branches to this block (due to 329543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // other tail recursions eliminated) the accumulator is not modified. 330543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Because we haven't added the branch in the current block to OldEntry yet, 331543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // it will not show up as a predecessor. 332543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner for (pred_iterator PI = pred_begin(OldEntry), PE = pred_end(OldEntry); 333543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner PI != PE; ++PI) { 334543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (*PI == &F->getEntryBlock()) 335543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner AccPN->addIncoming(AccumulatorRecursionEliminationInitVal, *PI); 336543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner else 337543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner AccPN->addIncoming(AccPN, *PI); 338543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } 339543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 340543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Add an incoming argument for the current block, which is computed by our 341543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // associative accumulator instruction. 342543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner AccPN->addIncoming(AccRecInstr, BB); 343543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 344543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Next, rewrite the accumulator recursion instruction so that it does not 345543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // use the result of the call anymore, instead, use the PHI node we just 346543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // inserted. 347543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN); 348543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 349543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // Finally, rewrite any return instructions in the program to return the PHI 350543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // node instead of the "initval" that they do currently. This loop will 351543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner // actually rewrite the return value we are destroying, but that's ok. 352543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) 353543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator())) 354543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner RI->setOperand(0, AccPN); 355543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner ++NumAccumAdded; 356543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner } 357543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner 3587152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // Now that all of the PHI nodes are in place, remove the call and 3597152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner // ret instructions, replacing them with an unconditional branch. 3607152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner new BranchInst(OldEntry, Ret); 3617152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner BB->getInstList().erase(Ret); // Remove return. 3627152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner BB->getInstList().erase(CI); // Remove call. 363543d622ef7505910c1cdc09ada0ab797c3437590Chris Lattner ++NumEliminated; 3647152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner return true; 3657152da38ef2c1f9f8ee407dc7740dfd43cbc41a6Chris Lattner} 366