Good evening, hackers. Today's missive is more of a massive, in thesense that it's another presentation transcript-alike; these things alwaystranslate to many vertical pixels.

In my defense, I hardly ever give apresentation twice, so not only do I miss out on the usualper-presentation cost amortization and on the incremental improvementsof repetition, the more dire error is that whatever message I might havecan only ever reach a subset of those that it might interest; here atleast I can be more or less sure that if the presentation would interestsomeone, that they will find it.

So for the time being I will try toshare presentations here, in the spirit of, well, why the hell not.

Last week I gave a training talk to SpritelyInstitute collaborators on the intermediaterepresentation used by Guile's compiler.

An intermediate representation (IR) (or intermediate language, IL)is just another way to express a computer program. Specifically it'sthe kind of language that is appropriate for the middle-end of acompiler, and by "appropriate" I meant that an IR serves a purpose:there has to be a straightforward transformation to the IR fromhigh-level abstract syntax trees (ASTs) from the front-end, and therehas to be a straightforward translation from IR to machine code.

There are also usually a set of necessary source-to-sourcetransformations on IR to "lower" it, meaning to make it closer to theback-end than to the front-end. There are usually a set of optionaltransformations to the IR to make the program run faster or allocateless memory or be more simple: these are the optimizations.

"CPS soup" is Guile's IR. This talk presents the essentials of CPS soupin the context of more traditional IRs.

(+ 1 (if x 42 69))

 cmpi $x, #f je L1 movi $t, 42 j L2 L1: movi $t, 69L2: addi $t, 1

Before we dive in, consider what we might call the dynamic range of anintermediate representation: we start with what is usually an algebraicformulation of a program and we need to get down to a specific sequenceof instructions operating on registers (unlimited in number, at thisstage; allocating to a fixed set of registers is a back-end concern),with explicit control flow between them. What kind of a language mightbe good for this? Let's attempt to answer the question by looking intowhat the standard solutions are for this problem domain.

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 BB2BB1: t = const 42; goto BB3BB2: t = const 69; goto BB3BB3: t2 = addi t, 1; ret t2

Of course in the early days, there was no intermediate language;compilers translated ASTs directly to machine code. It's been a whilesince I dove into all this but the milestone I have in my head is thatit's the 70s when compiler middle-ends come into their own right, withFran Allen's work on flow analysis and optimization.

In those days the intermediate representation for a compiler was a graphof basic blocks, but unlike today the paradigm was assignment tolocations rather than definition of values. By that I mean that in ourexample program, we get t assigned to in two places (BB1 and BB2); theactual definition of t is implicit, as a storage location, and ourgraph consists of assignments to the set of storage locations in theprogram.

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 BB2BB1: v0 := const 42; goto BB3BB2: v1 := const 69; goto BB3BB3: v2 := φ(v0,v1); v3:=addi t,1; ret v3

These days we still live in Fran Allen's world, but with a twist: we nolonger model programs as graphs of assignments, but rather graphs ofdefinitions. The introduction in the mid-80s of so-called "staticsingle-assignment" (SSA) form graphs mean that instead of having twoassignments to t, we would define two different values v0 and v1.Then later instead of reading the value of the storage locationassociated with t, we define v2 to be either v0 or v1: theformer if we reach the use of t in BB3 from BB1, the latter if we arecoming from BB2.

If you think on the machine level, in terms of what the resultingmachine code will be, this either function isn't a real operation;probably register allocation will put v0, v1, and v2 in the sameplace, say $rax. The function linking the definition of v2 to theinputs v0 and v1 is purely notational; in a way, you could say thatit is phony, or not real. But when the creators of SSA went to submitthis notation for publication they knew that they would need somethingthat sounded more rigorous than "phony function", so they instead called it a "phi" (φ)function. Really.

graph := array<block>block := tuple<preds, succs, args, insts>

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 IRproblem. There have been some refinements, though. I learned of one ofthem from MLton; I don't know if they were firstbut they had the idea of interpreting phi variables as arguments tobasic blocks. In this formulation, you don't have explicit phiinstructions; rather the "v2 is either v1 or v0" property isexpressed by v2 being a parameter of a block which is "called" witheither v0 or v1 as an argument. It's the same semantics, but aninteresting notational change.

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 somenumber of instructions that can define values or have side effects butwhich otherwise exhibit fall-through control flow, followed by a singleinstruction that transfers control to another block. We might as wellstore that control instruction separately; this would let us easily knowhow a block ends, and in the case of phi block arguments, easily saywhat values are the inputs of a phi variable. So let's do that.

graph := array<block>block := tuple<args, insts, control>

At this point we notice that we are repeating ourselves; the successorsof a block can be computed directly from the block's terminal controlinstruction. Let's drop those as a distinct part of a block, becausewhen you transform a program it's unpleasant to have to needlesslyupdate something in two places.

While we're doing that, we note that the predecessors array is alsoredundant, as it can be computed from the graph of block successors.Here we start to wonder: am I simpliying or am I removing something thatis fundamental to the algorithmic complexity of the various graphtransformations that I need to do? We press on, though, hoping we willget somewhere interesting.

Recall that the context for this meander is Guile's compiler, which is written in Scheme. Scheme doesn't have expandable arrays built-in. Youcan build them, of course, but it is annoying. Also, in Scheme-land,functions with side-effects are conventionally suffixed with anexclamation mark; after too many of them, both the writer and thereader get fatigued. I know it's a silly argument but it's one of thethings that made me grumpy about basic blocks.

If you permit me to continue with this introspection, I find there is anuneasy relationship between instructions and locations in an IR that isstructured around basic blocks. Do instructions live in afunction-level array and a basic block is an array of instructionindices? How do you get from instruction to basic block? How would youhoist an instruction to another basic block, might you need toreallocate the block itself?

And when you go to transform a graph of blocks... well how do you dothat? Is it in-place? That would be efficient; but what if you need torefer to the original program during the transformation? Might you riskreading a stale graph?

It seems to me that there are too many concepts, that in the same waythat SSA itself moved away from assignment to a more declarativelanguage, that perhaps there is something else here that might be moreappropriate to the task of a middle-end.

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 declarethat basic blocks themselves are redundant. Instead of containing anarray of instructions with fallthrough control-flow, why not just makeevery instruction a control instruction? (Yes, there are argumentsagainst 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 whichvalues are named in a MLton-style compiler: instead of distinguishingbetween basic block arguments and values defined within a basic block,we might as well make all names into basic block arguments.

graph := map<label, block>

In the traditional SSA CFG IR, a graph transformation would often nottouch the structure of the graph of blocks. But now having given eachinstruction its own basic block, we find that transformations of theprogram necessarily change the graph. Consider an instruction that weelide; before, we would just remove it from its basic block, or replaceit with a no-op. Now, we have to find its predecessor(s), and forwardthem to the instruction's successor. It would be useful to have a morecapable data structure to represent this graph. We might as well keeplabels as being small integers, but allow for sparse maps and growth byusing an integer-specialized map instead of an array.

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 ...

This is exactly what CPS soup is! We came at it "from below", so tospeak; instead of the heady fumes of the lambda calculus, we get herefrom down-to-earth basic blocks. (If you prefer the other way around,you might enjoy this article from a long timeago.)The remainder of this presentation goes deeper into what it is like towork with CPS soup in practice.

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

Before moving on, though, we should discuss what it means in anSSA-style IR that variables are defined rather than assigned. If youconsider variables as locations to which values can be assigned andwhich initially hold garbage, you can read them at any point in yourprogram. You might get garbage, though, if the variable wasn't assignedsomething 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 neverhas garbage; the single definition always precedes any uses of thevariable. That is to say that all paths from the function entry to theuse of a variable must pass through the variable's definition, or, inthe jargon, that definitions dominate uses. This is an invariant ofan SSA-style IR, that all variable uses be dominated by their associateddefinition.

You can flip the question around to ask what variables are available foruse at a given program point, which might be read equivalently as whichvariables are in scope; the answer is, all definitions from all programpoints that dominate the use site. The "CPS" in "CPS soup" stands forcontinuation-passing style, a dialect of the lambda calculus, whichhas also has a history of use as a compiler intermediate representation.But it turns out that if we use the lambda calculus in its conventionalform, we end up needing to maintain a lexical scope nesting at the sametime that we maintain the control-flow graph, and the lexical scope treecan fail to reflect the dominator tree. I go into this topic in moredetail in an oldarticle, and if itinterests you, please do go deep.

cont := $kargs names vars term | ...term := $continue k src expr | ...expr := $const C | $primcall ’add #f (a b) | ...

Anyway! In Guile, the concrete form that CPS soup takes is that aprogram is an intmap of label to cont. A cont is the smallestlabellable unit of code. You can call them blocks if that makes youfeel better. One kind of cont, $kargs, binds incoming values tovariables. It has a list of variables, vars, and also has anassociated list of human-readable names, names, for debuggingpurposes.

A $kargs contains a term, which is like a control instruction. Onekind of term is $continue, which passes control to a continuation k.Using our earlier language, this is just goto *k*, with values, as inMLton. (The src is a source location for the term.) The values comefrom the term's expr, of which there are a dozen kinds or so, forexample $const which passes a literal constant, or $primcall, whichinvokes some kind of primitive operation, which above is add. Theprimcall may have an immediate operand, in this case #f, and somevariables that it uses, in this case a and b. The number and typeof the produced values is a property of the primcall; some are just foreffect, some produce one value, some more.

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

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 truecontinuation kt depending on the result of performing op on thevariables args, with immediate operand param. In our runningexample, 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 inthe (language cps)module.

There is also $switch, which takes an unboxed unsigned integer argand 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 newcontinuation delimiter associated with the var tag; if code aborts totag before the prompt exits via an unwind primcall, the stack willbe unwound and control passed to the handler continuation kh. Ifescape? is true, the continuation is escape-only and aborting to theprompt doesn't need to capture the suspended continuation.

Finally there is $throw, which doesn't continue at all, because itcauses a non-resumable exception to be thrown. And that's it; it's justa handful of kinds of term, determined by the different shapes ofcontrol-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 $valuesexpression corresponds to passing an input to a phi variable, though$kargs vars can get their definitions from any expression thatproduces the right number of values.

When a $continue term continues to a $kargs with a $const 42expression, there are a number of invariants that the compiler canensure: that the $kargs continuation is always passed the expectednumber of values, that the vars that it binds can be allocated tospecific locations (e.g. registers), and that because all predecessorsof the $kargs are known, that those predecessors can place theirvalues directly into the variable's storage locations. Effectively, thecompiler determines a custom calling convention between each $kargsand its predecessors.

Consider the $call expression, though; in general you don't know whatthe callee will do to produce its values. You don't even generally knowthat it will produce the right number of values. Therefore $callcan't (in general) continue to $kargs; instead it continues to$kreceive, which expects the return values in well-known places. $kreceive willcheck that it is getting the right number of values and then continue toa $kargs, shuffling those values into place. A standard callingconvention defines how functions return values to callers.

cont := $kfun src meta self ktail kentry | $kclause arity kbody kalternate | $kargs names syms term | $kreceive arity kbody | $ktail

Of course, a $call expression could be a tail-call, in which case itwould continue instead to $ktail, indicating an exit from thefirst-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; inGuile we start functions with $kfun, which has some metadata attached,and then proceed to $kclause which bridges the boundary between thestandard calling convention and the specialized graph of $kargscontinuations. (Many details of this could be tweaked, for example thatthe case-lambda dispatch built-in to $kclause could instead dispatchto distinct functions instead of to different places in the samefunction; historical accidents abound.)

As a detail, if a function is well-known, in that all its callers areknown, then we can lighten the calling convention, moving theargument-count check to callees. In that case $kfun continuesdirectly to $kargs. Similarly for return values, optimizations canmake $call continue to $kargs, though there is still somevalue-shuffling to do.

CPS soup is the bridge between parsed Scheme and machine code. Itstarts out quite high-level, notably allowing for nested scope, in whichexpressions can directly refer to free variables. Variables are smallintegers, and for high-level CPS, variable indices have to be uniqueacross all functions in a program. CPS gets lowered viaclosureconversion,which chooses specific representations for each closure that remainsafter optimization. After closure conversion, all variable access islocal to the function; free variables are accessed via explicit loadsfrom a function's closure.

Because of the broad remit of CPS, the language itself has two dialects,high and low. The high level dialect has cross-function variablereferences, first-class abstract functions (whose representation hasn'tbeen chosen), and recursive function binding. The low-level dialect hasonly specific ways to refer to functions: labels and specific closurerepresentations. It also includes calls to function labels instead ofjust function values. But these are minor variations; some optimizationand transformation passes can work on either dialect.

I mentioned that programs were intmaps, and specifically in Guile theyare Clojure/Bagwell-style persistent functional data structures. Byfunctional I mean that intmaps (and intsets) are values that can't bemutated in place (though we do have the transientoptimization).

I find that immutability has the effect of deploying a sense of calm tothe compiler hacker -- I don't need to worry about data structureschanging out from under me; instead I just structure all thetransformations that you need to do as functions. An optimization isjust a function that takes an intmap and produces another intmap. Ananalysis associating some data with each program label is just afunction that computes an intmap, given a program; that analysis willnever be invalidated by subsequent transformations, because the programto which it applies will never be mutated.

This pervasive feeling of calm allows me to tackle problems that Iwouldn't have otherwise been able to fit into my head. One example isthe novel online CSEpass; oneday I'll either wrap that up as a paper or just capitulate and blog itinstead.

A[k] = meet(A[p] for p in preds[k]) - kill[k] + gen[k]

But to keep it concrete, let's take the example of flow analysis. Forexample, you might want to compute "available values" at a given label:these are the values that are candidates for common subexpressionelimination. For example if a term is dominated by a car x primcallwhose value is bound to v, and there is no path from the definition ofV to a subsequent car x primcall, we can replace that second duplicateoperation with $values (v) instead.

There is a standard solution for this problem, which is to solve theflow equation above. I wrote about this at length agesago,but looking back on it, the thing that pleases me is how easy it is todecompose the task of flow analysis into manageable parts, and how thetypes tell you exactly what you need to do. It's easy to compute aninitial analysis A, easy to define your meet function when your maps andsets have built-in intersect and union operators, easy to define whataddition and subtraction mean over sets, and so on.

Computing an analysis isn't free, but it is manageable in cost: thestructure-sharing means that meet is usually trivial (for fallthroughcontrol flow) and the cost of + and - is proportional to the log ofthe problem size.

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 itsweaknesses.

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 developmentteam is small and not particularly well-resourced, and we can't affordcomplicated things. The simplicity of CPS soup works well for ourdevelopment process (flawed though that process may be!).

I also like how by having every variable be potentially a phi, that anyoptimization that we implement will be global (i.e. not local to a basicblock) by default.

Perhaps best of all, we get these benefits while also being able to usethe existing SSA transformation literature. Because CPS is SSA, thelessons learned in SSA (e.g. loop peeling) apply directly.

CPS soup is not without its drawbacks, though. It's not suitable forJIT compilers, because it imposes some significant constant-factor (andsometimes algorithmic) overheads. You are always indirecting throughintmaps and intsets, and these data structures involve significantpointer-chasing.

Also, there are some forms of lightweight flow analysis that can beperformed naturally on a graph of basic blocks without looking too muchat the contents of the blocks; for example in our available variablesanalysis you could run it over blocks instead of individualinstructions. In these cases, basic blocks themselves are anoptimization, as they can reduce the size of the problem space, withcorresponding reductions in time and memory use for analyses andtransformations. Of course you could overlay a basic block graph on topof 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 adetail; if these names are important, little $values trampolines canbe inserted.

Probably the main drawback as an IR is that the graph of conts in CPSsoup over-linearizes the program. There are other intermediaterepresentations thatdon't encode ordering constraints where there are none; perhaps it wouldbe useful to marry CPS soup with sea-of-nodes, at least during sometransformations.

Finally, CPS soup does not encourage a style of programming where ananalysis is incrementally kept up to date as a program is transformed insmall ways. The result is that we end up performing much redundantcomputation within each individual optimization pass.

But all in all, CPS soup has been good for Guile. It's just SSA byanother name, in a simpler form, with a functional flavor. Or, it'sjust CPS, but first-order only, without lambda.

In the near future, I am interested in seeing what a newGCwill do for CPS soup; will bump-pointer allocation palliate some of thecosts of pointer-chasing? We'll see. A tricky thing about CPS soup isthat I don't think that anyone else has tried it in other languages, soit's hard to objectively understand its characteristics independent ofGuile itself.

Finally, it would be nice to engage in the academic conversation bypublishing a paper somewhere; I would like to see interesting criticism,and blog posts don't really participate in the citation graph. But inthe limited time available tome, faced withthe choice between hacking on something and writing a paper, it's alwaysbeen hacking, so far :)

Speaking of limited time, I probably need to hit publish on this one andmove on. Happy hacking to all, and until next time.