| 1 | //===- BlockFrequencyImplInfo.cpp - Block Frequency Info Implementation ---===// |
| 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 | // Loops should be simplified before this analysis. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "llvm/Analysis/BlockFrequencyInfoImpl.h" |
| 14 | #include "AnalysisOptions.h" |
| 15 | #include "llvm/ADT/MapVector.h" |
| 16 | #include "llvm/ADT/SCCIterator.h" |
| 17 | #include "llvm/ADT/SmallString.h" |
| 18 | #include "llvm/Config/llvm-config.h" |
| 19 | #include "llvm/IR/Function.h" |
| 20 | #include "llvm/Support/BlockFrequency.h" |
| 21 | #include "llvm/Support/BranchProbability.h" |
| 22 | #include "llvm/Support/Compiler.h" |
| 23 | #include "llvm/Support/Debug.h" |
| 24 | #include "llvm/Support/MathExtras.h" |
| 25 | #include "llvm/Support/ScaledNumber.h" |
| 26 | #include "llvm/Support/raw_ostream.h" |
| 27 | #include <algorithm> |
| 28 | #include <cassert> |
| 29 | #include <cstddef> |
| 30 | #include <cstdint> |
| 31 | #include <iterator> |
| 32 | #include <list> |
| 33 | #include <numeric> |
| 34 | #include <optional> |
| 35 | #include <utility> |
| 36 | #include <vector> |
| 37 | |
| 38 | using namespace llvm; |
| 39 | using namespace llvm::bfi_detail; |
| 40 | |
| 41 | #define DEBUG_TYPE "block-freq" |
| 42 | |
| 43 | namespace llvm { |
| 44 | cl::opt<bool> UseIterativeBFIInference( |
| 45 | "use-iterative-bfi-inference" , cl::Hidden, |
| 46 | cl::desc("Apply an iterative post-processing to infer correct BFI counts" )); |
| 47 | } // namespace llvm |
| 48 | |
| 49 | bool llvm::shouldCheckBFIUnknownBlockQueries(const LLVMContext &C) { |
| 50 | return getAnalysisOptions(C).check_bfi_unknown_block_queries; |
| 51 | } |
| 52 | unsigned llvm::getIterativeBFIMaxIterationsPerBlock(const LLVMContext &C) { |
| 53 | return getAnalysisOptions(C).iterative_bfi_max_iterations_per_block; |
| 54 | } |
| 55 | double llvm::getIterativeBFIPrecision(const LLVMContext &C) { |
| 56 | return getAnalysisOptions(C).iterative_bfi_precision; |
| 57 | } |
| 58 | |
| 59 | ScaledNumber<uint64_t> BlockMass::toScaled() const { |
| 60 | if (isFull()) |
| 61 | return ScaledNumber<uint64_t>(1, 0); |
| 62 | return ScaledNumber<uint64_t>(getMass() + 1, -64); |
| 63 | } |
| 64 | |
| 65 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 66 | LLVM_DUMP_METHOD void BlockMass::dump() const { print(dbgs()); } |
| 67 | #endif |
| 68 | |
| 69 | static char getHexDigit(int N) { |
| 70 | assert(N < 16); |
| 71 | if (N < 10) |
| 72 | return '0' + N; |
| 73 | return 'a' + N - 10; |
| 74 | } |
| 75 | |
| 76 | raw_ostream &BlockMass::print(raw_ostream &OS) const { |
| 77 | for (int Digits = 0; Digits < 16; ++Digits) |
| 78 | OS << getHexDigit(N: Mass >> (60 - Digits * 4) & 0xf); |
| 79 | return OS; |
| 80 | } |
| 81 | |
| 82 | namespace { |
| 83 | |
| 84 | using BlockNode = BlockFrequencyInfoImplBase::BlockNode; |
| 85 | using Distribution = BlockFrequencyInfoImplBase::Distribution; |
| 86 | using WeightList = BlockFrequencyInfoImplBase::Distribution::WeightList; |
| 87 | using Scaled64 = BlockFrequencyInfoImplBase::Scaled64; |
| 88 | using LoopData = BlockFrequencyInfoImplBase::LoopData; |
| 89 | using Weight = BlockFrequencyInfoImplBase::Weight; |
| 90 | using FrequencyData = BlockFrequencyInfoImplBase::FrequencyData; |
| 91 | |
| 92 | /// Dithering mass distributer. |
| 93 | /// |
| 94 | /// This class splits up a single mass into portions by weight, dithering to |
| 95 | /// spread out error. No mass is lost. The dithering precision depends on the |
| 96 | /// precision of the product of \a BlockMass and \a BranchProbability. |
| 97 | /// |
| 98 | /// The distribution algorithm follows. |
| 99 | /// |
| 100 | /// 1. Initialize by saving the sum of the weights in \a RemWeight and the |
| 101 | /// mass to distribute in \a RemMass. |
| 102 | /// |
| 103 | /// 2. For each portion: |
| 104 | /// |
| 105 | /// 1. Construct a branch probability, P, as the portion's weight divided |
| 106 | /// by the current value of \a RemWeight. |
| 107 | /// 2. Calculate the portion's mass as \a RemMass times P. |
| 108 | /// 3. Update \a RemWeight and \a RemMass at each portion by subtracting |
| 109 | /// the current portion's weight and mass. |
| 110 | struct DitheringDistributer { |
| 111 | uint32_t RemWeight; |
| 112 | BlockMass RemMass; |
| 113 | |
| 114 | DitheringDistributer(Distribution &Dist, const BlockMass &Mass); |
| 115 | |
| 116 | BlockMass takeMass(uint32_t Weight); |
| 117 | }; |
| 118 | |
| 119 | } // end anonymous namespace |
| 120 | |
| 121 | DitheringDistributer::DitheringDistributer(Distribution &Dist, |
| 122 | const BlockMass &Mass) { |
| 123 | Dist.normalize(); |
| 124 | RemWeight = Dist.Total; |
| 125 | RemMass = Mass; |
| 126 | } |
| 127 | |
| 128 | BlockMass DitheringDistributer::takeMass(uint32_t Weight) { |
| 129 | assert(Weight && "invalid weight" ); |
| 130 | assert(Weight <= RemWeight); |
| 131 | BlockMass Mass = RemMass * BranchProbability(Weight, RemWeight); |
| 132 | |
| 133 | // Decrement totals (dither). |
| 134 | RemWeight -= Weight; |
| 135 | RemMass -= Mass; |
| 136 | return Mass; |
| 137 | } |
| 138 | |
| 139 | void Distribution::add(const BlockNode &Node, uint64_t Amount, |
| 140 | Weight::DistType Type) { |
| 141 | assert(Amount && "invalid weight of 0" ); |
| 142 | uint64_t NewTotal = Total + Amount; |
| 143 | |
| 144 | // Check for overflow. It should be impossible to overflow twice. |
| 145 | bool IsOverflow = NewTotal < Total; |
| 146 | assert(!(DidOverflow && IsOverflow) && "unexpected repeated overflow" ); |
| 147 | DidOverflow |= IsOverflow; |
| 148 | |
| 149 | // Update the total. |
| 150 | Total = NewTotal; |
| 151 | |
| 152 | // Save the weight. |
| 153 | Weights.push_back(Elt: Weight(Type, Node, Amount)); |
| 154 | } |
| 155 | |
| 156 | static void combineWeight(Weight &W, const Weight &OtherW) { |
| 157 | assert(OtherW.TargetNode.isValid()); |
| 158 | if (!W.Amount) { |
| 159 | W = OtherW; |
| 160 | return; |
| 161 | } |
| 162 | assert(W.Type == OtherW.Type); |
| 163 | assert(W.TargetNode == OtherW.TargetNode); |
| 164 | assert(OtherW.Amount && "Expected non-zero weight" ); |
| 165 | if (W.Amount > W.Amount + OtherW.Amount) |
| 166 | // Saturate on overflow. |
| 167 | W.Amount = UINT64_MAX; |
| 168 | else |
| 169 | W.Amount += OtherW.Amount; |
| 170 | } |
| 171 | |
| 172 | static void combineWeightsBySorting(WeightList &Weights) { |
| 173 | // Sort so edges to the same node are adjacent. |
| 174 | llvm::sort(C&: Weights, Comp: [](const Weight &L, const Weight &R) { |
| 175 | return L.TargetNode < R.TargetNode; |
| 176 | }); |
| 177 | |
| 178 | // Combine adjacent edges. |
| 179 | WeightList::iterator O = Weights.begin(); |
| 180 | for (WeightList::const_iterator I = O, L = O, E = Weights.end(); I != E; |
| 181 | ++O, (I = L)) { |
| 182 | *O = *I; |
| 183 | |
| 184 | // Find the adjacent weights to the same node. |
| 185 | for (++L; L != E && I->TargetNode == L->TargetNode; ++L) |
| 186 | combineWeight(W&: *O, OtherW: *L); |
| 187 | } |
| 188 | |
| 189 | // Erase extra entries. |
| 190 | Weights.erase(CS: O, CE: Weights.end()); |
| 191 | } |
| 192 | |
| 193 | static void combineWeightsByHashing(WeightList &Weights) { |
| 194 | MapVector<BlockNode::IndexType, Weight> Combined; |
| 195 | Combined.reserve(NumEntries: Weights.size()); |
| 196 | for (const Weight &W : Weights) |
| 197 | combineWeight(W&: Combined[W.TargetNode.Index], OtherW: W); |
| 198 | |
| 199 | // Check whether anything changed. |
| 200 | if (Weights.size() == Combined.size()) |
| 201 | return; |
| 202 | |
| 203 | // Fill in the new weights. |
| 204 | Weights.clear(); |
| 205 | for (const auto &I : Combined) |
| 206 | Weights.push_back(Elt: I.second); |
| 207 | } |
| 208 | |
| 209 | static void combineWeights(WeightList &Weights) { |
| 210 | // Use a hash table for many successors to keep this linear. |
| 211 | if (Weights.size() > 128) { |
| 212 | combineWeightsByHashing(Weights); |
| 213 | return; |
| 214 | } |
| 215 | |
| 216 | combineWeightsBySorting(Weights); |
| 217 | } |
| 218 | |
| 219 | static uint64_t shiftRightAndRound(uint64_t N, int Shift) { |
| 220 | assert(Shift >= 0); |
| 221 | assert(Shift < 64); |
| 222 | if (!Shift) |
| 223 | return N; |
| 224 | return (N >> Shift) + (UINT64_C(1) & N >> (Shift - 1)); |
| 225 | } |
| 226 | |
| 227 | void Distribution::normalize() { |
| 228 | // Early exit for termination nodes. |
| 229 | if (Weights.empty()) |
| 230 | return; |
| 231 | |
| 232 | // Only bother if there are multiple successors. |
| 233 | if (Weights.size() > 1) |
| 234 | combineWeights(Weights); |
| 235 | |
| 236 | // Early exit when combined into a single successor. |
| 237 | if (Weights.size() == 1) { |
| 238 | Total = 1; |
| 239 | Weights.front().Amount = 1; |
| 240 | return; |
| 241 | } |
| 242 | |
| 243 | // Determine how much to shift right so that the total fits into 32-bits. |
| 244 | // |
| 245 | // If we shift at all, shift by 1 extra. Otherwise, the lower limit of 1 |
| 246 | // for each weight can cause a 32-bit overflow. |
| 247 | int Shift = 0; |
| 248 | if (DidOverflow) |
| 249 | Shift = 33; |
| 250 | else if (Total > UINT32_MAX) |
| 251 | Shift = 33 - llvm::countl_zero(Val: Total); |
| 252 | |
| 253 | // Early exit if nothing needs to be scaled. |
| 254 | if (!Shift) { |
| 255 | // If we didn't overflow then combineWeights() shouldn't have changed the |
| 256 | // sum of the weights, but let's double-check. |
| 257 | assert(Total == std::accumulate(Weights.begin(), Weights.end(), UINT64_C(0), |
| 258 | [](uint64_t Sum, const Weight &W) { |
| 259 | return Sum + W.Amount; |
| 260 | }) && |
| 261 | "Expected total to be correct" ); |
| 262 | return; |
| 263 | } |
| 264 | |
| 265 | // Recompute the total through accumulation (rather than shifting it) so that |
| 266 | // it's accurate after shifting and any changes combineWeights() made above. |
| 267 | Total = 0; |
| 268 | |
| 269 | // Sum the weights to each node and shift right if necessary. |
| 270 | for (Weight &W : Weights) { |
| 271 | // Scale down below UINT32_MAX. Since Shift is larger than necessary, we |
| 272 | // can round here without concern about overflow. |
| 273 | assert(W.TargetNode.isValid()); |
| 274 | W.Amount = std::max(UINT64_C(1), b: shiftRightAndRound(N: W.Amount, Shift)); |
| 275 | assert(W.Amount <= UINT32_MAX); |
| 276 | |
| 277 | // Update the total. |
| 278 | Total += W.Amount; |
| 279 | } |
| 280 | assert(Total <= UINT32_MAX); |
| 281 | } |
| 282 | |
| 283 | void BlockFrequencyInfoImplBase::clear() { |
| 284 | // Swap with a default-constructed std::vector, since std::vector<>::clear() |
| 285 | // does not actually clear heap storage. |
| 286 | std::vector<FrequencyData>().swap(x&: Freqs); |
| 287 | IsIrrLoopHeader.clear(); |
| 288 | std::vector<WorkingData>().swap(x&: Working); |
| 289 | Loops.clear(); |
| 290 | TopContainsIrreducible = false; |
| 291 | } |
| 292 | |
| 293 | /// Clear all memory not needed downstream. |
| 294 | /// |
| 295 | /// Releases all memory not used downstream. In particular, saves Freqs. |
| 296 | static void cleanup(BlockFrequencyInfoImplBase &BFI) { |
| 297 | std::vector<FrequencyData> SavedFreqs(std::move(BFI.Freqs)); |
| 298 | SparseBitVector<> (std::move(BFI.IsIrrLoopHeader)); |
| 299 | BFI.clear(); |
| 300 | BFI.Freqs = std::move(SavedFreqs); |
| 301 | BFI.IsIrrLoopHeader = std::move(SavedIsIrrLoopHeader); |
| 302 | } |
| 303 | |
| 304 | void BlockFrequencyInfoImplBase::addToDist(Distribution &Dist, |
| 305 | const LoopData *OuterLoop, |
| 306 | const BlockNode &Pred, |
| 307 | const BlockNode &Succ, |
| 308 | uint64_t Weight) { |
| 309 | if (!Weight) |
| 310 | Weight = 1; |
| 311 | |
| 312 | auto = [&OuterLoop](const BlockNode &Node) { |
| 313 | return OuterLoop && OuterLoop->isHeader(Node); |
| 314 | }; |
| 315 | |
| 316 | BlockNode Resolved = Working[Succ.Index].getResolvedNode(); |
| 317 | |
| 318 | #ifndef NDEBUG |
| 319 | auto debugSuccessor = [&](const char *Type) { |
| 320 | dbgs() << " =>" |
| 321 | << " [" << Type << "] weight = " << Weight; |
| 322 | if (!isLoopHeader(Resolved)) |
| 323 | dbgs() << ", succ = " << getBlockName(Succ); |
| 324 | dbgs() << ", pred = " << getBlockName(Pred); |
| 325 | if (Resolved != Succ) |
| 326 | dbgs() << ", resolved = " << getBlockName(Resolved); |
| 327 | dbgs() << "\n" ; |
| 328 | }; |
| 329 | (void)debugSuccessor; |
| 330 | #endif |
| 331 | |
| 332 | if (isLoopHeader(Resolved)) { |
| 333 | LLVM_DEBUG(debugSuccessor("backedge" )); |
| 334 | Dist.addBackedge(Node: Resolved, Amount: Weight); |
| 335 | return; |
| 336 | } |
| 337 | |
| 338 | if (Working[Resolved.Index].getContainingLoop() != OuterLoop) { |
| 339 | LLVM_DEBUG(debugSuccessor(" exit " )); |
| 340 | Dist.addExit(Node: Resolved, Amount: Weight); |
| 341 | return; |
| 342 | } |
| 343 | |
| 344 | // Every irreducible SCC is packaged before mass distribution and an |
| 345 | // irreducible package is solved rather than swept, so the only retreating |
| 346 | // edge left is the one to OuterLoop's header, handled above. |
| 347 | assert(Resolved >= Pred && "unhandled irreducible control flow" ); |
| 348 | |
| 349 | LLVM_DEBUG(debugSuccessor(" local " )); |
| 350 | Dist.addLocal(Node: Resolved, Amount: Weight); |
| 351 | } |
| 352 | |
| 353 | void BlockFrequencyInfoImplBase::addLoopSuccessorsToDist( |
| 354 | const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist) { |
| 355 | // Copy the exit map into Dist. |
| 356 | for (const auto &I : Loop.Exits) |
| 357 | addToDist(Dist, OuterLoop, Pred: Loop.getHeader(), Succ: I.first, Weight: I.second.getMass()); |
| 358 | } |
| 359 | |
| 360 | /// Compute the loop scale for a loop. |
| 361 | void BlockFrequencyInfoImplBase::computeLoopScale(LoopData &Loop) { |
| 362 | // Compute loop scale. |
| 363 | LLVM_DEBUG(dbgs() << "compute-loop-scale: " << getLoopName(Loop) << "\n" ); |
| 364 | |
| 365 | // Infinite loops need special handling. If we give the back edge an infinite |
| 366 | // mass, they may saturate all the other scales in the function down to 1, |
| 367 | // making all the other region temperatures look exactly the same. Choose an |
| 368 | // arbitrary scale to avoid these issues. |
| 369 | // |
| 370 | // FIXME: An alternate way would be to select a symbolic scale which is later |
| 371 | // replaced to be the maximum of all computed scales plus 1. This would |
| 372 | // appropriately describe the loop as having a large scale, without skewing |
| 373 | // the final frequency computation. |
| 374 | const Scaled64 InfiniteLoopScale(1, 12); |
| 375 | |
| 376 | // LoopScale == 1 / ExitMass |
| 377 | // ExitMass == HeadMass - BackedgeMass |
| 378 | BlockMass ExitMass = BlockMass::getFull() - Loop.BackedgeMass; |
| 379 | |
| 380 | // Block scale stores the inverse of the scale. If this is an infinite loop, |
| 381 | // its exit mass will be zero. In this case, use an arbitrary scale for the |
| 382 | // loop scale. |
| 383 | Loop.Scale = |
| 384 | ExitMass.isEmpty() ? InfiniteLoopScale : ExitMass.toScaled().inverse(); |
| 385 | |
| 386 | LLVM_DEBUG(dbgs() << " - exit-mass = " << ExitMass << " (" |
| 387 | << BlockMass::getFull() << " - " << Loop.BackedgeMass |
| 388 | << ")\n" |
| 389 | << " - scale = " << Loop.Scale << "\n" ); |
| 390 | } |
| 391 | |
| 392 | /// Package up a loop. |
| 393 | void BlockFrequencyInfoImplBase::packageLoop(LoopData &Loop) { |
| 394 | LLVM_DEBUG(dbgs() << "packaging-loop: " << getLoopName(Loop) << "\n" ); |
| 395 | |
| 396 | // Clear the subloop exits to prevent quadratic memory usage. |
| 397 | for (const BlockNode &M : Loop.Nodes) { |
| 398 | if (auto *Loop = Working[M.Index].getPackagedLoop()) |
| 399 | Loop->Exits.clear(); |
| 400 | LLVM_DEBUG(dbgs() << " - node: " << getBlockName(M.Index) << "\n" ); |
| 401 | } |
| 402 | Loop.IsPackaged = true; |
| 403 | } |
| 404 | |
| 405 | #ifndef NDEBUG |
| 406 | static void debugAssign(const BlockFrequencyInfoImplBase &BFI, |
| 407 | const DitheringDistributer &D, const BlockNode &T, |
| 408 | const BlockMass &M, const char *Desc) { |
| 409 | dbgs() << " => assign " << M << " (" << D.RemMass << ")" ; |
| 410 | if (Desc) |
| 411 | dbgs() << " [" << Desc << "]" ; |
| 412 | if (T.isValid()) |
| 413 | dbgs() << " to " << BFI.getBlockName(T); |
| 414 | dbgs() << "\n" ; |
| 415 | } |
| 416 | #endif |
| 417 | |
| 418 | void BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source, |
| 419 | LoopData *OuterLoop, |
| 420 | Distribution &Dist) { |
| 421 | BlockMass Mass = Working[Source.Index].getMass(); |
| 422 | LLVM_DEBUG(dbgs() << " => mass: " << Mass << "\n" ); |
| 423 | |
| 424 | // Distribute mass to successors as laid out in Dist. |
| 425 | DitheringDistributer D(Dist, Mass); |
| 426 | |
| 427 | for (const Weight &W : Dist.Weights) { |
| 428 | // Check for a local edge (non-backedge and non-exit). |
| 429 | BlockMass Taken = D.takeMass(Weight: W.Amount); |
| 430 | if (W.Type == Weight::Local) { |
| 431 | Working[W.TargetNode.Index].getMass() += Taken; |
| 432 | LLVM_DEBUG(debugAssign(*this, D, W.TargetNode, Taken, nullptr)); |
| 433 | continue; |
| 434 | } |
| 435 | |
| 436 | // Backedges and exits only make sense if we're processing a loop. |
| 437 | assert(OuterLoop && "backedge or exit outside of loop" ); |
| 438 | |
| 439 | // Check for a backedge. |
| 440 | if (W.Type == Weight::Backedge) { |
| 441 | OuterLoop->BackedgeMass += Taken; |
| 442 | LLVM_DEBUG(debugAssign(*this, D, W.TargetNode, Taken, "back" )); |
| 443 | continue; |
| 444 | } |
| 445 | |
| 446 | // This must be an exit. |
| 447 | assert(W.Type == Weight::Exit); |
| 448 | OuterLoop->Exits.push_back(Elt: std::make_pair(x: W.TargetNode, y&: Taken)); |
| 449 | LLVM_DEBUG(debugAssign(*this, D, W.TargetNode, Taken, "exit" )); |
| 450 | } |
| 451 | } |
| 452 | |
| 453 | static void convertFloatingToInteger(BlockFrequencyInfoImplBase &BFI) { |
| 454 | auto Max = Scaled64::getZero(); |
| 455 | for (const FrequencyData &F : BFI.Freqs) |
| 456 | Max = std::max(a: Max, b: F.Scaled); |
| 457 | |
| 458 | // Scale the Factor to a size that creates integers. If possible scale |
| 459 | // integers so that Max == UINT64_MAX so that they can be best differentiated. |
| 460 | // It is possible that the range between min and max cannot be accurately |
| 461 | // represented in a 64bit integer without either loosing precision for small |
| 462 | // values (so small unequal numbers all map to 1) or saturaturing big numbers |
| 463 | // loosing precision for big numbers (so unequal big numbers may map to |
| 464 | // UINT64_MAX). We choose to loose precision for small numbers. |
| 465 | const unsigned MaxBits = sizeof(Scaled64::DigitsType) * CHAR_BIT; |
| 466 | // Users often add up multiple BlockFrequency values or multiply them with |
| 467 | // things like instruction costs. Leave some room to avoid saturating |
| 468 | // operations reaching UIN64_MAX too early. |
| 469 | const unsigned Slack = 10; |
| 470 | Scaled64 ScalingFactor = Scaled64(1, MaxBits - Slack) / Max; |
| 471 | |
| 472 | // Translate the floats to integers. |
| 473 | LLVM_DEBUG({ |
| 474 | auto Min = Scaled64::getLargest(); |
| 475 | for (const FrequencyData &F : BFI.Freqs) |
| 476 | Min = std::min(Min, F.Scaled); |
| 477 | dbgs() << "float-to-int: min = " << Min << ", max = " << Max |
| 478 | << ", factor = " << ScalingFactor << "\n" ; |
| 479 | }); |
| 480 | for (size_t Index = 0; Index < BFI.Freqs.size(); ++Index) { |
| 481 | Scaled64 Scaled = BFI.Freqs[Index].Scaled * ScalingFactor; |
| 482 | BFI.Freqs[Index].Integer = std::max(UINT64_C(1), b: Scaled.toInt<uint64_t>()); |
| 483 | LLVM_DEBUG(dbgs() << " - " << BFI.getBlockName(Index) << ": float = " |
| 484 | << BFI.Freqs[Index].Scaled << ", scaled = " << Scaled |
| 485 | << ", int = " << BFI.Freqs[Index].Integer << "\n" ); |
| 486 | } |
| 487 | } |
| 488 | |
| 489 | /// Unwrap a loop package. |
| 490 | /// |
| 491 | /// Visits all the members of a loop, adjusting their BlockData according to |
| 492 | /// the loop's pseudo-node. |
| 493 | static void unwrapLoop(BlockFrequencyInfoImplBase &BFI, LoopData &Loop) { |
| 494 | LLVM_DEBUG(dbgs() << "unwrap-loop-package: " << BFI.getLoopName(Loop) |
| 495 | << ": mass = " << Loop.Mass << ", scale = " << Loop.Scale |
| 496 | << "\n" ); |
| 497 | Loop.Scale *= Loop.Mass.toScaled(); |
| 498 | Loop.IsPackaged = false; |
| 499 | LLVM_DEBUG(dbgs() << " => combined-scale = " << Loop.Scale << "\n" ); |
| 500 | |
| 501 | // Propagate the head scale through the loop. Since members are visited in |
| 502 | // RPO, the head scale will be updated by the loop scale first, and then the |
| 503 | // final head scale will be used for updated the rest of the members. |
| 504 | for (const BlockNode &N : Loop.Nodes) { |
| 505 | const auto &Working = BFI.Working[N.Index]; |
| 506 | Scaled64 &F = Working.isAPackage() ? Working.getPackagedLoop()->Scale |
| 507 | : BFI.Freqs[N.Index].Scaled; |
| 508 | Scaled64 New = Loop.Scale * F; |
| 509 | LLVM_DEBUG(dbgs() << " - " << BFI.getBlockName(N) << ": " << F << " => " |
| 510 | << New << "\n" ); |
| 511 | F = New; |
| 512 | } |
| 513 | } |
| 514 | |
| 515 | void BlockFrequencyInfoImplBase::unwrapLoops() { |
| 516 | // Set initial frequencies from loop-local masses. |
| 517 | for (size_t Index = 0; Index < Working.size(); ++Index) |
| 518 | Freqs[Index].Scaled = Working[Index].Mass.toScaled(); |
| 519 | |
| 520 | for (LoopData &Loop : Loops) |
| 521 | unwrapLoop(BFI&: *this, Loop); |
| 522 | } |
| 523 | |
| 524 | void BlockFrequencyInfoImplBase::finalizeMetrics() { |
| 525 | // Convert to integers. |
| 526 | convertFloatingToInteger(BFI&: *this); |
| 527 | |
| 528 | // Clean up data structures. |
| 529 | cleanup(BFI&: *this); |
| 530 | |
| 531 | // Print out the final stats. |
| 532 | LLVM_DEBUG(dump()); |
| 533 | } |
| 534 | |
| 535 | BlockFrequency |
| 536 | BlockFrequencyInfoImplBase::getBlockFreq(const BlockNode &Node) const { |
| 537 | if (!Node.isValid()) { |
| 538 | #ifndef NDEBUG |
| 539 | if (CheckUnknownBlockQueries) { |
| 540 | SmallString<256> Msg; |
| 541 | raw_svector_ostream OS(Msg); |
| 542 | OS << "*** Detected BFI query for unknown block " << getBlockName(Node); |
| 543 | report_fatal_error(OS.str()); |
| 544 | } |
| 545 | #endif |
| 546 | return BlockFrequency(0); |
| 547 | } |
| 548 | return BlockFrequency(Freqs[Node.Index].Integer); |
| 549 | } |
| 550 | |
| 551 | std::optional<uint64_t> |
| 552 | BlockFrequencyInfoImplBase::getBlockProfileCount(const Function &F, |
| 553 | const BlockNode &Node) const { |
| 554 | return getProfileCountFromFreq(F, Freq: getBlockFreq(Node)); |
| 555 | } |
| 556 | |
| 557 | std::optional<uint64_t> |
| 558 | BlockFrequencyInfoImplBase::getProfileCountFromFreq(const Function &F, |
| 559 | BlockFrequency Freq) const { |
| 560 | auto EntryCount = F.getEntryCount(); |
| 561 | if (!EntryCount) |
| 562 | return std::nullopt; |
| 563 | return mulDivNearest(X: *EntryCount, Y: Freq.getFrequency(), |
| 564 | Z: getEntryFreq().getFrequency()); |
| 565 | } |
| 566 | |
| 567 | bool |
| 568 | BlockFrequencyInfoImplBase::(const BlockNode &Node) { |
| 569 | if (!Node.isValid()) |
| 570 | return false; |
| 571 | return IsIrrLoopHeader.test(Idx: Node.Index); |
| 572 | } |
| 573 | |
| 574 | Scaled64 |
| 575 | BlockFrequencyInfoImplBase::getFloatingBlockFreq(const BlockNode &Node) const { |
| 576 | if (!Node.isValid()) |
| 577 | return Scaled64::getZero(); |
| 578 | return Freqs[Node.Index].Scaled; |
| 579 | } |
| 580 | |
| 581 | void BlockFrequencyInfoImplBase::setBlockFreq(const BlockNode &Node, |
| 582 | BlockFrequency Freq) { |
| 583 | assert(Node.isValid() && "Expected valid node" ); |
| 584 | assert(Node.Index < Freqs.size() && "Expected legal index" ); |
| 585 | Freqs[Node.Index].Integer = Freq.getFrequency(); |
| 586 | } |
| 587 | |
| 588 | std::string |
| 589 | BlockFrequencyInfoImplBase::getBlockName(const BlockNode &Node) const { |
| 590 | return {}; |
| 591 | } |
| 592 | |
| 593 | std::string |
| 594 | BlockFrequencyInfoImplBase::getLoopName(const LoopData &Loop) const { |
| 595 | return getBlockName(Node: Loop.getHeader()) + (Loop.isIrreducible() ? "**" : "*" ); |
| 596 | } |
| 597 | |
| 598 | void IrreducibleGraph::addNodesInLoop(const BFIBase::LoopData &OuterLoop) { |
| 599 | Start = OuterLoop.getHeader(); |
| 600 | Nodes.reserve(n: OuterLoop.Nodes.size()); |
| 601 | for (auto N : OuterLoop.Nodes) |
| 602 | addNode(Node: N); |
| 603 | indexNodes(); |
| 604 | } |
| 605 | |
| 606 | void IrreducibleGraph::addNodesInFunction() { |
| 607 | Start = 0; |
| 608 | for (uint32_t Index = 0; Index < BFI.Working.size(); ++Index) |
| 609 | if (!BFI.Working[Index].isPackaged()) |
| 610 | addNode(Node: Index); |
| 611 | indexNodes(); |
| 612 | } |
| 613 | |
| 614 | void IrreducibleGraph::indexNodes() { |
| 615 | for (auto &I : Nodes) |
| 616 | Lookup[I.Node.Index] = &I; |
| 617 | } |
| 618 | |
| 619 | void IrreducibleGraph::addEdge(IrrNode &Irr, const BlockNode &Succ, |
| 620 | const BFIBase::LoopData *OuterLoop) { |
| 621 | if (OuterLoop && OuterLoop->isHeader(Node: Succ)) |
| 622 | return; |
| 623 | auto L = Lookup.find(Val: Succ.Index); |
| 624 | if (L == Lookup.end()) |
| 625 | return; |
| 626 | IrrNode &SuccIrr = *L->second; |
| 627 | Irr.Succs.push_back(Elt: &SuccIrr); |
| 628 | } |
| 629 | |
| 630 | namespace llvm { |
| 631 | |
| 632 | template <> struct GraphTraits<IrreducibleGraph> { |
| 633 | using GraphT = bfi_detail::IrreducibleGraph; |
| 634 | using NodeRef = const GraphT::IrrNode *; |
| 635 | using ChildIteratorType = GraphT::IrrNode::iterator; |
| 636 | |
| 637 | static NodeRef getEntryNode(const GraphT &G) { return G.StartIrr; } |
| 638 | static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } |
| 639 | static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } |
| 640 | }; |
| 641 | |
| 642 | } // end namespace llvm |
| 643 | |
| 644 | /// Package \c SCC into a loop represented by its lowest-RPO member. |
| 645 | static void |
| 646 | createIrreducibleLoop(BlockFrequencyInfoImplBase &BFI, |
| 647 | const IrreducibleGraph &G, LoopData *OuterLoop, |
| 648 | std::list<LoopData>::iterator Insert, |
| 649 | ArrayRef<const IrreducibleGraph::IrrNode *> SCC, |
| 650 | const BitVector &IsEntry, const BitVector &) { |
| 651 | LLVM_DEBUG(dbgs() << " - found-scc\n" ); |
| 652 | |
| 653 | // One representative, not a header set: solving the SCC makes the entries' |
| 654 | // relative frequencies fall out of the solve rather than out of an assumed |
| 655 | // split. Take the lowest RPO node so the choice is deterministic. |
| 656 | LoopData::NodeList Members; |
| 657 | Members.reserve(N: SCC.size()); |
| 658 | for (const auto *I : SCC) { |
| 659 | Members.push_back(Elt: I->Node); |
| 660 | // The package no longer distinguishes headers; the marking stays because |
| 661 | // PGOInstrumentation places counters on isIrrLoopHeader(). |
| 662 | bool = IsEntry.test(Idx: G.getIndex(N: I)) || Extra.test(Idx: G.getIndex(N: I)); |
| 663 | if (Header) |
| 664 | BFI.IsIrrLoopHeader.set(I->Node.Index); |
| 665 | LLVM_DEBUG(dbgs() << (Header ? " => header = " : " => member = " ) |
| 666 | << BFI.getBlockName(I->Node) << "\n" ); |
| 667 | } |
| 668 | llvm::sort(C&: Members); |
| 669 | |
| 670 | auto Loop = BFI.Loops.emplace(position: Insert, args&: OuterLoop, args: std::move(Members)); |
| 671 | |
| 672 | // Update loop hierarchy. |
| 673 | for (const auto &N : Loop->Nodes) |
| 674 | if (BFI.Working[N.Index].isLoopHeader()) |
| 675 | BFI.Working[N.Index].Loop->Parent = &*Loop; |
| 676 | else |
| 677 | BFI.Working[N.Index].Loop = &*Loop; |
| 678 | } |
| 679 | |
| 680 | iterator_range<std::list<LoopData>::iterator> |
| 681 | BlockFrequencyInfoImplBase::analyzeIrreducible( |
| 682 | const IrreducibleGraph &G, LoopData *OuterLoop, |
| 683 | std::list<LoopData>::iterator Insert) { |
| 684 | assert((OuterLoop == nullptr) == (Insert == Loops.begin())); |
| 685 | auto Prev = OuterLoop ? std::prev(x: Insert) : Loops.end(); |
| 686 | |
| 687 | // Number every node's SCC, as the sweeps below compare an edge's two ends. |
| 688 | // Only multi-node SCCs become loops, so keep just their members. |
| 689 | SmallVector<unsigned> SccId(G.Nodes.size(), ~0u); |
| 690 | SmallVector<SmallVector<const IrreducibleGraph::IrrNode *>> SCCs; |
| 691 | unsigned Id = 0; |
| 692 | for (auto I = scc_begin(G); !I.isAtEnd(); ++I, ++Id) { |
| 693 | for (const auto *N : *I) |
| 694 | SccId[G.getIndex(N)] = Id; |
| 695 | if (I->size() >= 2) |
| 696 | SCCs.emplace_back(Args: I->begin(), Args: I->end()); |
| 697 | } |
| 698 | |
| 699 | // A node is an entry if an edge from another SCC reaches it, and an extra |
| 700 | // header if a backedge within its SCC targets it. Backedges from entries |
| 701 | // can have inverted ordering, so they do not make a header. Mass no longer |
| 702 | // depends on this split; it only decides isIrrLoopHeader(). |
| 703 | BitVector IsEntry(G.Nodes.size()); |
| 704 | BitVector (G.Nodes.size()); |
| 705 | for (const auto &U : G.Nodes) |
| 706 | for (const auto *V : U.Succs) |
| 707 | if (SccId[G.getIndex(N: &U)] != SccId[G.getIndex(N: V)]) |
| 708 | IsEntry.set(G.getIndex(N: V)); |
| 709 | for (const auto &U : G.Nodes) { |
| 710 | if (IsEntry.test(Idx: G.getIndex(N: &U))) |
| 711 | continue; |
| 712 | for (const auto *V : U.Succs) |
| 713 | if (SccId[G.getIndex(N: V)] == SccId[G.getIndex(N: &U)] && !(U.Node < V->Node)) |
| 714 | Extra.set(G.getIndex(N: V)); |
| 715 | } |
| 716 | |
| 717 | for (const auto &SCC : SCCs) |
| 718 | createIrreducibleLoop(BFI&: *this, G, OuterLoop, Insert, SCC, IsEntry, Extra); |
| 719 | |
| 720 | if (OuterLoop) |
| 721 | return make_range(x: std::next(x: Prev), y: Insert); |
| 722 | return make_range(x: Loops.begin(), y: Insert); |
| 723 | } |
| 724 | |