[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

45–46

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

81–89

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);

253–260

I think this is approximately

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

which has added binary-search goodness.

275–277

I think the assertion would be reasonable.

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

45–46

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

81–89

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!

253–260

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.

275–277

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.

[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

45–46

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.

253–260

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

275–277

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

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

330

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

330

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

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
 #include "llvm/Target/TargetOpcodes.h"
 #include <cstdint>
 #include <cassert>
 #include <tuple>
 #include <utility>
+#include <map>
 
 namespace llvm {
 
 class MachineInstr;
 class MachineIRBuilder;
 class MachineRegisterInfo;
 
 /// Legalization is decided based on an instruction's opcode, which type slot
static bool NeedsLegalizingToDifferentSize(const LegalizeAction Action) {
     case MoreElements:
     case Unsupported:
       return true;
     default:
       return false;
     }
   }
 
+  typedef std::pair<uint16_t, LegalizeAction> SizeAndAction;
+  typedef std::vector<SizeAndAction> SizeAndActionsVec;
+  using SizeChangeStrategy =
+      std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;
+
   /// More friendly way to set an action for common types that have an LLT
   /// representation.
+  /// The LegalizeAction must be one for which NeedsLegalizingToDifferentSize
+  /// returns false.
   void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
+    assert(!NeedsLegalizingToDifferentSize(Action));
     TablesInitialized = false;
-    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;
+    const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
+    if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
+      SpecifiedActions[OpcodeIdx].resize(Aspect.Idx + 1);
+    SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
   }
 
-  /// 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;
+  /// The setAction calls record the non-size-changing legalization actions
+  /// to take on specificly-sized types. The SizeChangeStrategy defines what
+  /// to do when the size of the type needs to be changed to reach a legally
+  /// sized type (i.e., one that was defined through a setAction call).
+  /// e.g.
+  /// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
+  /// setLegalizeScalarToDifferentSizeStrategy(
+  ///   G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
+  /// will end up defining getAction({G_ADD, 0, T}) to return the following 
+  /// actions for different scalar types T:
+  ///  LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
+  ///  LLT::scalar(32):                 {Legal, 0, LLT::scalar(32)}
+  ///  LLT::scalar(33)..:               {NarrowScalar, 0, LLT::scalar(32)}
+  ///
+  /// If no SizeChangeAction gets defined, through this function,
+  /// the default is unsupportedForDifferentSizes.
+  void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,
+                                                const unsigned TypeIdx,
+                                                SizeChangeStrategy S) {
+    const unsigned OpcodeIdx = Opcode - FirstOp;
+    if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
+      ScalarSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
+    ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
+  }
+
+  /// See also setLegalizeScalarToDifferentSizeStrategy.
+  /// This function allows to set the SizeChangeStrategy for vector elements.
+  void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,
+                                                       const unsigned TypeIdx,
+                                                       SizeChangeStrategy S) {
+    const unsigned OpcodeIdx = Opcode - FirstOp;
+    if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
+      VectorElementSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
+    VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
+  }
+
+  /// A SizeChangeStrategy for the common case where legalization for a 
+  /// particular operation consists of only supporting a specific set of type
+  /// sizes. E.g.
+  ///   setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
+  ///   setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
+  ///   setLegalizeScalarToDifferentSizeStrategy(
+  ///     G_DIV, 0, unsupportedForDifferentSizes);
+  /// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
+  /// and Unsupported for all other scalar types T.
+  static SizeAndActionsVec
+  unsupportedForDifferentSizes(const SizeAndActionsVec &v) {
+    return increaseToLargerTypesAndDecreaseToLargest(v, Unsupported,
+                                                        Unsupported);
+  }
+
+  /// A SizeChangeStrategy 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.
+  static SizeAndActionsVec
+  widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
+    return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
+                                                        NarrowScalar);
+  }
+
+  static SizeAndActionsVec
+  widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) {
+    return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
+                                                        Unsupported);
+  }
+
+  static SizeAndActionsVec
+  narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) {
+    return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
+                                                          Unsupported);
   }
 
+  /// A SizeChangeStrategy 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.
+  ///   setAction({G_ADD, LLT::vector(8, 8)}, Legal);
+  ///   setAction({G_ADD, LLT::vector(16, 8)}, Legal);
+  ///   setAction({G_ADD, LLT::vector(2, 32)}, Legal);
+  ///   setAction({G_ADD, LLT::vector(4, 32)}, Legal);
+  ///   setLegalizeVectorElementToDifferentSizeStrategy(
+  ///     G_ADD, 0, moreToWiderTypesAndLessToWidest);
+  /// will result in the following getAction results:
+  ///   * getAction({G_ADD, LLT::vector(8,8)}) returns
+  ///       (Legal, vector(8,8)).
+  ///   * getAction({G_ADD, LLT::vector(9,8)}) returns
+  ///       (MoreElements, vector(16,8)).
+  ///   * getAction({G_ADD, LLT::vector(8,32)}) returns
+  ///       (FewerElements, vector(4,32)).
+  static SizeAndActionsVec
+  moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
+    return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
+                                                        FewerElements);
+  }
+
+  /// Helper function to implement many typical SizeChangeStrategy functions.
+  static SizeAndActionsVec
+  increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v,
+                                            LegalizeAction IncreaseAction,
+                                            LegalizeAction DecreaseAction);
+  /// Helper function to implement many typical SizeChangeStrategy functions.
+  static SizeAndActionsVec
+  decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v,
+                                              LegalizeAction DecreaseAction,
+                                              LegalizeAction IncreaseAction);
+
   /// Determine what action should be taken to legalize the given generic
   /// instruction opcode, type-index and type. Requires computeTables to have
   /// been called.
   ///
   /// \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;
 
   /// 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;
 
-  /// Iterate the given function (typically something like doubling the width)
-  /// on Ty until we find a legal type for this operation.
-  Optional<LLT> findLegalizableSize(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()) {
-        auto DefaultIt = DefaultActions.find(Aspect.Opcode);
-        if (DefaultIt == DefaultActions.end())
-          return None;
-        Action = DefaultIt->second;
-      } else
-        Action = ActionIt->second;
-    } while (NeedsLegalizingToDifferentSize(Action));
-    return Ty;
-  }
-
-  /// Find what type it's actually OK to perform the given operation on, given
-  /// the general approach we've decided to take.
-  Optional<LLT> findLegalType(const InstrAspect &Aspect, LegalizeAction Action) const;
-
-  std::pair<LegalizeAction, LLT> findLegalAction(const InstrAspect &Aspect,
-                                                 LegalizeAction Action) const {
-    auto LegalType = findLegalType(Aspect, Action);
-    if (!LegalType)
-      return std::make_pair(LegalizeAction::Unsupported, LLT());
-    return std::make_pair(Action, *LegalType);
-  }
-
-  /// 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 {
-    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 ActionIt->second;
-  }
-
   bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 
   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;
+  /// 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:
+  /// setScalarAction(G_ADD, 0,
+  ///           {{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:
+  /// setPointerAction(G_GEP, 0, LLT:pointer(1),
+  ///           {{1, Unsupported},  // bit sizes [ 1, 63[
+  ///            {64, Legal},       // bit sizes [64, 65[
+  ///            {65, Unsupported}, // bit sizes [65, +inf[
+  ///           });
+  void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
+                       const SizeAndActionsVec &SizeAndActions) {
+    const unsigned OpcodeIdx = Opcode - FirstOp;
+    SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
+    setActions(TypeIndex, Actions, SizeAndActions);
+  }
+  void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
+                        const unsigned AddressSpace,
+                        const SizeAndActionsVec &SizeAndActions) {
+    const unsigned OpcodeIdx = Opcode - FirstOp;
+    if (AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace) ==
+        AddrSpace2PointerActions[OpcodeIdx].end())
+      AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
+    SmallVector<SizeAndActionsVec, 1> &Actions =
+        AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second;
+    setActions(TypeIndex, Actions, SizeAndActions);
+  }
 
-  using TypeMap = DenseMap<LLT, LegalizeAction>;
-  using SIVActionMap = DenseMap<std::pair<unsigned, LLT>, LegalizeAction>;
+  /// 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(const unsigned Opcode, const unsigned TypeIndex,
+                               const SizeAndActionsVec &SizeAndActions) {
+    unsigned OpcodeIdx = Opcode - FirstOp;
+    SmallVector<SizeAndActionsVec, 1> &Actions =
+        ScalarInVectorActions[OpcodeIdx];
+    setActions(TypeIndex, Actions, SizeAndActions);
+  }
+
+  /// See also setScalarInVectorAction.
+  /// This function let's you specify the number of elements in a vector that
+  /// are legal for a legal element size.
+  void setVectorNumElementAction(const unsigned Opcode,
+                                 const unsigned TypeIndex,
+                                 const unsigned ElementSize,
+                                 const SizeAndActionsVec &SizeAndActions) {
+    const unsigned OpcodeIdx = Opcode - FirstOp;
+    if (NumElements2Actions[OpcodeIdx].find(ElementSize) ==
+        NumElements2Actions[OpcodeIdx].end())
+      NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
+    SmallVector<SizeAndActionsVec, 1> &Actions =
+        NumElements2Actions[OpcodeIdx].find(ElementSize)->second;
+    setActions(TypeIndex, Actions, SizeAndActions);
+  }
 
-  SmallVector<TypeMap, 1> Actions[LastOp - FirstOp + 1];
-  SIVActionMap ScalarInVectorActions;
-  DenseMap<std::pair<unsigned, LLT>, uint16_t> MaxLegalVectorElts;
-  DenseMap<unsigned, LegalizeAction> DefaultActions;
+  /// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
+  /// i.e. it's OK if it doesn't start from size 1.
+  static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
+#ifndef NDEBUG
+    // The sizes should be in increasing order
+    int prev_size = -1;
+    for(auto SizeAndAction: v) {
+      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<v.size(); ++i) {
+      switch (v[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
+  }
+
+  /// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
+  /// from size 1.
+  static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
+#ifndef NDEBUG
+    // Data structure invariant: The first bit size must be size 1.
+    assert(v.size() >= 1);
+    assert(v[0].first == 1);
+    checkPartialSizeAndActionsVector(v);
+#endif
+  }
+
+  /// Sets actions for all bit sizes on a particular generic opcode, type
+  /// index and scalar or pointer type.
+  void setActions(unsigned TypeIndex,
+                  SmallVector<SizeAndActionsVec, 1> &Actions,
+                  const SizeAndActionsVec &SizeAndActions) {
+    checkFullSizeAndActionsVector(SizeAndActions);
+    if (Actions.size() <= TypeIndex)
+      Actions.resize(TypeIndex + 1);
+    Actions[TypeIndex] = SizeAndActions;
+  }
+
+  static SizeAndAction findAction(const SizeAndActionsVec &Vec,
+                                  const uint32_t Size);
+
+  /// Returns the next action needed to get the scalar or pointer type closer
+  /// to being legal
+  /// E.g. findLegalAction({G_REM, 13}) should return
+  /// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
+  /// probably be called, which should return (Lower, 32).
+  /// This is assuming the setScalarAction on G_REM was something like:
+  /// setScalarAction(G_REM, 0,
+  ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
+  ///            {32, Lower},       // bit sizes [32, 33[
+  ///            {33, NarrowScalar} // bit sizes [65, +inf[
+  ///           });
+  std::pair<LegalizeAction, LLT>
+  findScalarLegalAction(const InstrAspect &Aspect) const;
+
+  /// Returns the next action needed towards legalizing the vector type.
+  std::pair<LegalizeAction, LLT>
+  findVectorLegalAction(const InstrAspect &Aspect) const;
+
+  static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
+  static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
 
-  bool TablesInitialized = false;
+  // Data structures used temporarily during construction of legality data:
+  typedef DenseMap<LLT, LegalizeAction> TypeMap;
+  SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
+  SmallVector<SizeChangeStrategy, 1>
+      ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
+  SmallVector<SizeChangeStrategy, 1>
+      VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
+  bool TablesInitialized;
+
+  // Data structures used by getAction:
+  SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
+  SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
+  std::map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
+      AddrSpace2PointerActions[LastOp - FirstOp + 1];
+  std::map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
+      NumElements2Actions[LastOp - FirstOp + 1];
 };
 
-} // end namespace llvm
+} // end namespace llvm.
 
 #endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H

include/llvm/Support/LowLevelTypeImpl.h

public:
   LLT getElementType() const {
     assert(isVector() && "cannot get element type of scalar/aggregate");
     if (IsPointer)
       return pointer(getAddressSpace(), getScalarSizeInBits());
     else
       return scalar(getScalarSizeInBits());
   }
 
-  /// 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{/*isPointer=*/false, IsVector ? true : false,
-               IsVector ? getNumElements() : (uint16_t)0,
-               getScalarSizeInBits() / 2, /*AddressSpace=*/0};
-  }
-
-  /// 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{/*isPointer=*/false, IsVector ? true : false,
-               IsVector ? getNumElements() : (uint16_t)0,
-               getScalarSizeInBits() * 2, /*AddressSpace=*/0};
-  }
-
-  /// 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() && getNumElements() % 2 == 0 && "cannot half odd vector");
-    if (getNumElements() == 2)
-      return scalar(getScalarSizeInBits());
-
-    return LLT{/*isPointer=*/false, /*isVector=*/true,
-               (uint16_t)(getNumElements() / 2), getScalarSizeInBits(),
-               /*AddressSpace=*/0};
-  }
-
-  /// 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 {
-    return LLT{IsPointer ? true : false, /*isVector=*/true,
-               (uint16_t)(getNumElements() * 2), getScalarSizeInBits(),
-               IsPointer ? getAddressSpace() : 0};
-  }
-
   void print(raw_ostream &OS) const;
 
   bool operator==(const LLT &RHS) const {
     return IsPointer == RHS.IsPointer && IsVector == RHS.IsVector &&
            RHS.RawData == RawData;
   }
 
   bool operator!=(const LLT &RHS) const { return !(*this == RHS); }

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

if (TypeIdx != 0 && MI.getOpcode() != TargetOpcode::G_EXTRACT)
     return UnableToLegalize;
 
   MIRBuilder.setInstr(MI);
 
   switch (MI.getOpcode()) {
   default:
     return UnableToLegalize;
   case TargetOpcode::G_ADD: {
+    unsigned Size = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
+    unsigned NarrowSize = NarrowTy.getSizeInBits();
+    // FIXME: add support for when Size isn't an exact multiple of NarrowSize.
+    if (Size % NarrowSize != 0)
+      return UnableToLegalize;
     // Expand in terms of carry-setting/consuming G_ADDE instructions.
-    int NumParts = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits() /
-                   NarrowTy.getSizeInBits();
+    int NumParts = Size / NarrowTy.getSizeInBits();
 
     SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
     extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
 
     unsigned CarryIn = MRI.createGenericVirtualRegister(LLT::scalar(1));
     MIRBuilder.buildConstant(CarryIn, 0);
 
for (int i = 0; i < NumParts; ++i) {
       DstRegs.push_back(SegReg);
     }
 
     MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
     MI.eraseFromParent();
     return Legalized;
   }
   case TargetOpcode::G_INSERT: {
-    if (TypeIdx != 0)
+    unsigned Size = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
+    int64_t NarrowSize = NarrowTy.getSizeInBits();
+    // FIXME: add support for when Size isn't an exact multiple of NarrowSize.
+    if (Size % NarrowSize != 0)
       return UnableToLegalize;
 
-    int64_t NarrowSize = NarrowTy.getSizeInBits();
-    int NumParts =
-        MRI.getType(MI.getOperand(0).getReg()).getSizeInBits() / NarrowSize;
+    int NumParts = Size / NarrowSize;
 
     SmallVector<unsigned, 2> SrcRegs, DstRegs;
     SmallVector<uint64_t, 2> Indexes;
     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, SrcRegs);
 
     unsigned OpReg = MI.getOperand(2).getReg();
     int64_t OpStart = MI.getOperand(3).getImm();
     int64_t OpSize = MRI.getType(OpReg).getSizeInBits();
case TargetOpcode::G_INSERT: {
     }
 
     assert(DstRegs.size() == (unsigned)NumParts && "not all parts covered");
     MIRBuilder.buildMerge(MI.getOperand(0).getReg(), DstRegs);
     MI.eraseFromParent();
     return Legalized;
   }
   case TargetOpcode::G_LOAD: {
+    unsigned Size = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
     unsigned NarrowSize = NarrowTy.getSizeInBits();
-    int NumParts =
-        MRI.getType(MI.getOperand(0).getReg()).getSizeInBits() / NarrowSize;
     LLT OffsetTy = LLT::scalar(
         MRI.getType(MI.getOperand(1).getReg()).getScalarSizeInBits());
+    // FIXME: add support for when Size isn't an exact multiple of NarrowSize.
+    if (Size % NarrowSize != 0)
+      return UnableToLegalize;
+
+    int NumParts = Size / NarrowSize;
 
     SmallVector<unsigned, 2> DstRegs;
     for (int i = 0; i < NumParts; ++i) {
       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
       unsigned SrcReg = 0;
       unsigned Adjustment = i * NarrowSize / 8;
 
       MIRBuilder.materializeGEP(SrcReg, MI.getOperand(1).getReg(), OffsetTy,
                                 Adjustment);
 
       // TODO: This is conservatively correct, but we probably want to split the
       // memory operands in the future.
       MIRBuilder.buildLoad(DstReg, SrcReg, **MI.memoperands_begin());
 
       DstRegs.push_back(DstReg);
     }
     unsigned DstReg = MI.getOperand(0).getReg();
     MIRBuilder.buildMerge(DstReg, DstRegs);
     MI.eraseFromParent();
     return Legalized;
   }
   case TargetOpcode::G_STORE: {
+    unsigned Size = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
     unsigned NarrowSize = NarrowTy.getSizeInBits();
-    int NumParts =
-        MRI.getType(MI.getOperand(0).getReg()).getSizeInBits() / NarrowSize;
     LLT OffsetTy = LLT::scalar(
         MRI.getType(MI.getOperand(1).getReg()).getScalarSizeInBits());
+    // FIXME: add support for when Size isn't an exact multiple of NarrowSize.
+    if (Size % NarrowSize != 0)
+      return UnableToLegalize;
+    int NumParts = Size / NarrowSize;
 
     SmallVector<unsigned, 2> SrcRegs;
     extractParts(MI.getOperand(0).getReg(), NarrowTy, NumParts, SrcRegs);
 
     for (int i = 0; i < NumParts; ++i) {
       unsigned DstReg = 0;
       unsigned Adjustment = i * NarrowSize / 8;
 
       MIRBuilder.materializeGEP(DstReg, MI.getOperand(1).getReg(), OffsetTy,
                                 Adjustment);
 
       // TODO: This is conservatively correct, but we probably want to split the
       // memory operands in the future.
       MIRBuilder.buildStore(SrcRegs[i], DstReg, **MI.memoperands_begin());
     }
     MI.eraseFromParent();
     return Legalized;
   }
   case TargetOpcode::G_CONSTANT: {
+    unsigned Size = MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
     unsigned NarrowSize = NarrowTy.getSizeInBits();
-    int NumParts =
-        MRI.getType(MI.getOperand(0).getReg()).getSizeInBits() / NarrowSize;
+    // FIXME: add support for when Size isn't an exact multiple of NarrowSize.
+    if (Size % NarrowSize != 0)
+      return UnableToLegalize;
+    int NumParts = Size / NarrowSize;
     const APInt &Cst = MI.getOperand(1).getCImm()->getValue();
     LLVMContext &Ctx = MIRBuilder.getMF().getFunction()->getContext();
 
     SmallVector<unsigned, 2> DstRegs;
     for (int i = 0; i < NumParts; ++i) {
       unsigned DstReg = MRI.createGenericVirtualRegister(NarrowTy);
       ConstantInt *CI =
           ConstantInt::get(Ctx, Cst.lshr(NarrowSize * i).trunc(NarrowSize));
LegalizerHelper::fewerElementsVector(MachineInstr &MI, unsigned TypeIdx,
   if (TypeIdx != 0)
     return UnableToLegalize;
   switch (MI.getOpcode()) {
   default:
     return UnableToLegalize;
   case TargetOpcode::G_ADD: {
     unsigned NarrowSize = NarrowTy.getSizeInBits();
     unsigned DstReg = MI.getOperand(0).getReg();
-    int NumParts = MRI.getType(DstReg).getSizeInBits() / NarrowSize;
+    unsigned Size = MRI.getType(DstReg).getSizeInBits();
+    int NumParts = Size / NarrowSize;
+    // FIXME: Don't know how to handle the situation where the small vectors
+    // aren't all the same size yet.
+    if (Size % NarrowSize != 0)
+      return UnableToLegalize;
 
     MIRBuilder.setInstr(MI);
 
     SmallVector<unsigned, 2> Src1Regs, Src2Regs, DstRegs;
     extractParts(MI.getOperand(1).getReg(), NarrowTy, NumParts, Src1Regs);
     extractParts(MI.getOperand(2).getReg(), NarrowTy, NumParts, Src2Regs);
 
     for (int i = 0; i < NumParts; ++i) {

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/MC/MCInstrDesc.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetOpcodes.h"
 #include <algorithm>
-#include <cassert>
-#include <tuple>
-#include <utility>
-
+#include <map>
 using namespace llvm;
 
-LegalizerInfo::LegalizerInfo() {
-  // 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_EXTRACT] = NarrowScalar;
-  DefaultActions[TargetOpcode::G_FNEG] = Lower;
+LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
+  // Set defaults.
+  setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
+  setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
+  setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
+  setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
+  setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
+
+  setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
+  setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
+
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_ADD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
+
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
+  setScalarAction(TargetOpcode::G_FNEG, 0, {{1, 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;
+  assert(TablesInitialized == false);
 
-        auto &Entry = MaxLegalVectorElts[std::make_pair(Opcode + FirstOp,
-                                                        Ty.getElementType())];
-        Entry = std::max(Entry, Ty.getNumElements());
-      }
+  for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
+    const unsigned Opcode = FirstOp + OpcodeIdx;
+    for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
+         ++TypeIdx) {
+      // 0. Collect information specified through the setAction API, i.e.
+      // for specific bit sizes.
+      // For scalar types:
+      SizeAndActionsVec ScalarSpecifiedActions;
+      // For pointer types:
+      std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
+      // For vector types:
+      std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
+      for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
+        const LLT Type = LLT2Action.first;
+        const LegalizeAction Action = LLT2Action.second;
+        SizeAndActionsVec &v =
+            Type.isPointer()
+                ? AddressSpace2SpecifiedActions[Type.getAddressSpace()]
+                : Type.isVector()
+                      ? ElemSize2SpecifiedActions[Type.getElementType()
+                                                      .getSizeInBits()]
+
+                      : ScalarSpecifiedActions;
+        v.push_back({Type.getSizeInBits(), Action});
+      }
+
+      // 1. Handle scalar types
+      {
+        // Decide how to handle bit sizes for which no explicit specification
+        // was given.
+        SizeChangeStrategy S = &unsupportedForDifferentSizes;
+        if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
+            ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
+          S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
+        std::sort(ScalarSpecifiedActions.begin(), ScalarSpecifiedActions.end());
+        checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
+        setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
+      }
+
+      // 2. Handle pointer types
+      for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
+        std::sort(PointerSpecifiedActions.second.begin(),
+                  PointerSpecifiedActions.second.end());
+        checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
+        // For pointer types, we assume that there isn't a meaningfull way
+        // to change the number of bits used in the pointer.
+        setPointerAction(
+            Opcode, TypeIdx, PointerSpecifiedActions.first,
+            unsupportedForDifferentSizes(PointerSpecifiedActions.second));
+      }
+
+      // 3. Handle vector types
+      SizeAndActionsVec ElementSizesSeen;
+      for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
+        std::sort(VectorSpecifiedActions.second.begin(),
+                  VectorSpecifiedActions.second.end());
+        const uint16_t ElementSize = VectorSpecifiedActions.first;
+        ElementSizesSeen.push_back({ElementSize, Legal});
+        checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
+        // For vector types, we assume that the best way to adapt the number
+        // of elements is to the next larger number of elements type for which
+        // the vector type is legal, unless there is no such type. In that case,
+        // legalize towards a vector type with a smaller number of elements.
+        SizeAndActionsVec NumElementsActions;
+        for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
+          assert(BitsizeAndAction.first % ElementSize == 0);
+          const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
+          NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
+        }
+        setVectorNumElementAction(
+            Opcode, TypeIdx, ElementSize,
+            moreToWiderTypesAndLessToWidest(NumElementsActions));
+      }
+      std::sort(ElementSizesSeen.begin(), ElementSizesSeen.end());
+      SizeChangeStrategy VectorElementSizeChangeStrategy =
+          &unsupportedForDifferentSizes;
+      if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
+          VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
+        VectorElementSizeChangeStrategy =
+            VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
+      setScalarInVectorAction(
+          Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
     }
   }
 
   TablesInitialized = true;
 }
 
 // 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::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.
 
   // FIXME: the long-term plan calls for expansion in terms of load/store (if
   // they're not legal).
   if (Aspect.Opcode == TargetOpcode::G_MERGE_VALUES ||
       Aspect.Opcode == TargetOpcode::G_UNMERGE_VALUES)
     return std::make_pair(Legal, Aspect.Type);
 
-  LLT Ty = Aspect.Type;
-  LegalizeAction Action = findInActions(Aspect);
-  // LegalizerHelper is not able to handle non-power-of-2 types right now, so do
-  // not try to legalize them unless they are marked as Legal or Custom.
-  // FIXME: This is a temporary hack until the general non-power-of-2
-  // legalization works.
-  if (!isPowerOf2_64(Ty.getSizeInBits()) &&
-      !(Action == Legal || Action == Custom))
-    return std::make_pair(Unsupported, LLT());
-
-  if (Action != NotFound)
-    return findLegalAction(Aspect, Action);
-
-  unsigned Opcode = Aspect.Opcode;
-  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);
-  }
-
-  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);
+  if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
+    return findScalarLegalAction(Aspect);
+  assert(Aspect.Type.isVector());
+  return findVectorLegalAction(Aspect);
 }
 
 std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
 LegalizerInfo::getAction(const MachineInstr &MI,
                          const MachineRegisterInfo &MRI) const {
   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);
   }
   return std::make_tuple(Legal, 0, LLT{});
 }
 
 bool LegalizerInfo::isLegal(const MachineInstr &MI,
                             const MachineRegisterInfo &MRI) const {
   return std::get<0>(getAction(MI, MRI)) == Legal;
 }
 
-Optional<LLT> LegalizerInfo::findLegalType(const InstrAspect &Aspect,
-                                 LegalizeAction Action) const {
-  switch(Action) {
-  default:
-    llvm_unreachable("Cannot find legal type");
+bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
+                                   MachineIRBuilder &MIRBuilder) const {
+  return false;
+}
+
+LegalizerInfo::SizeAndActionsVec
+LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
+    const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
+    LegalizeAction DecreaseAction) {
+  SizeAndActionsVec result;
+  unsigned LargestSizeSoFar = 0;
+  if (v.size() >= 1 && v[0].first != 1)
+    result.push_back({1, IncreaseAction});
+  for (size_t i = 0; i < v.size(); ++i) {
+    result.push_back(v[i]);
+    LargestSizeSoFar = v[i].first;
+    if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
+      result.push_back({LargestSizeSoFar + 1, IncreaseAction});
+      LargestSizeSoFar = v[i].first + 1;
+    }
+  }
+  result.push_back({LargestSizeSoFar + 1, DecreaseAction});
+  return result;
+}
+
+LegalizerInfo::SizeAndActionsVec
+LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
+    const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
+    LegalizeAction IncreaseAction) {
+  SizeAndActionsVec result;
+  if (v.size() == 0 || v[0].first != 1)
+    result.push_back({1, IncreaseAction});
+  for (size_t i = 0; i < v.size(); ++i) {
+    result.push_back(v[i]);
+    if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
+      result.push_back({v[i].first + 1, DecreaseAction});
+    }
+  }
+  return result;
+}
+
+LegalizerInfo::SizeAndAction
+LegalizerInfo::findAction(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.
+  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 Aspect.Type;
-  case NarrowScalar: {
-    return findLegalizableSize(
-        Aspect, [&](LLT Ty) -> LLT { return Ty.halfScalarSize(); });
-  }
-  case WidenScalar: {
-    return findLegalizableSize(Aspect, [&](LLT Ty) -> LLT {
-      return Ty.getSizeInBits() < 8 ? LLT::scalar(8) : Ty.doubleScalarSize();
-    });
-  }
-  case FewerElements: {
-    return findLegalizableSize(
-        Aspect, [&](LLT Ty) -> LLT { return Ty.halfElements(); });
-  }
-  case MoreElements: {
-    return findLegalizableSize(
-        Aspect, [&](LLT Ty) -> LLT { return Ty.doubleElements(); });
+    return {Size, Action};
+  case FewerElements:
+    // FIXME: is this special case still needed and correct?
+    // Special case for scalarization:
+    if (Vec == SizeAndActionsVec({{1, FewerElements}}))
+      return {1, FewerElements};
+  case NarrowScalar:
+    // FIXME: do we really need a loop here? Or could we assert at construction
+    // time that there cannot be 2 consecutive actions in a SizeAndActionsVec
+    // for which NeedsLegalizingToDifferentSize() is true.
+    for (int i = VecIdx - 1; i >= 0; --i)
+      if (!NeedsLegalizingToDifferentSize(Vec[i].second))
+        return {Vec[i].first, Action};
+    llvm_unreachable("");
+  case WidenScalar:
+  case MoreElements:
+    // FIXME: do we really need a loop here?
+    for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
+      if (!NeedsLegalizingToDifferentSize(Vec[i].second))
+        return {Vec[i].first, Action};
+    llvm_unreachable("");
+  case Unsupported:
+    return {Size, Unsupported};
+  case NotFound:
+    llvm_unreachable("NotFound");
   }
-  }
+
+std::pair<LegalizerInfo::LegalizeAction, LLT>
+LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
+  assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
+  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
+    return {NotFound, LLT()};
+  const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
+  if (Aspect.Type.isPointer() &&
+      AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
+          AddrSpace2PointerActions[OpcodeIdx].end()) {
+    return {NotFound, LLT()};
+  }
+  const SmallVector<SizeAndActionsVec, 1> &Actions =
+      Aspect.Type.isPointer()
+          ? AddrSpace2PointerActions[OpcodeIdx]
+                .find(Aspect.Type.getAddressSpace())
+                ->second
+          : ScalarActions[OpcodeIdx];
+  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?
+  auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
+  return {SizeAndAction.second,
+          Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
+                                 : LLT::pointer(Aspect.Type.getAddressSpace(),
+                                                SizeAndAction.first)};
 }
 
-bool LegalizerInfo::legalizeCustom(MachineInstr &MI,
-                                   MachineRegisterInfo &MRI,
-                                   MachineIRBuilder &MIRBuilder) const {
-  return false;
+std::pair<LegalizerInfo::LegalizeAction, LLT>
+LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
+  assert(Aspect.Type.isVector());
+  // First legalize the vector element size, then legalize the number of
+  // lanes in the vector.
+  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
+    return {NotFound, Aspect.Type};
+  const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
+  const unsigned TypeIdx = Aspect.Idx;
+  if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
+    return {NotFound, Aspect.Type};
+  const SizeAndActionsVec &ElemSizeVec =
+      ScalarInVectorActions[OpcodeIdx][TypeIdx];
+
+  LLT IntermediateType;
+  auto ElementSizeAndAction =
+      findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
+  IntermediateType =
+      LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
+  if (ElementSizeAndAction.second != Legal)
+    return {ElementSizeAndAction.second, IntermediateType};
+
+  auto i = NumElements2Actions[OpcodeIdx].find(
+      IntermediateType.getScalarSizeInBits());
+  if (i == NumElements2Actions[OpcodeIdx].end()) {
+    return {NotFound, IntermediateType};
+  }
+  const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
+  auto NumElementsAndAction =
+      findAction(NumElementsVec, IntermediateType.getNumElements());
+  return {NumElementsAndAction.second,
+          LLT::vector(NumElementsAndAction.first,
+                      IntermediateType.getScalarSizeInBits())};
 }

lib/Support/LowLevelType.cpp

void LLT::print(raw_ostream &OS) const {
   if (isVector())
     OS << "<" << getNumElements() << " x " << getElementType() << ">";
   else if (isPointer())
     OS << "p" << getAddressSpace();
   else if (isValid()) {
     assert(isScalar() && "unexpected type");
     OS << "s" << getScalarSizeInBits();
   } else
-    llvm_unreachable("trying to print an invalid type");
+    OS << "LLT_invalid";
 }
 
 const constexpr LLT::BitFieldInfo LLT::ScalarSizeFieldInfo;
 const constexpr LLT::BitFieldInfo LLT::PointerSizeFieldInfo;
 const constexpr LLT::BitFieldInfo LLT::PointerAddressSpaceFieldInfo;
 const constexpr LLT::BitFieldInfo LLT::VectorElementsFieldInfo;
 const constexpr LLT::BitFieldInfo LLT::VectorSizeFieldInfo;
 const constexpr LLT::BitFieldInfo LLT::PointerVectorElementsFieldInfo;
 const constexpr LLT::BitFieldInfo LLT::PointerVectorSizeFieldInfo;
 const constexpr LLT::BitFieldInfo LLT::PointerVectorAddressSpaceFieldInfo;

lib/Target/AArch64/AArch64LegalizerInfo.cpp

 #include "llvm/Target/TargetOpcodes.h"
 
 using namespace llvm;
 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
+
+/// FIXME: The following static functions are SizeChangeStrategy functions
+/// that are meant to temporarily mimic the behaviour of the old legalization
+/// based on doubling/halving non-legal types as closely as possible. This is
+/// not entirly possible as only legalizing the types that are exactly a power
+/// of 2 times the size of the legal types would require specifying all those
+/// sizes explicitly.
+/// In practice, not specifying those  isn't a problem, and the below functions
+/// should disappear quickly as we add support for legalizing non-power-of-2
+/// sized types further.
+static void
+addAndInterleaveWithUnsupported(LegalizerInfo::SizeAndActionsVec &result,
+                                const LegalizerInfo::SizeAndActionsVec &v) {
+  for (unsigned i = 0; i < v.size(); ++i) {
+    result.push_back(v[i]);
+    if (i + 1 < v[i].first && i + 1 < v.size() &&
+        v[i + 1].first != v[i].first + 1)
+      result.push_back({v[i].first + 1, LegalizerInfo::Unsupported});
+  }
+}
+
+static LegalizerInfo::SizeAndActionsVec
+widen_1_narrow_128_ToLargest(const LegalizerInfo::SizeAndActionsVec &v) {
+  assert(v.size() >= 1);
+  assert(v[0].first > 2);
+  LegalizerInfo::SizeAndActionsVec result = {{1, LegalizerInfo::WidenScalar},
+                                             {2, LegalizerInfo::Unsupported}};
+  addAndInterleaveWithUnsupported(result, v);
+  auto Largest = result.back().first;
+  assert(Largest + 1 < 128);
+  result.push_back({Largest + 1, LegalizerInfo::Unsupported});
+  result.push_back({128, LegalizerInfo::NarrowScalar});
+  result.push_back({129, LegalizerInfo::Unsupported});
+  return result;
+}
+
+static LegalizerInfo::SizeAndActionsVec
+widen_16(const LegalizerInfo::SizeAndActionsVec &v) {
+  assert(v.size() >= 1);
+  assert(v[0].first > 17);
+  LegalizerInfo::SizeAndActionsVec result = {{1, LegalizerInfo::Unsupported},
+                                             {16, LegalizerInfo::WidenScalar},
+                                             {17, LegalizerInfo::Unsupported}};
+  addAndInterleaveWithUnsupported(result, v);
+  auto Largest = result.back().first;
+  result.push_back({Largest + 1, LegalizerInfo::Unsupported});
+  return result;
+}
+
+static LegalizerInfo::SizeAndActionsVec
+widen_1_8_16(const LegalizerInfo::SizeAndActionsVec &v) {
+  assert(v.size() >= 1);
+  assert(v[0].first > 17);
+  LegalizerInfo::SizeAndActionsVec result = {
+      {1, LegalizerInfo::WidenScalar},  {2, LegalizerInfo::Unsupported},
+      {8, LegalizerInfo::WidenScalar},  {9, LegalizerInfo::Unsupported},
+      {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported}};
+  addAndInterleaveWithUnsupported(result, v);
+  auto Largest = result.back().first;
+  result.push_back({Largest + 1, LegalizerInfo::Unsupported});
+  return result;
+}
+
+static LegalizerInfo::SizeAndActionsVec
+widen_1_8_16_narrowToLargest(const LegalizerInfo::SizeAndActionsVec &v) {
+  assert(v.size() >= 1);
+  assert(v[0].first > 17);
+  LegalizerInfo::SizeAndActionsVec result = {
+      {1, LegalizerInfo::WidenScalar},  {2, LegalizerInfo::Unsupported},
+      {8, LegalizerInfo::WidenScalar},  {9, LegalizerInfo::Unsupported},
+      {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported}};
+  addAndInterleaveWithUnsupported(result, v);
+  auto Largest = result.back().first;
+  result.push_back({Largest + 1, LegalizerInfo::NarrowScalar});
+  return result;
+}
+
+static LegalizerInfo::SizeAndActionsVec
+widen_1_8_16_narrowLarger(const LegalizerInfo::SizeAndActionsVec &v) {
+  assert(v.size() >= 1);
+  assert(v[0].first > 17);
+  LegalizerInfo::SizeAndActionsVec result = {
+      {1, LegalizerInfo::WidenScalar},  {2, LegalizerInfo::Unsupported},
+      {8, LegalizerInfo::WidenScalar},  {9, LegalizerInfo::Unsupported},
+      {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported}};
+  addAndInterleaveWithUnsupported(result, v);
+  auto Largest = result.back().first;
+  result.push_back({Largest + 1, LegalizerInfo::NarrowScalar});
+  return result;
+}
+
+static LegalizerInfo::SizeAndActionsVec
+widen_1_8_16_32(const LegalizerInfo::SizeAndActionsVec &v) {
+  assert(v.size() >= 1);
+  assert(v[0].first > 33);
+  LegalizerInfo::SizeAndActionsVec result = {
+      {1, LegalizerInfo::WidenScalar},  {2, LegalizerInfo::Unsupported},
+      {8, LegalizerInfo::WidenScalar},  {9, LegalizerInfo::Unsupported},
+      {16, LegalizerInfo::WidenScalar}, {17, LegalizerInfo::Unsupported},
+      {32, LegalizerInfo::WidenScalar}, {33, LegalizerInfo::Unsupported}};
+  addAndInterleaveWithUnsupported(result, v);
+  auto Largest = result.back().first;
+  result.push_back({Largest + 1, LegalizerInfo::Unsupported});
+  return result;
+}
+
 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);
 
   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);
+    setLegalizeScalarToDifferentSizeStrategy(BinOp, 0,
+                                             widen_1_8_16_narrowLarger);
   }
 
   setAction({G_GEP, p0}, Legal);
   setAction({G_GEP, 1, s64}, Legal);
 
-  for (auto Ty : {s1, s8, s16, s32})
-    setAction({G_GEP, 1, Ty}, WidenScalar);
+  setLegalizeScalarToDifferentSizeStrategy(G_GEP, 1, widen_1_8_16_32);
 
   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);
+    setLegalizeScalarToDifferentSizeStrategy(BinOp, 0, widen_1_8_16);
   }
 
   for (unsigned BinOp : {G_SREM, G_UREM})
     for (auto Ty : { s1, s8, s16, s32, s64 })
       setAction({BinOp, Ty}, Lower);
 
-  for (unsigned Op : {G_SMULO, G_UMULO})
-      setAction({Op, s64}, Lower);
+  for (unsigned Op : {G_SMULO, G_UMULO}) {
+    setAction({Op, 0, s64}, Lower);
+    setAction({Op, 1, s1}, Legal);
+  }
 
   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);
   }
 
   for (unsigned BinOp : {G_FADD, G_FSUB, G_FMUL, G_FDIV})
     for (auto Ty : {s32, s64})
       setAction({BinOp, Ty}, Legal);
 
   for (unsigned BinOp : {G_FREM, G_FPOW}) {
     setAction({BinOp, s32}, Libcall);
     setAction({BinOp, s64}, Libcall);
   }
 
   for (auto Ty : {s32, s64, p0}) {
     setAction({G_INSERT, Ty}, Legal);
     setAction({G_INSERT, 1, Ty}, Legal);
   }
+  setLegalizeScalarToDifferentSizeStrategy(G_INSERT, 0,
+                                           widen_1_8_16_narrowToLargest);
   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).
   }
 
   for (auto Ty : {s1, s8, s16, s32, s64, p0})
     setAction({G_EXTRACT, Ty}, Legal);
 
   for (auto Ty : {s32, s64})
     setAction({G_EXTRACT, 1, Ty}, Legal);
 
   for (unsigned MemOp : {G_LOAD, G_STORE}) {
     for (auto Ty : {s8, s16, s32, s64, p0, v2s32})
       setAction({MemOp, Ty}, Legal);
 
-    setAction({MemOp, s1}, WidenScalar);
+    setLegalizeScalarToDifferentSizeStrategy(MemOp, 0,
+                                             widen_1_narrow_128_ToLargest);
 
     // And everything's fine in addrspace 0.
     setAction({MemOp, 1, p0}, Legal);
   }
 
   // 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);
+  setLegalizeScalarToDifferentSizeStrategy(G_CONSTANT, 0, widen_1_8_16);
+  setLegalizeScalarToDifferentSizeStrategy(G_FCONSTANT, 0, widen_16);
 
   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);
-  }
+  setLegalizeScalarToDifferentSizeStrategy(G_ICMP, 1, widen_1_8_16);
 
   setAction({G_FCMP, s1}, Legal);
   setAction({G_FCMP, 1, s32}, Legal);
   setAction({G_FCMP, 1, s64}, Legal);
 
   // 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);
-  }
-
   setAction({G_FPEXT, s64}, Legal);
   setAction({G_FPEXT, 1, s32}, Legal);
 
   // 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);
-
   // 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);
-  }
+  setLegalizeScalarToDifferentSizeStrategy(G_FPTOSI, 0, widen_1_8_16);
+  setLegalizeScalarToDifferentSizeStrategy(G_FPTOUI, 0, widen_1_8_16);
+  setLegalizeScalarToDifferentSizeStrategy(G_SITOFP, 1, widen_1_8_16);
+  setLegalizeScalarToDifferentSizeStrategy(G_UITOFP, 1, widen_1_8_16);
 
   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);
   }
 
   // Control-flow
   for (auto Ty : {s1, s8, s16, s32})
     setAction({G_BRCOND, Ty}, Legal);
   setAction({G_BRINDIRECT, p0}, Legal);
 
   // Select
-  for (auto Ty : {s1, s8, s16})
-    setAction({G_SELECT, Ty}, WidenScalar);
+  setLegalizeScalarToDifferentSizeStrategy(G_SELECT, 0, widen_1_8_16);
 
   for (auto Ty : {s32, s64, p0})
     setAction({G_SELECT, Ty}, Legal);
 
   setAction({G_SELECT, 1, s1}, Legal);
 
   // Pointer-handling
   setAction({G_FRAME_INDEX, p0}, Legal);

lib/Target/ARM/ARMLegalizerInfo.cpp

ARMLegalizerInfo::ARMLegalizerInfo(const ARMSubtarget &ST) {
 
   for (unsigned Op : {G_LOAD, G_STORE}) {
     for (auto Ty : {s1, s8, s16, s32, p0})
       setAction({Op, Ty}, Legal);
     setAction({Op, 1, p0}, Legal);
   }
 
   for (unsigned Op : {G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR}) {
-    for (auto Ty : {s1, s8, s16})
-      setAction({Op, Ty}, WidenScalar);
+    setLegalizeScalarToDifferentSizeStrategy(Op, 0,
+        widenToLargerTypesUnsupportedOtherwise);
     setAction({Op, s32}, Legal);
   }
 
   for (unsigned Op : {G_SDIV, G_UDIV}) {
-    for (auto Ty : {s8, s16})
-      setAction({Op, Ty}, WidenScalar);
+    setLegalizeScalarToDifferentSizeStrategy(Op, 0,
+        widenToLargerTypesUnsupportedOtherwise);
     if (ST.hasDivideInARMMode())
       setAction({Op, s32}, Legal);
     else
       setAction({Op, s32}, Libcall);
   }
 
   // FIXME: Support s8 and s16 as well
   for (unsigned Op : {G_SREM, G_UREM})
     if (ST.hasDivideInARMMode())
       setAction({Op, s32}, Lower);
     else if (ST.isTargetAEABI() || ST.isTargetGNUAEABI() ||
              ST.isTargetMuslAEABI())
       setAction({Op, s32}, Custom);
     else
       setAction({Op, s32}, Libcall);
 
-  for (unsigned Op : {G_SEXT, G_ZEXT}) {
+  for (unsigned Op : {G_SEXT, G_ZEXT, G_ANYEXT}) {
     setAction({Op, s32}, Legal);
-    for (auto Ty : {s1, s8, s16})
-      setAction({Op, 1, Ty}, Legal);
   }
 
   setAction({G_GEP, p0}, Legal);
   setAction({G_GEP, 1, s32}, Legal);
 
   setAction({G_SELECT, s32}, Legal);
   setAction({G_SELECT, p0}, Legal);
   setAction({G_SELECT, 1, s1}, Legal);
 
   setAction({G_CONSTANT, s32}, Legal);
 
   setAction({G_ICMP, s1}, Legal);
-  for (auto Ty : {s8, s16})
-    setAction({G_ICMP, 1, Ty}, WidenScalar);
+  setLegalizeScalarToDifferentSizeStrategy(G_ICMP, 1,
+      widenToLargerTypesUnsupportedOtherwise);
   for (auto Ty : {s32, p0})
     setAction({G_ICMP, 1, Ty}, Legal);
 
   if (!ST.useSoftFloat() && ST.hasVFP2()) {
     setAction({G_FADD, s32}, Legal);
     setAction({G_FADD, s64}, Legal);
 
     setAction({G_LOAD, s64}, Legal);

lib/Target/X86/X86LegalizerInfo.cpp

void X86LegalizerInfo::setLegalizerInfo32bit() {
   if (Subtarget.is64Bit())
     return;
 
   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);
 
   for (unsigned BinOp : {G_ADD, G_SUB, G_MUL})
     for (auto Ty : {s8, s16, s32})
       setAction({BinOp, Ty}, Legal);
 
   for (unsigned Op : {G_UADDE}) {
     setAction({Op, s32}, Legal);
     setAction({Op, 1, s1}, Legal);
   }
 
   for (unsigned MemOp : {G_LOAD, G_STORE}) {
     for (auto Ty : {s8, s16, s32, p0})
       setAction({MemOp, Ty}, Legal);
 
     // And everything's fine in addrspace 0.
     setAction({MemOp, 1, p0}, Legal);
   }
 
   // Pointer-handling
   setAction({G_FRAME_INDEX, p0}, Legal);
 
   setAction({G_GEP, p0}, Legal);
   setAction({G_GEP, 1, s32}, Legal);
 
-  for (auto Ty : {s1, s8, s16})
-    setAction({G_GEP, 1, Ty}, WidenScalar);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_GEP, 1, widenToLargerTypesUnsupportedOtherwise);
 
   // Constants
   for (auto Ty : {s8, s16, s32, p0})
     setAction({TargetOpcode::G_CONSTANT, Ty}, Legal);
 
-  setAction({TargetOpcode::G_CONSTANT, s1}, WidenScalar);
-  setAction({TargetOpcode::G_CONSTANT, s64}, NarrowScalar);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_CONSTANT, 0, widenToLargerTypesAndNarrowToLargest);
 
   // Extensions
   setAction({G_ZEXT, s32}, Legal);
   setAction({G_SEXT, s32}, Legal);
 
-  for (auto Ty : {s1, s8, s16}) {
-    setAction({G_ZEXT, 1, Ty}, Legal);
-    setAction({G_SEXT, 1, Ty}, Legal);
-  }
-
   // Comparison
   setAction({G_ICMP, s1}, Legal);
 
   for (auto Ty : {s8, s16, s32, p0})
     setAction({G_ICMP, 1, Ty}, Legal);
 }
 
 void X86LegalizerInfo::setLegalizerInfo64bit() {
void X86LegalizerInfo::setLegalizerInfo64bit() {
 
   // Pointer-handling
   setAction({G_FRAME_INDEX, p0}, Legal);
 
   setAction({G_GEP, p0}, Legal);
   setAction({G_GEP, 1, s32}, Legal);
   setAction({G_GEP, 1, s64}, Legal);
 
-  for (auto Ty : {s1, s8, s16})
-    setAction({G_GEP, 1, Ty}, WidenScalar);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_GEP, 1, widenToLargerTypesUnsupportedOtherwise);
 
   // Constants
   for (auto Ty : {s8, s16, s32, s64, p0})
     setAction({TargetOpcode::G_CONSTANT, Ty}, Legal);
 
-  setAction({TargetOpcode::G_CONSTANT, s1}, WidenScalar);
+  setLegalizeScalarToDifferentSizeStrategy(
+      TargetOpcode::G_CONSTANT, 0, widenToLargerTypesAndNarrowToLargest);
 
   // Extensions
   for (auto Ty : {s32, s64}) {
     setAction({G_ZEXT, Ty}, Legal);
     setAction({G_SEXT, Ty}, Legal);
   }
 
-  for (auto Ty : {s1, s8, s16, s32}) {
-    setAction({G_ZEXT, 1, Ty}, Legal);
-    setAction({G_SEXT, 1, Ty}, Legal);
-  }
-
   // Comparison
   setAction({G_ICMP, s1}, Legal);
 
   for (auto Ty : {s8, s16, s32, s64, p0})
     setAction({G_ICMP, 1, Ty}, Legal);
 }
 
 void X86LegalizerInfo::setLegalizerInfoSSE1() {

test/CodeGen/AArch64/GlobalISel/arm64-fallback.ll

 
 ; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg0<def>(<2 x p0>) = G_INSERT_VECTOR_ELT %vreg1, %vreg2, %vreg3; (in function: vector_of_pointers_insertelement
 ; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for vector_of_pointers_insertelement
 ; FALLBACK-WITH-REPORT-OUT-LABEL: vector_of_pointers_insertelement:
 define void @vector_of_pointers_insertelement() {
   %dummy = insertelement <2 x i16*> undef, i16* null, i32 0
   ret void
 }
+
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg1<def>(s96) = G_INSERT %vreg2, %vreg0, 0; (in function: nonpow2_insertvalue_narrowing
+; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_insertvalue_narrowing
+; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_insertvalue_narrowing:
+%struct96 = type { float, float, float }
+define void @nonpow2_insertvalue_narrowing(float %a) {
+  %dummy = insertvalue %struct96 undef, float %a, 0
+  ret void
+}
+
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg1<def>(s96) = G_ADD %vreg0, %vreg0; (in function: nonpow2_add_narrowing
+; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_add_narrowing
+; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_add_narrowing:
+define void @nonpow2_add_narrowing() {
+  %dummy = add i96 undef, undef
+  ret void
+}
+
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg0<def>(s96) = G_LOAD %vreg1; mem:LD12[undef](align=16) (in function: nonpow2_load_narrowing
+; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_load_narrowing
+; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_load_narrowing:
+define void @nonpow2_load_narrowing() {
+  %dummy = load i96, i96* undef
+  ret void
+}
+
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: G_STORE %vreg0, %vreg1; mem:ST12[undef](align=16) (in function: nonpow2_store_narrowing
+; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_store_narrowing
+; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_store_narrowing:
+define void @nonpow2_store_narrowing() {
+  store i96 undef, i96* undef
+  ret void
+}
+
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg0<def>(s96) = G_CONSTANT 0; (in function: nonpow2_constant_narrowing
+; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_constant_narrowing
+; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_constant_narrowing:
+define void @nonpow2_constant_narrowing() {
+  store i96 0, i96* undef
+  ret void
+}
+
+; Currently can't handle vector lengths that aren't an exact multiple of
+; natively supported vector lengths. Test that the fall-back works for those.
+; FALLBACK-WITH-REPORT-ERR: remark: <unknown>:0:0: unable to legalize instruction: %vreg1<def>(<7 x s64>) = G_ADD %vreg0, %vreg0; (in function: nonpow2_vector_add_fewerelements
+; FALLBACK-WITH-REPORT-ERR: warning: Instruction selection used fallback path for nonpow2_vector_add_fewerelements
+; FALLBACK-WITH-REPORT-OUT-LABEL: nonpow2_vector_add_fewerelements:
+define void @nonpow2_vector_add_fewerelements() {
+  %dummy = add <7 x i64> undef, undef
+  ret void
+}

test/CodeGen/AArch64/GlobalISel/legalize-add.mir

 # RUN: llc -O0 -run-pass=legalizer -global-isel %s -o - | FileCheck %s
 
 --- |
   target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
   target triple = "aarch64--"
   define void @test_scalar_add_big() {
   entry:
     ret void
   }
+  define void @test_scalar_add_big_nonpow2() {
+  entry:
+    ret void
+  }
   define void @test_scalar_add_small() {
   entry:
     ret void
   }
   define void @test_vector_add() {
   entry:
     ret void
   }
+  define void @test_vector_add_nonpow2() {
+  entry:
+    ret void
+  }
 ...
 
 ---
 name:            test_scalar_add_big
 registers:
   - { id: 0, class: _ }
   - { id: 1, class: _ }
   - { id: 2, class: _ }
bb.0.entry:
     %5(s128) = G_MERGE_VALUES %2, %3
     %6(s128) = G_ADD %4, %5
     %7(s64), %8(s64) = G_UNMERGE_VALUES %6
     %x0 = COPY %7
     %x1 = COPY %8
 ...
 
 ---
+name:            test_scalar_add_big_nonpow2
+registers:
+  - { id: 0, class: _ }
+  - { id: 1, class: _ }
+  - { id: 2, class: _ }
+  - { id: 3, class: _ }
+  - { id: 4, class: _ }
+  - { id: 5, class: _ }
+  - { id: 6, class: _ }
+  - { id: 7, class: _ }
+  - { id: 8, class: _ }
+  - { id: 9, class: _ }
+body: |
+  bb.0.entry:
+    liveins: %x0, %x1, %x2, %x3
+    ; CHECK-LABEL: name: test_scalar_add_big_nonpow2
+    ; CHECK-NOT: G_MERGE_VALUES
+    ; CHECK-NOT: G_UNMERGE_VALUES
+    ; CHECK-DAG: [[CARRY0_32:%.*]](s32) = G_CONSTANT i32 0
+    ; CHECK-DAG: [[CARRY0:%[0-9]+]](s1) = G_TRUNC [[CARRY0_32]]
+    ; CHECK: [[RES_LO:%.*]](s64), [[CARRY1:%.*]](s1) = G_UADDE %0, %1, [[CARRY0]]
+    ; CHECK: [[RES_MI:%.*]](s64), [[CARRY2:%.*]](s1) = G_UADDE %1, %2, [[CARRY1]]
+    ; CHECK: [[RES_HI:%.*]](s64), {{%.*}}(s1) = G_UADDE %2, %3, [[CARRY2]]
+    ; CHECK-NOT: G_MERGE_VALUES
+    ; CHECK-NOT: G_UNMERGE_VALUES
+    ; CHECK: %x0 = COPY [[RES_LO]]
+    ; CHECK: %x1 = COPY [[RES_MI]]
+    ; CHECK: %x2 = COPY [[RES_HI]]
+
+    %0(s64) = COPY %x0
+    %1(s64) = COPY %x1
+    %2(s64) = COPY %x2
+    %3(s64) = COPY %x3
+    %4(s192) = G_MERGE_VALUES %0, %1, %2
+    %5(s192) = G_MERGE_VALUES %1, %2, %3
+    %6(s192) = G_ADD %4, %5
+    %7(s64), %8(s64), %9(s64) = G_UNMERGE_VALUES %6
+    %x0 = COPY %7
+    %x1 = COPY %8
+    %x2 = COPY %9
+...
+
+---
 name:            test_scalar_add_small
 registers:
   - { id: 0, class: _ }
   - { id: 1, class: _ }
   - { id: 2, class: _ }
   - { id: 3, class: _ }
   - { id: 4, class: _ }
   - { id: 5, class: _ }
bb.0.entry:
     %3(<2 x s64>) = COPY %q3
     %4(<4 x s64>) = G_MERGE_VALUES %0, %1
     %5(<4 x s64>) = G_MERGE_VALUES %2, %3
     %6(<4 x s64>) = G_ADD %4, %5
     %7(<2 x s64>), %8(<2 x s64>) = G_UNMERGE_VALUES %6
     %q0 = COPY %7
     %q1 = COPY %8
 ...
+---
+name:            test_vector_add_nonpow2
+registers:
+  - { id: 0, class: _ }
+  - { id: 1, class: _ }
+  - { id: 2, class: _ }
+  - { id: 3, class: _ }
+  - { id: 4, class: _ }
+  - { id: 5, class: _ }
+  - { id: 6, class: _ }
+  - { id: 7, class: _ }
+  - { id: 8, class: _ }
+  - { id: 9, class: _ }
+body: |
+  bb.0.entry:
+    liveins: %q0, %q1, %q2, %q3
+    ; CHECK-LABEL: name: test_vector_add_nonpow2
+    ; CHECK-NOT: G_EXTRACT
+    ; CHECK-NOT: G_SEQUENCE
+    ; CHECK: [[RES_LO:%.*]](<2 x s64>) = G_ADD %0, %1
+    ; CHECK: [[RES_MI:%.*]](<2 x s64>) = G_ADD %1, %2
+    ; CHECK: [[RES_HI:%.*]](<2 x s64>) = G_ADD %2, %3
+    ; CHECK-NOT: G_EXTRACT
+    ; CHECK-NOT: G_SEQUENCE
+    ; CHECK: %q0 = COPY [[RES_LO]]
+    ; CHECK: %q1 = COPY [[RES_MI]]
+    ; CHECK: %q2 = COPY [[RES_HI]]
+
+    %0(<2 x s64>) = COPY %q0
+    %1(<2 x s64>) = COPY %q1
+    %2(<2 x s64>) = COPY %q2
+    %3(<2 x s64>) = COPY %q3
+    %4(<6 x s64>) = G_MERGE_VALUES %0, %1, %2
+    %5(<6 x s64>) = G_MERGE_VALUES %1, %2, %3
+    %6(<6 x s64>) = G_ADD %4, %5
+    %7(<2 x s64>), %8(<2 x s64>), %9(<2 x s64>) = G_UNMERGE_VALUES %6
+    %q0 = COPY %7
+    %q1 = COPY %8
+    %q2 = COPY %9
+...

test/CodeGen/AArch64/GlobalISel/legalize-inserts.mir

 # RUN: llc -O0 -run-pass=legalizer -global-isel %s -o - | FileCheck %s
 
 --- |
   target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
   target triple = "aarch64--"
   define void @test_inserts_1() { ret void }
   define void @test_inserts_2() { ret void }
   define void @test_inserts_3() { ret void }
   define void @test_inserts_4() { ret void }
   define void @test_inserts_5() { ret void }
   define void @test_inserts_6() { ret void }
+  define void @test_inserts_nonpow2() { ret void }
 ...
 
 ---
 name:            test_inserts_1
 body: |
   bb.0:
     liveins: %w0
 
bb.0:
     ; CHECK: %4(s128) = G_MERGE_VALUES [[VAL_LO]](s64), %1(s64)
     %0:_(s64) = COPY %x0
     %1:_(s64) = COPY %x1
     %2:_(s32) = COPY %w2
     %3:_(s128) = G_MERGE_VALUES %0, %1
     %4:_(s128) = G_INSERT %3, %2, 32
     RET_ReallyLR
 ...
+
+---
+name:            test_inserts_nonpow2
+body: |
+  bb.0:
+    liveins: %x0, %x1, %x2
+
+
+    ; CHECK-LABEL: name: test_inserts_nonpow2
+    ; CHECK: %5(s192) = G_MERGE_VALUES %3(s64), %1(s64), %2(s64)
+    %0:_(s64) = COPY %x0
+    %1:_(s64) = COPY %x1
+    %2:_(s64) = COPY %x2
+    %3:_(s64) = COPY %x3
+    %4:_(s192) = G_MERGE_VALUES %0, %1, %2
+    %5:_(s192) = G_INSERT %4, %3, 0
+    RET_ReallyLR
+...

unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp

 
 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);
+  for (auto Op : {G_ADD, G_SUB}) {
+    for (unsigned Size : {32, 64})
+      L.setAction({Op, 0, LLT::scalar(Size)}, LegalizerInfo::Legal);
+    L.setLegalizeScalarToDifferentSizeStrategy(
+        Op, 0, LegalizerInfo::widenToLargerTypesAndNarrowToLargest);
+  }
+
   L.computeTables();
 
+  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)}),
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(8)}),
               std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(16)}),
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(16)}),
               std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(32)}),
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(32)}),
               std::make_pair(LegalizerInfo::Legal, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(64)}),
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(64)}),
               std::make_pair(LegalizerInfo::Legal, LLT::scalar(64)));
 
     // Make sure the default for over-sized types applies.
-  ASSERT_EQ(L.getAction({G_ADD, LLT::scalar(128)}),
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(128)}),
               std::make_pair(LegalizerInfo::NarrowScalar, LLT::scalar(64)));
+    // Make sure we also handle unusual sizes
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(1)}),
+              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(31)}),
+              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(33)}),
+              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(63)}),
+              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, LLT::scalar(65)}),
+              std::make_pair(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.setLegalizeVectorElementToDifferentSizeStrategy(
+      G_ADD, 0, LegalizerInfo::widenToLargerTypesUnsupportedOtherwise);
+
+  L.setAction({G_SUB, 0, LLT::scalar(32)}, LegalizerInfo::Legal);
+
   L.computeTables();
 
   // 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)}),
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 7)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::vector(8, 8)));
+  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, 32)}),
             std::make_pair(LegalizerInfo::FewerElements, LLT::vector(4, 32)));
+  // Check a few non-power-of-2 sizes:
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 3)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::vector(3, 8)));
+  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 8)}),
+            std::make_pair(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.setLegalizeScalarToDifferentSizeStrategy(
+      G_PTRTOINT, 0, LegalizerInfo::widenToLargerTypesAndNarrowToLargest);
+
   L.computeTables();
 
   // 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));
   ASSERT_EQ(L.getAction({G_PTRTOINT, 1, p0}),
             std::make_pair(LegalizerInfo::Legal, p0));
+  // Make sure we also handle unusual sizes
+  ASSERT_EQ(L.getAction({G_PTRTOINT, 0, LLT::scalar(65)}),
+            std::make_pair(LegalizerInfo::NarrowScalar, s64));
+  ASSERT_EQ(L.getAction({G_PTRTOINT, 1, LLT::pointer(0, 32)}),
+            std::make_pair(LegalizerInfo::Unsupported, LLT::pointer(0, 32)));
 }
 
 TEST(LegalizerInfoTest, MultipleSteps) {
   using namespace TargetOpcode;
   LegalizerInfo L;
-  LLT s16 = LLT::scalar(16);
   LLT s32 = LLT::scalar(32);
   LLT s64 = LLT::scalar(64);
 
-  L.setAction({G_UREM, 0, s16}, LegalizerInfo::WidenScalar);
+  L.setLegalizeScalarToDifferentSizeStrategy(
+      G_UREM, 0, LegalizerInfo::widenToLargerTypesUnsupportedOtherwise);
   L.setAction({G_UREM, 0, s32}, LegalizerInfo::Lower);
   L.setAction({G_UREM, 0, s64}, LegalizerInfo::Lower);
 
   L.computeTables();
 
   ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(16)}),
             std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
   ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(32)}),
             std::make_pair(LegalizerInfo::Lower, LLT::scalar(32)));
 }
+
+TEST(LegalizerInfoTest, SizeChangeStrategy) {
+  using namespace TargetOpcode;
+  LegalizerInfo L;
+  for (unsigned Size : {1, 8, 16, 32})
+    L.setAction({G_UREM, 0, LLT::scalar(Size)}, LegalizerInfo::Legal);
+
+  L.setLegalizeScalarToDifferentSizeStrategy(
+      G_UREM, 0, LegalizerInfo::widenToLargerTypesUnsupportedOtherwise);
+  L.computeTables();
+
+  // Check we infer the correct types and actually do what we're told.
+  for (unsigned Size : {1, 8, 16, 32}) {
+    ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(Size)}),
+              std::make_pair(LegalizerInfo::Legal, LLT::scalar(Size)));
+  }
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(2)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(8)));
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(7)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(8)));
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(9)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(16)));
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(17)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(31)}),
+            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(33)}),
+            std::make_pair(LegalizerInfo::Unsupported, LLT::scalar(33)));
+}
 }

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));
     }
   }
 }