[stella] First steps with 6502 superoptimizer

Subject: [stella] First steps with 6502 superoptimizer
From: "Fred Quimby" <c9r@xxxxxxxxxxx>
Date: Fri, 27 May 2005 19:03:05 -0400
If you want something done, you gotta do it yourself.

So I've started on writing a 6502 superoptimizer from scratch.  It's now 
starting to become functional, though it probably still has tons of bugs.  
I'll attach a DOS .exe for testing (call this one alpha version 0.01.)

Limitations: (there are many)
Probably has lots of bugs.
Only zero-page, immediate and implied addressing, and forward branches are 
allowed
(All other code treated as NOP.)
Input and output only via accululator at this time
No decimal mode yet.
Overflow flag not yet implemented.
PHP/PLP not properly implemented.
No self-modifying code allowed.
Will take eons to calculate code sequences longer than about 7 instructions.
Only one immediate per code sequence (will allow more later)
Only one Zero-page address (will allow more later)
Branch targets not displayed properly yet (though operands are.)

Good things:
All illegal opcodes implemented (that use the above addressing modes, that 
is.)
Useful and fast for very short chunks of code
Benchmarks itself (in MIPS) until a valid code sequence is found.
If it runs for more than a few minutes, it gives a rough estimate of how 
long it might take (but do not take the estimate totally seriously... It is 
accurate to +/- 1 order of magnitude)

How it works:

the program takes a short (SHORT!) 6502 binary, terminated with an RTS as 
input (stdin) and outputs superoptimized code to the screen (stdout.)  The 
program assumes input in the accumulator and output also to the accumulator, 
so it's only useful for short functions at this time.  To create a short 
6502 binary to run through the program, you can use dasm.  Here's an 
example, called test.asm, which zeros the lower 4 bits of A and shifts it 
right two bits.

                processor 6502
                include "vcs.h"
                include "macro.h"

                SEG
                ORG $F000
and #$f0
lsr
lsr
rts ; do not forget the RTS!!!!!

          END

use dasm test.asm -f3 -otest.bin to create a 5 byte file.  To run the 
superoptimizer with this file:

6502so.exe <test.bin

and within seconds, the program will output all code sequences that produce 
the same output, such as:

.0: 4b f0 ASR #f0
.1: 4a    LSR

.0: 4b f1 ASR #f1
.1: 4a    LSR

.0: 4b f2 ASR #f2
.1: 4a    LSR

.0: 4b f3 ASR #f3
.1: 4a    LSR

.0: 6b f0 ARR #f0
.1: 4a    LSR

.0: 6b f1 ARR #f1
.1: 4a    LSR

.0: 6b f2 ARR #f2
.1: 4a    LSR

.0: 6b f3 ARR #f3
.1: 4a    LSR

.0: 4b f0 ASR #f0
.1: 6a    ROR

.0: 4b f2 ASR #f2
.1: 6a    ROR

.0: 6b f0 ARR #f0
.1: 6a    ROR

.0: 6b f2 ARR #f2
.1: 6a    ROR

.0: 4a    LSR
.1: 4b 78 ASR #78

.0: 4a    LSR
.1: 4b 79 ASR #79

.0: 4a    LSR
.1: 4b f8 ASR #f8

.0: 4a    LSR
.1: 4b f9 ASR #f9

.0: 6a    ROR
.1: 4b 78 ASR #78

.0: 6a    ROR
.1: 4b 79 ASR #79

.0: 6a    ROR
.1: 4b f8 ASR #f8

.0: 6a    ROR
.1: 4b f9 ASR #f9

^C
and so on... it will run forever, producing longer and longer sequences.  
Comments/suggestions/bug reports welcome!

Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://stella.biglist.com

[demime 1.01d removed an attachment of type application/x-dosexec which had a name of 6502SO.exe]

Current Thread