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