2 ms·
Huge fan of Franz' work on this, his PhD thesis on it[1] is a thing of beauty for it's simple, accessible description. Beyond that, I just wanted to add a coup
by vidarh 4y ago
Huge fan of Franz' work on this, his PhD thesis on it[1] is a thing of beauty for it's simple, accessible description.
Beyond that, I just wanted to add a couple of things:
It doesn't require keeping the generated datastream at the level of the AST per see. You can generate as high- or low-level data as suitable where e.g. a lower level representation requires additional computation but remains independent of hardware architectures. The key is just that what you generate should fit a tree structure. So you can do any number of optimisation steps on the tree prior to applying the semantic dictionary encoding step if you choose. The extension to e.g. serialising SSA forms was pretty natural - there was work at ETHZ on generating SSA form around the same time as well [2]
The real beauty of the method is that the encoder and decoder each generates a dictionary the same way e.g. LZW does (and the dissertation cites Welch; Lempel-Ziv style variable length dictionary entries is achieved by simply variable length encoding all integers stored), but where the encoder uses it to compress and flatten the tree, the decoder does not reconstitute the original tree, but uses it to generate machine code fragments directly, and either copy it straight into the code being generated or stores it as a template to reuse for generation of other occurrences of that dictionary element.
The compression/decompression and serialization/code-generation are one and the same, and avoiding a separate layer is a key reason why it achieved the speed it did.
[1] Code-Generation On-the-Fly: A Key to Portable Software, M. Franz (1994): https://oberoncore.ru/_media/library/franz_m.code-generation_on-the-fly_a_key_to_portable_software.en.pdf https://oberoncore.ru/_media/library/franz_m.code-generation...
[2] Single-pass generation of static single-assignment form for structured languages, M. Brandis, H. Mössenböck (1994)