Bug Summary

File:lib/Transforms/Scalar/TailRecursionElimination.cpp
Warning:line 480, column 14
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name TailRecursionElimination.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/TailRecursionElimination.cpp -faddrsig
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"
84using namespace llvm;
85
86#define DEBUG_TYPE"tailcallelim" "tailcallelim"
87
88STATISTIC(NumEliminated, "Number of tail calls removed")static llvm::Statistic NumEliminated = {"tailcallelim", "NumEliminated"
, "Number of tail calls removed", {0}, {false}}
;
89STATISTIC(NumRetDuped, "Number of return duplicated")static llvm::Statistic NumRetDuped = {"tailcallelim", "NumRetDuped"
, "Number of return duplicated", {0}, {false}}
;
90STATISTIC(NumAccumAdded, "Number of accumulators introduced")static llvm::Statistic NumAccumAdded = {"tailcallelim", "NumAccumAdded"
, "Number of accumulators introduced", {0}, {false}}
;
91
92/// Scan the specified function for alloca instructions.
93/// If it contains any dynamic allocas, returns false.
94static 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
102namespace {
103struct 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
188static bool markTails(Function &F, bool &AllCallsAreTailCalls,
189 OptimizationRemarkEmitter *ORE) {
190 if (F.callsFunctionThatReturnsTwice())
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 };
216 DenseMap<BasicBlock *, VisitType> Visited;
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"tailcallelim", "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")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("tailcallelim")) { dbgs() << "Marked as tail call candidate: "
<< *CI << "\n"; } } while (false)
;
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///
328static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA) {
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(),
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.
362static 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.
396static Value *getCommonReturnValue(ReturnInst *IgnoreRI, CallInst *CI) {
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.
422static Value *canTransformAccumulatorRecursion(Instruction *I, CallInst *CI) {
423 if (!I->isAssociative() || !I->isCommutative()) return nullptr;
424 assert(I->getNumOperands() == 2 &&((I->getNumOperands() == 2 && "Associative/commutative operations should have 2 args!"
) ? static_cast<void> (0) : __assert_fail ("I->getNumOperands() == 2 && \"Associative/commutative operations should have 2 args!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/TailRecursionElimination.cpp"
, 425, __PRETTY_FUNCTION__))
425 "Associative/commutative operations should have 2 args!")((I->getNumOperands() == 2 && "Associative/commutative operations should have 2 args!"
) ? static_cast<void> (0) : __assert_fail ("I->getNumOperands() == 2 && \"Associative/commutative operations should have 2 args!\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/TailRecursionElimination.cpp"
, 425, __PRETTY_FUNCTION__))
;
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
442static Instruction *firstNonDbg(BasicBlock::iterator I) {
443 while (isa<DbgInfoIntrinsic>(I))
444 ++I;
445 return &*I;
446}
447
448static CallInst *findTRECandidate(Instruction *TI,
449 bool CannotTailCallElimCallsMarkedTail,
450 const TargetTransformInfo *TTI) {
451 BasicBlock *BB = TI->getParent();
452 Function *F = BB->getParent();
12
'F' initialized here
453
454 if (&BB->front() == TI) // Make sure there is something before the terminator.
13
Assuming the condition is false
14
Taking false branch
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) {
15
Loop condition is true. Entering loop body
462 CI = dyn_cast<CallInst>(BBI);
463 if (CI && CI->getCalledFunction() == F)
16
Assuming 'CI' is non-null
17
Assuming the condition is true
18
Assuming pointer value is null
19
Taking true branch
464 break;
20
Execution continues on line 473
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)
21
Taking false branch
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() &&
22
Called C++ object pointer is null
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.
486 CallSite::arg_iterator I = CallSite(CI).arg_begin(),
487 E = CallSite(CI).arg_end();
488 Function::arg_iterator FI = F->arg_begin(),
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
499static bool eliminateRecursiveTailCall(
500 CallInst *CI, ReturnInst *Ret, BasicBlock *&OldEntry,
501 bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
502 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
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"tailcallelim", "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
686static bool foldReturnAndProcessPred(
687 BasicBlock *BB, ReturnInst *Ret, BasicBlock *&OldEntry,
688 bool &TailCallsAreMarkedTail, SmallVectorImpl<PHINode *> &ArgumentPHIs,
689 bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
690 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
691 bool Change = false;
692
693 // Make sure this block is a trivial return block.
694 assert(BB->getFirstNonPHIOrDbg() == Ret &&((BB->getFirstNonPHIOrDbg() == Ret && "Trying to fold non-trivial return block"
) ? static_cast<void> (0) : __assert_fail ("BB->getFirstNonPHIOrDbg() == Ret && \"Trying to fold non-trivial return block\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/TailRecursionElimination.cpp"
, 695, __PRETTY_FUNCTION__))
695 "Trying to fold non-trivial return block")((BB->getFirstNonPHIOrDbg() == Ret && "Trying to fold non-trivial return block"
) ? static_cast<void> (0) : __assert_fail ("BB->getFirstNonPHIOrDbg() == Ret && \"Trying to fold non-trivial return block\""
, "/build/llvm-toolchain-snapshot-9~svn362543/lib/Transforms/Scalar/TailRecursionElimination.cpp"
, 695, __PRETTY_FUNCTION__))
;
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: " << *BBdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("tailcallelim")) { dbgs() << "FOLDING: " << *BB <<
"INTO UNCOND BRANCH PRED: " << *Pred; } } while (false
)
715 << "INTO UNCOND BRANCH PRED: " << *Pred)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("tailcallelim")) { dbgs() << "FOLDING: " << *BB <<
"INTO UNCOND BRANCH PRED: " << *Pred; } } while (false
)
;
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
735static bool processReturningBlock(
736 ReturnInst *Ret, BasicBlock *&OldEntry, bool &TailCallsAreMarkedTail,
737 SmallVectorImpl<PHINode *> &ArgumentPHIs,
738 bool CannotTailCallElimCallsMarkedTail, const TargetTransformInfo *TTI,
739 AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
740 CallInst *CI = findTRECandidate(Ret, CannotTailCallElimCallsMarkedTail, TTI);
11
Calling 'findTRECandidate'
741 if (!CI)
742 return false;
743
744 return eliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail,
745 ArgumentPHIs, AA, ORE, DTU);
746}
747
748static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI,
749 AliasAnalysis *AA,
750 OptimizationRemarkEmitter *ORE,
751 DomTreeUpdater &DTU) {
752 if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true")
2
Assuming the condition is false
3
Taking false branch
753 return false;
754
755 bool MadeChange = false;
756 bool AllCallsAreTailCalls = false;
757 MadeChange |= markTails(F, AllCallsAreTailCalls, ORE);
758 if (!AllCallsAreTailCalls)
4
Assuming 'AllCallsAreTailCalls' is not equal to 0
5
Taking false branch
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())
6
Taking false branch
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*/) {
7
Loop condition is true. Entering loop body
782 BasicBlock *BB = &*BBI++; // foldReturnAndProcessPred may delete BB.
783 if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) {
8
Taking true branch
784 bool Change = processReturningBlock(Ret, OldEntry, TailCallsAreMarkedTail,
10
Calling 'processReturningBlock'
785 ArgumentPHIs, !CanTRETailMarkedCall,
9
Assuming 'CanTRETailMarkedCall' is not equal to 0
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
811namespace {
812struct TailCallElim : public FunctionPass {
813 static char ID; // Pass identification, replacement for typeid
814 TailCallElim() : FunctionPass(ID) {
815 initializeTailCallElimPass(*PassRegistry::getPassRegistry());
816 }
817
818 void getAnalysisUsage(AnalysisUsage &AU) const override {
819 AU.addRequired<TargetTransformInfoWrapperPass>();
820 AU.addRequired<AAResultsWrapperPass>();
821 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
822 AU.addPreserved<GlobalsAAWrapperPass>();
823 AU.addPreserved<DominatorTreeWrapperPass>();
824 AU.addPreserved<PostDominatorTreeWrapperPass>();
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.
838 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
839
840 return eliminateTailRecursion(
841 F, &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F),
842 &getAnalysis<AAResultsWrapperPass>().getAAResults(),
843 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(), DTU);
844 }
845};
846}
847
848char TailCallElim::ID = 0;
849INITIALIZE_PASS_BEGIN(TailCallElim, "tailcallelim", "Tail Call Elimination",static void *initializeTailCallElimPassOnce(PassRegistry &
Registry) {
850 false, false)static void *initializeTailCallElimPassOnce(PassRegistry &
Registry) {
851INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
852INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
853INITIALIZE_PASS_END(TailCallElim, "tailcallelim", "Tail Call Elimination",PassInfo *PI = new PassInfo( "Tail Call Elimination", "tailcallelim"
, &TailCallElim::ID, PassInfo::NormalCtor_t(callDefaultCtor
<TailCallElim>), false, false); Registry.registerPass(*
PI, true); return PI; } static llvm::once_flag InitializeTailCallElimPassFlag
; void llvm::initializeTailCallElimPass(PassRegistry &Registry
) { llvm::call_once(InitializeTailCallElimPassFlag, initializeTailCallElimPassOnce
, std::ref(Registry)); }
854 false, false)PassInfo *PI = new PassInfo( "Tail Call Elimination", "tailcallelim"
, &TailCallElim::ID, PassInfo::NormalCtor_t(callDefaultCtor
<TailCallElim>), false, false); Registry.registerPass(*
PI, true); return PI; } static llvm::once_flag InitializeTailCallElimPassFlag
; void llvm::initializeTailCallElimPass(PassRegistry &Registry
) { llvm::call_once(InitializeTailCallElimPassFlag, initializeTailCallElimPassOnce
, std::ref(Registry)); }
855
856// Public interface to the TailCallElimination pass
857FunctionPass *llvm::createTailCallEliminationPass() {
858 return new TailCallElim();
859}
860
861PreservedAnalyses TailCallElimPass::run(Function &F,
862 FunctionAnalysisManager &AM) {
863
864 TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
865 AliasAnalysis &AA = AM.getResult<AAManager>(F);
866 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
867 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
868 auto *PDT = AM.getCachedResult<PostDominatorTreeAnalysis>(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.
872 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
873 bool Changed = eliminateTailRecursion(F, &TTI, &AA, &ORE, DTU);
1
Calling 'eliminateTailRecursion'
874
875 if (!Changed)
876 return PreservedAnalyses::all();
877 PreservedAnalyses PA;
878 PA.preserve<GlobalsAA>();
879 PA.preserve<DominatorTreeAnalysis>();
880 PA.preserve<PostDominatorTreeAnalysis>();
881 return PA;
882}