Assembler Optimizer

ah, good point about parallelizing! I could try using multiple threads during the search. I don't think it should be too hard. I am using a standard depth-first-search + iterative deepening as the base search algorithm, so I could parallelize that maybe at the very first level of the search tree, to allow for k parallel threads (I am sure there must be an easy way to poll for the number of available cores with some system call?). I'll give it a try!

There's also several optimizations to the search process that I still need to implement (like defining a "canonical order" of instructions for those sequences that are synonymous, to make sure they are only searched once, etc.).

That's a good question! I'll run a few tests and see how long would it take to find the smallest or the fastest. The main big problem is constants (like that 0xE0), which blow up the search space. By default, I only allow the constant "0" (but you can specify this, to consider more, or all). And the second problem is if allowing instructions that read/write from memory, since this forces me to run some extra code during search (e.g., to restore the program after each simulation, as a program could modify itself), making search significantly slower. However, I have not done any systematic experiment yet to see how slow does it get allowing EVERYTHING. Might be an interesting test!

Ok, I just did the test, tldr: it will take a long time haha

So, starting from easier to harder and using the latest version, which can do multithreaded search, and has some improvements on search-space prunning ( https://github.com/santiontanon/mdlz80optimizer/releases/tag... ):

First is the easy case, with a reduced search space:

allowed_ops: 
    addition
    shift
    ld
allow_ram_use = false
allowed_registers: hl, a
max_ops = 7
initial_state:
    HL = val
goal_state:
    HL = val << 13

This takes about 15 seconds on the latest development version using 8 threads in my laptop (Apple M1 macbook pro), and finds this solution when optimizing for number of instructions (-so-ops):

    add hl, hl
    add hl, hl
    add hl, hl
    add hl, hl
    add hl, hl
    ld h, l
    ld l, 0

I then modified it a bit to try to find the solution you proposed (targeting the instruction set), to this:

allowed_ops: 
    logic
    ld
    rotation
allow_ram_use = false
allowed_registers: a, hl
8bit_constants: 0, 224
max_ops = 7
initial_state:
    HL = val
goal_state:
    HL = val << 13

When optimizing for execution time (-so-time), this finds a very similar solution in a bit less than 30 seconds (I think they are equivalent):

    ld a, l
    ld l, 0
    rrca
    rrca
    rrca
    and 224
    ld h, a

I then expanded it to use ALL the instruction types that I currently have (but still limited to only using a, h, l and the constants 0 and 224):

allowed_ops: 
    logic
    increment
    addition
    ld
    rotation
    shift
    negation
    bits
    carry
    cp
    jump
allow_ram_use = false
allowed_registers: a, hl
8bit_constants: 0, 224
max_ops = 7
initial_state:
    HL = val
goal_state:
    HL = val << 13

I only left it running for about 10 minutes, but it's clear this will take a long time. From the growth rate I was seeing, maybe it could finish in less than 1 day? I'm not sure. But this search will take a long time in any case haha. And if we allow even more constants than 0 and 224 to try to guarantee finding the absolute optimal, that'll be even slower. Perhaps removing "cp" and "jump" can help, or maybe the "bits" operations (bit/set/res) can help as I'm not sure if those would be helpful?

Ah, yes, the "copying using the stack" is a very nice "trick" to move data very fast!

As for constructing the description for the MDL optimizer to use that, it can probably not be specified with the current specification language, and I'll have to expand it. Only register and flag constraints can be specified at this point. But it'd be very nice to be able to specify constraints concerning memory (for finding optimal ways to move data, etc.). I am not sure how fast/slow will the search process be, but this will be a very nice addition!! It's in my to-do list, hopefully for the next version

And indeed, I'll add "time elapsed", since I usually run everything from inside the IDE, I get timing automatically, but I forget that's not the actual way MDL is supposed to be run haha.

Oh, there is currently no option to just "annotate" the optimizations. But that's an interesting option, I'll make a note of that. The two ways you can do something similar is:
- If you use an editor like Sublime Text, vim, or VSCode, you can integrate mdl into the editor, and it will show annotations directly over your code (in a similar way as compilation warnings/errors are displayed)
- Or a simpler option is just to redirect the output to a file, like: java -jar mdl.jar ffp.asm -asm ffopt.asm -dialect glass -po speed > output.txt
And then just inspect the output.txt file

Nice to see that it generates some optimizations!!! I have a new version coming soon, hopefully this weekend