1//===- MemProfUse.cpp - memory allocation profile use pass --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the MemProfUsePass which reads memory profiling data
10// and uses it to add metadata to instructions to guide profile-guided memory
11// optimization (MemPGO).
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/Instrumentation/MemProfUse.h"
16#include "InstrumentationOptions.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/Analysis/MemoryProfileInfo.h"
22#include "llvm/Analysis/OptimizationRemarkEmitter.h"
23#include "llvm/Analysis/StaticDataProfileInfo.h"
24#include "llvm/Analysis/TargetLibraryInfo.h"
25#include "llvm/IR/DiagnosticInfo.h"
26#include "llvm/IR/Function.h"
27#include "llvm/IR/IntrinsicInst.h"
28#include "llvm/IR/Module.h"
29#include "llvm/ProfileData/DataAccessProf.h"
30#include "llvm/ProfileData/InstrProf.h"
31#include "llvm/ProfileData/InstrProfReader.h"
32#include "llvm/ProfileData/MemProfCommon.h"
33#include "llvm/Support/BLAKE3.h"
34#include "llvm/Support/CommandLine.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/HashBuilder.h"
37#include "llvm/Support/MD5.h"
38#include "llvm/Support/VirtualFileSystem.h"
39#include "llvm/Transforms/Utils/LongestCommonSequence.h"
40#include <map>
41#include <set>
42
43using namespace llvm;
44using namespace llvm::memprof;
45
46#define DEBUG_TYPE "memprof"
47
48namespace llvm {
49extern cl::opt<bool> NoPGOWarnMismatch;
50} // namespace llvm
51
52// Matching statistics
53STATISTIC(NumOfMemProfMissing, "Number of functions without memory profile.");
54STATISTIC(NumOfMemProfMismatch,
55 "Number of functions having mismatched memory profile hash.");
56STATISTIC(NumOfMemProfFunc, "Number of functions having valid memory profile.");
57STATISTIC(NumOfMemProfAllocContextProfiles,
58 "Number of alloc contexts in memory profile.");
59STATISTIC(NumOfMemProfCallSiteProfiles,
60 "Number of callsites in memory profile.");
61STATISTIC(NumOfMemProfMatchedAllocContexts,
62 "Number of matched memory profile alloc contexts.");
63STATISTIC(NumOfMemProfMatchedAllocs,
64 "Number of matched memory profile allocs.");
65STATISTIC(NumOfMemProfMatchedCallSites,
66 "Number of matched memory profile callsites.");
67STATISTIC(NumOfMemProfHotGlobalVars,
68 "Number of global vars annotated with 'hot' section prefix.");
69STATISTIC(NumOfMemProfColdGlobalVars,
70 "Number of global vars annotated with 'unlikely' section prefix.");
71STATISTIC(NumOfMemProfUnknownGlobalVars,
72 "Number of global vars with unknown hotness (no section prefix).");
73STATISTIC(NumOfMemProfExplicitSectionGlobalVars,
74 "Number of global vars with user-specified section (not annotated).");
75
76static void addCallsiteMetadata(Instruction &I,
77 ArrayRef<uint64_t> InlinedCallStack,
78 LLVMContext &Ctx) {
79 I.setMetadata(KindID: LLVMContext::MD_callsite,
80 Node: buildCallstackMetadata(CallStack: InlinedCallStack, Ctx));
81}
82
83static uint64_t computeStackId(GlobalValue::GUID Function, uint32_t LineOffset,
84 uint32_t Column) {
85 llvm::HashBuilder<llvm::TruncatedBLAKE3<8>, llvm::endianness::little>
86 HashBuilder;
87 HashBuilder.add(Args: Function, Args: LineOffset, Args: Column);
88 llvm::BLAKE3Result<8> Hash = HashBuilder.final();
89 uint64_t Id;
90 std::memcpy(dest: &Id, src: Hash.data(), n: sizeof(Hash));
91 return Id;
92}
93
94static uint64_t computeStackId(const memprof::Frame &Frame) {
95 return computeStackId(Function: Frame.Function, LineOffset: Frame.LineOffset, Column: Frame.Column);
96}
97
98// Compute the line offset of a debug location relative to the start line of
99// its enclosing subprogram, clamped at 0 as the profile reader does (e.g. for
100// locations without debug info whose line is 0).
101static uint32_t getLineOffset(const DILocation *DIL) {
102 unsigned Line = DIL->getLine();
103 unsigned SubprogramLine = DIL->getScope()->getSubprogram()->getLine();
104 if (Line < SubprogramLine)
105 return 0;
106 return Line - SubprogramLine;
107}
108
109static AllocationType getAllocType(const AllocationInfo *AllocInfo) {
110 return getAllocType(TotalLifetimeAccessDensity: AllocInfo->Info.getTotalLifetimeAccessDensity(),
111 AllocCount: AllocInfo->Info.getAllocCount(),
112 TotalLifetime: AllocInfo->Info.getTotalLifetime());
113}
114
115static AllocationType addCallStack(CallStackTrie &AllocTrie,
116 const AllocationInfo *AllocInfo,
117 uint64_t FullStackId) {
118 SmallVector<uint64_t> StackIds;
119 for (const auto &StackFrame : AllocInfo->CallStack)
120 StackIds.push_back(Elt: computeStackId(Frame: StackFrame));
121 auto AllocType = getAllocType(AllocInfo);
122 std::vector<ContextTotalSize> ContextSizeInfo;
123 if (recordContextSizeInfoForAnalysis()) {
124 auto TotalSize = AllocInfo->Info.getTotalSize();
125 assert(TotalSize);
126 assert(FullStackId != 0);
127 ContextSizeInfo.push_back(x: {.FullStackId: FullStackId, .TotalSize: TotalSize});
128 }
129 AllocTrie.addCallStack(AllocType, StackIds, ContextSizeInfo: std::move(ContextSizeInfo));
130 return AllocType;
131}
132
133// Return true if InlinedCallStack, computed from a call instruction's debug
134// info, is a prefix of ProfileCallStack, a list of Frames from profile data
135// (either the allocation data or a callsite).
136static bool
137stackFrameIncludesInlinedCallStack(ArrayRef<Frame> ProfileCallStack,
138 ArrayRef<uint64_t> InlinedCallStack) {
139 return ProfileCallStack.size() >= InlinedCallStack.size() &&
140 llvm::equal(LRange: ProfileCallStack.take_front(N: InlinedCallStack.size()),
141 RRange&: InlinedCallStack, P: [](const Frame &F, uint64_t StackId) {
142 return computeStackId(Frame: F) == StackId;
143 });
144}
145
146static bool isAllocationWithHotColdVariant(const InstrumentationOptions &Opts,
147 const Function *Callee,
148 const TargetLibraryInfo &TLI) {
149 if (!Callee)
150 return false;
151 LibFunc Func = TLI.getLibFunc(FDecl: *Callee);
152 if (Func == NotLibFunc)
153 return false;
154 switch (Func) {
155 case LibFunc_Znwm:
156 case LibFunc_ZnwmRKSt9nothrow_t:
157 case LibFunc_ZnwmSt11align_val_t:
158 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t:
159 case LibFunc_Znam:
160 case LibFunc_ZnamRKSt9nothrow_t:
161 case LibFunc_ZnamSt11align_val_t:
162 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t:
163 case LibFunc_size_returning_new:
164 case LibFunc_size_returning_new_aligned:
165 return true;
166 case LibFunc_Znwm12__hot_cold_t:
167 case LibFunc_ZnwmRKSt9nothrow_t12__hot_cold_t:
168 case LibFunc_ZnwmSt11align_val_t12__hot_cold_t:
169 case LibFunc_ZnwmSt11align_val_tRKSt9nothrow_t12__hot_cold_t:
170 case LibFunc_Znam12__hot_cold_t:
171 case LibFunc_ZnamRKSt9nothrow_t12__hot_cold_t:
172 case LibFunc_ZnamSt11align_val_t12__hot_cold_t:
173 case LibFunc_ZnamSt11align_val_tRKSt9nothrow_t12__hot_cold_t:
174 case LibFunc_size_returning_new_hot_cold:
175 case LibFunc_size_returning_new_aligned_hot_cold:
176 return Opts.memprof_match_hot_cold_new;
177 default:
178 return false;
179 }
180}
181
182static void HandleUnsupportedAnnotationKinds(GlobalVariable &GVar,
183 AnnotationKind Kind) {
184 assert(Kind != llvm::memprof::AnnotationKind::AnnotationOK &&
185 "Should not handle AnnotationOK here");
186 SmallString<32> Reason;
187 switch (Kind) {
188 case llvm::memprof::AnnotationKind::ExplicitSection:
189 ++NumOfMemProfExplicitSectionGlobalVars;
190 Reason.append(RHS: "explicit section name");
191 break;
192 case llvm::memprof::AnnotationKind::DeclForLinker:
193 Reason.append(RHS: "linker declaration");
194 break;
195 case llvm::memprof::AnnotationKind::ReservedName:
196 Reason.append(RHS: "name starts with `llvm.`");
197 break;
198 default:
199 llvm_unreachable("Unexpected annotation kind");
200 }
201 LLVM_DEBUG(dbgs() << "Skip annotation for " << GVar.getName() << " due to "
202 << Reason << ".\n");
203}
204
205// Computes the LLVM version of MD5 hash for the content of a string
206// literal.
207static std::optional<uint64_t>
208getStringContentHash(const GlobalVariable &GVar) {
209 auto *Initializer = GVar.getInitializer();
210 if (!Initializer)
211 return std::nullopt;
212 if (auto *C = dyn_cast<ConstantDataSequential>(Val: Initializer))
213 if (C->isString()) {
214 // Note the hash computed for the literal would include the null byte.
215 return llvm::MD5Hash(Str: C->getAsString());
216 }
217 return std::nullopt;
218}
219
220// Structure for tracking info about matched allocation contexts for use with
221// -memprof-print-match-info and -memprof-print-matched-alloc-stack.
222struct AllocMatchInfo {
223 // Total size in bytes of matched context.
224 uint64_t TotalSize = 0;
225 // Matched allocation's type.
226 AllocationType AllocType = AllocationType::None;
227 // Number of frames matched to the allocation itself (values will be >1 in
228 // cases where allocation was already inlined). Use a set because there can
229 // be multiple inlined instances and each may have a different inline depth.
230 // Use std::set to iterate in sorted order when printing.
231 std::set<unsigned> MatchedFramesSet;
232 // The full call stack of the allocation, for cases where requested via
233 // -memprof-print-matched-alloc-stack.
234 std::vector<Frame> CallStack;
235
236 // Caller responsible for inserting the matched frames and the call stack when
237 // appropriate.
238 AllocMatchInfo(uint64_t TotalSize, AllocationType AllocType)
239 : TotalSize(TotalSize), AllocType(AllocType) {}
240};
241
242DenseMap<uint64_t, SmallVector<CallEdgeTy, 0>>
243memprof::extractCallsFromIR(Module &M, const TargetLibraryInfo &TLI,
244 function_ref<bool(uint64_t)> IsPresentInProfile) {
245 const InstrumentationOptions &Opts = getInstrumentationOptions(M);
246 DenseMap<uint64_t, SmallVector<CallEdgeTy, 0>> Calls;
247
248 for (Function &F : M) {
249 if (F.isDeclaration())
250 continue;
251
252 for (auto &BB : F) {
253 for (auto &I : BB) {
254 if (!isa<CallBase>(Val: &I) || isa<IntrinsicInst>(Val: &I))
255 continue;
256
257 auto *CB = dyn_cast<CallBase>(Val: &I);
258 auto *CalledFunction = CB->getCalledFunction();
259 // Disregard indirect calls and intrinsics.
260 if (!CalledFunction || CalledFunction->isIntrinsic())
261 continue;
262
263 StringRef CalleeName = CalledFunction->getName();
264 // True if we are calling a heap allocation function that supports
265 // hot/cold variants.
266 bool IsAlloc =
267 isAllocationWithHotColdVariant(Opts, Callee: CalledFunction, TLI);
268 // True for the first iteration below, indicating that we are looking at
269 // a leaf node.
270 bool IsLeaf = true;
271 for (const DILocation *DIL = I.getDebugLoc(); DIL;
272 DIL = DIL->getInlinedAt()) {
273 StringRef CallerName = DIL->getSubprogramLinkageName();
274 assert(!CallerName.empty() &&
275 "Be sure to enable -fdebug-info-for-profiling");
276 uint64_t CallerGUID = memprof::getGUID(FunctionName: CallerName);
277 uint64_t CalleeGUID = memprof::getGUID(FunctionName: CalleeName);
278 // Pretend that we are calling a function with GUID == 0 if we are
279 // in the inline stack leading to a heap allocation function.
280 if (IsAlloc) {
281 if (IsLeaf) {
282 // For leaf nodes, set CalleeGUID to 0 without consulting
283 // IsPresentInProfile.
284 CalleeGUID = 0;
285 } else if (!IsPresentInProfile(CalleeGUID)) {
286 // In addition to the leaf case above, continue to set CalleeGUID
287 // to 0 as long as we don't see CalleeGUID in the profile.
288 CalleeGUID = 0;
289 } else {
290 // Once we encounter a callee that exists in the profile, stop
291 // setting CalleeGUID to 0.
292 IsAlloc = false;
293 }
294 }
295
296 LineLocation Loc = {getLineOffset(DIL), DIL->getColumn()};
297 Calls[CallerGUID].emplace_back(Args&: Loc, Args&: CalleeGUID);
298 CalleeName = CallerName;
299 IsLeaf = false;
300 }
301 }
302 }
303 }
304
305 // Sort each call list by the source location.
306 for (auto &[CallerGUID, CallList] : Calls) {
307 llvm::sort(C&: CallList);
308 CallList.erase(CS: llvm::unique(R&: CallList), CE: CallList.end());
309 }
310
311 return Calls;
312}
313
314DenseMap<uint64_t, LocToLocMap>
315memprof::computeUndriftMap(Module &M, IndexedInstrProfReader *MemProfReader,
316 const TargetLibraryInfo &TLI) {
317 DenseMap<uint64_t, LocToLocMap> UndriftMaps;
318
319 DenseMap<uint64_t, SmallVector<memprof::CallEdgeTy, 0>> CallsFromProfile =
320 MemProfReader->getMemProfCallerCalleePairs();
321 DenseMap<uint64_t, SmallVector<memprof::CallEdgeTy, 0>> CallsFromIR =
322 extractCallsFromIR(M, TLI, IsPresentInProfile: [&](uint64_t GUID) {
323 return CallsFromProfile.contains(Val: GUID);
324 });
325
326 // Compute an undrift map for each CallerGUID.
327 for (const auto &[CallerGUID, IRAnchors] : CallsFromIR) {
328 auto It = CallsFromProfile.find(Val: CallerGUID);
329 if (It == CallsFromProfile.end())
330 continue;
331 const auto &ProfileAnchors = It->second;
332
333 LocToLocMap Matchings;
334 longestCommonSequence<LineLocation, GlobalValue::GUID>(
335 AnchorList1: ProfileAnchors, AnchorList2: IRAnchors, FunctionMatchesProfile: std::equal_to<GlobalValue::GUID>(),
336 InsertMatching: [&](LineLocation A, LineLocation B) { Matchings.try_emplace(Key: A, Args&: B); });
337 [[maybe_unused]] bool Inserted =
338 UndriftMaps.try_emplace(Key: CallerGUID, Args: std::move(Matchings)).second;
339
340 // The insertion must succeed because we visit each GUID exactly once.
341 assert(Inserted);
342 }
343
344 return UndriftMaps;
345}
346
347// Given a MemProfRecord, undrift all the source locations present in the
348// record in place.
349static void
350undriftMemProfRecord(const DenseMap<uint64_t, LocToLocMap> &UndriftMaps,
351 memprof::MemProfRecord &MemProfRec) {
352 // Undrift a call stack in place.
353 auto UndriftCallStack = [&](std::vector<Frame> &CallStack) {
354 for (auto &F : CallStack) {
355 auto I = UndriftMaps.find(Val: F.Function);
356 if (I == UndriftMaps.end())
357 continue;
358 auto J = I->second.find(Val: LineLocation(F.LineOffset, F.Column));
359 if (J == I->second.end())
360 continue;
361 auto &NewLoc = J->second;
362 F.LineOffset = NewLoc.LineOffset;
363 F.Column = NewLoc.Column;
364 }
365 };
366
367 for (auto &AS : MemProfRec.AllocSites)
368 UndriftCallStack(AS.CallStack);
369
370 for (auto &CS : MemProfRec.CallSites)
371 UndriftCallStack(CS.Frames);
372}
373
374// Helper function to process CalleeGuids and create value profile metadata
375static void addVPMetadata(const InstrumentationOptions &Opts, Module &M,
376 Instruction &I,
377 ArrayRef<GlobalValue::GUID> CalleeGuids) {
378 if (!Opts.memprof_attach_calleeguids || CalleeGuids.empty())
379 return;
380
381 // Prepare the vector of value data, initializing from any existing
382 // value-profile metadata present on the instruction so that we merge the
383 // new CalleeGuids into the existing entries.
384 SmallVector<InstrProfValueData> VDs;
385 uint64_t TotalCount = 0;
386
387 if (I.getMetadata(KindID: LLVMContext::MD_prof)) {
388 // Read all existing entries so we can merge them. Use a large
389 // MaxNumValueData to retrieve all existing entries.
390 VDs = getValueProfDataFromInst(Inst: I, ValueKind: IPVK_IndirectCallTarget,
391 /*MaxNumValueData=*/UINT32_MAX, TotalC&: TotalCount);
392 }
393
394 // Save the original size for use later in detecting whether any were added.
395 const size_t OriginalSize = VDs.size();
396
397 // Initialize the set of existing guids with the original list.
398 DenseSet<uint64_t> ExistingValues(
399 llvm::from_range,
400 llvm::map_range(
401 C&: VDs, F: [](const InstrProfValueData &Entry) { return Entry.Value; }));
402
403 // Merge CalleeGuids into list of existing VDs, by appending any that are not
404 // already included.
405 VDs.reserve(N: OriginalSize + CalleeGuids.size());
406 for (auto G : CalleeGuids) {
407 if (!ExistingValues.insert(V: G).second)
408 continue;
409 InstrProfValueData NewEntry;
410 NewEntry.Value = G;
411 // For MemProf, we don't have actual call counts, so we assign
412 // a weight of 1 to each potential target.
413 // TODO: Consider making this weight configurable or increasing it to
414 // improve effectiveness for ICP.
415 NewEntry.Count = 1;
416 TotalCount += NewEntry.Count;
417 VDs.push_back(Elt: NewEntry);
418 }
419
420 // Update the VP metadata if we added any new callee GUIDs to the list.
421 assert(VDs.size() >= OriginalSize);
422 if (VDs.size() == OriginalSize)
423 return;
424
425 // First clear the existing !prof.
426 I.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
427
428 // No need to sort the updated VDs as all appended entries have the same count
429 // of 1, which is no larger than any existing entries. The incoming list of
430 // CalleeGuids should already be deterministic for a given profile.
431 annotateValueSite(M, Inst&: I, VDs, Sum: TotalCount, ValueKind: IPVK_IndirectCallTarget, MaxMDCount: VDs.size());
432}
433
434static void handleAllocSite(
435 const InstrumentationOptions &Opts, Instruction &I, CallBase *CI,
436 ArrayRef<uint64_t> InlinedCallStack, LLVMContext &Ctx,
437 OptimizationRemarkEmitter &ORE, uint64_t MaxColdSize,
438 const std::set<const AllocationInfo *> &AllocInfoSet,
439 std::map<uint64_t, AllocMatchInfo> &FullStackIdToAllocMatchInfo) {
440 // TODO: Remove this once the profile creation logic deduplicates contexts
441 // that are the same other than the IsInlineFrame bool. Until then, keep the
442 // largest.
443 DenseMap<uint64_t, const AllocationInfo *> UniqueFullContextIdAllocInfo;
444 for (auto *AllocInfo : AllocInfoSet) {
445 auto FullStackId = computeFullStackId(CallStack: AllocInfo->CallStack);
446 auto [It, Inserted] =
447 UniqueFullContextIdAllocInfo.insert(KV: {FullStackId, AllocInfo});
448 // If inserted entry, done.
449 if (Inserted)
450 continue;
451 // Keep the larger one, or the noncold one if they are the same size.
452 auto CurSize = It->second->Info.getTotalSize();
453 auto NewSize = AllocInfo->Info.getTotalSize();
454 if ((CurSize > NewSize) ||
455 (CurSize == NewSize &&
456 getAllocType(AllocInfo) != AllocationType::NotCold))
457 continue;
458 It->second = AllocInfo;
459 }
460 // We may match this instruction's location list to multiple MIB
461 // contexts. Add them to a Trie specialized for trimming the contexts to
462 // the minimal needed to disambiguate contexts with unique behavior.
463 CallStackTrie AllocTrie(&ORE, MaxColdSize);
464 uint64_t TotalSize = 0;
465 uint64_t TotalColdSize = 0;
466 for (auto &[FullStackId, AllocInfo] : UniqueFullContextIdAllocInfo) {
467 // Check the full inlined call stack against this one.
468 // If we found and thus matched all frames on the call, include
469 // this MIB.
470 if (stackFrameIncludesInlinedCallStack(ProfileCallStack: AllocInfo->CallStack,
471 InlinedCallStack)) {
472 NumOfMemProfMatchedAllocContexts++;
473 auto AllocType = addCallStack(AllocTrie, AllocInfo, FullStackId);
474 TotalSize += AllocInfo->Info.getTotalSize();
475 if (AllocType == AllocationType::Cold)
476 TotalColdSize += AllocInfo->Info.getTotalSize();
477 // Record information about the allocation if match info printing
478 // was requested.
479 if (Opts.memprof_print_match_info) {
480 assert(FullStackId != 0);
481 auto [Iter, Inserted] = FullStackIdToAllocMatchInfo.try_emplace(
482 k: FullStackId,
483 args: AllocMatchInfo(AllocInfo->Info.getTotalSize(), AllocType));
484 // Always insert the new matched frame count, since it may differ.
485 Iter->second.MatchedFramesSet.insert(x: InlinedCallStack.size());
486 if (Inserted && Opts.memprof_print_matched_alloc_stack)
487 Iter->second.CallStack.insert(position: Iter->second.CallStack.begin(),
488 first: AllocInfo->CallStack.begin(),
489 last: AllocInfo->CallStack.end());
490 }
491 ORE.emit(
492 OptDiag: OptimizationRemark(DEBUG_TYPE, "MemProfUse", CI)
493 << ore::NV("AllocationCall", CI) << " in function "
494 << ore::NV("Caller", CI->getFunction())
495 << " matched alloc context with alloc type "
496 << ore::NV("Attribute", getAllocTypeAttributeString(Type: AllocType))
497 << " total size " << ore::NV("Size", AllocInfo->Info.getTotalSize())
498 << " full context id " << ore::NV("Context", FullStackId)
499 << " frame count " << ore::NV("Frames", InlinedCallStack.size()));
500 }
501 }
502 // If the threshold for the percent of cold bytes is less than 100%,
503 // and not all bytes are cold, see if we should still hint this
504 // allocation as cold without context sensitivity.
505 if (TotalColdSize < TotalSize && Opts.memprof_matching_cold_threshold < 100 &&
506 TotalColdSize * 100 >= Opts.memprof_matching_cold_threshold * TotalSize) {
507 AllocTrie.addSingleAllocTypeAttribute(CI, AT: AllocationType::Cold, Descriptor: "dominant");
508 return;
509 }
510
511 // We might not have matched any to the full inlined call stack.
512 // But if we did, create and attach metadata, or a function attribute if
513 // all contexts have identical profiled behavior.
514 if (!AllocTrie.empty()) {
515 NumOfMemProfMatchedAllocs++;
516 // MemprofMDAttached will be false if a function attribute was
517 // attached.
518 bool MemprofMDAttached = AllocTrie.buildAndAttachMIBMetadata(CI);
519 assert(MemprofMDAttached == I.hasMetadata(LLVMContext::MD_memprof));
520 if (MemprofMDAttached) {
521 // Add callsite metadata for the instruction's location list so that
522 // it simpler later on to identify which part of the MIB contexts
523 // are from this particular instruction (including during inlining,
524 // when the callsite metadata will be updated appropriately).
525 // FIXME: can this be changed to strip out the matching stack
526 // context ids from the MIB contexts and not add any callsite
527 // metadata here to save space?
528 addCallsiteMetadata(I, InlinedCallStack, Ctx);
529 }
530 }
531}
532
533// Helper struct for maintaining refs to callsite data. As an alternative we
534// could store a pointer to the CallSiteInfo struct but we also need the frame
535// index. Using ArrayRefs instead makes it a little easier to read.
536struct CallSiteEntry {
537 // Subset of frames for the corresponding CallSiteInfo.
538 ArrayRef<Frame> Frames;
539 // Potential targets for indirect calls.
540 ArrayRef<GlobalValue::GUID> CalleeGuids;
541};
542
543static void handleCallSite(const InstrumentationOptions &Opts, Instruction &I,
544 const Function *CalledFunction,
545 ArrayRef<uint64_t> InlinedCallStack,
546 const std::vector<CallSiteEntry> &CallSiteEntries,
547 Module &M,
548 std::set<std::vector<uint64_t>> &MatchedCallSites,
549 OptimizationRemarkEmitter &ORE) {
550 auto &Ctx = M.getContext();
551 // Set of Callee GUIDs to attach to indirect calls. We accumulate all of them
552 // to support cases where the instruction's inlined frames match multiple call
553 // site entries, which can happen if the profile was collected from a binary
554 // where this instruction was eventually inlined into multiple callers.
555 SetVector<GlobalValue::GUID> CalleeGuids;
556 bool CallsiteMDAdded = false;
557 for (const auto &CallSiteEntry : CallSiteEntries) {
558 // If we found and thus matched all frames on the call, create and
559 // attach call stack metadata.
560 if (stackFrameIncludesInlinedCallStack(ProfileCallStack: CallSiteEntry.Frames,
561 InlinedCallStack)) {
562 NumOfMemProfMatchedCallSites++;
563 // Only need to find one with a matching call stack and add a single
564 // callsite metadata.
565 if (!CallsiteMDAdded) {
566 addCallsiteMetadata(I, InlinedCallStack, Ctx);
567
568 // Accumulate call site matching information upon request.
569 if (Opts.memprof_print_match_info) {
570 std::vector<uint64_t> CallStack;
571 append_range(C&: CallStack, R&: InlinedCallStack);
572 MatchedCallSites.insert(x: std::move(CallStack));
573 }
574 OptimizationRemark Remark(DEBUG_TYPE, "MemProfUse", &I);
575 Remark << ore::NV("CallSite", &I) << " in function "
576 << ore::NV("Caller", I.getFunction())
577 << " matched callsite with frame count "
578 << ore::NV("Frames", InlinedCallStack.size())
579 << " and stack ids";
580 for (uint64_t StackId : InlinedCallStack)
581 Remark << " " << ore::NV("StackId", StackId);
582 ORE.emit(OptDiag&: Remark);
583
584 // If this is a direct call, we're done.
585 if (CalledFunction)
586 break;
587 CallsiteMDAdded = true;
588 }
589
590 assert(!CalledFunction && "Didn't expect direct call");
591
592 // Collect Callee GUIDs from all matching CallSiteEntries.
593 CalleeGuids.insert(Start: CallSiteEntry.CalleeGuids.begin(),
594 End: CallSiteEntry.CalleeGuids.end());
595 }
596 }
597 // Try to attach indirect call metadata if possible.
598 addVPMetadata(Opts, M, I, CalleeGuids: CalleeGuids.getArrayRef());
599}
600
601// Dump inline call stack for debugging purposes.
602static void dumpInlineCallStack(Instruction &I, CallBase *CI,
603 OptimizationRemarkEmitter &ORE,
604 DenseSet<uint64_t> &SeenFrames,
605 DenseSet<uint64_t> &SeenStacks,
606 bool ProfileHasColumns) {
607 // Dump frame info. Frames are deduplicated using FrameID.
608 std::string CallStack;
609 raw_string_ostream CallStackOS(CallStack);
610 bool First = true;
611 for (const DILocation *DIL = I.getDebugLoc(); DIL;
612 DIL = DIL->getInlinedAt()) {
613 StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
614 if (Name.empty())
615 Name = DIL->getScope()->getSubprogram()->getName();
616 auto CalleeGUID = Function::getGUIDAssumingExternalLinkage(GlobalName: Name);
617 uint64_t FrameID = computeStackId(Function: CalleeGUID, LineOffset: getLineOffset(DIL),
618 Column: ProfileHasColumns ? DIL->getColumn() : 0);
619 if (SeenFrames.insert(V: FrameID).second) {
620 std::string DictMsg;
621 raw_string_ostream DictOS(DictMsg);
622 DictOS << "frame: " << FrameID << " " << Name << ":" << getLineOffset(DIL)
623 << ":" << (ProfileHasColumns ? DIL->getColumn() : 0);
624 ORE.emit(OptDiag: OptimizationRemarkAnalysis(DEBUG_TYPE, "MemProfUse", CI)
625 << DictOS.str());
626 }
627
628 if (First)
629 First = false;
630 else
631 CallStackOS << ",";
632 CallStackOS << FrameID;
633 }
634
635 // Dump inline call stack info. Stacks are deduplicated using StackHash.
636 uint64_t StackHash = llvm::MD5Hash(Str: CallStack);
637 if (SeenStacks.insert(V: StackHash).second) {
638 std::string Msg;
639 raw_string_ostream OS(Msg);
640 OS << "inline call stack: " << CallStack;
641 ORE.emit(OptDiag: OptimizationRemarkAnalysis(DEBUG_TYPE, "MemProfUse", CI)
642 << OS.str());
643 }
644}
645
646static void
647readMemprof(const InstrumentationOptions &Opts, Module &M, Function &F,
648 IndexedInstrProfReader *MemProfReader, const TargetLibraryInfo &TLI,
649 std::map<uint64_t, AllocMatchInfo> &FullStackIdToAllocMatchInfo,
650 std::set<std::vector<uint64_t>> &MatchedCallSites,
651 DenseMap<uint64_t, LocToLocMap> &UndriftMaps,
652 OptimizationRemarkEmitter &ORE, uint64_t MaxColdSize,
653 DenseSet<uint64_t> &SeenStacks, DenseSet<uint64_t> &SeenFrames) {
654 auto &Ctx = M.getContext();
655 // Previously we used getIRPGOObjectName() here. If F is local linkage,
656 // getIRPGOObjectName() returns FuncName with prefix 'FileName;'. But
657 // llvm-profdata uses FuncName in dwarf to create GUID which doesn't
658 // contain FileName's prefix. It caused local linkage function can't
659 // find MemProfRecord. So we use getName() now.
660 // 'unique-internal-linkage-names' can make MemProf work better for local
661 // linkage function.
662 auto FuncName = F.getName();
663 auto FuncGUID = Function::getGUIDAssumingExternalLinkage(GlobalName: FuncName);
664 if (Opts.memprof_print_function_guids)
665 errs() << "MemProf: Function GUID " << FuncGUID << " is " << FuncName
666 << "\n";
667 std::optional<memprof::MemProfRecord> MemProfRec;
668 auto Err = MemProfReader->getMemProfRecord(FuncNameHash: FuncGUID).moveInto(Value&: MemProfRec);
669 if (Err) {
670 handleAllErrors(E: std::move(Err), Handlers: [&](const InstrProfError &IPE) {
671 auto Err = IPE.get();
672 bool SkipWarning = false;
673 LLVM_DEBUG(dbgs() << "Error in reading profile for Func " << FuncName
674 << ": ");
675 if (Err == instrprof_error::unknown_function) {
676 NumOfMemProfMissing++;
677 SkipWarning = !Opts.pgo_warn_missing_function;
678 LLVM_DEBUG(dbgs() << "unknown function");
679 } else if (Err == instrprof_error::hash_mismatch) {
680 NumOfMemProfMismatch++;
681 SkipWarning =
682 NoPGOWarnMismatch ||
683 (Opts.no_pgo_warn_mismatch_comdat_weak &&
684 (F.hasComdat() ||
685 F.getLinkage() == GlobalValue::AvailableExternallyLinkage));
686 LLVM_DEBUG(dbgs() << "hash mismatch (skip=" << SkipWarning << ")");
687 }
688
689 if (SkipWarning)
690 return;
691
692 std::string Msg = (IPE.message() + Twine(" ") + F.getName().str() +
693 Twine(" Hash = ") + std::to_string(val: FuncGUID))
694 .str();
695
696 Ctx.diagnose(
697 DI: DiagnosticInfoPGOProfile(M.getName().data(), Msg, DS_Warning));
698 });
699 return;
700 }
701
702 NumOfMemProfFunc++;
703
704 // If requested, undrfit MemProfRecord so that the source locations in it
705 // match those in the IR.
706 if (Opts.memprof_salvage_stale_profile)
707 undriftMemProfRecord(UndriftMaps, MemProfRec&: *MemProfRec);
708
709 // Detect if there are non-zero column numbers in the profile. If not,
710 // treat all column numbers as 0 when matching (i.e. ignore any non-zero
711 // columns in the IR). The profiled binary might have been built with
712 // column numbers disabled, for example.
713 bool ProfileHasColumns = false;
714
715 // Build maps of the location hash to all profile data with that leaf location
716 // (allocation info and the callsites).
717 std::map<uint64_t, std::set<const AllocationInfo *>> LocHashToAllocInfo;
718
719 // For the callsites we need to record slices of the frame array (see comments
720 // below where the map entries are added) along with their CalleeGuids.
721 std::map<uint64_t, std::vector<CallSiteEntry>> LocHashToCallSites;
722 for (auto &AI : MemProfRec->AllocSites) {
723 NumOfMemProfAllocContextProfiles++;
724 // Associate the allocation info with the leaf frame. The later matching
725 // code will match any inlined call sequences in the IR with a longer prefix
726 // of call stack frames.
727 uint64_t StackId = computeStackId(Frame: AI.CallStack[0]);
728 LocHashToAllocInfo[StackId].insert(x: &AI);
729 ProfileHasColumns |= AI.CallStack[0].Column;
730 }
731 for (auto &CS : MemProfRec->CallSites) {
732 NumOfMemProfCallSiteProfiles++;
733 // Need to record all frames from leaf up to and including this function,
734 // as any of these may or may not have been inlined at this point.
735 unsigned Idx = 0;
736 for (auto &StackFrame : CS.Frames) {
737 uint64_t StackId = computeStackId(Frame: StackFrame);
738 ArrayRef<Frame> FrameSlice = ArrayRef<Frame>(CS.Frames).drop_front(N: Idx++);
739 // The callee guids for the slice containing all frames (due to the
740 // increment above Idx is now 1) comes from the CalleeGuids recorded in
741 // the CallSite. For the slices not containing the leaf-most frame, the
742 // callee guid is simply the function GUID of the prior frame.
743 LocHashToCallSites[StackId].push_back(
744 x: {.Frames: FrameSlice, .CalleeGuids: (Idx == 1 ? CS.CalleeGuids
745 : ArrayRef<GlobalValue::GUID>(
746 CS.Frames[Idx - 2].Function))});
747
748 ProfileHasColumns |= StackFrame.Column;
749 // Once we find this function, we can stop recording.
750 if (StackFrame.Function == FuncGUID)
751 break;
752 }
753 assert(Idx <= CS.Frames.size() && CS.Frames[Idx - 1].Function == FuncGUID);
754 }
755
756 // Now walk the instructions, looking up the associated profile data using
757 // debug locations.
758 for (auto &BB : F) {
759 for (auto &I : BB) {
760 // We are only interested in calls (allocation or interior call stack
761 // context calls).
762 auto *CI = dyn_cast<CallBase>(Val: &I);
763 if (!CI)
764 continue;
765 auto *CalledFunction = CI->getCalledFunction();
766 if (CalledFunction && CalledFunction->isIntrinsic())
767 continue;
768
769 if (ORE.allowExtraAnalysis(DEBUG_TYPE))
770 dumpInlineCallStack(I, CI, ORE, SeenFrames, SeenStacks,
771 ProfileHasColumns);
772
773 // List of call stack ids computed from the location hashes on debug
774 // locations (leaf to inlined at root).
775 SmallVector<uint64_t, 8> InlinedCallStack;
776 // Was the leaf location found in one of the profile maps?
777 bool LeafFound = false;
778 // If leaf was found in a map, iterators pointing to its location in both
779 // of the maps. It might exist in neither, one, or both (the latter case
780 // can happen because we don't currently have discriminators to
781 // distinguish the case when a single line/col maps to both an allocation
782 // and another callsite).
783 auto AllocInfoIter = LocHashToAllocInfo.end();
784 auto CallSitesIter = LocHashToCallSites.end();
785 for (const DILocation *DIL = I.getDebugLoc(); DIL != nullptr;
786 DIL = DIL->getInlinedAt()) {
787 // Use C++ linkage name if possible. Need to compile with
788 // -fdebug-info-for-profiling to get linkage name.
789 StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
790 if (Name.empty())
791 Name = DIL->getScope()->getSubprogram()->getName();
792 auto CalleeGUID = Function::getGUIDAssumingExternalLinkage(GlobalName: Name);
793 auto StackId = computeStackId(Function: CalleeGUID, LineOffset: getLineOffset(DIL),
794 Column: ProfileHasColumns ? DIL->getColumn() : 0);
795 // Check if we have found the profile's leaf frame. If yes, collect
796 // the rest of the call's inlined context starting here. If not, see if
797 // we find a match further up the inlined context (in case the profile
798 // was missing debug frames at the leaf).
799 if (!LeafFound) {
800 AllocInfoIter = LocHashToAllocInfo.find(x: StackId);
801 CallSitesIter = LocHashToCallSites.find(x: StackId);
802 if (AllocInfoIter != LocHashToAllocInfo.end() ||
803 CallSitesIter != LocHashToCallSites.end())
804 LeafFound = true;
805 }
806 if (LeafFound)
807 InlinedCallStack.push_back(Elt: StackId);
808 }
809 // If leaf not in either of the maps, skip inst.
810 if (!LeafFound)
811 continue;
812
813 // First add !memprof metadata from allocation info, if we found the
814 // instruction's leaf location in that map, and if the rest of the
815 // instruction's locations match the prefix Frame locations on an
816 // allocation context with the same leaf.
817 if (AllocInfoIter != LocHashToAllocInfo.end() &&
818 // Only consider allocations which support hinting.
819 isAllocationWithHotColdVariant(Opts, Callee: CI->getCalledFunction(), TLI))
820 handleAllocSite(Opts, I, CI, InlinedCallStack, Ctx, ORE, MaxColdSize,
821 AllocInfoSet: AllocInfoIter->second, FullStackIdToAllocMatchInfo);
822 else if (CallSitesIter != LocHashToCallSites.end())
823 // Otherwise, add callsite metadata. If we reach here then we found the
824 // instruction's leaf location in the callsites map and not the
825 // allocation map.
826 handleCallSite(Opts, I, CalledFunction, InlinedCallStack,
827 CallSiteEntries: CallSitesIter->second, M, MatchedCallSites, ORE);
828 }
829 }
830}
831
832MemProfUsePass::MemProfUsePass(std::string MemoryProfileFile,
833 IntrusiveRefCntPtr<vfs::FileSystem> FS)
834 : MemoryProfileFileName(MemoryProfileFile), FS(FS) {
835 if (!FS)
836 this->FS = vfs::getRealFileSystem();
837}
838
839PreservedAnalyses MemProfUsePass::run(Module &M, ModuleAnalysisManager &AM) {
840 const InstrumentationOptions &Opts = getInstrumentationOptions(M);
841 // Return immediately if the module doesn't contain any function or global
842 // variables.
843 if (M.empty() && M.globals().empty())
844 return PreservedAnalyses::all();
845
846 LLVM_DEBUG(dbgs() << "Read in memory profile:\n");
847 auto &Ctx = M.getContext();
848 auto ReaderOrErr = IndexedInstrProfReader::create(Path: MemoryProfileFileName, FS&: *FS);
849 if (Error E = ReaderOrErr.takeError()) {
850 handleAllErrors(E: std::move(E), Handlers: [&](const ErrorInfoBase &EI) {
851 Ctx.diagnose(
852 DI: DiagnosticInfoPGOProfile(MemoryProfileFileName.data(), EI.message()));
853 });
854 return PreservedAnalyses::all();
855 }
856
857 std::unique_ptr<IndexedInstrProfReader> MemProfReader =
858 std::move(ReaderOrErr.get());
859 if (!MemProfReader) {
860 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(
861 MemoryProfileFileName.data(), StringRef("Cannot get MemProfReader")));
862 return PreservedAnalyses::all();
863 }
864
865 if (!MemProfReader->hasMemoryProfile()) {
866 Ctx.diagnose(DI: DiagnosticInfoPGOProfile(MemoryProfileFileName.data(),
867 "Not a memory profile"));
868 return PreservedAnalyses::all();
869 }
870
871 const bool Changed =
872 Opts.memprof_annotate_static_data_prefix &&
873 annotateGlobalVariables(M, DataAccessProf: MemProfReader->getDataAccessProfileData());
874
875 // If the module doesn't contain any function, return after we process all
876 // global variables.
877 if (M.empty())
878 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
879
880 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
881
882 TargetLibraryInfo &TLI = FAM.getResult<TargetLibraryAnalysis>(IR&: *M.begin());
883 DenseMap<uint64_t, LocToLocMap> UndriftMaps;
884 if (Opts.memprof_salvage_stale_profile)
885 UndriftMaps = computeUndriftMap(M, MemProfReader: MemProfReader.get(), TLI);
886
887 // Map from the stack hash of each matched allocation context in the function
888 // profiles to match info such as the total profiled size (bytes), allocation
889 // type, number of frames matched to the allocation itself, and the full array
890 // of call stack ids.
891 std::map<uint64_t, AllocMatchInfo> FullStackIdToAllocMatchInfo;
892
893 // Set of the matched call sites, each expressed as a sequence of an inline
894 // call stack.
895 std::set<std::vector<uint64_t>> MatchedCallSites;
896
897 DenseSet<uint64_t> SeenStacks;
898 DenseSet<uint64_t> SeenFrames;
899
900 uint64_t MaxColdSize = 0;
901 if (auto *MemProfSum = MemProfReader->getMemProfSummary())
902 MaxColdSize = MemProfSum->getMaxColdTotalSize();
903
904 for (auto &F : M) {
905 if (F.isDeclaration())
906 continue;
907
908 const TargetLibraryInfo &TLI = FAM.getResult<TargetLibraryAnalysis>(IR&: F);
909 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
910 readMemprof(Opts, M, F, MemProfReader: MemProfReader.get(), TLI,
911 FullStackIdToAllocMatchInfo, MatchedCallSites, UndriftMaps, ORE,
912 MaxColdSize, SeenStacks, SeenFrames);
913 }
914
915 if (Opts.memprof_print_match_info) {
916 for (const auto &[Id, Info] : FullStackIdToAllocMatchInfo) {
917 for (auto Frames : Info.MatchedFramesSet) {
918 // TODO: To reduce verbosity, should we change the existing message
919 // so that we emit a list of matched frame counts in a single message
920 // about the context (instead of one message per frame count?
921 errs() << "MemProf " << getAllocTypeAttributeString(Type: Info.AllocType)
922 << " context with id " << Id << " has total profiled size "
923 << Info.TotalSize << " is matched with " << Frames << " frames";
924 if (Opts.memprof_print_matched_alloc_stack) {
925 errs() << " and call stack";
926 for (auto &F : Info.CallStack)
927 errs() << " " << computeStackId(Frame: F);
928 }
929 errs() << "\n";
930 }
931 }
932
933 for (const auto &CallStack : MatchedCallSites) {
934 errs() << "MemProf callsite match for inline call stack";
935 for (uint64_t StackId : CallStack)
936 errs() << " " << StackId;
937 errs() << "\n";
938 }
939 }
940
941 return PreservedAnalyses::none();
942}
943
944bool MemProfUsePass::annotateGlobalVariables(
945 Module &M, const memprof::DataAccessProfData *DataAccessProf) {
946 if (M.globals().empty())
947 return false;
948
949 if (!DataAccessProf) {
950 M.addModuleFlag(Behavior: Module::Warning, Key: "EnableDataAccessProf", Val: 0U);
951 // FIXME: Add a diagnostic message without failing the compilation when
952 // data access profile payload is not available.
953 return false;
954 }
955 M.addModuleFlag(Behavior: Module::Warning, Key: "EnableDataAccessProf", Val: 1U);
956
957 bool Changed = false;
958 // Iterate all global variables in the module and annotate them based on
959 // data access profiles. Note it's up to the linker to decide how to map input
960 // sections to output sections, and one conservative practice is to map
961 // unlikely-prefixed ones to unlikely output section, and map the rest
962 // (hot-prefixed or prefix-less) to the canonical output section.
963 for (GlobalVariable &GVar : M.globals()) {
964 assert(!GVar.getSectionPrefix().has_value() &&
965 "GVar shouldn't have section prefix yet");
966 auto Kind = llvm::memprof::getAnnotationKind(GV: GVar);
967 if (Kind != llvm::memprof::AnnotationKind::AnnotationOK) {
968 HandleUnsupportedAnnotationKinds(GVar, Kind);
969 continue;
970 }
971
972 StringRef Name = GVar.getName();
973 SymbolHandleRef Handle = SymbolHandleRef(Name);
974 // Skip string literals as their mangled names don't stay stable across
975 // binary releases.
976 if (!shouldAnnotateStringLiteralSectionPrefix(C: GVar.getContext()))
977 if (Name.starts_with(Prefix: ".str"))
978 continue;
979
980 if (Name.starts_with(Prefix: ".str")) {
981 std::optional<uint64_t> Hash = getStringContentHash(GVar);
982 if (!Hash) {
983 LLVM_DEBUG(dbgs() << "Cannot compute content hash for string literal "
984 << Name << "\n");
985 continue;
986 }
987 Handle = SymbolHandleRef(Hash.value());
988 }
989
990 // DataAccessProfRecord's get* methods will canonicalize the name under the
991 // hood before looking it up, so optimizer doesn't need to do it.
992 std::optional<DataAccessProfRecord> Record =
993 DataAccessProf->getProfileRecord(SymID: Handle);
994 // Annotate a global variable as hot if it has non-zero sampled count, and
995 // annotate it as cold if it's seen in the profiled binary
996 // file but doesn't have any access sample.
997 // For logging, optimization remark emitter requires a llvm::Function, but
998 // it's not well defined how to associate a global variable with a function.
999 // So we just print out the static data section prefix in LLVM_DEBUG.
1000 if (Record && Record->AccessCount > 0) {
1001 ++NumOfMemProfHotGlobalVars;
1002 Changed |= GVar.setSectionPrefix("hot");
1003 LLVM_DEBUG(dbgs() << "Global variable " << Name
1004 << " is annotated as hot\n");
1005 } else if (DataAccessProf->isKnownColdSymbol(SymID: Handle)) {
1006 ++NumOfMemProfColdGlobalVars;
1007 Changed |= GVar.setSectionPrefix("unlikely");
1008 Changed = true;
1009 LLVM_DEBUG(dbgs() << "Global variable " << Name
1010 << " is annotated as unlikely\n");
1011 } else {
1012 ++NumOfMemProfUnknownGlobalVars;
1013 LLVM_DEBUG(dbgs() << "Global variable " << Name << " is not annotated\n");
1014 }
1015 }
1016
1017 return Changed;
1018}
1019