# MIR-based Compiler Pipeline Overview
This document serves as an outline in which to collect my thoughts on the next
generation of `mice`'s interpreter and as an introduction to those who are unfamiliar
with the project.
## Previous Design and Justification
Before I get into the new design, let's take a moment to review the one currently in use.
We currently parse dice expressions into an arena allocated AST, modeled like this:
```rust
enum Term {
Integer(i64),
Add(Id<Term>, Id<Term>),
Subtract(Id<Term>, Id<Term>),
// ...
}
```
and then take two paths to evaluating it, depending on performance requirements.
If we don't require running an expression to be very fast, but do require knowledge of
all intermediate results for output formatting purposes (e.g., the `!roll` command in `mbot`),
the AST is fed directly into a recursive tree walking interpreter.
That tree walking interpreter produces an additional tree as output, composed of the results
of evaluating each AST node. That output tree is then used in combination with the input AST
to produce textual formatted output.
If we *do* require running an expression to be very fast, but don't require knowledge of
intermediate results for output formatting purposes (e.g., the `!plot` command in `mbot`),
the AST is compiled to a simple bytecode for a stack machine, which is then interpreted
by a straightforward linear scan.
We do not have a middle ground, where high speed is require *and* intermediate results
must be saved, but that is not addressed in particular by the new design.
There are two problems with the current design that are addressed by the new one:
- Adding a new feature to the language requires implementing it twice- once for each interpreter.
- The AST walking interpreter is going to become difficult to continue maintaining as soon as
we add marginally more complicated features to the language, like exploding dice or custom functions.
## New Design
In the new design, we use the same AST as before, but lower it to a new IR (MIR).
### MIR
MIR is a nested graph data structure modeled after the
[Regionalized Value State Dependence Graph](https://arxiv.org/abs/1912.05036).
(Feel free to skim that paper, or not. I'll include a summary of the important stuff down below.)
We define a simple node type for each primitive operation we want to support, and
utilize the structural nodes outlined in the RVSDG paper for expressing any necessary control flow.
(At least for now. It is plausible that we will design a few of our own structural nodes at some point.)
These are the simple nodes corresponding to the operations we already support:
- Integer
- Roll
- BinaryOp
- Add
- Subtract
- Filter
- KeepHigh
We take the opportunity to reify type coercions that were implicit in the AST in MIR,
so the summation of sets of dice upon being used in integer arithmetic is made explicit.
This allows the implementation of particular operators to be monomorphic- the interpreter
does not need to check the operand types and change its behavior depending on them,
which simplifies stuff a lot and reduces code duplication some more.
Doing so introduces the following extra node type:
- Coerce
- FromOutputToInt
It is not unlikely that we will rename this one in the future.
In the meantime, we also fill out the obvious gap in set filters, with these three new operations:
- Filter
- KeepLow
- DropHigh
- DropLow
#### Intermediate Results
To produce formatted output, we still keep a tree of intermediate results. But, because there is no
ironclad association between the structure of the MIR and the structure of the input AST, we give MIR
programs the ability to control that tree building directly. This requires adding a few nodes,
- FmtNode
- MakeList
- PushToList
- Record
- Annotate
- RegionArgument
and allows us to decouple the specifics of scraping data for formatting purposes from the backend(s).
#### Validation and Evaluation Fuel
In actual usage, we do not actually evaluate arbitrary dice expressions given to us by untrusted users.
We are required to place bounds on the expressions we accept, and reject expressions that do not meet those
bounds.
In the old design, we took advantage of how every construct in the input language takes a precisely
known number of evaluation steps and allocates a precisely known amount of memory.
We just computed these quantities before running a given program, and rejected it if it was too expensive.
This strategy is no longer precisely tenable, as we wish to enable the evaluation of
programs whose termination is probabilistic.
And so, we adopt a new strategy. We introduce a notion of "evaluation fuel", which is a runtime tracked
quantity that describes how much longer a dice program is allowed to run. For constructs whose execution
is not known to terminate in a particular constant amount of time, we insert machinery that ensures
they will run no longer than some acceptable bound.
For this purpose, we introduce the `UseFuel` MIR node type.
The `UseFuel` MIR node type encodes a weakly stateful action. That is, it accesses and mutates a potentially
global state, but the ordering of `UseFuel` nodes with respect to each other does not matter.
A `UseFuel` instruction takes an argument and returns it as is, but aborts the program if there
is not enough available evaluation fuel.
A future direction we may head in is taking a quantity of evaluation fuel as an argument
and passing it along explicitly and using it as regular data, or varying the amount of fuel used
based on information available at runtime, like the number of dice a particular loop iteration is rolling.
For now, I am simply taking the lowest effort solution to get something working.
#### Closures
MIR does not have first class functions, and calls are required to be resolvable at compile time.
But, we can simulate closures for many cases by use of a new node kind: `PartialApply`.
A closure is composed of its captures and a regular function, after all.
So, we can simulate a closure by defining a function that takes its captures as arguments,
and using partial application to give them to it early, so long as we can use partially applied
functions in all places we can use regular functions.
### Optimizations
Optimizations for dice expressions are not necessary yet, but will become necessary once
we permit user defined functions and operators. We do not want users to need to contort to
find the best performance.
#### Misp
An internal Lisp language we'll be using to express MIR, partly because I had a Lisp parser
that could be used for this sitting around in an unpublished project already.
This language will have similar rules to the eventual user facing language, so we should be able to
figure out what optimizations will be relevant by working around it.
#### Constant Propagation (TODO)
#### Function Inlining (TODO)
#### Reference Elision (TODO)
#### Loop Fusion (NOT YET, blocked on #Devectorization)
#### Intermediate Result Elision (NOT YET, blocked on #Devectorization)
#### Devectorization (TODO)
There are a few vectorized instructions in MIR that don't lend themselves very well to optimization,
which I added for two reasons: First, the current backend we're generating code for is an interpreter,
which does best when we keep as much of the work for a loop in native code as we can.
Second, it was more convenient for writing out already extremely verbose MIR graphs using `petgraph`
methods directly.
That second reason is now minimized with the introduction of Misp.
That first reason is more challenging, and will ultimately probably prevent this
from being viable until we perform JIT compilation to machine code.
#### Loop Invariant Code Motion (TODO)
#### Fuel Lifting and Coalescing (TODO)
This optimization will likely be necessary for the introduction of a user facing scripting language,
as the lowering for that language will likely insert a `UseFuel` node for every term.
This might also be useful for unifying our cost analysis logic, as we could simply inject `UseFuel`
nodes for every term and perform the checks for statically known uses prior to running them,
so long as the process of lowering itself is of negligible cost.
### Codegen
# Appendix
## RVSDG
TODO: write a summary of RVSDG