---
# System prepended metadata

title: RVSDG Notes
tags: [numba_design_notes]

---

# RVSDG Notes

RVSDG: Regionailized Value-State Dependence Graph

Why?

- Regions provide hierarchical structure that maps nicely to MLIR's multi-level dialect concepts
- Value-State Dependence Graph (VSDG) allows us to view imperative programs in the lens of pure-functional dataflow graph
    
    
    
## A Pure View of Imperative Programs

Imperative: `putChar(c)`
Functional: `putChar(io, c) -> io` where `io` is a symbolic encoding for the I/O states.

Monad (haskell like syntax):

```haskell
do
    putChar("h")
    putChar("i")
```

`do` block implicitly stuff `io` through all calls in it. This just looks like imperative programs.

NonMonad equivalent but still pure:

```
io2 = putChar(io, "h")
io3 = putChar(io2, "i")
```

`io` is tracked explicitly. This is essentially how RVSDG handle the "world" state (or global effects/side-effects).

In the RVSDG frontend, the "world" is tracked via the value-state named `env`, which is itself just a symbolic representation that materializes to nothing in the imperative LLVM IR or machine code.