Split tailcallelim into tailcallmark and tailcallelim

[uenoku]

Summary

Currently, tailcallelim does
(1) mark call instruction as "tail" if possible
(2) eliminate tail call and generate loops

Like memcpyopt, some passes add call instruction but these calls are not marked as tail[1]. So it is better to add (1) after such passes.

I split tailcallelim into tailcallmark and tailcallelim.

tailcallmark - only for marking function calls as "tail".
tailcallelim - does what old tailcalleim did except for marking the calls.

[1]https://reviews.llvm.org/D59534

[lebedev.ri]

include/llvm/Transforms/Scalar/TailCallMarking.h

1 ↗

(On Diff #192980)

License blurb missing

lib/Transforms/Scalar/TailCallMarking.cpp

8 ↗

(On Diff #192980)

Might be a good idea to add a comment here as to what this does

lib/Transforms/Scalar/TailRecursionElimination.cpp

531

block

[uenoku]

Add license blurb

[uenoku]

Add description

[efriedma]

lib/Transforms/Scalar/TailRecursionElimination.cpp

536

There's a helper in llvm/ADT/DepthFirstIterator.h which can automatically handle all the boilerplate for iterating over all the reachable blocks in a function.

[nicholas]

lib/Transforms/Scalar/TailCallMarking.cpp

1 ↗

(On Diff #192983)

Fix ruler, it's too short.

lib/Transforms/Scalar/TailRecursionElimination.cpp

530–539

"areAllCallsTailCalls"? "allCallsAreTail"? "allCallsHaveTail"? Or the inverse, "hasAnyNonTailCall"?

[uenoku]

use DepthFirstIterator and rename

[jdoerfert]

I might have missed some earlier discussion but how does this solve the problem? Also, I assume the problem is still PR41047, correct?

lib/Transforms/Scalar/TailCallMarking.cpp

13 ↗

(On Diff #193293)

I would have "just" created the second pass in the original TailRecursionElimination.cpp file but separating it is fine too. (One benefit would have been a much smaller diff ;))

[uenoku]

This comment was removed by uenoku.

lib/Transforms/Scalar/TailRecursionElimination.cpp

531

Sorry, could you tell me what this means?

[uenoku]

Yes, the problem is PR41047. Inserting tailcallmark after memcpyopt would solve this problem.

Will you have a plan to make Attributor mark "tail"? If so, I think it is better to leave marking to Attributor.

[nicholas]

lib/Transforms/Scalar/TailRecursionElimination.cpp

531

There's a typo in the comment, "blcok" should read "block".

[uenoku]

Fix typo.

[uenoku]

lib/Transforms/Scalar/TailRecursionElimination.cpp

531

Oh, Thanks.

[jdoerfert]

In D60031#1452642, @uenoku wrote:

Yes, the problem is PR41047. Inserting tailcallmark after memcpyopt would solve this problem.

Will you have a plan to make Attributor mark "tail"? If so, I think it is better to leave marking to Attributor.

My main point is that you did not move tailcallmark after memcpyopt, correct?

If we want to change how/when tail is deduced is a separate discussion I guess. Keeping the existing deduction is the right thing for the patch.

[uenoku]

Yes, tailcallmark is not moved after memcpyopt in this patch.
I was going to make another patch for this change.

So this patch only split the pass and there is nothing to be changed in results.

[jdoerfert]

In D60031#1454360, @uenoku wrote:

Yes, tailcallmark is not moved after memcpyopt in this patch.
I was going to make another patch for this change.

So this patch only split the pass and there is nothing to be changed in results.

Fair point.

Except for the things I noted in the comments, this LGTM.

lib/Transforms/Scalar/TailRecursionElimination.cpp

528

Function behavior descriptions go usually above the function (3 x /). See canMoveAboveCall below for an example.

531

Please use BasicBlock and Instruction instead of auto, it is not helping to hide the type.

536

I'd remove the braces around a single return stmt.

[uenoku]

Remove auto and brace

[uenoku]

I don't have commit access. Would you commit?

[jdoerfert]

In D60031#1455793, @uenoku wrote:

I don't have commit access. Would you commit?

I'm running the tests now, will commit if all is good.

[jdoerfert]

In D60031#1456431, @jdoerfert wrote:

In D60031#1455793, @uenoku wrote:

I don't have commit access. Would you commit?

I'm running the tests now, will commit if all is good.

I see these failures:

LLVM :: Other/opt-O2-pipeline.ll
LLVM :: Other/opt-O3-pipeline.ll
LLVM :: Other/opt-Os-pipeline.ll
LLVM :: Transforms/TailCallElim/ackermann.ll
LLVM :: Transforms/TailCallElim/dup_tail.ll

Please build LLVM with assertions and fix the tests.

[uenoku]

Fix testcases

[lebedev.ri]

test/Other/opt-O3-pipeline.ll

90–101

This looks weird.
Does Tail Call Marking discard/does not preserve those analysises?

[jdoerfert]

test/Other/opt-O3-pipeline.ll

90–101

Good catch. It probably doesn't preserve but should. (Not only those)

[efriedma]

(Probably should be using setPreservesCFG().)

[uenoku]

Set preserved Analysis and fix testcases.

[uenoku]

test/Other/opt-O3-pipeline.ll

90–101

I cannot be sure whether preserved Analysis are enough.
Is there missing analysis?

[jdoerfert]

test/Other/opt-O3-pipeline.ll

90–101

Optimization Remark Emitter seems to be recomputed, you should "preserve" that one as well.

[uenoku]

Add preservedAnalysis

[uenoku]

Remove wrong file

[jdoerfert]

I inlined a question. Also, did you run the tests with assertions enabled?

test/Other/opt-Os-pipeline.ll

80

Why do the analysis appear here? I would have expected them to be somewhere on the left as well.

Btw. please submit patches with *all* the context so I can see more than 3 lines if I want.

[uenoku]

Make AA preserved.

[uenoku]

test/Other/opt-Os-pipeline.ll

80

You are right. AA should be preserved.

I submit a patch with all the context. I am sorry to have inconvenienced you.

[uenoku]

I didn't added files. Fix it.

[uenoku]

Yes, I ran the tests with assertions enabled. check-llvm and check-clang have passed.

[jdoerfert]

In D60031#1471295, @uenoku wrote:

Yes, I ran the tests with assertions enabled. check-llvm and check-clang have passed.

I'll need to run it (probably at the end of this week) and assuming that works out I'll submit it (= LGTM).

[efriedma]

What happened to this patch?

[xbolva00]

Reping.

It would be great to have some late “tailcallmark” pass.

[xbolva00]

In D60031#1483566, @jdoerfert wrote:

In D60031#1471295, @uenoku wrote:

Yes, I ran the tests with assertions enabled. check-llvm and check-clang have passed.

I'll need to run it (probably at the end of this week) and assuming that works out I'll submit it (= LGTM).

Can you submit it please?

[uenoku]

Rebased. I didn't realize this was not merged. Sorry everyone who waited for this.

[xbolva00]

Thanks. if all tests pass, please land it as this got LGTM.

[xbolva00]

re-ping

[uenoku]

It still fails some tests and I'm afraid it changed something since the review was almost three years ago.
I don't have enough time to work on so @xbolva00, could you take over this PR if you have urgent use cases?

Sorry I will not have time to work so I'd like to abandon this.

include/llvm/InitializePasses.h

 void initializeStripDeadDebugInfoPass(PassRegistry&);
 void initializeStripDeadPrototypesLegacyPassPass(PassRegistry&);
 void initializeStripDebugDeclarePass(PassRegistry&);
 void initializeStripGCRelocatesPass(PassRegistry&);
 void initializeStripNonDebugSymbolsPass(PassRegistry&);
 void initializeStripNonLineTableDebugInfoPass(PassRegistry&);
 void initializeStripSymbolsPass(PassRegistry&);
 void initializeStructurizeCFGPass(PassRegistry&);
+void initializeTailCallMarkPass(PassRegistry &);
 void initializeTailCallElimPass(PassRegistry&);
 void initializeTailDuplicatePass(PassRegistry&);
 void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&);
 void initializeTargetPassConfigPass(PassRegistry&);
 void initializeTargetTransformInfoWrapperPassPass(PassRegistry&);
 void initializeThreadSanitizerLegacyPassPass(PassRegistry&);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createSCCPPass();
       (void) llvm::createSafeStackPass();
       (void) llvm::createSROAPass();
       (void) llvm::createSingleLoopExtractorPass();
       (void) llvm::createStripSymbolsPass();
       (void) llvm::createStripNonDebugSymbolsPass();
       (void) llvm::createStripDeadDebugInfoPass();
       (void) llvm::createStripDeadPrototypesPass();
+      (void) llvm::createTailCallMarkingPass();
       (void) llvm::createTailCallEliminationPass();
       (void) llvm::createJumpThreadingPass();
       (void) llvm::createUnifyFunctionExitNodesPass();
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createEntryExitInstrumenterPass();
       (void) llvm::createPostInlineEntryExitInstrumenterPass();

include/llvm/Transforms/Scalar.h

 //
 ///
 /// When \p SkipUniformRegions is true the structizer will not structurize
 /// regions that only contain uniform branches.
 Pass *createStructurizeCFGPass(bool SkipUniformRegions = false);
 
 //===----------------------------------------------------------------------===//
 //
+// TailCallMarking - This pass mark call instructions as tail if possible
+//
+FunctionPass *createTailCallMarkingPass();
+
+//===----------------------------------------------------------------------===//
+//
 // TailCallElimination - This pass eliminates call instructions to the current
 // function which occur immediately before return instructions.
 //
 FunctionPass *createTailCallEliminationPass();
 
 //===----------------------------------------------------------------------===//
 //
 // EarlyCSE - This pass performs a simple and fast CSE pass over the dominator

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Scalar/SROA.h"
 #include "llvm/Transforms/Scalar/Scalarizer.h"
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/Sink.h"
 #include "llvm/Transforms/Scalar/SpeculateAroundPHIs.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
+#include "llvm/Transforms/Scalar/TailCallMarking.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Scalar/WarnMissedTransforms.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/EntryExitInstrumenter.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
   invokePeepholeEPCallbacks(FPM, Level);
 
   // For PGO use pipeline, try to optimize memory intrinsics such as memcpy
   // using the size value profile. Don't perform this when optimizing for size.
   if (PGOOpt && PGOOpt->Action == PGOOptions::IRUse &&
       !isOptimizingForSize(Level))
     FPM.addPass(PGOMemOPSizeOpt());
 
+  FPM.addPass(TailCallMarkPass());
   FPM.addPass(TailCallElimPass());
   FPM.addPass(SimplifyCFGPass());
 
   // Form canonically associated expression trees, and simplify the trees using
   // basic mathematical properties. For example, this will form (nearly)
   // minimal multiplication trees.
   FPM.addPass(ReassociatePass());
 
else if (PGOOpt->CSAction == PGOOptions::CSIRUse)
                         PGOOpt->ProfileRemappingFile);
   }
 
   // Break up allocas
   FPM.addPass(SROA());
 
   // LTO provides additional opportunities for tailcall elimination due to
   // link-time inlining, and visibility of nocapture attribute.
+  FPM.addPass(TailCallMarkPass());
   FPM.addPass(TailCallElimPass());
 
   // Run a few AA driver optimizations here and now to cleanup the code.
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
 
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(
               PostOrderFunctionAttrsPass()));
   // FIXME: here we run IP alias analysis in the legacy PM.

lib/Passes/PassRegistry.def

 FUNCTION_PASS("reassociate", ReassociatePass())
 FUNCTION_PASS("scalarizer", ScalarizerPass())
 FUNCTION_PASS("sccp", SCCPPass())
 FUNCTION_PASS("sink", SinkingPass())
 FUNCTION_PASS("slp-vectorizer", SLPVectorizerPass())
 FUNCTION_PASS("speculative-execution", SpeculativeExecutionPass())
 FUNCTION_PASS("spec-phis", SpeculateAroundPHIsPass())
 FUNCTION_PASS("sroa", SROA())
+FUNCTION_PASS("tailcallmark", TailCallMarkPass())
 FUNCTION_PASS("tailcallelim", TailCallElimPass())
 FUNCTION_PASS("unreachableblockelim", UnreachableBlockElimPass())
 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 FUNCTION_PASS("verify<loops>", LoopVerifierPass())
 FUNCTION_PASS("verify<memoryssa>", MemorySSAVerifierPass())
 FUNCTION_PASS("verify<regions>", RegionInfoVerifierPass())
 FUNCTION_PASS("verify<safepoint-ir>", SafepointIRVerifierPass())

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   if (SizeLevel == 0 && !DisableLibCallsShrinkWrap)
     MPM.add(createLibCallsShrinkWrapPass());
   addExtensionsToPM(EP_Peephole, MPM);
 
   // Optimize memory intrinsic calls based on the profiled size information.
   if (SizeLevel == 0)
     MPM.add(createPGOMemOPSizeOptLegacyPass());
 
+  MPM.add(createTailCallMarkingPass());     // Mark tail calls
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createReassociatePass());           // Reassociate expressions
 
   // Begin the loop pass pipeline.
   if (EnableSimpleLoopUnswitch) {
     // The simple loop unswitch pass relies on separate cleanup passes. Schedule
     // them first so when we re-process a loop they run before other loop
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   addExtensionsToPM(EP_Peephole, PM);
   PM.add(createJumpThreadingPass());
 
   // Break up allocas
   PM.add(createSROAPass());
 
   // LTO provides additional opportunities for tailcall elimination due to
   // link-time inlining, and visibility of nocapture attribute.
+  PM.add(createTailCallMarkingPass());
   PM.add(createTailCallEliminationPass());
 
   // Run a few AA driven optimizations here and now, to cleanup the code.
   PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture.
   PM.add(createGlobalsAAWrapperPass()); // IP alias analysis.
 
   PM.add(createLICMPass());                 // Hoist loop invariants.
   PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.

lib/Transforms/Scalar/CMakeLists.txt

add_llvm_library(LLVMScalarOpts
   SeparateConstOffsetFromGEP.cpp
   SimpleLoopUnswitch.cpp
   SimplifyCFGPass.cpp
   Sink.cpp
   SpeculativeExecution.cpp
   SpeculateAroundPHIs.cpp
   StraightLineStrengthReduce.cpp
   StructurizeCFG.cpp
+  TailCallMarking.cpp
   TailRecursionElimination.cpp
   WarnMissedTransforms.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Scalar
 
   DEPENDS
   intrinsics_gen
   )

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeRegToMemPass(Registry);
   initializeRewriteStatepointsForGCLegacyPassPass(Registry);
   initializeSCCPLegacyPassPass(Registry);
   initializeSROALegacyPassPass(Registry);
   initializeCFGSimplifyPassPass(Registry);
   initializeStructurizeCFGPass(Registry);
   initializeSimpleLoopUnswitchLegacyPassPass(Registry);
   initializeSinkingLegacyPassPass(Registry);
+  initializeTailCallMarkPass(Registry);
   initializeTailCallElimPass(Registry);
   initializeSeparateConstOffsetFromGEPPass(Registry);
   initializeSpeculativeExecutionLegacyPassPass(Registry);
   initializeStraightLineStrengthReducePass(Registry);
   initializePlaceBackedgeSafepointsImplPass(Registry);
   initializePlaceSafepointsPass(Registry);
   initializeFloat2IntLegacyPassPass(Registry);
   initializeLoopDistributeLegacyPass(Registry);
void LLVMAddScalarReplAggregatesPassWithThreshold(LLVMPassManagerRef PM,
                                                   int Threshold) {
   unwrap(PM)->add(createSROAPass());
 }
 
 void LLVMAddSimplifyLibCallsPass(LLVMPassManagerRef PM) {
   // NOTE: The simplify-libcalls pass has been removed.
 }
 
+void LLVMAddTailCallMarkPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createTailCallMarkingPass());
+}
+
 void LLVMAddTailCallEliminationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createTailCallEliminationPass());
 }
 
 void LLVMAddConstantPropagationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createConstantPropagationPass());
 }
 

lib/Transforms/Scalar/TailRecursionElimination.cpp

 //     move ahead of the call, but doing so could allow many more TREs to be
 //     performed, for example in TreeAdd/TreeAlloc from the treeadd benchmark.
 //  4. The algorithm we use to detect if callees access their caller stack
 //     frames is very primitive.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InlineCost.h"

 static bool canTRE(Function &F) {
   // Because of PR962, we don't TRE dynamic allocas.
   return llvm::all_of(instructions(F), [](Instruction &I) {
     auto *AI = dyn_cast<AllocaInst>(&I);
     return !AI || AI->isStaticAlloca();
   });
 }
 
-namespace {
-struct AllocaDerivedValueTracker {
-  // Start at a root value and walk its use-def chain to mark calls that use the
-  // value or a derived value in AllocaUsers, and places where it may escape in
-  // EscapePoints.
-  void walk(Value *Root) {
-    SmallVector<Use *, 32> Worklist;
-    SmallPtrSet<Use *, 32> Visited;
-
-    auto AddUsesToWorklist = [&](Value *V) {
-      for (auto &U : V->uses()) {
-        if (!Visited.insert(&U).second)
-          continue;
-        Worklist.push_back(&U);
-      }
-    };
-
-    AddUsesToWorklist(Root);
-
-    while (!Worklist.empty()) {
-      Use *U = Worklist.pop_back_val();
-      Instruction *I = cast<Instruction>(U->getUser());
-
-      switch (I->getOpcode()) {
-      case Instruction::Call:
-      case Instruction::Invoke: {
-        CallSite CS(I);
-        // If the alloca-derived argument is passed byval it is not an escape
-        // point, or a use of an alloca. Calling with byval copies the contents
-        // of the alloca into argument registers or stack slots, which exist
-        // beyond the lifetime of the current frame.
-        if (CS.isArgOperand(U) && CS.isByValArgument(CS.getArgumentNo(U)))
-          continue;
-        bool IsNocapture =
-            CS.isDataOperand(U) && CS.doesNotCapture(CS.getDataOperandNo(U));
-        callUsesLocalStack(CS, IsNocapture);
-        if (IsNocapture) {
-          // If the alloca-derived argument is passed in as nocapture, then it
-          // can't propagate to the call's return. That would be capturing.
-          continue;
-        }
-        break;
-      }
-      case Instruction::Load: {
-        // The result of a load is not alloca-derived (unless an alloca has
-        // otherwise escaped, but this is a local analysis).
-        continue;
-      }
-      case Instruction::Store: {
-        if (U->getOperandNo() == 0)
-          EscapePoints.insert(I);
-        continue;  // Stores have no users to analyze.
-      }
-      case Instruction::BitCast:
-      case Instruction::GetElementPtr:
-      case Instruction::PHI:
-      case Instruction::Select:
-      case Instruction::AddrSpaceCast:
-        break;
-      default:
-        EscapePoints.insert(I);
-        break;
-      }
-
-      AddUsesToWorklist(I);
-    }
-  }
-
-  void callUsesLocalStack(CallSite CS, bool IsNocapture) {
-    // Add it to the list of alloca users.
-    AllocaUsers.insert(CS.getInstruction());
-
-    // If it's nocapture then it can't capture this alloca.
-    if (IsNocapture)
-      return;
-
-    // If it can write to memory, it can leak the alloca value.
-    if (!CS.onlyReadsMemory())
-      EscapePoints.insert(CS.getInstruction());
-  }
-
-  SmallPtrSet<Instruction *, 32> AllocaUsers;
-  SmallPtrSet<Instruction *, 32> EscapePoints;
-};
-}
-
-static bool markTails(Function &F, bool &AllCallsAreTailCalls,
-                      OptimizationRemarkEmitter *ORE) {
-  if (F.callsFunctionThatReturnsTwice())
-    return false;
-  AllCallsAreTailCalls = true;
-
-  // The local stack holds all alloca instructions and all byval arguments.
-  AllocaDerivedValueTracker Tracker;
-  for (Argument &Arg : F.args()) {
-    if (Arg.hasByValAttr())
-      Tracker.walk(&Arg);
-  }
-  for (auto &BB : F) {
-    for (auto &I : BB)
-      if (AllocaInst *AI = dyn_cast<AllocaInst>(&I))
-        Tracker.walk(AI);
-  }
-
-  bool Modified = false;
-
-  // Track whether a block is reachable after an alloca has escaped. Blocks that
-  // contain the escaping instruction will be marked as being visited without an
-  // escaped alloca, since that is how the block began.
-  enum VisitType {
-    UNVISITED,
-    UNESCAPED,
-    ESCAPED
-  };
-  DenseMap<BasicBlock *, VisitType> Visited;
-
-  // We propagate the fact that an alloca has escaped from block to successor.
-  // Visit the blocks that are propagating the escapedness first. To do this, we
-  // maintain two worklists.
-  SmallVector<BasicBlock *, 32> WorklistUnescaped, WorklistEscaped;
-
-  // We may enter a block and visit it thinking that no alloca has escaped yet,
-  // then see an escape point and go back around a loop edge and come back to
-  // the same block twice. Because of this, we defer setting tail on calls when
-  // we first encounter them in a block. Every entry in this list does not
-  // statically use an alloca via use-def chain analysis, but may find an alloca
-  // through other means if the block turns out to be reachable after an escape
-  // point.
-  SmallVector<CallInst *, 32> DeferredTails;
-
-  BasicBlock *BB = &F.getEntryBlock();
-  VisitType Escaped = UNESCAPED;
-  do {
-    for (auto &I : *BB) {
-      if (Tracker.EscapePoints.count(&I))
-        Escaped = ESCAPED;
-
-      CallInst *CI = dyn_cast<CallInst>(&I);
-      if (!CI || CI->isTailCall() || isa<DbgInfoIntrinsic>(&I))
-        continue;
-
-      bool IsNoTail = CI->isNoTailCall() || CI->hasOperandBundles();
-
-      if (!IsNoTail && CI->doesNotAccessMemory()) {
-        // A call to a readnone function whose arguments are all things computed
-        // outside this function can be marked tail. Even if you stored the
-        // alloca address into a global, a readnone function can't load the
-        // global anyhow.
-        //
-        // Note that this runs whether we know an alloca has escaped or not. If
-        // it has, then we can't trust Tracker.AllocaUsers to be accurate.
-        bool SafeToTail = true;
-        for (auto &Arg : CI->arg_operands()) {
-          if (isa<Constant>(Arg.getUser()))
-            continue;
-          if (Argument *A = dyn_cast<Argument>(Arg.getUser()))
-            if (!A->hasByValAttr())
-              continue;
-          SafeToTail = false;
-          break;
-        }
-        if (SafeToTail) {
-          using namespace ore;
-          ORE->emit([&]() {
-            return OptimizationRemark(DEBUG_TYPE, "tailcall-readnone", CI)
-                   << "marked as tail call candidate (readnone)";
-          });
-          CI->setTailCall();
-          Modified = true;
-          continue;
-        }
-      }
-
-      if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI)) {
-        DeferredTails.push_back(CI);
-      } else {
-        AllCallsAreTailCalls = false;
-      }
-    }
-
-    for (auto *SuccBB : make_range(succ_begin(BB), succ_end(BB))) {
-      auto &State = Visited[SuccBB];
-      if (State < Escaped) {
-        State = Escaped;
-        if (State == ESCAPED)
-          WorklistEscaped.push_back(SuccBB);
-        else
-          WorklistUnescaped.push_back(SuccBB);
-      }
-    }
-
-    if (!WorklistEscaped.empty()) {
-      BB = WorklistEscaped.pop_back_val();
-      Escaped = ESCAPED;
-    } else {
-      BB = nullptr;
-      while (!WorklistUnescaped.empty()) {
-        auto *NextBB = WorklistUnescaped.pop_back_val();
-        if (Visited[NextBB] == UNESCAPED) {
-          BB = NextBB;
-          Escaped = UNESCAPED;
-          break;
-        }
-      }
-    }
-  } while (BB);
-
-  for (CallInst *CI : DeferredTails) {
-    if (Visited[CI->getParent()] != ESCAPED) {
-      // If the escape point was part way through the block, calls after the
-      // escape point wouldn't have been put into DeferredTails.
-      LLVM_DEBUG(dbgs() << "Marked as tail call candidate: " << *CI << "\n");
-      CI->setTailCall();
-      Modified = true;
-    } else {
-      AllCallsAreTailCalls = false;
-    }
-  }
-
-  return Modified;
-}
-
 /// Return true if it is safe to move the specified
 /// instruction from after the call to before the call, assuming that all
 /// instructions between the call and this instruction are movable.
 ///
 static bool canMoveAboveCall(Instruction *I, CallInst *CI, AliasAnalysis *AA) {
   // FIXME: We can move load/store/call/free instructions above the call if the
   // call does not mod/ref the memory location being processed.
   if (I->mayHaveSideEffects())  // This also handles volatile loads.
static bool processReturningBlock(
     AliasAnalysis *AA, OptimizationRemarkEmitter *ORE, DomTreeUpdater &DTU) {
   CallInst *CI = findTRECandidate(Ret, CannotTailCallElimCallsMarkedTail, TTI);
   if (!CI)
     return false;
 
   return eliminateRecursiveTailCall(CI, Ret, OldEntry, TailCallsAreMarkedTail,
                                     ArgumentPHIs, AA, ORE, DTU);
 }
+/// Return true if all call instructions which can be reachble entry blcok are
+/// marked as "tail".
+///
+static bool areAllCallsTailCalls(Function &F) {
 
+  for (BasicBlock *BB : depth_first(&F)) {
+    for (Instruction &I : *BB) {
+      CallInst *CI = dyn_cast<CallInst>(&I);
+      if (CI && !CI->isTailCall())
+        return false;
+    }
+  }
+  return true;
+}
 static bool eliminateTailRecursion(Function &F, const TargetTransformInfo *TTI,
                                    AliasAnalysis *AA,
                                    OptimizationRemarkEmitter *ORE,
                                    DomTreeUpdater &DTU) {
   if (F.getFnAttribute("disable-tail-calls").getValueAsString() == "true")
     return false;
 
   bool MadeChange = false;
-  bool AllCallsAreTailCalls = false;
-  MadeChange |= markTails(F, AllCallsAreTailCalls, ORE);
+  bool AllCallsAreTailCalls = areAllCallsTailCalls(F);
   if (!AllCallsAreTailCalls)
     return MadeChange;
 
   // If this function is a varargs function, we won't be able to PHI the args
   // right, so don't even try to convert it...
   if (F.getFunctionType()->isVarArg())
     return false;
 

test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O3-NEXT: AggressiveInstCombinePass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O1-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O3-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-EP-PEEPHOLE-NEXT: Running pass: NoOpFunctionPass
+; CHECK-O-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O-NEXT: Running pass: TailCallElimPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: ReassociatePass
 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}OptimizationRemarkEmitterAnalysis
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LoopStandardAnalysisResults{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running analysis: LoopAnalysis

test/Other/new-pm-lto-defaults.ll

 ; CHECK-O2-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O2-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O2-NEXT: Running pass: InstCombinePass
 ; CHECK-EP-Peephole-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O2-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O2-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O2-NEXT: Running pass: SROA on foo
+; CHECK-O2-NEXT: Running pass: TailCallMarkPass on foo
 ; CHECK-O2-NEXT: Running pass: TailCallElimPass on foo
 ; CHECK-O2-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O2-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}PostOrderFunctionAttrsPass>
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O2-NEXT: Running analysis: MemoryDependenceAnalysis
 ; CHECK-O2-NEXT: Running analysis: PhiValuesAnalysis
 ; CHECK-O2-NEXT: Running analysis: DemandedBitsAnalysis
 ; CHECK-O2-NEXT: Running pass: CrossDSOCFIPass

test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O3-NEXT: Running pass: AggressiveInstCombinePass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O1-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O3-NEXT: Running pass: LibCallsShrinkWrapPass
+; CHECK-O-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O-NEXT: Running pass: TailCallElimPass
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: ReassociatePass
 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}OptimizationRemarkEmitterAnalysis
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LoopStandardAnalysisResults{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run
 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running analysis: LoopAnalysis

test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         Conditionally eliminate dead library calls
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Branch Probability Analysis
 ; CHECK-NEXT:         Block Frequency Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         PGOMemOPSize
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
+; CHECK-NEXT:         Tail Call Marking
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass

test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         Conditionally eliminate dead library calls
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Branch Probability Analysis
 ; CHECK-NEXT:         Block Frequency Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         PGOMemOPSize
-; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
-; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
+; CHECK-NEXT:         Tail Call Marking
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
+; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops

test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Optimization Remark Emitter
+; CHECK-NEXT:         Tail Call Marking
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results

test/Transforms/Inline/byval-tail-call.ll

-; RUN: opt < %s -basicaa -tailcallelim -inline -instcombine -dse -S | FileCheck %s
-; RUN: opt < %s -aa-pipeline=basic-aa -passes='function(tailcallelim),cgscc(inline,function(instcombine,dse))' -S | FileCheck %s
+; RUN: opt < %s -basicaa -tailcallmark -tailcallelim -inline -instcombine -dse -S | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes='function(tailcallmark,tailcallelim),cgscc(inline,function(instcombine,dse))' -S | FileCheck %s
 ; PR7272
 
 ; Calls that capture byval parameters cannot be marked as tail calls. Other
 ; tails that don't capture byval parameters can still be tail calls.
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32"
 target triple = "i386-pc-linux-gnu"
 

test/Transforms/TailCallElim/2010-06-26-MultipleReturnValues.ll

-; RUN: opt < %s -tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -S | FileCheck %s
 ; PR7328
 ; PR7506
 define i32 @foo(i32 %x) {
 ; CHECK-LABEL: define i32 @foo(
 ; CHECK: %accumulator.tr = phi i32 [ 1, %entry ], [ 0, %body ]
 entry:
   %cond = icmp ugt i32 %x, 0                      ; <i1> [#uses=1]
   br i1 %cond, label %return, label %body

test/Transforms/TailCallElim/accum_recursion.ll

-; RUN: opt < %s -tailcallelim -verify-dom-info -S | FileCheck %s
-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=tailcallmark,tailcallelim -verify-dom-info -S | FileCheck %s
 
 define i32 @test1_factorial(i32 %x) {
 entry:
   %tmp.1 = icmp sgt i32 %x, 0    ; <i1> [#uses=1]
   br i1 %tmp.1, label %then, label %else
 then:   ; preds = %entry
   %tmp.6 = add i32 %x, -1   ; <i32> [#uses=1]
   %tmp.4 = call i32 @test1_factorial( i32 %tmp.6 )    ; <i32> [#uses=1]

test/Transforms/TailCallElim/ackermann.ll

 ; REQUIRES: asserts
 ; This function contains two tail calls, which should be eliminated
-; RUN: opt < %s -tailcallelim -verify-dom-info -stats -disable-output 2>&1 | grep "2 tailcallelim"
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -stats -disable-output 2>&1 | grep "2 tailcallelim"
 
 define i32 @Ack(i32 %M.1, i32 %N.1) {
 entry:
   %tmp.1 = icmp eq i32 %M.1, 0    ; <i1> [#uses=1]
   br i1 %tmp.1, label %then.0, label %endif.0
 then.0:   ; preds = %entry
   %tmp.4 = add i32 %N.1, 1    ; <i32> [#uses=1]
   ret i32 %tmp.4

test/Transforms/TailCallElim/basic.ll

-; RUN: opt < %s -tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -S | FileCheck %s
 
 declare void @noarg()
 declare void @use(i32*)
 declare void @use_nocapture(i32* nocapture)
 declare void @use2_nocapture(i32* nocapture, i32* nocapture)
 
 ; Trivial case. Mark @noarg with tail call.
 define void @test0() {

test/Transforms/TailCallElim/debugloc.ll

-; RUN: opt < %s -debugify -tailcallelim -S | FileCheck %s
+; RUN: opt < %s -debugify -tailcallmark -tailcallelim -S | FileCheck %s
 
 define void @foo() {
 entry:
 ; CHECK-LABEL: entry:
 ; CHECK: br label %tailrecurse, !dbg ![[DbgLoc:[0-9]+]]
 
   call void @foo()                            ;; line 1
   ret void
 
 ; CHECK-LABEL: tailrecurse:
 ; CHECK: br label %tailrecurse, !dbg ![[DbgLoc]]
 }
 
 ;; Make sure tailrecurse has the call instruction's DL
 ; CHECK: ![[DbgLoc]] = !DILocation(line: 1

test/Transforms/TailCallElim/deopt-bundle.ll

-; RUN: opt < %s -tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -S | FileCheck %s
 
 define i32 @f_1(i32 %x) {
 ; CHECK-LABEL: @f_1(
 wentry:
   %cond = icmp ugt i32 %x, 0
   br i1 %cond, label %return, label %body
 
 body:

test/Transforms/TailCallElim/dup_tail.ll

 ; REQUIRES: asserts
 ; Duplicate the return into if.end to enable TCE.
-; RUN: opt -tailcallelim -verify-dom-info -stats -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt -tailcallmark -tailcallelim -verify-dom-info -stats -disable-output < %s 2>&1 | FileCheck %s
 
 ; CHECK: Number of return duplicated
 
 define i32 @fib(i32 %n) nounwind ssp {
 entry:
   %cmp = icmp slt i32 %n, 2
   br i1 %cmp, label %if.then, label %if.end
 

test/Transforms/TailCallElim/inf-recursion.ll

-; RUN: opt < %s -tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -S | FileCheck %s
 
 ; Don't turn this into an infinite loop, this is probably the implementation
 ; of fabs and we expect the codegen to lower fabs.
 ; CHECK: @fabs(double %f)
 ; CHECK: call
 ; CHECK: ret
 
 define double @fabs(double %f) {

test/Transforms/TailCallElim/notail.ll

-; RUN: opt < %s -tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -S | FileCheck %s
 
 ; CHECK: tail call void @callee0()
 ; CHECK: notail call void @callee1()
 
 define void @foo1(i32 %a) {
 entry:
   %tobool = icmp eq i32 %a, 0
   br i1 %tobool, label %if.else, label %if.then

test/Transforms/TailCallElim/opt-remarks-recursion.ll

-; RUN: opt %s -tailcallelim -verify-dom-info -pass-remarks=tailcallelim -o /dev/null 2>&1 | FileCheck %s
-; RUN: opt %s -o /dev/null -passes='require<opt-remark-emit>,tailcallelim' -pass-remarks=tailcallelim 2>&1 | FileCheck %s
+; RUN: opt %s -tailcallmark -tailcallelim -verify-dom-info -pass-remarks=tailcallelim -o /dev/null 2>&1 | FileCheck %s
+; RUN: opt %s -o /dev/null -passes='require<opt-remark-emit>,tailcallmark,tailcallelim' -pass-remarks=tailcallelim 2>&1 | FileCheck %s
 
 ; CHECK: /home/davide/pat.c:2:20: transforming tail recursion into loop
 define i32 @fib(i32 %n) nounwind ssp {
 entry:
   %cmp = icmp slt i32 %n, 2
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:                                          ; preds = %entry

test/Transforms/TailCallElim/reorder_load.ll

-; RUN: opt < %s -tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -tailcallmark -tailcallelim -verify-dom-info -S | FileCheck %s
 ; PR4323
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Several cases where tail call elimination should move the load above the call,
 ; then eliminate the tail recursion.