Wed Sep 26 02:05:11 CEST 2007

assembler optimizations / corrections

A) jump size optimization

currently i have none. recently i introduced at least error reporting
on overflow. i think the deal is that doing it 'really right' is
difficult; i'm not sure there exists an optimal algorithm. the
simplest approach is:

  * convert small -> long jump
  * increment/decrement jumps before/after the instruction
  * update dictionary accordingly

it's probably easiest to do this on an already fully resolved buffer
(after 2nd pass). this algorithm is confusing due to the
forward/backward absolute/relative destinction. also, doing this
without mutation seems troublesome.

B) jump chaining

was really easy in the original badnop due to use of side-effects.

somehow this problem looks as if there's some weird control structure
that might help solve this is a more direct way.

OK... finding the optimal is apparently NP-complete


> [There was a paper by Tom Szymanski in the CACM in the 1970s that
> explained how to calculate branch sizes. The general problem is
> NP-complete, but as is usually the case with NP-complete problems,
> there is simple algorithm that gets you very close to the optimal
> result. -John]

or not?


  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.

so, it looks like the simple approach of using short branches and
expanding/adjusting + checking is good enough.