Assembler Optimizer

Paragon (1831)

11-06-2020, 19:01

For a while I've been thinking of creating an optimizer tool for assembler code. As a starting point, I was just thinking of simple optimizations (like automatic replacement of "cp 0" by "or a", etc. but doing them ensuring that the optimizations maintain functionality with 100% guarantees, so, the optimizer would have to make sure the replacements do not alter any flags that are later used, etc.). There are lots of Z80 assembler pages with optimization tricks (e.g.: http://z80-heaven.wikidot.com/optimization https://wikiti.brandonw.net/index.php?title=Z80_Optimization , but there are many others).

Of course, it'd be great to have more advanced optimization by turning the code into some sort of abstract representation and then optimizing that. But that seems like a much larger undertaking, that might take much more work.

I was also thinking of "optimizing for speed" vs "optimizing for space" options.

So, anyway, my question is if you are aware of any such tool already existing, or if any one has anything started on that direction. I spend hours upon hours optimizing code for making my games run as smooth as possible, and often I think if it would be more worth it to try to put my effort into creating an optimizer that does automatically everything I do manually, and maybe more.

Для того, чтобы оставить комментарий, необходимо регистрация или !login

By Manuel

Ascended (19678)

11-06-2020, 19:03

Sounds useful also for assembler code generated by compilers.

By eimaster

Champion (285)

11-06-2020, 19:15

Of course it would be worth it. Do it man. It would be a most wanted assembly code optimizing tool for so many. I hope you go for it.

By salutte

Master (165)

11-06-2020, 19:35

SDCC has an embedded optimizer for Z80 assembler. It is named peep-hole optimizer. Check section: 8.1.16 of the SDCC manual:
http://sdcc.sourceforge.net/doc/sdccman.pdf
It uses rule substitutions to akin to:

replace restart {
pop %1
push %1 } by {
; nop
}

And the rule set is optimized of course, to clean up the mess that the C compiler produces. But I found it SDCC unusable without this optimizer, but still, I find the optimize assembler still far from optimal.

You can actually apply this optimizer to your own code by using the embedded asm syntax:

static inline void phony_function() {
__asm

 ld a, 0 ; place your asm code here
__endasm;
}

But you need to call sdcc with the --peep-asm option, as usually inlined asm is left untouched.

Maybe this is can be used as an starting point.

By santiontanon

Paragon (1831)

11-06-2020, 19:53

Interesting! that "peep-hole" optimization is what I was thinking as a starting point. Thanks for the reference!

When optimizing hand-authored asm code, the optimizer might have to me more careful than just those blind pattern substitutions though, as programmers usually exploit side effects of instructions (e.g., flags) in the code some times, and thus, the optimizer must be aware of those dependencies before applying the substitution. So, I was thinking that a first step is to parse the assembler code (I was looking at the parser from grauw's Glass compiler for example), and then build a simple dependency graph of which instructions depend on the output of which others (always erring on the safe side when dependencies are unclear when there are complex things such as self-modifying code, etc.), to ensure safe substitutions. I don't think that should be too hard.

But that peel-hole optimizer seems like a great starting point for example patterns to include in the optimizer!

By Metalion

Paragon (1628)

11-06-2020, 20:16

Nice idea, but I'm afraid optimizations are strongly based on context.
And therefore require a true analysis of the coder.

By santiontanon

Paragon (1831)

11-06-2020, 20:58

Indeed, that is true. It's hard to optimize without knowing what the code is supposed to do. But I'm not aiming for that yet, hehe

In my experience the only way to finish a project is to start with a small finish-able idea, and the build from there. So, I am just aiming at something that would apply these simple pattern-based optimizations for now, but ensuring 100% safety guarantees. So, my first idea is:
1) parse assembler code
2) generate dependency graph (which instructions potentially depend on outputs/flags of other instructions)
3) match patterns
4) apply substitutions only if they are safe based on the dependency graph
5) write out a modified version of the .asm code (original source, but just modified)

Something simple like that, that seems doable and might be useful to put in Github. Just to start. If it ends up being useful, then I can think of going beyond that

By Grauw

Ascended (10820)

11-06-2020, 21:32

Sounds really interesting santiontanon, I’m looking forward to that!

By monant

Resident (48)

11-06-2020, 22:48

For code Analisys what do you think about
Cutter and radare2?

By santiontanon

Paragon (1831)

12-06-2020, 00:56

I have never used them, but they look quite interesting. Probably more useful for disassembling existing games than for optimizing, but I'll look into the data structures they use to store the disassembled code, might be useful!

In any case, I just wanted to start brain storming. I'm not going to get to it until I finish my game for the MSXDev, so maybe 1 month or so. But will keep you informed if I do any progress

By thegeps

Paragon (1251)

12-06-2020, 08:25

Hi Santu, any preview of your game for msxdev? Or is it top secret? I'm really curious...