Page MenuHomePhabricator

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

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



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.


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.