Stream: git-wasmtime

Topic: wasmtime / issue #7954 cranelift: Use `DominatorTreePreor...

Wasmtime GitHub notifications bot (Feb 16 2024 at 23:35):

jameysharp added the good first issue label to Issue #7954.

Wasmtime GitHub notifications bot (Feb 16 2024 at 23:35):

jameysharp added the cranelift:E-easy label to Issue #7954.

Wasmtime GitHub notifications bot (Feb 16 2024 at 23:35):

jameysharp added the cranelift:mid-end label to Issue #7954.

Wasmtime GitHub notifications bot (Feb 16 2024 at 23:35):

jameysharp added the cranelift:goal:compile-time label to Issue #7954.

Wasmtime GitHub notifications bot (Feb 16 2024 at 23:35):

jameysharp opened issue #7954:

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.

1. We should audit all uses of DominatorTree to see if they would be better served by using DominatorTreePreorder instead.
2. If we end up using DominatorTreePreorder in more places than just the egraph pass, then we should compute it once and share it.
3. 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.

Wasmtime GitHub notifications bot (Feb 18 2024 at 05:35):

MuhtasimTanmoy commented on issue #7954:

Would like to take this one

Wasmtime GitHub notifications bot (Feb 20 2024 at 17:59):

jameysharp commented on issue #7954:

Great, please do! If you have any questions, let us know. We're happy to help!

Wasmtime GitHub notifications bot (Sep 01 2024 at 08:06):

badumbatish commented on issue #7954:

hi there! is this issue still on going?

Wasmtime GitHub notifications bot (Sep 06 2024 at 05:58):

badumbatish commented on issue #7954:

i'll give this one a try if nobody's doing this

Wasmtime GitHub notifications bot (Apr 25 2025 at 17:57):

adamperlin commented on issue #7954:

Hi! I'm curious if this PR is blocked?

Wasmtime GitHub notifications bot (Apr 25 2025 at 17:59):

adamperlin commented on issue #7954:

Hi! I'm curious what the status of this issue is?

Wasmtime GitHub notifications bot (Apr 25 2025 at 18:13):

cfallin commented on issue #7954:

It looks like the most recent attempt to adapt our alias analysis and related optimizations to use DominatorTreePreorder in #9213 stalled because of some failing assertions in the modified version. I suspect you'd be welcome to ping there and try pushing it further if you like!

Wasmtime GitHub notifications bot (Jun 21 2025 at 17:29):

PhantomInTheWire commented on issue #7954:

I’d like to pick this up, is anyone actively working on it? If not can someone assign this to me?

Wasmtime GitHub notifications bot (Jun 24 2025 at 15:46):

PhantomInTheWire commented on issue #7954:

@cfallin this should probably be closed now

Wasmtime GitHub notifications bot (Jun 24 2025 at 16:36):

cfallin commented on issue #7954:

@PhantomInTheWire the DominatorTree still exists and is used in several places still, so IMHO let's leave this open until the issue's stated goal (auditing remaining uses of DominatorTree and migrating all possible cases). Thank you for your efforts in pushing this forward, however!

Wasmtime GitHub notifications bot (Sep 03 2025 at 19:18):

cfallin closed issue #7954:

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.

1. We should audit all uses of DominatorTree to see if they would be better served by using DominatorTreePreorder instead.
2. If we end up using DominatorTreePreorder in more places than just the egraph pass, then we should compute it once and share it.
3. 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.

Last updated: Dec 13 2025 at 19:03 UTC