20
$\begingroup$

GHC is an optimizing Haskell compiler. Since Haskell is lazy and mutation is rare, control flow and data flow are often very closely aligned. Therefore, it is often most useful to think about evaluation of Haskell programs in terms of graph reduction. GHC implements an abstract graph reduction machine known as the spineless, tagless G-machine, or STG.

One of the key insights of the original work on STG (which, incidentally, predates Haskell) is that the graphs reduced by this machine can be thought of as a small, functional language, where sharing in the graph structure is denoted using let. What’s more, this language can be used directly as the intermediate representation of an optimizing compiler. Since lazy evaluation is entirely demand-driven, an STG program is, in a very real sense, a dataflow graph used directly as IR.

Much more recently, RVSDG (pdf) was published, which sounds in some ways remarkably similar to STG:

We present the Regionalized Value State Dependence Graph (RVSDG) IR for optimizing compilers. The RVSDG is a data flow centric IR where nodes represent computations, edges represent computational dependencies, and regions capture the hierarchical structure of programs. It represents programs in demand-dependence form, implicitly supports structured control flow, and models entire programs within a single IR.

The authors choose to illustrate terms in their IR diagrammatically rather than as a small programming language, but it seems quite similar to STG:

  • Like STG, terms in RVSDG are nested graphs that encode data dependence.

  • RVSDG’s γ-nodes encode multi-way conditional branching, which corresponds directly to STG’s case expressions.

  • RVSDG’s θ-nodes encode do-while loops, which correspond directly to tail-recursive functions in STG.

  • RVSDG’s λ-nodes encode functions, just as STG’s lambda expressions do.

  • RVSDG’s δ-nodes represent references to global variables, which in STG are represented directly as references to global variables.

  • RVSDG’s φ-nodes encode mutually-recursive environments, which correspond directly to STG’s letrec expressions.

  • RVSDG’s ω-nodes represent compilation units, which in STG are called modules.

  • RVSDG uses artificial “state edges” to encode ordering invariants in terms of data flow, and STG does exactly the same thing using special State# pseudo-values.

The correspondence is, frankly, a little astonishing. Are these two models truly completely equivalent? Is RVSDG “merely” independent reinvention of STG? Or does something significant about them differ that I am overlooking?

Also, a little over five years ago, GHC’s implementation of STG was extended with join points, which are like phi nodes in SSA. Do these correspond to anything in RVSDG?

$\endgroup$
6
  • 1
    $\begingroup$ Quite possible that the authors are entirely oblivious to STG and the entire body of research on functional languages implementation, which is pretty evident from the list of citations in the paper. I'm not surprised, these two sub-cultures always had remarkably little overlap for some historical reasons. Every time I mention, say, CPS-SSA equivalence to anyone from either side of this divide, they seem genuinely baffled as if it's the first time they hear about the other side existence. $\endgroup$
    – SK-logic
    Commented Jul 1, 2023 at 8:54
  • 2
    $\begingroup$ @SK-logic To be clear, I am assuming the authors are oblivious to STG—and I’m certainly not accusing them of anything! Independent reinvention happens all the time. I’m just curious whether there are meaningful differences between the designs that I’m overlooking. $\endgroup$
    – Alexis King
    Commented Jul 1, 2023 at 19:13
  • $\begingroup$ @AlexisKing it's the only possible explanation I can see - otherwise similarities are sufficient to at least warrant a citation, so the lack of citations is consistent with the assumption that the authors belong to the academic sub-culture that was not exposed to any of the FP-related work. It works the other way too - a lot of people of the FP tribe are unaware of some of the important and influential publications on the classical compiler theory side. $\endgroup$
    – SK-logic
    Commented Jul 1, 2023 at 19:49
  • $\begingroup$ I guess there are some differences. For example, STG's case expressions are the only way to peer inside a data constructor. STG's lambdas also have separate environment and arguments, which are slightly different from traditional CPS-like IRs... $\endgroup$
    – Pseudonym
    Commented Jul 5, 2023 at 4:36
  • 2
    $\begingroup$ Is one difference between STG and RVSDGs that STG has scopes and named bindings? I'm new to STG, but it seems like in STG you can refer to variables outside of the scope of a let or letrec. While in RVSDG everything has to be passed through explicitly, so there are no names of variables (and thus no alpha-equivalence problems) $\endgroup$ Commented Apr 12 at 23:18

1 Answer 1

2
$\begingroup$

The RVSDG is fairly similar to the STG, but not identical by any means.

Alright, so I've done a bit of research into the two, based off the original papers for both the STG and the RVSDG, and all your noted equivalences hold. State# and the RVSDG's state edges are indeed weirdly similar, seeing as they serve basically the same purpose despite being in such different environments.

Join points sort of correspond to gamma nodes in the RVSDG, but they're not really exactly SSA phis. (Weirdly enough, the RVSDG uses "phi" to represent something completely different. I'm not sure I like their naming conventions.)

Some of the differences:

Differences because of laziness:

  • The STG has "update" nodes on every lambda, which dictate specifics of evaluation - whether a given closure needs to be updated or not on reduction. The RVSDG doesn't need this.
  • The STG features explicit forcing of terms via case, which is also not needed in the RVSDG.

Differences caused by general operational focus:

  • The STG is much more runtime-focused (while still working perfectly fine as an IR, to be clear), as opposed to the RVSDG, which is only focused on being a good IR.

  • As part of this, (and as noted), the STG features let, which is the only method of heap allocation for closures and similar. The RVSDG has no such structure, as it's not intended for runtime usage. (In fact, the RVSDG paper doesn't even contain the word "heap")

  • The RVSDG has a more imperative-focused design, obviously, and the optimisations that are "evident" by its structure follow as such. While things like theta-nodes (do-while) do correspond to tail recursion, they exist on their own in a way that would require more effort in something like the STG. Likewise for the STG and its purely-functional-focused design.

  • The RVSDG's general structure is more complex than the STG (though not by much), as it needs to permit a larger number of imperative structures.

    • The RVSDG doesn't actually provide a "grammar" for their language, so it's slightly hard to provide an objective comparison, but it has ~6 main "essential" constructs (gamma, theta, lambda, delta, phi, omega), and the way they interact is somewhat complex. (Perhaps this is also slight observation bias, as the diagrammatic presentation does make it seem more complex).
    • In opposition, the STG has somewhere between 3 and 5 constructs (case, letrec, lambda, then arguably fail & default), and the interactions between these are more simple.
    • Defining "essential" here to mean "things that are described as the "core" of the given language.
    • I've omitted things like function application, datastructures, etc from this comparison because both have them, and they're close enough to the same basic concept as to be boring.
  • The STG emerges basically "naturally" from GHC's Core language, whereas the RVSDG requires some effort put in to translate some languages to it. The paper notes unstructured control flow as being untranslatable.

As part of the above:

I think that there is that there is a distinct language that emerges "naturally" from the STG (in the sense any real attempt interpreting this language would give you a version of at least a graph machine, the ST portion of the STG really just being optimizations), but there's no real distinct language that emerges from the RVSDG. Any attempt to interpret such a language could really just look like any other small imperative language, and could be implemented as such.

Whether one sees this as distinctness is up to personal taste, but I see it as such.


(please feel free to edit if anyone notices more differences or similarities that might be useful)

$\endgroup$
3
  • 1
    $\begingroup$ This is a nice answer—thank you! I’m a little curious what you mean by “RVSDG has a much more imperative-focused design”. I agree that RVSDG was obviously designed in the context of imperative languages, but I’m not sure what aspects of its design you feel reflect that context, relative to STG. Similarly, I’m curious what you mean when you say that “RVSDG’s general structure is more complex than STG”—in what ways do you mean? $\endgroup$
    – Alexis King
    Commented May 22 at 14:11
  • $\begingroup$ @AlexisKing Thanks! For the former, the clearest signallers to me are the absence of any higher order representational functionality (you could of course perform a lowering before lowering to the RVSDG, but still), and general node design (giving "obvious" representation to structures commonly seen in imperative languages, like do-while loops and linear structured control flow like switch). To be honest though, "much" was probably overselling it a bit, and I'll change it. As for your second point, I'll edit the answer to quantify that a bit more. $\endgroup$
    – blueberry
    Commented May 22 at 21:46
  • $\begingroup$ Now that I look again, you probably could represent higher order functionality in the RVSDG? I take the fact that they don't seem to consider this possibility at all as further evidence that it's not really intended for functional language, though. $\endgroup$
    – blueberry
    Commented May 22 at 22:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .