1*0a6a1f1dSLionel Sambuc================================ 2*0a6a1f1dSLionel SambucLLVM Block Frequency Terminology 3*0a6a1f1dSLionel Sambuc================================ 4*0a6a1f1dSLionel Sambuc 5*0a6a1f1dSLionel Sambuc.. contents:: 6*0a6a1f1dSLionel Sambuc :local: 7*0a6a1f1dSLionel Sambuc 8*0a6a1f1dSLionel SambucIntroduction 9*0a6a1f1dSLionel Sambuc============ 10*0a6a1f1dSLionel Sambuc 11*0a6a1f1dSLionel SambucBlock Frequency is a metric for estimating the relative frequency of different 12*0a6a1f1dSLionel Sambucbasic blocks. This document describes the terminology that the 13*0a6a1f1dSLionel Sambuc``BlockFrequencyInfo`` and ``MachineBlockFrequencyInfo`` analysis passes use. 14*0a6a1f1dSLionel Sambuc 15*0a6a1f1dSLionel SambucBranch Probability 16*0a6a1f1dSLionel Sambuc================== 17*0a6a1f1dSLionel Sambuc 18*0a6a1f1dSLionel SambucBlocks with multiple successors have probabilities associated with each 19*0a6a1f1dSLionel Sambucoutgoing edge. These are called branch probabilities. For a given block, the 20*0a6a1f1dSLionel Sambucsum of its outgoing branch probabilities should be 1.0. 21*0a6a1f1dSLionel Sambuc 22*0a6a1f1dSLionel SambucBranch Weight 23*0a6a1f1dSLionel Sambuc============= 24*0a6a1f1dSLionel Sambuc 25*0a6a1f1dSLionel SambucRather than storing fractions on each edge, we store an integer weight. 26*0a6a1f1dSLionel SambucWeights are relative to the other edges of a given predecessor block. The 27*0a6a1f1dSLionel Sambucbranch probability associated with a given edge is its own weight divided by 28*0a6a1f1dSLionel Sambucthe sum of the weights on the predecessor's outgoing edges. 29*0a6a1f1dSLionel Sambuc 30*0a6a1f1dSLionel SambucFor example, consider this IR: 31*0a6a1f1dSLionel Sambuc 32*0a6a1f1dSLionel Sambuc.. code-block:: llvm 33*0a6a1f1dSLionel Sambuc 34*0a6a1f1dSLionel Sambuc define void @foo() { 35*0a6a1f1dSLionel Sambuc ; ... 36*0a6a1f1dSLionel Sambuc A: 37*0a6a1f1dSLionel Sambuc br i1 %cond, label %B, label %C, !prof !0 38*0a6a1f1dSLionel Sambuc ; ... 39*0a6a1f1dSLionel Sambuc } 40*0a6a1f1dSLionel Sambuc !0 = metadata !{metadata !"branch_weights", i32 7, i32 8} 41*0a6a1f1dSLionel Sambuc 42*0a6a1f1dSLionel Sambucand this simple graph representation:: 43*0a6a1f1dSLionel Sambuc 44*0a6a1f1dSLionel Sambuc A -> B (edge-weight: 7) 45*0a6a1f1dSLionel Sambuc A -> C (edge-weight: 8) 46*0a6a1f1dSLionel Sambuc 47*0a6a1f1dSLionel SambucThe probability of branching from block A to block B is 7/15, and the 48*0a6a1f1dSLionel Sambucprobability of branching from block A to block C is 8/15. 49*0a6a1f1dSLionel Sambuc 50*0a6a1f1dSLionel SambucSee :doc:`BranchWeightMetadata` for details about the branch weight IR 51*0a6a1f1dSLionel Sambucrepresentation. 52*0a6a1f1dSLionel Sambuc 53*0a6a1f1dSLionel SambucBlock Frequency 54*0a6a1f1dSLionel Sambuc=============== 55*0a6a1f1dSLionel Sambuc 56*0a6a1f1dSLionel SambucBlock frequency is a relative metric that represents the number of times a 57*0a6a1f1dSLionel Sambucblock executes. The ratio of a block frequency to the entry block frequency is 58*0a6a1f1dSLionel Sambucthe expected number of times the block will execute per entry to the function. 59*0a6a1f1dSLionel Sambuc 60*0a6a1f1dSLionel SambucBlock frequency is the main output of the ``BlockFrequencyInfo`` and 61*0a6a1f1dSLionel Sambuc``MachineBlockFrequencyInfo`` analysis passes. 62*0a6a1f1dSLionel Sambuc 63*0a6a1f1dSLionel SambucImplementation: a series of DAGs 64*0a6a1f1dSLionel Sambuc================================ 65*0a6a1f1dSLionel Sambuc 66*0a6a1f1dSLionel SambucThe implementation of the block frequency calculation analyses each loop, 67*0a6a1f1dSLionel Sambucbottom-up, ignoring backedges; i.e., as a DAG. After each loop is processed, 68*0a6a1f1dSLionel Sambucit's packaged up to act as a pseudo-node in its parent loop's (or the 69*0a6a1f1dSLionel Sambucfunction's) DAG analysis. 70*0a6a1f1dSLionel Sambuc 71*0a6a1f1dSLionel SambucBlock Mass 72*0a6a1f1dSLionel Sambuc========== 73*0a6a1f1dSLionel Sambuc 74*0a6a1f1dSLionel SambucFor each DAG, the entry node is assigned a mass of ``UINT64_MAX`` and mass is 75*0a6a1f1dSLionel Sambucdistributed to successors according to branch weights. Block Mass uses a 76*0a6a1f1dSLionel Sambucfixed-point representation where ``UINT64_MAX`` represents ``1.0`` and ``0`` 77*0a6a1f1dSLionel Sambucrepresents a number just above ``0.0``. 78*0a6a1f1dSLionel Sambuc 79*0a6a1f1dSLionel SambucAfter mass is fully distributed, in any cut of the DAG that separates the exit 80*0a6a1f1dSLionel Sambucnodes from the entry node, the sum of the block masses of the nodes succeeded 81*0a6a1f1dSLionel Sambucby a cut edge should equal ``UINT64_MAX``. In other words, mass is conserved 82*0a6a1f1dSLionel Sambucas it "falls" through the DAG. 83*0a6a1f1dSLionel Sambuc 84*0a6a1f1dSLionel SambucIf a function's basic block graph is a DAG, then block masses are valid block 85*0a6a1f1dSLionel Sambucfrequencies. This works poorly in practise though, since downstream users rely 86*0a6a1f1dSLionel Sambucon adding block frequencies together without hitting the maximum. 87*0a6a1f1dSLionel Sambuc 88*0a6a1f1dSLionel SambucLoop Scale 89*0a6a1f1dSLionel Sambuc========== 90*0a6a1f1dSLionel Sambuc 91*0a6a1f1dSLionel SambucLoop scale is a metric that indicates how many times a loop iterates per entry. 92*0a6a1f1dSLionel SambucAs mass is distributed through the loop's DAG, the (otherwise ignored) backedge 93*0a6a1f1dSLionel Sambucmass is collected. This backedge mass is used to compute the exit frequency, 94*0a6a1f1dSLionel Sambucand thus the loop scale. 95*0a6a1f1dSLionel Sambuc 96*0a6a1f1dSLionel SambucImplementation: Getting from mass and scale to frequency 97*0a6a1f1dSLionel Sambuc======================================================== 98*0a6a1f1dSLionel Sambuc 99*0a6a1f1dSLionel SambucAfter analysing the complete series of DAGs, each block has a mass (local to 100*0a6a1f1dSLionel Sambucits containing loop, if any), and each loop pseudo-node has a loop scale and 101*0a6a1f1dSLionel Sambucits own mass (from its parent's DAG). 102*0a6a1f1dSLionel Sambuc 103*0a6a1f1dSLionel SambucWe can get an initial frequency assignment (with entry frequency of 1.0) by 104*0a6a1f1dSLionel Sambucmultiplying these masses and loop scales together. A given block's frequency 105*0a6a1f1dSLionel Sambucis the product of its mass, the mass of containing loops' pseudo nodes, and the 106*0a6a1f1dSLionel Sambuccontaining loops' loop scales. 107*0a6a1f1dSLionel Sambuc 108*0a6a1f1dSLionel SambucSince downstream users need integers (not floating point), this initial 109*0a6a1f1dSLionel Sambucfrequency assignment is shifted as necessary into the range of ``uint64_t``. 110*0a6a1f1dSLionel Sambuc 111*0a6a1f1dSLionel SambucBlock Bias 112*0a6a1f1dSLionel Sambuc========== 113*0a6a1f1dSLionel Sambuc 114*0a6a1f1dSLionel SambucBlock bias is a proposed *absolute* metric to indicate a bias toward or away 115*0a6a1f1dSLionel Sambucfrom a given block during a function's execution. The idea is that bias can be 116*0a6a1f1dSLionel Sambucused in isolation to indicate whether a block is relatively hot or cold, or to 117*0a6a1f1dSLionel Sambuccompare two blocks to indicate whether one is hotter or colder than the other. 118*0a6a1f1dSLionel Sambuc 119*0a6a1f1dSLionel SambucThe proposed calculation involves calculating a *reference* block frequency, 120*0a6a1f1dSLionel Sambucwhere: 121*0a6a1f1dSLionel Sambuc 122*0a6a1f1dSLionel Sambuc* every branch weight is assumed to be 1 (i.e., every branch probability 123*0a6a1f1dSLionel Sambuc distribution is even) and 124*0a6a1f1dSLionel Sambuc 125*0a6a1f1dSLionel Sambuc* loop scales are ignored. 126*0a6a1f1dSLionel Sambuc 127*0a6a1f1dSLionel SambucThis reference frequency represents what the block frequency would be in an 128*0a6a1f1dSLionel Sambucunbiased graph. 129*0a6a1f1dSLionel Sambuc 130*0a6a1f1dSLionel SambucThe bias is the ratio of the block frequency to this reference block frequency. 131