LLVM  13.0.0git
TailRecursionElimination.cpp
Go to the documentation of this file.
1 //===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file transforms calls of the current function (self recursion) followed
10 // by a return instruction with a branch to the entry of the function, creating
11 // a loop. This pass also implements the following extensions to the basic
12 // algorithm:
13 //
14 // 1. Trivial instructions between the call and return do not prevent the
15 // transformation from taking place, though currently the analysis cannot
16 // support moving any really useful instructions (only dead ones).
17 // 2. This pass transforms functions that are prevented from being tail
18 // recursive by an associative and commutative expression to use an
19 // accumulator variable, thus compiling the typical naive factorial or
20 // 'fib' implementation into efficient code.
21 // 3. TRE is performed if the function returns void, if the return
22 // returns the result returned by the call, or if the function returns a
23 // run-time constant on all exits from the function. It is possible, though
24 // unlikely, that the return returns something else (like constant 0), and
25 // can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in
26 // the function return the exact same value.
27 // 4. If it can prove that callees do not access their caller stack frame,
28 // they are marked as eligible for tail call elimination (by the code
29 // generator).
30 //
31 // There are several improvements that could be made:
32 //
33 // 1. If the function has any alloca instructions, these instructions will be
34 // moved out of the entry block of the function, causing them to be
35 // evaluated each time through the tail recursion. Safely keeping allocas
36 // in the entry block requires analysis to proves that the tail-called
37 // function does not read or write the stack object.
38 // 2. Tail recursion is only performed if the call immediately precedes the
39 // return instruction. It's possible that there could be a jump between
40 // the call and the return.
41 // 3. There can be intervening operations between the call and the return that
42 // prevent the TRE from occurring. For example, there could be GEP's and
43 // stores to memory that will not be read or written by the call. This
44 // requires some substantial analysis (such as with DSA) to prove safe to
45 // move ahead of the call, but doing so could allow many more TREs to be
46 // performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark.
47 // 4. The algorithm we use to detect if callees access their caller stack
48 // frames is very primitive.
49 //
50 //===----------------------------------------------------------------------===//
51 
53 #include "llvm/ADT/STLExtras.h"
54 #include "llvm/ADT/SmallPtrSet.h"
55 #include "llvm/ADT/Statistic.h"
56 #include "llvm/Analysis/CFG.h"
62 #include "llvm/Analysis/Loads.h"
66 #include "llvm/IR/CFG.h"
67 #include "llvm/IR/Constants.h"
68 #include "llvm/IR/DataLayout.h"
69 #include "llvm/IR/DerivedTypes.h"
70 #include "llvm/IR/DiagnosticInfo.h"
71 #include "llvm/IR/Dominators.h"
72 #include "llvm/IR/Function.h"
73 #include "llvm/IR/InstIterator.h"
74 #include "llvm/IR/Instructions.h"
75 #include "llvm/IR/IntrinsicInst.h"
76 #include "llvm/IR/Module.h"
77 #include "llvm/IR/ValueHandle.h"
78 #include "llvm/InitializePasses.h"
79 #include "llvm/Pass.h"
80 #include "llvm/Support/Debug.h"
82 #include "llvm/Transforms/Scalar.h"
84 using namespace llvm;
85 
86 #define DEBUG_TYPE "tailcallelim"
87 
88 STATISTIC(NumEliminated, "Number of tail calls removed");
89 STATISTIC(NumRetDuped, "Number of return duplicated");
90 STATISTIC(NumAccumAdded, "Number of accumulators introduced");
91 
92 /// Scan the specified function for alloca instructions.
93 /// If it contains any dynamic allocas, returns false.
94 static bool canTRE(Function &F) {
95  // FIXME: The code generator produces really bad code when an 'escaping
96  // alloca' is changed from being a static alloca to being a dynamic alloca.
97  // Until this is resolved, disable this transformation if that would ever
98  // happen. This bug is PR962.
99  return llvm::all_of(instructions(F), [](Instruction &I) {
100  auto *AI = dyn_cast<AllocaInst>(&I);
101  return !AI || AI->isStaticAlloca();
102  });
103 }
104 
105 namespace {
106 struct AllocaDerivedValueTracker {
107  // Start at a root value and walk its use-def chain to mark calls that use the
108  // value or a derived value in AllocaUsers, and places where it may escape in
109  // EscapePoints.
110  void walk(Value *Root) {
111  SmallVector<Use *, 32> Worklist;
112  SmallPtrSet<Use *, 32> Visited;
113 
114  auto AddUsesToWorklist = [&](Value *V) {
115  for (auto &U : V->uses()) {
116  if (!Visited.insert(&U).second)
117  continue;
118  Worklist.push_back(&U);
119  }
120  };
121 
122  AddUsesToWorklist(Root);
123 
124  while (!Worklist.empty()) {
125  Use *U = Worklist.pop_back_val();
126  Instruction *I = cast<Instruction>(U->getUser());
127 
128  switch (I->getOpcode()) {
129  case Instruction::Call:
130  case Instruction::Invoke: {
131  auto &CB = cast<CallBase>(*I);
132  // If the alloca-derived argument is passed byval it is not an escape
133  // point, or a use of an alloca. Calling with byval copies the contents
134  // of the alloca into argument registers or stack slots, which exist
135  // beyond the lifetime of the current frame.
136  if (CB.isArgOperand(U) && CB.isByValArgument(CB.getArgOperandNo(U)))
137  continue;
138  bool IsNocapture =
139  CB.isDataOperand(U) && CB.doesNotCapture(CB.getDataOperandNo(U));
140  callUsesLocalStack(CB, IsNocapture);
141  if (IsNocapture) {
142  // If the alloca-derived argument is passed in as nocapture, then it
143  // can't propagate to the call's return. That would be capturing.
144  continue;
145  }
146  break;
147  }
148  case Instruction::Load: {
149  // The result of a load is not alloca-derived (unless an alloca has
150  // otherwise escaped, but this is a local analysis).
151  continue;
152  }
153  case Instruction::Store: {
154  if (U->getOperandNo() == 0)
155  EscapePoints.insert(I);
156  continue; // Stores have no users to analyze.
157  }
158  case Instruction::BitCast:
159  case Instruction::GetElementPtr:
160  case Instruction::PHI:
161  case Instruction::Select:
162  case Instruction::AddrSpaceCast:
163  break;
164  default:
165  EscapePoints.insert(I);
166  break;
167  }
168 
169  AddUsesToWorklist(I);
170  }
171  }
172 
173  void callUsesLocalStack(CallBase &CB, bool IsNocapture) {
174  // Add it to the list of alloca users.
175  AllocaUsers.insert(&CB);
176 
177  // If it's nocapture then it can't capture this alloca.
178  if (IsNocapture)
179  return;
180 
181  // If it can write to memory, it can leak the alloca value.
182  if (!CB.onlyReadsMemory())
183  EscapePoints.insert(&CB);
184  }
185 
186  SmallPtrSet<Instruction *, 32> AllocaUsers;
187  SmallPtrSet<Instruction *, 32> EscapePoints;
188 };
189 }
190 
191 static bool markTails(Function &F, bool &AllCallsAreTailCalls,
193  if (F.callsFunctionThatReturnsTwice())
194  return false;
195  AllCallsAreTailCalls = true;
196 
197  // The local stack holds all alloca instructions and all byval arguments.
198  AllocaDerivedValueTracker Tracker;
199  for (Argument &Arg : F.args()) {
200  if (Arg.hasByValAttr())
201  Tracker.walk(&Arg);
202  }
203  for (auto &BB : F) {
204  for (auto &I : BB)
205  if (AllocaInst *AI = dyn_cast<AllocaInst>(&I))
206  Tracker.walk(AI);
207  }
208 
209  bool Modified = false;
210 
211  // Track whether a block is reachable after an alloca has escaped. Blocks that
212  // contain the escaping instruction will be marked as being visited without an
213  // escaped alloca, since that is how the block began.
214  enum VisitType {
215  UNVISITED,
216  UNESCAPED,
217  ESCAPED
218  };
220 
221  // We propagate the fact that an alloca has escaped from block to successor.
222  // Visit the blocks that are propagating the escapedness first. To do this, we
223  // maintain two worklists.
224  SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped;
225 
226  // We may enter a block and visit it thinking that no alloca has escaped yet,
227  // then see an escape point and go back around a loop edge and come back to
228  // the same block twice. Because of this, we defer setting tail on calls when
229  // we first encounter them in a block. Every entry in this list does not
230  // statically use an alloca via use-def chain analysis, but may find an alloca
231  // through other means if the block turns out to be reachable after an escape
232  // point.
233  SmallVector<CallInst *, 32> DeferredTails;
234 
235  BasicBlock *BB = &F.getEntryBlock();
236  VisitType Escaped = UNESCAPED;
237  do {
238  for (auto &I : *BB) {
239  if (Tracker.EscapePoints.count(&I))
240  Escaped = ESCAPED;
241 
242  CallInst *CI = dyn_cast<CallInst>(&I);
243  // A PseudoProbeInst has the IntrInaccessibleMemOnly tag hence it is
244  // considered accessing memory and will be marked as a tail call if we
245  // don't bail out here.
246  if (!CI || CI->isTailCall() || isa<DbgInfoIntrinsic>(&I) ||
247  isa<PseudoProbeInst>(&I))
248  continue;
249 
250  // Special-case operand bundle "clang.arc.attachedcall".
251  bool IsNoTail =
254 
255  if (!IsNoTail && CI->doesNotAccessMemory()) {
256  // A call to a readnone function whose arguments are all things computed
257  // outside this function can be marked tail. Even if you stored the
258  // alloca address into a global, a readnone function can't load the
259  // global anyhow.
260  //
261  // Note that this runs whether we know an alloca has escaped or not. If
262  // it has, then we can't trust Tracker.AllocaUsers to be accurate.
263  bool SafeToTail = true;
264  for (auto &Arg : CI->arg_operands()) {
265  if (isa<Constant>(Arg.getUser()))
266  continue;
267  if (Argument *A = dyn_cast<Argument>(Arg.getUser()))
268  if (!A->hasByValAttr())
269  continue;
270  SafeToTail = false;
271  break;
272  }
273  if (SafeToTail) {
274  using namespace ore;
275  ORE->emit([&]() {
276  return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI)
277  << "marked as tail call candidate (readnone)";
278  });
279  CI->setTailCall();
280  Modified = true;
281  continue;
282  }
283  }
284 
285  if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) {
286  DeferredTails.push_back(CI);
287  } else {
288  AllCallsAreTailCalls = false;
289  }
290  }
291 
292  for (auto *SuccBB : successors(BB)) {
293  auto &State = Visited[SuccBB];
294  if (State < Escaped) {
295  State = Escaped;
296  if (State == ESCAPED)
297  WorklistEscaped.push_back(SuccBB);
298  else
299  WorklistUnescaped.push_back(SuccBB);
300  }
301  }
302 
303  if (!WorklistEscaped.empty()) {
304  BB = WorklistEscaped.pop_back_val();
305  Escaped = ESCAPED;
306  } else {
307  BB = nullptr;
308  while (!WorklistUnescaped.empty()) {
309  auto *NextBB = WorklistUnescaped.pop_back_val();
310  if (Visited[NextBB] == UNESCAPED) {
311  BB = NextBB;
312  Escaped = UNESCAPED;
313  break;
314  }
315  }
316  }
317  } while (BB);
318 
319  for (CallInst *CI : DeferredTails) {
320  if (Visited[CI->getParent()] != ESCAPED) {
321  // If the escape point was part way through the block, calls after the
322  // escape point wouldn't have been put into DeferredTails.
323  LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n");
324  CI->setTailCall();
325  Modified = true;
326  } else {
327  AllCallsAreTailCalls = false;
328  }
329  }
330 
331  return Modified;
332 }
333 
334 /// Return true if it is safe to move the specified
335 /// instruction from after the call to before the call, assuming that all
336 /// instructions between the call and this instruction are movable.
337 ///
339  // FIXME: We can move load/store/call/free instructions above the call if the
340  // call does not mod/ref the memory location being processed.
341  if (I->mayHaveSideEffects()) // This also handles volatile loads.
342  return false;
343 
344  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
345  // Loads may always be moved above calls without side effects.
346  if (CI->mayHaveSideEffects()) {
347  // Non-volatile loads may be moved above a call with side effects if it
348  // does not write to memory and the load provably won't trap.
349  // Writes to memory only matter if they may alias the pointer
350  // being loaded from.
351  const DataLayout &DL = L->getModule()->getDataLayout();
352  if (isModSet(AA->getModRefInfo(CI, MemoryLocation::get(L))) ||
353  !isSafeToLoadUnconditionally(L->getPointerOperand(), L->getType(),
354  L->getAlign(), DL, L))
355  return false;
356  }
357  }
358 
359  // Otherwise, if this is a side-effect free instruction, check to make sure
360  // that it does not use the return value of the call. If it doesn't use the
361  // return value of the call, it must only use things that are defined before
362  // the call, or movable instructions between the call and the instruction
363  // itself.
364  return !is_contained(I->operands(), CI);
365 }
366 
368  if (!I->isAssociative() || !I->isCommutative())
369  return false;
370 
371  assert(I->getNumOperands() == 2 &&
372  "Associative/commutative operations should have 2 args!");
373 
374  // Exactly one operand should be the result of the call instruction.
375  if ((I->getOperand(0) == CI && I->getOperand(1) == CI) ||
376  (I->getOperand(0) != CI && I->getOperand(1) != CI))
377  return false;
378 
379  // The only user of this instruction we allow is a single return instruction.
380  if (!I->hasOneUse() || !isa<ReturnInst>(I->user_back()))
381  return false;
382 
383  return true;
384 }
385 
387  while (isa<DbgInfoIntrinsic>(I))
388  ++I;
389  return &*I;
390 }
391 
392 namespace {
393 class TailRecursionEliminator {
394  Function &F;
395  const TargetTransformInfo *TTI;
396  AliasAnalysis *AA;
398  DomTreeUpdater &DTU;
399 
400  // The below are shared state we want to have available when eliminating any
401  // calls in the function. There values should be populated by
402  // createTailRecurseLoopHeader the first time we find a call we can eliminate.
403  BasicBlock *HeaderBB = nullptr;
404  SmallVector<PHINode *, 8> ArgumentPHIs;
405  bool RemovableCallsMustBeMarkedTail = false;
406 
407  // PHI node to store our return value.
408  PHINode *RetPN = nullptr;
409 
410  // i1 PHI node to track if we have a valid return value stored in RetPN.
411  PHINode *RetKnownPN = nullptr;
412 
413  // Vector of select instructions we insereted. These selects use RetKnownPN
414  // to either propagate RetPN or select a new return value.
415  SmallVector<SelectInst *, 8> RetSelects;
416 
417  // The below are shared state needed when performing accumulator recursion.
418  // There values should be populated by insertAccumulator the first time we
419  // find an elimination that requires an accumulator.
420 
421  // PHI node to store our current accumulated value.
422  PHINode *AccPN = nullptr;
423 
424  // The instruction doing the accumulating.
425  Instruction *AccumulatorRecursionInstr = nullptr;
426 
427  TailRecursionEliminator(Function &F, const TargetTransformInfo *TTI,
429  DomTreeUpdater &DTU)
430  : F(F), TTI(TTI), AA(AA), ORE(ORE), DTU(DTU) {}
431 
432  CallInst *findTRECandidate(BasicBlock *BB,
433  bool CannotTailCallElimCallsMarkedTail);
434 
435  void createTailRecurseLoopHeader(CallInst *CI);
436 
437  void insertAccumulator(Instruction *AccRecInstr);
438 
439  bool eliminateCall(CallInst *CI);
440 
441  void cleanupAndFinalize();
442 
443  bool processBlock(BasicBlock &BB, bool CannotTailCallElimCallsMarkedTail);
444 
445 public:
446  static bool eliminate(Function &F, const TargetTransformInfo *TTI,
448  DomTreeUpdater &DTU);
449 };
450 } // namespace
451 
452 CallInst *TailRecursionEliminator::findTRECandidate(
453  BasicBlock *BB, bool CannotTailCallElimCallsMarkedTail) {
454  Instruction *TI = BB->getTerminator();
455 
456  if (&BB->front() == TI) // Make sure there is something before the terminator.
457  return nullptr;
458 
459  // Scan backwards from the return, checking to see if there is a tail call in
460  // this block. If so, set CI to it.
461  CallInst *CI = nullptr;
462  BasicBlock::iterator BBI(TI);
463  while (true) {
464  CI = dyn_cast<CallInst>(BBI);
465  if (CI && CI->getCalledFunction() == &F)
466  break;
467 
468  if (BBI == BB->begin())
469  return nullptr; // Didn't find a potential tail call.
470  --BBI;
471  }
472 
473  // If this call is marked as a tail call, and if there are dynamic allocas in
474  // the function, we cannot perform this optimization.
475  if (CI->isTailCall() && CannotTailCallElimCallsMarkedTail)
476  return nullptr;
477 
478  // As a special case, detect code like this:
479  // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
480  // and disable this xform in this case, because the code generator will
481  // lower the call to fabs into inline code.
482  if (BB == &F.getEntryBlock() &&
483  firstNonDbg(BB->front().getIterator()) == CI &&
484  firstNonDbg(std::next(BB->begin())) == TI && CI->getCalledFunction() &&
486  // A single-block function with just a call and a return. Check that
487  // the arguments match.
488  auto I = CI->arg_begin(), E = CI->arg_end();
489  Function::arg_iterator FI = F.arg_begin(), FE = F.arg_end();
490  for (; I != E && FI != FE; ++I, ++FI)
491  if (*I != &*FI) break;
492  if (I == E && FI == FE)
493  return nullptr;
494  }
495 
496  return CI;
497 }
498 
499 void TailRecursionEliminator::createTailRecurseLoopHeader(CallInst *CI) {
500  HeaderBB = &F.getEntryBlock();
501  BasicBlock *NewEntry = BasicBlock::Create(F.getContext(), "", &F, HeaderBB);
502  NewEntry->takeName(HeaderBB);
503  HeaderBB->setName("tailrecurse");
504  BranchInst *BI = BranchInst::Create(HeaderBB, NewEntry);
505  BI->setDebugLoc(CI->getDebugLoc());
506 
507  // If this function has self recursive calls in the tail position where some
508  // are marked tail and some are not, only transform one flavor or another.
509  // We have to choose whether we move allocas in the entry block to the new
510  // entry block or not, so we can't make a good choice for both. We make this
511  // decision here based on whether the first call we found to remove is
512  // marked tail.
513  // NOTE: We could do slightly better here in the case that the function has
514  // no entry block allocas.
515  RemovableCallsMustBeMarkedTail = CI->isTailCall();
516 
517  // If this tail call is marked 'tail' and if there are any allocas in the
518  // entry block, move them up to the new entry block.
519  if (RemovableCallsMustBeMarkedTail)
520  // Move all fixed sized allocas from HeaderBB to NewEntry.
521  for (BasicBlock::iterator OEBI = HeaderBB->begin(), E = HeaderBB->end(),
522  NEBI = NewEntry->begin();
523  OEBI != E;)
524  if (AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++))
525  if (isa<ConstantInt>(AI->getArraySize()))
526  AI->moveBefore(&*NEBI);
527 
528  // Now that we have created a new block, which jumps to the entry
529  // block, insert a PHI node for each argument of the function.
530  // For now, we initialize each PHI to only have the real arguments
531  // which are passed in.
532  Instruction *InsertPos = &HeaderBB->front();
533  for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
534  PHINode *PN =
535  PHINode::Create(I->getType(), 2, I->getName() + ".tr", InsertPos);
536  I->replaceAllUsesWith(PN); // Everyone use the PHI node now!
537  PN->addIncoming(&*I, NewEntry);
538  ArgumentPHIs.push_back(PN);
539  }
540 
541  // If the function doen't return void, create the RetPN and RetKnownPN PHI
542  // nodes to track our return value. We initialize RetPN with undef and
543  // RetKnownPN with false since we can't know our return value at function
544  // entry.
545  Type *RetType = F.getReturnType();
546  if (!RetType->isVoidTy()) {
547  Type *BoolType = Type::getInt1Ty(F.getContext());
548  RetPN = PHINode::Create(RetType, 2, "ret.tr", InsertPos);
549  RetKnownPN = PHINode::Create(BoolType, 2, "ret.known.tr", InsertPos);
550 
551  RetPN->addIncoming(UndefValue::get(RetType), NewEntry);
552  RetKnownPN->addIncoming(ConstantInt::getFalse(BoolType), NewEntry);
553  }
554 
555  // The entry block was changed from HeaderBB to NewEntry.
556  // The forward DominatorTree needs to be recalculated when the EntryBB is
557  // changed. In this corner-case we recalculate the entire tree.
558  DTU.recalculate(*NewEntry->getParent());
559 }
560 
561 void TailRecursionEliminator::insertAccumulator(Instruction *AccRecInstr) {
562  assert(!AccPN && "Trying to insert multiple accumulators");
563 
564  AccumulatorRecursionInstr = AccRecInstr;
565 
566  // Start by inserting a new PHI node for the accumulator.
567  pred_iterator PB = pred_begin(HeaderBB), PE = pred_end(HeaderBB);
568  AccPN = PHINode::Create(F.getReturnType(), std::distance(PB, PE) + 1,
569  "accumulator.tr", &HeaderBB->front());
570 
571  // Loop over all of the predecessors of the tail recursion block. For the
572  // real entry into the function we seed the PHI with the identity constant for
573  // the accumulation operation. For any other existing branches to this block
574  // (due to other tail recursions eliminated) the accumulator is not modified.
575  // Because we haven't added the branch in the current block to HeaderBB yet,
576  // it will not show up as a predecessor.
577  for (pred_iterator PI = PB; PI != PE; ++PI) {
578  BasicBlock *P = *PI;
579  if (P == &F.getEntryBlock()) {
581  AccRecInstr->getOpcode(), AccRecInstr->getType());
582  AccPN->addIncoming(Identity, P);
583  } else {
584  AccPN->addIncoming(AccPN, P);
585  }
586  }
587 
588  ++NumAccumAdded;
589 }
590 
591 bool TailRecursionEliminator::eliminateCall(CallInst *CI) {
592  ReturnInst *Ret = cast<ReturnInst>(CI->getParent()->getTerminator());
593 
594  // Ok, we found a potential tail call. We can currently only transform the
595  // tail call if all of the instructions between the call and the return are
596  // movable to above the call itself, leaving the call next to the return.
597  // Check that this is the case now.
598  Instruction *AccRecInstr = nullptr;
599  BasicBlock::iterator BBI(CI);
600  for (++BBI; &*BBI != Ret; ++BBI) {
601  if (canMoveAboveCall(&*BBI, CI, AA))
602  continue;
603 
604  // If we can't move the instruction above the call, it might be because it
605  // is an associative and commutative operation that could be transformed
606  // using accumulator recursion elimination. Check to see if this is the
607  // case, and if so, remember which instruction accumulates for later.
608  if (AccPN || !canTransformAccumulatorRecursion(&*BBI, CI))
609  return false; // We cannot eliminate the tail recursion!
610 
611  // Yes, this is accumulator recursion. Remember which instruction
612  // accumulates.
613  AccRecInstr = &*BBI;
614  }
615 
616  BasicBlock *BB = Ret->getParent();
617 
618  using namespace ore;
619  ORE->emit([&]() {
620  return OptimizationRemark(DEBUG_TYPE, "tailcall-recursion", CI)
621  << "transforming tail recursion into loop";
622  });
623 
624  // OK! We can transform this tail call. If this is the first one found,
625  // create the new entry block, allowing us to branch back to the old entry.
626  if (!HeaderBB)
627  createTailRecurseLoopHeader(CI);
628 
629  if (RemovableCallsMustBeMarkedTail && !CI->isTailCall())
630  return false;
631 
632  // Ok, now that we know we have a pseudo-entry block WITH all of the
633  // required PHI nodes, add entries into the PHI node for the actual
634  // parameters passed into the tail-recursive call.
635  for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i)
636  ArgumentPHIs[i]->addIncoming(CI->getArgOperand(i), BB);
637 
638  if (AccRecInstr) {
639  insertAccumulator(AccRecInstr);
640 
641  // Rewrite the accumulator recursion instruction so that it does not use
642  // the result of the call anymore, instead, use the PHI node we just
643  // inserted.
644  AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN);
645  }
646 
647  // Update our return value tracking
648  if (RetPN) {
649  if (Ret->getReturnValue() == CI || AccRecInstr) {
650  // Defer selecting a return value
651  RetPN->addIncoming(RetPN, BB);
652  RetKnownPN->addIncoming(RetKnownPN, BB);
653  } else {
654  // We found a return value we want to use, insert a select instruction to
655  // select it if we don't already know what our return value will be and
656  // store the result in our return value PHI node.
658  RetKnownPN, RetPN, Ret->getReturnValue(), "current.ret.tr", Ret);
659  RetSelects.push_back(SI);
660 
661  RetPN->addIncoming(SI, BB);
662  RetKnownPN->addIncoming(ConstantInt::getTrue(RetKnownPN->getType()), BB);
663  }
664 
665  if (AccPN)
666  AccPN->addIncoming(AccRecInstr ? AccRecInstr : AccPN, BB);
667  }
668 
669  // Now that all of the PHI nodes are in place, remove the call and
670  // ret instructions, replacing them with an unconditional branch.
671  BranchInst *NewBI = BranchInst::Create(HeaderBB, Ret);
672  NewBI->setDebugLoc(CI->getDebugLoc());
673 
674  BB->getInstList().erase(Ret); // Remove return.
675  BB->getInstList().erase(CI); // Remove call.
676  DTU.applyUpdates({{DominatorTree::Insert, BB, HeaderBB}});
677  ++NumEliminated;
678  return true;
679 }
680 
681 void TailRecursionEliminator::cleanupAndFinalize() {
682  // If we eliminated any tail recursions, it's possible that we inserted some
683  // silly PHI nodes which just merge an initial value (the incoming operand)
684  // with themselves. Check to see if we did and clean up our mess if so. This
685  // occurs when a function passes an argument straight through to its tail
686  // call.
687  for (PHINode *PN : ArgumentPHIs) {
688  // If the PHI Node is a dynamic constant, replace it with the value it is.
689  if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) {
690  PN->replaceAllUsesWith(PNV);
691  PN->eraseFromParent();
692  }
693  }
694 
695  if (RetPN) {
696  if (RetSelects.empty()) {
697  // If we didn't insert any select instructions, then we know we didn't
698  // store a return value and we can remove the PHI nodes we inserted.
699  RetPN->dropAllReferences();
700  RetPN->eraseFromParent();
701 
702  RetKnownPN->dropAllReferences();
703  RetKnownPN->eraseFromParent();
704 
705  if (AccPN) {
706  // We need to insert a copy of our accumulator instruction before any
707  // return in the function, and return its result instead.
708  Instruction *AccRecInstr = AccumulatorRecursionInstr;
709  for (BasicBlock &BB : F) {
710  ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator());
711  if (!RI)
712  continue;
713 
714  Instruction *AccRecInstrNew = AccRecInstr->clone();
715  AccRecInstrNew->setName("accumulator.ret.tr");
716  AccRecInstrNew->setOperand(AccRecInstr->getOperand(0) == AccPN,
717  RI->getOperand(0));
718  AccRecInstrNew->insertBefore(RI);
719  RI->setOperand(0, AccRecInstrNew);
720  }
721  }
722  } else {
723  // We need to insert a select instruction before any return left in the
724  // function to select our stored return value if we have one.
725  for (BasicBlock &BB : F) {
726  ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator());
727  if (!RI)
728  continue;
729 
731  RetKnownPN, RetPN, RI->getOperand(0), "current.ret.tr", RI);
732  RetSelects.push_back(SI);
733  RI->setOperand(0, SI);
734  }
735 
736  if (AccPN) {
737  // We need to insert a copy of our accumulator instruction before any
738  // of the selects we inserted, and select its result instead.
739  Instruction *AccRecInstr = AccumulatorRecursionInstr;
740  for (SelectInst *SI : RetSelects) {
741  Instruction *AccRecInstrNew = AccRecInstr->clone();
742  AccRecInstrNew->setName("accumulator.ret.tr");
743  AccRecInstrNew->setOperand(AccRecInstr->getOperand(0) == AccPN,
744  SI->getFalseValue());
745  AccRecInstrNew->insertBefore(SI);
746  SI->setFalseValue(AccRecInstrNew);
747  }
748  }
749  }
750  }
751 }
752 
753 bool TailRecursionEliminator::processBlock(
754  BasicBlock &BB, bool CannotTailCallElimCallsMarkedTail) {
755  Instruction *TI = BB.getTerminator();
756 
757  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
758  if (BI->isConditional())
759  return false;
760 
761  BasicBlock *Succ = BI->getSuccessor(0);
762  ReturnInst *Ret = dyn_cast<ReturnInst>(Succ->getFirstNonPHIOrDbg(true));
763 
764  if (!Ret)
765  return false;
766 
767  CallInst *CI = findTRECandidate(&BB, CannotTailCallElimCallsMarkedTail);
768 
769  if (!CI)
770  return false;
771 
772  LLVM_DEBUG(dbgs() << "FOLDING: " << *Succ
773  << "INTO UNCOND BRANCH PRED: " << BB);
774  FoldReturnIntoUncondBranch(Ret, Succ, &BB, &DTU);
775  ++NumRetDuped;
776 
777  // If all predecessors of Succ have been eliminated by
778  // FoldReturnIntoUncondBranch, delete it. It is important to empty it,
779  // because the ret instruction in there is still using a value which
780  // eliminateCall will attempt to remove. This block can only contain
781  // instructions that can't have uses, therefore it is safe to remove.
782  if (pred_empty(Succ))
783  DTU.deleteBB(Succ);
784 
785  eliminateCall(CI);
786  return true;
787  } else if (isa<ReturnInst>(TI)) {
788  CallInst *CI = findTRECandidate(&BB, CannotTailCallElimCallsMarkedTail);
789 
790  if (CI)
791  return eliminateCall(CI);
792  }
793 
794  return false;
795 }
796 
797 bool TailRecursionEliminator::eliminate(Function &F,
798  const TargetTransformInfo *TTI,
799  AliasAnalysis *AA,
801  DomTreeUpdater &DTU) {
802  if (F.getFnAttribute("disable-tail-calls").getValueAsBool())
803  return false;
804 
805  bool MadeChange = false;
806  bool AllCallsAreTailCalls = false;
807  MadeChange |= markTails(F, AllCallsAreTailCalls, ORE);
808  if (!AllCallsAreTailCalls)
809  return MadeChange;
810 
811  // If this function is a varargs function, we won't be able to PHI the args
812  // right, so don't even try to convert it...
813  if (F.getFunctionType()->isVarArg())
814  return MadeChange;
815 
816  // If false, we cannot perform TRE on tail calls marked with the 'tail'
817  // attribute, because doing so would cause the stack size to increase (real
818  // TRE would deallocate variable sized allocas, TRE doesn't).
819  bool CanTRETailMarkedCall = canTRE(F);
820 
821  // Change any tail recursive calls to loops.
822  TailRecursionEliminator TRE(F, TTI, AA, ORE, DTU);
823 
824  for (BasicBlock &BB : F)
825  MadeChange |= TRE.processBlock(BB, !CanTRETailMarkedCall);
826 
827  TRE.cleanupAndFinalize();
828 
829  return MadeChange;
830 }
831 
832 namespace {
833 struct TailCallElim : public FunctionPass {
834  static char ID; // Pass identification, replacement for typeid
835  TailCallElim() : FunctionPass(ID) {
837  }
838 
839  void getAnalysisUsage(AnalysisUsage &AU) const override {
846  }
847 
848  bool runOnFunction(Function &F) override {
849  if (skipFunction(F))
850  return false;
851 
852  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
853  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
854  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
855  auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
856  // There is no noticable performance difference here between Lazy and Eager
857  // UpdateStrategy based on some test results. It is feasible to switch the
858  // UpdateStrategy to Lazy if we find it profitable later.
860 
861  return TailRecursionEliminator::eliminate(
862  F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
863  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
864  &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU);
865  }
866 };
867 }
868 
869 char TailCallElim::ID = 0;
870 INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",
871  false, false)
876 
877 // Public interface to the TailCallElimination pass
879  return new TailCallElim();
880 }
881 
884 
886  AliasAnalysis &AA = AM.getResult<AAManager>(F);
888  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
890  // There is no noticable performance difference here between Lazy and Eager
891  // UpdateStrategy based on some test results. It is feasible to switch the
892  // UpdateStrategy to Lazy if we find it profitable later.
894  bool Changed = TailRecursionEliminator::eliminate(F, &TTI, &AA, &ORE, DTU);
895 
896  if (!Changed)
897  return PreservedAnalyses::all();
899  PA.preserve<GlobalsAA>();
902  return PA;
903 }
i
i
Definition: README.txt:29
llvm::GlobalsAA
Analysis pass providing a never-invalidated alias analysis result.
Definition: GlobalsModRef.h:132
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1221
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2319
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:37
llvm
Definition: AllocatorList.h:23
llvm::createTailCallEliminationPass
FunctionPass * createTailCallEliminationPass()
Definition: TailRecursionElimination.cpp:878
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:194
llvm::TailCallElimPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: TailRecursionElimination.cpp:882
llvm::CallInst::setTailCall
void setTailCall(bool IsTc=true)
Definition: Instructions.h:1657
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2925
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::BasicBlock::getFirstNonPHIOrDbg
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=false) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:219
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
Scalar.h
InstIterator.h
Loads.h
llvm::Function
Definition: Function.h:61
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
CaptureTracking.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
TailRecursionElimination.h
DomTreeUpdater.h
OptimizationRemarkEmitter.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
GlobalsModRef.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
Module.h
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::FoldReturnIntoUncondBranch
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
Definition: BasicBlockUtils.cpp:1297
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::CallBase::getNumArgOperands
unsigned getNumArgOperands() const
Definition: InstrTypes.h:1339
STLExtras.h
llvm::CallBase::arg_begin
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1306
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::initializeTailCallElimPass
void initializeTailCallElimPass(PassRegistry &)
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1482
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1746
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::AAResults
Definition: AliasAnalysis.h:456
PostDominators.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
tailcallelim
tailcallelim
Definition: TailRecursionElimination.cpp:874
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1396
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
SI
@ SI
Definition: SIInstrInfo.cpp:7411
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::SimplifyInstruction
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:5788
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:371
LoopDeletionResult::Modified
@ Modified
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1770
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
SmallPtrSet.h
llvm::CallInst::isTailCall
bool isTailCall() const
Definition: Instructions.h:1644
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::CallBase::onlyReadsMemory
bool onlyReadsMemory(unsigned OpNo) const
Definition: InstrTypes.h:1699
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
firstNonDbg
static Instruction * firstNonDbg(BasicBlock::iterator I)
Definition: TailRecursionElimination.cpp:386
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination", false, false) INITIALIZE_PASS_END(TailCallElim
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::CallBase::doesNotAccessMemory
bool doesNotAccessMemory(unsigned OpNo) const
Definition: InstrTypes.h:1693
llvm::ConstantExpr::getBinOpIdentity
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2786
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2375
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2722
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3063
llvm::DenseMap
Definition: DenseMap.h:714
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1547
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
llvm::Instruction::mayHaveSideEffects
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:629
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
InlineCost.h
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1715
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:162
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::TargetTransformInfo::isLoweredToCall
bool isLoweredToCall(const Function *F) const
Test whether calls to a function lower to actual program function calls.
Definition: TargetTransformInfo.cpp:275
canTransformAccumulatorRecursion
static bool canTransformAccumulatorRecursion(Instruction *I, CallInst *CI)
Definition: TailRecursionElimination.cpp:367
llvm::CallBase::arg_end
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1312
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
CFG.h
llvm::Instruction::clone
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
Definition: Instruction.cpp:821
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
DataLayout.h
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:527
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::CallInst::isNoTailCall
bool isNoTailCall() const
Definition: Instructions.h:1651
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:119
llvm::PredIterator
Definition: CFG.h:43
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
ValueHandle.h
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:148
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
llvm::CallBase::hasOperandBundlesOtherThan
bool hasOperandBundlesOtherThan(ArrayRef< uint32_t > IDs) const
Return true if this operand bundle user contains operand bundles with tags other than those specified...
Definition: InstrTypes.h:2068
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::OptimizationRemarkEmitterWrapperPass
OptimizationRemarkEmitter legacy analysis pass.
Definition: OptimizationRemarkEmitter.h:138
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2614
Elimination
Tail Call Elimination
Definition: TailRecursionElimination.cpp:874
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:804
DiagnosticInfo.h
Function.h
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:684
Instructions.h
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
Dominators.h
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
DEBUG_TYPE
#define DEBUG_TYPE
Definition: TailRecursionElimination.cpp:86
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1269
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2572
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1164
DerivedTypes.h
llvm::isSafeToLoadUnconditionally
bool isSafeToLoadUnconditionally(Value *V, Align Alignment, APInt &Size, const DataLayout &DL, Instruction *ScanFrom=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if we know that executing a load from this value cannot trap.
Definition: Loads.cpp:335
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
canTRE
static bool canTRE(Function &F)
Scan the specified function for alloca instructions.
Definition: TailRecursionElimination.cpp:94
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::PostDominatorTreeAnalysis
Analysis pass which computes a PostDominatorTree.
Definition: PostDominators.h:47
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:377
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3007
raw_ostream.h
llvm::CallBase::arg_operands
iterator_range< User::op_iterator > arg_operands()
Definition: InstrTypes.h:1333
BasicBlockUtils.h
InitializePasses.h
llvm::OptimizationRemarkEmitterAnalysis
Definition: OptimizationRemarkEmitter.h:156
markTails
static bool markTails(Function &F, bool &AllCallsAreTailCalls, OptimizationRemarkEmitter *ORE)
Definition: TailRecursionElimination.cpp:191
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::AAResults::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
Definition: AliasAnalysis.cpp:217
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3086
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3100
llvm::LLVMContext::OB_clang_arc_attachedcall
@ OB_clang_arc_attachedcall
Definition: LLVMContext.h:96
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
canMoveAboveCall
static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA)
Return true if it is safe to move the specified instruction from after the call to before the call,...
Definition: TailRecursionElimination.cpp:338