How I implement SSA form · GitHub
/" data-turbo-transient="true" />
Skip to content
-->
Search Gists
Search Gists
Sign in
Sign up
You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
{{ message }}
Instantly share code, notes, and snippets.
pizlonator/pizlossafull.md
Last active<br>June 30, 2026 19:46
Show Gist options
Download ZIP
Star
107<br>(107)
You must be signed in to star a gist
Fork
(3)
You must be signed in to fork a gist
Embed
Select an option
Embed<br>Embed this gist in your website.
Share<br>Copy sharable link for this gist.
Clone via HTTPS<br>Clone using the web URL.
No results found
Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea3fdb963.js"></script>
" readonly="readonly" data-autoselect="true" data-target="primer-text-field.inputElement " aria-describedby="validation-386c93c0-7331-478d-89fe-fe29bdeb091d" class="form-control FormControl-monospace FormControl-input FormControl-small rounded-left-0 rounded-right-0 border-right-0" type="text" name="gist-share-url-sized-down" />
Save pizlonator/cf1e72b8600b1437dda8153ea3fdb963 to your computer and use it in GitHub Desktop.
Embed
Select an option
Embed<br>Embed this gist in your website.
Share<br>Copy sharable link for this gist.
Clone via HTTPS<br>Clone using the web URL.
No results found
Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea3fdb963.js"></script>
" readonly="readonly" data-autoselect="true" data-target="primer-text-field.inputElement " aria-describedby="validation-fb7c4ecc-5c1f-4bb0-b110-e5ae2828ca1b" class="form-control FormControl-monospace FormControl-input FormControl-small rounded-left-0 rounded-right-0 border-right-0" type="text" name="gist-share-url-original" />
Save pizlonator/cf1e72b8600b1437dda8153ea3fdb963 to your computer and use it in GitHub Desktop.
Download ZIP
How I implement SSA form
Raw
pizlossafull.md
This document explains how I would implement an SSA-based compiler if I was writing one today.
This document is intentionally opinionated. It just tells you how I would do it. This document is intended for anyone who has read about SSA and understands the concept, but is confused about how exactly to put it into practice. If you're that person, then I'm here to show you a way to do it that works well for me. If you're looking for a review of other ways to do it, I recommend this post.
My approach works well when implementing the compiler in any language that easily permits cyclic mutable data structures. I know from experience that it'll work great in C++, C#, or Java. The memory management of this approach is simple (and I'll explain it), so you won't have to stress about use after frees.
I like my approach because it leads to an ergonomic API by minimizing the amount of special cases you have to worry about. Most of the compiler is analyses and transformations over the IR. If the IR's API is great, then the compiler passes are easy to write, succinct, and read almost like the pseudocode in a compiler textbook. This speeds maintenance of the compiler, and makes it cheap (in terms of labor) to add optimizations. This then lets you add lots of optimizations quickly, which leads to the compiler having lots of optimizations, which then leads to great throughput and happy users.
The key ideas:
Instruction-value uniformity. Each instruction is a value, and each value is an instruction. Phi is an instruction. Even a constant is an instruction. Let's call it an Inst for the purpose of this doc. SSA data flow is represented by each Inst having an args vector, which is of type vector. So, each data flow edge is represented as a pointer from the user Inst (where the data flows to) to the Inst being used (where the data flows from).
Phi/Upsilon form, also described here. This decouples the CFG from the SSA form, which makes all CFG transforms easier to write. It doesn't inhibit the implementation of any SSA optimization that I know of (i.e. it's exactly as powerful as SSA). It's also easy to compile out of (if you want to exit SSA).
Arrays. Each function body is just vector. Each basic block contains its instructions by just having a vector. Each basic block knows its index in the function body vector. Each Inst knows its index in its basic block's Inst vector. I'll explain how to make this fast and ergonomic.
Absence of use lists. I find it easier to build the IR, and not any harder to use it, if there are no edges from Insts to the Insts that use them.
Uniform effect representation. Each Inst can produce for you a description of its effects. If an Inst reports no effects, then this means that it can be evaluated at...