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.
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
RVSDG’s θ-nodes encode
whileloops, 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
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
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?