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 30operarands 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 incorrent branch prediction information. 118