Stream: git-wasmtime

Topic: wasmtime / PR #8535 converted DominatorTree to DominatorT...

Wasmtime GitHub notifications bot (May 03 2024 at 07:13):

VamshiReddy02 opened PR #8535 from VamshiReddy02:DominatorTree to bytecodealliance:main:

ref: #7954
Hey @jameysharp,
I made a few changes; this is my first time contributing to wasmtime. please let me know if there are any changes to make.

Wasmtime GitHub notifications bot (May 03 2024 at 07:13):

VamshiReddy02 requested wasmtime-compiler-reviewers for a review on PR #8535.

Wasmtime GitHub notifications bot (May 03 2024 at 07:13):

VamshiReddy02 requested abrown for a review on PR #8535.

Wasmtime GitHub notifications bot (May 03 2024 at 16:00):

abrown requested jameysharp for a review on PR #8535.

Wasmtime GitHub notifications bot (May 03 2024 at 16:00):

abrown commented on PR #8535:

@jameysharp, sounds like you have some previous context for this change?

Wasmtime GitHub notifications bot (May 03 2024 at 20:23):

jameysharp commented on PR #8535:

I do, thanks Andrew! I proposed doing this in #7954.

@VamshiReddy02, this is a good start! I'm excited that you're working on it.

I labeled this issue "easy" but there are some things that are not so easy about it, and you've started with one of the more difficult cases: Comparing two instructions, instead of two blocks. That's okay! Let's figure out how to make it work.

Instruction a dominates instruction b if either of these conditions are true:

1. a and b are in the same block, and a is not after b. Here's an example showing how to check if inst_a is not after last: https://github.com/bytecodealliance/wasmtime/blob/71800cc1a1daf01e8c3cfee09e651cf8f46ff31b/cranelift/codegen/src/dominator_tree.rs#L137
2. Or the block containing a dominates the block containing b.

You've implemented the second condition, but not the first.

The first thing I think you should do is add a new method to DominatorTreePreorder which answers the question of whether one instruction dominates another. I suggest this method should look like pub fn dominates_inst(&self, a: Inst, b: Inst, layout: &Layout) -> bool, and it needs to implement the above condition.

Then you can call dominates_inst in alias_analysis.rs. I think this should make the changes in alias_analysis.rs very small. This method will also be useful for the calls to dominates that are in cranelift/codegen/src/verifier/mod.rs. The only other calls are in cranelift/codegen/src/loop_analysis.rs, which can just compare blocks, but it's a little complicated to explain why.

I hope that helps. One more request:

Could you run cargo fmt before committing changes? That will clean up changes to whitespace and make your pull requests easier to review.

Thank you for working on this!

Wasmtime GitHub notifications bot (May 04 2024 at 15:29):

VamshiReddy02 commented on PR #8535:

Hey @jameysharp,
Thank you for the feedback. Correct me if I am wrong, First I need to add a new method called pub fn dominates_inst(&self, a: Inst, b: Inst, layout: &Layout) -> bool in the DominatorTreePreorder applying all the above conditions. For example like this:

impl DominatorTreePreorder {
 pub fn dominates_inst(&self, a: Inst, b: Inst, layout: &Layout) -> bool {
        match (layout.inst_block(a), layout.inst_block(b)) {
            (Some(block_a), Some(block_b)) => {
                if block_a == block_b {
                    layout.pp_cmp::<ProgramPoint, ProgramPoint>(a.into(), b.into()) != Ordering::Greater
                } else {
                    self.dominates(block_a, block_b)
                }
            }
            _ => false,
        }
    }
}

Then I need to call the dominates_inst in alias_analysis.rs file, for example like this:

let aliased =
                    if let Some((def_inst, value)) = self.mem_values.get(&mem_loc).cloned() {
                        trace!(
                            " -> sees known value v{} from inst{}",
                            value.index(),
                            def_inst.index()
                        );
                        if let (Some(_def_block), Some(_inst_block)) = (
                            func.layout.inst_block(def_inst),
                            func.layout.inst_block(inst),
                        ) {
                            if self.domtree.`dominates_inst(def_inst, inst, &func.layout)` {
                                trace!(
                                    " -> dominates; value equiv from v{} to v{} inserted",
                                    load_result.index(),
                                    value.index()
                                );
                                Some(value)
                            } else {
                                None
                            }
                        } else {
                            None
                        }
                    } else {
                        None
                    };

Am I going in the correct direction?

Wasmtime GitHub notifications bot (May 05 2024 at 18:33):

jameysharp commented on PR #8535:

Yes, that is the correct direction! There are a few ways to make this easier though:

1. In alias_analysis.rs, you don't need to call inst_block, because now you don't need to know the blocks there. So you can delete that if in the middle.

2. Instead of explicitly specifying the type of pp_cmp, you can let Rust figure it out. layout.pp_cmp(a, b) should work. Just don't call .into() in this case, because that gives the compiler too many choices and it gets confused.

3. When dominates_inst is called, I happen to know that the instructions should be in the Layout, so inst_block should not fail. As a result, instead of checking whether inst_block returns Some, you can use expect, like this: https://github.com/bytecodealliance/wasmtime/blob/81a89169f556d2ba8c6ddc75ae0ac471f213f1c3/cranelift/codegen/src/dominator_tree.rs#L133-L135

But yes, you are most of the way there! I look forward to seeing your updated pull request.

Some other projects expect "perfect" git commits, so I just want to let you know that we don't care about that for Wasmtime and Cranelift. As you make further changes, just commit them and push them to your DominatorTree branch. You don't need to open a new PR or use git rebase or anything. We'll "squash" your changes together into a single commit once they're ready to merge.

Wasmtime GitHub notifications bot (May 06 2024 at 10:32):

VamshiReddy02 updated PR #8535.

Wasmtime GitHub notifications bot (May 06 2024 at 10:39):

VamshiReddy02 updated PR #8535.

Wasmtime GitHub notifications bot (May 07 2024 at 05:49):

VamshiReddy02 commented on PR #8535:

Hey @jameysharp, I made some changes, let me know if any changes need to be made.

Wasmtime GitHub notifications bot (May 07 2024 at 06:34):

jameysharp submitted PR review:

This is almost exactly what I wanted! Let's just figure out why the test suite is failing in CI.

Based on the logs from CI, you should be able to reproduce the test failures by running cargo test -p wasi-common --test all. It looks like Cranelift's tests all passed, which I think means we need some more tests…

The key error messages I'm looking at say "cranelift/codegen/src/egraph/elaborate.rs:691:21: something has gone very wrong if we are elaborating effectful instructions, they should have remained in the skeleton". This is not very helpful if you don't already know how the egraph optimization pass works, but as you make changes you can at least check whether this message changes or goes away.

My guess is that what happened is that you've called DominatorTreePreorder::new but it's uninitialized and empty. I looked at the implementation of DominatorTreePreorder::dominates and I think it always returns true when it isn't initialized. This seems like a reasonable explanation for the test failures to me: if it falsely reports that things dominate each other when they actually don't, then we would "optimize" in places where we aren't actually allowed to.

The first thing I would like you to do is add this to the existing DominatorTreePreorder::dominates function, and commit this change because if other people have the same problem this will help them figure it out more quickly:

// Check that both blocks are reachable.
debug_assert!(na.pre_number != 0);
debug_assert!(nb.pre_number != 0);

When you do that, I predict that more tests will start failing at these asserts. In particular, I hope that cargo test -p cranelift-tools will have some failing tests.

If you can confirm that those asserts fail for some tests, then you can try fixing this and then make sure that the tests pass afterward. I think all you need to do is, in cranelift/codegen/src/context.rs, change compute_domtree so after it calls self.domtree.compute it also calls self.domtree_preorder.compute.

If any of that doesn't work, I'm happy to look at it more carefully.

Once the tests are all passing, I have a couple more comments below. But again, I think this is almost ready!

Wasmtime GitHub notifications bot (May 07 2024 at 06:34):

jameysharp submitted PR review:

This is almost exactly what I wanted! Let's just figure out why the test suite is failing in CI.

Based on the logs from CI, you should be able to reproduce the test failures by running cargo test -p wasi-common --test all. It looks like Cranelift's tests all passed, which I think means we need some more tests…

The key error messages I'm looking at say "cranelift/codegen/src/egraph/elaborate.rs:691:21: something has gone very wrong if we are elaborating effectful instructions, they should have remained in the skeleton". This is not very helpful if you don't already know how the egraph optimization pass works, but as you make changes you can at least check whether this message changes or goes away.

My guess is that what happened is that you've called DominatorTreePreorder::new but it's uninitialized and empty. I looked at the implementation of DominatorTreePreorder::dominates and I think it always returns true when it isn't initialized. This seems like a reasonable explanation for the test failures to me: if it falsely reports that things dominate each other when they actually don't, then we would "optimize" in places where we aren't actually allowed to.

The first thing I would like you to do is add this to the existing DominatorTreePreorder::dominates function, and commit this change because if other people have the same problem this will help them figure it out more quickly:

// Check that both blocks are reachable.
debug_assert!(na.pre_number != 0);
debug_assert!(nb.pre_number != 0);

When you do that, I predict that more tests will start failing at these asserts. In particular, I hope that cargo test -p cranelift-tools will have some failing tests.

If you can confirm that those asserts fail for some tests, then you can try fixing this and then make sure that the tests pass afterward. I think all you need to do is, in cranelift/codegen/src/context.rs, change compute_domtree so after it calls self.domtree.compute it also calls self.domtree_preorder.compute.

If any of that doesn't work, I'm happy to look at it more carefully.

Once the tests are all passing, I have a couple more comments below. But again, I think this is almost ready!

Wasmtime GitHub notifications bot (May 07 2024 at 06:34):

jameysharp created PR review comment:

This statement can be removed, because the instruction's block is not used here.

The place that I meant you could use this pattern is in the dominates_inst function, where you could use it instead of the match expression. But you don't have to do that if you don't want to; that function is okay the way you wrote it.

Wasmtime GitHub notifications bot (May 07 2024 at 06:34):

jameysharp created PR review comment:

This is a minor thing, but I would prefer to have dominates_inst next to the dominates method that it uses. Then someone looking at one of them can easily see the other one too.

Wasmtime GitHub notifications bot (May 12 2024 at 21:12):

jameysharp commented on PR #8535:

I think you are very close to having this working, so I just want to check how you're doing with it. I'd love to merge this PR once it passes the test suite!

Wasmtime GitHub notifications bot (Jul 25 2024 at 08:26):

fbrv commented on PR #8535:

happy to take a look if @VamshiReddy02 does not enough bandwith.

Wasmtime GitHub notifications bot (Jul 25 2024 at 08:32):

VamshiReddy02 commented on PR #8535:

Sure! Sorry for being inactive, caught up with some work. I'll close this PR. @fbrv you can create a new PR.

Wasmtime GitHub notifications bot (Jul 25 2024 at 15:57):

jameysharp commented on PR #8535:

Thank you for your effort on this, @VamshiReddy02! I think you got most of the way there and I appreciate the time that you put into it.

@fbrv, welcome! Let me know if you have any questions.

Wasmtime GitHub notifications bot (Jul 25 2024 at 17:07):

VamshiReddy02 closed without merge PR #8535.

Last updated: Dec 13 2025 at 19:03 UTC