[RFC][GlobalISel] Enable legalizing non-power-of-2 sized types.

[kristof.beyls]

Summary

I've been working on and off on implementing/designing support for
non-power-of-2-sized types in GlobalISel. By now, I think I've iterated
to a plausible design, but the patch is large-ish and I think it might
make more sense to first discuss the design tradeoffs at a higher level.
That's why I tried to add a higher-level description here that I hope
will help in reviewing the design.

1. Interface for targets to describe how to legalize.

In GlobalISel, the API in the LegalizerInfo class is the main interface
for targets to specify which types are legal for which operations, and
what to do to turn illegal type/operation combinations into legal ones.

For each operation the type sizes that can be legalized without having
to change the size of the type are specified with a call to setAction.
This isn't different to how GlobalISel works today. For example, for a
target that supports 32 and 64 bit adds natively:

for (auto Ty : {s32, s64})

setAction({G_ADD, 0, s32}, Legal);

or for a target that needs a library call for a 32 bit division:

setAction({G_SDIV, s32}, Libcall);

The main conceptual change I propose to the LegalizerInfo API, is in
specifying how to legalize the type sizes for which a change of size is
needed. For example, in the above example, how to specify how all types
from i1 to i8388607 (apart from s32 and s64 which are legal) need to be
legalized and expressed in terms of operations on the available legal
sizes (again, i32 and i64 in this case). Up till now, the implementation
only allows specifying power-of-2-sized types (e.g. setAction({G_ADD, 0,
s128}, NarrowScalar). A worse limitation is that if you'd want to
specify how to legalize all the sized types as allowed by the LLVM-IR
LangRef, i1 to i8388607, you'd have to call setAction 8388607-3 times
and probably would need a lot of memory to store all of these
specifications.

Instead, my proposal is to specify the legalization actions that need
to change the size of the type to be specified using a
"SizeChangeStrategy". For example:

setLegalizeScalarToDifferentSizeStrategy(
    G_ADD, 0, widenToLargerAndNarrowToLargest);

This example indicates that for type sizes for which there is a larger
size that can be legalized towards, do it by Widening the size.
For example, G_ADD on s17 will be legalized by first doing WidenScalar
to make it s32, after which it's legal.
The "NarrowToLargest" indicates what to do if there is no larger size
that can be legalized towards. E.g. G_ADD on s92 will be legalized by
doing NarrowScalar to s64.

Another example, taken from the ARM backend is:

for (unsigned Op : {G_SDIV, G_UDIV}) {
  setLegalizeScalarToDifferentSizeStrategy(Op, 0,
      widenToLargerTypesUnsupportedOtherwise);
  if (ST.hasDivideInARMMode())
    setAction({Op, s32}, Legal);
  else
    setAction({Op, s32}, Libcall);
}

For this example, G_SDIV on s8, on a target without a divide
instruction, would be legalized by first doing action (WidenScalar,
s32), followed by (Libcall, s32).

The same principle is also followed for when the number of vector lanes
on vector data types need to be changed, e.g.:

setAction({G_ADD, LLT::vector(8, 8)}, LegalizerInfo::Legal);
setAction({G_ADD, LLT::vector(16, 8)}, LegalizerInfo::Legal);
setAction({G_ADD, LLT::vector(4, 16)}, LegalizerInfo::Legal);
setAction({G_ADD, LLT::vector(8, 16)}, LegalizerInfo::Legal);
setAction({G_ADD, LLT::vector(2, 32)}, LegalizerInfo::Legal);
setAction({G_ADD, LLT::vector(4, 32)}, LegalizerInfo::Legal);
setLegalizeVectorElementToDifferentSizeStrategy(
    G_ADD, 0, widenToLargerTypesUnsupportedOtherwise);

As currently implemented in this patch, vector types are legalized by
first making the vector element size legal, followed by then making the
number of lanes legal. The strategy to follow in the first step is set
by a call to setLegalizeVectorElementToDifferentSizeStrategy, see
example above. The strategy followed in the second step
"moreToWiderTypesAndLessToWidest" (see patch for its definition),
indicating that vectors are widened to more elements so they map to
natively supported vector widths, or when there isn't a legal wider
vector, split the vector to map it to the widest vector supported.

Therefore, for the above specification, some example legalizations are:

• getAction({G_ADD, LLT::vector(3, 3)}) returns {WidenScalar, LLT::vector(3, 8)}
• getAction({G_ADD, LLT::vector(3, 8)}) then returns {MoreElements, LLT::vector(8, 8)}
• getAction({G_ADD, LLT::vector(20, 8)}) returns {FewerElements, LLT::vector(16, 8)}

2. Key implementation aspects.

How to legalize a specific (operation, type index, size) tuple is
represented by mapping intervals of integers representing a range of
size types to an action to take, e.g.:

setScalarAction({G_ADD, LLT:scalar(1)},
                {{1, WidenScalar},  // bit sizes [ 1, 31[
                 {32, Legal},       // bit sizes [32, 33[
                 {33, WidenScalar}, // bit sizes [33, 64[
                 {64, Legal},       // bit sizes [64, 65[
                 {65, NarrowScalar} // bit sizes [65, +inf[
                });

Please note that most of the code to do the actual lowering of
non-power-of-2 sized types is missing, this is just trying to make it
possible for targets to specify what is legal, and how non-legal types
should be legalized. Probably quite a bit of further work is needed in
the actual legalizing and the other passes in GlobalISel to support
non-power-of-2 sized types.

I hope the documentation in LegalizerInfo.h and the examples provided in the
various {Target}LegalizerInfo.cpp and LegalizerInfoTest.cpp explains well
enough how this is meant to be used.

In the existing targets having some support for GlobalIsel, I tried to not
change the semantics of what is defined in setAction at the moment for ARM,
X86 and AMDGPU.

This drops the need for:

• LLT::{half,double}...Size().

This might make legalization slower than before (I didn't try to measure
it yet), but I'm assuming that by introducing one or a few caches (see
FIXMEs), we can remove most of the overhead. I thought I'd try to get
some feedback on the high-level design before putting too much further
effort in...

[kristof.beyls]

• Rebased to top-of-trunk.
• Correctly store Action info for pointer types for targets with multiple address spaces.
• Added a few basic checks to verify correctness of a targets legalization specification.
• Added one more static function to LegalizerInfo to make specifications shorter and more readable. (UnsupportedButFor).
• Adapted setAction API to be able to specify if a particular setAction should be the first specification on the operation, or if it could be a refinement.
• Introduced a few typedefs to improve readability.
• Made legalization info identical to current ToT for all backends, so that this patch becomes NFCi.

[rengolin]

Hi Kristof,

I haven't seen the patch at all, but what about situations where 64-bit is done with lib calls? For example, ldivmod takes 64-bit arguments and you wouldn't want to narrow them to 32-bits.

If this patch is intended to just simplify the legal vs. others, it shouldn't have a narrow-all that spans to +inf. Makes sense?

cheers,
--renato

[kristof.beyls]

In D30529#698648, @rengolin wrote:

Hi Kristof,

I haven't seen the patch at all, but what about situations where 64-bit is done with lib calls? For example, ldivmod takes 64-bit arguments and you wouldn't want to narrow them to 32-bits.

If this patch is intended to just simplify the legal vs. others, it shouldn't have a narrow-all that spans to +inf. Makes sense?

cheers,
--renato

Hi Renato,

This patch should allow to specify everything you want to do for each individual bitsize, if that's what you want.
I'm not exactly sure what exact actions you're thinking of are needed for the different sizes of div or mod, but for example, you could specify:

setAction({G_REM, LLT:scalar(1)},
          {{1, WidenScalar},  // bit sizes [ 1, 31[
           {32, Lower},       // bit sizes [32, 33[
           {33, NarrowScalar}, // bit sizes [33, 63[
           {64, Libcall}, // bit sizes [64, 65[
           {65, Unsupported} // bit sizes [65, +inf[
          });

I'm assuming the above example wouldn't be what you want to do in detail, but it just shows that for different bit sizes, you can specify to do different things to legalize.

Since the design should allow to specify what to do for all bit sizes, there should be a mapping from the set of natural numbers (all bit sizes) to what action to take.
In this patch, I chose for that mapping to be represented using a simple vector, with the boundary bit sizes where the action changes represented as an element in the array.

As this can get a bit verbose, I've added a few helper/syntactic sugar functions that help to specify typical specifications concisely. I created these functions based on the specifications that already exist in the existing backends that support GlobalISel.
The most-used example in this patch is UnsupportedButFor. An example of how it's used from the AArch64 backend is:

for (unsigned BinOp : {G_SREM, G_UREM})
  setAction({BinOp, Scalar}, UnsupportedButFor({1,8,16,32,64}, Lower));

which without this helper function, would be written as something like:

for (unsigned BinOp : {G_SREM, G_UREM})
  setAction({BinOp, Scalar}, 
        {{1, Lower},  // bit sizes [ 1, 1[
         {2, Unsupported},       // bit sizes [2, 8[
         {8, Lower},  // bit sizes [ 8, 8[
         {9, Unsupported},       // bit sizes [9, 16[
         {16, Lower},  // bit sizes [ 16, 17[
         {17, Unsupported},       // bit sizes [17, 32[
         {32, Lower},  // bit sizes [ 32, 33[
         {33, Unsupported},       // bit sizes [33, 64[
         {64, Lower},  // bit sizes [ 64, 65[
         {65, Unsupported} // bit sizes [65, +inf[
        }

You can find more examples in the changes in this patch in the {Target}LegalarizerInfo.cpp files.
Of course, the whole idea of this patch is to be able to easily specify what to do to legalize ranges of bit sizes, e.g. using "NarrowScalar" or "WidenScalar" on a wide range of bitsizes.
Without this patch, currently every single bitsize has to be explicitly enumerated, which is far from ideal.
There are a few examples of how this is done in the first version of the patch on this review. In the second version, I decided to make the patch NFC, which as a consequence means there aren't many (no?) examples of "NarrowScalar" or "WidenScalar" over a range of bit sizes, as that wasn't easily specified before.
One simple example could be:

for (unsigned BinOp : {G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL}) {
    // These operations naturally get the right answer when used on
    // GPR32, even if the actual type is narrower.
    setAction({BinOp, s1},
      {{1, WidenScalar},
       {32, Legal},
       {33, WidenScalar},
       {64, Legal},
       {65, NarrowScalar}
      });

which specifies the intended action for all bit sizes. Before this patch, you'd have to specify (have a call to setAction) for every single bit size you'd want to support. Apart from wasting a lot of memory in tables, you'd also need to decide what the largest bit size would be you'd like to support, as you wouldn't be able to specify "all bit sizes larger than this should be legalized using this action".

I hope the above makes sense?

Thanks,

Kristof

[rengolin]

In D30529#699110, @kristof.beyls wrote:

setAction({G_REM, LLT:scalar(1)},
          {{1, WidenScalar},  // bit sizes [ 1, 31[
           {32, Lower},       // bit sizes [32, 33[
           {33, NarrowScalar}, // bit sizes [33, 63[
           {64, Libcall}, // bit sizes [64, 65[
           {65, Unsupported} // bit sizes [65, +inf[
          });

I'd expect 33~63 to Widen+LibCall here.

I hope the above makes sense?

It does, but there are two issues here:

1. How would this inter-operate with table-gen?

IIUC, the idea is to move as much as possible to table-gen. Currently (SelDAG), instructions that are described in table-gen are "legal". It would be good to re-use as much as possible of that, to avoid table-gen bloat.

Are we going to ignore that info and re-build a specific lowering database? Or re-use that for the lowering (thus needing merge, see below)? Or is this technique only for when the generic instruction doesn't map to anything in table-gen?

2. Would this allow merging data?

When sub-arch specific decisions are concerned, having a way to override a base default case would reduce the amount of code on both table-gen and c++ parts.

For example, we could have a default catch-all case like {1,widen; 32,legal; 33,unsupp}, and later on, based on sub-arch decisions, increment legality, lib calls, etc.

cheers,
--renato

[kristof.beyls]

I hope the above makes sense?

It does, but there are two issues here:

Those are probably the most interesting questions around this patch that I don't have an answer too, and I hope this review can help with getting closer to an answer.
Thanks for making them explicit here. (Of course there may be other big issues hiding here, but I'm not aware of them at the moment).

The hard part is that I don't think there's a good answer yet indeed on the question on whether it is possible to incrementally specify how to legalize different bitsizes on a specific operation.
A few more thoughts inline below.

1. How would this inter-operate with table-gen?

IIUC, the idea is to move as much as possible to table-gen. Currently (SelDAG), instructions that are described in table-gen are "legal". It would be good to re-use as much as possible of that, to avoid table-gen bloat.

Are we going to ignore that info and re-build a specific lowering database? Or re-use that for the lowering (thus needing merge, see below)? Or is this technique only for when the generic instruction doesn't map to anything in table-gen?

Indeed, it would be best not to ignore that info. Or at least not violate the DRY principle. Or if we did end up violating that principle, in an asserts-build make sure that we'd assert if the different pieces of info would conflict.
That being said, there might be a hint of a solution already in this patch. One of the helper functions to more concisely specify how to legalize all bit sizes in this patch is getWidenToLargerTypesAndNarrowToLargest.
Let me copy paste the documentation I wrote for it here:

/// Helper function for the common case where legalization for a particular
/// operation consists of widening the type to a large legal type, unless
/// there is no such type and then instead it should be narrowed to the
/// largest legal type. E.g.
/// setAction({G_ADD, LLT:scalar(1)},
///           {{1, WidenScalar},  // bit sizes [ 1, 31[
///            {32, Legal},       // bit sizes [32, 33[
///            {33, WidenScalar}, // bit sizes [33, 64[
///            {64, Legal},       // bit sizes [64, 65[
///            {65, NarrowScalar} // bit sizes [65, +inf[
///           });
/// can be shortened to:
/// setAction({G_ADD, LLT:scalar(1)},
///           getWidenToLargerTypesAndNarrowToLargest(
///            {32, Legal}, {64, Legal}));

The info that a G_ADD is legal on 32 and 64-bit types could indeed be retrieved from tablegen.
The fact that WidenScalar is a good way to legalize if there is a wider legal type is, if I'm not mistaken, target-indepedent, so that could be logic in the target-independent part.
I'm not entirely sure on the exact conditions for NarrowScalar to be an appropriate way to legalize adds that are larger than the largest legal size. Maybe it is also fully target-independent.
If it is, than the above setAction could indeed fully be derived from tablegen info and some target-independent logic.
FWIW, the above seems quite similar to what current SelDAG type-legalization does at https://github.com/llvm-mirror/llvm/blob/master/lib/CodeGen/TargetLoweringBase.cpp#L1341 (if I understand that code correctly).

2. Would this allow merging data?

When sub-arch specific decisions are concerned, having a way to override a base default case would reduce the amount of code on both table-gen and c++ parts.

For example, we could have a default catch-all case like {1,widen; 32,legal; 33,unsupp}, and later on, based on sub-arch decisions, increment legality, lib calls, etc.

With the patch as is, you indeed need to re-specify the info for all bit sizes.
It could be that I pushed the current patch way too far in breaking existing APIs and if I turned back the patch to only change the internal representations used in LegalizerInfo.cpp,
this would work. So, the idea being that tablegen info and targets specify for which data types an action can be taken that doesn't require changing bitsize, such as Legal, Lower, Libcall.
And then the target-independent logic can hopefully make decisions on most/all operations on how to adapt types to different bitsizes when that's needed.
I'll look into that.

Thanks for sharing your thoughts!

[dsanders]

I haven't read the actual code yet, but I've got a couple questions and a comment based on the description and the conversation so far.

Another major change is that getAction no longer returns a single action, but
returns a sequence of actions, as legalizing non-power-of-2 types may need
multiple actions. For example: findLegalAction({G_REM, 13}) should return

[(WidenScalar, 32), (Lower, 32)], indicating to first widen the s13
scalar to 32 bits, and to then lower it, assuming the setAction on SREM
was something like:
setAction({G_REM, LLT:scalar(1)},

{{1, WidenScalar},  // bit sizes [ 1, 31[
 {32, Lower},       // bit sizes [32, 33[
 {33, NarrowScalar} // bit sizes [65, +inf[
});

Does findLegalAction() need to return a sequence here? I'm thinking that it could simply be called twice:

iterator I = findLegalAction({G_REM, 13}); // *I == (WidenScalar, 32)
iterator J = findLegalAction({G_REM, 32}); // *J == (Lower, 32), I could also be given as an argument to speed up the search

Also, given that the 2nd argument to setAction() describes all the bit sizes, is the bit-size of the LLT::scalar(1) still required for something?

How would this inter-operate with table-gen?
IIUC, the idea is to move as much as possible to table-gen. Currently (SelDAG), instructions that are described in table-gen are "legal". It would be good to re-use as much as possible of that, to avoid table-gen bloat.

I agree that there's a correlation there but I don't think it's the tablegen definition that specifies that they are legal. In SelectionDAG, it's the calls to setOperationAction() that specify legality and the default is 'Legal'.

Would this allow merging data?
When sub-arch specific decisions are concerned, having a way to override a base default case would reduce the amount of code on both table-gen and c++ parts.
For example, we could have a default catch-all case like {1,widen; 32,legal; 33,unsupp}, and later on, based on sub-arch decisions, increment legality, lib calls, etc.

With the patch as is, you indeed need to re-specify the info for all bit sizes.
It could be that I pushed the current patch way too far in breaking existing APIs and if I turned back the patch to only change the internal representations used in LegalizerInfo.cpp,
this would work. So, the idea being that tablegen info and targets specify for which data types an action can be taken that doesn't require changing bitsize, such as Legal, Lower, Libcall.
And then the target-independent logic can hopefully make decisions on most/all operations on how to adapt types to different bitsizes when that's needed.
I'll look into that.

One way to allow mergable data in your current API is with an 'Inherit' action like so:

setAction({G_ADD, LLT::scalar(1)}, {{1, Inherit}, {33, WidenScalar}, {64, Legal}, {65, NarrowScalar}});

This would keep existing actions for sizes 1-32, and replace the actions for size 33 and up.

One other possibility is to move the specification to tablegen, and have it figure out an array layout that is cheap to configure. For example, it could decide to take

{{1, WidenScalar}, {32, Legal}, {33, NarrowScalar}
{{1, WidenScalar}, {32, Legal}, {33, WidenScalar}, {64, Legal}, {65, NarrowScalar}} // if 64-bit supported

and create a default array like so:

{{1, WidenScalar}, {32, Legal}, {33, NarrowScalar}, {64, NarrowScalar}, {65, NarrowScalar}}

so that when 64-bit support is enabled it can just replace elements 2 and 3 with:

{33, WidenScalar}, {64, Legal}

[kristof.beyls]

In D30529#699569, @dsanders wrote:

I haven't read the actual code yet, but I've got a couple questions and a comment based on the description and the conversation so far.

Thanks for the comments - they're very useful!

Another major change is that getAction no longer returns a single action, but
returns a sequence of actions, as legalizing non-power-of-2 types may need
multiple actions. For example: findLegalAction({G_REM, 13}) should return

[(WidenScalar, 32), (Lower, 32)], indicating to first widen the s13
scalar to 32 bits, and to then lower it, assuming the setAction on SREM
was something like:
setAction({G_REM, LLT:scalar(1)},

{{1, WidenScalar},  // bit sizes [ 1, 31[
 {32, Lower},       // bit sizes [32, 33[
 {33, NarrowScalar} // bit sizes [65, +inf[
});

Does findLegalAction() need to return a sequence here? I'm thinking that it could simply be called twice:

iterator I = findLegalAction({G_REM, 13}); // *I == (WidenScalar, 32)
iterator J = findLegalAction({G_REM, 32}); // *J == (Lower, 32), I could also be given as an argument to speed up the search

I think both options are doable (calling multiple times like your example above, or returning all the legalization steps in on go like the patch currently does).
I don't have a very strong preference on one versus the other - at the moment, just returning the full sequence of legalization steps seemed a little bit conceptually cleaner to me.
I think that the decision on which option to take probably should be done based on which one is the higher-performing one.
My expectation is that the linear or binary search through the vector might be the slowest part, and therefore gathering all legalization steps in one go may be most efficient.
But of course, if you'd keep an iterator and pass it on between different findLegalAction calls, maybe the performance difference wouldn't be big.

I'm also assuming that we'll end up caching the results to findLegalAction queries per function to speed this up, and then the speed difference may be completely irrelevant.

Also, given that the 2nd argument to setAction() describes all the bit sizes, is the bit-size of the LLT::scalar(1) still required for something?

The only relevant part is that it's a LLT::scalar and not an LLT::pointer.
I could get rid of it by having separate setScalarAction/setPointerAction functions. The idea crossed my mind before.
Probably that will make the specifications easier to read, as I agree that the LLT::scalar(1) is a bit confusing.
I'll look into changing that.

Would this allow merging data?
When sub-arch specific decisions are concerned, having a way to override a base default case would reduce the amount of code on both table-gen and c++ parts.
For example, we could have a default catch-all case like {1,widen; 32,legal; 33,unsupp}, and later on, based on sub-arch decisions, increment legality, lib calls, etc.

With the patch as is, you indeed need to re-specify the info for all bit sizes.
It could be that I pushed the current patch way too far in breaking existing APIs and if I turned back the patch to only change the internal representations used in LegalizerInfo.cpp,
this would work. So, the idea being that tablegen info and targets specify for which data types an action can be taken that doesn't require changing bitsize, such as Legal, Lower, Libcall.
And then the target-independent logic can hopefully make decisions on most/all operations on how to adapt types to different bitsizes when that's needed.
I'll look into that.

One way to allow mergable data in your current API is with an 'Inherit' action like so:

setAction({G_ADD, LLT::scalar(1)}, {{1, Inherit}, {33, WidenScalar}, {64, Legal}, {65, NarrowScalar}});

This would keep existing actions for sizes 1-32, and replace the actions for size 33 and up.

That sounds like a promising idea!
It seems to have the nice quality that you could check that "Inherit" covers all but the largest bitsize specified before, so that asserts can protect users of the API from accidentally overwriting earlier specifications.
Or in other words, checking that when using "Inherit", you only extend the specification details, not re-specify earlier specifications. I just think it'd be nice to have those kinds of asserts as on architectures with many different subTargets, it's probably easy to make some mistake somewhere.
My assumption here is that most subTarget extensions will make more bitsizes natively supported/legal, rather than fewer.
This probably needs a bit more experimenting/going through several examples to see how it would play out in practice.

One other possibility is to move the specification to tablegen, and have it figure out an array layout that is cheap to configure. For example, it could decide to take

{{1, WidenScalar}, {32, Legal}, {33, NarrowScalar}
{{1, WidenScalar}, {32, Legal}, {33, WidenScalar}, {64, Legal}, {65, NarrowScalar}} // if 64-bit supported

and create a default array like so:

{{1, WidenScalar}, {32, Legal}, {33, NarrowScalar}, {64, NarrowScalar}, {65, NarrowScalar}}

so that when 64-bit support is enabled it can just replace elements 2 and 3 with:

{33, WidenScalar}, {64, Legal}

Moving this kind of information into tablegen currently seems a bit of overkill to me - but maybe I'm not getting the full reason why it might be beneficial.
As to the idea where you can replace elements in a fixed-size array: my assumption so far is that the creation of these data structures will not be on the critical path, so not worth optimizing for that. But I could be wrong of course.
Unless the technique would have benefits beyond making the creation of the data structures faster?

[kristof.beyls]

• Split LegalizerInfo::setAction into setScalarAction and setPointerAction to avoid having to specify a mostly meaningless LLT as an argument just to indicate whether the type is a scalar or a pointer(with address space).

[kristof.beyls]

• Made the API change to LegalizerInfo::setAction much smaller: the setAction API is largely unchanged now. The only difference is that it no longer allows legalizationActions that change the size to be specified this way.
• Instead, specifying how to legalize when the size of the type legalized needs to change is specified using a SizeChangeStrategy. In follow-up work, I think that these size-changing strategies will turn out to be largely target-independent, and therefore can be shared between all targets, and not need to be respecified for each target separately.
• Split setAction into setScalarAction and setPointerAction to avoid having to specify an LLT just to indicate whether the type is a scalar or a pointer(with address space).
• To keep this patch as NFC as possible, for AArch64, I had to come up with some complicated SizeChangeStrategies. While not pretty, it demonstrates that it is possible to create very custom SizeChangeStrategies. These ugly SizeChangeStrategies are also only expect to be there for a short while, until we make functional-change-changes to allow all non-power-of-two-sized types
• Moved some of the implementation code from LegalizerInfo.h to LegalizerInfo.cpp
• A lot of smaller cleanups.

[kristof.beyls]

2. Would this allow merging data?

When sub-arch specific decisions are concerned, having a way to override a base default case would reduce the amount of code on both table-gen and c++ parts.

For example, we could have a default catch-all case like {1,widen; 32,legal; 33,unsupp}, and later on, based on sub-arch decisions, increment legality, lib calls, etc.

With the patch as is, you indeed need to re-specify the info for all bit sizes.
It could be that I pushed the current patch way too far in breaking existing APIs and if I turned back the patch to only change the internal representations used in LegalizerInfo.cpp,
this would work. So, the idea being that tablegen info and targets specify for which data types an action can be taken that doesn't require changing bitsize, such as Legal, Lower, Libcall.
And then the target-independent logic can hopefully make decisions on most/all operations on how to adapt types to different bitsizes when that's needed.
I'll look into that.

The above is what the latest version of the patch does now.

[t.p.northover]

Hi Kristof,

Thanks for working on this and I'm really sorry it took so long to reply.

I like the basic structure and I think it should be able to represent everything we need. I originally thought that mixing the strategies with setAction calls was clunky, but I assume almost all of that is going to go away once sensible default strategies are in place for all the operations?

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

29–30

This should probably be widen-then-narrow, but I assume it's like this to minimize the functional diff.

46–54

Since v is only used for the push_back maybe just do it directly with ifs:

auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
if (Type.isPointer())
  AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(SizeAction);
else if (Type.isVector())
  ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()].push_back(SizeAction);
else
  ScalarSpecifiedActions.push_back(SizeAction);

91–93

I think the assertion would be reasonable.

130–137

I think this is approximately

VecIdx = std::lower_bound(Vec.begin(), Vec.end()) - Vec.begin();

which has added binary-search goodness.

lib/Target/AArch64/AArch64LegalizerInfo.cpp

107–108

I think this is the same as widen_1_8_16_narrowToLargest isn't it?

[kristof.beyls]

In D30529#820847, @t.p.northover wrote:

Hi Kristof,

Thanks for working on this and I'm really sorry it took so long to reply.

No problem, and thanks very much for the review!

I like the basic structure and I think it should be able to represent everything we need. I originally thought that mixing the strategies with setAction calls was clunky, but I assume almost all of that is going to go away once sensible default strategies are in place for all the operations?

I'm assuming you're talking about how the target defines legality in the TargetLegalizerInfo, right? Yes, I expect most of the strategy specifications to go away there in follow-up patches that don't aim to be as NFC-ish as this one, introducing more default strategies.
I agree that the mixing of setAction and strategies and how they work together isn't fully trivial, but it seems to me that they probably would work well in practice, which is why I also liked this basic structure. So, probably, once this lands, a brief explanation might be needed somewhere on http://llvm.org/docs/GlobalISel.html - enough for target authors to understand how the setAction and SizeChangingStrategies work together.

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

29–30

Hmmm, I can't tell of the top of my head. I'll look into it.

46–54

I think both styles are probably roughly equally readable, but I don't have a preference for one over another, so I'll go for your suggestion, thanks!

91–93

I'm still not entirely sure if it wouldn't be possible to come up with a theoretical example where it still would make sense for 2 consecutive actions to both NeedsLegalizingToDifferentSize().
But indeed, probably best to just assert on that and reintroduce the loops if we have an example demonstrating there really is such a case.

130–137

Yeah, I thought of that while writing this, but also thought that typically the Vec array being searched to be very short, and therefore linear search to potentially be faster than binary search. But, true, that is premature optimization not based on any empirical data, and the std::lower_bound expresses the intended semantics more clearly, so I'll look into going with that.

[qcolombet]

Hi Kristof,

I was under the impression that the patch is good to land, at least as a first step.
What are we missing to push this change?

Cheers,
-Quentin

[kristof.beyls]

In D30529#880298, @qcolombet wrote:

Hi Kristof,

I was under the impression that the patch is good to land, at least as a first step.
What are we missing to push this change?

Cheers,
-Quentin

Hi Quentin,

This should indeed not need much more work to land. I just need to find a bit of time to:

• rebase to ToT.
• address the few minor remarks made by Tim during review, which shouldn't be hard.
• do some basic correctness testing and ideally compile time impact on the test-suite.

I've been hoping to push on with the above for a little while now, but have failed so far with more urgent stuff popping up all the time....
I hope to make progress on this this week....

Thanks,

Kristof

[kristof.beyls]

• Rebased to ToT.
• Addressed all outstanding review comments.
• Used the test-suite on AArch64 to make sure there are no correctness regressions, both in fallback mode and in assert-when-not-legalizable mode.
• Measured compile time impact of this change: it's below the noise level I see on gathering CTMark compile time numbers on my system.

I believe this makes the patch as is ready to be committed.
I noticed that on X86, with this patch, there will be 7 new failures when GlobalISel is enabled in the test-suite, seemingly because the X86 RegisterBankSelector cannot handle G_TRUNC nodes with non-power-of-2-sized types.
As the testing on AArch64 demonstrates that those are handled correctly by the AArch64 RegisterBankSelector, I'm inclined to commit this patch as is to avoid letting this patch increase further in size.

[kristof.beyls]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

29–30

I've made G_ADD widenToLargerTypesAndNarrowToLargest.
There are going to be lots of tiny functional differences in here that will be extremely hard to avoid, so I might as well change this.

91–93

It turns out the loops are actually needed - see new comment I put in in case NarrowScalar to explain why.

130–137

It turned out to be slightly less trivial than VecIdx = std::lower_bound(...); but still concise enough to go for it.

lib/Target/AArch64/AArch64LegalizerInfo.cpp

107–108

Good catch! I removed the function and replaced its uses with wide_1_8_16_narrowToLargest

[aemerson]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

561

Not to block this patch, but std::map seems a little heavy handed for use here, given I think its a BST underneath. I'm assuming DenseMap won't work because of you need to define another tombstone key. Maybe use unordered_map or a simple vector?

[kristof.beyls]

Use unordered_map instead of (ordered) map.

[kristof.beyls]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

561

Thanks Amara - indeed, an ordered map is not needed.
I switched it to unordered_map.
A pre-allocated vector would waste too much space IMHO, and I don't think it's useful to add the complexity of resizing the vector at run-time until we've seen unordered_map actually is too slow in practice.
As you've guessed, I looked into using a DenseMap here before and concluded that it wouldn't work easily.

[kristof.beyls]

• updated to ToT; adapting the G_OR narrowing support added recently by Quentin.
• slightly improve test arm64-fallback.ll by working around not being able to legalize non-power-of-2-sized G_IMPLICIT_DEFs yet.

[t.p.northover]

Thanks Kristof. I think this looks pretty reasonable as a starting point.

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

 #define LLVM_CODEGEN_GLOBALISEL_MACHINELEGALIZER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/Target/TargetOpcodes.h"
 
 #include <cstdint>
 #include <functional>
+#include <map>
 
 namespace llvm {
 class LLVMContext;
 class MachineInstr;
 class MachineIRBuilder;
 class MachineRegisterInfo;
 class Type;
 class VectorType;
enum LegalizeAction : std::uint8_t {
 
     /// Sentinel value for when no action was found in the specified table.
     NotFound,
   };
 
   LegalizerInfo();
   virtual ~LegalizerInfo() = default;
 
-  /// Compute any ancillary tables needed to quickly decide how an operation
-  /// should be handled. This must be called after all "set*Action"methods but
-  /// before any query is made or incorrect results may be returned.
-  void computeTables();
-
-  /// More friendly way to set an action for common types that have an LLT
-  /// representation.
-  void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
-    TablesInitialized = false;
+  static bool NeedsLegalizingToDifferentSize(const LegalizeAction Action) {
+    switch (Action) {
+    case NarrowScalar:
+    case WidenScalar:
+    case FewerElements:
+    case MoreElements:
+    case Unsupported:
+      return true;
+    default:
+      return false;
+    }
+  }
+
+  typedef std::pair<uint16_t, LegalizeAction> SizeAndAction;
+  typedef std::vector<SizeAndAction> SizeAndActionsVec;
+  typedef SmallVector<SizeAndAction, 4> SmallSizeAndActionsVec;
+  typedef std::map<uint16_t, SizeAndActionsVec> ElemSize2LegalizeNumElementsMap;
+  typedef SmallVector<std::pair<LegalizeAction, LLT>, 4> ActionAndTypes;
+  typedef SmallVector<std::tuple<LegalizeAction, unsigned, LLT>, 4>
+      ActionIndexAndTypes;
+
+  /// The SizeAndActionsVec is a representation mapping between all natural
+  /// numbers and an Action. The natural number represents the bit size of
+  /// the InstrAspect. For example, for a target with native support for 32-bit
+  /// and 64-bit additions, you'd express that as:
+  /// setAction({G_ADD, LLT:scalar(1)},
+  ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
+  ///            {32, Legal},       // bit sizes [32, 33[
+  ///            {33, WidenScalar}, // bit sizes [33, 64[
+  ///            {64, Legal},       // bit sizes [64, 65[
+  ///            {65, NarrowScalar} // bit sizes [65, +inf[
+  ///           });
+  /// It may be that only 64-bit pointers are supported on your target:
+  /// setAction({G_GEP, LLT:pointer(1)},
+  ///           {{1, Unsupported},  // bit sizes [ 1, 63[
+  ///            {64, Legal},       // bit sizes [64, 65[
+  ///            {65, Unsupported}, // bit sizes [65, +inf[
+  ///           });
+  /// FIXME: should we create a new ADT for mapping an integer range to an
+  /// Action, so the above could be written in a way that's easier to
+  /// comprehend without documentation?
+  void setAction(const InstrAspect &Aspect,
+                 const SizeAndActionsVec &SizeAndActions,
+                 const bool ResetAllowed=false) {
+    // sizeInBits is meaningless on the Aspect, just make sure it's 1 for
+    // consistency here.
+    assert(Aspect.Type.isPointer() ||
+           (Aspect.Type.isScalar() && Aspect.Type.getSizeInBits() == 1));
     unsigned Opcode = Aspect.Opcode - FirstOp;
-    if (Actions[Opcode].size() <= Aspect.Idx)
-      Actions[Opcode].resize(Aspect.Idx + 1);
-    Actions[Aspect.Opcode - FirstOp][Aspect.Idx][Aspect.Type] = Action;
+    if (Aspect.Type.isPointer() &&
+        AddrSpace2PointerActions[Opcode].find(Aspect.Type.getAddressSpace()) ==
+            AddrSpace2PointerActions[Opcode].end())
+      AddrSpace2PointerActions[Opcode][Aspect.Type.getAddressSpace()] = {{}};
+    SmallVector<SizeAndActionsVec, 1> &Actions =
+        Aspect.Type.isPointer()
+            ? AddrSpace2PointerActions[Opcode]
+                  .find(Aspect.Type.getAddressSpace())
+                  ->second
+            : ScalarActions[Opcode];
+    if (Actions.size() <= Aspect.Idx)
+      Actions.resize(Aspect.Idx + 1);
+#ifndef NDEBUG
+    // FIXME: ResetAllowed isn't used in release builds, so that probably
+    // will generate a warning.
+    // No information must have been set for this InstrAspect before, as
+    // it otherwise would be overwritten silently, which is probably not
+    // the intent of the user.
+    if (!ResetAllowed)
+      assert(Actions[Aspect.Idx].size() == 0);
+    // Data structure invariant: The first bit size must be size 1.
+    assert(SizeAndActions.size() >= 1);
+    assert(SizeAndActions[0].first == 1);
+    // The sizes should be in increasing order
+    int prev_size = -1;
+    for(auto SizeAndAction: SizeAndActions) {
+      assert(SizeAndAction.first > prev_size);
+      prev_size = SizeAndAction.first;
+    }
+    // - for every Widen action, there should be a larger bitsize that
+    //   can be legalized towards (e.g. Legal, Lower, Libcall or Custom
+    //   action).
+    // - for every Narrow action, there should be a smaller bitsize that
+    //   can be legalized towards.
+    int SmallestNarrowIdx = -1;
+    int LargestWidenIdx = -1;
+    int SmallestLegalizableToSameSizeIdx = -1;
+    int LargestLegalizableToSameSizeIdx = -1;
+    for(size_t i=0; i<SizeAndActions.size(); ++i) {
+      switch (SizeAndActions[i].second) {
+        case FewerElements:
+        case NarrowScalar:
+          if (SmallestNarrowIdx == -1)
+            SmallestNarrowIdx = i;
+          break;
+        case WidenScalar:
+        case MoreElements:
+          LargestWidenIdx = i;
+          break;
+        case Unsupported:
+          break;
+        default:
+          if (SmallestLegalizableToSameSizeIdx == -1)
+            SmallestLegalizableToSameSizeIdx = i;
+          LargestLegalizableToSameSizeIdx = i;
+      }
+    }
+    if (SmallestNarrowIdx != -1) {
+      assert(SmallestLegalizableToSameSizeIdx != -1);
+      assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
+    }
+    if (LargestWidenIdx != -1)
+      assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
+#endif
+    Actions[Aspect.Idx] = SizeAndActions;
+  }
+
+  static SizeAndActionsVec
+  UnsupportedButFor(const std::vector<unsigned> &Supported,
+                    LegalizeAction A) {
+    SizeAndActionsVec result;
+    for (size_t i = 0; i < Supported.size(); ++i) {
+      if (i == 0 && Supported[i] != 1)
+        result.push_back({1, Unsupported});
+      result.push_back({Supported[i], A});
+      if (i + 1 < Supported.size() && Supported[i + 1] != Supported[i] + 1)
+        result.push_back({Supported[i] + 1, A});
+    }
+    return result;
+  }
+
+  /// Helper function for the common case where legalization for a particular
+  /// operation consists of widening the type to a large legal type, unless
+  /// there is no such type and then instead it should be narrowed to the
+  /// largest legal type. E.g.
+  /// setAction({G_ADD, LLT:scalar(1)},
+  ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
+  ///            {32, Legal},       // bit sizes [32, 33[
+  ///            {33, WidenScalar}, // bit sizes [33, 64[
+  ///            {64, Legal},       // bit sizes [64, 65[
+  ///            {65, NarrowScalar} // bit sizes [65, +inf[
+  ///           });
+  /// can be shortened to:
+  /// setAction({G_ADD, LLT:scalar(1)},
+  ///           getWidenToLargerTypesAndNarrowToLargest(
+  ///            {32, Legal}, {64, Legal}));
+  static SizeAndActionsVec
+  getWidenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
+    return getIncreaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
+                                                        NarrowScalar);
+  }
+
+  /// Helper function for the common case where legalization for a particular
+  /// vector operation consists of having more elements in the vector, to a
+  /// type that is legal. Unless / there is no such type and then instead it
+  /// should be legalized towards the widest vector that's still legal. E.g.
+  ///           {8,{
+  ///            {1, MoreElements}, // [  <1x8>,  <8x8> [ :increase to <8x8>
+  ///            {8, Legal},        // [  <8x8>,  <9x8> [ :is Legal
+  ///            {9, MoreElements}, // [  <9x8>, <16x8> [ :increase to <16x8>
+  ///            {16, Legal},       // [ <16x8>, <16x8> [ :is Legal
+  ///            {17, FewerElements}// [ <17x8>, <infx8>[ :decrease to <16x8>
+  ///           }}
+  /// can be shortened to:
+  ///           {8,
+  ///            getMoreToWiderTypesAndLessToWidest({8, Legal}, {16, Legal})
+  ///           }
+  static SizeAndActionsVec
+  getMoreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
+    return getIncreaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
+                                                        FewerElements);
+  }
+
+  static SizeAndActionsVec
+  getIncreaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v,
+                                               LegalizeAction IncreaseAction,
+                                               LegalizeAction DecreaseAction) {
+    SizeAndActionsVec result;
+    assert(v.size() >= 1);
+    if (v[0].first != 1)
+      result.push_back({1, IncreaseAction});
+    for (unsigned i = 0; i < v.size(); ++i) {
+      assert(!NeedsLegalizingToDifferentSize(v[i].second));
+      result.push_back(v[i]);
+      if (i + 1 == v.size())
+        result.push_back({v[i].first + 1, DecreaseAction});
+      else
+        result.push_back({v[i].first + 1, IncreaseAction});
+    }
+    return result;
   }
 
   /// If an operation on a given vector type (say <M x iN>) isn't explicitly
   /// specified, we proceed in 2 stages. First we legalize the underlying scalar
   /// (so that there's at least one legal vector with that scalar), then we
   /// adjust the number of elements in the vector so that it is legal. The
   /// desired action in the first step is controlled by this function.
-  void setScalarInVectorAction(unsigned Opcode, LLT ScalarTy,
-                               LegalizeAction Action) {
-    assert(!ScalarTy.isVector());
-    ScalarInVectorActions[std::make_pair(Opcode, ScalarTy)] = Action;
+  void setScalarInVectorAction(unsigned Opcode,
+                               const SizeAndActionsVec &SizeAndActions) {
+    unsigned Index = Opcode - FirstOp;
+    ScalarInVectorActions[Index] = SizeAndActions;
+    // FIXME: do a few basic correctness checks
   }
 
+  /// See also setScalarInVectorAction.
+  /// This function let's you specify the number of elements in a vector that
+  /// are legal for various element sizes.
+  /// E.g.
+  ///  setScalarInVectorAction(
+  ///    G_ADD, getWidenToLargerTypesAndNarrowToLargest(
+  ///               {{8, Legal}, {16, Legal}, {32, Legal}, {64, Legal}}));
+  ///  setLegalNrVectorLanes(BinOp,
+  ///                    {
+  ///                        {8, {4, 8, 16}}, // 4x8, 8x8 and 16x8 are legal
+  ///                        {16, {2, 4, 8}}, // 2x16, 4x16 and 8x16 are legal
+  ///                        {32, {1, 2, 4}}, // 1x32, 2x32 and 4x32 are legal
+  ///                        {64, {1, 2}},    // 1x64 and 2x642 are legal
+  ///                    });
+  void setLegalNrVectorLanes(
+      unsigned Opcode,
+      const std::vector<std::pair<uint16_t, std::vector<unsigned>>>
+          &ElemSize2LegalNumElements) {
+    // FIXME: do a few basic correctness checks
+    ElemSize2LegalizeNumElementsMap M;
+    for (auto ElemSizeAndLegalVectorWidths : ElemSize2LegalNumElements) {
+      const uint16_t ElemSize = ElemSizeAndLegalVectorWidths.first;
+      const auto &LegalVectorWidths = ElemSizeAndLegalVectorWidths.second;
+      SizeAndActionsVec V;
+      for (uint16_t Size : LegalVectorWidths)
+        V.push_back({Size, Legal});
+      M[ElemSize] = getMoreToWiderTypesAndLessToWidest(V);
+    }
+    unsigned Index = Opcode - FirstOp;
+    VectorNumElementsActions[Index] = M;
+  }
 
   /// Determine what action should be taken to legalize the given generic
-  /// instruction opcode, type-index and type. Requires computeTables to have
-  /// been called.
+  /// instruction opcode, type-index and type.
   ///
   /// \returns a pair consisting of the kind of legalization that should be
   /// performed and the destination type.
-  std::pair<LegalizeAction, LLT> getAction(const InstrAspect &Aspect) const;
+  ActionAndTypes getAction(const InstrAspect &Aspect) const;
 
   /// Determine what action should be taken to legalize the given generic
   /// instruction.
   ///
   /// \returns a tuple consisting of the LegalizeAction that should be
   /// performed, the type-index it should be performed on and the destination
   /// type.
-  std::tuple<LegalizeAction, unsigned, LLT>
-  getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
+  ActionIndexAndTypes getAction(const MachineInstr &MI,
+                                const MachineRegisterInfo &MRI) const;
 
-  /// Iterate the given function (typically something like doubling the width)
-  /// on Ty until we find a legal type for this operation.
-  LLT findLegalType(const InstrAspect &Aspect,
-                    function_ref<LLT(LLT)> NextType) const {
-    LegalizeAction Action;
-    const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx];
-    LLT Ty = Aspect.Type;
-    do {
-      Ty = NextType(Ty);
-      auto ActionIt = Map.find(Ty);
-      if (ActionIt == Map.end())
-        Action = DefaultActions.find(Aspect.Opcode)->second;
+  static SmallSizeAndActionsVec findActionInSAAV(const SizeAndActionsVec &Vec,
+                                                 const uint32_t Size) {
+    assert(Size >= 1);
+    // Find the first element in Vec that has a bitsize equal to or smaller
+    // than the requested bit size. We can do that using reverse iterators
+    int VecIdx = -1;
+    for (int i = Vec.size() - 1; i >= 0; --i) {
+      const uint32_t BitSize = Vec[i].first;
+      if (BitSize <= Size) {
+        VecIdx = i;
+        break;
+      }
+    }
+    assert(VecIdx != -1);
+    LegalizeAction Action = Vec[VecIdx].second;
+    switch (Action) {
+    case Legal:
+    case Lower:
+    case Libcall:
+    case Custom:
+      return {{Size, Action}};
+    case NarrowScalar:
+    case FewerElements:
+      for (int i = VecIdx - 1; i >= 0; --i)
+        if (!NeedsLegalizingToDifferentSize(Vec[i].second)) {
+          if (Vec[i].second == Legal)
+            return {{Vec[i].first, Action}};
           else
-        Action = ActionIt->second;
-    } while(Action != Legal);
-    return Ty;
+            return {{Vec[i].first, Action}, {Vec[i].first, Vec[i].second}};
+        }
+      llvm_unreachable("");
+    case WidenScalar:
+    case MoreElements:
+      for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
+        if (!NeedsLegalizingToDifferentSize(Vec[i].second)) {
+          if (Vec[i].second == Legal)
+            return {{Vec[i].first, Action}};
+          else
+            return {{Vec[i].first, Action}, {Vec[i].first, Vec[i].second}};
+        }
+      llvm_unreachable("");
+    case Unsupported:
+      return {{Size, Unsupported}};
+    case NotFound:
+      llvm_unreachable("NotFound");
+    }
   }
 
-  /// Find what type it's actually OK to perform the given operation on, given
-  /// the general approach we've decided to take.
-  LLT findLegalType(const InstrAspect &Aspect, LegalizeAction Action) const;
-
-  std::pair<LegalizeAction, LLT> findLegalAction(const InstrAspect &Aspect,
-                                                 LegalizeAction Action) const {
-    return std::make_pair(Action, findLegalType(Aspect, Action));
+  /// Returns the sequence of actions the target requested to legalize
+  /// the scalar or pointer type.
+  /// E.g. findLegalAction({G_REM, 13}) should return
+  /// [(WidenScalar, 32), (Lower, 32)], indicating to first widen the s13
+  /// scalar to 32 bits, and to then lower it, assuming the setAction on SREM
+  /// was something like:
+  /// setAction({G_REM, LLT:scalar(1)},
+  ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
+  ///            {32, Lower},       // bit sizes [32, 33[
+  ///            {33, NarrowScalar} // bit sizes [65, +inf[
+  ///           });
+  ActionAndTypes findScalarLegalAction(const InstrAspect &Aspect) const {
+    assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
+    if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
+      return {{NotFound, LLT()}};
+    unsigned Opcode = Aspect.Opcode - FirstOp;
+    if (Aspect.Type.isPointer() &&
+        AddrSpace2PointerActions[Opcode].find(Aspect.Type.getAddressSpace()) ==
+            AddrSpace2PointerActions[Opcode].end()) {
+      return {{NotFound, LLT()}};
+    }
+    const SmallVector<SizeAndActionsVec, 1> &Actions =
+        Aspect.Type.isPointer()
+            ? AddrSpace2PointerActions[Opcode]
+                  .find(Aspect.Type.getAddressSpace())
+                  ->second
+            : ScalarActions[Opcode];
+    if (Aspect.Idx >= Actions.size())
+      return {{NotFound, LLT()}};
+    const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
+    // FIXME: speed up this search, e.g. by using a results cache for repeated
+    // queries?
+
+    ActionAndTypes result;
+    for (auto SizeAndAction :
+         findActionInSAAV(Vec, Aspect.Type.getSizeInBits())) {
+      result.push_back({SizeAndAction.second,
+                        Aspect.Type.isScalar()
+                            ? LLT::scalar(SizeAndAction.first)
+                            : LLT::pointer(Aspect.Type.getAddressSpace(),
+                                           SizeAndAction.first)});
+    }
+    return result;
   }
 
-  /// Find the specified \p Aspect in the primary (explicitly set) Actions
-  /// table. Returns either the action the target requested or NotFound if there
-  /// was no setAction call.
-  LegalizeAction findInActions(const InstrAspect &Aspect) const {
+  /// Returns the sequence of actions the target requested to legalize the
+  /// vector type.
+  ActionAndTypes findVectorLegalAction(const InstrAspect &Aspect) const {
+    assert(Aspect.Type.isVector());
+    // First legalize the vector element size, then legalize the number of
+    // lanes in the vector.
+    assert(Aspect.Type.isVector());
     if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
-      return NotFound;
-    if (Aspect.Idx >= Actions[Aspect.Opcode - FirstOp].size())
-      return NotFound;
-    const TypeMap &Map = Actions[Aspect.Opcode - FirstOp][Aspect.Idx];
-    auto ActionIt =  Map.find(Aspect.Type);
-    if (ActionIt == Map.end())
-      return NotFound;
+      return {{NotFound, Aspect.Type}};
+    if (Aspect.Idx >= ScalarInVectorActions[Aspect.Opcode - FirstOp].size())
+      return {{NotFound, Aspect.Type}};
+    const SizeAndActionsVec &ElemSizeVec =
+        ScalarInVectorActions[Aspect.Opcode - FirstOp];
+
+    ActionAndTypes result;
+    LLT IntermediateType;
+    for (auto &SizeAndAction :
+         findActionInSAAV(ElemSizeVec, Aspect.Type.getScalarSizeInBits())) {
+      IntermediateType =
+          LLT::vector(Aspect.Type.getNumElements(), SizeAndAction.first);
+      // No need to push in an "already-legal" action here, as that will be
+      // pushed in by the number-of-elements legalization below.
+      if (SizeAndAction.second == Legal)
+        continue;
+      result.push_back({SizeAndAction.second, IntermediateType});
+      if (SizeAndAction.second == NotFound ||
+          SizeAndAction.second == Unsupported)
+        return result;
+    }
 
-    return ActionIt->second;
+    ElemSize2LegalizeNumElementsMap::const_iterator i =
+        VectorNumElementsActions[Aspect.Opcode - FirstOp].find(
+            IntermediateType.getScalarSizeInBits());
+    if (i == VectorNumElementsActions[Aspect.Opcode - FirstOp].end()) {
+      return {{NotFound, IntermediateType}};
+    }
+    const SizeAndActionsVec &NumElementsVec = (*i).second;
+    for (auto &SizeAndAction :
+         findActionInSAAV(NumElementsVec, IntermediateType.getNumElements())) {
+      // No need to push in an "already-legal" action here, if there was
+      // already another action recorded.
+      if (SizeAndAction.second == Legal && result.size() != 0)
+        continue;
+      result.push_back({SizeAndAction.second,
+                        LLT::vector(SizeAndAction.first,
+                                    IntermediateType.getScalarSizeInBits())});
+    }
+
+    return result;
   }
 
   bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 
-  virtual bool legalizeCustom(MachineInstr &MI,
-                              MachineRegisterInfo &MRI,
+  virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
                               MachineIRBuilder &MIRBuilder) const;
 
 private:
   static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
   static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
 
-  typedef DenseMap<LLT, LegalizeAction> TypeMap;
-  typedef DenseMap<std::pair<unsigned, LLT>, LegalizeAction> SIVActionMap;
-
-  SmallVector<TypeMap, 1> Actions[LastOp - FirstOp + 1];
-  SIVActionMap ScalarInVectorActions;
-  DenseMap<std::pair<unsigned, LLT>, uint16_t> MaxLegalVectorElts;
-  DenseMap<unsigned, LegalizeAction> DefaultActions;
-
-  bool TablesInitialized;
+  SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
+  std::map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
+      AddrSpace2PointerActions[LastOp - FirstOp + 1];
+  SizeAndActionsVec ScalarInVectorActions[LastOp - FirstOp + 1];
+  ElemSize2LegalizeNumElementsMap
+      VectorNumElementsActions[LastOp - FirstOp + 1];
 };
 
-
 } // End namespace llvm.
 
 #endif

include/llvm/CodeGen/LowLevelType.h

 #define LLVM_CODEGEN_LOWLEVELTYPE_H
 
 #include "llvm/Support/LowLevelTypeImpl.h"
 
 namespace llvm {
 
 class DataLayout;
 class Type;
-
 /// Construct a low-level type based on an LLVM type.
 LLT getLLTForType(Type &Ty, const DataLayout &DL);
 
 }
 
 #endif // LLVM_CODEGEN_LOWLEVELTYPE_H

include/llvm/Support/LowLevelTypeImpl.h

public:
   }
 
   /// Returns the vector's element type. Only valid for vector types.
   LLT getElementType() const {
     assert(isVector() && "cannot get element type of scalar/aggregate");
     return scalar(SizeInBits);
   }
 
-  /// Get a low-level type with half the size of the original, by halving the
-  /// size of the scalar type involved. For example `s32` will become `s16`,
-  /// `<2 x s32>` will become `<2 x s16>`.
-  LLT halfScalarSize() const {
-    assert(!isPointer() && getScalarSizeInBits() > 1 &&
-           getScalarSizeInBits() % 2 == 0 && "cannot half size of this type");
-    return LLT{Kind, ElementsOrAddrSpace, SizeInBits / 2};
-  }
-
-  /// Get a low-level type with twice the size of the original, by doubling the
-  /// size of the scalar type involved. For example `s32` will become `s64`,
-  /// `<2 x s32>` will become `<2 x s64>`.
-  LLT doubleScalarSize() const {
-    assert(!isPointer() && "cannot change size of this type");
-    return LLT{Kind, ElementsOrAddrSpace, SizeInBits * 2};
-  }
-
-  /// Get a low-level type with half the size of the original, by halving the
-  /// number of vector elements of the scalar type involved. The source must be
-  /// a vector type with an even number of elements. For example `<4 x s32>`
-  /// will become `<2 x s32>`, `<2 x s32>` will become `s32`.
-  LLT halfElements() const {
-    assert(isVector() && ElementsOrAddrSpace % 2 == 0 &&
-           "cannot half odd vector");
-    if (ElementsOrAddrSpace == 2)
-      return scalar(SizeInBits);
-
-    return LLT{Vector, static_cast<uint16_t>(ElementsOrAddrSpace / 2),
-               SizeInBits};
-  }
-
-  /// Get a low-level type with twice the size of the original, by doubling the
-  /// number of vector elements of the scalar type involved. The source must be
-  /// a vector type. For example `<2 x s32>` will become `<4 x s32>`. Doubling
-  /// the number of elements in sN produces <2 x sN>.
-  LLT doubleElements() const {
-    assert(!isPointer() && "cannot double elements in pointer");
-    return LLT{Vector, static_cast<uint16_t>(ElementsOrAddrSpace * 2),
-               SizeInBits};
-  }
-
   void print(raw_ostream &OS) const;
 
   bool operator==(const LLT &RHS) const {
     return Kind == RHS.Kind && SizeInBits == RHS.SizeInBits &&
            ElementsOrAddrSpace == RHS.ElementsOrAddrSpace;
   }
 
   bool operator!=(const LLT &RHS) const { return !(*this == RHS); }

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

 LegalizerHelper::LegalizerHelper(MachineFunction &MF)
   : MRI(MF.getRegInfo()) {
   MIRBuilder.setMF(MF);
 }
 
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstrStep(MachineInstr &MI,
                                    const LegalizerInfo &LegalizerInfo) {
-  auto Action = LegalizerInfo.getAction(MI, MRI);
+  const auto Actions = LegalizerInfo.getAction(MI, MRI);
+  LegalizeResult result;
+  bool AllLegal = true;
+  for (unsigned i = 0; i < Actions.size(); ++i) {
+    const auto Action = Actions[i];
+    if (std::get<0>(Action) != LegalizerInfo::Legal)
+      AllLegal = false;
     switch (std::get<0>(Action)) {
     case LegalizerInfo::Legal:
-    return AlreadyLegal;
+      result = AlreadyLegal;
+      break;
     case LegalizerInfo::Libcall:
-    return libcall(MI);
+      result = libcall(MI);
+      break;
     case LegalizerInfo::NarrowScalar:
-    return narrowScalar(MI, std::get<1>(Action), std::get<2>(Action));
+      result = narrowScalar(MI, std::get<1>(Action), std::get<2>(Action));
+      break;
     case LegalizerInfo::WidenScalar:
-    return widenScalar(MI, std::get<1>(Action), std::get<2>(Action));
+      result = widenScalar(MI, std::get<1>(Action), std::get<2>(Action));
+      break;
     case LegalizerInfo::Lower:
-    return lower(MI, std::get<1>(Action), std::get<2>(Action));
+      result = lower(MI, std::get<1>(Action), std::get<2>(Action));
+      break;
     case LegalizerInfo::FewerElements:
-    return fewerElementsVector(MI, std::get<1>(Action), std::get<2>(Action));
+      result =
+          fewerElementsVector(MI, std::get<1>(Action), std::get<2>(Action));
+      break;
     case LegalizerInfo::Custom:
-    return LegalizerInfo.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized
-                                                             : UnableToLegalize;
+      result = LegalizerInfo.legalizeCustom(MI, MRI, MIRBuilder)
+                   ? Legalized
+      break;
     default:
+      result = UnableToLegalize;
+      break;
+    }
+    if (result == UnableToLegalize)
       return UnableToLegalize;
   }
+  return AllLegal ? AlreadyLegal : Legalized;
 }
 
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstr(MachineInstr &MI,
                                const LegalizerInfo &LegalizerInfo) {
   SmallVector<MachineInstr *, 4> WorkList;
   MIRBuilder.recordInsertions(
       [&](MachineInstr *MI) { WorkList.push_back(MI); });

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

 
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Target/TargetOpcodes.h"
 using namespace llvm;
 
-LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
-  // FIXME: these two can be legalized to the fundamental load/store Jakob
-  // proposed. Once loads & stores are supported.
-  DefaultActions[TargetOpcode::G_ANYEXT] = Legal;
-  DefaultActions[TargetOpcode::G_TRUNC] = Legal;
-
-  DefaultActions[TargetOpcode::G_INTRINSIC] = Legal;
-  DefaultActions[TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS] = Legal;
-
-  DefaultActions[TargetOpcode::G_ADD] = NarrowScalar;
-  DefaultActions[TargetOpcode::G_LOAD] = NarrowScalar;
-  DefaultActions[TargetOpcode::G_STORE] = NarrowScalar;
-
-  DefaultActions[TargetOpcode::G_BRCOND] = WidenScalar;
-  DefaultActions[TargetOpcode::G_INSERT] = NarrowScalar;
-  DefaultActions[TargetOpcode::G_FNEG] = Lower;
-}
-
-void LegalizerInfo::computeTables() {
-  for (unsigned Opcode = 0; Opcode <= LastOp - FirstOp; ++Opcode) {
-    for (unsigned Idx = 0; Idx != Actions[Opcode].size(); ++Idx) {
-      for (auto &Action : Actions[Opcode][Idx]) {
-        LLT Ty = Action.first;
-        if (!Ty.isVector())
-          continue;
-
-        auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
-                                                        Ty.getElementType())];
-        Entry = std::max(Entry, Ty.getNumElements());
-      }
-    }
-  }
-
-  TablesInitialized = true;
-}
+LegalizerInfo::LegalizerInfo() {}
 
 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
 // probably going to need specialized lookup structures for various types before
 // we have any hope of doing well with something like <13 x i3>. Even the common
 // cases should do better than what we have now.
-std::pair<LegalizerInfo::LegalizeAction, LLT>
+LegalizerInfo::ActionAndTypes
 LegalizerInfo::getAction(const InstrAspect &Aspect) const {
-  assert(TablesInitialized && "backend forgot to call computeTables");
   // These *have* to be implemented for now, they're the fundamental basis of
   // how everything else is transformed.
 
-  // Nothing is going to go well with types that aren't a power of 2 yet, so
-  // don't even try because we might make things worse.
-  if (!isPowerOf2_64(Aspect.Type.getSizeInBits()))
-      return std::make_pair(Unsupported, LLT());
-
   // FIXME: the long-term plan calls for expansion in terms of load/store (if
   // they're not legal).
   if (Aspect.Opcode == TargetOpcode::G_SEQUENCE ||
       Aspect.Opcode == TargetOpcode::G_EXTRACT ||
       Aspect.Opcode == TargetOpcode::G_MERGE_VALUES ||
       Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES)
-    return std::make_pair(Legal, Aspect.Type);
+    return {std::make_pair(Legal, Aspect.Type)};
 
-  LegalizeAction Action = findInActions(Aspect);
-  if (Action != NotFound)
-    return findLegalAction(Aspect, Action);
-
-  unsigned Opcode = Aspect.Opcode;
-  LLT Ty = Aspect.Type;
-  if (!Ty.isVector()) {
-    auto DefaultAction = DefaultActions.find(Aspect.Opcode);
-    if (DefaultAction != DefaultActions.end() && DefaultAction->second == Legal)
-      return std::make_pair(Legal, Ty);
-
-    if (DefaultAction != DefaultActions.end() && DefaultAction->second == Lower)
-      return std::make_pair(Lower, Ty);
-
-    if (DefaultAction == DefaultActions.end() ||
-        DefaultAction->second != NarrowScalar)
-      return std::make_pair(Unsupported, LLT());
-    return findLegalAction(Aspect, NarrowScalar);
-  }
+  if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
+    return findScalarLegalAction(Aspect);
+  if (Aspect.Type.isVector())
+    return findVectorLegalAction(Aspect);
+  return {};
 
-  LLT EltTy = Ty.getElementType();
-  int NumElts = Ty.getNumElements();
-
-  auto ScalarAction = ScalarInVectorActions.find(std::make_pair(Opcode, EltTy));
-  if (ScalarAction != ScalarInVectorActions.end() &&
-      ScalarAction->second != Legal)
-    return findLegalAction(Aspect, ScalarAction->second);
-
-  // The element type is legal in principle, but the number of elements is
-  // wrong.
-  auto MaxLegalElts = MaxLegalVectorElts.lookup(std::make_pair(Opcode, EltTy));
-  if (MaxLegalElts > NumElts)
-    return findLegalAction(Aspect, MoreElements);
-
-  if (MaxLegalElts == 0) {
-    // Scalarize if there's no legal vector type, which is just a special case
-    // of FewerElements.
-    return std::make_pair(FewerElements, EltTy);
-  }
-
-  return findLegalAction(Aspect, FewerElements);
-}
-
-std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
+LegalizerInfo::ActionIndexAndTypes
 LegalizerInfo::getAction(const MachineInstr &MI,
                          const MachineRegisterInfo &MRI) const {
+  ActionIndexAndTypes result;
   SmallBitVector SeenTypes(8);
   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
+  // FIXME: probably we'll need to cache the results here somehow?
   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
     if (!OpInfo[i].isGenericType())
       continue;
 
-    // We don't want to repeatedly check the same operand index, that
-    // could get expensive.
+    // We must only record actions once for each TypeIdx; otherwise we'd
+    // try to legalize operands multiple times down the line.
     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
     if (SeenTypes[TypeIdx])
       continue;
 
     SeenTypes.set(TypeIdx);
 
     LLT Ty = MRI.getType(MI.getOperand(i).getReg());
-    auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
-    if (Action.first != Legal)
-      return std::make_tuple(Action.first, TypeIdx, Action.second);
+    auto Actions = getAction({MI.getOpcode(), TypeIdx, Ty});
+    for (auto &Action : Actions)
+      result.push_back(std::make_tuple(Action.first, TypeIdx, Action.second));
   }
-  return std::make_tuple(Legal, 0, LLT{});
+  return result;
 }
 
 bool LegalizerInfo::isLegal(const MachineInstr &MI,
                             const MachineRegisterInfo &MRI) const {
-  return std::get<0>(getAction(MI, MRI)) == Legal;
-}
-
-LLT LegalizerInfo::findLegalType(const InstrAspect &Aspect,
-                                 LegalizeAction Action) const {
-  switch(Action) {
-  default:
-    llvm_unreachable("Cannot find legal type");
-  case Legal:
-  case Lower:
-  case Libcall:
-  case Custom:
-    return Aspect.Type;
-  case NarrowScalar: {
-    return findLegalType(Aspect,
-                         [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
-  }
-  case WidenScalar: {
-    return findLegalType(Aspect, [&](LLT Ty) -> LLT {
-      return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
-    });
-  }
-  case FewerElements: {
-    return findLegalType(Aspect,
-                         [&](LLT Ty) -> LLT { return Ty.halfElements(); });
-  }
-  case MoreElements: {
-    return findLegalType(Aspect,
-                         [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
-  }
-  }
+  const ActionIndexAndTypes Actions = getAction(MI, MRI);
+  for (auto Action : Actions)
+    if (std::get<0>(Action) != Legal)
+      return false;
+  return true;
 }
 
-bool LegalizerInfo::legalizeCustom(MachineInstr &MI,
-                                   MachineRegisterInfo &MRI,
+bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
                                    MachineIRBuilder &MIRBuilder) const {
   return false;
 }

lib/Target/AArch64/AArch64LegalizerInfo.cpp

-//===- AArch64LegalizerInfo.cpp ----------------------------------*- C++ -*-==//
+
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file

 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
 AArch64LegalizerInfo::AArch64LegalizerInfo() {
   using namespace TargetOpcode;
   const LLT p0 = LLT::pointer(0, 64);
-  const LLT s1 = LLT::scalar(1);
-  const LLT s8 = LLT::scalar(8);
-  const LLT s16 = LLT::scalar(16);
-  const LLT s32 = LLT::scalar(32);
-  const LLT s64 = LLT::scalar(64);
-  const LLT v2s32 = LLT::vector(2, 32);
-  const LLT v4s32 = LLT::vector(4, 32);
-  const LLT v2s64 = LLT::vector(2, 64);
+  const LLT Scalar = LLT::scalar(1);
+
+  const SizeAndActionsVec Only1IsLegal = UnsupportedButFor({1}, Legal);
+  const SizeAndActionsVec Only32IsLegal = UnsupportedButFor({32}, Legal);
+  const SizeAndActionsVec Only64IsLegal = UnsupportedButFor({64}, Legal);
+  const SizeAndActionsVec Only32Or64IsLegal =
+      UnsupportedButFor({32, 64}, Legal);
+  const SizeAndActionsVec Only32Or64Lower = UnsupportedButFor({32, 64}, Lower);
+  const SizeAndActionsVec Only16Or32IsLegal =
+      UnsupportedButFor({16, 32}, Legal);
+  const SizeAndActionsVec Only1Or8Or16Or32IsLegal =
+      UnsupportedButFor({1, 8, 16, 32}, Legal);
+  const SizeAndActionsVec Only1Or8Or16Or32Or64IsLegal =
+      UnsupportedButFor({1, 8, 16, 34, 64}, Legal);
+  const SizeAndActionsVec Only8Or16Or32Or64IsLegal =
+      UnsupportedButFor({8, 16, 32, 64}, Legal);
+
+  const SizeAndActionsVec p0Legality = {
+      {1, Unsupported}, {64, Legal}, {65, Unsupported}};
+  const SizeAndActionsVec Widen_1_8_16_Legal_32_64 =
+  {{1, WidenScalar}, {2, Unsupported}, {8, WidenScalar}, {9, Unsupported},
+    {16, WidenScalar}, {17, Unsupported}, {32, Legal}, {33, Unsupported},
+    {64, Legal}, {65, Unsupported}};
+  const SizeAndActionsVec Widen_1_8_16_32_Legal_64 =
+  {{1, WidenScalar}, {2, Unsupported}, {8, WidenScalar}, {9, Unsupported},
+    {16, WidenScalar}, {17, Unsupported}, {32, WidenScalar}, {33, Unsupported},
+    {64, Legal}, {65, Unsupported}};
+  const SizeAndActionsVec Widen_1_8_16_Legal_32_64_NarrowLarger =
+  {{1, WidenScalar}, {2, Unsupported}, {8, WidenScalar}, {9, Unsupported},
+    {16, WidenScalar}, {17, Unsupported}, {32, Legal}, {33, Unsupported},
+    {64, Legal}, {65, NarrowScalar}};
+  const SizeAndActionsVec Widen_16_Legal_32_64 =
+  {{1, Unsupported},
+    {16, WidenScalar}, {17, Unsupported}, {32, Legal}, {33, Unsupported},
+    {64, Legal}, {65, Unsupported}};
+  const SizeAndActionsVec LoadStoreOnlyAllowPow2Actions = {
+      {{1, WidenScalar},
+       {8, Legal},
+       {9, Unsupported},
+       {16, Legal},
+       {17, Unsupported},
+       {32, Legal},
+       {33, Unsupported},
+       {64, Legal},
+       {65, Unsupported},
+       {128, NarrowScalar},
+       {129, Unsupported}}};
 
   for (unsigned BinOp : {G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SHL}) {
     // These operations naturally get the right answer when used on
     // GPR32, even if the actual type is narrower.
-    for (auto Ty : {s32, s64, v2s32, v4s32, v2s64})
-      setAction({BinOp, Ty}, Legal);
-
-    for (auto Ty : {s1, s8, s16})
-      setAction({BinOp, Ty}, WidenScalar);
+    setAction({BinOp, Scalar}, Widen_1_8_16_Legal_32_64_NarrowLarger);
+    setScalarInVectorAction(BinOp, Only32Or64IsLegal);
+    setLegalNrVectorLanes(BinOp,
+                          {
+                              {8, {4, 8, 16}}, // 4x8, 8x8 and 16x8 are legal
+                              {16, {2, 4, 8}}, // 2x16, 4x16 and 8x16 are legal
+                              {32, {1, 2, 4}}, // 1x32, 2x32 and 4x32 are legal
+                              {64, {1, 2}},    // 1x64 and 2x642 are legal
+                          });
   }
 
-  setAction({G_GEP, p0}, Legal);
-  setAction({G_GEP, 1, s64}, Legal);
+  setAction({G_GEP, p0}, p0Legality);
+  setAction({G_GEP, 1, Scalar}, Widen_1_8_16_32_Legal_64);
 
-  for (auto Ty : {s1, s8, s16, s32})
-    setAction({G_GEP, 1, Ty}, WidenScalar);
+  setAction({G_PTR_MASK, p0}, p0Legality);
 
-  setAction({G_PTR_MASK, p0}, Legal);
-
-  for (unsigned BinOp : {G_LSHR, G_ASHR, G_SDIV, G_UDIV}) {
-    for (auto Ty : {s32, s64})
-      setAction({BinOp, Ty}, Legal);
-
-    for (auto Ty : {s1, s8, s16})
-      setAction({BinOp, Ty}, WidenScalar);
-  }
+  for (unsigned BinOp : {G_LSHR, G_ASHR, G_SDIV, G_UDIV})
+    setAction({BinOp, Scalar}, Widen_1_8_16_Legal_32_64);
 
   for (unsigned BinOp : {G_SREM, G_UREM})
-    for (auto Ty : { s1, s8, s16, s32, s64 })
-      setAction({BinOp, Ty}, Lower);
+    setAction({BinOp, Scalar}, UnsupportedButFor({1,8,16,32,64}, Lower));
 
-  for (unsigned Op : {G_SMULO, G_UMULO})
-      setAction({Op, s64}, Lower);
+  for (unsigned Op : {G_SMULO, G_UMULO}) {
+    setAction({Op, Scalar}, {{1, WidenScalar}, {64, Lower}, {65, Unsupported}});
+    setAction({Op, 1, Scalar}, Only1IsLegal);
+  }
 
   for (unsigned Op : {G_UADDE, G_USUBE, G_SADDO, G_SSUBO, G_SMULH, G_UMULH}) {
-    for (auto Ty : { s32, s64 })
-      setAction({Op, Ty}, Legal);
-
-    setAction({Op, 1, s1}, Legal);
+    setAction({Op, Scalar}, Only32Or64IsLegal);
+    setAction({Op, 1, Scalar}, Only1IsLegal);
   }
 
   for (unsigned BinOp : {G_FADD, G_FSUB, G_FMUL, G_FDIV})
-    for (auto Ty : {s32, s64})
-      setAction({BinOp, Ty}, Legal);
+    setAction({BinOp, Scalar}, Only32Or64IsLegal);
+  setAction({G_FNEG, Scalar}, Only32Or64Lower);
 
-  for (unsigned BinOp : {G_FREM, G_FPOW}) {
-    setAction({BinOp, s32}, Libcall);
-    setAction({BinOp, s64}, Libcall);
-  }
+  for (unsigned BinOp : {G_FREM, G_FPOW})
+    setAction({BinOp, Scalar}, UnsupportedButFor({32,64}, Libcall));
 
-  for (auto Ty : {s32, s64, p0}) {
-    setAction({G_INSERT, Ty}, Legal);
-    setAction({G_INSERT, 1, Ty}, Legal);
-  }
-  for (auto Ty : {s1, s8, s16}) {
-    setAction({G_INSERT, Ty}, WidenScalar);
-    setAction({G_INSERT, 1, Ty}, Legal);
-    // FIXME: Can't widen the sources because that violates the constraints on
-    // G_INSERT (It seems entirely reasonable that inputs shouldn't overlap).
-  }
+  // FIXME: what should we do about G_INSERTs with more than one source value?
+  // For now the default of not specifying means we'll fall back.
+  setAction({G_INSERT, Scalar}, Widen_1_8_16_Legal_32_64_NarrowLarger);
+  setAction({G_INSERT, p0}, p0Legality);
+  setAction({G_INSERT, 1, p0}, p0Legality);
+  setAction({G_INSERT, 1, Scalar}, Only1Or8Or16Or32Or64IsLegal);
 
   for (unsigned MemOp : {G_LOAD, G_STORE}) {
-    for (auto Ty : {s8, s16, s32, s64, p0, v2s32})
-      setAction({MemOp, Ty}, Legal);
-
-    setAction({MemOp, s1}, WidenScalar);
+    setAction({MemOp, Scalar}, LoadStoreOnlyAllowPow2Actions);
+    setAction({MemOp, p0}, p0Legality);
+    setScalarInVectorAction(MemOp, Only32IsLegal);
+    // FIXME: could this increase the number of bytes loaded or stored?
+    setLegalNrVectorLanes(MemOp,
+                          {
+                              {8, {4, 8, 16}}, // 4x8, 8x8 and 16x8 are legal
+                              {16, {2, 4, 8}}, // 2x16, 4x16 and 8x16 are legal
+                              {32, {1, 2, 4}}, // 1x32, 2x32 and 4x32 are legal
+                              {64, {1, 2}},    // 1x64 and 2x642 are legal
+                          });
 
     // And everything's fine in addrspace 0.
-    setAction({MemOp, 1, p0}, Legal);
+    setAction({MemOp, 1, p0}, p0Legality);
   }
 
   // Constants
-  for (auto Ty : {s32, s64}) {
-    setAction({TargetOpcode::G_CONSTANT, Ty}, Legal);
-    setAction({TargetOpcode::G_FCONSTANT, Ty}, Legal);
-  }
-
-  setAction({G_CONSTANT, p0}, Legal);
-
-  for (auto Ty : {s1, s8, s16})
-    setAction({TargetOpcode::G_CONSTANT, Ty}, WidenScalar);
-
-  setAction({TargetOpcode::G_FCONSTANT, s16}, WidenScalar);
-
-  setAction({G_ICMP, s1}, Legal);
-  setAction({G_ICMP, 1, s32}, Legal);
-  setAction({G_ICMP, 1, s64}, Legal);
-  setAction({G_ICMP, 1, p0}, Legal);
-
-  for (auto Ty : {s1, s8, s16}) {
-    setAction({G_ICMP, 1, Ty}, WidenScalar);
-  }
+  setAction({G_CONSTANT, Scalar}, Widen_1_8_16_Legal_32_64);
+  setAction({G_FCONSTANT, Scalar}, Widen_16_Legal_32_64);
+  setAction({G_CONSTANT, p0}, p0Legality);
+
+  setAction({G_ICMP, Scalar}, UnsupportedButFor({1}, Legal)); //Only1IsLegal);
+  setAction({G_ICMP, 1, Scalar}, Widen_1_8_16_Legal_32_64);
+  setAction({G_ICMP, 1, p0}, p0Legality);
 
-  setAction({G_FCMP, s1}, Legal);
-  setAction({G_FCMP, 1, s32}, Legal);
-  setAction({G_FCMP, 1, s64}, Legal);
+  setAction({G_FCMP, Scalar}, Only1IsLegal);
+  setAction({G_FCMP, 1, Scalar}, Only32Or64IsLegal);
 
   // Extensions
-  for (auto Ty : { s1, s8, s16, s32, s64 }) {
-    setAction({G_ZEXT, Ty}, Legal);
-    setAction({G_SEXT, Ty}, Legal);
-    setAction({G_ANYEXT, Ty}, Legal);
-  }
-
-  for (auto Ty : { s1, s8, s16, s32 }) {
-    setAction({G_ZEXT, 1, Ty}, Legal);
-    setAction({G_SEXT, 1, Ty}, Legal);
-    setAction({G_ANYEXT, 1, Ty}, Legal);
+  for (unsigned ExtOp : {G_ZEXT, G_SEXT, G_ANYEXT}) {
+    setAction({ExtOp, Scalar}, Only1Or8Or16Or32Or64IsLegal);
+    setAction({ExtOp, 1, Scalar}, Only1Or8Or16Or32IsLegal);
   }
 
-  setAction({G_FPEXT, s64}, Legal);
-  setAction({G_FPEXT, 1, s32}, Legal);
+  setAction({G_FPEXT, Scalar}, Only64IsLegal);
+  setAction({G_FPEXT, 1, Scalar}, Only32IsLegal);
 
   // Truncations
-  for (auto Ty : { s16, s32 })
-    setAction({G_FPTRUNC, Ty}, Legal);
-
-  for (auto Ty : { s32, s64 })
-    setAction({G_FPTRUNC, 1, Ty}, Legal);
-
-  for (auto Ty : { s1, s8, s16, s32 })
-    setAction({G_TRUNC, Ty}, Legal);
-
-  for (auto Ty : { s8, s16, s32, s64 })
-    setAction({G_TRUNC, 1, Ty}, Legal);
+  setAction({G_FPTRUNC, 0, Scalar}, Only16Or32IsLegal);
+  setAction({G_FPTRUNC, 1, Scalar}, Only32Or64IsLegal);
+  setAction({G_TRUNC, 0, Scalar}, Only1Or8Or16Or32IsLegal);
+  setAction({G_TRUNC, 1, Scalar}, Only8Or16Or32Or64IsLegal);
 
   // Conversions
-  for (auto Ty : { s32, s64 }) {
-    setAction({G_FPTOSI, 0, Ty}, Legal);
-    setAction({G_FPTOUI, 0, Ty}, Legal);
-    setAction({G_SITOFP, 1, Ty}, Legal);
-    setAction({G_UITOFP, 1, Ty}, Legal);
-  }
-  for (auto Ty : { s1, s8, s16 }) {
-    setAction({G_FPTOSI, 0, Ty}, WidenScalar);
-    setAction({G_FPTOUI, 0, Ty}, WidenScalar);
-    setAction({G_SITOFP, 1, Ty}, WidenScalar);
-    setAction({G_UITOFP, 1, Ty}, WidenScalar);
-  }
-
-  for (auto Ty : { s32, s64 }) {
-    setAction({G_FPTOSI, 1, Ty}, Legal);
-    setAction({G_FPTOUI, 1, Ty}, Legal);
-    setAction({G_SITOFP, 0, Ty}, Legal);
-    setAction({G_UITOFP, 0, Ty}, Legal);
-  }
+  setAction({G_FPTOSI, 0, Scalar}, Widen_1_8_16_Legal_32_64);
+  setAction({G_FPTOUI, 0, Scalar}, Widen_1_8_16_Legal_32_64);
+  setAction({G_SITOFP, 1, Scalar}, Widen_1_8_16_Legal_32_64);
+  setAction({G_UITOFP, 1, Scalar}, Widen_1_8_16_Legal_32_64);
+  setAction({G_FPTOSI, 1, Scalar}, Only32Or64IsLegal);
+  setAction({G_FPTOUI, 1, Scalar}, Only32Or64IsLegal);
+  setAction({G_SITOFP, 0, Scalar}, Only32Or64IsLegal);
+  setAction({G_UITOFP, 0, Scalar}, Only32Or64IsLegal);
 
   // Control-flow
-  for (auto Ty : {s1, s8, s16, s32})
-    setAction({G_BRCOND, Ty}, Legal);
-  setAction({G_BRINDIRECT, p0}, Legal);
+  setAction({G_BRCOND, Scalar}, Only1Or8Or16Or32IsLegal);
+  setAction({G_BRINDIRECT, p0}, p0Legality);
 
   // Select
-  for (auto Ty : {s1, s8, s16})
-    setAction({G_SELECT, Ty}, WidenScalar);
-
-  for (auto Ty : {s32, s64, p0})
-    setAction({G_SELECT, Ty}, Legal);
-
-  setAction({G_SELECT, 1, s1}, Legal);
+  setAction({G_SELECT, Scalar}, Widen_1_8_16_Legal_32_64);
+  setAction({G_SELECT, p0}, p0Legality);
+  setAction({G_SELECT, 1, Scalar}, Only1IsLegal);
 
   // Pointer-handling
-  setAction({G_FRAME_INDEX, p0}, Legal);
-  setAction({G_GLOBAL_VALUE, p0}, Legal);
+  setAction({G_FRAME_INDEX, p0}, p0Legality);
+  setAction({G_GLOBAL_VALUE, p0}, p0Legality);
 
-  for (auto Ty : {s1, s8, s16, s32, s64})
-    setAction({G_PTRTOINT, 0, Ty}, Legal);
+  setAction({G_PTRTOINT, 0, Scalar}, Only1Or8Or16Or32Or64IsLegal);
+  setAction({G_PTRTOINT, 1, p0}, p0Legality);
 
-  setAction({G_PTRTOINT, 1, p0}, Legal);
-
-  setAction({G_INTTOPTR, 0, p0}, Legal);
-  setAction({G_INTTOPTR, 1, s64}, Legal);
+  setAction({G_INTTOPTR, 0, p0}, p0Legality);
+  setAction({G_INTTOPTR, 1, Scalar}, Only64IsLegal);
 
   // Casts for 32 and 64-bit width type are just copies.
-  for (auto Ty : {s1, s8, s16, s32, s64}) {
-    setAction({G_BITCAST, 0, Ty}, Legal);
-    setAction({G_BITCAST, 1, Ty}, Legal);
-  }
+  setAction({G_BITCAST, 0, Scalar}, Only1Or8Or16Or32Or64IsLegal);
+  setAction({G_BITCAST, 1, Scalar}, Only1Or8Or16Or32Or64IsLegal);
 
   // For the sake of copying bits around, the type does not really
   // matter as long as it fits a register.
-  for (int EltSize = 8; EltSize <= 64; EltSize *= 2) {
-    setAction({G_BITCAST, 0, LLT::vector(128/EltSize, EltSize)}, Legal);
-    setAction({G_BITCAST, 1, LLT::vector(128/EltSize, EltSize)}, Legal);
-    if (EltSize >= 64)
-      continue;
-
-    setAction({G_BITCAST, 0, LLT::vector(64/EltSize, EltSize)}, Legal);
-    setAction({G_BITCAST, 1, LLT::vector(64/EltSize, EltSize)}, Legal);
-    if (EltSize >= 32)
-      continue;
+  setScalarInVectorAction(G_BITCAST, Only8Or16Or32Or64IsLegal);
+  setLegalNrVectorLanes(G_BITCAST,
+                        {
+                            {8, {4, 8, 16}}, // 4x8, 8x8 and 16x8 are legal
+                            {16, {2, 4, 8}}, // 2x16, 4x16 and 8x16 are legal
+                            {32, {1, 2, 4}}, // 1x32, 2x32 and 4x32 are legal
+                            {64, {1, 2}},    // 1x64 and 2x642 are legal
+                        });
 
-    setAction({G_BITCAST, 0, LLT::vector(32/EltSize, EltSize)}, Legal);
-    setAction({G_BITCAST, 1, LLT::vector(32/EltSize, EltSize)}, Legal);
-  }
-
-  setAction({G_VASTART, p0}, Legal);
+  setAction({G_VASTART, p0}, p0Legality);
 
   // va_list must be a pointer, but most sized types are pretty easy to handle
   // as the destination.
-  setAction({G_VAARG, 1, p0}, Legal);
-
-  for (auto Ty : {s8, s16, s32, s64, p0})
-    setAction({G_VAARG, Ty}, Custom);
-
-  computeTables();
+  setAction({G_VAARG, 1, p0}, p0Legality);
+  setAction({G_VAARG, Scalar}, UnsupportedButFor({8,16,32,64}, Custom));
+  setAction({G_VAARG, p0}, {{1, Custom}});
 }
 
 bool AArch64LegalizerInfo::legalizeCustom(MachineInstr &MI,
                                           MachineRegisterInfo &MRI,
                                           MachineIRBuilder &MIRBuilder) const {
   switch (MI.getOpcode()) {
   default:
     // No idea what to do.

lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp

 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
 AMDGPULegalizerInfo::AMDGPULegalizerInfo() {
   using namespace TargetOpcode;
 
-  const LLT S32 = LLT::scalar(32);
-  const LLT S64 = LLT::scalar(64);
+  const LLT s1 = LLT::scalar(1);
   const LLT P1 = LLT::pointer(1, 64);
   const LLT P2 = LLT::pointer(2, 64);
 
-  setAction({G_CONSTANT, S64}, Legal);
+  const SizeAndActionsVec P1Legality = UnsupportedButFor({64}, Legal);
+  const SizeAndActionsVec P2Legality = P1Legality;
 
-  setAction({G_GEP, P1}, Legal);
-  setAction({G_GEP, P2}, Legal);
-  setAction({G_GEP, 1, S64}, Legal);
-
-  setAction({G_LOAD, P1}, Legal);
-  setAction({G_LOAD, P2}, Legal);
-  setAction({G_LOAD, S32}, Legal);
-  setAction({G_LOAD, 1, P1}, Legal);
-  setAction({G_LOAD, 1, P2}, Legal);
+  const SizeAndActionsVec Only32IsLegal = UnsupportedButFor({32}, Legal);
+  const SizeAndActionsVec Only64IsLegal = UnsupportedButFor({64}, Legal);
 
-  setAction({G_STORE, S32}, Legal);
-  setAction({G_STORE, 1, P1}, Legal);
+  setAction({G_CONSTANT, s1}, Only64IsLegal);
+
+  setAction({G_GEP, P1}, P1Legality);
+  setAction({G_GEP, P2}, P2Legality);
+  setAction({G_GEP, 1, s1}, Only64IsLegal);
+
+  setAction({G_LOAD, P1}, P1Legality);
+  setAction({G_LOAD, P2}, P2Legality);
+  setAction({G_LOAD, s1}, Only32IsLegal);
+  setAction({G_LOAD, 1, P1}, P1Legality);
+  setAction({G_LOAD, 1, P2}, P2Legality);
+
+  setAction({G_STORE, s1}, Only32IsLegal);
+  setAction({G_STORE, 1, P1}, P1Legality);
 
   // FIXME: When RegBankSelect inserts copies, it will only create new
   // registers with scalar types.  This means we can end up with
   // G_LOAD/G_STORE/G_GEP instruction with scalar types for their pointer
   // operands.  In assert builds, the instruction selector will assert
   // if it sees a generic instruction which isn't legal, so we need to
   // tell it that scalar types are legal for pointer operands
-  setAction({G_GEP, S64}, Legal);
-  setAction({G_LOAD, 1, S64}, Legal);
-  setAction({G_STORE, 1, S64}, Legal);
-
-  computeTables();
+  setAction({G_GEP, s1}, Only64IsLegal);
+  setAction({G_LOAD, 1, s1}, Only64IsLegal);
+  setAction({G_STORE, 1, s1}, Only64IsLegal);
 }

lib/Target/ARM/ARMLegalizerInfo.cpp

 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
 ARMLegalizerInfo::ARMLegalizerInfo(const ARMSubtarget &ST) {
   using namespace TargetOpcode;
 
   const LLT p0 = LLT::pointer(0, 32);
-
   const LLT s1 = LLT::scalar(1);
-  const LLT s8 = LLT::scalar(8);
-  const LLT s16 = LLT::scalar(16);
-  const LLT s32 = LLT::scalar(32);
-  const LLT s64 = LLT::scalar(64);
-
-  setAction({G_FRAME_INDEX, p0}, Legal);
-
-  for (unsigned Op : {G_LOAD, G_STORE}) {
-    for (auto Ty : {s1, s8, s16, s32, p0})
-      setAction({Op, Ty}, Legal);
-    setAction({Op, 1, p0}, Legal);
+
+  const SizeAndActionsVec p0Legality = UnsupportedButFor({32}, Legal);
+  const SizeAndActionsVec Only32IsLegal = UnsupportedButFor({32}, Legal);
+  const SizeAndActionsVec Only64IsLegal = UnsupportedButFor({64}, Legal);
+  const SizeAndActionsVec Only32Or64IsLegal =
+      UnsupportedButFor({32, 64}, Legal);
+  const SizeAndActionsVec Only16Or32IsLegal =
+      UnsupportedButFor({16, 32}, Legal);
+  const SizeAndActionsVec Only1Or8Or16IsLegal =
+      UnsupportedButFor({1, 8, 16}, Legal);
+  const SizeAndActionsVec Only1Or8Or16Or32IsLegal =
+      UnsupportedButFor({1, 8, 16, 32}, Legal);
+  const SizeAndActionsVec Only1Or8Or16Or32Or64IsLegal =
+      UnsupportedButFor({1, 8, 16, 32, 64}, Legal);
+
+  setAction({G_FRAME_INDEX, p0}, p0Legality);
+
+  if (ST.hasVFP2()) {
+    setAction({G_LOAD, s1}, Only1Or8Or16Or32Or64IsLegal);
+    setAction({G_STORE, s1}, Only1Or8Or16Or32Or64IsLegal);
+  } else {
+    setAction({G_LOAD, s1}, Only1Or8Or16Or32IsLegal);
+    setAction({G_STORE, s1}, Only1Or8Or16Or32IsLegal);
   }
+  setAction({G_LOAD, p0}, p0Legality);
+  setAction({G_LOAD, 1, p0}, p0Legality);
+  setAction({G_STORE, p0}, p0Legality);
+  setAction({G_STORE, 1, p0}, p0Legality);
 
-  for (auto Ty : {s1, s8, s16, s32})
-    setAction({G_ADD, Ty}, Legal);
+  setAction({G_ADD, s1}, Only1Or8Or16Or32IsLegal);
 
   for (unsigned Op : {G_SEXT, G_ZEXT}) {
-    setAction({Op, s32}, Legal);
-    for (auto Ty : {s1, s8, s16})
-      setAction({Op, 1, Ty}, Legal);
+    setAction({Op, s1}, Only32IsLegal);
+    setAction({Op, 1, s1}, Only1Or8Or16IsLegal);
   }
 
-  setAction({G_GEP, p0}, Legal);
-  setAction({G_GEP, 1, s32}, Legal);
+  setAction({G_GEP, p0}, p0Legality);
+  setAction({G_GEP, 1, s1}, Only32IsLegal);
 
-  setAction({G_CONSTANT, s32}, Legal);
+  setAction({G_CONSTANT, s1}, Only32IsLegal);
 
   if (ST.hasVFP2()) {
-    setAction({G_FADD, s32}, Legal);
-    setAction({G_FADD, s64}, Legal);
-
-    setAction({G_LOAD, s64}, Legal);
-    setAction({G_STORE, s64}, Legal);
+    setAction({G_FADD, s1}, Only32Or64IsLegal);
   }
-
-  computeTables();
 }

lib/Target/X86/X86LegalizerInfo.cpp

 using namespace llvm;
 using namespace TargetOpcode;
 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
 X86LegalizerInfo::X86LegalizerInfo(const X86Subtarget &STI) : Subtarget(STI) {
-
   setLegalizerInfo32bit();
   setLegalizerInfo64bit();
   setLegalizerInfoSSE1();
   setLegalizerInfoSSE2();
-
-  computeTables();
 }
 
+const LegalizerInfo::SizeAndActionsVec Only8Or16Or32IsLegal =
+    LegalizerInfo::UnsupportedButFor({8, 16, 32}, LegalizerInfo::Legal);
+const LegalizerInfo::SizeAndActionsVec Only8Or16Or32Or64IsLegal =
+    LegalizerInfo::UnsupportedButFor({8, 16, 32, 64}, LegalizerInfo::Legal);
+const LegalizerInfo::SizeAndActionsVec Only32IsLegal =
+    LegalizerInfo::UnsupportedButFor({32}, LegalizerInfo::Legal);
+const LegalizerInfo::SizeAndActionsVec Only32Or64IsLegal =
+    LegalizerInfo::UnsupportedButFor({32, 64}, LegalizerInfo::Legal);
+const LLT Scalar = LLT::scalar(1);
+
 void X86LegalizerInfo::setLegalizerInfo32bit() {
+  if (Subtarget.is64Bit())
+    return;
 
-  const LLT s8 = LLT::scalar(8);
-  const LLT s16 = LLT::scalar(16);
-  const LLT s32 = LLT::scalar(32);
-
-  for (auto Ty : {s8, s16, s32}) {
-    setAction({G_ADD, Ty}, Legal);
-    setAction({G_SUB, Ty}, Legal);
-  }
+  setAction({TargetOpcode::G_ADD, Scalar}, Only8Or16Or32IsLegal);
+  setAction({TargetOpcode::G_SUB, Scalar}, Only8Or16Or32IsLegal);
 }
 
 void X86LegalizerInfo::setLegalizerInfo64bit() {
-
   if (!Subtarget.is64Bit())
     return;
 
-  const LLT s64 = LLT::scalar(64);
-
-  setAction({G_ADD, s64}, Legal);
-  setAction({G_SUB, s64}, Legal);
+  setAction({TargetOpcode::G_ADD, Scalar}, Only8Or16Or32Or64IsLegal);
+  setAction({TargetOpcode::G_SUB, Scalar}, Only8Or16Or32Or64IsLegal);
 }
 
 void X86LegalizerInfo::setLegalizerInfoSSE1() {
   if (!Subtarget.hasSSE1())
     return;
 
-  const LLT s32 = LLT::scalar(32);
-  const LLT v4s32 = LLT::vector(4, 32);
-
-  for (unsigned BinOp : {G_FADD, G_FSUB, G_FMUL, G_FDIV})
-    for (auto Ty : {s32, v4s32})
-      setAction({BinOp, Ty}, Legal);
+  for (unsigned BinOp : {G_FADD, G_FSUB, G_FMUL, G_FDIV}) {
+    setAction({BinOp, Scalar}, Only32IsLegal);
+    setScalarInVectorAction(
+        BinOp, getWidenToLargerTypesAndNarrowToLargest({{32, Legal}}));
+    setLegalNrVectorLanes(BinOp, {
+                                     {32, {4}}, // 4x32 is legal
+                                 });
+  }
 }
 
 void X86LegalizerInfo::setLegalizerInfoSSE2() {
   if (!Subtarget.hasSSE2())
     return;
 
-  const LLT s64 = LLT::scalar(64);
-  const LLT v4s32 = LLT::vector(4, 32);
-  const LLT v2s64 = LLT::vector(2, 64);
-
-  for (unsigned BinOp : {G_FADD, G_FSUB, G_FMUL, G_FDIV})
-    for (auto Ty : {s64, v2s64})
-      setAction({BinOp, Ty}, Legal);
-
-  for (unsigned BinOp : {G_ADD, G_SUB})
-    for (auto Ty : {v4s32})
-      setAction({BinOp, Ty}, Legal);
-
+  for (unsigned BinOp : {G_FADD, G_FSUB, G_FMUL, G_FDIV}) {
+    setAction({BinOp, Scalar}, Only32Or64IsLegal, /*ResetAllowed=*/true);
+    setScalarInVectorAction(BinOp, getWidenToLargerTypesAndNarrowToLargest(
+                                       {{32, Legal}, {64, Legal}}));
+    setLegalNrVectorLanes(BinOp, {
+                                     {32, {4}}, // 4x32 is legal
+                                     {64, {2}}, // 2x64 is legal
+                                 });
+  }
+  for (unsigned BinOp : {G_ADD, G_SUB}) {
+    setScalarInVectorAction(
+        BinOp, getWidenToLargerTypesAndNarrowToLargest({{32, Legal}}));
+    setLegalNrVectorLanes(BinOp, {
+                                     {32, {4}}, // 4x32 is legal
+                                 });
+  }
 }

unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp

 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
 #include "llvm/Target/TargetOpcodes.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 // Define a couple of pretty printers to help debugging when things go wrong.
 namespace llvm {
-std::ostream &
-operator<<(std::ostream &OS, const llvm::LegalizerInfo::LegalizeAction Act) {
+std::ostream &operator<<(std::ostream &OS,
+                         const llvm::LegalizerInfo::LegalizeAction Act) {
   switch (Act) {
-  case LegalizerInfo::Lower: OS << "Lower"; break;
-  case LegalizerInfo::Legal: OS << "Legal"; break;
-  case LegalizerInfo::NarrowScalar: OS << "NarrowScalar"; break;
-  case LegalizerInfo::WidenScalar:  OS << "WidenScalar"; break;
-  case LegalizerInfo::FewerElements:  OS << "FewerElements"; break;
-  case LegalizerInfo::MoreElements:  OS << "MoreElements"; break;
-  case LegalizerInfo::Libcall: OS << "Libcall"; break;
-  case LegalizerInfo::Custom: OS << "Custom"; break;
-  case LegalizerInfo::Unsupported: OS << "Unsupported"; break;
-  case LegalizerInfo::NotFound: OS << "NotFound";
+  case LegalizerInfo::Lower:
+    OS << "Lower";
+    break;
+  case LegalizerInfo::Legal:
+    OS << "Legal";
+    break;
+  case LegalizerInfo::NarrowScalar:
+    OS << "NarrowScalar";
+    break;
+  case LegalizerInfo::WidenScalar:
+    OS << "WidenScalar";
+    break;
+  case LegalizerInfo::FewerElements:
+    OS << "FewerElements";
+    break;
+  case LegalizerInfo::MoreElements:
+    OS << "MoreElements";
+    break;
+  case LegalizerInfo::Libcall:
+    OS << "Libcall";
+    break;
+  case LegalizerInfo::Custom:
+    OS << "Custom";
+    break;
+  case LegalizerInfo::Unsupported:
+    OS << "Unsupported";
+    break;
+  case LegalizerInfo::NotFound:
+    OS << "NotFound";
   }
   return OS;
 }
 
-std::ostream &
-operator<<(std::ostream &OS, const llvm::LLT Ty) {
+std::ostream &operator<<(std::ostream &OS, const llvm::LLT Ty) {
   std::string Repr;
   raw_string_ostream SS{Repr};
   Ty.print(SS);
   OS << SS.str();
   return OS;
 }
 }
 
 namespace {
 
-
 TEST(LegalizerInfoTest, ScalarRISC) {
   using namespace TargetOpcode;
   LegalizerInfo L;
   // Typical RISCy set of operations based on AArch64.
-  L.setAction({G_ADD, LLT::scalar(8)}, LegalizerInfo::WidenScalar);
-  L.setAction({G_ADD, LLT::scalar(16)}, LegalizerInfo::WidenScalar);
-  L.setAction({G_ADD, LLT::scalar(32)}, LegalizerInfo::Legal);
-  L.setAction({G_ADD, LLT::scalar(64)}, LegalizerInfo::Legal);
-  L.computeTables();
+  L.setAction({G_ADD, LLT::scalar(1)}, {{1, LegalizerInfo::WidenScalar},
+                                        {32, LegalizerInfo::Legal},
+                                        {33, LegalizerInfo::WidenScalar},
+                                        {64, LegalizerInfo::Legal},
+                                        {65, LegalizerInfo::NarrowScalar}});
+  L.setAction({G_SUB, LLT::scalar(1)},
+              LegalizerInfo::getWidenToLargerTypesAndNarrowToLargest(
+                  {{32, LegalizerInfo::Legal}, {64, LegalizerInfo::Legal}}));
 
+  for (auto &opcode : {G_ADD, G_SUB}) {
     // Check we infer the correct types and actually do what we're told.
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(8)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(16)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(32)}),
-            std::make_pair(LegalizerInfo::Legal, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(64)}),
-            std::make_pair(LegalizerInfo::Legal, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(8)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::WidenScalar, LLT::scalar(32)}}));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(16)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::WidenScalar, LLT::scalar(32)}}));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(32)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::Legal, LLT::scalar(32)}}));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(64)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::Legal, LLT::scalar(64)}}));
 
     // Make sure the default for over-sized types applies.
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(128)}),
-            std::make_pair(LegalizerInfo::NarrowScalar, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(128)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::NarrowScalar, LLT::scalar(64)}}));
+    // Make sure we also handle unusual sizes
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(1)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::WidenScalar, LLT::scalar(32)}}));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(31)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::WidenScalar, LLT::scalar(32)}}));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(33)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::WidenScalar, LLT::scalar(64)}}));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(63)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::WidenScalar, LLT::scalar(64)}}));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(65)}),
+              LegalizerInfo::ActionAndTypes(
+                  {{LegalizerInfo::NarrowScalar, LLT::scalar(64)}}));
+  }
 }
 
 TEST(LegalizerInfoTest, VectorRISC) {
   using namespace TargetOpcode;
   LegalizerInfo L;
   // Typical RISCy set of operations based on ARM.
-  L.setScalarInVectorAction(G_ADD, LLT::scalar(8), LegalizerInfo::Legal);
-  L.setScalarInVectorAction(G_ADD, LLT::scalar(16), LegalizerInfo::Legal);
-  L.setScalarInVectorAction(G_ADD, LLT::scalar(32), LegalizerInfo::Legal);
-
-  L.setAction({G_ADD, LLT::vector(8, 8)}, LegalizerInfo::Legal);
-  L.setAction({G_ADD, LLT::vector(16, 8)}, LegalizerInfo::Legal);
-  L.setAction({G_ADD, LLT::vector(4, 16)}, LegalizerInfo::Legal);
-  L.setAction({G_ADD, LLT::vector(8, 16)}, LegalizerInfo::Legal);
-  L.setAction({G_ADD, LLT::vector(2, 32)}, LegalizerInfo::Legal);
-  L.setAction({G_ADD, LLT::vector(4, 32)}, LegalizerInfo::Legal);
-  L.computeTables();
+  L.setScalarInVectorAction(
+      G_ADD, LegalizerInfo::getWidenToLargerTypesAndNarrowToLargest(
+                 {{8, LegalizerInfo::Legal},
+                  {16, LegalizerInfo::Legal},
+                  {32, LegalizerInfo::Legal}}));
+  L.setLegalNrVectorLanes(G_ADD, {{8, {8, 16}},   // 8x8 and 16x8 are legal
+                                  {16, {4, 8}},   // 16x4 and 16x8 are legal
+                                  {32, {2, 4}}}); // 32x2 and 32x4 are legal
 
   // Check we infer the correct types and actually do what we're told for some
   // simple cases.
-  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(2, 8)}),
-            std::make_pair(LegalizerInfo::MoreElements, LLT::vector(8, 8)));
   ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 8)}),
-            std::make_pair(LegalizerInfo::Legal, LLT::vector(8, 8)));
-  ASSERT_EQ(
-      L.getAction({G_ADD, LLT::vector(8, 32)}),
-      std::make_pair(LegalizerInfo::FewerElements, LLT::vector(4, 32)));
+            LegalizerInfo::ActionAndTypes(
+                {{LegalizerInfo::Legal, LLT::vector(8, 8)}}));
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 7)}),
+            LegalizerInfo::ActionAndTypes(
+                {{LegalizerInfo::WidenScalar, LLT::vector(8, 8)}}));
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(2, 8)}),
+            LegalizerInfo::ActionAndTypes(
+                {{LegalizerInfo::MoreElements, LLT::vector(8, 8)}}));
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 32)}),
+            LegalizerInfo::ActionAndTypes(
+                {{LegalizerInfo::FewerElements, LLT::vector(4, 32)}}));
+  // Check a few non-power-of-2 sizes:
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 8)}),
+            LegalizerInfo::ActionAndTypes(
+                {{LegalizerInfo::MoreElements, LLT::vector(8, 8)}}));
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 3)}),
+            LegalizerInfo::ActionAndTypes(
+                {{LegalizerInfo::WidenScalar, LLT::vector(3, 8)},
+                 {LegalizerInfo::MoreElements, LLT::vector(8, 8)}}));
 }
 
 TEST(LegalizerInfoTest, MultipleTypes) {
   using namespace TargetOpcode;
   LegalizerInfo L;
   LLT p0 = LLT::pointer(0, 64);
-  LLT s32 = LLT::scalar(32);
   LLT s64 = LLT::scalar(64);
 
   // Typical RISCy set of operations based on AArch64.
-  L.setAction({G_PTRTOINT, 0, s64}, LegalizerInfo::Legal);
-  L.setAction({G_PTRTOINT, 1, p0}, LegalizerInfo::Legal);
-
-  L.setAction({G_PTRTOINT, 0, s32}, LegalizerInfo::WidenScalar);
-  L.computeTables();
+  L.setAction({G_PTRTOINT, 0, LLT::scalar(1)},
+              {{1, LegalizerInfo::WidenScalar},
+               {64, LegalizerInfo::Legal},
+               {65, LegalizerInfo::NarrowScalar}});
+  L.setAction({G_PTRTOINT, 1, LLT::pointer(0, 1)},
+              {{1, LegalizerInfo::Unsupported},
+               {64, LegalizerInfo::Legal},
+               {65, LegalizerInfo::Unsupported}});
 
   // Check we infer the correct types and actually do what we're told.
   ASSERT_EQ(L.getAction({G_PTRTOINT, 0, s64}),
-            std::make_pair(LegalizerInfo::Legal, s64));
+            LegalizerInfo::ActionAndTypes({{LegalizerInfo::Legal, s64}}));
   ASSERT_EQ(L.getAction({G_PTRTOINT, 1, p0}),
-            std::make_pair(LegalizerInfo::Legal, p0));
+            LegalizerInfo::ActionAndTypes({{LegalizerInfo::Legal, p0}}));
+  // Make sure we also handle unusual sizes
+  ASSERT_EQ(
+      L.getAction({G_PTRTOINT, 0, LLT::scalar(65)}),
+      LegalizerInfo::ActionAndTypes({{LegalizerInfo::NarrowScalar, s64}}));
+  ASSERT_EQ(L.getAction({G_PTRTOINT, 1, LLT::pointer(0, 32)}),
+            LegalizerInfo::ActionAndTypes(
+                {{LegalizerInfo::Unsupported, LLT::pointer(0, 32)}}));
+}
+
+TEST(LegalizerInfoTest, MultipleSteps) {
+  using namespace TargetOpcode;
+  LegalizerInfo L;
+  L.setAction({G_UREM, LLT::scalar(1)}, {{1, LegalizerInfo::WidenScalar},
+                                         {32, LegalizerInfo::Lower},
+                                         {33, LegalizerInfo::WidenScalar},
+                                         {64, LegalizerInfo::Lower},
+                                         {65, LegalizerInfo::NarrowScalar}});
+  L.setAction({G_LOAD, LLT::scalar(1)}, {{1, LegalizerInfo::WidenScalar},
+                                         {8, LegalizerInfo::Legal},
+                                         {9, LegalizerInfo::Unsupported},
+                                         {16, LegalizerInfo::NarrowScalar},
+                                         {17, LegalizerInfo::Unsupported}});
+
+  // Check we infer the correct types and actually do what we're told.
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(8)}),
+            LegalizerInfo::ActionAndTypes({
+                std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)),
+                std::make_pair(LegalizerInfo::Lower, LLT::scalar(32)),
+            }));
+  // Check that we correctly jump over Unsupported sizes when looking for
+  // a larger/smaller type size to legalize towards.
+  ASSERT_EQ(L.getAction({G_LOAD, LLT::scalar(16)}),
+            LegalizerInfo::ActionAndTypes({
+                std::make_pair(LegalizerInfo::NarrowScalar, LLT::scalar(8)),
+            }));
 }
 }

unittests/CodeGen/LowLevelTypeTest.cpp

 namespace {
 
 TEST(LowLevelTypeTest, Scalar) {
   LLVMContext C;
   DataLayout DL("");
 
   for (unsigned S : {1U, 17U, 32U, 64U, 0xfffffU}) {
     const LLT Ty = LLT::scalar(S);
-    const LLT HalfTy = (S % 2) == 0 ? Ty.halfScalarSize() : Ty;
-    const LLT DoubleTy = Ty.doubleScalarSize();
 
     // Test kind.
-    for (const LLT TestTy : {Ty, HalfTy, DoubleTy}) {
-      ASSERT_TRUE(TestTy.isValid());
-      ASSERT_TRUE(TestTy.isScalar());
+    ASSERT_TRUE(Ty.isValid());
+    ASSERT_TRUE(Ty.isScalar());
 
-      ASSERT_FALSE(TestTy.isPointer());
-      ASSERT_FALSE(TestTy.isVector());
-    }
+    ASSERT_FALSE(Ty.isPointer());
+    ASSERT_FALSE(Ty.isVector());
 
     // Test sizes.
     EXPECT_EQ(S, Ty.getSizeInBits());
     EXPECT_EQ(S, Ty.getScalarSizeInBits());
 
-    EXPECT_EQ(S*2, DoubleTy.getSizeInBits());
-    EXPECT_EQ(S*2, DoubleTy.getScalarSizeInBits());
-
-    if ((S % 2) == 0) {
-      EXPECT_EQ(S/2, HalfTy.getSizeInBits());
-      EXPECT_EQ(S/2, HalfTy.getScalarSizeInBits());
-    }
-
     // Test equality operators.
     EXPECT_TRUE(Ty == Ty);
     EXPECT_FALSE(Ty != Ty);
 
-    EXPECT_NE(Ty, DoubleTy);
-
     // Test Type->LLT conversion.
     Type *IRTy = IntegerType::get(C, S);
     EXPECT_EQ(Ty, getLLTForType(*IRTy, DL));
   }
 }
 
 TEST(LowLevelTypeTest, Vector) {
   LLVMContext C;
   DataLayout DL("");
 
   for (unsigned S : {1U, 17U, 32U, 64U, 0xfffU}) {
     for (uint16_t Elts : {2U, 3U, 4U, 32U, 0xffU}) {
       const LLT STy = LLT::scalar(S);
       const LLT VTy = LLT::vector(Elts, S);
 
       // Test the alternative vector().
       {
         const LLT VSTy = LLT::vector(Elts, STy);
         EXPECT_EQ(VTy, VSTy);
       }
 
       // Test getElementType().
       EXPECT_EQ(STy, VTy.getElementType());
 
-      const LLT HalfSzTy = ((S % 2) == 0) ? VTy.halfScalarSize() : VTy;
-      const LLT DoubleSzTy = VTy.doubleScalarSize();
-
-      // halfElements requires an even number of elements.
-      const LLT HalfEltIfEvenTy = ((Elts % 2) == 0) ?  VTy.halfElements() : VTy;
-      const LLT DoubleEltTy = VTy.doubleElements();
-
       // Test kind.
-      for (const LLT TestTy : {VTy, HalfSzTy, DoubleSzTy, DoubleEltTy}) {
-        ASSERT_TRUE(TestTy.isValid());
-        ASSERT_TRUE(TestTy.isVector());
-
-        ASSERT_FALSE(TestTy.isScalar());
-        ASSERT_FALSE(TestTy.isPointer());
-      }
-
-      // Test halving elements to a scalar.
-      {
-        ASSERT_TRUE(HalfEltIfEvenTy.isValid());
-        ASSERT_FALSE(HalfEltIfEvenTy.isPointer());
-        if (Elts > 2) {
-          ASSERT_TRUE(HalfEltIfEvenTy.isVector());
-        } else {
-          ASSERT_FALSE(HalfEltIfEvenTy.isVector());
-          EXPECT_EQ(STy, HalfEltIfEvenTy);
-        }
-      }
+      ASSERT_TRUE(VTy.isValid());
+      ASSERT_TRUE(VTy.isVector());
 
+      ASSERT_FALSE(VTy.isScalar());
+      ASSERT_FALSE(VTy.isPointer());
 
       // Test sizes.
       EXPECT_EQ(S * Elts, VTy.getSizeInBits());
       EXPECT_EQ(S, VTy.getScalarSizeInBits());
       EXPECT_EQ(Elts, VTy.getNumElements());
 
-      if ((S % 2) == 0) {
-        EXPECT_EQ((S / 2) * Elts, HalfSzTy.getSizeInBits());
-        EXPECT_EQ(S / 2, HalfSzTy.getScalarSizeInBits());
-        EXPECT_EQ(Elts, HalfSzTy.getNumElements());
-      }
-
-      EXPECT_EQ((S * 2) * Elts, DoubleSzTy.getSizeInBits());
-      EXPECT_EQ(S * 2, DoubleSzTy.getScalarSizeInBits());
-      EXPECT_EQ(Elts, DoubleSzTy.getNumElements());
-
-      if ((Elts % 2) == 0) {
-        EXPECT_EQ(S * (Elts / 2), HalfEltIfEvenTy.getSizeInBits());
-        EXPECT_EQ(S, HalfEltIfEvenTy.getScalarSizeInBits());
-        if (Elts > 2)
-          EXPECT_EQ(Elts / 2, HalfEltIfEvenTy.getNumElements());
-      }
-
-      EXPECT_EQ(S * (Elts * 2), DoubleEltTy.getSizeInBits());
-      EXPECT_EQ(S, DoubleEltTy.getScalarSizeInBits());
-      EXPECT_EQ(Elts * 2, DoubleEltTy.getNumElements());
-
       // Test equality operators.
       EXPECT_TRUE(VTy == VTy);
       EXPECT_FALSE(VTy != VTy);
 
       // Test inequality operators on..
       // ..different kind.
       EXPECT_NE(VTy, STy);
-      // ..different #elts.
-      EXPECT_NE(VTy, DoubleEltTy);
-      // ..different scalar size.
-      EXPECT_NE(VTy, DoubleSzTy);
 
       // Test Type->LLT conversion.
       Type *IRSTy = IntegerType::get(C, S);
       Type *IRTy = VectorType::get(IRSTy, Elts);
       EXPECT_EQ(VTy, getLLTForType(*IRTy, DL));
     }
   }
 }