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