Tulgo - First steps in partial rewrite of the core algorithm [2013-12-29]

[⚛]

A short software engineering story:

https://atom-symbol.rhcloud.com/a/2013-12-29-tulgo-partial-rewrite/

[Dave Cheney]

Thanks for the writeup.

With respect to the clearflags example, is this something that can be
resolved via a peephole optimiser, or is that just closing the gate
after the horse has bolted ? Or more accurately after the compiler has
decided that ebx is not longer available.

On Sun, Dec 29, 2013 at 9:33 AM, ⚛ <0xe2.0x...@gmail.com> wrote:
> A short software engineering story:
>
> https://atom-symbol.rhcloud.com/a/2013-12-29-tulgo-partial-rewrite/
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-dev+...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[⚛]

In my opinion if the peephole optimization pass is among the later optimization passes (which it is) then it isn't actually an optimization for use in a compiler. A compiler should in the first place try to avoid printing the instructions. A nice assembly code should leave very little opportunity for peephole optimizations.

The main problem is that it is impossible to feed information from peephole optimizations back to the core of the optimizer because peephole opts are based on string pattern matching.   For example, if the peephole optimizer deletes an assignment to register ebx it may make ebx available to the register allocator. The new information about ebx changes the assumptions that caused the compiler to print the assignment instruction, but the core has no idea why ebx is free and has no idea what to do about it.

Secondly, peephole optimizations are unsafe. For example they cannot be blindly applied to NaCl code or self-modifying code.

On Saturday, December 28, 2013 11:54:40 PM UTC+1, Dave Cheney wrote:

Thanks for the writeup.

With respect to the clearflags example, is this something that can be
resolved via a peephole optimiser, or is that just closing the gate
after the horse has bolted ? Or more accurately after the compiler has
decided that ebx is not longer available.

In relation to your last sentence: In the clearflags example the compiler is choosing paths that do not involve ebx at all.

[shka...@gmail.com]

Here is another interesting idea on optimization: http://theory.stanford.edu/~sbansal/pubs/asplos06.pdf Basically they propose to find peephole optimization automatically.

I guess this db can be extracted/computed once and shipped as a part of compiler.

[Michael Jones]

Do not overlook Alexia Massalin's superoptimizer...

http://www.stanford.edu/class/cs343/resources/superoptimizer.pdf

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

(Note: this email has been shared with you under the terms of Regulation 23)

[⚛]

On Sunday, December 29, 2013 4:42:15 PM UTC+1, shka...@gmail.com wrote:

Here is another interesting idea on optimization: http://theory.stanford.edu/~sbansal/pubs/asplos06.pdf Basically they propose to find peephole optimization automatically.

I guess this db can be extracted/computed once and shipped as a part of compiler.

I will be thinking about this, but I do not expect Tul to closely follow the method described by the article.

[shka...@gmail.com]

I'm curious to see if it the method is practical overall. Where do you host your code? Is it open to the public?

[⚛]

On Tuesday, December 31, 2013 3:08:34 AM UTC+1, shka...@gmail.com wrote:

I'm curious to see if it the method is practical overall. Where do you host your code? Is it open to the public?

It seems irrational to me to publish the code. The open source community is currently based on an economic model that isn't working for me.

A prior version of Tul was on github, but it is no longer there because I erased the project.