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