[InstrProf] Temporal Profiling

[ellis]

Summary

As described in [0], this extends IRPGO to support Temporal Profiling.

When -pgo-temporal-instrumentation is used we add the llvm.instrprof.timestamp() intrinsic to the entry of functions which in turn gets lowered to a call to the compiler-rt function INSTR_PROF_PROFILE_SET_TIMESTAMP(). A new field in the llvm_prf_cnts section stores each function's timestamp. Then in llvm-profdata merge we convert these function timestamps into a trace and add it to the indexed profile.

Since these traces could significantly increase the profile size, we've added -max-temporal-profile-trace-length and -temporal-profile-trace-reservoir-size to limit the length of a trace and the number of traces in a profile, respectively.

In a future diff we plan to use these traces to construct an optimized function order to reduce the number of page faults during startup.

Special thanks to Julian Mestre for helping with reservoir sampling.

[0] https://discourse.llvm.org/t/rfc-temporal-profiling-extension-for-irpgo/68068

[davidxl]

compiler-rt/include/profile/InstrProfData.inc

657

8 bits --> 12 bits

compiler-rt/lib/profile/InstrProfiling.c

27

what is -1 value reserved for?

llvm/include/llvm/ProfileData/InstrProfData.inc

657

8->12

llvm/lib/ProfileData/InstrProfReader.cpp

281

Describe trace text format as comments.

644

what is this increment?

llvm/lib/ProfileData/InstrProfWriter.cpp

311

Is it better to do deeper merge, e.g. b -c -d can be merged with a-b-c-d-e, and a-b and be merged with b-c. A trace count can also be added for each merged trace to show the weight.

[ellis]

Add/update comments

compiler-rt/lib/profile/InstrProfiling.c

27

For counts instrumentation the __llvm_prf_cnts section is initialized to zero while for coverage instrumetation the section is initialized to all ones. So both 0 and -1 are uninitialized values. See https://github.com/llvm/llvm-project/blob/a78997e0aa89250a193ff036e7c6e71562e03222/llvm/lib/Transforms/Instrumentation/InstrProfiling.cpp#L911-L926

llvm/lib/ProfileData/InstrProfReader.cpp

644

I added a clarifying comment. Hopefully it makes sense :)

llvm/lib/ProfileData/InstrProfWriter.cpp

311

That's an interesting idea, but I think this will lose information. If b-c-d is merged with a-b-c-d-e then we no longer remember that b was the first function in a trace. This is important because functions called early in a trace are important during startup.

Also, in practice I would guess most traces would differ in small sections scattered throughout the trace, making this type of merging less useful. We could probably "compress" these traces by storing common runs of functions, but this is overkill IMO. With TraceReservoirSize = 100 and MaxTraceLength = 10000 the max overhead is 8Mb I believe.

[snehasish]

Looks good overall, added a few comments which are mostly cosmetic.

compiler-rt/include/profile/InstrProfData.inc

670

If we used the 63rd bit then we wouldn't have to update the mask. Is there reason why we can't do so?

llvm/include/llvm/ProfileData/InstrProfReader.h

535

I think in the common case the indexed format will contain instrumentation profiles and TemporalProfiles. If so, then naming this hasTemporalProfile would be nice.

llvm/lib/ProfileData/InstrProfReader.cpp

270–274

Prefer a more descriptive text here: "temporal_profile" or "function_traces". Also see other comment about using a consistent naming scheme.

1132

Add a comment about the expected information to be read, i.e. NumTraces and TraceStreamSize?

llvm/lib/ProfileData/InstrProfWriter.cpp

303

This feels like it would lead to non-deterministic builds where the raw profile is an input to the build. Is the seed deterministic?

341

Can we use auto& to avoid a copy for Trace?

440

There seem to be a few different phrases referring to the same functionality, e.g. TemporalProfile, FunctionTraces and just Trace in other places. It would be nice to have a single prefix for all the var and function names to be able to quickly navigate the code. What do you think?

llvm/unittests/ProfileData/InstrProfTest.cpp

233

Add a comment for the param set to false, I think it should be /*Sparse=*/=false. Here and below.

[ellis]

Resolve some comments

compiler-rt/include/profile/InstrProfData.inc

670

Oh my mistake, we can in fact use the 63rd bit here. I think I was anticipating this bit being used in my earlier revisions. Thanks for catching!

llvm/lib/ProfileData/InstrProfWriter.cpp

303

I've added std::mt19937 RNG to InstrProfWriter which has a constant default seed which should make this deterministic.

440

I see what you mean. I'm using FunctionTrace and Trace interchangeably and they aren't very descriptive. What do you think of the TP (Temporal Profiling) prefix? So I would use TPTrace in code and :tp_traces for the text format.

[ellis]

Remove comments

[snehasish]

llvm/include/llvm/ProfileData/InstrProfReader.h

138

nit: s/is/has

llvm/lib/ProfileData/InstrProfWriter.cpp

440

I prefer something more verbose like "TemporalProf", but up to you to decide, "TP" as the prefix is fine too.

[ellis]

Rename trace variables to be more consistent

llvm/lib/ProfileData/InstrProfWriter.cpp

440

Thanks for the feedback! I ended up going with TemporalProf... and I tried to update all the variables to be more consistent.

[snehasish]

lgtm

[ellis]

Thanks for the quick review! Unless anyone else has concerns, I'll land on Tuesday since I'm out of town on Monday.

[ellis]

Rebase and test

[hans]

This broke the profile tests on Darwin, see e.g. the end of https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8784035713603613281/+/u/package_clang/stdout

It seems these tests are checking what symbols are exported by the runtime, and are surprised to find the new __llvm_profile_global_timestamp variable there.

From what I can tell, that variable is only accessed inside the library, and making it static fixes the tests, so I'll go ahead and do that. Please revert if that doesn't seem right to you.

[ellis]

In D147287#4261473, @hans wrote:

This broke the profile tests on Darwin, see e.g. the end of https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8784035713603613281/+/u/package_clang/stdout

It seems these tests are checking what symbols are exported by the runtime, and are surprised to find the new __llvm_profile_global_timestamp variable there.

From what I can tell, that variable is only accessed inside the library, and making it static fixes the tests, so I'll go ahead and do that. Please revert if that doesn't seem right to you.

That seems fine to me. Thanks for fixing!

[MaskRay]

In D147287#4261473, @hans wrote:

This broke the profile tests on Darwin, see e.g. the end of https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket/8784035713603613281/+/u/package_clang/stdout

It seems these tests are checking what symbols are exported by the runtime, and are surprised to find the new __llvm_profile_global_timestamp variable there.

From what I can tell, that variable is only accessed inside the library, and making it static fixes the tests, so I'll go ahead and do that. Please revert if that doesn't seem right to you.

Seems good. If we make the variable internal linkage, we can drop the leading __, but we don't need to make the change right now :)

(Thanks for the feature and I will try studying it after a long vacation...)

compiler-rt/include/profile/InstrProfData.inc

 #define INSTR_PROF_RAW_MAGIC_32 (uint64_t)255 << 56 | (uint64_t)'l' << 48 | \
        (uint64_t)'p' << 40 | (uint64_t)'r' << 32 | (uint64_t)'o' << 24 |  \
         (uint64_t)'f' << 16 | (uint64_t)'R' << 8 | (uint64_t)129
 
 /* FIXME: Please remedy the fixme in the header before bumping the version. */
 /* Raw profile format version (start from 1). */
 #define INSTR_PROF_RAW_VERSION 8
 /* Indexed profile format version (start from 1). */
-#define INSTR_PROF_INDEX_VERSION 9
+#define INSTR_PROF_INDEX_VERSION 10
 /* Coverage mapping format version (start from 0). */
 #define INSTR_PROF_COVMAP_VERSION 5
 
 /* Profile version is always of type uint64_t. Reserve the upper 8 bits in the
  * version for other variants of profile. We set the lowest bit of the upper 8
  * bits (i.e. bit 56) to 1 to indicate if this is an IR-level instrumentation
  * generated profile, and 0 if this is a Clang FE generated profile.
  * 1 in bit 57 indicates there are context-sensitive records in the profile.
+ * The 55th bit indicates if this is a temporal profile.
  * The 59th bit indicates whether to use debug info to correlate profiles.
  * The 60th bit indicates single byte coverage instrumentation.
  * The 61st bit indicates function entry instrumentation only.
  * The 62nd bit indicates whether memory profile information is present.
  */
-#define VARIANT_MASKS_ALL 0xff00000000000000ULL
+#define VARIANT_MASKS_ALL 0xfff0000000000000ULL
 #define GET_VERSION(V) ((V) & ~VARIANT_MASKS_ALL)
+#define VARIANT_MASK_TEMPORAL_PROF (0x1ULL << 55)
 #define VARIANT_MASK_IR_PROF (0x1ULL << 56)
 #define VARIANT_MASK_CSIR_PROF (0x1ULL << 57)
 #define VARIANT_MASK_INSTR_ENTRY (0x1ULL << 58)
 #define VARIANT_MASK_DBG_CORRELATE (0x1ULL << 59)
 #define VARIANT_MASK_BYTE_COVERAGE (0x1ULL << 60)
 #define VARIANT_MASK_FUNCTION_ENTRY_ONLY (0x1ULL << 61)
 #define VARIANT_MASK_MEMPROF (0x1ULL << 62)
 #define INSTR_PROF_RAW_VERSION_VAR __llvm_profile_raw_version
 #define INSTR_PROF_PROFILE_RUNTIME_VAR __llvm_profile_runtime
 #define INSTR_PROF_PROFILE_COUNTER_BIAS_VAR __llvm_profile_counter_bias
+#define INSTR_PROF_PROFILE_SET_TIMESTAMP __llvm_profile_set_timestamp
 
 /* The variable that holds the name of the profile data
  * specified via command line. */
 #define INSTR_PROF_PROFILE_NAME_VAR __llvm_profile_filename
 
 /* section name strings common to all targets other
    than WIN32 */
 #define INSTR_PROF_DATA_COMMON __llvm_prf_data

compiler-rt/lib/profile/InstrProfiling.c

 #include <string.h>
 
 #include "InstrProfiling.h"
 #include "InstrProfilingInternal.h"
 
 #define INSTR_PROF_VALUE_PROF_DATA
 #include "profile/InstrProfData.inc"
 
+uint32_t __llvm_profile_global_timestamp = 1;
+
+COMPILER_RT_VISIBILITY
+void INSTR_PROF_PROFILE_SET_TIMESTAMP(uint64_t *Probe) {
+  if (*Probe == 0 || *Probe == (uint64_t)-1)
+    *Probe = __llvm_profile_global_timestamp++;
+}
+
 COMPILER_RT_VISIBILITY uint64_t __llvm_profile_get_magic(void) {
   return sizeof(void *) == sizeof(uint64_t) ? (INSTR_PROF_RAW_MAGIC_64)
                                             : (INSTR_PROF_RAW_MAGIC_32);
 }
 
 COMPILER_RT_VISIBILITY void __llvm_profile_set_dumped(void) {
   lprofSetProfileDumped(1);
 }
 
 /* Return the number of bytes needed to add to SizeInBytes to make it
  *   the result a multiple of 8.
  */
 COMPILER_RT_VISIBILITY uint8_t
 __llvm_profile_get_num_padding_bytes(uint64_t SizeInBytes) {
   return 7 & (sizeof(uint64_t) - SizeInBytes % sizeof(uint64_t));
 }
 
 COMPILER_RT_VISIBILITY uint64_t __llvm_profile_get_version(void) {
   return INSTR_PROF_RAW_VERSION_VAR;
 }
 
 COMPILER_RT_VISIBILITY void __llvm_profile_reset_counters(void) {
+  if (__llvm_profile_get_version() & VARIANT_MASK_TEMPORAL_PROF)
+    __llvm_profile_global_timestamp = 1;
+
   char *I = __llvm_profile_begin_counters();
   char *E = __llvm_profile_end_counters();
 
   char ResetValue =
       (__llvm_profile_get_version() & VARIANT_MASK_BYTE_COVERAGE) ? 0xFF : 0;
   memset(I, ResetValue, E - I);
 
   const __llvm_profile_data *DataBegin = __llvm_profile_begin_data();

compiler-rt/test/profile/instrprof-timestamp.c

+// RUN: rm -f %t.profdata
+// RUN: %clang_pgogen -o %t -mllvm -pgo-temporal-instrumentation %s
+// RUN: env LLVM_PROFILE_FILE=%t.0.profraw %run %t n
+// RUN: env LLVM_PROFILE_FILE=%t.1.profraw %run %t y
+// RUN: llvm-profdata merge -o %t.profdata %t.0.profraw %t.1.profraw
+// RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --implicit-check-not=unused
+
+// RUN: rm -f %t.profdata
+// RUN: %clang_pgogen -o %t -mllvm -pgo-temporal-instrumentation -mllvm -pgo-block-coverage %s
+// RUN: env LLVM_PROFILE_FILE=%t.0.profraw %run %t n
+// RUN: env LLVM_PROFILE_FILE=%t.1.profraw %run %t y
+// RUN: llvm-profdata merge -o %t.profdata %t.0.profraw %t.1.profraw
+// RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --implicit-check-not=unused
+
+extern void exit(int);
+extern void __llvm_profile_reset_counters();
+
+void a() {}
+void b() {}
+void unused() { exit(1); }
+void c() {}
+
+int main(int argc, const char *argv[]) {
+  if (argc != 2)
+    unused();
+  a();
+  b();
+  b();
+  c();
+  if (*argv[1] == 'y')
+    __llvm_profile_reset_counters();
+  a();
+  c();
+  b();
+  return 0;
+}
+
+// CHECK: Function Traces (samples=2 seen=2):
+// CHECK:   Trace 0 (count=4):
+// CHECK:     main
+// CHECK:     a
+// CHECK:     b
+// CHECK:     c
+// CHECK:   Trace 1 (count=3):
+// CHECK:     a
+// CHECK:     c
+// CHECK:     b

llvm/docs/LangRef.rst

 intrinsic.
 
 The last argument specifies the value of the increment of the counter variable.
 
 Semantics:
 """"""""""
 See description of '``llvm.instrprof.increment``' intrinsic.
 
+'``llvm.instrprof.timestamp``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare void @llvm.instrprof.timestamp(i8* <name>, i64 <hash>,
+                                             i32 <num-counters>, i32 <index>)
+
+Overview:
+"""""""""
+
+The '``llvm.instrprof.timestamp``' intrinsic is used to implement function
+timestamp instrumentation.
+
+Arguments:
+""""""""""
+The arguments are the same as '``llvm.instrprof.increment``'. The ``index`` is
+expected to always be zero.
+
+Semantics:
+""""""""""
+Similar to the '``llvm.instrprof.increment``' intrinsic, but it stores a
+timestamp representing when this function was executed for the first time.
+
 '``llvm.instrprof.cover``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 

llvm/include/llvm/IR/IntrinsicInst.h

public:
   static bool classof(const IntrinsicInst *I) {
     return I->getIntrinsicID() == Intrinsic::instrprof_increment_step;
   }
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
   }
 };
 
+/// This represents the llvm.instrprof.timestamp intrinsic.
+class InstrProfTimestampInst : public InstrProfInstBase {
+public:
+  static bool classof(const IntrinsicInst *I) {
+    return I->getIntrinsicID() == Intrinsic::instrprof_timestamp;
+  }
+  static bool classof(const Value *V) {
+    return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));
+  }
+};
+
 /// This represents the llvm.instrprof.value.profile intrinsic.
 class InstrProfValueProfileInst : public InstrProfInstBase {
 public:
   static bool classof(const IntrinsicInst *I) {
     return I->getIntrinsicID() == Intrinsic::instrprof_value_profile;
   }
   static bool classof(const Value *V) {
     return isa<IntrinsicInst>(V) && classof(cast<IntrinsicInst>(V));

llvm/include/llvm/IR/Intrinsics.td

def int_instrprof_increment : Intrinsic<[],
                                         [llvm_ptr_ty, llvm_i64_ty,
                                          llvm_i32_ty, llvm_i32_ty]>;
 
 // A counter increment with step for instrumentation based profiling.
 def int_instrprof_increment_step : Intrinsic<[],
                                         [llvm_ptr_ty, llvm_i64_ty,
                                          llvm_i32_ty, llvm_i32_ty, llvm_i64_ty]>;
 
+// A timestamp for instrumentation based profiling.
+def int_instrprof_timestamp : Intrinsic<[], [llvm_ptr_ty, llvm_i64_ty,
+                                             llvm_i32_ty, llvm_i32_ty]>;
+
 // A call to profile runtime for value profiling of target expressions
 // through instrumentation based profiling.
 def int_instrprof_value_profile : Intrinsic<[],
                                             [llvm_ptr_ty, llvm_i64_ty,
                                              llvm_i64_ty, llvm_i32_ty,
                                              llvm_i32_ty]>;
 
 def int_call_preallocated_setup : DefaultAttrsIntrinsic<[llvm_token_ty], [llvm_i32_ty]>;

llvm/include/llvm/ProfileData/InstrProf.h

enum class InstrProfKind {
   // A context sensitive IR-level profile.
   ContextSensitive = 0x8,
   // Use single byte probes for coverage.
   SingleByteCoverage = 0x10,
   // Only instrument the function entry basic block.
   FunctionEntryOnly = 0x20,
   // A memory profile collected using -fprofile=memory.
   MemProf = 0x40,
-  LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/MemProf)
+  // A temporal profile.
+  TemporalProfile = 0x80,
+  LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/TemporalProfile)
 };
 
 const std::error_category &instrprof_category();
 
 enum class instrprof_error {
   success = 0,
   eof,
   unrecognized_format,
enum class instrprof_error {
   counter_overflow,
   value_site_count_mismatch,
   compress_failed,
   uncompress_failed,
   empty_raw_profile,
   zlib_unavailable
 };
 
+/// An ordered list of functions identified by their NameRef found in
+/// INSTR_PROF_DATA
+using InstrProfTraceTy = std::vector<uint64_t>;
+
 inline std::error_code make_error_code(instrprof_error E) {
   return std::error_code(static_cast<int>(E), instrprof_category());
 }
 
 class InstrProfError : public ErrorInfo<InstrProfError> {
 public:
   InstrProfError(instrprof_error Err, const Twine &ErrStr = Twine())
       : Err(Err), Msg(ErrStr.str()) {
enum ProfVersion {
   // may produce hashes different from Version5.
   Version6 = 6,
   // An additional counter is added around logical operators.
   Version7 = 7,
   // An additional (optional) memory profile type is added.
   Version8 = 8,
   // Binary ids are added.
   Version9 = 9,
-  // The current version is 9.
+  // An additional (optional) function traces section is added.
+  Version10 = 10,
+  // The current version is 10.
   CurrentVersion = INSTR_PROF_INDEX_VERSION
 };
 const uint64_t Version = ProfVersion::CurrentVersion;
 
 const HashT HashType = HashT::MD5;
 
 inline uint64_t ComputeHash(StringRef K) { return ComputeHash(HashType, K); }
 
 // This structure defines the file header of the LLVM profile
 // data file in indexed-format.
 struct Header {
   uint64_t Magic;
   uint64_t Version;
   uint64_t Unused; // Becomes unused since version 4
   uint64_t HashType;
   uint64_t HashOffset;
   uint64_t MemProfOffset;
   uint64_t BinaryIdOffset;
+  uint64_t FunctionTracesOffset;
   // New fields should only be added at the end to ensure that the size
   // computation is correct. The methods below need to be updated to ensure that
   // the new field is read correctly.
 
   // Reads a header struct from the buffer.
   static Expected<Header> readFromBuffer(const unsigned char *Buffer);
 
   // Returns the size of the header in bytes for all valid fields based on the

llvm/include/llvm/ProfileData/InstrProfData.inc

 #define INSTR_PROF_RAW_MAGIC_32 (uint64_t)255 << 56 | (uint64_t)'l' << 48 | \
        (uint64_t)'p' << 40 | (uint64_t)'r' << 32 | (uint64_t)'o' << 24 |  \
         (uint64_t)'f' << 16 | (uint64_t)'R' << 8 | (uint64_t)129
 
 /* FIXME: Please remedy the fixme in the header before bumping the version. */
 /* Raw profile format version (start from 1). */
 #define INSTR_PROF_RAW_VERSION 8
 /* Indexed profile format version (start from 1). */
-#define INSTR_PROF_INDEX_VERSION 9
+#define INSTR_PROF_INDEX_VERSION 10
 /* Coverage mapping format version (start from 0). */
 #define INSTR_PROF_COVMAP_VERSION 5
 
 /* Profile version is always of type uint64_t. Reserve the upper 8 bits in the
  * version for other variants of profile. We set the lowest bit of the upper 8
  * bits (i.e. bit 56) to 1 to indicate if this is an IR-level instrumentation
  * generated profile, and 0 if this is a Clang FE generated profile.
  * 1 in bit 57 indicates there are context-sensitive records in the profile.
+ * The 55th bit indicates if this is a temporal profile.
  * The 59th bit indicates whether to use debug info to correlate profiles.
  * The 60th bit indicates single byte coverage instrumentation.
  * The 61st bit indicates function entry instrumentation only.
  * The 62nd bit indicates whether memory profile information is present.
  */
-#define VARIANT_MASKS_ALL 0xff00000000000000ULL
+#define VARIANT_MASKS_ALL 0xfff0000000000000ULL
 #define GET_VERSION(V) ((V) & ~VARIANT_MASKS_ALL)
+#define VARIANT_MASK_TEMPORAL_PROF (0x1ULL << 55)
 #define VARIANT_MASK_IR_PROF (0x1ULL << 56)
 #define VARIANT_MASK_CSIR_PROF (0x1ULL << 57)
 #define VARIANT_MASK_INSTR_ENTRY (0x1ULL << 58)
 #define VARIANT_MASK_DBG_CORRELATE (0x1ULL << 59)
 #define VARIANT_MASK_BYTE_COVERAGE (0x1ULL << 60)
 #define VARIANT_MASK_FUNCTION_ENTRY_ONLY (0x1ULL << 61)
 #define VARIANT_MASK_MEMPROF (0x1ULL << 62)
 #define INSTR_PROF_RAW_VERSION_VAR __llvm_profile_raw_version
 #define INSTR_PROF_PROFILE_RUNTIME_VAR __llvm_profile_runtime
 #define INSTR_PROF_PROFILE_COUNTER_BIAS_VAR __llvm_profile_counter_bias
+#define INSTR_PROF_PROFILE_SET_TIMESTAMP __llvm_profile_set_timestamp
 
 /* The variable that holds the name of the profile data
  * specified via command line. */
 #define INSTR_PROF_PROFILE_NAME_VAR __llvm_profile_filename
 
 /* section name strings common to all targets other
    than WIN32 */
 #define INSTR_PROF_DATA_COMMON __llvm_prf_data

llvm/include/llvm/ProfileData/InstrProfReader.h

public:
   virtual bool hasSingleByteCoverage() const = 0;
 
   /// Return true if the profile only instruments function entries.
   virtual bool functionEntryOnly() const = 0;
 
   /// Return true if profile includes a memory profile.
   virtual bool hasMemoryProfile() const = 0;
 
+  /// Return true if this is a temporal profile.
+  virtual bool isTemporalProfile() const = 0;
+
   /// Returns a BitsetEnum describing the attributes of the profile. To check
   /// individual attributes prefer using the helpers above.
   virtual InstrProfKind getProfileKind() const = 0;
 
   /// Return the PGO symtab. There are three different readers:
   /// Raw, Text, and Indexed profile readers. The first two types
   /// of readers are used only by llvm-profdata tool, while the indexed
   /// profile reader is also used by llvm-cov tool and the compiler (
   /// backend or frontend). Since creating PGO symtab can create
   /// significant runtime and memory overhead (as it touches data
   /// for the whole program), InstrProfSymtab for the indexed profile
   /// reader should be created on demand and it is recommended to be
   /// only used for dumping purpose with llvm-proftool, not with the
   /// compiler.
   virtual InstrProfSymtab &getSymtab() = 0;
 
   /// Compute the sum of counts and return in Sum.
   void accumulateCounts(CountSumOrPercent &Sum, bool IsCS);
 
 protected:
   std::unique_ptr<InstrProfSymtab> Symtab;
+  /// A list of function traces.
+  SmallVector<InstrProfTraceTy> Traces;
+  /// The total number of function traces seen.
+  uint64_t TraceStreamSize = 0;
 
   /// Set the current error and return same.
   Error error(instrprof_error Err, const std::string &ErrMsg = "") {
     LastError = Err;
     LastErrorMsg = ErrMsg;
     if (Err == instrprof_error::success)
       return Error::success();
     return make_error<InstrProfError>(Err, ErrMsg);
public:
   /// instrprof file.
   static Expected<std::unique_ptr<InstrProfReader>>
   create(const Twine &Path, vfs::FileSystem &FS,
          const InstrProfCorrelator *Correlator = nullptr);
 
   static Expected<std::unique_ptr<InstrProfReader>>
   create(std::unique_ptr<MemoryBuffer> Buffer,
          const InstrProfCorrelator *Correlator = nullptr);
+
+  /// Returns a list of function traces.
+  virtual const SmallVector<InstrProfTraceTy> &getFunctionTraces() {
+    return Traces;
+  }
+  /// Returns the total number of function traces seen.
+  uint64_t getTraceStreamSize() { return TraceStreamSize; }
 };
 
 /// Reader for the simple text based instrprof format.
 ///
 /// This format is a simple text format that's suitable for test data. Records
 /// are separated by one or more blank lines, and record fields are separated by
 /// new lines.
 ///
 /// Each record consists of a function name, a function hash, a number of
 /// counters, and then each counter value, in that order.
 class TextInstrProfReader : public InstrProfReader {
 private:
   /// The profile data file contents.
   std::unique_ptr<MemoryBuffer> DataBuffer;
   /// Iterator over the profile data.
   line_iterator Line;
   /// The attributes of the current profile.
   InstrProfKind ProfileKind = InstrProfKind::Unknown;
 
   Error readValueProfileData(InstrProfRecord &Record);
 
+  Error readTraceData();
+
 public:
   TextInstrProfReader(std::unique_ptr<MemoryBuffer> DataBuffer_)
       : DataBuffer(std::move(DataBuffer_)), Line(*DataBuffer, true, '#') {}
   TextInstrProfReader(const TextInstrProfReader &) = delete;
   TextInstrProfReader &operator=(const TextInstrProfReader &) = delete;
 
   /// Return true if the given buffer is in text instrprof format.
   static bool hasFormat(const MemoryBuffer &Buffer);
bool functionEntryOnly() const override {
     return static_cast<bool>(ProfileKind & InstrProfKind::FunctionEntryOnly);
   }
 
   bool hasMemoryProfile() const override {
     // TODO: Add support for text format memory profiles.
     return false;
   }
 
+  bool isTemporalProfile() const override {
+    return static_cast<bool>(ProfileKind & InstrProfKind::TemporalProfile);
+  }
+
   InstrProfKind getProfileKind() const override { return ProfileKind; }
 
   /// Read the header.
   Error readHeader() override;
 
   /// Read a single record.
   Error readNextRecord(NamedInstrProfRecord &Record) override;
 

 template <class IntPtrT>
 class RawInstrProfReader : public InstrProfReader {
 private:
   /// The profile data file contents.
   std::unique_ptr<MemoryBuffer> DataBuffer;
   /// If available, this hold the ProfileData array used to correlate raw
   /// instrumentation data to their functions.
   const InstrProfCorrelatorImpl<IntPtrT> *Correlator;
+  /// A list of timestamps paired with a function name reference.
+  std::vector<std::pair<uint64_t, uint64_t>> FunctionTimestamps;
   bool ShouldSwapBytes;
   // The value of the version field of the raw profile data header. The lower 56
   // bits specifies the format version and the most significant 8 bits specify
   // the variant types of the profile.
   uint64_t Version;
   uint64_t CountersDelta;
   uint64_t NamesDelta;
   const RawInstrProf::ProfileData<IntPtrT> *Data;
public:
   }
 
   bool hasMemoryProfile() const override {
     // Memory profiles have a separate raw format, so this should never be set.
     assert(!(Version & VARIANT_MASK_MEMPROF));
     return false;
   }
 
+  bool isTemporalProfile() const override {
+    return (Version & VARIANT_MASK_TEMPORAL_PROF) != 0;
+  }
+
   /// Returns a BitsetEnum describing the attributes of the raw instr profile.
   InstrProfKind getProfileKind() const override;
 
   InstrProfSymtab &getSymtab() override {
     assert(Symtab.get());
     return *Symtab.get();
   }
 
+  const SmallVector<InstrProfTraceTy> &getFunctionTraces() override;
+
 private:
   Error createSymtab(InstrProfSymtab &Symtab);
   Error readNextHeader(const char *CurrentPos);
   Error readHeader(const RawInstrProf::Header &Header);
 
   template <class IntT> IntT swap(IntT Int) const {
     return ShouldSwapBytes ? sys::getSwappedBytes(Int) : Int;
   }
struct InstrProfReaderIndexBase {
   virtual void setValueProfDataEndianness(support::endianness Endianness) = 0;
   virtual uint64_t getVersion() const = 0;
   virtual bool isIRLevelProfile() const = 0;
   virtual bool hasCSIRLevelProfile() const = 0;
   virtual bool instrEntryBBEnabled() const = 0;
   virtual bool hasSingleByteCoverage() const = 0;
   virtual bool functionEntryOnly() const = 0;
   virtual bool hasMemoryProfile() const = 0;
+  virtual bool isTemporalProfile() const = 0;
   virtual InstrProfKind getProfileKind() const = 0;
   virtual Error populateSymtab(InstrProfSymtab &) = 0;
 };
 
 using OnDiskHashTableImplV3 =
     OnDiskIterableChainedHashTable<InstrProfLookupTrait>;
 
 using MemProfRecordHashTable =
public:
   bool functionEntryOnly() const override {
     return (FormatVersion & VARIANT_MASK_FUNCTION_ENTRY_ONLY) != 0;
   }
 
   bool hasMemoryProfile() const override {
     return (FormatVersion & VARIANT_MASK_MEMPROF) != 0;
   }
 
+  bool isTemporalProfile() const override {
+    return (FormatVersion & VARIANT_MASK_TEMPORAL_PROF) != 0;
+  }
+
   InstrProfKind getProfileKind() const override;
 
   Error populateSymtab(InstrProfSymtab &Symtab) override {
     return Symtab.create(HashTable->keys());
   }
 };
 
 /// Name matcher supporting fuzzy matching of symbol names to names in profiles.
public:
   bool hasSingleByteCoverage() const override {
     return Index->hasSingleByteCoverage();
   }
 
   bool functionEntryOnly() const override { return Index->functionEntryOnly(); }
 
   bool hasMemoryProfile() const override { return Index->hasMemoryProfile(); }
 
+  bool isTemporalProfile() const override { return Index->isTemporalProfile(); }
+
   /// Returns a BitsetEnum describing the attributes of the indexed instr
   /// profile.
   InstrProfKind getProfileKind() const override {
     return Index->getProfileKind();
   }
 
   /// Return true if the given buffer is in an indexed instrprof format.
   static bool hasFormat(const MemoryBuffer &DataBuffer);

llvm/include/llvm/ProfileData/InstrProfWriter.h

 #include "llvm/IR/GlobalValue.h"
 #include "llvm/Object/BuildID.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/ProfileData/MemProf.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include <cstdint>
 #include <memory>
+#include <random>
 
 namespace llvm {
 
 /// Writer for instrumentation based profile data.
 class InstrProfRecordWriterTrait;
 class ProfOStream;
 class MemoryBuffer;
 class raw_fd_ostream;
 
 class InstrProfWriter {
 public:
   using ProfilingData = SmallDenseMap<uint64_t, InstrProfRecord>;
 
 private:
   bool Sparse;
   StringMap<ProfilingData> FunctionData;
+  /// The maximum length of a single trace.
+  uint64_t MaxTraceLength;
+  /// The maximum number of stored traces.
+  uint64_t TraceReservoirSize;
+  /// The total number of function traces seen.
+  uint64_t TraceStreamSize = 0;
+  /// The list of traces.
+  SmallVector<InstrProfTraceTy> Traces;
+  std::mt19937 RNG;
 
   // A map to hold memprof data per function. The lower 64 bits obtained from
   // the md5 hash of the function name is used to index into the map.
   llvm::MapVector<GlobalValue::GUID, memprof::IndexedMemProfRecord>
       MemProfRecordData;
   // A map to hold frame id to frame mappings. The mappings are used to
   // convert IndexedMemProfRecord to MemProfRecords with frame information
   // inline.
   llvm::MapVector<memprof::FrameId, memprof::Frame> MemProfFrameData;
 
   // List of binary ids.
   std::vector<llvm::object::BuildID> BinaryIds;
 
   // An enum describing the attributes of the profile.
   InstrProfKind ProfileKind = InstrProfKind::Unknown;
   // Use raw pointer here for the incomplete type object.
   InstrProfRecordWriterTrait *InfoObj;
 
 public:
-  InstrProfWriter(bool Sparse = false);
+  InstrProfWriter(bool Sparse = false, uint64_t TraceReservoirSize = 0,
+                  uint64_t MaxTraceLength = 0);
   ~InstrProfWriter();
 
   StringMap<ProfilingData> &getProfileData() { return FunctionData; }
 
   /// Add function counts for the given function. If there are already counts
   /// for this function and the hash and number of counts match, each counter is
   /// summed. Optionally scale counts by \p Weight.
   void addRecord(NamedInstrProfRecord &&I, uint64_t Weight,
                  function_ref<void(Error)> Warn);
   void addRecord(NamedInstrProfRecord &&I, function_ref<void(Error)> Warn) {
     addRecord(std::move(I), 1, Warn);
   }
 
+  /// Add \p SrcTraces using reservoir sampling where \p SrcTraceStreamSize is
+  /// the total number of traces the source has seen.
+  void addFunctionTraces(SmallVector<InstrProfTraceTy> SrcTraces,
+                         uint64_t SrcTraceStreamSize);
+
   /// Add a memprof record for a function identified by its \p Id.
   void addMemProfRecord(const GlobalValue::GUID Id,
                         const memprof::IndexedMemProfRecord &Record);
 
   /// Add a memprof frame identified by the hash of the contents of the frame in
   /// \p FrameId.
   bool addMemProfFrame(const memprof::FrameId, const memprof::Frame &F,
                        function_ref<void(Error)> Warn);
 
   // Add a binary id to the binary ids list.
   void addBinaryIds(ArrayRef<llvm::object::BuildID> BIs);
 
   /// Merge existing function counts from the given writer.
   void mergeRecordsFromWriter(InstrProfWriter &&IPW,
                               function_ref<void(Error)> Warn);
 
   /// Write the profile to \c OS
   Error write(raw_fd_ostream &OS);
 
   /// Write the profile in text format to \c OS
   Error writeText(raw_fd_ostream &OS);
 
+  /// Write function trace data to the header in text format to \c OS
+  void writeTextTraceData(raw_fd_ostream &OS, InstrProfSymtab &Symtab);
+
   Error validateRecord(const InstrProfRecord &Func);
 
   /// Write \c Record in text format to \c OS
   static void writeRecordInText(StringRef Name, uint64_t Hash,
                                 const InstrProfRecord &Counters,
                                 InstrProfSymtab &Symtab, raw_fd_ostream &OS);
 
   /// Write the profile, returning the raw data. For testing.
public:
   void overlapRecord(NamedInstrProfRecord &&Other, OverlapStats &Overlap,
                      OverlapStats &FuncLevelOverlap,
                      const OverlapFuncFilters &FuncFilter);
 
 private:
   void addRecord(StringRef Name, uint64_t Hash, InstrProfRecord &&I,
                  uint64_t Weight, function_ref<void(Error)> Warn);
   bool shouldEncodeData(const ProfilingData &PD);
+  /// Add \p Trace using reservoir sampling.
+  void addFunctionTrace(InstrProfTraceTy Trace);
 
   Error writeImpl(ProfOStream &OS);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_INSTRPROFWRITER_H

llvm/include/llvm/Transforms/Instrumentation/InstrProfiling.h

private:
   void computeNumValueSiteCounts(InstrProfValueProfileInst *Ins);
 
   /// Replace instrprof.value.profile with a call to runtime library.
   void lowerValueProfileInst(InstrProfValueProfileInst *Ins);
 
   /// Replace instrprof.cover with a store instruction to the coverage byte.
   void lowerCover(InstrProfCoverInst *Inc);
 
+  /// Replace instrprof.timestamp with a call to
+  /// INSTR_PROF_PROFILE_SET_TIMESTAMP.
+  void lowerTimestamp(InstrProfTimestampInst *TimestampInstruction);
+
   /// Replace instrprof.increment with an increment of the appropriate value.
   void lowerIncrement(InstrProfIncrementInst *Inc);
 
   /// Force emitting of name vars for unused functions.
   void lowerCoverageData(GlobalVariable *CoverageNamesVar);
 
   /// Compute the address of the counter value that this profiling instruction
   /// acts on.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::experimental_gc_result:
     return;
   case Intrinsic::experimental_gc_relocate:
     visitGCRelocate(cast<GCRelocateInst>(I));
     return;
   case Intrinsic::instrprof_cover:
     llvm_unreachable("instrprof failed to lower a cover");
   case Intrinsic::instrprof_increment:
     llvm_unreachable("instrprof failed to lower an increment");
+  case Intrinsic::instrprof_timestamp:
+    llvm_unreachable("instrprof failed to lower a timestamp");
   case Intrinsic::instrprof_value_profile:
     llvm_unreachable("instrprof failed to lower a value profiling call");
   case Intrinsic::localescape: {
     MachineFunction &MF = DAG.getMachineFunction();
     const TargetInstrInfo *TII = DAG.getSubtarget().getInstrInfo();
 
     // Directly emit some LOCAL_ESCAPE machine instrs. Label assignment emission
     // is the same on all targets.

llvm/lib/ProfileData/InstrProf.cpp

Expected<Header> Header::readFromBuffer(const unsigned char *Buffer) {
   if (GET_VERSION(H.formatVersion()) >
       IndexedInstrProf::ProfVersion::CurrentVersion)
     return make_error<InstrProfError>(instrprof_error::unsupported_version);
 
   switch (GET_VERSION(H.formatVersion())) {
     // When a new field is added in the header add a case statement here to
     // populate it.
     static_assert(
-        IndexedInstrProf::ProfVersion::CurrentVersion == Version9,
+        IndexedInstrProf::ProfVersion::CurrentVersion == Version10,
         "Please update the reading code below if a new field has been added, "
         "if not add a case statement to fall through to the latest version.");
+  case 10ull:
+    H.FunctionTracesOffset =
+        read(Buffer, offsetOf(&Header::FunctionTracesOffset));
+    LLVM_FALLTHROUGH;
   case 9ull:
     H.BinaryIdOffset = read(Buffer, offsetOf(&Header::BinaryIdOffset));
     [[fallthrough]];
   case 8ull:
     H.MemProfOffset = read(Buffer, offsetOf(&Header::MemProfOffset));
     [[fallthrough]];
   default: // Version7 (when the backwards compatible header was introduced).
     H.HashType = read(Buffer, offsetOf(&Header::HashType));
     H.HashOffset = read(Buffer, offsetOf(&Header::HashOffset));
   }
 
   return H;
 }
 
 size_t Header::size() const {
   switch (GET_VERSION(formatVersion())) {
     // When a new field is added to the header add a case statement here to
     // compute the size as offset of the new field + size of the new field. This
     // relies on the field being added to the end of the list.
-    static_assert(IndexedInstrProf::ProfVersion::CurrentVersion == Version9,
+    static_assert(IndexedInstrProf::ProfVersion::CurrentVersion == Version10,
                   "Please update the size computation below if a new field has "
                   "been added to the header, if not add a case statement to "
                   "fall through to the latest version.");
+  case 10ull:
+    return offsetOf(&Header::FunctionTracesOffset) +
+           sizeof(Header::FunctionTracesOffset);
   case 9ull:
     return offsetOf(&Header::BinaryIdOffset) + sizeof(Header::BinaryIdOffset);
   case 8ull:
     return offsetOf(&Header::MemProfOffset) + sizeof(Header::MemProfOffset);
   default: // Version7 (when the backwards compatible header was introduced).
     return offsetOf(&Header::HashOffset) + sizeof(Header::HashOffset);
   }
 }
 
 } // namespace IndexedInstrProf
 
 } // end namespace llvm

llvm/lib/ProfileData/InstrProfReader.cpp

if (Version & VARIANT_MASK_BYTE_COVERAGE) {
     ProfileKind |= InstrProfKind::SingleByteCoverage;
   }
   if (Version & VARIANT_MASK_FUNCTION_ENTRY_ONLY) {
     ProfileKind |= InstrProfKind::FunctionEntryOnly;
   }
   if (Version & VARIANT_MASK_MEMPROF) {
     ProfileKind |= InstrProfKind::MemProf;
   }
+  if (Version & VARIANT_MASK_TEMPORAL_PROF) {
+    ProfileKind |= InstrProfKind::TemporalProfile;
+  }
   return ProfileKind;
 }
 
 static Expected<std::unique_ptr<MemoryBuffer>>
 setupMemoryBuffer(const Twine &Filename, vfs::FileSystem &FS) {
   auto BufferOrErr = Filename.str() == "-" ? MemoryBuffer::getSTDIN()
                                            : FS.getBufferForFile(Filename);
   if (std::error_code EC = BufferOrErr.getError())
else if (Str.equals_insensitive("fe"))
       ProfileKind |= InstrProfKind::FrontendInstrumentation;
     else if (Str.equals_insensitive("csir")) {
       ProfileKind |= InstrProfKind::IRInstrumentation;
       ProfileKind |= InstrProfKind::ContextSensitive;
     } else if (Str.equals_insensitive("entry_first"))
       ProfileKind |= InstrProfKind::FunctionEntryInstrumentation;
     else if (Str.equals_insensitive("not_entry_first"))
       ProfileKind &= ~InstrProfKind::FunctionEntryInstrumentation;
-    else
+    else if (Str.equals_insensitive("traces")) {
+      ProfileKind |= InstrProfKind::TemporalProfile;
+      if (auto Err = readTraceData())
+        return error(std::move(Err));
+    } else
       return error(instrprof_error::bad_header);
     ++Line;
   }
   return success();
 }
 
+Error TextInstrProfReader::readTraceData() {
+  if ((++Line).is_at_end())
+    return error(instrprof_error::eof);
+
+  uint32_t NumTraces;
+  if (Line->getAsInteger(0, NumTraces))
+    return error(instrprof_error::malformed);
+
+  if ((++Line).is_at_end())
+    return error(instrprof_error::eof);
+
+  if (Line->getAsInteger(0, TraceStreamSize))
+    return error(instrprof_error::malformed);
+
+  for (uint32_t i = 0; i < NumTraces; i++) {
+    if ((++Line).is_at_end())
+      return error(instrprof_error::eof);
+
+    InstrProfTraceTy Trace;
+    SmallVector<StringRef> FuncNames;
+    Line->split(FuncNames, ",", /*MaxSplit=*/-1, /*KeepEmpty=*/false);
+    for (auto &FuncName : FuncNames)
+      Trace.push_back(IndexedInstrProf::ComputeHash(FuncName.trim()));
+    Traces.push_back(std::move(Trace));
+  }
+  return success();
+}
+
 Error
 TextInstrProfReader::readValueProfileData(InstrProfRecord &Record) {
 
 #define CHECK_LINE_END(Line)                                                   \
   if (Line.is_at_end())                                                        \
     return error(instrprof_error::truncated);
 #define READ_NUM(Str, Dst)                                                     \
   if ((Str).getAsInteger(10, (Dst)))                                           \

 }
 
 template <class IntPtrT>
 InstrProfKind RawInstrProfReader<IntPtrT>::getProfileKind() const {
   return getProfileKindFromVersion(Version);
 }
 
 template <class IntPtrT>
+const SmallVector<InstrProfTraceTy> &
+RawInstrProfReader<IntPtrT>::getFunctionTraces() {
+  if (FunctionTimestamps.empty()) {
+    assert(Traces.empty());
+    return Traces;
+  }
+  // Sort functions by their timestamps to build the trace.
+  std::sort(FunctionTimestamps.begin(), FunctionTimestamps.end());
+  InstrProfTraceTy Trace;
+  for (auto &[TimestampValue, NameRef] : FunctionTimestamps)
+    Trace.push_back(NameRef);
+  Traces = {std::move(Trace)};
+  return Traces;
+}
+
+template <class IntPtrT>
 bool RawInstrProfReader<IntPtrT>::hasFormat(const MemoryBuffer &DataBuffer) {
   if (DataBuffer.getBufferSize() < sizeof(uint64_t))
     return false;
   uint64_t Magic =
     *reinterpret_cast<const uint64_t *>(DataBuffer.getBufferStart());
   return RawInstrProf::getMagic<IntPtrT>() == Magic ||
          sys::getSwappedBytes(RawInstrProf::getMagic<IntPtrT>()) == Magic;
 }
return error(instrprof_error::malformed,
                   Twine(MaxNumCounters))
                      .str());
 
   Record.Counts.clear();
   Record.Counts.reserve(NumCounters);
   for (uint32_t I = 0; I < NumCounters; I++) {
     const char *Ptr =
         CountersStart + CounterBaseOffset + I * getCounterTypeSize();
+    if (I == 0 && isTemporalProfile()) {
+      uint64_t TimestampValue = swap(*reinterpret_cast<const uint64_t *>(Ptr));
+      if (TimestampValue != 0 &&
+          TimestampValue != std::numeric_limits<uint64_t>::max()) {
+        FunctionTimestamps.emplace_back(TimestampValue, swap(Data->NameRef));
+        TraceStreamSize = 1;
+      }
+      if (hasSingleByteCoverage())
+        I += 7;
+      continue;
+    }
     if (hasSingleByteCoverage()) {
       // A value of zero signifies the block is covered.
       Record.Counts.push_back(*Ptr == 0 ? 1 : 0);
     } else {
       const auto *CounterValue = reinterpret_cast<const uint64_t *>(Ptr);
       Record.Counts.push_back(swap(*CounterValue));
     }
   }

 Error RawInstrProfReader<IntPtrT>::readNextRecord(NamedInstrProfRecord &Record) {
   // Keep reading profiles that consist of only headers and no profile data and
   // counters.
   while (atEnd())
     // At this point, ValueDataStart field points to the next header.
     if (Error E = readNextHeader(getNextHeaderPos()))
       return error(std::move(E));
 
-  // Read name ad set it in Record.
+  // Read name and set it in Record.
   if (Error E = readName(Record))
     return error(std::move(E));
 
   // Read FuncHash and set it in Record.
   if (Error E = readFuncHash(Record))
     return error(std::move(E));
 
   // Read raw counts and set Record.
if (BinaryIdsSize % sizeof(uint64_t))
       return error(instrprof_error::bad_header);
     // Set the binary ids start.
     BinaryIdsStart = Ptr;
     if (BinaryIdsStart > (const unsigned char *)DataBuffer->getBufferEnd())
       return make_error<InstrProfError>(instrprof_error::malformed,
                                         "corrupted binary ids");
   }
 
+  if (GET_VERSION(Header->formatVersion()) >= 10 &&
+      Header->formatVersion() & VARIANT_MASK_TEMPORAL_PROF) {
+    uint64_t FunctionTracesOffset =
+        endian::byte_swap<uint64_t, little>(Header->FunctionTracesOffset);
+    const unsigned char *Ptr = Start + FunctionTracesOffset;
+    const auto *PtrEnd = (const unsigned char *)DataBuffer->getBufferEnd();
+    if (Ptr + 2 * sizeof(uint64_t) > PtrEnd)
+      return error(instrprof_error::truncated);
+    const uint64_t NumTraces =
+        support::endian::readNext<uint64_t, little, unaligned>(Ptr);
+    TraceStreamSize =
+        support::endian::readNext<uint64_t, little, unaligned>(Ptr);
+    for (unsigned i = 0; i < NumTraces; i++) {
+      if (Ptr + sizeof(uint64_t) > PtrEnd)
+        return error(instrprof_error::truncated);
+      const uint64_t NumFunctions =
+          support::endian::readNext<uint64_t, little, unaligned>(Ptr);
+      if (Ptr + NumFunctions * sizeof(uint64_t) > PtrEnd)
+        return error(instrprof_error::truncated);
+      InstrProfTraceTy Trace;
+      for (unsigned j = 0; j < NumFunctions; j++) {
+        const uint64_t NameRef =
+            support::endian::readNext<uint64_t, little, unaligned>(Ptr);
+        Trace.push_back(NameRef);
+      }
+      Traces.push_back(std::move(Trace));
+    }
+  }
+
   // Load the remapping table now if requested.
   if (RemappingBuffer) {
     Remapper =
         std::make_unique<InstrProfReaderItaniumRemapper<OnDiskHashTableImplV3>>(
             std::move(RemappingBuffer), *IndexPtr);
     if (Error E = Remapper->populateRemappings())
       return E;
   } else {

llvm/lib/ProfileData/InstrProfWriter.cpp

 //===- InstrProfWriter.cpp - Instrumented profiling writer ----------------===//
 //
 // 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 contains support for writing profiling data for clang's
 // instrumentation based PGO and coverage.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ProfileData/InstrProfWriter.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/ProfileData/MemProf.h"
 #include "llvm/ProfileData/ProfileCommon.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/EndianStream.h"
 #include "llvm/Support/Error.h"
for (const auto &ProfileData : *V) {
       VDataPtr->swapBytesFromHost(ValueProfDataEndianness);
       Out.write((const char *)VDataPtr.get(), S);
     }
   }
 };
 
 } // end namespace llvm
 
-InstrProfWriter::InstrProfWriter(bool Sparse)
-    : Sparse(Sparse), InfoObj(new InstrProfRecordWriterTrait()) {}
+InstrProfWriter::InstrProfWriter(bool Sparse, uint64_t TraceReservoirSize,
+                                 uint64_t MaxTraceLength)
+    : Sparse(Sparse), MaxTraceLength(MaxTraceLength),
+      TraceReservoirSize(TraceReservoirSize),
+      InfoObj(new InstrProfRecordWriterTrait()) {}
 
 InstrProfWriter::~InstrProfWriter() { delete InfoObj; }
 
 // Internal interface for testing purpose only.
 void InstrProfWriter::setValueProfDataEndianness(
     support::endianness Endianness) {
   InfoObj->ValueProfDataEndianness = Endianness;
 }
bool InstrProfWriter::addMemProfFrame(const memprof::FrameId Id,
   }
   return true;
 }
 
 void InstrProfWriter::addBinaryIds(ArrayRef<llvm::object::BuildID> BIs) {
   llvm::append_range(BinaryIds, BIs);
 }
 
+void InstrProfWriter::addFunctionTrace(InstrProfTraceTy Trace) {
+  if (Trace.size() > MaxTraceLength)
+    Trace.resize(MaxTraceLength);
+  if (Trace.empty())
+    return;
+
+  if (TraceStreamSize < TraceReservoirSize) {
+    // Simply append the trace if we have not yet hit our reservoir size limit.
+    Traces.push_back(std::move(Trace));
+  } else {
+    // Otherwise, replace a random trace in the stream.
+    std::uniform_int_distribution<uint64_t> Distribution(0, TraceStreamSize);
+    uint64_t RandomIndex = Distribution(RNG);
+    if (RandomIndex < Traces.size())
+      Traces[RandomIndex] = std::move(Trace);
+  }
+  ++TraceStreamSize;
+}
+
+void InstrProfWriter::addFunctionTraces(SmallVector<InstrProfTraceTy> SrcTraces,
+                                        uint64_t SrcTraceStreamSize) {
+  // Assume that the source has the same reservoir size as the destination to
+  // avoid needing to record it in the indexed profile format.
+  bool IsDestSampled = (TraceStreamSize > TraceReservoirSize);
+  bool IsSrcSampled = (SrcTraceStreamSize > TraceReservoirSize);
+  if (!IsDestSampled && IsSrcSampled) {
+    // If one of the traces are sampled, ensure that it belongs to Dest.
+    std::swap(Traces, SrcTraces);
+    std::swap(TraceStreamSize, SrcTraceStreamSize);
+    std::swap(IsDestSampled, IsSrcSampled);
+  }
+  if (!IsSrcSampled) {
+    // If the source stream is not sampled, we add each source trace normally.
+    for (auto &Trace : SrcTraces)
+      addFunctionTrace(std::move(Trace));
+    return;
+  }
+  // Otherwise, we find the traces that would have been removed if we added
+  // the whole source stream.
+  SmallSetVector<uint64_t, 8> IndicesToReplace;
+  for (uint64_t I = 0; I < SrcTraceStreamSize; I++) {
+    std::uniform_int_distribution<uint64_t> Distribution(0, TraceStreamSize);
+    uint64_t RandomIndex = Distribution(RNG);
+    if (RandomIndex < Traces.size())
+      IndicesToReplace.insert(RandomIndex);
+    ++TraceStreamSize;
+  }
+  // Then we insert a random sample of the source traces.
+  llvm::shuffle(SrcTraces.begin(), SrcTraces.end(), RNG);
+  for (auto [Index, Trace] : llvm::zip(IndicesToReplace, SrcTraces))
+    Traces[Index] = std::move(Trace);
+}
+
 void InstrProfWriter::mergeRecordsFromWriter(InstrProfWriter &&IPW,
                                              function_ref<void(Error)> Warn) {
   for (auto &I : IPW.FunctionData)
     for (auto &Func : I.getValue())
       addRecord(I.getKey(), Func.first, std::move(Func.second), 1, Warn);
 
   BinaryIds.reserve(BinaryIds.size() + IPW.BinaryIds.size());
   for (auto &I : IPW.BinaryIds)
     addBinaryIds(I);
 
+  addFunctionTraces(std::move(IPW.Traces), IPW.TraceStreamSize);
+
   MemProfFrameData.reserve(IPW.MemProfFrameData.size());
   for (auto &I : IPW.MemProfFrameData) {
     // If we weren't able to add the frame mappings then it doesn't make sense
     // to try to merge the records from this profile.
     if (!addMemProfFrame(I.first, I.second, Warn))
       return;
   }
 
if (static_cast<bool>(ProfileKind &
                         InstrProfKind::FunctionEntryInstrumentation))
     Header.Version |= VARIANT_MASK_INSTR_ENTRY;
   if (static_cast<bool>(ProfileKind & InstrProfKind::SingleByteCoverage))
     Header.Version |= VARIANT_MASK_BYTE_COVERAGE;
   if (static_cast<bool>(ProfileKind & InstrProfKind::FunctionEntryOnly))
     Header.Version |= VARIANT_MASK_FUNCTION_ENTRY_ONLY;
   if (static_cast<bool>(ProfileKind & InstrProfKind::MemProf))
     Header.Version |= VARIANT_MASK_MEMPROF;
+  if (static_cast<bool>(ProfileKind & InstrProfKind::TemporalProfile))
+    Header.Version |= VARIANT_MASK_TEMPORAL_PROF;
 
   Header.Unused = 0;
   Header.HashType = static_cast<uint64_t>(IndexedInstrProf::HashType);
   Header.HashOffset = 0;
   Header.MemProfOffset = 0;
   Header.BinaryIdOffset = 0;
+  Header.FunctionTracesOffset = 0;
   int N = sizeof(IndexedInstrProf::Header) / sizeof(uint64_t);
 
-  // Only write out all the fields except 'HashOffset', 'MemProfOffset' and
-  // 'BinaryIdOffset'. We need to remember the offset of these fields to allow
-  // back patching later.
-  for (int I = 0; I < N - 3; I++)
+  // Only write out all the fields except 'HashOffset', 'MemProfOffset',
+  // 'BinaryIdOffset' and `FunctionTracesOffset`. We need to remember the offset
+  // of these fields to allow back patching later.
+  for (int I = 0; I < N - 4; I++)
     OS.write(reinterpret_cast<uint64_t *>(&Header)[I]);
 
   // Save the location of Header.HashOffset field in \c OS.
   uint64_t HashTableStartFieldOffset = OS.tell();
   // Reserve the space for HashOffset field.
   OS.write(0);
 
   // Save the location of MemProf profile data. This is stored in two parts as
   // the schema and as a separate on-disk chained hashtable.
   uint64_t MemProfSectionOffset = OS.tell();
   // Reserve space for the MemProf table field to be patched later if this
   // profile contains memory profile information.
   OS.write(0);
 
   // Save the location of binary ids section.
   uint64_t BinaryIdSectionOffset = OS.tell();
   // Reserve space for the BinaryIdOffset field to be patched later if this
   // profile contains binary ids.
   OS.write(0);
 
+  uint64_t FunctionTracesOffset = OS.tell();
+  OS.write(0);
+
   // Reserve space to write profile summary data.
   uint32_t NumEntries = ProfileSummaryBuilder::DefaultCutoffs.size();
   uint32_t SummarySize = Summary::getSize(Summary::NumKinds, NumEntries);
   // Remember the summary offset.
   uint64_t SummaryOffset = OS.tell();
   for (unsigned I = 0; I < SummarySize / sizeof(uint64_t); I++)
     OS.write(0);
   uint64_t CSSummaryOffset = 0;
for (auto BI : BinaryIds) {
     for (unsigned K = 0; K < BILen; K++)
       OS.writeByte(BI[K]);
     // Write padding if necessary.
     uint64_t PaddingSize = alignToPowerOf2(BILen, sizeof(uint64_t)) - BILen;
     for (unsigned K = 0; K < PaddingSize; K++)
       OS.writeByte(0);
   }
 
+  uint64_t FunctionTracesSectionStart = 0;
+  if (static_cast<bool>(ProfileKind & InstrProfKind::TemporalProfile)) {
+    FunctionTracesSectionStart = OS.tell();
+    OS.write(Traces.size());
+    OS.write(TraceStreamSize);
+    for (auto &Trace : Traces) {
+      OS.write(Trace.size());
+      for (auto &NameRef : Trace)
+        OS.write(NameRef);
+    }
+  }
+
   // Allocate space for data to be serialized out.
   std::unique_ptr<IndexedInstrProf::Summary> TheSummary =
       IndexedInstrProf::allocSummary(SummarySize);
   // Compute the Summary and copy the data to the data
   // structure to be serialized out (to disk or buffer).
   std::unique_ptr<ProfileSummary> PS = ISB.getSummary();
   setSummary(TheSummary.get(), *PS);
   InfoObj->SummaryBuilder = nullptr;
Error InstrProfWriter::writeImpl(ProfOStream &OS) {
   PatchItem PatchItems[] = {
       // Patch the Header.HashOffset field.
       {HashTableStartFieldOffset, &HashTableStart, 1},
       // Patch the Header.MemProfOffset (=0 for profiles without MemProf
       // data).
       {MemProfSectionOffset, &MemProfSectionStart, 1},
       // Patch the Header.BinaryIdSectionOffset.
       {BinaryIdSectionOffset, &BinaryIdSectionStart, 1},
+      // Patch the Header.FunctionTracesOffset (=0 for profiles without traces).
+      {FunctionTracesOffset, &FunctionTracesSectionStart, 1},
       // Patch the summary data.
       {SummaryOffset, reinterpret_cast<uint64_t *>(TheSummary.get()),
        (int)(SummarySize / sizeof(uint64_t))},
       {CSSummaryOffset, reinterpret_cast<uint64_t *>(TheCSSummary.get()),
        (int)CSSummarySize}};
 
   OS.patch(PatchItems, std::size(PatchItems));
 
for (const auto &I : FunctionData) {
     if (shouldEncodeData(I.getValue())) {
       if (Error E = Symtab.addFuncName(I.getKey()))
         return E;
       for (const auto &Func : I.getValue())
         OrderedFuncData.push_back(std::make_pair(I.getKey(), Func));
     }
   }
 
+  if (static_cast<bool>(ProfileKind & InstrProfKind::TemporalProfile))
+    writeTextTraceData(OS, Symtab);
+
   llvm::sort(OrderedFuncData, [](const RecordType &A, const RecordType &B) {
     return std::tie(A.first, A.second.first) <
            std::tie(B.first, B.second.first);
   });
 
   for (const auto &record : OrderedFuncData) {
     const StringRef &Name = record.first;
     const FuncPair &Func = record.second;
     writeRecordInText(Name, Func.first, Func.second, Symtab, OS);
   }
 
   for (const auto &record : OrderedFuncData) {
     const FuncPair &Func = record.second;
     if (Error E = validateRecord(Func.second))
       return E;
   }
 
   return Error::success();
 }
+
+void InstrProfWriter::writeTextTraceData(raw_fd_ostream &OS,
+                                         InstrProfSymtab &Symtab) {
+  OS << ":traces\n";
+  OS << "# Num Traces:\n" << Traces.size() << "\n";
+  OS << "# Trace Stream Size:\n" << TraceStreamSize << "\n";
+  for (auto &Trace : Traces) {
+    for (auto &NameRef : Trace)
+      OS << Symtab.getFuncName(NameRef) << ",";
+    OS << "\n";
+  }
+  OS << "\n";
+}

llvm/lib/Transforms/Instrumentation/InstrProfiling.cpp

bool InstrProfiling::lowerIntrinsics(Function *F) {
   for (BasicBlock &BB : *F) {
     for (Instruction &Instr : llvm::make_early_inc_range(BB)) {
       if (auto *IPIS = dyn_cast<InstrProfIncrementInstStep>(&Instr)) {
         lowerIncrement(IPIS);
         MadeChange = true;
       } else if (auto *IPI = dyn_cast<InstrProfIncrementInst>(&Instr)) {
         lowerIncrement(IPI);
         MadeChange = true;
+      } else if (auto *IPC = dyn_cast<InstrProfTimestampInst>(&Instr)) {
+        lowerTimestamp(IPC);
+        MadeChange = true;
       } else if (auto *IPC = dyn_cast<InstrProfCoverInst>(&Instr)) {
         lowerCover(IPC);
         MadeChange = true;
       } else if (auto *IPVP = dyn_cast<InstrProfValueProfileInst>(&Instr)) {
         lowerValueProfileInst(IPVP);
         MadeChange = true;
       }
     }
static bool containsProfilingIntrinsics(Module &M) {
   auto containsIntrinsic = [&](int ID) {
     if (auto *F = M.getFunction(Intrinsic::getName(ID)))
       return !F->use_empty();
     return false;
   };
   return containsIntrinsic(llvm::Intrinsic::instrprof_cover) ||
          containsIntrinsic(llvm::Intrinsic::instrprof_increment) ||
          containsIntrinsic(llvm::Intrinsic::instrprof_increment_step) ||
+         containsIntrinsic(llvm::Intrinsic::instrprof_timestamp) ||
          containsIntrinsic(llvm::Intrinsic::instrprof_value_profile);
 }
 
 bool InstrProfiling::run(
     Module &M, std::function<const TargetLibraryInfo &(Function &F)> GetTLI) {
   this->M = &M;
   this->GetTLI = std::move(GetTLI);
   NamesVar = nullptr;
void InstrProfiling::lowerValueProfileInst(InstrProfValueProfileInst *Ind) {
   Ind->replaceAllUsesWith(Call);
   Ind->eraseFromParent();
 }
 
 Value *InstrProfiling::getCounterAddress(InstrProfInstBase *I) {
   auto *Counters = getOrCreateRegionCounters(I);
   IRBuilder<> Builder(I);
 
+  if (isa<InstrProfTimestampInst>(I))
+    Counters->setAlignment(Align(8));
+
   auto *Addr = Builder.CreateConstInBoundsGEP2_32(
       Counters->getValueType(), Counters, 0, I->getIndex()->getZExtValue());
 
   if (!isRuntimeCounterRelocationEnabled())
     return Addr;
 
   Type *Int64Ty = Type::getInt64Ty(M->getContext());
   Function *Fn = I->getParent()->getParent();

 void InstrProfiling::lowerCover(InstrProfCoverInst *CoverInstruction) {
   auto *Addr = getCounterAddress(CoverInstruction);
   IRBuilder<> Builder(CoverInstruction);
   // We store zero to represent that this block is covered.
   Builder.CreateStore(Builder.getInt8(0), Addr);
   CoverInstruction->eraseFromParent();
 }
 
+void InstrProfiling::lowerTimestamp(
+    InstrProfTimestampInst *TimestampInstruction) {
+  assert(TimestampInstruction->getIndex()->isZeroValue() &&
+         "timestamp probes are always the first probe for a function");
+  auto &Ctx = M->getContext();
+  auto *TimestampAddr = getCounterAddress(TimestampInstruction);
+  IRBuilder<> Builder(TimestampInstruction);
+  auto *CalleeTy =
+      FunctionType::get(Type::getVoidTy(Ctx), TimestampAddr->getType(), false);
+  auto Callee = M->getOrInsertFunction(
+      INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_SET_TIMESTAMP), CalleeTy);
+  Builder.CreateCall(Callee, {TimestampAddr});
+  TimestampInstruction->eraseFromParent();
+}
+
 void InstrProfiling::lowerIncrement(InstrProfIncrementInst *Inc) {
   auto *Addr = getCounterAddress(Inc);
 
   IRBuilder<> Builder(Inc);
   if (Options.Atomic || AtomicCounterUpdateAll ||
       (Inc->getIndex()->isZeroValue() && AtomicFirstCounter)) {
     Builder.CreateAtomicRMW(AtomicRMWInst::Add, Addr, Inc->getStep(),
                             MaybeAlign(), AtomicOrdering::Monotonic);

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

static cl::opt<bool> PGOBlockCoverage(
     "pgo-block-coverage",
     cl::desc("Use this option to enable basic block coverage instrumentation"));
 
 static cl::opt<bool>
     PGOViewBlockCoverageGraph("pgo-view-block-coverage-graph",
                               cl::desc("Create a dot file of CFGs with block "
                                        "coverage inference information"));
 
+static cl::opt<bool> PGOTemporalInstrumentation(
+    "pgo-temporal-instrumentation",
+    cl::desc("Use this option to enable temporal instrumentation"));
+
 static cl::opt<bool>
     PGOFixEntryCount("pgo-fix-entry-count", cl::init(true), cl::Hidden,
                      cl::desc("Fix function entry count in profile use."));
 
 static cl::opt<bool> PGOVerifyHotBFI(
     "pgo-verify-hot-bfi", cl::init(false), cl::Hidden,
     cl::desc("Print out the non-match BFI count if a hot raw profile count "
              "becomes non-hot, or a cold raw profile count becomes hot. "
if (PGOInstrumentEntry)
     ProfileVersion |= VARIANT_MASK_INSTR_ENTRY;
   if (DebugInfoCorrelate)
     ProfileVersion |= VARIANT_MASK_DBG_CORRELATE;
   if (PGOFunctionEntryCoverage)
     ProfileVersion |=
         VARIANT_MASK_BYTE_COVERAGE | VARIANT_MASK_FUNCTION_ENTRY_ONLY;
   if (PGOBlockCoverage)
     ProfileVersion |= VARIANT_MASK_BYTE_COVERAGE;
+  if (PGOTemporalInstrumentation)
+    ProfileVersion |= VARIANT_MASK_TEMPORAL_PROF;
   auto IRLevelVersionVariable = new GlobalVariable(
       M, IntTy64, true, GlobalValue::WeakAnyLinkage,
       Constant::getIntegerValue(IntTy64, APInt(64, ProfileVersion)), VarName);
   IRLevelVersionVariable->setVisibility(GlobalValue::HiddenVisibility);
   Triple TT(M.getTargetTriple());
   if (TT.supportsCOMDAT()) {
     IRLevelVersionVariable->setLinkage(GlobalValue::ExternalLinkage);
     IRLevelVersionVariable->setComdat(M.getOrInsertComdat(VarName));
static void instrumentOneFunc(
   }
 
   std::vector<BasicBlock *> InstrumentBBs;
   FuncInfo.getInstrumentBBs(InstrumentBBs);
   unsigned NumCounters =
       InstrumentBBs.size() + FuncInfo.SIVisitor.getNumOfSelectInsts();
 
   uint32_t I = 0;
+  if (PGOTemporalInstrumentation) {
+    NumCounters += PGOBlockCoverage ? 8 : 1;
+    auto &EntryBB = F.getEntryBlock();
+    IRBuilder<> Builder(&EntryBB, EntryBB.getFirstInsertionPt());
+    // llvm.instrprof.timestamp(i8* <name>, i64 <hash>, i32 <num-counters>,
+    //                          i32 <index>)
+    Builder.CreateCall(
+        Intrinsic::getDeclaration(M, Intrinsic::instrprof_timestamp),
+        {Name, CFGHash, Builder.getInt32(NumCounters), Builder.getInt32(I)});
+    I += PGOBlockCoverage ? 8 : 1;
+  }
+
   for (auto *InstrBB : InstrumentBBs) {
     IRBuilder<> Builder(InstrBB, InstrBB->getFirstInsertionPt());
     assert(Builder.GetInsertPoint() != InstrBB->end() &&
            "Cannot get the Instrumentation point");
     // llvm.instrprof.increment(i8* <name>, i64 <hash>, i32 <num-counters>,
     //                          i32 <index>)
     Builder.CreateCall(
         Intrinsic::getDeclaration(M, PGOBlockCoverage

llvm/test/Instrumentation/InstrProfiling/timestamp-coverage.ll

+; RUN: opt < %s -passes=instrprof -S | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnu"
+
+@__profn_foo = private constant [3 x i8] c"foo"
+; CHECK: @__profc_foo = private global [9 x i8] c"\FF\FF\FF\FF\FF\FF\FF\FF\FF", section "__llvm_prf_cnts", comdat, align 8
+
+define void @_Z3foov() {
+  call void @llvm.instrprof.timestamp(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_foo, i32 0, i32 0), i64 12345678, i32 9, i32 0)
+  ; CHECK: call void @__llvm_profile_set_timestamp(ptr @__profc_foo)
+  call void @llvm.instrprof.cover(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_foo, i32 0, i32 0), i64 12345678, i32 9, i32 8)
+  ret void
+}
+
+declare void @llvm.instrprof.timestamp(i8*, i64, i32, i32)
+declare void @llvm.instrprof.cover(i8*, i64, i32, i32)

llvm/test/Instrumentation/InstrProfiling/timestamp.ll

+; RUN: opt < %s -passes=instrprof -S | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnu"
+
+@__profn_foo = private constant [3 x i8] c"foo"
+; CHECK: @__profc_foo = private global [2 x i64] zeroinitializer, section "__llvm_prf_cnts", comdat, align 8
+
+define void @_Z3foov() {
+  call void @llvm.instrprof.timestamp(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_foo, i32 0, i32 0), i64 12345678, i32 2, i32 0)
+  ; CHECK: call void @__llvm_profile_set_timestamp(ptr @__profc_foo)
+  call void @llvm.instrprof.increment(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @__profn_foo, i32 0, i32 0), i64 12345678, i32 2, i32 1)
+  ret void
+}
+
+declare void @llvm.instrprof.timestamp(i8*, i64, i32, i32)
+declare void @llvm.instrprof.increment(i8*, i64, i32, i32)

llvm/test/Transforms/PGOProfile/timestamp.ll

+; RUN: opt < %s -passes=pgo-instr-gen -pgo-temporal-instrumentation -S | FileCheck %s
+; RUN: opt < %s -passes=pgo-instr-gen -pgo-temporal-instrumentation -pgo-block-coverage -S | FileCheck %s
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @foo() {
+entry:
+  ; CHECK: call void @llvm.instrprof.timestamp({{.*}})
+  ret void
+}
+
+; CHECK: declare void @llvm.instrprof.timestamp(

llvm/test/tools/llvm-profdata/merge-traces.proftext

+# RUN: llvm-profdata merge --trace-reservoir-size=2 %s -o %t.profdata
+# RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --check-prefixes=SAMPLE1,SEEN1
+# RUN: llvm-profdata merge --trace-reservoir-size=2 %s %t.profdata -o %t.profdata
+# RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --check-prefixes=SAMPLE2,SEEN2
+# RUN: llvm-profdata merge --trace-reservoir-size=2 %s %t.profdata -o %t.profdata
+# RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --check-prefixes=SAMPLE2,SEEN3
+# RUN: llvm-profdata merge --trace-reservoir-size=2 %s %t.profdata -o %t.profdata
+# RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --check-prefixes=SAMPLE2,SEEN4
+
+# SEEN1: Function Traces (samples=1 seen=1):
+# SEEN2: Function Traces (samples=2 seen=2):
+# SEEN3: Function Traces (samples=2 seen=3):
+# SEEN4: Function Traces (samples=2 seen=4):
+# SAMPLE1: Trace 0 (count=3):
+# SAMPLE1:   a
+# SAMPLE1:   b
+# SAMPLE1:   c
+# SAMPLE2: Trace 1 (count=3):
+# SAMPLE2:   a
+# SAMPLE2:   b
+# SAMPLE2:   c
+
+# Header
+:ir
+:traces
+# Num Traces
+1
+# Trace Stream Size:
+1
+a, b, c
+
+
+a
+# Func Hash:
+0x1234
+# Num Counters:
+1
+# Counter Values:
+101
+
+b
+0x5678
+1
+202
+
+c
+0xabcd
+1
+303

llvm/test/tools/llvm-profdata/read-traces.proftext

+# RUN: llvm-profdata merge -text %s -o %t.1.proftext
+# RUN: llvm-profdata merge -binary %t.1.proftext -o %t.2.profdata
+# RUN: llvm-profdata merge -text %t.2.profdata -o %t.3.proftext
+# RUN: diff %t.1.proftext %t.3.proftext
+
+# RUN: llvm-profdata show --function-traces %t.1.proftext | FileCheck %s
+
+# CHECK: Function Traces (samples=3 seen=3):
+# CHECK: Trace 0 (count=3):
+# CHECK:   foo
+# CHECK:   bar
+# CHECK:   goo
+# CHECK: Trace 1 (count=3):
+# CHECK:   foo
+# CHECK:   goo
+# CHECK:   bar
+# CHECK: Trace 2 (count=1):
+# CHECK:   goo
+
+:ir
+:traces
+# Num Traces:
+3
+# Trace Stream Size:
+3
+foo, bar, goo
+foo,goo,bar,
+goo
+
+foo
+# Func Hash:
+0x1234
+# Num Counters:
+1
+# Counter Values:
+101
+
+bar
+0x5678
+1
+202
+
+goo
+0xabcd
+1
+303

llvm/test/tools/llvm-profdata/trace-limit.proftext

+# RUN: llvm-profdata merge --max-trace-length=0 %s -o %t.profdata
+# RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --check-prefix=NONE
+
+# RUN: llvm-profdata merge --max-trace-length=2 %s -o %t.profdata
+# RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --check-prefixes=CHECK,SOME
+
+# RUN: llvm-profdata merge --max-trace-length=1000 %s -o %t.profdata
+# RUN: llvm-profdata show --function-traces %t.profdata | FileCheck %s --check-prefixes=CHECK,ALL
+
+# NONE: Function Traces (samples=0 seen=0):
+# CHECK: Function Traces (samples=1 seen=1):
+# SOME:   Trace 0 (count=2):
+# ALL:    Trace 0 (count=3):
+
+# Header
+:ir
+:traces
+# Num Traces
+1
+# Trace Stream Size:
+1
+a, b, c
+
+
+a
+# Func Hash:
+0x1234
+# Num Counters:
+1
+# Counter Values:
+101
+
+b
+0x5678
+1
+202
+
+c
+0xabcd
+1
+303

llvm/tools/llvm-profdata/llvm-profdata.cpp

 struct WriterContext {
   std::mutex Lock;
   InstrProfWriter Writer;
   std::vector<std::pair<Error, std::string>> Errors;
   std::mutex &ErrLock;
   SmallSet<instrprof_error, 4> &WriterErrorCodes;
 
   WriterContext(bool IsSparse, std::mutex &ErrLock,
-                SmallSet<instrprof_error, 4> &WriterErrorCodes)
-      : Writer(IsSparse), ErrLock(ErrLock), WriterErrorCodes(WriterErrorCodes) {
-  }
+                SmallSet<instrprof_error, 4> &WriterErrorCodes,
+                uint64_t TraceReservoirSize = 0, uint64_t MaxTraceLength = 0)
+      : Writer(IsSparse, TraceReservoirSize, MaxTraceLength), ErrLock(ErrLock),
+        WriterErrorCodes(WriterErrorCodes) {}
 };
 
 /// Computer the overlap b/w profile BaseFilename and TestFileName,
 /// and store the program level result to Overlap.
 static void overlapInput(const std::string &BaseFilename,
                          const std::string &TestFilename, WriterContext *WC,
                          OverlapStats &Overlap,
                          const OverlapFuncFilters &FuncFilter,
for (const auto &I : FunctionProfileData) {
       WC->Writer.addMemProfRecord(/*Id=*/I.first, /*Record=*/I.second);
     }
     return;
   }
 
   auto FS = vfs::getRealFileSystem();
   auto ReaderOrErr = InstrProfReader::create(Input.Filename, *FS, Correlator);
   if (Error E = ReaderOrErr.takeError()) {
-    // Skip the empty profiles by returning sliently.
+    // Skip the empty profiles by returning silently.
     instrprof_error IPE = InstrProfError::take(std::move(E));
     if (IPE != instrprof_error::empty_raw_profile)
       WC->Errors.emplace_back(make_error<InstrProfError>(IPE), Filename);
     return;
   }
 
   auto Reader = std::move(ReaderOrErr.get());
   if (Error E = WC->Writer.mergeProfileKind(Reader->getProfileKind())) {
WC->Writer.addRecord(std::move(I), Input.Weight, [&](Error E) {
       instrprof_error IPE = InstrProfError::take(std::move(E));
       std::unique_lock<std::mutex> ErrGuard{WC->ErrLock};
       bool firstTime = WC->WriterErrorCodes.insert(IPE).second;
       handleMergeWriterError(make_error<InstrProfError>(IPE), Input.Filename,
                              FuncName, firstTime);
     });
   }
 
+  if (Reader->isTemporalProfile()) {
+    auto &Traces = Reader->getFunctionTraces();
+    if (!Traces.empty())
+      WC->Writer.addFunctionTraces(Traces, Reader->getTraceStreamSize());
+  }
   if (Reader->hasError()) {
     if (Error E = Reader->getError())
       WC->Errors.emplace_back(std::move(E), Filename);
   }
 
   std::vector<llvm::object::BuildID> BinaryIds;
   if (Error E = Reader->readBinaryIds(BinaryIds))
     WC->Errors.emplace_back(std::move(E), Filename);
static void writeInstrProfile(StringRef OutputFilename,
   } else {
     if (Output.is_displayed())
       exitWithError("cannot write a non-text format profile to the terminal");
     if (Error E = Writer.write(Output))
       warn(std::move(E));
   }
 }
 
-static void mergeInstrProfile(const WeightedFileVector &Inputs,
-                              StringRef DebugInfoFilename,
-                              SymbolRemapper *Remapper,
-                              StringRef OutputFilename,
-                              ProfileFormat OutputFormat, bool OutputSparse,
-                              unsigned NumThreads, FailureMode FailMode,
-                              const StringRef ProfiledBinary) {
+static void
+mergeInstrProfile(const WeightedFileVector &Inputs, StringRef DebugInfoFilename,
+                  SymbolRemapper *Remapper, StringRef OutputFilename,
+                  ProfileFormat OutputFormat, uint64_t TraceReservoirSize,
+                  uint64_t MaxTraceLength, bool OutputSparse,
   if (OutputFormat != PF_Binary && OutputFormat != PF_Compact_Binary &&
       OutputFormat != PF_Ext_Binary && OutputFormat != PF_Text)
     exitWithError("unknown format is specified");
 
   std::unique_ptr<InstrProfCorrelator> Correlator;
   if (!DebugInfoFilename.empty()) {
     if (auto Err =
             InstrProfCorrelator::get(DebugInfoFilename).moveInto(Correlator))
mergeInstrProfile(const WeightedFileVector &Inputs, StringRef DebugInfoFilename,
   if (NumThreads == 0)
     NumThreads = std::min(hardware_concurrency().compute_thread_count(),
                           unsigned((Inputs.size() + 1) / 2));
 
   // Initialize the writer contexts.
   SmallVector<std::unique_ptr<WriterContext>, 4> Contexts;
   for (unsigned I = 0; I < NumThreads; ++I)
     Contexts.emplace_back(std::make_unique<WriterContext>(
-        OutputSparse, ErrorLock, WriterErrorCodes));
+        OutputSparse, ErrorLock, WriterErrorCodes, TraceReservoirSize,
+        MaxTraceLength));
 
   if (NumThreads == 1) {
     for (const auto &Input : Inputs)
       loadInput(Input, Remapper, Correlator.get(), ProfiledBinary,
                 Contexts[0].get());
   } else {
     ThreadPool Pool(hardware_concurrency(NumThreads));
 
cl::opt<std::string> DebugInfoFilename(
       cl::desc("Use the provided debug info to correlate the raw profile."));
   cl::opt<std::string> ProfiledBinary(
       "profiled-binary", cl::init(""),
       cl::desc("Path to binary from which the profile was collected."));
   cl::opt<bool> DropProfileSymbolList(
       "drop-profile-symbol-list", cl::init(false), cl::Hidden,
       cl::desc("Drop the profile symbol list when merging AutoFDO profiles "
                "(only meaningful for -sample)"));
+  // WARNING: This reservoir size value is propagated to any input indexed
+  // profiles for simplicity. Changing this value between invocations could
+  // result in sample bias.
+  cl::opt<uint64_t> TraceReservoirSize(
+      "trace-reservoir-size", cl::init(100),
+      cl::desc("The maximum number of stored traces (default: 100)"));
+  cl::opt<uint64_t> MaxTraceLength(
+      "max-trace-length", cl::init(10000),
+      cl::desc("The maximum length of a single trace (default: 10000)"));
 
   cl::ParseCommandLineOptions(argc, argv, "LLVM profile data merger\n");
 
   WeightedFileVector WeightedInputs;
   for (StringRef Filename : InputFilenames)
     addWeightedInput(WeightedInputs, {std::string(Filename), 1});
   for (StringRef WeightedFilename : WeightedInputFilenames)
     addWeightedInput(WeightedInputs, parseWeightedFile(WeightedFilename));
if (!SupplInstrWithSample.empty()) {
     supplementInstrProfile(WeightedInputs, SupplInstrWithSample, OutputFilename,
                            OutputFormat, OutputSparse, SupplMinSizeThreshold,
                            ZeroCounterThreshold, InstrProfColdThreshold);
     return 0;
   }
 
   if (ProfileKind == instr)
     mergeInstrProfile(WeightedInputs, DebugInfoFilename, Remapper.get(),
-                      OutputFilename, OutputFormat, OutputSparse, NumThreads,
-                      FailureMode, ProfiledBinary);
+                      OutputFilename, OutputFormat, TraceReservoirSize,
+                      MaxTraceLength, OutputSparse, NumThreads, FailureMode,
+                      ProfiledBinary);
   else
     mergeSampleProfile(WeightedInputs, Remapper.get(), OutputFilename,
                        OutputFormat, ProfileSymbolListFile, CompressAllSections,
                        UseMD5, GenPartialProfile, ProfileLayout,
                        SampleMergeColdContext, SampleTrimColdContext,
                        SampleColdContextFrameDepth, FailureMode,
                        DropProfileSymbolList, OutputSizeLimit);
   return 0;

 static int showInstrProfile(const std::string &Filename, bool ShowCounts,
                             uint32_t TopN, bool ShowIndirectCallTargets,
                             bool ShowMemOPSizes, bool ShowDetailedSummary,
                             std::vector<uint32_t> DetailedSummaryCutoffs,
                             bool ShowAllFunctions, bool ShowCS,
                             uint64_t ValueCutoff, bool OnlyListBelow,
                             const std::string &ShowFunction, bool TextFormat,
                             bool ShowBinaryIds, bool ShowCovered,
-                            bool ShowProfileVersion, ShowFormat SFormat,
-                            raw_fd_ostream &OS) {
+                            bool ShowProfileVersion, bool ShowFunctionTraces,
+                            ShowFormat SFormat, raw_fd_ostream &OS) {
   if (SFormat == ShowFormat::Json)
     exitWithError("JSON output is not supported for instr profiles");
   if (SFormat == ShowFormat::Yaml)
     exitWithError("YAML output is not supported for instr profiles");
   auto FS = vfs::getRealFileSystem();
   auto ReaderOrErr = InstrProfReader::create(Filename, *FS);
   std::vector<uint32_t> Cutoffs = std::move(DetailedSummaryCutoffs);
   if (ShowDetailedSummary && Cutoffs.empty()) {
static int showInstrProfile(const std::string &Filename, bool ShowCounts,
   }
 
   if (ShowBinaryIds)
     if (Error E = Reader->printBinaryIds(OS))
       exitWithError(std::move(E), Filename);
 
   if (ShowProfileVersion)
     OS << "Profile version: " << Reader->getVersion() << "\n";
+
+  if (ShowFunctionTraces) {
+    auto &Traces = Reader->getFunctionTraces();
+    OS << "Function Traces (samples=" << Traces.size()
+       << " seen=" << Reader->getTraceStreamSize() << "):\n";
+    for (unsigned i = 0; i < Traces.size(); i++) {
+      OS << "  Trace " << i << " (count=" << Traces[i].size() << "):\n";
+      for (auto &NameRef : Traces[i])
+        OS << "    " << Reader->getSymtab().getFuncName(NameRef) << "\n";
+    }
+  }
+
   return 0;
 }
 
 static void showSectionInfo(sampleprof::SampleProfileReader *Reader,
                             raw_fd_ostream &OS) {
   if (!Reader->dumpSectionInfo(OS)) {
     WithColor::warning() << "-show-sec-info-only is only supported for "
                          << "sample profile in extbinary format and is "
cl::opt<bool> ShowProfileSymbolList(
       cl::desc("Show profile symbol list if it exists in the profile. "));
   cl::opt<bool> ShowSectionInfoOnly(
       "show-sec-info-only", cl::init(false),
       cl::desc("Show the information of each section in the sample profile. "
                "The flag is only usable when the sample profile is in "
                "extbinary format"));
   cl::opt<bool> ShowBinaryIds("binary-ids", cl::init(false),
                               cl::desc("Show binary ids in the profile. "));
+  cl::opt<bool> ShowFunctionTraces(
+      "function-traces", cl::init(false),
+      cl::desc("Show function traces in the profile."));
   cl::opt<std::string> DebugInfoFilename(
       "debug-info", cl::init(""),
       cl::desc("Read and extract profile metadata from debug info and show "
                "the functions it found."));
   cl::opt<bool> ShowCovered(
       "covered", cl::init(false),
       cl::desc("Show only the functions that have been executed."));
   cl::opt<std::string> ProfiledBinary(
if (!DebugInfoFilename.empty())
     return showDebugInfoCorrelation(DebugInfoFilename, ShowDetailedSummary,
                                     ShowProfileSymbolList, SFormat, OS);
 
   if (ProfileKind == instr)
     return showInstrProfile(
         Filename, ShowCounts, TopNFunctions, ShowIndirectCallTargets,
         ShowMemOPSizes, ShowDetailedSummary, DetailedSummaryCutoffs,
         ShowAllFunctions, ShowCS, ValueCutoff, OnlyListBelow, ShowFunction,
-        TextFormat, ShowBinaryIds, ShowCovered, ShowProfileVersion, SFormat,
-        OS);
+        TextFormat, ShowBinaryIds, ShowCovered, ShowProfileVersion,
+        ShowFunctionTraces, SFormat, OS);
   if (ProfileKind == sample)
     return showSampleProfile(Filename, ShowCounts, TopNFunctions,
                              ShowAllFunctions, ShowDetailedSummary,
                              ShowFunction, ShowProfileSymbolList,
                              ShowSectionInfoOnly, ShowHotFuncList, SFormat, OS);
   return showMemProfProfile(Filename, ProfiledBinary, SFormat, OS);
 }
 

llvm/unittests/ProfileData/InstrProfTest.cpp

 #include "llvm/Support/Compression.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Testing/Support/Error.h"
 #include "llvm/Testing/Support/SupportHelpers.h"
 #include "gtest/gtest.h"
 #include <cstdarg>
 
 using namespace llvm;
+using ::testing::IsSubsetOf;
+using ::testing::SizeIs;
+using ::testing::UnorderedElementsAre;
 
 [[nodiscard]] static ::testing::AssertionResult
 ErrorEquals(instrprof_error Expected, Error E) {
   instrprof_error Found;
   std::string FoundMsg;
   handleAllErrors(std::move(E), [&](const InstrProfError &IPE) {
     Found = IPE.get();
     FoundMsg = IPE.message();
TEST_F(InstrProfTest, test_writer_merge) {
 
   R = Reader->getInstrProfRecord("func2", 0x1234);
   EXPECT_THAT_ERROR(R.takeError(), Succeeded());
   ASSERT_EQ(2U, R->Counts.size());
   ASSERT_EQ(0U, R->Counts[0]);
   ASSERT_EQ(0U, R->Counts[1]);
 }
 
+TEST_F(InstrProfTest, test_merge_traces_truncated) {
+  uint64_t TraceReservoirSize = 10;
+  uint64_t MaxTraceLength = 2;
+  InstrProfWriter Writer(false, TraceReservoirSize, MaxTraceLength);
+  ASSERT_THAT_ERROR(Writer.mergeProfileKind(InstrProfKind::TemporalProfile),
+                    Succeeded());
+
+  auto LargeTrace = {IndexedInstrProf::ComputeHash("foo"),
+                     IndexedInstrProf::ComputeHash("bar"),
+                     IndexedInstrProf::ComputeHash("goo")};
+  auto SmallTrace = {IndexedInstrProf::ComputeHash("foo"),
+                     IndexedInstrProf::ComputeHash("bar")};
+
+  Writer.addFunctionTraces({LargeTrace, SmallTrace}, 2);
+
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile));
+
+  ASSERT_TRUE(Reader->isTemporalProfile());
+  EXPECT_EQ(Reader->getTraceStreamSize(), 2);
+  EXPECT_THAT(Reader->getFunctionTraces(),
+              UnorderedElementsAre(SmallTrace, SmallTrace));
+}
+
+TEST_F(InstrProfTest, test_merge_traces_from_writer) {
+  uint64_t TraceReservoirSize = 10;
+  uint64_t MaxTraceLength = 10;
+  InstrProfWriter Writer(false, TraceReservoirSize, MaxTraceLength);
+  InstrProfWriter Writer2(false, TraceReservoirSize, MaxTraceLength);
+  ASSERT_THAT_ERROR(Writer.mergeProfileKind(InstrProfKind::TemporalProfile),
+                    Succeeded());
+  ASSERT_THAT_ERROR(Writer2.mergeProfileKind(InstrProfKind::TemporalProfile),
+                    Succeeded());
+
+  auto FooTrace = {IndexedInstrProf::ComputeHash("foo")};
+  auto BarTrace = {IndexedInstrProf::ComputeHash("bar")};
+
+  Writer.addFunctionTraces({FooTrace}, 1);
+  Writer2.addFunctionTraces({BarTrace}, 1);
+  Writer.mergeRecordsFromWriter(std::move(Writer2), Err);
+
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile));
+
+  ASSERT_TRUE(Reader->isTemporalProfile());
+  EXPECT_EQ(Reader->getTraceStreamSize(), 2);
+  EXPECT_THAT(Reader->getFunctionTraces(),
+              UnorderedElementsAre(FooTrace, BarTrace));
+}
+
+TEST_F(InstrProfTest, test_merge_traces_sampled) {
+  uint64_t TraceReservoirSize = 3;
+  uint64_t MaxTraceLength = 10;
+  InstrProfWriter Writer(false, TraceReservoirSize, MaxTraceLength);
+  ASSERT_THAT_ERROR(Writer.mergeProfileKind(InstrProfKind::TemporalProfile),
+                    Succeeded());
+
+  auto FooTrace = {IndexedInstrProf::ComputeHash("foo")};
+  auto BarTrace = {IndexedInstrProf::ComputeHash("bar")};
+  auto GooTrace = {IndexedInstrProf::ComputeHash("Goo")};
+
+  // Add some sampled traces
+  Writer.addFunctionTraces({FooTrace, BarTrace, GooTrace}, 5);
+  // Add some unsampled traces
+  Writer.addFunctionTraces({BarTrace, GooTrace}, 2);
+  Writer.addFunctionTraces({FooTrace}, 1);
+
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile));
+
+  ASSERT_TRUE(Reader->isTemporalProfile());
+  EXPECT_EQ(Reader->getTraceStreamSize(), 8);
+  // Check that we have a subset of all the traces we added
+  EXPECT_THAT(Reader->getFunctionTraces(), SizeIs(TraceReservoirSize));
+  EXPECT_THAT(
+      Reader->getFunctionTraces(),
+      IsSubsetOf({FooTrace, BarTrace, GooTrace, BarTrace, GooTrace, FooTrace}));
+}
+
 using ::llvm::memprof::IndexedMemProfRecord;
 using ::llvm::memprof::MemInfoBlock;
 using FrameIdMapTy =
     llvm::DenseMap<::llvm::memprof::FrameId, ::llvm::memprof::Frame>;
 
 static FrameIdMapTy getFrameMapping() {
   FrameIdMapTy Mapping;
   Mapping.insert({0, {0x123, 1, 2, false}});
TEST_P(MaybeSparseInstrProfTest, annotate_vp_data) {
   ASSERT_TRUE(Res);
   ASSERT_EQ(1U, N);
   ASSERT_EQ(21U, T);
 
   Res = getValueProfDataFromInst(*Inst2, IPVK_IndirectCallTarget, 5, ValueData,
                                  N, T);
   ASSERT_FALSE(Res);
 
-  // Remove the MD_prof metadata 
+  // Remove the MD_prof metadata
   Inst->setMetadata(LLVMContext::MD_prof, 0);
   // Annotate 5 records this time.
   annotateValueSite(*M, *Inst, R.get(), IPVK_IndirectCallTarget, 0, 5);
   Res = getValueProfDataFromInst(*Inst, IPVK_IndirectCallTarget, 5,
                                       ValueData, N, T);
   ASSERT_TRUE(Res);
   ASSERT_EQ(5U, N);
   ASSERT_EQ(21U, T);
   ASSERT_EQ(6000U, ValueData[0].Value);
   ASSERT_EQ(6U, ValueData[0].Count);
   ASSERT_EQ(5000U, ValueData[1].Value);
   ASSERT_EQ(5U, ValueData[1].Count);
   ASSERT_EQ(4000U, ValueData[2].Value);
   ASSERT_EQ(4U, ValueData[2].Count);
   ASSERT_EQ(3000U, ValueData[3].Value);
   ASSERT_EQ(3U, ValueData[3].Count);
   ASSERT_EQ(2000U, ValueData[4].Value);
   ASSERT_EQ(2U, ValueData[4].Count);
 
-  // Remove the MD_prof metadata 
+  // Remove the MD_prof metadata
   Inst->setMetadata(LLVMContext::MD_prof, 0);
   // Annotate with 4 records.
   InstrProfValueData VD0Sorted[] = {{1000, 6}, {2000, 5}, {3000, 4}, {4000, 3},
                               {5000, 2}, {6000, 1}};
   annotateValueSite(*M, *Inst, ArrayRef(VD0Sorted).slice(2), 10,
                     IPVK_IndirectCallTarget, 5);
   Res = getValueProfDataFromInst(*Inst, IPVK_IndirectCallTarget, 5,
                                       ValueData, N, T);