Convert Python source code to SSA form

[pfalcon]

Intro: https://en.wikipedia.org/wiki/Static_single_assignment_form

Convert Python to SSA form. Baseline example:

a = 0

if a:
    x = 1
else:
    x = 2
print(x)

Schematic transformation to SSA would be:

a0 = 0

if a0:
    x0 = 1
else:
    x1 = 2
x2 = __phi__(x0, x1)
print(x2)

However, that's not executable form. Can actually make it executable with more syntactic noise:

from ssa_interp import *


# All vars should be initialized
x0 = x1 = None

a0 = 0

__label__("bb0")
if a0:
    __label__("bb1")
    x0 = 1
else:
    __label__("bb2")
    x1 = 2
# Crucial point - __phi__'s really should be first "instructions" of
# the basic block, even before a label.
x2 = __phi__({"bb1": x0, "bb2": x1})
__label__("bb3")
print(x2)

Where ssa_interp.py is:

__all__ = ("__label__", "__phi__")

_last_bblock = None

def __label__(lab):
    global _last_bblock
    _last_bblock = lab


def __phi__(choices):
    global _last_bblock
    return choices[_last_bblock]

The challenge is to convert arbitrary Python source code to such an SSA form. See how far we can go without explicit __goto__. The first suspects would be break/continue. But Aycock/Hosrpool aren't put down by them. Indeed, break/continue are static control flow, so we just add CFG edge, and it's not important what we have in the surface form.

The real suspect is of course exception handling. But while it's conceptually dynamic control flow, we can over-approximate it statically. That would lead to ugly multi-var phi's, but such is exception handling. That's why many languages afraid of it. Us shouldn't ;-).

[pfalcon]

@isidentical: Based on our IRC discussion, and your expressed interest, cc'ing you from here.

[pfalcon]

And I should elaborate on the interest of doing SSA transformation on the Python source form. Let's have a look at https://shedskin.readthedocs.io/en/latest/documentation.html#typing-restrictions :

Shed Skin translates pure, but implicitly statically typed, Python programs into C++. The static typing restriction means that variables can only ever have a single, static type. So, for example,

a = 1
a = '1' # bad

That's pretty hilarious restriction. Rewriting the code to be a little bit less trivial:

a = 1
print(a)
a = '1' # bad
print(a)

It's clear that first "a" has nothing to do with the second "a", they're effectively 2 different variables. And the transformation which can make this fact explicit is exactly SSA. It effectively splits live ranges of variables, so any simple usages like above will be unconflicted. Then it makes points where 2 related variables liveranges merge - explicit, using Phi functions. So it's possible to see where bigger conflict arises and deal with it (either error out, or introduce a union type):

if foo:
    a0 = 1
else:
    a1 = "1"
# Here we have real type conflict, and it's easy to see it, based on (static) types of a0 vs a1
a2 = phi(a0, a1)
print(a2)

[pfalcon]

Otherwise, I put up whatever bits I had on this in https://github.com/pfalcon/python-ssa . And that's mostly examples of manual conversion, with a "framework" to make such a converted code actually executable (based on the code already posted above).

To remind, SSA for acyclic code is generally straightforward. The real "fun" begins with loops. In particular, to preserve Python syntax, while requires preprocessing, where it's converted to infinite loop, with an explicit if-break to terminate the loop: https://github.com/pfalcon/python-ssa/blob/master/example_while1_ssa.py . All that of course to allow to insert __phi__s before this terminating if, so it used the right variable version.

Funnily enough, I was get around that, using the proverbial assignment expressions which caused so much controversy in the community. With my Pycopy hat, I'm not really excited about them, and don't intend to use in real life, the more funny that I found them useful for this task:

while (
        a1 := __phi__({"l0": a0, "l1": a2}),
    )[0] < 5:
    __label__("l1")
    print(a1)
    a2 = a1 + 1

The idea is to put all __phi__s into tuple (because in general there can be a few of them, then index to get an actual loop condition (which doesn't have to be a __phi__ result in a general case either).

I mention this as a possibility, but don't push in that direction, because it leads to other issues, like __label__ placement (would need to revert to older requirement of putting __phi__ before __label__ (as pictured in the original description above and which I fixed by now, as it's not intuitive).

[pfalcon]

@isidentical: So, if you have time/interest, you're welcome to play with it, e.g. try to convert some cases manually. Any feedback is welcome.

One another thing I may mention is syntax for __phi__. So far it's:

__label__("label1")
foo = __phi__({"label1": 1})

In other words, dict literal. This is for symmetry with the definition of label, string in both case. It would be trivially to switch to:

__label__("label1")
foo = __phi__(label1=1)

But that leads to Python syntax asymmetry, another manifestation of which is that you can "set" value by keyword, but when you want to "get" it, has to switch to a string. Clearly, Common Lisp (and Ruby?) is more consistent with their :symbol syntax. Well, we know that our favorite language is not perfect, just the best compromise overall ;-). So, I don't push forward with keyword syntax yet, but anticipate it makes sense to switch to it, as it's shorter and thus clearer syntax.

[pfalcon]

Btw, my conclusion from even this initial, manual work is that it should be possible to convert "any" structure language syntax to SSA form. Intuitive explanation is that program syntax already encodes (implicit) CFG of the program. Then SSA conversion doesn't change the CFG. Well, at most, trivial pre-transformations may be required, as in the case of while loop above. So, SSA algorithm would operate on full CFG with explicit edges, its result would be variable renaming and extra Phi statements, but afterwards, explicit edges can be dropped, and result will remain surface syntax structure of the program, as it was before.

[pfalcon]

Anyway, next steps expected steps in the direction of solution: add an AST pass to label basic blocks, then build CFG from basic blocks. Then, just implement SSA algorithm for the CFG ;-).

[pfalcon]

Btw, I definitely was aware of folks doing stuff like CFG construction and dominator tree on Python AST. As I already pinged @isidentical, I thought of maybe pinging other folks too to see if they maybe interested to go beyond towards SSA.

And this time, the github search brought something really interesting: https://github.com/usagitoneko97/python-static-code-analysis . That seems to be about what I have in mind: it's about Python, it's about SSA, and it even has (lengthy, very lengthy) associated texts! That's exactly what I'd like to do, except I see the final outcome as distilled code and tutorial, to teach all the interested people that SSA is simple (it's not). Thumbs up @usagitoneko97! It seems there actually will be "challenge" and "competition", and I'll be able to see how much I suck in grokking this stuff comparing to others. ;-)

[0dminnimda]

Nice! Going through the same path right now. https://github.com/usagitoneko97/klara seems like a useful reference implementation. And their explanation is good too https://klara-py.readthedocs.io/en/latest/cfg_ssa.html
And I'm really exited to see https://github.com/windelbouwman/ppci and how much people have acomplished!
Sadly pycopy, klara, ppci look like they are not longer in active maintenance, but oh well, new and better things will come up!