[Sbcl-devel] Peephole Optimizer Update

[Jonathan Smith]

Hi,

So, I've got another version of the a peephole optimizer.
As requested, I have just done a diff.
It can be found here:
Https://sourceforge.net/projects/sbcl-peep-opt/files/

The filename is 'sbcl-peep.diff'.

This diff is between my version of 1.0.42 with peephole optimization, and the 1.0.42 version on the website.


This particular version only takes care of the circular move redundancy on x86 and x86_64. It also doesn't do any flow or deadness analysis, so you have, for example:

mov [ebp], ebx
mov ebx, [ebp]
getting replaced with:
mov [ebp], ebx

If you examine the .diff, I actually made very few changes to the original source code, The main points are adding a 'buffering' mode to instruction emission, as well as an 'values' field to scheduler instructions (which is really the arguments the instruction was called for emission with).

Then we are able to capture instructions as 'instruction' structs (as used by the scheduler), labels as 'label' structs, (as well as alignments as functions...) in a list.
Also we capture TNs/EAs within each created instruction (that the instruction was to be emitted with).

Because TNs are packed at emission time, they map directly onto machine registers, and are susceptible to comparison via sb, sc, offset, etc.

Because it is all captured, it becomes easy to peephole optimize the code.

There is also a basic declarative macro for defining optimizations, called 'define-pattern', and a macro called 'define-peephole-optimizer'.

Define-pattern is based on the arguments made to the instruction via the 'define-instruction' macro (you will notice that x86 optimization is different from the x86_64 definition, because 'mov' is defined differently...), the syntax is:

(define-pattern ...pattern... -> ...replacement... !! ...post-conditions...)
It does a very basic unification, variables in the unification are defined by symbols prefixed with ?. If the function passes unification, it returns a unified version of the replacement pattern.

The replacement pattern is then passed to the 'peephole-optimizer' lambda, (defined by 'define-peephole-optimizer', which is defined to include a variable length 'window'.

There is a bug in the peephole optimizer itself right now, in that it does not take care of the very important case, where the replacement pattern is longer than the optimizer pattern.

Anyway, it seems that I have met with some success with this project, and I welcome comments/thoughts on this.

I will note that (using a very rudimentary counter) compiling the system with this optimization on x86 seems to catch a couple of thousand redundancies, and compiling on x86_64 catches a few hundred... I'm not sure why there is the apparent difference (perhaps because there are fewer registers and memory locations on x86!). Once there are more peephole optimizations working there might even be some performance gains.

Thanks,

-Jon

[Jonathan Smith]

Hi,

https://sourceforge.net/projects/sbcl-peep-opt/files/
(file is sbcl-optimizer.diff)

This new version fixes a problem in the 64 bit where it wasn't matching all of the possible patterns.
Pretty much, 64 bit emits a lot of labels that are not used for jumps or anything, so during peephole optimization
this new version ignores the extra labels for the purpose of pattern matching, and leaves them in place.

On both platforms, the single optimization that I have is matched in about 2000 occurrences during compilation.

This version compiles the whole source, runs all of the tests properly.
I also compiled Maxima and CL-PCCRE with it.
It passes all of the tests (that are expected to pass) for both.

-Jon

[Nikodemus Siivola]

On 17 September 2010 07:48, Jonathan Smith <jonathan...@gmail.com> wrote:

> Pretty much, 64 bit emits a lot of labels that are not used for jumps
> or anything, so during peephole optimization
> this new version ignores the extra labels for the purpose of pattern
> matching, and leaves them in place.

Just checking: it ignores only labels without any jumps to them, right?

Cheers,

-- Nikodemus

------------------------------------------------------------------------------
Start uncovering the many advantages of virtual appliances
and start using them to simplify application deployment and
accelerate your shift to cloud computing.
http://p.sf.net/sfu/novell-sfdev2dev
_______________________________________________
Sbcl-devel mailing list
Sbcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel

[Jonathan Smith]

On Fri, Sep 17, 2010 at 2:49 AM, Nikodemus Siivola <niko...@random-state.net> wrote:

On 17 September 2010 07:48, Jonathan Smith <jonathan...@gmail.com> wrote:

> Pretty much, 64 bit emits a lot of labels that are not used for jumps
> or anything, so during peephole optimization
> this new version ignores the extra labels for the purpose of pattern
> matching, and leaves them in place.

Just checking: it ignores only labels without any jumps to them, right?

Cheers,

 -- Nikodemus

Without any references in the instructions. (So yes, jumps).

[Nikodemus Siivola]

On 17 September 2010 07:48, Jonathan Smith <jonathan...@gmail.com>

> https://sourceforge.net/projects/sbcl-peep-opt/files/
> (file is sbcl-optimizer.diff)

Hi, I wanted to put this on my merge queue for 1.0.50/51, and noticed
that the diff appears broken -- patch says that only garbage was found
at input.

Not sure what's up with that, but if you still have the tree around,
if would be great if you could regenerate the diff with

diff -ruN sbcl-old sbcl-new

It doesn't look _too_ hard to patch in manually if you've lost the
tree... but I'd rather not. :)

Cheers,

-- nikodemus

------------------------------------------------------------------------------
vRanger cuts backup time in half-while increasing security.
With the market-leading solution for virtual backup and recovery,
you get blazing-fast, flexible, and affordable data protection.
Download your free trial now.
http://p.sf.net/sfu/quest-d2dcopy1

[Jonathan Smith]

Hi, glad to see some interest in this. :-)

Are you looking for the output of this command:

diff -ruN ~/Dropbox/sbcl-1.0.42-peep/ ~/Dropbox/sbcl-1.0.48/ > peephole-diff.txt

or this command:

diff -ruN ~/Dropbox/sbcl-1.0.42 ~/Dropbox/sbcl-1.0.42-peep// >
peephole-diff.txt

I've attached the results of the first command In compressed form. If
you need the second I believe I can do some digging on my home
computer and find a version of sbcl-1.0.42 there.

[Jonathan Smith]

I thought about it and decided that the second version would likely be
easier to apply as a patch.

Attached is a diff of 1.0.42 against the peephole optimizer version

It seems to have applied cleanly against 1.0.48 on my machine.
('patch -p5 -i patchfilename' in the sbcl 1.0.48 directory)

I compiled and ran tests and it was an 'apparent success'.

[Nikodemus Siivola]

On 24 May 2011 19:47, Jonathan Smith <jonathan...@gmail.com> wrote:

> I thought about it and decided that the second version would likely be
> easier to apply as a patch.

That was what I meant, yes. Sorry for being unclear. I'll see if I can
review and forward port it over the next week or two.