Value State Dependence Graph

The Value State Dependence Graph (VSDG) is a high-level intermediate representation for software procedures. It represents values as having an operation plus inputs plus a virtual "state" input used to ensure the ordering of side-effects is explicitly maintained. It makes many optimizations simple, but is very difficult to convert into linear code efficiently.

Optimizing Compilation with the VSDG - by Alan C. Lawrence

This technical report describes in detail the VSDG, the PDG (program dependence graph), and CFG (control-flow graph) program representations. It describes a way to generate a PDG from a VSDG, and a CFG from a PDG, resulting in a linear program from a VSDG.

http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-705.pdf

Compared to CFG (control-flow graph)

• In the CFG, the procedure is broken into basic blocks, whereas in VSDG the entire procedure can be one big graph. This makes code motion simpler in VSDG as you just have to adjust the dependencies.
• In the CFG, state dependencies are explicit, so it's hard to know whether it is safe to re-order instructions inside a basic block, or basic blocks within a procedure. In VSDG the state dependency is explicit so there is more freedom to reorder code.