Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
Line
Count
Source (jump to first uncovered line)
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
52
#include "llvm/Transforms/Scalar/TailRecursionElimination.h"
53
#include "llvm/ADT/STLExtras.h"
54
#include "llvm/ADT/SmallPtrSet.h"
55
#include "llvm/ADT/Statistic.h"
56
#include "llvm/Analysis/CFG.h"
57
#include "llvm/Analysis/CaptureTracking.h"
58
#include "llvm/Analysis/DomTreeUpdater.h"
59
#include "llvm/Analysis/GlobalsModRef.h"
60
#include "llvm/Analysis/InlineCost.h"
61
#include "llvm/Analysis/InstructionSimplify.h"
62
#include "llvm/Analysis/Loads.h"
63
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
64
#include "llvm/Analysis/PostDominators.h"
65
#include "llvm/Analysis/TargetTransformInfo.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"
81
#include "llvm/Support/raw_ostream.h"
82
#include "llvm/Transforms/Scalar.h"
83
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
84
using namespace llvm;
85
86
2
#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
427k
static bool canTRE(Function &F) {
95
427k
  // Because of PR962, we don't TRE dynamic allocas.
96
8.82M
  return llvm::all_of(instructions(F), [](Instruction &I) {
97
8.82M
    auto *AI = dyn_cast<AllocaInst>(&I);
98
8.82M
    return !AI || 
AI->isStaticAlloca()66
;
99
8.82M
  });
100
427k
}
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
83.9k
  void walk(Value *Root) {
108
83.9k
    SmallVector<Use *, 32> Worklist;
109
83.9k
    SmallPtrSet<Use *, 32> Visited;
110
83.9k
111
1.11M
    auto AddUsesToWorklist = [&](Value *V) {
112
1.90M
      for (auto &U : V->uses()) {
113
1.90M
        if (!Visited.insert(&U).second)
114
217k
          continue;
115
1.69M
        Worklist.push_back(&U);
116
1.69M
      }
117
1.11M
    };
118
83.9k
119
83.9k
    AddUsesToWorklist(Root);
120
83.9k
121
1.77M
    while (!Worklist.empty()) {
122
1.69M
      Use *U = Worklist.pop_back_val();
123
1.69M
      Instruction *I = cast<Instruction>(U->getUser());
124
1.69M
125
1.69M
      switch (I->getOpcode()) {
126
1.69M
      case Instruction::Call:
127
471k
      case Instruction::Invoke: {
128
471k
        CallSite CS(I);
129
471k
        // If the alloca-derived argument is passed byval it is not an escape
130
471k
        // point, or a use of an alloca. Calling with byval copies the contents
131
471k
        // of the alloca into argument registers or stack slots, which exist
132
471k
        // beyond the lifetime of the current frame.
133
471k
        if (CS.isArgOperand(U) && 
CS.isByValArgument(CS.getArgumentNo(U))471k
)
134
439
          continue;
135
470k
        bool IsNocapture =
136
470k
            CS.isDataOperand(U) && CS.doesNotCapture(CS.getDataOperandNo(U));
137
470k
        callUsesLocalStack(CS, IsNocapture);
138
470k
        if (IsNocapture) {
139
214k
          // If the alloca-derived argument is passed in as nocapture, then it
140
214k
          // can't propagate to the call's return. That would be capturing.
141
214k
          continue;
142
214k
        }
143
256k
        break;
144
256k
      }
145
256k
      case Instruction::Load: {
146
123k
        // The result of a load is not alloca-derived (unless an alloca has
147
123k
        // otherwise escaped, but this is a local analysis).
148
123k
        continue;
149
256k
      }
150
318k
      case Instruction::Store: {
151
318k
        if (U->getOperandNo() == 0)
152
13.1k
          EscapePoints.insert(I);
153
318k
        continue;  // Stores have no users to analyze.
154
256k
      }
155
599k
      case Instruction::BitCast:
156
599k
      case Instruction::GetElementPtr:
157
599k
      case Instruction::PHI:
158
599k
      case Instruction::Select:
159
599k
      case Instruction::AddrSpaceCast:
160
599k
        break;
161
599k
      default:
162
178k
        EscapePoints.insert(I);
163
178k
        break;
164
1.03M
      }
165
1.03M
166
1.03M
      AddUsesToWorklist(I);
167
1.03M
    }
168
83.9k
  }
169
170
470k
  void callUsesLocalStack(CallSite CS, bool IsNocapture) {
171
470k
    // Add it to the list of alloca users.
172
470k
    AllocaUsers.insert(CS.getInstruction());
173
470k
174
470k
    // If it's nocapture then it can't capture this alloca.
175
470k
    if (IsNocapture)
176
214k
      return;
177
256k
178
256k
    // If it can write to memory, it can leak the alloca value.
179
256k
    if (!CS.onlyReadsMemory())
180
256k
      EscapePoints.insert(CS.getInstruction());
181
256k
  }
182
183
  SmallPtrSet<Instruction *, 32> AllocaUsers;
184
  SmallPtrSet<Instruction *, 32> EscapePoints;
185
};
186
}
187
188
static bool markTails(Function &F, bool &AllCallsAreTailCalls,
189
466k
                      OptimizationRemarkEmitter *ORE) {
190
466k
  if (F.callsFunctionThatReturnsTwice())
191
29
    return false;
192
466k
  AllCallsAreTailCalls = true;
193
466k
194
466k
  // The local stack holds all alloca instructions and all byval arguments.
195
466k
  AllocaDerivedValueTracker Tracker;
196
954k
  for (Argument &Arg : F.args()) {
197
954k
    if (Arg.hasByValAttr())
198
452
      Tracker.walk(&Arg);
199
954k
  }
200
2.62M
  for (auto &BB : F) {
201
2.62M
    for (auto &I : BB)
202
14.2M
      if (AllocaInst *AI = dyn_cast<AllocaInst>(&I))
203
83.4k
        Tracker.walk(AI);
204
2.62M
  }
205
466k
206
466k
  bool Modified = false;
207
466k
208
466k
  // Track whether a block is reachable after an alloca has escaped. Blocks that
209
466k
  // contain the escaping instruction will be marked as being visited without an
210
466k
  // escaped alloca, since that is how the block began.
211
466k
  enum VisitType {
212
466k
    UNVISITED,
213
466k
    UNESCAPED,
214
466k
    ESCAPED
215
466k
  };
216
466k
  DenseMap<BasicBlock *, VisitType> Visited;
217
466k
218
466k
  // We propagate the fact that an alloca has escaped from block to successor.
219
466k
  // Visit the blocks that are propagating the escapedness first. To do this, we
220
466k
  // maintain two worklists.
221
466k
  SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped;
222
466k
223
466k
  // We may enter a block and visit it thinking that no alloca has escaped yet,
224
466k
  // then see an escape point and go back around a loop edge and come back to
225
466k
  // the same block twice. Because of this, we defer setting tail on calls when
226
466k
  // we first encounter them in a block. Every entry in this list does not
227
466k
  // statically use an alloca via use-def chain analysis, but may find an alloca
228
466k
  // through other means if the block turns out to be reachable after an escape
229
466k
  // point.
230
466k
  SmallVector<CallInst *, 32> DeferredTails;
231
466k
232
466k
  BasicBlock *BB = &F.getEntryBlock();
233
466k
  VisitType Escaped = UNESCAPED;
234
2.68M
  do {
235
14.5M
    for (auto &I : *BB) {
236
14.5M
      if (Tracker.EscapePoints.count(&I))
237
351k
        Escaped = ESCAPED;
238
14.5M
239
14.5M
      CallInst *CI = dyn_cast<CallInst>(&I);
240
14.5M
      if (!CI || 
CI->isTailCall()1.88M
||
isa<DbgInfoIntrinsic>(&I)1.15M
)
241
13.4M
        continue;
242
1.15M
243
1.15M
      bool IsNoTail = CI->isNoTailCall() || 
CI->hasOperandBundles()1.15M
;
244
1.15M
245
1.15M
      if (!IsNoTail && 
CI->doesNotAccessMemory()1.15M
) {
246
51.9k
        // A call to a readnone function whose arguments are all things computed
247
51.9k
        // outside this function can be marked tail. Even if you stored the
248
51.9k
        // alloca address into a global, a readnone function can't load the
249
51.9k
        // global anyhow.
250
51.9k
        //
251
51.9k
        // Note that this runs whether we know an alloca has escaped or not. If
252
51.9k
        // it has, then we can't trust Tracker.AllocaUsers to be accurate.
253
51.9k
        bool SafeToTail = true;
254
51.9k
        for (auto &Arg : CI->arg_operands()) {
255
51.8k
          if (isa<Constant>(Arg.getUser()))
256
0
            continue;
257
51.8k
          if (Argument *A = dyn_cast<Argument>(Arg.getUser()))
258
0
            if (!A->hasByValAttr())
259
0
              continue;
260
51.8k
          SafeToTail = false;
261
51.8k
          break;
262
51.8k
        }
263
51.9k
        if (SafeToTail) {
264
65
          using namespace ore;
265
65
          ORE->emit([&]() {
266
0
            return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI)
267
0
                   << "marked as tail call candidate (readnone)";
268
0
          });
269
65
          CI->setTailCall();
270
65
          Modified = true;
271
65
          continue;
272
65
        }
273
1.15M
      }
274
1.15M
275
1.15M
      if (!IsNoTail && 
Escaped == UNESCAPED1.15M
&&
!Tracker.AllocaUsers.count(CI)652k
) {
276
555k
        DeferredTails.push_back(CI);
277
597k
      } else {
278
597k
        AllCallsAreTailCalls = false;
279
597k
      }
280
1.15M
    }
281
2.68M
282
3.49M
    for (auto *SuccBB : make_range(succ_begin(BB), succ_end(BB))) {
283
3.49M
      auto &State = Visited[SuccBB];
284
3.49M
      if (State < Escaped) {
285
2.23M
        State = Escaped;
286
2.23M
        if (State == ESCAPED)
287
515k
          WorklistEscaped.push_back(SuccBB);
288
1.71M
        else
289
1.71M
          WorklistUnescaped.push_back(SuccBB);
290
2.23M
      }
291
3.49M
    }
292
2.68M
293
2.68M
    if (!WorklistEscaped.empty()) {
294
515k
      BB = WorklistEscaped.pop_back_val();
295
515k
      Escaped = ESCAPED;
296
2.16M
    } else {
297
2.16M
      BB = nullptr;
298
2.18M
      while (!WorklistUnescaped.empty()) {
299
1.71M
        auto *NextBB = WorklistUnescaped.pop_back_val();
300
1.71M
        if (Visited[NextBB] == UNESCAPED) {
301
1.69M
          BB = NextBB;
302
1.69M
          Escaped = UNESCAPED;
303
1.69M
          break;
304
1.69M
        }
305
1.71M
      }
306
2.16M
    }
307
2.68M
  } while (BB);
308
466k
309
555k
  for (CallInst *CI : DeferredTails) {
310
555k
    if (Visited[CI->getParent()] != ESCAPED) {
311
534k
      // If the escape point was part way through the block, calls after the
312
534k
      // escape point wouldn't have been put into DeferredTails.
313
534k
      LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n");
314
534k
      CI->setTailCall();
315
534k
      Modified = true;
316
534k
    } else {
317
21.2k
      AllCallsAreTailCalls = false;
318
21.2k
    }
319
555k
  }
320
466k
321
466k
  return Modified;
322
466k
}
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
///
328
250
static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA) {
329
250
  // FIXME: We can move load/store/call/free instructions above the call if the
330
250
  // call does not mod/ref the memory location being processed.
331
250
  if (I->mayHaveSideEffects())  // This also handles volatile loads.
332
101
    return false;
333
149
334
149
  if (LoadInst *L = dyn_cast<LoadInst>(I)) {
335
22
    // Loads may always be moved above calls without side effects.
336
22
    if (CI->mayHaveSideEffects()) {
337
19
      // Non-volatile loads may be moved above a call with side effects if it
338
19
      // does not write to memory and the load provably won't trap.
339
19
      // Writes to memory only matter if they may alias the pointer
340
19
      // being loaded from.
341
19
      const DataLayout &DL = L->getModule()->getDataLayout();
342
19
      if (isModSet(AA->getModRefInfo(CI, MemoryLocation::get(L))) ||
343
19
          !isSafeToLoadUnconditionally(L->getPointerOperand(), L->getType(),
344
6
                                       L->getAlignment(), DL, L))
345
15
        return false;
346
134
    }
347
22
  }
348
134
349
134
  // Otherwise, if this is a side-effect free instruction, check to make sure
350
134
  // that it does not use the return value of the call.  If it doesn't use the
351
134
  // return value of the call, it must only use things that are defined before
352
134
  // the call, or movable instructions between the call and the instruction
353
134
  // itself.
354
134
  return !is_contained(I->operands(), CI);
355
134
}
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
57
static bool isDynamicConstant(Value *V, CallInst *CI, ReturnInst *RI) {
363
57
  if (isa<Constant>(V)) 
return true35
; // Static constants are always dyn consts
364
22
365
22
  // Check to see if this is an immutable argument, if so, the value
366
22
  // will be available to initialize the accumulator.
367
22
  if (Argument *Arg = dyn_cast<Argument>(V)) {
368
4
    // Figure out which argument number this is...
369
4
    unsigned ArgNo = 0;
370
4
    Function *F = CI->getParent()->getParent();
371
4
    for (Function::arg_iterator AI = F->arg_begin(); &*AI != Arg; 
++AI0
)
372
0
      ++ArgNo;
373
4
374
4
    // If we are passing this argument into call as the corresponding
375
4
    // argument operand, then the argument is dynamically constant.
376
4
    // Otherwise, we cannot transform this function safely.
377
4
    if (CI->getArgOperand(ArgNo) == Arg)
378
2
      return true;
379
20
  }
380
20
381
20
  // Switch cases are always constant integers. If the value is being switched
382
20
  // on and the return is only reachable from one of its cases, it's
383
20
  // effectively constant.
384
20
  if (BasicBlock *UniquePred = RI->getParent()->getUniquePredecessor())
385
10
    if (SwitchInst *SI = dyn_cast<SwitchInst>(UniquePred->getTerminator()))
386
2
      if (SI->getCondition() == V)
387
2
        return SI->getDefaultDest() != RI->getParent();
388
18
389
18
  // Not a constant or immutable argument, we can't safely transform.
390
18
  return false;
391
18
}
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.
396
42
static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) {
397
42
  Function *F = CI->getParent()->getParent();
398
42
  Value *ReturnedValue = nullptr;
399
42
400
500
  for (BasicBlock &BBI : *F) {
401
500
    ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator());
402
500
    if (RI == nullptr || 
RI == IgnoreRI81
)
continue450
;
403
50
404
50
    // We can only perform this transformation if the value returned is
405
50
    // evaluatable at the start of the initial invocation of the function,
406
50
    // instead of at the end of the evaluation.
407
50
    //
408
50
    Value *RetOp = RI->getOperand(0);
409
50
    if (!isDynamicConstant(RetOp, CI, RI))
410
14
      return nullptr;
411
36
412
36
    if (ReturnedValue && 
RetOp != ReturnedValue5
)
413
1
      return nullptr;     // Cannot transform if differing values are returned.
414
35
    ReturnedValue = RetOp;
415
35
  }
416
42
  
return ReturnedValue27
;
417
42
}
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.
422
175
static Value *canTransformAccumulatorRecursion(Instruction *I, CallInst *CI) {
423
175
  if (!I->isAssociative() || 
!I->isCommutative()29
)
return nullptr146
;
424
29
  assert(I->getNumOperands() == 2 &&
425
29
         "Associative/commutative operations should have 2 args!");
426
29
427
29
  // Exactly one operand should be the result of the call instruction.
428
29
  if ((I->getOperand(0) == CI && 
I->getOperand(1) == CI11
) ||
429
29
      (I->getOperand(0) != CI && 
I->getOperand(1) != CI18
))
430
0
    return nullptr;
431
29
432
29
  // The only user of this instruction we allow is a single return instruction.
433
29
  if (!I->hasOneUse() || !isa<ReturnInst>(I->user_back()))
434
1
    return nullptr;
435
28
436
28
  // Ok, now we have to check all of the other return instructions in this
437
28
  // function.  If they return non-constants or differing values, then we cannot
438
28
  // transform the function safely.
439
28
  return getCommonReturnValue(cast<ReturnInst>(I->user_back()), CI);
440
28
}
441
442
10
static Instruction *firstNonDbg(BasicBlock::iterator I) {
443
10
  while (isa<DbgInfoIntrinsic>(I))
444
0
    ++I;
445
10
  return &*I;
446
10
}
447
448
static CallInst *findTRECandidate(Instruction *TI,
449
                                  bool CannotTailCallElimCallsMarkedTail,
450
639k
                                  const TargetTransformInfo *TTI) {
451
639k
  BasicBlock *BB = TI->getParent();
452
639k
  Function *F = BB->getParent();
453
639k
454
639k
  if (&BB->front() == TI) // Make sure there is something before the terminator.
455
100k
    return nullptr;
456
538k
457
538k
  // Scan backwards from the return, checking to see if there is a tail call in
458
538k
  // this block.  If so, set CI to it.
459
538k
  CallInst *CI = nullptr;
460
538k
  BasicBlock::iterator BBI(TI);
461
2.88M
  while (true) {
462
2.88M
    CI = dyn_cast<CallInst>(BBI);
463
2.88M
    if (CI && 
CI->getCalledFunction() == F652k
)
464
443
      break;
465
2.88M
466
2.88M
    if (BBI == BB->begin())
467
538k
      return nullptr;          // Didn't find a potential tail call.
468
2.35M
    --BBI;
469
2.35M
  }
470
538k
471
538k
  // If this call is marked as a tail call, and if there are dynamic allocas in
472
538k
  // the function, we cannot perform this optimization.
473
538k
  
if (443
CI->isTailCall()443
&&
CannotTailCallElimCallsMarkedTail443
)
474
0
    return nullptr;
475
443
476
443
  // As a special case, detect code like this:
477
443
  //   double fabs(double f) { return __builtin_fabs(f); } // a 'fabs' call
478
443
  // and disable this xform in this case, because the code generator will
479
443
  // lower the call to fabs into inline code.
480
443
  if (BB == &F->getEntryBlock() &&
481
443
      
firstNonDbg(BB->front().getIterator()) == CI6
&&
482
443
      
firstNonDbg(std::next(BB->begin())) == TI4
&&
CI->getCalledFunction()4
&&
483
443
      
!TTI->isLoweredToCall(CI->getCalledFunction())4
) {
484
2
    // A single-block function with just a call and a return. Check that
485
2
    // the arguments match.
486
2
    CallSite::arg_iterator I = CallSite(CI).arg_begin(),
487
2
                           E = CallSite(CI).arg_end();
488
2
    Function::arg_iterator FI = F->arg_begin(),
489
2
                           FE = F->arg_end();
490
3
    for (; I != E && 
FI != FE2
;
++I, ++FI1
)
491
2
      if (*I != &*FI) 
break1
;
492
2
    if (I == E && 
FI == FE1
)
493
1
      return nullptr;
494
442
  }
495
442
496
442
  return CI;
497
442
}
498
499
static bool eliminateRecursiveTailCall(
500
    CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry,
501
    bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
502
442
    AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
503
442
  // If we are introducing accumulator recursion to eliminate operations after
504
442
  // the call instruction that are both associative and commutative, the initial
505
442
  // value for the accumulator is placed in this variable.  If this value is set
506
442
  // then we actually perform accumulator recursion elimination instead of
507
442
  // simple tail recursion elimination.  If the operation is an LLVM instruction
508
442
  // (eg: "add") then it is recorded in AccumulatorRecursionInstr.  If not, then
509
442
  // we are handling the case when the return instruction returns a constant C
510
442
  // which is different to the constant returned by other return instructions
511
442
  // (which is recorded in AccumulatorRecursionEliminationInitVal).  This is a
512
442
  // special case of accumulator recursion, the operation being "return C".
513
442
  Value *AccumulatorRecursionEliminationInitVal = nullptr;
514
442
  Instruction *AccumulatorRecursionInstr = nullptr;
515
442
516
442
  // Ok, we found a potential tail call.  We can currently only transform the
517
442
  // tail call if all of the instructions between the call and the return are
518
442
  // movable to above the call itself, leaving the call next to the return.
519
442
  // Check that this is the case now.
520
442
  BasicBlock::iterator BBI(CI);
521
539
  for (++BBI; &*BBI != Ret; 
++BBI97
) {
522
250
    if (canMoveAboveCall(&*BBI, CI, AA))
523
75
      continue;
524
175
525
175
    // If we can't move the instruction above the call, it might be because it
526
175
    // is an associative and commutative operation that could be transformed
527
175
    // using accumulator recursion elimination.  Check to see if this is the
528
175
    // case, and if so, remember the initial accumulator value for later.
529
175
    if ((AccumulatorRecursionEliminationInitVal =
530
175
             canTransformAccumulatorRecursion(&*BBI, CI))) {
531
22
      // Yes, this is accumulator recursion.  Remember which instruction
532
22
      // accumulates.
533
22
      AccumulatorRecursionInstr = &*BBI;
534
153
    } else {
535
153
      return false;   // Otherwise, we cannot eliminate the tail recursion!
536
153
    }
537
175
  }
538
442
539
442
  // We can only transform call/return pairs that either ignore the return value
540
442
  // of the call and return void, ignore the value of the call and return a
541
442
  // constant, return the value returned by the tail call, or that are being
542
442
  // accumulator recursion variable eliminated.
543
442
  
if (289
Ret->getNumOperands() == 1289
&&
Ret->getReturnValue() != CI188
&&
544
289
      
!isa<UndefValue>(Ret->getReturnValue())36
&&
545
289
      
AccumulatorRecursionEliminationInitVal == nullptr33
&&
546
289
      
!getCommonReturnValue(nullptr, CI)11
) {
547
7
    // One case remains that we are able to handle: the current return
548
7
    // instruction returns a constant, and all other return instructions
549
7
    // return a different constant.
550
7
    if (!isDynamicConstant(Ret->getReturnValue(), CI, Ret))
551
4
      return false; // Current return instruction does not return a constant.
552
3
    // Check that all other return instructions return a common constant.  If
553
3
    // so, record it in AccumulatorRecursionEliminationInitVal.
554
3
    AccumulatorRecursionEliminationInitVal = getCommonReturnValue(Ret, CI);
555
3
    if (!AccumulatorRecursionEliminationInitVal)
556
2
      return false;
557
283
  }
558
283
559
283
  BasicBlock *BB = Ret->getParent();
560
283
  Function *F = BB->getParent();
561
283
562
283
  using namespace ore;
563
283
  ORE->emit([&]() {
564
2
    return OptimizationRemark(DEBUG_TYPE, "tailcall-recursion", CI)
565
2
           << "transforming tail recursion into loop";
566
2
  });
567
283
568
283
  // OK! We can transform this tail call.  If this is the first one found,
569
283
  // create the new entry block, allowing us to branch back to the old entry.
570
283
  if (!OldEntry) {
571
227
    OldEntry = &F->getEntryBlock();
572
227
    BasicBlock *NewEntry = BasicBlock::Create(F->getContext(), "", F, OldEntry);
573
227
    NewEntry->takeName(OldEntry);
574
227
    OldEntry->setName("tailrecurse");
575
227
    BranchInst *BI = BranchInst::Create(OldEntry, NewEntry);
576
227
    BI->setDebugLoc(CI->getDebugLoc());
577
227
578
227
    // If this tail call is marked 'tail' and if there are any allocas in the
579
227
    // entry block, move them up to the new entry block.
580
227
    TailCallsAreMarkedTail = CI->isTailCall();
581
227
    if (TailCallsAreMarkedTail)
582
227
      // Move all fixed sized allocas from OldEntry to NewEntry.
583
227
      for (BasicBlock::iterator OEBI = OldEntry->begin(), E = OldEntry->end(),
584
1.28k
             NEBI = NewEntry->begin(); OEBI != E; )
585
1.06k
        if (AllocaInst *AI = dyn_cast<AllocaInst>(OEBI++))
586
1
          if (isa<ConstantInt>(AI->getArraySize()))
587
1
            AI->moveBefore(&*NEBI);
588
227
589
227
    // Now that we have created a new block, which jumps to the entry
590
227
    // block, insert a PHI node for each argument of the function.
591
227
    // For now, we initialize each PHI to only have the real arguments
592
227
    // which are passed in.
593
227
    Instruction *InsertPos = &OldEntry->front();
594
227
    for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
595
713
         I != E; 
++I486
) {
596
486
      PHINode *PN = PHINode::Create(I->getType(), 2,
597
486
                                    I->getName() + ".tr", InsertPos);
598
486
      I->replaceAllUsesWith(PN); // Everyone use the PHI node now!
599
486
      PN->addIncoming(&*I, NewEntry);
600
486
      ArgumentPHIs.push_back(PN);
601
486
    }
602
227
    // The entry block was changed from OldEntry to NewEntry.
603
227
    // The forward DominatorTree needs to be recalculated when the EntryBB is
604
227
    // changed. In this corner-case we recalculate the entire tree.
605
227
    DTU.recalculate(*NewEntry->getParent());
606
227
  }
607
283
608
283
  // If this function has self recursive calls in the tail position where some
609
283
  // are marked tail and some are not, only transform one flavor or another.  We
610
283
  // have to choose whether we move allocas in the entry block to the new entry
611
283
  // block or not, so we can't make a good choice for both.  NOTE: We could do
612
283
  // slightly better here in the case that the function has no entry block
613
283
  // allocas.
614
283
  if (TailCallsAreMarkedTail && !CI->isTailCall())
615
0
    return false;
616
283
617
283
  // Ok, now that we know we have a pseudo-entry block WITH all of the
618
283
  // required PHI nodes, add entries into the PHI node for the actual
619
283
  // parameters passed into the tail-recursive call.
620
950
  
for (unsigned i = 0, e = CI->getNumArgOperands(); 283
i != e;
++i667
)
621
667
    ArgumentPHIs[i]->addIncoming(CI->getArgOperand(i), BB);
622
283
623
283
  // If we are introducing an accumulator variable to eliminate the recursion,
624
283
  // do so now.  Note that we _know_ that no subsequent tail recursion
625
283
  // eliminations will happen on this function because of the way the
626
283
  // accumulator recursion predicate is set up.
627
283
  //
628
283
  if (AccumulatorRecursionEliminationInitVal) {
629
23
    Instruction *AccRecInstr = AccumulatorRecursionInstr;
630
23
    // Start by inserting a new PHI node for the accumulator.
631
23
    pred_iterator PB = pred_begin(OldEntry), PE = pred_end(OldEntry);
632
23
    PHINode *AccPN = PHINode::Create(
633
23
        AccumulatorRecursionEliminationInitVal->getType(),
634
23
        std::distance(PB, PE) + 1, "accumulator.tr", &OldEntry->front());
635
23
636
23
    // Loop over all of the predecessors of the tail recursion block.  For the
637
23
    // real entry into the function we seed the PHI with the initial value,
638
23
    // computed earlier.  For any other existing branches to this block (due to
639
23
    // other tail recursions eliminated) the accumulator is not modified.
640
23
    // Because we haven't added the branch in the current block to OldEntry yet,
641
23
    // it will not show up as a predecessor.
642
46
    for (pred_iterator PI = PB; PI != PE; 
++PI23
) {
643
23
      BasicBlock *P = *PI;
644
23
      if (P == &F->getEntryBlock())
645
23
        AccPN->addIncoming(AccumulatorRecursionEliminationInitVal, P);
646
0
      else
647
0
        AccPN->addIncoming(AccPN, P);
648
23
    }
649
23
650
23
    if (AccRecInstr) {
651
22
      // Add an incoming argument for the current block, which is computed by
652
22
      // our associative and commutative accumulator instruction.
653
22
      AccPN->addIncoming(AccRecInstr, BB);
654
22
655
22
      // Next, rewrite the accumulator recursion instruction so that it does not
656
22
      // use the result of the call anymore, instead, use the PHI node we just
657
22
      // inserted.
658
22
      AccRecInstr->setOperand(AccRecInstr->getOperand(0) != CI, AccPN);
659
22
    } else {
660
1
      // Add an incoming argument for the current block, which is just the
661
1
      // constant returned by the current return instruction.
662
1
      AccPN->addIncoming(Ret->getReturnValue(), BB);
663
1
    }
664
23
665
23
    // Finally, rewrite any return instructions in the program to return the PHI
666
23
    // node instead of the "initval" that they do currently.  This loop will
667
23
    // actually rewrite the return value we are destroying, but that's ok.
668
23
    for (BasicBlock &BBI : *F)
669
98
      if (ReturnInst *RI = dyn_cast<ReturnInst>(BBI.getTerminator()))
670
46
        RI->setOperand(0, AccPN);
671
23
    ++NumAccumAdded;
672
23
  }
673
283
674
283
  // Now that all of the PHI nodes are in place, remove the call and
675
283
  // ret instructions, replacing them with an unconditional branch.
676
283
  BranchInst *NewBI = BranchInst::Create(OldEntry, Ret);
677
283
  NewBI->setDebugLoc(CI->getDebugLoc());
678
283
679
283
  BB->getInstList().erase(Ret);  // Remove return.
680
283
  BB->getInstList().erase(CI);   // Remove call.
681
283
  DTU.applyUpdates({{DominatorTree::Insert, BB, OldEntry}});
682
283
  ++NumEliminated;
683
283
  return true;
684
283
}
685
686
static bool foldReturnAndProcessPred(
687
    BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry,
688
    bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
689
    bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
690
145k
    AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
691
145k
  bool Change = false;
692
145k
693
145k
  // Make sure this block is a trivial return block.
694
145k
  assert(BB->getFirstNonPHIOrDbg() == Ret &&
695
145k
         "Trying to fold non-trivial return block");
696
145k
697
145k
  // If the return block contains nothing but the return and PHI's,
698
145k
  // there might be an opportunity to duplicate the return in its
699
145k
  // predecessors and perform TRE there. Look for predecessors that end
700
145k
  // in unconditional branch and recursive call(s).
701
145k
  SmallVector<BranchInst*, 8> UncondBranchPreds;
702
535k
  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; 
++PI389k
) {
703
389k
    BasicBlock *Pred = *PI;
704
389k
    Instruction *PTI = Pred->getTerminator();
705
389k
    if (BranchInst *BI = dyn_cast<BranchInst>(PTI))
706
379k
      if (BI->isUnconditional())
707
211k
        UncondBranchPreds.push_back(BI);
708
389k
  }
709
145k
710
356k
  while (!UncondBranchPreds.empty()) {
711
211k
    BranchInst *BI = UncondBranchPreds.pop_back_val();
712
211k
    BasicBlock *Pred = BI->getParent();
713
211k
    if (CallInst *CI = findTRECandidate(BI, CannotTailCallElimCallsMarkedTail, TTI)){
714
418
      LLVM_DEBUG(dbgs() << "FOLDING: " << *BB
715
418
                        << "INTO UNCOND BRANCH PRED: " << *Pred);
716
418
      ReturnInst *RI = FoldReturnIntoUncondBranch(Ret, BB, Pred, &DTU);
717
418
718
418
      // Cleanup: if all predecessors of BB have been eliminated by
719
418
      // FoldReturnIntoUncondBranch, delete it.  It is important to empty it,
720
418
      // because the ret instruction in there is still using a value which
721
418
      // eliminateRecursiveTailCall will attempt to remove.
722
418
      if (!BB->hasAddressTaken() && pred_begin(BB) == pred_end(BB))
723
2
        DTU.deleteBB(BB);
724
418
725
418
      eliminateRecursiveTailCall(CI, RI, OldEntry, TailCallsAreMarkedTail,
726
418
                                 ArgumentPHIs, AA, ORE, DTU);
727
418
      ++NumRetDuped;
728
418
      Change = true;
729
418
    }
730
211k
  }
731
145k
732
145k
  return Change;
733
145k
}
734
735
static bool processReturningBlock(
736
    ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail,
737
    SmallVectorImpl<PHINode *> &ArgumentPHIs,
738
    bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
739
427k
    AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
740
427k
  CallInst *CI = findTRECandidate(Ret, CannotTailCallElimCallsMarkedTail, TTI);
741
427k
  if (!CI)
742
427k
    return false;
743
18
744
18
  return eliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail,
745
18
                                    ArgumentPHIs, AA, ORE, DTU);
746
18
}
747
748
static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI,
749
                                   AliasAnalysis *AA,
750
                                   OptimizationRemarkEmitter *ORE,
751
466k
                                   DomTreeUpdater &DTU) {
752
466k
  if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true")
753
11
    return false;
754
466k
755
466k
  bool MadeChange = false;
756
466k
  bool AllCallsAreTailCalls = false;
757
466k
  MadeChange |= markTails(F, AllCallsAreTailCalls, ORE);
758
466k
  if (!AllCallsAreTailCalls)
759
39.6k
    return MadeChange;
760
427k
761
427k
  // If this function is a varargs function, we won't be able to PHI the args
762
427k
  // right, so don't even try to convert it...
763
427k
  if (F.getFunctionType()->isVarArg())
764
24
    return false;
765
427k
766
427k
  BasicBlock *OldEntry = nullptr;
767
427k
  bool TailCallsAreMarkedTail = false;
768
427k
  SmallVector<PHINode*, 8> ArgumentPHIs;
769
427k
770
427k
  // If false, we cannot perform TRE on tail calls marked with the 'tail'
771
427k
  // attribute, because doing so would cause the stack size to increase (real
772
427k
  // TRE would deallocate variable sized allocas, TRE doesn't).
773
427k
  bool CanTRETailMarkedCall = canTRE(F);
774
427k
775
427k
  // Change any tail recursive calls to loops.
776
427k
  //
777
427k
  // FIXME: The code generator produces really bad code when an 'escaping
778
427k
  // alloca' is changed from being a static alloca to being a dynamic alloca.
779
427k
  // Until this is resolved, disable this transformation if that would ever
780
427k
  // happen.  This bug is PR962.
781
2.18M
  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) {
782
1.75M
    BasicBlock *BB = &*BBI++; // foldReturnAndProcessPred may delete BB.
783
1.75M
    if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) {
784
427k
      bool Change = processReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail,
785
427k
                                          ArgumentPHIs, !CanTRETailMarkedCall,
786
427k
                                          TTI, AA, ORE, DTU);
787
427k
      if (!Change && 
BB->getFirstNonPHIOrDbg() == Ret427k
)
788
145k
        Change = foldReturnAndProcessPred(
789
145k
            BB, Ret, OldEntry, TailCallsAreMarkedTail, ArgumentPHIs,
790
145k
            !CanTRETailMarkedCall, TTI, AA, ORE, DTU);
791
427k
      MadeChange |= Change;
792
427k
    }
793
1.75M
  }
794
427k
795
427k
  // If we eliminated any tail recursions, it's possible that we inserted some
796
427k
  // silly PHI nodes which just merge an initial value (the incoming operand)
797
427k
  // with themselves.  Check to see if we did and clean up our mess if so.  This
798
427k
  // occurs when a function passes an argument straight through to its tail
799
427k
  // call.
800
427k
  for (PHINode *PN : ArgumentPHIs) {
801
486
    // If the PHI Node is a dynamic constant, replace it with the value it is.
802
486
    if (Value *PNV = SimplifyInstruction(PN, F.getParent()->getDataLayout())) {
803
217
      PN->replaceAllUsesWith(PNV);
804
217
      PN->eraseFromParent();
805
217
    }
806
486
  }
807
427k
808
427k
  return MadeChange;
809
427k
}
810
811
namespace {
812
struct TailCallElim : public FunctionPass {
813
  static char ID; // Pass identification, replacement for typeid
814
13.4k
  TailCallElim() : FunctionPass(ID) {
815
13.4k
    initializeTailCallElimPass(*PassRegistry::getPassRegistry());
816
13.4k
  }
817
818
13.4k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
819
13.4k
    AU.addRequired<TargetTransformInfoWrapperPass>();
820
13.4k
    AU.addRequired<AAResultsWrapperPass>();
821
13.4k
    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
822
13.4k
    AU.addPreserved<GlobalsAAWrapperPass>();
823
13.4k
    AU.addPreserved<DominatorTreeWrapperPass>();
824
13.4k
    AU.addPreserved<PostDominatorTreeWrapperPass>();
825
13.4k
  }
826
827
465k
  bool runOnFunction(Function &F) override {
828
465k
    if (skipFunction(F))
829
44
      return false;
830
465k
831
465k
    auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
832
18.4E
    auto *DT = DTWP ? 
&DTWP->getDomTree()465k
: nullptr;
833
465k
    auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
834
465k
    auto *PDT = PDTWP ? 
&PDTWP->getPostDomTree()0
: nullptr;
835
465k
    // There is no noticable performance difference here between Lazy and Eager
836
465k
    // UpdateStrategy based on some test results. It is feasible to switch the
837
465k
    // UpdateStrategy to Lazy if we find it profitable later.
838
465k
    DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
839
465k
840
465k
    return eliminateTailRecursion(
841
465k
        F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
842
465k
        &getAnalysis<AAResultsWrapperPass>().getAAResults(),
843
465k
        &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU);
844
465k
  }
845
};
846
}
847
848
char TailCallElim::ID = 0;
849
48.9k
INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",
850
48.9k
                      false, false)
851
48.9k
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
852
48.9k
INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
853
48.9k
INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination",
854
                    false, false)
855
856
// Public interface to the TailCallElimination pass
857
13.4k
FunctionPass *llvm::createTailCallEliminationPass() {
858
13.4k
  return new TailCallElim();
859
13.4k
}
860
861
PreservedAnalyses TailCallElimPass::run(Function &F,
862
1.18k
                                        FunctionAnalysisManager &AM) {
863
1.18k
864
1.18k
  TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
865
1.18k
  AliasAnalysis &AA = AM.getResult<AAManager>(F);
866
1.18k
  auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
867
1.18k
  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
868
1.18k
  auto *PDT = AM.getCachedResult<PostDominatorTreeAnalysis>(F);
869
1.18k
  // There is no noticable performance difference here between Lazy and Eager
870
1.18k
  // UpdateStrategy based on some test results. It is feasible to switch the
871
1.18k
  // UpdateStrategy to Lazy if we find it profitable later.
872
1.18k
  DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
873
1.18k
  bool Changed = eliminateTailRecursion(F, &TTI, &AA, &ORE, DTU);
874
1.18k
875
1.18k
  if (!Changed)
876
588
    return PreservedAnalyses::all();
877
594
  PreservedAnalyses PA;
878
594
  PA.preserve<GlobalsAA>();
879
594
  PA.preserve<DominatorTreeAnalysis>();
880
594
  PA.preserve<PostDominatorTreeAnalysis>();
881
594
  return PA;
882
594
}