from Hacker News

Ways to generate SSA

by g0xA52A2A on 2/11/25, 7:21 AM with 35 comments

• by pizlonator on 2/11/25, 3:11 PM

  Pro tips from an SSA hacker.

  - Ignore the SSA conversion algorithms that don’t use dominance frontiers. Also ignore the dominator tree generation algorithms that aren’t Langauer-Trajan. Reason: you’ll want to have a dominator tree (ie immediate dominators) anyway for a bunch of SSA optimizations. So, you’ll want Langauer-Tarjan. And if you have that, then using dominance frontiers to generate SSA is just easier.

  - CPS isn’t really anything like SSA. Don’t believe that hype. Any claim in PL of two languages or forms being equivalent is not falsifiable because any two Turing complete languages are going to have some transformation between them, so really these papers are just saying “hey look I invented a translation that we all knew was going to be possible and I like my translation for aesthetic reasons”. Working with CPS is nothing like working with SSA.

  - The best way I know of representing Phi in your SSA IR is a Pizlo special. I haven’t written it up except by implementing it (JavaScriptCore uses Pizlo SSA). Here’s the idea. Phi takes no arguments (no block arguments and no value arguments). Each Phi has a shadow variable (in addition to the implicit SSA variable it assigns to). Phi just loads the value out of its shadow variable and assigns it to its implicit variable. Then I have a second instruction called Upsilon that takes two args: an input variable and a Phi. It loads the input variable’s implicit value (just as any SSA use would) and stores it to the Phi’s shadow variable. The result of using this IR is that you have zero coupling between your CFG and the SSA graph. It makes CFG transforms much much easier to write. It also means much less special casing of Phi, in practice.

• by swid on 2/12/25, 4:33 PM

  I worked on compilers at Fortify which does static code analysis, and it's always surprised me SSA does not come up more in context about how to write clean, maintainable, and secure code.

  SSA makes auditing code for dataflow issues much easier - both for people and programs. If you learn how to transform your code to SSA, you might find yourself choosing to write code this way so that you know, exactly, where that input to whatever sensitive string you are building came from. You can more easily trace the lifetime of that input and see what transformations it has been through already.

  I feel like I am the only person in the world talking about SSA outside of compilers! It is useful for humans as well, and we all want to write readable and secure code.

• by pbiggar on 2/11/25, 3:17 PM

  I'll add my own way of constructing SSA, which is mostly untested but worked fine in my compiler: https://paulbiggar.com/research/fit-2009.pdf

• by burjui on 2/21/25, 7:32 AM

  I've used the 2013 algorithm, it's fast, simple enough and easy to implement in Rust.

• by RossBencina on 2/11/25, 9:33 AM

  This looks helpful. I would love to find a simple method of generating SSA that can deal with goto statements.

  A paper that was suggested to me (not mentioned in the linked blog post) is:

  "Practical Improvements to the Construction and Destruction of Static Single Assignment Form", by Preston Briggs, Keith D. Cooper, Timothy J. Harvey, I. Taylor Simpson all at Rice University SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 28(8), 1–28 (July 1998)

• by kldx on 2/11/25, 5:16 PM

  Can anyone suggest simple to implement algorithms for SSA destruction? I find Cytron's destruction easy (paired with copy propagation), but the more recent ones are difficult to implement directly from the papers.

• by UncleEntity on 2/11/25, 6:58 PM

  I don't remember the exact details[0] but the AIs were saying Destination Driven Code Generation is a good (and simple) algorithm for lowering to SSA form. Something about it naturally produces a CFG or the dominance frontier or IDK, I filed it away as something to look into later.

  It does make sense because it can produce reasonably efficient machine code directly from an AST so it is doing a lot of work a naive SSA lowering algorithm leaves for later stages.

  [0] leave this as an exercise for the reader, we aren't on speaking terms lately.

• by theodorethomas on 2/11/25, 6:12 PM

  FORTRAN (IBM, 1956) introduced the "Computed GOTO".

  SSA (IBM, 1988) introduced the "Computed COMEFROM".