LLVM  8.0.0svn
TailRecursionElimination.cpp
Go to the documentation of this file.
1 //===- TailRecursionElimination.cpp - Eliminate Tail Calls ----------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file transforms calls of the current function (self recursion) followed
11 // by a return instruction with a branch to the entry of the function, creating
12 // a loop. This pass also implements the following extensions to the basic
13 // algorithm:
14 //
15 // 1. Trivial instructions between the call and return do not prevent the
16 // transformation from taking place, though currently the analysis cannot
17 // support moving any really useful instructions (only dead ones).
18 // 2. This pass transforms functions that are prevented from being tail
19 // recursive by an associative and commutative expression to use an
20 // accumulator variable, thus compiling the typical naive factorial or
21 // 'fib' implementation into efficient code.
22 // 3. TRE is performed if the function returns void, if the return
23 // returns the result returned by the call, or if the function returns a
24 // run-time constant on all exits from the function. It is possible, though
25 // unlikely, that the return returns something else (like constant 0), and
26 // can still be TRE'd. It can be TRE'd if ALL OTHER return instructions in
27 // the function return the exact same value.
28 // 4. If it can prove that callees do not access their caller stack frame,
29 // they are marked as eligible for tail call elimination (by the code
30 // generator).
31 //
32 // There are several improvements that could be made:
33 //
34 // 1. If the function has any alloca instructions, these instructions will be
35 // moved out of the entry block of the function, causing them to be
36 // evaluated each time through the tail recursion. Safely keeping allocas
37 // in the entry block requires analysis to proves that the tail-called
38 // function does not read or write the stack object.
39 // 2. Tail recursion is only performed if the call immediately precedes the
40 // return instruction. It's possible that there could be a jump between
41 // the call and the return.
42 // 3. There can be intervening operations between the call and the return that
43 // prevent the TRE from occurring. For example, there could be GEP's and
44 // stores to memory that will not be read or written by the call. This
45 // requires some substantial analysis (such as with DSA) to prove safe to
46 // move ahead of the call, but doing so could allow many more TREs to be
47 // performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark.
48 // 4. The algorithm we use to detect if callees access their caller stack
49 // frames is very primitive.
50 //
51 //===----------------------------------------------------------------------===//
52 
54 #include "llvm/ADT/STLExtras.h"
55 #include "llvm/ADT/SmallPtrSet.h"
56 #include "llvm/ADT/Statistic.h"
57 #include "llvm/Analysis/CFG.h"
62 #include "llvm/Analysis/Loads.h"
66 #include "llvm/IR/CFG.h"
67 #include "llvm/IR/CallSite.h"
68 #include "llvm/IR/Constants.h"
69 #include "llvm/IR/DataLayout.h"
70 #include "llvm/IR/DerivedTypes.h"
71 #include "llvm/IR/DiagnosticInfo.h"
72 #include "llvm/IR/DomTreeUpdater.h"
73 #include "llvm/IR/Dominators.h"
74 #include "llvm/IR/Function.h"
75 #include "llvm/IR/InstIterator.h"
76 #include "llvm/IR/Instructions.h"
77 #include "llvm/IR/IntrinsicInst.h"
78 #include "llvm/IR/Module.h"
79 #include "llvm/IR/ValueHandle.h"
80 #include "llvm/Pass.h"
81 #include "llvm/Support/Debug.h"
83 #include "llvm/Transforms/Scalar.h"
85 using namespace llvm;
86 
87 #define DEBUG_TYPE "tailcallelim"
88 
89 STATISTIC(NumEliminated, "Number of tail calls removed");
90 STATISTIC(NumRetDuped, "Number of return duplicated");
91 STATISTIC(NumAccumAdded, "Number of accumulators introduced");
92 
93 /// Scan the specified function for alloca instructions.
94 /// If it contains any dynamic allocas, returns false.
95 static bool canTRE(Function &F) {
96  // Because of PR962, we don't TRE dynamic allocas.
97  return llvm::all_of(instructions(F), [](Instruction &I) {
98  auto *AI = dyn_cast<AllocaInst>(&I);
99  return !AI || AI->isStaticAlloca();
100  });
101 }
102 
103 namespace {
104 struct AllocaDerivedValueTracker {
105  // Start at a root value and walk its use-def chain to mark calls that use the
106  // value or a derived value in AllocaUsers, and places where it may escape in
107  // EscapePoints.
108  void walk(Value *Root) {
109  SmallVector<Use *, 32> Worklist;
110  SmallPtrSet<Use *, 32> Visited;
111 
112  auto AddUsesToWorklist = [&](Value *V) {
113  for (auto &U : V->uses()) {
114  if (!Visited.insert(&U).second)
115  continue;
116  Worklist.push_back(&U);
117  }
118  };
119 
120  AddUsesToWorklist(Root);
121 
122  while (!Worklist.empty()) {
123  Use *U = Worklist.pop_back_val();
124  Instruction *I = cast<Instruction>(U->getUser());
125 
126  switch (I->getOpcode()) {
127  case Instruction::Call:
128  case Instruction::Invoke: {
129  CallSite CS(I);
130  // If the alloca-derived argument is passed byval it is not an escape
131  // point, or a use of an alloca. Calling with byval copies the contents
132  // of the alloca into argument registers or stack slots, which exist
133  // beyond the lifetime of the current frame.
134  if (CS.isArgOperand(U) && CS.isByValArgument(CS.getArgumentNo(U)))
135  continue;
136  bool IsNocapture =
137  CS.isDataOperand(U) && CS.doesNotCapture(CS.getDataOperandNo(U));
138  callUsesLocalStack(CS, IsNocapture);
139  if (IsNocapture) {
140  // If the alloca-derived argument is passed in as nocapture, then it
141  // can't propagate to the call's return. That would be capturing.
142  continue;
143  }
144  break;
145  }
146  case Instruction::Load: {
147  // The result of a load is not alloca-derived (unless an alloca has
148  // otherwise escaped, but this is a local analysis).
149  continue;
150  }
151  case Instruction::Store: {
152  if (U->getOperandNo() == 0)
153  EscapePoints.insert(I);
154  continue; // Stores have no users to analyze.
155  }
156  case Instruction::BitCast:
157  case Instruction::GetElementPtr:
158  case Instruction::PHI:
159  case Instruction::Select:
160  case Instruction::AddrSpaceCast:
161  break;
162  default:
163  EscapePoints.insert(I);
164  break;
165  }
166 
167  AddUsesToWorklist(I);
168  }
169  }
170 
171  void callUsesLocalStack(CallSite CS, bool IsNocapture) {
172  // Add it to the list of alloca users.
173  AllocaUsers.insert(CS.getInstruction());
174 
175  // If it's nocapture then it can't capture this alloca.
176  if (IsNocapture)
177  return;
178 
179  // If it can write to memory, it can leak the alloca value.
180  if (!CS.onlyReadsMemory())
181  EscapePoints.insert(CS.getInstruction());
182  }
183 
184  SmallPtrSet<Instruction *, 32> AllocaUsers;
185  SmallPtrSet<Instruction *, 32> EscapePoints;
186 };
187 }
188 
189 static bool markTails(Function &F, bool &AllCallsAreTailCalls,
192  return false;
193  AllCallsAreTailCalls = true;
194 
195  // The local stack holds all alloca instructions and all byval arguments.
196  AllocaDerivedValueTracker Tracker;
197  for (Argument &Arg : F.args()) {
198  if (Arg.hasByValAttr())
199  Tracker.walk(&Arg);
200  }
201  for (auto &BB : F) {
202  for (auto &I : BB)
203  if (AllocaInst *AI = dyn_cast<AllocaInst>(&I))
204  Tracker.walk(AI);
205  }
206 
207  bool Modified = false;
208 
209  // Track whether a block is reachable after an alloca has escaped. Blocks that
210  // contain the escaping instruction will be marked as being visited without an
211  // escaped alloca, since that is how the block began.
212  enum VisitType {
213  UNVISITED,
214  UNESCAPED,
215  ESCAPED
216  };
218 
219  // We propagate the fact that an alloca has escaped from block to successor.
220  // Visit the blocks that are propagating the escapedness first. To do this, we
221  // maintain two worklists.
222  SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped;
223 
224  // We may enter a block and visit it thinking that no alloca has escaped yet,
225  // then see an escape point and go back around a loop edge and come back to
226  // the same block twice. Because of this, we defer setting tail on calls when
227  // we first encounter them in a block. Every entry in this list does not
228  // statically use an alloca via use-def chain analysis, but may find an alloca
229  // through other means if the block turns out to be reachable after an escape
230  // point.
231  SmallVector<CallInst *, 32> DeferredTails;
232 
233  BasicBlock *BB = &F.getEntryBlock();
234  VisitType Escaped = UNESCAPED;
235  do {
236  for (auto &I : *BB) {
237  if (Tracker.EscapePoints.count(&I))
238  Escaped = ESCAPED;
239 
240  CallInst *CI = dyn_cast<CallInst>(&I);
241  if (!CI || CI->isTailCall() || isa<DbgInfoIntrinsic>(&I))
242  continue;
243 
244  bool IsNoTail = CI->isNoTailCall() || CI->hasOperandBundles();
245 
246  if (!IsNoTail && CI->doesNotAccessMemory()) {
247  // A call to a readnone function whose arguments are all things computed
248  // outside this function can be marked tail. Even if you stored the
249  // alloca address into a global, a readnone function can't load the
250  // global anyhow.
251  //
252  // Note that this runs whether we know an alloca has escaped or not. If
253  // it has, then we can't trust Tracker.AllocaUsers to be accurate.
254  bool SafeToTail = true;
255  for (auto &Arg : CI->arg_operands()) {
256  if (isa<Constant>(Arg.getUser()))
257  continue;
258  if (Argument *A = dyn_cast<Argument>(Arg.getUser()))
259  if (!A->hasByValAttr())
260  continue;
261  SafeToTail = false;
262  break;
263  }
264  if (SafeToTail) {
265  using namespace ore;
266  ORE->emit([&]() {
267  return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI)
268  << "marked as tail call candidate (readnone)";
269  });
270  CI->setTailCall();
271  Modified = true;
272  continue;
273  }
274  }
275 
276  if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) {
277  DeferredTails.push_back(CI);
278  } else {
279  AllCallsAreTailCalls = false;
280  }
281  }
282 
283  for (auto *SuccBB : make_range(succ_begin(BB), succ_end(BB))) {
284  auto &State = Visited[SuccBB];
285  if (State < Escaped) {
286  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 ///
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(),
345  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.
363 static 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.
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.
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 
444  while (isa<DbgInfoIntrinsic>(I))
445  ++I;
446  return &*I;
447 }
448 
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.
488  E = CallSite(CI).arg_end();
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 
501  CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry,
502  bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
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.insertEdge(BB, OldEntry);
683  ++NumEliminated;
684  return true;
685 }
686 
688  BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry,
689  bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
690  bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
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 
737  ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail,
738  SmallVectorImpl<PHINode *> &ArgumentPHIs,
739  bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
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 
750  AliasAnalysis *AA,
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 
812 namespace {
813 struct TailCallElim : public FunctionPass {
814  static char ID; // Pass identification, replacement for typeid
815  TailCallElim() : FunctionPass(ID) {
817  }
818 
819  void getAnalysisUsage(AnalysisUsage &AU) const override {
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.
840 
841  return eliminateTailRecursion(
842  F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
843  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
844  &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU);
845  }
846 };
847 }
848 
849 char TailCallElim::ID = 0;
850 INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",
851  false, false)
854 INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination",
855  false, false)
856 
857 // Public interface to the TailCallElimination pass
859  return new TailCallElim();
860 }
861 
864 
866  AliasAnalysis &AA = AM.getResult<AAManager>(F);
868  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(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.
874  bool Changed = eliminateTailRecursion(F, &TTI, &AA, &ORE, DTU);
875 
876  if (!Changed)
877  return PreservedAnalyses::all();
879  PA.preserve<GlobalsAA>();
882  return PA;
883 }
Legacy wrapper pass to provide the GlobalsAAResult object.
bool hasOperandBundles() const
Return true if this User has any operand bundles.
Definition: InstrTypes.h:1130
Return a value (possibly void), from a function.
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:213
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
Function * getCalledFunction() const
Return the function called, or null if this is an indirect function invocation.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static bool processReturningBlock(ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
iterator erase(iterator where)
Definition: ilist.h:267
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
iterator end()
Definition: Function.h:658
This class represents a function call, abstracting a target machine&#39;s calling convention.
Analysis pass providing the TargetTransformInfo.
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:1042
arg_iterator arg_end()
Definition: Function.h:680
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
An instruction for reading from memory.
Definition: Instructions.h:168
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:138
bool isSafeToLoadUnconditionally(Value *V, unsigned Align, const DataLayout &DL, Instruction *ScanFrom=nullptr, const DominatorTree *DT=nullptr)
Return true if we know that executing a load from this value cannot trap.
Definition: Loads.cpp:201
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:263
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:454
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
bool isArgOperand(Value::const_user_iterator UI) const
Determine whether the passed iterator points to an argument operand.
Definition: CallSite.h:151
IterTy arg_end() const
Definition: CallSite.h:575
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
InstrTy * getInstruction() const
Definition: CallSite.h:92
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:295
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
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...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:249
bool isVarArg() const
Definition: DerivedTypes.h:123
unsigned getDataOperandNo(Value::const_user_iterator UI) const
Given a value use iterator, return the data operand corresponding to it.
Definition: CallSite.h:223
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:301
iterator begin()
Definition: Function.h:656
Value * getOperand(unsigned i) const
Definition: User.h:170
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
bool doesNotAccessMemory() const
Determine if the call does not access memory.
static bool eliminateRecursiveTailCall(CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:304
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Conditional or Unconditional Branch instruction.
FunctionPass * createTailCallEliminationPass()
static bool foldReturnAndProcessPred(BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail, SmallVectorImpl< PHINode *> &ArgumentPHIs, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:275
#define DEBUG_TYPE
static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI)
Return true if the specified value is the same when the return would exit as it was when the initial ...
A manager for alias analyses.
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:371
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:558
Diagnostic information for applied optimization remarks.
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:113
bool isAssociative() const LLVM_READONLY
Return true if the instruction is associative:
Represent the analysis usage information of a pass.
Analysis pass providing a never-invalidated alias analysis result.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
op_range operands()
Definition: User.h:238
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
arg_iterator arg_begin()
Definition: Function.h:671
self_iterator getIterator()
Definition: ilist_node.h:82
bool isDataOperand(Value::const_user_iterator UI) const
Determine whether the passed iterator points to a data operand.
Definition: CallSite.h:177
Tail Call Elimination
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:593
void setTailCall(bool isTC=true)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
iterator_range< User::op_iterator > arg_operands()
Iteration adapter for range-for loops.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static Instruction * firstNonDbg(BasicBlock::iterator I)
static Value * getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI)
Check to see if the function containing the specified tail call consistently returns the same runtime...
static CallInst * findTRECandidate(Instruction *TI, bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:386
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:328
void insertEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge insertion.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:192
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
iterator end()
Definition: BasicBlock.h:265
IterTy arg_begin() const
Definition: CallSite.h:571
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Analysis pass which computes a PostDominatorTree.
Module.h This file contains the declarations for the Module class.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:64
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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...
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:474
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:164
void initializeTailCallElimPass(PassRegistry &)
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
static bool canTRE(Function &F)
Scan the specified function for alloca instructions.
bool isTailCall() const
INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination", false, false) INITIALIZE_PASS_END(TailCallElim
amdgpu Simplify well known AMD library false Value Value * Arg
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...
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
void recalculate(Function &F)
Recalculate all available trees and flush all BasicBlocks awaiting deletion immediately.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:307
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
unsigned getNumArgOperands() const
Return the number of call arguments.
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:195
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:58
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:789
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:598
bool callsFunctionThatReturnsTwice() const
callsFunctionThatReturnsTwice - Return true if the function has a call to setjmp or other function th...
Definition: Function.cpp:1291
Multiway switch.
static Value * canTransformAccumulatorRecursion(Instruction *I, CallInst *CI)
If the specified instruction can be transformed using accumulator recursion elimination, return the constant which is the start of the accumulator value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
LLVM Value Representation.
Definition: Value.h:73
static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI, AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU)
bool isLoweredToCall(const Function *F) const
Test whether calls to a function lower to actual program function calls.
OptimizationRemarkEmitter legacy analysis pass.
unsigned getArgumentNo(Value::const_user_iterator I) const
Given a value use iterator, returns the argument that corresponds to it.
Definition: CallSite.h:199
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.h:331
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
bool isNoTailCall() const
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:197
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
This pass exposes codegen information to IR-level passes.
bool isStaticAlloca() const
Return true if this alloca is in the entry block of the function and is a constant size...
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
static bool markTails(Function &F, bool &AllCallsAreTailCalls, OptimizationRemarkEmitter *ORE)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
The optimization diagnostic interface.
iterator_range< arg_iterator > args()
Definition: Function.h:689
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
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:1101