1===========================
2LLVM Branch Weight Metadata
3===========================
4
5.. contents::
6   :local:
7
8Introduction
9============
10
11Branch Weight Metadata represents branch weights as its likeliness to be taken
12(see :doc:`BlockFrequencyTerminology`). Metadata is assigned to the
13``TerminatorInst`` as a ``MDNode`` of the ``MD_prof`` kind. The first operator
14is always a ``MDString`` node with the string "branch_weights".  Number of
15operators depends on the terminator type.
16
17Branch weights might be fetch from the profiling file, or generated based on
18`__builtin_expect`_ instruction.
19
20All weights are represented as an unsigned 32-bit values, where higher value
21indicates greater chance to be taken.
22
23Supported Instructions
24======================
25
26``BranchInst``
27^^^^^^^^^^^^^^
28
29Metadata is only assigned to the conditional branches. There are two extra
30operands for the true and the false branch.
31
32.. code-block:: llvm
33
34  !0 = metadata !{
35    metadata !"branch_weights",
36    i32 <TRUE_BRANCH_WEIGHT>,
37    i32 <FALSE_BRANCH_WEIGHT>
38  }
39
40``SwitchInst``
41^^^^^^^^^^^^^^
42
43Branch weights are assigned to every case (including the ``default`` case which
44is always case #0).
45
46.. code-block:: llvm
47
48  !0 = metadata !{
49    metadata !"branch_weights",
50    i32 <DEFAULT_BRANCH_WEIGHT>
51    [ , i32 <CASE_BRANCH_WEIGHT> ... ]
52  }
53
54``IndirectBrInst``
55^^^^^^^^^^^^^^^^^^
56
57Branch weights are assigned to every destination.
58
59.. code-block:: llvm
60
61  !0 = metadata !{
62    metadata !"branch_weights",
63    i32 <LABEL_BRANCH_WEIGHT>
64    [ , i32 <LABEL_BRANCH_WEIGHT> ... ]
65  }
66
67Other
68^^^^^
69
70Other terminator instructions are not allowed to contain Branch Weight Metadata.
71
72.. _\__builtin_expect:
73
74Built-in ``expect`` Instructions
75================================
76
77``__builtin_expect(long exp, long c)`` instruction provides branch prediction
78information. The return value is the value of ``exp``.
79
80It is especially useful in conditional statements. Currently Clang supports two
81conditional statements:
82
83``if`` statement
84^^^^^^^^^^^^^^^^
85
86The ``exp`` parameter is the condition. The ``c`` parameter is the expected
87comparison value. If it is equal to 1 (true), the condition is likely to be
88true, in other case condition is likely to be false. For example:
89
90.. code-block:: c++
91
92  if (__builtin_expect(x > 0, 1)) {
93    // This block is likely to be taken.
94  }
95
96``switch`` statement
97^^^^^^^^^^^^^^^^^^^^
98
99The ``exp`` parameter is the value. The ``c`` parameter is the expected
100value. If the expected value doesn't show on the cases list, the ``default``
101case is assumed to be likely taken.
102
103.. code-block:: c++
104
105  switch (__builtin_expect(x, 5)) {
106  default: break;
107  case 0:  // ...
108  case 3:  // ...
109  case 5:  // This case is likely to be taken.
110  }
111
112CFG Modifications
113=================
114
115Branch Weight Metatada is not proof against CFG changes. If terminator operands'
116are changed some action should be taken. In other case some misoptimizations may
117occur due to incorrect branch prediction information.
118
119Function Entry Counts
120=====================
121
122To allow comparing different functions during inter-procedural analysis and
123optimization, ``MD_prof`` nodes can also be assigned to a function definition.
124The first operand is a string indicating the name of the associated counter.
125
126Currently, one counter is supported: "function_entry_count". This is a 64-bit
127counter that indicates the number of times that this function was invoked (in
128the case of instrumentation-based profiles). In the case of sampling-based
129profiles, this counter is an approximation of how many times the function was
130invoked.
131
132For example, in the code below, the instrumentation for function foo()
133indicates that it was called 2,590 times at runtime.
134
135.. code-block:: llvm
136
137  define i32 @foo() !prof !1 {
138    ret i32 0
139  }
140  !1 = !{!"function_entry_count", i64 2590}
141