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/DenseMap.h" 18 #include "llvm/ADT/DenseSet.h" 19 #include "llvm/ADT/GraphTraits.h" 20 #include "llvm/ADT/Optional.h" 21 #include "llvm/ADT/PostOrderIterator.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/SparseBitVector.h" 24 #include "llvm/ADT/Twine.h" 25 #include "llvm/ADT/iterator_range.h" 26 #include "llvm/IR/BasicBlock.h" 27 #include "llvm/Support/BlockFrequency.h" 28 #include "llvm/Support/BranchProbability.h" 29 #include "llvm/Support/DOTGraphTraits.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/Format.h" 33 #include "llvm/Support/ScaledNumber.h" 34 #include "llvm/Support/raw_ostream.h" 35 #include <algorithm> 36 #include <cassert> 37 #include <cstddef> 38 #include <cstdint> 39 #include <deque> 40 #include <iterator> 41 #include <limits> 42 #include <list> 43 #include <string> 44 #include <utility> 45 #include <vector> 46 47 #define DEBUG_TYPE "block-freq" 48 49 namespace llvm { 50 51 class BranchProbabilityInfo; 52 class Function; 53 class Loop; 54 class LoopInfo; 55 class MachineBasicBlock; 56 class MachineBranchProbabilityInfo; 57 class MachineFunction; 58 class MachineLoop; 59 class MachineLoopInfo; 60 61 namespace bfi_detail { 62 63 struct IrreducibleGraph; 64 65 // This is part of a workaround for a GCC 4.7 crash on lambdas. 66 template <class BT> struct BlockEdgesAdder; 67 68 /// Mass of a block. 69 /// 70 /// This class implements a sort of fixed-point fraction always between 0.0 and 71 /// 1.0. getMass() == std::numeric_limits<uint64_t>::max() indicates a value of 72 /// 1.0. 73 /// 74 /// Masses can be added and subtracted. Simple saturation arithmetic is used, 75 /// so arithmetic operations never overflow or underflow. 76 /// 77 /// Masses can be multiplied. Multiplication treats full mass as 1.0 and uses 78 /// an inexpensive floating-point algorithm that's off-by-one (almost, but not 79 /// quite, maximum precision). 80 /// 81 /// Masses can be scaled by \a BranchProbability at maximum precision. 82 class BlockMass { 83 uint64_t Mass = 0; 84 85 public: 86 BlockMass() = default; 87 explicit BlockMass(uint64_t Mass) : Mass(Mass) {} 88 89 static BlockMass getEmpty() { return BlockMass(); } 90 91 static BlockMass getFull() { 92 return BlockMass(std::numeric_limits<uint64_t>::max()); 93 } 94 95 uint64_t getMass() const { return Mass; } 96 97 bool isFull() const { return Mass == std::numeric_limits<uint64_t>::max(); } 98 bool isEmpty() const { return !Mass; } 99 100 bool operator!() const { return isEmpty(); } 101 102 /// Add another mass. 103 /// 104 /// Adds another mass, saturating at \a isFull() rather than overflowing. 105 BlockMass &operator+=(BlockMass X) { 106 uint64_t Sum = Mass + X.Mass; 107 Mass = Sum < Mass ? std::numeric_limits<uint64_t>::max() : Sum; 108 return *this; 109 } 110 111 /// Subtract another mass. 112 /// 113 /// Subtracts another mass, saturating at \a isEmpty() rather than 114 /// undeflowing. 115 BlockMass &operator-=(BlockMass X) { 116 uint64_t Diff = Mass - X.Mass; 117 Mass = Diff > Mass ? 0 : Diff; 118 return *this; 119 } 120 121 BlockMass &operator*=(BranchProbability P) { 122 Mass = P.scale(Mass); 123 return *this; 124 } 125 126 bool operator==(BlockMass X) const { return Mass == X.Mass; } 127 bool operator!=(BlockMass X) const { return Mass != X.Mass; } 128 bool operator<=(BlockMass X) const { return Mass <= X.Mass; } 129 bool operator>=(BlockMass X) const { return Mass >= X.Mass; } 130 bool operator<(BlockMass X) const { return Mass < X.Mass; } 131 bool operator>(BlockMass X) const { return Mass > X.Mass; } 132 133 /// Convert to scaled number. 134 /// 135 /// Convert to \a ScaledNumber. \a isFull() gives 1.0, while \a isEmpty() 136 /// gives slightly above 0.0. 137 ScaledNumber<uint64_t> toScaled() const; 138 139 void dump() const; 140 raw_ostream &print(raw_ostream &OS) const; 141 }; 142 143 inline BlockMass operator+(BlockMass L, BlockMass R) { 144 return BlockMass(L) += R; 145 } 146 inline BlockMass operator-(BlockMass L, BlockMass R) { 147 return BlockMass(L) -= R; 148 } 149 inline BlockMass operator*(BlockMass L, BranchProbability R) { 150 return BlockMass(L) *= R; 151 } 152 inline BlockMass operator*(BranchProbability L, BlockMass R) { 153 return BlockMass(R) *= L; 154 } 155 156 inline raw_ostream &operator<<(raw_ostream &OS, BlockMass X) { 157 return X.print(OS); 158 } 159 160 } // end namespace bfi_detail 161 162 /// Base class for BlockFrequencyInfoImpl 163 /// 164 /// BlockFrequencyInfoImplBase has supporting data structures and some 165 /// algorithms for BlockFrequencyInfoImplBase. Only algorithms that depend on 166 /// the block type (or that call such algorithms) are skipped here. 167 /// 168 /// Nevertheless, the majority of the overall algorithm documention lives with 169 /// BlockFrequencyInfoImpl. See there for details. 170 class BlockFrequencyInfoImplBase { 171 public: 172 using Scaled64 = ScaledNumber<uint64_t>; 173 using BlockMass = bfi_detail::BlockMass; 174 175 /// Representative of a block. 176 /// 177 /// This is a simple wrapper around an index into the reverse-post-order 178 /// traversal of the blocks. 179 /// 180 /// Unlike a block pointer, its order has meaning (location in the 181 /// topological sort) and it's class is the same regardless of block type. 182 struct BlockNode { 183 using IndexType = uint32_t; 184 185 IndexType Index; 186 187 BlockNode() : Index(std::numeric_limits<uint32_t>::max()) {} 188 BlockNode(IndexType Index) : Index(Index) {} 189 190 bool operator==(const BlockNode &X) const { return Index == X.Index; } 191 bool operator!=(const BlockNode &X) const { return Index != X.Index; } 192 bool operator<=(const BlockNode &X) const { return Index <= X.Index; } 193 bool operator>=(const BlockNode &X) const { return Index >= X.Index; } 194 bool operator<(const BlockNode &X) const { return Index < X.Index; } 195 bool operator>(const BlockNode &X) const { return Index > X.Index; } 196 197 bool isValid() const { return Index <= getMaxIndex(); } 198 199 static size_t getMaxIndex() { 200 return std::numeric_limits<uint32_t>::max() - 1; 201 } 202 }; 203 204 /// Stats about a block itself. 205 struct FrequencyData { 206 Scaled64 Scaled; 207 uint64_t Integer; 208 }; 209 210 /// Data about a loop. 211 /// 212 /// Contains the data necessary to represent a loop as a pseudo-node once it's 213 /// packaged. 214 struct LoopData { 215 using ExitMap = SmallVector<std::pair<BlockNode, BlockMass>, 4>; 216 using NodeList = SmallVector<BlockNode, 4>; 217 using HeaderMassList = SmallVector<BlockMass, 1>; 218 219 LoopData *Parent; ///< The parent loop. 220 bool IsPackaged = false; ///< Whether this has been packaged. 221 uint32_t NumHeaders = 1; ///< Number of headers. 222 ExitMap Exits; ///< Successor edges (and weights). 223 NodeList Nodes; ///< Header and the members of the loop. 224 HeaderMassList BackedgeMass; ///< Mass returned to each loop header. 225 BlockMass Mass; 226 Scaled64 Scale; 227 228 LoopData(LoopData *Parent, const BlockNode &Header) 229 : Parent(Parent), Nodes(1, Header), BackedgeMass(1) {} 230 231 template <class It1, class It2> 232 LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther, 233 It2 LastOther) 234 : Parent(Parent), Nodes(FirstHeader, LastHeader) { 235 NumHeaders = Nodes.size(); 236 Nodes.insert(Nodes.end(), FirstOther, LastOther); 237 BackedgeMass.resize(NumHeaders); 238 } 239 240 bool isHeader(const BlockNode &Node) const { 241 if (isIrreducible()) 242 return std::binary_search(Nodes.begin(), Nodes.begin() + NumHeaders, 243 Node); 244 return Node == Nodes[0]; 245 } 246 247 BlockNode getHeader() const { return Nodes[0]; } 248 bool isIrreducible() const { return NumHeaders > 1; } 249 250 HeaderMassList::difference_type getHeaderIndex(const BlockNode &B) { 251 assert(isHeader(B) && "this is only valid on loop header blocks"); 252 if (isIrreducible()) 253 return std::lower_bound(Nodes.begin(), Nodes.begin() + NumHeaders, B) - 254 Nodes.begin(); 255 return 0; 256 } 257 258 NodeList::const_iterator members_begin() const { 259 return Nodes.begin() + NumHeaders; 260 } 261 262 NodeList::const_iterator members_end() const { return Nodes.end(); } 263 iterator_range<NodeList::const_iterator> members() const { 264 return make_range(members_begin(), members_end()); 265 } 266 }; 267 268 /// Index of loop information. 269 struct WorkingData { 270 BlockNode Node; ///< This node. 271 LoopData *Loop = nullptr; ///< The loop this block is inside. 272 BlockMass Mass; ///< Mass distribution from the entry block. 273 274 WorkingData(const BlockNode &Node) : Node(Node) {} 275 276 bool isLoopHeader() const { return Loop && Loop->isHeader(Node); } 277 278 bool isDoubleLoopHeader() const { 279 return isLoopHeader() && Loop->Parent && Loop->Parent->isIrreducible() && 280 Loop->Parent->isHeader(Node); 281 } 282 283 LoopData *getContainingLoop() const { 284 if (!isLoopHeader()) 285 return Loop; 286 if (!isDoubleLoopHeader()) 287 return Loop->Parent; 288 return Loop->Parent->Parent; 289 } 290 291 /// Resolve a node to its representative. 292 /// 293 /// Get the node currently representing Node, which could be a containing 294 /// loop. 295 /// 296 /// This function should only be called when distributing mass. As long as 297 /// there are no irreducible edges to Node, then it will have complexity 298 /// O(1) in this context. 299 /// 300 /// In general, the complexity is O(L), where L is the number of loop 301 /// headers Node has been packaged into. Since this method is called in 302 /// the context of distributing mass, L will be the number of loop headers 303 /// an early exit edge jumps out of. 304 BlockNode getResolvedNode() const { 305 auto L = getPackagedLoop(); 306 return L ? L->getHeader() : Node; 307 } 308 309 LoopData *getPackagedLoop() const { 310 if (!Loop || !Loop->IsPackaged) 311 return nullptr; 312 auto L = Loop; 313 while (L->Parent && L->Parent->IsPackaged) 314 L = L->Parent; 315 return L; 316 } 317 318 /// Get the appropriate mass for a node. 319 /// 320 /// Get appropriate mass for Node. If Node is a loop-header (whose loop 321 /// has been packaged), returns the mass of its pseudo-node. If it's a 322 /// node inside a packaged loop, it returns the loop's mass. 323 BlockMass &getMass() { 324 if (!isAPackage()) 325 return Mass; 326 if (!isADoublePackage()) 327 return Loop->Mass; 328 return Loop->Parent->Mass; 329 } 330 331 /// Has ContainingLoop been packaged up? 332 bool isPackaged() const { return getResolvedNode() != Node; } 333 334 /// Has Loop been packaged up? 335 bool isAPackage() const { return isLoopHeader() && Loop->IsPackaged; } 336 337 /// Has Loop been packaged up twice? 338 bool isADoublePackage() const { 339 return isDoubleLoopHeader() && Loop->Parent->IsPackaged; 340 } 341 }; 342 343 /// Unscaled probability weight. 344 /// 345 /// Probability weight for an edge in the graph (including the 346 /// successor/target node). 347 /// 348 /// All edges in the original function are 32-bit. However, exit edges from 349 /// loop packages are taken from 64-bit exit masses, so we need 64-bits of 350 /// space in general. 351 /// 352 /// In addition to the raw weight amount, Weight stores the type of the edge 353 /// in the current context (i.e., the context of the loop being processed). 354 /// Is this a local edge within the loop, an exit from the loop, or a 355 /// backedge to the loop header? 356 struct Weight { 357 enum DistType { Local, Exit, Backedge }; 358 DistType Type = Local; 359 BlockNode TargetNode; 360 uint64_t Amount = 0; 361 362 Weight() = default; 363 Weight(DistType Type, BlockNode TargetNode, uint64_t Amount) 364 : Type(Type), TargetNode(TargetNode), Amount(Amount) {} 365 }; 366 367 /// Distribution of unscaled probability weight. 368 /// 369 /// Distribution of unscaled probability weight to a set of successors. 370 /// 371 /// This class collates the successor edge weights for later processing. 372 /// 373 /// \a DidOverflow indicates whether \a Total did overflow while adding to 374 /// the distribution. It should never overflow twice. 375 struct Distribution { 376 using WeightList = SmallVector<Weight, 4>; 377 378 WeightList Weights; ///< Individual successor weights. 379 uint64_t Total = 0; ///< Sum of all weights. 380 bool DidOverflow = false; ///< Whether \a Total did overflow. 381 382 Distribution() = default; 383 384 void addLocal(const BlockNode &Node, uint64_t Amount) { 385 add(Node, Amount, Weight::Local); 386 } 387 388 void addExit(const BlockNode &Node, uint64_t Amount) { 389 add(Node, Amount, Weight::Exit); 390 } 391 392 void addBackedge(const BlockNode &Node, uint64_t Amount) { 393 add(Node, Amount, Weight::Backedge); 394 } 395 396 /// Normalize the distribution. 397 /// 398 /// Combines multiple edges to the same \a Weight::TargetNode and scales 399 /// down so that \a Total fits into 32-bits. 400 /// 401 /// This is linear in the size of \a Weights. For the vast majority of 402 /// cases, adjacent edge weights are combined by sorting WeightList and 403 /// combining adjacent weights. However, for very large edge lists an 404 /// auxiliary hash table is used. 405 void normalize(); 406 407 private: 408 void add(const BlockNode &Node, uint64_t Amount, Weight::DistType Type); 409 }; 410 411 /// Data about each block. This is used downstream. 412 std::vector<FrequencyData> Freqs; 413 414 /// Whether each block is an irreducible loop header. 415 /// This is used downstream. 416 SparseBitVector<> IsIrrLoopHeader; 417 418 /// Loop data: see initializeLoops(). 419 std::vector<WorkingData> Working; 420 421 /// Indexed information about loops. 422 std::list<LoopData> Loops; 423 424 /// Virtual destructor. 425 /// 426 /// Need a virtual destructor to mask the compiler warning about 427 /// getBlockName(). 428 virtual ~BlockFrequencyInfoImplBase() = default; 429 430 /// Add all edges out of a packaged loop to the distribution. 431 /// 432 /// Adds all edges from LocalLoopHead to Dist. Calls addToDist() to add each 433 /// successor edge. 434 /// 435 /// \return \c true unless there's an irreducible backedge. 436 bool addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop, 437 Distribution &Dist); 438 439 /// Add an edge to the distribution. 440 /// 441 /// Adds an edge to Succ to Dist. If \c LoopHead.isValid(), then whether the 442 /// edge is local/exit/backedge is in the context of LoopHead. Otherwise, 443 /// every edge should be a local edge (since all the loops are packaged up). 444 /// 445 /// \return \c true unless aborted due to an irreducible backedge. 446 bool addToDist(Distribution &Dist, const LoopData *OuterLoop, 447 const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight); 448 449 LoopData &getLoopPackage(const BlockNode &Head) { 450 assert(Head.Index < Working.size()); 451 assert(Working[Head.Index].isLoopHeader()); 452 return *Working[Head.Index].Loop; 453 } 454 455 /// Analyze irreducible SCCs. 456 /// 457 /// Separate irreducible SCCs from \c G, which is an explict graph of \c 458 /// OuterLoop (or the top-level function, if \c OuterLoop is \c nullptr). 459 /// Insert them into \a Loops before \c Insert. 460 /// 461 /// \return the \c LoopData nodes representing the irreducible SCCs. 462 iterator_range<std::list<LoopData>::iterator> 463 analyzeIrreducible(const bfi_detail::IrreducibleGraph &G, LoopData *OuterLoop, 464 std::list<LoopData>::iterator Insert); 465 466 /// Update a loop after packaging irreducible SCCs inside of it. 467 /// 468 /// Update \c OuterLoop. Before finding irreducible control flow, it was 469 /// partway through \a computeMassInLoop(), so \a LoopData::Exits and \a 470 /// LoopData::BackedgeMass need to be reset. Also, nodes that were packaged 471 /// up need to be removed from \a OuterLoop::Nodes. 472 void updateLoopWithIrreducible(LoopData &OuterLoop); 473 474 /// Distribute mass according to a distribution. 475 /// 476 /// Distributes the mass in Source according to Dist. If LoopHead.isValid(), 477 /// backedges and exits are stored in its entry in Loops. 478 /// 479 /// Mass is distributed in parallel from two copies of the source mass. 480 void distributeMass(const BlockNode &Source, LoopData *OuterLoop, 481 Distribution &Dist); 482 483 /// Compute the loop scale for a loop. 484 void computeLoopScale(LoopData &Loop); 485 486 /// Adjust the mass of all headers in an irreducible loop. 487 /// 488 /// Initially, irreducible loops are assumed to distribute their mass 489 /// equally among its headers. This can lead to wrong frequency estimates 490 /// since some headers may be executed more frequently than others. 491 /// 492 /// This adjusts header mass distribution so it matches the weights of 493 /// the backedges going into each of the loop headers. 494 void adjustLoopHeaderMass(LoopData &Loop); 495 496 void distributeIrrLoopHeaderMass(Distribution &Dist); 497 498 /// Package up a loop. 499 void packageLoop(LoopData &Loop); 500 501 /// Unwrap loops. 502 void unwrapLoops(); 503 504 /// Finalize frequency metrics. 505 /// 506 /// Calculates final frequencies and cleans up no-longer-needed data 507 /// structures. 508 void finalizeMetrics(); 509 510 /// Clear all memory. 511 void clear(); 512 513 virtual std::string getBlockName(const BlockNode &Node) const; 514 std::string getLoopName(const LoopData &Loop) const; 515 516 virtual raw_ostream &print(raw_ostream &OS) const { return OS; } 517 void dump() const { print(dbgs()); } 518 519 Scaled64 getFloatingBlockFreq(const BlockNode &Node) const; 520 521 BlockFrequency getBlockFreq(const BlockNode &Node) const; 522 Optional<uint64_t> getBlockProfileCount(const Function &F, 523 const BlockNode &Node, 524 bool AllowSynthetic = false) const; 525 Optional<uint64_t> getProfileCountFromFreq(const Function &F, 526 uint64_t Freq, 527 bool AllowSynthetic = false) const; 528 bool isIrrLoopHeader(const BlockNode &Node); 529 530 void setBlockFreq(const BlockNode &Node, uint64_t Freq); 531 532 raw_ostream &printBlockFreq(raw_ostream &OS, const BlockNode &Node) const; 533 raw_ostream &printBlockFreq(raw_ostream &OS, 534 const BlockFrequency &Freq) const; 535 536 uint64_t getEntryFreq() const { 537 assert(!Freqs.empty()); 538 return Freqs[0].Integer; 539 } 540 }; 541 542 namespace bfi_detail { 543 544 template <class BlockT> struct TypeMap {}; 545 template <> struct TypeMap<BasicBlock> { 546 using BlockT = BasicBlock; 547 using FunctionT = Function; 548 using BranchProbabilityInfoT = BranchProbabilityInfo; 549 using LoopT = Loop; 550 using LoopInfoT = LoopInfo; 551 }; 552 template <> struct TypeMap<MachineBasicBlock> { 553 using BlockT = MachineBasicBlock; 554 using FunctionT = MachineFunction; 555 using BranchProbabilityInfoT = MachineBranchProbabilityInfo; 556 using LoopT = MachineLoop; 557 using LoopInfoT = MachineLoopInfo; 558 }; 559 560 /// Get the name of a MachineBasicBlock. 561 /// 562 /// Get the name of a MachineBasicBlock. It's templated so that including from 563 /// CodeGen is unnecessary (that would be a layering issue). 564 /// 565 /// This is used mainly for debug output. The name is similar to 566 /// MachineBasicBlock::getFullName(), but skips the name of the function. 567 template <class BlockT> std::string getBlockName(const BlockT *BB) { 568 assert(BB && "Unexpected nullptr"); 569 auto MachineName = "BB" + Twine(BB->getNumber()); 570 if (BB->getBasicBlock()) 571 return (MachineName + "[" + BB->getName() + "]").str(); 572 return MachineName.str(); 573 } 574 /// Get the name of a BasicBlock. 575 template <> inline std::string getBlockName(const BasicBlock *BB) { 576 assert(BB && "Unexpected nullptr"); 577 return BB->getName().str(); 578 } 579 580 /// Graph of irreducible control flow. 581 /// 582 /// This graph is used for determining the SCCs in a loop (or top-level 583 /// function) that has irreducible control flow. 584 /// 585 /// During the block frequency algorithm, the local graphs are defined in a 586 /// light-weight way, deferring to the \a BasicBlock or \a MachineBasicBlock 587 /// graphs for most edges, but getting others from \a LoopData::ExitMap. The 588 /// latter only has successor information. 589 /// 590 /// \a IrreducibleGraph makes this graph explicit. It's in a form that can use 591 /// \a GraphTraits (so that \a analyzeIrreducible() can use \a scc_iterator), 592 /// and it explicitly lists predecessors and successors. The initialization 593 /// that relies on \c MachineBasicBlock is defined in the header. 594 struct IrreducibleGraph { 595 using BFIBase = BlockFrequencyInfoImplBase; 596 597 BFIBase &BFI; 598 599 using BlockNode = BFIBase::BlockNode; 600 struct IrrNode { 601 BlockNode Node; 602 unsigned NumIn = 0; 603 std::deque<const IrrNode *> Edges; 604 605 IrrNode(const BlockNode &Node) : Node(Node) {} 606 607 using iterator = std::deque<const IrrNode *>::const_iterator; 608 609 iterator pred_begin() const { return Edges.begin(); } 610 iterator succ_begin() const { return Edges.begin() + NumIn; } 611 iterator pred_end() const { return succ_begin(); } 612 iterator succ_end() const { return Edges.end(); } 613 }; 614 BlockNode Start; 615 const IrrNode *StartIrr = nullptr; 616 std::vector<IrrNode> Nodes; 617 SmallDenseMap<uint32_t, IrrNode *, 4> Lookup; 618 619 /// Construct an explicit graph containing irreducible control flow. 620 /// 621 /// Construct an explicit graph of the control flow in \c OuterLoop (or the 622 /// top-level function, if \c OuterLoop is \c nullptr). Uses \c 623 /// addBlockEdges to add block successors that have not been packaged into 624 /// loops. 625 /// 626 /// \a BlockFrequencyInfoImpl::computeIrreducibleMass() is the only expected 627 /// user of this. 628 template <class BlockEdgesAdder> 629 IrreducibleGraph(BFIBase &BFI, const BFIBase::LoopData *OuterLoop, 630 BlockEdgesAdder addBlockEdges) : BFI(BFI) { 631 initialize(OuterLoop, addBlockEdges); 632 } 633 634 template <class BlockEdgesAdder> 635 void initialize(const BFIBase::LoopData *OuterLoop, 636 BlockEdgesAdder addBlockEdges); 637 void addNodesInLoop(const BFIBase::LoopData &OuterLoop); 638 void addNodesInFunction(); 639 640 void addNode(const BlockNode &Node) { 641 Nodes.emplace_back(Node); 642 BFI.Working[Node.Index].getMass() = BlockMass::getEmpty(); 643 } 644 645 void indexNodes(); 646 template <class BlockEdgesAdder> 647 void addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop, 648 BlockEdgesAdder addBlockEdges); 649 void addEdge(IrrNode &Irr, const BlockNode &Succ, 650 const BFIBase::LoopData *OuterLoop); 651 }; 652 653 template <class BlockEdgesAdder> 654 void IrreducibleGraph::initialize(const BFIBase::LoopData *OuterLoop, 655 BlockEdgesAdder addBlockEdges) { 656 if (OuterLoop) { 657 addNodesInLoop(*OuterLoop); 658 for (auto N : OuterLoop->Nodes) 659 addEdges(N, OuterLoop, addBlockEdges); 660 } else { 661 addNodesInFunction(); 662 for (uint32_t Index = 0; Index < BFI.Working.size(); ++Index) 663 addEdges(Index, OuterLoop, addBlockEdges); 664 } 665 StartIrr = Lookup[Start.Index]; 666 } 667 668 template <class BlockEdgesAdder> 669 void IrreducibleGraph::addEdges(const BlockNode &Node, 670 const BFIBase::LoopData *OuterLoop, 671 BlockEdgesAdder addBlockEdges) { 672 auto L = Lookup.find(Node.Index); 673 if (L == Lookup.end()) 674 return; 675 IrrNode &Irr = *L->second; 676 const auto &Working = BFI.Working[Node.Index]; 677 678 if (Working.isAPackage()) 679 for (const auto &I : Working.Loop->Exits) 680 addEdge(Irr, I.first, OuterLoop); 681 else 682 addBlockEdges(*this, Irr, OuterLoop); 683 } 684 685 } // end namespace bfi_detail 686 687 /// Shared implementation for block frequency analysis. 688 /// 689 /// This is a shared implementation of BlockFrequencyInfo and 690 /// MachineBlockFrequencyInfo, and calculates the relative frequencies of 691 /// blocks. 692 /// 693 /// LoopInfo defines a loop as a "non-trivial" SCC dominated by a single block, 694 /// which is called the header. A given loop, L, can have sub-loops, which are 695 /// loops within the subgraph of L that exclude its header. (A "trivial" SCC 696 /// consists of a single block that does not have a self-edge.) 697 /// 698 /// In addition to loops, this algorithm has limited support for irreducible 699 /// SCCs, which are SCCs with multiple entry blocks. Irreducible SCCs are 700 /// discovered on they fly, and modelled as loops with multiple headers. 701 /// 702 /// The headers of irreducible sub-SCCs consist of its entry blocks and all 703 /// nodes that are targets of a backedge within it (excluding backedges within 704 /// true sub-loops). Block frequency calculations act as if a block is 705 /// inserted that intercepts all the edges to the headers. All backedges and 706 /// entries point to this block. Its successors are the headers, which split 707 /// the frequency evenly. 708 /// 709 /// This algorithm leverages BlockMass and ScaledNumber to maintain precision, 710 /// separates mass distribution from loop scaling, and dithers to eliminate 711 /// probability mass loss. 712 /// 713 /// The implementation is split between BlockFrequencyInfoImpl, which knows the 714 /// type of graph being modelled (BasicBlock vs. MachineBasicBlock), and 715 /// BlockFrequencyInfoImplBase, which doesn't. The base class uses \a 716 /// BlockNode, a wrapper around a uint32_t. BlockNode is numbered from 0 in 717 /// reverse-post order. This gives two advantages: it's easy to compare the 718 /// relative ordering of two nodes, and maps keyed on BlockT can be represented 719 /// by vectors. 720 /// 721 /// This algorithm is O(V+E), unless there is irreducible control flow, in 722 /// which case it's O(V*E) in the worst case. 723 /// 724 /// These are the main stages: 725 /// 726 /// 0. Reverse post-order traversal (\a initializeRPOT()). 727 /// 728 /// Run a single post-order traversal and save it (in reverse) in RPOT. 729 /// All other stages make use of this ordering. Save a lookup from BlockT 730 /// to BlockNode (the index into RPOT) in Nodes. 731 /// 732 /// 1. Loop initialization (\a initializeLoops()). 733 /// 734 /// Translate LoopInfo/MachineLoopInfo into a form suitable for the rest of 735 /// the algorithm. In particular, store the immediate members of each loop 736 /// in reverse post-order. 737 /// 738 /// 2. Calculate mass and scale in loops (\a computeMassInLoops()). 739 /// 740 /// For each loop (bottom-up), distribute mass through the DAG resulting 741 /// from ignoring backedges and treating sub-loops as a single pseudo-node. 742 /// Track the backedge mass distributed to the loop header, and use it to 743 /// calculate the loop scale (number of loop iterations). Immediate 744 /// members that represent sub-loops will already have been visited and 745 /// packaged into a pseudo-node. 746 /// 747 /// Distributing mass in a loop is a reverse-post-order traversal through 748 /// the loop. Start by assigning full mass to the Loop header. For each 749 /// node in the loop: 750 /// 751 /// - Fetch and categorize the weight distribution for its successors. 752 /// If this is a packaged-subloop, the weight distribution is stored 753 /// in \a LoopData::Exits. Otherwise, fetch it from 754 /// BranchProbabilityInfo. 755 /// 756 /// - Each successor is categorized as \a Weight::Local, a local edge 757 /// within the current loop, \a Weight::Backedge, a backedge to the 758 /// loop header, or \a Weight::Exit, any successor outside the loop. 759 /// The weight, the successor, and its category are stored in \a 760 /// Distribution. There can be multiple edges to each successor. 761 /// 762 /// - If there's a backedge to a non-header, there's an irreducible SCC. 763 /// The usual flow is temporarily aborted. \a 764 /// computeIrreducibleMass() finds the irreducible SCCs within the 765 /// loop, packages them up, and restarts the flow. 766 /// 767 /// - Normalize the distribution: scale weights down so that their sum 768 /// is 32-bits, and coalesce multiple edges to the same node. 769 /// 770 /// - Distribute the mass accordingly, dithering to minimize mass loss, 771 /// as described in \a distributeMass(). 772 /// 773 /// In the case of irreducible loops, instead of a single loop header, 774 /// there will be several. The computation of backedge masses is similar 775 /// but instead of having a single backedge mass, there will be one 776 /// backedge per loop header. In these cases, each backedge will carry 777 /// a mass proportional to the edge weights along the corresponding 778 /// path. 779 /// 780 /// At the end of propagation, the full mass assigned to the loop will be 781 /// distributed among the loop headers proportionally according to the 782 /// mass flowing through their backedges. 783 /// 784 /// Finally, calculate the loop scale from the accumulated backedge mass. 785 /// 786 /// 3. Distribute mass in the function (\a computeMassInFunction()). 787 /// 788 /// Finally, distribute mass through the DAG resulting from packaging all 789 /// loops in the function. This uses the same algorithm as distributing 790 /// mass in a loop, except that there are no exit or backedge edges. 791 /// 792 /// 4. Unpackage loops (\a unwrapLoops()). 793 /// 794 /// Initialize each block's frequency to a floating point representation of 795 /// its mass. 796 /// 797 /// Visit loops top-down, scaling the frequencies of its immediate members 798 /// by the loop's pseudo-node's frequency. 799 /// 800 /// 5. Convert frequencies to a 64-bit range (\a finalizeMetrics()). 801 /// 802 /// Using the min and max frequencies as a guide, translate floating point 803 /// frequencies to an appropriate range in uint64_t. 804 /// 805 /// It has some known flaws. 806 /// 807 /// - The model of irreducible control flow is a rough approximation. 808 /// 809 /// Modelling irreducible control flow exactly involves setting up and 810 /// solving a group of infinite geometric series. Such precision is 811 /// unlikely to be worthwhile, since most of our algorithms give up on 812 /// irreducible control flow anyway. 813 /// 814 /// Nevertheless, we might find that we need to get closer. Here's a sort 815 /// of TODO list for the model with diminishing returns, to be completed as 816 /// necessary. 817 /// 818 /// - The headers for the \a LoopData representing an irreducible SCC 819 /// include non-entry blocks. When these extra blocks exist, they 820 /// indicate a self-contained irreducible sub-SCC. We could treat them 821 /// as sub-loops, rather than arbitrarily shoving the problematic 822 /// blocks into the headers of the main irreducible SCC. 823 /// 824 /// - Entry frequencies are assumed to be evenly split between the 825 /// headers of a given irreducible SCC, which is the only option if we 826 /// need to compute mass in the SCC before its parent loop. Instead, 827 /// we could partially compute mass in the parent loop, and stop when 828 /// we get to the SCC. Here, we have the correct ratio of entry 829 /// masses, which we can use to adjust their relative frequencies. 830 /// Compute mass in the SCC, and then continue propagation in the 831 /// parent. 832 /// 833 /// - We can propagate mass iteratively through the SCC, for some fixed 834 /// number of iterations. Each iteration starts by assigning the entry 835 /// blocks their backedge mass from the prior iteration. The final 836 /// mass for each block (and each exit, and the total backedge mass 837 /// used for computing loop scale) is the sum of all iterations. 838 /// (Running this until fixed point would "solve" the geometric 839 /// series by simulation.) 840 template <class BT> class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { 841 // This is part of a workaround for a GCC 4.7 crash on lambdas. 842 friend struct bfi_detail::BlockEdgesAdder<BT>; 843 844 using BlockT = typename bfi_detail::TypeMap<BT>::BlockT; 845 using FunctionT = typename bfi_detail::TypeMap<BT>::FunctionT; 846 using BranchProbabilityInfoT = 847 typename bfi_detail::TypeMap<BT>::BranchProbabilityInfoT; 848 using LoopT = typename bfi_detail::TypeMap<BT>::LoopT; 849 using LoopInfoT = typename bfi_detail::TypeMap<BT>::LoopInfoT; 850 using Successor = GraphTraits<const BlockT *>; 851 using Predecessor = GraphTraits<Inverse<const BlockT *>>; 852 853 const BranchProbabilityInfoT *BPI = nullptr; 854 const LoopInfoT *LI = nullptr; 855 const FunctionT *F = nullptr; 856 857 // All blocks in reverse postorder. 858 std::vector<const BlockT *> RPOT; 859 DenseMap<const BlockT *, BlockNode> Nodes; 860 861 using rpot_iterator = typename std::vector<const BlockT *>::const_iterator; 862 863 rpot_iterator rpot_begin() const { return RPOT.begin(); } 864 rpot_iterator rpot_end() const { return RPOT.end(); } 865 866 size_t getIndex(const rpot_iterator &I) const { return I - rpot_begin(); } 867 868 BlockNode getNode(const rpot_iterator &I) const { 869 return BlockNode(getIndex(I)); 870 } 871 BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB); } 872 873 const BlockT *getBlock(const BlockNode &Node) const { 874 assert(Node.Index < RPOT.size()); 875 return RPOT[Node.Index]; 876 } 877 878 /// Run (and save) a post-order traversal. 879 /// 880 /// Saves a reverse post-order traversal of all the nodes in \a F. 881 void initializeRPOT(); 882 883 /// Initialize loop data. 884 /// 885 /// Build up \a Loops using \a LoopInfo. \a LoopInfo gives us a mapping from 886 /// each block to the deepest loop it's in, but we need the inverse. For each 887 /// loop, we store in reverse post-order its "immediate" members, defined as 888 /// the header, the headers of immediate sub-loops, and all other blocks in 889 /// the loop that are not in sub-loops. 890 void initializeLoops(); 891 892 /// Propagate to a block's successors. 893 /// 894 /// In the context of distributing mass through \c OuterLoop, divide the mass 895 /// currently assigned to \c Node between its successors. 896 /// 897 /// \return \c true unless there's an irreducible backedge. 898 bool propagateMassToSuccessors(LoopData *OuterLoop, const BlockNode &Node); 899 900 /// Compute mass in a particular loop. 901 /// 902 /// Assign mass to \c Loop's header, and then for each block in \c Loop in 903 /// reverse post-order, distribute mass to its successors. Only visits nodes 904 /// that have not been packaged into sub-loops. 905 /// 906 /// \pre \a computeMassInLoop() has been called for each subloop of \c Loop. 907 /// \return \c true unless there's an irreducible backedge. 908 bool computeMassInLoop(LoopData &Loop); 909 910 /// Try to compute mass in the top-level function. 911 /// 912 /// Assign mass to the entry block, and then for each block in reverse 913 /// post-order, distribute mass to its successors. Skips nodes that have 914 /// been packaged into loops. 915 /// 916 /// \pre \a computeMassInLoops() has been called. 917 /// \return \c true unless there's an irreducible backedge. 918 bool tryToComputeMassInFunction(); 919 920 /// Compute mass in (and package up) irreducible SCCs. 921 /// 922 /// Find the irreducible SCCs in \c OuterLoop, add them to \a Loops (in front 923 /// of \c Insert), and call \a computeMassInLoop() on each of them. 924 /// 925 /// If \c OuterLoop is \c nullptr, it refers to the top-level function. 926 /// 927 /// \pre \a computeMassInLoop() has been called for each subloop of \c 928 /// OuterLoop. 929 /// \pre \c Insert points at the last loop successfully processed by \a 930 /// computeMassInLoop(). 931 /// \pre \c OuterLoop has irreducible SCCs. 932 void computeIrreducibleMass(LoopData *OuterLoop, 933 std::list<LoopData>::iterator Insert); 934 935 /// Compute mass in all loops. 936 /// 937 /// For each loop bottom-up, call \a computeMassInLoop(). 938 /// 939 /// \a computeMassInLoop() aborts (and returns \c false) on loops that 940 /// contain a irreducible sub-SCCs. Use \a computeIrreducibleMass() and then 941 /// re-enter \a computeMassInLoop(). 942 /// 943 /// \post \a computeMassInLoop() has returned \c true for every loop. 944 void computeMassInLoops(); 945 946 /// Compute mass in the top-level function. 947 /// 948 /// Uses \a tryToComputeMassInFunction() and \a computeIrreducibleMass() to 949 /// compute mass in the top-level function. 950 /// 951 /// \post \a tryToComputeMassInFunction() has returned \c true. 952 void computeMassInFunction(); 953 954 std::string getBlockName(const BlockNode &Node) const override { 955 return bfi_detail::getBlockName(getBlock(Node)); 956 } 957 958 public: 959 BlockFrequencyInfoImpl() = default; 960 961 const FunctionT *getFunction() const { return F; } 962 963 void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, 964 const LoopInfoT &LI); 965 966 using BlockFrequencyInfoImplBase::getEntryFreq; 967 968 BlockFrequency getBlockFreq(const BlockT *BB) const { 969 return BlockFrequencyInfoImplBase::getBlockFreq(getNode(BB)); 970 } 971 972 Optional<uint64_t> getBlockProfileCount(const Function &F, 973 const BlockT *BB, 974 bool AllowSynthetic = false) const { 975 return BlockFrequencyInfoImplBase::getBlockProfileCount(F, getNode(BB), 976 AllowSynthetic); 977 } 978 979 Optional<uint64_t> getProfileCountFromFreq(const Function &F, 980 uint64_t Freq, 981 bool AllowSynthetic = false) const { 982 return BlockFrequencyInfoImplBase::getProfileCountFromFreq(F, Freq, 983 AllowSynthetic); 984 } 985 986 bool isIrrLoopHeader(const BlockT *BB) { 987 return BlockFrequencyInfoImplBase::isIrrLoopHeader(getNode(BB)); 988 } 989 990 void setBlockFreq(const BlockT *BB, uint64_t Freq); 991 992 Scaled64 getFloatingBlockFreq(const BlockT *BB) const { 993 return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB)); 994 } 995 996 const BranchProbabilityInfoT &getBPI() const { return *BPI; } 997 998 /// Print the frequencies for the current function. 999 /// 1000 /// Prints the frequencies for the blocks in the current function. 1001 /// 1002 /// Blocks are printed in the natural iteration order of the function, rather 1003 /// than reverse post-order. This provides two advantages: writing -analyze 1004 /// tests is easier (since blocks come out in source order), and even 1005 /// unreachable blocks are printed. 1006 /// 1007 /// \a BlockFrequencyInfoImplBase::print() only knows reverse post-order, so 1008 /// we need to override it here. 1009 raw_ostream &print(raw_ostream &OS) const override; 1010 1011 using BlockFrequencyInfoImplBase::dump; 1012 using BlockFrequencyInfoImplBase::printBlockFreq; 1013 1014 raw_ostream &printBlockFreq(raw_ostream &OS, const BlockT *BB) const { 1015 return BlockFrequencyInfoImplBase::printBlockFreq(OS, getNode(BB)); 1016 } 1017 }; 1018 1019 template <class BT> 1020 void BlockFrequencyInfoImpl<BT>::calculate(const FunctionT &F, 1021 const BranchProbabilityInfoT &BPI, 1022 const LoopInfoT &LI) { 1023 // Save the parameters. 1024 this->BPI = &BPI; 1025 this->LI = &LI; 1026 this->F = &F; 1027 1028 // Clean up left-over data structures. 1029 BlockFrequencyInfoImplBase::clear(); 1030 RPOT.clear(); 1031 Nodes.clear(); 1032 1033 // Initialize. 1034 LLVM_DEBUG(dbgs() << "\nblock-frequency: " << F.getName() 1035 << "\n=================" 1036 << std::string(F.getName().size(), '=') << "\n"); 1037 initializeRPOT(); 1038 initializeLoops(); 1039 1040 // Visit loops in post-order to find the local mass distribution, and then do 1041 // the full function. 1042 computeMassInLoops(); 1043 computeMassInFunction(); 1044 unwrapLoops(); 1045 finalizeMetrics(); 1046 } 1047 1048 template <class BT> 1049 void BlockFrequencyInfoImpl<BT>::setBlockFreq(const BlockT *BB, uint64_t Freq) { 1050 if (Nodes.count(BB)) 1051 BlockFrequencyInfoImplBase::setBlockFreq(getNode(BB), Freq); 1052 else { 1053 // If BB is a newly added block after BFI is done, we need to create a new 1054 // BlockNode for it assigned with a new index. The index can be determined 1055 // by the size of Freqs. 1056 BlockNode NewNode(Freqs.size()); 1057 Nodes[BB] = NewNode; 1058 Freqs.emplace_back(); 1059 BlockFrequencyInfoImplBase::setBlockFreq(NewNode, Freq); 1060 } 1061 } 1062 1063 template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() { 1064 const BlockT *Entry = &F->front(); 1065 RPOT.reserve(F->size()); 1066 std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT)); 1067 std::reverse(RPOT.begin(), RPOT.end()); 1068 1069 assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() && 1070 "More nodes in function than Block Frequency Info supports"); 1071 1072 LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n"); 1073 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) { 1074 BlockNode Node = getNode(I); 1075 LLVM_DEBUG(dbgs() << " - " << getIndex(I) << ": " << getBlockName(Node) 1076 << "\n"); 1077 Nodes[*I] = Node; 1078 } 1079 1080 Working.reserve(RPOT.size()); 1081 for (size_t Index = 0; Index < RPOT.size(); ++Index) 1082 Working.emplace_back(Index); 1083 Freqs.resize(RPOT.size()); 1084 } 1085 1086 template <class BT> void BlockFrequencyInfoImpl<BT>::initializeLoops() { 1087 LLVM_DEBUG(dbgs() << "loop-detection\n"); 1088 if (LI->empty()) 1089 return; 1090 1091 // Visit loops top down and assign them an index. 1092 std::deque<std::pair<const LoopT *, LoopData *>> Q; 1093 for (const LoopT *L : *LI) 1094 Q.emplace_back(L, nullptr); 1095 while (!Q.empty()) { 1096 const LoopT *Loop = Q.front().first; 1097 LoopData *Parent = Q.front().second; 1098 Q.pop_front(); 1099 1100 BlockNode Header = getNode(Loop->getHeader()); 1101 assert(Header.isValid()); 1102 1103 Loops.emplace_back(Parent, Header); 1104 Working[Header.Index].Loop = &Loops.back(); 1105 LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header) << "\n"); 1106 1107 for (const LoopT *L : *Loop) 1108 Q.emplace_back(L, &Loops.back()); 1109 } 1110 1111 // Visit nodes in reverse post-order and add them to their deepest containing 1112 // loop. 1113 for (size_t Index = 0; Index < RPOT.size(); ++Index) { 1114 // Loop headers have already been mostly mapped. 1115 if (Working[Index].isLoopHeader()) { 1116 LoopData *ContainingLoop = Working[Index].getContainingLoop(); 1117 if (ContainingLoop) 1118 ContainingLoop->Nodes.push_back(Index); 1119 continue; 1120 } 1121 1122 const LoopT *Loop = LI->getLoopFor(RPOT[Index]); 1123 if (!Loop) 1124 continue; 1125 1126 // Add this node to its containing loop's member list. 1127 BlockNode Header = getNode(Loop->getHeader()); 1128 assert(Header.isValid()); 1129 const auto &HeaderData = Working[Header.Index]; 1130 assert(HeaderData.isLoopHeader()); 1131 1132 Working[Index].Loop = HeaderData.Loop; 1133 HeaderData.Loop->Nodes.push_back(Index); 1134 LLVM_DEBUG(dbgs() << " - loop = " << getBlockName(Header) 1135 << ": member = " << getBlockName(Index) << "\n"); 1136 } 1137 } 1138 1139 template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInLoops() { 1140 // Visit loops with the deepest first, and the top-level loops last. 1141 for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; ++L) { 1142 if (computeMassInLoop(*L)) 1143 continue; 1144 auto Next = std::next(L); 1145 computeIrreducibleMass(&*L, L.base()); 1146 L = std::prev(Next); 1147 if (computeMassInLoop(*L)) 1148 continue; 1149 llvm_unreachable("unhandled irreducible control flow"); 1150 } 1151 } 1152 1153 template <class BT> 1154 bool BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) { 1155 // Compute mass in loop. 1156 LLVM_DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop) << "\n"); 1157 1158 if (Loop.isIrreducible()) { 1159 LLVM_DEBUG(dbgs() << "isIrreducible = true\n"); 1160 Distribution Dist; 1161 unsigned NumHeadersWithWeight = 0; 1162 Optional<uint64_t> MinHeaderWeight; 1163 DenseSet<uint32_t> HeadersWithoutWeight; 1164 HeadersWithoutWeight.reserve(Loop.NumHeaders); 1165 for (uint32_t H = 0; H < Loop.NumHeaders; ++H) { 1166 auto &HeaderNode = Loop.Nodes[H]; 1167 const BlockT *Block = getBlock(HeaderNode); 1168 IsIrrLoopHeader.set(Loop.Nodes[H].Index); 1169 Optional<uint64_t> HeaderWeight = Block->getIrrLoopHeaderWeight(); 1170 if (!HeaderWeight) { 1171 LLVM_DEBUG(dbgs() << "Missing irr loop header metadata on " 1172 << getBlockName(HeaderNode) << "\n"); 1173 HeadersWithoutWeight.insert(H); 1174 continue; 1175 } 1176 LLVM_DEBUG(dbgs() << getBlockName(HeaderNode) 1177 << " has irr loop header weight " 1178 << HeaderWeight.getValue() << "\n"); 1179 NumHeadersWithWeight++; 1180 uint64_t HeaderWeightValue = HeaderWeight.getValue(); 1181 if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight) 1182 MinHeaderWeight = HeaderWeightValue; 1183 if (HeaderWeightValue) { 1184 Dist.addLocal(HeaderNode, HeaderWeightValue); 1185 } 1186 } 1187 // As a heuristic, if some headers don't have a weight, give them the 1188 // minimium weight seen (not to disrupt the existing trends too much by 1189 // using a weight that's in the general range of the other headers' weights, 1190 // and the minimum seems to perform better than the average.) 1191 // FIXME: better update in the passes that drop the header weight. 1192 // If no headers have a weight, give them even weight (use weight 1). 1193 if (!MinHeaderWeight) 1194 MinHeaderWeight = 1; 1195 for (uint32_t H : HeadersWithoutWeight) { 1196 auto &HeaderNode = Loop.Nodes[H]; 1197 assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() && 1198 "Shouldn't have a weight metadata"); 1199 uint64_t MinWeight = MinHeaderWeight.getValue(); 1200 LLVM_DEBUG(dbgs() << "Giving weight " << MinWeight << " to " 1201 << getBlockName(HeaderNode) << "\n"); 1202 if (MinWeight) 1203 Dist.addLocal(HeaderNode, MinWeight); 1204 } 1205 distributeIrrLoopHeaderMass(Dist); 1206 for (const BlockNode &M : Loop.Nodes) 1207 if (!propagateMassToSuccessors(&Loop, M)) 1208 llvm_unreachable("unhandled irreducible control flow"); 1209 if (NumHeadersWithWeight == 0) 1210 // No headers have a metadata. Adjust header mass. 1211 adjustLoopHeaderMass(Loop); 1212 } else { 1213 Working[Loop.getHeader().Index].getMass() = BlockMass::getFull(); 1214 if (!propagateMassToSuccessors(&Loop, Loop.getHeader())) 1215 llvm_unreachable("irreducible control flow to loop header!?"); 1216 for (const BlockNode &M : Loop.members()) 1217 if (!propagateMassToSuccessors(&Loop, M)) 1218 // Irreducible backedge. 1219 return false; 1220 } 1221 1222 computeLoopScale(Loop); 1223 packageLoop(Loop); 1224 return true; 1225 } 1226 1227 template <class BT> 1228 bool BlockFrequencyInfoImpl<BT>::tryToComputeMassInFunction() { 1229 // Compute mass in function. 1230 LLVM_DEBUG(dbgs() << "compute-mass-in-function\n"); 1231 assert(!Working.empty() && "no blocks in function"); 1232 assert(!Working[0].isLoopHeader() && "entry block is a loop header"); 1233 1234 Working[0].getMass() = BlockMass::getFull(); 1235 for (rpot_iterator I = rpot_begin(), IE = rpot_end(); I != IE; ++I) { 1236 // Check for nodes that have been packaged. 1237 BlockNode Node = getNode(I); 1238 if (Working[Node.Index].isPackaged()) 1239 continue; 1240 1241 if (!propagateMassToSuccessors(nullptr, Node)) 1242 return false; 1243 } 1244 return true; 1245 } 1246 1247 template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() { 1248 if (tryToComputeMassInFunction()) 1249 return; 1250 computeIrreducibleMass(nullptr, Loops.begin()); 1251 if (tryToComputeMassInFunction()) 1252 return; 1253 llvm_unreachable("unhandled irreducible control flow"); 1254 } 1255 1256 /// \note This should be a lambda, but that crashes GCC 4.7. 1257 namespace bfi_detail { 1258 1259 template <class BT> struct BlockEdgesAdder { 1260 using BlockT = BT; 1261 using LoopData = BlockFrequencyInfoImplBase::LoopData; 1262 using Successor = GraphTraits<const BlockT *>; 1263 1264 const BlockFrequencyInfoImpl<BT> &BFI; 1265 1266 explicit BlockEdgesAdder(const BlockFrequencyInfoImpl<BT> &BFI) 1267 : BFI(BFI) {} 1268 1269 void operator()(IrreducibleGraph &G, IrreducibleGraph::IrrNode &Irr, 1270 const LoopData *OuterLoop) { 1271 const BlockT *BB = BFI.RPOT[Irr.Node.Index]; 1272 for (const auto Succ : children<const BlockT *>(BB)) 1273 G.addEdge(Irr, BFI.getNode(Succ), OuterLoop); 1274 } 1275 }; 1276 1277 } // end namespace bfi_detail 1278 1279 template <class BT> 1280 void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass( 1281 LoopData *OuterLoop, std::list<LoopData>::iterator Insert) { 1282 LLVM_DEBUG(dbgs() << "analyze-irreducible-in-"; 1283 if (OuterLoop) dbgs() 1284 << "loop: " << getLoopName(*OuterLoop) << "\n"; 1285 else dbgs() << "function\n"); 1286 1287 using namespace bfi_detail; 1288 1289 // Ideally, addBlockEdges() would be declared here as a lambda, but that 1290 // crashes GCC 4.7. 1291 BlockEdgesAdder<BT> addBlockEdges(*this); 1292 IrreducibleGraph G(*this, OuterLoop, addBlockEdges); 1293 1294 for (auto &L : analyzeIrreducible(G, OuterLoop, Insert)) 1295 computeMassInLoop(L); 1296 1297 if (!OuterLoop) 1298 return; 1299 updateLoopWithIrreducible(*OuterLoop); 1300 } 1301 1302 // A helper function that converts a branch probability into weight. 1303 inline uint32_t getWeightFromBranchProb(const BranchProbability Prob) { 1304 return Prob.getNumerator(); 1305 } 1306 1307 template <class BT> 1308 bool 1309 BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop, 1310 const BlockNode &Node) { 1311 LLVM_DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n"); 1312 // Calculate probability for successors. 1313 Distribution Dist; 1314 if (auto *Loop = Working[Node.Index].getPackagedLoop()) { 1315 assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop"); 1316 if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist)) 1317 // Irreducible backedge. 1318 return false; 1319 } else { 1320 const BlockT *BB = getBlock(Node); 1321 for (auto SI = GraphTraits<const BlockT *>::child_begin(BB), 1322 SE = GraphTraits<const BlockT *>::child_end(BB); 1323 SI != SE; ++SI) 1324 if (!addToDist( 1325 Dist, OuterLoop, Node, getNode(*SI), 1326 getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI)))) 1327 // Irreducible backedge. 1328 return false; 1329 } 1330 1331 // Distribute mass to successors, saving exit and backedge data in the 1332 // loop header. 1333 distributeMass(Node, OuterLoop, Dist); 1334 return true; 1335 } 1336 1337 template <class BT> 1338 raw_ostream &BlockFrequencyInfoImpl<BT>::print(raw_ostream &OS) const { 1339 if (!F) 1340 return OS; 1341 OS << "block-frequency-info: " << F->getName() << "\n"; 1342 for (const BlockT &BB : *F) { 1343 OS << " - " << bfi_detail::getBlockName(&BB) << ": float = "; 1344 getFloatingBlockFreq(&BB).print(OS, 5) 1345 << ", int = " << getBlockFreq(&BB).getFrequency(); 1346 if (Optional<uint64_t> ProfileCount = 1347 BlockFrequencyInfoImplBase::getBlockProfileCount( 1348 F->getFunction(), getNode(&BB))) 1349 OS << ", count = " << ProfileCount.getValue(); 1350 if (Optional<uint64_t> IrrLoopHeaderWeight = 1351 BB.getIrrLoopHeaderWeight()) 1352 OS << ", irr_loop_header_weight = " << IrrLoopHeaderWeight.getValue(); 1353 OS << "\n"; 1354 } 1355 1356 // Add an extra newline for readability. 1357 OS << "\n"; 1358 return OS; 1359 } 1360 1361 // Graph trait base class for block frequency information graph 1362 // viewer. 1363 1364 enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count }; 1365 1366 template <class BlockFrequencyInfoT, class BranchProbabilityInfoT> 1367 struct BFIDOTGraphTraitsBase : public DefaultDOTGraphTraits { 1368 using GTraits = GraphTraits<BlockFrequencyInfoT *>; 1369 using NodeRef = typename GTraits::NodeRef; 1370 using EdgeIter = typename GTraits::ChildIteratorType; 1371 using NodeIter = typename GTraits::nodes_iterator; 1372 1373 uint64_t MaxFrequency = 0; 1374 1375 explicit BFIDOTGraphTraitsBase(bool isSimple = false) 1376 : DefaultDOTGraphTraits(isSimple) {} 1377 1378 static std::string getGraphName(const BlockFrequencyInfoT *G) { 1379 return G->getFunction()->getName(); 1380 } 1381 1382 std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph, 1383 unsigned HotPercentThreshold = 0) { 1384 std::string Result; 1385 if (!HotPercentThreshold) 1386 return Result; 1387 1388 // Compute MaxFrequency on the fly: 1389 if (!MaxFrequency) { 1390 for (NodeIter I = GTraits::nodes_begin(Graph), 1391 E = GTraits::nodes_end(Graph); 1392 I != E; ++I) { 1393 NodeRef N = *I; 1394 MaxFrequency = 1395 std::max(MaxFrequency, Graph->getBlockFreq(N).getFrequency()); 1396 } 1397 } 1398 BlockFrequency Freq = Graph->getBlockFreq(Node); 1399 BlockFrequency HotFreq = 1400 (BlockFrequency(MaxFrequency) * 1401 BranchProbability::getBranchProbability(HotPercentThreshold, 100)); 1402 1403 if (Freq < HotFreq) 1404 return Result; 1405 1406 raw_string_ostream OS(Result); 1407 OS << "color=\"red\""; 1408 OS.flush(); 1409 return Result; 1410 } 1411 1412 std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph, 1413 GVDAGType GType, int layout_order = -1) { 1414 std::string Result; 1415 raw_string_ostream OS(Result); 1416 1417 if (layout_order != -1) 1418 OS << Node->getName() << "[" << layout_order << "] : "; 1419 else 1420 OS << Node->getName() << " : "; 1421 switch (GType) { 1422 case GVDT_Fraction: 1423 Graph->printBlockFreq(OS, Node); 1424 break; 1425 case GVDT_Integer: 1426 OS << Graph->getBlockFreq(Node).getFrequency(); 1427 break; 1428 case GVDT_Count: { 1429 auto Count = Graph->getBlockProfileCount(Node); 1430 if (Count) 1431 OS << Count.getValue(); 1432 else 1433 OS << "Unknown"; 1434 break; 1435 } 1436 case GVDT_None: 1437 llvm_unreachable("If we are not supposed to render a graph we should " 1438 "never reach this point."); 1439 } 1440 return Result; 1441 } 1442 1443 std::string getEdgeAttributes(NodeRef Node, EdgeIter EI, 1444 const BlockFrequencyInfoT *BFI, 1445 const BranchProbabilityInfoT *BPI, 1446 unsigned HotPercentThreshold = 0) { 1447 std::string Str; 1448 if (!BPI) 1449 return Str; 1450 1451 BranchProbability BP = BPI->getEdgeProbability(Node, EI); 1452 uint32_t N = BP.getNumerator(); 1453 uint32_t D = BP.getDenominator(); 1454 double Percent = 100.0 * N / D; 1455 raw_string_ostream OS(Str); 1456 OS << format("label=\"%.1f%%\"", Percent); 1457 1458 if (HotPercentThreshold) { 1459 BlockFrequency EFreq = BFI->getBlockFreq(Node) * BP; 1460 BlockFrequency HotFreq = BlockFrequency(MaxFrequency) * 1461 BranchProbability(HotPercentThreshold, 100); 1462 1463 if (EFreq >= HotFreq) { 1464 OS << ",color=\"red\""; 1465 } 1466 } 1467 1468 OS.flush(); 1469 return Str; 1470 } 1471 }; 1472 1473 } // end namespace llvm 1474 1475 #undef DEBUG_TYPE 1476 1477 #endif // LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H 1478