[RFC PATCH] .bundle_align_mode

[John Reiser]

On 02/22/2012 11:21 AM, Roland McGrath wrote:
> On Wed, Feb 22, 2012 at 8:50 AM, nick clifton <nickc@redhat.com> wrote:
>> No.  Well yes - a rewrite of gas, but that is not practical right now. So
>> for now, frags are the way.
> 
> :-)  I also meant if there is any feasible method for avoiding the
> pessimistic relaxation issue.  That is, that I wind up over-padding
> unnecessarily when a relaxable instruction is close enough to a boundary
> that the longest encoding doesn't fit, but relaxation winds up using a
> shorter encoding that would have fit.  I take it none comes to mind.

This problem was solved decades ago.  Search for "span-dependent instruction".
The main article [Thomas G Szymanski, 1978] even appeared in CACM (Communications
of the Association for Computing Machinery), which is about as prominent
and wide-spread as possible.

Although in general it's equivalent to 3-SAT (three satisfiability) and
thus is NP-complete [all the naive algorithms are at least quadratic
for the worst case], in practice it's a non-issue.

--