Re: Best tools for writing an assembler?

On 2/24/2014 12:42 PM, glen herrmannsfeldt wrote:


<snip>




> -- glen [Variable length instructions aren't that hard. You start by
> assuming everything will be the long form, then iterate over the code
> a few times shrinking what you can. That isn't always perfectly
> optimal (which is known to be NP complete), but it's pretty close.
> -John]
>


Shrink is not NP, it is exact using a relaxation algorithm: track pairs
of addresses, one the smallest address assuming all unresolved are
resolved short, and one largest assuming all unresolved address are
long. Resolve long all those spreads whose shortest is longer than the
longest short; resolve short all those spreads whose longest is shorter
than than the longest short. Iterate resolution until you do a pass in
which no more were resolved. Set any remaining unresolved to short.


In practice, three iterations are always sufficient, including the final
one that resolves nothing.
[With some assumptions about chaining variable length jumps,
it really is NP-complete. See this 1978 CACM article
http://dx.doi.org/10.1145/359460.359474 -John]

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