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