LLVM API Documentation
00001 //===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file transforms calls of the current function (self recursion) followed 00011 // by a return instruction with a branch to the entry of the function, creating 00012 // a loop. This pass also implements the following extensions to the basic 00013 // algorithm: 00014 // 00015 // 1. Trivial instructions between the call and return do not prevent the 00016 // transformation from taking place, though currently the analysis cannot 00017 // support moving any really useful instructions (only dead ones). 00018 // 2. This pass transforms functions that are prevented from being tail 00019 // recursive by an associative expression to use an accumulator variable, 00020 // thus compiling the typical naive factorial or 'fib' implementation into 00021 // efficient code. 00022 // 3. TRE is performed if the function returns void, if the return 00023 // returns the result returned by the call, or if the function returns a 00024 // run-time constant on all exits from the function. It is possible, though 00025 // unlikely, that the return returns something else (like constant 0), and 00026 // can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in 00027 // the function return the exact same value. 00028 // 4. If it can prove that callees do not access theier caller stack frame, 00029 // they are marked as eligible for tail call elimination (by the code 00030 // generator). 00031 // 00032 // There are several improvements that could be made: 00033 // 00034 // 1. If the function has any alloca instructions, these instructions will be 00035 // moved out of the entry block of the function, causing them to be 00036 // evaluated each time through the tail recursion. Safely keeping allocas 00037 // in the entry block requires analysis to proves that the tail-called 00038 // function does not read or write the stack object. 00039 // 2. Tail recursion is only performed if the call immediately preceeds the 00040 // return instruction. It's possible that there could be a jump between 00041 // the call and the return. 00042 // 3. There can be intervening operations between the call and the return that 00043 // prevent the TRE from occurring. For example, there could be GEP's and 00044 // stores to memory that will not be read or written by the call. This 00045 // requires some substantial analysis (such as with DSA) to prove safe to 00046 // move ahead of the call, but doing so could allow many more TREs to be 00047 // performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark. 00048 // 4. The algorithm we use to detect if callees access their caller stack 00049 // frames is very primitive. 00050 // 00051 //===----------------------------------------------------------------------===// 00052 00053 #define DEBUG_TYPE "tailcallelim" 00054 #include "llvm/Transforms/Scalar.h" 00055 #include "llvm/Transforms/Utils/Local.h" 00056 #include "llvm/Constants.h" 00057 #include "llvm/DerivedTypes.h" 00058 #include "llvm/Function.h" 00059 #include "llvm/Instructions.h" 00060 #include "llvm/Pass.h" 00061 #include "llvm/Support/CFG.h" 00062 #include "llvm/ADT/Statistic.h" 00063 #include "llvm/Support/Compiler.h" 00064 using namespace llvm; 00065 00066 STATISTIC(NumEliminated, "Number of tail calls removed"); 00067 STATISTIC(NumAccumAdded, "Number of accumulators introduced"); 00068 00069 namespace { 00070 struct VISIBILITY_HIDDEN TailCallElim : public FunctionPass { 00071 static char ID; // Pass identification, replacement for typeid 00072 TailCallElim() : FunctionPass(&ID) {} 00073 00074 virtual bool runOnFunction(Function &F); 00075 00076 private: 00077 bool ProcessReturningBlock(ReturnInst *RI, BasicBlock *&OldEntry, 00078 bool &TailCallsAreMarkedTail, 00079 std::vector<PHINode*> &ArgumentPHIs, 00080 bool CannotTailCallElimCallsMarkedTail); 00081 bool CanMoveAboveCall(Instruction *I, CallInst *CI); 00082 Value *CanTransformAccumulatorRecursion(Instruction *I, CallInst *CI); 00083 }; 00084 } 00085 00086 char TailCallElim::ID = 0; 00087 static RegisterPass<TailCallElim> X("tailcallelim", "Tail Call Elimination"); 00088 00089 // Public interface to the TailCallElimination pass 00090 FunctionPass *llvm::createTailCallEliminationPass() { 00091 return new TailCallElim(); 00092 } 00093 00094 00095 /// AllocaMightEscapeToCalls - Return true if this alloca may be accessed by 00096 /// callees of this function. We only do very simple analysis right now, this 00097 /// could be expanded in the future to use mod/ref information for particular 00098 /// call sites if desired. 00099 static bool AllocaMightEscapeToCalls(AllocaInst *AI) { 00100 // FIXME: do simple 'address taken' analysis. 00101 return true; 00102 } 00103 00104 /// FunctionContainsAllocas - Scan the specified basic block for alloca 00105 /// instructions. If it contains any that might be accessed by calls, return 00106 /// true. 00107 static bool CheckForEscapingAllocas(BasicBlock *BB, 00108 bool &CannotTCETailMarkedCall) { 00109 bool RetVal = false; 00110 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00111 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) { 00112 RetVal |= AllocaMightEscapeToCalls(AI); 00113 00114 // If this alloca is in the body of the function, or if it is a variable 00115 // sized allocation, we cannot tail call eliminate calls marked 'tail' 00116 // with this mechanism. 00117 if (BB != &BB->getParent()->getEntryBlock() || 00118 !isa<ConstantInt>(AI->getArraySize())) 00119 CannotTCETailMarkedCall = true; 00120 } 00121 return RetVal; 00122 } 00123 00124 bool TailCallElim::runOnFunction(Function &F) { 00125 // If this function is a varargs function, we won't be able to PHI the args 00126 // right, so don't even try to convert it... 00127 if (F.getFunctionType()->isVarArg()) return false; 00128 00129 BasicBlock *OldEntry = 0; 00130 bool TailCallsAreMarkedTail = false; 00131 std::vector<PHINode*> ArgumentPHIs; 00132 bool MadeChange = false; 00133 00134 bool FunctionContainsEscapingAllocas = false; 00135 00136 // CannotTCETailMarkedCall - If true, we cannot perform TCE on tail calls 00137 // marked with the 'tail' attribute, because doing so would cause the stack 00138 // size to increase (real TCE would deallocate variable sized allocas, TCE 00139 // doesn't). 00140 bool CannotTCETailMarkedCall = false; 00141 00142 // Loop over the function, looking for any returning blocks, and keeping track 00143 // of whether this function has any non-trivially used allocas. 00144 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 00145 if (FunctionContainsEscapingAllocas && CannotTCETailMarkedCall) 00146 break; 00147 00148 FunctionContainsEscapingAllocas |= 00149 CheckForEscapingAllocas(BB, CannotTCETailMarkedCall); 00150 } 00151 00152 /// FIXME: The code generator produces really bad code when an 'escaping 00153 /// alloca' is changed from being a static alloca to being a dynamic alloca. 00154 /// Until this is resolved, disable this transformation if that would ever 00155 /// happen. This bug is PR962. 00156 if (FunctionContainsEscapingAllocas) 00157 return false; 00158 00159 00160 // Second pass, change any tail calls to loops. 00161 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 00162 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) 00163 MadeChange |= ProcessReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, 00164 ArgumentPHIs,CannotTCETailMarkedCall); 00165 00166 // If we eliminated any tail recursions, it's possible that we inserted some 00167 // silly PHI nodes which just merge an initial value (the incoming operand) 00168 // with themselves. Check to see if we did and clean up our mess if so. This 00169 // occurs when a function passes an argument straight through to its tail 00170 // call. 00171 if (!ArgumentPHIs.empty()) { 00172 for (unsigned i = 0, e = ArgumentPHIs.size(); i != e; ++i) { 00173 PHINode *PN = ArgumentPHIs[i]; 00174 00175 // If the PHI Node is a dynamic constant, replace it with the value it is. 00176 if (Value *PNV = PN->hasConstantValue()) { 00177 PN->replaceAllUsesWith(PNV); 00178 PN->eraseFromParent(); 00179 } 00180 } 00181 } 00182 00183 // Finally, if this function contains no non-escaping allocas, mark all calls 00184 // in the function as eligible for tail calls (there is no stack memory for 00185 // them to access). 00186 if (!FunctionContainsEscapingAllocas) 00187 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 00188 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00189 if (CallInst *CI = dyn_cast<CallInst>(I)) { 00190 CI->setTailCall(); 00191 MadeChange = true; 00192 } 00193 00194 return MadeChange; 00195 } 00196 00197 00198 /// CanMoveAboveCall - Return true if it is safe to move the specified 00199 /// instruction from after the call to before the call, assuming that all 00200 /// instructions between the call and this instruction are movable. 00201 /// 00202 bool TailCallElim::CanMoveAboveCall(Instruction *I, CallInst *CI) { 00203 // FIXME: We can move load/store/call/free instructions above the call if the 00204 // call does not mod/ref the memory location being processed. 00205 if (I->mayHaveSideEffects()) // This also handles volatile loads. 00206 return false; 00207 00208 if (LoadInst* L = dyn_cast<LoadInst>(I)) { 00209 // Loads may always be moved above calls without side effects. 00210 if (CI->mayHaveSideEffects()) { 00211 // Non-volatile loads may be moved above a call with side effects if it 00212 // does not write to memory and the load provably won't trap. 00213 // FIXME: Writes to memory only matter if they may alias the pointer 00214 // being loaded from. 00215 if (CI->mayWriteToMemory() || 00216 !isSafeToLoadUnconditionally(L->getPointerOperand(), L)) 00217 return false; 00218 } 00219 } 00220 00221 // Otherwise, if this is a side-effect free instruction, check to make sure 00222 // that it does not use the return value of the call. If it doesn't use the 00223 // return value of the call, it must only use things that are defined before 00224 // the call, or movable instructions between the call and the instruction 00225 // itself. 00226 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00227 if (I->getOperand(i) == CI) 00228 return false; 00229 return true; 00230 } 00231 00232 // isDynamicConstant - Return true if the specified value is the same when the 00233 // return would exit as it was when the initial iteration of the recursive 00234 // function was executed. 00235 // 00236 // We currently handle static constants and arguments that are not modified as 00237 // part of the recursion. 00238 // 00239 static bool isDynamicConstant(Value *V, CallInst *CI) { 00240 if (isa<Constant>(V)) return true; // Static constants are always dyn consts 00241 00242 // Check to see if this is an immutable argument, if so, the value 00243 // will be available to initialize the accumulator. 00244 if (Argument *Arg = dyn_cast<Argument>(V)) { 00245 // Figure out which argument number this is... 00246 unsigned ArgNo = 0; 00247 Function *F = CI->getParent()->getParent(); 00248 for (Function::arg_iterator AI = F->arg_begin(); &*AI != Arg; ++AI) 00249 ++ArgNo; 00250 00251 // If we are passing this argument into call as the corresponding 00252 // argument operand, then the argument is dynamically constant. 00253 // Otherwise, we cannot transform this function safely. 00254 if (CI->getOperand(ArgNo+1) == Arg) 00255 return true; 00256 } 00257 // Not a constant or immutable argument, we can't safely transform. 00258 return false; 00259 } 00260 00261 // getCommonReturnValue - Check to see if the function containing the specified 00262 // return instruction and tail call consistently returns the same 00263 // runtime-constant value at all exit points. If so, return the returned value. 00264 // 00265 static Value *getCommonReturnValue(ReturnInst *TheRI, CallInst *CI) { 00266 Function *F = TheRI->getParent()->getParent(); 00267 Value *ReturnedValue = 0; 00268 00269 // TODO: Handle multiple value ret instructions; 00270 if (isa<StructType>(F->getReturnType())) 00271 return 0; 00272 00273 for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) 00274 if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator())) 00275 if (RI != TheRI) { 00276 Value *RetOp = RI->getOperand(0); 00277 00278 // We can only perform this transformation if the value returned is 00279 // evaluatable at the start of the initial invocation of the function, 00280 // instead of at the end of the evaluation. 00281 // 00282 if (!isDynamicConstant(RetOp, CI)) 00283 return 0; 00284 00285 if (ReturnedValue && RetOp != ReturnedValue) 00286 return 0; // Cannot transform if differing values are returned. 00287 ReturnedValue = RetOp; 00288 } 00289 return ReturnedValue; 00290 } 00291 00292 /// CanTransformAccumulatorRecursion - If the specified instruction can be 00293 /// transformed using accumulator recursion elimination, return the constant 00294 /// which is the start of the accumulator value. Otherwise return null. 00295 /// 00296 Value *TailCallElim::CanTransformAccumulatorRecursion(Instruction *I, 00297 CallInst *CI) { 00298 if (!I->isAssociative()) return 0; 00299 assert(I->getNumOperands() == 2 && 00300 "Associative operations should have 2 args!"); 00301 00302 // Exactly one operand should be the result of the call instruction... 00303 if ((I->getOperand(0) == CI && I->getOperand(1) == CI) || 00304 (I->getOperand(0) != CI && I->getOperand(1) != CI)) 00305 return 0; 00306 00307 // The only user of this instruction we allow is a single return instruction. 00308 if (!I->hasOneUse() || !isa<ReturnInst>(I->use_back())) 00309 return 0; 00310 00311 // Ok, now we have to check all of the other return instructions in this 00312 // function. If they return non-constants or differing values, then we cannot 00313 // transform the function safely. 00314 return getCommonReturnValue(cast<ReturnInst>(I->use_back()), CI); 00315 } 00316 00317 bool TailCallElim::ProcessReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, 00318 bool &TailCallsAreMarkedTail, 00319 std::vector<PHINode*> &ArgumentPHIs, 00320 bool CannotTailCallElimCallsMarkedTail) { 00321 BasicBlock *BB = Ret->getParent(); 00322 Function *F = BB->getParent(); 00323 00324 if (&BB->front() == Ret) // Make sure there is something before the ret... 00325 return false; 00326 00327 // If the return is in the entry block, then making this transformation would 00328 // turn infinite recursion into an infinite loop. This transformation is ok 00329 // in theory, but breaks some code like: 00330 // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call 00331 // disable this xform in this case, because the code generator will lower the 00332 // call to fabs into inline code. 00333 if (BB == &F->getEntryBlock()) 00334 return false; 00335 00336 // Scan backwards from the return, checking to see if there is a tail call in 00337 // this block. If so, set CI to it. 00338 CallInst *CI; 00339 BasicBlock::iterator BBI = Ret; 00340 while (1) { 00341 CI = dyn_cast<CallInst>(BBI); 00342 if (CI && CI->getCalledFunction() == F) 00343 break; 00344 00345 if (BBI == BB->begin()) 00346 return false; // Didn't find a potential tail call. 00347 --BBI; 00348 } 00349 00350 // If this call is marked as a tail call, and if there are dynamic allocas in 00351 // the function, we cannot perform this optimization. 00352 if (CI->isTailCall() && CannotTailCallElimCallsMarkedTail) 00353 return false; 00354 00355 // If we are introducing accumulator recursion to eliminate associative 00356 // operations after the call instruction, this variable contains the initial 00357 // value for the accumulator. If this value is set, we actually perform 00358 // accumulator recursion elimination instead of simple tail recursion 00359 // elimination. 00360 Value *AccumulatorRecursionEliminationInitVal = 0; 00361 Instruction *AccumulatorRecursionInstr = 0; 00362 00363 // Ok, we found a potential tail call. We can currently only transform the 00364 // tail call if all of the instructions between the call and the return are 00365 // movable to above the call itself, leaving the call next to the return. 00366 // Check that this is the case now. 00367 for (BBI = CI, ++BBI; &*BBI != Ret; ++BBI) 00368 if (!CanMoveAboveCall(BBI, CI)) { 00369 // If we can't move the instruction above the call, it might be because it 00370 // is an associative operation that could be tranformed using accumulator 00371 // recursion elimination. Check to see if this is the case, and if so, 00372 // remember the initial accumulator value for later. 00373 if ((AccumulatorRecursionEliminationInitVal = 00374 CanTransformAccumulatorRecursion(BBI, CI))) { 00375 // Yes, this is accumulator recursion. Remember which instruction 00376 // accumulates. 00377 AccumulatorRecursionInstr = BBI; 00378 } else { 00379 return false; // Otherwise, we cannot eliminate the tail recursion! 00380 } 00381 } 00382 00383 // We can only transform call/return pairs that either ignore the return value 00384 // of the call and return void, ignore the value of the call and return a 00385 // constant, return the value returned by the tail call, or that are being 00386 // accumulator recursion variable eliminated. 00387 if (Ret->getNumOperands() == 1 && Ret->getReturnValue() != CI && 00388 !isa<UndefValue>(Ret->getReturnValue()) && 00389 AccumulatorRecursionEliminationInitVal == 0 && 00390 !getCommonReturnValue(Ret, CI)) 00391 return false; 00392 00393 // OK! We can transform this tail call. If this is the first one found, 00394 // create the new entry block, allowing us to branch back to the old entry. 00395 if (OldEntry == 0) { 00396 OldEntry = &F->getEntryBlock(); 00397 BasicBlock *NewEntry = BasicBlock::Create(F->getContext(), "", F, OldEntry); 00398 NewEntry->takeName(OldEntry); 00399 OldEntry->setName("tailrecurse"); 00400 BranchInst::Create(OldEntry, NewEntry); 00401 00402 // If this tail call is marked 'tail' and if there are any allocas in the 00403 // entry block, move them up to the new entry block. 00404 TailCallsAreMarkedTail = CI->isTailCall(); 00405 if (TailCallsAreMarkedTail) 00406 // Move all fixed sized allocas from OldEntry to NewEntry. 00407 for (BasicBlock::iterator OEBI = OldEntry->begin(), E = OldEntry->end(), 00408 NEBI = NewEntry->begin(); OEBI != E; ) 00409 if (AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++)) 00410 if (isa<ConstantInt>(AI->getArraySize())) 00411 AI->moveBefore(NEBI); 00412 00413 // Now that we have created a new block, which jumps to the entry 00414 // block, insert a PHI node for each argument of the function. 00415 // For now, we initialize each PHI to only have the real arguments 00416 // which are passed in. 00417 Instruction *InsertPos = OldEntry->begin(); 00418 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00419 I != E; ++I) { 00420 PHINode *PN = PHINode::Create(I->getType(), 00421 I->getName() + ".tr", InsertPos); 00422 I->replaceAllUsesWith(PN); // Everyone use the PHI node now! 00423 PN->addIncoming(I, NewEntry); 00424 ArgumentPHIs.push_back(PN); 00425 } 00426 } 00427 00428 // If this function has self recursive calls in the tail position where some 00429 // are marked tail and some are not, only transform one flavor or another. We 00430 // have to choose whether we move allocas in the entry block to the new entry 00431 // block or not, so we can't make a good choice for both. NOTE: We could do 00432 // slightly better here in the case that the function has no entry block 00433 // allocas. 00434 if (TailCallsAreMarkedTail && !CI->isTailCall()) 00435 return false; 00436 00437 // Ok, now that we know we have a pseudo-entry block WITH all of the 00438 // required PHI nodes, add entries into the PHI node for the actual 00439 // parameters passed into the tail-recursive call. 00440 for (unsigned i = 0, e = CI->getNumOperands()-1; i != e; ++i) 00441 ArgumentPHIs[i]->addIncoming(CI->getOperand(i+1), BB); 00442 00443 // If we are introducing an accumulator variable to eliminate the recursion, 00444 // do so now. Note that we _know_ that no subsequent tail recursion 00445 // eliminations will happen on this function because of the way the 00446 // accumulator recursion predicate is set up. 00447 // 00448 if (AccumulatorRecursionEliminationInitVal) { 00449 Instruction *AccRecInstr = AccumulatorRecursionInstr; 00450 // Start by inserting a new PHI node for the accumulator. 00451 PHINode *AccPN = PHINode::Create(AccRecInstr->getType(), "accumulator.tr", 00452 OldEntry->begin()); 00453 00454 // Loop over all of the predecessors of the tail recursion block. For the 00455 // real entry into the function we seed the PHI with the initial value, 00456 // computed earlier. For any other existing branches to this block (due to 00457 // other tail recursions eliminated) the accumulator is not modified. 00458 // Because we haven't added the branch in the current block to OldEntry yet, 00459 // it will not show up as a predecessor. 00460 for (pred_iterator PI = pred_begin(OldEntry), PE = pred_end(OldEntry); 00461 PI != PE; ++PI) { 00462 if (*PI == &F->getEntryBlock()) 00463 AccPN->addIncoming(AccumulatorRecursionEliminationInitVal, *PI); 00464 else 00465 AccPN->addIncoming(AccPN, *PI); 00466 } 00467 00468 // Add an incoming argument for the current block, which is computed by our 00469 // associative accumulator instruction. 00470 AccPN->addIncoming(AccRecInstr, BB); 00471 00472 // Next, rewrite the accumulator recursion instruction so that it does not 00473 // use the result of the call anymore, instead, use the PHI node we just 00474 // inserted. 00475 AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN); 00476 00477 // Finally, rewrite any return instructions in the program to return the PHI 00478 // node instead of the "initval" that they do currently. This loop will 00479 // actually rewrite the return value we are destroying, but that's ok. 00480 for (Function::iterator BBI = F->begin(), E = F->end(); BBI != E; ++BBI) 00481 if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI->getTerminator())) 00482 RI->setOperand(0, AccPN); 00483 ++NumAccumAdded; 00484 } 00485 00486 // Now that all of the PHI nodes are in place, remove the call and 00487 // ret instructions, replacing them with an unconditional branch. 00488 BranchInst::Create(OldEntry, Ret); 00489 BB->getInstList().erase(Ret); // Remove return. 00490 BB->getInstList().erase(CI); // Remove call. 00491 ++NumEliminated; 00492 return true; 00493 }