Re: Jump size optimization info...

Karsten Nyblad <148f3wg02@sneakemail.com>
28 Jan 2007 01:41:31 -0500

          From comp.compilers
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)
| List of all articles for this month |
From: Karsten Nyblad <148f3wg02@sneakemail.com>
Newsgroups: comp.compilers
Date: 28 Jan 2007 01:41:31 -0500
Organization: Compilers Central
References: 07-01-023 07-01-040
Keywords: assembler, optimize, theory
Posted-Date: 28 Jan 2007 01:41:31 EST

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


A way of making the problem NP-complete is to allow reordering of code.


    In some cases you can save branches or save long branches by
reordering the code, e.g., by swapping the order of two basic blocks.
Unfortunately the CACM paper John referenced to proves that that is
NP-complete. The paper goes on to prove that the algorithm described
by Steven Nichols is optimal as long as you are forbidden to reorder
the code.


Karsten Nyblad
148f3wg02 at sneakemail dot com

Post a followup to this message

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