Discussion on Simple and Efficient Construction of Static Single Assignment Form

[natetyoung]

Discussion thread for: Simple and Efficient Construction of Static Single
Assignment Form

Discussion leads: @natetyoung, @arw274, @SolidLao, @NingWang0123, Eddie Chen

[maheshejs]

Critique:
The paper was an interesting read, addressing efficient SSA construction, something that’s become a core part of modern compiler design. That said, I found it a bit hard to follow at times, especially when trying to parse the figures, proofs, and code all together. I really appreciate the effort they put into proving the minimality of their SSA form, but I think moving some of those proofs to an appendix might have made the main ideas easier to digest.

I also like how their algorithm doesn’t rely on extra passes or transformations to produce a minimal and pruned SSA. Still, I wonder if that doesn't go against compiler engineering principles: shouldn’t we aim for modular, independent passes? For example, they handle dead code elimination of phi-functions inside the algorithm itself, but DCE is an independent pass that doesn't just apply for SSA, so it could be reused and run after SSA. This makes me question if having it inside SSA construction really simplifies things or just blurs the boundaries between passes.

Question:
It’s been a bit more than ten years since the paper came out, and I’m curious whether their algorithm ever made it into real-world compilers as a replacement for Cytron’s classic algorithm. They showed some improvements compared to Cytron’s, but I wonder if LLVM (or any other compiler) actually adopted it or if Cytron’s algorithm still remains the standard in practice.

[sunwookim028]

It could've helped me as well if they provided more intuitive section first. I also am curious if their approach could be against the modular ideal. Plus, I think proving the algorithm and proving the implementation is a separate thing, and the latter could be practically more important. Can we leverage the proposed proofs to formally verify implemented passes?

[Jacqueline-Wen]

Critique

This paper introduces a novel algorithm for constructing SSAs. This new algorithm is a lazy and backward algorithm – when a variable is used, the algorithm backtracks to find its reaching definitions, caching results to avoid duplicated computation.

I appreciated that the authors of this paper compared this new SSA algorithm with Cytron. However, I feel that the paper could have spent more time discussing evaluation results. The researchers could have built a more systemic understanding of the benefits/drawback of this new algorithm if they had extended the test suite to also include other hardware architectures (RISC instead of CISC). Additionally, I also wish they included metrics regarding compilation time for comparisons between this new algorithm and Cytron.

Questions

• What are the use cases/tradeoffs between Braun’s new algorithm and Cytron?
• Does the simplicity of this algorithm scale to larger programs?

[magg1egao]

Critique:
This paper introduces a new algorithm that is said to make it easier to build SSA form directly while compiling, rather than using separate analyses like the dominance frontier. The idea of constructing the SSA on demand, where the phi-functions are created only when needed, feels conceptually clean and efficient. However, I believe that this lazy, backwards approach might make debugging and understanding the immediate representation more difficult, since all these steps (construction + optimization) are happening at once instead of in clear phases. It would have been interesting if the authors discussed more on the potential tradeoffs between simplicity and transparency. The paper also does not go into much detail how exactly this algorithm would perform in larger, real-world compilers that have to handle unstructured and complex control flow. I wish it would have delved a bit deeper into that aspect, and explored more on how easily this algorithm could be integrated into existing compiler infrastructures.

Question:
While this new algorithm has been marketed as significantly better and more efficient compared to the older Cytron et al.’s algorithm, it does not appear to have been extremely widely adopted. Why do you think this is the case? Is it due to tradition, or possibly something about the performance that this paper does not capture?

[mercure67]

The paper was interesting. While the technique was over my head, the supporting evidence appears to suggest that it is sound, and generally yields some performance result (especially on the compiler performance side). I do wonder if, considering that the paper was discussing an earlier version of LLVM, and the authors do actually modify it, if their changes were ever upstreamed, and if LLVM uses this approach today. I also wonder if there is any memory penalty associated with the approach; and if the resutls produced with on-the-fly optimisations are necessarily more performant programs (if they are possibly a premature optimisation)

As for discussion question(s):

1. How does such an SSA approach impact debuggability / compiler messages (is possibly useful information lost by not going through the CFG)? Is it even worth talking about such issues at the SSA stage, or is it already at a level of abstraction where we can't do anything about these issues?

[Smubge]

Critique
This paper showcases a new algorithm that is built based on the observed flaws with the Cytron et al. SSA algorithm. The ideas seem simple at a glance, but there seem to be some parts that need further development. For instance, they state that the algorithm is not highly optimized, yet on comparison it seems to be faster in runtime than a highly optimized Cytron et al. I am very curious to how this algorithm would perform in the industry.

Question
This algorithm (although the authors are biased) is stated to have a runtime on par with Cyrtron et al.'s algorithm while allowing a "direct translation into SSA-based IR" (p. 1). This paper was written in 2013, and I am curious of the 1) use of this algorithm in modern day, 2) further development of this algorithm (if there are any) and 3) has another algorithm that is better than it been developed? If the algorithm is not used in modern day, I am curious as to why that is. If there is also not further development on the algorithm or research to create a better algorithm, I am curious on why it would be seen as "complete", as in the conclusions the authors themselves state that they expect after further fine tuning, the performance can be improved.

[SerenaYZhang]

Critique:
This paper offers an alternative approach for SSA construction to the traditional Cytron et al.'s algorithm. The algorithm uses a lazy, backward search strategy that enables direct construction from ASTs or bytecode, eliminating the need to build a CFG that is required in Cytron et al's algorithm. I do wish that the paper went more in-depth into its exact details of how the algorithm works as some of the steps seem to require a CFG, so I'm curious on how the algorithm goes around this. Perhaps including a more detailed walkthrough of the entire procedure on an example could improve clarity and reproducibility. I also wish there was a section on evaluating the overhead of CFG construction, as this is the key computational step that the paper's algorithm aims to optimize.

Questions:
What is the typical compile-time cost of constructing a CFG, and how does this cost scale with program size and complexity?
Under what conditions might the overhead of the traditional CFG construction be negligible, making Cytron et al.'s algorithm the faster choice?
What is the proposed framework for deciding between these two algorithms, considering the trade-off between the new algorithm's directness and the potential for the traditional approach to be faster when a CFG is already available or inexpensive to compute?

[az275]

Critique

It reads to me like the main benefit of the SSA construction algorithm presented in this paper is that it avoids the intermediate CFG construction and dominance relation/dominance frontier analysis required by the Cytron et al. algorithm. I don't know that I would characterize the algorithm and its presentation as "simple"; I found it somewhat hard to parse. In particular, I concur with @SerenaYZhang that I'm not totally clear on how some parts work without a pre-computed CFG, e.g. section 2.2. I'll take the proofs at face value, but I'm also somewhat skeptical of the evaluation; it is absolutely not comprehensive and gives little context as to why the results are what they are, and why we should care.

Questions

Pros and cons of this algorithm versus the Cytron et al. algorithm? How do they compare in terms of readability and performance on workloads of interest? Why choose one over the other?
Has this changed the landscape significantly in the dozen-ish years since its publication? Are there compilers which use this algorithm?

[pedropontesgarcia]

Critique: The paper's proposal - a backward SSA algorithm that doesn't use the dominance frontier - seems quite interesting! It naturally yields a "pruned" SSA and allows for optimizations during IR construction. Strong points: conceptually simple, awesome theoretical work (proof of minimality e.g) and presented evidence that compares it with LLVM's algorithm (Cytron et al). One slightly confusing aspect is the layering of phi-handling strategies (trivial phi removal, SCC contraction, marker algorithm); this makes it difficult to separate the core SSA construction from the optimization passes.

Question: Is the backward construction affected in any way by highly irregular control flow, perhaps in ways that are not as impactful for Cytron et al's algorithm? I'm specifically thinking of programs with complex control flow (like a lot of nested loops), where recursion and delayed phi placement could add overhead.

[itingtsai]

Critique: This paper introduces a backward algorithm for building Static Single Assignment (SSA). It aims to make SSA construction easier by generating it directly, rather than relying on separate analyses such as dominance frontiers. Unlike the older Cytron et al. method, it doesn’t require constructing a control flow graph first, which could make it faster and simpler. While the idea seems efficient, I would like to see how well the method performs on large or real-world programs through concrete examples and evaluations. Overall, the approach appears promising, but I wonder whether it has been widely adopted in real compilers.

Questions: Has this SSA algorithm been used in any modern compilers? What further developments or improvements have been made since then?

[adnan-armouti]

Critique:
The main contribution is a lazy SSA builder: while Cytron et al. first compute dominance IDF sets and then insert phi nodes, this paper instead looks up reaching definitions on demand while building IR, and inserts phi nodes only along paths actually traversed. One advantage is that it produces pruned SSA automatically. For reducible CFGs, it provides minimal SSA always. For irreducible CFGs a short post-pass is required to collapse redundant phi nodes to ensure minimality. This seems useful because you can translate directly from bytecode into SSA and even run SSA-based local optimizations such as simple constant folding and value numbering during construction.

Question:
I actually have two. First, under what conditions would this method be better than Cytron et al. and vice versa? Apologies if this is too open ended, I just couldn't tell in the evaluation if this was addressed, beyond them showing near-parity with Cytron et al. on SPEC. Second, is there any way that we can do away with the post pass for irreducible CFGs? e.g. if we performed some additional online checks to avoid most phi nodes up front, would this added complexity be worth it?

[SyphonArch]

Critique

Programming languages research often fascinates me because it blends formal reasoning with tangible system impact. Many papers in this field are deeply theoretical and proof driven, yet they frequently lead to techniques used in real compilers. This paper is a great example; it does not just propose a new SSA construction algorithm, it actively demonstrates how it integrates into real compilation pipelines. I appreciate that it grounds the discussion in practical compiler construction rather than staying abstract.

One small critique I have is that while the authors emphasize that their approach avoids dominance and liveness analyses, the resulting algorithm still involves recursive lookups and phi placement logic whose complexity can grow with control flow and variable count. I wonder whether the practical benefits of avoiding explicit dominance computation truly outweigh the implicit cost of these global traversals, especially in large or irregular programs.

Discussion Question

The authors argue that their algorithm’s ability to interleave SSA construction with on the fly optimizations is a key strength. Could performing optimizations this early in the pipeline ever interfere with later, more global optimizations, or is earlier simplification always a win in practice?

[jku20]

Critique: In the time complexity analysis, I saw the SCC construction looks like it can get quite expensive. In particular, the $(B + E) \cdot V^2$ component feels like it could grow really really quickly for large programs as I find programs can sometimes have a lot of variables, especially in lower level intermediate languages which seems like it could be an application of this algorithm. The construction based on dominator I don't think shares this same and instead grows I think by roughly a power less on the $V$. This didn't seem to come up in practice in their evaluations in that it wasn't addressed at all, but this still leaves it unclear to me if there is a measurable/noticeable slowdown at all (and wasn't that bad) or if it just washed out in the noise in all but adversarial programs due to $V$ normally not being huge enough.

Question: I saw @pedropontesgarcia and @magg1egao mentioned this a bit, but I want to drill in on it: my understanding of the algorithm is that by design it requires optimizations to occur inline with CFG construction. The authors mention that simple optimizations based on single basic blocks can be preformed during construction, and of course analyses can be applied after. However, I wonder if there are global analyses which would benefit from being performed prior to the SSA CFG construction which now become impossible to do?

[tf-mac]

Critique: I thought the property section of the paper was the most interesting, especially minimal SSA form. The paper goes into great depth on proving the algorithm produces an intermediate in this form. Thus, the algorithm is proven to be, in at least some form, optimal, in that it contains no trivial phi functions and has singular definitions for each variable.

Question: The authors mix average time and worst time complexity heavily in their analysis. Is there an advantage to this level of disparate analysis, especially given that the conclusion to that section still uses worst time complexity?

[CynyuS]

Critique: This paper presents a really elegant solution to creating SSAs. It reminds me of a more DP approach. I wish the paper made more comparisons about what properties of certain benchmarks made the Marker to Cytron's algorithm instruction ratio higher, and what general properties of a program makes the SSA builder excel.

Question: I saw @adnan-armouti mention this as well and I was wondering the same thing. The condition that this simple algorithm works on reducible CFG and other post-processing algorithms must be applied to it if it's not reducible seems to be a pretty good explanation for why different benchmarks perform comparably or worse for the proposed algorithm. I wonder if there are other insights into program structures that do better with this DP-like approach, and how could we take advantage of different programming languages structure to further optimize this algorithm?

[Mond45]

Critique

The paper introduces a lazy approach to SSA construction that produces a minimal, pruned SSA form. The algorithm also supports incomplete CFGs, making it applicable during the translation from AST to IR. The paper discusses several optimizations aimed at reducing the number of inserted $\phi$-nodes, including the removal of trivial $\phi$-nodes, elimination of redundant SCCs, and the use of the marker algorithm.
An interesting aspect of the paper is the discussion of optimizations that can be performed simultaneously with SSA construction, further reducing the number of $\phi$-nodes. I also appreciate that the paper notes how certain optimizations in SSA form can alter data flow and thus affect the placement of $\phi$-nodes, requiring SSA reconstruction.
Overall, it was an interesting read. However, I would like to see a more detailed analysis comparing the approach with LLVM, as well as a comparison between programs optimized on-the-fly during SSA construction versus those optimized after conversion.

Questions

• How does the algorithm lead to LLVM's constant folding being triggered more frequently?
• The paper mentions that the algorithm for removing superfluous $\phi$-nodes could be integrated into other SSA construction methods - what would be the result if applied to Cytron's algorithm?
• Is constructing a control flow graph really that big of an overhead?

[tobiwg]

Discussion: A Lazy Take on Building SSA

This paper proposes a really neat alternative to the classic Cytron et al. algorithm for building SSA. Instead of computing dominance frontiers and placing φ-nodes eagerly, they flip the process around — it’s lazy and backwards.

Whenever a variable is used, the algorithm searches backwards through the CFG to find its reaching definition, inserting φ-functions only when necessary. It also handles incomplete CFGs (like when you’re still building the IR from an AST) by using a concept called sealing — blocks are “sealed” once all their predecessors are known. This makes it possible to build SSA directly from high-level structures like ASTs or bytecode, without detouring through a non-SSA CFG first.

Another cool part is that it performs on-the-fly optimizations (constant folding, copy propagation, etc.) during construction. Because it’s already in SSA form, some optimizations can happen immediately, sometimes even reducing φ-nodes below what Cytron’s “minimal” SSA would produce.

In the evaluation, they implemented it in LLVM and found it just as fast as the traditional approach — sometimes faster when you include those early optimizations. It’s also great for JIT compilers or for reconstructing SSA after transformations like jump threading.

What I liked most is how conceptually simple it is: it treats SSA construction almost like variable lookup with memoization instead of a heavy analysis pass. It feels more intuitive, especially if you’re used to functional or recursive program structures.

Things I’m wondering:

• Would this approach scale well for large or parallel IR construction (like MLIR or Rust’s MIR)?

• How much benefit do we really get from on-the-fly optimizations vs. running standard passes afterward?

• Could the same lazy idea be used for other compiler analyses, like liveness or dominance computation?

[jeffreyqdd]

Critique: This paper presents an alternative SSA-construction algorithm that enables direct transformation from AST or bytecode into pruned SSA format, without the need for building dominance trees and dominance frontiers like in Cytron et al. The algorithm appears to work well when the control flow is reducible, but for irreducible control flow it may insert extra phi nodes, and cleanup could be non-trivial. I also found the proof to be quite challenging to understand. However, I still think this is really cool.

Question: I'm curious about the real-world performance of this algorithm. Do on-the-fly operations cancel out the benefits of fewer phi nodes? I guess it's a compiler, so you can afford to take more time to generate a better binary.