# Why is static-single assignment preferred over continuation passing style in many industry-used compilers?

According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects using continuation-passing style (CPS) is a bit lacking in comparison.

I have this notion that CPS is preferred by compilers and interpreters that implement primarily functional languages -- particularly, Haskell and Scheme seem to have strong inclinations towards CPS style due to the restrictions on mutation or need for first-class continuation support (I would guess that Smalltalk would possibly need this as well). The major literature that I've encountered that uses CPS seems to be those that are primarily working on Scheme or are related to Scheme in some respect.

Is there any particular reason why SSA is used in industry besides momentum of adoption? SSA and CPS have a close relationship; that means that it would be easy to state either in terms of another, but perhaps the information representation would be less compact or less efficient for CPS.

• IIRC, traditional optimisations for imperative languages designed in the days of traditional dataflow analysis transfer to SSA form more easily than they do to CPS.. In particular, use-def and def-use chains can be "read off" the SSA representation directly. Inertia counts for something – Pseudonym Aug 13 '18 at 2:00

I imagine many compiler implementers for typical imperative languages simply weren't that familiar with CPS and CPS-based compilation techniques. In the functional programming community both CPS and CPS-based compilation are very well-known techniques - the latter from Guy Steele's work. Nevertheless, even in the FP community, most compilers don't use CPS-based techniques for compilation unless the language itself supports control operators like call/cc. Something more like Administrative Normal Form (ANF) (sometimes also referred to as Monadic Normal Form which is intimately related for reasons that will become clear) is used which has an even tighter relationship to SSA than CPS does.

Nevertheless, there were some benefits to CPS versus ANF. In particular, there were certain optimizations that you could do in CPS with just standard optimizations, such as beta reducing, that required (seemingly) ad-hoc rules for ANF. From the monadic perspective, these rules correspond to commuting conversions. The upshot is now there is a theory that can explain what rules should be added and why. A recent paper gives a (new and) pretty clear description of this (from a logical perspective) and its related work section serves as a brief but decent survey of and references into the literature on the topics I mention.

The problem with CPS is tied to one of its main benefits. CPS transforming allows you to implement control operators like call/cc, but this means every non-local function call in the CPS intermediate code has to be treated as potentially performing control effects. If your language includes control operators, then this is just as it should be (though even then most functions probably aren't doing any control shenanigans). If your language doesn't include control operators, then there are global invariants on the use of continuations that are not evident locally. This means there are optimizations that are unsound to perform on general CPS code that would be sound to perform on this particularly well-behaved use of CPS. One way this manifests is in the change in precision of data and control flow analyses. (CPS transforming helps in some ways, hurts in others, though the ways it helps are mostly due to duplication rather than the CPS aspect itself.)1 You could, of course, add rules and adjust analyses to compensate for this (i.e. to exploit the global invariants), but then you've partially defeated one of the major benefits of CPS-based compilation which is that many (seemingly) special-purpose, ad-hoc optimizations become special-cases of general-purpose optimization (particularly beta reduction).

Ultimately, unless your language has control operators, there is usually not much reason to use a CPS-based compilation scheme. Once you compensate for the issues I mentioned above, you've typically eliminated the benefits of CPS-based compilation and produced something equivalent to not using CPS. At that point, CPS is just making convoluted looking intermediate code for not much benefit. An argument for CPS-based compilation from 2007 addresses some of these issues and presents some other benefits using a different form of CPS conversion. The things that paper brings up are covered in part by the (2017) paper I mentioned before.

1 Doesn't the equivalence between SSA and CPS make this more or less impossible? No. One of the first things the paper introducing this equivalence states is that the equivalence does not work for arbitrary CPS code, but it does work for the output of a CPS transform (which they define) for a language without control operators.

• It's been awhile since the initial answer but I feel good enough to finally accept the answer cuz I understand more than 10%... – CinchBlue Feb 5 '19 at 1:07

I'm not a compiler expert, so take what I say with a grain of salt, I hope that a real compiler expert will chime in. I was told that:

• CPSed code tends to jump non-locally a lot, which ruins cache locality, hence performance.
• CPS requires more expensive garbage collection than conventional compilation which can typically store a lot of stuff on the stack (which is faster to allocate and deallocate).

Both conspire to making code compiled by CPS-transform comparatively slow.

• I think you are mixing CPS transformed source code (or a source-to-source transformation) with using CPS an an intermediate language. Assuming your input language doesn't support control effects like call/cc, then, for example, the continuations will be used with a stack discipline - no garbage collector will be needed, and the continuations will correspond, more or less, to edges of the control flow graph so there will not be any extra jumping. You don't need to implement the continuations using some general-purpose implementation of higher order functions. – Derek Elkins left SE Aug 12 '18 at 22:11
• @DerekElkins It was not clear to me what the OP was asking about. – Martin Berger Aug 14 '18 at 15:38