Proposed: first class packed structures

Currently, Structure layout is left to targets, which implement them
according to the ABI of that platform. While this is fine for most
structures, it makes packed structures very ugly. All fields in a
packed type must be converted to byte arrays with casts to access
fields, which bloats accesses and obsfucates the types. First class
support for packed types would clean up the generated code from these
(lowering bytecode sizes) as well as having minimal impact on
optimizations.

Consider:

extern struct { char a; int x; int y; int z; } __attribute((packed)) foos;;
int foo() { return foos.x + foos.y + foos.z; }
struct { int x; char a;} __attribute((packed)) bara[2];
int bar() { return bara[0].x + bara[1].x;}

which compiles to:
%struct.anon = type { sbyte, [4 x ubyte], [4 x ubyte], [4 x ubyte] }
%foos = external global %struct.anon
%bara = weak global [2 x { [4 x ubyte], sbyte }] zeroinitializer
implementation ; Functions:
int %foo() {
entry:
  %tmp = load int* bitcast ([4 x ubyte]* getelementptr (%struct.anon*
%foos, int 0, uint 1) to int*)
  %tmp3 = load int* bitcast ([4 x ubyte]* getelementptr (%struct.anon*
%foos, int 0, uint 2) to int*)
  %tmp6 = load int* bitcast ([4 x ubyte]* getelementptr (%struct.anon*
%foos, int 0, uint 3) to int*)
  %tmp4 = add int %tmp3, %tmp
  %tmp7 = add int %tmp4, %tmp6
  ret int %tmp7
}

int %bar() {
entry:
  %tmp = load int* bitcast ([2 x { [4 x ubyte], sbyte }]* %bara to int*)
  %tmp4 = load int* bitcast ([4 x ubyte]* getelementptr ([2 x { [4 x
ubyte], sbyte }]* %bara, int 0, int 1, uint 0) to int*)
  %tmp5 = add int %tmp4, %tmp
  ret int %tmp5
}

Packed structure types would let us say:
%struct.anon = type <{ sbyte, int, int, int }>
%foos = external global %struct.anon
%bara = weak global [2 x <{ int, sbyte }>] zeroinitializer
implementation ; Functions:
int %foo() {
entry:
  %tmp = load int* getelementptr (%struct.anon* %foos, int 0, uint 1)
  %tmp3 = load int* getelementptr (%struct.anon* %foos, int 0, uint 2)
  %tmp6 = load int* getelementptr (%struct.anon* %foos, int 0, uint 3)
  %tmp4 = add int %tmp3, %tmp
  %tmp7 = add int %tmp4, %tmp6
  ret int %tmp7
}

int %bar() {
entry:
  %tmp = load int* getelementptr([2 x <{ int, sbyte }>]* %bara, int 0,
int 0, uint 0 )
  %tmp4 = load int* getelementptr ([2 x <{ int, sbyte }>]* %bara, int
0, int 1, uint 0)
  %tmp5 = add int %tmp4, %tmp
  ret int %tmp5
}

The attached patch implements this (with the above syntax). Let me
know what you all think.
The bytecodes reduce for the above example from 342B -> 325B. This
also would fix bug 931.

Andrew

packed.patch.raw (19 KB)

Attached is a cleaned up patch.

Andrew

packed.patch (12.4 KB)

The attached patch (gcc.patch) implements the gcc portion of packed
types. I have only tested this on a few examples, so I may be missing
some type conversions somewhere.

The gcc patch requires llvm_extra.patch, not included in the previous emails.

Andrew

llvm_extra.patch (1.64 KB)

gcc.patch (2.65 KB)

Currently, Structure layout is left to targets, which implement them
according to the ABI of that platform. While this is fine for most
structures, it makes packed structures very ugly. All fields in a
packed type must be converted to byte arrays with casts to access
fields, which bloats accesses and obsfucates the types. First class
support for packed types would clean up the generated code from these
(lowering bytecode sizes) as well as having minimal impact on
optimizations.

...

The attached patch implements this (with the above syntax). Let me
know what you all think.
The bytecodes reduce for the above example from 342B -> 325B. This
also would fix bug 931.

I like this approach a *lot*. The syntax is even pretty clever :). I attached some nit-picky comments below about your revised patch: please address the issues then commit the patch.

However, there is a issue that this patch brings up: pointers to packed fields are not necessarily aligned correctly. On targets with transparent unaligned load/store support (x86) this isn't an issue, but other targets (alpha, ppc, arm, ia64, etc) will be seriously impacted by this.

The code generator has the ability to represent unaligned load/stores (in LoadSDNode and StoreSDNode) but this capability is currently unused. We need to extend load/store instructions to have an alignment field that can be set on them, and this alignment should be propagated into the code generator. This is http://llvm.org/PR400.

It would be great if you were interested in tackling this too, but your patch isn't a regression, so it can go in without it.

Comments:

*** You need to update LangRef.html.

@@ -154,24 +154,28 @@ public:
  class StructType : public CompositeType {
    friend class TypeMap<StructValType, StructType>;
    StructType(const StructType &); // Do not implement
    const StructType &operator=(const StructType &); // Do not implement

+ // is this a packed structure?
+ bool packed;

The attached patch (gcc.patch) implements the gcc portion of packed
types. I have only tested this on a few examples, so I may be missing
some type conversions somewhere.

The gcc patch requires llvm_extra.patch, not included in the previous emails.

Andrew
<llvm_extra.patch>

llvm_extra.patch is fine, it can go in with the rest.

<gcc.patch>

This patch isn’t sufficient for two reasons: 1) it will turn structs that don’t need to be packed into packed llvm structs. 2) it won’t turn some that should be packed llvm structs into packed structs (e.g. strange ABI considerations force a field to be unaligned, not an attribute at the source level).

Here’s an example of #1:
extern struct { int x; int y; int z; } __attribute((packed)) foos;;
This should just be {int,int,int}, not <{int,int,int}>.

The approach I’d like to see is:

StructTypeConversionInfo should have a bool field “Packed” that is initialized to false.

As fields are added to StructTypeConversionInfo, there are three cases:

  1. GCC wants the field to be at an offset equal to where LLVM would place it. Just add the field.
  2. GCC wants to place the field at an offset further from where llvm would place it. Just add enough dummy fields to pad it over to where it needs to be.
  3. GCC wants to place the field at an offset closer to where LLVM would place it. When this happens, the current struct is marked packed and the existing fields have ‘spacers’ put in between them if necessary.

This ensures we only make things ‘llvm packed’ if needed, and should allow the logic to be significantly simplified.

Seem reasonable?

-Chris

> Currently, Structure layout is left to targets, which implement them
> according to the ABI of that platform. While this is fine for most
> structures, it makes packed structures very ugly. All fields in a
> packed type must be converted to byte arrays with casts to access
> fields, which bloats accesses and obsfucates the types. First class
> support for packed types would clean up the generated code from these
> (lowering bytecode sizes) as well as having minimal impact on
> optimizations.

Cool!

Reid can chime in here, but it seems like there should be a more
efficient way to encode the packed'ness than using a whole byte per
struct type. Perhaps it doesn't matter, because we will hopefully be
moving to per-bit encoding in the near future.

I don't thinkits worth it at this point. We have way more serious things
going on than an extra byte for a type. Consider that all ICmp/FCmp
instructions will use format0 (the largest) in anything but the smallest
of functions (less than 64 instructions). This will get naturally
cleaned up when we move to bit streams.

If you *really* want to be efficient, the *right* way to do this is to
create a new TypeID and the corresponding class (class
PackedStructureType : public StructureType). That way it costs nothing
(the value of the TypeID indicates that its PackedStructure) and there's
no need to mess with an additional byte in the StructureType class.
But, that might be a little heavy weight :slight_smile:

Reid.

Ok, fair enough!

-Chris

I thought of that, but packed really seemed like an attribute on an
existing class and not worth making a subclass for. Thus adding a
TypeID for it would mean we had a typeID that didn't corrospond to a
real class.

Andrew

<gcc.patch>

This patch isn't sufficient for two reasons: 1) it will turn structs that
don't need to be packed into packed llvm structs. 2) it won't turn some
that should be packed llvm structs into packed structs (e.g. strange ABI
considerations force a field to be unaligned, not an attribute at the source
level).

Yea, I've also come across a case:
struct { short x __attribute((packed)); int y __attribute((packed)); }
a = {1, 2}, b = ... ;
That my patch doesn't handle;

Seem reasonable?

Yea, having tried the logic on larger codes (aka the linux kernel)
I've found more packed idioms I wasn't handling. I'll see what I can
do.

Andrew

no, consider
struct foo { int x; int y; int z; } __attribute((packed));
struct {char c; struct foo f;} bar;

sizeof(bar) == 13
if struct foo wasn't packed it's allignment would force a larger size for bar;

Andrew

I would expect the type of bar to be:

<{sbyte, {int,int,int} }>

which has size = 13.

-Chris