Assembler Optimizer

Page 42/46
35 | 36 | 37 | 38 | 39 | 40 | 41 | | 43 | 44 | 45 | 46

By santiontanon

Paragon (1353)

santiontanon's picture

14-04-2021, 21:32

Oh, interesting error!! It's easy to prevent MDL crashing there (which I'll do right away). But I'm intrigued about why doesn't it find that label! Can you give me a few details of that label? Can you show me the line that uses _myJIFFY and the line in game.asm that defines it? I wonder if there is any way in which SDCC can define/import/export labels that I missed Smile

By Bengalack

Champion (361)

Bengalack's picture

15-04-2021, 06:34

I'll send you more details, is there a way to send you some files directly?

By santiontanon

Paragon (1353)

santiontanon's picture

15-04-2021, 15:41

Sure! you can just send to my email: santi.ontanon@gmail.com

Thanks a lot btw! :)

By Bengalack

Champion (361)

Bengalack's picture

15-04-2021, 18:57

Bengalack wrote:

(the symbol is there Smile)

I was just about to document what is going on here. I was sure _myJIFFY was present as I found it when searching. I was wrong. Let me investigate this on my side first, and let me come back on this...

By santiontanon

Paragon (1353)

santiontanon's picture

26-04-2021, 00:40

Not completely finished yet, but I just uploaded a "dev" version of MDL 2.0 to GitHub: https://github.com/santiontanon/mdlz80optimizer/releases/tag...

Other than a few bug fixes here and there (Bengalack, I hope the issue we were discussing via email is fixed now), the big change is a new experimental optimizer: the "search-based optimizer". This is basically like the "super optimizador" (https://www.msx.org/news/development/en/super-optimizador). You provide a program specification as input, and it tries to generate the smallest/fastest assembler program that satisfies the specs.

This all sounds great, but...

Well, the search space of programs is HUGE, so, it can only find tiny programs (in my internal tests, 6 instructions is pretty much the limit assuming execution times in the order of 1 minute). Testing a program is very fast, since just running a 4-5 instruction assembler code does not take much time (I am now getting about 20 million "program candidate" tests per second), but there's lots of possible programs. In order to push the limit of how far can it go, I have lots of ways to prune the search space (e.g., never use uninitialized registers, etc.), and I also added lots of syntax to the specifications, so you can constraint the space in many ways, for example, you can do this:

Create a "specification.txt" file like this (more examples in this folder https://github.com/santiontanon/mdlz80optimizer/tree/master/... ):

allowed_ops: 
    addition
    shift
    ld
allow_ram_use = false
allowed_registers: hl, a
max_ops = 5
initial_state:
    HL = ?val
goal_state:
    HL = ?val << 11

then you call mdl like: java -jar mdl.jar specification.txt -so -asm out.asm

And it will output this:

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

This one takes under a second, since notice I constrained it to use only addition (add/adc/sub/sbc), shift (sla/sra/srl/sli) and ld instructions, I disallowed RAM use, and I only let it use the HL and A registers. The "max_ops" here is just so that it gives up if it does not find a program with at most 5 instructions. By default it looks for the program with the smallest number of instructions, but you can ask for the one with the fewest bytes (-so-size), or the fastest to execute (-so-time), although optimizing for size in bytes and time is not very optimized yet, and is slower.

I still need to write some documentation on how to use it, and optimize the search process as much as I can, but at least this is a start!

In order to verify correctness, I included a full Z80 emulator inside of MDL (a modified version of this project: https://github.com/codesqueak/Z80Processor ), so that I can simulate the effect of programs, and test if they are correct. I did not want to get into model-checking or anything complex, so, in order to verify if a program is correct, MDL just runs it 1000 times with random input, and if it works all 1000 times, then it assumes the program works (I can easily change this to 10000 or higher to increase safety, as it does not affect execution speed much, since most solutions fail i the first trial anyway).

I am also not 100% sure if I like the syntax of the program specification file, so, if anyone plays around with this and has any feedback, I'm all ears :)

In any case, this is just the start, as being able to simulate programs inside of MDL now opens lots of possibilities (e.g., @salute proposed a few months back that we could automatically generate optimization patterns via search to then be used in the pattern-based optimizer, etc.). So, many things to think about and work on still :)

By ARTRAG

Enlighted (6497)

ARTRAG's picture

26-04-2021, 14:36

How amazing! It is a crucial step in this project. Maybe you could challenge the super-optimizer against the patterns already in the library and replace those that get a better/shorter/faster equivalent.

By Bengalack

Champion (361)

Bengalack's picture

26-04-2021, 18:35

This is cool! I'll test on my code and let you know asap.

By pgimeno

Champion (285)

pgimeno's picture

27-04-2021, 02:12

Cool, a super-optimizer!

Are there docs on what allowed_ops allows? I'd suggest to accept instruction mnemonics. Or does it already work like that, and 'addition' is a shortcut for ADD/ADC/SUB/SBC?

By santiontanon

Paragon (1353)

santiontanon's picture

27-04-2021, 03:52

@ARTRAG: Oh! that's a great idea! Noting that down!!

@Bengalack, got your email and with that I should have the problem you reported fixed asap, thanks a lot Smile

And yes indeed, I need to write documentation for it. You can specify individual mnemonics, and, just for making things a bit easy, I defined groups. So, it's exactly as you say @pgimeno: "addition" is a shortcut for "add, adc, sub, sbc". There's other group shortcuts like "rotation", "shift", "logic", "bits", etc. I haven't added all the instructions yet, but I'm adding them bit by bit. I will write some documentation and share it here asap.

It's getting faster every day (I have it up to about 40 million "program candidate" tests per second now). But it's still only fast enough for very short programs. So, I wouldn't keep my hopes very high as for generating any complex code automatically any time soon hahaha

By santiontanon

Paragon (1353)

santiontanon's picture

28-04-2021, 05:50

I updated the "dev" 2.0 release with some optimizations to the search code, and some bug fixes: https://github.com/santiontanon/mdlz80optimizer/releases/tag...

I also added some documentation (early draft, just in case anyone wants to play with it) here: https://github.com/santiontanon/mdlz80optimizer/blob/master/...

Page 42/46
35 | 36 | 37 | 38 | 39 | 40 | 41 | | 43 | 44 | 45 | 46