diff options
| author | Bill Wendling <isanbard@gmail.com> | 2012-06-20 10:17:46 +0000 |
|---|---|---|
| committer | Bill Wendling <isanbard@gmail.com> | 2012-06-20 10:17:46 +0000 |
| commit | 707f2fd26bd36e384b5d78d61a21ee45711768ef (patch) | |
| tree | 44533a921f2e51390a12e783d3c5afbc8eb9772e /docs | |
| parent | a3a2eb08e1a2ab8e8138be05f9b03fc8f0d46fc0 (diff) | |
Sphinxify BranchWeightMetadata document.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158810 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/BranchWeightMetadata.html | 164 | ||||
| -rw-r--r-- | docs/BranchWeightMetadata.rst | 118 | ||||
| -rw-r--r-- | docs/subsystems.rst | 3 |
3 files changed, 120 insertions, 165 deletions
diff --git a/docs/BranchWeightMetadata.html b/docs/BranchWeightMetadata.html deleted file mode 100644 index 3a0af29043..0000000000 --- a/docs/BranchWeightMetadata.html +++ /dev/null @@ -1,164 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" - "http://www.w3.org/TR/html4/strict.dtd"> -<html> -<head> - <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> - <title>LLVM Branch Weight Metadata</title> - <link rel="stylesheet" href="_static/llvm.css" type="text/css"> -</head> -<body> - -<h1> - LLVM Branch Weight Metadata -</h1> - -<ol> - <li><a href="#introduction">Introduction</a></li> - <li><a href="#supported_instructions">Supported Instructions</a></li> - <li><a href="#builtin_expect">Built-in "expect" Instruction </a></li> - <li><a href="#cfg_modifications">CFG Modifications</a></li> -</ol> - -<div class="doc_author"> - <p>Written by <a href="mailto:jstaszak@apple.com">Jakub Staszak</a></p> -</div> - -<h2> - <a name="introduction">Introduction</a> -</h2> -<div> -<p>Branch Weight Metadata represents branch weights as its likeliness to -be taken. Metadata is assigned to the <tt>TerminatorInst</tt> as a -<tt>MDNode</tt> of the <tt>MD_prof</tt> kind. The first operator is always a -<tt>MDString</tt> node with the string "branch_weights". Number of operators -depends on the terminator type.</p> - -<p>Branch weights might be fetch from the profiling file, or generated based on -<a href="#builtin_expect"><tt>__builtin_expect</tt></a> instruction. -</p> - -<p>All weights are represented as an unsigned 32-bit values, where higher value -indicates greater chance to be taken.</p> -</div> - -<h2> - <a name="supported_instructions">Supported Instructions</a> -</h2> - -<div> - <h4>BranchInst</h4> - <div> - <p>Metadata is only assign to the conditional branches. There are two extra - operarands, for the true and the false branch.</p> - </div> - <div class="doc_code"> - <pre> -!0 = metadata !{ - metadata !"branch_weights", - i32 <TRUE_BRANCH_WEIGHT>, - i32 <FALSE_BRANCH_WEIGHT> -} - </pre> - </div> - - <h4>SwitchInst</h4> - <div> - <p>Branch weights are assign to every case (including <tt>default</tt> case - which is always case #0).</p> - </div> - <div class="doc_code"> - <pre> -!0 = metadata !{ - metadata !"branch_weights", - i32 <DEFAULT_BRANCH_WEIGHT> - [ , i32 <CASE_BRANCH_WEIGHT> ... ] -} - </pre> - </div> - - <h4>IndirectBrInst</h4> - <div> - <p>Branch weights are assign to every destination.</p> - </div> - <div class="doc_code"> - <pre> -!0 = metadata !{ - metadata !"branch_weights", - i32 <LABEL_BRANCH_WEIGHT> - [ , i32 <LABEL_BRANCH_WEIGHT> ... ] -} - </pre> - </div> - - <h4>Other</h4> - <div> - <p>Other terminator instructions are not allowed to contain Branch Weight - Metadata.</p> - </div> -</div> - -<h2> - <a name="builtin_expect">Built-in "expect" Instructions</a> -</h2> -<div> - <p><tt>__builtin_expect(long exp, long c)</tt> instruction provides branch - prediction information. The return value is the value of <tt>exp</tt>.</p> - - <p>It is especially useful in conditional statements. Currently Clang supports - two conditional statements: - </p> - <h4><tt>if</tt> statement</h4> - <div> - <p>The <tt>exp</tt> parameter is the condition. The <tt>c</tt> parameter is - the expected comparison value. If it is equal to 1 (true), the condition is - likely to be true, in other case condition is likely to be false. For example: - </p> - </div> - <div class="doc_code"> - <pre> - if (__builtin_expect(x > 0, 1)) { - // This block is likely to be taken. - } - </pre> - </div> - - <h4><tt>switch</tt> statement</h4> - <div> - <p>The <tt>exp</tt> parameter is the value. The <tt>c</tt> parameter is the - expected value. If the expected value doesn't show on the cases list, the - <tt>default</tt> case is assumed to be likely taken.</p> - </div> - <div class="doc_code"> - <pre> - switch (__builtin_expect(x, 5)) { - default: break; - case 0: // ... - case 3: // ... - case 5: // This case is likely to be taken. - } - </pre> - </div> -</div> - -<h2> - <a name="cfg_modifications">CFG Modifications</a> -</h2> -<div> -<p>Branch Weight Metatada is not proof against CFG changes. If terminator -operands' are changed some action should be taken. In other case some -misoptimizations may occur due to incorrent branch prediction information.</p> -</div> - -<hr> -<address> - <a href="http://jigsaw.w3.org/css-validator/check/referer"><img - src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a> - <a href="http://validator.w3.org/check/referer"><img - src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a> - - <a href="mailto:jstaszak@apple.com">Jakub Staszak</a><br> - <a href="http://llvm.org/">LLVM Compiler Infrastructure</a><br> -</address> - -</body> -</html> diff --git a/docs/BranchWeightMetadata.rst b/docs/BranchWeightMetadata.rst new file mode 100644 index 0000000000..f0df971f87 --- /dev/null +++ b/docs/BranchWeightMetadata.rst @@ -0,0 +1,118 @@ +.. _branch_weight: + +=========================== +LLVM Branch Weight Metadata +=========================== + +.. contents:: + :local: + +Introduction +============ + +Branch Weight Metadata represents branch weights as its likeliness to be +taken. Metadata is assigned to the ``TerminatorInst`` as a ``MDNode`` of the +``MD_prof`` kind. The first operator is always a ``MDString`` node with the +string "branch_weights". Number of operators depends on the terminator type. + +Branch weights might be fetch from the profiling file, or generated based on +`__builtin_expect`_ instruction. + +All weights are represented as an unsigned 32-bit values, where higher value +indicates greater chance to be taken. + +Supported Instructions +====================== + +``BranchInst`` +^^^^^^^^^^^^^^ + +Metadata is only assign to the conditional branches. There are two extra +operarands, for the true and the false branch. + +.. code-block:: llvm + + !0 = metadata !{ + metadata !"branch_weights", + i32 <TRUE_BRANCH_WEIGHT>, + i32 <FALSE_BRANCH_WEIGHT> + } + +``SwitchInst`` +^^^^^^^^^^^^^^ + +Branch weights are assign to every case (including ``default`` case which is +always case #0). + +.. code-block:: llvm + + !0 = metadata !{ + metadata !"branch_weights", + i32 <DEFAULT_BRANCH_WEIGHT> + [ , i32 <CASE_BRANCH_WEIGHT> ... ] + } + +``IndirectBrInst`` +^^^^^^^^^^^^^^^^^^ + +Branch weights are assign to every destination. + +.. code-block:: llvm + + !0 = metadata !{ + metadata !"branch_weights", + i32 <LABEL_BRANCH_WEIGHT> + [ , i32 <LABEL_BRANCH_WEIGHT> ... ] + } + +Other +^^^^^ + +Other terminator instructions are not allowed to contain Branch Weight Metadata. + +.. _\__builtin_expect: + +Built-in ``expect`` Instructions +================================ + +``__builtin_expect(long exp, long c)`` instruction provides branch prediction +information. The return value is the value of ``exp``. + +It is especially useful in conditional statements. Currently Clang supports two +conditional statements: + +``if`` statement +^^^^^^^^^^^^^^^^ + +The ``exp`` parameter is the condition. The ``c`` parameter is the expected +comparison value. If it is equal to 1 (true), the condition is likely to be +true, in other case condition is likely to be false. For example: + +.. code-block:: c++ + + if (__builtin_expect(x > 0, 1)) { + // This block is likely to be taken. + } + +``switch`` statement +^^^^^^^^^^^^^^^^^^^^ + +The ``exp`` parameter is the value. The ``c`` parameter is the expected +value. If the expected value doesn't show on the cases list, the ``default`` +case is assumed to be likely taken. + +.. code-block:: c++ + + switch (__builtin_expect(x, 5)) { + default: break; + case 0: // ... + case 3: // ... + case 5: // This case is likely to be taken. + } + +CFG Modifications +================= + +Branch Weight Metatada is not proof against CFG changes. If terminator operands' +are changed some action should be taken. In other case some misoptimizations may +occur due to incorrent branch prediction information. diff --git a/docs/subsystems.rst b/docs/subsystems.rst index ee0c2bedd0..1f9bd7d6ed 100644 --- a/docs/subsystems.rst +++ b/docs/subsystems.rst @@ -7,6 +7,7 @@ Subsystem Documentation :hidden: AliasAnalysis + BranchWeightMetadata LinkTimeOptimization * `Writing an LLVM Pass <WritingAnLLVMPass.html>`_ @@ -75,6 +76,6 @@ Subsystem Documentation How to debug JITed code with GDB. -* `Branch Weight Metadata <BranchWeightMetadata.html>`_ +* :ref:`branch_weight` Provides information about Branch Prediction Information. |