[yaml2obj] - Remove helper methods that are probably excessive. NFC.
[llvm-complete.git] / docs / GlobalISel.rst
blobf6a2bfc38b41b60589774c8bb7548248b80d1655
1 ============================
2 Global Instruction Selection
3 ============================
5 .. contents::
6    :local:
7    :depth: 1
9 .. warning::
10    This document is a work in progress.  It reflects the current state of the
11    implementation, as well as open design and implementation issues.
13 Introduction
14 ============
16 GlobalISel is a framework that provides a set of reusable passes and utilities
17 for instruction selection --- translation from LLVM IR to target-specific
18 Machine IR (MIR).
20 GlobalISel is intended to be a replacement for SelectionDAG and FastISel, to
21 solve three major problems:
23 * **Performance** --- SelectionDAG introduces a dedicated intermediate
24   representation, which has a compile-time cost.
26   GlobalISel directly operates on the post-isel representation used by the
27   rest of the code generator, MIR.
28   It does require extensions to that representation to support arbitrary
29   incoming IR: :ref:`gmir`.
31 * **Granularity** --- SelectionDAG and FastISel operate on individual basic
32   blocks, losing some global optimization opportunities.
34   GlobalISel operates on the whole function.
36 * **Modularity** --- SelectionDAG and FastISel are radically different and share
37   very little code.
39   GlobalISel is built in a way that enables code reuse. For instance, both the
40   optimized and fast selectors share the :ref:`pipeline`, and targets can
41   configure that pipeline to better suit their needs.
44 .. _gmir:
46 Generic Machine IR
47 ==================
49 Machine IR operates on physical registers, register classes, and (mostly)
50 target-specific instructions.
52 To bridge the gap with LLVM IR, GlobalISel introduces "generic" extensions to
53 Machine IR:
55 .. contents::
56    :local:
58 ``NOTE``:
59 The generic MIR (GMIR) representation still contains references to IR
60 constructs (such as ``GlobalValue``).  Removing those should let us write more
61 accurate tests, or delete IR after building the initial MIR.  However, it is
62 not part of the GlobalISel effort.
64 .. _gmir-instructions:
66 Generic Instructions
67 --------------------
69 The main addition is support for pre-isel generic machine instructions (e.g.,
70 ``G_ADD``).  Like other target-independent instructions (e.g., ``COPY`` or
71 ``PHI``), these are available on all targets.
73 ``TODO``:
74 While we're progressively adding instructions, one kind in particular exposes
75 interesting problems: compares and how to represent condition codes.
76 Some targets (x86, ARM) have generic comparisons setting multiple flags,
77 which are then used by predicated variants.
78 Others (IR) specify the predicate in the comparison and users just get a single
79 bit.  SelectionDAG uses SETCC/CONDBR vs BR_CC (and similar for select) to
80 represent this.
82 The ``MachineIRBuilder`` class wraps the ``MachineInstrBuilder`` and provides
83 a convenient way to create these generic instructions.
85 .. _gmir-gvregs:
87 Generic Virtual Registers
88 -------------------------
90 Generic instructions operate on a new kind of register: "generic" virtual
91 registers.  As opposed to non-generic vregs, they are not assigned a Register
92 Class.  Instead, generic vregs have a :ref:`gmir-llt`, and can be assigned
93 a :ref:`gmir-regbank`.
95 ``MachineRegisterInfo`` tracks the same information that it does for
96 non-generic vregs (e.g., use-def chains).  Additionally, it also tracks the
97 :ref:`gmir-llt` of the register, and, instead of the ``TargetRegisterClass``,
98 its :ref:`gmir-regbank`, if any.
100 For simplicity, most generic instructions only accept generic vregs:
102 * instead of immediates, they use a gvreg defined by an instruction
103   materializing the immediate value (see :ref:`irtranslator-constants`).
104 * instead of physical register, they use a gvreg defined by a ``COPY``.
106 ``NOTE``:
107 We started with an alternative representation, where MRI tracks a size for
108 each gvreg, and instructions have lists of types.
109 That had two flaws: the type and size are redundant, and there was no generic
110 way of getting a given operand's type (as there was no 1:1 mapping between
111 instruction types and operands).
112 We considered putting the type in some variant of MCInstrDesc instead:
113 See `PR26576 <http://llvm.org/PR26576>`_: [GlobalISel] Generic MachineInstrs
114 need a type but this increases the memory footprint of the related objects
116 .. _gmir-regbank:
118 Register Bank
119 -------------
121 A Register Bank is a set of register classes defined by the target.
122 A bank has a size, which is the maximum store size of all covered classes.
124 In general, cross-class copies inside a bank are expected to be cheaper than
125 copies across banks.  They are also coalesceable by the register coalescer,
126 whereas cross-bank copies are not.
128 Also, equivalent operations can be performed on different banks using different
129 instructions.
131 For example, X86 can be seen as having 3 main banks: general-purpose, x87, and
132 vector (which could be further split into a bank per domain for single vs
133 double precision instructions).
135 Register banks are described by a target-provided API,
136 :ref:`RegisterBankInfo <api-registerbankinfo>`.
138 .. _gmir-llt:
140 Low Level Type
141 --------------
143 Additionally, every generic virtual register has a type, represented by an
144 instance of the ``LLT`` class.
146 Like ``EVT``/``MVT``/``Type``, it has no distinction between unsigned and signed
147 integer types.  Furthermore, it also has no distinction between integer and
148 floating-point types: it mainly conveys absolutely necessary information, such
149 as size and number of vector lanes:
151 * ``sN`` for scalars
152 * ``pN`` for pointers
153 * ``<N x sM>`` for vectors
154 * ``unsized`` for labels, etc..
156 ``LLT`` is intended to replace the usage of ``EVT`` in SelectionDAG.
158 Here are some LLT examples and their ``EVT`` and ``Type`` equivalents:
160    =============  =========  ======================================
161    LLT            EVT        IR Type
162    =============  =========  ======================================
163    ``s1``         ``i1``     ``i1``
164    ``s8``         ``i8``     ``i8``
165    ``s32``        ``i32``    ``i32``
166    ``s32``        ``f32``    ``float``
167    ``s17``        ``i17``    ``i17``
168    ``s16``        N/A        ``{i8, i8}``
169    ``s32``        N/A        ``[4 x i8]``
170    ``p0``         ``iPTR``   ``i8*``, ``i32*``, ``%opaque*``
171    ``p2``         ``iPTR``   ``i8 addrspace(2)*``
172    ``<4 x s32>``  ``v4f32``  ``<4 x float>``
173    ``s64``        ``v1f64``  ``<1 x double>``
174    ``<3 x s32>``  ``v3i32``  ``<3 x i32>``
175    ``unsized``    ``Other``  ``label``
176    =============  =========  ======================================
179 Rationale: instructions already encode a specific interpretation of types
180 (e.g., ``add`` vs. ``fadd``, or ``sdiv`` vs. ``udiv``).  Also encoding that
181 information in the type system requires introducing bitcast with no real
182 advantage for the selector.
184 Pointer types are distinguished by address space.  This matches IR, as opposed
185 to SelectionDAG where address space is an attribute on operations.
186 This representation better supports pointers having different sizes depending
187 on their addressspace.
189 ``NOTE``:
190 Currently, LLT requires at least 2 elements in vectors, but some targets have
191 the concept of a '1-element vector'.  Representing them as their underlying
192 scalar type is a nice simplification.
194 ``TODO``:
195 Currently, non-generic virtual registers, defined by non-pre-isel-generic
196 instructions, cannot have a type, and thus cannot be used by a pre-isel generic
197 instruction.  Instead, they are given a type using a COPY.  We could relax that
198 and allow types on all vregs: this would reduce the number of MI required when
199 emitting target-specific MIR early in the pipeline.  This should purely be
200 a compile-time optimization.
202 .. _pipeline:
204 Core Pipeline
205 =============
207 There are four required passes, regardless of the optimization mode:
209 .. contents::
210    :local:
212 Additional passes can then be inserted at higher optimization levels or for
213 specific targets. For example, to match the current SelectionDAG set of
214 transformations: MachineCSE and a better MachineCombiner between every pass.
216 ``NOTE``:
217 In theory, not all passes are always necessary.
218 As an additional compile-time optimization, we could skip some of the passes by
219 setting the relevant MachineFunction properties.  For instance, if the
220 IRTranslator did not encounter any illegal instruction, it would set the
221 ``legalized`` property to avoid running the :ref:`milegalizer`.
222 Similarly, we considered specializing the IRTranslator per-target to directly
223 emit target-specific MI.
224 However, we instead decided to keep the core pipeline simple, and focus on
225 minimizing the overhead of the passes in the no-op cases.
228 .. _irtranslator:
230 IRTranslator
231 ------------
233 This pass translates the input LLVM IR ``Function`` to a GMIR
234 ``MachineFunction``.
236 ``TODO``:
237 This currently doesn't support the more complex instructions, in particular
238 those involving control flow (``switch``, ``invoke``, ...).
239 For ``switch`` in particular, we can initially use the ``LowerSwitch`` pass.
241 .. _api-calllowering:
243 API: CallLowering
244 ^^^^^^^^^^^^^^^^^
246 The ``IRTranslator`` (using the ``CallLowering`` target-provided utility) also
247 implements the ABI's calling convention by lowering calls, returns, and
248 arguments to the appropriate physical register usage and instruction sequences.
250 .. _irtranslator-aggregates:
252 Aggregates
253 ^^^^^^^^^^
255 Aggregates are lowered to a single scalar vreg.
256 This differs from SelectionDAG's multiple vregs via ``GetValueVTs``.
258 ``TODO``:
259 As some of the bits are undef (padding), we should consider augmenting the
260 representation with additional metadata (in effect, caching computeKnownBits
261 information on vregs).
262 See `PR26161 <http://llvm.org/PR26161>`_: [GlobalISel] Value to vreg during
263 IR to MachineInstr translation for aggregate type
265 .. _irtranslator-constants:
267 Constant Lowering
268 ^^^^^^^^^^^^^^^^^
270 The ``IRTranslator`` lowers ``Constant`` operands into uses of gvregs defined
271 by ``G_CONSTANT`` or ``G_FCONSTANT`` instructions.
272 Currently, these instructions are always emitted in the entry basic block.
273 In a ``MachineFunction``, each ``Constant`` is materialized by a single gvreg.
275 This is beneficial as it allows us to fold constants into immediate operands
276 during :ref:`instructionselect`, while still avoiding redundant materializations
277 for expensive non-foldable constants.
278 However, this can lead to unnecessary spills and reloads in an -O0 pipeline, as
279 these vregs can have long live ranges.
281 ``TODO``:
282 We're investigating better placement of these instructions, in fast and
283 optimized modes.
286 .. _milegalizer:
288 Legalizer
289 ---------
291 This pass transforms the generic machine instructions such that they are legal.
293 A legal instruction is defined as:
295 * **selectable** --- the target will later be able to select it to a
296   target-specific (non-generic) instruction.
298 * operating on **vregs that can be loaded and stored** -- if necessary, the
299   target can select a ``G_LOAD``/``G_STORE`` of each gvreg operand.
301 As opposed to SelectionDAG, there are no legalization phases.  In particular,
302 'type' and 'operation' legalization are not separate.
304 Legalization is iterative, and all state is contained in GMIR.  To maintain the
305 validity of the intermediate code, instructions are introduced:
307 * ``G_MERGE_VALUES`` --- concatenate multiple registers of the same
308   size into a single wider register.
310 * ``G_UNMERGE_VALUES`` --- extract multiple registers of the same size
311   from a single wider register.
313 * ``G_EXTRACT`` --- extract a simple register (as contiguous sequences of bits)
314   from a single wider register.
316 As they are expected to be temporary byproducts of the legalization process,
317 they are combined at the end of the :ref:`milegalizer` pass.
318 If any remain, they are expected to always be selectable, using loads and stores
319 if necessary.
321 The legality of an instruction may only depend on the instruction itself and
322 must not depend on any context in which the instruction is used. However, after
323 deciding that an instruction is not legal, using the context of the instruction
324 to decide how to legalize the instruction is permitted. As an example, if we
325 have a ``G_FOO`` instruction of the form::
327   %1:_(s32) = G_CONSTANT i32 1
328   %2:_(s32) = G_FOO %0:_(s32), %1:_(s32)
330 it's impossible to say that G_FOO is legal iff %1 is a ``G_CONSTANT`` with
331 value ``1``. However, the following::
333   %2:_(s32) = G_FOO %0:_(s32), i32 1
335 can say that it's legal iff operand 2 is an immediate with value ``1`` because
336 that information is entirely contained within the single instruction.
338 .. _api-legalizerinfo:
340 API: LegalizerInfo
341 ^^^^^^^^^^^^^^^^^^
343 The recommended [#legalizer-legacy-footnote]_ API looks like this::
345   getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL})
346       .legalFor({s32, s64, v2s32, v4s32, v2s64})
347       .clampScalar(0, s32, s64)
348       .widenScalarToNextPow2(0)
349       .clampNumElements(0, v2s32, v4s32)
350       .clampNumElements(0, v2s64, v2s64)
351       .moreElementsToNextPow2(0);
353 and describes a set of rules by which we can either declare an instruction legal
354 or decide which action to take to make it more legal.
356 At the core of this ruleset is the ``LegalityQuery`` which describes the
357 instruction. We use a description rather than the instruction to both allow other
358 passes to determine legality without having to create an instruction and also to
359 limit the information available to the predicates to that which is safe to rely
360 on. Currently, the information available to the predicates that determine
361 legality contains:
363 * The opcode for the instruction
365 * The type of each type index (see ``type0``, ``type1``, etc.)
367 * The size in bytes and atomic ordering for each MachineMemOperand
369 Rule Processing and Declaring Rules
370 """""""""""""""""""""""""""""""""""
372 The ``getActionDefinitionsBuilder`` function generates a ruleset for the given
373 opcode(s) that rules can be added to. If multiple opcodes are given, they are
374 all permanently bound to the same ruleset. The rules in a ruleset are executed
375 from top to bottom and will start again from the top if an instruction is
376 legalized as a result of the rules. If the ruleset is exhausted without
377 satisfying any rule, then it is considered unsupported.
379 When it doesn't declare the instruction legal, each pass over the rules may
380 request that one type changes to another type. Sometimes this can cause multiple
381 types to change but we avoid this as much as possible as making multiple changes
382 can make it difficult to avoid infinite loops where, for example, narrowing one
383 type causes another to be too small and widening that type causes the first one
384 to be too big.
386 In general, it's advisable to declare instructions legal as close to the top of
387 the rule as possible and to place any expensive rules as low as possible. This
388 helps with performance as testing for legality happens more often than
389 legalization and legalization can require multiple passes over the rules.
391 As a concrete example, consider the rule::
393   getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL})
394       .legalFor({s32, s64, v2s32, v4s32, v2s64})
395       .clampScalar(0, s32, s64)
396       .widenScalarToNextPow2(0);
398 and the instruction::
400   %2:_(s7) = G_ADD %0:_(s7), %1:_(s7)
402 this doesn't meet the predicate for the :ref:`.legalFor() <legalfor>` as ``s7``
403 is not one of the listed types so it falls through to the
404 :ref:`.clampScalar() <clampscalar>`. It does meet the predicate for this rule
405 as the type is smaller than the ``s32`` and this rule instructs the legalizer
406 to change type 0 to ``s32``. It then restarts from the top. This time it does
407 satisfy ``.legalFor()`` and the resulting output is::
409   %3:_(s32) = G_ANYEXT %0:_(s7)
410   %4:_(s32) = G_ANYEXT %1:_(s7)
411   %5:_(s32) = G_ADD %3:_(s32), %4:_(s32)
412   %2:_(s7) = G_TRUNC %5:_(s32)
414 where the ``G_ADD`` is legal and the other instructions are scheduled for
415 processing by the legalizer.
417 Rule Actions
418 """"""""""""
420 There are various rule factories that append rules to a ruleset but they have a
421 few actions in common:
423 .. _legalfor:
425 * ``legalIf()``, ``legalFor()``, etc. declare an instruction to be legal if the
426   predicate is satisfied.
428 * ``narrowScalarIf()``, ``narrowScalarFor()``, etc. declare an instruction to be illegal
429   if the predicate is satisfied and indicates that narrowing the scalars in one
430   of the types to a specific type would make it more legal. This action supports
431   both scalars and vectors.
433 * ``widenScalarIf()``, ``widenScalarFor()``, etc. declare an instruction to be illegal
434   if the predicate is satisfied and indicates that widening the scalars in one
435   of the types to a specific type would make it more legal. This action supports
436   both scalars and vectors.
438 * ``fewerElementsIf()``, ``fewerElementsFor()``, etc. declare an instruction to be
439   illegal if the predicate is satisfied and indicates reducing the number of
440   vector elements in one of the types to a specific type would make it more
441   legal. This action supports vectors.
443 * ``moreElementsIf()``, ``moreElementsFor()``, etc. declare an instruction to be illegal
444   if the predicate is satisfied and indicates increasing the number of vector
445   elements in one of the types to a specific type would make it more legal.
446   This action supports vectors.
448 * ``lowerIf()``, ``lowerFor()``, etc. declare an instruction to be illegal if the
449   predicate is satisfied and indicates that replacing it with equivalent
450   instruction(s) would make it more legal. Support for this action differs for
451   each opcode.
453 * ``libcallIf()``, ``libcallFor()``, etc. declare an instruction to be illegal if the
454   predicate is satisfied and indicates that replacing it with a libcall would
455   make it more legal. Support for this action differs for
456   each opcode.
458 * ``customIf()``, ``customFor()``, etc. declare an instruction to be illegal if the
459   predicate is satisfied and indicates that the backend developer will supply
460   a means of making it more legal.
462 * ``unsupportedIf()``, ``unsupportedFor()``, etc. declare an instruction to be illegal
463   if the predicate is satisfied and indicates that there is no way to make it
464   legal and the compiler should fail.
466 * ``fallback()`` falls back on an older API and should only be used while porting
467   existing code from that API.
469 Rule Predicates
470 """""""""""""""
472 The rule factories also have predicates in common:
474 * ``legal()``, ``lower()``, etc. are always satisfied.
476 * ``legalIf()``, ``narrowScalarIf()``, etc. are satisfied if the user-supplied
477   ``LegalityPredicate`` function returns true. This predicate has access to the
478   information in the ``LegalityQuery`` to make its decision.
479   User-supplied predicates can also be combined using ``all(P0, P1, ...)``.
481 * ``legalFor()``, ``narrowScalarFor()``, etc. are satisfied if the type matches one in
482   a given set of types. For example ``.legalFor({s16, s32})`` declares the
483   instruction legal if type 0 is either s16 or s32. Additional versions for two
484   and three type indices are generally available. For these, all the type
485   indices considered together must match all the types in one of the tuples. So
486   ``.legalFor({{s16, s32}, {s32, s64}})`` will only accept ``{s16, s32}``, or
487   ``{s32, s64}`` but will not accept ``{s16, s64}``.
489 * ``legalForTypesWithMemSize()``, ``narrowScalarForTypesWithMemSize()``, etc. are
490   similar to ``legalFor()``, ``narrowScalarFor()``, etc. but additionally require a
491   MachineMemOperand to have a given size in each tuple.
493 * ``legalForCartesianProduct()``, ``narrowScalarForCartesianProduct()``, etc. are
494   satisfied if each type index matches one element in each of the independent
495   sets. So ``.legalForCartesianProduct({s16, s32}, {s32, s64})`` will accept
496   ``{s16, s32}``, ``{s16, s64}``, ``{s32, s32}``, and ``{s32, s64}``.
498 Composite Rules
499 """""""""""""""
501 There are some composite rules for common situations built out of the above facilities:
503 * ``widenScalarToNextPow2()`` is like ``widenScalarIf()`` but is satisfied iff the type
504   size in bits is not a power of 2 and selects a target type that is the next
505   largest power of 2. 
507 .. _clampscalar:
509 * ``minScalar()`` is like ``widenScalarIf()`` but is satisfied iff the type
510   size in bits is smaller than the given minimum and selects the minimum as the
511   target type. Similarly, there is also a ``maxScalar()`` for the maximum and a
512   ``clampScalar()`` to do both at once. 
514 * ``minScalarSameAs()`` is like ``minScalar()`` but the minimum is taken from another
515   type index.
517 * ``moreElementsToNextMultiple()`` is like ``moreElementsToNextPow2()`` but is based on
518   multiples of X rather than powers of 2.
520 Other Information
521 """""""""""""""""
523 ``TODO``:
524 An alternative worth investigating is to generalize the API to represent
525 actions using ``std::function`` that implements the action, instead of explicit
526 enum tokens (``Legal``, ``WidenScalar``, ...).
528 ``TODO``:
529 Moreover, we could use TableGen to initially infer legality of operation from
530 existing patterns (as any pattern we can select is by definition legal).
531 Expanding that to describe legalization actions is a much larger but
532 potentially useful project.
534 .. rubric:: Footnotes
536 .. [#legalizer-legacy-footnote] An API is broadly similar to
537    SelectionDAG/TargetLowering is available but is not recommended as a more
538    powerful API is available.
540 .. _regbankselect:
542 RegBankSelect
543 -------------
545 This pass constrains the :ref:`gmir-gvregs` operands of generic
546 instructions to some :ref:`gmir-regbank`.
548 It iteratively maps instructions to a set of per-operand bank assignment.
549 The possible mappings are determined by the target-provided
550 :ref:`RegisterBankInfo <api-registerbankinfo>`.
551 The mapping is then applied, possibly introducing ``COPY`` instructions if
552 necessary.
554 It traverses the ``MachineFunction`` top down so that all operands are already
555 mapped when analyzing an instruction.
557 This pass could also remap target-specific instructions when beneficial.
558 In the future, this could replace the ExeDepsFix pass, as we can directly
559 select the best variant for an instruction that's available on multiple banks.
561 .. _api-registerbankinfo:
563 API: RegisterBankInfo
564 ^^^^^^^^^^^^^^^^^^^^^
566 The ``RegisterBankInfo`` class describes multiple aspects of register banks.
568 * **Banks**: ``addRegBankCoverage`` --- which register bank covers each
569   register class.
571 * **Cross-Bank Copies**: ``copyCost`` --- the cost of a ``COPY`` from one bank
572   to another.
574 * **Default Mapping**: ``getInstrMapping`` --- the default bank assignments for
575   a given instruction.
577 * **Alternative Mapping**: ``getInstrAlternativeMapping`` --- the other
578   possible bank assignments for a given instruction.
580 ``TODO``:
581 All this information should eventually be static and generated by TableGen,
582 mostly using existing information augmented by bank descriptions.
584 ``TODO``:
585 ``getInstrMapping`` is currently separate from ``getInstrAlternativeMapping``
586 because the latter is more expensive: as we move to static mapping info,
587 both methods should be free, and we should merge them.
589 .. _regbankselect-modes:
591 RegBankSelect Modes
592 ^^^^^^^^^^^^^^^^^^^
594 ``RegBankSelect`` currently has two modes:
596 * **Fast** --- For each instruction, pick a target-provided "default" bank
597   assignment.  This is the default at -O0.
599 * **Greedy** --- For each instruction, pick the cheapest of several
600   target-provided bank assignment alternatives.
602 We intend to eventually introduce an additional optimizing mode:
604 * **Global** --- Across multiple instructions, pick the cheapest combination of
605   bank assignments.
607 ``NOTE``:
608 On AArch64, we are considering using the Greedy mode even at -O0 (or perhaps at
609 backend -O1):  because :ref:`gmir-llt` doesn't distinguish floating point from
610 integer scalars, the default assignment for loads and stores is the integer
611 bank, introducing cross-bank copies on most floating point operations.
614 .. _instructionselect:
616 InstructionSelect
617 -----------------
619 This pass transforms generic machine instructions into equivalent
620 target-specific instructions.  It traverses the ``MachineFunction`` bottom-up,
621 selecting uses before definitions, enabling trivial dead code elimination.
623 .. _api-instructionselector:
625 API: InstructionSelector
626 ^^^^^^^^^^^^^^^^^^^^^^^^
628 The target implements the ``InstructionSelector`` class, containing the
629 target-specific selection logic proper.
631 The instance is provided by the subtarget, so that it can specialize the
632 selector by subtarget feature (with, e.g., a vector selector overriding parts
633 of a general-purpose common selector).
634 We might also want to parameterize it by MachineFunction, to enable selector
635 variants based on function attributes like optsize.
637 The simple API consists of:
639   .. code-block:: c++
641     virtual bool select(MachineInstr &MI)
643 This target-provided method is responsible for mutating (or replacing) a
644 possibly-generic MI into a fully target-specific equivalent.
645 It is also responsible for doing the necessary constraining of gvregs into the
646 appropriate register classes as well as passing through COPY instructions to
647 the register allocator.
649 The ``InstructionSelector`` can fold other instructions into the selected MI,
650 by walking the use-def chain of the vreg operands.
651 As GlobalISel is Global, this folding can occur across basic blocks.
653 SelectionDAG Rule Imports
654 ^^^^^^^^^^^^^^^^^^^^^^^^^
656 TableGen will import SelectionDAG rules and provide the following function to
657 execute them:
659   .. code-block:: c++
661     bool selectImpl(MachineInstr &MI)
663 The ``--stats`` option can be used to determine what proportion of rules were
664 successfully imported. The easiest way to use this is to copy the
665 ``-gen-globalisel`` tablegen command from ``ninja -v`` and modify it.
667 Similarly, the ``--warn-on-skipped-patterns`` option can be used to obtain the
668 reasons that rules weren't imported. This can be used to focus on the most
669 important rejection reasons.
671 PatLeaf Predicates
672 ^^^^^^^^^^^^^^^^^^
674 PatLeafs cannot be imported because their C++ is implemented in terms of
675 ``SDNode`` objects. PatLeafs that handle immediate predicates should be
676 replaced by ``ImmLeaf``, ``IntImmLeaf``, or ``FPImmLeaf`` as appropriate.
678 There's no standard answer for other PatLeafs. Some standard predicates have
679 been baked into TableGen but this should not generally be done.
681 Custom SDNodes
682 ^^^^^^^^^^^^^^
684 Custom SDNodes should be mapped to Target Pseudos using ``GINodeEquiv``. This
685 will cause the instruction selector to import them but you will also need to
686 ensure the target pseudo is introduced to the MIR before the instruction
687 selector. Any preceding pass is suitable but the legalizer will be a
688 particularly common choice.
690 ComplexPatterns
691 ^^^^^^^^^^^^^^^
693 ComplexPatterns cannot be imported because their C++ is implemented in terms of
694 ``SDNode`` objects. GlobalISel versions should be defined with
695 ``GIComplexOperandMatcher`` and mapped to ComplexPattern with
696 ``GIComplexPatternEquiv``.
698 The following predicates are useful for porting ComplexPattern:
700 * isBaseWithConstantOffset() - Check for base+offset structures
701 * isOperandImmEqual() - Check for a particular constant
702 * isObviouslySafeToFold() - Check for reasons an instruction can't be sunk and folded into another.
704 There are some important points for the C++ implementation:
706 * Don't modify MIR in the predicate
707 * Renderer lambdas should capture by value to avoid use-after-free. They will be used after the predicate returns.
708 * Only create instructions in a renderer lambda. GlobalISel won't clean up things you create but don't use.
711 .. _maintainability:
713 Maintainability
714 ===============
716 .. _maintainability-iterative:
718 Iterative Transformations
719 -------------------------
721 Passes are split into small, iterative transformations, with all state
722 represented in the MIR.
724 This differs from SelectionDAG (in particular, the legalizer) using various
725 in-memory side-tables.
728 .. _maintainability-mir:
730 MIR Serialization
731 -----------------
733 .. FIXME: Update the MIRLangRef to include GMI additions.
735 :ref:`gmir` is serializable (see :doc:`MIRLangRef`).
736 Combined with :ref:`maintainability-iterative`, this enables much finer-grained
737 testing, rather than requiring large and fragile IR-to-assembly tests.
739 The current "stage" in the :ref:`pipeline` is represented by a set of
740 ``MachineFunctionProperties``:
742 * ``legalized``
743 * ``regBankSelected``
744 * ``selected``
747 .. _maintainability-verifier:
749 MachineVerifier
750 ---------------
752 The pass approach lets us use the ``MachineVerifier`` to enforce invariants.
753 For instance, a ``regBankSelected`` function may not have gvregs without
754 a bank.
756 ``TODO``:
757 The ``MachineVerifier`` being monolithic, some of the checks we want to do
758 can't be integrated to it:  GlobalISel is a separate library, so we can't
759 directly reference it from CodeGen.  For instance, legality checks are
760 currently done in RegBankSelect/InstructionSelect proper.  We could #ifdef out
761 the checks, or we could add some sort of verifier API.
764 .. _progress:
766 Progress and Future Work
767 ========================
769 The initial goal is to replace FastISel on AArch64.  The next step will be to
770 replace SelectionDAG as the optimized ISel.
772 ``NOTE``:
773 While we iterate on GlobalISel, we strive to avoid affecting the performance of
774 SelectionDAG, FastISel, or the other MIR passes.  For instance, the types of
775 :ref:`gmir-gvregs` are stored in a separate table in ``MachineRegisterInfo``,
776 that is destroyed after :ref:`instructionselect`.
778 .. _progress-fastisel:
780 FastISel Replacement
781 --------------------
783 For the initial FastISel replacement, we intend to fallback to SelectionDAG on
784 selection failures.
786 Currently, compile-time of the fast pipeline is within 1.5x of FastISel.
787 We're optimistic we can get to within 1.1/1.2x, but beating FastISel will be
788 challenging given the multi-pass approach.
789 Still, supporting all IR (via a complete legalizer) and avoiding the fallback
790 to SelectionDAG in the worst case should enable better amortized performance
791 than SelectionDAG+FastISel.
793 ``NOTE``:
794 We considered never having a fallback to SelectionDAG, instead deciding early
795 whether a given function is supported by GlobalISel or not.  The decision would
796 be based on :ref:`milegalizer` queries.
797 We abandoned that for two reasons:
798 a) on IR inputs, we'd need to basically simulate the :ref:`irtranslator`;
799 b) to be robust against unforeseen failures and to enable iterative
800 improvements.
802 .. _progress-targets:
804 Support For Other Targets
805 -------------------------
807 In parallel, we're investigating adding support for other - ideally quite
808 different - targets.  For instance, there is some initial AMDGPU support.
811 .. _porting:
813 Porting GlobalISel to A New Target
814 ==================================
816 There are four major classes to implement by the target:
818 * :ref:`CallLowering <api-calllowering>` --- lower calls, returns, and arguments
819   according to the ABI.
820 * :ref:`RegisterBankInfo <api-registerbankinfo>` --- describe
821   :ref:`gmir-regbank` coverage, cross-bank copy cost, and the mapping of
822   operands onto banks for each instruction.
823 * :ref:`LegalizerInfo <api-legalizerinfo>` --- describe what is legal, and how
824   to legalize what isn't.
825 * :ref:`InstructionSelector <api-instructionselector>` --- select generic MIR
826   to target-specific MIR.
828 Additionally:
830 * ``TargetPassConfig`` --- create the passes constituting the pipeline,
831   including additional passes not included in the :ref:`pipeline`.
833 .. _other_resources:
835 Resources
836 =========
838 * `Global Instruction Selection - A Proposal by Quentin Colombet @LLVMDevMeeting 2015 <https://www.youtube.com/watch?v=F6GGbYtae3g>`_
839 * `Global Instruction Selection - Status by Quentin Colombet, Ahmed Bougacha, and Tim Northover @LLVMDevMeeting 2016 <https://www.youtube.com/watch?v=6tfb344A7w8>`_
840 * `GlobalISel - LLVM's Latest Instruction Selection Framework by Diana Picus @FOSDEM17 <https://www.youtube.com/watch?v=d6dF6E4BPeU>`_
841 * GlobalISel: Past, Present, and Future by Quentin Colombet and Ahmed Bougacha @LLVMDevMeeting 2017
842 * Head First into GlobalISel by Daniel Sanders, Aditya Nandakumar, and Justin Bogner @LLVMDevMeeting 2017