1.. _branch_weight:
2
3===========================
4LLVM Branch Weight Metadata
5===========================
6
7.. contents::
8   :local:
9
10Introduction
11============
12
13Branch Weight Metadata represents branch weights as its likeliness to be
14taken. Metadata is assigned to the ``TerminatorInst`` as a ``MDNode`` of the
15``MD_prof`` kind. The first operator is always a ``MDString`` node with the
16string "branch_weights". Number of operators depends on the terminator type.
17
18Branch weights might be fetch from the profiling file, or generated based on
19`__builtin_expect`_ instruction.
20
21All weights are represented as an unsigned 32-bit values, where higher value
22indicates greater chance to be taken.
23
24Supported Instructions
25======================
26
27``BranchInst``
28^^^^^^^^^^^^^^
29
30Metadata is only assign to the conditional branches. There are two extra
31operarands, for the true and the false branch.
32
33.. code-block:: llvm
34
35  !0 = metadata !{
36    metadata !"branch_weights",
37    i32 <TRUE_BRANCH_WEIGHT>,
38    i32 <FALSE_BRANCH_WEIGHT>
39  }
40
41``SwitchInst``
42^^^^^^^^^^^^^^
43
44Branch weights are assign to every case (including ``default`` case which is
45always case #0).
46
47.. code-block:: llvm
48
49  !0 = metadata !{
50    metadata !"branch_weights",
51    i32 <DEFAULT_BRANCH_WEIGHT>
52    [ , i32 <CASE_BRANCH_WEIGHT> ... ]
53  }
54
55``IndirectBrInst``
56^^^^^^^^^^^^^^^^^^
57
58Branch weights are assign to every destination.
59
60.. code-block:: llvm
61
62  !0 = metadata !{
63    metadata !"branch_weights",
64    i32 <LABEL_BRANCH_WEIGHT>
65    [ , i32 <LABEL_BRANCH_WEIGHT> ... ]
66  }
67
68Other
69^^^^^
70
71Other terminator instructions are not allowed to contain Branch Weight Metadata.
72
73.. _\__builtin_expect:
74
75Built-in ``expect`` Instructions
76================================
77
78``__builtin_expect(long exp, long c)`` instruction provides branch prediction
79information. The return value is the value of ``exp``.
80
81It is especially useful in conditional statements. Currently Clang supports two
82conditional statements:
83
84``if`` statement
85^^^^^^^^^^^^^^^^
86
87The ``exp`` parameter is the condition. The ``c`` parameter is the expected
88comparison value. If it is equal to 1 (true), the condition is likely to be
89true, in other case condition is likely to be false. For example:
90
91.. code-block:: c++
92
93  if (__builtin_expect(x > 0, 1)) {
94    // This block is likely to be taken.
95  }
96
97``switch`` statement
98^^^^^^^^^^^^^^^^^^^^
99
100The ``exp`` parameter is the value. The ``c`` parameter is the expected
101value. If the expected value doesn't show on the cases list, the ``default``
102case is assumed to be likely taken.
103
104.. code-block:: c++
105
106  switch (__builtin_expect(x, 5)) {
107  default: break;
108  case 0:  // ...
109  case 3:  // ...
110  case 5:  // This case is likely to be taken.
111  }
112
113CFG Modifications
114=================
115
116Branch Weight Metatada is not proof against CFG changes. If terminator operands'
117are changed some action should be taken. In other case some misoptimizations may
118occur due to incorrent branch prediction information.
119