Re: Jump size optimization info...

"Orlando Llanes" <Orlando.Llanes@gmail.com> 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
practice.


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
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html


[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]

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