[MemProf] Use profiled lifetime access density directly

[tejohnson]

Summary

Now that the runtime tracks the lifetime access density directly, we can
use that directly in the threshold checks instead of less accurately
computing from other statistics.

[snehasish]

lgtm

llvm/lib/Analysis/MemoryProfileInfo.cpp

22

AccessesPerBytePerSec seems to be synonymous to LifetimeAccessDensity which we use elsewhere in this patch. Can we use the same (latter) phrase for this option too? E.g MemprofLifetimeAccessDensityColdThreshold

Also update the options and description if you choose to adopt this suggestion.

llvm/unittests/Analysis/MemoryProfileInfoTest.cpp

74

nit: const

[tejohnson]

Also noticed the comments in the new tests for MemProfContextDisambiguation refer to the old version of the lifetime threshold option, updating those too.

[tejohnson]

Address comments

llvm/include/llvm/Analysis/MemoryProfileInfo.h

 #include "llvm/IR/Module.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
 #include <map>
 
 namespace llvm {
 namespace memprof {
 
 /// Return the allocation type for a given set of memory profile values.
-AllocationType getAllocType(uint64_t MaxAccessCount, uint64_t MinSize,
-                            uint64_t MinLifetime);
+AllocationType getAllocType(uint64_t TotalLifetimeAccessDensity,
+                            uint64_t AllocCount, uint64_t TotalLifetime);
 
 /// Build callstack metadata from the provided list of call stack ids. Returns
 /// the resulting metadata node.
 MDNode *buildCallstackMetadata(ArrayRef<uint64_t> CallStack, LLVMContext &Ctx);
 
 /// Returns the stack node from an MIB metadata node.
 MDNode *getMIBStackNode(const MDNode *MIB);
 

llvm/lib/Analysis/MemoryProfileInfo.cpp

 #include "llvm/Analysis/MemoryProfileInfo.h"
 #include "llvm/Support/CommandLine.h"
 
 using namespace llvm;
 using namespace llvm::memprof;
 
 #define DEBUG_TYPE "memory-profile-info"
 
-// Upper bound on accesses per byte for marking an allocation cold.
-cl::opt<float> MemProfAccessesPerByteColdThreshold(
-    "memprof-accesses-per-byte-cold-threshold", cl::init(10.0), cl::Hidden,
-    cl::desc("The threshold the accesses per byte must be under to consider "
-             "an allocation cold"));
+// Upper bound on lifetime access density (accesses per byte per lifetime sec)
+// for marking an allocation cold.
+cl::opt<float> MemProfLifetimeAccessDensityColdThreshold(
+    "memprof-lifetime-access-density-cold-threshold", cl::init(0.05),
+    cl::Hidden,
+    cl::desc("The threshold the lifetime access density (accesses per byte per "
+             "lifetime sec) must be under to consider an allocation cold"));
 
 // Lower bound on lifetime to mark an allocation cold (in addition to accesses
-// per byte above). This is to avoid pessimizing short lived objects.
-cl::opt<unsigned> MemProfMinLifetimeColdThreshold(
-    "memprof-min-lifetime-cold-threshold", cl::init(200), cl::Hidden,
-    cl::desc("The minimum lifetime (s) for an allocation to be considered "
+// per byte per sec above). This is to avoid pessimizing short lived objects.
+cl::opt<unsigned> MemProfAveLifetimeColdThreshold(
+    "memprof-ave-lifetime-cold-threshold", cl::init(200), cl::Hidden,
+    cl::desc("The average lifetime (s) for an allocation to be considered "
              "cold"));
 
-AllocationType llvm::memprof::getAllocType(uint64_t MaxAccessCount,
-                                           uint64_t MinSize,
-                                           uint64_t MinLifetime) {
-  if (((float)MaxAccessCount) / MinSize < MemProfAccessesPerByteColdThreshold &&
-      // MinLifetime is expected to be in ms, so convert the threshold to ms.
-      MinLifetime >= MemProfMinLifetimeColdThreshold * 1000)
+AllocationType llvm::memprof::getAllocType(uint64_t TotalLifetimeAccessDensity,
+                                           uint64_t AllocCount,
+                                           uint64_t TotalLifetime) {
+  // The access densities are multiplied by 100 to hold 2 decimal places of
+  // precision, so need to divide by 100.
+  if (((float)TotalLifetimeAccessDensity) / AllocCount / 100 <
+          MemProfLifetimeAccessDensityColdThreshold
+      // Lifetime is expected to be in ms, so convert the threshold to ms.
+      && ((float)TotalLifetime) / AllocCount >=
+             MemProfAveLifetimeColdThreshold * 1000)
     return AllocationType::Cold;
   return AllocationType::NotCold;
 }
 
 MDNode *llvm::memprof::buildCallstackMetadata(ArrayRef<uint64_t> CallStack,
                                               LLVMContext &Ctx) {
   std::vector<Metadata *> StackVals;
   for (auto Id : CallStack) {

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

static uint64_t computeStackId(const memprof::Frame &Frame) {
   return computeStackId(Frame.Function, Frame.LineOffset, Frame.Column);
 }
 
 static void addCallStack(CallStackTrie &AllocTrie,
                          const AllocationInfo *AllocInfo) {
   SmallVector<uint64_t> StackIds;
   for (const auto &StackFrame : AllocInfo->CallStack)
     StackIds.push_back(computeStackId(StackFrame));
-  auto AllocType = getAllocType(AllocInfo->Info.getMaxAccessCount(),
-                                AllocInfo->Info.getMinSize(),
-                                AllocInfo->Info.getMinLifetime());
+  auto AllocType = getAllocType(AllocInfo->Info.getTotalLifetimeAccessDensity(),
+                                AllocInfo->Info.getAllocCount(),
+                                AllocInfo->Info.getTotalLifetime());
   AllocTrie.addCallStack(AllocType, StackIds);
 }
 
 // Helper to compare the InlinedCallStack computed from an instruction's debug
 // info to a list of Frames from profile data (either the allocation data or a
 // callsite). For callsites, the StartIndex to use in the Frame array may be
 // non-zero.
 static bool

llvm/test/ThinLTO/X86/memprof-basic.ll

 ;;   memset(x, 0, 10);
 ;;   memset(y, 0, 10);
 ;;   delete[] x;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The IR was then reduced using llvm-reduce with the expected FileCheck input.
 
 ; RUN: opt -thinlto-bc %s >%t.o
 ; RUN: llvm-lto2 run %t.o -enable-memprof-context-disambiguation \
 ; RUN:  -r=%t.o,main,plx \
 ; RUN:  -r=%t.o,_ZdaPv, \

llvm/test/ThinLTO/X86/memprof-duplicate-context-ids.ll

 ;;   memset(z, 0, 10);
 ;;   delete[] z;
 ;;   sleep(10);
 ;;   delete[] x;
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The code below was created by forcing inlining of C into both B and E.
 ;; Since both allocation contexts via C are cold, the matched memprof
 ;; metadata has the context pruned above C's callsite. This requires
 ;; matching the stack node for C to callsites where it was inlined (i.e.
 ;; the callsites in B and E that have callsite metadata that includes C's).
 ;; It also requires duplication of that node in the graph as well as the

llvm/test/ThinLTO/X86/memprof-duplicate-context-ids2.ll

 ;;   delete[] e;
 ;;   sleep(10);
 ;;   delete[] a1;
 ;;   delete[] a2;
 ;;   delete[] f;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The code below was created by forcing inlining of A into its callers,
 ;; without any other inlining or optimizations. Since both allocation contexts
 ;; via A for each allocation in D have the same allocation type (cold via
 ;; A1 and A2 for the first new in D, and non-cold via A3 and A4 for the second
 ;; new in D, the contexts for those respective allocations are pruned above A.
 ;; The allocations via E and F are to ensure we don't prune above B.

llvm/test/ThinLTO/X86/memprof-indirectcall.ll

 ;;   delete[] r;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   delete[] z;
 ;;   delete[] s;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; Compiled without optimization to prevent inlining and devirtualization.
 ;;
 ;; The IR was then reduced using llvm-reduce with the expected FileCheck input.
 
 ; RUN: opt -thinlto-bc %s >%t.o
 ; RUN: llvm-lto2 run %t.o -enable-memprof-context-disambiguation \

llvm/test/ThinLTO/X86/memprof-inlined.ll

 ;;   memset(x, 0, 10);
 ;;   memset(y, 0, 10);
 ;;   delete[] x;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The code below was created by forcing inlining of baz into foo, and
 ;; bar into baz. Due to the inlining of bar we will initially have two
 ;; allocation nodes in the graph. This tests that we correctly match
 ;; foo (with baz inlined) onto the graph nodes first, and generate a new
 ;; fused node for it. We should then not match baz (with bar inlined) as that
 ;; is not reached by the MIB contexts (since all calls from main will look

llvm/test/ThinLTO/X86/memprof-inlined2.ll

 ;;   memset(x, 0, 10);
 ;;   memset(y, 0, 10);
 ;;   delete[] x;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; Both foo and baz are inlined into main, at both foo callsites.
 ;; We should update the graph for new fused nodes for both of those inlined
 ;; callsites to bar.
 ;;
 ;; Note that baz and bar are both dead due to the inlining, but have been left
 ;; in the input IR to ensure that the MIB call chain is matched to the longer

llvm/test/Transforms/MemProfContextDisambiguation/basic.ll

 ;;   memset(x, 0, 10);
 ;;   memset(y, 0, 10);
 ;;   delete[] x;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The IR was then reduced using llvm-reduce with the expected FileCheck input.
 
 ; RUN: opt -passes=memprof-context-disambiguation \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \
 ; RUN:  -memprof-export-to-dot -memprof-dot-file-path-prefix=%t. \
 ; RUN:  %s -S 2>&1 | FileCheck %s --check-prefix=DUMP

llvm/test/Transforms/MemProfContextDisambiguation/duplicate-context-ids.ll

 ;;   memset(z, 0, 10);
 ;;   delete[] z;
 ;;   sleep(10);
 ;;   delete[] x;
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The code below was created by forcing inlining of C into both B and E.
 ;; Since both allocation contexts via C are cold, the matched memprof
 ;; metadata has the context pruned above C's callsite. This requires
 ;; matching the stack node for C to callsites where it was inlined (i.e.
 ;; the callsites in B and E that have callsite metadata that includes C's).
 ;; It also requires duplication of that node in the graph as well as the

llvm/test/Transforms/MemProfContextDisambiguation/duplicate-context-ids2.ll

 ;;   delete[] e;
 ;;   sleep(10);
 ;;   delete[] a1;
 ;;   delete[] a2;
 ;;   delete[] f;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The code below was created by forcing inlining of A into its callers,
 ;; without any other inlining or optimizations. Since both allocation contexts
 ;; via A for each allocation in D have the same allocation type (cold via
 ;; A1 and A2 for the first new in D, and non-cold via A3 and A4 for the second
 ;; new in D, the contexts for those respective allocations are pruned above A.
 ;; The allocations via E and F are to ensure we don't prune above B.

llvm/test/Transforms/MemProfContextDisambiguation/indirectcall.ll

 ;;   delete[] r;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   delete[] z;
 ;;   delete[] s;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; Compiled without optimization to prevent inlining and devirtualization.
 ;;
 ;; The IR was then reduced using llvm-reduce with the expected FileCheck input.
 
 ; RUN: opt -passes=memprof-context-disambiguation \
 ; RUN:  -memprof-verify-ccg -memprof-verify-nodes -memprof-dump-ccg \

llvm/test/Transforms/MemProfContextDisambiguation/inlined.ll

 ;;   memset(x, 0, 10);
 ;;   memset(y, 0, 10);
 ;;   delete[] x;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; The code below was created by forcing inlining of baz into foo, and
 ;; bar into baz. Due to the inlining of bar we will initially have two
 ;; allocation nodes in the graph. This tests that we correctly match
 ;; foo (with baz inlined) onto the graph nodes first, and generate a new
 ;; fused node for it. We should then not match baz (with bar inlined) as that
 ;; is not reached by the MIB contexts (since all calls from main will look

llvm/test/Transforms/MemProfContextDisambiguation/inlined2.ll

 ;;   memset(x, 0, 10);
 ;;   memset(y, 0, 10);
 ;;   delete[] x;
 ;;   sleep(10);
 ;;   delete[] y;
 ;;   return 0;
 ;; }
 ;;
-;; Code compiled with -mllvm -memprof-min-lifetime-cold-threshold=5 so that the
+;; Code compiled with -mllvm -memprof-ave-lifetime-cold-threshold=5 so that the
 ;; memory freed after sleep(10) results in cold lifetimes.
 ;;
 ;; Both foo and baz are inlined into main, at both foo callsites.
 ;; We should update the graph for new fused nodes for both of those inlined
 ;; callsites to bar.
 ;;
 ;; Note that baz and bar are both dead due to the inlining, but have been left
 ;; in the input IR to ensure that the MIB call chain is matched to the longer

llvm/unittests/Analysis/MemoryProfileInfoTest.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 #include <cstring>
 
 using namespace llvm;
 using namespace llvm::memprof;
 
-extern cl::opt<float> MemProfAccessesPerByteColdThreshold;
-extern cl::opt<unsigned> MemProfMinLifetimeColdThreshold;
+extern cl::opt<float> MemProfLifetimeAccessDensityColdThreshold;
+extern cl::opt<unsigned> MemProfAveLifetimeColdThreshold;
 
 namespace {
 
 class MemoryProfileInfoTest : public testing::Test {
 protected:
   std::unique_ptr<Module> makeLLVMModule(LLVMContext &C, const char *IR) {
     SMDiagnostic Err;
     std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
CallBase *findCall(Function &F, const char *Name = nullptr) {
     return nullptr;
   }
 };
 
 // Test getAllocType helper.
 // Basic checks on the allocation type for values just above and below
 // the thresholds.
 TEST_F(MemoryProfileInfoTest, GetAllocType) {
-  // Long lived with more accesses per byte than threshold is not cold.
-  EXPECT_EQ(
-      getAllocType(/*MaxAccessCount=*/MemProfAccessesPerByteColdThreshold + 1,
-                   /*MinSize=*/1,
-                   /*MinLifetime=*/MemProfMinLifetimeColdThreshold * 1000 + 1),
+  const uint64_t AllocCount = 2;
+  // To be cold we require that
+  // ((float)TotalLifetimeAccessDensity) / AllocCount / 100 <
+  //    MemProfLifetimeAccessDensityColdThreshold
+  // so compute the TotalLifetimeAccessDensity right at the threshold.
+  const uint64_t TotalLifetimeAccessDensityThreshold =
+      (uint64_t)(MemProfLifetimeAccessDensityColdThreshold * AllocCount * 100);
+  // To be cold we require that
+  // ((float)TotalLifetime) / AllocCount >=
+  //    MemProfAveLifetimeColdThreshold * 1000
+  // so compute the TotalLifetime right at the threshold.
+  const uint64_t TotalLifetimeThreshold =
+      MemProfAveLifetimeColdThreshold * AllocCount * 1000;
+
+  // Long lived with more accesses per byte per sec than threshold is not cold.
+  EXPECT_EQ(getAllocType(TotalLifetimeAccessDensityThreshold + 1, AllocCount,
+                         TotalLifetimeThreshold + 1),
             AllocationType::NotCold);
-  // Long lived with less accesses per byte than threshold is cold.
-  EXPECT_EQ(
-      getAllocType(/*MaxAccessCount=*/MemProfAccessesPerByteColdThreshold - 1,
-                   /*MinSize=*/1,
-                   /*MinLifetime=*/MemProfMinLifetimeColdThreshold * 1000 + 1),
+  // Long lived with less accesses per byte per sec than threshold is cold.
+  EXPECT_EQ(getAllocType(TotalLifetimeAccessDensityThreshold - 1, AllocCount,
+                         TotalLifetimeThreshold + 1),
             AllocationType::Cold);
-  // Short lived with more accesses per byte than threshold is not cold.
-  EXPECT_EQ(
-      getAllocType(/*MaxAccessCount=*/MemProfAccessesPerByteColdThreshold + 1,
-                   /*MinSize=*/1,
-                   /*MinLifetime=*/MemProfMinLifetimeColdThreshold * 1000 - 1),
+  // Short lived with more accesses per byte per sec than threshold is not cold.
+  EXPECT_EQ(getAllocType(TotalLifetimeAccessDensityThreshold + 1, AllocCount,
+                         TotalLifetimeThreshold - 1),
             AllocationType::NotCold);
-  // Short lived with less accesses per byte than threshold is not cold.
-  EXPECT_EQ(
-      getAllocType(/*MaxAccessCount=*/MemProfAccessesPerByteColdThreshold - 1,
-                   /*MinSize=*/1,
-                   /*MinLifetime=*/MemProfMinLifetimeColdThreshold * 1000 - 1),
+  // Short lived with less accesses per byte per sec than threshold is not cold.
+  EXPECT_EQ(getAllocType(TotalLifetimeAccessDensityThreshold - 1, AllocCount,
+                         TotalLifetimeThreshold - 1),
             AllocationType::NotCold);
 }
 
 // Test the hasSingleAllocType helper.
 TEST_F(MemoryProfileInfoTest, SingleAllocType) {
   uint8_t NotCold = (uint8_t)AllocationType::NotCold;
   uint8_t Cold = (uint8_t)AllocationType::Cold;
   EXPECT_TRUE(hasSingleAllocType(NotCold));
   EXPECT_TRUE(hasSingleAllocType(Cold));