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