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