llvm/docs/GlobalISel/Pipeline.rst

   1 .. _pipeline:
   2
   3 Core Pipeline
   4 =============
   5
   6 .. toctree::
   7   :hidden:
   8
   9   IRTranslator
  10   Legalizer
  11   RegBankSelect
  12   InstructionSelect
  13
  14 The core pipeline of GlobalISel is:
  15
  16 .. image:: pipeline-overview.png
  17
  18 The four passes shown in the diagram consist of:
  19
  20 :doc:`IRTranslator`
  21
  22   Converts :doc:`LLVM-IR <../LangRef>` into :doc:`gMIR (Generic MIR) <GMIR>`.
  23   This is largely a direct translation and has little target customization.
  24   It's somewhat analogous to SelectionDAGBuilder but builds a flavour of MIR
  25   called gMIR instead of a specialized representation. gMIR uses exactly the
  26   same data structures as MIR but has more relaxed constraints. For example,
  27   a virtual register may be constrained to a particular type without also
  28   constraining it to a specific register class.
  29
  30 :doc:`Legalizer`
  31
  32   Replaces unsupported operations with supported ones. In other words, it shapes
  33   the gMIR to suit what the backend can support. There is a very small set of
  34   operations which targets are required to support but aside from that targets
  35   can shape the MIR as they wish.
  36
  37 :doc:`Register Bank Selector <RegBankSelect>`
  38
  39   Binds virtual registers to register banks. This pass is intended to minimize
  40   cross-register-bank copies by clustering portions of the MIR together.
  41
  42 :doc:`Instruction Select <InstructionSelect>`
  43
  44   Select target instructions using the gMIR. At this point, the gMIR has been
  45   constrained enough that it becomes MIR.
  46
  47 Although we tend to talk about them as distinct passes, it should be noted that
  48 there's a good deal of flexibility here and it's ok for things to happen
  49 earlier than described below. For example, it's not unusual for the legalizer to
  50 legalize an intrinsic directly to a target instruction. The concrete
  51 requirement is that the following additional constraints are preserved after
  52 each of these passes:
  53
  54 IRTranslator
  55
  56   The representation must be gMIR, MIR, or a mixture of the two after this pass.
  57   The majority will typically be gMIR to begin with but later passes will
  58   gradually transition the gMIR to MIR.
  59
  60 Legalizer
  61
  62   No illegal operations must remain or be introduced after this pass.
  63
  64 Register Bank Selector
  65
  66   All virtual registers must have a register bank assigned after this pass.
  67
  68 Instruction Select
  69
  70   No gMIR must remain or be introduced after this pass. In other words, we must
  71   have completed the conversion from gMIR to MIR.
  72
  73 In addition to these passes, there are also some optional passes that perform
  74 an optimization. The current optional passes are:
  75
  76 Combiner
  77
  78   Replaces patterns of instructions with a better alternative. Typically, this
  79   means improving run time performance by replacing instructions with faster
  80   alternatives but Combiners can also focus on code size or other metrics.
  81
  82 Additional passes such as these can be inserted to support higher optimization
  83 levels or target specific needs. A likely pipeline is:
  84
  85 .. image:: pipeline-overview-with-combiners.png
  86
  87 Of course, combiners can be inserted in other places too. Also passes can be
  88 replaced entirely so long as their task is complete as shown in this (more
  89 customized) example pipeline.
  90
  91 .. image:: pipeline-overview-customized.png
  92
  93 .. _maintainability-verifier:
  94
  95 MachineVerifier
  96 ---------------
  97
  98 The pass approach lets us use the ``MachineVerifier`` to enforce invariants
  99 that are required beyond certain points of the pipeline. For example, a
 100 function with the ``legalized`` property can have the ``MachineVerifier``
 101 enforce that no illegal instructions occur. Similarly, a
 102 ``regBankSelected`` function may not have virtual registers without a register
 103 bank assigned.
 104
 105 .. note::
 106
 107   For layering reasons, ``MachineVerifier`` isn't able to be the sole verifier
 108   in GlobalISel. Currently some of the passes also perform verification while
 109   we find a way to solve this problem.
 110
 111   The main issue is that GlobalISel is a separate library, so we can't
 112   directly reference it from CodeGen.
 113
 114 Testing
 115 -------
 116
 117 The ability to test GlobalISel is significantly improved over SelectionDAG.
 118 SelectionDAG is something of a black box and there's a lot going on inside it.
 119 This makes it difficult to write a test that reliably tests a particular aspect
 120 of its behaviour. For comparison, see the following diagram:
 121
 122 .. image:: testing-pass-level.png
 123
 124 Each of the grey boxes indicates an opportunity to serialize the current state
 125 and test the behaviour between two points in the pipeline. The current state
 126 can be serialized using ``-stop-before`` or ``-stop-after`` and loaded using
 127 ``-start-before``, ``-start-after``, and ``-run-pass``.
 128
 129 We can also go further still, as many of GlobalISel's passes are readily unit
 130 testable:
 131
 132 .. image:: testing-unit-level.png
 133
 134 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>`_
 135 and perform a single step of the algorithm and check the result. The MIR and
 136 FileCheck directives can be embedded using strings so you still have access to
 137 the convenience available in llvm-lit.
 138
 139 Debugging
 140 ---------
 141
 142 One debugging technique that's proven particularly valuable is to use the
 143 BlockExtractor to extract basic blocks into new functions. This can be used
 144 to track down correctness bugs and can also be used to track down performance
 145 regressions. It can also be coupled with function attributes to disable
 146 GlobalISel for one or more of the extracted functions.
 147
 148 .. image:: block-extract.png
 149
 150 The command to do the extraction is:
 151
 152 .. code-block:: shell
 153
 154   ./bin/llvm-extract -o - -S -b ‘foo:bb1;bb4’ <input> > extracted.ll
 155
 156 This particular example extracts two basic blocks from a function named ``foo``.
 157 The new LLVM-IR can then be modified to add the ``failedISel`` attribute to the
 158 extracted function containing bb4 to make that function use SelectionDAG.
 159
 160 This can prevent some optimizations as GlobalISel is generally able to work on a
 161 single function at a time. This technique can be repeated for different
 162 combinations of basic blocks until you have identified the critical blocks
 163 involved in a bug.
 164
 165 Once the critical blocks have been identified, you can further increase the
 166 resolution to the critical instructions by splitting the blocks like from:
 167
 168 .. code-block:: none
 169
 170   bb1:
 171     ... instructions group 1 ...
 172     ... instructions group 2 ...
 173
 174 into:
 175
 176 .. code-block:: none
 177
 178   bb1:
 179     ... instructions group 1 ...
 180     br %bb2
 181
 182   bb2:
 183     ... instructions group 2 ...
 184
 185 and then repeating the process for the new blocks.
 186
 187 It's also possible to use this technique in a mode where the main function
 188 is compiled with GlobalISel and the extracted basic blocks are compiled with
 189 SelectionDAG (or the other way around) to leverage the existing quality of
 190 another code generator to track down bugs. This technique can also be used to
 191 improve the similarity between fast and slow code when tracking down performance
 192 regressions and help you zero in on a particular cause of the regression.