Description
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
DominatorTreeto see if they would be better served by usingDominatorTreePreorderinstead. - If we end up using
DominatorTreePreorderin 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
DominatorTreePreorderwhen 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.