[globalisel][docs] Add KnownBits Analysis documentation

[dsanders]

Summary

This is largely based off of the slides from the keynote

Depends on D69545

[arsenm]

llvm/docs/GlobalISel/KnownBits.rst

6

Typo passs

[rovka]

llvm/docs/GlobalISel/KnownBits.rst

6

Nit: What exactly does "such transformations" refer to? It sounds a bit weird to use this in the first sentence of the document.

[dsanders]

Fix the two nits.
Also s/llvm-mir-body/none/g as the upstream bot treats warnings as errors.

[dsanders]

llvm/docs/GlobalISel/KnownBits.rst

6

I got a bit lazy with the copy/pasting here. The original slides introduced an example first but this document does that later.

[dsanders]

s/llvm-mir-body/none/g properly

[rovka]

LGTM

llvm/docs/GlobalISel/KnownBits.rst

6

Still a typo :P should be "passes".

[dsanders]

llvm/docs/GlobalISel/KnownBits.rst

6

Ugh, that's what I get for context switching so much. Fixed it in the push, Thanks

llvm/docs/GlobalISel/KnownBits.rst

+Known Bits Analysis
+===================
+
+The Known Bits Analysis pass makes information about the known values of bits
+available to other passes to enable transformations like those in the examples
+below. The information is lazily computed so you should only pay for what you
+use.
+
+Examples
+--------
+
+A simple example is that transforming::
+
+  a + 1
+
+into::
+
+  a | 1
+
+is only valid when the addition doesn't carry. In other words it's only valid
+if ``a & 1`` is zero.
+
+Another example is:
+
+.. code-block:: none
+
+  %1:(s32) = G_CONSTANT i32 0xFF0
+  %2:(s32) = G_AND %0, %1
+  %3:(s32) = G_CONSTANT i32 0x0FF
+  %4:(s32) = G_AND %2, %3
+
+We can use the constants and the definition of ``G_AND`` to determine the known
+bits:
+
+.. code-block:: none
+
+                                   ; %0 = 0x????????
+  %1:(s32) = G_CONSTANT i32 0xFF0  ; %1 = 0x00000FF0
+  %2:(s32) = G_AND %0, %1          ; %2 = 0x00000??0
+  %3:(s32) = G_CONSTANT i32 0x0FF  ; %3 = 0x000000FF
+  %4:(s32) = G_AND %2, %3          ; %4 = 0x000000?0
+
+and then use this to simplify the expression:
+
+.. code-block:: none
+
+                                   ; %0 = 0x????????
+  %5:(s32) = G_CONSTANT i32 0x0F0  ; %5 = 0x00000FF0
+  %4:(s32) = G_AND %0, %5          ; %4 = 0x000000?0
+
+Note that ``%4`` still has the same known bits as before the transformation.
+Many transformations share this property. The main exception being when the
+transform causes undefined bits to become defined to either zero, one, or
+defined but unknown.
+
+Usage
+-----
+
+To use Known Bits Analysis in a pass, first include the header and register the
+dependency with ``INITIALIZE_PASS_DEPENDENCY``.
+
+.. code-block:: c++
+
+  #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
+
+  ...
+
+  INITIALIZE_PASS_BEGIN(...)
+  INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
+  INITIALIZE_PASS_END(...)
+
+and require the pass in ``getAnalysisUsage``.
+
+.. code-block:: c++
+
+  void MyPass::getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.addRequired<GISelKnownBitsAnalysis>();
+    // Optional: If your pass preserves known bits analysis (many do) then
+    //           indicate that it's preserved for re-use by another pass here.
+    AU.addPreserved<GISelKnownBitsAnalysis>();
+  }
+
+Then it's just a matter of fetching the analysis and using it:
+
+.. code-block:: c++
+
+  bool MyPass::runOnMachineFunction(MachineFunction &MF) {
+    ...
+    GISelKnownBits &KB = getAnalysis<GISelKnownBitsAnalysis>().get(MF);
+    ...
+    MachineInstr *MI = ...;
+    KnownBits Known = KB->getKnownBits(MI->getOperand(0).getReg());
+    if (Known.Zeros & 1) {
+      // Bit 0 is known to be zero
+    }
+    ...
+  }
+
+There are many more API's beyond ``getKnownBits()``. See the `API reference
+<http://llvm.org/doxygen>`_ for more information

llvm/docs/GlobalISel/index.rst

 
 .. toctree::
   :maxdepth: 1
 
   IRTranslator
   Legalizer
   RegBankSelect
   InstructionSelect
+  KnownBits
 
 .. _progress:
 
 Progress and Future Work
 ========================
 
 The initial goal is to replace FastISel on AArch64.  The next step will be to
 replace SelectionDAG as the optimized ISel.