Re: HLA v1.68 is now available

From: C (cc-news_at_hermes.mirlex.com)
Date: 07/28/04 

Date: Tue, 27 Jul 2004 22:44:09 GMT

Randall Hyde wrote:

> Well, if you believe this then you're heading down the
> wrong path with displacement optimization just as you've
> headed down the wrong path with disassembly.
> Branch optimization has been proved to be an NP-Complete
> problem. As a result, no assembler is going to guarantee
> complete optimization of all the displacements. Therefore,
> they tend to use heuristics and iteration to get as good a
> job done as they can. If you think you can do it perfectly
> without trying all possibilities, you're wrong. If your
> heuristics don't involve multiple passes over the object
> code, then other assemblers will do a much better job
> of optimizing those branch displacements than you do.
> It's as simple as that.
>
> Unless, of course, you've managed to prove the
> open Computer Science question "does P=NP?"

Luxasm optimises branches _without_ multiple passes over
the source code and complete optimisation is guaranteed,
how it achieves this I will leave you to guess for now :-P

(Oh, yes, and you are correct the problem is still
NP-complete, therefore a brute force method has been used.)

Never the less, I cannot foresee any way of achieveing this
at neglable cost, or by using anything other than a brute
force method.

C
2004-07-27