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