Stream: cranelift

Topic: ISLE matching problems

kmeakin (Mar 17 2023 at 15:37):

More pattern matching woes. These rules dont seem to be firing:

;; x%1 == 0.
(rule (simplify (urem ty x (iconst ty (u64_from_imm64 1))))
      (subsume (iconst ty (imm64 0))))

;; x%c == x&(c-1) when c is a power of 2.
(rule (simplify (urem ty x (iconst ty (u64_from_imm64 c))))
      (if-let $true (u64_is_power_of_two c))
      (band ty x (iconst ty (imm64 (u64_sub c 1)))))

These functions are unchanged:

function %urem_x_1(i32) -> i32 {
block0(v0: i32):
    v1 = iconst.i32 1
    v2 = urem v0, v1
    return v2
    ; check: v3 = iconst.i32 0
    ; check: return v3 ; v3 = 0
}

function %urem_x_pow2(i32) -> i32 {
block0(v0: i32):
    v1 = iconst.i32 2
    v2 = urem v0, v1
    return v2
    ; check: v3 = iconst.i32 1
    ; check: v4 = band v0, v3
    ; check: return v4
}

and the constructor is

        #[inline]
        fn u64_is_power_of_two(&mut self, x: u64) -> bool {
            x.is_power_of_two()
        }

Chris Fallin (Mar 17 2023 at 16:18):

Ah, I believe this is due to a limitation in the egraph framework: we cannot rewrite instructions that have side-effects. urem can trap, and so we can't have a rule that rewrites it away, in the general case. Of course this doesn't account for the fact that we should be able to, if the divisor is constant, as here. We talked a bit about this in #5908 and prior linked issue; we have ideas for how to better represent this; but right now, it's expected that the above won't work, sorry :-/

kmeakin (Mar 17 2023 at 16:51):

That's unfortunate. But I see there is a rewrite for x/1 == x though. Does that rule work?

Chris Fallin (Mar 17 2023 at 16:53):

I believe it's dead currently, too

kmeakin (Mar 17 2023 at 16:59):

I see. I'll submit a PR and note that they wont actually get fired yet

Chris Fallin (Mar 17 2023 at 17:01):

thanks!

fitzgen (he/him) (Mar 17 2023 at 17:37):

ah this has interesting implications for porting the magic constant div/rem rewrites from the old simple preopt pass

fitzgen (he/him) (Mar 17 2023 at 17:38):

(if you are interested in doing more mid-end rewrites stuff @kmeakin, that could be an interesting project)

fitzgen (he/him) (Mar 17 2023 at 17:42):

this is the old simple preopt stuff for some number divided/remaindered by a constant:

• https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/divconst_magic_numbers.rs#L41-L217

• https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/simple_preopt.rs#L206-L243

needs to be ported to ISLE in the mid-end, but to do that we need to be able to rewrite potentially-trapping instructions in ISLE, as discussed upthread

fitzgen (he/him) (Mar 17 2023 at 17:46):

I filed an issue for porting these magic constants over to ISLE, since I couldn't find one already on file: https://github.com/bytecodealliance/wasmtime/issues/6049

kmeakin (Mar 17 2023 at 18:06):

fitzgen (he/him) said:

(if you are interested in doing more mid-end rewrites stuff kmeakin, that could be an interesting project)

That could be fun

Last updated: Dec 23 2024 at 13:07 UTC