Re: Jump size optimization info... (Anton Ertl)
12 Jan 2007 16:58:14 -0500

          From comp.compilers

Related articles
Jump size optimization info... (Orlando Llanes) (2007-01-08)
Re: Jump size optimization info... (Ken Rose) (2007-01-11)
Re: Jump size optimization info... (Steven Nichols) (2007-01-12)
Re: Jump size optimization info... (Steven Nichols) (2007-01-12)
Re: Jump size optimization info... (2007-01-12)
Re: Jump size optimization info... (glen herrmannsfeldt) (2007-01-14)
Re: Jump size optimization info... (Karsten Nyblad) (2007-01-28)
Re: Jump size optimization info... (Sandeep Dutta) (2007-01-31)
Re: Jump size optimization info... (Orlando Llanes) (2007-02-09)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: 12 Jan 2007 16:58:14 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 07-01-023
Keywords: assembler, optimize
Posted-Date: 12 Jan 2007 16:58:14 EST

"Orlando Llanes" <> writes:
[Moderator's note:]
>The general problem is NP-complete

For such a general definition of the problem that it does not occur
with relative branches, and typically only rarely elsewhere in
linking: IIRC you need to allow subtractions between arbitrary
addresses in the code, and want to optimize the size needed for the
resulting numbers in order to construct an NP-complete problem.

If you only want to optimize relative branch sizes, this problem is
polynomial: Just start with everything small, then make everything
larger that does not fit, and reiterate until everything fits.
Because in this case no size can get smaller by making another size
larger, you have at worst as many steps as you have branches, and the
cost of each step is at most proportional to the program size.

This approach is also a good heuristic for the NP-complete problem,
and will usually produce the optimal result in the cases occuring in

This is a very nice example of a harmful NP-completeness result:
People just remember that "size optimization is NP-complete" or worse
"linking is NP-complete", without remembering the exact problem for
which the NP-completeness was proven. And even for the NP-complete
problem, a polynomial algorithm usually produces the optimal result
for problems occuring in practice; and I guess that an optimal
algorithm would run in acceptable time on practical cases (but is
probably not worth implementing).

However, mentioning the NP-completeness often stops people from
attacking the problem in the detail they would otherwise apply, and
that's the harm that the NP-completeness result does.

- anton
M. Anton Ertl

[To get the genreral NP complete subtraction problem I'd think you
could add branch chaining, e.g., if you have A->C and B->C, you can
change that to A->B and B->C. -John]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.