This is an archive of the discontinued LLVM Phabricator instance.

Add an algorithm for performing "optimal" layout of a struct.
AcceptedPublic

Authored by rjmccall on Mar 20 2020, 2:03 PM.

Details

Reviewers
echristo
Summary

The algorithm supports both assigning a fixed offset to a field prior to layout and allowing fields to have sizes that aren't multiples of their required alignments. This means that the well-known algorithm of sorting by decreasing alignment isn't always good enough. Still, we start with that, and only if that leaves padding around do we fall back on a greedy padding-minimizing algorithm.

There is no known efficient algorithm for producing a guaranteed-minimal layout in all cases. In fact, allowing arbitrary fixed-offset fields means there's a straightforward reduction from bin-packing, making this NP-hard. But as usual with such problems, we can still efficiently produce adequate solutions to the cases that matter most to us.

I intend to use this in coroutine frame layout, where the retcon lowerings very badly want to minimize total space usage, and where the switch lowering can indeed produce a header with interior padding if the promise field is highly-aligned. But it may be useful in a much wider variety of situations.

Diff Detail

Event Timeline

rjmccall created this revision.Mar 20 2020, 2:03 PM
rjmccall edited the summary of this revision. (Show Details)Mar 20 2020, 2:09 PM
rjmccall added a reviewer: echristo.
echristo accepted this revision.Apr 7 2020, 11:02 AM

Looks great to me as is. Thanks.

-eric

This revision is now accepted and ready to land.Apr 7 2020, 11:02 AM

Thanks. Chris asked me offline to rename it to something like OptimizedStructLayout, which seems reasonable to me; I just haven't had the time to do that yet.

aykevl added a subscriber: aykevl.Apr 10 2021, 3:24 PM
aykevl added inline comments.
llvm/include/llvm/Support/OptimalLayout.h
40

This line is triggered in the coroutine lowering passes, see: https://bugs.llvm.org/show_bug.cgi?id=49916

I don't know whether this is a bug in OptimizedStructLayout or in the coroutine lowering passes, but I'm noting it here just in case.

rjmccall added inline comments.Apr 10 2021, 9:15 PM
llvm/include/llvm/Support/OptimalLayout.h
40

Hmm. Abstractly it seems like a reasonable precondition, so it's probably best to fix in the coroutine lowering passes.

lxfind added inline comments.Apr 10 2021, 10:13 PM
llvm/include/llvm/Support/OptimalLayout.h
40

I guess we could explicitly check for the size of Alloca in corosplit, and if it's 0, don't put it on the frame?

rjmccall added inline comments.Apr 10 2021, 11:13 PM
llvm/include/llvm/Support/OptimalLayout.h
40

It depends on what semantics we need to provide for the alloca. If the address needs to be consistent and unique throughout the coroutine, which I think is the usual alloca guarantee, then coroutine lowering should probably ask layout for something as if the object had size 1.

Out of curiosity, what's the motivating use case for the fixed offset fields in this tool?

Out of curiosity, what's the motivating use case for the fixed offset fields in this tool?

There is a need for this in coroutines. In the coroutine frame layout, the first few fields are fixed according to C++ standard.

Out of curiosity, what's the motivating use case for the fixed offset fields in this tool?

There is a need for this in coroutines. In the coroutine frame layout, the first few fields are fixed according to C++ standard.

Ah, makes sense - is that only for prefixes, or can that result in arbitrary non-initial-sequence fixed offset fields too?

Out of curiosity, what's the motivating use case for the fixed offset fields in this tool?

There is a need for this in coroutines. In the coroutine frame layout, the first few fields are fixed according to C++ standard.

Ah, makes sense - is that only for prefixes, or can that result in arbitrary non-initial-sequence fixed offset fields too?

It does support filling holes between fixed fields, yes. This is actually currently used in coroutines with over-aligned promises that require padding. (Apparently we are currently putting the padding in the wrong place, but that doesn't deeply matter, since in either case there's padding we can fill.)

lxfind added inline comments.May 3 2021, 4:47 PM
llvm/include/llvm/Support/OptimalLayout.h
40

Curious, would it just work if we remove this assertion?
That would still allow the alloca to have a consistent address and I cannot think of a reason this algorithm will fail because a field is 0 size?

rjmccall added inline comments.May 3 2021, 5:26 PM
llvm/include/llvm/Support/OptimalLayout.h
40

The assertion is there because I don't want this library to have to start making policy decisions like that. You can very easily handle zero-sized allocas that don't have to have a unique address by assigning them an offset of zero within the frame. It looks like alloca doesn't guarantee a unique address, so that should be fine.

Matt added a subscriber: Matt.May 31 2021, 9:52 AM