[globalisel] Update the legalizer documentation

[dsanders]

Summary

• The getActionDefinitionsBuilder() is now documented.
  • Includes descriptions of the various actions (legal*, widenScalar*, lower*, etc).
  • Includes descriptions of the various predicates (*If, *For, *ForCartesianProduct, etc.)
  • Includes the rule-order details
• Removed the out-of-date prohibition on non-power-of-2 types.
• Removed the Vector types section since it was incorrect and vectors follow the same ruleset as scalars. They're only special in the sense that more of the actions and predicates are meaningful for them (e.g. moreElements).
• Clarified the position on context sensitive legality (which is not permitted) and contrasted this with context sensitive legalization (which is permitted).

[paquette]

I think this looks good. I have a few stylistic suggestions, but I don't think they're worth holding up review over.

• Added some inline comments on document structure. I think that adding some more sections would make it easier to quickly search. I'm not sure if we can have that deep of nested sections though.
• I took this and copied it into Hemingwayapp (http://www.hemingwayapp.com) and found a few sentences were hard to read. I think it would be good to resolve some of those if possible? Of course, this is entirely stylistic preference. :)

docs/GlobalISel.rst

343–345 ↗

(On Diff #197156)

I think it would be better to mention the SelectionDAG/TargetLowering API after detailing the recommended method. Probably don't want people to think about the unrecommended API before thinking about the recommended API. ;)

358 ↗

(On Diff #197156)

If getActionDefinitionsBuilder can have its own subsection, then I think this should too for symmetry's sake.

371 ↗

(On Diff #197156)

I think this is long enough that it deserves its own section? (Is it possible to have another subsection here? If not, meh, whatever.)

378–379 ↗

(On Diff #197156)

It seems like this could have a subsection as well. Something like "Declaring Rules"?

381 ↗

(On Diff #197156)

Should legalIf(), legalFor() etc have code quotes?

425 ↗

(On Diff #197156)

This could have a section just called "Predicates" or something?

450–451 ↗

(On Diff #197156)

This could have a section called "Composite Rules"

468 ↗

(On Diff #197156)

I think that if you add a "Predicates" section, this could be pulled into there

[dsanders]

docs/GlobalISel.rst

343–345 ↗

(On Diff #197156)

I've moved this to a footnote. I don't like the way footnotes render (they look like citations) but at least it's out of the way.

358 ↗

(On Diff #197156)

I haven't put this one into a subsection as it would leave the initial section rather short and it felt like it was part of the same high-level overview. Let me know if the latest version still looks like it needs a section here

371 ↗

(On Diff #197156)

There's exactly one left :-)

Having added the various sections the others felt more like a reference and this one felt more like an explanation so I've expanded on this section with examples and advice. Could you take a look at the new text in the 'Rule Processing and Declaring Rules' section?

[dsanders]

Added example and further explanation of the rule processing.
Subdivided into sections and other minor changes.

[paquette]

The extra sections really make a difference! Looks great now.

llvm/trunk/docs/GlobalISel.rst

 * ``G_EXTRACT`` --- extract a simple register (as contiguous sequences of bits)
   from a single wider register.
 
 As they are expected to be temporary byproducts of the legalization process,
 they are combined at the end of the :ref:`milegalizer` pass.
 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() <legalfor>` as ``s7``
+is not one of the listed types so it falls through to the
+:ref:`.clampScalar() <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
 actions using ``std::function`` that implements the action, instead of explicit
 enum tokens (``Legal``, ``WidenScalar``, ...).
 
 ``TODO``:
 Moreover, we could use TableGen to initially infer legality of operation from
 existing patterns (as any pattern we can select is by definition legal).
 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: ``<A x sB>`` becomes
-``<A x sC>`` 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:
 
 RegBankSelect
 -------------
 
 This pass constrains the :ref:`gmir-gvregs` operands of generic
 instructions to some :ref:`gmir-regbank`.