Add GlobalISel cook book

[Kai]

Summary

Based on our recent experience with implementing GlobalISel for the PowerPC target,
we came up with the idea that some cook book style documentation may be useful.

llvm/docs/GlobalISel/Cookbook.rst

+GlobalISel Cookbook
+===================
+
+.. contents::
+   :local:
+
+How to get started
+------------------
+
+You should watch the GlobalISel tutorial `"Head First into GlobalISel"
+<https://www.youtube.com/watch?v=Zh4R40ZyJ2k>`_ and `Optimized GISel
+<https://www.youtube.com/watch?v=8427bl_7k1g>`_ to get an understanding what you
+need to implement.
+
+The first step is adding the necessary infrastructure. Create a `GISel`
+directory in the top level directory of your target, and add stub files:
+
+- `<Target>CallLowering.h` and `<Target>CallLowering.cpp` for lowering of
+  function calls
+- `<Target>LegalizerInfo.h` and `<Target>LegalizerInfo.cpp` for the Legalizer
+  implementation
+- `<Target>RegisterBankInfo.h` and `<Target>RegisterBankInfo.cpp` for the
+  register bank selection
+- `<Target>InstructionSelector.cpp` for the instruction selector
+- `<Target>GenRegisterBankInfo.def` for (potential later generated) support code
+  for the register bank selection
+
+In the top level directory, you need to stub files:
+- `<Target>RegisterBanks.td` for the register bank definition
+  
+All of these files need to be added to the `CMakeLists.txt` build description. You
+can use the GlobalISel implementation from another target, for example AArch64,
+as a blueprint.
+
+For a proof-of-concept implementation you need to decide on an instruction you
+want to tackle first. One of the logical instructions is usually a good choice.
+The goal is to add enough code to lower a simple function like
+
+.. code-block:: none
+
+  define i32 @f1(i32 %a, i32 %b) {
+    %res = and i32 %a, %b
+    ret i32 %res
+  }
+
+with GlobalISel.
+
+Now you can extend the stubs:
+- Extend `<Target>CallLowering.cpp` to be able to lower simple arguments and
+  return a simple value. The calling convention definition in the target
+  description is also used here.
+- In `<Target>LegalizerInfo.cpp`, you just add code to legalize the generic
+  instruction which will be lowered into the instruction you chooose.
+- To implement the register bank selection you need to extend several files:
+  - Add a single register bank definition to `<Target>RegisterBanks.td`
+  - Add the support code to `<Target>GenRegisterBankInfo.def`, only for that
+    single register bank
+  - And in `<Target>RegisterBankInfo.cpp` implement enough to select the
+    register bank for the generic instruction.
+- The instruction selector only needs to call the generated matcher, based on
+  the SelectionDAG patterns.
+
+When you got this working then you can lower a simple IR file like the above to
+machine code using the `-global-isel` option of `llc`.
+
+After implementing this base, it is easy to extend your implementation to:
+- Add lowering of similar instructons. For example, if you started with `G_AND`
+  then `G_OR` and `G_XOR` are very similar, and can be easily added.
+- Add support for an instruction requiring another register bank. For example,
+  if your target has different register banks for integer and floating point
+  values, then adding a floating point instruction is a good next step.
+
+In this way you easily grow the implementation of GlobalISel for your target.
+
+Legalizer
+---------
+
+One of the basic generic instructions is not legal on my target. What can I do?
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+This is actually a common case. The legalizer can lower many generic
+instructions into a different form, for example expression `G_SREM` in terms of
+division and subtraction. The transformation is intended to produce a legal
+generic instruction, or a generic instruction which can easily legalized. You
+use the `lowerFor()` or `lowerIf()` method to trigger lowering of the
+instruction. However, the legalizer cannot lower all instructions. An example is
+`G_SELECT` which can only be lowered for vector types. In such cases you use
+`customFor()` or `customIf()` to provide your own lowering.
+
+Legalizing one of the instructions requires custom lowering code which requires a new basic block.
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+The legalizer currently does not support adding new basic blocks. As a work
+around you can lower such an instruction in a pre-legalizer combiner, in a
+post-legalizer combiner, or in the instruction selector.
+
+
+Register banks
+--------------
+
+I defined a register bank but the generated file does not contain definitions for it.
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Check if the parameter of the `RegisterBank` record is really a register class.
+The TableGen generator silently ignores parameters of the wrong type, resulting
+in missing definitions in the generated file.
+
+Instruction selection
+---------------------
+
+The selector generated from the SelectionDAG patterns does not select instruction xyz!
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+There are several reasons why this can happen. We are currently aware of:
+
+- For commutable instructions, the generated selector does not check both sides.
+  Most common, this is a problem if immediates are involved. The SelectionDAG
+  selector expects the immediate to be the right operand, but with GlobalISel it
+  can happen that the immediate is the left operand. In this case no match is
+  made.
+- The operand type is different from what the selector expects. It may indicate
+  that a bitcast is missing.
+- The SelectionDAG pattern consists of several instructions. With the generic
+  instructions, an additional `COPY` instruction may be present in the def-use
+  chain of one of the operands. The `COPY` is a no-op in this case, but the
+  generated selector is not yet able to handle it.
+
+Combiners
+---------
+
+Can I specify a constraint for a combiner in TableGen?
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+This is not yet implemented.