[pypy-dev] Contributing Polyhedral Optimisations in PyPy

[William ML Leslie]

On Fri, 18 Dec 2020 at 05:14, muke101 via pypy-dev <pypy-dev at python.org> wrote:
>
> I'm doing a computer science masters and am looking for an appropriate project to take on for a dissertation related to Polyhedral optimisations. Talking to my professor, we both think trying to implement the model and it's loop transformations in PyPy's JIT optimiser could be a good project to pursue, but before committing to anything I wanted to run this idea by the devs here who might be able to point out any hurdles I'd be likely to quickly come across that could prove difficult to solve at just a masters level, or whether or not these optimisations are actually already implemented in the first place (I have tried to google if this is the case and hadn't found anything, but can't be sure). I think this could have some good real world impact too as a lot of scientific code is written in Python and run on PyPy, and the Polyhedral model can offer substantial performance improvements in the form of auto-parallelization for these types of codes, which is why I'm interested in working on this for PyPy rather than CPython, although if anyone has good reason that I might want to look at CPython for this over PyPy please let me know.
>
> Appreciate any and all advice, thanks.

Hi! That's a great topic.

The challenge with implementing this in the pypy JIT at this point is
that the JIT only sees one control flow path.  That is, one loop, and
the branches taken within that loop.  It does not find out about the
outer loop usually until later, and may not ever find out about the
content of other control flow paths if they aren't taken.  This
narrows the amount of information available about effects and possible
aliases quite a bit, making semantic-preserving cross-loop
transformations difficult in many cases.

On the other hand, since you can deal with precise types in the JIT,
it's possible to narrow down the domain of discourse, which might make
it possible to rule out problematic side-effects.

Nevertheless, please dig and experiment.  You might find that a
combination of custom annotations and JIT work get you what you need.

-- 
William Leslie

Q: What is your boss's password?
A: "Authentication", clearly

Notice:
Likely much of this email is, by the nature of copyright, covered
under copyright law.  You absolutely MAY reproduce any part of it in
accordance with the copyright law of the nation you are reading this
in.  Any attempt to DENY YOU THOSE RIGHTS would be illegal without
prior contractual agreement.