1 //==- BlockFrequencyInfoImpl.h - Block Frequency Implementation --*- 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 // Shared implementation of BlockFrequency for IR and Machine Instructions. 10 // See the documentation below for BlockFrequencyInfoImpl for details. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H 15 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H 16 17 #include "llvm/ADT/BitVector.h" 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/DenseSet.h" 20 #include "llvm/ADT/GraphTraits.h" 21 #include "llvm/ADT/PostOrderIterator.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/ADT/SparseBitVector.h" 25 #include "llvm/ADT/Twine.h" 26 #include "llvm/ADT/iterator_range.h" 27 #include "llvm/IR/BasicBlock.h" 28 #include "llvm/IR/Function.h" 29 #include "llvm/IR/ValueHandle.h" 30 #include "llvm/Support/BlockFrequency.h" 31 #include "llvm/Support/BranchProbability.h" 32 #include "llvm/Support/CommandLine.h" 33 #include "llvm/Support/DOTGraphTraits.h" 34 #include "llvm/Support/Debug.h" 35 #include "llvm/Support/Format.h" 36 #include "llvm/Support/ScaledNumber.h" 37 #include "llvm/Support/raw_ostream.h" 38 #include <algorithm> 39 #include <cassert> 40 #include <cstddef> 41 #include <cstdint> 42 #include <deque> 43 #include <iterator> 44 #include <limits> 45 #include <list> 46 #include <optional> 47 #include <queue> 48 #include <string> 49 #include <utility> 50 #include <vector> 51 52 #define DEBUG_TYPE "block-freq" 53 54 namespace llvm { 55 extern llvm::cl::opt<bool> CheckBFIUnknownBlockQueries; 56 57 extern llvm::cl::opt<bool> UseIterativeBFIInference; 58 extern llvm::cl::opt<unsigned> IterativeBFIMaxIterationsPerBlock; 59 extern llvm::cl::opt<double> IterativeBFIPrecision; 60 61 class BranchProbabilityInfo; 62 class Function; 63 class Loop; 64 class LoopInfo; 65 class MachineBasicBlock; 66 class MachineBranchProbabilityInfo; 67 class MachineFunction; 68 class MachineLoop; 69 class MachineLoopInfo; 70 71 namespace bfi_detail { 72 73 struct IrreducibleGraph; 74 75 // This is part of a workaround for a GCC 4.7 crash on lambdas. 76 template <class BT> struct BlockEdgesAdder; 77 78 /// Mass of a block. 79 /// 80 /// This class implements a sort of fixed-point fraction always between 0.0 and 81 /// 1.0. getMass() == std::numeric_limits<uint64_t>::max() indicates a value of 82 /// 1.0. 83 /// 84 /// Masses can be added and subtracted. Simple saturation arithmetic is used, 85 /// so arithmetic operations never overflow or underflow. 86 /// 87 /// Masses can be multiplied. Multiplication treats full mass as 1.0 and uses 88 /// an inexpensive floating-point algorithm that's off-by-one (almost, but not 89 /// quite, maximum precision). 90 /// 91 /// Masses can be scaled by \a BranchProbability at maximum precision. 92 class BlockMass { 93 uint64_t Mass = 0; 94 95 public: 96 BlockMass() = default; 97 explicit BlockMass(uint64_t Mass) : Mass(Mass) {} 98 99 static BlockMass getEmpty() { return BlockMass(); } 100 101 static BlockMass getFull() { 102 return BlockMass(std::numeric_limits<uint64_t>::max()); 103 } 104 105 uint64_t getMass() const { return Mass; } 106 107 bool isFull() const { return Mass == std::numeric_limits<uint64_t>::max(); } 108 bool isEmpty() const { return !Mass; } 109 110 bool operator!() const { return isEmpty(); } 111 112 /// Add another mass. 113 /// 114 /// Adds another mass, saturating at \a isFull() rather than overflowing. 115 BlockMass &operator+=(BlockMass X) { 116 uint64_t Sum = Mass + X.Mass; 117 Mass = Sum < Mass ? std::numeric_limits<uint64_t>::max() : Sum; 118 return *this; 119 } 120 121 /// Subtract another mass. 122 /// 123 /// Subtracts another mass, saturating at \a isEmpty() rather than 124 /// undeflowing. 125 BlockMass &operator-=(BlockMass X) { 126 uint64_t Diff = Mass - X.Mass; 127 Mass = Diff > Mass ? 0 : Diff; 128 return *this; 129 } 130 131 BlockMass &operator*=(BranchProbability P) { 132 Mass = P.scale(Mass); 133 return *this; 134 } 135 136 bool operator==(BlockMass X) const { return Mass == X.Mass; } 137 bool operator!=(BlockMass X) const { return Mass != X.Mass; } 138 bool operator<=(BlockMass X) const { return Mass <= X.Mass; } 139 bool operator>=(BlockMass X) const { return Mass >= X.Mass; } 140 bool operator<(BlockMass X) const { return Mass < X.Mass; } 141 bool operator>(BlockMass X) const { return Mass > X.Mass; } 142 143 /// Convert to scaled number. 144 /// 145 /// Convert to \a ScaledNumber. \a isFull() gives 1.0, while \a isEmpty() 146 /// gives slightly above 0.0. 147 ScaledNumber<uint64_t> toScaled() const; 148 149 void dump() const; 150 raw_ostream &print(raw_ostream &OS) const; 151 }; 152 153 inline BlockMass operator+(BlockMass L, BlockMass R) { 154 return BlockMass(L) += R; 155 } 156 inline BlockMass operator-(BlockMass L, BlockMass R) { 157 return BlockMass(L) -= R; 158 } 159 inline BlockMass operator*(BlockMass L, BranchProbability R) { 160 return BlockMass(L) *= R; 161 } 162 inline BlockMass operator*(BranchProbability L, BlockMass R) { 163 return BlockMass(R) *= L; 164 } 165 166 inline raw_ostream &operator<<(raw_ostream &OS, BlockMass X) { 167 return X.print(OS); 168 } 169 170 } // end namespace bfi_detail 171 172 /// Base class for BlockFrequencyInfoImpl 173 /// 174 /// BlockFrequencyInfoImplBase has supporting data structures and some 175 /// algorithms for BlockFrequencyInfoImplBase. Only algorithms that depend on 176 /// the block type (or that call such algorithms) are skipped here. 177 /// 178 /// Nevertheless, the majority of the overall algorithm documentation lives with 179 /// BlockFrequencyInfoImpl. See there for details. 180 class BlockFrequencyInfoImplBase { 181 public: 182 using Scaled64 = ScaledNumber<uint64_t>; 183 using BlockMass = bfi_detail::BlockMass; 184 185 /// Representative of a block. 186 /// 187 /// This is a simple wrapper around an index into the reverse-post-order 188 /// traversal of the blocks. 189 /// 190 /// Unlike a block pointer, its order has meaning (location in the 191 /// topological sort) and it's class is the same regardless of block type. 192 struct BlockNode { 193 using IndexType = uint32_t; 194 195 IndexType Index; 196 197 BlockNode() : Index(std::numeric_limits<uint32_t>::max()) {} 198 BlockNode(IndexType Index) : Index(Index) {} 199 200 bool operator==(const BlockNode &X) const { return Index == X.Index; } 201 bool operator!=(const BlockNode &X) const { return Index != X.Index; } 202 bool operator<=(const BlockNode &X) const { return Index <= X.Index; } 203 bool operator>=(const BlockNode &X) const { return Index >= X.Index; } 204 bool operator<(const BlockNode &X) const { return Index < X.Index; } 205 bool operator>(const BlockNode &X) const { return Index > X.Index; } 206 207 bool isValid() const { return Index <= getMaxIndex(); } 208 209 static size_t getMaxIndex() { 210 return std::numeric_limits<uint32_t>::max() - 1; 211 } 212 }; 213 214 /// Stats about a block itself. 215 struct FrequencyData { 216 Scaled64 Scaled; 217 uint64_t Integer; 218 }; 219 220 /// Data about a loop. 221 /// 222 /// Contains the data necessary to represent a loop as a pseudo-node once it's 223 /// packaged. 224 struct LoopData { 225 using ExitMap = SmallVector<std::pair<BlockNode, BlockMass>, 4>; 226 using NodeList = SmallVector<BlockNode, 4>; 227 using HeaderMassList = SmallVector<BlockMass, 1>; 228 229 LoopData *Parent; ///< The parent loop. 230 bool IsPackaged = false; ///< Whether this has been packaged. 231 uint32_t NumHeaders = 1; ///< Number of headers. 232 ExitMap Exits; ///< Successor edges (and weights). 233 NodeList Nodes; ///< Header and the members of the loop. 234 HeaderMassList BackedgeMass; ///< Mass returned to each loop header. 235 BlockMass Mass; 236 Scaled64 Scale; 237 238 LoopData(LoopData *Parent, const BlockNode &Header) 239 : Parent(Parent), Nodes(1, Header), BackedgeMass(1) {} 240 241 template <class It1, class It2> 242 LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther, 243 It2 LastOther) 244 : Parent(Parent), Nodes(FirstHeader, LastHeader) { 245 NumHeaders = Nodes.size(); 246 Nodes.insert(Nodes.end(), FirstOther, LastOther); 247 BackedgeMass.resize(NumHeaders); 248 } 249 250 bool isHeader(const BlockNode &Node) const { 251 if (isIrreducible()) 252 return std::binary_search(Nodes.begin(), Nodes.begin() + NumHeaders, 253 Node); 254 return Node == Nodes[0]; 255 } 256 257 BlockNode getHeader() const { return Nodes[0]; } 258 bool isIrreducible() const { return NumHeaders > 1; } 259 260 HeaderMassList::difference_type getHeaderIndex(const BlockNode &B) { 261 assert(isHeader(B) && "this is only valid on loop header blocks"); 262 if (isIrreducible()) 263 return std::lower_bound(Nodes.begin(), Nodes.begin() + NumHeaders, B) - 264 Nodes.begin(); 265 return 0; 266 } 267 268 NodeList::const_iterator members_begin() const { 269 return Nodes.begin() + NumHeaders; 270 } 271 272 NodeList::const_iterator members_end() const { return Nodes.end(); } 273 iterator_range<NodeList::const_iterator> members() const { 274 return make_range(members_begin(), members_end()); 275 } 276 }; 277 278 /// Index of loop information. 279 struct WorkingData { 280 BlockNode Node; ///< This node. 281 LoopData *Loop = nullptr; ///< The loop this block is inside. 282 BlockMass Mass; ///< Mass distribution from the entry block. 283 284 WorkingData(const BlockNode &Node) : Node(Node) {} 285 286 bool isLoopHeader() const { return Loop && Loop->isHeader(Node); } 287 288 bool isDoubleLoopHeader() const { 289 return isLoopHeader() && Loop->Parent && Loop->Parent->isIrreducible() && 290 Loop->Parent->isHeader(Node); 291 } 292 293 LoopData *getContainingLoop() const { 294 if (!isLoopHeader()) 295 return Loop; 296 if (!isDoubleLoopHeader()) 297 return Loop->Parent; 298 return Loop->Parent->Parent; 299 } 300 301 /// Resolve a node to its representative. 302 /// 303 /// Get the node currently representing Node, which could be a containing 304 /// loop. 305 /// 306 /// This function should only be called when distributing mass. As long as 307 /// there are no irreducible edges to Node, then it will have complexity 308 /// O(1) in this context. 309 /// 310 /// In general, the complexity is O(L), where L is the number of loop 311 /// headers Node has been packaged into. Since this method is called in 312 /// the context of distributing mass, L will be the number of loop headers 313 /// an early exit edge jumps out of. 314 BlockNode getResolvedNode() const { 315 auto *L = getPackagedLoop(); 316 return L ? L->getHeader() : Node; 317 } 318 319 LoopData *getPackagedLoop() const { 320 if (!Loop || !Loop->IsPackaged) 321 return nullptr; 322 auto *L = Loop; 323 while (L->Parent && L->Parent->IsPackaged) 324 L = L->Parent; 325 return L; 326 } 327 328 /// Get the appropriate mass for a node. 329 /// 330 /// Get appropriate mass for Node. If Node is a loop-header (whose loop 331 /// has been packaged), returns the mass of its pseudo-node. If it's a 332 /// node inside a packaged loop, it returns the loop's mass. 333 BlockMass &getMass() { 334 if (!isAPackage()) 335 return Mass; 336 if (!isADoublePackage()) 337 return Loop->Mass; 338 return Loop->Parent->Mass; 339 } 340 341 /// Has ContainingLoop been packaged up? 342 bool isPackaged() const { return getResolvedNode() != Node; } 343 344 /// Has Loop been packaged up? 345 bool isAPackage() const { return isLoopHeader() && Loop->IsPackaged; } 346 347 /// Has Loop been packaged up twice? 348 bool isADoublePackage() const { 349 return isDoubleLoopHeader() && Loop->Parent->IsPackaged; 350 } 351 }; 352 353 /// Unscaled probability weight. 354 /// 355 /// Probability weight for an edge in the graph (including the 356 /// successor/target node). 357 /// 358 /// All edges in the original function are 32-bit. However, exit edges from 359 /// loop packages are taken from 64-bit exit masses, so we need 64-bits of 360 /// space in general. 361 /// 362 /// In addition to the raw weight amount, Weight stores the type of the edge 363 /// in the current context (i.e., the context of the loop being processed). 364 /// Is this a local edge within the loop, an exit from the loop, or a 365 /// backedge to the loop header? 366 struct Weight { 367 enum DistType { Local, Exit, Backedge }; 368 DistType Type = Local; 369 BlockNode TargetNode; 370 uint64_t Amount = 0; 371 372 Weight() = default; 373 Weight(DistType Type, BlockNode TargetNode, uint64_t Amount) 374 : Type(Type), TargetNode(TargetNode), Amount(Amount) {} 375 }; 376 377 /// Distribution of unscaled probability weight. 378 /// 379 /// Distribution of unscaled probability weight to a set of successors. 380 /// 381 /// This class collates the successor edge weights for later processing. 382 /// 383 /// \a DidOverflow indicates whether \a Total did overflow while adding to 384 /// the distribution. It should never overflow twice. 385 struct Distribution { 386 using WeightList = SmallVector<Weight, 4>; 387 388 WeightList Weights; ///< Individual successor weights. 389 uint64_t Total = 0; ///< Sum of all weights. 390 bool DidOverflow = false; ///< Whether \a Total did overflow. 391 392 Distribution() = default; 393 394 void addLocal(const BlockNode &Node, uint64_t Amount) { 395 add(Node, Amount, Weight::Local); 396 } 397 398 void addExit(const BlockNode &Node, uint64_t Amount) { 399 add(Node, Amount, Weight::Exit); 400 } 401 402 void addBackedge(const BlockNode &Node, uint64_t Amount) { 403 add(Node, Amount, Weight::Backedge); 404 } 405 406 /// Normalize the distribution. 407 /// 408 /// Combines multiple edges to the same \a Weight::TargetNode and scales 409 /// down so that \a Total fits into 32-bits. 410 /// 411 /// This is linear in the size of \a Weights. For the vast majority of 412 /// cases, adjacent edge weights are combined by sorting WeightList and 413 /// combining adjacent weights. However, for very large edge lists an 414 /// auxiliary hash table is used. 415 void normalize(); 416 417 private: 418 void add(const BlockNode &Node, uint64_t Amount, Weight::DistType Type); 419 }; 420 421 /// Data about each block. This is used downstream. 422 std::vector<FrequencyData> Freqs; 423 424 /// Whether each block is an irreducible loop header. 425 /// This is used downstream. 426 SparseBitVector<> IsIrrLoopHeader; 427 428 /// Loop data: see initializeLoops(). 429 std::vector<WorkingData> Working; 430 431 /// Indexed information about loops. 432 std::list<LoopData> Loops; 433 434 /// Virtual destructor. 435 /// 436 /// Need a virtual destructor to mask the compiler warning about 437 /// getBlockName(). 438 virtual ~BlockFrequencyInfoImplBase() = default; 439 440 /// Add all edges out of a packaged loop to the distribution. 441 /// 442 /// Adds all edges from LocalLoopHead to Dist. Calls addToDist() to add each 443 /// successor edge. 444 /// 445 /// \return \c true unless there's an irreducible backedge. 446 bool addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop, 447 Distribution &Dist); 448 449 /// Add an edge to the distribution. 450 /// 451 /// Adds an edge to Succ to Dist. If \c LoopHead.isValid(), then whether the 452 /// edge is local/exit/backedge is in the context of LoopHead. Otherwise, 453 /// every edge should be a local edge (since all the loops are packaged up). 454 /// 455 /// \return \c true unless aborted due to an irreducible backedge. 456 bool addToDist(Distribution &Dist, const LoopData *OuterLoop, 457 const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight); 458 459 /// Analyze irreducible SCCs. 460 /// 461 /// Separate irreducible SCCs from \c G, which is an explicit graph of \c 462 /// OuterLoop (or the top-level function, if \c OuterLoop is \c nullptr). 463 /// Insert them into \a Loops before \c Insert. 464 /// 465 /// \return the \c LoopData nodes representing the irreducible SCCs. 466 iterator_range<std::list<LoopData>::iterator> 467 analyzeIrreducible(const bfi_detail::IrreducibleGraph &G, LoopData *OuterLoop, 468 std::list<LoopData>::iterator Insert); 469 470 /// Update a loop after packaging irreducible SCCs inside of it. 471 /// 472 /// Update \c OuterLoop. Before finding irreducible control flow, it was 473 /// partway through \a computeMassInLoop(), so \a LoopData::Exits and \a 474 /// LoopData::BackedgeMass need to be reset. Also, nodes that were packaged 475 /// up need to be removed from \a OuterLoop::Nodes. 476 void updateLoopWithIrreducible(LoopData &OuterLoop); 477 478 /// Distribute mass according to a distribution. 479 /// 480 /// Distributes the mass in Source according to Dist. If LoopHead.isValid(), 481 /// backedges and exits are stored in its entry in Loops. 482 /// 483 /// Mass is distributed in parallel from two copies of the source mass. 484 void distributeMass(const BlockNode &Source, LoopData *OuterLoop, 485 Distribution &Dist); 486 487 /// Compute the loop scale for a loop. 488 void computeLoopScale(LoopData &Loop); 489 490 /// Adjust the mass of all headers in an irreducible loop. 491 /// 492 /// Initially, irreducible loops are assumed to distribute their mass 493 /// equally among its headers. This can lead to wrong frequency estimates 494 /// since some headers may be executed more frequently than others. 495 /// 496 /// This adjusts header mass distribution so it matches the weights of 497 /// the backedges going into each of the loop headers. 498 void adjustLoopHeaderMass(LoopData &Loop); 499 500 void distributeIrrLoopHeaderMass(Distribution &Dist); 501 502 /// Package up a loop. 503 void packageLoop(LoopData &Loop); 504 505 /// Unwrap loops. 506 void unwrapLoops(); 507 508 /// Finalize frequency metrics. 509 /// 510 /// Calculates final frequencies and cleans up no-longer-needed data 511 /// structures. 512 void finalizeMetrics(); 513 514 /// Clear all memory. 515 void clear(); 516 517 virtual std::string getBlockName(const BlockNode &Node) const; 518 std::string getLoopName(const LoopData &Loop) const; 519 520 virtual raw_ostream &print(raw_ostream &OS) const { return OS; } 521 void dump() const { print(dbgs()); } 522 523 Scaled64 getFloatingBlockFreq(const BlockNode &Node) const; 524 525 BlockFrequency getBlockFreq(const BlockNode &Node) const; 526 std::optional<uint64_t> 527 getBlockProfileCount(const Function &F, const BlockNode &Node, 528 bool AllowSynthetic = false) const; 529 std::optional<uint64_t> 530 getProfileCountFromFreq(const Function &F, uint64_t Freq, 531 bool AllowSynthetic = false) const; 532 bool isIrrLoopHeader(const BlockNode &Node); 533 534 void setBlockFreq(const BlockNode &Node, uint64_t Freq); 535 536 raw_ostream &printBlockFreq(raw_ostream &OS, const BlockNode &Node) const; 537 raw_ostream &printBlockFreq(raw_ostream &OS, 538 const BlockFrequency &Freq) const; 539 540 uint64_t getEntryFreq() const { 541 assert(!Freqs.empty()); 542 return Freqs[0].Integer; 543 } 544 }; 545 546 namespace bfi_detail { 547 548 template <class BlockT> struct TypeMap {}; 549 template <> struct TypeMap<BasicBlock> { 550 using BlockT = BasicBlock; 551 using BlockKeyT = AssertingVH<const BasicBlock>; 552 using FunctionT = Function; 553 using BranchProbabilityInfoT = BranchProbabilityInfo; 554 using LoopT = Loop; 555 using LoopInfoT = LoopInfo; 556 }; 557 template <> struct TypeMap<MachineBasicBlock> { 558 using BlockT = MachineBasicBlock; 559 using BlockKeyT = const MachineBasicBlock *; 560 using FunctionT = MachineFunction; 561 using BranchProbabilityInfoT = MachineBranchProbabilityInfo; 562 using LoopT = MachineLoop; 563 using LoopInfoT = MachineLoopInfo; 564 }; 565 566 template <class BlockT, class BFIImplT> 567 class BFICallbackVH; 568 569 /// Get the name of a MachineBasicBlock. 570 /// 571 /// Get the name of a MachineBasicBlock. It's templated so that including from 572 /// CodeGen is unnecessary (that would be a layering issue). 573 /// 574 /// This is used mainly for debug output. The name is similar to 575 /// MachineBasicBlock::getFullName(), but skips the name of the function. 576 template <class BlockT> std::string getBlockName(const BlockT *BB) { 577 assert(BB && "Unexpected nullptr"); 578 auto MachineName = "BB" + Twine(BB->getNumber()); 579 if (BB->getBasicBlock()) 580 return (MachineName + "[" + BB->getName() + "]").str(); 581 return MachineName.str(); 582 } 583 /// Get the name of a BasicBlock. 584 template <> inline std::string getBlockName(const BasicBlock *BB) { 585 assert(BB && "Unexpected nullptr"); 586 return BB->getName().str(); 587 } 588 589 /// Graph of irreducible control flow. 590 /// 591 /// This graph is used for determining the SCCs in a loop (or top-level 592 /// function) that has irreducible control flow. 593 /// 594 /// During the block frequency algorithm, the local graphs are defined in a 595 /// light-weight way, deferring to the \a BasicBlock or \a MachineBasicBlock 596 /// graphs for most edges, but getting others from \a LoopData::ExitMap. The 597 /// latter only has successor information. 598 /// 599 /// \a IrreducibleGraph makes this graph explicit. It's in a form that can use 600 /// \a GraphTraits (so that \a analyzeIrreducible() can use \a scc_iterator), 601 /// and it explicitly lists predecessors and successors. The initialization 602 /// that relies on \c MachineBasicBlock is defined in the header. 603 struct IrreducibleGraph { 604 using BFIBase = BlockFrequencyInfoImplBase; 605 606 BFIBase &BFI; 607 608 using BlockNode = BFIBase::BlockNode; 609 struct IrrNode { 610 BlockNode Node; 611 unsigned NumIn = 0; 612 std::deque<const IrrNode *> Edges; 613 614 IrrNode(const BlockNode &Node) : Node(Node) {} 615 616 using iterator = std::deque<const IrrNode *>::const_iterator; 617 618 iterator pred_begin() const { return Edges.begin(); } 619 iterator succ_begin() const { return Edges.begin() + NumIn; } 620 iterator pred_end() const { return succ_begin(); } 621 iterator succ_end() const { return Edges.end(); } 622 }; 623 BlockNode Start; 624 const IrrNode *StartIrr = nullptr; 625 std::vector<IrrNode> Nodes; 626 SmallDenseMap<uint32_t, IrrNode *, 4> Lookup; 627 628 /// Construct an explicit graph containing irreducible control flow. 629 /// 630 /// Construct an explicit graph of the control flow in \c OuterLoop (or the 631 /// top-level function, if \c OuterLoop is \c nullptr). Uses \c 632 /// addBlockEdges to add block successors that have not been packaged into 633 /// loops. 634 /// 635 /// \a BlockFrequencyInfoImpl::computeIrreducibleMass() is the only expected 636 /// user of this. 637 template <class BlockEdgesAdder> 638 IrreducibleGraph(BFIBase &BFI, const BFIBase::LoopData *OuterLoop, 639 BlockEdgesAdder addBlockEdges) : BFI(BFI) { 640 initialize(OuterLoop, addBlockEdges); 641 } 642 643 template <class BlockEdgesAdder> 644 void initialize(const BFIBase::LoopData *OuterLoop, 645 BlockEdgesAdder addBlockEdges); 646 void addNodesInLoop(const BFIBase::LoopData &OuterLoop); 647 void addNodesInFunction(); 648 649 void addNode(const BlockNode &Node) { 650 Nodes.emplace_back(Node); 651 BFI.Working[Node.Index].getMass() = BlockMass::getEmpty(); 652 } 653 654 void indexNodes(); 655 template <class BlockEdgesAdder> 656 void addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop, 657 BlockEdgesAdder addBlockEdges); 658 void addEdge(IrrNode &Irr, const BlockNode &Succ, 659 const BFIBase::LoopData *OuterLoop); 660 }; 661 662 template <class BlockEdgesAdder> 663 void IrreducibleGraph::initialize(const BFIBase::LoopData *OuterLoop, 664 BlockEdgesAdder addBlockEdges) { 665 if (OuterLoop) { 666 addNodesInLoop(*OuterLoop); 667 for (auto N : OuterLoop->Nodes) 668 addEdges(N, OuterLoop, addBlockEdges); 669 } else { 670 addNodesInFunction(); 671 for (uint32_t Index = 0; Index < BFI.Working.size(); ++Index) 672 addEdges(Index, OuterLoop, addBlockEdges); 673 } 674 StartIrr = Lookup[Start.Index]; 675 } 676 677 template <class BlockEdgesAdder> 678 void IrreducibleGraph::addEdges(const BlockNode &Node, 679 const BFIBase::LoopData *OuterLoop, 680 BlockEdgesAdder addBlockEdges) { 681 auto L = Lookup.find(Node.Index); 682 if (L == Lookup.end()) 683 return; 684 IrrNode &Irr = *L->second; 685 const auto &Working = BFI.Working[Node.Index]; 686 687 if (Working.isAPackage()) 688 for (const auto &I : Working.Loop->Exits) 689 addEdge(Irr, I.first, OuterLoop); 690 else 691 addBlockEdges(*this, Irr, OuterLoop); 692 } 693 694 } // end namespace bfi_detail 695 696 /// Shared implementation for block frequency analysis. 697 /// 698 /// This is a shared implementation of BlockFrequencyInfo and 699 /// MachineBlockFrequencyInfo, and calculates the relative frequencies of 700 /// blocks. 701 /// 702 /// LoopInfo defines a loop as a "non-trivial" SCC dominated by a single block, 703 /// which is called the header. A given loop, L, can have sub-loops, which are 704 /// loops within the subgraph of L that exclude its header. (A "trivial" SCC 705 /// consists of a single block that does not have a self-edge.) 706 /// 707 /// In addition to loops, this algorithm has limited support for irreducible 708 /// SCCs, which are SCCs with multiple entry blocks. Irreducible SCCs are 709 /// discovered on the fly, and modelled as loops with multiple headers. 710 /// 711 /// The headers of irreducible sub-SCCs consist of its entry blocks and all 712 /// nodes that are targets of a backedge within it (excluding backedges within 713 /// true sub-loops). Block frequency calculations act as if a block is 714 /// inserted that intercepts all the edges to the headers. All backedges and 715 /// entries point to this block. Its successors are the headers, which split 716 /// the frequency evenly. 717 /// 718 /// This algorithm leverages BlockMass and ScaledNumber to maintain precision, 719 /// separates mass distribution from loop scaling, and dithers to eliminate 720 /// probability mass loss. 721 /// 722 /// The implementation is split between BlockFrequencyInfoImpl, which knows the 723 /// type of graph being modelled (BasicBlock vs. MachineBasicBlock), and 724 /// BlockFrequencyInfoImplBase, which doesn't. The base class uses \a 725 /// BlockNode, a wrapper around a uint32_t. BlockNode is numbered from 0 in 726 /// reverse-post order. This gives two advantages: it's easy to compare the 727 /// relative ordering of two nodes, and maps keyed on BlockT can be represented 728 /// by vectors. 729 /// 730 /// This algorithm is O(V+E), unless there is irreducible control flow, in 731 /// which case it's O(V*E) in the worst case. 732 /// 733 /// These are the main stages: 734 /// 735 /// 0. Reverse post-order traversal (\a initializeRPOT()). 736 /// 737 /// Run a single post-order traversal and save it (in reverse) in RPOT. 738 /// All other stages make use of this ordering. Save a lookup from BlockT 739 /// to BlockNode (the index into RPOT) in Nodes. 740 /// 741 /// 1. Loop initialization (\a initializeLoops()). 742 /// 743 /// Translate LoopInfo/MachineLoopInfo into a form suitable for the rest of 744 /// the algorithm. In particular, store the immediate members of each loop 745 /// in reverse post-order. 746 /// 747 /// 2. Calculate mass and scale in loops (\a computeMassInLoops()). 748 /// 749 /// For each loop (bottom-up), distribute mass through the DAG resulting 750 /// from ignoring backedges and treating sub-loops as a single pseudo-node. 751 /// Track the backedge mass distributed to the loop header, and use it to 752 /// calculate the loop scale (number of loop iterations). Immediate 753 /// members that represent sub-loops will already have been visited and 754 /// packaged into a pseudo-node. 755 /// 756 /// Distributing mass in a loop is a reverse-post-order traversal through 757 /// the loop. Start by assigning full mass to the Loop header. For each 758 /// node in the loop: 759 /// 760 /// - Fetch and categorize the weight distribution for its successors. 761 /// If this is a packaged-subloop, the weight distribution is stored 762 /// in \a LoopData::Exits. Otherwise, fetch it from 763 /// BranchProbabilityInfo. 764 /// 765 /// - Each successor is categorized as \a Weight::Local, a local edge 766 /// within the current loop, \a Weight::Backedge, a backedge to the 767 /// loop header, or \a Weight::Exit, any successor outside the loop. 768 /// The weight, the successor, and its category are stored in \a 769 /// Distribution. There can be multiple edges to each successor. 770 /// 771 /// - If there's a backedge to a non-header, there's an irreducible SCC. 772 /// The usual flow is temporarily aborted. \a 773 /// computeIrreducibleMass() finds the irreducible SCCs within the 774 /// loop, packages them up, and restarts the flow. 775 /// 776 /// - Normalize the distribution: scale weights down so that their sum 777 /// is 32-bits, and coalesce multiple edges to the same node. 778 /// 779 /// - Distribute the mass accordingly, dithering to minimize mass loss, 780 /// as described in \a distributeMass(). 781 /// 782 /// In the case of irreducible loops, instead of a single loop header, 783 /// there will be several. The computation of backedge masses is similar 784 /// but instead of having a single backedge mass, there will be one 785 /// backedge per loop header. In these cases, each backedge will carry 786 /// a mass proportional to the edge weights along the corresponding 787 /// path. 788 /// 789 /// At the end of propagation, the full mass assigned to the loop will be 790 /// distributed among the loop headers proportionally according to the 791 /// mass flowing through their backedges. 792 /// 793 /// Finally, calculate the loop scale from the accumulated backedge mass. 794 /// 795 /// 3. Distribute mass in the function (\a computeMassInFunction()). 796 /// 797 /// Finally, distribute mass through the DAG resulting from packaging all 798 /// loops in the function. This uses the same algorithm as distributing 799 /// mass in a loop, except that there are no exit or backedge edges. 800 /// 801 /// 4. Unpackage loops (\a unwrapLoops()). 802 /// 803 /// Initialize each block's frequency to a floating point representation of 804 /// its mass. 805 /// 806 /// Visit loops top-down, scaling the frequencies of its immediate members 807 /// by the loop's pseudo-node's frequency. 808 /// 809 /// 5. Convert frequencies to a 64-bit range (\a finalizeMetrics()). 810 /// 811 /// Using the min and max frequencies as a guide, translate floating point 812 /// frequencies to an appropriate range in uint64_t. 813 /// 814 /// It has some known flaws. 815 /// 816 /// - The model of irreducible control flow is a rough approximation. 817 /// 818 /// Modelling irreducible control flow exactly involves setting up and 819 /// solving a group of infinite geometric series. Such precision is 820 /// unlikely to be worthwhile, since most of our algorithms give up on 821 /// irreducible control flow anyway. 822 /// 823 /// Nevertheless, we might find that we need to get closer. Here's a sort 824 /// of TODO list for the model with diminishing returns, to be completed as 825 /// necessary. 826 /// 827 /// - The headers for the \a LoopData representing an irreducible SCC 828 /// include non-entry blocks. When these extra blocks exist, they 829 /// indicate a self-contained irreducible sub-SCC. We could treat them 830 /// as sub-loops, rather than arbitrarily shoving the problematic 831 /// blocks into the headers of the main irreducible SCC. 832 /// 833 /// - Entry frequencies are assumed to be evenly split between the 834 /// headers of a given irreducible SCC, which is the only option if we 835 /// need to compute mass in the SCC before its parent loop. Instead, 836 /// we could partially compute mass in the parent loop, and stop when 837 /// we get to the SCC. Here, we have the correct ratio of entry 838 /// masses, which we can use to adjust their relative frequencies. 839 /// Compute mass in the SCC, and then continue propagation in the 840 /// parent. 841 /// 842 /// - We can propagate mass iteratively through the SCC, for some fixed 843 /// number of iterations. Each iteration starts by assigning the entry 844 /// blocks their backedge mass from the prior iteration. The final 845 /// mass for each block (and each exit, and the total backedge mass 846 /// used for computing loop scale) is the sum of all iterations. 847 /// (Running this until fixed point would "solve" the geometric 848 /// series by simulation.) 849 template <class BT> class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { 850 // This is part of a workaround for a GCC 4.7 crash on lambdas. 851 friend struct bfi_detail::BlockEdgesAdder<BT>; 852 853 using BlockT = typename bfi_detail::TypeMap<BT>::BlockT; 854 using BlockKeyT = typename bfi_detail::TypeMap<BT>::BlockKeyT; 855 using FunctionT = typename bfi_detail::TypeMap<BT>::FunctionT; 856 using BranchProbabilityInfoT = 857 typename bfi_detail::TypeMap<BT>::BranchProbabilityInfoT; 858 using LoopT = typename bfi_detail::TypeMap<BT>::LoopT; 859 using LoopInfoT = typename bfi_detail::TypeMap<BT>::LoopInfoT; 860 using Successor = GraphTraits<const BlockT *>; 861 using Predecessor = GraphTraits<Inverse<const BlockT *>>; 862 using BFICallbackVH = 863 bfi_detail::BFICallbackVH<BlockT, BlockFrequencyInfoImpl>; 864 865 const BranchProbabilityInfoT *BPI = nullptr; 866 const LoopInfoT *LI = nullptr; 867 const FunctionT *F = nullptr; 868 869 // All blocks in reverse postorder. 870 std::vector<const BlockT *> RPOT; 871 DenseMap<BlockKeyT, std::pair<BlockNode, BFICallbackVH>> Nodes; 872 873 using rpot_iterator = typename std::vector<const BlockT *>::const_iterator; 874 875 rpot_iterator rpot_begin() const { return RPOT.begin(); } 876 rpot_iterator rpot_end() const { return RPOT.end(); } 877 878 size_t getIndex(const rpot_iterator &I) const { return I - rpot_begin(); } 879 880 BlockNode getNode(const rpot_iterator &I) const { 881 return BlockNode(getIndex(I)); 882 } 883 884 BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB).first; } 885 886 const BlockT *getBlock(const BlockNode &Node) const { 887 assert(Node.Index < RPOT.size()); 888 return RPOT[Node.Index]; 889 } 890 891 /// Run (and save) a post-order traversal. 892 /// 893 /// Saves a reverse post-order traversal of all the nodes in \a F. 894 void initializeRPOT(); 895 896 /// Initialize loop data. 897 /// 898 /// Build up \a Loops using \a LoopInfo. \a LoopInfo gives us a mapping from 899 /// each block to the deepest loop it's in, but we need the inverse. For each 900 /// loop, we store in reverse post-order its "immediate" members, defined as 901 /// the header, the headers of immediate sub-loops, and all other blocks in 902 /// the loop that are not in sub-loops. 903 void initializeLoops(); 904 905 /// Propagate to a block's successors. 906 /// 907 /// In the context of distributing mass through \c OuterLoop, divide the mass 908 /// currently assigned to \c Node between its successors. 909 /// 910 /// \return \c true unless there's an irreducible backedge. 911 bool propagateMassToSuccessors(LoopData *OuterLoop, const BlockNode &Node); 912 913 /// Compute mass in a particular loop. 914 /// 915 /// Assign mass to \c Loop's header, and then for each block in \c Loop in 916 /// reverse post-order, distribute mass to its successors. Only visits nodes 917 /// that have not been packaged into sub-loops. 918 /// 919 /// \pre \a computeMassInLoop() has been called for each subloop of \c Loop. 920 /// \return \c true unless there's an irreducible backedge. 921 bool computeMassInLoop(LoopData &Loop); 922 923 /// Try to compute mass in the top-level function. 924 /// 925 /// Assign mass to the entry block, and then for each block in reverse 926 /// post-order, distribute mass to its successors. Skips nodes that have 927 /// been packaged into loops. 928 /// 929 /// \pre \a computeMassInLoops() has been called. 930 /// \return \c true unless there's an irreducible backedge. 931 bool tryToComputeMassInFunction(); 932 933 /// Compute mass in (and package up) irreducible SCCs. 934 /// 935 /// Find the irreducible SCCs in \c OuterLoop, add them to \a Loops (in front 936 /// of \c Insert), and call \a computeMassInLoop() on each of them. 937 /// 938 /// If \c OuterLoop is \c nullptr, it refers to the top-level function. 939 /// 940 /// \pre \a computeMassInLoop() has been called for each subloop of \c 941 /// OuterLoop. 942 /// \pre \c Insert points at the last loop successfully processed by \a 943 /// computeMassInLoop(). 944 /// \pre \c OuterLoop has irreducible SCCs. 945 void computeIrreducibleMass(LoopData *OuterLoop, 946 std::list<LoopData>::iterator Insert); 947 948 /// Compute mass in all loops. 949 /// 950 /// For each loop bottom-up, call \a computeMassInLoop(). 951 /// 952 /// \a computeMassInLoop() aborts (and returns \c false) on loops that 953 /// contain a irreducible sub-SCCs. Use \a computeIrreducibleMass() and then 954 /// re-enter \a computeMassInLoop(). 955 /// 956 /// \post \a computeMassInLoop() has returned \c true for every loop. 957 void computeMassInLoops(); 958 959 /// Compute mass in the top-level function. 960 /// 961 /// Uses \a tryToComputeMassInFunction() and \a computeIrreducibleMass() to 962 /// compute mass in the top-level function. 963 /// 964 /// \post \a tryToComputeMassInFunction() has returned \c true. 965 void computeMassInFunction(); 966 967 std::string getBlockName(const BlockNode &Node) const override { 968 return bfi_detail::getBlockName(getBlock(Node)); 969 } 970 971 /// The current implementation for computing relative block frequencies does 972 /// not handle correctly control-flow graphs containing irreducible loops. To 973 /// resolve the problem, we apply a post-processing step, which iteratively 974 /// updates block frequencies based on the frequencies of their predesessors. 975 /// This corresponds to finding the stationary point of the Markov chain by 976 /// an iterative method aka "PageRank computation". 977 /// The algorithm takes at most O(|E| * IterativeBFIMaxIterations) steps but 978 /// typically converges faster. 979 /// 980 /// Decide whether we want to apply iterative inference for a given function. 981 bool needIterativeInference() const; 982 983 /// Apply an iterative post-processing to infer correct counts for irr loops. 984 void applyIterativeInference(); 985 986 using ProbMatrixType = std::vector<std::vector<std::pair<size_t, Scaled64>>>; 987 988 /// Run iterative inference for a probability matrix and initial frequencies. 989 void iterativeInference(const ProbMatrixType &ProbMatrix, 990 std::vector<Scaled64> &Freq) const; 991 992 /// Find all blocks to apply inference on, that is, reachable from the entry 993 /// and backward reachable from exists along edges with positive probability. 994 void findReachableBlocks(std::vector<const BlockT *> &Blocks) const; 995 996 /// Build a matrix of probabilities with transitions (edges) between the 997 /// blocks: ProbMatrix[I] holds pairs (J, P), where Pr[J -> I | J] = P 998 void initTransitionProbabilities( 999 const std::vector<const BlockT *> &Blocks, 1000 const DenseMap<const BlockT *, size_t> &BlockIndex, 1001 ProbMatrixType &ProbMatrix) const; 1002 1003 #ifndef NDEBUG 1004 /// Compute the discrepancy between current block frequencies and the 1005 /// probability matrix. 1006 Scaled64 discrepancy(const ProbMatrixType &ProbMatrix, 1007 const std::vector<Scaled64> &Freq) const; 1008 #endif 1009 1010 public: 1011 BlockFrequencyInfoImpl() = default; 1012 1013 const FunctionT *getFunction() const { return F; } 1014 1015 void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, 1016 const LoopInfoT &LI); 1017 1018 using BlockFrequencyInfoImplBase::getEntryFreq; 1019 1020 BlockFrequency getBlockFreq(const BlockT *BB) const { 1021 return BlockFrequencyInfoImplBase::getBlockFreq(getNode(BB)); 1022 } 1023 1024 std::optional<uint64_t> 1025 getBlockProfileCount(const Function &F, const BlockT *BB, 1026 bool AllowSynthetic = false) const { 1027 return BlockFrequencyInfoImplBase::getBlockProfileCount(F, getNode(BB), 1028 AllowSynthetic); 1029 } 1030 1031 std::optional<uint64_t> 1032 getProfileCountFromFreq(const Function &F, uint64_t Freq, 1033 bool AllowSynthetic = false) const { 1034 return BlockFrequencyInfoImplBase::getProfileCountFromFreq(F, Freq, 1035 AllowSynthetic); 1036 } 1037 1038 bool isIrrLoopHeader(const BlockT *BB) { 1039 return BlockFrequencyInfoImplBase::isIrrLoopHeader(getNode(BB)); 1040 } 1041 1042 void setBlockFreq(const BlockT *BB, uint64_t Freq); 1043 1044 void forgetBlock(const BlockT *BB) { 1045 // We don't erase corresponding items from `Freqs`, `RPOT` and other to 1046 // avoid invalidating indices. Doing so would have saved some memory, but 1047 // it's not worth it. 1048 Nodes.erase(BB); 1049 } 1050 1051 Scaled64 getFloatingBlockFreq(const BlockT *BB) const { 1052 return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB)); 1053 } 1054 1055 const BranchProbabilityInfoT &getBPI() const { return *BPI; } 1056 1057 /// Print the frequencies for the current function. 1058 /// 1059 /// Prints the frequencies for the blocks in the current function. 1060 /// 1061 /// Blocks are printed in the natural iteration order of the function, rather 1062 /// than reverse post-order. This provides two advantages: writing -analyze 1063 /// tests is easier (since blocks come out in source order), and even 1064 /// unreachable blocks are printed. 1065 /// 1066 /// \a BlockFrequencyInfoImplBase::print() only knows reverse post-order, so 1067 /// we need to override it here. 1068 raw_ostream &print(raw_ostream &OS) const override; 1069 1070 using BlockFrequencyInfoImplBase::dump; 1071 using BlockFrequencyInfoImplBase::printBlockFreq; 1072 1073 raw_ostream &printBlockFreq(raw_ostream &OS, const BlockT *BB) const { 1074 return BlockFrequencyInfoImplBase::printBlockFreq(OS, getNode(BB)); 1075 } 1076 1077 void verifyMatch(BlockFrequencyInfoImpl<BT> &Other) const; 1078 }; 1079 1080 namespace bfi_detail { 1081 1082 template <class BFIImplT> 1083 class BFICallbackVH<BasicBlock, BFIImplT> : public CallbackVH { 1084 BFIImplT *BFIImpl; 1085 1086 public: 1087 BFICallbackVH() = default; 1088 1089 BFICallbackVH(const BasicBlock *BB, BFIImplT *BFIImpl) 1090 : CallbackVH(BB), BFIImpl(BFIImpl) {} 1091 1092 virtual ~BFICallbackVH() = default; 1093 1094 void deleted() override { 1095 BFIImpl->forgetBlock(cast<BasicBlock>(getValPtr())); 1096 } 1097 }; 1098 1099 /// Dummy implementation since MachineBasicBlocks aren't Values, so ValueHandles 1100 /// don't apply to them. 1101 template <class BFIImplT> 1102 class BFICallbackVH<MachineBasicBlock, BFIImplT> { 1103 public: 1104 BFICallbackVH() = default; 1105 BFICallbackVH(const MachineBasicBlock *, BFIImplT *) {} 1106 }; 1107 1108 } // end namespace bfi_detail 1109 1110 template <class BT> 1111 void BlockFrequencyInfoImpl<BT>::calculate(const FunctionT &F, 1112 const BranchProbabilityInfoT &BPI, 1113 const LoopInfoT &LI) { 1114 // Save the parameters. 1115 this->BPI = &BPI; 1116 this->LI = &LI; 1117 this->F = &F; 1118 1119 // Clean up left-over data structures. 1120 BlockFrequencyInfoImplBase::clear(); 1121 RPOT.clear(); 1122 Nodes.clear(); 1123 1124 // Initialize. 1125 LLVM_DEBUG(dbgs() << "\nblock-frequency: " << F.getName() 1126 << "\n=================" 1127 << std::string(F.getName().size(), '=') << "\n"); 1128 initializeRPOT(); 1129 initializeLoops(); 1130 1131 // Visit loops in post-order to find the local mass distribution, and then do 1132 // the full function. 1133 computeMassInLoops(); 1134 computeMassInFunction(); 1135 unwrapLoops(); 1136 // Apply a post-processing step improving computed frequencies for functions 1137 // with irreducible loops. 1138 if (needIterativeInference()) 1139 applyIterativeInference(); 1140 finalizeMetrics(); 1141 1142 if (CheckBFIUnknownBlockQueries) { 1143 // To detect BFI queries for unknown blocks, add entries for unreachable 1144 // blocks, if any. This is to distinguish between known/existing unreachable 1145 // blocks and unknown blocks. 1146 for (const BlockT &BB : F) 1147 if (!Nodes.count(&BB)) 1148 setBlockFreq(&BB, 0); 1149 } 1150 } 1151 1152 template <class BT> 1153 void BlockFrequencyInfoImpl<BT>::setBlockFreq(const BlockT *BB, uint64_t Freq) { 1154 if (Nodes.count(BB)) 1155 BlockFrequencyInfoImplBase::setBlockFreq(getNode(BB), Freq); 1156 else { 1157 // If BB is a newly added block after BFI is done, we need to create a new 1158 // BlockNode for it assigned with a new index. The index can be determined 1159 // by the size of Freqs. 1160 BlockNode NewNode(Freqs.size()); 1161 Nodes[BB] = {NewNode, BFICallbackVH(BB, this)}; 1162 Freqs.emplace_back(); 1163 BlockFrequencyInfoImplBase::setBlockFreq(NewNode, Freq); 1164 } 1165 } 1166 1167 template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() { 1168 const BlockT *Entry = &F->front(); 1169 RPOT.reserve(F->size()); 1170 std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT)); 1171 std::reverse(RPOT.begin(), RPOT.end()); 1172 1173 assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() && 1174 "More nodes in function than Block Frequency Info supports"); 1175 1176 LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n"); 1177 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) { 1178 BlockNode Node = getNode(I); 1179 LLVM_DEBUG(dbgs() << " - " << getIndex(I) << ": " << getBlockName(Node) 1180 << "\n"); 1181 Nodes[*I] = {Node, BFICallbackVH(*I, this)}; 1182 } 1183 1184 Working.reserve(RPOT.size()); 1185 for (size_t Index = 0; Index < RPOT.size(); ++Index) 1186 Working.emplace_back(Index); 1187 Freqs.resize(RPOT.size()); 1188 } 1189 1190 template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() { 1191 LLVM_DEBUG(dbgs() << "loop-detection\n"); 1192 if (LI->empty()) 1193 return; 1194 1195 // Visit loops top down and assign them an index. 1196 std::deque<std::pair<const LoopT *, LoopData *>> Q; 1197 for (const LoopT *L : *LI) 1198 Q.emplace_back(L, nullptr); 1199 while (!Q.empty()) { 1200 const LoopT *Loop = Q.front().first; 1201 LoopData *Parent = Q.front().second; 1202 Q.pop_front(); 1203 1204 BlockNode Header = getNode(Loop->getHeader()); 1205 assert(Header.isValid()); 1206 1207 Loops.emplace_back(Parent, Header); 1208 Working[Header.Index].Loop = &Loops.back(); 1209 LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header) << "\n"); 1210 1211 for (const LoopT *L : *Loop) 1212 Q.emplace_back(L, &Loops.back()); 1213 } 1214 1215 // Visit nodes in reverse post-order and add them to their deepest containing 1216 // loop. 1217 for (size_t Index = 0; Index < RPOT.size(); ++Index) { 1218 // Loop headers have already been mostly mapped. 1219 if (Working[Index].isLoopHeader()) { 1220 LoopData *ContainingLoop = Working[Index].getContainingLoop(); 1221 if (ContainingLoop) 1222 ContainingLoop->Nodes.push_back(Index); 1223 continue; 1224 } 1225 1226 const LoopT *Loop = LI->getLoopFor(RPOT[Index]); 1227 if (!Loop) 1228 continue; 1229 1230 // Add this node to its containing loop's member list. 1231 BlockNode Header = getNode(Loop->getHeader()); 1232 assert(Header.isValid()); 1233 const auto &HeaderData = Working[Header.Index]; 1234 assert(HeaderData.isLoopHeader()); 1235 1236 Working[Index].Loop = HeaderData.Loop; 1237 HeaderData.Loop->Nodes.push_back(Index); 1238 LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header) 1239 << ": member = " << getBlockName(Index) << "\n"); 1240 } 1241 } 1242 1243 template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInLoops() { 1244 // Visit loops with the deepest first, and the top-level loops last. 1245 for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; ++L) { 1246 if (computeMassInLoop(*L)) 1247 continue; 1248 auto Next = std::next(L); 1249 computeIrreducibleMass(&*L, L.base()); 1250 L = std::prev(Next); 1251 if (computeMassInLoop(*L)) 1252 continue; 1253 llvm_unreachable("unhandled irreducible control flow"); 1254 } 1255 } 1256 1257 template <class BT> 1258 bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) { 1259 // Compute mass in loop. 1260 LLVM_DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop) << "\n"); 1261 1262 if (Loop.isIrreducible()) { 1263 LLVM_DEBUG(dbgs() << "isIrreducible = true\n"); 1264 Distribution Dist; 1265 unsigned NumHeadersWithWeight = 0; 1266 std::optional<uint64_t> MinHeaderWeight; 1267 DenseSet<uint32_t> HeadersWithoutWeight; 1268 HeadersWithoutWeight.reserve(Loop.NumHeaders); 1269 for (uint32_t H = 0; H < Loop.NumHeaders; ++H) { 1270 auto &HeaderNode = Loop.Nodes[H]; 1271 const BlockT *Block = getBlock(HeaderNode); 1272 IsIrrLoopHeader.set(Loop.Nodes[H].Index); 1273 std::optional<uint64_t> HeaderWeight = Block->getIrrLoopHeaderWeight(); 1274 if (!HeaderWeight) { 1275 LLVM_DEBUG(dbgs() << "Missing irr loop header metadata on " 1276 << getBlockName(HeaderNode) << "\n"); 1277 HeadersWithoutWeight.insert(H); 1278 continue; 1279 } 1280 LLVM_DEBUG(dbgs() << getBlockName(HeaderNode) 1281 << " has irr loop header weight " << *HeaderWeight 1282 << "\n"); 1283 NumHeadersWithWeight++; 1284 uint64_t HeaderWeightValue = *HeaderWeight; 1285 if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight) 1286 MinHeaderWeight = HeaderWeightValue; 1287 if (HeaderWeightValue) { 1288 Dist.addLocal(HeaderNode, HeaderWeightValue); 1289 } 1290 } 1291 // As a heuristic, if some headers don't have a weight, give them the 1292 // minimum weight seen (not to disrupt the existing trends too much by 1293 // using a weight that's in the general range of the other headers' weights, 1294 // and the minimum seems to perform better than the average.) 1295 // FIXME: better update in the passes that drop the header weight. 1296 // If no headers have a weight, give them even weight (use weight 1). 1297 if (!MinHeaderWeight) 1298 MinHeaderWeight = 1; 1299 for (uint32_t H : HeadersWithoutWeight) { 1300 auto &HeaderNode = Loop.Nodes[H]; 1301 assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() && 1302 "Shouldn't have a weight metadata"); 1303 uint64_t MinWeight = *MinHeaderWeight; 1304 LLVM_DEBUG(dbgs() << "Giving weight " << MinWeight << " to " 1305 << getBlockName(HeaderNode) << "\n"); 1306 if (MinWeight) 1307 Dist.addLocal(HeaderNode, MinWeight); 1308 } 1309 distributeIrrLoopHeaderMass(Dist); 1310 for (const BlockNode &M : Loop.Nodes) 1311 if (!propagateMassToSuccessors(&Loop, M)) 1312 llvm_unreachable("unhandled irreducible control flow"); 1313 if (NumHeadersWithWeight == 0) 1314 // No headers have a metadata. Adjust header mass. 1315 adjustLoopHeaderMass(Loop); 1316 } else { 1317 Working[Loop.getHeader().Index].getMass() = BlockMass::getFull(); 1318 if (!propagateMassToSuccessors(&Loop, Loop.getHeader())) 1319 llvm_unreachable("irreducible control flow to loop header!?"); 1320 for (const BlockNode &M : Loop.members()) 1321 if (!propagateMassToSuccessors(&Loop, M)) 1322 // Irreducible backedge. 1323 return false; 1324 } 1325 1326 computeLoopScale(Loop); 1327 packageLoop(Loop); 1328 return true; 1329 } 1330 1331 template <class BT> 1332 bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() { 1333 // Compute mass in function. 1334 LLVM_DEBUG(dbgs() << "compute-mass-in-function\n"); 1335 assert(!Working.empty() && "no blocks in function"); 1336 assert(!Working[0].isLoopHeader() && "entry block is a loop header"); 1337 1338 Working[0].getMass() = BlockMass::getFull(); 1339 for (rpot_iterator I = rpot_begin(), IE = rpot_end(); I != IE; ++I) { 1340 // Check for nodes that have been packaged. 1341 BlockNode Node = getNode(I); 1342 if (Working[Node.Index].isPackaged()) 1343 continue; 1344 1345 if (!propagateMassToSuccessors(nullptr, Node)) 1346 return false; 1347 } 1348 return true; 1349 } 1350 1351 template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() { 1352 if (tryToComputeMassInFunction()) 1353 return; 1354 computeIrreducibleMass(nullptr, Loops.begin()); 1355 if (tryToComputeMassInFunction()) 1356 return; 1357 llvm_unreachable("unhandled irreducible control flow"); 1358 } 1359 1360 template <class BT> 1361 bool BlockFrequencyInfoImpl<BT>::needIterativeInference() const { 1362 if (!UseIterativeBFIInference) 1363 return false; 1364 if (!F->getFunction().hasProfileData()) 1365 return false; 1366 // Apply iterative inference only if the function contains irreducible loops; 1367 // otherwise, computed block frequencies are reasonably correct. 1368 for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; ++L) { 1369 if (L->isIrreducible()) 1370 return true; 1371 } 1372 return false; 1373 } 1374 1375 template <class BT> void BlockFrequencyInfoImpl<BT>::applyIterativeInference() { 1376 // Extract blocks for processing: a block is considered for inference iff it 1377 // can be reached from the entry by edges with a positive probability. 1378 // Non-processed blocks are assigned with the zero frequency and are ignored 1379 // in the computation 1380 std::vector<const BlockT *> ReachableBlocks; 1381 findReachableBlocks(ReachableBlocks); 1382 if (ReachableBlocks.empty()) 1383 return; 1384 1385 // The map is used to to index successors/predecessors of reachable blocks in 1386 // the ReachableBlocks vector 1387 DenseMap<const BlockT *, size_t> BlockIndex; 1388 // Extract initial frequencies for the reachable blocks 1389 auto Freq = std::vector<Scaled64>(ReachableBlocks.size()); 1390 Scaled64 SumFreq; 1391 for (size_t I = 0; I < ReachableBlocks.size(); I++) { 1392 const BlockT *BB = ReachableBlocks[I]; 1393 BlockIndex[BB] = I; 1394 Freq[I] = getFloatingBlockFreq(BB); 1395 SumFreq += Freq[I]; 1396 } 1397 assert(!SumFreq.isZero() && "empty initial block frequencies"); 1398 1399 LLVM_DEBUG(dbgs() << "Applying iterative inference for " << F->getName() 1400 << " with " << ReachableBlocks.size() << " blocks\n"); 1401 1402 // Normalizing frequencies so they sum up to 1.0 1403 for (auto &Value : Freq) { 1404 Value /= SumFreq; 1405 } 1406 1407 // Setting up edge probabilities using sparse matrix representation: 1408 // ProbMatrix[I] holds a vector of pairs (J, P) where Pr[J -> I | J] = P 1409 ProbMatrixType ProbMatrix; 1410 initTransitionProbabilities(ReachableBlocks, BlockIndex, ProbMatrix); 1411 1412 // Run the propagation 1413 iterativeInference(ProbMatrix, Freq); 1414 1415 // Assign computed frequency values 1416 for (const BlockT &BB : *F) { 1417 auto Node = getNode(&BB); 1418 if (!Node.isValid()) 1419 continue; 1420 if (BlockIndex.count(&BB)) { 1421 Freqs[Node.Index].Scaled = Freq[BlockIndex[&BB]]; 1422 } else { 1423 Freqs[Node.Index].Scaled = Scaled64::getZero(); 1424 } 1425 } 1426 } 1427 1428 template <class BT> 1429 void BlockFrequencyInfoImpl<BT>::iterativeInference( 1430 const ProbMatrixType &ProbMatrix, std::vector<Scaled64> &Freq) const { 1431 assert(0.0 < IterativeBFIPrecision && IterativeBFIPrecision < 1.0 && 1432 "incorrectly specified precision"); 1433 // Convert double precision to Scaled64 1434 const auto Precision = 1435 Scaled64::getInverse(static_cast<uint64_t>(1.0 / IterativeBFIPrecision)); 1436 const size_t MaxIterations = IterativeBFIMaxIterationsPerBlock * Freq.size(); 1437 1438 #ifndef NDEBUG 1439 LLVM_DEBUG(dbgs() << " Initial discrepancy = " 1440 << discrepancy(ProbMatrix, Freq).toString() << "\n"); 1441 #endif 1442 1443 // Successors[I] holds unique sucessors of the I-th block 1444 auto Successors = std::vector<std::vector<size_t>>(Freq.size()); 1445 for (size_t I = 0; I < Freq.size(); I++) { 1446 for (const auto &Jump : ProbMatrix[I]) { 1447 Successors[Jump.first].push_back(I); 1448 } 1449 } 1450 1451 // To speedup computation, we maintain a set of "active" blocks whose 1452 // frequencies need to be updated based on the incoming edges. 1453 // The set is dynamic and changes after every update. Initially all blocks 1454 // with a positive frequency are active 1455 auto IsActive = BitVector(Freq.size(), false); 1456 std::queue<size_t> ActiveSet; 1457 for (size_t I = 0; I < Freq.size(); I++) { 1458 if (Freq[I] > 0) { 1459 ActiveSet.push(I); 1460 IsActive[I] = true; 1461 } 1462 } 1463 1464 // Iterate over the blocks propagating frequencies 1465 size_t It = 0; 1466 while (It++ < MaxIterations && !ActiveSet.empty()) { 1467 size_t I = ActiveSet.front(); 1468 ActiveSet.pop(); 1469 IsActive[I] = false; 1470 1471 // Compute a new frequency for the block: NewFreq := Freq \times ProbMatrix. 1472 // A special care is taken for self-edges that needs to be scaled by 1473 // (1.0 - SelfProb), where SelfProb is the sum of probabilities on the edges 1474 Scaled64 NewFreq; 1475 Scaled64 OneMinusSelfProb = Scaled64::getOne(); 1476 for (const auto &Jump : ProbMatrix[I]) { 1477 if (Jump.first == I) { 1478 OneMinusSelfProb -= Jump.second; 1479 } else { 1480 NewFreq += Freq[Jump.first] * Jump.second; 1481 } 1482 } 1483 if (OneMinusSelfProb != Scaled64::getOne()) 1484 NewFreq /= OneMinusSelfProb; 1485 1486 // If the block's frequency has changed enough, then 1487 // make sure the block and its successors are in the active set 1488 auto Change = Freq[I] >= NewFreq ? Freq[I] - NewFreq : NewFreq - Freq[I]; 1489 if (Change > Precision) { 1490 ActiveSet.push(I); 1491 IsActive[I] = true; 1492 for (size_t Succ : Successors[I]) { 1493 if (!IsActive[Succ]) { 1494 ActiveSet.push(Succ); 1495 IsActive[Succ] = true; 1496 } 1497 } 1498 } 1499 1500 // Update the frequency for the block 1501 Freq[I] = NewFreq; 1502 } 1503 1504 LLVM_DEBUG(dbgs() << " Completed " << It << " inference iterations" 1505 << format(" (%0.0f per block)", double(It) / Freq.size()) 1506 << "\n"); 1507 #ifndef NDEBUG 1508 LLVM_DEBUG(dbgs() << " Final discrepancy = " 1509 << discrepancy(ProbMatrix, Freq).toString() << "\n"); 1510 #endif 1511 } 1512 1513 template <class BT> 1514 void BlockFrequencyInfoImpl<BT>::findReachableBlocks( 1515 std::vector<const BlockT *> &Blocks) const { 1516 // Find all blocks to apply inference on, that is, reachable from the entry 1517 // along edges with non-zero probablities 1518 std::queue<const BlockT *> Queue; 1519 SmallPtrSet<const BlockT *, 8> Reachable; 1520 const BlockT *Entry = &F->front(); 1521 Queue.push(Entry); 1522 Reachable.insert(Entry); 1523 while (!Queue.empty()) { 1524 const BlockT *SrcBB = Queue.front(); 1525 Queue.pop(); 1526 for (const BlockT *DstBB : children<const BlockT *>(SrcBB)) { 1527 auto EP = BPI->getEdgeProbability(SrcBB, DstBB); 1528 if (EP.isZero()) 1529 continue; 1530 if (Reachable.insert(DstBB).second) 1531 Queue.push(DstBB); 1532 } 1533 } 1534 1535 // Find all blocks to apply inference on, that is, backward reachable from 1536 // the entry along (backward) edges with non-zero probablities 1537 SmallPtrSet<const BlockT *, 8> InverseReachable; 1538 for (const BlockT &BB : *F) { 1539 // An exit block is a block without any successors 1540 bool HasSucc = GraphTraits<const BlockT *>::child_begin(&BB) != 1541 GraphTraits<const BlockT *>::child_end(&BB); 1542 if (!HasSucc && Reachable.count(&BB)) { 1543 Queue.push(&BB); 1544 InverseReachable.insert(&BB); 1545 } 1546 } 1547 while (!Queue.empty()) { 1548 const BlockT *SrcBB = Queue.front(); 1549 Queue.pop(); 1550 for (const BlockT *DstBB : children<Inverse<const BlockT *>>(SrcBB)) { 1551 auto EP = BPI->getEdgeProbability(DstBB, SrcBB); 1552 if (EP.isZero()) 1553 continue; 1554 if (InverseReachable.insert(DstBB).second) 1555 Queue.push(DstBB); 1556 } 1557 } 1558 1559 // Collect the result 1560 Blocks.reserve(F->size()); 1561 for (const BlockT &BB : *F) { 1562 if (Reachable.count(&BB) && InverseReachable.count(&BB)) { 1563 Blocks.push_back(&BB); 1564 } 1565 } 1566 } 1567 1568 template <class BT> 1569 void BlockFrequencyInfoImpl<BT>::initTransitionProbabilities( 1570 const std::vector<const BlockT *> &Blocks, 1571 const DenseMap<const BlockT *, size_t> &BlockIndex, 1572 ProbMatrixType &ProbMatrix) const { 1573 const size_t NumBlocks = Blocks.size(); 1574 auto Succs = std::vector<std::vector<std::pair<size_t, Scaled64>>>(NumBlocks); 1575 auto SumProb = std::vector<Scaled64>(NumBlocks); 1576 1577 // Find unique successors and corresponding probabilities for every block 1578 for (size_t Src = 0; Src < NumBlocks; Src++) { 1579 const BlockT *BB = Blocks[Src]; 1580 SmallPtrSet<const BlockT *, 2> UniqueSuccs; 1581 for (const auto SI : children<const BlockT *>(BB)) { 1582 // Ignore cold blocks 1583 if (BlockIndex.find(SI) == BlockIndex.end()) 1584 continue; 1585 // Ignore parallel edges between BB and SI blocks 1586 if (!UniqueSuccs.insert(SI).second) 1587 continue; 1588 // Ignore jumps with zero probability 1589 auto EP = BPI->getEdgeProbability(BB, SI); 1590 if (EP.isZero()) 1591 continue; 1592 1593 auto EdgeProb = 1594 Scaled64::getFraction(EP.getNumerator(), EP.getDenominator()); 1595 size_t Dst = BlockIndex.find(SI)->second; 1596 Succs[Src].push_back(std::make_pair(Dst, EdgeProb)); 1597 SumProb[Src] += EdgeProb; 1598 } 1599 } 1600 1601 // Add transitions for every jump with positive branch probability 1602 ProbMatrix = ProbMatrixType(NumBlocks); 1603 for (size_t Src = 0; Src < NumBlocks; Src++) { 1604 // Ignore blocks w/o successors 1605 if (Succs[Src].empty()) 1606 continue; 1607 1608 assert(!SumProb[Src].isZero() && "Zero sum probability of non-exit block"); 1609 for (auto &Jump : Succs[Src]) { 1610 size_t Dst = Jump.first; 1611 Scaled64 Prob = Jump.second; 1612 ProbMatrix[Dst].push_back(std::make_pair(Src, Prob / SumProb[Src])); 1613 } 1614 } 1615 1616 // Add transitions from sinks to the source 1617 size_t EntryIdx = BlockIndex.find(&F->front())->second; 1618 for (size_t Src = 0; Src < NumBlocks; Src++) { 1619 if (Succs[Src].empty()) { 1620 ProbMatrix[EntryIdx].push_back(std::make_pair(Src, Scaled64::getOne())); 1621 } 1622 } 1623 } 1624 1625 #ifndef NDEBUG 1626 template <class BT> 1627 BlockFrequencyInfoImplBase::Scaled64 BlockFrequencyInfoImpl<BT>::discrepancy( 1628 const ProbMatrixType &ProbMatrix, const std::vector<Scaled64> &Freq) const { 1629 assert(Freq[0] > 0 && "Incorrectly computed frequency of the entry block"); 1630 Scaled64 Discrepancy; 1631 for (size_t I = 0; I < ProbMatrix.size(); I++) { 1632 Scaled64 Sum; 1633 for (const auto &Jump : ProbMatrix[I]) { 1634 Sum += Freq[Jump.first] * Jump.second; 1635 } 1636 Discrepancy += Freq[I] >= Sum ? Freq[I] - Sum : Sum - Freq[I]; 1637 } 1638 // Normalizing by the frequency of the entry block 1639 return Discrepancy / Freq[0]; 1640 } 1641 #endif 1642 1643 /// \note This should be a lambda, but that crashes GCC 4.7. 1644 namespace bfi_detail { 1645 1646 template <class BT> struct BlockEdgesAdder { 1647 using BlockT = BT; 1648 using LoopData = BlockFrequencyInfoImplBase::LoopData; 1649 using Successor = GraphTraits<const BlockT *>; 1650 1651 const BlockFrequencyInfoImpl<BT> &BFI; 1652 1653 explicit BlockEdgesAdder(const BlockFrequencyInfoImpl<BT> &BFI) 1654 : BFI(BFI) {} 1655 1656 void operator()(IrreducibleGraph &G, IrreducibleGraph::IrrNode &Irr, 1657 const LoopData *OuterLoop) { 1658 const BlockT *BB = BFI.RPOT[Irr.Node.Index]; 1659 for (const auto *Succ : children<const BlockT *>(BB)) 1660 G.addEdge(Irr, BFI.getNode(Succ), OuterLoop); 1661 } 1662 }; 1663 1664 } // end namespace bfi_detail 1665 1666 template <class BT> 1667 void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass( 1668 LoopData *OuterLoop, std::list<LoopData>::iterator Insert) { 1669 LLVM_DEBUG(dbgs() << "analyze-irreducible-in-"; 1670 if (OuterLoop) dbgs() 1671 << "loop: " << getLoopName(*OuterLoop) << "\n"; 1672 else dbgs() << "function\n"); 1673 1674 using namespace bfi_detail; 1675 1676 // Ideally, addBlockEdges() would be declared here as a lambda, but that 1677 // crashes GCC 4.7. 1678 BlockEdgesAdder<BT> addBlockEdges(*this); 1679 IrreducibleGraph G(*this, OuterLoop, addBlockEdges); 1680 1681 for (auto &L : analyzeIrreducible(G, OuterLoop, Insert)) 1682 computeMassInLoop(L); 1683 1684 if (!OuterLoop) 1685 return; 1686 updateLoopWithIrreducible(*OuterLoop); 1687 } 1688 1689 // A helper function that converts a branch probability into weight. 1690 inline uint32_t getWeightFromBranchProb(const BranchProbability Prob) { 1691 return Prob.getNumerator(); 1692 } 1693 1694 template <class BT> 1695 bool 1696 BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop, 1697 const BlockNode &Node) { 1698 LLVM_DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n"); 1699 // Calculate probability for successors. 1700 Distribution Dist; 1701 if (auto *Loop = Working[Node.Index].getPackagedLoop()) { 1702 assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop"); 1703 if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist)) 1704 // Irreducible backedge. 1705 return false; 1706 } else { 1707 const BlockT *BB = getBlock(Node); 1708 for (auto SI = GraphTraits<const BlockT *>::child_begin(BB), 1709 SE = GraphTraits<const BlockT *>::child_end(BB); 1710 SI != SE; ++SI) 1711 if (!addToDist( 1712 Dist, OuterLoop, Node, getNode(*SI), 1713 getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI)))) 1714 // Irreducible backedge. 1715 return false; 1716 } 1717 1718 // Distribute mass to successors, saving exit and backedge data in the 1719 // loop header. 1720 distributeMass(Node, OuterLoop, Dist); 1721 return true; 1722 } 1723 1724 template <class BT> 1725 raw_ostream &BlockFrequencyInfoImpl<BT>::print(raw_ostream &OS) const { 1726 if (!F) 1727 return OS; 1728 OS << "block-frequency-info: " << F->getName() << "\n"; 1729 for (const BlockT &BB : *F) { 1730 OS << " - " << bfi_detail::getBlockName(&BB) << ": float = "; 1731 getFloatingBlockFreq(&BB).print(OS, 5) 1732 << ", int = " << getBlockFreq(&BB).getFrequency(); 1733 if (std::optional<uint64_t> ProfileCount = 1734 BlockFrequencyInfoImplBase::getBlockProfileCount( 1735 F->getFunction(), getNode(&BB))) 1736 OS << ", count = " << *ProfileCount; 1737 if (std::optional<uint64_t> IrrLoopHeaderWeight = 1738 BB.getIrrLoopHeaderWeight()) 1739 OS << ", irr_loop_header_weight = " << *IrrLoopHeaderWeight; 1740 OS << "\n"; 1741 } 1742 1743 // Add an extra newline for readability. 1744 OS << "\n"; 1745 return OS; 1746 } 1747 1748 template <class BT> 1749 void BlockFrequencyInfoImpl<BT>::verifyMatch( 1750 BlockFrequencyInfoImpl<BT> &Other) const { 1751 bool Match = true; 1752 DenseMap<const BlockT *, BlockNode> ValidNodes; 1753 DenseMap<const BlockT *, BlockNode> OtherValidNodes; 1754 for (auto &Entry : Nodes) { 1755 const BlockT *BB = Entry.first; 1756 if (BB) { 1757 ValidNodes[BB] = Entry.second.first; 1758 } 1759 } 1760 for (auto &Entry : Other.Nodes) { 1761 const BlockT *BB = Entry.first; 1762 if (BB) { 1763 OtherValidNodes[BB] = Entry.second.first; 1764 } 1765 } 1766 unsigned NumValidNodes = ValidNodes.size(); 1767 unsigned NumOtherValidNodes = OtherValidNodes.size(); 1768 if (NumValidNodes != NumOtherValidNodes) { 1769 Match = false; 1770 dbgs() << "Number of blocks mismatch: " << NumValidNodes << " vs " 1771 << NumOtherValidNodes << "\n"; 1772 } else { 1773 for (auto &Entry : ValidNodes) { 1774 const BlockT *BB = Entry.first; 1775 BlockNode Node = Entry.second; 1776 if (OtherValidNodes.count(BB)) { 1777 BlockNode OtherNode = OtherValidNodes[BB]; 1778 const auto &Freq = Freqs[Node.Index]; 1779 const auto &OtherFreq = Other.Freqs[OtherNode.Index]; 1780 if (Freq.Integer != OtherFreq.Integer) { 1781 Match = false; 1782 dbgs() << "Freq mismatch: " << bfi_detail::getBlockName(BB) << " " 1783 << Freq.Integer << " vs " << OtherFreq.Integer << "\n"; 1784 } 1785 } else { 1786 Match = false; 1787 dbgs() << "Block " << bfi_detail::getBlockName(BB) << " index " 1788 << Node.Index << " does not exist in Other.\n"; 1789 } 1790 } 1791 // If there's a valid node in OtherValidNodes that's not in ValidNodes, 1792 // either the above num check or the check on OtherValidNodes will fail. 1793 } 1794 if (!Match) { 1795 dbgs() << "This\n"; 1796 print(dbgs()); 1797 dbgs() << "Other\n"; 1798 Other.print(dbgs()); 1799 } 1800 assert(Match && "BFI mismatch"); 1801 } 1802 1803 // Graph trait base class for block frequency information graph 1804 // viewer. 1805 1806 enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count }; 1807 1808 template <class BlockFrequencyInfoT, class BranchProbabilityInfoT> 1809 struct BFIDOTGraphTraitsBase : public DefaultDOTGraphTraits { 1810 using GTraits = GraphTraits<BlockFrequencyInfoT *>; 1811 using NodeRef = typename GTraits::NodeRef; 1812 using EdgeIter = typename GTraits::ChildIteratorType; 1813 using NodeIter = typename GTraits::nodes_iterator; 1814 1815 uint64_t MaxFrequency = 0; 1816 1817 explicit BFIDOTGraphTraitsBase(bool isSimple = false) 1818 : DefaultDOTGraphTraits(isSimple) {} 1819 1820 static StringRef getGraphName(const BlockFrequencyInfoT *G) { 1821 return G->getFunction()->getName(); 1822 } 1823 1824 std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph, 1825 unsigned HotPercentThreshold = 0) { 1826 std::string Result; 1827 if (!HotPercentThreshold) 1828 return Result; 1829 1830 // Compute MaxFrequency on the fly: 1831 if (!MaxFrequency) { 1832 for (NodeIter I = GTraits::nodes_begin(Graph), 1833 E = GTraits::nodes_end(Graph); 1834 I != E; ++I) { 1835 NodeRef N = *I; 1836 MaxFrequency = 1837 std::max(MaxFrequency, Graph->getBlockFreq(N).getFrequency()); 1838 } 1839 } 1840 BlockFrequency Freq = Graph->getBlockFreq(Node); 1841 BlockFrequency HotFreq = 1842 (BlockFrequency(MaxFrequency) * 1843 BranchProbability::getBranchProbability(HotPercentThreshold, 100)); 1844 1845 if (Freq < HotFreq) 1846 return Result; 1847 1848 raw_string_ostream OS(Result); 1849 OS << "color=\"red\""; 1850 OS.flush(); 1851 return Result; 1852 } 1853 1854 std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph, 1855 GVDAGType GType, int layout_order = -1) { 1856 std::string Result; 1857 raw_string_ostream OS(Result); 1858 1859 if (layout_order != -1) 1860 OS << Node->getName() << "[" << layout_order << "] : "; 1861 else 1862 OS << Node->getName() << " : "; 1863 switch (GType) { 1864 case GVDT_Fraction: 1865 Graph->printBlockFreq(OS, Node); 1866 break; 1867 case GVDT_Integer: 1868 OS << Graph->getBlockFreq(Node).getFrequency(); 1869 break; 1870 case GVDT_Count: { 1871 auto Count = Graph->getBlockProfileCount(Node); 1872 if (Count) 1873 OS << *Count; 1874 else 1875 OS << "Unknown"; 1876 break; 1877 } 1878 case GVDT_None: 1879 llvm_unreachable("If we are not supposed to render a graph we should " 1880 "never reach this point."); 1881 } 1882 return Result; 1883 } 1884 1885 std::string getEdgeAttributes(NodeRef Node, EdgeIter EI, 1886 const BlockFrequencyInfoT *BFI, 1887 const BranchProbabilityInfoT *BPI, 1888 unsigned HotPercentThreshold = 0) { 1889 std::string Str; 1890 if (!BPI) 1891 return Str; 1892 1893 BranchProbability BP = BPI->getEdgeProbability(Node, EI); 1894 uint32_t N = BP.getNumerator(); 1895 uint32_t D = BP.getDenominator(); 1896 double Percent = 100.0 * N / D; 1897 raw_string_ostream OS(Str); 1898 OS << format("label=\"%.1f%%\"", Percent); 1899 1900 if (HotPercentThreshold) { 1901 BlockFrequency EFreq = BFI->getBlockFreq(Node) * BP; 1902 BlockFrequency HotFreq = BlockFrequency(MaxFrequency) * 1903 BranchProbability(HotPercentThreshold, 100); 1904 1905 if (EFreq >= HotFreq) { 1906 OS << ",color=\"red\""; 1907 } 1908 } 1909 1910 OS.flush(); 1911 return Str; 1912 } 1913 }; 1914 1915 } // end namespace llvm 1916 1917 #undef DEBUG_TYPE 1918 1919 #endif // LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H 1920