| 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 | |
| 33 | using namespace llvm; |
| 34 | |
| 35 | namespace llvm { |
| 36 | |
| 37 | cl::opt<std::string> |
| 38 | UseCtxProfile("use-ctx-profile" , cl::init(Val: "" ), cl::Hidden, |
| 39 | cl::desc("Use the specified contextual profile file" )); |
| 40 | |
| 41 | class 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 | |
| 298 | public: |
| 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 | |
| 352 | ProfileAnnotator::ProfileAnnotator(const Function &F, |
| 353 | ArrayRef<uint64_t> RawCounters) |
| 354 | : PImpl(std::make_unique<ProfileAnnotatorImpl>(args: F, args&: RawCounters)) {} |
| 355 | |
| 356 | ProfileAnnotator::~ProfileAnnotator() = default; |
| 357 | |
| 358 | uint64_t ProfileAnnotator::getBBCount(const BasicBlock &BB) const { |
| 359 | return PImpl->getBBCount(BB); |
| 360 | } |
| 361 | |
| 362 | bool 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 | |
| 385 | bool 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 | |
| 408 | AnalysisKey CtxProfAnalysis::Key; |
| 409 | |
| 410 | CtxProfAnalysis::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 | |
| 419 | PGOContextualProfile 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 | |
| 512 | CtxProfAnalysisPrinterPass::CtxProfAnalysisPrinterPass(raw_ostream &OS) |
| 513 | : OS(OS) {} |
| 514 | |
| 515 | PreservedAnalyses 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 | |
| 550 | InstrProfCallsite *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 | |
| 563 | InstrProfIncrementInst *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 | |
| 571 | InstrProfIncrementInstStep * |
| 572 | CtxProfAnalysis::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 | |
| 580 | template <class ProfTy> |
| 581 | static 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 | |
| 592 | template <class ProfilesTy, class ProfTy> |
| 593 | static void preorderVisit(ProfilesTy &Profiles, |
| 594 | function_ref<void(ProfTy &)> Visitor) { |
| 595 | for (auto &[_, P] : Profiles) |
| 596 | preorderVisitOneRoot<ProfTy>(P, Visitor); |
| 597 | } |
| 598 | |
| 599 | void 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 | |
| 620 | bool PGOContextualProfile::isInSpecializedModule() const { |
| 621 | return IsInSpecializedModule; |
| 622 | } |
| 623 | |
| 624 | void 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 | |
| 632 | void 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 | |
| 643 | const 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 | |
| 673 | const CtxProfFlatIndirectCallProfile |
| 674 | PGOContextualProfile::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 | |
| 690 | void 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 | |