1.. _milegalizer: 2 3Legalizer 4--------- 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 a 11 target-specific (non-generic) instruction. This doesn't necessarily mean that 12 :doc:`InstructionSelect` has to handle it though. It just means that 13 **something** must handle it. 14 15* operating on **vregs that can be loaded and stored** -- if necessary, the 16 target can select a ``G_LOAD``/``G_STORE`` of each gvreg operand. 17 18As opposed to 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 the 22validity of the intermediate code, instructions are introduced: 23 24* ``G_MERGE_VALUES`` --- concatenate multiple registers of the same 25 size into a single wider register. 26 27* ``G_UNMERGE_VALUES`` --- extract multiple registers of the same size 28 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 stores 36if necessary. 37 38The legality of an instruction may only depend on the instruction itself and 39must not depend on any context in which the instruction is used. However, after 40deciding that an instruction is not legal, using the context of the instruction 41to decide how to legalize the instruction is permitted. As an example, if we 42have a ``G_FOO`` instruction of the form:: 43 44 %1:_(s32) = G_CONSTANT i32 1 45 %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`` with 48value ``1``. However, the following:: 49 50 %2:_(s32) = G_FOO %0:_(s32), i32 1 51 52can say that it's legal iff operand 2 is an immediate with value ``1`` because 53that information is entirely contained within the single instruction. 54 55.. _api-legalizerinfo: 56 57API: LegalizerInfo 58^^^^^^^^^^^^^^^^^^ 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 legal 71or decide which action to take to make it more legal. 72 73At the core of this ruleset is the ``LegalityQuery`` which describes the 74instruction. We use a description rather than the instruction to both allow other 75passes to determine legality without having to create an instruction and also to 76limit the information available to the predicates to that which is safe to rely 77on. Currently, the information available to the predicates that determine 78legality contains: 79 80* The opcode for the instruction 81 82* The type of each type index (see ``type0``, ``type1``, etc.) 83 84* The size in bytes and atomic ordering for each MachineMemOperand 85 86.. note:: 87 88 An alternative worth investigating is to generalize the API to represent 89 actions using ``std::function`` that implements the action, instead of explicit 90 enum tokens (``Legal``, ``WidenScalar``, ...) that instruct it to call a 91 function. This would have some benefits, most notable being that Custom could 92 be removed. 93 94.. rubric:: Footnotes 95 96.. [#legalizer-legacy-footnote] An API is broadly similar to 97 SelectionDAG/TargetLowering is available but is not recommended as a more 98 powerful API is available. 99 100Rule Processing and Declaring Rules 101""""""""""""""""""""""""""""""""""" 102 103The ``getActionDefinitionsBuilder`` function generates a ruleset for the given 104opcode(s) that rules can be added to. If multiple opcodes are given, they are 105all permanently bound to the same ruleset. The rules in a ruleset are executed 106from top to bottom and will start again from the top if an instruction is 107legalized as a result of the rules. If the ruleset is exhausted without 108satisfying any rule, then it is considered unsupported. 109 110When it doesn't declare the instruction legal, each pass over the rules may 111request that one type changes to another type. Sometimes this can cause multiple 112types to change but we avoid this as much as possible as making multiple changes 113can make it difficult to avoid infinite loops where, for example, narrowing one 114type causes another to be too small and widening that type causes the first one 115to be too big. 116 117In general, it's advisable to declare instructions legal as close to the top of 118the rule as possible and to place any expensive rules as low as possible. This 119helps with performance as testing for legality happens more often than 120legalization 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 the 135:ref:`.clampScalar() <clampscalar>`. It does meet the predicate for this rule 136as the type is smaller than the ``s32`` and this rule instructs the legalizer 137to change type 0 to ``s32``. It then restarts from the top. This time it does 138satisfy ``.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 for 146processing by the legalizer. 147 148Rule Actions 149"""""""""""" 150 151There are various rule factories that append rules to a ruleset but they have a 152few actions in common: 153 154.. _legalfor: 155 156* ``legalIf()``, ``legalFor()``, etc. declare an instruction to be legal if the 157 predicate is satisfied. 158 159* ``narrowScalarIf()``, ``narrowScalarFor()``, etc. declare an instruction to be illegal 160 if the predicate is satisfied and indicates that narrowing the scalars in one 161 of the types to a specific type would make it more legal. This action supports 162 both scalars and vectors. 163 164* ``widenScalarIf()``, ``widenScalarFor()``, etc. declare an instruction to be illegal 165 if the predicate is satisfied and indicates that widening the scalars in one 166 of the types to a specific type would make it more legal. This action supports 167 both scalars and vectors. 168 169* ``fewerElementsIf()``, ``fewerElementsFor()``, etc. declare an instruction to be 170 illegal if the predicate is satisfied and indicates reducing the number of 171 vector elements in one of the types to a specific type would make it more 172 legal. This action supports vectors. 173 174* ``moreElementsIf()``, ``moreElementsFor()``, etc. declare an instruction to be illegal 175 if the predicate is satisfied and indicates increasing the number of vector 176 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 be 180 illegal if the predicate is satisfied and indicates that replacing 181 it with equivalent instruction(s) would make it more legal. Support 182 for this action differs for each opcode. These may provide an 183 optional LegalizeMutation containing a type to attempt to perform 184 the expansion in a different type. 185 186* ``libcallIf()``, ``libcallFor()``, etc. declare an instruction to be illegal if the 187 predicate is satisfied and indicates that replacing it with a libcall would 188 make it more legal. Support for this action differs for 189 each opcode. 190 191* ``customIf()``, ``customFor()``, etc. declare an instruction to be illegal if the 192 predicate is satisfied and indicates that the backend developer will supply 193 a means of making it more legal. 194 195* ``unsupportedIf()``, ``unsupportedFor()``, etc. declare an instruction to be illegal 196 if the predicate is satisfied and indicates that there is no way to make it 197 legal and the compiler should fail. 198 199* ``fallback()`` falls back on an older API and should only be used while porting 200 existing code from that API. 201 202Rule Predicates 203""""""""""""""" 204 205The rule factories also have predicates in common: 206 207* ``legal()``, ``lower()``, etc. are always satisfied. 208 209* ``legalIf()``, ``narrowScalarIf()``, etc. are satisfied if the user-supplied 210 ``LegalityPredicate`` function returns true. This predicate has access to the 211 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 in 215 a given set of types. For example ``.legalFor({s16, s32})`` declares the 216 instruction legal if type 0 is either s16 or s32. Additional versions for two 217 and three type indices are generally available. For these, all the type 218 indices considered together must match all the types in one of the tuples. So 219 ``.legalFor({{s16, s32}, {s32, s64}})`` will only accept ``{s16, s32}``, or 220 ``{s32, s64}`` but will not accept ``{s16, s64}``. 221 222* ``legalForTypesWithMemSize()``, ``narrowScalarForTypesWithMemSize()``, etc. are 223 similar to ``legalFor()``, ``narrowScalarFor()``, etc. but additionally require a 224 MachineMemOperand to have a given size in each tuple. 225 226* ``legalForCartesianProduct()``, ``narrowScalarForCartesianProduct()``, etc. are 227 satisfied if each type index matches one element in each of the independent 228 sets. So ``.legalForCartesianProduct({s16, s32}, {s32, s64})`` will accept 229 ``{s16, s32}``, ``{s16, s64}``, ``{s32, s32}``, and ``{s32, s64}``. 230 231Composite Rules 232""""""""""""""" 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 type 237 size in bits is not a power of 2 and selects a target type that is the next 238 largest power of 2. 239 240.. _clampscalar: 241 242* ``minScalar()`` is like ``widenScalarIf()`` but is satisfied iff the type 243 size in bits is smaller than the given minimum and selects the minimum as the 244 target type. Similarly, there is also a ``maxScalar()`` for the maximum and a 245 ``clampScalar()`` to do both at once. 246 247* ``minScalarSameAs()`` is like ``minScalar()`` but the minimum is taken from another 248 type index. 249 250* ``moreElementsToNextMultiple()`` is like ``moreElementsToNextPow2()`` but is based on 251 multiples of X rather than powers of 2. 252 253.. _min-legalizerinfo: 254 255Minimum Rule Set 256^^^^^^^^^^^^^^^^ 257 258GlobalISel's legalizer has a great deal of flexibility in how a given target 259shapes the GMIR that the rest of the backend must handle. However, there are 260a small number of requirements that all targets must meet. 261 262Before discussing the minimum requirements, we'll need some terminology: 263 264Producer Type Set 265 The set of types which is the union of all possible types produced by at 266 least one legal instruction. 267 268Consumer Type Set 269 The set of types which is the union of all possible types consumed by at 270 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 it 274for a few specific instructions. 275 276Minimum Rules For Scalars 277""""""""""""""""""""""""" 278 279* G_ANYEXT must be legal for all inputs from the producer type set and all larger 280 outputs from the consumer type set. 281* G_TRUNC must be legal for all inputs from the producer type set and all 282 smaller outputs from the consumer type set. 283 284G_ANYEXT, and G_TRUNC have mandatory legality since the GMIR requires a means to 285connect operations with different type sizes. They are usually trivial to support 286since G_ANYEXT doesn't define the value of the additional bits and G_TRUNC is 287discarding bits. The other conversions can be lowered into G_ANYEXT/G_TRUNC 288with some additional operations that are subject to further legalization. For 289example, G_SEXT can lower to:: 290 291 %1 = G_ANYEXT %0 292 %2 = G_CONSTANT ... 293 %3 = G_SHL %1, %2 294 %4 = G_ASHR %3, %2 295 296and the G_CONSTANT/G_SHL/G_ASHR can further lower to other operations or target 297instructions. Similarly, G_FPEXT has no legality requirement since it can lower 298to a G_ANYEXT followed by a target instruction. 299 300G_MERGE_VALUES and G_UNMERGE_VALUES do not have legality requirements since the 301former can lower to G_ANYEXT and some other legalizable instructions, while the 302latter can lower to some legalizable instructions followed by G_TRUNC. 303 304Minimum Legality For Vectors 305"""""""""""""""""""""""""""" 306 307Within the vector types, there aren't any defined conversions in LLVM IR as 308vectors are often converted by reinterpreting the bits or by decomposing the 309vector and reconstituting it as a different type. As such, G_BITCAST is the 310only operation to account for. We generally don't require that it's legal 311because it can usually be lowered to COPY (or to nothing using 312replaceAllUses()). However, there are situations where G_BITCAST is non-trivial 313(e.g. little-endian vectors of big-endian data such as on big-endian MIPS MSA and 314big-endian ARM NEON, see `_i_bitcast`). To account for this G_BITCAST must be 315legal 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 requirements 325for vector inputs. 326 327Minimum Legality for Pointers 328""""""""""""""""""""""""""""" 329 330There are no minimum rules for pointers since G_INTTOPTR and G_PTRTOINT can 331be selected to a COPY from register class to another by the legalizer. 332 333Minimum Legality For Operations 334""""""""""""""""""""""""""""""" 335 336The rules for G_ANYEXT, G_MERGE_VALUES, G_BITCAST, G_BUILD_VECTOR, 337G_BUILD_VECTOR_TRUNC, G_CONCAT_VECTORS, G_UNMERGE_VALUES, G_PTRTOINT, and 338G_INTTOPTR have already been noted above. In addition to those, the following 339operations have requirements: 340 341* For every type that can be produced by any instruction, G_IMPLICIT_DEF must be 342 legal. 343* G_PHI must be legal for all types in the producer and consumer typesets. This 344 is usually trivial as it requires no code to be selected. 345* At least one G_FRAME_INDEX must be legal 346* At least one G_BLOCK_ADDR must be legal 347 348There are many other operations you'd expect to have legality requirements but 349they can be lowered to target instructions which are legal by definition. 350