Assembler Optimizer

بواسطة thegeps

Paragon (1249)

21-06-2020, 19:26

I agree with artrag. Focus on plain asm code. I think that assemblers' creators (like Grauw about Glass) should implement in their assemblers an option to generate (if desired) a plain z80 asm file, purified by macros, if/endif and other (very useful) syntax adds when compiling...

بواسطة santiontanon

Paragon (1830)

21-06-2020, 23:50

Yeah, I think you are right... I'm going down a rabbit hole that is deeper than I imagined with just parsing the different syntax. But I'm doing good progress bit by bit on the project (even if I really should put it aside for the moment and finish my damn MSXDev game... haha). Maybe in a 1/2 weeks I'll have something to show already (even if it's simple)

بواسطة santiontanon

Paragon (1830)

28-06-2020, 20:28

Alright!!! It's aliiiive! hahaha: https://github.com/santiontanon/mdlz80optimizer

I have a very simple first version working, which is very exciting! I'm calling it "mdl" (from "minimum description length") It can take an assembler project, perform simple pattern-based optimizations, and either report the potential optimizations, or generate optimized assembler code directly! You can call it like this:

java -jar mdl.jar main.asm -po -asm main-optimized.asm

I have tried it in my projects, and even if it does not do too many optimizations yet, it managed to save 17 bytes in XSpelunker, for example. Which is a start! haha

As suggested before, you can run it in two different ways. If you call it as above, it will generate optimized assembler for you, but if you just call it like this, it will only point out the optimizations to you (lint style), without actually generating code:

java -jar mdl.jar main-asm -po

It contains a number of other things that I find useful for helping me optimize, but the core functionality is the optimizer. I've been currently focusing on optimizing space (which is the main thing I need for my current project, but I plan to also support speed optimizations shortly!).

Btw, Grauw, the Z80 instruction set table you have in this page ( http://map.grauw.nl/resources/z80instr.php ) was an amazing resource. MDL includes an extended version of that table ( https://github.com/santiontanon/mdlz80optimizer/blob/master/... ) as part of the source code (github does not display the table very well, you need to scroll right to see the content)), I gave you credit for the original table at the top of the file, I hope it's ok. If you'd rather that table not be there, let me know, and I can create my own table and replace.

بواسطة santiontanon

Paragon (1830)

28-06-2020, 20:30

Btw, these are the optimizations that MDL can do for now, it's a small and limited set, but I'll be expanding the set of patterns over time: https://github.com/santiontanon/mdlz80optimizer/blob/master/...

بواسطة ARTRAG

Enlighted (6976)

28-06-2020, 22:02

Very good ! Anyway, how far can replacement rules go?
E.g. can you replace a subroutine that returns a binary value in A, in another one returning the result in a flag?

بواسطة santiontanon

Paragon (1830)

28-06-2020, 22:12

They cannot go very far at the moment. I was precisely thinking of that case this morning (because of the other thread about the sprite collision routine), and I don't think I could encode that optimization with the current pattern system. But I have a few ideas about how could I handle those! For now I will try to push the current pattern system as far as I can (I have about 10 - 20 additional patterns I collected from z80 optimization websites that I still need to incorporate), and then we'll see where do I take it from there!

Also, one complex thing is to make sure the optimizations do not break the code. I just noticed after posting the messages above that 2 of the patterns I have are not safe, so, I need to fix them. Bit by bit

بواسطة theNestruo

Champion (428)

29-06-2020, 09:11

One more:
CALL address + RET => JP address (sorry, not at my computer so I cannot make a proper pull request)

Quote:

pattern: unused ld r,value
0: ld ?reg,?any
replacement:
constraints:
regNotUsed(0,?reg)

I feel uneasy about this one. Some of my routines end with "LD a, value + RET" (usually after some conditionals). Note: I didn't have the chance to look that deep at the code, so I'm not sure how do you detect the register usage...

بواسطة santiontanon

Paragon (1830)

29-06-2020, 09:35

Thanks theNestruo! And wow, you even looked at the patterns, awesome!

The way it works is this: "regNotUsed(0,?reg)" checks that register "?reg" is not used after instruction 0. So, it starts going forward in the code (following all possible paths jp/jr/djnz/call, etc.) trying to see if the register is used before being overwritten. But if it encounters some instruction like a "ret", or a "jp hl", for which my code still cannot determine the target jump position, it stops and cancels the optimization. So, at this point, if there is a "ld a,value + ret", the "ld a,value" will not be optimized, as the "ret" will stop the optimization. I hope all the optimizations done now are safe, but I'm sure I forgot some case or another

Ah! And good one of call+reg -> jp, noted down! (might have to verify that the return address is not used for anything in the target routine, I hope that's easy to check!).

edit: But btw, I have a set of "tests" to check if optimizations are safe ( https://github.com/santiontanon/mdlz80optimizer/tree/master/... ). If anyone encounters a case where an optimization being made is not safe, let me know, and I'll add a test to that folder to make sure I can fix it :)

بواسطة Grauw

Ascended (10818)

29-06-2020, 11:09

Very nice!

I read that you used the Z80 manual as a source. Note that although it is a nice resource that I also use a lot myself, be cautious that it is not without errors. Some more obvious than others, e.g. and s and or s clearly don’t flag overflow in p/v, rather like xor s they flag parity. One to note in particular is that outi & co. modify a lot of flags, including the carry flag which the Z80 manual claims it doesn’t, and in a rather odd way, too. See The Undocumented Z80 Documented section 4.3.

santiontanon wrote:

Btw, Grauw, the Z80 instruction set table you have in this page was an amazing resource. MDL includes an extended version of that table as part of the source code, I gave you credit for the original table at the top of the file, I hope it's ok.

Yes that’s fine with me.

بواسطة pgimeno

Champion (328)

29-06-2020, 17:03

santiontanon wrote:

In general, you should be more careful about flags. CP 0 sets the N flag. CP 1 produces carry, DEC A doesn't; I've used the carry from CP 1 often. CP 255 changes the flags in a very different way than INC A, especially carry. SRL changes carry, AND clears it. DJNZ changes no flags, DEC B does. LDI changes some flags, which are left intact by LD and by INC rr.

In NEG->CPL I'm not sure if the previous value of A has an influence on any of the flags. I'd need to check to be sure. Also I'm not sure if NEG and SUB produce the same flags.

The jr<= and jp<= substitutions don't work when the constant is 255.

Also a missed opportunity: I've seen both XOR A and SUB A used to clear A. You correctly interpret that XOR A does not depend on A, but apparently you interpret SUB A as depending on the previous value of A. Similarly, SBC A,A does not depend on the previous value of A (although it depends on carry).

Another missed opportunity: LD A,(HL) / INC HL / LD (DE),A / INC DE, that is, changing the order of INC HL and LD (DE),A with respect to the current replacement. I often place the LD and INC together, or even in a macro.

I couldn't compile it because of the logger and the use of strip(); my Java is older than that. I had to remove the logging related stuff and change it to System.out.println, and change strip() to trim().