- We introduce a function:
def identifyConstantSubtrees(ir: BaseIR): Memo[Unit]
it takes in an IR and recurs over it doing the following:
- For any IRs that introduce constant bindings, use
UsesAndDefsto find the
Refs, then mark them as being constant. Then recur on children
- For all other IRs, recur on children to check if they’re constant subtrees. For most value IRs, we can say that they are constant if their children are constant. There are exceptions, like
UUID4. TableIRs and MatrixTableIrs cannot be constant.
- We have a second function:
def fixupUnrealizables(ir: BaseIR, constantSubtrees: Memo[Unit], usesAndDefs: Memo[IR], parentPointers: Memo[IR])
This recurs over the tree, stopping at each identified constant subtree and checking if it is of a realizable type. If it is not a realizable subtree, then we need to remove it from
constantSubtrees, as well as deal with the Refs it introduces. That means using
usesAndDefsto jump to the relevant Refs, removing them from memo, then using
parentPointersto walk up the IR tree, removing each IR it encounters from memo until encountering one that isn’t constant. We also need to recur on the child of the original unrealizable constant subtree.
(We may also consider filtering out any degenerate constant subtrees at this step. I.e., we shouldn’t count a single constant (like just an
Literal) as a constant subtree).
- Now we need to collect the constant subtrees to compile.
constantSubtreescontains too many subtrees, since some are children of others, so we should just walk the IR again, stopping and collecting each subtree we encounter. We have to handle lets in a special way as we do this. Define a function:
def collectConstantIRs(ir: BaseIR, constantSubtrees: Memo[Unit]): (IndexedSeq[(String, IR)], IndexedSeq[IR])
Whenever we see a
Let that isn’t a constant subtree, we need to check if the value it binds is a constant subtree. If the value is a constant subtree, we need to add a pair of the name being bound and the constantIR it binds to an
IndexedSeq[(String, IR)] (or a mutable list type if that’s easier). When we encounter a constant subtree, we add it to an
IndexedSeq[IR]. We return both of these things.
We turn the
IndexedSeq[(String, IR)]into a series of let bindings. In the body of the innermost let, we use
MakeTupleto create a tuple of all of constant subtrees. Then we call
CompileAndEvaluateon this IR we’ve generated.
One last walk through the IR, reconstructing it as we go this time. Now when we encounter a constant subtree, we figure out which position in the tuple it matches up with and replace constant subtree with a
Literalor a primitive IR wrapping the value from the tuple.