TailRecursionElimination.cpp revision f8485c643412dbff46fe87ea2867445169a5c28e
12240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner//===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 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. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 92240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 102240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// This file implements tail recursion elimination. 112240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 122240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// Caveats: The algorithm implemented is trivially simple. There are several 132240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// improvements that could be made: 142240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 152240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 1. If the function has any alloca instructions, these instructions will not 162240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// remain in the entry block of the function. Doing this requires analysis 172240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// to prove that the alloca is not reachable by the recursively invoked 182240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// function call. 192240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 2. Tail recursion is only performed if the call immediately preceeds the 202240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// return instruction. Would it be useful to generalize this somehow? 212240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 3. TRE is only performed if the function returns void or if the return 222240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// returns the result returned by the call. It is possible, but unlikely, 232240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// that the return returns something else (like constant 0), and can still 242240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// be TRE'd. It can be TRE'd if ALL OTHER return instructions in the 252240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// function return the exact same value. 262240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner// 272240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner//===----------------------------------------------------------------------===// 282240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 293fc6ef1bb96d9a3194cef667a2d3cbc94e3fb189Chris Lattner#include "llvm/Transforms/Scalar.h" 302240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/DerivedTypes.h" 312240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/Function.h" 322240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/Instructions.h" 332240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "llvm/Pass.h" 342240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner#include "Support/Statistic.h" 352240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 36f8485c643412dbff46fe87ea2867445169a5c28eChris Lattnerusing namespace llvm; 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 382240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattnernamespace { 392240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner Statistic<> NumEliminated("tailcallelim", "Number of tail calls removed"); 402240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 412240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner struct TailCallElim : public FunctionPass { 422240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner virtual bool runOnFunction(Function &F); 432240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner }; 442240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner RegisterOpt<TailCallElim> X("tailcallelim", "Tail Call Elimination"); 452240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner} 462240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 47d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the TailCallElimination pass 48f8485c643412dbff46fe87ea2867445169a5c28eChris LattnerFunctionPass *llvm::createTailCallEliminationPass() { 49f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner return new TailCallElim(); 50f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner} 513fc6ef1bb96d9a3194cef667a2d3cbc94e3fb189Chris Lattner 522240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 532240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattnerbool TailCallElim::runOnFunction(Function &F) { 542240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // If this function is a varargs function, we won't be able to PHI the args 552240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // right, so don't even try to convert it... 562240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (F.getFunctionType()->isVarArg()) return false; 572240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 582240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner BasicBlock *OldEntry = 0; 592240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner std::vector<PHINode*> ArgumentPHIs; 602240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner bool MadeChange = false; 612240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 622240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Loop over the function, looking for any returning blocks... 632240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 642240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) 65d452ebd0bfcba6ba017390c392b81c080e362f28Chris Lattner if (Ret != BB->begin()) // Make sure there is something before the ret... 662240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (CallInst *CI = dyn_cast<CallInst>(Ret->getPrev())) 672240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Make sure the tail call is to the current function, and that the 682240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // return either returns void or returns the value computed by the 692240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // call. 702240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (CI->getCalledFunction() == &F && 712240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner (Ret->getNumOperands() == 0 || Ret->getReturnValue() == CI)) { 722240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Ohh, it looks like we found a tail call, is this the first? 732240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner if (!OldEntry) { 742240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Ok, so this is the first tail call we have found in this 752240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // function. Insert a new entry block into the function, allowing 762240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // us to branch back to the old entry block. 7702a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner OldEntry = &F.getEntryBlock(); 782240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner BasicBlock *NewEntry = new BasicBlock("tailrecurse", OldEntry); 79f8485c643412dbff46fe87ea2867445169a5c28eChris Lattner new BranchInst(OldEntry, 0, 0, NewEntry); 802240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 812240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Now that we have created a new block, which jumps to the entry 822240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // block, insert a PHI node for each argument of the function. 832240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // For now, we initialize each PHI to only have the real arguments 842240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // which are passed in. 852240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner Instruction *InsertPos = OldEntry->begin(); 862240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner for (Function::aiterator I = F.abegin(), E = F.aend(); I!=E; ++I){ 872240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner PHINode *PN = new PHINode(I->getType(), I->getName()+".tr", 882240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner InsertPos); 89d452ebd0bfcba6ba017390c392b81c080e362f28Chris Lattner I->replaceAllUsesWith(PN); // Everyone use the PHI node now! 902240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner PN->addIncoming(I, NewEntry); 912240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner ArgumentPHIs.push_back(PN); 922240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner } 932240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner } 942240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 952240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Ok, now that we know we have a pseudo-entry block WITH all of the 962240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // required PHI nodes, add entries into the PHI node for the actual 972240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // parameters passed into the tail-recursive call. 982240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner for (unsigned i = 0, e = CI->getNumOperands()-1; i != e; ++i) 992240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner ArgumentPHIs[i]->addIncoming(CI->getOperand(i+1), BB); 1002240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 1012240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // Now that all of the PHI nodes are in place, remove the call and 1022240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner // ret instructions, replacing them with an unconditional branch. 1032240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner new BranchInst(OldEntry, CI); 1042240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner BB->getInstList().pop_back(); // Remove return. 1052240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner BB->getInstList().pop_back(); // Remove call. 1062240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner MadeChange = true; 1072240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner NumEliminated++; 1082240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner } 1092240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner 1102240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner return MadeChange; 1112240d2b3f7b9f5835868c83ce78d125d1b65212bChris Lattner} 112