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