Improve ZAPF's branch size optimization
This repository is deprecated. Use Heptapod instead.
Status: Beta
Brought to you by:
jmcgrew
Menu
▾
▴
#4 Improve ZAPF's branch size optimization
ZAPF takes multiple passes through the code to find label addresses and optimize operand sizes. This is complicated and usually requires at least 4 passes. It should be possible to assemble in a single pass using Inform-style backpatching: when an operand refers to a label whose value isn't known with 100% certainty, assume it'll fit into short form, then go back later and insert extra bytes where needed.
When code contains a lot of labels (like DeZapf output), the multiple pass method becomes inefficient or unusable. The backpatching method is probably necessary.
Backpatching may not be the greatest solution after all. The paper "Assembling Code for Machines with Span-Dependent Instructions" by Thomas Szymanski describes an efficient algorithm for optimizing branch sizes under constraints that are reasonable for ZAPF, using two assembly passes and three auxiliary structures.
This algorithm will let us eliminate ZAPF's multiple measuring passes and mid-pass reassembly, reducing complexity and run time, without the need to buffer and alter the object code that is emitted. We will need to change the symbol table representation, though: information about local labels must be tracked across passes.