14
$\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
  • $\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
    Jul 1, 2023 at 8:54
  • $\begingroup$ @SK-logic good to know, but as someone who watches both worlds, I missed the similarities. Like Alexis, I would like to know. Is there a way to put a bounty on a question I didn't ask? $\endgroup$ Jul 1, 2023 at 12:18
  • $\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
    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
    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
    Jul 5, 2023 at 4:36

0

You must log in to answer this question.