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

Last updated: Dec 23 2024 at 12:05 UTC