Index: docs/GlobalISel.rst =================================================================== --- docs/GlobalISel.rst +++ docs/GlobalISel.rst @@ -318,17 +318,154 @@ 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: +An API is broadly similar to SelectionDAG/TargetLowering is available but is not +recommended as a more powerful API is available. The recommended API looks like +this:: + + 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); + +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. + +At the core of this ruleset is the ``LegalityQuery`` which describes the +instruction. We use a description rather than 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 + +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. + +There are various rule factories that append rules to a ruleset but they have a +few outcomes in common: + +* 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. + +* 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. + +They 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. + +* 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}``. + +and finally 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. + +* 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. -* 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). +* moreElementsToNextMultiple() is like moreElementsToNextPow2() but is based on + multiples of X rather than powers of 2. + +Predicates can also be combined using ``all(P0, P1, ...)``. * Since there's no separate type legalization, independently varying types on an instruction can have independent actions. For example a @@ -336,20 +473,6 @@ 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. - -An example use might be: - - .. code-block:: c++ - - // 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); - - ``TODO``: An alternative worth investigating is to generalize the API to represent actions using ``std::function`` that implements the action, instead of explicit @@ -361,42 +484,6 @@ 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>``). - - .. _regbankselect: RegBankSelect