converted DominatorTree to DominatorTreePreorder in alias_analysis file

[VamshiReddy02]

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.

[abrown]

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

[jameysharp]

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!

[VamshiReddy02]

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?

[jameysharp]

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.

[VamshiReddy02]

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

[jameysharp]

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!

[fbrv]

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

[VamshiReddy02]

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

[jameysharp]

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.