search

rocky / elisp-bytecode

Let's document Emacs Lisp Bytecode (Lisp Assembly Program) instructions
178 stars 11 forks source link

Document optimizations performed #52

Open rocky opened 6 years ago

rocky commented 6 years ago

What kinds of optimization are performed? When were they introduced? Examples of optimizations.

vkazanov commented 5 years ago

In the main document you mention constant propagation.

But there's no constant propagation, only constant folding and dead code elimination, i.e. (byte-optimize '(let ((a 1)) (+ 2 a)) does not get compiled to a single constant 3. It doesn't work with lexical scoping enabled and it cannot work with dynamic scoping.

The example you showed ( (+ 2 3) optimizing to 5 ) happens because the + function has some specialized optimizing logic attached to it.

I wonder if it's possible to introduce a limited form of constant propagation for functions compiled with lexical scope enabled... It's a bit inconvenient using source-to-source transformations only, without a proper CFG, but should be doable.

rocky commented 5 years ago

But there's no constant propagation, only constant folding and dead code elimination

Okay. Please correct what I wrote in a pull request. You have looked at this in more detail than I have.

I wonder if it's possible to introduce a limited form of constant propagation for functions compiled with lexical scope enabled... It's a bit inconvenient using source-to-source transformations only, without a proper CFG,

I have code written in Python to create a CFG and give some basic summary information about basic blocks. That is in the https://github.com/rocky/elisp-decompile project though.

vkazanov commented 5 years ago

Okay. Please correct what I wrote in a pull request. In fact, I am thinking about it right now. :-)

I was writing an article about Emacs Lisp implementation, both the interpreter and the compiler. Right now it's a huge draft describing relevant subsystems. But it's really hard to put together a coherent narrative using that kind of material, and I am still not sure if I want to publish it.

I wonder if can reuse some of the work done to improve your manual.

You have looked at this in more detail than I have.

I think that's only relatively speaking :-) I have looked into the optimizer throughly but it's not like I know a lot about the VM itself.

But I think the part of the manual related to optimizations should be restructured. E.g., in byteopt.el there's a very clear separation between the source-to-source transformation framework and the peephole optimizer (just a single function really). The peephole part has a very typical implementation, while the source-to-source transformations are ad hoc, and very, ehm, "lispish".

written in Python

While it's definitely interesting to take a look at a CFG, a Python implementation makes it impossible to use it for, say, data flow analysis within the compiler :-(

larsbrinkhoff commented 5 years ago

@vkazanov, maybe this it outside the scope of your article, but perhaps it would be interesting to compare Emacs Lisp with Maclisp. As far as I can see, they are quite similar. E.g. both have obarray for looking up interned symbols.

vkazanov commented 5 years ago

@larsbrinkhoff When writing articles I usually try to keep a target in mind. Here I am aiming to improve my understanding Lisp optimisation approaches and use it to improve the current Emacs Lisp optimizer.

I don't know much about Maclisp, apart from what they say on Wikipedia. Is it's code worth looking at?

obarray for looking up interned symbols

I think that's a very popular approach in lisp implementations, no?

larsbrinkhoff commented 5 years ago

I don't think looking at Maclisp will help your understanding of the Emacs Lisp implementation.

rocky commented 5 years ago

While it's definitely interesting to take a look at a CFG, a Python implementation makes it impossible to use it for, say, data flow analysis within the compiler :-(

The code to create a CFG in Python isn't that complicated or long (espcially compared to the rest of the decomplier with its J Earely algorithm parser). I believe it is straightforward to port this portion into Emacs Lisp. However given all the other things needed, I'm probably not going to be the one to do it.

vkazanov commented 5 years ago

For me the question is not whether it's hard to build a CFG or not :-) the real problem is getting cfg-based optimizations into Emacs itself. Byte compilation is already relatively slow, adding machinery will only slow it down.

OTOH, this a path to many interesting possibilities... Proper constant propagation is really hard to do within the current framework. I had a chat with compiler people - they mostly mention newer SSA or traditional CFG-based approaches.

But that's a long discussion. Let's add some material into this book first! :-)