Z80 peephole optimizer

Got a brilliant program idea? Let us know!

Moderator: MaxCoderz Staff

Post Reply
User avatar
qarnos
Maxcoderz Staff
Posts: 227
Joined: Thu 01 Dec, 2005 9:04 am
Location: Melbourne, Australia

Z80 peephole optimizer

Post by qarnos »

I always thought this would be a cool project, but I'd never get the time to do it myself.

The idea is a Z80 peephole optimizer. A peephole optimizer is a program which parses assembly code, breaks it down into "basic blocks" (blocks where flow control doesn't change) and optimizes by looking for code snippets which can be improved by an internal library of optimizations.

Example:

An optimizer might see this:

Code: Select all

sla l
rl h
and change it to this:

Code: Select all

add hl, hl
If this were linked to the back-end of a Z80 C-compiler (such as SDCC), it could be quite useful. It could also be useful for optimizing hand-written code where the programmer has missed something.
"I don't know why a refrigerator is now involved, but put that aside for now". - Jim e on unitedti.org

avatar courtesy of driesguldolf.
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

This can be tricky though, because the side effects might change in surprising ways, and such changes might break the program if the code relies on a certain behaviour of flags for instance, not to mention SMC (which is most likely not an issue with a C compiler though)...
User avatar
qarnos
Maxcoderz Staff
Posts: 227
Joined: Thu 01 Dec, 2005 9:04 am
Location: Melbourne, Australia

Post by qarnos »

CoBB wrote:This can be tricky though, because the side effects might change in surprising ways, and such changes might break the program if the code relies on a certain behaviour of flags for instance, not to mention SMC (which is most likely not an issue with a C compiler though)...
Yeah, that's the tricky part. If an program could "see" these effects, though, it should be ok. If the example code were followed by "or a", then it would be fine. That's the general idea behind "basic blocks" - pieces of code that are isolated from the rest of the program. I probably over-simplified it in my description.

I'm sure it could be done. Obviously, the more intelligent the optimizer is when it comes to things like flags, the better the results.
"I don't know why a refrigerator is now involved, but put that aside for now". - Jim e on unitedti.org

avatar courtesy of driesguldolf.
User avatar
GuillaumeH
Regular Member
Posts: 143
Joined: Fri 17 Dec, 2004 8:30 pm
Contact:

Post by GuillaumeH »

I thought the same thing as CoBB, but to solve this, one can imagine source code annotations to mark areas that must not be rewritten (SMC parts mostly).
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

GuillaumeH wrote:I thought the same thing as CoBB, but to solve this, one can imagine source code annotations to mark areas that must not be rewritten (SMC parts mostly).
That’s unfortunately a chicken and egg problem of some sort. Since the optimiser has limited means to find out what effects you want to preserve, how can you tell in advance which parts it will mess up? If you could, you could also write optimised code to start with...

The optimiser can only have guarantees about desired effects during the compilation from a high-level language. Assembly code simply doesn’t carry as much information about the algorithm, and there are inconvenient theoretical limits of inferring higher level constructs from (hand-written) low-level code in an algorithmic way. All in all, I don’t think there’s much to be gained this way in practice.
User avatar
GuillaumeH
Regular Member
Posts: 143
Joined: Fri 17 Dec, 2004 8:30 pm
Contact:

Post by GuillaumeH »

I was not clear sorry: I was talking about annotations written by the programmer.
CoBB
MCF Legend
Posts: 1601
Joined: Mon 20 Dec, 2004 8:45 am
Location: Budapest, Absurdistan
Contact:

Post by CoBB »

GuillaumeH wrote:I was not clear sorry: I was talking about annotations written by the programmer.
Yes, that’s how I understood it.
Liazon
Calc Guru
Posts: 962
Joined: Thu 27 Oct, 2005 8:28 pm

Post by Liazon »

what if there was a nice gui interface where this thing goes line by line and show the user 1 at a time what it's suggesting. kinda like a find&replace type of thing. maybe even make it some kind of extension off of texteditor or something. or IDE
Image Image Image
User avatar
Halifax
Sir Posts-A-Lot
Posts: 225
Joined: Mon 01 Jan, 2007 10:39 am
Location: Pennsylvania, US

Post by Halifax »

This is already tied into the backend of SDCC. If you check the SVN right now, you can see the file that contains all the peephole optimizations which are very numerous, verging on 300 the last time I looked.
Post Reply