Page MenuHomePhabricator

[SelectionDAG] Add SDNode:RawSDNodeBits.
ClosedPublic

Authored by jlebar on Sep 4 2016, 4:35 PM.

Details

Summary

Previously we were assuming that SDNodeBits covered all of SDNode's
anonymous subclass data bitfield union. But that's not right; it might
have size 1, in which it clearly doesn't.

This patch adds a field that does cover the whole union and adds
static_asserts to ensure it stays correct.

Diff Detail

Repository
rL LLVM

Event Timeline

jlebar updated this revision to Diff 70299.Sep 4 2016, 4:35 PM
jlebar retitled this revision from to [SelectionDAG] Add SDNode:RawSDNodeBits..
jlebar updated this object.
jlebar added reviewers: ahatanak, chandlerc.
jlebar added a subscriber: llvm-commits.
chandlerc added inline comments.Sep 4 2016, 5:30 PM
llvm/include/llvm/CodeGen/SelectionDAGNodes.h
466 ↗(On Diff #70299)

I think you should make this:

char RawSDNodeBits[sizeof(uint16_t)];

Because then it will actually be underlying storage and be well defined to access it as such. It also makes it clear that you don't get some *particular* uint16_t here, you just get that many bytes of memory.

1114 ↗(On Diff #70299)

So, as I mentioned in the other thread, I'm not sure what exact problem you're trying to solve. The change description is a bit confusing.

This makes sure that we copy a full uint16_t chunk of data out. Which might avoid copying only 1 byte instead of 2 bytes compared to the old version.

I think you could have the same effect by taking the max size of the various subclass bits... But maybe using the named entity is a bit cleaner than that, and you can just static assert that it *is* the max.

But this doesn't solve anything to do with endianness. I think that's OK, but your change description talks a lot about endianness for a change that doesn't really change that.

Perhaps worse, if the problem is uninitialized memory, I don't think this really helps at the theoretical level, even if it happens to help in practice. While you initialize all of the memory to zero, you then store through a bitfield. That gets to notionally store "uninitialized" into the high bits of the union. I don't think you can rely on them remaining zero.

If you need for all of the bitfields to occupy a full 16 bits in all cases so that you can use the raw 16 bits as an input to a hash code, I think you'll need to add a padding bitfield member to each and every one to cause them to have 16-bits worth of data, and you'll need to actually store a zero into that member when writing that bitfield.

Then you can change your static_asserts to check that each leaf size is *equal* to the raw union member. This will also force you to have a hard separation between classes with a prefix bitfield composed with others and a leaf class that is not composed any farther. I'm not sure if that'll be awkward or not. You will be able to completely remove the "zeroing" step you do in the base class constructor with the raw member.

The end result you want is that the typed accesses into the union always use exactly one leaf type that is exactly 16-bits large and (optionally) some set of *prefix* types that consist solely of a prefix of the leaf type's bitfields. That matches the spirit of the "common prefix" rules for unions.

Then you can have a raw member that you use here to read the un-typed underlying storage. But you don't want to do mutation through this because subsequent mutations through the leaf types can clobber things with "uninitialized".

jlebar marked an inline comment as done.Sep 7 2016, 9:21 AM
jlebar added inline comments.
llvm/include/llvm/CodeGen/SelectionDAGNodes.h
466 ↗(On Diff #70299)

sgtm, I'll make that change once we resolve the issue below.

1114 ↗(On Diff #70299)

But this doesn't solve anything to do with endianness.

I'll try to clarify the commit message (although fwiw it never mentioned endianness). What I was trying to get at when I mentioned endianness earlier is that I didn't want to rearrange the bits when copying them out.

Perhaps worse, if the problem is uninitialized memory, I don't think this really helps at the theoretical level, even if it happens to help in practice. While you initialize all of the memory to zero, you then store through a bitfield. That gets to notionally store "uninitialized" into the high bits of the union. I don't think you can rely on them remaining zero.

The uninitialized memory problem I was trying to solve was that when we effectively did

uint16_t ret;
memcpy(&ret, SubclassData, 1);
return ret;

half of ret was uninitialized.

However it sounds like there's also a problem with the bitfield itself, discussed below...

I think you'll need to add a padding bitfield member to each and every one to cause them to have 16-bits worth of data

Every *leaf* struct, as I read below? That makes sense.

and you'll need to actually store a zero into that member when writing that bitfield.

This makes a little less sense to me. When exactly do I need to store zero into the "padding" member? Just once, I would presume? Not every time I write to any member in the bitfield?

If writing to a bitfield sets all bits that are not in the bf to undef, then isn't it unsafe to write to a non-leaf bitfield after we've initialized the leaf? You're saying we can safely read from the non-leaf because of the prefix rule, but not write to it, yes? If so, that breaks everything here, and we should just write our own class with manual bit manipulation because this is beyond insane.

chandlerc accepted this revision.Sep 9 2016, 1:10 AM
chandlerc edited edge metadata.

LGTM as-is, see below.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h
1114 ↗(On Diff #70299)

Ah, yes, you are correct: you just need a tail padding bitfield member in each leaf struct, and you need to store zero to it when you initialize it.

But now that you say that, I'm easily persuading myself that I'm wrong and you don't need to do this at all.

Let's consider a simpler example:

struct BitsA {
  uint8_t a : 2;
};
struct BitsB {
  uint8_t : 2;
  uint8_t b : 4;
};
struct UnpaddedUnion {
  union {
    uint8_t raw;
    BitsA a_bits;
    BitsB b_bits;
  };
};
void f(UnpaddedUnion &u) {
  memset(&u.raw, 0, sizeof u.raw);
  u.a_bits.a = 1;
  u.b_bits.b = 13;
}

struct BitsPadding {
  uint8_t : 6;
  uint8_t padding : 2;
};
struct PaddedUnion {
  union {
    BitsA a_bits;
    BitsB b_bits;
    BitsPadding padding_bits;
  };
};
void g(PaddedUnion &u) {
  u.a_bits.a = 0;
  u.b_bits.b = 0;
  u.padding_bits.padding = 0;

  u.a_bits.a = 1;
  u.b_bits.b = 13;
}

What's the difference between f and g here? I think nothing. If the common prefix thing works at all, then when we put 1 into u.a_bits.a we can't put undef into any other bits, and when we put 13 into u.b_bits.b we can't put undef into any other bits, and that means in both f and g the other bits hold zero.

I'd like to chat with Richard to make sure this seems like a rational model, and at this point I think we should file a C++ defect report to get this entire thing clearly spelled out in the standard. Being able to use bitfield prefixes in a union seems sufficiently useful for us to make sure it has clearly defined and portable semantics.

But I think you're good to proceed just with the patch as is. If in fact we need to do some crazy tail padding bitfield, you can always add that later.

This revision is now accepted and ready to land.Sep 9 2016, 1:10 AM
This revision was automatically updated to reflect the committed changes.
jlebar marked an inline comment as done.