contrib/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

   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
  38 namespace llvm {
  39
  40 class BasicBlock;
  41 class BranchProbabilityInfo;
  42 class Function;
  43 class Loop;
  44 class LoopInfo;
  45 class MachineBasicBlock;
  46 class MachineBranchProbabilityInfo;
  47 class MachineFunction;
  48 class MachineLoop;
  49 class MachineLoopInfo;
  50
  51 namespace bfi_detail {
  52
  53 struct IrreducibleGraph;
  54
  55 // This is part of a workaround for a GCC 4.7 crash on lambdas.
  56 template <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.
  71 class BlockMass {
  72   uint64_t Mass;
  73
  74 public:
  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
 129 inline BlockMass operator+(BlockMass L, BlockMass R) {
 130   return BlockMass(L) += R;
 131 }
 132 inline BlockMass operator-(BlockMass L, BlockMass R) {
 133   return BlockMass(L) -= R;
 134 }
 135 inline BlockMass operator*(BlockMass L, BranchProbability R) {
 136   return BlockMass(L) *= R;
 137 }
 138 inline BlockMass operator*(BranchProbability L, BlockMass R) {
 139   return BlockMass(R) *= L;
 140 }
 141
 142 inline raw_ostream &operator<<(raw_ostream &OS, BlockMass X) {
 143   return X.print(OS);
 144 }
 145
 146 } // end namespace bfi_detail
 147
 148 template <> 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.
 160 class BlockFrequencyInfoImplBase {
 161 public:
 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
 505 namespace bfi_detail {
 506 template <class BlockT> struct TypeMap {};
 507 template <> struct TypeMap<BasicBlock> {
 508   typedef BasicBlock BlockT;
 509   typedef Function FunctionT;
 510   typedef BranchProbabilityInfo BranchProbabilityInfoT;
 511   typedef Loop LoopT;
 512   typedef LoopInfo LoopInfoT;
 513 };
 514 template <> 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.
 529 template <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.
 537 template <> 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.
 556 struct 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 };
 611 template <class BlockEdgesAdder>
 612 void 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 }
 625 template <class BlockEdgesAdder>
 626 void 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.)
 796 template <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
 915 public:
 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
 961 template <class BT>
 962 void 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
 989 template <class BT>
 990 void 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
1004 template <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
1026 template <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
1079 template <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
1093 template <class BT>
1094 bool 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
1125 template <class BT>
1126 bool 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
1145 template <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.
1155 namespace bfi_detail {
1156 template <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 }
1172 template <class BT>
1173 void 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.
1194 inline uint32_t getWeightFromBranchProb(const BranchProbability Prob) {
1195   return Prob.getNumerator();
1196 }
1197
1198 template <class BT>
1199 bool
1200 BlockFrequencyInfoImpl<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
1225 template <class BT>
1226 raw_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
1244 enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count };
1245
1246 template <class BlockFrequencyInfoT, class BranchProbabilityInfoT>
1247 struct 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