wasmtime
wasmtime copied to clipboard
cranelift: Use `DominatorTreePreorder` in more places
Feature
We have two interfaces in Cranelift for navigating dominator trees, both defined in the cranelift_codegen::dominator_tree
module: DominatorTree
and DominatorTreePreorder
. But we weren't using the latter outside of tests after #3434 landed in 2021, until I switched the egraph pass over to using it in #7948 today.
- We should audit all uses of
DominatorTree
to see if they would be better served by usingDominatorTreePreorder
instead. - If we end up using
DominatorTreePreorder
in more places than just the egraph pass, then we should compute it once and share it. - If it turns out that we always need a
DominatorTreePreorder
when compiling any function, then we should fold the two types into one and always compute the preorder when we're computing the dominator tree.
Benefit
These two interfaces both provide a method named dominates
which checks whether one basic block dominates another. However, DominatorTree
does this in time proportional to the length of the path from one block to the other within the dominator tree. Thanks to a linear-time preprocessing step performed once, DominatorTreePreorder
can answer this question in constant time.
So if we're using the DominatorTree::dominates
method anywhere that's performance-critical, switching to DominatorTreePreorder
could provide an asymptotic-complexity improvement.
On top of that, sharing a precomputed preorder across multiple uses saves time redoing the preprocessing step and also may allow us to reuse a heap allocation for the temporary storage used during that preprocessing step.
Implementation
To start with, search for all uses of DominatorTree::dominates
. For each one, see if we can just replace it with DominatorTreePreorder::dominates
.
This is easy if both arguments are Block
IDs, but either one is currently also allowed to be an instruction ID (Inst
) or a ProgramPoint
. If we're relying on that feature somewhere, it's only slightly more complicated: If two instructions are in the same block then the earlier instruction dominates the later instruction; otherwise we can go back to the easy case and compare the blocks they're in to see if one block dominates the other.
If some instances of DominatorTree
are only being used to call dominates
, then removing that structure from those instances in favor of DominatorTreePreorder
is the next step. However, some cases may also be using other methods such as cfg_postorder
or idom
, which are not available on DominatorTreePreorder
.
Alternatives
We can always leave this alone, but I think it's a good source of small changes that may give us performance improvements during compilation.
Would like to take this one
Great, please do! If you have any questions, let us know. We're happy to help!