LLVM  10.0.0svn
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/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/Dominators.h"
73 #include "llvm/IR/Function.h"
74 #include "llvm/IR/InstIterator.h"
75 #include "llvm/IR/Instructions.h"
76 #include "llvm/IR/IntrinsicInst.h"
77 #include "llvm/IR/Module.h"
78 #include "llvm/IR/ValueHandle.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  // Because of PR962, we don't TRE dynamic allocas.
96  return llvm::all_of(instructions(F), [](Instruction &I) {
97  auto *AI = dyn_cast<AllocaInst>(&I);
98  return !AI || AI->isStaticAlloca();
99  });
100 }
101 
102 namespace {
103 struct AllocaDerivedValueTracker {
104  // Start at a root value and walk its use-def chain to mark calls that use the
105  // value or a derived value in AllocaUsers, and places where it may escape in
106  // EscapePoints.
107  void walk(Value *Root) {
108  SmallVector<Use *, 32> Worklist;
109  SmallPtrSet<Use *, 32> Visited;
110 
111  auto AddUsesToWorklist = [&](Value *V) {
112  for (auto &U : V->uses()) {
113  if (!Visited.insert(&U).second)
114  continue;
115  Worklist.push_back(&U);
116  }
117  };
118 
119  AddUsesToWorklist(Root);
120 
121  while (!Worklist.empty()) {
122  Use *U = Worklist.pop_back_val();
123  Instruction *I = cast<Instruction>(U->getUser());
124 
125  switch (I->getOpcode()) {
126  case Instruction::Call:
127  case Instruction::Invoke: {
128  CallSite CS(I);
129  // If the alloca-derived argument is passed byval it is not an escape
130  // point, or a use of an alloca. Calling with byval copies the contents
131  // of the alloca into argument registers or stack slots, which exist
132  // beyond the lifetime of the current frame.
133  if (CS.isArgOperand(U) && CS.isByValArgument(CS.getArgumentNo(U)))
134  continue;
135  bool IsNocapture =
136  CS.isDataOperand(U) && CS.doesNotCapture(CS.getDataOperandNo(U));
137  callUsesLocalStack(CS, IsNocapture);
138  if (IsNocapture) {
139  // If the alloca-derived argument is passed in as nocapture, then it
140  // can't propagate to the call's return. That would be capturing.
141  continue;
142  }
143  break;
144  }
145  case Instruction::Load: {
146  // The result of a load is not alloca-derived (unless an alloca has
147  // otherwise escaped, but this is a local analysis).
148  continue;
149  }
150  case Instruction::Store: {
151  if (U->getOperandNo() == 0)
152  EscapePoints.insert(I);
153  continue; // Stores have no users to analyze.
154  }
155  case Instruction::BitCast:
156  case Instruction::GetElementPtr:
157  case Instruction::PHI:
158  case Instruction::Select:
159  case Instruction::AddrSpaceCast:
160  break;
161  default:
162  EscapePoints.insert(I);
163  break;
164  }
165 
166  AddUsesToWorklist(I);
167  }
168  }
169 
170  void callUsesLocalStack(CallSite CS, bool IsNocapture) {
171  // Add it to the list of alloca users.
172  AllocaUsers.insert(CS.getInstruction());
173 
174  // If it's nocapture then it can't capture this alloca.
175  if (IsNocapture)
176  return;
177 
178  // If it can write to memory, it can leak the alloca value.
179  if (!CS.onlyReadsMemory())
180  EscapePoints.insert(CS.getInstruction());
181  }
182 
183  SmallPtrSet<Instruction *, 32> AllocaUsers;
184  SmallPtrSet<Instruction *, 32> EscapePoints;
185 };
186 }
187 
188 static bool markTails(Function &F, bool &AllCallsAreTailCalls,
191  return false;
192  AllCallsAreTailCalls = true;
193 
194  // The local stack holds all alloca instructions and all byval arguments.
195  AllocaDerivedValueTracker Tracker;
196  for (Argument &Arg : F.args()) {
197  if (Arg.hasByValAttr())
198  Tracker.walk(&Arg);
199  }
200  for (auto &BB : F) {
201  for (auto &I : BB)
202  if (AllocaInst *AI = dyn_cast<AllocaInst>(&I))
203  Tracker.walk(AI);
204  }
205 
206  bool Modified = false;
207 
208  // Track whether a block is reachable after an alloca has escaped. Blocks that
209  // contain the escaping instruction will be marked as being visited without an
210  // escaped alloca, since that is how the block began.
211  enum VisitType {
212  UNVISITED,
213  UNESCAPED,
214  ESCAPED
215  };
217 
218  // We propagate the fact that an alloca has escaped from block to successor.
219  // Visit the blocks that are propagating the escapedness first. To do this, we
220  // maintain two worklists.
221  SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped;
222 
223  // We may enter a block and visit it thinking that no alloca has escaped yet,
224  // then see an escape point and go back around a loop edge and come back to
225  // the same block twice. Because of this, we defer setting tail on calls when
226  // we first encounter them in a block. Every entry in this list does not
227  // statically use an alloca via use-def chain analysis, but may find an alloca
228  // through other means if the block turns out to be reachable after an escape
229  // point.
230  SmallVector<CallInst *, 32> DeferredTails;
231 
232  BasicBlock *BB = &F.getEntryBlock();
233  VisitType Escaped = UNESCAPED;
234  do {
235  for (auto &I : *BB) {
236  if (Tracker.EscapePoints.count(&I))
237  Escaped = ESCAPED;
238 
239  CallInst *CI = dyn_cast<CallInst>(&I);
240  if (!CI || CI->isTailCall() || isa<DbgInfoIntrinsic>(&I))
241  continue;
242 
243  bool IsNoTail = CI->isNoTailCall() || CI->hasOperandBundles();
244 
245  if (!IsNoTail && CI->doesNotAccessMemory()) {
246  // A call to a readnone function whose arguments are all things computed
247  // outside this function can be marked tail. Even if you stored the
248  // alloca address into a global, a readnone function can't load the
249  // global anyhow.
250  //
251  // Note that this runs whether we know an alloca has escaped or not. If
252  // it has, then we can't trust Tracker.AllocaUsers to be accurate.
253  bool SafeToTail = true;
254  for (auto &Arg : CI->arg_operands()) {
255  if (isa<Constant>(Arg.getUser()))
256  continue;
257  if (Argument *A = dyn_cast<Argument>(Arg.getUser()))
258  if (!A->hasByValAttr())
259  continue;
260  SafeToTail = false;
261  break;
262  }
263  if (SafeToTail) {
264  using namespace ore;
265  ORE->emit([&]() {
266  return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI)
267  << "marked as tail call candidate (readnone)";
268  });
269  CI->setTailCall();
270  Modified = true;
271  continue;
272  }
273  }
274 
275  if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) {
276  DeferredTails.push_back(CI);
277  } else {
278  AllCallsAreTailCalls = false;
279  }
280  }
281 
282  for (auto *SuccBB : make_range(succ_begin(BB), succ_end(BB))) {
283  auto &State = Visited[SuccBB];
284  if (State < Escaped) {
285  State = Escaped;
286  if (State == ESCAPED)
287  WorklistEscaped.push_back(SuccBB);
288  else
289  WorklistUnescaped.push_back(SuccBB);
290  }
291  }
292 
293  if (!WorklistEscaped.empty()) {
294  BB = WorklistEscaped.pop_back_val();
295  Escaped = ESCAPED;
296  } else {
297  BB = nullptr;
298  while (!WorklistUnescaped.empty()) {
299  auto *NextBB = WorklistUnescaped.pop_back_val();
300  if (Visited[NextBB] == UNESCAPED) {
301  BB = NextBB;
302  Escaped = UNESCAPED;
303  break;
304  }
305  }
306  }
307  } while (BB);
308 
309  for (CallInst *CI : DeferredTails) {
310  if (Visited[CI->getParent()] != ESCAPED) {
311  // If the escape point was part way through the block, calls after the
312  // escape point wouldn't have been put into DeferredTails.
313  LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n");
314  CI->setTailCall();
315  Modified = true;
316  } else {
317  AllCallsAreTailCalls = false;
318  }
319  }
320 
321  return Modified;
322 }
323 
324 /// Return true if it is safe to move the specified
325 /// instruction from after the call to before the call, assuming that all
326 /// instructions between the call and this instruction are movable.
327 ///
329  // FIXME: We can move load/store/call/free instructions above the call if the
330  // call does not mod/ref the memory location being processed.
331  if (I->mayHaveSideEffects()) // This also handles volatile loads.
332  return false;
333 
334  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
335  // Loads may always be moved above calls without side effects.
336  if (CI->mayHaveSideEffects()) {
337  // Non-volatile loads may be moved above a call with side effects if it
338  // does not write to memory and the load provably won't trap.
339  // Writes to memory only matter if they may alias the pointer
340  // being loaded from.
341  const DataLayout &DL = L->getModule()->getDataLayout();
342  if (isModSet(AA->getModRefInfo(CI, MemoryLocation::get(L))) ||
343  !isSafeToLoadUnconditionally(L->getPointerOperand(), L->getType(),
344  L->getAlignment(), DL, L))
345  return false;
346  }
347  }
348 
349  // Otherwise, if this is a side-effect free instruction, check to make sure
350  // that it does not use the return value of the call. If it doesn't use the
351  // return value of the call, it must only use things that are defined before
352  // the call, or movable instructions between the call and the instruction
353  // itself.
354  return !is_contained(I->operands(), CI);
355 }
356 
357 /// Return true if the specified value is the same when the return would exit
358 /// as it was when the initial iteration of the recursive function was executed.
359 ///
360 /// We currently handle static constants and arguments that are not modified as
361 /// part of the recursion.
362 static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) {
363  if (isa<Constant>(V)) return true; // Static constants are always dyn consts
364 
365  // Check to see if this is an immutable argument, if so, the value
366  // will be available to initialize the accumulator.
367  if (Argument *Arg = dyn_cast<Argument>(V)) {
368  // Figure out which argument number this is...
369  unsigned ArgNo = 0;
370  Function *F = CI->getParent()->getParent();
371  for (Function::arg_iterator AI = F->arg_begin(); &*AI != Arg; ++AI)
372  ++ArgNo;
373 
374  // If we are passing this argument into call as the corresponding
375  // argument operand, then the argument is dynamically constant.
376  // Otherwise, we cannot transform this function safely.
377  if (CI->getArgOperand(ArgNo) == Arg)
378  return true;
379  }
380 
381  // Switch cases are always constant integers. If the value is being switched
382  // on and the return is only reachable from one of its cases, it's
383  // effectively constant.
384  if (BasicBlock *UniquePred = RI->getParent()->getUniquePredecessor())
385  if (SwitchInst *SI = dyn_cast<SwitchInst>(UniquePred->getTerminator()))
386  if (SI->getCondition() == V)
387  return SI->getDefaultDest() != RI->getParent();
388 
389  // Not a constant or immutable argument, we can't safely transform.
390  return false;
391 }
392 
393 /// Check to see if the function containing the specified tail call consistently
394 /// returns the same runtime-constant value at all exit points except for
395 /// IgnoreRI. If so, return the returned value.
397  Function *F = CI->getParent()->getParent();
398  Value *ReturnedValue = nullptr;
399 
400  for (BasicBlock &BBI : *F) {
401  ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator());
402  if (RI == nullptr || RI == IgnoreRI) continue;
403 
404  // We can only perform this transformation if the value returned is
405  // evaluatable at the start of the initial invocation of the function,
406  // instead of at the end of the evaluation.
407  //
408  Value *RetOp = RI->getOperand(0);
409  if (!isDynamicConstant(RetOp, CI, RI))
410  return nullptr;
411 
412  if (ReturnedValue && RetOp != ReturnedValue)
413  return nullptr; // Cannot transform if differing values are returned.
414  ReturnedValue = RetOp;
415  }
416  return ReturnedValue;
417 }
418 
419 /// If the specified instruction can be transformed using accumulator recursion
420 /// elimination, return the constant which is the start of the accumulator
421 /// value. Otherwise return null.
423  if (!I->isAssociative() || !I->isCommutative()) return nullptr;
424  assert(I->getNumOperands() == 2 &&
425  "Associative/commutative operations should have 2 args!");
426 
427  // Exactly one operand should be the result of the call instruction.
428  if ((I->getOperand(0) == CI && I->getOperand(1) == CI) ||
429  (I->getOperand(0) != CI && I->getOperand(1) != CI))
430  return nullptr;
431 
432  // The only user of this instruction we allow is a single return instruction.
433  if (!I->hasOneUse() || !isa<ReturnInst>(I->user_back()))
434  return nullptr;
435 
436  // Ok, now we have to check all of the other return instructions in this
437  // function. If they return non-constants or differing values, then we cannot
438  // transform the function safely.
439  return getCommonReturnValue(cast<ReturnInst>(I->user_back()), CI);
440 }
441 
443  while (isa<DbgInfoIntrinsic>(I))
444  ++I;
445  return &*I;
446 }
447 
449  bool CannotTailCallElimCallsMarkedTail,
450  const TargetTransformInfo *TTI) {
451  BasicBlock *BB = TI->getParent();
452  Function *F = BB->getParent();
453 
454  if (&BB->front() == TI) // Make sure there is something before the terminator.
455  return nullptr;
456 
457  // Scan backwards from the return, checking to see if there is a tail call in
458  // this block. If so, set CI to it.
459  CallInst *CI = nullptr;
460  BasicBlock::iterator BBI(TI);
461  while (true) {
462  CI = dyn_cast<CallInst>(BBI);
463  if (CI && CI->getCalledFunction() == F)
464  break;
465 
466  if (BBI == BB->begin())
467  return nullptr; // Didn't find a potential tail call.
468  --BBI;
469  }
470 
471  // If this call is marked as a tail call, and if there are dynamic allocas in
472  // the function, we cannot perform this optimization.
473  if (CI->isTailCall() && CannotTailCallElimCallsMarkedTail)
474  return nullptr;
475 
476  // As a special case, detect code like this:
477  // double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
478  // and disable this xform in this case, because the code generator will
479  // lower the call to fabs into inline code.
480  if (BB == &F->getEntryBlock() &&
481  firstNonDbg(BB->front().getIterator()) == CI &&
482  firstNonDbg(std::next(BB->begin())) == TI && CI->getCalledFunction() &&
483  !TTI->isLoweredToCall(CI->getCalledFunction())) {
484  // A single-block function with just a call and a return. Check that
485  // the arguments match.
487  E = CallSite(CI).arg_end();
489  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 
500  CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry,
501  bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
503  // If we are introducing accumulator recursion to eliminate operations after
504  // the call instruction that are both associative and commutative, the initial
505  // value for the accumulator is placed in this variable. If this value is set
506  // then we actually perform accumulator recursion elimination instead of
507  // simple tail recursion elimination. If the operation is an LLVM instruction
508  // (eg: "add") then it is recorded in AccumulatorRecursionInstr. If not, then
509  // we are handling the case when the return instruction returns a constant C
510  // which is different to the constant returned by other return instructions
511  // (which is recorded in AccumulatorRecursionEliminationInitVal). This is a
512  // special case of accumulator recursion, the operation being "return C".
513  Value *AccumulatorRecursionEliminationInitVal = nullptr;
514  Instruction *AccumulatorRecursionInstr = nullptr;
515 
516  // Ok, we found a potential tail call. We can currently only transform the
517  // tail call if all of the instructions between the call and the return are
518  // movable to above the call itself, leaving the call next to the return.
519  // Check that this is the case now.
520  BasicBlock::iterator BBI(CI);
521  for (++BBI; &*BBI != Ret; ++BBI) {
522  if (canMoveAboveCall(&*BBI, CI, AA))
523  continue;
524 
525  // If we can't move the instruction above the call, it might be because it
526  // is an associative and commutative operation that could be transformed
527  // using accumulator recursion elimination. Check to see if this is the
528  // case, and if so, remember the initial accumulator value for later.
529  if ((AccumulatorRecursionEliminationInitVal =
530  canTransformAccumulatorRecursion(&*BBI, CI))) {
531  // Yes, this is accumulator recursion. Remember which instruction
532  // accumulates.
533  AccumulatorRecursionInstr = &*BBI;
534  } else {
535  return false; // Otherwise, we cannot eliminate the tail recursion!
536  }
537  }
538 
539  // We can only transform call/return pairs that either ignore the return value
540  // of the call and return void, ignore the value of the call and return a
541  // constant, return the value returned by the tail call, or that are being
542  // accumulator recursion variable eliminated.
543  if (Ret->getNumOperands() == 1 && Ret->getReturnValue() != CI &&
544  !isa<UndefValue>(Ret->getReturnValue()) &&
545  AccumulatorRecursionEliminationInitVal == nullptr &&
546  !getCommonReturnValue(nullptr, CI)) {
547  // One case remains that we are able to handle: the current return
548  // instruction returns a constant, and all other return instructions
549  // return a different constant.
550  if (!isDynamicConstant(Ret->getReturnValue(), CI, Ret))
551  return false; // Current return instruction does not return a constant.
552  // Check that all other return instructions return a common constant. If
553  // so, record it in AccumulatorRecursionEliminationInitVal.
554  AccumulatorRecursionEliminationInitVal = getCommonReturnValue(Ret, CI);
555  if (!AccumulatorRecursionEliminationInitVal)
556  return false;
557  }
558 
559  BasicBlock *BB = Ret->getParent();
560  Function *F = BB->getParent();
561 
562  using namespace ore;
563  ORE->emit([&]() {
564  return OptimizationRemark(DEBUG_TYPE, "tailcall-recursion", CI)
565  << "transforming tail recursion into loop";
566  });
567 
568  // OK! We can transform this tail call. If this is the first one found,
569  // create the new entry block, allowing us to branch back to the old entry.
570  if (!OldEntry) {
571  OldEntry = &F->getEntryBlock();
572  BasicBlock *NewEntry = BasicBlock::Create(F->getContext(), "", F, OldEntry);
573  NewEntry->takeName(OldEntry);
574  OldEntry->setName("tailrecurse");
575  BranchInst *BI = BranchInst::Create(OldEntry, NewEntry);
576  BI->setDebugLoc(CI->getDebugLoc());
577 
578  // If this tail call is marked 'tail' and if there are any allocas in the
579  // entry block, move them up to the new entry block.
580  TailCallsAreMarkedTail = CI->isTailCall();
581  if (TailCallsAreMarkedTail)
582  // Move all fixed sized allocas from OldEntry to NewEntry.
583  for (BasicBlock::iterator OEBI = OldEntry->begin(), E = OldEntry->end(),
584  NEBI = NewEntry->begin(); OEBI != E; )
585  if (AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++))
586  if (isa<ConstantInt>(AI->getArraySize()))
587  AI->moveBefore(&*NEBI);
588 
589  // Now that we have created a new block, which jumps to the entry
590  // block, insert a PHI node for each argument of the function.
591  // For now, we initialize each PHI to only have the real arguments
592  // which are passed in.
593  Instruction *InsertPos = &OldEntry->front();
594  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
595  I != E; ++I) {
596  PHINode *PN = PHINode::Create(I->getType(), 2,
597  I->getName() + ".tr", InsertPos);
598  I->replaceAllUsesWith(PN); // Everyone use the PHI node now!
599  PN->addIncoming(&*I, NewEntry);
600  ArgumentPHIs.push_back(PN);
601  }
602  // The entry block was changed from OldEntry to NewEntry.
603  // The forward DominatorTree needs to be recalculated when the EntryBB is
604  // changed. In this corner-case we recalculate the entire tree.
605  DTU.recalculate(*NewEntry->getParent());
606  }
607 
608  // If this function has self recursive calls in the tail position where some
609  // are marked tail and some are not, only transform one flavor or another. We
610  // have to choose whether we move allocas in the entry block to the new entry
611  // block or not, so we can't make a good choice for both. NOTE: We could do
612  // slightly better here in the case that the function has no entry block
613  // allocas.
614  if (TailCallsAreMarkedTail && !CI->isTailCall())
615  return false;
616 
617  // Ok, now that we know we have a pseudo-entry block WITH all of the
618  // required PHI nodes, add entries into the PHI node for the actual
619  // parameters passed into the tail-recursive call.
620  for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i)
621  ArgumentPHIs[i]->addIncoming(CI->getArgOperand(i), BB);
622 
623  // If we are introducing an accumulator variable to eliminate the recursion,
624  // do so now. Note that we _know_ that no subsequent tail recursion
625  // eliminations will happen on this function because of the way the
626  // accumulator recursion predicate is set up.
627  //
628  if (AccumulatorRecursionEliminationInitVal) {
629  Instruction *AccRecInstr = AccumulatorRecursionInstr;
630  // Start by inserting a new PHI node for the accumulator.
631  pred_iterator PB = pred_begin(OldEntry), PE = pred_end(OldEntry);
632  PHINode *AccPN = PHINode::Create(
633  AccumulatorRecursionEliminationInitVal->getType(),
634  std::distance(PB, PE) + 1, "accumulator.tr", &OldEntry->front());
635 
636  // Loop over all of the predecessors of the tail recursion block. For the
637  // real entry into the function we seed the PHI with the initial value,
638  // computed earlier. For any other existing branches to this block (due to
639  // other tail recursions eliminated) the accumulator is not modified.
640  // Because we haven't added the branch in the current block to OldEntry yet,
641  // it will not show up as a predecessor.
642  for (pred_iterator PI = PB; PI != PE; ++PI) {
643  BasicBlock *P = *PI;
644  if (P == &F->getEntryBlock())
645  AccPN->addIncoming(AccumulatorRecursionEliminationInitVal, P);
646  else
647  AccPN->addIncoming(AccPN, P);
648  }
649 
650  if (AccRecInstr) {
651  // Add an incoming argument for the current block, which is computed by
652  // our associative and commutative accumulator instruction.
653  AccPN->addIncoming(AccRecInstr, BB);
654 
655  // Next, rewrite the accumulator recursion instruction so that it does not
656  // use the result of the call anymore, instead, use the PHI node we just
657  // inserted.
658  AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN);
659  } else {
660  // Add an incoming argument for the current block, which is just the
661  // constant returned by the current return instruction.
662  AccPN->addIncoming(Ret->getReturnValue(), BB);
663  }
664 
665  // Finally, rewrite any return instructions in the program to return the PHI
666  // node instead of the "initval" that they do currently. This loop will
667  // actually rewrite the return value we are destroying, but that's ok.
668  for (BasicBlock &BBI : *F)
669  if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator()))
670  RI->setOperand(0, AccPN);
671  ++NumAccumAdded;
672  }
673 
674  // Now that all of the PHI nodes are in place, remove the call and
675  // ret instructions, replacing them with an unconditional branch.
676  BranchInst *NewBI = BranchInst::Create(OldEntry, Ret);
677  NewBI->setDebugLoc(CI->getDebugLoc());
678 
679  BB->getInstList().erase(Ret); // Remove return.
680  BB->getInstList().erase(CI); // Remove call.
681  DTU.applyUpdates({{DominatorTree::Insert, BB, OldEntry}});
682  ++NumEliminated;
683  return true;
684 }
685 
687  BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry,
688  bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
689  bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
691  bool Change = false;
692 
693  // Make sure this block is a trivial return block.
694  assert(BB->getFirstNonPHIOrDbg() == Ret &&
695  "Trying to fold non-trivial return block");
696 
697  // If the return block contains nothing but the return and PHI's,
698  // there might be an opportunity to duplicate the return in its
699  // predecessors and perform TRE there. Look for predecessors that end
700  // in unconditional branch and recursive call(s).
701  SmallVector<BranchInst*, 8> UncondBranchPreds;
702  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
703  BasicBlock *Pred = *PI;
704  Instruction *PTI = Pred->getTerminator();
705  if (BranchInst *BI = dyn_cast<BranchInst>(PTI))
706  if (BI->isUnconditional())
707  UncondBranchPreds.push_back(BI);
708  }
709 
710  while (!UncondBranchPreds.empty()) {
711  BranchInst *BI = UncondBranchPreds.pop_back_val();
712  BasicBlock *Pred = BI->getParent();
713  if (CallInst *CI = findTRECandidate(BI, CannotTailCallElimCallsMarkedTail, TTI)){
714  LLVM_DEBUG(dbgs() << "FOLDING: " << *BB
715  << "INTO UNCOND BRANCH PRED: " << *Pred);
716  ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred, &DTU);
717 
718  // Cleanup: if all predecessors of BB have been eliminated by
719  // FoldReturnIntoUncondBranch, delete it. It is important to empty it,
720  // because the ret instruction in there is still using a value which
721  // eliminateRecursiveTailCall will attempt to remove.
722  if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
723  DTU.deleteBB(BB);
724 
725  eliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail,
726  ArgumentPHIs, AA, ORE, DTU);
727  ++NumRetDuped;
728  Change = true;
729  }
730  }
731 
732  return Change;
733 }
734 
736  ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail,
737  SmallVectorImpl<PHINode *> &ArgumentPHIs,
738  bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
740  CallInst *CI = findTRECandidate(Ret, CannotTailCallElimCallsMarkedTail, TTI);
741  if (!CI)
742  return false;
743 
744  return eliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail,
745  ArgumentPHIs, AA, ORE, DTU);
746 }
747 
749  AliasAnalysis *AA,
751  DomTreeUpdater &DTU) {
752  if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true")
753  return false;
754 
755  bool MadeChange = false;
756  bool AllCallsAreTailCalls = false;
757  MadeChange |= markTails(F, AllCallsAreTailCalls, ORE);
758  if (!AllCallsAreTailCalls)
759  return MadeChange;
760 
761  // If this function is a varargs function, we won't be able to PHI the args
762  // right, so don't even try to convert it...
763  if (F.getFunctionType()->isVarArg())
764  return false;
765 
766  BasicBlock *OldEntry = nullptr;
767  bool TailCallsAreMarkedTail = false;
768  SmallVector<PHINode*, 8> ArgumentPHIs;
769 
770  // If false, we cannot perform TRE on tail calls marked with the 'tail'
771  // attribute, because doing so would cause the stack size to increase (real
772  // TRE would deallocate variable sized allocas, TRE doesn't).
773  bool CanTRETailMarkedCall = canTRE(F);
774 
775  // Change any tail recursive calls to loops.
776  //
777  // FIXME: The code generator produces really bad code when an 'escaping
778  // alloca' is changed from being a static alloca to being a dynamic alloca.
779  // Until this is resolved, disable this transformation if that would ever
780  // happen. This bug is PR962.
781  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) {
782  BasicBlock *BB = &*BBI++; // foldReturnAndProcessPred may delete BB.
783  if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) {
784  bool Change = processReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail,
785  ArgumentPHIs, !CanTRETailMarkedCall,
786  TTI, AA, ORE, DTU);
787  if (!Change && BB->getFirstNonPHIOrDbg() == Ret)
788  Change = foldReturnAndProcessPred(
789  BB, Ret, OldEntry, TailCallsAreMarkedTail, ArgumentPHIs,
790  !CanTRETailMarkedCall, TTI, AA, ORE, DTU);
791  MadeChange |= Change;
792  }
793  }
794 
795  // If we eliminated any tail recursions, it's possible that we inserted some
796  // silly PHI nodes which just merge an initial value (the incoming operand)
797  // with themselves. Check to see if we did and clean up our mess if so. This
798  // occurs when a function passes an argument straight through to its tail
799  // call.
800  for (PHINode *PN : ArgumentPHIs) {
801  // If the PHI Node is a dynamic constant, replace it with the value it is.
802  if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) {
803  PN->replaceAllUsesWith(PNV);
804  PN->eraseFromParent();
805  }
806  }
807 
808  return MadeChange;
809 }
810 
811 namespace {
812 struct TailCallElim : public FunctionPass {
813  static char ID; // Pass identification, replacement for typeid
814  TailCallElim() : FunctionPass(ID) {
816  }
817 
818  void getAnalysisUsage(AnalysisUsage &AU) const override {
825  }
826 
827  bool runOnFunction(Function &F) override {
828  if (skipFunction(F))
829  return false;
830 
831  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
832  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
833  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
834  auto *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
835  // There is no noticable performance difference here between Lazy and Eager
836  // UpdateStrategy based on some test results. It is feasible to switch the
837  // UpdateStrategy to Lazy if we find it profitable later.
839 
840  return eliminateTailRecursion(
841  F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
842  &getAnalysis<AAResultsWrapperPass>().getAAResults(),
843  &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU);
844  }
845 };
846 }
847 
848 char TailCallElim::ID = 0;
849 INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",
850  false, false)
853 INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination",
854  false, false)
855 
856 // Public interface to the TailCallElimination pass
858  return new TailCallElim();
859 }
860 
863 
865  AliasAnalysis &AA = AM.getResult<AAManager>(F);
867  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
869  // There is no noticable performance difference here between Lazy and Eager
870  // UpdateStrategy based on some test results. It is feasible to switch the
871  // UpdateStrategy to Lazy if we find it profitable later.
873  bool Changed = eliminateTailRecursion(F, &TTI, &AA, &ORE, DTU);
874 
875  if (!Changed)
876  return PreservedAnalyses::all();
878  PA.preserve<GlobalsAA>();
881  return PA;
882 }
Legacy wrapper pass to provide the GlobalsAAResult object.
IterTy arg_end() const
Definition: CallSite.h:588
bool hasOperandBundles() const
Return true if this User has any operand bundles.
Definition: InstrTypes.h:1733
Return a value (possibly void), from a function.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
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:29
bool doesNotAccessMemory(unsigned OpNo) const
Definition: InstrTypes.h:1551
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
iterator erase(iterator where)
Definition: ilist.h:265
IterTy arg_begin() const
Definition: CallSite.h:584
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
iterator end()
Definition: Function.h:682
bool isDataOperand(Value::const_user_iterator UI) const
Determine whether the passed iterator points to a data operand.
Definition: CallSite.h:184
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool isSafeToLoadUnconditionally(Value *V, unsigned Align, APInt &Size, 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:262
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:1165
arg_iterator arg_end()
Definition: Function.h:704
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
unsigned getDataOperandNo(Value::const_user_iterator UI) const
Given a value use iterator, return the data operand corresponding to it.
Definition: CallSite.h:230
An instruction for reading from memory.
Definition: Instructions.h:167
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:137
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
Definition: CallSite.h:602
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1241
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
unsigned getArgumentNo(Value::const_user_iterator I) const
Given a value use iterator, returns the argument that corresponds to it.
Definition: CallSite.h:206
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
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:102
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...
InstrTy * getInstruction() const
Definition: CallSite.h:96
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:246
bool isVarArg() const
Definition: DerivedTypes.h:123
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
iterator_range< User::op_iterator > arg_operands()
Definition: InstrTypes.h:1233
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
iterator begin()
Definition: Function.h:680
bool onlyReadsMemory() const
Determine if the call does not access or only reads memory.
Definition: CallSite.h:467
Value * getOperand(unsigned i) const
Definition: User.h:169
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
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:664
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:153
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:328
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:280
#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:370
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:582
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:112
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:284
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
op_range operands()
Definition: User.h:237
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:99
arg_iterator arg_begin()
Definition: Function.h:695
self_iterator getIterator()
Definition: ilist_node.h:81
Tail Call Elimination
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:205
void setTailCall(bool isTC=true)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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:391
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:333
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
bool isArgOperand(Value::const_user_iterator UI) const
Determine whether the passed iterator points to an argument operand.
Definition: CallSite.h:158
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
iterator end()
Definition: BasicBlock.h:270
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
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:63
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
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...
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:220
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:498
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:163
void initializeTailCallElimPass(PassRegistry &)
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
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)
Notify DTU that the entry block was replaced.
unsigned getNumArgOperands() const
Definition: InstrTypes.h:1239
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:331
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getValueAsString() const
Return the attribute&#39;s value as a string.
Definition: Attributes.cpp:223
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1287
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#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:795
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:332
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
bool callsFunctionThatReturnsTwice() const
callsFunctionThatReturnsTwice - Return true if the function has a call to setjmp or other function th...
Definition: Function.cpp:1396
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.
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
Definition: CallSite.h:607
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
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.
Attribute getFnAttribute(Attribute::AttrKind Kind) const
Return the attribute for the given attribute kind.
Definition: Function.h:333
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:432
bool isNoTailCall() const
inst_range instructions(Function *F)
Definition: InstIterator.h:133
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:196
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
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...
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
static bool markTails(Function &F, bool &AllCallsAreTailCalls, OptimizationRemarkEmitter *ORE)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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:719
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:59
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:1224