Assembler Optimizer

Paragon (1805)

29-06-2020, 17:49

@grauw: Oh, great to know about the errors in the Z80 manual! I make a note and will revise the instructions you mention later today!

@pgimeno: good catches!! I'll check those cases you mention, and add safety checks. Should be easy to add constraints on jp<=/jr<= to ensure the constant is not 255 for example! And good point about sub a / sbc a! I'll also mark them as not depending on A! Hopefully that enables a few more optimizations

About the Java version: I know!! I wanted to change it to Java 8, but hesitated because "strip" (introduced in Java 11) is the current recommended function as it supports unicode... but that's the only thing. I really do not use anything from the Logger class, and could easily remove that dependency (I just left it since that's how I implemented it the first time). If the Java 12 dependency is a problem, I might just drop it and go back to Java 8...

Par Grauw

Ascended (10767)

29-06-2020, 19:06

I reckon for flags, you can treat them the same as how you check registers whether they are used (if you don’t already). If they are not tested or used before being modified, the optimisation is a go.

One of your optimisations has “or a” in it to clear the carry before subtracting. I myself always use “and a” for that. Possibly if you could guarantee that the carry is always 0 rather than specifically checking for and or or, you could use the optimisation based on that. And if it’s guaranteed to be 1, adjust the addition by one. And if there are some conditions checking the carry after the addition, flip the flags. (Encroaching on “human optimisation” territory.)

Another common optimisation: add a,a in place of sla a. Only the H and P/V flags differ.

Par theNestruo

Champion (421)

29-06-2020, 19:04

santiontanon wrote:

About the Java version (...)

I'm so used to Apache Maven that I cannot conceive a Java project without it... And usually the first dependencies I include are Apache Commons' Lang3 and IO*. Lang3 mainly because of StringUtils/RegExUtils, and IO for files and streams manipulation. And Maven can conveniently build jar-with-dependencies...
If you have string manipulations, StringUtils is definitely the way go; give it a try!
Other Apache Commons components may cover your needs in other areas (Math, Text, Geometry, Numbers...)

* Other people prefers Google's Guava, but I find it kind of bloated.

Edit (to clarify my point): Since I started to use Apache Commons, I no longer care about the methods of standard Java Objects and the version they were introduced... You can write very idiomatic and concise Java code without pushing the Java version.

Par santiontanon

Paragon (1805)

29-06-2020, 19:24

Thanks for the additional suggestions!! I'll try to bring as many of those as I can over the next few days and report back And yes, flags dependencies are checked in the same way as registers. In fact I divide dependencies into 4 classes: registers, flags, i/o ports and memory. The mechanism to step through the code looking for dependencies is shared among all four, and then I just have special code to check for a "dependency match/update" for each of the 4 categories above. Some are tricky (for example, when looking forward for a dependency on "bc", if an instruction modifies "c", the dependency should still go forward, but just with "b"), but I hope I'm handling them correctly .

My current goal (other than increase the set of patterns and make it more robust) is to expand the parser a bit to allow for some Glass/sjasm/asMSX syntax so I can test the optimizer in some of the projects you pointed out above. I think that with just 2/3 more constructs I will already be able to load a few of those projects. After that I have a million additional ideas for optimizations haha, but step by step

As for Maven/Apache, thanks for the suggestions! I've used a few apache commons libraries in the past (I think Match for sure, and maybe others). I try keeping my projects dependency-light if I can, but the string ones might come handy. I'll check it out!

Par pgimeno

Champion (328)

29-06-2020, 23:11

santiontanon wrote:

I doubt anyone uses Unicode spacers (e.g. the stuff in the U+2000 range) in assembly code

santiontanon wrote:

I really do not use anything from the Logger class, and could easily remove that dependency (I just left it since that's how I implemented it the first time). If the Java 12 dependency is a problem, I might just drop it and go back to Java 8...

Well, for me it is but I'm likely to be alone in that, so I can just keep a private patch as I do with other projects.

Par theNestruo

Champion (421)

01-07-2020, 14:42

@santiontanon: I was thinking today about this (not at my computer, so I haven't tested the optimizer yet)... If the optimizer output all the lines where it has found a possible optimization in a parseable manner ("Possible optimization at dummy.asm#123: Replace ld a,0 with xor a") that output would be very useful.

For example, it can fed a VSCode problem matcher so the possible optimizations are shown within the editor (with a squiggly line, as warnings or infos or tasks or ...).
It would be perfect if the developer could mark the "false positives" (or optimizations the developer don't want to apply) with a comment ("; no-mdlz80").

This behaviour would suit my workflow better, but I think is less aggresive than running the optimizer and then looking at the generated source code and trying to locate the optimization in the original sources.
It also alleviates the problem of detecting if a value is actually used in not-so-corner cases (e.g.: non-optimizable "ld a,0 + ret" to return 0 but keeping flags, or detecting register usage within subroutines not present in the source, such as BIOS routines).

Par santiontanon

Paragon (1805)

01-07-2020, 18:28

That's a great idea! Not in the current "release" version, but in the latest committed version, you can already get that output actually. For example, running it in my current project, it would generate something like this (only part of the output shown):

...
PatternBasedOptimizer substitution in src/weapons.asm, line 263: 1 bytes saved
    srl a
    srl a
    srl a
Replaced by:
    rrca
    rrca
    rrca
    and 31

PatternBasedOptimizer substitution in src/weapons-secondary.asm, line 132: 1 bytes saved
    srl a
    srl a
    srl a
Replaced by:
    rrca
    rrca
    rrca
    and 31

PatternBasedOptimizer: 12 patterns applied, 12 bytes saved

So, what you suggest is indeed doable, it'd be a matter of generating the output of the optimizer in a way that is easily parseable by the VSCode plugin!

I really also like the idea of having comment annotations. There are a few situations where it is hard for the optimizer to guess the target position of a jump, or the return address of a "ret" (since the user might be modifying the stack in funny ways). So, allowing annotations of this style would help the optimizer further! What would be a good format for generating the output that is easily parseable from a VSCode problem matcher?

Par theNestruo

Champion (421)

01-07-2020, 18:38

santiontanon wrote:

What would be a good format for generating the output that is easily parseable from a VSCode problem matcher?

Anything that can be parsed with a regexp is good enough!
I for one would go for: (Likely|Possible) optimization in src/dummy.asm, line 123: pattern: cp 0 -> or a (-1byte)
The patterns can be rewritten as messages for readability ("Replace CP 0 by OR A"), and I would use the wording "Likely optimization" for "safe" optimizations and "Possible optimization" for the -popotential ones. This way, the problem matcher can mark the likelies as warnings and the possible as infos, or whatever choice the user prefers.
Thank you!

Par santiontanon

Paragon (1805)

01-07-2020, 18:52

Nice, ok! I was going to upload a new "release" tomorrow or so with the latest updates, so, I'll try to include this type of output. It'd be very cool actually to have these suggested optimizations while you code!

One detail is that currently the optimizer needs to know which is the main file of your project (since everything else is included from there). If this is a problem maybe I can make the parser a bit more permissive, so that it can be run on individual assembler files even if they contain labels that are not defined in that file in particular (this would limit the optimizations that can be done, but still, at least it'll run )

Par theNestruo

Champion (421)

01-07-2020, 18:58

My plan was to include the mdlz80optimizer execution in the makefile/.bat just after the assembly (to skip it if the assembly has failed) so no problem; at that point the main asm file is known