Home | History | Annotate | Download | only in docs 
      1 .. _branch_weight:
      2 
      3 ===========================
      4 LLVM Branch Weight Metadata
      5 ===========================
      6 
      7 .. contents::
      8    :local:
      9 
     10 Introduction
     11 ============
     12 
     13 Branch Weight Metadata represents branch weights as its likeliness to be
     14 taken. 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
     16 string "branch_weights". Number of operators depends on the terminator type.
     17 
     18 Branch weights might be fetch from the profiling file, or generated based on
     19 `__builtin_expect`_ instruction.
     20 
     21 All weights are represented as an unsigned 32-bit values, where higher value
     22 indicates greater chance to be taken.
     23 
     24 Supported Instructions
     25 ======================
     26 
     27 ``BranchInst``
     28 ^^^^^^^^^^^^^^
     29 
     30 Metadata is only assign to the conditional branches. There are two extra
     31 operarands, 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 
     44 Branch weights are assign to every case (including ``default`` case which is
     45 always 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 
     58 Branch 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 
     68 Other
     69 ^^^^^
     70 
     71 Other terminator instructions are not allowed to contain Branch Weight Metadata.
     72 
     73 .. _\__builtin_expect:
     74 
     75 Built-in ``expect`` Instructions
     76 ================================
     77 
     78 ``__builtin_expect(long exp, long c)`` instruction provides branch prediction
     79 information. The return value is the value of ``exp``.
     80 
     81 It is especially useful in conditional statements. Currently Clang supports two
     82 conditional statements:
     83 
     84 ``if`` statement
     85 ^^^^^^^^^^^^^^^^
     86 
     87 The ``exp`` parameter is the condition. The ``c`` parameter is the expected
     88 comparison value. If it is equal to 1 (true), the condition is likely to be
     89 true, 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 
    100 The ``exp`` parameter is the value. The ``c`` parameter is the expected
    101 value. If the expected value doesn't show on the cases list, the ``default``
    102 case 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 
    113 CFG Modifications
    114 =================
    115 
    116 Branch Weight Metatada is not proof against CFG changes. If terminator operands'
    117 are changed some action should be taken. In other case some misoptimizations may
    118 occur due to incorrent branch prediction information.
    119