1//===- CtxProfAnalysis.cpp - contextual profile analysis ------------------===//
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// Implementation of the contextual profile analysis, which maintains contextual
10// profiling info through IPO passes.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/CtxProfAnalysis.h"
15#include "AnalysisOptions.h"
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/Analysis/CFG.h"
19#include "llvm/IR/Analysis.h"
20#include "llvm/IR/Dominators.h"
21#include "llvm/IR/IntrinsicInst.h"
22#include "llvm/IR/Module.h"
23#include "llvm/IR/PassManager.h"
24#include "llvm/ProfileData/PGOCtxProfReader.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/MemoryBuffer.h"
27#include "llvm/Support/Path.h"
28#include <deque>
29#include <memory>
30
31#define DEBUG_TYPE "ctx_prof"
32
33using namespace llvm;
34
35namespace llvm {
36
37cl::opt<std::string>
38 UseCtxProfile("use-ctx-profile", cl::init(Val: ""), cl::Hidden,
39 cl::desc("Use the specified contextual profile file"));
40
41class ProfileAnnotatorImpl final {
42 friend class ProfileAnnotator;
43 class BBInfo;
44 struct EdgeInfo {
45 BBInfo *const Src;
46 BBInfo *const Dest;
47 std::optional<uint64_t> Count;
48
49 explicit EdgeInfo(BBInfo &Src, BBInfo &Dest) : Src(&Src), Dest(&Dest) {}
50 };
51
52 class BBInfo {
53 std::optional<uint64_t> Count;
54 // OutEdges is dimensioned to match the number of terminator operands.
55 // Entries in the vector match the index in the terminator operand list. In
56 // some cases - see `shouldExcludeEdge` and its implementation - an entry
57 // will be nullptr.
58 // InEdges doesn't have the above constraint.
59 SmallVector<EdgeInfo *> OutEdges;
60 SmallVector<EdgeInfo *> InEdges;
61 size_t UnknownCountOutEdges = 0;
62 size_t UnknownCountInEdges = 0;
63
64 // Pass AssumeAllKnown when we try to propagate counts from edges to BBs -
65 // because all the edge counters must be known.
66 // Return std::nullopt if there were no edges to sum. The user can decide
67 // how to interpret that.
68 std::optional<uint64_t> getEdgeSum(const SmallVector<EdgeInfo *> &Edges,
69 bool AssumeAllKnown) const {
70 std::optional<uint64_t> Sum;
71 for (const auto *E : Edges) {
72 // `Edges` may be `OutEdges`, case in which `E` could be nullptr.
73 if (E) {
74 if (!Sum.has_value())
75 Sum = 0;
76 *Sum += (AssumeAllKnown ? *E->Count : E->Count.value_or(u: 0U));
77 }
78 }
79 return Sum;
80 }
81
82 bool computeCountFrom(const SmallVector<EdgeInfo *> &Edges) {
83 assert(!Count.has_value());
84 Count = getEdgeSum(Edges, AssumeAllKnown: true);
85 return Count.has_value();
86 }
87
88 void setSingleUnknownEdgeCount(SmallVector<EdgeInfo *> &Edges) {
89 uint64_t KnownSum = getEdgeSum(Edges, AssumeAllKnown: false).value_or(u: 0U);
90 uint64_t EdgeVal = *Count > KnownSum ? *Count - KnownSum : 0U;
91 EdgeInfo *E = nullptr;
92 for (auto *I : Edges)
93 if (I && !I->Count.has_value()) {
94 E = I;
95#ifdef NDEBUG
96 break;
97#else
98 assert((!E || E == I) &&
99 "Expected exactly one edge to have an unknown count, "
100 "found a second one");
101 continue;
102#endif
103 }
104 assert(E && "Expected exactly one edge to have an unknown count");
105 assert(!E->Count.has_value());
106 E->Count = EdgeVal;
107 assert(E->Src->UnknownCountOutEdges > 0);
108 assert(E->Dest->UnknownCountInEdges > 0);
109 --E->Src->UnknownCountOutEdges;
110 --E->Dest->UnknownCountInEdges;
111 }
112
113 public:
114 BBInfo(size_t NumInEdges, size_t NumOutEdges, std::optional<uint64_t> Count)
115 : Count(Count) {
116 // For in edges, we just want to pre-allocate enough space, since we know
117 // it at this stage. For out edges, we will insert edges at the indices
118 // corresponding to positions in this BB's terminator instruction, so we
119 // construct a default (nullptr values)-initialized vector. A nullptr edge
120 // corresponds to those that are excluded (see shouldExcludeEdge).
121 InEdges.reserve(N: NumInEdges);
122 OutEdges.resize(N: NumOutEdges);
123 }
124
125 bool tryTakeCountFromKnownOutEdges(const BasicBlock &BB) {
126 if (!UnknownCountOutEdges) {
127 return computeCountFrom(Edges: OutEdges);
128 }
129 return false;
130 }
131
132 bool tryTakeCountFromKnownInEdges(const BasicBlock &BB) {
133 if (!UnknownCountInEdges) {
134 return computeCountFrom(Edges: InEdges);
135 }
136 return false;
137 }
138
139 void addInEdge(EdgeInfo &Info) {
140 InEdges.push_back(Elt: &Info);
141 ++UnknownCountInEdges;
142 }
143
144 // For the out edges, we care about the position we place them in, which is
145 // the position in terminator instruction's list (at construction). Later,
146 // we build branch_weights metadata with edge frequency values matching
147 // these positions.
148 void addOutEdge(size_t Index, EdgeInfo &Info) {
149 OutEdges[Index] = &Info;
150 ++UnknownCountOutEdges;
151 }
152
153 bool hasCount() const { return Count.has_value(); }
154
155 uint64_t getCount() const { return *Count; }
156
157 bool trySetSingleUnknownInEdgeCount() {
158 if (UnknownCountInEdges == 1) {
159 setSingleUnknownEdgeCount(InEdges);
160 return true;
161 }
162 return false;
163 }
164
165 bool trySetSingleUnknownOutEdgeCount() {
166 if (UnknownCountOutEdges == 1) {
167 setSingleUnknownEdgeCount(OutEdges);
168 return true;
169 }
170 return false;
171 }
172 size_t getNumOutEdges() const { return OutEdges.size(); }
173
174 uint64_t getEdgeCount(size_t Index) const {
175 if (auto *E = OutEdges[Index])
176 return *E->Count;
177 return 0U;
178 }
179 };
180
181 const Function &F;
182 ArrayRef<uint64_t> Counters;
183 // To be accessed through getBBInfo() after construction.
184 std::map<const BasicBlock *, BBInfo> BBInfos;
185 std::vector<EdgeInfo> EdgeInfos;
186
187 // The only criteria for exclusion is faux suspend -> exit edges in presplit
188 // coroutines. The API serves for readability, currently.
189 bool shouldExcludeEdge(const BasicBlock &Src, const BasicBlock &Dest) const {
190 return llvm::isPresplitCoroSuspendExitEdge(Src, Dest);
191 }
192
193 BBInfo &getBBInfo(const BasicBlock &BB) { return BBInfos.find(x: &BB)->second; }
194
195 const BBInfo &getBBInfo(const BasicBlock &BB) const {
196 return BBInfos.find(x: &BB)->second;
197 }
198
199 // validation function after we propagate the counters: all BBs and edges'
200 // counters must have a value.
201 bool allCountersAreAssigned() const {
202 for (const auto &BBInfo : BBInfos)
203 if (!BBInfo.second.hasCount())
204 return false;
205 for (const auto &EdgeInfo : EdgeInfos)
206 if (!EdgeInfo.Count.has_value())
207 return false;
208 return true;
209 }
210
211 /// Check that all paths from the entry basic block that use edges with
212 /// non-zero counts arrive at a basic block with no successors (i.e. "exit")
213 bool allTakenPathsExit() const {
214 std::deque<const BasicBlock *> Worklist;
215 DenseSet<const BasicBlock *> Visited;
216 Worklist.push_back(x: &F.getEntryBlock());
217 bool HitExit = false;
218 while (!Worklist.empty()) {
219 const auto *BB = Worklist.front();
220 Worklist.pop_front();
221 if (!Visited.insert(V: BB).second)
222 continue;
223 if (succ_size(BB) == 0) {
224 if (isa<UnreachableInst>(Val: BB->getTerminator()))
225 return false;
226 HitExit = true;
227 continue;
228 }
229 if (succ_size(BB) == 1) {
230 Worklist.push_back(x: BB->getUniqueSuccessor());
231 continue;
232 }
233 const auto &BBInfo = getBBInfo(BB: *BB);
234 bool HasAWayOut = false;
235 for (auto I = 0U; I < BB->getTerminator()->getNumSuccessors(); ++I) {
236 const auto *Succ = BB->getTerminator()->getSuccessor(Idx: I);
237 if (!shouldExcludeEdge(Src: *BB, Dest: *Succ)) {
238 if (BBInfo.getEdgeCount(Index: I) > 0) {
239 HasAWayOut = true;
240 Worklist.push_back(x: Succ);
241 }
242 }
243 }
244 if (!HasAWayOut)
245 return false;
246 }
247 return HitExit;
248 }
249
250 bool allNonColdSelectsHaveProfile() const {
251 for (const auto &BB : F) {
252 if (getBBInfo(BB).getCount() > 0) {
253 for (const auto &I : BB) {
254 if (const auto *SI = dyn_cast<SelectInst>(Val: &I)) {
255 if (const auto *Inst = CtxProfAnalysis::getSelectInstrumentation(
256 SI&: *const_cast<SelectInst *>(SI))) {
257 auto Index = Inst->getIndex()->getZExtValue();
258 assert(Index < Counters.size());
259 if (Counters[Index] == 0)
260 return false;
261 }
262 }
263 }
264 }
265 }
266 return true;
267 }
268
269 // This is an adaptation of PGOUseFunc::populateCounters.
270 // FIXME(mtrofin): look into factoring the code to share one implementation.
271 void propagateCounterValues() {
272 bool KeepGoing = true;
273 while (KeepGoing) {
274 KeepGoing = false;
275 for (const auto &BB : F) {
276 auto &Info = getBBInfo(BB);
277 if (!Info.hasCount())
278 KeepGoing |= Info.tryTakeCountFromKnownOutEdges(BB) ||
279 Info.tryTakeCountFromKnownInEdges(BB);
280 if (Info.hasCount()) {
281 KeepGoing |= Info.trySetSingleUnknownOutEdgeCount();
282 KeepGoing |= Info.trySetSingleUnknownInEdgeCount();
283 }
284 }
285 }
286 assert(allCountersAreAssigned() &&
287 "[ctx-prof] Expected all counters have been assigned.");
288 assert(allTakenPathsExit() &&
289 "[ctx-prof] Encountered a BB with more than one successor, where "
290 "all outgoing edges have a 0 count. This occurs in non-exiting "
291 "functions (message pumps, usually) which are not supported in the "
292 "contextual profiling case");
293 assert(allNonColdSelectsHaveProfile() &&
294 "[ctx-prof] All non-cold select instructions were expected to have "
295 "a profile.");
296 }
297
298public:
299 ProfileAnnotatorImpl(const Function &F, ArrayRef<uint64_t> Counters)
300 : F(F), Counters(Counters) {
301 assert(!F.isDeclaration());
302 assert(!Counters.empty());
303 size_t NrEdges = 0;
304 for (const auto &BB : F) {
305 std::optional<uint64_t> Count;
306 if (auto *Ins = CtxProfAnalysis::getBBInstrumentation(
307 BB&: const_cast<BasicBlock &>(BB))) {
308 auto Index = Ins->getIndex()->getZExtValue();
309 assert(Index < Counters.size() &&
310 "The index must be inside the counters vector by construction - "
311 "tripping this assertion indicates a bug in how the contextual "
312 "profile is managed by IPO transforms");
313 (void)Index;
314 Count = Counters[Ins->getIndex()->getZExtValue()];
315 } else if (isa<UnreachableInst>(Val: BB.getTerminator())) {
316 // The program presumably didn't crash.
317 Count = 0;
318 }
319 auto [It, Ins] =
320 BBInfos.insert(x: {&BB, {pred_size(BB: &BB), succ_size(BB: &BB), Count}});
321 (void)Ins;
322 assert(Ins && "We iterate through the function's BBs, no reason to "
323 "insert one more than once");
324 NrEdges += llvm::count_if(Range: successors(BB: &BB), P: [&](const auto *Succ) {
325 return !shouldExcludeEdge(Src: BB, Dest: *Succ);
326 });
327 }
328 // Pre-allocate the vector, we want references to its contents to be stable.
329 EdgeInfos.reserve(n: NrEdges);
330 for (const auto &BB : F) {
331 auto &Info = getBBInfo(BB);
332 for (auto I = 0U; I < BB.getTerminator()->getNumSuccessors(); ++I) {
333 const auto *Succ = BB.getTerminator()->getSuccessor(Idx: I);
334 if (!shouldExcludeEdge(Src: BB, Dest: *Succ)) {
335 auto &EI = EdgeInfos.emplace_back(args&: getBBInfo(BB), args&: getBBInfo(BB: *Succ));
336 Info.addOutEdge(Index: I, Info&: EI);
337 getBBInfo(BB: *Succ).addInEdge(Info&: EI);
338 }
339 }
340 }
341 assert(EdgeInfos.capacity() == NrEdges &&
342 "The capacity of EdgeInfos should have stayed unchanged it was "
343 "populated, because we need pointers to its contents to be stable");
344 propagateCounterValues();
345 }
346
347 uint64_t getBBCount(const BasicBlock &BB) { return getBBInfo(BB).getCount(); }
348};
349
350} // namespace llvm
351
352ProfileAnnotator::ProfileAnnotator(const Function &F,
353 ArrayRef<uint64_t> RawCounters)
354 : PImpl(std::make_unique<ProfileAnnotatorImpl>(args: F, args&: RawCounters)) {}
355
356ProfileAnnotator::~ProfileAnnotator() = default;
357
358uint64_t ProfileAnnotator::getBBCount(const BasicBlock &BB) const {
359 return PImpl->getBBCount(BB);
360}
361
362bool ProfileAnnotator::getSelectInstrProfile(SelectInst &SI,
363 uint64_t &TrueCount,
364 uint64_t &FalseCount) const {
365 const auto &BBInfo = PImpl->getBBInfo(BB: *SI.getParent());
366 TrueCount = FalseCount = 0;
367 if (BBInfo.getCount() == 0)
368 return false;
369
370 auto *Step = CtxProfAnalysis::getSelectInstrumentation(SI);
371 if (!Step)
372 return false;
373 auto Index = Step->getIndex()->getZExtValue();
374 assert(Index < PImpl->Counters.size() &&
375 "The index of the step instruction must be inside the "
376 "counters vector by "
377 "construction - tripping this assertion indicates a bug in "
378 "how the contextual profile is managed by IPO transforms");
379 auto TotalCount = BBInfo.getCount();
380 TrueCount = PImpl->Counters[Index];
381 FalseCount = (TotalCount > TrueCount ? TotalCount - TrueCount : 0U);
382 return true;
383}
384
385bool ProfileAnnotator::getOutgoingBranchWeights(
386 BasicBlock &BB, SmallVectorImpl<uint64_t> &Profile,
387 uint64_t &MaxCount) const {
388 Profile.clear();
389
390 if (succ_size(BB: &BB) < 2)
391 return false;
392
393 auto *Term = BB.getTerminator();
394 Profile.resize(N: Term->getNumSuccessors());
395
396 const auto &BBInfo = PImpl->getBBInfo(BB);
397 MaxCount = 0;
398 for (unsigned SuccIdx = 0, Size = BBInfo.getNumOutEdges(); SuccIdx < Size;
399 ++SuccIdx) {
400 uint64_t EdgeCount = BBInfo.getEdgeCount(Index: SuccIdx);
401 if (EdgeCount > MaxCount)
402 MaxCount = EdgeCount;
403 Profile[SuccIdx] = EdgeCount;
404 }
405 return MaxCount > 0;
406}
407
408AnalysisKey CtxProfAnalysis::Key;
409
410CtxProfAnalysis::CtxProfAnalysis(std::optional<StringRef> Profile)
411 : Profile([&]() -> std::optional<StringRef> {
412 if (Profile)
413 return *Profile;
414 if (UseCtxProfile.getNumOccurrences())
415 return UseCtxProfile;
416 return std::nullopt;
417 }()) {}
418
419PGOContextualProfile CtxProfAnalysis::run(Module &M,
420 ModuleAnalysisManager &MAM) {
421 if (!Profile)
422 return {};
423 ErrorOr<std::unique_ptr<MemoryBuffer>> MB = MemoryBuffer::getFile(Filename: *Profile);
424 if (auto EC = MB.getError()) {
425 M.getContext().emitError(ErrorStr: "could not open contextual profile file: " +
426 EC.message());
427 return {};
428 }
429 PGOCtxProfileReader Reader(MB.get()->getBuffer());
430 auto MaybeProfiles = Reader.loadProfiles();
431 if (!MaybeProfiles) {
432 M.getContext().emitError(ErrorStr: "contextual profile file is invalid: " +
433 toString(E: MaybeProfiles.takeError()));
434 return {};
435 }
436
437 // FIXME: We should drive this from ThinLTO, but for the time being, use the
438 // module name as indicator.
439 // We want to *only* keep the contextual profiles in modules that capture
440 // context trees. That allows us to compute specific PSIs, for example.
441 auto DetermineRootsInModule = [&M]() -> const DenseSet<GlobalValue::GUID> {
442 DenseSet<GlobalValue::GUID> ProfileRootsInModule;
443 auto ModName = M.getName();
444 auto Filename = sys::path::filename(path: ModName);
445 // Drop the file extension.
446 Filename = Filename.substr(Start: 0, N: Filename.find_last_of(C: '.'));
447 // See if it parses
448 APInt Guid;
449 // getAsInteger returns true if there are more chars to read other than the
450 // integer. So the "false" test is what we want.
451 if (!Filename.getAsInteger(Radix: 0, Result&: Guid))
452 ProfileRootsInModule.insert(V: Guid.getZExtValue());
453 return ProfileRootsInModule;
454 };
455 const auto ProfileRootsInModule = DetermineRootsInModule();
456 PGOContextualProfile Result;
457 Result.IsInSpecializedModule =
458 valueOr(X: getAnalysisOptions(M).ctx_profile_force_is_specialized,
459 Default: !ProfileRootsInModule.empty());
460
461 // the logic from here on allows for modules that contain - by design - more
462 // than one root. We currently don't support that, because the determination
463 // happens based on the module name matching the root guid, but the logic can
464 // avoid assuming that.
465 if (!ProfileRootsInModule.empty()) {
466 // Trim first the roots that aren't in this module.
467 for (auto &[RootGuid, _] :
468 llvm::make_early_inc_range(Range&: MaybeProfiles->Contexts))
469 if (!ProfileRootsInModule.contains(V: RootGuid))
470 MaybeProfiles->Contexts.erase(x: RootGuid);
471 // we can also drop the flat profiles
472 MaybeProfiles->FlatProfiles.clear();
473 }
474
475 for (const auto &F : M) {
476 if (F.isDeclaration())
477 continue;
478 auto GUID = F.getGUID();
479 assert(GUID && "guid not found for defined function");
480 const auto &Entry = F.begin();
481 uint32_t MaxCounters = 0; // we expect at least a counter.
482 for (const auto &I : *Entry)
483 if (auto *C = dyn_cast<InstrProfIncrementInst>(Val: &I)) {
484 MaxCounters =
485 static_cast<uint32_t>(C->getNumCounters()->getZExtValue());
486 break;
487 }
488 if (!MaxCounters)
489 continue;
490 uint32_t MaxCallsites = 0;
491 for (const auto &BB : F)
492 for (const auto &I : BB)
493 if (auto *C = dyn_cast<InstrProfCallsite>(Val: &I)) {
494 MaxCallsites =
495 static_cast<uint32_t>(C->getNumCounters()->getZExtValue());
496 break;
497 }
498 auto [It, Ins] = Result.FuncInfo.insert(
499 x: {GUID, PGOContextualProfile::FunctionInfo(F.getName())});
500 (void)Ins;
501 assert(Ins);
502 It->second.NextCallsiteIndex = MaxCallsites;
503 It->second.NextCounterIndex = MaxCounters;
504 }
505 // If we made it this far, the Result is valid - which we mark by setting
506 // .Profiles.
507 Result.Profiles = std::move(*MaybeProfiles);
508 Result.initIndex();
509 return Result;
510}
511
512CtxProfAnalysisPrinterPass::CtxProfAnalysisPrinterPass(raw_ostream &OS)
513 : OS(OS) {}
514
515PreservedAnalyses CtxProfAnalysisPrinterPass::run(Module &M,
516 ModuleAnalysisManager &MAM) {
517 CtxProfAnalysis::Result &C = MAM.getResult<CtxProfAnalysis>(IR&: M);
518 if (C.contexts().empty()) {
519 OS << "No contextual profile was provided.\n";
520 return PreservedAnalyses::all();
521 }
522
523 const CtxProfPrintMode Mode = getAnalysisOptions(M).ctx_profile_printer_level;
524 if (Mode == CtxProfPrintMode::Everything) {
525 OS << "Function Info:\n";
526 for (const auto &[Guid, FuncInfo] : C.FuncInfo)
527 OS << Guid << " : " << FuncInfo.Name
528 << ". MaxCounterID: " << FuncInfo.NextCounterIndex
529 << ". MaxCallsiteID: " << FuncInfo.NextCallsiteIndex << "\n";
530 }
531
532 if (Mode == CtxProfPrintMode::Everything)
533 OS << "\nCurrent Profile:\n";
534 convertCtxProfToYaml(OS, Profile: C.profiles());
535 OS << "\n";
536 if (Mode == CtxProfPrintMode::YAML)
537 return PreservedAnalyses::all();
538
539 OS << "\nFlat Profile:\n";
540 auto Flat = C.flatten();
541 for (const auto &[Guid, Counters] : Flat) {
542 OS << Guid << " : ";
543 for (auto V : Counters)
544 OS << V << " ";
545 OS << "\n";
546 }
547 return PreservedAnalyses::all();
548}
549
550InstrProfCallsite *CtxProfAnalysis::getCallsiteInstrumentation(CallBase &CB) {
551 if (!InstrProfCallsite::canInstrumentCallsite(CB))
552 return nullptr;
553 for (auto *Prev = CB.getPrevNode(); Prev; Prev = Prev->getPrevNode()) {
554 if (auto *IPC = dyn_cast<InstrProfCallsite>(Val: Prev))
555 return IPC;
556 assert(!isa<CallBase>(Prev) &&
557 "didn't expect to find another call, that's not the callsite "
558 "instrumentation, before an instrumentable callsite");
559 }
560 return nullptr;
561}
562
563InstrProfIncrementInst *CtxProfAnalysis::getBBInstrumentation(BasicBlock &BB) {
564 for (auto &I : BB)
565 if (auto *Incr = dyn_cast<InstrProfIncrementInst>(Val: &I))
566 if (!isa<InstrProfIncrementInstStep>(Val: &I))
567 return Incr;
568 return nullptr;
569}
570
571InstrProfIncrementInstStep *
572CtxProfAnalysis::getSelectInstrumentation(SelectInst &SI) {
573 Instruction *Prev = &SI;
574 while ((Prev = Prev->getPrevNode()))
575 if (auto *Step = dyn_cast<InstrProfIncrementInstStep>(Val: Prev))
576 return Step;
577 return nullptr;
578}
579
580template <class ProfTy>
581static void preorderVisitOneRoot(ProfTy &Profile,
582 function_ref<void(ProfTy &)> Visitor) {
583 std::function<void(ProfTy &)> Traverser = [&](auto &Ctx) {
584 Visitor(Ctx);
585 for (auto &[_, SubCtxSet] : Ctx.callsites())
586 for (auto &[__, Subctx] : SubCtxSet)
587 Traverser(Subctx);
588 };
589 Traverser(Profile);
590}
591
592template <class ProfilesTy, class ProfTy>
593static void preorderVisit(ProfilesTy &Profiles,
594 function_ref<void(ProfTy &)> Visitor) {
595 for (auto &[_, P] : Profiles)
596 preorderVisitOneRoot<ProfTy>(P, Visitor);
597}
598
599void PGOContextualProfile::initIndex() {
600 // Initialize the head of the index list for each function. We don't need it
601 // after this point.
602 DenseMap<GlobalValue::GUID, PGOCtxProfContext *> InsertionPoints;
603 for (auto &[Guid, FI] : FuncInfo)
604 InsertionPoints[Guid] = &FI.Index;
605 preorderVisit<PGOCtxProfContext::CallTargetMapTy, PGOCtxProfContext>(
606 Profiles&: Profiles.Contexts, Visitor: [&](PGOCtxProfContext &Ctx) {
607 auto InsertIt = InsertionPoints.find(Val: Ctx.guid());
608 if (InsertIt == InsertionPoints.end())
609 return;
610 // Insert at the end of the list. Since we traverse in preorder, it
611 // means that when we iterate the list from the beginning, we'd
612 // encounter the contexts in the order we would have, should we have
613 // performed a full preorder traversal.
614 InsertIt->second->Next = &Ctx;
615 Ctx.Previous = InsertIt->second;
616 InsertIt->second = &Ctx;
617 });
618}
619
620bool PGOContextualProfile::isInSpecializedModule() const {
621 return IsInSpecializedModule;
622}
623
624void PGOContextualProfile::update(Visitor V, const Function &F) {
625 assert(isFunctionKnown(F));
626 GlobalValue::GUID G = F.getGUID();
627 for (auto *Node = FuncInfo.find(x: G)->second.Index.Next; Node;
628 Node = Node->Next)
629 V(*reinterpret_cast<PGOCtxProfContext *>(Node));
630}
631
632void PGOContextualProfile::visit(ConstVisitor V, const Function *F) const {
633 if (!F)
634 return preorderVisit<const PGOCtxProfContext::CallTargetMapTy,
635 const PGOCtxProfContext>(Profiles: Profiles.Contexts, Visitor: V);
636 assert(isFunctionKnown(*F));
637 GlobalValue::GUID G = F->getGUID();
638 for (const auto *Node = FuncInfo.find(x: G)->second.Index.Next; Node;
639 Node = Node->Next)
640 V(*reinterpret_cast<const PGOCtxProfContext *>(Node));
641}
642
643const CtxProfFlatProfile PGOContextualProfile::flatten() const {
644 CtxProfFlatProfile Flat;
645 auto Accummulate = [](SmallVectorImpl<uint64_t> &Into,
646 const SmallVectorImpl<uint64_t> &From,
647 uint64_t SamplingRate) {
648 if (Into.empty())
649 Into.resize(N: From.size());
650 assert(Into.size() == From.size() &&
651 "All contexts corresponding to a function should have the exact "
652 "same number of counters.");
653 for (size_t I = 0, E = Into.size(); I < E; ++I)
654 Into[I] += From[I] * SamplingRate;
655 };
656
657 for (const auto &[_, CtxRoot] : Profiles.Contexts) {
658 const uint64_t SamplingFactor = CtxRoot.getTotalRootEntryCount();
659 preorderVisitOneRoot<const PGOCtxProfContext>(
660 Profile: CtxRoot, Visitor: [&](const PGOCtxProfContext &Ctx) {
661 Accummulate(Flat[Ctx.guid()], Ctx.counters(), SamplingFactor);
662 });
663
664 for (const auto &[G, Unh] : CtxRoot.getUnhandled())
665 Accummulate(Flat[G], Unh, SamplingFactor);
666 }
667 // We don't sample "Flat" currently, so sampling rate is 1.
668 for (const auto &[G, FC] : Profiles.FlatProfiles)
669 Accummulate(Flat[G], FC, /*SamplingRate=*/1);
670 return Flat;
671}
672
673const CtxProfFlatIndirectCallProfile
674PGOContextualProfile::flattenVirtCalls() const {
675 CtxProfFlatIndirectCallProfile Ret;
676 for (const auto &[_, CtxRoot] : Profiles.Contexts) {
677 const uint64_t TotalRootEntryCount = CtxRoot.getTotalRootEntryCount();
678 preorderVisitOneRoot<const PGOCtxProfContext>(
679 Profile: CtxRoot, Visitor: [&](const PGOCtxProfContext &Ctx) {
680 auto &Targets = Ret[Ctx.guid()];
681 for (const auto &[ID, SubctxSet] : Ctx.callsites())
682 for (const auto &Subctx : SubctxSet)
683 Targets[ID][Subctx.first] +=
684 Subctx.second.getEntrycount() * TotalRootEntryCount;
685 });
686 }
687 return Ret;
688}
689
690void CtxProfAnalysis::collectIndirectCallPromotionList(
691 CallBase &IC, Result &Profile,
692 SetVector<std::pair<CallBase *, Function *>> &Candidates) {
693 const auto *Instr = CtxProfAnalysis::getCallsiteInstrumentation(CB&: IC);
694 if (!Instr)
695 return;
696 Module &M = *IC.getParent()->getModule();
697 const uint32_t CallID = Instr->getIndex()->getZExtValue();
698 Profile.visit(
699 V: [&](const PGOCtxProfContext &Ctx) {
700 const auto &Targets = Ctx.callsites().find(x: CallID);
701 if (Targets == Ctx.callsites().end())
702 return;
703 for (const auto &[Guid, _] : Targets->second)
704 if (auto Name = Profile.getFunctionName(GUID: Guid); !Name.empty())
705 if (auto *Target = M.getFunction(Name))
706 if (Target->hasFnAttribute(Kind: Attribute::AlwaysInline))
707 Candidates.insert(X: {&IC, Target});
708 },
709 F: IC.getCaller());
710}
711