Index: llvm/trunk/docs/GlobalISel.rst =================================================================== --- llvm/trunk/docs/GlobalISel.rst +++ llvm/trunk/docs/GlobalISel.rst @@ -318,37 +318,207 @@ If any remain, they are expected to always be selectable, using loads and stores if necessary. +The legality of an instruction may only depend on the instruction itself and +must not depend on any context in which the instruction is used. However, after +deciding that an instruction is not legal, using the context of the instruction +to decide how to legalize the instruction is permitted. As an example, if we +have a ``G_FOO`` instruction of the form:: + + %1:_(s32) = G_CONSTANT i32 1 + %2:_(s32) = G_FOO %0:_(s32), %1:_(s32) + +it's impossible to say that G_FOO is legal iff %1 is a ``G_CONSTANT`` with +value ``1``. However, the following:: + + %2:_(s32) = G_FOO %0:_(s32), i32 1 + +can say that it's legal iff operand 2 is an immediate with value ``1`` because +that information is entirely contained within the single instruction. + .. _api-legalizerinfo: API: LegalizerInfo ^^^^^^^^^^^^^^^^^^ -Currently the API is broadly similar to SelectionDAG/TargetLowering, but -extended in two ways: +The recommended [#legalizer-legacy-footnote]_ API looks like this:: -* The set of available actions is wider, avoiding the currently very - overloaded ``Expand`` (which can cover everything from libcalls to - scalarization depending on the node's opcode). - -* Since there's no separate type legalization, independently varying - types on an instruction can have independent actions. For example a - ``G_ICMP`` has 2 independent types: the result and the inputs; we need - to be able to say that comparing 2 s32s is OK, but the s1 result - must be dealt with in another way. - -As such, the primary key when deciding what to do is the ``InstrAspect``, -essentially a tuple consisting of ``(Opcode, TypeIdx, Type)`` and mapping to a -suggested course of action. + getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL}) + .legalFor({s32, s64, v2s32, v4s32, v2s64}) + .clampScalar(0, s32, s64) + .widenScalarToNextPow2(0) + .clampNumElements(0, v2s32, v4s32) + .clampNumElements(0, v2s64, v2s64) + .moreElementsToNextPow2(0); -An example use might be: +and describes a set of rules by which we can either declare an instruction legal +or decide which action to take to make it more legal. - .. code-block:: c++ +At the core of this ruleset is the ``LegalityQuery`` which describes the +instruction. We use a description rather than the instruction to both allow other +passes to determine legality without having to create an instruction and also to +limit the information available to the predicates to that which is safe to rely +on. Currently, the information available to the predicates that determine +legality contains: + +* The opcode for the instruction + +* The type of each type index (see ``type0``, ``type1``, etc.) + +* The size in bytes and atomic ordering for each MachineMemOperand + +Rule Processing and Declaring Rules +""""""""""""""""""""""""""""""""""" + +The ``getActionDefinitionsBuilder`` function generates a ruleset for the given +opcode(s) that rules can be added to. If multiple opcodes are given, they are +all permanently bound to the same ruleset. The rules in a ruleset are executed +from top to bottom and will start again from the top if an instruction is +legalized as a result of the rules. If the ruleset is exhausted without +satisfying any rule, then it is considered unsupported. + +When it doesn't declare the instruction legal, each pass over the rules may +request that one type changes to another type. Sometimes this can cause multiple +types to change but we avoid this as much as possible as making multiple changes +can make it difficult to avoid infinite loops where, for example, narrowing one +type causes another to be too small and widening that type causes the first one +to be too big. + +In general, it's advisable to declare instructions legal as close to the top of +the rule as possible and to place any expensive rules as low as possible. This +helps with performance as testing for legality happens more often than +legalization and legalization can require multiple passes over the rules. + +As a concrete example, consider the rule:: + + getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL}) + .legalFor({s32, s64, v2s32, v4s32, v2s64}) + .clampScalar(0, s32, s64) + .widenScalarToNextPow2(0); + +and the instruction:: + + %2:_(s7) = G_ADD %0:_(s7), %1:_(s7) + +this doesn't meet the predicate for the :ref:`.legalFor() ` as ``s7`` +is not one of the listed types so it falls through to the +:ref:`.clampScalar() `. It does meet the predicate for this rule +as the type is smaller than the ``s32`` and this rule instructs the legalizer +to change type 0 to ``s32``. It then restarts from the top. This time it does +satisfy ``.legalFor()`` and the resulting output is:: + + %3:_(s32) = G_ANYEXT %0:_(s7) + %4:_(s32) = G_ANYEXT %1:_(s7) + %5:_(s32) = G_ADD %3:_(s32), %4:_(s32) + %2:_(s7) = G_TRUNC %5:_(s32) + +where the ``G_ADD`` is legal and the other instructions are scheduled for +processing by the legalizer. + +Rule Actions +"""""""""""" + +There are various rule factories that append rules to a ruleset but they have a +few actions in common: + +.. _legalfor: + +* ``legalIf()``, ``legalFor()``, etc. declare an instruction to be legal if the + predicate is satisfied. + +* ``narrowScalarIf()``, ``narrowScalarFor()``, etc. declare an instruction to be illegal + if the predicate is satisfied and indicates that narrowing the scalars in one + of the types to a specific type would make it more legal. This action supports + both scalars and vectors. - // The CPU can't deal with an s1 result, do something about it. - setAction({G_ICMP, 0, s1}, WidenScalar); - // An s32 input (the second type) is fine though. - setAction({G_ICMP, 1, s32}, Legal); +* ``widenScalarIf()``, ``widenScalarFor()``, etc. declare an instruction to be illegal + if the predicate is satisfied and indicates that widening the scalars in one + of the types to a specific type would make it more legal. This action supports + both scalars and vectors. +* ``fewerElementsIf()``, ``fewerElementsFor()``, etc. declare an instruction to be + illegal if the predicate is satisfied and indicates reducing the number of + vector elements in one of the types to a specific type would make it more + legal. This action supports vectors. + +* ``moreElementsIf()``, ``moreElementsFor()``, etc. declare an instruction to be illegal + if the predicate is satisfied and indicates increasing the number of vector + elements in one of the types to a specific type would make it more legal. + This action supports vectors. + +* ``lowerIf()``, ``lowerFor()``, etc. declare an instruction to be illegal if the + predicate is satisfied and indicates that replacing it with equivalent + instruction(s) would make it more legal. Support for this action differs for + each opcode. + +* ``libcallIf()``, ``libcallFor()``, etc. declare an instruction to be illegal if the + predicate is satisfied and indicates that replacing it with a libcall would + make it more legal. Support for this action differs for + each opcode. + +* ``customIf()``, ``customFor()``, etc. declare an instruction to be illegal if the + predicate is satisfied and indicates that the backend developer will supply + a means of making it more legal. + +* ``unsupportedIf()``, ``unsupportedFor()``, etc. declare an instruction to be illegal + if the predicate is satisfied and indicates that there is no way to make it + legal and the compiler should fail. + +* ``fallback()`` falls back on an older API and should only be used while porting + existing code from that API. + +Rule Predicates +""""""""""""""" + +The rule factories also have predicates in common: + +* ``legal()``, ``lower()``, etc. are always satisfied. + +* ``legalIf()``, ``narrowScalarIf()``, etc. are satisfied if the user-supplied + ``LegalityPredicate`` function returns true. This predicate has access to the + information in the ``LegalityQuery`` to make its decision. + User-supplied predicates can also be combined using ``all(P0, P1, ...)``. + +* ``legalFor()``, ``narrowScalarFor()``, etc. are satisfied if the type matches one in + a given set of types. For example ``.legalFor({s16, s32})`` declares the + instruction legal if type 0 is either s16 or s32. Additional versions for two + and three type indices are generally available. For these, all the type + indices considered together must match all the types in one of the tuples. So + ``.legalFor({{s16, s32}, {s32, s64}})`` will only accept ``{s16, s32}``, or + ``{s32, s64}`` but will not accept ``{s16, s64}``. + +* ``legalForTypesWithMemSize()``, ``narrowScalarForTypesWithMemSize()``, etc. are + similar to ``legalFor()``, ``narrowScalarFor()``, etc. but additionally require a + MachineMemOperand to have a given size in each tuple. + +* ``legalForCartesianProduct()``, ``narrowScalarForCartesianProduct()``, etc. are + satisfied if each type index matches one element in each of the independent + sets. So ``.legalForCartesianProduct({s16, s32}, {s32, s64})`` will accept + ``{s16, s32}``, ``{s16, s64}``, ``{s32, s32}``, and ``{s32, s64}``. + +Composite Rules +""""""""""""""" + +There are some composite rules for common situations built out of the above facilities: + +* ``widenScalarToNextPow2()`` is like ``widenScalarIf()`` but is satisfied iff the type + size in bits is not a power of 2 and selects a target type that is the next + largest power of 2. + +.. _clampscalar: + +* ``minScalar()`` is like ``widenScalarIf()`` but is satisfied iff the type + size in bits is smaller than the given minimum and selects the minimum as the + target type. Similarly, there is also a ``maxScalar()`` for the maximum and a + ``clampScalar()`` to do both at once. + +* ``minScalarSameAs()`` is like ``minScalar()`` but the minimum is taken from another + type index. + +* ``moreElementsToNextMultiple()`` is like ``moreElementsToNextPow2()`` but is based on + multiples of X rather than powers of 2. + +Other Information +""""""""""""""""" ``TODO``: An alternative worth investigating is to generalize the API to represent @@ -361,41 +531,11 @@ Expanding that to describe legalization actions is a much larger but potentially useful project. -.. _milegalizer-non-power-of-2: - -Non-power of 2 types -^^^^^^^^^^^^^^^^^^^^ - -``TODO``: -Types which have a size that isn't a power of 2 aren't currently supported. -The setAction API will probably require changes to support them. -Even notionally explicitly specified operations only make suggestions -like "Widen" or "Narrow". The eventual type is still unspecified and a -search is performed by repeated doubling/halving of the type's -size. -This is incorrect for types that aren't a power of 2. It's reasonable to -expect we could construct an efficient set of side-tables for more general -lookups though, encoding a map from the integers (i.e. the size of the current -type) to types (the legal size). - -.. _milegalizer-vector: - -Vector types -^^^^^^^^^^^^ - -Vectors first get their element type legalized: ```` becomes -```` such that at least one operation is legal with ``sC``. - -This is currently specified by the function ``setScalarInVectorAction``, called -for example as: - - setScalarInVectorAction(G_ICMP, s1, WidenScalar); - -Next the number of elements is chosen so that the entire operation is -legal. This aspect is not controllable at the moment, but probably -should be (you could imagine disagreements on whether a ``<2 x s8>`` -operation should be scalarized or extended to ``<8 x s8>``). +.. rubric:: Footnotes +.. [#legalizer-legacy-footnote] An API is broadly similar to + SelectionDAG/TargetLowering is available but is not recommended as a more + powerful API is available. .. _regbankselect: