1.. _pipeline: 2 3Core Pipeline 4============= 5 6.. toctree:: 7 :hidden: 8 9 IRTranslator 10 Legalizer 11 RegBankSelect 12 InstructionSelect 13 14The core pipeline of GlobalISel is: 15 16.. image:: pipeline-overview.png 17 18The 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 47Although we tend to talk about them as distinct passes, it should be noted that 48there's a good deal of flexibility here and it's ok for things to happen 49earlier than described below. For example, it's not unusual for the legalizer to 50legalize an intrinsic directly to a target instruction. The concrete 51requirement is that the following additional constraints are preserved after 52each of these passes: 53 54IRTranslator 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 60Legalizer 61 62 No illegal operations must remain or be introduced after this pass. 63 64Register Bank Selector 65 66 All virtual registers must have a register bank assigned after this pass. 67 68Instruction 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 73In addition to these passes, there are also some optional passes that perform 74an optimization. The current optional passes are: 75 76Combiner 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 82Additional passes such as these can be inserted to support higher optimization 83levels or target specific needs. A likely pipeline is: 84 85.. image:: pipeline-overview-with-combiners.png 86 87Of course, combiners can be inserted in other places too. Also passes can be 88replaced entirely so long as their task is complete as shown in this (more 89customized) example pipeline. 90 91.. image:: pipeline-overview-customized.png 92 93.. _maintainability-verifier: 94 95MachineVerifier 96--------------- 97 98The pass approach lets us use the ``MachineVerifier`` to enforce invariants 99that are required beyond certain points of the pipeline. For example, a 100function with the ``legalized`` property can have the ``MachineVerifier`` 101enforce that no illegal instructions occur. Similarly, a 102``regBankSelected`` function may not have virtual registers without a register 103bank 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 114Testing 115------- 116 117The ability to test GlobalISel is significantly improved over SelectionDAG. 118SelectionDAG is something of a black box and there's a lot going on inside it. 119This makes it difficult to write a test that reliably tests a particular aspect 120of its behaviour. For comparison, see the following diagram: 121 122.. image:: testing-pass-level.png 123 124Each of the grey boxes indicates an opportunity to serialize the current state 125and test the behaviour between two points in the pipeline. The current state 126can be serialized using ``-stop-before`` or ``-stop-after`` and loaded using 127``-start-before``, ``-start-after``, and ``-run-pass``. 128 129We can also go further still, as many of GlobalISel's passes are readily unit 130testable: 131 132.. image:: testing-unit-level.png 133 134It'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>`_ 135and perform a single step of the algorithm and check the result. The MIR and 136FileCheck directives can be embedded using strings so you still have access to 137the convenience available in llvm-lit. 138 139Debugging 140--------- 141 142One debugging technique that's proven particularly valuable is to use the 143BlockExtractor to extract basic blocks into new functions. This can be used 144to track down correctness bugs and can also be used to track down performance 145regressions. It can also be coupled with function attributes to disable 146GlobalISel for one or more of the extracted functions. 147 148.. image:: block-extract.png 149 150The 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 156This particular example extracts two basic blocks from a function named ``foo``. 157The new LLVM-IR can then be modified to add the ``failedISel`` attribute to the 158extracted function containing bb4 to make that function use SelectionDAG. 159 160This can prevent some optimizations as GlobalISel is generally able to work on a 161single function at a time. This technique can be repeated for different 162combinations of basic blocks until you have identified the critical blocks 163involved in a bug. 164 165Once the critical blocks have been identified, you can further increase the 166resolution 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 174into: 175 176.. code-block:: none 177 178 bb1: 179 ... instructions group 1 ... 180 br %bb2 181 182 bb2: 183 ... instructions group 2 ... 184 185and then repeating the process for the new blocks. 186 187It's also possible to use this technique in a mode where the main function 188is compiled with GlobalISel and the extracted basic blocks are compiled with 189SelectionDAG (or the other way around) to leverage the existing quality of 190another code generator to track down bugs. This technique can also be used to 191improve the similarity between fast and slow code when tracking down performance 192regressions and help you zero in on a particular cause of the regression. 193
