4 ms·
For those who are curious why CPS is such a great compiler representation for implementing optimizations, it's because the passes require less analysis complexi
by larsberg 13y ago
For those who are curious why CPS is such a great compiler representation for implementing optimizations, it's because the passes require less analysis complexity. You only have to handle the "call" portion and don't have to worry separately about "return" points (though you've really just converted returns into a call to a new function!).
It sounds trivial, but in practice it dramatically reduces the size of not only optimization passes such as inlining, but it makes analyses that drive optimizations simpler as well (e.g., control-flow analysis). For an example from my experience (Manticore - http://manticore.cs.uchicago.edu/ http://manticore.cs.uchicago.edu/), my pretty coarse CFA analysis on our direct-style IR is about 750 lines of SML code whereas an optimized CFA with three different variants and extra support for environment analysis is only 700 lines of SML.
- Flow 13y agoInteresting, do you mean that one can use CPS transforms instead of SSA? I've never written a non-trivial code generator, so please excuse me if the question seem dumb.
- lmkg 13y agoSSA and CPS are actually the same thing, in some fashion. I'm not 100% up to speed on the details myself, but as I understand it, CPS is the functional-language form and SSA is the imperative-language form.
- takeoutweight 13y agoA good reference is Andrew Appel's "SSA is functional programming"[1] which discusses the similarities. There are practical differences between SSA, ANF, and CPS, but the similarity at a high level is quite strong. [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3282 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.3...
- larsberg 13y agoThe basic result is that if you just CPS-convert a language without first-class continuations (so, no call-CC), all of that is interchangeable with SSA and any optimization written against one IR can be rewritten fairly mindlessly against the other IR. If you allow first-class continuations in user programs, though, all bets are off and CPS is more expressive. Richard Kelsey wrote the paper that talks about how to convert between CPS and SSA forms, along with the first-class continuation limitation mentioned above: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.6773 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.67...