[globalisel][docs] Rewrite the pipeline overview

[dsanders]

Summary

Rewrite the pipeline overview to be more focused on the structure and
flexibility as well as highlight the increased usefulness of
MachineVerifier and increased testability resulting from the smaller
incremental passes approach.

The diagrams are lifted from the slides for the LLVMDev 2019 talk
'Generating Optimized Code with GlobalISel' and adapted to be readable on
the white background used in the docs.

[rovka]

Thanks for writing this up! I just have a few suggestions and one small bug to point out (I can't figure out how to comment on a png file, so I'll write it here).

llvm/docs/GlobalISel/testing-pass-level.png: Between the Register Bank Selector and the Instruction Selector, it should be gMIR + MIR (right now it's just MIR).

llvm/docs/GlobalISel/Pipeline.rst

25

I think somewhere in this paragraph we should mention what gMIR stands for (just so we don't introduce unexplained acronyms - even if all the details are just a click away).
Perhaps also a sentence or two explaining the exact relationship between MIR and gMIR would make the rest of the text easier to read (I'm thinking especially around lines 51-52) .

59

Maybe "The concrete requirement is that the following constraints are preserved after each of these passes:"

63

You're using MIR both for "pure" MIR and for "MIRs in general". It's a bit confusing to read. I would suggest something along the lines of "The representation must be some kind of machine IR after this pass. It will initially be gMIR but will gradually transition to strict MIR throughout the rest of the pipeline."

134

Just a quick question since I don't know how github links work: That's a link to a specific commit, right? (So the code and line number will stay the same forever).

137

I think this paragraph needs to be expanded a bit. Unless I missed it (entirely possible, I'm still waking up after the weekend), the text never mentions that legalization is performed in steps, so I think there should be a few words here about what the steps are and how they interact with each other (e.g. just by looking at that picture people might wonder if the steps can be run in any order).

[dsanders]

In D69456#1723011, @rovka wrote:

Thanks for writing this up! I just have a few suggestions and one small bug to point out (I can't figure out how to comment on a png file, so I'll write it here).

llvm/docs/GlobalISel/testing-pass-level.png: Between the Register Bank Selector and the Instruction Selector, it should be gMIR + MIR (right now it's just MIR).

Well spotted. These are images straight from our LLVMDev Keynote slides so I guess I should fix that while I'm at it. Hopefully I can sneak the fix in before Tanya uploads them :-)

llvm/docs/GlobalISel/Pipeline.rst

59

In addition to that, I also expanded on the bit about flexibility and explicitly stated the general point that doing things early is ok rather than just hinting at it with the example

63

Good point. We never really came up with a term for the original MIR to contrast it with gMIR.

I've tried to dodge the issue here by using gMIR, MIR, or a mixture of the two. Does it read better?

134

Yes, that's right. I got it from the 'Copy Permalink' option that's in the '...' button to the left of the marked line.

I just found out that you can do line ranges too so the link now highlights the whole function

137

I don't really want to go into the details of the passes here so I've kept that intentionally abstract. I think the place to talk about the details is the individual pass pages. The main point I want to make here is that it's possible to go much deeper into testing than SelectionDAG could

[dsanders]

Updated for review comments (except the picture, that will follow shortly)

[dsanders]

Fix the image too

[volkan]

LGTM with a nit.

llvm/docs/GlobalISel/Pipeline.rst

82

It would be nice to describe combiner too like the other passes.

[rovka]

Thanks, looks great!

[dsanders]

Thanks. llvm.org doesn't seem to be have the previous changes yet so I've asked on llvm-dev about that. Maybe the update mechanism is broken

llvm/docs/GlobalISel/Pipeline.rst

82

I added a brief mention. I'll expand on it when I get to that pass

llvm/docs/GlobalISel/Pipeline.rst

 .. _pipeline:
 
 Core Pipeline
 =============
 
-There are four required passes, regardless of the optimization mode:
-
 .. toctree::
-  :maxdepth: 1
+  :hidden:
 
   IRTranslator
   Legalizer
   RegBankSelect
   InstructionSelect
 
-Additional passes can then be inserted at higher optimization levels or for
-specific targets. For example, to match the current SelectionDAG set of
-transformations: MachineCSE and a better MachineCombiner between every pass.
-
-``NOTE``:
-In theory, not all passes are always necessary.
-As an additional compile-time optimization, we could skip some of the passes by
-setting the relevant MachineFunction properties.  For instance, if the
-IRTranslator did not encounter any illegal instruction, it would set the
-``legalized`` property to avoid running the :ref:`milegalizer`.
-Similarly, we considered specializing the IRTranslator per-target to directly
-emit target-specific MI.
-However, we instead decided to keep the core pipeline simple, and focus on
-minimizing the overhead of the passes in the no-op cases.
+The core pipeline of GlobalISel is:
 
-.. _maintainability-verifier:
+.. image:: pipeline-overview.png
 
-MachineVerifier
----------------
+The four passes shown in the diagram consist of:
+
+:doc:`IRTranslator`
+
+  Converts :doc:`LLVM-IR <../LangRef>` into :doc:`gMIR (Generic MIR) <GMIR>`.
+  This is largely a direct translation and has little target customization.
+  It's somewhat analogous to SelectionDAGBuilder but builds a flavour of MIR
+  called gMIR instead of a specialized representation. gMIR uses exactly the
+  same data structures as MIR but has more relaxed constraints. For example,
+  a virtual register may be constrained to a particular type without also
+  constraining it to a specific register class.
+
+:doc:`Legalizer`
+
+  Replaces unsupported operations with supported ones. In other words, it shapes
+  the gMIR to suit what the backend can support. There is a very small set of
+  operations which targets are required to support but aside from that targets
+  can shape the MIR as they wish.
+
+:doc:`Register Bank Selector <RegBankSelect>`
+
+  Binds virtual registers to register banks. This pass is intended to minimize
+  cross-register-bank copies by clustering portions of the MIR together.
 
-The pass approach lets us use the ``MachineVerifier`` to enforce invariants.
-For instance, a ``regBankSelected`` function may not have gvregs without
-a bank.
+:doc:`Instruction Select <InstructionSelect>`
 
-``TODO``:
-The ``MachineVerifier`` being monolithic, some of the checks we want to do
-can't be integrated to it:  GlobalISel is a separate library, so we can't
-directly reference it from CodeGen.  For instance, legality checks are
-currently done in RegBankSelect/InstructionSelect proper.  We could #ifdef out
-the checks, or we could add some sort of verifier API.
+  Select target instructions using the gMIR. At this point, the gMIR has been
+  constrained enough that it becomes MIR.
 
+Although we tend to talk about them as distinct passes, it should be noted that
+there's a good deal of flexibility here and it's ok for things to happen
+earlier than described below. For example, it's not unusual for the legalizer to
+legalize an intrinsic directly to a target instruction. The concrete
+requirement is that the following additional constraints are preserved after
+each of these passes:
 
-.. _maintainability:
+IRTranslator
+
+  The representation must be gMIR, MIR, or a mixture of the two after this pass.
+  The majority will typically be gMIR to begin with but later passes will
+  gradually transition the gMIR to MIR.
+
+Legalizer
+
+  No illegal operations must remain or be introduced after this pass.
 
-Maintainability
-===============
+Register Bank Selector
 
-.. _maintainability-iterative:
+  All virtual registers must have a register bank assigned after this pass.
 
-Iterative Transformations
--------------------------
+Instruction Select
+
+  No gMIR must remain or be introduced after this pass. In other words, we must
+  have completed the conversion from gMIR to MIR.
 
-Passes are split into small, iterative transformations, with all state
-represented in the MIR.
+In addition to these passes, there are also some optional passes that perform
+an optimization. The current optional passes are:
 
-This differs from SelectionDAG (in particular, the legalizer) using various
-in-memory side-tables.
+Combiner
 
+  Replaces patterns of instructions with a better alternative. Typically, this
+  means improving run time performance by replacing instructions with faster
+  alternatives but Combiners can also focus on code size or other metrics.
 
-.. _maintainability-mir:
+Additional passes such as these can be inserted to support higher optimization
+levels or target specific needs. A likely pipeline is:
 
-MIR Serialization
------------------
+.. image:: pipeline-overview-with-combiners.png
 
-.. FIXME: Update the MIRLangRef to include GMI additions.
+Of course, combiners can be inserted in other places too. Also passes can be
+replaced entirely so long as their task is complete as shown in this (more
+customized) example pipeline.
 
-:ref:`gmir` is serializable (see :doc:`../MIRLangRef`).
-Combined with :ref:`maintainability-iterative`, this enables much finer-grained
-testing, rather than requiring large and fragile IR-to-assembly tests.
+.. image:: pipeline-overview-customized.png
 
-The current "stage" in the :ref:`pipeline` is represented by a set of
-``MachineFunctionProperties``:
+.. _maintainability-verifier:
 
-* ``legalized``
-* ``regBankSelected``
-* ``selected``
+MachineVerifier
+---------------
 
+The pass approach lets us use the ``MachineVerifier`` to enforce invariants
+that are required beyond certain points of the pipeline. For example, a
+function with the ``legalized`` property can have the ``MachineVerifier``
+enforce that no illegal instructions occur. Similarly, a
+``regBankSelected`` function may not have virtual registers without a register
+bank assigned.
+
+.. note::
+
+  For layering reasons, ``MachineVerifier`` isn't able to be the sole verifier
+  in GlobalISel. Currently some of the passes also perform verification while
+  we find a way to solve this problem.
+
+  The main issue is that GlobalISel is a separate library, so we can't
+  directly reference it from CodeGen.
+
+Testing
+-------
+
+The ability to test GlobalISel is significantly improved over SelectionDAG.
+SelectionDAG is something of a black box and there's a lot going on inside it.
+This makes it difficult to write a test that reliably tests a particular aspect
+of its behaviour. For comparison, see the following diagram:
+
+.. image:: testing-pass-level.png
+
+Each of the grey boxes indicates an opportunity to serialize the current state
+and test the behaviour between two points in the pipeline. The current state
+can be serialized using ``-stop-before`` or ``-stop-after`` and loaded using
+``-start-before``, ``-start-after``, and ``-run-pass``.
+
+We can also go further still, as many of GlobalISel's passes are readily unit
+testable:
+
+.. image:: testing-unit-level.png
+
+It's possible to create an imaginary target such as in `LegalizerHelperTest.cpp <https://github.com/llvm/llvm-project/blob/93b29d3882baf7df42e4e9bc26b977b00373ef56/llvm/unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp#L28-L57>`_
+and perform a single step of the algorithm and check the result. The MIR and
+FileCheck directives can be embedded using strings so you still have access to
+the convenience available in llvm-lit.