[CSSPGO] Pseudo probe instrumentation for basic blocks.

[hoy]

Summary

This change introduces a low-cost instrumentation technique for AutoFDO, namely pseudo probe. Please see RFC here: https://groups.google.com/g/llvm-dev/c/1p1rdYbL93s

Being able to profile production binaries is a key advantage of AutoFDO over Instrumentation PGO, but it also comes with a big challenge. While using line number and discriminator as anchor for profile mapping incurs zero run time overhead for AutoFDO, it’s not as accurate as instrumented probes. This is because the instrumented probes are part of the IR, rather than metadata attached to the IR like !dbg. That has two implications: 1) it’s easier to maintain IR than metadata for optimization passes; 2) probe blocks some CFG transformations that can mess up profile correlation.
 
With the proposed pseudo instrumentation, we can achieve most of the benefit of instrumentation PGO in little runtime overhead. We instrument each basic block with a pseudo probe associated with the block Id. Unlike in PGO instrumentation where a counter is implemented as a persisting operation such as atomic read/write or runtime helper call, a pseudo probe is implemented as a dedicated intrinsic call with the IntrInaccessibleMemOnly attribute. The intrinsic comes with most of the semantics of a PGO counter but is much less optimization-intrusive. 
 
The pseudo probe intrinsic calls are on the IR throughout the optimization and code generation pipeline and are materialized as a piece of binary data stored in a separate .pseudo_probe data section. The section is then used to map binary samples back to blocks of CFG during profile generation. There are also no real machine instructions generated for a pseudo probe and the.pseudo_probe section won’t be loaded into memory at runtime, therefore they should incur very little runtime overhead.

Let's now look at an example. Given the following LLVM IR:

define internal void @foo2(i32 %x, void (i32)* %f) !dbg !4 {
bb0:
  %cmp = icmp eq i32 %x, 0
   br i1 %cmp, label %bb1, label %bb2
bb1:
   br label %bb3
bb2:
   br label %bb3
bb3:
   ret void
}

The instrumented IR will look like below. Note that each llvm.pseudoprobe intrinsic call represents a pseudo probe at a block, of which the first parameter is the GUID of the probe’s owner function and the second parameter is the probe’s ID.

define internal void @foo2(i32 %x, void (i32)* %f) !dbg !4 {
bb0:
   %cmp = icmp eq i32 %x, 0
   call void @llvm.pseudoprobe(i64 837061429793323041, i64 1)
   br i1 %cmp, label %bb1, label %bb2
bb1:                                             
   call void @llvm.pseudoprobe(i64 837061429793323041, i64 2)
   br label %bb3
bb2:                                              
   call void @llvm.pseudoprobe(i64 837061429793323041, i64 3)
   br label %bb3
bb3:                                              
   call void @llvm.pseudoprobe(i64 837061429793323041, i64 4)
   ret void
}

One implication from pseudo-probe instrumentation is that the profile is now sensitive to CFG changes. We perform the pseudo instrumentation very early in the pre-LTO pipeline, before any CFG transformation. This ensures that the CFG instrumented and annotated is stable. We added SampleProfileProber that performs the pseudo instrumentation and runs independent of profile annotation.

An llvm.pseudoprobe intrinsic call will be lowered into a target-independent operation named PSEUDO_PROBE. The MIR shown below corresponds to the previous example. Note that block bb3 is duplicated into bb1 and bb2 where its probe is duplicated too. This allows for an accurate execution count to be collected for bb3, which is basically the sum of the counts of bb1 and bb2.

bb.0.bb0:
   frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp
   TEST32rr killed renamable $edi, renamable $edi, implicit-def $eflags
   PSEUDO_PROBE 837061429793323041, 1, 0
   $edi = MOV32ri 1, debug-location !13; test.c:0
   JCC_1 %bb.1, 4, implicit $eflags

bb.2.bb2:
   PSEUDO_PROBE 837061429793323041, 3, 0
   PSEUDO_PROBE 837061429793323041, 4, 0
   $rax = frame-destroy POP64r implicit-def $rsp, implicit $rsp
   RETQ

bb.1.bb1:
   PSEUDO_PROBE 837061429793323041, 2, 0
   PSEUDO_PROBE 837061429793323041, 4, 0
   $rax = frame-destroy POP64r implicit-def $rsp, implicit $rsp
   RETQ

The target op PSEUDO_PROBE will be converted into a piece of binary data by the object emitter with no machine instructions generated.

As a starter patch of the whole pseudo probe work, this change focus on the block instrumentation part. The callsite instrumentation and the materialization/encoding of probes will come in separate changes.

A new clang switch -fpseudo-probe-for-profiling is added to enable AutoFDO with pseudo instrumentation, similar to -fdebug-info-for-profiling for AutoFDO.

[hoy]

Updating D86193: [CSSPGO] Pseudo probe instrumentation for basic blocks

[davidxl]

A heads up -- I won't be able to review patch until mid Sept. Hope this is fine.

[hoy]

Updating D86193: [CSSPGO] Pseudo probe instrumentation for basic blocks.

[hoy]

In D86193#2227129, @davidxl wrote:

A heads up -- I won't be able to review patch until mid Sept. Hope this is fine.

Thanks for the heads-up. That's fine. We can wait for your input.

[wmi]

Thanks for the patch! A few questions:

probe blocks some CFG transformations that can mess up profile correlation.

Can you enumerate some CFG transformations which be blocked? Is it possible that some CFG transformations being blocked are actually beneficial for later optimizations?

Are the intrinsic probes counted when computing bb size and function size?

And could you split the patches into small parts for easier review. For example, Add the intrinsic support in IR and MIR. SampleProfileProbe pass. -fpseudo-probe-for-profiling support. changes in various passes.

[hoy]

In D86193#2232609, @wmi wrote:

Thanks for the patch! A few questions:

probe blocks some CFG transformations that can mess up profile correlation.

Can you enumerate some CFG transformations which be blocked? Is it possible that some CFG transformations being blocked are actually beneficial for later optimizations?

There are some optimizations such as if-convert, tail call elimination, that were initially blocked by the pseudo probe intrinsic but is now unblocked by fixes included in this change. With the current change we do not see perf degradation out of SPEC and one of our internal large services.

The main optimizations left blocked intentionally are those that merge blocks for smaller code size, such as tail merge which is the opposite of jump threading. We believe that those optimizations are not very beneficial for performance and AutoFDO. But if things are changed we can always unblock them.

Are the intrinsic probes counted when computing bb size and function size?

That's a good question. On the IR level, pseudo probe intrinsics are treated in a similar way of the debug intrinsics and the side-effect intrinsics. On the MIR level, pseudo probe intrinsics are implemented as a StandardPseudoInstruction. So they should not be counted towards real code size.

And could you split the patches into small parts for easier review. For example, Add the intrinsic support in IR and MIR. SampleProfileProbe pass. -fpseudo-probe-for-profiling support. changes in various passes.

Thanks for the suggestion. Agreed the current patch is too big to review. Will come up with a list of breakdowns.

[wmi]

There are some optimizations such as if-convert, tail call elimination, that were initially blocked by the pseudo probe intrinsic but is now unblocked by fixes included in this change. With the current change we do not see perf degradation out of SPEC and one of our internal large services.
The main optimizations left blocked intentionally are those that merge blocks for smaller code size, such as tail merge which is the opposite of jump threading. We believe that those optimizations are not very beneficial for performance and AutoFDO.

If the optimizations are not very beneficial for performance and AutoFDO and should be blocked, it may be better to block them in a more general way and not depend on pseudo probe, because blocking them may also be beneficial for debug info based AutoFDO.

Another reason is that pseudo probe looks pretty much like debug information to me. They are used to annotate the IR but shouldn't affect the transformation. Binaries built w/wo debug information are required to be identical in LLVM. I think that requirement could be applied on pseudo probe as well. It is even better to have some test to enforce it so that no change in the future could break the requirement.

[hoy]

In D86193#2240353, @wmi wrote:

There are some optimizations such as if-convert, tail call elimination, that were initially blocked by the pseudo probe intrinsic but is now unblocked by fixes included in this change. With the current change we do not see perf degradation out of SPEC and one of our internal large services.
The main optimizations left blocked intentionally are those that merge blocks for smaller code size, such as tail merge which is the opposite of jump threading. We believe that those optimizations are not very beneficial for performance and AutoFDO.

If the optimizations are not very beneficial for performance and AutoFDO and should be blocked, it may be better to block them in a more general way and not depend on pseudo probe, because blocking them may also be beneficial for debug info based AutoFDO.

In theory, yes, we should have a black list of transforms (mainly related to block merge) that are not needed by AutoFDO and block them. In reality it might take quite some efforts to figure them out. Pseudo probe, on the other hand, starts with blocking those transforms in the first place and relax the ones that might actually help AutoFDO.

Another reason is that pseudo probe looks pretty much like debug information to me. They are used to annotate the IR but shouldn't affect the transformation. Binaries built w/wo debug information are required to be identical in LLVM. I think that requirement could be applied on pseudo probe as well. It is even better to have some test to enforce it so that no change in the future could break the requirement.

Good point! Yes, pseudo probe is implemented in a similar way with the debug intrinsics. However they are not guaranteed to not affect the codegen since its main purpose is to achieve an accurate profile correlation with low cost. Regarding the cost, it sits somewhere between the debug intrinsics and the PGO instrumentation and close to a zero cost in practice. Agreed that it would be better to have tests protect the pseudo probe cost from going too high, but not sure which optimizations we should start with. Maybe to start with some critical optimizations like inlining, vectorization?

[wmi]

In D86193#2240502, @hoy wrote:

In D86193#2240353, @wmi wrote:

There are some optimizations such as if-convert, tail call elimination, that were initially blocked by the pseudo probe intrinsic but is now unblocked by fixes included in this change. With the current change we do not see perf degradation out of SPEC and one of our internal large services.
The main optimizations left blocked intentionally are those that merge blocks for smaller code size, such as tail merge which is the opposite of jump threading. We believe that those optimizations are not very beneficial for performance and AutoFDO.

If the optimizations are not very beneficial for performance and AutoFDO and should be blocked, it may be better to block them in a more general way and not depend on pseudo probe, because blocking them may also be beneficial for debug info based AutoFDO.

In theory, yes, we should have a black list of transforms (mainly related to block merge) that are not needed by AutoFDO and block them. In reality it might take quite some efforts to figure them out. Pseudo probe, on the other hand, starts with blocking those transforms in the first place and relax the ones that might actually help AutoFDO.

Another reason is that pseudo probe looks pretty much like debug information to me. They are used to annotate the IR but shouldn't affect the transformation. Binaries built w/wo debug information are required to be identical in LLVM. I think that requirement could be applied on pseudo probe as well. It is even better to have some test to enforce it so that no change in the future could break the requirement.

Good point! Yes, pseudo probe is implemented in a similar way with the debug intrinsics. However they are not guaranteed to not affect the codegen since its main purpose is to achieve an accurate profile correlation with low cost. Regarding the cost, it sits somewhere between the debug intrinsics and the PGO instrumentation and close to a zero cost in practice.

I see. It makes sense to fix up some important transformations to achieve the goal of low cost. To achieve the goal of not affecting codegen needs a lot more effort to test and fix up all over the pipeline. I don't mean to have it ready in the patch, but I think it maybe something worthy to strive for later on.

Agreed that it would be better to have tests protect the pseudo probe cost from going too high, but not sure which optimizations we should start with. Maybe to start with some critical optimizations like inlining, vectorization?

The test I have in my mind comes from debug info. It is to bootstrap llvm with and without debug information. The test is to check whether the binaries built after stripping the debug information are identical. I am thinking pseudo probe can have such test setup somewhere sometime in the future. Same as above, it doesn't have to be ready currently.

[hoy]

In D86193#2240596, @wmi wrote:

In D86193#2240502, @hoy wrote:

In D86193#2240353, @wmi wrote:

There are some optimizations such as if-convert, tail call elimination, that were initially blocked by the pseudo probe intrinsic but is now unblocked by fixes included in this change. With the current change we do not see perf degradation out of SPEC and one of our internal large services.
The main optimizations left blocked intentionally are those that merge blocks for smaller code size, such as tail merge which is the opposite of jump threading. We believe that those optimizations are not very beneficial for performance and AutoFDO.

If the optimizations are not very beneficial for performance and AutoFDO and should be blocked, it may be better to block them in a more general way and not depend on pseudo probe, because blocking them may also be beneficial for debug info based AutoFDO.

In theory, yes, we should have a black list of transforms (mainly related to block merge) that are not needed by AutoFDO and block them. In reality it might take quite some efforts to figure them out. Pseudo probe, on the other hand, starts with blocking those transforms in the first place and relax the ones that might actually help AutoFDO.

Another reason is that pseudo probe looks pretty much like debug information to me. They are used to annotate the IR but shouldn't affect the transformation. Binaries built w/wo debug information are required to be identical in LLVM. I think that requirement could be applied on pseudo probe as well. It is even better to have some test to enforce it so that no change in the future could break the requirement.

Good point! Yes, pseudo probe is implemented in a similar way with the debug intrinsics. However they are not guaranteed to not affect the codegen since its main purpose is to achieve an accurate profile correlation with low cost. Regarding the cost, it sits somewhere between the debug intrinsics and the PGO instrumentation and close to a zero cost in practice.

I see. It makes sense to fix up some important transformations to achieve the goal of low cost. To achieve the goal of not affecting codegen needs a lot more effort to test and fix up all over the pipeline. I don't mean to have it ready in the patch, but I think it maybe something worthy to strive for later on.

Sounds good, we will be accumulating a list of AutoFDO-unfriendly transforms over time.

Agreed that it would be better to have tests protect the pseudo probe cost from going too high, but not sure which optimizations we should start with. Maybe to start with some critical optimizations like inlining, vectorization?

The test I have in my mind comes from debug info. It is to bootstrap llvm with and without debug information. The test is to check whether the binaries built after stripping the debug information are identical. I am thinking pseudo probe can have such test setup somewhere sometime in the future. Same as above, it doesn't have to be ready currently.

I like the idea. It would catch a regression on pseudo probe with new optimization changes. Let me think about it. Thanks!

[wmi]

The patches split from the main one look good to me. Please see if David has further comments.

[hoy]

@davidxl I'm wondering if it is a good time for you to start reviewing the patches. Please let me know if you need more time. Thanks!

[hoy]

Abandoning this diff which has been broken into four other diffs.

clang/include/clang/Basic/CodeGenOptions.def

 
 /// Whether we should use the undefined behaviour optimization for control flow
 /// paths that reach the end of a function without executing a required return.
 CODEGENOPT(StrictReturn, 1, 1)
 
 /// Whether emit extra debug info for sample pgo profile collection.
 CODEGENOPT(DebugInfoForProfiling, 1, 0)
 
+/// Whether emit pseudo probes for sample pgo profile collection.
+CODEGENOPT(PseudoProbeForProfiling, 1, 0)
+
 /// Whether 3-component vector type is preserved.
 CODEGENOPT(PreserveVec3Type, 1, 0)
 
 /// Whether to emit .debug_gnu_pubnames section instead of .debug_pubnames.
 CODEGENOPT(DebugNameTable, 2, 0)
 
 /// Whether to use DWARF base address specifiers in .debug_ranges.
 CODEGENOPT(DebugRangesBaseAddress, 1, 0)

clang/include/clang/Driver/Options.td

 def fno_profile_use : Flag<["-"], "fno-profile-use">,
     Alias<fno_profile_instr_use>;
 def fprofile_filter_files_EQ : Joined<["-"], "fprofile-filter-files=">,
     Group<f_Group>, Flags<[CC1Option, CoreOption]>,
     HelpText<"Instrument only functions from files where names match any regex separated by a semi-colon">;
 def fprofile_exclude_files_EQ : Joined<["-"], "fprofile-exclude-files=">,
     Group<f_Group>, Flags<[CC1Option, CoreOption]>,
     HelpText<"Instrument only functions from files where names don't match all the regexes separated by a semi-colon">;
+def fpseudo_probe_for_profiling : Flag<["-"], "fpseudo-probe-for-profiling">,
+    Group<f_Group>, Flags<[DriverOption, CC1Option]>,
+    HelpText<"Emit pseudo probes for sample profiler">;
+def fno_pseudo_probe_for_profiling : Flag<["-"], "fno-pseudo-probe-for-profiling">,
+    Group<f_Group>, Flags<[DriverOption, CC1Option]>,
+    HelpText<"Do not emit pseudo probes for sample profiler.">;
 def forder_file_instrumentation : Flag<["-"], "forder-file-instrumentation">,
     Group<f_Group>, Flags<[CC1Option, CoreOption]>,
     HelpText<"Generate instrumented code to collect order file into default.profraw file (overridden by '=' form of option or LLVM_PROFILE_FILE env var)">;
 
 defm addrsig : OptInFFlag<"addrsig", "Emit", "Don't emit", " an address-significance table", [CoreOption]>;
 defm blocks : OptInFFlag<"blocks", "Enable the 'blocks' language feature", "", "", [CoreOption]>;
 def fbootclasspath_EQ : Joined<["-"], "fbootclasspath=">, Group<f_Group>;
 def fborland_extensions : Flag<["-"], "fborland-extensions">, Group<f_Group>, Flags<[CC1Option]>,

clang/lib/CodeGen/BackendUtil.cpp

else if (CodeGenOpts.hasProfileIRUse()) {
     // -fprofile-use.
     auto CSAction = CodeGenOpts.hasProfileCSIRUse() ? PGOOptions::CSIRUse
                                                     : PGOOptions::NoCSAction;
     PGOOpt = PGOOptions(CodeGenOpts.ProfileInstrumentUsePath, "",
                         CodeGenOpts.ProfileRemappingFile, PGOOptions::IRUse,
                         CSAction, CodeGenOpts.DebugInfoForProfiling);
   } else if (!CodeGenOpts.SampleProfileFile.empty())
     // -fprofile-sample-use
+    PGOOpt = PGOOptions(
+        CodeGenOpts.SampleProfileFile, "", CodeGenOpts.ProfileRemappingFile,
+        PGOOptions::SampleUse, PGOOptions::NoCSAction,
+        CodeGenOpts.DebugInfoForProfiling, CodeGenOpts.PseudoProbeForProfiling);
+  else if (CodeGenOpts.PseudoProbeForProfiling)
+    // -fpseudo-probe-for-profiling
     PGOOpt =
-        PGOOptions(CodeGenOpts.SampleProfileFile, "",
-                   CodeGenOpts.ProfileRemappingFile, PGOOptions::SampleUse,
-                   PGOOptions::NoCSAction, CodeGenOpts.DebugInfoForProfiling);
+        PGOOptions("", "", "", PGOOptions::NoAction, PGOOptions::NoCSAction,
+                   CodeGenOpts.DebugInfoForProfiling, true);
   else if (CodeGenOpts.DebugInfoForProfiling)
     // -fdebug-info-for-profiling
     PGOOpt = PGOOptions("", "", "", PGOOptions::NoAction,
                         PGOOptions::NoCSAction, true);
 
   // Check to see if we want to generate a CS profile.
   if (CodeGenOpts.hasProfileCSIRInstr()) {
     assert(!CodeGenOpts.hasProfileCSIRUse() &&

clang/lib/Driver/ToolChains/Clang.cpp

if (Arg *A = getLastProfileSampleUseArg(Args)) {
     StringRef fname = A->getValue();
     if (!llvm::sys::fs::exists(fname))
       D.Diag(diag::err_drv_no_such_file) << fname;
     else
       A->render(Args, CmdArgs);
   }
   Args.AddLastArg(CmdArgs, options::OPT_fprofile_remapping_file_EQ);
 
+  if (Args.hasFlag(options::OPT_fpseudo_probe_for_profiling,
+                   options::OPT_fno_pseudo_probe_for_profiling, false))
+    CmdArgs.push_back("-fpseudo-probe-for-profiling");
+
   RenderBuiltinOptions(TC, RawTriple, Args, CmdArgs);
 
   if (!Args.hasFlag(options::OPT_fassume_sane_operator_new,
                     options::OPT_fno_assume_sane_operator_new))
     CmdArgs.push_back("-fno-assume-sane-operator-new");
 
   // -fblocks=0 is default.
   if (Args.hasFlag(options::OPT_fblocks, options::OPT_fno_blocks,

clang/lib/Frontend/CompilerInvocation.cpp

static bool ParseCodeGenArgs(CodeGenOptions &Opts, ArgList &Args, InputKind IK,
   Opts.RerollLoops = Args.hasArg(OPT_freroll_loops);
 
   Opts.DisableIntegratedAS = Args.hasArg(OPT_fno_integrated_as);
   Opts.Autolink = !Args.hasArg(OPT_fno_autolink);
   Opts.SampleProfileFile =
       std::string(Args.getLastArgValue(OPT_fprofile_sample_use_EQ));
   Opts.DebugInfoForProfiling = Args.hasFlag(
       OPT_fdebug_info_for_profiling, OPT_fno_debug_info_for_profiling, false);
+  Opts.PseudoProbeForProfiling =
+      Args.hasFlag(OPT_fpseudo_probe_for_profiling,
+                   OPT_fno_pseudo_probe_for_profiling, false);
   Opts.DebugNameTable = static_cast<unsigned>(
       Args.hasArg(OPT_ggnu_pubnames)
           ? llvm::DICompileUnit::DebugNameTableKind::GNU
           : Args.hasArg(OPT_gpubnames)
                 ? llvm::DICompileUnit::DebugNameTableKind::Default
                 : llvm::DICompileUnit::DebugNameTableKind::None);
   Opts.DebugRangesBaseAddress = Args.hasArg(OPT_fdebug_ranges_base_address);
 

clang/test/CodeGen/emit-pseudo-probe.c

+// RUN: %clang -O2  -fexperimental-new-pass-manager -fpseudo-probe-for-profiling -g -emit-llvm -S -o - %s | FileCheck %s --check-prefix=CHECK
+
+// Check the generation of pseudoprobe intrinsic call
+
+void bar();
+void go();
+
+void foo(int x) {
+  // CHECK: call void @llvm.pseudoprobe(i64 [[#GUID:]], i64 1)
+  if (x == 0)
+    // CHECK: call void @llvm.pseudoprobe(i64 [[#GUID]], i64 2)
+    bar();
+  else
+    // CHECK: call void @llvm.pseudoprobe(i64 [[#GUID]], i64 3)
+    go();
+  // CHECK: call void @llvm.pseudoprobe(i64 [[#GUID]], i64 4)
+}
+
+void foo2(void (*f)()) {
+  // Check pseudo_probe metadata attached to the indirect call instruction.
+  // CHECK: call void @llvm.pseudoprobe(i64 [[#GUID2:]], i64 1)
+  // CHECK: {{.*}} call {{.*}} !dbg ![[#PROBE0:]]
+  f();
+}
+
+// Check the generation of module - level metadata that contains function info necessary to
+// synthesize probe - based sample counts.The format is;
+// { FunctionName, FunctionGUID, FunctionHash }
+// CHECK : !llvm.pseudo_probe_desc = !{![[#DESC0:]], ![[#DESC1:]]};
+// CHECK : ![[#DESC0]] = !{!"foo", i64[[#GUID]], i64[[#HASH:]]};
+// CHECK : ![[#DESC1]] = !{ !"foo2", i64[[#GUID2]], i64[[#HASH2:]] }
+// CHECK : ![[#PROBE0]] = !DILocation(line: [[#]], column: [[#]], scope: ![[#SCOPE:]])
+// CHECK : ![[#SCOPE]] = !DILexicalBlockFile(scope: ![[#]], file: ![[#]], discriminator: 16777218)

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   unsigned getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
                                  TTI::TargetCostKind CostKind) {
     switch (ICA.getID()) {
     default:
       break;
     case Intrinsic::annotation:
     case Intrinsic::assume:
     case Intrinsic::sideeffect:
+    case Intrinsic::pseudoprobe:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_value:
     case Intrinsic::dbg_label:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::launder_invariant_group:
     case Intrinsic::strip_invariant_group:
     case Intrinsic::is_constant:

llvm/include/llvm/CodeGen/BasicTTIImpl.h

case Intrinsic::fmuladd:
       break;
     case Intrinsic::experimental_constrained_fmuladd:
       ISDs.push_back(ISD::STRICT_FMA);
       break;
     // FIXME: We should return 0 whenever getIntrinsicCost == TCC_Free.
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::sideeffect:
+    case Intrinsic::pseudoprobe:
       return 0;
     case Intrinsic::masked_store: {
       Type *Ty = Tys[0];
       Align TyAlign = thisT()->DL.getABITypeAlign(Ty);
       return thisT()->getMaskedMemoryOpCost(Instruction::Store, Ty, TyAlign, 0,
                                             CostKind);
     }
     case Intrinsic::masked_load: {

llvm/include/llvm/CodeGen/CommandFlags.h

 llvm::DebuggerKind getDebuggerTuningOpt();
 
 bool getEnableStackSizeSection();
 
 bool getEnableAddrsig();
 
 bool getEmitCallSiteInfo();
 
+bool getPseudoProbeForProfiling();
+
 bool getEnableDebugEntryValues();
 
 bool getForceDwarfFrameSection();
 
 bool getXRayOmitFunctionIndex();
 
 /// Create this object with static storage to register codegen-related command
 /// line options.

llvm/include/llvm/CodeGen/ISDOpcodes.h

   GC_TRANSITION_END,
 
   /// GET_DYNAMIC_AREA_OFFSET - get offset from native SP to the address of
   /// the most recent dynamic alloca. For most targets that would be 0, but
   /// for some others (e.g. PowerPC, PowerPC64) that would be compile-time
   /// known nonzero constant. The only operand here is the chain.
   GET_DYNAMIC_AREA_OFFSET,
 
+  /// Pseudo probe for AutoFDO, as a place holder in a basic block to improve
+  /// the sample counts quality.
+  PSEUDO_PROBE,
+
   /// VSCALE(IMM) - Returns the runtime scaling factor used to calculate the
   /// number of elements within a scalable vector. IMM is a constant integer
   /// multiplier that is applied to the runtime value.
   VSCALE,
 
   /// Generic reduction nodes. These nodes represent horizontal vector
   /// reduction operations, producing a scalar result.
   /// The STRICT variants perform reductions in sequential order. The first

llvm/include/llvm/CodeGen/MachineInstr.h

bool isMetaInstruction() const {
     case TargetOpcode::KILL:
     case TargetOpcode::CFI_INSTRUCTION:
     case TargetOpcode::EH_LABEL:
     case TargetOpcode::GC_LABEL:
     case TargetOpcode::DBG_VALUE:
     case TargetOpcode::DBG_LABEL:
     case TargetOpcode::LIFETIME_START:
     case TargetOpcode::LIFETIME_END:
+    case TargetOpcode::PSEUDO_PROBE:
       return true;
     }
   }
 
   /// Return true if this is a transient instruction that is either very likely
   /// to be eliminated during register allocation (such as copy-like
   /// instructions), or if this instruction doesn't have an execution-time cost.
   bool isTransient() const {

llvm/include/llvm/CodeGen/Passes.h

/// MachineDominanaceFrontier - This pass is a machine dominators analysis pass.
 
   /// Creates CFGuard longjmp target identification pass.
   /// \see CFGuardLongjmp.cpp
   FunctionPass *createCFGuardLongjmpPass();
 
   /// Create Hardware Loop pass. \see HardwareLoops.cpp
   FunctionPass *createHardwareLoopsPass();
 
+  /// This pass inserts pseudo probe annotation for value profiling.
+  FunctionPass *createPseudoProbeInserter();
+
   /// Create IR Type Promotion pass. \see TypePromotion.cpp
   FunctionPass *createTypePromotionPass();
 
   /// Creates MIR Debugify pass. \see MachineDebugify.cpp
   ModulePass *createDebugifyMachineModulePass();
 
   /// Creates MIR Strip Debug pass. \see MachineStripDebug.cpp
   /// If OnlyDebugified is true then it will only strip debug info if it was

llvm/include/llvm/CodeGen/SelectionDAG.h

SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
                               MachineMemOperand *MMO);
 
   /// Creates a LifetimeSDNode that starts (`IsStart==true`) or ends
   /// (`IsStart==false`) the lifetime of the portion of `FrameIndex` between
   /// offsets `Offset` and `Offset + Size`.
   SDValue getLifetimeNode(bool IsStart, const SDLoc &dl, SDValue Chain,
                           int FrameIndex, int64_t Size, int64_t Offset = -1);
 
+  /// Creates a PseudoProbeSDNode with function GUID `Guid` and
+  /// the index of the block `Index` it is probing.
+  SDValue getPseudoProbeNode(const SDLoc &dl, SDValue Chain, uint64_t Guid,
+                             uint64_t Index);
+
   /// Create a MERGE_VALUES node from the given operands.
   SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
 
   /// Loads are not normal binary operators: their result type is not
   /// determined by their operands, and they produce a value AND a token chain.
   ///
   /// This function will set the MOLoad flag on MMOFlags, but you can set it if
   /// you want.  The MOStore flag must not be set.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

public:
 
   // Methods to support isa and dyn_cast
   static bool classof(const SDNode *N) {
     return N->getOpcode() == ISD::LIFETIME_START ||
            N->getOpcode() == ISD::LIFETIME_END;
   }
 };
 
+/// This SDNode is used for PSEUDO_PROBE values, which indicate
+/// the function guid and the index of the basic block that is
+/// being probed. A pseudo probe serves as a place holder and
+/// will be removed at the end of compilation. It does not have
+/// any operand because we do not want the instruction selection
+/// to deal with any.
+class PseudoProbeSDNode : public SDNode {
+  friend class SelectionDAG;
+  uint64_t Guid;
+  uint64_t Index;
+
+  PseudoProbeSDNode(unsigned Opcode, unsigned Order, const DebugLoc &dl,
+                    SDVTList VTs, uint64_t Guid, uint64_t Index)
+      : SDNode(Opcode, Order, dl, VTs), Guid(Guid), Index(Index) {}
+
+public:
+  int64_t getGuid() const { return Guid; }
+  uint64_t getIndex() const { return Index; }
+
+  // Methods to support isa and dyn_cast
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::PSEUDO_PROBE;
+  }
+};
+
 class JumpTableSDNode : public SDNode {
   friend class SelectionDAG;
 
   int JTI;
   unsigned TargetFlags;
 
   JumpTableSDNode(int jti, EVT VT, bool isTarg, unsigned TF)
     : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable,

llvm/include/llvm/IR/BasicBlock.h

public:
   /// Returns a pointer to the first instruction in this block that is not a
   /// PHINode, a debug intrinsic, or a lifetime intrinsic.
   const Instruction* getFirstNonPHIOrDbgOrLifetime() const;
   Instruction* getFirstNonPHIOrDbgOrLifetime() {
     return const_cast<Instruction *>(
         static_cast<const BasicBlock *>(this)->getFirstNonPHIOrDbgOrLifetime());
   }
 
+  /// Returns a pointer to the first instruction in this block that is not a
+  /// PHINode, a debug intrinsic, or a pseudo probe intrinsic.
+  const Instruction *getFirstNonPHIOrDbgOrPseudoProbe() const;
+  Instruction *getFirstNonPHIOrDbgOrPseudoProbe() {
+    return const_cast<Instruction *>(static_cast<const BasicBlock *>(this)
+                                         ->getFirstNonPHIOrDbgOrPseudoProbe());
+  }
+
   /// Returns an iterator to the first instruction in this block that is
   /// suitable for inserting a non-PHI instruction.
   ///
   /// In particular, it skips all PHIs and LandingPad instructions.
   const_iterator getFirstInsertionPt() const;
   iterator getFirstInsertionPt() {
     return static_cast<const BasicBlock *>(this)
                                           ->getFirstInsertionPt().getNonConst();

llvm/include/llvm/IR/IntrinsicInst.h

public:
   }
 
   // Returns the value site index.
   ConstantInt *getIndex() const {
     return cast<ConstantInt>(const_cast<Value *>(getArgOperand(4)));
   }
 };
 
+class PseudoProbeInst : public IntrinsicInst {
+public:
+  static bool classof(const IntrinsicInst *I) {
+    return I->getIntrinsicID() == Intrinsic::pseudoprobe;
+  }
+  static bool classof(const Value *V) {
+    return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
+  }
+
+  ConstantInt *getFuncGuid() const {
+    return cast<ConstantInt>(const_cast<Value *>(getArgOperand(0)));
+  }
+
+  ConstantInt *getIndex() const {
+    return cast<ConstantInt>(const_cast<Value *>(getArgOperand(1)));
+  }
+};
 } // end namespace llvm
 
 #endif // LLVM_IR_INTRINSICINST_H

llvm/include/llvm/IR/Intrinsics.td

 def int_donothing : Intrinsic<[], [], [IntrNoMem, IntrWillReturn]>;
 
 // This instruction has no actual effect, though it is treated by the optimizer
 // has having opaque side effects. This may be inserted into loops to ensure
 // that they are not removed even if they turn out to be empty, for languages
 // which specify that infinite loops must be preserved.
 def int_sideeffect : Intrinsic<[], [], [IntrInaccessibleMemOnly, IntrWillReturn]>;
 
+// The pseudoprobe intrinsic works as a place holder to the block it probes.
+// Like the sideeffect intrinsic defined above, this intrinsic is treated by the 
+// optimizer as having opaque side effects so that it won't be get rid of or moved 
+// out of the block it probes.
+def int_pseudoprobe : Intrinsic<[], [llvm_i64_ty, llvm_i64_ty], [IntrInaccessibleMemOnly, IntrWillReturn]>;
+
 // Intrinsics to support half precision floating point format
 let IntrProperties = [IntrNoMem, IntrWillReturn] in {
 def int_convert_to_fp16   : Intrinsic<[llvm_i16_ty], [llvm_anyfloat_ty]>;
 def int_convert_from_fp16 : Intrinsic<[llvm_anyfloat_ty], [llvm_i16_ty]>;
 }
 
 // Clear cache intrinsic, default to ignore (ie. emit nothing)
 // maps to void __clear_cache() on supporting platforms

llvm/include/llvm/InitializePasses.h

 void initializePreISelIntrinsicLoweringLegacyPassPass(PassRegistry&);
 void initializePredicateInfoPrinterLegacyPassPass(PassRegistry&);
 void initializePrintFunctionPassWrapperPass(PassRegistry&);
 void initializePrintModulePassWrapperPass(PassRegistry&);
 void initializeProcessImplicitDefsPass(PassRegistry&);
 void initializeProfileSummaryInfoWrapperPassPass(PassRegistry&);
 void initializePromoteLegacyPassPass(PassRegistry&);
 void initializePruneEHPass(PassRegistry&);
+void initializePseudoProbeInserterPass(PassRegistry &);
 void initializeRABasicPass(PassRegistry&);
 void initializeRAGreedyPass(PassRegistry&);
 void initializeReachingDefAnalysisPass(PassRegistry&);
 void initializeReassociateLegacyPassPass(PassRegistry&);
 void initializeRedundantDbgInstEliminationPass(PassRegistry&);
 void initializeRegAllocFastPass(PassRegistry&);
 void initializeRegBankSelectPass(PassRegistry&);
 void initializeRegToMemPass(PassRegistry&);

llvm/include/llvm/Passes/PassBuilder.h

 class ModuleSummaryIndex;
 
 /// A struct capturing PGO tunables.
 struct PGOOptions {
   enum PGOAction { NoAction, IRInstr, IRUse, SampleUse };
   enum CSPGOAction { NoCSAction, CSIRInstr, CSIRUse };
   PGOOptions(std::string ProfileFile = "", std::string CSProfileGenFile = "",
              std::string ProfileRemappingFile = "", PGOAction Action = NoAction,
-             CSPGOAction CSAction = NoCSAction, bool SamplePGOSupport = false)
+             CSPGOAction CSAction = NoCSAction,
+             bool DebugInfoForProfiling = false,
+             bool PseudoProbeForProfiling = false)
       : ProfileFile(ProfileFile), CSProfileGenFile(CSProfileGenFile),
         ProfileRemappingFile(ProfileRemappingFile), Action(Action),
-        CSAction(CSAction),
-        SamplePGOSupport(SamplePGOSupport || Action == SampleUse) {
+        CSAction(CSAction), DebugInfoForProfiling(DebugInfoForProfiling ||
+                                                  (Action == SampleUse &&
+                                                   !PseudoProbeForProfiling)),
+        PseudoProbeForProfiling(PseudoProbeForProfiling) {
     // Note, we do allow ProfileFile.empty() for Action=IRUse LTO can
     // callback with IRUse action without ProfileFile.
 
     // If there is a CSAction, PGOAction cannot be IRInstr or SampleUse.
     assert(this->CSAction == NoCSAction ||
            (this->Action != IRInstr && this->Action != SampleUse));
 
     // For CSIRInstr, CSProfileGenFile also needs to be nonempty.
     assert(this->CSAction != CSIRInstr || !this->CSProfileGenFile.empty());
 
     // If CSAction is CSIRUse, PGOAction needs to be IRUse as they share
     // a profile.
     assert(this->CSAction != CSIRUse || this->Action == IRUse);
 
-    // If neither Action nor CSAction, SamplePGOSupport needs to be true.
+    // If neither Action nor CSAction, DebugInfoForProfiling or
+    // PseudoProbeForProfiling needs to be true.
     assert(this->Action != NoAction || this->CSAction != NoCSAction ||
-           this->SamplePGOSupport);
+           this->DebugInfoForProfiling || this->PseudoProbeForProfiling);
+
+    // Pseudo probe instrumentation should only work with autoFDO or no FDO.
+    assert(!this->PseudoProbeForProfiling || this->Action == NoAction ||
+           this->Action == SampleUse);
   }
   std::string ProfileFile;
   std::string CSProfileGenFile;
   std::string ProfileRemappingFile;
   PGOAction Action;
   CSPGOAction CSAction;
-  bool SamplePGOSupport;
+  bool DebugInfoForProfiling;
+  bool PseudoProbeForProfiling;
 };
 
 /// Tunable parameters for passes in the default pipelines.
 class PipelineTuningOptions {
 public:
   /// Constructor sets pipeline tuning defaults based on cl::opts. Each option
   /// can be set in the PassBuilder when using a LLVM as a library.
   PipelineTuningOptions();

llvm/include/llvm/Support/TargetOpcodes.def

 /// which immediately follow a BUNDLE instruction which are marked with
 /// 'InsideBundle' flag are inside the bundle.
 HANDLE_TARGET_OPCODE(BUNDLE)
 
 /// Lifetime markers.
 HANDLE_TARGET_OPCODE(LIFETIME_START)
 HANDLE_TARGET_OPCODE(LIFETIME_END)
 
+/// Pseudo probe
+HANDLE_TARGET_OPCODE(PSEUDO_PROBE)
+
 /// A Stackmap instruction captures the location of live variables at its
 /// position in the instruction stream. It is followed by a shadow of bytes
 /// that must lie within the function and not contain another stackmap.
 HANDLE_TARGET_OPCODE(STACKMAP)
 
 /// FEntry all - This is a marker instruction which gets translated into a raw fentry call.
 HANDLE_TARGET_OPCODE(FENTRY_CALL)
 

llvm/include/llvm/Target/Target.td

def LIFETIME_START : StandardPseudoInstruction {
   let hasSideEffects = 0;
 }
 def LIFETIME_END : StandardPseudoInstruction {
   let OutOperandList = (outs);
   let InOperandList = (ins i32imm:$id);
   let AsmString = "LIFETIME_END";
   let hasSideEffects = 0;
 }
+def PSEUDO_PROBE : StandardPseudoInstruction {
+  let OutOperandList = (outs);
+  let InOperandList = (ins i64imm:$guid, i64imm:$index, i64imm:$type);
+  let AsmString = "PSEUDO_PROBE";
+  let hasSideEffects = 1;
+}
+
 def STACKMAP : StandardPseudoInstruction {
   let OutOperandList = (outs);
   let InOperandList = (ins i64imm:$id, i32imm:$nbytes, variable_ops);
   let hasSideEffects = 1;
   let isCall = 1;
   let mayLoad = 1;
   let usesCustomInserter = 1;
 }

llvm/include/llvm/Transforms/IPO/SampleProfileProbe.h

+//===- Transforms/IPO/SampleProfileProbe.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
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// This file provides the interface for the pseudo probe implementation for
+/// AutoFDO.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBER_H
+#define LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBER_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Target/TargetMachine.h"
+#include <unordered_map>
+
+namespace llvm {
+
+class Module;
+
+using BlockIdMap = std::unordered_map<BasicBlock *, uint32_t>;
+
+enum class PseudoProbeReservedId { Invalid = 0, Last = Invalid };
+
+enum class PseudoProbeType { Block = 0 };
+
+/// Sample profile pseudo prober.
+///
+/// Insert pseudo probes for block sampling and value sampling.
+class SampleProfileProber {
+public:
+  // Give an empty module id when the prober is not used for instrumentation.
+  SampleProfileProber(Function &F);
+  void instrumentOneFunc(Function &F, TargetMachine *TM);
+
+private:
+  Function *getFunction() const { return F; }
+  uint32_t getBlockId(const BasicBlock *BB) const;
+  void computeProbeIdForBlocks();
+
+  Function *F;
+
+  /// Map basic blocks to the their pseudo probe ids.
+  BlockIdMap BlockProbeIds;
+
+  /// The ID of the last probe, Can be used to number a new probe.
+  uint32_t LastProbeId;
+};
+
+class SampleProfileProbePass : public PassInfoMixin<SampleProfileProbePass> {
+  TargetMachine *TM;
+
+public:
+  SampleProfileProbePass(TargetMachine *TM) : TM(TM) {}
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+};
+
+} // end namespace llvm
+#endif // LLVM_TRANSFORMS_IPO_SAMPLEPROFILEPROBER_H

llvm/lib/Analysis/AliasSetTracker.cpp

if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
     // These intrinsics will show up as affecting memory, but they are just
     // markers.
     switch (II->getIntrinsicID()) {
     default:
       break;
       // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
     case Intrinsic::assume:
     case Intrinsic::sideeffect:
+    case Intrinsic::pseudoprobe:
       return;
     }
   }
   if (!Inst->mayReadOrWriteMemory())
     return; // doesn't alias anything
 
   if (AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
     AS->addUnknownInst(Inst, AA);

llvm/lib/Analysis/ValueTracking.cpp

 bool llvm::isAssumeLikeIntrinsic(const Instruction *I) {
   if (const CallInst *CI = dyn_cast<CallInst>(I))
     if (Function *F = CI->getCalledFunction())
       switch (F->getIntrinsicID()) {
       default: break;
       // FIXME: This list is repeated from NoTTI::getIntrinsicCost.
       case Intrinsic::assume:
       case Intrinsic::sideeffect:
+      case Intrinsic::pseudoprobe:
       case Intrinsic::dbg_declare:
       case Intrinsic::dbg_value:
       case Intrinsic::dbg_label:
       case Intrinsic::invariant_start:
       case Intrinsic::invariant_end:
       case Intrinsic::lifetime_start:
       case Intrinsic::lifetime_end:
       case Intrinsic::objectsize:

llvm/lib/Analysis/VectorUtils.cpp

 Intrinsic::ID llvm::getVectorIntrinsicIDForCall(const CallInst *CI,
                                                 const TargetLibraryInfo *TLI) {
   Intrinsic::ID ID = getIntrinsicForCallSite(*CI, TLI);
   if (ID == Intrinsic::not_intrinsic)
     return Intrinsic::not_intrinsic;
 
   if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start ||
       ID == Intrinsic::lifetime_end || ID == Intrinsic::assume ||
-      ID == Intrinsic::sideeffect)
+      ID == Intrinsic::sideeffect || ID == Intrinsic::pseudoprobe)
     return ID;
   return Intrinsic::not_intrinsic;
 }
 
 /// Find the operand of the GEP that should be checked for consecutive
 /// stores. This ignores trailing indices that have no effect on the final
 /// pointer.
 unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) {

llvm/lib/CodeGen/Analysis.cpp

bool llvm::isInTailCallPosition(const CallBase &Call, const TargetMachine &TM) {
   // chain interposes between I and the return.
   // Check for all calls including speculatable functions.
   for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {
     if (&*BBI == &Call)
       break;
     // Debug info intrinsics do not get in the way of tail call optimization.
     if (isa<DbgInfoIntrinsic>(BBI))
       continue;
+    // Pseudo probe intrinsics do not block tail call optimization either.
+    if (isa<PseudoProbeInst>(BBI))
+      continue;
     // A lifetime end or assume intrinsic should not stop tail call
     // optimization.
     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
       if (II->getIntrinsicID() == Intrinsic::lifetime_end ||
           II->getIntrinsicID() == Intrinsic::assume)
         continue;
     if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
         !isSafeToSpeculativelyExecute(&*BBI))

llvm/lib/CodeGen/CodeGenPrepare.cpp

bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB, bool &ModifiedDT) {
 
   // Make sure there are no instructions between the PHI and return, or that the
   // return is the first instruction in the block.
   if (PN) {
     BasicBlock::iterator BI = BB->begin();
     // Skip over debug and the bitcast.
     do {
       ++BI;
-    } while (isa<DbgInfoIntrinsic>(BI) || &*BI == BCI || &*BI == EVI);
+    } while (isa<DbgInfoIntrinsic>(BI) || &*BI == BCI || &*BI == EVI ||
+             isa<PseudoProbeInst>(BI));
     if (&*BI != RetI)
       return false;
   } else {
     BasicBlock::iterator BI = BB->begin();
-    while (isa<DbgInfoIntrinsic>(BI)) ++BI;
+    while (isa<DbgInfoIntrinsic>(BI) || isa<PseudoProbeInst>(BI))
+      ++BI;
     if (&*BI != RetI)
       return false;
   }
 
   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
   /// call.
   const Function *F = BB->getParent();
   SmallVector<BasicBlock*, 4> TailCallBBs;
if (PN) {
     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
       if (!VisitedBBs.insert(*PI).second)
         continue;
 
       BasicBlock::InstListType &InstList = (*PI)->getInstList();
       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
-      do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
+      do {
+        ++RI;
+      } while (RI != RE &&
+               (isa<DbgInfoIntrinsic>(&*RI) || isa<PseudoProbeInst>(&*RI)));
       if (RI == RE)
         continue;
 
       CallInst *CI = dyn_cast<CallInst>(&*RI);
       if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI) &&
           attributesPermitTailCall(F, CI, RetI, *TLI))
         TailCallBBs.push_back(*PI);
     }

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue visitBR_CC(SDNode *N);
     SDValue visitLOAD(SDNode *N);
 
     SDValue replaceStoreChain(StoreSDNode *ST, SDValue BetterChain);
     SDValue replaceStoreOfFPConstant(StoreSDNode *ST);
 
     SDValue visitSTORE(SDNode *N);
     SDValue visitLIFETIME_END(SDNode *N);
+    SDValue visitPSEUDO_PROBE(SDNode *N);
     SDValue visitINSERT_VECTOR_ELT(SDNode *N);
     SDValue visitEXTRACT_VECTOR_ELT(SDNode *N);
     SDValue visitBUILD_VECTOR(SDNode *N);
     SDValue visitCONCAT_VECTORS(SDNode *N);
     SDValue visitEXTRACT_SUBVECTOR(SDNode *N);
     SDValue visitVECTOR_SHUFFLE(SDNode *N);
     SDValue visitSCALAR_TO_VECTOR(SDNode *N);
     SDValue visitINSERT_SUBVECTOR(SDNode *N);

llvm/lib/CodeGen/SelectionDAG/InstrEmitter.cpp

case ISD::LIFETIME_END: {
     TargetOpcode::LIFETIME_START : TargetOpcode::LIFETIME_END;
 
     FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Node->getOperand(1));
     BuildMI(*MBB, InsertPos, Node->getDebugLoc(), TII->get(TarOp))
     .addFrameIndex(FI->getIndex());
     break;
   }
 
+  case ISD::PSEUDO_PROBE: {
+    unsigned TarOp = TargetOpcode::PSEUDO_PROBE;
+    auto Guid = cast<PseudoProbeSDNode>(Node)->getGuid();
+    auto Index = cast<PseudoProbeSDNode>(Node)->getIndex();
+
+    BuildMI(*MBB, InsertPos, Node->getDebugLoc(), TII->get(TarOp))
+        .addImm(Guid)
+        .addImm(Index)
+        .addImm(0); // 0 for block probes
+    break;
+  }
+
   case ISD::INLINEASM:
   case ISD::INLINEASM_BR: {
     unsigned NumOps = Node->getNumOperands();
     if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
       --NumOps;  // Ignore the glue operand.
 
     // Create the inline asm machine instruction.
     unsigned TgtOpc = Node->getOpcode() == ISD::INLINEASM_BR

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

case ISD::TargetFrameIndex:
     break;
   case ISD::LIFETIME_START:
   case ISD::LIFETIME_END:
     if (cast<LifetimeSDNode>(N)->hasOffset()) {
       ID.AddInteger(cast<LifetimeSDNode>(N)->getSize());
       ID.AddInteger(cast<LifetimeSDNode>(N)->getOffset());
     }
     break;
+  case ISD::PSEUDO_PROBE:
+    ID.AddInteger(cast<PseudoProbeSDNode>(N)->getGuid());
+    ID.AddInteger(cast<PseudoProbeSDNode>(N)->getIndex());
+    break;
   case ISD::JumpTable:
   case ISD::TargetJumpTable:
     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
     ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
     break;
   case ISD::ConstantPool:
   case ISD::TargetConstantPool: {
     const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
SDValue SelectionDAG::getLifetimeNode(bool IsStart, const SDLoc &dl,
   createOperands(N, Ops);
   CSEMap.InsertNode(N, IP);
   InsertNode(N);
   SDValue V(N, 0);
   NewSDValueDbgMsg(V, "Creating new node: ", this);
   return V;
 }
 
+SDValue SelectionDAG::getPseudoProbeNode(const SDLoc &dl, SDValue Chain,
+                                         uint64_t Guid, uint64_t Index) {
+
+  const unsigned Opcode = ISD::PSEUDO_PROBE;
+  const auto VTs = getVTList(MVT::Other);
+  SDValue Ops[] = {Chain};
+  FoldingSetNodeID ID;
+  AddNodeIDNode(ID, Opcode, VTs, Ops);
+  ID.AddInteger(Guid);
+  ID.AddInteger(Index);
+  void *IP = nullptr;
+  if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP))
+    return SDValue(E, 0);
+
+  auto *N = newSDNode<PseudoProbeSDNode>(Opcode, dl.getIROrder(),
+                                         dl.getDebugLoc(), VTs, Guid, Index);
+  createOperands(N, Ops);
+  CSEMap.InsertNode(N, IP);
+  InsertNode(N);
+  SDValue V(N, 0);
+  NewSDValueDbgMsg(V, "Creating new node: ", this);
+  return V;
+}
+
 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
 /// MachinePointerInfo record from it.  This is particularly useful because the
 /// code generator has many cases where it doesn't bother passing in a
 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
 static MachinePointerInfo InferPointerInfo(const MachinePointerInfo &Info,
                                            SelectionDAG &DAG, SDValue Ptr,
                                            int64_t Offset = 0) {
   // If this is FI+Offset, we can model it.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

for (SmallVectorImpl<const Value*>::iterator Object = Allocas.begin(),
               ObjectPtr, Offset, DAG.getDataLayout()) != LifetimeObject)
         Offset = -1; // Cannot determine offset from alloca to lifetime object.
       Res = DAG.getLifetimeNode(IsStart, sdl, getRoot(), FrameIndex, ObjectSize,
                                 Offset);
       DAG.setRoot(Res);
     }
     return;
   }
+  case Intrinsic::pseudoprobe: {
+    auto Guid = cast<ConstantInt>(I.getArgOperand(0))->getZExtValue();
+    auto Index = cast<ConstantInt>(I.getArgOperand(1))->getZExtValue();
+    Res = DAG.getPseudoProbeNode(sdl, getRoot(), Guid, Index);
+    DAG.setRoot(Res);
+    return;
+  }
   case Intrinsic::invariant_start:
     // Discard region information.
     setValue(&I, DAG.getUNDEF(TLI.getPointerTy(DAG.getDataLayout())));
     return;
   case Intrinsic::invariant_end:
     // Discard region information.
     return;
   case Intrinsic::clear_cache:

llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

#endif
   case ISD::EXTRACT_ELEMENT:            return "extract_element";
   case ISD::BUILD_PAIR:                 return "build_pair";
   case ISD::STACKSAVE:                  return "stacksave";
   case ISD::STACKRESTORE:               return "stackrestore";
   case ISD::TRAP:                       return "trap";
   case ISD::DEBUGTRAP:                  return "debugtrap";
   case ISD::LIFETIME_START:             return "lifetime.start";
   case ISD::LIFETIME_END:               return "lifetime.end";
+  case ISD::PSEUDO_PROBE:
+    return "pseudoprobe";
   case ISD::GC_TRANSITION_START:        return "gc_transition.start";
   case ISD::GC_TRANSITION_END:          return "gc_transition.end";
   case ISD::GET_DYNAMIC_AREA_OFFSET:    return "get.dynamic.area.offset";
   case ISD::FREEZE:                     return "freeze";
   case ISD::PREALLOCATED_SETUP:
     return "call_setup";
   case ISD::PREALLOCATED_ARG:
     return "call_alloc";

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
   case ISD::TargetGlobalAddress:
   case ISD::TokenFactor:
   case ISD::CopyFromReg:
   case ISD::CopyToReg:
   case ISD::EH_LABEL:
   case ISD::ANNOTATION_LABEL:
   case ISD::LIFETIME_START:
   case ISD::LIFETIME_END:
+  case ISD::PSEUDO_PROBE:
     NodeToMatch->setNodeId(-1); // Mark selected.
     return;
   case ISD::AssertSext:
   case ISD::AssertZext:
   case ISD::AssertAlign:
     ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
     CurDAG->RemoveDeadNode(NodeToMatch);
     return;

llvm/lib/IR/BasicBlock.cpp

for (const Instruction &I : *this) {
     if (I.isLifetimeStartOrEnd())
       continue;
 
     return &I;
   }
   return nullptr;
 }
 
+const Instruction *BasicBlock::getFirstNonPHIOrDbgOrPseudoProbe() const {
+  for (const Instruction &I : *this) {
+    if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I) || isa<PseudoProbeInst>(I))
+      continue;
+    return &I;
+  }
+  return nullptr;
+}
+
 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
   const Instruction *FirstNonPHI = getFirstNonPHI();
   if (!FirstNonPHI)
     return end();
 
   const_iterator InsertPt = FirstNonPHI->getIterator();
   if (InsertPt->isEHPad()) ++InsertPt;
   return InsertPt;

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/Transforms/IPO/MergeFunctions.h"
 #include "llvm/Transforms/IPO/OpenMPOpt.h"
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/SampleProfile.h"
+#include "llvm/Transforms/IPO/SampleProfileProbe.h"
 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
 #include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Instrumentation/AddressSanitizer.h"
 #include "llvm/Transforms/Instrumentation/BoundsChecking.h"
 #include "llvm/Transforms/Instrumentation/CGProfile.h"
PassBuilder::buildInlinerPipeline(OptimizationLevel Level, ThinLTOPhase Phase,
 
   return MIWP;
 }
 
 ModulePassManager PassBuilder::buildModuleSimplificationPipeline(
     OptimizationLevel Level, ThinLTOPhase Phase, bool DebugLogging) {
   ModulePassManager MPM(DebugLogging);
 
+  // Place pseudo probe instrumentation as the first pass of the pipeline to
+  // minimize the impact of optimization changes.
+  if (PGOOpt && PGOOpt->PseudoProbeForProfiling &&
+      Phase != ThinLTOPhase::PostLink)
+    MPM.addPass(SampleProfileProbePass(TM));
+
   bool HasSampleProfile = PGOOpt && (PGOOpt->Action == PGOOptions::SampleUse);
 
   // In ThinLTO mode, when flattened profile is used, all the available
   // profile information will be annotated in PreLink phase so there is
   // no need to load the profile again in PostLink.
   bool LoadSampleProfile =
       HasSampleProfile &&
       !(FlattenedProfileUsed && Phase == ThinLTOPhase::PostLink);
PassBuilder::buildPerModuleDefaultPipeline(OptimizationLevel Level,
 
   // Force any function attributes we want the rest of the pipeline to observe.
   MPM.addPass(ForceFunctionAttrsPass());
 
   // Apply module pipeline start EP callback.
   for (auto &C : PipelineStartEPCallbacks)
     C(MPM);
 
-  if (PGOOpt && PGOOpt->SamplePGOSupport)
+  if (PGOOpt && PGOOpt->DebugInfoForProfiling)
     MPM.addPass(createModuleToFunctionPassAdaptor(AddDiscriminatorsPass()));
 
   // Add the core simplification pipeline.
   MPM.addPass(buildModuleSimplificationPipeline(Level, ThinLTOPhase::None,
                                                 DebugLogging));
 
   // Now add the optimization pipeline.
   MPM.addPass(buildModuleOptimizationPipeline(Level, DebugLogging, LTOPreLink));
 
   return MPM;
 }
 
 ModulePassManager
 PassBuilder::buildThinLTOPreLinkDefaultPipeline(OptimizationLevel Level,
                                                 bool DebugLogging) {
   assert(Level != OptimizationLevel::O0 &&
          "Must request optimizations for the default pipeline!");
 
   ModulePassManager MPM(DebugLogging);
 
   // Force any function attributes we want the rest of the pipeline to observe.
   MPM.addPass(ForceFunctionAttrsPass());
 
-  if (PGOOpt && PGOOpt->SamplePGOSupport)
+  if (PGOOpt && PGOOpt->DebugInfoForProfiling)
     MPM.addPass(createModuleToFunctionPassAdaptor(AddDiscriminatorsPass()));
 
   // Apply module pipeline start EP callback.
   for (auto &C : PipelineStartEPCallbacks)
     C(MPM);
 
   // If we are planning to perform ThinLTO later, we don't bloat the code with
   // unrolling/vectorization/... now. Just simplify the module as much as we

llvm/lib/Passes/PassRegistry.def

 MODULE_PASS("print-lcg-dot", LazyCallGraphDOTPrinterPass(dbgs()))
 MODULE_PASS("print-stack-safety", StackSafetyGlobalPrinterPass(dbgs()))
 MODULE_PASS("rewrite-statepoints-for-gc", RewriteStatepointsForGC())
 MODULE_PASS("rewrite-symbols", RewriteSymbolPass())
 MODULE_PASS("rpo-function-attrs", ReversePostOrderFunctionAttrsPass())
 MODULE_PASS("sample-profile", SampleProfileLoaderPass())
 MODULE_PASS("scc-oz-module-inliner",
   buildInlinerPipeline(OptimizationLevel::Oz, ThinLTOPhase::None, DebugLogging))
+MODULE_PASS("pseudo-probe", SampleProfileProbePass(TM))
 MODULE_PASS("strip-dead-prototypes", StripDeadPrototypesPass())
 MODULE_PASS("synthetic-counts-propagation", SyntheticCountsPropagation())
 MODULE_PASS("wholeprogramdevirt", WholeProgramDevirtPass(nullptr, nullptr))
 MODULE_PASS("verify", VerifierPass())
 MODULE_PASS("dfsan", DataFlowSanitizerPass())
 MODULE_PASS("asan-module", ModuleAddressSanitizerPass(/*CompileKernel=*/false, false, true, false))
 MODULE_PASS("msan-module", MemorySanitizerPass({}))
 MODULE_PASS("tsan-module", ThreadSanitizerPass())

llvm/lib/Transforms/IPO/CMakeLists.txt

add_llvm_component_library(LLVMipo
   LoopExtractor.cpp
   LowerTypeTests.cpp
   MergeFunctions.cpp
   OpenMPOpt.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleProfile.cpp
+  SampleProfileProbe.cpp
   SCCP.cpp
   StripDeadPrototypes.cpp
   StripSymbols.cpp
   SyntheticCountsPropagation.cpp
   ThinLTOBitcodeWriter.cpp
   WholeProgramDevirt.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/IPO
 
   DEPENDS
   intrinsics_gen
   omp_gen
   )

llvm/lib/Transforms/IPO/SampleProfileProbe.cpp

+//===- SampleProfileProbe.cpp - Pseudo probe Instrumentation -------------===//
+//
+// 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 implements the SampleProfileProber transformation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/SampleProfileProbe.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/GlobalValue.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/ProfileData/SampleProf.h"
+#include "llvm/Support/CRC.h"
+#include "llvm/Transforms/Instrumentation.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
+#include <vector>
+
+using namespace llvm;
+#define DEBUG_TYPE "sample-profile-probe"
+
+SampleProfileProber::SampleProfileProber(Function &Func) : F(&Func) {
+  BlockProbeIds.clear();
+  LastProbeId = (uint32_t)PseudoProbeReservedId::Last;
+  computeProbeIdForBlocks();
+}
+
+void SampleProfileProber::computeProbeIdForBlocks() {
+  for (auto &BB : *F) {
+    BlockProbeIds[&BB] = ++LastProbeId;
+  }
+}
+
+uint32_t SampleProfileProber::getBlockId(const BasicBlock *BB) const {
+  auto iter = BlockProbeIds.find(const_cast<BasicBlock *>(BB));
+  return iter == BlockProbeIds.end() ? 0 : iter->second;
+}
+
+void SampleProfileProber::instrumentOneFunc(Function &F, TargetMachine *TM) {
+  Module *M = F.getParent();
+  MDBuilder MDB(F.getContext());
+  // Compute a GUID without considering the function's linkage type. This is
+  // fine for now since function name is the only key in the profile database.
+  // Same-named global function and static functions will have their profiles
+  // merged into a single one eventually anyway. This is also a workaround for
+  // GUID computation of callsite probes in LTO mode (see
+  // PseudoProbeInserter.cpp), where module name is not available and
+  // considering linkage type will result in an invalid GUID.
+  uint64_t Guid = Function::getGUID(F.getName());
+
+  // Probe basic blocks.
+  for (auto &I : BlockProbeIds) {
+    auto BB = I.first;
+    auto Index = I.second;
+    // Insert a probe before an instruction with a valid debug line number which
+    // will be assigned to the probe. The line number will be used later to
+    // model the inline context when the probe is inlined into other functions.
+    // Debug instructions, phi nodes and lifetime markers do not have an valid
+    // line number. Real instructions generated by optimizations may not come
+    // with a line number either.
+    auto HasValidDbgLine = [](Instruction *J) {
+      return !isa<PHINode>(J) && !isa<DbgInfoIntrinsic>(J) &&
+             !J->isLifetimeStartOrEnd() && J->getDebugLoc();
+    };
+
+    auto J = &*BB->getFirstInsertionPt();
+    while (J != BB->getTerminator() && !HasValidDbgLine(J)) {
+      J = J->getNextNode();
+    }
+
+    IRBuilder<> Builder(J);
+    assert(Builder.GetInsertPoint() != BB->end() &&
+           "Cannot get the probing point");
+    Function *ProbeFn =
+        llvm::Intrinsic::getDeclaration(M, Intrinsic::pseudoprobe);
+    Value *args[] = {Builder.getInt64(Guid), Builder.getInt64(Index)};
+    Builder.CreateCall(ProbeFn, args);
+  }
+}
+
+PreservedAnalyses SampleProfileProbePass::run(Module &M,
+                                              ModuleAnalysisManager &AM) {
+  for (auto &F : M) {
+    if (F.isDeclaration())
+      continue;
+    SampleProfileProber ProbeManager(F);
+    ProbeManager.instrumentOneFunc(F, TM);
+  }
+
+  return PreservedAnalyses::none();
+}

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

static bool markTails(Function &F, bool &AllCallsAreTailCalls,
   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))
+      // A PseudoProbeInst does access 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;
 
       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

 
 bool TailRecursionEliminator::foldReturnAndProcessPred(
     ReturnInst *Ret, bool CannotTailCallElimCallsMarkedTail) {
   BasicBlock *BB = Ret->getParent();
 
   bool Change = false;
 
   // Make sure this block is a trivial return block.
-  assert(BB->getFirstNonPHIOrDbg() == Ret &&
+  assert(BB->getFirstNonPHIOrDbgOrPseudoProbe() == Ret &&
          "Trying to fold non-trivial return block");
 
   // If the return block contains nothing but the return and PHI's,
   // there might be an opportunity to duplicate the return in its
   // predecessors and perform TRE there. Look for predecessors that end
   // in unconditional branch and recursive call(s).
   SmallVector<BranchInst*, 8> UncondBranchPreds;
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
bool TailRecursionEliminator::eliminate(Function &F,
   // FIXME: The code generator produces really bad code when an 'escaping
   // alloca' is changed from being a static alloca to being a dynamic alloca.
   // Until this is resolved, disable this transformation if that would ever
   // happen.  This bug is PR962.
   for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; /*in loop*/) {
     BasicBlock *BB = &*BBI++; // foldReturnAndProcessPred may delete BB.
     if (ReturnInst *Ret = dyn_cast<ReturnInst>(BB->getTerminator())) {
       bool Change = TRE.processReturningBlock(Ret, !CanTRETailMarkedCall);
-      if (!Change && BB->getFirstNonPHIOrDbg() == Ret)
+      if (!Change && BB->getFirstNonPHIOrDbgOrPseudoProbe() == Ret)
         Change = TRE.foldReturnAndProcessPred(Ret, !CanTRETailMarkedCall);
       MadeChange |= Change;
     }
   }
 
   TRE.cleanupAndFinalize();
 
   return MadeChange;

llvm/lib/Transforms/Utils/Evaluator.cpp

if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
         } else if (II->getIntrinsicID() == Intrinsic::assume) {
           LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
           ++CurInst;
           continue;
         } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
           LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
           ++CurInst;
           continue;
+        } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
+          LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
+          ++CurInst;
+          continue;
         }
 
         LLVM_DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
         return false;
       }
 
       // Resolve function pointers.
       SmallVector<Constant *, 8> Formals;

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB,
   // Look for a store to the same pointer in BrBB.
   unsigned MaxNumInstToLookAt = 9;
   for (Instruction &CurI : reverse(BrBB->instructionsWithoutDebug())) {
     if (!MaxNumInstToLookAt)
       break;
     --MaxNumInstToLookAt;
 
     // Could be calling an instruction that affects memory like free().
-    if (CurI.mayHaveSideEffects() && !isa<StoreInst>(CurI))
+    // Skip pseudo probe intrinsic calls which are not really killing any memory
+    // accesses.
+    if (CurI.mayHaveSideEffects() && !isa<StoreInst>(CurI) &&
+        !isa<PseudoProbeInst>(CurI))
       return nullptr;
 
     if (auto *SI = dyn_cast<StoreInst>(&CurI)) {
       // Found the previous store make sure it stores to the same location.
       if (SI->getPointerOperand() == StorePtr)
         // Found the previous store, return its value operand.
         return SI->getValueOperand();
       return nullptr; // Unknown store.
for (BasicBlock::iterator BBI = ThenBB->begin(),
        BBI != BBE; ++BBI) {
     Instruction *I = &*BBI;
     // Skip debug info.
     if (isa<DbgInfoIntrinsic>(I)) {
       SpeculatedDbgIntrinsics.push_back(I);
       continue;
     }
 
+    // Skip pseudo probes. The consequence is we lose track of the branch
+    // probability for ThenBB, which is fine since the optimization here takes
+    // place regardless of the branch probability.
+    if (isa<PseudoProbeInst>(I)) {
+      SpeculatedDbgIntrinsics.push_back(I);
+      continue;
+    }
+
     // Only speculatively execute a single instruction (not counting the
     // terminator) for now.
     ++SpeculatedInstructions;
     if (SpeculatedInstructions > 1)
       return false;
 
     // Don't hoist the instruction if it's unsafe or expensive.
     if (!isSafeToSpeculativelyExecute(I) &&
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
   BasicBlock *DomBlock = nullptr;
   BasicBlock *IfBlock1 = PN->getIncomingBlock(0);
   BasicBlock *IfBlock2 = PN->getIncomingBlock(1);
   if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) {
     IfBlock1 = nullptr;
   } else {
     DomBlock = *pred_begin(IfBlock1);
     for (BasicBlock::iterator I = IfBlock1->begin(); !I->isTerminator(); ++I)
-      if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) {
+      if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I) &&
+          !isa<PseudoProbeInst>(I)) {
         // This is not an aggressive instruction that we can promote.
         // Because of this, we won't be able to get rid of the control flow, so
         // the xform is not worth it.
         return Changed;
       }
   }
 
   if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) {
     IfBlock2 = nullptr;
   } else {
     DomBlock = *pred_begin(IfBlock2);
     for (BasicBlock::iterator I = IfBlock2->begin(); !I->isTerminator(); ++I)
-      if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I)) {
+      if (!AggressiveInsts.count(&*I) && !isa<DbgInfoIntrinsic>(I) &&
+          !isa<PseudoProbeInst>(I)) {
         // This is not an aggressive instruction that we can promote.
         // Because of this, we won't be able to get rid of the control flow, so
         // the xform is not worth it.
         return Changed;
       }
   }
   assert(DomBlock && "Failed to find root DomBlock");
 

llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
       if (!is_contained(Chain, &I))
         MemoryInstrs.push_back(&I);
       else
         ChainInstrs.push_back(&I);
     } else if (isa<IntrinsicInst>(&I) &&
                cast<IntrinsicInst>(&I)->getIntrinsicID() ==
                    Intrinsic::sideeffect) {
       // Ignore llvm.sideeffect calls.
+    } else if (isa<IntrinsicInst>(&I) &&
+               cast<IntrinsicInst>(&I)->getIntrinsicID() ==
+                   Intrinsic::pseudoprobe) {
+      // Ignore llvm.pseudoprobe calls.
     } else if (IsLoadChain && (I.mayWriteToMemory() || I.mayThrow())) {
       LLVM_DEBUG(dbgs() << "LSV: Found may-write/throw operation: " << I
                         << '\n');
       break;
     } else if (!IsLoadChain && (I.mayReadOrWriteMemory() || I.mayThrow())) {
       LLVM_DEBUG(dbgs() << "LSV: Found may-read/write/throw operation: " << I
                         << '\n');
       break;

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
       [this, CI](unsigned VF) { return CM.isScalarWithPredication(CI, VF); },
       Range);
 
   if (IsPredicated)
     return nullptr;
 
   Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
   if (ID && (ID == Intrinsic::assume || ID == Intrinsic::lifetime_end ||
-             ID == Intrinsic::lifetime_start || ID == Intrinsic::sideeffect))
+             ID == Intrinsic::lifetime_start || ID == Intrinsic::sideeffect ||
+             ID == Intrinsic::pseudoprobe))
     return nullptr;
 
   auto willWiden = [&](unsigned VF) -> bool {
     Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
     // The following case may be scalarized depending on the VF.
     // The flag shows whether we use Intrinsic or a usual Call for vectorized
     // version of the instruction.
     // Is it beneficial to perform intrinsic call compared to lib call?

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

if (!SD) {
       SD->Inst = I;
     }
     assert(!isInSchedulingRegion(SD) &&
            "new ScheduleData already in scheduling region");
     SD->init(SchedulingRegionID, I);
 
     if (I->mayReadOrWriteMemory() &&
         (!isa<IntrinsicInst>(I) ||
-         cast<IntrinsicInst>(I)->getIntrinsicID() != Intrinsic::sideeffect)) {
+         (cast<IntrinsicInst>(I)->getIntrinsicID() != Intrinsic::sideeffect &&
+          cast<IntrinsicInst>(I)->getIntrinsicID() !=
+              Intrinsic::pseudoprobe))) {
       // Update the linked list of memory accessing instructions.
       if (CurrentLoadStore) {
         CurrentLoadStore->NextLoadStore = SD;
       } else {
         FirstLoadStoreInRegion = SD;
       }
       CurrentLoadStore = SD;
     }

llvm/test/Transforms/SampleProfile/emit-pseudo-probe.ll

+; RUN: opt < %s -passes=pseudo-probe -function-sections -S -o %t
+; RUN: FileCheck %s < %t --check-prefix=CHECK-IL
+; RUN: llc %t -stop-after=instruction-select -o - | FileCheck %s --check-prefix=CHECK-MIR
+;
+;; Check the generation of pseudoprobe intrinsic call.
+
+define void @foo(i32 %x) {
+bb0:
+  %cmp = icmp eq i32 %x, 0
+; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID:]], i64 1)
+; CHECK-MIR: PSEUDO_PROBE [[#GUID:]], 1, 0
+  br i1 %cmp, label %bb1, label %bb2
+
+bb1:
+; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID]], i64 2)
+; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 3, 0
+; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 4, 0
+  br label %bb3
+
+bb2:
+; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID]], i64 3)
+; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 2, 0
+; CHECK-MIR: PSEUDO_PROBE [[#GUID]], 4, 0
+  br label %bb3
+
+bb3:
+; CHECK-IL: call void @llvm.pseudoprobe(i64 [[#GUID]], i64 4)
+  ret void
+}