lib/Transforms/Scalar/TailRecursionElimination.cpp

   1 //===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements tail recursion elimination.
  11 //
  12 // Caveats: The algorithm implemented is trivially simple.  There are several
  13 // improvements that could be made:
  14 //
  15 //  1. If the function has any alloca instructions, these instructions will not
  16 //     remain in the entry block of the function.  Doing this requires analysis
  17 //     to prove that the alloca is not reachable by the recursively invoked
  18 //     function call.
  19 //  2. Tail recursion is only performed if the call immediately preceeds the
  20 //     return instruction.  Would it be useful to generalize this somehow?
  21 //  3. TRE is only performed if the function returns void or if the return
  22 //     returns the result returned by the call.  It is possible, but unlikely,
  23 //     that the return returns something else (like constant 0), and can still
  24 //     be TRE'd.  It can be TRE'd if ALL OTHER return instructions in the
  25 //     function return the exact same value.
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "llvm/Transforms/Scalar.h"
  30 #include "llvm/DerivedTypes.h"
  31 #include "llvm/Function.h"
  32 #include "llvm/Instructions.h"
  33 #include "llvm/Pass.h"
  34 #include "Support/Statistic.h"
  35
  36 namespace llvm {
  37
  38 namespace {
  39   Statistic<> NumEliminated("tailcallelim", "Number of tail calls removed");
  40
  41   struct TailCallElim : public FunctionPass {
  42     virtual bool runOnFunction(Function &F);
  43   };
  44   RegisterOpt<TailCallElim> X("tailcallelim", "Tail Call Elimination");
  45 }
  46
  47 // Public interface to the TailCallElimination pass
  48 FunctionPass *createTailCallEliminationPass() { return new TailCallElim(); }
  49
  50
  51 bool TailCallElim::runOnFunction(Function &F) {
  52   // If this function is a varargs function, we won't be able to PHI the args
  53   // right, so don't even try to convert it...
  54   if (F.getFunctionType()->isVarArg()) return false;
  55
  56   BasicBlock *OldEntry = 0;
  57   std::vector<PHINode*> ArgumentPHIs;
  58   bool MadeChange = false;
  59
  60   // Loop over the function, looking for any returning blocks...
  61   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
  62     if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator()))
  63       if (Ret != BB->begin())  // Make sure there is something before the ret...
  64         if (CallInst *CI = dyn_cast<CallInst>(Ret->getPrev()))
  65           // Make sure the tail call is to the current function, and that the
  66           // return either returns void or returns the value computed by the
  67           // call.
  68           if (CI->getCalledFunction() == &F &&
  69               (Ret->getNumOperands() == 0 || Ret->getReturnValue() == CI)) {
  70             // Ohh, it looks like we found a tail call, is this the first?
  71             if (!OldEntry) {
  72               // Ok, so this is the first tail call we have found in this
  73               // function.  Insert a new entry block into the function, allowing
  74               // us to branch back to the old entry block.
  75               OldEntry = &F.getEntryBlock();
  76               BasicBlock *NewEntry = new BasicBlock("tailrecurse", OldEntry);
  77               NewEntry->getInstList().push_back(new BranchInst(OldEntry));
  78
  79               // Now that we have created a new block, which jumps to the entry
  80               // block, insert a PHI node for each argument of the function.
  81               // For now, we initialize each PHI to only have the real arguments
  82               // which are passed in.
  83               Instruction *InsertPos = OldEntry->begin();
  84               for (Function::aiterator I = F.abegin(), E = F.aend(); I!=E; ++I){
  85                 PHINode *PN = new PHINode(I->getType(), I->getName()+".tr",
  86                                           InsertPos);
  87                 I->replaceAllUsesWith(PN); // Everyone use the PHI node now!
  88                 PN->addIncoming(I, NewEntry);
  89                 ArgumentPHIs.push_back(PN);
  90               }
  91             }
  92
  93             // Ok, now that we know we have a pseudo-entry block WITH all of the
  94             // required PHI nodes, add entries into the PHI node for the actual
  95             // parameters passed into the tail-recursive call.
  96             for (unsigned i = 0, e = CI->getNumOperands()-1; i != e; ++i)
  97               ArgumentPHIs[i]->addIncoming(CI->getOperand(i+1), BB);
  98
  99             // Now that all of the PHI nodes are in place, remove the call and
 100             // ret instructions, replacing them with an unconditional branch.
 101             new BranchInst(OldEntry, CI);
 102             BB->getInstList().pop_back();  // Remove return.
 103             BB->getInstList().pop_back();  // Remove call.
 104             MadeChange = true;
 105             NumEliminated++;
 106           }
 107
 108   return MadeChange;
 109 }
 110
 111 } // End llvm namespace