docs/BranchWeightMetadata.rst

   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 assigned 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 assigned to every case (including the ``default`` case which
  45 is 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 assigned 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.