Stream: cranelift

Topic: ✔ Matching on numeric limits n ISLE

kmeakin (Mar 16 2023 at 22:33):

How can I match on numeric limits (eg UMIN, SMIN, SMAX) in ISLE?
I'm trying to add rewrites for sge(x, SMIN) == true etc

Jamey Sharp (Mar 16 2023 at 22:40):

Good question! Unsigned minimum is easy since it's always 0. Unsigned maximum for a given type ty is available as (ty_mask ty). The signed versions are trickier.

kmeakin (Mar 16 2023 at 22:42):

Good catch, I meant UMAX :sweat_smile:

Jamey Sharp (Mar 16 2023 at 22:43):

Let's see. Signed minimum is all zeroes except a 1 in the sign bit, and signed maximum is all ones except a 0 in the sign bit… There's probably something clever there.

Chris Fallin (Mar 16 2023 at 22:45):

I dunno about y'all but I personally enjoy mashing 0 or f exactly 15 times when writing consts in hex!

Chris Fallin (Mar 16 2023 at 22:46):

the straightforward answer is that we should probably just define some constants in the prelude

Jamey Sharp (Mar 16 2023 at 22:46):

These aren't constants though because they depend on the bit-width of the type :sweat_smile:

Chris Fallin (Mar 16 2023 at 22:47):

ah, right, type-parameterized... so yeah we might want a ty_smin, ty_smax

Chris Fallin (Mar 16 2023 at 22:47):

(external pure ctors I mean)

Jamey Sharp (Mar 16 2023 at 22:52):

I think it's interesting that signed min is the same as unsigned min with the sign bit flipped, and similarly for max. So we could do this with one extra pure constructor (flip sign bit?). But I think you're right that it should just be the specialized signed-min and signed-max constructors.

Whatever we do here will also be useful in backends. For example, riscv currently has an open PR that could use this for saturating floating-point to integer conversions.

Jamey Sharp (Mar 16 2023 at 22:54):

Ooh, the one annoying thing here too is that you kinda really want an extractor instead of having to do (if-let $true (u64_eq ...))

Chris Fallin (Mar 16 2023 at 22:55):

unless something has changed, one can bind both an etor and ctor to a term...

Chris Fallin (Mar 16 2023 at 22:55):

ah, I guess the tricky bit is the flipped signature though

Chris Fallin (Mar 16 2023 at 22:55):

oh wait no, it's the same (type on the "outside") in most contexts you'd probably want an etor

Chris Fallin (Mar 16 2023 at 22:56):

err, no to myself, it's flipped

Chris Fallin (Mar 16 2023 at 22:56):

less parens more coffee

Jamey Sharp (Mar 16 2023 at 22:59):

I always have trouble with which way around the constructor and extractor types are, so I'd just have to try it. "type on the outside" sounds plausible?

Chris Fallin (Mar 16 2023 at 23:00):

works for the extractor, but for the constructor I think you want (Type) u64

Jamey Sharp (Mar 16 2023 at 23:05):

Oh yeah. Okay I hate all the options now.

Chris Fallin (Mar 16 2023 at 23:06):

yup...

Jamey Sharp (Mar 16 2023 at 23:10):

@kmeakin Okay, so in conclusion: Would you mind opening a PR which adds external constructors ty_smin and ty_smax, which take a Type and return a u64? You'd use them like (if-let $true (u64_eq n (ty_smin ty))), which nobody is happy with, but that seems to be where we're at today.

kmeakin (Mar 16 2023 at 23:16):

thank you, I will try that

Notification Bot (Mar 16 2023 at 23:29):

kmeakin has marked this topic as resolved.

Jamey Sharp (Mar 17 2023 at 00:03):

Nice work, @kmeakin!

Notification Bot (Mar 17 2023 at 01:08):

kmeakin has marked this topic as unresolved.

kmeakin (Mar 17 2023 at 01:09):

The constructors don't seem to be matching :(

This function is unchanged

function %icmp_ule_umax(i32) -> i8 {
block0(v0: i32):
    v1 = iconst.i32 0xffff_ffff
    v2 = icmp ule v0, v1
    return v2
}

kmeakin (Mar 17 2023 at 01:09):

This is the rule that should fire:

;; ule(x, UMAX) == true.
(rule (simplify
       (icmp (fits_in_64 (ty_int ty)) (IntCC.UnsignedLessThanOrEqual) x umax @ (iconst _ (u64_from_imm64 y))))
       (if-let $true (u64_eq y (ty_umax ty)))
       (subsume (iconst ty (imm64 1))))

kmeakin (Mar 17 2023 at 01:10):

And the constructor implementations are

        #[inline]
        fn ty_umin(&mut self, _ty: Type) -> u64 {
            0
        }

        #[inline]
        fn ty_umax(&mut self, ty: Type) -> u64 {
            self.ty_mask(ty)
        }

        #[inline]
        fn ty_smin(&mut self, ty: Type) -> u64 {
            let ty_bits = ty.bits();
            debug_assert_ne!(ty_bits, 0);
            let shift = 64_u64
                .checked_sub(ty_bits.into())
                .expect("unimplemented for > 64 bits");
            (i64::MIN as u64) >> shift
        }

        #[inline]
        fn ty_smax(&mut self, ty: Type) -> u64 {
            let ty_bits = ty.bits();
            debug_assert_ne!(ty_bits, 0);
            let shift = 64_u64
                .checked_sub(ty_bits.into())
                .expect("unimplemented for > 64 bits");
            (i64::MAX as u64) >> shift
        }

kmeakin (Mar 17 2023 at 01:54):

nvm I figured it out. I was passing the ty from the icmp instruction to ty_umax, when I should have passed the ty from the iconst instruction

Notification Bot (Mar 17 2023 at 02:00):

kmeakin has marked this topic as resolved.

Last updated: Dec 23 2024 at 12:05 UTC