TailRecursionElimination.cpp revision 360784
1114402Sru//===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===// 2114402Sru// 3114402Sru// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4114402Sru// See https://llvm.org/LICENSE.txt for license information. 5114402Sru// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6114402Sru// 7114402Sru//===----------------------------------------------------------------------===// 8114402Sru// 9114402Sru// This file transforms calls of the current function (self recursion) followed 10114402Sru// by a return instruction with a branch to the entry of the function, creating 11114402Sru// a loop. This pass also implements the following extensions to the basic 12114402Sru// algorithm: 13114402Sru// 14114402Sru// 1. Trivial instructions between the call and return do not prevent the 15114402Sru// transformation from taking place, though currently the analysis cannot 16114402Sru// support moving any really useful instructions (only dead ones). 17114402Sru// 2. This pass transforms functions that are prevented from being tail 18114402Sru// recursive by an associative and commutative expression to use an 19114402Sru// accumulator variable, thus compiling the typical naive factorial or 20114402Sru// 'fib' implementation into efficient code. 21114402Sru// 3. TRE is performed if the function returns void, if the return 22114402Sru// returns the result returned by the call, or if the function returns a 23114402Sru// run-time constant on all exits from the function. It is possible, though 24114402Sru// unlikely, that the return returns something else (like constant 0), and 25114402Sru// can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in 26114402Sru// the function return the exact same value. 27114402Sru// 4. If it can prove that callees do not access their caller stack frame, 28114402Sru// they are marked as eligible for tail call elimination (by the code 29114402Sru// generator). 30114402Sru// 31114402Sru// There are several improvements that could be made: 32114402Sru// 33114402Sru// 1. If the function has any alloca instructions, these instructions will be 34114402Sru// moved out of the entry block of the function, causing them to be 35114402Sru// evaluated each time through the tail recursion. Safely keeping allocas 36114402Sru// in the entry block requires analysis to proves that the tail-called 37114402Sru// function does not read or write the stack object. 38114402Sru// 2. Tail recursion is only performed if the call immediately precedes the 39114402Sru// return instruction. It's possible that there could be a jump between 40114402Sru// the call and the return. 41114402Sru// 3. There can be intervening operations between the call and the return that 42114402Sru// prevent the TRE from occurring. For example, there could be GEP's and 43114402Sru// stores to memory that will not be read or written by the call. This 44114402Sru// requires some substantial analysis (such as with DSA) to prove safe to 45114402Sru// move ahead of the call, but doing so could allow many more TREs to be 46114402Sru// performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark. 47114402Sru// 4. The algorithm we use to detect if callees access their caller stack 48114402Sru// frames is very primitive. 49114402Sru// 50114402Sru//===----------------------------------------------------------------------===// 51114402Sru 52114402Sru#include "llvm/Transforms/Scalar/TailRecursionElimination.h" 53114402Sru#include "llvm/ADT/STLExtras.h" 54114402Sru#include "llvm/ADT/SmallPtrSet.h" 55114402Sru#include "llvm/ADT/Statistic.h" 56114402Sru#include "llvm/Analysis/CFG.h" 57114402Sru#include "llvm/Analysis/CaptureTracking.h" 58114402Sru#include "llvm/Analysis/DomTreeUpdater.h" 59114402Sru#include "llvm/Analysis/GlobalsModRef.h" 60114402Sru#include "llvm/Analysis/InlineCost.h" 61114402Sru#include "llvm/Analysis/InstructionSimplify.h" 62114402Sru#include "llvm/Analysis/Loads.h" 63114402Sru#include "llvm/Analysis/OptimizationRemarkEmitter.h" 64114402Sru#include "llvm/Analysis/PostDominators.h" 65114402Sru#include "llvm/Analysis/TargetTransformInfo.h" 66114402Sru#include "llvm/IR/CFG.h" 67114402Sru#include "llvm/IR/CallSite.h" 68114402Sru#include "llvm/IR/Constants.h" 69114402Sru#include "llvm/IR/DataLayout.h" 70114402Sru#include "llvm/IR/DerivedTypes.h" 71114402Sru#include "llvm/IR/DiagnosticInfo.h" 72114402Sru#include "llvm/IR/Dominators.h" 73114402Sru#include "llvm/IR/Function.h" 74114402Sru#include "llvm/IR/InstIterator.h" 75114402Sru#include "llvm/IR/Instructions.h" 76114402Sru#include "llvm/IR/IntrinsicInst.h" 77114402Sru#include "llvm/IR/Module.h" 78114402Sru#include "llvm/IR/ValueHandle.h" 79114402Sru#include "llvm/InitializePasses.h" 80114402Sru#include "llvm/Pass.h" 81114402Sru#include "llvm/Support/Debug.h" 82114402Sru#include "llvm/Support/raw_ostream.h" 83114402Sru#include "llvm/Transforms/Scalar.h" 84114402Sru#include "llvm/Transforms/Utils/BasicBlockUtils.h" 85114402Sruusing namespace llvm; 86114402Sru 87114402Sru#define DEBUG_TYPE "tailcallelim" 88114402Sru 89114402SruSTATISTIC(NumEliminated, "Number of tail calls removed"); 90114402SruSTATISTIC(NumRetDuped, "Number of return duplicated"); 91114402SruSTATISTIC(NumAccumAdded, "Number of accumulators introduced"); 92114402Sru 93114402Sru/// Scan the specified function for alloca instructions. 94114402Sru/// If it contains any dynamic allocas, returns false. 95114402Srustatic bool canTRE(Function &F) { 96114402Sru // Because of PR962, we don't TRE dynamic allocas. 97114402Sru return llvm::all_of(instructions(F), [](Instruction &I) { 98114402Sru auto *AI = dyn_cast<AllocaInst>(&I); 99114402Sru return !AI || AI->isStaticAlloca(); 100114402Sru }); 101114402Sru} 102114402Sru 103114402Srunamespace { 104114402Srustruct AllocaDerivedValueTracker { 105114402Sru // Start at a root value and walk its use-def chain to mark calls that use the 106114402Sru // value or a derived value in AllocaUsers, and places where it may escape in 107114402Sru // EscapePoints. 108114402Sru void walk(Value *Root) { 109114402Sru SmallVector<Use *, 32> Worklist; 110114402Sru SmallPtrSet<Use *, 32> Visited; 111114402Sru 112114402Sru auto AddUsesToWorklist = [&](Value *V) { 113114402Sru for (auto &U : V->uses()) { 114114402Sru if (!Visited.insert(&U).second) 115114402Sru continue; 116114402Sru Worklist.push_back(&U); 117114402Sru } 118114402Sru }; 119114402Sru 120114402Sru AddUsesToWorklist(Root); 121114402Sru 122114402Sru while (!Worklist.empty()) { 123114402Sru Use *U = Worklist.pop_back_val(); 124114402Sru Instruction *I = cast<Instruction>(U->getUser()); 125114402Sru 126114402Sru switch (I->getOpcode()) { 127114402Sru case Instruction::Call: 128114402Sru case Instruction::Invoke: { 129114402Sru CallSite CS(I); 130114402Sru // If the alloca-derived argument is passed byval it is not an escape 131114402Sru // point, or a use of an alloca. Calling with byval copies the contents 132114402Sru // of the alloca into argument registers or stack slots, which exist 133114402Sru // beyond the lifetime of the current frame. 134114402Sru if (CS.isArgOperand(U) && CS.isByValArgument(CS.getArgumentNo(U))) 135114402Sru continue; 136114402Sru bool IsNocapture = 137114402Sru CS.isDataOperand(U) && CS.doesNotCapture(CS.getDataOperandNo(U)); 138114402Sru callUsesLocalStack(CS, IsNocapture); 139114402Sru if (IsNocapture) { 140114402Sru // If the alloca-derived argument is passed in as nocapture, then it 141114402Sru // can't propagate to the call's return. That would be capturing. 142114402Sru continue; 143114402Sru } 144114402Sru break; 145114402Sru } 146114402Sru case Instruction::Load: { 147114402Sru // The result of a load is not alloca-derived (unless an alloca has 148114402Sru // otherwise escaped, but this is a local analysis). 149114402Sru continue; 150114402Sru } 151114402Sru case Instruction::Store: { 152114402Sru if (U->getOperandNo() == 0) 153114402Sru EscapePoints.insert(I); 154114402Sru continue; // Stores have no users to analyze. 155114402Sru } 156114402Sru case Instruction::BitCast: 157114402Sru case Instruction::GetElementPtr: 158114402Sru case Instruction::PHI: 159114402Sru case Instruction::Select: 160114402Sru case Instruction::AddrSpaceCast: 161114402Sru break; 162114402Sru default: 163114402Sru EscapePoints.insert(I); 164114402Sru break; 165114402Sru } 166114402Sru 167114402Sru AddUsesToWorklist(I); 168114402Sru } 169114402Sru } 170114402Sru 171114402Sru void callUsesLocalStack(CallSite CS, bool IsNocapture) { 172114402Sru // Add it to the list of alloca users. 173114402Sru AllocaUsers.insert(CS.getInstruction()); 174114402Sru 175114402Sru // If it's nocapture then it can't capture this alloca. 176114402Sru if (IsNocapture) 177114402Sru return; 178114402Sru 179114402Sru // If it can write to memory, it can leak the alloca value. 180114402Sru if (!CS.onlyReadsMemory()) 181114402Sru EscapePoints.insert(CS.getInstruction()); 182114402Sru } 183114402Sru 184114402Sru SmallPtrSet<Instruction *, 32> AllocaUsers; 185114402Sru SmallPtrSet<Instruction *, 32> EscapePoints; 186114402Sru}; 187114402Sru} 188114402Sru 189114402Srustatic bool markTails(Function &F, bool &AllCallsAreTailCalls, 190114402Sru OptimizationRemarkEmitter *ORE) { 191114402Sru if (F.callsFunctionThatReturnsTwice()) 192114402Sru return false; 193114402Sru AllCallsAreTailCalls = true; 194114402Sru 195114402Sru // The local stack holds all alloca instructions and all byval arguments. 196114402Sru AllocaDerivedValueTracker Tracker; 197114402Sru for (Argument &Arg : F.args()) { 198114402Sru if (Arg.hasByValAttr()) 199114402Sru Tracker.walk(&Arg); 200114402Sru } 201114402Sru for (auto &BB : F) { 202114402Sru for (auto &I : BB) 203114402Sru if (AllocaInst *AI = dyn_cast<AllocaInst>(&I)) 204114402Sru Tracker.walk(AI); 205114402Sru } 206114402Sru 207114402Sru bool Modified = false; 208114402Sru 209114402Sru // Track whether a block is reachable after an alloca has escaped. Blocks that 210114402Sru // contain the escaping instruction will be marked as being visited without an 211114402Sru // escaped alloca, since that is how the block began. 212114402Sru enum VisitType { 213114402Sru UNVISITED, 214114402Sru UNESCAPED, 215114402Sru ESCAPED 216114402Sru }; 217114402Sru DenseMap<BasicBlock *, VisitType> Visited; 218114402Sru 219114402Sru // We propagate the fact that an alloca has escaped from block to successor. 220114402Sru // Visit the blocks that are propagating the escapedness first. To do this, we 221114402Sru // maintain two worklists. 222114402Sru SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped; 223114402Sru 224114402Sru // We may enter a block and visit it thinking that no alloca has escaped yet, 225114402Sru // then see an escape point and go back around a loop edge and come back to 226114402Sru // the same block twice. Because of this, we defer setting tail on calls when 227114402Sru // we first encounter them in a block. Every entry in this list does not 228114402Sru // statically use an alloca via use-def chain analysis, but may find an alloca 229114402Sru // through other means if the block turns out to be reachable after an escape 230114402Sru // point. 231114402Sru SmallVector<CallInst *, 32> DeferredTails; 232114402Sru 233114402Sru BasicBlock *BB = &F.getEntryBlock(); 234114402Sru VisitType Escaped = UNESCAPED; 235114402Sru do { 236114402Sru for (auto &I : *BB) { 237114402Sru if (Tracker.EscapePoints.count(&I)) 238114402Sru Escaped = ESCAPED; 239114402Sru 240114402Sru CallInst *CI = dyn_cast<CallInst>(&I); 241114402Sru if (!CI || CI->isTailCall() || isa<DbgInfoIntrinsic>(&I)) 242114402Sru continue; 243114402Sru 244114402Sru bool IsNoTail = CI->isNoTailCall() || CI->hasOperandBundles(); 245114402Sru 246114402Sru if (!IsNoTail && CI->doesNotAccessMemory()) { 247114402Sru // A call to a readnone function whose arguments are all things computed 248114402Sru // outside this function can be marked tail. Even if you stored the 249114402Sru // alloca address into a global, a readnone function can't load the 250114402Sru // global anyhow. 251114402Sru // 252114402Sru // Note that this runs whether we know an alloca has escaped or not. If 253114402Sru // it has, then we can't trust Tracker.AllocaUsers to be accurate. 254114402Sru bool SafeToTail = true; 255114402Sru for (auto &Arg : CI->arg_operands()) { 256114402Sru if (isa<Constant>(Arg.getUser())) 257114402Sru continue; 258114402Sru if (Argument *A = dyn_cast<Argument>(Arg.getUser())) 259114402Sru if (!A->hasByValAttr()) 260114402Sru continue; 261114402Sru SafeToTail = false; 262114402Sru break; 263114402Sru } 264114402Sru if (SafeToTail) { 265114402Sru using namespace ore; 266114402Sru ORE->emit([&]() { 267114402Sru return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI) 268114402Sru << "marked as tail call candidate (readnone)"; 269114402Sru }); 270114402Sru CI->setTailCall(); 271114402Sru Modified = true; 272114402Sru continue; 273114402Sru } 274114402Sru } 275114402Sru 276114402Sru if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) { 277114402Sru DeferredTails.push_back(CI); 278114402Sru } else { 279114402Sru AllCallsAreTailCalls = false; 280114402Sru } 281114402Sru } 282114402Sru 283114402Sru for (auto *SuccBB : make_range(succ_begin(BB), succ_end(BB))) { 284114402Sru auto &State = Visited[SuccBB]; 285114402Sru if (State < Escaped) { 286114402Sru State = Escaped; 287 if (State == ESCAPED) 288 WorklistEscaped.push_back(SuccBB); 289 else 290 WorklistUnescaped.push_back(SuccBB); 291 } 292 } 293 294 if (!WorklistEscaped.empty()) { 295 BB = WorklistEscaped.pop_back_val(); 296 Escaped = ESCAPED; 297 } else { 298 BB = nullptr; 299 while (!WorklistUnescaped.empty()) { 300 auto *NextBB = WorklistUnescaped.pop_back_val(); 301 if (Visited[NextBB] == UNESCAPED) { 302 BB = NextBB; 303 Escaped = UNESCAPED; 304 break; 305 } 306 } 307 } 308 } while (BB); 309 310 for (CallInst *CI : DeferredTails) { 311 if (Visited[CI->getParent()] != ESCAPED) { 312 // If the escape point was part way through the block, calls after the 313 // escape point wouldn't have been put into DeferredTails. 314 LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n"); 315 CI->setTailCall(); 316 Modified = true; 317 } else { 318 AllCallsAreTailCalls = false; 319 } 320 } 321 322 return Modified; 323} 324 325/// Return true if it is safe to move the specified 326/// instruction from after the call to before the call, assuming that all 327/// instructions between the call and this instruction are movable. 328/// 329static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA) { 330 // FIXME: We can move load/store/call/free instructions above the call if the 331 // call does not mod/ref the memory location being processed. 332 if (I->mayHaveSideEffects()) // This also handles volatile loads. 333 return false; 334 335 if (LoadInst *L = dyn_cast<LoadInst>(I)) { 336 // Loads may always be moved above calls without side effects. 337 if (CI->mayHaveSideEffects()) { 338 // Non-volatile loads may be moved above a call with side effects if it 339 // does not write to memory and the load provably won't trap. 340 // Writes to memory only matter if they may alias the pointer 341 // being loaded from. 342 const DataLayout &DL = L->getModule()->getDataLayout(); 343 if (isModSet(AA->getModRefInfo(CI, MemoryLocation::get(L))) || 344 !isSafeToLoadUnconditionally(L->getPointerOperand(), L->getType(), 345 MaybeAlign(L->getAlignment()), DL, L)) 346 return false; 347 } 348 } 349 350 // Otherwise, if this is a side-effect free instruction, check to make sure 351 // that it does not use the return value of the call. If it doesn't use the 352 // return value of the call, it must only use things that are defined before 353 // the call, or movable instructions between the call and the instruction 354 // itself. 355 return !is_contained(I->operands(), CI); 356} 357 358/// Return true if the specified value is the same when the return would exit 359/// as it was when the initial iteration of the recursive function was executed. 360/// 361/// We currently handle static constants and arguments that are not modified as 362/// part of the recursion. 363static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) { 364 if (isa<Constant>(V)) return true; // Static constants are always dyn consts 365 366 // Check to see if this is an immutable argument, if so, the value 367 // will be available to initialize the accumulator. 368 if (Argument *Arg = dyn_cast<Argument>(V)) { 369 // Figure out which argument number this is... 370 unsigned ArgNo = 0; 371 Function *F = CI->getParent()->getParent(); 372 for (Function::arg_iterator AI = F->arg_begin(); &*AI != Arg; ++AI) 373 ++ArgNo; 374 375 // If we are passing this argument into call as the corresponding 376 // argument operand, then the argument is dynamically constant. 377 // Otherwise, we cannot transform this function safely. 378 if (CI->getArgOperand(ArgNo) == Arg) 379 return true; 380 } 381 382 // Switch cases are always constant integers. If the value is being switched 383 // on and the return is only reachable from one of its cases, it's 384 // effectively constant. 385 if (BasicBlock *UniquePred = RI->getParent()->getUniquePredecessor()) 386 if (SwitchInst *SI = dyn_cast<SwitchInst>(UniquePred->getTerminator())) 387 if (SI->getCondition() == V) 388 return SI->getDefaultDest() != RI->getParent(); 389 390 // Not a constant or immutable argument, we can't safely transform. 391 return false; 392} 393 394/// Check to see if the function containing the specified tail call consistently 395/// returns the same runtime-constant value at all exit points except for 396/// IgnoreRI. If so, return the returned value. 397static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) { 398 Function *F = CI->getParent()->getParent(); 399 Value *ReturnedValue = nullptr; 400 401 for (BasicBlock &BBI : *F) { 402 ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator()); 403 if (RI == nullptr || RI == IgnoreRI) continue; 404 405 // We can only perform this transformation if the value returned is 406 // evaluatable at the start of the initial invocation of the function, 407 // instead of at the end of the evaluation. 408 // 409 Value *RetOp = RI->getOperand(0); 410 if (!isDynamicConstant(RetOp, CI, RI)) 411 return nullptr; 412 413 if (ReturnedValue && RetOp != ReturnedValue) 414 return nullptr; // Cannot transform if differing values are returned. 415 ReturnedValue = RetOp; 416 } 417 return ReturnedValue; 418} 419 420/// If the specified instruction can be transformed using accumulator recursion 421/// elimination, return the constant which is the start of the accumulator 422/// value. Otherwise return null. 423static Value *canTransformAccumulatorRecursion(Instruction *I, CallInst *CI) { 424 if (!I->isAssociative() || !I->isCommutative()) return nullptr; 425 assert(I->getNumOperands() == 2 && 426 "Associative/commutative operations should have 2 args!"); 427 428 // Exactly one operand should be the result of the call instruction. 429 if ((I->getOperand(0) == CI && I->getOperand(1) == CI) || 430 (I->getOperand(0) != CI && I->getOperand(1) != CI)) 431 return nullptr; 432 433 // The only user of this instruction we allow is a single return instruction. 434 if (!I->hasOneUse() || !isa<ReturnInst>(I->user_back())) 435 return nullptr; 436 437 // Ok, now we have to check all of the other return instructions in this 438 // function. If they return non-constants or differing values, then we cannot 439 // transform the function safely. 440 return getCommonReturnValue(cast<ReturnInst>(I->user_back()), CI); 441} 442 443static Instruction *firstNonDbg(BasicBlock::iterator I) { 444 while (isa<DbgInfoIntrinsic>(I)) 445 ++I; 446 return &*I; 447} 448 449static CallInst *findTRECandidate(Instruction *TI, 450 bool CannotTailCallElimCallsMarkedTail, 451 const TargetTransformInfo *TTI) { 452 BasicBlock *BB = TI->getParent(); 453 Function *F = BB->getParent(); 454 455 if (&BB->front() == TI) // Make sure there is something before the terminator. 456 return nullptr; 457 458 // Scan backwards from the return, checking to see if there is a tail call in 459 // this block. If so, set CI to it. 460 CallInst *CI = nullptr; 461 BasicBlock::iterator BBI(TI); 462 while (true) { 463 CI = dyn_cast<CallInst>(BBI); 464 if (CI && CI->getCalledFunction() == F) 465 break; 466 467 if (BBI == BB->begin()) 468 return nullptr; // Didn't find a potential tail call. 469 --BBI; 470 } 471 472 // If this call is marked as a tail call, and if there are dynamic allocas in 473 // the function, we cannot perform this optimization. 474 if (CI->isTailCall() && CannotTailCallElimCallsMarkedTail) 475 return nullptr; 476 477 // As a special case, detect code like this: 478 // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call 479 // and disable this xform in this case, because the code generator will 480 // lower the call to fabs into inline code. 481 if (BB == &F->getEntryBlock() && 482 firstNonDbg(BB->front().getIterator()) == CI && 483 firstNonDbg(std::next(BB->begin())) == TI && CI->getCalledFunction() && 484 !TTI->isLoweredToCall(CI->getCalledFunction())) { 485 // A single-block function with just a call and a return. Check that 486 // the arguments match. 487 CallSite::arg_iterator I = CallSite(CI).arg_begin(), 488 E = CallSite(CI).arg_end(); 489 Function::arg_iterator FI = F->arg_begin(), 490 FE = F->arg_end(); 491 for (; I != E && FI != FE; ++I, ++FI) 492 if (*I != &*FI) break; 493 if (I == E && FI == FE) 494 return nullptr; 495 } 496 497 return CI; 498} 499 500static bool eliminateRecursiveTailCall( 501 CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, 502 bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs, 503 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) { 504 // If we are introducing accumulator recursion to eliminate operations after 505 // the call instruction that are both associative and commutative, the initial 506 // value for the accumulator is placed in this variable. If this value is set 507 // then we actually perform accumulator recursion elimination instead of 508 // simple tail recursion elimination. If the operation is an LLVM instruction 509 // (eg: "add") then it is recorded in AccumulatorRecursionInstr. If not, then 510 // we are handling the case when the return instruction returns a constant C 511 // which is different to the constant returned by other return instructions 512 // (which is recorded in AccumulatorRecursionEliminationInitVal). This is a 513 // special case of accumulator recursion, the operation being "return C". 514 Value *AccumulatorRecursionEliminationInitVal = nullptr; 515 Instruction *AccumulatorRecursionInstr = nullptr; 516 517 // Ok, we found a potential tail call. We can currently only transform the 518 // tail call if all of the instructions between the call and the return are 519 // movable to above the call itself, leaving the call next to the return. 520 // Check that this is the case now. 521 BasicBlock::iterator BBI(CI); 522 for (++BBI; &*BBI != Ret; ++BBI) { 523 if (canMoveAboveCall(&*BBI, CI, AA)) 524 continue; 525 526 // If we can't move the instruction above the call, it might be because it 527 // is an associative and commutative operation that could be transformed 528 // using accumulator recursion elimination. Check to see if this is the 529 // case, and if so, remember the initial accumulator value for later. 530 if ((AccumulatorRecursionEliminationInitVal = 531 canTransformAccumulatorRecursion(&*BBI, CI))) { 532 // Yes, this is accumulator recursion. Remember which instruction 533 // accumulates. 534 AccumulatorRecursionInstr = &*BBI; 535 } else { 536 return false; // Otherwise, we cannot eliminate the tail recursion! 537 } 538 } 539 540 // We can only transform call/return pairs that either ignore the return value 541 // of the call and return void, ignore the value of the call and return a 542 // constant, return the value returned by the tail call, or that are being 543 // accumulator recursion variable eliminated. 544 if (Ret->getNumOperands() == 1 && Ret->getReturnValue() != CI && 545 !isa<UndefValue>(Ret->getReturnValue()) && 546 AccumulatorRecursionEliminationInitVal == nullptr && 547 !getCommonReturnValue(nullptr, CI)) { 548 // One case remains that we are able to handle: the current return 549 // instruction returns a constant, and all other return instructions 550 // return a different constant. 551 if (!isDynamicConstant(Ret->getReturnValue(), CI, Ret)) 552 return false; // Current return instruction does not return a constant. 553 // Check that all other return instructions return a common constant. If 554 // so, record it in AccumulatorRecursionEliminationInitVal. 555 AccumulatorRecursionEliminationInitVal = getCommonReturnValue(Ret, CI); 556 if (!AccumulatorRecursionEliminationInitVal) 557 return false; 558 } 559 560 BasicBlock *BB = Ret->getParent(); 561 Function *F = BB->getParent(); 562 563 using namespace ore; 564 ORE->emit([&]() { 565 return OptimizationRemark(DEBUG_TYPE, "tailcall-recursion", CI) 566 << "transforming tail recursion into loop"; 567 }); 568 569 // OK! We can transform this tail call. If this is the first one found, 570 // create the new entry block, allowing us to branch back to the old entry. 571 if (!OldEntry) { 572 OldEntry = &F->getEntryBlock(); 573 BasicBlock *NewEntry = BasicBlock::Create(F->getContext(), "", F, OldEntry); 574 NewEntry->takeName(OldEntry); 575 OldEntry->setName("tailrecurse"); 576 BranchInst *BI = BranchInst::Create(OldEntry, NewEntry); 577 BI->setDebugLoc(CI->getDebugLoc()); 578 579 // If this tail call is marked 'tail' and if there are any allocas in the 580 // entry block, move them up to the new entry block. 581 TailCallsAreMarkedTail = CI->isTailCall(); 582 if (TailCallsAreMarkedTail) 583 // Move all fixed sized allocas from OldEntry to NewEntry. 584 for (BasicBlock::iterator OEBI = OldEntry->begin(), E = OldEntry->end(), 585 NEBI = NewEntry->begin(); OEBI != E; ) 586 if (AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++)) 587 if (isa<ConstantInt>(AI->getArraySize())) 588 AI->moveBefore(&*NEBI); 589 590 // Now that we have created a new block, which jumps to the entry 591 // block, insert a PHI node for each argument of the function. 592 // For now, we initialize each PHI to only have the real arguments 593 // which are passed in. 594 Instruction *InsertPos = &OldEntry->front(); 595 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 596 I != E; ++I) { 597 PHINode *PN = PHINode::Create(I->getType(), 2, 598 I->getName() + ".tr", InsertPos); 599 I->replaceAllUsesWith(PN); // Everyone use the PHI node now! 600 PN->addIncoming(&*I, NewEntry); 601 ArgumentPHIs.push_back(PN); 602 } 603 // The entry block was changed from OldEntry to NewEntry. 604 // The forward DominatorTree needs to be recalculated when the EntryBB is 605 // changed. In this corner-case we recalculate the entire tree. 606 DTU.recalculate(*NewEntry->getParent()); 607 } 608 609 // If this function has self recursive calls in the tail position where some 610 // are marked tail and some are not, only transform one flavor or another. We 611 // have to choose whether we move allocas in the entry block to the new entry 612 // block or not, so we can't make a good choice for both. NOTE: We could do 613 // slightly better here in the case that the function has no entry block 614 // allocas. 615 if (TailCallsAreMarkedTail && !CI->isTailCall()) 616 return false; 617 618 // Ok, now that we know we have a pseudo-entry block WITH all of the 619 // required PHI nodes, add entries into the PHI node for the actual 620 // parameters passed into the tail-recursive call. 621 for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) 622 ArgumentPHIs[i]->addIncoming(CI->getArgOperand(i), BB); 623 624 // If we are introducing an accumulator variable to eliminate the recursion, 625 // do so now. Note that we _know_ that no subsequent tail recursion 626 // eliminations will happen on this function because of the way the 627 // accumulator recursion predicate is set up. 628 // 629 if (AccumulatorRecursionEliminationInitVal) { 630 Instruction *AccRecInstr = AccumulatorRecursionInstr; 631 // Start by inserting a new PHI node for the accumulator. 632 pred_iterator PB = pred_begin(OldEntry), PE = pred_end(OldEntry); 633 PHINode *AccPN = PHINode::Create( 634 AccumulatorRecursionEliminationInitVal->getType(), 635 std::distance(PB, PE) + 1, "accumulator.tr", &OldEntry->front()); 636 637 // Loop over all of the predecessors of the tail recursion block. For the 638 // real entry into the function we seed the PHI with the initial value, 639 // computed earlier. For any other existing branches to this block (due to 640 // other tail recursions eliminated) the accumulator is not modified. 641 // Because we haven't added the branch in the current block to OldEntry yet, 642 // it will not show up as a predecessor. 643 for (pred_iterator PI = PB; PI != PE; ++PI) { 644 BasicBlock *P = *PI; 645 if (P == &F->getEntryBlock()) 646 AccPN->addIncoming(AccumulatorRecursionEliminationInitVal, P); 647 else 648 AccPN->addIncoming(AccPN, P); 649 } 650 651 if (AccRecInstr) { 652 // Add an incoming argument for the current block, which is computed by 653 // our associative and commutative accumulator instruction. 654 AccPN->addIncoming(AccRecInstr, BB); 655 656 // Next, rewrite the accumulator recursion instruction so that it does not 657 // use the result of the call anymore, instead, use the PHI node we just 658 // inserted. 659 AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN); 660 } else { 661 // Add an incoming argument for the current block, which is just the 662 // constant returned by the current return instruction. 663 AccPN->addIncoming(Ret->getReturnValue(), BB); 664 } 665 666 // Finally, rewrite any return instructions in the program to return the PHI 667 // node instead of the "initval" that they do currently. This loop will 668 // actually rewrite the return value we are destroying, but that's ok. 669 for (BasicBlock &BBI : *F) 670 if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator())) 671 RI->setOperand(0, AccPN); 672 ++NumAccumAdded; 673 } 674 675 // Now that all of the PHI nodes are in place, remove the call and 676 // ret instructions, replacing them with an unconditional branch. 677 BranchInst *NewBI = BranchInst::Create(OldEntry, Ret); 678 NewBI->setDebugLoc(CI->getDebugLoc()); 679 680 BB->getInstList().erase(Ret); // Remove return. 681 BB->getInstList().erase(CI); // Remove call. 682 DTU.applyUpdates({{DominatorTree::Insert, BB, OldEntry}}); 683 ++NumEliminated; 684 return true; 685} 686 687static bool foldReturnAndProcessPred( 688 BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry, 689 bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs, 690 bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, 691 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) { 692 bool Change = false; 693 694 // Make sure this block is a trivial return block. 695 assert(BB->getFirstNonPHIOrDbg() == Ret && 696 "Trying to fold non-trivial return block"); 697 698 // If the return block contains nothing but the return and PHI's, 699 // there might be an opportunity to duplicate the return in its 700 // predecessors and perform TRE there. Look for predecessors that end 701 // in unconditional branch and recursive call(s). 702 SmallVector<BranchInst*, 8> UncondBranchPreds; 703 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 704 BasicBlock *Pred = *PI; 705 Instruction *PTI = Pred->getTerminator(); 706 if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 707 if (BI->isUnconditional()) 708 UncondBranchPreds.push_back(BI); 709 } 710 711 while (!UncondBranchPreds.empty()) { 712 BranchInst *BI = UncondBranchPreds.pop_back_val(); 713 BasicBlock *Pred = BI->getParent(); 714 if (CallInst *CI = findTRECandidate(BI, CannotTailCallElimCallsMarkedTail, TTI)){ 715 LLVM_DEBUG(dbgs() << "FOLDING: " << *BB 716 << "INTO UNCOND BRANCH PRED: " << *Pred); 717 ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred, &DTU); 718 719 // Cleanup: if all predecessors of BB have been eliminated by 720 // FoldReturnIntoUncondBranch, delete it. It is important to empty it, 721 // because the ret instruction in there is still using a value which 722 // eliminateRecursiveTailCall will attempt to remove. 723 if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB)) 724 DTU.deleteBB(BB); 725 726 eliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail, 727 ArgumentPHIs, AA, ORE, DTU); 728 ++NumRetDuped; 729 Change = true; 730 } 731 } 732 733 return Change; 734} 735 736static bool processReturningBlock( 737 ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, 738 SmallVectorImpl<PHINode *> &ArgumentPHIs, 739 bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, 740 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) { 741 CallInst *CI = findTRECandidate(Ret, CannotTailCallElimCallsMarkedTail, TTI); 742 if (!CI) 743 return false; 744 745 return eliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail, 746 ArgumentPHIs, AA, ORE, DTU); 747} 748 749static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI, 750 AliasAnalysis *AA, 751 OptimizationRemarkEmitter *ORE, 752 DomTreeUpdater &DTU) { 753 if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true") 754 return false; 755 756 bool MadeChange = false; 757 bool AllCallsAreTailCalls = false; 758 MadeChange |= markTails(F, AllCallsAreTailCalls, ORE); 759 if (!AllCallsAreTailCalls) 760 return MadeChange; 761 762 // If this function is a varargs function, we won't be able to PHI the args 763 // right, so don't even try to convert it... 764 if (F.getFunctionType()->isVarArg()) 765 return false; 766 767 BasicBlock *OldEntry = nullptr; 768 bool TailCallsAreMarkedTail = false; 769 SmallVector<PHINode*, 8> ArgumentPHIs; 770 771 // If false, we cannot perform TRE on tail calls marked with the 'tail' 772 // attribute, because doing so would cause the stack size to increase (real 773 // TRE would deallocate variable sized allocas, TRE doesn't). 774 bool CanTRETailMarkedCall = canTRE(F); 775 776 // Change any tail recursive calls to loops. 777 // 778 // FIXME: The code generator produces really bad code when an 'escaping 779 // alloca' is changed from being a static alloca to being a dynamic alloca. 780 // Until this is resolved, disable this transformation if that would ever 781 // happen. This bug is PR962. 782 for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) { 783 BasicBlock *BB = &*BBI++; // foldReturnAndProcessPred may delete BB. 784 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) { 785 bool Change = processReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail, 786 ArgumentPHIs, !CanTRETailMarkedCall, 787 TTI, AA, ORE, DTU); 788 if (!Change && BB->getFirstNonPHIOrDbg() == Ret) 789 Change = foldReturnAndProcessPred( 790 BB, Ret, OldEntry, TailCallsAreMarkedTail, ArgumentPHIs, 791 !CanTRETailMarkedCall, TTI, AA, ORE, DTU); 792 MadeChange |= Change; 793 } 794 } 795 796 // If we eliminated any tail recursions, it's possible that we inserted some 797 // silly PHI nodes which just merge an initial value (the incoming operand) 798 // with themselves. Check to see if we did and clean up our mess if so. This 799 // occurs when a function passes an argument straight through to its tail 800 // call. 801 for (PHINode *PN : ArgumentPHIs) { 802 // If the PHI Node is a dynamic constant, replace it with the value it is. 803 if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) { 804 PN->replaceAllUsesWith(PNV); 805 PN->eraseFromParent(); 806 } 807 } 808 809 return MadeChange; 810} 811 812namespace { 813struct TailCallElim : public FunctionPass { 814 static char ID; // Pass identification, replacement for typeid 815 TailCallElim() : FunctionPass(ID) { 816 initializeTailCallElimPass(*PassRegistry::getPassRegistry()); 817 } 818 819 void getAnalysisUsage(AnalysisUsage &AU) const override { 820 AU.addRequired<TargetTransformInfoWrapperPass>(); 821 AU.addRequired<AAResultsWrapperPass>(); 822 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 823 AU.addPreserved<GlobalsAAWrapperPass>(); 824 AU.addPreserved<DominatorTreeWrapperPass>(); 825 AU.addPreserved<PostDominatorTreeWrapperPass>(); 826 } 827 828 bool runOnFunction(Function &F) override { 829 if (skipFunction(F)) 830 return false; 831 832 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 833 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; 834 auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>(); 835 auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr; 836 // There is no noticable performance difference here between Lazy and Eager 837 // UpdateStrategy based on some test results. It is feasible to switch the 838 // UpdateStrategy to Lazy if we find it profitable later. 839 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); 840 841 return eliminateTailRecursion( 842 F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F), 843 &getAnalysis<AAResultsWrapperPass>().getAAResults(), 844 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU); 845 } 846}; 847} 848 849char TailCallElim::ID = 0; 850INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination", 851 false, false) 852INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 853INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 854INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination", 855 false, false) 856 857// Public interface to the TailCallElimination pass 858FunctionPass *llvm::createTailCallEliminationPass() { 859 return new TailCallElim(); 860} 861 862PreservedAnalyses TailCallElimPass::run(Function &F, 863 FunctionAnalysisManager &AM) { 864 865 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F); 866 AliasAnalysis &AA = AM.getResult<AAManager>(F); 867 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 868 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); 869 auto *PDT = AM.getCachedResult<PostDominatorTreeAnalysis>(F); 870 // There is no noticable performance difference here between Lazy and Eager 871 // UpdateStrategy based on some test results. It is feasible to switch the 872 // UpdateStrategy to Lazy if we find it profitable later. 873 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); 874 bool Changed = eliminateTailRecursion(F, &TTI, &AA, &ORE, DTU); 875 876 if (!Changed) 877 return PreservedAnalyses::all(); 878 PreservedAnalyses PA; 879 PA.preserve<GlobalsAA>(); 880 PA.preserve<DominatorTreeAnalysis>(); 881 PA.preserve<PostDominatorTreeAnalysis>(); 882 return PA; 883} 884