Re: Jump size optimization info...

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