Assembler Optimizer | MSX Resource Center (Page 13/58)

Paragon (1831)

16-07-2020, 09:16

The current set of optimization patterns only includes those that optimize BOTH size and speed. So, I started an alternative set that also includes patterns that only optimize size (I should also add one to optimize only for speed), added the basic "jp->jr" pattern, and omg, just in XSpelunker alone (a game that is not tight CPU-wise at all), there are 501 "jp"s that could have been turned into "jr"s, saving 501 bytes in the rom that would have been really useful back in the day! (the rom only has 17 bytes free!). I tried in other projects (e.g. in "Metal Gear", and only about 100 jps could be turned into jrs; so, it might be me who is really bad at using jr, haha)

Par theNestruo

Champion (429)

16-07-2020, 11:28

Metalion wrote:

santiontanon wrote:

This one would be cool to capture also if there is code in between 0 and 1 that do not modify "de"

That is exactly the case I was tring to explain.
In my code, there was a dozen lines between those 2 "ld de".

Actually, the pattern should be more general and detect if you are loading a previously loaded value (e.g.: "classical" RAM initialization with ld a, 3 / ld [...], a / ... and then another ld a, 3 / ld [...], a / ...).

There are several tricky things here that I guess it would be really difficult to find:

Detect half values within an expression (e.g: ld de, $ab00 / ...(does not touch e)... / ld de, $cd00 -> replace by ld d, $cd)
Detect previously loaded non-constant values (e.g: ld a,b / ...(does not touch b)... / ld a, b -> remove)
Detect implicit values after conditional ret (e.g: or a / ret nz / ...(does not touch a)... / xor a -> a is guaranteed to be 0 at the xor a -> remove)
Detect implicit value of b after djnz (e.g: djnz b / ...(does not touch b)... / ld b, 0 -> b is guaranteed to be 0 at the ld b, 0 -> remove)
Suggest registers with guaranteed values (e.g: typical RAM zeroing: ld hl, $e000 / ld de, $e001 / ld bc, $0ffe / ld [hl], 0 -> l is guaranteed to be 0 at the ld [hl], 0 -> replace by ld [hl], l)

Par santiontanon

Paragon (1831)

16-07-2020, 18:53

Lots of interesting ideas there! I think the "half values" and "loaded non-constant values" are definitively doable! The implicit values after conditionals might be a bit harder with the current pattern setup, but I am making notes of these, since those might be detectable with a different type of optimizer (or with specialized code to detect them).

And about the "guaranteed values", maybe not all, but a few cases I think should be doable too!

Edit: but now that I think of it, I think at least some simple cases of the "implicit values after conditionals" should be doable too! Basically the instructions right after "ret nz", "jp/jr nz", "djnz" should guarantee a/b being zero. Unfortunately the oposite cases "ret z"m "jp/jr z" cannot be captured, as the guarantee would be at the jump destination, and patterns cannot capture that currently. So, at least a few cases we can cover!

Par pgimeno

Champion (328)

17-07-2020, 20:44

Beware of labels changing value as a result of the optimizations.

Imagine this:

  org 100h
  ld de,Label1  ; 3 bytes
  ld (Var1),de  ; 4 bytes
Label1:         ; Label1 equals 100h+3+4=107h
  ld de,Label2  ; 3 bytes
  ld (Var2),de  ; 4 bytes
  ds 249        ; 249 bytes (imagine it's some other code that happens to be that length)
Label2:         ; Label2 equals 107h + 3 + 4 + 249 = 207h

Now if you optimize ld de,Label2 to ld d,2, the code is no longer equivalent, because Label2 now equals 206h, due to the fact that the reduction in size happens between the two labels.

Par santiontanon

Paragon (1831)

17-07-2020, 21:29

Yes, indeed! That's taken into account already (but it did cause some bugs in the early versions, so, thanks for checking! I think this works well since version 0.4 or 0.5, can't remember now). All labels internally in MDL are represented by the "expression" with which they are represented in the code, e.g. "label1", or "label2+3*CONSTANT". The first time their value is needed, their value is cached to make execution faster. But each time an optimization is performed (or code is modified in any way), these caches are cleared. So, their values will have to be recomputed if they are needed again. I cannot guarantee there's no bugs haha, but at least it should be handled correctly

Par santiontanon

Paragon (1831)

18-07-2020, 03:23

Oh, but wait, I don't think I understood your comment the first time. Yes, indeed, the code will not be equivalent. If the code uses label addresses as part of its calculations, then any optimization will modify that! If that's the case, MDL allows for you to place tags in the code to prevent optimizations. For example, any line that has a comment like

; mdl:no-opt

will not be optimized. So, in that way, you can protect parts of the code that are delicate, or that you just don't want to be touched

Par santiontanon

Paragon (1831)

18-07-2020, 08:57

Btw, I just added a bunch of patterns to capture what we were discussing in the past couple of days. It generates lots of new optimizations, but some of them are a bit scary! For example, imagine something like this:

    ld hl,some_variable
    ld (hl),a
    ld c,#18

if by pure chance "some_variable" has value, say, #c018. It will want to optimize "ld c,#18" by "ld c,l".

This is fine, but if you do this optimization halfway through your development, as soon as your "some_variable" changes address, the optimization would basically break your code (if you have applied it blindly). This is related to what pgimeno was mentioning earlier actually.

So, I was thinking of having these types of optimizations off by default. These are great when you apply them at the very end of the life of a project, but applying them half-way through might be dangerous. Another idea is, by default, not to do any optimization of this type if the expressions involved have any reference to code labels. Any ideas?

Par theNestruo

Champion (429)

18-07-2020, 11:19

santiontanon wrote:

This is fine, but if you do this optimization halfway through your development, as soon as your "some_variable" changes address, the optimization would basically break your code (if you have applied it blindly). This is related to what pgimeno was mentioning earlier actually.

So, I was thinking of having these types of optimizations off by default. These are great when you apply them at the very end of the life of a project, but applying them half-way through might be dangerous. Another idea is, by default, not to do any optimization of this type if the expressions involved have any reference to code labels. Any ideas?

Is this a real problem? I mean, I see two ways of working with the optimizer:

either it is part of the building pipeline (prepare resources + generate optimized .asm + assemble) and the optimizations are not written in the source code but rather in an intermediate artifact,
or you use the optimizer as a linter and manually apply the optimizations in the code editor (where you'll probably discard these wild optimizations, or apply them if really needed, but protecting the code somehow)

Blindly letting a tool (not just this optimizer, but any tool) to modify my actual source files is a no-go for me.

On the other hand, when I do "tricky" optimizations, I usually leave the removed instruction commented, and a small note explaining why I removed it (e.g.: ; xor a ; (unnecessary because of previous ret nz)). This way, the code is more readable (the commented instruction helps) and easier to modify ("wait, I changed the ret so now this instruction is necessary again").
Maybe the optimizer can do something similar in the output assembly; appending a comment with "; optimization of: ..." with the original source code...

Par pgimeno

Champion (328)

18-07-2020, 11:31

That's pretty much why I think that the optimizer should be an assembler in itself. and output an optimized binary. That way it can take advantage of the current values of labels etc. without risk.

Think of an optimizing C compiler. It can warn about things like unused variables or dead code, but the optimizations are applied to the output and not to the source.

Par theNestruo

Champion (429)

18-07-2020, 14:11

pgimeno wrote:

That's pretty much why I think that the optimizer should be an assembler in itself. and output an optimized binary. That way it can take advantage of the current values of labels etc. without risk.

Think of an optimizing C compiler. It can warn about things like unused variables or dead code, but the optimizations are applied to the output and not to the source.

I must disagree. I would never use an assembler that does not assemble the source code but something different. That is an accident waiting to happend and a debugging hell.
However, I understand your point... but that's achievable by having the optimizer as a separate step in the assembling pipeline: sources (assembly) -> optimizer -> optimized intermediate source (assembly) -> assembler -> binary (bin/rom/cas).