[GlobalISel] Generic MachineInstrs need a type but this increases the memory footprint of the related objects

[qcolombet]

Bugzilla Link	26576
Version	trunk
OS	All
CC	@chandlerc,@lattner,@dwblaikie,@echristo,@qcolombet,@TNorthover

Extended Description

As r260558, we added a Type * field to the MachineInstr class. This field is actually used only for generic MachineInstr and moreover, only during the instruction selection process.
In other words, we negatively impact the memory footprint of the whole backend pipeline for generic instructions that are used only at the beginning of such pipeline.

The question is then, is it possible to have that information in a union or
something?
My initial thought was that we could have a derived class GenericMachineInstr
with additional information, but in practice it makes little to no sense since
generic MachineInstrs are likely turned into non-generic ones by just switching
the opcode. In other words, we don't want to go through the process of creating
a new, non-generic MachineInstr, object each time we do this switch. The memory
benefit probably is not worth the extra compile time.

Another option would be to keep the type of the MachineInstr in a side table.
This would induce an extra indirection though.

That being said, when we have the basic pipeline lay down, we will be able to make measurements for the different option.

However, if you have ideas, please share!

[qcolombet]

Hi Chandler, Chris, David, Eric, and Jim,

Any ideas for this?
In particular, could there be some C++ construction I haven’t thought that could help here?

Thanks.

[qcolombet]

I was thinking the side table may be the most natural approach here. My problem was where do we make it live, but now I think it would be reasonable to have it on the MachineFunctionInfo or something.

Thoughts?

[echristo]

There's way not enough context to know what the heck you need the type for and so where to put it :p

That said, it seems reasonable to put it as part of the instruction, but perhaps layer the generic instructions differently so only they need the type rather than change the generic type? Possibly make the generic instructions inherit from MachineInstr? or a unified base?

[qcolombet]

There's way not enough context to know what the heck you need the type for
and so where to put it :p

Good point, I am so into it that I did not realize.
Basically, at the MI level the type of an instruction is encoded in the opcode, e.g., ADDi8rr, ADDi16rr, etc. However, we do not want to have a generic opcode for all the possible add, sub, and so on, because generic opcodes are not bound on the number of input types. Indeed, we can go with ADDi1 to ADDi123456 etc.

Anyhow, it does not scale.

The solution to this problem is then to have the generic instructions to be typed.

That said, it seems reasonable to put it as part of the instruction, but
perhaps layer the generic instructions differently so only they need the
type rather than change the generic type? Possibly make the generic
instructions inherit from MachineInstr? or a unified base?

Having inheritance was one of the option, but I rejected it because when we after legalization, the select phase will likely be just a matter of switching an opcode (G_ADD i16 for instance to ADDi16rr).
In other words, we probably do not want to delete the generic instance and create a non-generic one.

[chandlerc]

I don't understand why this is such a problem...

MachineInstr has 6 pointer sized fields I spot by inspection, plus a 32-bit field and 3 8-bit fields. Glancing at it, I think there may be 5 bytes of padding as well. It seems surprising to me that it would be so problematic to increase the memory consumed by this one class by 1/7th... Do you have specific measurements that concern you here?

The opcode isn't stored inline in MachineInstr though, so maybe the type shouldn't be either.

If you look at MCInstrDesc, it has 6 >= pointer sized fields as well, plus 8 bytes packed into it. So you could also create one of these per opcode/type pair, and only grow the MCInstrDesc size by 1/7th (this would create some really amazing layering challenges though, please be extremely careful if you go this route).

But I also suspect you don't need all the things in MCInstrDesc when you have a generic MachineInstr. In fact, I don't think you need almost any of the stuff in there. most of it is about MC physical registers and other MC-level information which seems definitionally irrelevant for your case? Similarly the encoding size?

Why not make the pointer to an MCInstrDesc instead point to a custom struct for the generic MI, with your own opcode and type pointer and other metadata you need?

[chandlerc]

(Since it wasn't obvious, the last paragraph was suggesting something like PointerUnion<const MCInstrDesc, MyOtherInstrDescType>.

[qcolombet]

Thanks Chandler!

I like the analysis and the way you found space for me ;).

[qcolombet]

I gave this some more thoughts.

Another alternative that is less intrusive than messing with the MCDescription field and more general is to define a new kind of MachineOperand: Type.

It is less intrusive in the sense that we do not have to play a dance with the MC description held by TRI and generated by tablegen. (Generic instructions do have MSCDesc.) Moreover, the new MachineOperand kind wouldn’t impact the size of the MachineOperand class. (We would get a new type pointer in Content union.)

It is more general in the sense that we would support generic instruction with several types for free.

In terms of space, the machine operands arrays are allocated for size of power of 2. I expect that, in most cases, we will have spare space to store them an additional machine operand, but yes, in the worst case, we will bump the size of the machine operands arrays at runtime.

PS: Thanks to Ahmed for double checking the allocation strategy of MachineOperand after I through the idea.

[chandlerc]

I gave this some more thoughts.

Another alternative that is less intrusive than messing with the
MCDescription field and more general is to define a new kind of
MachineOperand: Type.

There is no 'MCDescription' so I'm not sure what you're referring to here at all... Perhaps you're imagining changing the contents of the MCInstrDesc class itself? As I said in my post, that doesn't seem necessary or clean, and isn't what I suggest (although it does seem possible).

I suggested that you take the first field of MachineInstr:

const MCInstrDesc *MCID;

And make it instead:

PointerUnion<const MachineGenericOp *, const MCInstDesc *> ID;

This wouldn't require any changes to MCInstDesc. It wouldn't require any changes to anything in MC, which seems like a clear non-starter. It wouldn't require any more bits that I can see and it would allow re-pointing the MachineInstr to a concrete MCInstDesc whenever you like.

Is there a problem with this approach that you're struggling with? (Other than perhaps needing better names than the ones I've suggested?)

It is less intrusive in the sense that we do not have to play a dance with
the MC description held by TRI and generated by tablegen. (Generic
instructions do have MSCDesc.)

I don't know what you really mean by MSCDesc, do you mean MCInstrDesc? If so, that seems weird and unlikely to be the right design. MCInstrDesc (and generally all of MC) doesn't make a whole lot of sense for generic nodes here. And it isn't clear why this would be necessary either, but maybe I just don't understand some inner coupling between MI and MC?

Moreover, the new MachineOperand kind
wouldn’t impact the size of the MachineOperand class. (We would get a new
type pointer in Content union.)

Note that MachineOperand is already crazy expensive, and I'm somewhat worried about packing more into the Content union, but OK.

It is more general in the sense that we would support generic instruction
with several types for free.

I don't really understand this statement. Can you elaborate on what you mean? I don't think I've suggested an approach that has a cost associated with generic instructions with several types, but maybe I've missed something...

In terms of space, the machine operands arrays are allocated for size of
power of 2. I expect that, in most cases, we will have spare space to store
them an additional machine operand, but yes, in the worst case, we will bump
the size of the machine operands arrays at runtime.

How confident are you? I would expect there to be a reasonably large number of instructions with one or two operands.

But maybe all of this is irrelevant, as it isn't clear what problem this design is setting out to solve...

[qcolombet]

I gave this some more thoughts.

Another alternative that is less intrusive than messing with the
MCDescription field and more general is to define a new kind of
MachineOperand: Type.

There is no 'MCDescription' so I'm not sure what you're referring to here at
all... Perhaps you're imagining changing the contents of the MCInstrDesc
class itself? As I said in my post, that doesn't seem necessary or clean,
and isn't what I suggest (although it does seem possible).

I suggested that you take the first field of MachineInstr:

const MCInstrDesc *MCID;

And make it instead:

PointerUnion<const MachineGenericOp *, const MCInstDesc *> ID;

Yes, I’ve got that :).

This wouldn't require any changes to MCInstDesc. It wouldn't require any
changes to anything in MC, which seems like a clear non-starter. It wouldn't
require any more bits that I can see and it would allow re-pointing the
MachineInstr to a concrete MCInstDesc whenever you like.

Yeah, I meant MCInstDesc.
Yes, we wouldn’t require to make any changes to MCInstDesc, but generic operations do have MCInstDesc. Those are used to query things like associativity or number of operands.
I.e., the MachineGenericOp (or whatever name we choose), would at least partially contain some of the MCInstDesc information. Moreover, the MCInstDesc is obtained by querying the tables in instrinfo. Those table are generated by tablegen.
That means that for generic operations, when we do TII->get(Opcode), we would need to do some post processing to produce the MachineGenericOp from the MCInstDesc, or we have to modify TII::get to produce want we want.

That’s the dance I was talking about and why I think it is intrusive.

Is there a problem with this approach that you're struggling with? (Other
than perhaps needing better names than the ones I've suggested?)

Unless it was not clear, it feels intrusive and unnatural to me :).

It is less intrusive in the sense that we do not have to play a dance with
the MC description held by TRI and generated by tablegen. (Generic
instructions do have MSCDesc.)

I don't know what you really mean by MSCDesc, do you mean MCInstrDesc? If
so, that seems weird and unlikely to be the right design. MCInstrDesc (and
generally all of MC) doesn't make a whole lot of sense for generic nodes
here. And it isn't clear why this would be necessary either, but maybe I
just don't understand some inner coupling between MI and MC?

Is it clearer now?

Moreover, the new MachineOperand kind
wouldn’t impact the size of the MachineOperand class. (We would get a new
type pointer in Content union.)

Note that MachineOperand is already crazy expensive, and I'm somewhat
worried about packing more into the Content union, but OK.

It is more general in the sense that we would support generic instruction
with several types for free.

I don't really understand this statement. Can you elaborate on what you
mean? I don't think I've suggested an approach that has a cost associated
with generic instructions with several types, but maybe I've missed
something...

Indeed, you didn’t suggested a cost associated with generic instructions with several types. I was just thinking that if we want several types for the instruction (e.g., mul_lohi), we could have several “type” machine operand at least at first. I.e., this is more or less free implementation wise.

In terms of space, the machine operands arrays are allocated for size of
power of 2. I expect that, in most cases, we will have spare space to store
them an additional machine operand, but yes, in the worst case, we will bump
the size of the machine operands arrays at runtime.

How confident are you? I would expect there to be a reasonably large number
of instructions with one or two operands.

I haven’t actually measured, but I would expect that the instructions needing types (i.e., anything that is not a move or a target specific instructions) have around 3 operands (1 def and 2 arguments).

I may be wrong of course and this is something we will measure.

But maybe all of this is irrelevant, as it isn't clear what problem this
design is setting out to solve...

I think you got it right: this is primarily runtime size. However, I think it is important that the handling of generic MachineInstr feels natural and I don’t think the dance between MCInstDesc and MachineGenericOp falls into that category.

Anyhow, that was a proposed alternative, I am of course open to discuss and actually, I think this kind of debates are good for the end result design.

In other words, thanks for your time in discussing, evaluating the different approaches!

[chandlerc]

OK, If you need to have MCInstrDesc for generic MIs, then it seems really easy to have that type contain the the type in addition to the opcode. Even if it makes those objects larger, it wouldn't make the MachineInstr larger.

Perhaps we need to better separate the different bits of MCInstrDesc from things that are table generated, but it sounds like you'll need to do that anyways if you need to have MCInstrDesc objects for the generic ops.

I pretty strongly feel like the correct location for the type is either in the generic MI analog to MCInstrDesc or in MCInstrDesc itself. It seems really awkward to try to hide the type inside the operand list. I think it will add a lot of complexity to the end result even if it is easier to cut in today.

[qcolombet]

OK, If you need to have MCInstrDesc for generic MIs,

(Note: Actually we already have that with target independent instructions like COPY. The new generic instructions are special in the sense that they should not appear after ISel, but other than that, this is really the same thing.)

then it seems really
easy to have that type contain the the type in addition to the opcode.

That does not work with the current scheme.

The MCInstrDesc are shared between similar instructions. If we put the type here, then all those instructions share the same type, whereas it is probably not what we want.
So ok, let say we have one MCInstrDesc per type then. The problem now is that it does not scale for tablegen, i.e., we don’t know before hand how many types we will have in a Module.
We could create them at runtime then, but that is shift in the way we represent MCInstrDesc: Right now they are known at compile time. (One big table with the MCInstrDesc.)

Even
if it makes those objects larger, it wouldn't make the MachineInstr larger.

Perhaps we need to better separate the different bits of MCInstrDesc from
things that are table generated, but it sounds like you'll need to do that
anyways if you need to have MCInstrDesc objects for the generic ops.

Like I said in my note in the beginning of that post, generic operations already exist and are well supported with the current MCInstrDesc. What is missing is “just" the type and as just stated, it feels wrong to keep it there.

At some point, I was thinking a side table could do as well. I’ll come back to that.

Again the MachineOperand felt nice in the sense that I believe we already have unused space in the array in MachineInstr instances.

I pretty strongly feel like the correct location for the type is either in
the generic MI analog to MCInstrDesc or in MCInstrDesc itself.

Maybe what we need is a MachineInstrInfo that could hold the information we are missing (I.e., the side table idea). That would have the benefit to be consistent with what we do for TargetRegisterInfo vs. MachineRegisterInfo.

What I don’t like is the fact that an instruction is not self contained, but that’s already the case anyway.

It seems
really awkward to try to hide the type inside the operand list. I think it
will add a lot of complexity to the end result even if it is easier to cut
in today.

Possibly yeah, though prototyping is good to answer this kind of questions.

How do you feel about the side table/MachineInstrInfo idea?

[chandlerc]

OK, If you need to have MCInstrDesc for generic MIs,
then it seems really
easy to have that type contain the the type in addition to the opcode.

That does not work with the current scheme.

The MCInstrDesc are shared between similar instructions. If we put the type
here, then all those instructions share the same type, whereas it is
probably not what we want.
So ok, let say we have one MCInstrDesc per type then.

Right, sorry I wasn't more explicit about this, I was of course assuming that you'd generate the types you need.

The problem now is
that it does not scale for tablegen, i.e., we don’t know before hand how
many types we will have in a Module.
We could create them at runtime then, but that is shift in the way we
represent MCInstrDesc: Right now they are known at compile time. (One big
table with the MCInstrDesc.)

Ok, I see the reason you're reluctant to go this route now, but I still think something like this is the right long term design. To try to give you an idea of why, let's take a look at what is in MCInstrDesc:

class MCInstrDesc {
public:
unsigned short Opcode; // The opcode number
unsigned short NumOperands; // Num of args (may be more if variable_ops)
unsigned char NumDefs; // Num of args that are definitions

Totally fine so far...

unsigned char Size; // Number of bytes in encoding.
unsigned short SchedClass; // enum identifying instr sched class

These ill fitting for the target independent phase...

uint64_t Flags; // Flags identifying machine instr class

But this one makes sense...

uint64_t TSFlags; // Target Specific Flag values

It says on the tin that this is for targets...

const MCPhysReg *ImplicitUses; // Registers implicitly read by this instr
const MCPhysReg *ImplicitDefs; // Registers implicitly defined by this instr

Pretty sure you aren't going to end up with physical registers for these...

const MCOperandInfo *OpInfo; // 'NumOperands' entries about operands

This actually makes sense though...

// Subtarget feature that this is deprecated on, if any
// -1 implies this is not deprecated by any single feature. It may still be
// deprecated due to a "complex" reason, below.
int64_t DeprecatedFeature;

But this seems again really unnecessary.

So I feel like here we have some 4 pointer-sized (or larger!) fields, plus some smaller fields, which have no utility for target independent instructions.

But the separate object to describe the opcode + generic information (operand number, type, etc) makes lots of sense to me, especially as it lets us avoid repeating that information in each 64-bit integer add instruction (which we will have soooo many of), etc.

But pretty clearly generating statically all possible combinations doesn't make sense. I'm totally in agreement there.

Ultimately, I think that in order for the design to make sense, you'll have to change at least one of the following properties:

1. Don't use MCInstrDesc for your new generic nodes, and teach everything that needs to look through this to look through both MCInstrDescs and whatever your new description object is.

2. Augment the table generated MCInstrDesc nodes with additional ones created on demand with types.

3. Add a layer of indirection between the MachineInstr and the MCInstrDesc which can carry the type information.

The reason I was pushing toward #​1 is because it really feels like MCInstrDesc is a poor fit for MI during the phase where you have types and are in a completely target independent space. I suspect the nodes could be made much smaller (and thus memory efficient) by separating them from the MCInstrDesc type, and it seems it would also solve the problem of having these things not fit the statically-generated-table model that uses.

It also helps clarify that these constructs simply can't exist at the MC level at all. It makes the lowering from them to actual MC representable instructions make much more sense IMO.

To an extent, doing #​3 would also achieve much of this, and maybe that's a better path. If so, I'm fine with that too, they seem pretty interchangeable from a high level design and mostly a difference of how the bits are represented.

That said, I hear you that this would be an invasive and big change. I also think it is the right design, and I don't think we should compromise that.

Even
if it makes those objects larger, it wouldn't make the MachineInstr larger.

Perhaps we need to better separate the different bits of MCInstrDesc from
things that are table generated, but it sounds like you'll need to do that
anyways if you need to have MCInstrDesc objects for the generic ops.

Like I said in my note in the beginning of that post, generic operations
already exist and are well supported with the current MCInstrDesc.

I'm surprised you feel this way. Looking at MCInstrDesc, it seems like a rather poor fit for generic operations. My comments above probably elaborate why I see it that way. If this is the root cause of us preferring different designs this might really be what we need to focus on...

At some point, I was thinking a side table could do as well. I’ll come back
to that.

A side table also feels like side stepping the core design issue here: MachineInstr currently is hard coded to an MC level construct that doesn't support type-full MI. I think we will eventually need to undo that coupling for the design to make any sense.

[qcolombet]

[…]

That said, I hear you that this would be an invasive and big change. I also
think it is the right design, and I don't think we should compromise that.

Although I agree with you, for the prototype I wanted to avoid big invasive change like this.
That being said, sooner or later, I would totally go into that direction!

Like I said in my note in the beginning of that post, generic operations
already exist and are well supported with the current MCInstrDesc.

I'm surprised you feel this way. Looking at MCInstrDesc, it seems like a
rather poor fit for generic operations. My comments above probably elaborate
why I see it that way. If this is the root cause of us preferring different
designs this might really be what we need to focus on…

Actually, I did not look into the MCInstrDesc.
I naively assumed that since it was used for target independent operations (PHIs, COPY, etc.) it was required as a whole for generic like instructions.
Clearly, I was wrong! (As a side note, this is funny that we already waste some space to keep thing like the encoding size for PHIs and COPYs, I thought all of that was carefully designed :).)

Thank for the patience you put in showing me where I was wrong!

At some point, I was thinking a side table could do as well. I’ll come back
to that.

A side table also feels like side stepping the core design issue here:
MachineInstr currently is hard coded to an MC level construct that doesn't
support type-full MI. I think we will eventually need to undo that coupling
for the design to make any sense.

That sounds legit, yes.

[TNorthover]

Just a drive-by note that more than one type will probably be needed for some instructions (icmp, cmpxchg and especially intrinsics spring to mind).

[aemerson]

Closing this as an old issue not to be addressed.