22
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ 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 $\endgroup$
    – Pseudonym
    Aug 13, 2018 at 2:00

2 Answers 2

17
$\begingroup$

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.

If I remember correctly, administrative normal form gets its name from the fact that CPS-based compilation can lead to beta-redexes in the intermediate code that didn't correspond to anything in the source code. These were referred to as "administrative redexes". These could reduced at compile-time, but there was a good amount of research on performing a CPS transform that would output code without the administrative redexes in the first place. The goal then was to produce output in a normal form where all "administrative" redexes were reduced, and this was the origin of Administrative Normal Form. It didn't take long to realize there wasn't a whole lot of benefit to viewing this as a(n optimization of a) two-step process: CPS-transform, reduce administrative redexes. In particular, administrative normal form looks rather like monadic-style as practiced (by hand) most notably in Haskell. The CPS transform can be understood as a conversion to monadic-style where you just happen to be using the CPS monad (so there's really multiple ways to "convert" to monadic-style corresponding to different evaluation orders). In general, though, you could be using a quite different monad, and so conversion to monadic-style and thus administrative normal form isn't really related to CPS in particular.

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.

$\endgroup$
1
  • 3
    $\begingroup$ It's been awhile since the initial answer but I feel good enough to finally accept the answer cuz I understand more than 10%... $\endgroup$
    – CinchBlue
    Feb 5, 2019 at 1:07
2
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 12, 2018 at 22:11
  • $\begingroup$ @DerekElkins It was not clear to me what the OP was asking about. $\endgroup$ Aug 14, 2018 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.