350 lines · plain
1.. _milegalizer:2 3Legalizer4---------5 6This pass transforms the generic machine instructions such that they are legal.7 8A legal instruction is defined as:9 10* **selectable** --- the target will later be able to select it to a11 target-specific (non-generic) instruction. This doesn't necessarily mean that12 :doc:`InstructionSelect` has to handle it though. It just means that13 **something** must handle it.14 15* operating on **vregs that can be loaded and stored** -- if necessary, the16 target can select a ``G_LOAD``/``G_STORE`` of each gvreg operand.17 18Unlike SelectionDAG, there are no legalization phases. In particular,19'type' and 'operation' legalization are not separate.20 21Legalization is iterative, and all state is contained in GMIR. To maintain the22validity of the intermediate code, instructions are introduced:23 24* ``G_MERGE_VALUES`` --- concatenate multiple registers of the same25 size into a single wider register.26 27* ``G_UNMERGE_VALUES`` --- extract multiple registers of the same size28 from a single wider register.29 30* ``G_EXTRACT`` --- extract a simple register (as contiguous sequences of bits)31 from a single wider register.32 33As they are expected to be temporary byproducts of the legalization process,34they are combined at the end of the :ref:`milegalizer` pass.35If any remain, they are expected to always be selectable, using loads and stores36if necessary.37 38The legality of an instruction may only depend on the instruction itself and39must not depend on any context in which the instruction is used. However, after40deciding that an instruction is not legal, using the context of the instruction41to decide how to legalize the instruction is permitted. As an example, if we42have a ``G_FOO`` instruction of the form::43 44 %1:_(s32) = G_CONSTANT i32 145 %2:_(s32) = G_FOO %0:_(s32), %1:_(s32)46 47it's impossible to say that ``G_FOO`` is legal iff %1 is a ``G_CONSTANT`` with48value ``1``. However, the following::49 50 %2:_(s32) = G_FOO %0:_(s32), i32 151 52can say that it's legal iff operand 2 is an immediate with value ``1`` because53that information is entirely contained within the single instruction.54 55.. _api-legalizerinfo:56 57API: LegalizerInfo58^^^^^^^^^^^^^^^^^^59 60The recommended [#legalizer-legacy-footnote]_ API looks like this::61 62 getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL})63 .legalFor({s32, s64, v2s32, v4s32, v2s64})64 .clampScalar(0, s32, s64)65 .widenScalarToNextPow2(0)66 .clampNumElements(0, v2s32, v4s32)67 .clampNumElements(0, v2s64, v2s64)68 .moreElementsToNextPow2(0);69 70and describes a set of rules by which we can either declare an instruction legal71or decide which action to take to make it more legal.72 73At the core of this ruleset is the ``LegalityQuery`` which describes the74instruction. We use a description rather than the instruction to both allow other75passes to determine legality without having to create an instruction and also to76limit the information available to the predicates to that which is safe to rely77on. Currently, the information available to the predicates that determine78legality contains:79 80* The opcode for the instruction81 82* The type of each type index (see ``type0``, ``type1``, etc.)83 84* The size in bytes and atomic ordering for each MachineMemOperand85 86.. note::87 88 An alternative worth investigating is to generalize the API to represent89 actions using ``std::function`` that implements the action, instead of explicit90 enum tokens (``Legal``, ``WidenScalar``, ...) that instruct it to call a91 function. This would have some benefits, most notable being that Custom could92 be removed.93 94.. rubric:: Footnotes95 96.. [#legalizer-legacy-footnote] An API that is broadly similar to97 SelectionDAG/TargetLowering is available, but is not recommended as a more98 powerful API is available.99 100Rule Processing and Declaring Rules101"""""""""""""""""""""""""""""""""""102 103The ``getActionDefinitionsBuilder`` function generates a ruleset for the given104opcode(s) that rules can be added to. If multiple opcodes are given, they are105all permanently bound to the same ruleset. The rules in a ruleset are executed106from top to bottom and will start again from the top if an instruction is107legalized as a result of the rules. If the ruleset is exhausted without108satisfying any rule, then it is considered unsupported.109 110When it doesn't declare the instruction legal, each pass over the rules may111request that one type be changed to another type. Sometimes this can cause multiple112types to change but we avoid this as much as possible as making multiple changes113can make it difficult to avoid infinite loops where, for example, narrowing one114type causes another to be too small, and widening that type causes the first one115to be too big.116 117In general, it's advisable to declare instructions legal as close to the top of118the rule as possible and to place any expensive rules as low as possible. This119helps with performance as testing for legality happens more often than120legalization and legalization can require multiple passes over the rules.121 122As a concrete example, consider the rule::123 124 getActionDefinitionsBuilder({G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL})125 .legalFor({s32, s64, v2s32, v4s32, v2s64})126 .clampScalar(0, s32, s64)127 .widenScalarToNextPow2(0);128 129and the instruction::130 131 %2:_(s7) = G_ADD %0:_(s7), %1:_(s7)132 133This doesn't meet the predicate for the :ref:`.legalFor() <legalfor>` as ``s7``134is not one of the listed types so it falls through to the135:ref:`.clampScalar() <clampscalar>`. It does meet the predicate for this rule136as the type is smaller than the ``s32`` and this rule instructs the legalizer137to change type 0 to ``s32``. It then restarts from the top. This time it does138satisfy ``.legalFor()`` and the resulting output is::139 140 %3:_(s32) = G_ANYEXT %0:_(s7)141 %4:_(s32) = G_ANYEXT %1:_(s7)142 %5:_(s32) = G_ADD %3:_(s32), %4:_(s32)143 %2:_(s7) = G_TRUNC %5:_(s32)144 145where the ``G_ADD`` is legal and the other instructions are scheduled for146processing by the legalizer.147 148Rule Actions149""""""""""""150 151There are various rule factories that append rules to a ruleset, but they have a152few actions in common:153 154.. _legalfor:155 156* ``legalIf()``, ``legalFor()``, etc. declare an instruction to be legal if the157 predicate is satisfied.158 159* ``narrowScalarIf()``, ``narrowScalarFor()``, etc. declare an instruction to be illegal160 if the predicate is satisfied and indicates that narrowing the scalars in one161 of the types to a specific type would make it more legal. This action supports162 both scalars and vectors.163 164* ``widenScalarIf()``, ``widenScalarFor()``, etc. declare an instruction to be illegal165 if the predicate is satisfied and indicates that widening the scalars in one166 of the types to a specific type would make it more legal. This action supports167 both scalars and vectors.168 169* ``fewerElementsIf()``, ``fewerElementsFor()``, etc. declare an instruction to be170 illegal if the predicate is satisfied and indicates reducing the number of171 vector elements in one of the types to a specific type would make it more172 legal. This action supports vectors.173 174* ``moreElementsIf()``, ``moreElementsFor()``, etc. declare an instruction to be illegal175 if the predicate is satisfied and indicates increasing the number of vector176 elements in one of the types to a specific type would make it more legal.177 This action supports vectors.178 179* ``lowerIf()``, ``lowerFor()``, etc. declare an instruction to be180 illegal if the predicate is satisfied and indicates that replacing181 it with equivalent instruction(s) would make it more legal. Support182 for this action differs for each opcode. These may provide an183 optional LegalizeMutation containing a type to attempt to perform184 the expansion in a different type.185 186* ``libcallIf()``, ``libcallFor()``, etc. declare an instruction to be illegal if the187 predicate is satisfied and indicates that replacing it with a libcall would188 make it more legal. Support for this action differs for189 each opcode.190 191* ``customIf()``, ``customFor()``, etc. declare an instruction to be illegal if the192 predicate is satisfied and indicates that the backend developer will supply193 a means of making it more legal.194 195* ``unsupportedIf()``, ``unsupportedFor()``, etc. declare an instruction to be illegal196 if the predicate is satisfied and indicates that there is no way to make it197 legal and the compiler should fail.198 199* ``fallback()`` falls back on an older API and should only be used while porting200 existing code from that API.201 202Rule Predicates203"""""""""""""""204 205The rule factories also have the following predicates in common:206 207* ``legal()``, ``lower()``, etc. are always satisfied.208 209* ``legalIf()``, ``narrowScalarIf()``, etc. are satisfied if the user-supplied210 ``LegalityPredicate`` function returns true. This predicate has access to the211 information in the ``LegalityQuery`` to make its decision.212 User-supplied predicates can also be combined using ``all(P0, P1, ...)``.213 214* ``legalFor()``, ``narrowScalarFor()``, etc. are satisfied if the type matches one in215 a given set of types. For example ``.legalFor({s16, s32})`` declares the216 instruction legal if type 0 is either s16 or s32. Additional versions for two217 and three type indices are generally available. For these, all the type218 indices considered together must match all the types in one of the tuples. So219 ``.legalFor({{s16, s32}, {s32, s64}})`` will only accept ``{s16, s32}``, or220 ``{s32, s64}`` but will not accept ``{s16, s64}``.221 222* ``legalForTypesWithMemSize()``, ``narrowScalarForTypesWithMemSize()``, etc. are223 similar to ``legalFor()``, ``narrowScalarFor()``, etc. but additionally require a224 MachineMemOperand to have a given size in each tuple.225 226* ``legalForCartesianProduct()``, ``narrowScalarForCartesianProduct()``, etc. are227 satisfied if each type index matches one element in each of the independent228 sets. So ``.legalForCartesianProduct({s16, s32}, {s32, s64})`` will accept229 ``{s16, s32}``, ``{s16, s64}``, ``{s32, s32}``, and ``{s32, s64}``.230 231Composite Rules232"""""""""""""""233 234There are some composite rules for common situations built out of the above facilities:235 236* ``widenScalarToNextPow2()`` is like ``widenScalarIf()`` but is satisfied iff the type237 size in bits is not a power of 2 and selects a target type that is the next238 largest power of 2.239 240.. _clampscalar:241 242* ``minScalar()`` is like ``widenScalarIf()`` but is satisfied iff the type243 size in bits is smaller than the given minimum and selects the minimum as the244 target type. Similarly, there is also a ``maxScalar()`` for the maximum and a245 ``clampScalar()`` to do both at once.246 247* ``minScalarSameAs()`` is like ``minScalar()`` but the minimum is taken from another248 type index.249 250* ``moreElementsToNextMultiple()`` is like ``moreElementsToNextPow2()`` but is based on251 multiples of X rather than powers of 2.252 253.. _min-legalizerinfo:254 255Minimum Rule Set256^^^^^^^^^^^^^^^^257 258GlobalISel's legalizer has a great deal of flexibility in how a given target259shapes the GMIR that the rest of the backend must handle. However, there are260a small number of requirements that all targets must meet.261 262Before discussing the minimum requirements, we'll need some terminology:263 264Producer Type Set265 The set of types which is the union of all possible types produced by at266 least one legal instruction.267 268Consumer Type Set269 The set of types which is the union of all possible types consumed by at270 least one legal instruction.271 272Both sets are often identical, but there's no guarantee of that. For example,273it's not uncommon to be unable to consume s64 but still be able to produce it274for a few specific instructions.275 276Minimum Rules For Scalars277"""""""""""""""""""""""""278 279* ``G_ANYEXT`` must be legal for all inputs from the producer type set and all larger280 outputs from the consumer type set.281* ``G_TRUNC`` must be legal for all inputs from the producer type set and all282 smaller outputs from the consumer type set.283 284``G_ANYEXT`` and ``G_TRUNC`` have mandatory legality since the GMIR requires a means to285connect operations with different type sizes. They are usually trivial to support286since ``G_ANYEXT`` doesn't define the value of the additional bits and ``G_TRUNC`` is287discarding bits. The other conversions can be lowered into ``G_ANYEXT``/``G_TRUNC``288with some additional operations that are subject to further legalization. For289example, ``G_SEXT`` can lower to::290 291 %1 = G_ANYEXT %0292 %2 = G_CONSTANT ...293 %3 = G_SHL %1, %2294 %4 = G_ASHR %3, %2295 296and the ``G_CONSTANT``/``G_SHL``/``G_ASHR`` can further lower to other operations or target297instructions. Similarly, ``G_FPEXT`` has no legality requirement since it can lower298to a ``G_ANYEXT`` followed by a target instruction.299 300``G_MERGE_VALUES`` and ``G_UNMERGE_VALUES`` do not have legality requirements since the301former can lower to ``G_ANYEXT`` and some other legalizable instructions, while the302latter can lower to some legalizable instructions followed by ``G_TRUNC``.303 304Minimum Legality For Vectors305""""""""""""""""""""""""""""306 307Within the vector types, there aren't any defined conversions in LLVM IR as308vectors are often converted by reinterpreting the bits or by decomposing the309vector and reconstituting it as a different type. As such, ``G_BITCAST`` is the310only operation to account for. We generally don't require that it's legal311because it can usually be lowered to ``COPY`` (or to nothing using312``replaceAllUses()``). However, there are situations where ``G_BITCAST`` is non-trivial313(e.g. little-endian vectors of big-endian data such as on big-endian MIPS MSA and314big-endian ARM NEON, see `_i_bitcast`). To account for this, ``G_BITCAST`` must be315legal for all type combinations that change the bit pattern in the value.316 317There are no legality requirements for ``G_BUILD_VECTOR``, or ``G_BUILD_VECTOR_TRUNC``318since these can be handled by:319* Declaring them legal.320* Scalarizing them.321* Lowering them to ``G_TRUNC``+``G_ANYEXT`` and some legalizable instructions.322* Lowering them to target instructions which are legal by definition.323 324The same reasoning also allows ``G_UNMERGE_VALUES`` to lack legality requirements325for vector inputs.326 327Minimum Legality for Pointers328"""""""""""""""""""""""""""""329 330There are no minimum rules for pointers since ``G_INTTOPTR`` and ``G_PTRTOINT`` can331be selected to a ``COPY`` from register class to another by the legalizer.332 333Minimum Legality For Operations334"""""""""""""""""""""""""""""""335 336The rules for ``G_ANYEXT``, ``G_MERGE_VALUES``, ``G_BITCAST``, ``G_BUILD_VECTOR``,337``G_BUILD_VECTOR_TRUNC``, ``G_CONCAT_VECTORS``, ``G_UNMERGE_VALUES``, ``G_PTRTOINT``, and338``G_INTTOPTR`` have already been noted above. In addition to those, the following339operations have requirements:340 341* ``G_IMPLICIT_DEF`` must be legal for every type that can be produced342 by any instruction.343* ``G_PHI`` must be legal for all types in the producer and consumer typesets. This344 is usually trivial as it requires no code to be selected.345* At least one ``G_FRAME_INDEX`` must be legal346* At least one ``G_BLOCK_ADDR`` must be legal347 348There are many other operations you'd expect to have legality requirements, but349they can be lowered to target instructions which are legal by definition.350