Good evening, hackers. Today's missive is more of a massive, in the sense that it's another presentation transcript-alike; these things always translate to many vertical pixels.
In my defense, I hardly ever give a presentation twice, so not only do I miss out on the usual per-presentation cost amortization and on the incremental improvements of repetition, the more dire error is that whatever message I might have can only ever reach a subset of those that it might interest; here at least I can be more or less sure that if the presentation would interest someone, that they will find it.
So for the time being I will try to share presentations here, in the spirit of, well, why the hell not.
CPS Soup
A functional intermediate language
10 May 2023 – Spritely
Andy Wingo
Igalia, S.L.
Last week I gave a training talk to Spritely Institute collaborators on the intermediate representation used by Guile's compiler.
CPS Soup
Compiler: Front-end to Middle-end to Back-end
Middle-end spans gap between high-level source code (AST) and low-level machine code
Programs in middle-end expressed in intermediate language
CPS Soup is the language of Guile’s middle-end
An intermediate representation (IR) (or intermediate language , IL) is just another way to express a computer program. Specifically it's the kind of language that is appropriate for the middle-end of a compiler, and by "appropriate" I meant that an IR serves a purpose: there has to be a straightforward transformation to the IR from high-level abstract syntax trees (ASTs) from the front-end, and there has to be a straightforward translation from IR to machine code.
There are also usually a set of necessary source-to-source transformations on IR to "lower" it, meaning to make it closer to the back-end than to the front-end. There are usually a set of optional transformations to the IR to make the program run faster or allocate less memory or be more simple: these are the optimizations.
"CPS soup" is Guile's IR. This talk presents the essentials of CPS soup in the context of more traditional IRs.
How to lower?
High-level:
(+ 1 (if x 42 69))
Low-level:
cmpi $x, #f
je L1
movi $t, 42
j L2
L1:
movi $t, 69
L2:
addi $t, 1
How to get from here to there?
Before we dive in, consider what we might call the dynamic range of an intermediate representation: we start with what is usually an algebraic formulation of a program and we need to get down to a specific sequence of instructions operating on registers (unlimited in number, at this stage; allocating to a fixed set of registers is a back-end concern), with explicit control flow between them. What kind of a language might be good for this? Let's attempt to answer the question by looking into what the standard solutions are for this problem domain.
1970s
Control-flow graph (CFG)
graph := array<block>
block := tuple<preds, succs, insts>
inst := goto B
| if x then BT else BF
| z = const C
| z = add x, y
...
BB0: if x then BB1 else BB2
BB1: t = const 42; goto BB3
BB2: t = const 69; goto BB3
BB3: t2 = addi t, 1; ret t2
Assignment, not definition
Of course in the early days, there was no intermediate language; compilers translated ASTs directly to machine code. It's been a while since I dove into all this but the milestone I have in my head is that it's the 70s when compiler middle-ends come into their own right, with Fran Allen's work on flow analysis and optimization.
In those days the intermediate representation for a compiler was a graph of basic blocks, but unlike today the paradigm was assignment to locations rather than definition of values. By that I mean that in our example program, we get t assigned to in two places (BB1 and BB2); the actual definition of t is implicit, as a storage location, and our graph consists of assignments to the set of storage locations in the program.
1980s
Static single assignment (SSA) CFG
graph := array<block>
block := tuple<preds, succs, phis, insts>
phi := z := φ(x, y, ...)
inst := z := const C
| z := add x, y
...
BB0: if x then BB1 else BB2
BB1: v0 := const 42; goto BB3
BB2: v1 := const 69; goto BB3
BB3: v2 := φ(v0,v1); v3:=addi t,1; ret v3
Phi is phony function: v2 is v0 if coming from first predecessor, or v1 from second predecessor
These days we still live in Fran Allen's world, but with a twist: we no longer model programs as graphs of assignments, but rather graphs of definitions. The introduction in the mid-80s of so-called "static single-assignment" (SSA) form graphs mean that instead of having two assignments to t, we would define two different values v0 and v1. Then later instead of reading the value of the storage location associated with t, we define v2 to be either v0 or v1: the former if we reach the use of t in BB3 from BB1, the latter if we are coming from BB2.
If you think on the machine level, in terms of what the resulting machine code will be, this either function isn't a real operation; probably register allocation will put v0, v1, and v2 in the same place, say $rax. The function linking the definition of v2 to the inputs v0 and v1 is purely notational; in a way, you could say that it is phony , or not real. But when the creators of SSA went to submit this notation for publication they knew that they would need something that sounded more rigorous than "phony function", so they instead called it a "phi" (φ) function. Really.
2003: MLton
Refinement: phi variables are basic block args
graph := array<block>
block := tuple<preds, succs, args, insts>
Inputs of phis implicitly computed from preds
BB0(a0): if a0 then BB1() else BB2()
BB1(): v0 := const 42; BB3(v0)
BB2(): v1 := const 69; BB3(v1)
BB3(v2): v3 := addi v2, 1; ret v3
SSA is still where it's at, as a conventional solution to the IR problem. There have been some refinements, though. I learned of one of them from MLton; I don't know if they were first but they had the idea of interpreting phi variables as arguments to basic blocks. In this formulation, you don't have explicit phi instructions; rather the "v2 is either v1 or v0" property is expressed by v2 being a parameter of a block which is "called" with either v0 or v1 as an argument. It's the same semantics, but an interesting notational change.
Refinement: Control tail
Often nice to know how a block ends (e.g. to compute phi input vars)
graph := array<block>
block := tuple<preds, succs, args, insts,
control>
control := if v then L1 else L2
| L(v, ...)
| switch(v, L1, L2, ...)
| ret v
One other refinement to SSA is to note that basic blocks consist of some number of instructions that can define values or have side effects but which otherwise exhibit fall-through control flow, followed by a single instruction that transfers control to another block. We might as well store that control instruction separately; this would let us easily know how a block ends, and in the case of phi block arguments, easily say what values are the inputs of a phi variable. So let's do that.
Refinement: DRY
Block successors directly computable from control
Predecessors graph is inverse of successors graph
graph := array<block>
block := tuple<args, insts, control>
Can we simplify further?
At this point we notice that we are repeating ourselves; the successors of a block can be computed directly from the block's terminal control instruction. Let's drop those as a distinct part of a block, because when you transform a program it's unpleasant to have to needlessly update something in two places.
While we're doing that, we note that the predecessors array is also redundant, as it can be computed from the graph of block successors. Here we start to wonder: am I simpliying or am I removing something that is fundamental to the algorithmic complexity of the various graph transformations that I need to do? We press on, though, hoping we will get somewhere interesting.
Basic blocks are annoying
Ceremony about managing insts; array or doubly-linked list?
Nonuniformity: “local” vs ‘`global’' transformations
Optimizations transform graph A to graph B; mutability complicates this task
- Desire to keep A in mind while making B
- Bugs because of spooky action at a distance
Recall that the context for this meander is Guile's compiler, which is written in Scheme. Scheme doesn't have expandable arrays built-in. You can build them, of course, but it is annoying. Also, in Scheme-land, functions with side-effects are conventionally suffixed with an exclamation mark; after too many of them, both the writer and the reader get fatigued. I know it's a silly argument but it's one of the things that made me grumpy about basic blocks.
If you permit me to continue with this introspection, I find there is an uneasy relationship between instructions and locations in an IR that is structured around basic blocks. Do instructions live in a function-level array and a basic block is an array of instruction indices? How do you get from instruction to basic block? How would you hoist an instruction to another basic block, might you need to reallocate the block itself?
And when you go to transform a graph of blocks... well how do you do that? Is it in-place? That would be efficient; but what if you need to refer to the original program during the transformation? Might you risk reading a stale graph?
It seems to me that there are too many concepts, that in the same way that SSA itself moved away from assignment to a more declarative language, that perhaps there is something else here that might be more appropriate to the task of a middle-end.
Basic blocks, phi vars redundant
Blocks: label with args sufficient; “containing” multiple instructions is superfluous
Unify the two ways of naming values: every var is a phi
graph := array<block>
block := tuple<args, inst>
inst := L(expr)
| if v then L1() else L2()
...
expr := const C
| add x, y
...
I took a number of tacks here, but the one I ended up on was to declare that basic blocks themselves are redundant. Instead of containing an array of instructions with fallthrough control-flow, why not just make every instruction a control instruction? (Yes, there are arguments against this, but do come along for the ride, we get to a funny place.)
While you are doing that, you might as well unify the two ways in which values are named in a MLton-style compiler: instead of distinguishing between basic block arguments and values defined within a basic block, we might as well make all names into basic block arguments.
Arrays annoying
Array of blocks implicitly associates a label with each block
Optimizations add and remove blocks; annoying to have dead array entries
Keep labels as small integers, but use a map instead of an array
graph := map<label, block>
In the traditional SSA CFG IR, a graph transformation would often not touch the structure of the graph of blocks. But now having given each instruction its own basic block, we find that transformations of the program necessarily change the graph. Consider an instruction that we elide; before, we would just remove it from its basic block, or replace it with a no-op. Now, we have to find its predecessor(s), and forward them to the instruction's successor. It would be useful to have a more capable data structure to represent this graph. We might as well keep labels as being small integers, but allow for sparse maps and growth by using an integer-specialized map instead of an array.
This is CPS soup
graph := map<label, **cont** >
cont := tuple<args, **term** >
term := **continue** to L
with values from expr
| if v then L1() else L2()
...
expr := const C
| add x, y
...
SSA is CPS
This is exactly what CPS soup is! We came at it "from below", so to speak; instead of the heady fumes of the lambda calculus, we get here from down-to-earth basic blocks. (If you prefer the other way around, you might enjoy this article from a long time ago.) The remainder of this presentation goes deeper into what it is like to work with CPS soup in practice.
Scope and dominators
BB0(a0): if a0 then BB1() else BB2()
BB1(): v0 := const 42; BB3(v0)
BB2(): v1 := const 69; BB3(v1)
BB3(v2): v3 := addi v2, 1; ret v3
What vars are “in scope” at BB3? a0 and v2.
Not v0; not all paths from BB0 to BB3 define v0.
a0 always defined: its definition dominates all uses.
BB0 dominates BB3: All paths to BB3 go through BB0.
Before moving on, though, we should discuss what it means in an SSA-style IR that variables are defined rather than assigned. If you consider variables as locations to which values can be assigned and which initially hold garbage, you can read them at any point in your program. You might get garbage, though, if the variable wasn't assigned something sensible on the path that led to reading the location's value. It sounds bonkers but it is still the C and C++ semantic model.
If we switch instead to a definition-oriented IR, then a variable never has garbage; the single definition always precedes any uses of the variable. That is to say that all paths from the function entry to the use of a variable must pass through the variable's definition, or, in the jargon, that definitions dominate uses. This is an invariant of an SSA-style IR, that all variable uses be dominated by their associated definition.
You can flip the question around to ask what variables are available for use at a given program point, which might be read equivalently as which variables are in scope; the answer is, all definitions from all program points that dominate the use site. The "CPS" in "CPS soup" stands for continuation-passing style , a dialect of the lambda calculus, which has also has a history of use as a compiler intermediate representation. But it turns out that if we use the lambda calculus in its conventional form, we end up needing to maintain a lexical scope nesting at the same time that we maintain the control-flow graph, and the lexical scope tree can fail to reflect the dominator tree. I go into this topic in more detail in an old article, and if it interests you, please do go deep.
CPS soup in Guile
Compilation unit is intmap of label to cont
cont := $kargs names vars term
| ...
term := $continue k src expr
| ...
expr := $const C
| $primcall ’add #f (a b)
| ...
Conventionally, entry point is lowest-numbered label
Anyway! In Guile, the concrete form that CPS soup takes is that a program is an intmap of label to cont. A cont is the smallest labellable unit of code. You can call them blocks if that makes you feel better. One kind of cont, $kargs, binds incoming values to variables. It has a list of variables, vars , and also has an associated list of human-readable names, names , for debugging purposes.
A $kargs contains a term , which is like a control instruction. One kind of term is $continue, which passes control to a continuation k. Using our earlier language, this is just goto *k*, with values, as in MLton. (The src is a source location for the term.) The values come from the term's expr , of which there are a dozen kinds or so, for example $const which passes a literal constant, or $primcall, which invokes some kind of primitive operation, which above is add. The primcall may have an immediate operand, in this case #f, and some variables that it uses, in this case a and b. The number and type of the produced values is a property of the primcall; some are just for effect, some produce one value, some more.
CPS soup
term := $continue k src expr
| $branch kf kt src op param args
| $switch kf kt* src arg
| $prompt k kh src escape? tag
| $throw src op param args
Expressions can have effects, produce values
expr := $const val
| $primcall name param args
| $values args
| $call proc args
| ...
There are other kinds of terms besides $continue: there is $branch, which proceeds either to the false continuation kf or the true continuation kt depending on the result of performing op on the variables args , with immediate operand param. In our running example, we might have made the initial term via:
(build-term
($branch BB1 BB2 'false? #f (a0)))
The definition of build-term (and build-cont and build-exp) is in the (language cps) module.
There is also $switch, which takes an unboxed unsigned integer arg and performs an array dispatch to the continuations in the list kt , or kf otherwise.
There is $prompt which continues to its k , having pushed on a new continuation delimiter associated with the var tag ; if code aborts to tag before the prompt exits via an unwind primcall, the stack will be unwound and control passed to the handler continuation kh. If escape? is true, the continuation is escape-only and aborting to the prompt doesn't need to capture the suspended continuation.
Finally there is $throw, which doesn't continue at all, because it causes a non-resumable exception to be thrown. And that's it; it's just a handful of kinds of term, determined by the different shapes of control-flow (how many continuations the term has).
When it comes to values, we have about a dozen expression kinds. We saw $const and $primcall, but I want to explicitly mention $values, which simply passes on some number of values. Often a $values expression corresponds to passing an input to a phi variable, though $kargs vars can get their definitions from any expression that produces the right number of values.
Kinds of continuations
Guile functions untyped, can multiple return values
Error if too few values, possibly truncate too many values, possibly cons as rest arg...
Calling convention: contract between val producer & consumer
- both on call and return side
Continuation of $call unlike that of $const
When a $continue term continues to a $kargs with a $const 42 expression, there are a number of invariants that the compiler can ensure: that the $kargs continuation is always passed the expected number of values, that the vars that it binds can be allocated to specific locations (e.g. registers), and that because all predecessors of the $kargs are known, that those predecessors can place their values directly into the variable's storage locations. Effectively, the compiler determines a custom calling convention between each $kargs and its predecessors.
Consider the $call expression, though; in general you don't know what the callee will do to produce its values. You don't even generally know that it will produce the right number of values. Therefore $call can't (in general) continue to $kargs; instead it continues to $kreceive, which expects the return values in well-known places. $kreceive will check that it is getting the right number of values and then continue to a $kargs, shuffling those values into place. A standard calling convention defines how functions return values to callers.
The conts
cont := $kfun src meta self ktail kentry
| $kclause arity kbody kalternate
| $kargs names syms term
| $kreceive arity kbody
| $ktail
$kclause, $kreceive very similar
Continue to $ktail: return
$call and return (and $throw, $prompt) exit first-order flow graph
Of course, a $call expression could be a tail-call, in which case it would continue instead to $ktail, indicating an exit from the first-order function-local control-flow graph.
The calling convention also specifies how to pass arguments to callees, and likewise those continuations have a fixed calling convention; in Guile we start functions with $kfun, which has some metadata attached, and then proceed to $kclause which bridges the boundary between the standard calling convention and the specialized graph of $kargs continuations. (Many details of this could be tweaked, for example that the case-lambda dispatch built-in to $kclause could instead dispatch to distinct functions instead of to different places in the same function; historical accidents abound.)
As a detail, if a function is well-known , in that all its callers are known, then we can lighten the calling convention, moving the argument-count check to callees. In that case $kfun continues directly to $kargs. Similarly for return values, optimizations can make $call continue to $kargs, though there is still some value-shuffling to do.
High and low
CPS bridges AST (Tree-IL) and target code
High-level: vars in outer functions in scope
Closure conversion between high and low
Low-level: Explicit closure representations; access free vars through closure
CPS soup is the bridge between parsed Scheme and machine code. It starts out quite high-level, notably allowing for nested scope, in which expressions can directly refer to free variables. Variables are small integers, and for high-level CPS, variable indices have to be unique across all functions in a program. CPS gets lowered via closure conversion, which chooses specific representations for each closure that remains after optimization. After closure conversion, all variable access is local to the function; free variables are accessed via explicit loads from a function's closure.
Optimizations at all levels
Optimizations before and after lowering
Some exprs only present in one level
Some high-level optimizations can merge functions (higher-order to first-order)
Because of the broad remit of CPS, the language itself has two dialects, high and low. The high level dialect has cross-function variable references, first-class abstract functions (whose representation hasn't been chosen), and recursive function binding. The low-level dialect has only specific ways to refer to functions: labels and specific closure representations. It also includes calls to function labels instead of just function values. But these are minor variations; some optimization and transformation passes can work on either dialect.
Practicalities
Intmap, intset: Clojure-style persistent functional data structures
Program: intmap<label,cont>
Optimization: program→program
Identify functions: (program,label)→intset<label>
Edges: intmap<label,intset<label>>
Compute succs: (program,label)→edges
Compute preds: edges→edges
I mentioned that programs were intmaps, and specifically in Guile they are Clojure/Bagwell-style persistent functional data structures. By functional I mean that intmaps (and intsets) are values that can't be mutated in place (though we do have the transient optimization).
I find that immutability has the effect of deploying a sense of calm to the compiler hacker -- I don't need to worry about data structures changing out from under me; instead I just structure all the transformations that you need to do as functions. An optimization is just a function that takes an intmap and produces another intmap. An analysis associating some data with each program label is just a function that computes an intmap, given a program; that analysis will never be invalidated by subsequent transformations, because the program to which it applies will never be mutated.
This pervasive feeling of calm allows me to tackle problems that I wouldn't have otherwise been able to fit into my head. One example is the novel online CSE pass; one day I'll either wrap that up as a paper or just capitulate and blog it instead.
Flow analysis
A[k] = meet(A[p] for p in preds[k])
- kill[k] + gen[k]
Compute available values at labels:
- A:
intmap<label,intset<val>>
- meet:
intmap-intersect<intset-intersect>
- -, +:
intset-subtract, intset-union
- kill[k]: values invalidated by cont because of side effects
- gen[k]: values defined at k
But to keep it concrete, let's take the example of flow analysis. For example, you might want to compute "available values" at a given label: these are the values that are candidates for common subexpression elimination. For example if a term is dominated by a car x primcall whose value is bound to v, and there is no path from the definition of V to a subsequent car x primcall, we can replace that second duplicate operation with $values (v) instead.
There is a standard solution for this problem, which is to solve the flow equation above. I wrote about this at length ages ago, but looking back on it, the thing that pleases me is how easy it is to decompose the task of flow analysis into manageable parts, and how the types tell you exactly what you need to do. It's easy to compute an initial analysis A, easy to define your meet function when your maps and sets have built-in intersect and union operators, easy to define what addition and subtraction mean over sets, and so on.
Persistent data structures FTW
- meet:
intmap-intersect<intset-intersect>
- -, +:
intset-subtract, intset-union
Naïve: O(nconts * nvals)
Structure-sharing: O(nconts * log(nvals))
Computing an analysis isn't free, but it is manageable in cost: the structure-sharing means that meet is usually trivial (for fallthrough control flow) and the cost of + and - is proportional to the log of the problem size.
CPS soup: strengths
Relatively uniform, orthogonal
Facilitates functional transformations and analyses, lowering mental load: “I just have to write a function from foo to bar; I can do that”
Encourages global optimizations
Some kinds of bugs prevented by construction (unintended shared mutable state)
We get the SSA optimization literature
Well, we're getting to the end here, and I want to take a step back. Guile has used CPS soup as its middle-end IR for about 8 years now, enough time to appreciate its fine points while also understanding its weaknesses.
On the plus side, it has what to me is a kind of low cognitive overhead, and I say that not just because I came up with it: Guile's development team is small and not particularly well-resourced, and we can't afford complicated things. The simplicity of CPS soup works well for our development process (flawed though that process may be!).
I also like how by having every variable be potentially a phi, that any optimization that we implement will be global (i.e. not local to a basic block) by default.
Perhaps best of all, we get these benefits while also being able to use the existing SSA transformation literature. Because CPS is SSA, the lessons learned in SSA (e.g. loop peeling) apply directly.
CPS soup: weaknesses
Pointer-chasing, indirection through intmaps
Heavier than basic blocks: more control-flow edges
Names bound at continuation only; phi predecessors share a name
Over-linearizes control, relative to sea-of-nodes
Overhead of re-computation of analyses
CPS soup is not without its drawbacks, though. It's not suitable for JIT compilers, because it imposes some significant constant-factor (and sometimes algorithmic) overheads. You are always indirecting through intmaps and intsets, and these data structures involve significant pointer-chasing.
Also, there are some forms of lightweight flow analysis that can be performed naturally on a graph of basic blocks without looking too much at the contents of the blocks; for example in our available variables analysis you could run it over blocks instead of individual instructions. In these cases, basic blocks themselves are an optimization, as they can reduce the size of the problem space, with corresponding reductions in time and memory use for analyses and transformations. Of course you could overlay a basic block graph on top of CPS soup, but it's not a well-worn path.
There is a little detail that not all phi predecessor values have names, since names are bound at successors (continuations). But this is a detail; if these names are important, little $values trampolines can be inserted.
Probably the main drawback as an IR is that the graph of conts in CPS soup over-linearizes the program. There are other intermediate representations that don't encode ordering constraints where there are none; perhaps it would be useful to marry CPS soup with sea-of-nodes, at least during some transformations.
Finally, CPS soup does not encourage a style of programming where an analysis is incrementally kept up to date as a program is transformed in small ways. The result is that we end up performing much redundant computation within each individual optimization pass.
Recap
CPS soup is SSA, distilled
Labels and vars are small integers
Programs map labels to conts
Conts are the smallest labellable unit of code
Conts can have terms that continue to other conts
Compilation simplifies and lowers programs
Wasm vs VM backend: a question for another day :)
But all in all, CPS soup has been good for Guile. It's just SSA by another name, in a simpler form, with a functional flavor. Or, it's just CPS, but first-order only, without lambda.
In the near future, I am interested in seeing what a new GC will do for CPS soup; will bump-pointer allocation palliate some of the costs of pointer-chasing? We'll see. A tricky thing about CPS soup is that I don't think that anyone else has tried it in other languages, so it's hard to objectively understand its characteristics independent of Guile itself.
Finally, it would be nice to engage in the academic conversation by publishing a paper somewhere; I would like to see interesting criticism, and blog posts don't really participate in the citation graph. But in the limited time available to me, faced with the choice between hacking on something and writing a paper, it's always been hacking, so far :)
Speaking of limited time, I probably need to hit publish on this one and move on. Happy hacking to all, and until next time.
#gnu #gnuorg #opensource
