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