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

526 ↗

(On Diff #192980)

block

[uenoku]

Add license blurb

[uenoku]

Add description

[efriedma]

lib/Transforms/Scalar/TailRecursionElimination.cpp

531 ↗

(On Diff #192983)

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

525 ↗

(On Diff #192983)

"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

526 ↗

(On Diff #192980)

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

526 ↗

(On Diff #192980)

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

[uenoku]

Fix typo.

[uenoku]

lib/Transforms/Scalar/TailRecursionElimination.cpp

526 ↗

(On Diff #192980)

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 ↗

(On Diff #193434)

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

530 ↗

(On Diff #193434)

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

535 ↗

(On Diff #193434)

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 ↗

(On Diff #194012)

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

[jdoerfert]

test/Other/opt-O3-pipeline.ll

90–101 ↗

(On Diff #194012)

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 ↗

(On Diff #194012)

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

[jdoerfert]

test/Other/opt-O3-pipeline.ll

90–101 ↗

(On Diff #194012)

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 ↗

(On Diff #195337)

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 ↗

(On Diff #195337)

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.

llvm/bindings/go/llvm/transforms_scalar.go

 func (pm PassManager) AddPromoteMemoryToRegisterPass() { C.LLVMAddPromoteMemoryToRegisterPass(pm.C) }
 func (pm PassManager) AddReassociatePass()             { C.LLVMAddReassociatePass(pm.C) }
 func (pm PassManager) AddSCCPPass()                    { C.LLVMAddSCCPPass(pm.C) }
 func (pm PassManager) AddScalarReplAggregatesPass()    { C.LLVMAddScalarReplAggregatesPass(pm.C) }
 func (pm PassManager) AddScalarReplAggregatesPassWithThreshold(threshold int) {
   C.LLVMAddScalarReplAggregatesPassWithThreshold(pm.C, C.int(threshold))
 }
 func (pm PassManager) AddSimplifyLibCallsPass()       { C.LLVMAddSimplifyLibCallsPass(pm.C) }
+func (pm PassManager) AddTailCallMarkingPass()        { C.LLVMAddTailCallMarkingPass(pm.C) }
 func (pm PassManager) AddTailCallEliminationPass()    { C.LLVMAddTailCallEliminationPass(pm.C) }
 func (pm PassManager) AddDemoteMemoryToRegisterPass() { C.LLVMAddDemoteMemoryToRegisterPass(pm.C) }
 func (pm PassManager) AddVerifierPass()               { C.LLVMAddVerifierPass(pm.C) }

llvm/bindings/ocaml/transforms/scalar_opts/llvm_scalar_opts.mli

external add_scalar_repl_aggregation_with_threshold
   : int -> [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
   = "llvm_add_scalar_repl_aggregates_with_threshold"
 
 (** See the [llvm::createSimplifyLibCallsPass] function. *)
 external add_lib_call_simplification
   : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
   = "llvm_add_simplify_lib_calls"
 
+(** See the [llvm::createTailCallMarkingPass] function. *)
+external add_tail_call_marking
+  : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
+  = "llvm_add_tail_call_marking"
+
 (** See the [llvm::createTailCallEliminationPass] function. *)
 external add_tail_call_elimination
   : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
   = "llvm_add_tail_call_elimination"
 
 (** See the [llvm::createDemoteMemoryToRegisterPass] function. *)
 external add_memory_to_register_demotion
   : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit

llvm/bindings/ocaml/transforms/scalar_opts/scalar_opts_ocaml.c

 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 value llvm_add_tail_call_elimination(LLVMPassManagerRef PM) {
   LLVMAddTailCallEliminationPass(PM);
   return Val_unit;
 }
 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
+value llvm_add_tail_call_marking(LLVMPassManagerRef PM) {
+  LLVMAddTailCallMarkingPass(PM);
+  return Val_unit;
+}
+
+/* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 value llvm_add_demote_memory_to_register(LLVMPassManagerRef PM) {
   LLVMAddDemoteMemoryToRegisterPass(PM);
   return Val_unit;
 }
 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 value llvm_add_verifier(LLVMPassManagerRef PM) {
   LLVMAddVerifierPass(PM);

llvm/examples/OrcV2Examples/LLJITWithOptimizingIRTransform/LLJITWithOptimizingIRTransform.cpp

 
 )";
 
 // A function object that creates a simple pass pipeline to apply to each
 // module as it passes through the IRTransformLayer.
 class MyOptimizationTransform {
 public:
   MyOptimizationTransform() : PM(std::make_unique<legacy::PassManager>()) {
+    PM->add(createTailCallMarkingPass());
     PM->add(createTailCallEliminationPass());
     PM->add(createFunctionInliningPass());
     PM->add(createIndVarSimplifyPass());
     PM->add(createCFGSimplificationPass());
   }
 
   Expected<ThreadSafeModule> operator()(ThreadSafeModule TSM,
                                         MaterializationResponsibility &R) {

llvm/include/llvm-c/Transforms/Scalar.h

 
 /** See llvm::createSROAPass function. */
 void LLVMAddScalarReplAggregatesPassWithThreshold(LLVMPassManagerRef PM,
                                                   int Threshold);
 
 /** See llvm::createSimplifyLibCallsPass function. */
 void LLVMAddSimplifyLibCallsPass(LLVMPassManagerRef PM);
 
+/** See llvm::createTailCallMarkingPass function. */
+void LLVMAddTailCallMarkingPass(LLVMPassManagerRef PM);
+
 /** See llvm::createTailCallEliminationPass function. */
 void LLVMAddTailCallEliminationPass(LLVMPassManagerRef PM);
 
 /** See llvm::demotePromoteMemoryToRegisterPass function. */
 void LLVMAddDemoteMemoryToRegisterPass(LLVMPassManagerRef PM);
 
 /** See llvm::createVerifierPass function. */
 void LLVMAddVerifierPass(LLVMPassManagerRef PM);

llvm/include/llvm/InitializePasses.h

 void initializeStripDebugDeclarePass(PassRegistry&);
 void initializeStripDebugMachineModulePass(PassRegistry &);
 void initializeStripGCRelocatesLegacyPass(PassRegistry &);
 void initializeStripNonDebugSymbolsPass(PassRegistry&);
 void initializeStripNonLineTableDebugLegacyPassPass(PassRegistry &);
 void initializeStripSymbolsPass(PassRegistry&);
 void initializeStructurizeCFGLegacyPassPass(PassRegistry &);
 void initializeTailCallElimPass(PassRegistry&);
+void initializeTailCallMarkPass(PassRegistry&);
 void initializeTailDuplicatePass(PassRegistry&);
 void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&);
 void initializeTargetPassConfigPass(PassRegistry&);
 void initializeTargetTransformInfoWrapperPassPass(PassRegistry&);
 void initializeThreadSanitizerLegacyPassPass(PassRegistry&);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);
 void initializeTypePromotionPass(PassRegistry&);

llvm/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::createDFAJumpThreadingPass();
       (void) llvm::createUnifyFunctionExitNodesPass();
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createEntryExitInstrumenterPass();

llvm/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

llvm/include/llvm/Transforms/Scalar/TailCallMarking.h

+//===-- TailCallMarking.h -----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass marks call instruction as "tail". More specifically, if it can
+// prove that callees do not access their caller stack frame, they are marked as
+// eligible for tail call elimination (by the code generator).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_TAILCALLMARKING_H
+#define LLVM_TRANSFORMS_SCALAR_TAILCALLMARKING_H
+
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+struct TailCallMarkPass : PassInfoMixin<TailCallMarkPass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_TAILCALLMARKING_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/Scalarizer.h"
 #include "llvm/Transforms/Scalar/SeparateConstOffsetFromGEP.h"
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/Sink.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/StraightLineStrengthReduce.h"
 #include "llvm/Transforms/Scalar/StructurizeCFG.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/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/CanonicalizeFreezeInLoops.h"
 #include "llvm/Transforms/Utils/Debugify.h"

llvm/lib/Passes/PassBuilderPipelines.cpp

 #include "llvm/Transforms/Scalar/MergedLoadStoreMotion.h"
 #include "llvm/Transforms/Scalar/NewGVN.h"
 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Scalar/SROA.h"
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.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/AssumeBundleBuilder.h"
 #include "llvm/Transforms/Utils/CanonicalizeAliases.h"
 #include "llvm/Transforms/Utils/InjectTLIMappings.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/Transforms/Utils/Mem2Reg.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 &&
       !Level.isOptimizingForSize())
     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(SROAPass());
 
   // 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),
                                                 PTO.EagerlyInvalidateAnalyses));
 
   MPM.addPass(
       createModuleToPostOrderCGSCCPassAdaptor(PostOrderFunctionAttrsPass()));

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("sink", SinkingPass())
 FUNCTION_PASS("slp-vectorizer", SLPVectorizerPass())
 FUNCTION_PASS("slsr", StraightLineStrengthReducePass())
 FUNCTION_PASS("speculative-execution", SpeculativeExecutionPass())
 FUNCTION_PASS("sroa", SROAPass())
 FUNCTION_PASS("strip-gc-relocates", StripGCRelocates())
 FUNCTION_PASS("structurizecfg", StructurizeCFGPass())
 FUNCTION_PASS("tailcallelim", TailCallElimPass())
+FUNCTION_PASS("tailcallmark", TailCallMarkPass())
 FUNCTION_PASS("unify-loop-exits", UnifyLoopExitsPass())
 FUNCTION_PASS("vector-combine", VectorCombinePass())
 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())

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

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());
 
   // TODO: Investigate the cost/benefit of tail call elimination on debugging.
-  if (OptLevel > 1)
+  if (OptLevel > 1) {
+    MPM.add(createTailCallMarkingPass());     // Eliminate tail calls
     MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
-  MPM.add(createCFGSimplificationPass());      // Merge & remove BBs
-  MPM.add(createReassociatePass());           // Reassociate expressions
+  }
+  MPM.add(createCFGSimplificationPass()); // Merge & remove BBs
+  MPM.add(createReassociatePass());       // Reassociate expressions
 
   // The matrix extension can introduce large vector operations early, which can
   // benefit from running vector-combine early on.
   if (EnableMatrix)
     MPM.add(createVectorCombinePass());
 
   // Begin the loop pass pipeline.
   if (EnableSimpleLoopUnswitch) {
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   addExtensionsToPM(EP_Peephole, PM);
   PM.add(createJumpThreadingPass(/*FreezeSelectCond*/ true));
 
   // Break up allocas
   PM.add(createSROAPass());
 
   // LTO provides additional opportunities for tailcall elimination due to
   // link-time inlining, and visibility of nocapture attribute.
-  if (OptLevel > 1)
+  if (OptLevel > 1) {
+    PM.add(createTailCallMarkingPass());
     PM.add(createTailCallEliminationPass());
+  }
 
   // Infer attributes on declarations, call sites, arguments, etc.
   PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture.
   // Run a few AA driven optimizations here and now, to cleanup the code.
   PM.add(createGlobalsAAWrapperPass()); // IP alias analysis.
 
   PM.add(createLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap));
   PM.add(NewGVN ? createNewGVNPass()

llvm/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_component_library(LLVMScalarOpts
   ScalarizeMaskedMemIntrin.cpp
   SeparateConstOffsetFromGEP.cpp
   SimpleLoopUnswitch.cpp
   SimplifyCFGPass.cpp
   Sink.cpp
   SpeculativeExecution.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

llvm/lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeRewriteStatepointsForGCLegacyPassPass(Registry);
   initializeScalarizeMaskedMemIntrinLegacyPassPass(Registry);
   initializeSCCPLegacyPassPass(Registry);
   initializeSROALegacyPassPass(Registry);
   initializeCFGSimplifyPassPass(Registry);
   initializeStructurizeCFGLegacyPassPass(Registry);
   initializeSimpleLoopUnswitchLegacyPassPass(Registry);
   initializeSinkingLegacyPassPass(Registry);
+  initializeTailCallMarkPass(Registry);
   initializeTailCallElimPass(Registry);
   initializeSeparateConstOffsetFromGEPLegacyPassPass(Registry);
   initializeSpeculativeExecutionLegacyPassPass(Registry);
   initializeStraightLineStrengthReduceLegacyPassPass(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 LLVMAddDemoteMemoryToRegisterPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createDemoteRegisterToMemoryPass());
 }
 

llvm/lib/Transforms/Scalar/TailCallMarking.cpp

+//===- TailCallMarking.cpp - Mark Tail Calls ------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file mark call instruction as "tail" if possible.
+// If it is guaranteed that callees do not access their caller stack frame,
+// calls would be marked as "tail".
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/TailCallMarking.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"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
+#define DEBUG_TYPE "tailcallmark"
+
+using namespace llvm;
+
+STATISTIC(NumMarked, "Number of calls marked as tail");
+
+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: {
+        auto &CB = cast<CallBase>(*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 (CB.isArgOperand(U) && CB.isByValArgument(CB.getArgOperandNo(U)))
+          continue;
+        bool IsNocapture =
+            CB.isDataOperand(U) && CB.doesNotCapture(CB.getDataOperandNo(U));
+        callUsesLocalStack(CB, 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(CallBase &CB, bool IsNocapture) {
+    // Add it to the list of alloca users.
+    AllocaUsers.insert(&CB);
+
+    // 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 (!CB.onlyReadsMemory())
+      EscapePoints.insert(&CB);
+  }
+
+  SmallPtrSet<Instruction *, 32> AllocaUsers;
+  SmallPtrSet<Instruction *, 32> EscapePoints;
+};
+} // namespace
+
+static bool markTails(Function &F, OptimizationRemarkEmitter *ORE) {
+  if (F.callsFunctionThatReturnsTwice())
+    return false;
+
+  // 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);
+      // A PseudoProbeInst has the IntrInaccessibleMemOnly tag hence it is
+      // considered accessing memory and will be marked as a tail call if we
+      // don't bail out here.
+      if (!CI || CI->isTailCall() || isa<DbgInfoIntrinsic>(&I) ||
+          isa<PseudoProbeInst>(&I))
+        continue;
+
+      // Special-case operand bundle "clang.arc.attachedcall".
+      bool IsNoTail =
+          CI->isNoTailCall() || CI->hasOperandBundlesOtherThan(
+                                    LLVMContext::OB_clang_arc_attachedcall);
+
+      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->args()) {
+          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();
+          NumMarked++;
+          Modified = true;
+          continue;
+        }
+      }
+
+      if (!IsNoTail && Escaped == UNESCAPED && !Tracker.AllocaUsers.count(CI))
+        DeferredTails.push_back(CI);
+    }
+
+    for (auto *SuccBB : successors(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();
+      NumMarked++;
+      Modified = true;
+    }
+  }
+
+  return Modified;
+}
+
+namespace {
+struct TailCallMark : public FunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+  TailCallMark() : FunctionPass(ID) {
+    initializeTailCallMarkPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
+    AU.setPreservesCFG();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addPreserved<OptimizationRemarkEmitterWrapperPass>();
+    AU.addPreserved<AAResultsWrapperPass>();
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+    return markTails(
+        F, &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
+  }
+};
+} // namespace
+
+char TailCallMark::ID = 0;
+INITIALIZE_PASS_BEGIN(TailCallMark, "tailcallmark", "Tail Call Marking", false,
+                      false)
+INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
+INITIALIZE_PASS_END(TailCallMark, "tailcallmark", "Tail Call Marking", false,
+                    false)
+
+FunctionPass *llvm::createTailCallMarkingPass() { return new TailCallMark(); }
+PreservedAnalyses TailCallMarkPass::run(Function &F,
+                                        FunctionAnalysisManager &AM) {
+
+  auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+  bool Changed = markTails(F, &ORE);
+  if (!Changed)
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  PA.preserve<GlobalsAA>();
+  return PA;
+}

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

if (!CB.onlyReadsMemory())
       EscapePoints.insert(&CB);
   }
 
   SmallPtrSet<Instruction *, 32> AllocaUsers;
   SmallPtrSet<Instruction *, 32> EscapePoints;
 };
 }
 
-static bool markTails(Function &F, OptimizationRemarkEmitter *ORE) {
-  if (F.callsFunctionThatReturnsTwice())
-    return false;
-
-  // 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);
-      // A PseudoProbeInst has the IntrInaccessibleMemOnly tag hence it is
-      // considered accessing memory and will be marked as a tail call if we
-      // don't bail out here.
-      if (!CI || CI->isTailCall() || isa<DbgInfoIntrinsic>(&I) ||
-          isa<PseudoProbeInst>(&I))
-        continue;
-
-      // Special-case operand bundle "clang.arc.attachedcall".
-      bool IsNoTail =
-          CI->isNoTailCall() || CI->hasOperandBundlesOtherThan(
-                                    LLVMContext::OB_clang_arc_attachedcall);
-
-      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->args()) {
-          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);
-    }
-
-    for (auto *SuccBB : successors(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;
-    }
-  }
-
-  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) {
   if (isa<DbgInfoIntrinsic>(I))
     return true;
bool TailRecursionEliminator::eliminate(Function &F,
                                         const TargetTransformInfo *TTI,
                                         AliasAnalysis *AA,
                                         OptimizationRemarkEmitter *ORE,
                                         DomTreeUpdater &DTU) {
   if (F.getFnAttribute("disable-tail-calls").getValueAsBool())
     return false;
 
   bool MadeChange = false;
-  MadeChange |= markTails(F, ORE);
 
   // 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 MadeChange;
 
   if (!canTRE(F))
     return MadeChange;

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

 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O3-NEXT: AggressiveInstCombinePass
 ; 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-O23SZ-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O23SZ-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: LoopSimplifyPass
 ; CHECK-O-NEXT: Running analysis: LoopAnalysis
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis

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

 ; CHECK-O23SZ-NEXT: Running pass: GlobalOptPass
 ; CHECK-O23SZ-NEXT: Running pass: GlobalDCEPass
 ; CHECK-O23SZ-NEXT: Running pass: ArgumentPromotionPass
 ; CHECK-O23SZ-NEXT: Running pass: InstCombinePass
 ; CHECK-EP-Peephole-NEXT: Running pass: NoOpFunctionPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: SROAPass on foo
+; CHECK-O23SZ-NEXT: Running pass: TailCallMarkPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: TailCallElimPass on foo
 ; CHECK-O23SZ-NEXT: Running pass: PostOrderFunctionAttrsPass on (foo)
 ; CHECK-O23SZ-NEXT: Running pass: RequireAnalysisPass<{{.*}}GlobalsAA
 ; CHECK-O23SZ-NEXT: Running analysis: GlobalsAA on [module]
 ; CHECK-O23SZ-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}AAManager
 ; CHECK-O23SZ-NEXT: Invalidating analysis: AAManager on foo
 ; CHECK-O23SZ-NEXT: Running pass: LoopSimplifyPass on foo
 ; CHECK-O23SZ-NEXT: Running analysis: LoopAnalysis on foo

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

 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O3-NEXT: Running pass: AggressiveInstCombinePass
 ; CHECK-O1-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O3-NEXT: Running pass: LibCallsShrinkWrapPass
+; CHECK-O23SZ-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O23SZ-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: LoopSimplifyPass
 ; CHECK-O-NEXT: Running analysis: LoopAnalysis
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis

llvm/test/Other/new-pm-thinlto-postlink-pgo-defaults.ll

 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O3-NEXT: Running pass: AggressiveInstCombinePass
 ; CHECK-O1-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O3-NEXT: Running pass: LibCallsShrinkWrapPass
+; CHECK-O23SZ-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O23SZ-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: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy

llvm/test/Other/new-pm-thinlto-postlink-samplepgo-defaults.ll

 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O3-NEXT: Running pass: AggressiveInstCombinePass
 ; CHECK-O1-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O3-NEXT: Running pass: LibCallsShrinkWrapPass
+; CHECK-O23SZ-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O23SZ-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: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy

llvm/test/Other/new-pm-thinlto-prelink-pgo-defaults.ll

 ; CHECK-O-DAG: Running analysis: BranchProbabilityAnalysis on foo
 ; CHECK-O-DAG: Running analysis: PostDominatorTreeAnalysis on foo
 ; CHECK-O3-NEXT: Running pass: AggressiveInstCombinePass
 ; CHECK-O1-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O3-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: PGOMemOPSizeOpt
 ; CHECK-O3-NEXT: Running pass: PGOMemOPSizeOpt
+; CHECK-O23SZ-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O23SZ-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: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy

llvm/test/Other/new-pm-thinlto-prelink-samplepgo-defaults.ll

 ; CHECK-O23SZ-NEXT: Running pass: CorrelatedValuePropagationPass
 ; CHECK-O23SZ-NEXT: Invalidating analysis: LazyValueAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O3-NEXT: Running pass: AggressiveInstCombinePass
 ; CHECK-O1-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O2-NEXT: Running pass: LibCallsShrinkWrapPass
 ; CHECK-O3-NEXT: Running pass: LibCallsShrinkWrapPass
+; CHECK-O23SZ-NEXT: Running pass: TailCallMarkPass
 ; CHECK-O23SZ-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: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy

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

-; RUN: opt < %s -basic-aa -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 -basic-aa -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"
 

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

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

llvm/test/Transforms/TailCallElim/EraseBB.ll

-; RUN: opt -passes=tailcallelim -verify-dom-info -S < %s 2>&1 | FileCheck %s
+; RUN: opt -passes=tailcallmark,tailcallelim -verify-dom-info -S < %s 2>&1 | FileCheck %s
 
 ; CHECK: add nsw i32
 ; CHECK-NEXT: br label
 ; CHECK: add nsw i32
 ; CHECK-NEXT: br label
 ; CHECK-NOT: Uses remain when a value is destroyed
 define i32 @test(i32 %n) {
 entry:

llvm/test/Transforms/TailCallElim/accum_recursion.ll

-; RUN: opt < %s -passes=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
   br i1 %tmp.1, label %then, label %else
 then:
   %tmp.6 = add i32 %x, -1
   %recurse = call i32 @test1_factorial( i32 %tmp.6 )

llvm/test/Transforms/TailCallElim/ackermann.ll

 ; REQUIRES: asserts
 ; This function contains two tail calls, which should be eliminated
-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -stats -disable-output 2>&1 | grep "2 tailcallelim"
+; RUN: opt < %s -passes=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

llvm/test/Transforms/TailCallElim/basic.ll

-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=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() {

llvm/test/Transforms/TailCallElim/debugloc.ll

-; RUN: opt < %s -passes=debugify,tailcallelim -S | FileCheck %s
+; RUN: opt < %s -passes=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

llvm/test/Transforms/TailCallElim/deopt-bundle.ll

-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=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:

llvm/test/Transforms/TailCallElim/dont_reorder_load.ll

-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | grep call | count 4
+; RUN: opt < %s -passes=tailcallmark,tailcallelim -verify-dom-info -S | grep call | count 4
 ; PR4323
 
 ; Several cases where tail call elimination should not move the load above the
 ; call, and thus can't eliminate the tail recursion.
 
 
 @extern_weak_global = extern_weak global i32    ; <i32*> [#uses=1]
 

llvm/test/Transforms/TailCallElim/dup_tail.ll

 ; REQUIRES: asserts
 ; Duplicate the return into if.end to enable TCE.
-; RUN: opt -passes=tailcallelim -verify-dom-info -stats -disable-output < %s 2>&1 | FileCheck %s
+; RUN: opt -passes=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
 

llvm/test/Transforms/TailCallElim/inf-recursion.ll

-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=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) {

llvm/test/Transforms/TailCallElim/notail.ll

-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=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

llvm/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

llvm/test/Transforms/TailCallElim/reorder_load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=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.
 
 

llvm/test/Transforms/TailCallElim/setjmp.ll

-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=tailcallmark,tailcallelim -verify-dom-info -S | FileCheck %s
 
 ; Test that we don't tail call in a functions that calls returns_twice
 ; functions.
 
 declare void @bar()
 
 ; CHECK: foo1
 ; CHECK-NOT: tail call void @bar()

llvm/test/Transforms/TailCallElim/tre-byval-parameter-2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=tailcallmark,tailcallelim -verify-dom-info -S | FileCheck %s
 
 ; the test was generated from the following C++ source:
 ;
 ; #include <stdio.h>
 ; typedef struct A { long long x[10] = {0}; } A;
 ; A global;
 ; void dostuff(A a, A b, int i) {
 ;  if (i==10) return;

llvm/test/Transforms/TailCallElim/tre-byval-parameter.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=tailcallmark,tailcallelim -verify-dom-info -S | FileCheck %s
 
 ; the test was generated from the following C++ source:
 ;
 ; int zoo ( S p1 );
 ;
 ; int foo ( int count, S p1 ) {
 ;   if ( count > 10 )
 ;     return zoo(p1);

llvm/test/Transforms/TailCallElim/tre-multiple-exits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=tailcallmark,tailcallelim -verify-dom-info -S | FileCheck %s
 
 ; This test checks that TRE would be done for only one recursive call.
 ; The test_multiple_exits function has three recursive calls.
 ; First recursive call could not be eliminated because there is
 ; escaped pointer to local variable. Second recursive call could
 ; be eliminated. Thrid recursive call could not be eliminated since
 ; this is not last call. Thus, test checks that TRE would be done
 ; for only second recursive call.

llvm/test/Transforms/TailCallElim/tre-noncapturing-alloca-calls.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
+; RUN: opt < %s -passes=tailcallmark,tailcallelim -verify-dom-info -S | FileCheck %s
 
 ; IR for that test was generated from the following C++ source:
 ;
 ;int count;
 ;__attribute__((noinline)) void globalIncrement(const int* param) { count += *param; }
 ;
 ;void test(int recurseCount)
 ;{

polly/lib/CodeGen/CodegenCleanup.cpp

virtual bool doInitialization(Module &M) override {
     FPM->add(createSROAPass());
     FPM->add(createEarlyCSEPass(true));
     FPM->add(createSpeculativeExecutionIfHasBranchDivergencePass());
     FPM->add(createJumpThreadingPass());
     FPM->add(createCorrelatedValuePropagationPass());
     FPM->add(createCFGSimplificationPass());
     FPM->add(createInstructionCombiningPass(true));
     FPM->add(createLibCallsShrinkWrapPass());
+    FPM->add(createTailCallMarkingPass());
     FPM->add(createTailCallEliminationPass());
     FPM->add(createCFGSimplificationPass());
     FPM->add(createReassociatePass());
     FPM->add(createLoopRotatePass(-1));
     FPM->add(createGVNPass());
     FPM->add(createLICMPass());
     FPM->add(createLoopUnswitchPass());
     FPM->add(createCFGSimplificationPass());

polly/lib/Transform/Canonicalization.cpp

 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
 #include "llvm/Transforms/Scalar/IndVarSimplify.h"
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
+#include "llvm/Transforms/Scalar/TailCallMarking.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/Mem2Reg.h"
 
 using namespace llvm;
 using namespace polly;
 
 static cl::opt<bool>
     PollyInliner("polly-run-inliner",
                  cl::desc("Run an early inliner pass before Polly"), cl::Hidden,
                  cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 void polly::registerCanonicalicationPasses(llvm::legacy::PassManagerBase &PM) {
   bool UseMemSSA = true;
   PM.add(llvm::createPromoteMemoryToRegisterPass());
   PM.add(llvm::createEarlyCSEPass(UseMemSSA));
   PM.add(llvm::createInstructionCombiningPass());
   PM.add(llvm::createCFGSimplificationPass());
+  PM.add(llvm::createTailCallMarkingPass());
   PM.add(llvm::createTailCallEliminationPass());
   PM.add(llvm::createCFGSimplificationPass());
   PM.add(llvm::createReassociatePass());
   PM.add(llvm::createLoopRotatePass());
   if (PollyInliner) {
     PM.add(llvm::createFunctionInliningPass(200));
     PM.add(llvm::createPromoteMemoryToRegisterPass());
     PM.add(llvm::createCFGSimplificationPass());
polly::buildCanonicalicationPassesForNPM(llvm::ModulePassManager &MPM,
                                          llvm::OptimizationLevel Level) {
   FunctionPassManager FPM;
 
   bool UseMemSSA = true;
   FPM.addPass(PromotePass());
   FPM.addPass(EarlyCSEPass(UseMemSSA));
   FPM.addPass(InstCombinePass());
   FPM.addPass(SimplifyCFGPass());
+  FPM.addPass(TailCallMarkPass());
   FPM.addPass(TailCallElimPass());
   FPM.addPass(SimplifyCFGPass());
   FPM.addPass(ReassociatePass());
   {
     LoopPassManager LPM;
     LPM.addPass(LoopRotatePass(Level != OptimizationLevel::Oz));
     FPM.addPass(createFunctionToLoopPassAdaptor<LoopPassManager>(
         std::move(LPM), /*UseMemorySSA=*/false,