[SelectionDAG] Add SDNode:RawSDNodeBits.

[jlebar]

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.

[chandlerc]

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

466

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

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]

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

466

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

1114

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]

LGTM as-is, see below.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

1114

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.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

class StoreSDNodeBitfields {
     friend class MaskedStoreSDNode;
 
     uint16_t : NumLSBaseSDNodeBits;
 
     uint16_t IsTruncating : 1;
   };
 
   union {
+    uint16_t RawSDNodeBits;
     SDNodeBitfields SDNodeBits;
     ConstantSDNodeBitfields ConstantSDNodeBits;
     MemSDNodeBitfields MemSDNodeBits;
     LSBaseSDNodeBitfields LSBaseSDNodeBits;
     LoadSDNodeBitfields LoadSDNodeBits;
     StoreSDNodeBitfields StoreSDNodeBits;
   };
 
+  // RawSDNodeBits must cover the entirety of the union.  Which means that all
+  // of the union's members must have size <= RawSDNodeBits.
+  static_assert(sizeof(SDNodeBits) <= sizeof(RawSDNodeBits),
+                "SDNodeBits too wide");
+  static_assert(sizeof(ConstantSDNodeBits) <= sizeof(RawSDNodeBits),
+                "ConstantSDNodeBits too wide");
+  static_assert(sizeof(MemSDNodeBits) <= sizeof(RawSDNodeBits),
+                "MemSDNodeBits too wide");
+  static_assert(sizeof(LSBaseSDNodeBits) <= sizeof(RawSDNodeBits),
+                "LSBaseSDNodeBits too wide");
+  static_assert(sizeof(LoadSDNodeBits) <= sizeof(RawSDNodeBits),
+                "LoadSDNodeBits too wide");
+  static_assert(sizeof(StoreSDNodeBits) <= sizeof(RawSDNodeBits),
+                "StoreSDNodeBits too wide");
+
 private:
   /// Unique id per SDNode in the DAG.
   int NodeId;
 
   /// The values that are used by this operation.
   SDUse *OperandList;
 
   /// The types of the values this node defines.  SDNode's may
protected:
   /// Create an SDNode.
   ///
   /// SDNodes are created without any operands, and never own the operand
   /// storage. To add operands, see SelectionDAG::createOperands.
   SDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs)
       : NodeType(Opc), NodeId(-1), OperandList(nullptr), ValueList(VTs.VTs),
         UseList(nullptr), NumOperands(0), NumValues(VTs.NumVTs), IROrder(Order),
         debugLoc(std::move(dl)) {
-    memset(&SDNodeBits, 0, sizeof(SDNodeBits));
+    memset(&RawSDNodeBits, 0, sizeof(RawSDNodeBits));
     assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
     assert(NumValues == VTs.NumVTs &&
            "NumValues wasn't wide enough for its operands!");
   }
 
   /// Release the operands and set this node to have zero operands.
   void DropOperands();
 };
unsigned getAlignment() const {
     return MMO->getAlignment();
   }
 
   /// Return the SubclassData value, which contains an
   /// encoding of the volatile flag, as well as bits used by subclasses. This
   /// function should only be used to compute a FoldingSetNodeID value.
   unsigned getRawSubclassData() const {
     uint16_t Data;
-    memcpy(&Data, &SDNodeBits, sizeof(SDNodeBits));
-    static_assert(sizeof(SDNodeBits) <= sizeof(uint16_t),
-                  "SDNodeBits field too large?");
+    memcpy(&Data, &RawSDNodeBits, sizeof(RawSDNodeBits));
     return Data;
   }
 
   // We access subclass data here so that we can check consistency
   // with MachineMemOperand information.
   bool isVolatile() const { return MemSDNodeBits.IsVolatile; }
   bool isNonTemporal() const { return MemSDNodeBits.IsNonTemporal; }
   bool isInvariant() const { return MemSDNodeBits.IsInvariant; }