Lesson 6: Static Single Assignment

[sampsyo]

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

[5hubh4m]

SSA Conversion

Here is my code for converting Bril functions into and out of SSA. It contains two functions:

• ssa :: Function -> Function converts a function into SSA
• ssa' :: Function -> Function replaces all the phi instructions in a function with copies at relevant points (thereby converting the function out of SSA).

The implementation mostly follows the class pseudocode. First step is recovering a mapping between blocks, and the set of variables for which phi nodes must be added to them, which is done by the function addPhi. The next step performs recursive stack based renaming. This was pretty interesting to implement. I created a function rename which takes in a CFG (for the successors), the instructions, the previously obtained blocks to phi nodes map, a variable to stack map, and a node in the domination tree and then performs renaming on the instructions, phi nodes, updating the stack; and then recursively calls itself on it's children sequentially.

Testing

I did the most basic type of testing. I wrote a Turnt suite that checks whether the SSA conversion is indeed SSA using the is_ssa.py file. Then I wrote a brench suite that both compares the outputs from the baseline program and program after an SSA roundtrip (thereby verifying correctness) and calculates the total_dyn_instructions to quantify the overhead of the SSA roundtrip. Both suites use the test programs found in here.

These two combines confirmed that the SSA conversion is correct. The average overhead for these small programs was 34% i.e the roundtrip programs executed 34% more dynamic instructions on average.

Experience

This was indeed the hardest assignment yet with so many corner cases that need to be considered, especially in Haskell (why do I hate myself?) The two big ones are variables undeclared in a branch and how to incorporate function arguments. I'll briefly talk about how I handled these two:

Undefined Variables

There are two types of undefined variables that I encountered: variables that are explicitly undefined in another branch (eg. for already SSA programs) or variables in loops.

For instance consider this already SSA program:

.entry:
  br cond .true .false;
.true:
  a: int = const 1;
  jmp .exit;
.false:
  b: int = const 2;
  jmp .exit;
.exit:
  c: int = phi a b .true .false;
  print c;

The variable a is undefined in .false and b is undefined in true. Another example of a loop:

.entry:
   ... // no x defined here
.loop:
  x: int = const 1;
  cond: bool = call @fn x;
  br cond .loop .exit

In this case x is a variable that is undefined from the CFG edge entry -> loop but is defined from the CFG edge loop -> loop.

My solution handles this in two ways: detect if the variable has been defined along a certain branch and only add to the successor's phi node if it is defined; and if a phi node is detected to have a single entry, try to merge it with other phi nodes. So for instance the first program might be translated into:

.entry:
  br cond .true .false;
.true:
  a.1: int = const 1;
  jmp .exit;
.false:
  b.1: int = const 2;
  jmp .exit;
.exit:
  a.0: int = phi a.1 .true;
  b.0: int = phi b.1 .false;
  c.0: int = phi a.0 b.0 .true .false;
  print c.0;

The definitions a.0 and b.0 will throw an error because exactly one of those will be undefined. Therefore, we merge the instructions for a.0 and b.0 with the phi node, like so:

  a.0: int = phi a.1 .true;
  b.0: int = phi b.1 .false;
  c.0: int = phi a.1 b.1 .true .false;

are merged into the phi node for c.0 as follows:

  a.0: int = phi a.1 .true;
  b.0: int = phi b.1 .false;
  c: int = phi a.1 b.1 .true .false;

So that the definitions a.0 and b.0 can be cleaned up by TDCE. Note that we cannot simply remove single entry phi instructions as this might change program semantics. Similarly, the loop program is translated into:

.entry:
  ... // no x defined here
.loop:
 x.0: int = phi x.1 .loop;
 x.1: int = const 1;
 cond.0: bool = call @fn x;
 br cond.0 .loop .exit

This way the definition of x.0 can be removed by a TDCE pass. This approach does necessitate a TDCE pass, but I find that trade-off acceptable. In my tests I use the TDCE pass implemented in Scala in the previous assignments, and it all fits together because of the Bril JSON format!

Function Arguments

Consider this program

@main(x: int, cond: bool) {
.entry:
  one: int = const 1;
  x: int = sub x one;
...
.another:
  x: int = const 5;
  jmp .entry;
}

There is a very subtle problem here. To convert this, we need to add a phi node to the entry block for x which chooses which x's value to take depending on whether you are starting from the entry block or jumping from another block. However we have no such phi instruction since entry does not have a predecessor. To remedy this I add another fake entry block which basically contains copy assignments:

@main(x: int, cond: bool) {
.b0:
  x: int = id x;
  cond: bool = id cond;
.entry:
  one: int = const 1;
  x: int = sub x one;
...
.another:
  x: int = const 5;
  jmp .entry;
}

The the translation can proceed as follows:

@main(x: int, cond: bool) {
.b0:
  x.0: int = id x;
  cond.0: bool = id cond;
.entry:
  one.0: int = const 1;
  x.1: int = phi x.3 .another x.0 .b0;
  x.2: int = sub x.1 one;
...
.another:
  x.3: int = const 5;
  jmp .entry;
}

[charles-rs]

wow we got the same overhead figure!

[sampsyo]

Excellent work, @5hubh4m! Thanks for the very detailed discussion of the trickery involved in handling undefined variables. Relying on TDCE to clean up "impossible" edges seems like a solid approach in general.

One issue I have occasionally run into with a similar (not identical) approach in the past was the existence of cycles of these dead phi-nodes: in a loop, they might create a situation where no phi-node is actually useful, but they all mutually depend on each other in a cycle. That confused the TDCE as previously written. Did this happen to bite you along the way?

[5hubh4m]

The idea of cycles in phi nodes is very interesting. I didn't specifically run into an example that dealt with that, nor can I generate an examples where there are cycles in the phi nodes added to a block (I can think of cycles in case there are already phi nodes in a block).

In my method, I keep a map from block labels to the "extra" phi nodes that are to be tacked on to the beginning of that block, and those are identified by the original variable they refer to. I cannot come up with a counter example where there can be cycles within these "extra" nodes.

[charles-rs]

SSA and fun stuff!!

here is my implementation

Available options:

-h, --help print this help text
-s, --ssa convert a BRIL program into SSA form
-r, --ssa-rt convert a BRIL program into SSA, and then back
-g, --gvn use the global value numbering optimization
-v, --gvn-ssa use global value numbering, but stay in SSA form

Experience

I implemented the to ssa phase to test the last assignment, so that took a little weight off. The most annoying part of the actual implementation was probably dealing with values not being defined on every path, so i used a special value: 'undefined This was mostly just since it is easy to compare against as it's a different type from the strings that were used elsewhere.

How to design a CFG?????

alas we return to my lack of skills with choosing data structures lol. I have moved to an object based cfg, where there are basic block objects that keep track of their instructions and label separately. There is also a field for the "outgoing edge(s)" which is either ret, br, or jmp, but the br is redundant since that instruction needs to be in the instruction list. The jmp does not, as it can be completely determined by its label, and we can reconstruct the code by tracing through one lucky path that will be just fall through.

Now, where to φ functions fit into this? Initially, i added a separate slot in my basic block class for them, but this, it turns out, is not the move. It is much more convenient to just push them onto the list of instructions, so I did that.

Beyond that for implementing SSA, I didn't use a hashmap or the stack structure described in class. I will mention this again when i talk about GVN, but it seemed much more intuitive to me to use a persistent map (probably some kind of balanced binary tree). While the runtime isn't as nice as for other "better" environment data structures, it should be fine here, and it wouldn't be so hard to swap out for something with better Ο. The really convenient part of this structure is someone else implemented it so I don't have to.

SSA -> not so static anymore

the "easy part" (apparently). This was a little more subtle than I expected it to be, and I was barking up the wrong (maybe) tree for a while with undefined values. I ended up initialising anything that was EVER undefined to 0 in the start block, which is something of a penalty for runtime, but given that there is no way to jump into the start block, it's constant. I feel like there really should be a better way of doing this, but maybe this is a byproduct of the lack of undefined behavior in BRIL (not that this is a bad thing!!).

GVN

I shamelessly stole the implementation from this paper, since I was having some trouble getting it to work on my own. Hopefully this isn't too egregious, as it is similar to the level of pseudocode we see in lecture, though I did give it an honest effort without this. The main thing I was missing was the order of the traversal and pushing changes to the φ functions in the succ blocks. Unfortunate.

After copying this algorithm, some programs worked right away, which is always quite the joy, but certainly not all of them. I had to make a couple adjustments: Some things didn't have canonical homes when I looked them up, so I changed the lookup behaviour to return the key back to you instead of NIL when the lookup failed. This is to be expected, as it happens when there are arguments to the function. There is probably a more "elegant" solution to this, but this was what I could think of that was easy to implement, and easy to convince myself it was correct.

The next issue I ran into was with effectful operations: if you malloc two arrays of size n, GVN should NOT alias them, same for calling the same function a few times. I fixed this by changing the representation in my value table, and uniquifying the op when it was effectful.

This algorithm also called for a "context" data structure, which the paper described as a hashtable that could snapshot and rollback to those snapshots, so i whipped out the persistent map again, which worked well.

Testing

For the life of me, I could not get brench to work, and i'm really not sure why. Luckily, I was able to reimplement most of the functionality in bash, since python is still hard for me to understand. I run all my different options, put the dynamic instructions into a CSV, and append stdout to a file for each flag. After each run, I print the md5sum of each of these files, and can visually inspect if they are the same. This could be automated pretty easily, but it wasn't necessary, and I was more interested in the CSV.

We want to see how these things changed the performance, so I ran through the output.csv with a small awk script to collect averages and print them nicely. I normalized everything and show average percent speedup:

gvn-ssa over ssa:	 5.20%
gvn over ssa-rt:	 5.16%
gvn over init:		-32.45%
ssa over init:		-34.28%
ssa-rt over init:	-35.85%

We can see that SSA results in ~34% slowdown over the initial code, with the round trip back to non-ssa adding another ~1.6%. The global value numbering recovers about 5% of this performance, but not nearly enough to offset the SSA. This could probably be improved with a more impressive GVN implementation; i pretty much only did syntactic equivalence and commutativity. Copy + constant propagation would likely help some more, and if i get it implemented before midnight i'll update here.

UPDATE

I'm going to leave the above part as is, as a way of documenting progress. I have since updated the global value numbering to do constant propagation as well as be aware of the id operation, giving the numbers

gvn-ssa over ssa:	68.90%
gvn over ssa-rt:	70.50%
gvn over init:		 7.48%
ssa over init:		-34.28%
ssa-rt over init:	-35.85%

This is really cool if you look at the third row, since there was actually a 7% speedup using global value numbering over the initial code. The reason that gvn is faster than gvn-ssa is that I ran trivial dead code elimination on everything when it was done, and this gave more opportunities to get rid of code. I find the fact that there is a 70% speedup over the SSA code pretty impressive. The typescript compiled benchmarks are surely at least partially responsible for this, as they do a LOT of copying, so adding the id feature to the GVN was a big step up.

Challenges

so, when we eliminate redundancy this aggressively, it is possible to arrive at

a = φ b c
x = φ a d

which is a problem, since I was working with the assumption that the phi functions are all calculated in parallel (which isn't true, but I didn't think of them as affecting each other even when they could)

Initially, I thought i could try to reorder them to avoid this, but it is possible to have cycles. I ended up introducing more temp variables, so the above code would turn into

tmp = φ b c
x = φ a d
a = id tmp

This exposes an interesting property of SSA that I hadn't really thought about. In the φ functions, there are potentially two "versions" of a variable: the one that comes in, and the one that has been defined by the φ function, so this took some extra care, but even with these extra moves, there is a speedup!

I think it should be possible to look for cycles, do some kind of DFS through the dependency graph of φ functions, and then use fewer moves to fix things when a cycle appears, but I am wayyyy too tired to implement that right now, so maybe another day :)

[sampsyo]

Super impressive that you got GVN working on the SSA representation. It's absolutely not cheating to use Preston's OG GVN paper to do it; anyone sensible would do that! And using a persistent map to do environment push/pops is a pretty good idea. Awesome work!

And yes, it is especially gratifying that converting into SSA enabled an optimization that was able to overcome the overhead of converting into SSA. Yay!

Just a quick comment on your note about undefinedness in SSA:

I feel like there really should be a better way of doing this, but maybe this is a byproduct of the lack of undefined behavior in BRIL

I'm actually not sure there is! It's inevitably a kind of messy thing. I think Bril would need a special-purpose way to create undefined values (like LLVM's poison) to make this un-messy. Maybe it's more fun this way, though?!

[sampsyo]

Also, hella weird that brench never worked for you… I'm kinda stumped. Maybe I can look at your machine to debug someday.

[charles-rs]

I'm actually not sure there is! It's inevitably a kind of messy thing. I think Bril would need a special-purpose way to create undefined values (like LLVM's poison) to make this un-messy. Maybe it's more fun this way, though?!

Ah ok, well that makes me feel a bit better about not figuring something nicer out. I though that if we assumed that any undefined variable could be referenced, and would just give some undefined value, it would be easier, but this might not be the case

Also, hella weird that brench never worked for you… I'm kinda stumped. Maybe I can look at your machine to debug someday.

I just reran it for good measure, and yeah, still doesn't work. Happy for you to take a look at it some time, as brench seems like a very useful tool! (and if i don't get it working it looks like i might end up slowly reimplementing it...)

[sampsyo]

Yeah, I think it would be a lot simpler if referring to an undefined variable was OK. But allowing that is questionable for other reasons.

[atucker]

My code is here.

Testing

I tested in two ways.

The first was to run is_ssa.py on all of the tests from to_ssa and the programs in the benchmarks, and checking that my code always produced something in ssa. This was true, except for relative-primes.bril for some reason which I wasn't able to figure out. So the code mostly works, but is not 100% there. These tests are in compiler/test/to_ssa_makes_ssa.

The second way was to run all of the test programs in to_ssa (with made up arguments if needed), and save those outputs using turnt --save on a script of bril2json < {filename} | brili {args}. Then, I actually ran my ssa'd code bril2json < {filename} | python ../../ssa.py to | brill {args} to check if it produced the same output. This one always worked! But also it's a little sad since it ran on fewer programs.

Implementation

At first, I noticed that figuring out all of the ways that a variable could get named is really similar to reachability analysis. So, possibly unreasonably, I tried to do my insert ϕ-nodes step without the pseudocode, and just looking at the results of my reachability analysis from a previous assignment. This kind of worked, but it ran into issues where it didn't really know what the name of a variable should be after coming out of a basic block. This might have been fixable by just doing a pass where 1) a phi node is added whenever multiple versions of a variable reach a block, 2) each block goes through and renames everything that it needs to + stores the final variable names, 3) we go back and add all of the end-of-block variable names to phi blocks that didn't get names when we were renaming everything. This seems like it would work to me, but implementing SSA has taught me the humility to realize that that could very easily be not-quite-right in a subtle and challenging manner.

After that adventure, I stuck closer to the class pseudocode.

"Add a phi node if we haven't" turned out to hide a ton of complexity around when exactly a phi node should get added. I still wound up using my reachability analysis to figure out what should get added, but there were a few snags around how to handle definitions which are coming from the block that we're currently considering adding to. In retrospect, it makes sense that SSA is tricky in the case where a block both defines and uses a variable. In the end, I wound up adding a block's successors instead of the block if I wanted a phi statement that pointed to the block that was currently running, and creating a new entry block if I need to use a phi block to refer to the argument if the code starts running.

I also thought that a phi block would always need to return defined variables, but looking at some of the output for the test code, I realized that it was okay to return __undefined if we wouldn't actually use that variable on that code path.

I didn't actually do from_ssa yet, though I'll update this comment in a clearly-after-midnight section if I do.

Submitted after deadline:

After the deadline, I finished from_ssa, implemented here.

Testing

I tested this by just doing an ssa roundtrip (python ssa.py to | python ssa.py from) and then running that code with brill and made-up arguments to check that this resulted in the same answers on the test code here. Since the main goal for from_ssa is just correctness, this seemed like a reasonable amount of testing, though clearly it would be better to test on more programs.

Implementation

This wasn't nearly as bad as to_ssa, though there was an issue where the id instructions being generated by getting rid of phi instructions could build up and refer to each other, and so I had to jankily put them into an order that works (implemented here).

[charles-rs]

i think this is due next tuesday btw

[atucker]

Oops. My bad!

[sampsyo]

Indeed; sorry for the needless rush! But it was cool to hear how things were going in between the milestones. And interesting detour through an attempt to use reachable definitions to insert phi-nodes!

I think referring to a special __undefined variable is a sensible approach to partially-undefined phi-nodes… you will need some trickery, though, to make sure all of those get cleaned up when converting back out of SSA (to avoid having foo = id __undefined copies that would otherwise crash). Did this become a problem (and did trivial DCE solve it)?

Also, FWIW, you can try the brench tool to automate the process of checking that a program's output doesn't change after optimization.

[tonyjie]

SSA

My code is here

into SSA transformation

to_ssa.py is the implementation that transform a normal bril code into its SSA form.

It can be tested as follows, , which is actually running:

bril2json < {filename} | python ../to_ssa.py | bril2txt

cd to_ssa/
turnt *.bril

One thing worth mentioned is dealing with variables that are undefined along some paths. I need to look at the stack and see if the argument variable in phi node is actually defined or not. Set it as __undefined if it's not.

I also spent a lot of time in the beginning thinking of how to determine the number of args and labels in the phi node at each block. That's because I make it wrong at the beginning. I thought when inserting phi node at step 1, we need to know where the argument variables come from (in which block are they defined) and set them as labels. However, I found that the labels are just simply the predecessors of the block!

out of SSA transformation

from_ssa.py is the implementation that transform SSA-form code into normal bril code without phi-nodes.

It can be tested as follows, which is actually running:

bril2json < {filename} | python ../to_ssa.py | python ../from_ssa.py | bril2txt

cd from_ssa/
turnt *.bril

SSA Roundtrip Test

We can also stitch the to_ssa and from_ssa and dce together, and then use brili to test if the result is still correct. The testcases are copied from the bril repo.

Here dce.py is added to help remove unused variable. If I don't do Dead Code Elimination, brili will raise an error error: undefined variable __undefined

It can be tested as follows, which is actually running:

bril2json < {filename} | python ../to_ssa.py | python ../from_ssa.py | python ../dce.py | brili {args}

cd from_ssa/
turnt *.bril

Limitations

to_ssa_fail. dir contains the special testcases that this implementation haven't covered yet.

• if_ssa.bril is bril code with phi nodes. Current implementation doesn't support bril program with phi nodes. To support it, I should also give the destination of phi node a fresh new name, and save it in the stack and maintain it. But my implementation is kind of complicated (messy...?), so I just choose to not support it currently XD. Hope it didn't influence a lot.
• loop-branch.bril contains several functions and call op. This need some additional effort to analyze its control flow graph, etc.

[sampsyo]

However, I found that the labels are just simply the predecessors of the block!

Yes! Awesome! This is a great summary of a tricky part in making this work.

And it's also interesting to hear about the potential for supporting code that already has phi instructions in it. In principle, it should be possible, but I admit it's a little weird!

[JonathanDLTran]

Summary

My code is located at: ssa, dce, gvn. Tests are at to-ssa, from-ssa and gvn.

I implemented to-SSA and from-SSA, and then tested the transformations to make sure they worked correctly. This included using them in a "round-trip" fashion. To check correctness of SSA form, I use the is_ssa function every time a transformation is done to make sure the program is a well-formed SSA program.

To try to remove more phi nodes, I tried global value numbering using the dominator tree approach as documented in Value Numbering by Briggs, Cooper and Simpson. I then added on aggressive dead code elimination from the powerpoint slides: http://www.cs.cmu.edu/afs/cs/academic/class/15745-s12/public/lectures/L14-SSA-Optimizations-1up.pdf

Testing

I created tests as before for both the Bril to SSA pass and SSA back to normall brill pass. For the SSA back to normal Bril tests, I used tests from the original to-SSA output. I compared outputs without to-SSA, at the midpoint after to-SSA was run, and then after from-SSA was run, making sure they were identical.

For GVN testing, I wrote GVN tests and ran the GVN pass making sure the resutls were the same before and after.

I also tried some larger programs, using the Bril benchmarks that use integer instructions, but not floats nor pointers. For these, I checked GVN on the program, making sure the result was the same as not running the pass.

Optimization

For most of the Bril benchmarks, GVN was not able to identify much optimization potential. The trivial DCE also has some issues to identify dead instructions in basic blocks, if the instruction was used in the defined and used, but not used after some basic block in the control flow graph. I instead wrote a DCE pass on top of the SSA to identify instructions that were dead. Initially, I wanted to use a worklist style algorithm to remove more instructions, but could not figure out the relationship between different basic blocks and which instructions could be killed. I eventually used the algorithm documented in: http://www.cs.cmu.edu/afs/cs/academic/class/15745-s12/public/lectures/L14-SSA-Optimizations-1up.pdf
as a means to find more dead instructions. Along the way, I discovered that this algorithm fails to work when there is a trivial infinite loop. I modified it to take into account all loops, by looking for any backedge in the graph. Therefore, the DCE algorithm I wrote identifies less dead instructions.

Interestingly, the DCE algorithm finds many dead instructions, most of which are Phi nodes that the GVN algorithm fails to eliminate. For example, running the sum-divisors.bril benchmark with SSA using the command bril2json < int-benchmarks/sum-divisors.bril | python3 ssa.py --to-ssa=True | brili -p 1000 yields 711 dynamic instructions. Running with dce enabled using the command bril2json < int-benchmarks/sum-divisors.bril | python3 dce.py --adce=True | brili -p 1000 gives 513 dynamic instructions. Running with just gvn enabled using the command bril2json < int-benchmarks/sum-divisors.bril| python3 gvn.py --gvn=True | brili -p 1000 gives 704 dynamic instructions. Running with gvn after the dce pass using the command bril2json < int-benchmarks/sum-divisors.bril | python3 dce.py --adce=True | python3 gvn.py --gvn=True | python3 dce.py --adce=True| brili -p 1000 gives 511 dynamic instructions. Running DCE after GVN thereafter yields no further instruction cleanup.

Perhaps it is not surprising to see that DCE cleans up so many instructions, because when using bril2txt to examine the optimized program, many of the original phi nodes created by the to-SSA pass are eliminated. Meanwhile, these phi nodes are no redudant, so they are not eliminated by GVN.

However, all of these optimizations are actually end up adding instructions, as running bril2json < int-benchmarks/sum-divisors.bril | brili -p 1000, with no transformations actually gives 417 dynamic instructions total. The additional instructions created are likely from the added phi nodes that cannot be eliminated.

Challenges

One challenge was that I could not get brench to work. I wanted to compare the outputs,rather than the number of dynamic bril instructions executed, but I could not get this work.

Other challenges relate to SSA, where there were many edge cases, and I had to debug many different tests to get the implementation to work. Edge cases also caused issues in global value numbering, for example, with arguments, that did not have a number.

[sampsyo]

Awesome! Making a fancier DCE pass work is a great idea to help clean up from SSA is a wonderful idea; I'm happy to see it mostly worked. And cool that you got GVN working too!

Too bad that brench never worked for you. Can you elaborate on what the symptoms were? I can possibly help you get it running for next time!

[JonathanDLTran]

For the Brench problem, it seemed like I was able to measure the number of dynamic instructions executed using the -p flag for brili (but it reports they are not the same), and I was not able to compare whether the stdouts of the 2 passes were identical using brench. I ended up having to do the comparison manually.

[sampsyo]

Got it—as we discussed synchronously yesterday, it seems like the issue was realizing that brench can do the comparison for you automatically.

[anshumanmohan]

My code is here.

I think my code for to_ssa is quite close, but is not all the way there. There are a few little details to do with stack-management and dominance frontiers that I've not quite nailed down. It would have been super get it right, but sadly I need to move on to other things. My from_ssa looks good to me.

I tested my code with turnt throughout. I made three directories, one each for to_ssa, from_ssa, and the full round trip. I copied over the examples from the reference repository, which has handy "expected programs" in SSA form. As suggested once before, I used list sorting to de-noise my turnt outputs a little.

I found two(!) bugs in my domination-related work from last week, one of which was exactly in the line of python poetry I was so proud of. No rest for the wicked. I'm not sure if this is what was expected, but there is some cleverness in the way I deal with phi nodes. I only add new phi nodes for new variables; for old variables I extend the args and labels arrays of existing phi nodes. This means that, at the end of the phi-node-adding pass, phi nodes that still just have singleton args are redundant and can be cleaned up. I do this in a quick additional pass before renaming. It is renaming that gave me the most trouble.

[sampsyo]

Fair enough; sounds good! I'd be curious to hear about what the bugs were in the CFG analysis stuff from last time; that seems interesting.

[barabanshek]

My code is here: to_ssa. So far, I only implemented to_ssa and tested it on examples/test/dom/loopcond-front.bril and some other test cases that do not require argument passing. Bellow is an example for loopcond-front.bril when also running DCE to eliminate unnecessary phi nodes.

Original:

# ARGS: front
@main {
.entry:
  x: int = const 0;
  i: int = const 0;
  one: int = const 1;

.loop:
  max: int = const 10;
  cond: bool = lt i max;
  br cond .body .exit;

.body:
  mid: int = const 5;
  cond: bool = lt i mid;
  br cond .then .endif;

.then:
  x: int = add x one;
  jmp .endif;

.endif:
  factor: int = const 2;
  x: int = mul x factor;

  i: int = add i one;
  jmp .loop;

.exit:
  print x;
}

SSA + DCE

@main {
.entry:
  x_0: int = const 0;
  i_1: int = const 0;
  one_2: int = const 1;
.loop:
  i_6: int = phi i_1 i_15 .entry .endif;
  x_7: int = phi x_0 x_14 .entry .endif;
  max_8: int = const 10;
  cond_9: bool = lt i_6 max_8;
  br cond_9 .body .exit;
.body:
  mid_10: int = const 5;
  cond_11: bool = lt i_6 mid_10;
  br cond_11 .then .endif;
.then:
  x_16: int = add x_7 one_2;
  jmp .endif;
.endif:
  x_12: int = phi x_7 x_16 .body .then;
  factor_13: int = const 2;
  x_14: int = mul x_12 factor_13;
  i_15: int = add i_6 one_2;
  jmp .loop;
.exit:
  print x_7;
}

Some results when running for correctness:

# original
bril2json < ../examples/test/dom/loopcond-front.bril | brili > 1984
bril2json < ../examples/test/dom/loopcond-front.bril | python3 ../examples/is_ssa.py > no

# ssa + dce
bril2json < ../examples/test/dom/loopcond-front.bril | python3 ssa.py | python3 ../assignment_2/dce.py | brili > 1984
bril2json < ../examples/test/dom/loopcond-front.bril | python3 ssa.py | python3 ../assignment_2/dce.py | python3 ../examples/is_ssa.py > yes

Limitations:

• no argument passing
• not 100% sure my solution handles all undefined variables, needs more testing
• no from_ssa conversion yet (it's more trivial, and I just gave the priority to the to_ssa implementation), will do if find more time..

Fun debugging fact: I did not know Python has the 'shallow copy' and 'deep copy' modes for dict(). Spent some time debugging my recursion.

[sampsyo]

Thanks for the example! Given support for arguments or whatever, it would be interesting to see correctness and performance tests on the larger benchmarks (rather than just the smaller tests).

[gsvic]

Implementation

My implementation can be found here: https://github.com/gsvic/CornellCS6120/blob/l6-ssa/L6/ssa.py. Some details can be found below.

Details

The main logic is implemented inside SSA's constructor. This includes the extraction of phi-nodes, the stack implementation and the renaming, which executed at the end of the constructor by invoking the recursive _rename() method of the SSA class. The method is then being called for each child of the current block of the dominator tree. The do_ssa method needs to be invoked in order to generate the new bril code which contains the phi nodes.

Helper Classes

I am using two helper classes for better readability.

1. The Phi class simply represents a phi argument for a variable and the source block.
2. The PhiSet represents a set of Phi instances for a given variable, inside a block. It also contains a to_instr(self) method, which easily collects all Phis, constructs, and outputs the bril instruction.

Testing

For the testing, I exported the .bril files included here into JSON in order to create the corresponding python tests. Thus, I have two test cases, the loop-orig.bril and if-orig.bril. I integrated the is_ssa.py script to my testing suite. The loop-orig.bril fails, but it looks like this has to do with my buggy get_dom_tree() method from a previous assignment which I try to fix. The testing dir can be found here: https://github.com/gsvic/CornellCS6120/tree/l6-ssa/L6/test

[sampsyo]

Sounds like a reasonable start! Do you have any sense of how well this works on more complicated examples beyond these tests, such as the programs in the benchmarks directory?

Also, did you implement the "out of SSA" transformation?

[chhzh123]

In this assignment, I implemented the "into SSA" and "out of SSA" transformations, and tested them using turnt. Also, I followed the algorithm in Value Numbering to implement GVN. Code can be found in my repository. All the "from_ssa", "to_ssa", "ssa_roundtrip", and "gvn" tests are passed.

Converting to SSA

There are two steps in the SSA algorithm, the first one is phi-node insertion, and the second one is variable renaming. The pseudocode is very concise and misses lots of details. I was also confused about the phi-node part of the insertion algorithm in the first place and was misled that we insert an argument to the phi-node when we traverse the dominance frontier of def. Considering the following code that can bypass x from the .entry block to the .end block, we may probably get the phi-node with only one argument from .left since .end only in .left's dominance frontier but not in .entry's (which is an empty set).

@main(cond: bool) {
.entry:
  x: int = const 0;
  br cond .left .end;
.left:
  x: int = const 1;
  jmp .end;
.end:
  print x;
}

Later then I found that was incorrect. "Add a phi-node to block" means directly adding v = phi v v .b1 .b2 to block, and those v are just placeholders that will be given real names in the next pass. And how many predecessors the block has, how many arguments the phi node will have. The values that are not defined in some branches will be marked as undefined also in the next pass.

Also, "add a phi-node to block unless we have done so already" implies the phi-node is of variable v. A block can actually have multiple phi-nodes of different variables, so we need to exactly test if the phi-node of v exists, otherwise we do not insert it.

The renaming part is also tricky with several details that need to be paid attention to. For replacing the argument names, I added a constraint of not modifying the phi-node arguments. Since some of the phi-node arguments have already been written by the predecessor blocks, it will be overwritten if we do not distinguish the phi-node from other operations.

The phi-node renaming is probably the most confusing part -- "assuming p is for a variable v, make it read from stack[v]" -- the pseudocode does not tell us which phi-node argument we should modify and how to do that. I finally found some clues from this lecture note -- "replace the j-th operand of RHS(p) by Top(Stacks[v])", where "j is the position in s’s phi-function corresponding to block b". So we know we can replace the j-th operand of the phi-node by the top of the stack. If the stack is empty, then it means the value comes from a branch that has no definitions of that variable, so that operand should be set as __undefined.

Lastly, I added some enhancements to my SSA algorithm in order to pass all the test cases:

• Add my entry block at the beginning of the program (while.bril). This is always useful, especially for the program whose entry block is the header of a loop (which has a backedge). If the entry block is empty without doing any computation, I will eliminate it in the end.
• Support function arguments (argwrite.bril). This only needs to add those arguments into the variable stack at initialization.
• Support multiple functions (loop-branch.bril). Traverse all the functions and run the SSA algorithm for each of them.
• Type specification (loop.bril). The pseudocode does not mention anything about variable types, but to generate correct phi-nodes, we need to preserve the type information. This can be done by simply adding types into the variable definition map.
• Support phi node in the original program (if-ssa.bril). I rename the original phi node to phi_ so that it can be viewed as normal operations whose arguments will be replaced by the top name of the stack. Finally, the phi_ operation will be changed back to phi in order to be parsed by brili.

Converting from SSA

This is much easier than converting a program from non-SSA form to SSA form. As the algorithm describes, we only need to add id operations in the predecessor blocks of the block with phi-node, and then remove the phi instruction. There is one little thing to mention, the id instruction should be inserted before jmp/br, otherwise the variable may become undefined since the code may be executed before it jumps to different blocks.

Global Value Numbering

I also followed the Value Numbering paper written by KEITH D. COOPER and L. TAYLOR SIMPSON in 1995 to implement global value numbering, which is the dominator-based value numbering technique (DVNT) in Figure 4. The pseudocode is very clear. Since we have implemented LVN in Lesson3, the basic data structure of GVN is quite similar to that one. I used (op, VN[arg[0]], VN[arg[1]], ...) as the key of the GVN table and the canonical variable names (i.e. the SSA values) as the value of the table. After transforming the program to SSA form, we do not have duplicated assignments to the same variable, thus the SSA name can be directly used as the canonical name which also simplifies the algorithm.

For the part of "adjust the phi-function inputs in s", it is similar to what I did in SSA conversion. We need to first find out the corresponding argument index that refers to the current block, and change that argument to the canonical name.

I took the example in the paper (Fig. 5) to test the correctness of my implementation.

@main(a0: int, b0: int, c0: int, d0: int, e0: int, f0: int) {
.B1:
  u0: int = add a0 b0;
  v0: int = add c0 d0;
  w0: int = add e0 f0;
  cond: bool = const true;
  br cond .B2 .B3;
.B2:
  x0: int = add c0 d0;
  y0: int = add c0 d0;
  jmp .B4;
.B3:
  u1: int = add a0 b0;
  x1: int = add e0 f0;
  y1: int = add e0 f0;
  jmp .B4;
.B4:
  u2: int = phi u0 u1 .B2 .B3;
  x2: int = phi x0 x1 .B2 .B3;
  y2: int = phi y0 y1 .B2 .B3;
  z0: int = add u2 y2;
  u3: int = add a0 b0;
}

My program outputs the following results, which match the expected output in the paper. We can see those operations that calculate the same value are eliminated in B2 and B3, and those useless and redundant phi-nodes are also removed in B4.

@main(a0: int, b0: int, c0: int, d0: int, e0: int, f0: int) {
.B1:
  u0: int = add a0 b0;
  v0: int = add c0 d0;
  w0: int = add e0 f0;
  cond: bool = const true;
  br cond .B2 .B3;
.B2:
  jmp .B4;
.B3:
  jmp .B4;
.B4:
  x2: int = phi v0 w0 .B2 .B3;
  z0: int = add u0 x2;
  ret;
}

[sampsyo]

Awesome; super nice work describing all the tricky details in taking the high-level algorithm for SSA conversion and making it work for real! That bit about renaming the right argument to a phi-node is where a lot of creativity needs to be employed.

It's also super cool that you got GVN working on the SSA representation. This looks fantastic.

[michaelmaitland]

Converting into SSA

I implemented conversion into SSA using the algorithm discussed in class. It consisted of figuring out where phi nodes were needed, renaming variables, and actually performing the inserting of phi nodes into blocks. I was able to simplify the algorithm for determining where phi nodes were needed by getting rid of the "if we have already added" checks by using a set, which doesn't really make it any more efficient since the check is just occurring in the set abstraction instead -- but it made this code cleaner. With regard to renaming, this is where I spent most of my time. It took me a bit to wrap my head around how the stack was being used to make it all work. This became more clear after reading the Cytron paper. I also encountered a situation where a value comes from a branch that has no definitions of that variable, so that operand should be set as __undefined. I identified this during testing. Lastly, I inserted phi nodes to the start of blocks. It was a little messy passing around phis, phi_args, and phi_dests dictionaries around everywhere and if I was working in a larger codebase this is where I would say lets refactor class definition for blocks to encapsulate all this stuff.

Testing conversion into SSA

I tested converting into ssa by running all programs in the benchmarks directory against my conversion to ssa script and piped into the is_ssa script and then ran each benchmark in ssa form through the interpreter to make sure it still had the expected output. This was all accomplished using turnt. I did the same for all in the test/ssa directory. This gave confidence that I was in fact converting to SSA and that I did not change the side effects of any program incorrectly.

Converting out of SSA

I implemented the naive conversion out of SSA. It was pretty close to identical to the pseudo code in class. The one difference is that the id instruction must go before jumps or branches to make sure that it gets hit since not all blocks fall through to their successor.

Testing conversion out of SSA

I used a similar approach as described above. First, I converted all programs into SSA and then back out of SSA, checked against is_ssa script to be the same as it was before running conversion into ssa, since a program could be in SSA initially if variables were not reused, then ran through interpreter to make sure functionality was not changed.

Final thoughts

I enjoyed reading through a bunch of SSA related research papers during this assignment. In particular I read through Cytron and Bossinot and looked at parts of Briggs paper. They were quite interesting. I had quite a busy week and didn't have the available time to try and implement some of the fancier things, although I would have liked to. Perhaps I'll take a stab at it in the future if I have some free time

[sampsyo]

Sounds great overall! Did you try your conversion on programs beyond the stuff from my little tests directory? (For example, the benchmarks might expose other interesting behavior.)

[michaelmaitland]

Yes sorry I wasn’t more clear about that. I tested against all benchmarks round trip and mid way against their output and is_ssa midway

[sampsyo]

Awesome.

[orkosinha]

My implementation is here

Usage

usage: lesson6.py [-h] [--to-ssa] [--from-ssa]

options:
  -h, --help  show this help message and exit
  --to-ssa    convert bril program to ssa
  --from-ssa  convert bril program from ssa

to_ssa

This was by far the most challenging aspect of this task. Some initial hurdles I ran into was my phi nodes not being placed in the right blocks. For some reason they would consistently be placed in the block before they should be placed. This led to me figuring out there was a bug in my dominance frontier generation. Then through testing I encountered the previously warned about "tricky part of the translation". I realized prior to this, to maintain well-formedness, I needed to track the types of the variables. This was a straight forward fix where I tracked the type on the first definition of my variable when creating my defs map. By only adding in the type in the rename part, I'm able to check if the type is defined which also meant the variable was defined along the path, thus eliminating undefined variables along paths.

from_ssa

I implemented the naive conversion of from_ssa. This was fairly straight forward. I wish I started with this, as I had some initial misunderstandings on SSA.

Testing

I used the is_ssa.py script to check the correctness of my to_ssa. Additionally I ran it over the benchmarks in ssa form, and then with to_ssa -> from_ssa and it produced the correct results. I also added some tests in my own test directory to cover edge cases while trying to debug.

[sampsyo]

This led to me figuring out there was a bug in my dominance frontier generation.

Fascinating! Is there any way to summarize what was wrong with your DF implementation?

It sounds like you tested that your SSA implementation produced SSA code, but do you know whether it is correct? For example, did you try doing a "round trip" into and out of SSA, and then checking whether the program still produces the same output as it originally did?

[orkosinha]

Sorry, is "and then with to_ssa -> from_ssa" the roundtrip form we discussed? I ran both the round trip and SSA forms, but I totally forgot to include that detail. Will re-run and update on performance changes, but it did run correctly in the round trip on my subset of test cases and the benchmarks. Additionally, my bug was a result of a misunderstanding of dominance frontiers, I incorrectly computed the leaves of the sub-tree starting from the node in the dominance tree.

[sampsyo]

OK, sounds good! I was just interested how you checked whether the "round tripped" code in fact did the same thing as the original code—and which subset of benchmarks it worked on. (Knowing the percentage of correct benchmarks would be interesting, for example.)

[zzzDavid]

My implementation is here

Implementation

I implemented the passes to convert a program to SSA form and then converting back.

To SSA

Apart from following the pseudo code, I think it's important to think clearly about how to decide where the arguments of the phi node come from. The values that are undefined in the immediate predecessors cannot be simply marked as "undefined". For example, the self-loop test case. The x in .loop block is undefined in the .br block but defined in the .loop block itself because of the self-loop. In this case, we need to follow the predecessor path and try to find a definition (it could also be in the function argument), only when we reached the entry block without finding any definition, can we conclude that it is undefined.

From SSA

Converting from SSA is more straightforward, adding copy instruction at the end of predecessors does the job.

Usage

I have a main.py file as the entry of the program, it has the following command line arguments:

❯ python main.py -h
usage: main.py [-h] [-from-ssa] [-to-ssa] [-roundtrip] [-visualize]
               [-f FILENAME]

optional arguments:
  -h, --help   show this help message and exit
  -from-ssa    Convert SSA-form program to original
  -to-ssa      Convert program to SSA form
  -roundtrip   Convert program to SSA form then convert it back
  -visualize   visualize results
  -f FILENAME  json file

Tests

There are two set of test cases: ssa_roundtrip and to_ssa. The first one does a roundtrip and then check the execution result with brili. The second test set convert program to SSA form then uses a script is_ssa.py to check if the result is in SSA form.
To run all tests with turnt:

❯ turnt to_ssa/*.bril
❯ turnt ssa_roundtrip/*.bril

[sampsyo]

Thanks for the summary! I couldn't quite tell from your description of the testing: do you have an automated way of saying that the original program and the "round-tripped" program do the same thing?

It also looks like you've used handcrafted test cases (or maybe my test cases?). Did you try your implementation on complete programs, i.e., the benchmarks that come with the Bril repository?

[andrewb1999]

My implementation code is available here.

To SSA

There were definitely some complexities when trying to implement the pseudo code to cover all edge cases. As many other people have mentioned here, these issues mainly arise from variables being undefined along some paths and function arguments. For a while I was confusing myself over why a bunch of phi nodes were being generated for variables that were only ever assigned once, but this turns out to just be a side effect of the algorithm and these phi nodes can be automatically optimized away with tdce.

When varibles are undefined along some path, I just add an __undefined argument. Overall, SSA, unlike many of the previous implementation exercises, is mostly a challenge of handling edge cases without much concern over how to implement some data structure or framework.

From SSA

In comparison to converting to ssa, converting out of ssa is relatively simple, at least in the naive case. I followed the naive algorithm of adding copy instructions and deleting phi nodes.

Testing

I tested using the to_ssa and ssa_roundtrip test cases. I ensured the tests worked with a mix of spot checking and roundtrip testing. I ran out of time to do a more detailed analysis and brench, but my code seems to work for all the cases I have spot checked.

Usage

-f = from_ssa
-t = to_ssa
-r = roundtrip

[sampsyo]

OK, sounds good! Did you also check whether programs are in fact in SSA form, perhaps using the little is_ssa.py checker I wrote? It would also be interesting to see if anything breaks on the full set of benchmarks, rather than just my little (and very incomplete) test cases.

[andreyyao]

My implementation is here

to_ssa

I finished the phi-node insertion part of the algorithm, but didn't fully finish the renaming part, which is a bit more challenging than I expected. I will post updates here once that is done.

Initially I computed Defs, the map from variable names to the set of basic blocks where they are defined, by just iterating through the blocks with the pseudocode algorithm given on the course website. However this gives a map from strings to string sets, which is fine but a little clunky. I also noticed two difficulties from the renaming algorithm. First of all, how do we generate fresh variable names with the guarantee that no existing variables are using it? Second, when initializing the phi nodes, I need to know the return type of the phi instruction, which comes from the type of v if the phi node is v = phi l1 v ... ln v, for example.

To solve the above problems I implemented a function global_variable_rename (func: Func.t), whose spec says

Returns [func', n] where [func'] is [func] with all occurence of variables (including in the arguments) replaced with [v1,..., vn], and
[n] is the number of such variables. This makes creating new variable names much easier later.

The implementation of the above function is interesting. I basically keep one hashmap v2num that maps original variable names into an integer index. Then one iterates through the list of instructions, where every time a variable var is encountered anywhere, check if var is bound in v2num. If it's not bound(when we see it for the first time) then we add the binding v2num[var]:=size(v2num). And then rename that var to "v"+str(v2num[var]). I took the function arguments into consideration by initializing v2num with the arguments a1,...,ak bound to 0,...,k-1.

Then I defined a helper function parse that turns strings like "v3" to 3, for example.

This allows my to view variable names as array indices. So vars_to_defs_and_typs takes in a function and a number n, which is the total number of distinct variable names in the original program, and outputs an array arr of length n such that arr[i] is (defs_i, typ_i) where defs_i is the set of blocks where vi is defined and typ_i is the type of vi.

Similarly, the stack used in the renaming algorithm is now just an array of stacks, each for one variable. Reading from the top is just making a new string "v%d__%d" i stack.peek().

of_ssa

TODO to be implemented. I will update here once this is done.

Testing

Before starting this ssa project it took me a while to debug the previous dominators implementation. I also assumed that this assignment was due Thursday, which is incorrect... Anyways testing will be largely conducted with brench during half-trip as well as round-trips, against the tests in the bril/benchmarks, which I converted to json once and for all to avoid calling bril2json every time.

Update

i finished the to_ssa function using the algorithms from Cytron et al., but it seems to be erroring because of bugs in the dominance tree function... Trying to fix it now.

[sampsyo]

Thanks for the detailed description of how the renaming worked! I'd be interested to hear how the full round-trip turned out, if you want.

[andreyyao]

to_ssa is correct (each output is equivalent to original benchmark and in ssa form) for 70% of the benchmarks currently. There seems to be some tiny mistake lurking somewhere which I have not been able to pinpoint.

[sampsyo]

Cool; thanks for the summary!

[susan-garry]

My implementation for SSA is here.

There were many different edge cases to work through, and I spend most of my time debugging the function to rename variables. I discovered two bugs in my function to calculate a function's control flow graph and realized that my understanding of the dominance tree wasn't quite right, so I reimplemented that function.

Implementation

I assume that a function does not contain phi nodes before the SSA pass.

To handle cases where a function's arguments are redefined within a loop, I added a preheader block to the function, so

@f(arg1:t1, arg2:t2...) {
.entry:
...
}

becomes

@f(arg1:t1, ..., argn:tn) {
.preheader:
  arg1: t1 = id arg1;
  ...
  argn: tn = id argn;
.entry:
...
}

before converting to SSA form.

To handle cases where a variable is only defined along some paths, such as in the examples that Shubham gave, I add arguments to the phi nodes of a block's successors as I go and ignore phi instructions when I am renaming an operation's arguments. Additionally, I only add arguments to phi nodes for those paths along which the target variable is defined, which generally avoids the issues of working with undefined variables.

However, I don't know how to deal with cases when a variable is only sometimes defined along a path. If we have an if branch within a loop, where a variable v1 is defined along only one branch, we may end up insert phi nodes into the entry node to the loop. However, we can't simply add a move instruction to the last block in the loop because our variable v1 is only defined along one path - this would cause an error if the first execution of the loop traverses the other path. I don't know how to deal with this case, even after reading the other post in this discussion forum; anshumanmohan proposed getting rid of phi nodes that are only in the dominance frontier of one definition, which may be sound, but I'm not convinced that this deals with all cases (consider that a variable may be defined on 2/3 paths to the last node in a loop).

Testing

To test this code, I (1) used the is_ssa.py script to verify that the to_ssa pass successfully converts a program into ssa form, and (2) checked that the output of a program is the same once it has gone through an SSA roundtrip. I checked this on all of the testing examples (which terminate) written so far, and the portion of benchmarks tests which utilize only the core BRIL language. Obviously my implementation does not deal with all corner edges (as illustrated by the edge case above), but I am confident that it deals with many common cases.

[sampsyo]

This sounds very interesting!

I discovered two bugs in my function to calculate a function's control flow graph and realized that my understanding of the dominance tree wasn't quite right, so I reimplemented that function.

If you get a chance, I'd be interested to hear what went wrong with that (and any theories you might have about why your earlier testing let these bugs slip through).

And you're very right that dealing with undefined values is trickier than it seems, especially when "dependency cycles" can occur.

[susan-garry]

The bug in my code to form a function's control flow graph was caused because I did not check if the last instruction in a block was an instruction; in fact, some blocks may be empty (in my implementation, this means that the block would contain only a label). This bug could have been caught much sooner if I had, for example, tested my implementation of LLVM on the benchmarks.

The issue with my function to implement the dominance tree was that I only included blocks whose immediate dominator was a direct predecessor. (This struck me as odd, but I thought it was in line with the definition of the dominator tree). This was not caught in testing because my understanding of what the dominance tree was supposed to look like was simply wrong, so the expected output of my test cases was something other than the dominator tree. This would have been fixed earlier with a closer reading of the definition of an immediate dominator. However, the misconception came into sharp focus when I tried to use this function to rename my variables and realized that renaming would be impossible unless every block were present in the dominator tree.

[sampsyo]

Awesome; thanks for the recap!

[alaiasolkobreslin]

My implementation is here

Usage

--to-ssa      convert to ssa
--from-ssa    convert from ssa 

Implementation

To SSA

Converting to ssa was the most tricky part of this assignment since there were a lot of edge cases that I had to deal with. In particular, undefined values gave me a lot of trouble. In my implementation, if I try to read from stack[v] and if it is empty, then I replace that phi argument with "undefined" to indicate the variable doesn't exist along the path. One example of undefined values being tricky is that in my first implementation I initialized the stack to be empty, but caused the ssa form of argwrite.bril to be wrong:

@main(a: int) {
.b0:
  cond.0: bool = const true;
  br cond.0 .here .there;
.here:
  a.0: int = const 5;
  jmp .there;
.there:
  a.1: int = phi a.0 undefined .here .b0;  # should be a instead of undefined
  print a.1;
  ret;
}

I realized that I needed to initialize the stack to contain only the function arguments (each arg maps to a stack containing the same arg name). Another issue I had was a small bug in my l5 implementation for computing the dominance frontier: when checking that A does not strictly dominate B, I forgot to add the case for when A is equal to B (I'm not sure how I missed this- unfortunately my code to check the correctness of the dominance frontier was wrong for the same reason). This bug resulted in a phi node being missing in the case of self loops.

From SSA

Converting out of SSA was pretty straightforward. My only issue was that I tried to add id instructions as the second-to-last instruction in every block, but this meant that some arguments could be undefined if the last instruction wasn't a jump or a brach. Then I remembered there is a add_terminators function that puts in a dummy jump instruction when there was originally a fall-through. So I called this function before adding the id instructions.

Testing

I used the is_ssa.py script to verify that my code does in fact convert the examples to ssa form. I also tested to make sure that outputs were the same before and after ssa conversion for every example in ssa_roundtrip (this includes running dead code elimination after converting out of ssa to remove the instructions with "undefined").

[sampsyo]

All sounds good; thanks for the summary! It's interesting (and apparently quite common, judging from this thread) that implementing SSA helped you find bugs in your dominance tree that you missed the first time around.

[ayakayorihiro]

More than a month late but my implementation is finally here!
The nitty gritties of the implementation were definitely tough to handle, but it was a cool exercise :)

Usage

To convert a bril program to SSA form, run

bril2json < {filename} | python3 ../to_ssa.py

To convert a SSA bril program to a non-SSA bril program, run

bril2json < {filename} | python3 ../from_ssa.py

Implementation

As the writeup says, conversion to SSA was the most difficult part! The challenges were mostly in the details, such as:

• I mixed up dominators and dominated blocks in the function I wrote to compute the dominance frontier
• My initial plan for the replacement values/stack (a mapping from each variable to a number index that increased every time the variable was assigned to) messed things up considerably
• "Popping" the stack was surprisingly an implementation challenge?
• I forgot to put in function arguments into my list of variables

So a lot of the implementation process was focused on trying to fix small bugs. This process was really helpful in cementing my understanding of dominators as I went back to the drawing board a couple of times to determine if my dominator computing functions were correct in the first place!

The conversion from SSA wasn't too bad, besides having to deal with cases where the blocks ended with jmp or br instructions.

Testing

I tested by running my implementation of to_ssa.py and from_ssa.py on turnt. A lot of the bugs (now fixed) were found in the testing process!

[sampsyo]

Yeah, you're absolutely right about "popping the stack" being an annoying thing to get right! It's weird IMO because the algorithm is mostly functional but involves some mutation to do that push/pop thing. Nice work!

[yy665]

Sorry for the late post, but here is my implementation.

Usage

To SSA

bril2json < test.bril | python3 ../self_ssa.py --to-ssa

From SSA

bril2json < test.bril | python3 ../self_ssa.py --from-ssa

Implementation

It's indeed more difficult than what I've originally thought. I have spent quite a while debugging my code. Partly because my code was a bit hacky and I missed some of the details which turned out to be crucial for the correctness.

Here is some notable mistakes I made:

• I recursively called rename on ALL children in the dominated tree, but I was supposed to call only the immediate children.
• There was a minor mistake I made in my previous assignment (dom_frontier) which gave me nodes that shouldn't be consisted in the dom_frontier
• I poped the wrong end of variable stack

Some of the above mistakes are seemingly trivial, but it actually took me a while to debug since I didn't expect myself to make these mistakes.

Testing

I have run all the tests in ssa_roundtrip. It's not yet comprehensive and there might still be bugs on corner case, but the code should at least work for most scenerios.

[sampsyo]

OK; thanks for the summary! TBH I don't think my tests in ssa_roundtrip are anywhere close to comprehensive, and they are not intended to be what students use—it would be great to know if this breaks "real code", i.e., full benchmarks.

[thomasyang18]

Holy crap. I'm kind of on a dopamine high right now, so I haven't done the out-of-SSA transformation, but I'm super excited about the algorithm I came up with, so I just want to document it right now.

There were a TON of bugs with the SSA implementation, it really made me discouraged and skeptical that the program was working. A lot of misinterpretations of the pseudocode, and one thing lead to another, and I was pretty fed up with this lesson. I skipped ahead to lesson 7, only to feel bad and get even more lost, so in total lesson 5+6 basically took over a month to complete lol.

But it was all worth it in the end, since I got my algorithm to work!

Context

Take the following program:

@main(){
.b0:
  i: int = const 0;
  n: int = const 10;
  one: int = const 1;
.b1:
  i: int = add i one;
  cond: bool = ge i n;
  br cond .b3 .b2;
.b2:
  print i;
  jmp .b1;
.b3:
}

The issue with the in-class algorithm is that it says, "For all places where this variable is defined, check its domination frontier".

Well, i isn't defined in b2, but the only block that has a domination frontier is b2. So you'll never get it. So the straightforward interpretation of "defs", which is just mark any block where that variable has an assignment, doesn't work.

I assumed that the examples/to_ssa.py program did some kind of dataflow analysis in this case, or just said screw it and checked every node that was part of a domination frontier. So i tried both approaches (and a lot more), and ended up giving up for about a week before I somehow just got divine inspiration.

The idea is to literally just simulate phi nodes with dataflow analysis - every assignment to a variable, you can think of as a copy of that variable originating from that block. Then, if a block has 2+ different block copies of that variable going into it, assume that a phi node is going to go there, and the outblock will have a copy of that variable originating from that block. Otherwise, if it only has 1 block copy going into it, don't alter the block copy at all, and let it pass through normally.

I'm pretty confident in my program, because I ran it against all the benchmarks and it finally passed - those benchmarks have some nasty edge cases. I'm also pretty confident in my algorithm, although admittedly the merging at in-nodes operation is pretty sketchy, I have an intuitive argument but formally idk how to prove. The functions applied in the transfer function and out-nodes are (I think I proved correctly) monotonic though so that's fine. The rest I just copied from the pseudocode provided in class, it's pretty neat that the recursive naming algorithm just works.

I know this is different from the examples/to_ssa.py program, because when I was comparing outputs to see where I was going wrong, I noticed that examples/to_ssa.py had a lot of unnecessary phi nodes, with a bunch of undefineds or nodes where the variable is constant throughout the program. For example, in that very same program, the examples/to_ssa.py program would throw in a phi node for the cond variable even when it's not needed.

Benchmarks

First, after a ton of hassle, I confirmed that on all the benchmarks and my small tests, my program is indeed in SSA form and that it doesn't affect program behavior. So it's correct (on our small samples) at the very least.

Then, I ran a dynamic instructions benchmark to see just how much time I saved. Surprisingly, a ton!

For example, on eight-queens.bril, I had 110k instructions as opposed to 184k instructions. That's a 40% speedup right there!

On others, not so much - for fizbuzz, I had 60 million instructions as opposed to 63 million instructions. And for ackermann, I had literally 1 less instruction, which I thought was pretty funny.

Oh, and on my own program, bitwiseops, I saved 12% time, which was nice :)

TL;DR it's faster than the provided class implementation. Granted, I really don't know the real correctness of this algorithm - I still barely understand why the pseudocode provided in class works, and it's my first time writing a real dataflow analysis without just copying from an existing example. But given my current tools and effort (and sunk cost fallacy), I'm calling it correct. Hopefully you believe in me too :)

Update on the from-ssa program coming soon, I'm pooped for today tbh. A jumbled mess of thoughts can be found on my README and implementation here

[sampsyo]

Awesome work!

[thomasyang18]

Haha nevermind 😢 I completely underestimated undefined variables.

When I went to implement from_ssa.py, I realized that undefined variables actually mattered in that implementation, so I changed up my program just a little bit to handle that, and yup, I got like 180k instructions for eightqueens.bril

Man, that's annoying. I have no idea how my program passed the ssa_roundtrip tests the first time, but the second time they broke the code, and it added even more edge cases for from_ssa.py. In particular, if-const.bril broke my code.

I feel like there should be some kind of way to differentiate between the two cases of either a useless phi node versus actually necessary phi node, but tbh I just want to move onto the next lesson, so I just implemented from_ssa.py and called it a day. I may come back to this sometime in the future. Undefined variables are way too annoying.

I mean, my program still saves a decent amount of instructions - it saves a few thousand out of tens of thousands. Just not ludicriously like the 40% I claimed LOL.