12 Jan 2007 16:58:14 -0500

Related articles |
---|

Jump size optimization info... Orlando.Llanes@gmail.com (Orlando Llanes) (2007-01-08) |

Re: Jump size optimization info... kenrose@nc-sys.com (Ken Rose) (2007-01-11) |

Re: Jump size optimization info... sdn@svpal.org (Steven Nichols) (2007-01-12) |

Re: Jump size optimization info... sdn@svpal.org (Steven Nichols) (2007-01-12) |

Re: Jump size optimization info... anton@mips.complang.tuwien.ac.at (2007-01-12) |

Re: Jump size optimization info... gah@ugcs.caltech.edu (glen herrmannsfeldt) (2007-01-14) |

Re: Jump size optimization info... 148f3wg02@sneakemail.com (Karsten Nyblad) (2007-01-28) |

Re: Jump size optimization info... niktechc@niktech.com (Sandeep Dutta) (2007-01-31) |

Re: Jump size optimization info... Orlando.Llanes@gmail.com (Orlando Llanes) (2007-02-09) |

From: | anton@mips.complang.tuwien.ac.at (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" <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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.