commit 49e5a97ec363a844b167340a82b54a01dc4e671a
author John McCall <rjmccall@apple.com> Fri Mar 20 16:45:39 2020 -0400
committer John McCall <rjmccall@apple.com> Mon Mar 23 23:24:48 2020 -0400
tree 93aa84104dc0720ffddee6fb95dcea96c7d53c88
parent 98fa615002826e2e67892df0ee6847fbfa182308

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

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.