[pypy-dev] compiler optimizations: collecting ideas

Carl Friedrich Bolz cfbolz at gmx.de
Mon Nov 17 14:26:24 CET 2008

Hi Daniel,

sorry for the late response.

Daniel Furrer wrote:
> As part of an advanced compiler design course at our university (ETH
> Zurich), we have to implement an optimization (or various thereof).
> I've spoken with a couple of people who are, like me, very fascinated by
> Python.
> So I would just like to ask if somebody has any ideas on what we could do?
> Our constraints:
> - We are 4 persons, each willing to potentially spend around 4-6 full
> days of work.
> - We've been working on generating Control Flow Graphs, generating
> Static Single Assignment Form (inserting phi-nodes) and removing it
> again. We've also implemented techniques like constant folding, copy
> propagation, Common Subexpression Elimination etc.
> We're looking for:
> - Hints as to which python compiler would be best to work on. (The
> official Python compiler package seems very nice to work with
> actually... [and so does PyPy.])
> - If there are any requests in the area of optimization that we could
> have a look at
> Any feedback would be highly appreciated as well as pointers to specific
> bugs in the tracker and other relevant discussions.

I guess the problem for "classical" compiler optimizations applied to a
compiler producing Python bytecode is that most of them are potentially
unsafe. E.g. you cannot do CSE in Python, because any expression can
have arbitrary side-effects. Therefore it is very limited which
optimizations can be applied at all.

PyPy's translation toolchain works in SSI as an intermediate
representation (which is a sub-set of SSA). However, many of the
straightforward optimizations (constant-folding, copy-progragation,
inlining, a form of escape analysis) have already been implemented. Some
things are not done yet, like common subexpression elimination. We
didn't bother to implement them yet, because they are not as useful for
PyPy since we target C, and most C compilers can do theses things for us.


Carl Friedrich

More information about the Pypy-dev mailing list