Assembler Optimizer

Somehow all the good research in our field is done decades ago already . But it’s not specific to assembly I think, but to all imperative programming languages.

Subroutines basically serve two purposes, one is as a programmer abstraction, the other is an explicit form of space optimisation (with the C++ “inline” keyword being the time optimisation version of it).

Ideally the programmer would only worry about the abstraction side of things, to let him express the program as intuitively as possible, and the compiler would deal with the optimisation. At most they would have to mark parts of code as “optimise for size” or “optimise for speed” (the hot code paths).

But as Z80 programmers we’re worrying a lot about inlining and unrolling on the one end (to save time), and making subroutines, fall-throughs and tail calls on the other (to save space). It’s a very manual process. While really the place and order of the subroutines doesn’t matter as long as the logic remains the same.

What makes this topic interesting is that it integrates speed and size optimisation into a general problem; it works both ways. The control flow is separated from the code, and can be freely manipulated by the optimiser to achieve either goal. Even as a linter it can be useful to help programmers identify where they have code duplication and what could be better call hierarchies, and where it would either save a lot of space or time.

Beware that, as the author of the paper says, it has a negative impact on speed, as CPU time needed is greater. The author says the gain comes only from the loading time being reduced, due to the smaller file size. This gain will be null in most MSX cases, as most of the time, it's a cartridge that's being used, with zero loading time. And even if it's the case with a disk file for example, it's the speed of execution we're after.

I agree that it permits to focus more the programmer's attention to optimizing the bits of code that are "subroutined" as a result, but at the cost of 29 cycles (call+ret) times the number of time the subroutine is called. That's why unrolling is usually a best practice.

But perhaps that's the end result. Isolating bits of code that are repetitive and could be "subroutined', so that the programmer focuses on optimizing them to achieve better performance. And then ... unrolling them.

Perhaps tying in to your register optimizer plans, another paper often referenced together with Fraser et al.’s paper: Enhanced Code Compression for Embedded RISC Processors

I’m still reading it but it’s nice because it gives another take on Fraser’s algorithm and then builds on it. It also has a lot of useful references like for example to Ukkonen’s algorithm to build a suffix tree in O(n) time. Wonderful, O(n) is what I want for my build scripts.

I also found references to other papers about incorporating instruction reordering (maybe more useful for the Z80 as the instruction set is nonorthogonal). As is often the case with academic papers though, some are behind paywalls.

At least you’re familiar with reading academic papers . The Ukkonen paper makes my eyes glaze over despite it claiming that it’s an intuitive approach! Luckily there is StackOverflow and this answer here gives a very nice explanation of the algorithm.

Although I need to deal with only a subset of the problems for the case of compressing a “stream of register writes”, I’ll let you know how it goes.

I don't think a program is a DAG. Loops are cycles in the graph.

Besides, don't aim for minimal, it's hopeless. https://en.wikipedia.org/wiki/Full_employment_theorem

Look up Control Flow Graph. Also, recommended read:
http://staff.cs.upt.ro/~chirila/teaching/upt/c51-pt/aamcij/7...
Chapter 8.2 describes the basics of CFGs.