Lesson 6: Static Single Assignment

[sampsyo]

⚠️ Warning: Implementing the into SSA and out of SSA transformations can be trickier than it looks!

[UnsignedByte]

Code

Into SSA

I decided to use the new get and set version of SSA, which also meant that some of the algorithm (mainly rename had to be slightly modified to use this method. Mainly, I needed a way to generate both unique shadow names as well as unique non-shadow names. For this, I used the fact that a get instruction may only occur once in a basic block for a given base variable, and just generated unique shadow names based on the block they were generated in.

In my renaming, I modified it slightly by first adding v.shadow: <type> = get; for all the phi nodes in the basic block. Then, instead of generating phi nodes, I just did set v.shadow v; in the successors. Additionally, here was where I tracked whether a variable was undefined. This was done by checking if the source of the set was already in the name stack, as otherwise this means that the variable was not defined in any of its dominators, so an undef is necessary.

When handling undef, I decided to just collect a set of undefined variables and define them all in the entry block. I could have chosen to set them as undef right before the set instruction, but doing this in the entry block meant that at most one undef will be added to the program for each variable, which would lower the total number of executed instructions.

There was also one more nuance - if a function argument needs a phi node in the entry block (assuming the entry block is named) this leads to a problem where we generate a get with no corresponding set. Therefore, I needed to generate an empty entry block above all other blocks to prevent this from happening if the entry block has a label.

From SSA

Because I used the get/set method, from-ssa became incredibly simple - I just removed all gets and changed all set x y to x: ty = id y.

Testing

I tested my implementations by checking the outputs of the program execution against the unoptimized execution, to make sure that changing to SSA did not affect behavior. I also tested using brench against all the benchmarks in bril, where I found a bunch of different bugs in my implementation but also an interesting one within dead-branch.bril where immediately jumping to loop_end leaves v4 undefined, which brilirs for some reason catches and errors despite this branch not actually being run (I assume it does some well formedness checks?). This errors in non-ssa but because we add the v4 = undef in the SSA conversion brilirs no longer errors.

I also implemented a quick is-ssa sanity check that simply runs through each function and makes sure that no value is ever written to more than once (keeping a running set of written values).

Summary

As you warned, implementing into and out of SSA was more complicated than I expected (mainly for into SSA). I spent most of my time fixing bugs and dealing with edge cases like phi nodes in entry blocks, and undefined values. Overall, I would say that I deserve a star as I made sure the SSA tests worked on the full suite of benchmarks, which ended up finding a lot of edge cases I would not have thought of myself.