This is the mail archive of the mailing list for the binutils project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC PATCH] .bundle_align_mode

On 02/22/2012 11:21 AM, Roland McGrath wrote:
> On Wed, Feb 22, 2012 at 8:50 AM, nick clifton <> 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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]