Lesson 6: Static Single Assignment

[sampsyo]

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

[Mond45]

Source: https://github.com/Mond45/cs6120_tasks/tree/master/task6

What I Do

I implemented the converter into and out of SSA form in Rust.
The into-SSA conversion is the more complex version, utilizing dominance frontiers. My algorithm is divided into two steps, as discussed in class: $\phi$-node insertion and variable renaming.

The $\phi$-node insertion step doesn't actually place the $\phi$-nodes directly into the IR. Instead, it returns a list of $\phi$-nodes for each basic block, which are then inserted later during variable renaming.

Most of the work happens in the variable renaming step, where both variables and instruction arguments are renamed. Here, $\phi$-nodes are inserted into the IR in the form of get and set instructions. For each basic block, I iterate through its successors' $\phi$-nodes, inserting get instructions there and set instructions in the current block, while maintaining a map keeping $\phi$-node destination variables. To handle possibly undefined variables on some predecessors, I dynamically create a new undefined variable in the predecessor block and insert a corresponding set. Function arguments are handled by pushing them onto the stack before conversion begins.

The out-of-SSA converter is much more straightforward. It simply traverses every instruction: a set for variable v becomes an id that writes to __shadow_v (simulating shadow variables with a variable prefix), while a get for v reads from __shadow_v.

Testing

For the into-SSA converter, I first verify that the resulting IR is indeed in SSA form using the is_ssa.py script. I then test it on the example tests from the Bril repository. Because of different renaming strategies, I need to manually verify the correspondence between variable names. Finally, I test the converted SSA form on the entire Bril benchmark suite using brench, which also reports dynamic instruction counts.

For out-of-SSA, I follow a similar process. Initial testing on the example tests revealed an issue in my early implementation, which only handled set instructions and failed with dead sets and swaps. After fixing that, I perform round-trip conversion testing on the full Bril benchmark suite using brench.

The Hardest Part

The hardest part was implementing the into-SSA algorithm, particularly the variable renaming step. I spent considerable time figuring out exactly where to insert $\phi$-nodes. Initially, I attempted to place set instructions at definition sites using reaching-definition dataflow analysis rather than at the predecessors of the block containing a $\phi$-node (on the control-flow edge), which made the implementation unnecessarily complex.

Handling undefined variables and function arguments also required careful thought, but I'm quite satisfied with my final solution.

The out-of-SSA conversion turned out to be less trivial than I first expected as well, especially after dealing with the edge cases revealed by the example tests.

Performance

Here are the slowdown statistics across all Bril benchmark programs, measured as the ratio of dynamic instruction counts for programs in SSA form compared to the baseline:

mean       2.187849
std        0.714249
min        1.000000
25%        1.672043
50%        2.191275
75%        2.754310
max        4.630887

Since my out-of-SSA implementation does not remove any instructions, the slowdown remains the same.

Conclusion

I believe my work deserves a Michelin star, given its non-trivial implementation and thorough testing. I'm quite satisfied of the resulting implementation and learned a great deal from this task. I like that we got to reuse parts of previous tasks and it was satisfying to finally understand some concepts, such as realizing that we can simply handle inserting get and set for successors' $\phi$-nodes since the stack conveniently maintains the latest definitions.

[sampsyo]

Awesome! This is a really clear writeup, and thanks for reporting the descriptive statistics for your overhead after a round trip. It is indeed a little nuanced to see how to "simulate" a φ-node with a set/get pair, but you figured it out in the end. Looking very good!

[Fangtangtang]

Implementation

For the “into SSA” transformation, I implemented the dominance-frontier-based algorithm, which consists of two main phases: iterative φ-insertion and variable renaming.
One important implementation detail is that function parameters should be treated as definitions within the 'entry basic block', ensuring all uses in the function body have a corresponding reaching definition.

For the “out of SSA” transformation, I lowered φ-instructions by splitting them into id operations within their respective predecessor blocks.

To simplify instruction-level insertions and deletions during this process, I implemented a lightweight linked list structure to manage instructions within each function, allowing efficient and flexible transformations.

Correctness Verification

I tested both transformations across the full bril benchmark suite:

• The into SSA pass was validated using the provided is_ssa.py checker to confirm that the transformed program satisfies the SSA property.
• Both transformations were verified for correctness by comparing program outputs before and after the transformation.

Overhead Measurement

To measure the transformation overhead, I compared the dynamic instruction count between the original, ssa and round-tripped programs.
Results show:

Transformation	Max Overhead	Average Overhead
Into SSA	4.63×	2.17×
Round-tripped	2.82×	1.63×

The figure below summarizes the detailed dynamic instruction counts across all benchmarks.

[sampsyo]

Very cool! It sounds like this wasn't too complicated for you in the end—unless you ran into unexpected troubles that aren't summarized here? Anyway, sounds good overall!

[maheshejs]

Code: https://github.com/maheshejs/cs6120pr

SSA
I implemented SSA construction in Racket using the classic dominance-frontier algorithm from Cytron et al.’s paper, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph.

I added 7 passes to my compiler pipeline, broken into three stages: SSA preparation, going into SSA, and coming out of SSA.

;; Compiler pipeline
(define compile-pipeline
  (compose
    flatten-program             ; JSON
    bury-dead                   ; DCE
    optimize-values             ; LVN
    remove-phis                 ; SSA-OUT
    hoist-phis                  ; SSA-IN (Pizlo’s form)
    rename-variables            ; SSA-IN 
    place-phis                  ; SSA-IN
    insert-undefs               ; SSA-IN prep
    decorate-defines            ; SSA-IN prep
    fake-entry                  ; SSA-IN prep
    remove-unused-instructions  ; CFG cleanup
    decorate-flow-graph         ; CFG construction
    expose-basic-blocks         ; BB construction
))

;; Parse input JSON, apply pipeline, and output result
(define program
  (compile-pipeline (read-json (current-input-port))))

SSA Preparation
The first pass is fake-entry, which adds a dummy entry block to prepare for dominance utilities that expect the entry block to have no predecessors. The second pass is decorate-defines, which decorates the JSON program with a hash-map of variables and their defining blocks, this is needed for phi-placement in Cytron et al.’s algorithm. The last pass is insert-undefs, which presets all defined variables to undef in the entry block. This is also needed for phi-placement, at a join node, if a variable is defined in one branch but not in another, the corresponding phi is assumed to come from the entry block.

Into SSA
To go into SSA, I followed the two pseudocodes in Cytron et al.’s paper for phi-placement and variable renaming:

• place-phis inserts trivial phi-functions at join nodes (dominance frontiers).
• rename-variables recursively renames all mentions of variables starting from the root of the dominance tree.

Once in classic SSA form, I convert to Pizlo’s form with hoist-phis, following the sender–receiver approach to split phis into set and get pairs.

Out of SSA
Once in Pizlo’s form, going out of SSA is trivial:

• Replace set instructions with id instructions of the right type.
• Replace get instructions with nop.

Later passes (DCE and LVN) clean up nop, undef, and conservatively introduced id from phis.

Testing
I tested SSA construction (into SSA, out of SSA, and SSA roundtrip) using:

• turnt with Bril examples and handwritten cases,
• brili to interpret out-of-SSA programs in Pizlo’s form and confirm correctness, and
• brench to run SSA roundtrip on all Bril core benchmarks, checking correctness and dynamic instruction counts.

Results
Compared to my task 4’s global LVN + DCE baseline:

Total: 56 | Improved: 0 (0.0%) | Worsened: 56 (100.0%) | Unchanged: 0 (0.0%)
Mean speedup: 0.801× | Geomean: 0.789× | Best: 0.998× | Worst: 0.345×

The SSA roundtrip introduces overhead as expected, though the global LVN + DCE keeps it around 0.8× on average, which corresponds to a 25% overhead.

Hardest Part
This task relies on previous ones, and thankfully I didn’t hit any bugs from previous tasks. The main challenge was translating Cytron et al.’s pseudocode, which is heavily imperative, into functional Racket with immutable data structures.

Conclusion
I believe I deserve a Michelin star for successfully implementing the dominance-frontier version of SSA construction, fully integrated with my previous tasks (dominance utilities in task 5 and global LVN+DCE in task 4).

[sampsyo]

Really really cool! Nice work breaking down the work into logical steps that allowed you to write a pipeline of simpler passes—including literally inserting φ-nodes and then converting those into set/get form, which is super interesting. FWIW, I think it's also common for 6120 students to not literally insert these but to instead just add a data structure "on the side" indicating where they would go and then only insert fully-formed final instructions once the renaming is done. Anyway, not doing that makes things a bit more pipeline-y and makes a lot of sense too!

And it's also pretty cool that you were able to get the classic Cytron algorithm to work with immutable data structures too; you're right that the usual presentation is pretty imperative.

Very impressive!

[SolidLao]

Team Members

Ning Wang (nw366), Jiale Lao (jl4492)

Source Code

https://github.com/NingWang0123/cs6120/tree/main/assa6

Implementations

• ssa.py: Implements the dominance-frontier-based "into SSA" transformation using the standard algorithm with phi node placement and variable renaming.
• out_of_ssa.py: Implements the "out of SSA" transformation using parallel copy scheduling to resolve phi nodes while handling cycles correctly.

Testing and Visualization (Generative AI part)

All 62 benchmark programs from bril/benchmarks/core/ were tested through:

1. SSA Form Verification: Checking that each variable is assigned exactly once (using the script provided by Professor)
2. Round-trip Testing: Verifying that Original → SSA → Out of SSA produces valid code
3. Overhead Measurement: Counting static instruction differences

We use gpt-5 to generate the visualization codes in visualze_results.py. The generated figures look really great!

From this figure, we can see the static instruction overhead for each program, ordered from low overhead to high overhead with different colors to represent different levels of overheads. As we can see, the overhead could differ significantly across different programs (e.g., it introduces nearly 700 more instructions for dayofweek, for other programs it is typically less than 100 instructions).

From this figure, we can see the statistics and the summary. All 62 programs pass the SSA form verification and round-trip testing. For the overhead, the total original instruction number is 2148 and we introduce 1789 overhead instruction, with an overall overhead of 83.29%. This meas, we almost double each program after SSA round-trip.

The hardest part

Compared to prior tasks, this implementation is more complex and we need to understand the algorithm carefully and then implement things correctly. But the good thing is that, it is easier to test and evaluate (for some of prior works, we need manual checking). The hardest part is thinking how to reduce the overhead. The number of instruction is a good metric for measuaing overhead, but given that different instructions have different overheads, maybe we still need to measure the end-to-end execution time?

Michelin Star

I think we deserve a star, given that we implement all the functions, good testing, and good visualization.

[sampsyo]

Very cool; this all sounds good! I really wonder why dayofweek looks the way it does… it seems like it must be some sort of pathological case?

[zc579]

This time I write to_ssa.py to transform a regular Bril program into SSA form. I divide the whole task into 9 parts with the help of Chatgpt-5 and implement each of them and finally get my program running. The parts are listed below:
1.Build CFG and basic blocks
The code first groups instructions into basic blocks (straight-line code sequences without jumps) and builds a CFG that shows which blocks can follow which.
2.Record variable definition blocks
For every variable, the code scans all blocks to see where the variable is assigned.
It builds a mapping from each variable to the set of blocks that define it.
3.Collect variable type info
The function records the type of each variable, both from function arguments and from instruction destinations.
4.Determine phi insertion positions
For each block in its dominance frontier, mark that a phi node must be inserted for that variable and repeat recursively until no new blocks need phi.
5.Initialize SSA renaming bookkeeping
Before renaming variables, the program initializes several helper structures like version counter and stack of current variable versions.
6.Rename variables using iterative DFS
Each use of a variable is replaced with the current top version from the variable’s stack.7.Insert GET/SET instructions
After renaming, the code physically inserts the new operations get at the beginning of blocks and set in predecessor blocks.
8.Insert undef initializations
If a variable is used before any definition along a control-flow path, insert an undef instruction.
9.Reassemble final SSA instruction sequence
The function replaces the old instruction list in the function with this new, SSA-converted sequence.

[sampsyo]

Hello! This sounds like a reasonable series of phases. However, did you do the evaluation part of the task?

[YoruCathy]

Implementation: Link

What I did

I built an into SSA pass in Pizlo’s set/get form using the dominator frontier algorithm. First I constructed CFGs, dominators, idom tree, and dominance frontiers. For each variable, I place get at DF sites, treat function params as defs at entry, then do stack-based renaming over the dom-tree. After renaming, I split phi across edges by inserting set in each predecessor; missing defs use a typed undef temp. An out of SSA pass lowers get x->id x, x, and leaves set as a valid effect.

Evaluation

I wired turnt to run the first 30 core benchmarks in bril and added runners that infer # ARGS: or type defaults. This caught type pitfalls (e.g., eq on non-ints) which I fixed by inferring base types and annotating generated get/undef.
Across 30 programs, SSA-only added ~1.98× dynamic work on average, yet after lowering back out of SSA the round-tripped code was essentially neutral (~1.01×) on the seven profiled cases, with 6/30 showing no static growth at all.

=== Summary ===
Files: 30
Files with zero Δstatic: 6
SSA-only slowdown mean: 1.984× (n=30)
Round-trip slowdown mean: 1.005× (n=7)

I also made some plots:
Top-left (Totals: Static & Dynamic)*
Static instructions grow from after SSA and remain about the same after round-trip.
Dynamic totals rise in SSA-only but drop after round-trip.

Top files by static delta
A few programs dominate the overhead. dayofweek.bril is a clear outlier. Most other files add only tens of instructions.

Static overhead
Median round-trip static growth is roughly ~100% (i.e., about doubling), and long whiskers to ~600% driven by the outliers above.

CDF of static delta
The curve climbs steeply: ~80% of programs add ≤100 instructions; ~95% are ≤250. Only a tiny tail reaches into the high hundreds/1k+, again reflecting the few join-heavy outliers.

Hardest part

Getting SSA construction robust across all Bril tests (not just toy examples) was way harder than expected. My first version worked on a small hand-written case, but it blew up on real programs due to three intertwined issues:
My first version worked on a small hand-written case, but it blew up on real programs due to three intertwined issues:

• Types: generated get/undef must carry the right type (e.g., int vs bool). After renaming, some paths fed a bool into eq expecting int, or vice-versa. I added base-variable type inference (from function args + dests) and stamped every synthesized get/undef with that type.
• Missing definitions (undef): at merges, some predecessors don’t define a live variable. Without care, that produced 'get without corresponding set.' I fixed this by inserting a typed undef temp in those predecessors and set shadow <- undef_temp only on edges that need it.
• Loops/back-edges: get must exist at loop headers so each incoming edge can supply a set. Without that, loops triggered runtime errors or infinite recursion in brili. I detect headers (dominate their predecessors) and place gets there before renaming.

Even after these, corner cases kept surfacing. fallthrough edges, placing set before the terminator, and ensuring renaming never rewired set’s shadow name incorrectly. I iterated with turnt on the full test suite (well I couldn't get it through the entire core benchmarks, there's still one failing), and when I got stuck I leaned on GPT to pinpoint where the algorithmic intent didn’t match my implementation details and it is being very helpful.

Gen AI usage

I used GPT in this homework.

• Help me debueg when the test cases are not passing. This resulted in the run_bril_with_args.py file.
• Write a script to save the results to a csv, and plot the figures
• Write a readme for my code
  GPT is in general very helpful. but it doesn't seem to be very familiar with some context like turnt APIs. It suggests turnt --timeout which doesn't exist.

[sampsyo]

All looks good overall!

Across 30 programs, SSA-only added ~1.98× dynamic work on average, yet after lowering back out of SSA the round-tripped code was essentially neutral (~1.01×) on the seven profiled cases, with 6/30 showing no static growth at all.

That's very interesting! Did you run some post-processing optimizations to help eliminate some overhead (such as constant folding)? I would generally have expected a bit more overhead, so it's nice that this didn't happen for you.

• Loops/back-edges: get must exist at loop headers so each incoming edge can supply a set. Without that, loops triggered runtime errors or infinite recursion in brili. I detect headers (dominate their predecessors) and place gets there before renaming.

This is also quite interesting! I admit I don't fully understand the issue, i.e., why loops in particular need special handling. Any chance you have an example of a test program that caused you trouble?

[Jacqueline-Wen]

Team Members
Serena Zhang (syz8), Maggie Gao (mg2447), Jacqueline Wen (jw2347)

Source code URL

Converting to SSA

For converting to SSA, we split our code into 3 parts: collecting variable definitions, inserting the phi nodes, and renaming the variables. collectVariableDefinitions builds a map of which variables are defined in which blocks by iterating through all the instructions in a block and saving the dest and args for each variable definition in a map. For insertPhiNodes, we insert $\phi$ nodes based on the dominance frontier. Finally, for renameVariables, we assign unique names to each variable and update instructions and phi nodes.

Converting from SSA

This part of the assignment involves converting from SSA back into regular form. Here, we are replacing each $\phi$-node with explicit id assignments on the control-flow edges that feed into the $\phi$'s block. Our implementation first identifies all the $\phi$-nodes in each block and creates copies of their corresponding source values in each predecessor. To avoid breaking control flow, we also have the function isTerminator which checks for branch, jump, and return instructions. This ensures the inserted copies appear right before these terminators.

Testing

For testing, we first manually verified via random sampling that the test cases with and without SSA had the same results. Then, we measured the overhead of adding SSA by comparing the static overhead of the generated bril files. Our results are shown below:

Hardest Part

The hardest part was definitely implementing the converting to SSA, as well as debugging existing utility files that were broken. Converting to SSA was difficult purely because we had a lot of different parts to implement, which made debugging difficult. Debugging was also difficult because this project built off of some previous sections we implemented, and we found small bugs in those programs as well.

Michelin Star

We believe we deserve a michilin star for implementing SSA, as well as integrating our program with previous tasks.

[sampsyo]

Sounds good in general!

It looks like your implementation uses actual phi instructions (i.e., the "old" SSA form for Bril) instead of the set/get form (the "new" SSA extension). That means you can't interpret programs in SSA form, at least without checking out an old version of the reference interpreter, I think? Is that right? If so, did it cause you any trouble?

Debugging was also difficult because this project built off of some previous sections we implemented, and we found small bugs in those programs as well.

It would be interesting to hear a bit more about what those problems were exactly!

[adnan-armouti]

Team Members
Adnan Armouti and Tobi Weinberg

Link to Implementation
Repo available here

Implementation Overview
We implemented an SSA round-trip for Bril:

1. to_ssa.py inserts phi nodes via dominance frontiers and renames with version stacks
2. from_ssa.py lowers phi nodes into predecessor copies with simple cycle breaking
3. is_ssa.py checks well-formed SSA (single assignment per name, phi node consistency, etc...).

For phi node placement we used the dominance-frontier from the last assignment + a single dominator-tree DFS rename. When a use can be reached without a prior def, we materialize a typed undef in that predecessor and wire it into the successor’s phi node input to match Bril’s SSA extension semantics.

Testing Methodology
Correctness:

• We used a round-trip harness, as shown in lecture by Prof. Sampson: bril2json | to_ssa.py | from_ssa.py | brili and compared the output against the original brili run for each benchmark. We snapshot both runs with turnt and added a tiny helper (verify_outputs.py) to summarize matches/mismatches.
• We ran this on 114 benchmarks, copied from the bril/benchmarks directory and included all those listed in the "core", "float", "long", "mem", and "mixed" folders.
• After fixing undef handling and phi node argument patching (see "Hardest Part" below), we got 113/114 clean round trips that match the original.
• We didn't really have too much time to address the only failure case (orders.bril), and to be honest we were just happy to have gotten to this point. Resolving it cleanly would require restructuring unlabeled fall-throughs for minimal gain.

For dynamic and static overhead:
For both dynamic and static instruction count and overhead measurement, and for each .bril benchmark, we evaluate the baseline, the SSA round trip, the SSA round trip + LVN, SSA round trip + TDCE, the SSA round trip + LVN + TDCE. Please note the tdce.py and ;vn_dec.py were taken directly from L3 tasks.

• Dynamic Instruction Count: csv file available here
• Static Instruction Count: csv file available here

Hardest Part

1. Undef along some paths: Our first attempts left placeholder phi node args when a var had no reaching def; that produced wrong results on programs with early exits. We fixed this by adding undef in the predecessor block (just before its terminator) and then feed that into the successor phi node input. This exactly matches the spec and fixed multiple benchmarks.
2. Predecessor indexed phi node inputs: We initially patched phi node args by position without aligning them to each predecessor label; the fix was to index by labels.index(pred_name) for each successor block before filling the argument. Seems obvious now but when writing everything from scratch these small errors weren't initially caught.

Results/Output
Here are the numbers:

1. 113/114 (99.12%) benchmarks had a complete SSA round trip
2. For correctness, of the 113 benchmarks with complete SSA round trip: 113/113 (100%) benchmarks match the original
3. For overhead/optimization, please refer to the csv files for percentage measures for each benchmark and evaluation measure (baseline, SSA, SSA+LVN, SSA+TDCE, SSA+LVN+TDCE)

Self-Assessment
We believe we deserve a michelin star for attempting and testing both correctness and optimization rigorously.

GAI Tools Disclaimer
Please see the README in our repo for a very detailed explanation: https://github.com/adnan-armouti/cs6120/tree/main/lesson_6

[sampsyo]

Sounds awesome! You're right that one failing benchmark is a pretty good place to end up. It's totally out of scope for these tasks, but it would be interesting to know what it is about orders.bril that tripped up your implementation, if that ever becomes obvious.

When a use can be reached without a prior def, we materialize a typed undef in that predecessor and wire it into the successor’s phi node input to match Bril’s SSA extension semantics.

This sounds like quite a reasonable strategy! FWIW, it is also common to just insert undef willy-nilly at the top of the program and allow some of those to become dead. But this is nicer. :)

[mercure67]

source: https://codeberg.org/pedropontesgarcia/bril/src/branch/feat

We never use generative AI on these assignments.

what we did

We implemented into and out of SSA functions. We used the Pizlo form of 'upsilon' / 'phi' nodes, and the dominance-frontier based into SSA function. Since the Pizlo form already 'pushes' phi nodes into the parent blocks, the out of SSA algorithm just replaces all sets with an id and removes gets.

This image shows the ratio of instructions executed for a roundtrip vs. baseline. Pretty bad, as expected:

This image shows the ratio of instructions executed for the SSA form vs. baseline. Much worse, as expected:

This image shows the ratio of instructions executed for a roundtrip vs. the reference SSA roundtrip. We're generally doing better, without DCE:

verification

We used two brench test suites to test our implementation. The first tests:

• whether or not the ssa-into pass' result is still correct
• whether or not the ssa-out pass' result is still correct

It also produces instruction execution count for the reference Python to_ssa for comparison.

The second uses the is_ssa script to verify whether the result of ssa-into is indeed SSA.

Both use the entire benchmarks/core directory of the bril repository as input.

hardest part

The into SSA was definitely the hardest part. We used the Pizlo format, which complicated things further. We spent quite a bit of time writing and testing the code; and chasing down bugs as we encountered them.

One bug that took an especially long time to fix was in the orders.bril benchmark. The orders function branches based off of arguments to the first block (u), which isn't yet given a 'init' value

We also worked together in-person and talked through the problems we were encountering. Luckily, the out of SSA was made pretty easy by the Pizlo format.

michelin star?

Yes! This assignment was hard, and for relative novices in Rust (plus despite a really busy two weeks for the both of us, with multiple exams shared between the two of us), we were able to get something that works decently well (and do the more complicated dominance-frontier based version as well). Some refactoring can be done further down the road for efficiency, but the implementation is sound, and that's the key thing.

We also added the ability to print our CFGs with GraphViz (see print_cfg_dot) in resolver.rs, and cleaned up some of our past code.

[sampsyo]

Very nice! This all sounds great. And you're right that this is a moderately large amount of Rust to write for people still ramping up on Rust. :) Nice work overall!

One bug that took an especially long time to fix was in the orders.bril benchmark. The orders function branches based off of arguments to the first block (u), which isn't yet given a 'init' value

Aha! That does indeed work as an explanation for why orders.bril could trip up certain approaches to inserting undefs. Thanks for the capsule explanation!

[tf-mac]

Source: HERE

Implementation: I implemented the from SSA form first, then the to SSA in its naive form. I intended to do the dominance frontier version, but the helper functions for from SSA form and to SSA were more complex than I initially realized and I was unable to get to it.

Hardest Part: Definitely the to SSA form, I had to really work hard to rename everything, since my pattern matching didn't allow easy (non-tedious) access of the arguments of a function

Michelin Star: I do not claim a michelin star for this assignment, as I was unable to verify my result as I ran out of time.

[sampsyo]

Thanks for the straightforward summary! Sorry you ended up running out of time—it's true that this task is considerably heftier than previous 6120 tasks.

[natetyoung]

Amanda Wang @arw274 and I worked together on this.
Code Link

What we did

We implemented an algorithm to convert Bril to SSA (with set and get instructions).
For placing get nodes, we first tried an implementation of the dominance-frontier-based approach from Cytron et al., but found that we struggled with phi nodes in places where they weren't needed or where the variable wouldn't be defined (e.g., phi nodes were placed even for variables which weren't needed beyond a single block). Rather than fix this in that implementation, we decided to switch to something like the phi placement algorithm from Braun et al.; we find the uses of a variable and traverse backwards through paths in the CFG, placing gets as we go, until we reach a block which defines the variable. This allows us to avoid using undef. We implemented a fairly naive version of this, however; we did not remove trivial phis as described in the paper.
For placing set nodes, we implemented essentially the procedure described in the lesson. Our naive get placement helped us here -- since gets are placed in every block along a path from a definition to a use, each block need only look at its immediate successors to find which gets it needs to match with sets and what their names are.
To handle function arguments, we added a new entry block consisting entirely of set operations to match the gets generated for the renamed versions of function arguments in the original entry block.
For instance, mod in core/binary-fmt.bril normally begins:
@mod(a0: int, a1: int) : int {
v0: int = div a0 a1;
In our SSA form, it begins:
@mod(a0: int, a1: int): int {
set a1.0 a1;
set a0.0 a0;
.__entry__:
a1.0: int = get;
a0.0: int = get;
v0.0: int = div a0.0 a1.0;

For the out-of-ssa pass, we implemented a very naive algorithm which simply introduced "shadow" variables explicitly and replaced all get and set operations with id.

Analysis and testing

We used brench to run our algorithm on every core and float benchmark in Bril. In all of them, we were able to verify ssa-ness and correctness (except for float/leibniz.bril, which was very long-running to begin with and then suffered from high SSA overhead and so timed out).
Overhead was high: dynamic instruction count for SSA (equivalently for roundtrip, since instructions were 1-to-1 in fromSSA) was 2.7x baseline by geometric mean, with a max of 7.9x and a min of 1.25x. Here's a chart of overhead factors for the benchmarks we tested (except leibniz):

The hardest part

The hardest part of this assignment for us was probably the phi placement component of converting to SSA, since it's the one that most differed from our expectations in how many edge cases there would be and what they would look like (and this is why we switched to the Braun et al approach); I at least was not expecting the large number of useless phi instructions it would place and how we would have to use undef if we had stuck with it.

Michelin star

We believe we deserve a Michelin star for an intuitive and nonstandard implementation of the to-SSA transformation, sidestepping multiple issues by mixing the Braun and Cytron algorithms.

[sampsyo]

Very interesting indeed! Nice work!

we find the uses of a variable and traverse backwards through paths in the CFG, placing gets as we go, until we reach a block which defines the variable. This allows us to avoid using undef.

Huh! That is a very interesting twist on the overall idea here—it sounds like it could insert a lot of gets in the worst case, but you're right that it seems to avoid needing any kind of undef trickery. Very creative!

[jeffreyqdd]

https://github.com/jeffreyqdd/rust_bril/

What I Did

I implemented pruned SSA, which only inserts phi nodes in the dominance frontiers where the target variable is live. To ensure safety, my compiler first runs an initialization analysis (a forward dataflow analysis using the worklist algorithm) to check that used variables are initialized on all incoming control branches. This actually caught a bug in the dead-branch.bril benchmark.

Transfer error: Block 5 (loop_end) using uninitialized variable: v4
Error context:
     28:   jmp .loop_start;
     29: 
     30: .loop_end:
>>>  31:   print v4;
>>>         ^
     32: }

Afterward, my compiler performs φ-insertion and SSA renaming, and then runs Dead Code Elimination (DCE) and Local Value Numbering (LVN) on the SSA form. However, these optimizations did not eliminate as much redundancy as I expected. I believe this is because I have not yet implemented logic to properly handle φ-nodes within these passes.

After my compiler inserts and renames the phi nodes, it runs DCE and LVN on the SSA form. However, these optimizations did not eliminate as much redundancy as I expected. I think this has three major reasons.

1. My Rust compiler imploded, and I had to rewrite most of the infrastructure with better borrowing decisions. I did not have the time to re-implement const-expression folding, copy propagation, and commutative operations. (SSA makes basic LVN so much easier)
2. I did not have the time to implement LVN on the Phi Nodes.

Analysis and Testing

I wrote a short script that runs my compiler on every benchmark, piping the intermediate output into the is_ssa.py utility. I also collected static and dynamic instruction counts on all of the benchmarks.

I also compared my SSA round-trip, SSA + DCE, SSA + LVN + DCE, with the baseline outputs to ensure that the program still behaves as intended.

Hardest part

The hardest part of this assignment was, by far, the phi placement. It was especially tricky to deal with the following case.

@my_fun(a: int) {
 .loop_header:
    a: int = add a a;
}

I added a new basic block at the top of every function (could be empty), but this would allow me to push the phi function when converting out of SSA. Dealing with function arguments was also really tricky.

Michelin Star

I think I deserve a Michelin star for the time I put into this project to get the phi nodes working correctly. It's a shame I wasn't able to improve DCE and LVN to get a better speedup. I know it's possible, but I just genuinely don't have the time to work on this project anymore.

[sampsyo]

Very cool; this all sounds great! You're right that handling entry blocks and arguments can be subtle (and are generally glossed over in the pseudocode we develop for high-level algorithms for things).

My Rust compiler imploded, and I had to rewrite most of the infrastructure with better borrowing decisions.

Very sorry to hear that this happened to you. It definitely can happen! FWIW, a common strategy for Rust compiler implementations that sidesteps this kind of issue is to use "flat" data structures, which we will cover in the last lesson of the semester…

[jku20]

The bulk of the additions can be found here. Be warned, this one is particularly not pretty.

Summary

I implemented functions to go to ssa and come out of ssa based using an algorithm based on dominators. I tested a few difficult cases on hand crafted benchmarks and then evaluated the transformation on every core bril benchmark. It leaves unchanged the behavior of all of the benchmarks, however the performance hit does cause the already long running delannoy benchmark to timeout a lot of the time (I'm pretty sure this isn't due to a semantics change though). I used is_ssa.py in the bril repository to verify for each of these tests and benchmarks the to-ssa transformation did actually convert the program to ssa form.

Some Implementation Challenges

I'm mirroring @jeffreyqdd right above me, but I have to concur that dealing with the entry blocks took a lot of thought. Most of the time get instructions are at the top of basic blocks, but here having a get instruction at the top of the entry block would be an error as there was no previous set. I ended up special casing entry blocks in a post processing step right after renaming to add set instructions at the top of the blocks with either function arguments or undef variables. On a more engineering effort, there was also a surprising amount of information (more of which I kept discovering while writing the code) which has to be collected during each step and plumbed through the compiler which can be a bit difficult. I was writing in Rust, so this meant the easy (but inefficient) way out is superfluous clones everywhere. I feel like this transformation in particular would get a large bang for my buck if I where to do a second draft of the code, now with the knowledge having done the thing.

Evaluation

As mentioned earlier, is_ssa.py was used to verify my program indeed turned every program into ssa form. brench was used to benchmark and verify unchanged behavior after my transformation. For each bril program in brils core benchmarks, I measured the dynamic instruction count after a baseline run and compared it to after converting the program to ssa form, converting to ssa form and running dce, and roundtripping to and from ssa form running dce in the middle. Stats on the changes from the baseline are presented below along with a graph showing the change on specific benchmarks (timeouts and benchmarks showing no change were removed).

Stat (dyn insn count / baseline dyn insn count)		SSA	SSA + DCE	SSA + DCE Roundtrip
Average		2.344180483	1.448045202	1.228465383
Median		2.369565217	1.366812227	1.183406114
StdDev		0.7167899486	0.451742688	0.2458442709
Max		4.630887185	3.185651698	2.095016429
Min		1	0.6492307692	0.6492307692

The round trip SSA transformation seemed to incur around a 20% penalty to dynamic instruction count. Many of these instructions end up being ids left over from the conversion back from SSA. An advanced enough LVN could likely reduce the penalty a fair bit, however unfortunately my LVN has really bad failure modes making programs slower so using it in this evaluation felt like it would muddy the data more than it would help.

Comparing converting SSA to SSA + DCE, there is a huge, around 90% of baseline performance improvement. This suggests running DCE to remove extra gets and sets is really useful! It's worth noting comparing these directly to the baseline or the roundtrip examples isn't super meaningful as the programs have very different constraints on what is allowed in them.

A big outlier in these test cases was the fizz-buzz benchmark. That benchmark has a lot of variables which are pretty simply related. This causes a lot of extra sets and gets turning into a bunch of ids during the roundtrip. This failure mode feels avoidable with a sufficiently advanced LVN implementation, but this is currently just speculation as I haven't written an implementation to test against.

michelin star(s)

I managed a functional implementation and insightful (to me at least) evaluation of that implementation. I think both the implementation and evaluation are a little rough around the edges, but are still interesting and show some good work. However, this is also in the ~1-2 days late range so I would lean towards 0 stars (idk, is half a star a thing?) because of that.

[keikun555]

Good job on the evaluation! Indeed, there are many tricky parts about this task, and it's one of the more difficult ones in this class.

No worries about the lateness! It would be good to let us know early next time so we can give extensions.

[itingtsai]

Source Code

Implementation

I implemented the very basic “into SSA” and “out of SSA” transformations for Bril functions in basic_ssa.py. The goal was to correctly rename variables and insert phi-nodes while keeping the algorithm simple and easy to follow. The program first parses a function into basic blocks, builds predecessor/successor relationships, and collects all variables and their types. For each block B, it maintains the name of each variable on entry and on exit. Inside each block, every definition gets a fresh version generated by a simple counter, while every use refers to the current version. At the top of each block, entry blocks insert id instructions for parameters and undef for other variables. Non-entry blocks insert phi-nodes that merge incoming values from all predecessor blocks, ensuring that each variable is defined exactly once in SSA form. To convert back, phi-nodes are removed by inserting equivalent copy (id) instructions in predecessor blocks. Temporary variables are introduced to safely handle copy cycles. Finally, I added a helper function to measure the overhead of SSA conversion by comparing instruction counts before and after transformation.

Testing

I created test_ssa.py to validate the implementation and measure overhead. The script first transforms a Bril function into SSA form using to_ssa_basic, verifies the SSA property where each variable is assigned exactly once using a local is_ssa check, and then converts it back using from_ssa_basic. It also reports the instruction count overhead using measure_overhead, along with the number of phi and undef instructions for visibility. I also included the code from is_ssa.py in the same file. I tested the transformations on two Bril benchmarks: the conditional example if-orig.bril (result here) and the loop example loop-orig.bril (result here). The conditional example showed +10 instructions (~143% increase), and the loop example showed +15 instructions (~188% increase). The high overhead is expected for this basic algorithm, which inserts phi-nodes at every block entry and expands them into multiple copy instructions. A dominance-frontier–based SSA construction with phi pruning would significantly reduce this overhead for sure.

Michelin Star

I’ll claim ? Michelin star for completing this task. Sorry for the delay…

[keikun555]

I like the evaluation! Maybe we can add some tables to make the data clearer. Also, maybe instead of screenshots of the executions on the examples, we can put it in text form!

I wonder what you felt was the hardest part of this task was!

No worries for the delay! Next time it would be good to let us know beforehand so we can give extensions.

[SyphonArch]

Team & Code

Jake Hyun | Codebase

What I Did

I implemented bidirectional SSA transformations for Bril using the set/get (upsilon/phi) representation. The to_ssa.py uses dominance frontier-based phi placement with live-in filtering to reduce unnecessary phi nodes, and handles tricky cases like loop headers that are also function entry blocks by inserting preheader blocks. The from_ssa.py converts back by replacing get instructions with assignments and inserting copy instructions in predecessor blocks. I also built a comprehensive test harness in test_ssa.py that performs round-trip validation and measures instruction count overhead.

Testing and Results

I tested extensively using round-trip validation: original → SSA → back to standard, comparing outputs with brili and measuring both static and dynamic instruction counts. Testing covered 122 programs across all Bril benchmark suites (core, float, long, mem, mixed), excluding only tail-call.bril which is designed to fail on brili.

Results:

Target programs: 122
100%|█████████████████████████████| 122/122 [02:15<00:00,  1.11s/it]
Successful round trips: 122/122
Static Instr Increase (Geometric Mean): 1.13x
Dynamic Instr Increase (Geometric Mean): 1.14x

All 122 programs pass correctness validation with very low overhead - only 13-14% increase in instruction count, which I'm satisfied with. Refer to results.json for comprehensive results.

Hardest Part

The most challenging aspect was adapting the traditional dominance-frontier algorithm to work with set/get semantics. Ad-hoc patching the original algorithm to the set/get form ended up being a rabbit hole - figuring out how to split phi-nodes across CFG edges, handling terminator vs. fall-through insertion points, and managing shadow variable naming became quite complex. After iterating extensively on the benchmark suite, I ended up with something that may not be pretty but gets the job done. The specific breaking point was orders.bril, which would timeout due to infinite loops when the entry block was also a loop header and my implementation kept resetting parameter-backed phi variables on each iteration. I solved this with preheader insertion for one-time initialization.

Generative AI

I used generative AI to help clarify SSA concepts and algorithmic details when I got stuck on specific implementation challenges. It was particularly helpful for understanding the nuances of dominance frontiers and variable renaming in SSA form. I also used AI assistance to streamline my testing workflow, helping design the comprehensive test harness that validates correctness and measures performance across all benchmark suites.

Michelin Star

I put significant effort into this implementation, achieving 100% success rate across a comprehensive test suite with remarkably low overhead, solving challenging edge cases that trip up many SSA implementations, and building robust testing infrastructure that validates both correctness and performance on all benchmarks. However, I did submit this work 2 days late, so I understand if that affects the evaluation.

[keikun555]

Whew, sounds like a lot of effort was put into this task! Good job!

It would be cool to talk (just a bit) about the script you used to test your implementation too, since it seems like a good work was put in there!

[SyphonArch]

I thought, since I was spending so much time debugging on each test program, that I'd put in extra effort into making a robust tester. This allowed me to inspect intermediate .bril files, and inspect results (and different test verdicts) through a readable json. I only used brili and bril2json and bril2txt as interfaces, skipping any setup overhead or limitations that come with existing testers. Think it was effective for this assignment!

[Nikil-Shyamsunder]

Codebase: https://github.com/Nikil-Shyamsunder/compilers-cs6120

Section 1: What I Did

For this assignment, I implemented the “into SSA” transformation for Bril using the dominance frontier–based algorithm, which is the more challenging version of the SSA construction approach. To start, I realized that my dominance frontier computation from previous work was not entirely correct. Because of that, I significantly reworked my dominance and frontier calculations, rewriting much of that logic to make them more robust and consistent with the SSA algorithm’s needs.

Once I had a correct dominator and frontier computation, I implemented the into SSA pass. The algorithm first identifies where phi-like merges (in Bril’s case, implemented as get/set pairs) need to occur using dominance frontiers. Then, it systematically renames variables by walking the dominator tree, ensuring every variable definition gets a unique name version, and inserting get/set instructions as needed to maintain SSA semantics.

After finishing that, I implemented the out of SSA transformation, which was comparatively much easier. This pass effectively reverses the SSA process by analyzing the set operations to recover the correct variable mappings, normalizing names, and removing SSA-only instructions (get, set, undef). This restores the program to a valid, non-SSA form while preserving semantics.

Section 2: Testing

For testing, I used the core benchmark suite from the Bril repository. My first step was to run the provided Python script is_ssa on all the outputs of my into SSA pass to verify that they were valid SSA programs using a shell script I wrote. It created a valid ssa form for all the core benchmarks.

Once that passed, I ran end-to-end benchmarks comparing the baseline program, the SSA intermediate form, and the round-tripped (baseline to SSA back to non-SSA) version. I verified that all three versions produced identical functional results and also collected data on their total dynamic instruction counts using brench, and all passed.

Overhead as compared to baseline
Average SSA overhead: 107.32%
Average roundtrip overhead: 0.00% (Frankly, I'm not sure how I achieved this)

Section 3: Hardest Part
The hardest part of this assignment was debugging my into SSA transformation. Early on, I wasn’t sure whether my bugs came from the SSA logic itself or from errors upstream in my dominance and frontier calculations. To fix this, I had to “peel back the layers”: verifying each building block from prior assignments (CFG, dominators, dominance frontiers) to ensure they worked correctly both in isolation and together.

It turned out that the root cause was indeed in the dominance frontier computation, and once I fixed that, everything else started to fall into place. Another tricky bug was how I was inserting set instructions: I always placed them right before the terminator instruction, forgetting that some fall-through blocks don’t have explicit terminators. Debugging those subtle control-flow edge cases taught me a lot about being more systematic and careful in maintaining larger compiler passes as the project grows.

Gen AI

I did use Gen AI across this project, primarily to help me reason about and partially prototype parts of the dominance frontier logic in C++. However, it struggled to understand how my data structures interacted, and its suggested code was not functionally correct for my setup. I ended up engineering most of it myself, using AI more as a sounding board than as a direct code generator. I also used it to write my shell script to call is_ssa on all the core benchmarks after being turned into ssa form and to write the specific data analyses I wanted from the csv file generated by brench. ChatGPT did these flawlessly.

Additionally, I referenced the official Bril reference implementation of dominators to compare outputs and verify correctness. While I’m not thrilled that I had to refer to the reference code, doing so allowed me to confirm that this was the root cause of a bunch of errors I had by comparing the outputs from the reference implementation and mine and seeing they were inconsistent.

Michelin Star

This week’s case is admittedly a bit shaky. I struggled early due to incorrect dominance logic from a previous assignment, which slowed me down. However, I ultimately got the SSA transformation working correctly, and I’m proud of how I methodically debugged and fixed the issues, so maybe that deserves a star.

[keikun555]

Good job!

I used the core benchmark suite from the Bril repository

I wonder what the results would look like with the other benchmark suites!

Might be a good idea to talk about the output of the test script, the cases where the results returned incorrect and include them in the evaluation!

Average roundtrip overhead: 0.00% (Frankly, I'm not sure how I achieved this)

Hmm, maybe it could be related to why some of the benchmarks returned incorrect?

[CynyuS]

open source: https://github.com/Smubge/cs6120-L2/tree/L6

Cynthia Shao and Jonathan Brown worked together on this task.

Summary

We implemented the SSA using the Upsilon/Phi Variant as well as the conversion out of SSA. We verified correctness using the is_ssa.py script as well as checked that the programs would do the same thing when converted to SSA and back again.

Benchmark

We used the core benchmarks within Bril, and we tested for correctness after both passes - into SSA and out of SSA. Dynamic instruction count overall increased by 22.02% after the SSA pass, and in the figure below we can see that only 6 programs had a 40% increase in dynamic instruction count, but for 14 programs we were under 10% dynamic instruction difference.

SSA_In

For converting into SSA, I first followed the pseudocode for dominance frontiers, and I implemented by inserting phi instructions. I then realized that phi instructions were deprecated, and modified that implementation into get and set instructions.
This implementation was a little tricky, because I had to split up the logic of inserting phi instructions into gets and sets. Thus, in the phi insertions stage, that would be considered where I inserted gets, and then in the renaming stage, that was where I decided I would insert the sets. There were a lot of cases where sets and gets could be inserted, such as before or after terminators, before and after labels, which gave me a hard time. For the variable renaming, I first toyed with the idea of having each variable as an object so that it could have its own name generator with it, but then I decided that converting between object and variable for the final program output would be too tedious, and thus stuck with the stack implementation instead.

##SSA_out
For converting back to SSA, we knew that in terms of the instructions we had to look for, it would be changing the phi functions to id. However, along the way, we switched to Upsilon/Phi variant. This version was easier in terms of converting, as for the original basic version, you would have to look at both predecessors and add an id function, whereas with set and get, you could replace them with identity functions. This resulted in writing the code to convert back to SSA being significantly easier.

Testing

For testing, we first implemented our SSA with the phi instructions, and then realized that phi instructions in bril were deprecated, and would not work with brili. Due to this, we changed to the Upsilon/Phi Variant, utilizing the get/set instructions. For converting to SSA, we tested by first using the is_ssa.py script on the to_ssa example tests, and verifying that the functionality of the snapshot tests were the same. This was super helpful in the initial debugging, as the benchmark programs are oftentimes very long and hard to debug. We then tested on the core_benchmarks, adding a toml env for both to_ssa and out_ssa. We tested against brili for functionality, and we created .prof files to see the dynamic instruction count. This caught the majority of bugs, especially the ones where the get and set variables weren’t recognizing the back edges of a loop header. For the output, we tested by adding the ssa_out function after the conversion to SSA code, and testing it alongside utilizing the testing code between the ssa and the normal bril code. We also compared the number of instructions of each of them, and used this to view how many more instructions SSA would add to a bril file. Furthermore, we realized that because SSA_out converted the set and get functions to identity functions, that this would result in the same amount of instructions for ssa_out’s output as it would with the ssa_in output.

Hardest Part

There were many hard parts to this task, and honestly we couldn’t really pinpoint one.

One tough point was the realization that phi instructions were deprecated. We believe that through testing should always be the basis of implementation, and the inability to test incrementally between passes was the main motivator of switching to the get/set method.

Another difficult part was figuring out where to insert undefined variables, as well as what happens when the first basic block of a function is also a loop header. These two problems went hand in hand, and the eventual solution was that we had to initialize sets before that loop header label.

Additionally, we ran into a lot of naming issues. For example, things that we did as hacks before was a problem - naming blocks to be unique because we didn’t want to separate our data structures to be function based was an issue when we wanted to create new branches with SSA form. This was solved by a refactoring of all our data structures to be a mapping of functions to their respective basic blocks, preds, cfgs, and dominator sets, and turning all our construction logic into proper constructors.

Self Assessment

We sincerely apologize for the late submission, we experienced delays due to prelims, travel, and health challenges. We believe we deserve a Michelin star because we are proud of our work! We brainstormed an implementation of SSA, and thoroughly tested it. We tested thoroughly using both hand implemented benchmarks, against the core bril benchmark suite, and utilized the algorithms provided(is_ssa.py) to ensure tested correctness. Overall, we collaborated on the SSA’s design decisions and ensured correctness. We also practiced good team coding practices with git, and learned a lot about SSA, its added load to instructions, and the Phi/Upsilon Variant as a whole! We believe we deserve a Michelin star for the tenacity and persistence put into the task.

[keikun555]

Good work! One small suggestion for organization: I would put the benchmarks section under the testing and evaluation.

One tough point was the realization that phi instructions were deprecated

Right, maybe we could say this in the course task website so folks don't get stuck here.

[CynyuS]

Sounds good! We'll make sure to put the benchmarks section under testing next time.