Stream: cranelift

Topic: ISLE: how to represent transitive relations

kmeakin (Mar 29 2023 at 23:57):

Is it possible to represent transitive relations in ISLE?
ie I would like

function %icmp_eq_transitive(i32, i32, i32) -> i8, i8, i8 {
block0(v0: i32, v1: i32, v2: i32):
    v3 = icmp eq v0, v1
    v4 = icmp eq v1, v2
    v5 = icmp eq v0, v2
    return v3, v4, v5
}

be optimised to

function %icmp_eq_transitive(i32, i32, i32) -> i8, i8, i8 {
block0(v0: i32, v1: i32, v2: i32):
    v3 = icmp eq v0, v1
    v4 = icmp eq v1, v2
    v6 = band eq v3, v4
    return v3, v4, v6
}

kmeakin (Mar 29 2023 at 23:59):

Is it even possible, since v3 and v4 arent mentioned in the definition of v5?

Chris Fallin (Mar 30 2023 at 00:03):

A general technique for that sort of thing in an egraph is to rewrite icmp eq v0, v2 to (band (icmp v0 v1) (icmp v1 v2)), then letting the interning and cost function realize that the band is cheaper if we already have the two other icmps

Chris Fallin (Mar 30 2023 at 00:03):

that almost works except we don't have v1 and it would be too expensive to do it for all values in scope that fit

Chris Fallin (Mar 30 2023 at 00:03):

so... I can't think of a way, but it does seem like a nice optimization...

kmeakin (Mar 30 2023 at 00:17):

I feared it might require a manual pass over the BB

kmeakin (Mar 30 2023 at 00:18):

I opened an issue against LLVM a few months back but havent done any work on it yet: https://github.com/llvm/llvm-project/issues/57506

Chris Fallin (Mar 30 2023 at 00:19):

I'd also be curious about the performance difference, if any (this could be verified by compiling manually-optimized code); a compare of a register-width value is a single-cycle operation, as is an AND

Chris Fallin (Mar 30 2023 at 00:19):

(and usually both go to the general ALU so both have the same throughput, at least on x86)

Chris Fallin (Mar 30 2023 at 00:20):

also the band may force reification of the bools into registers whereas the icmp can be fused directly with its consumer (branch, select, etc)

kmeakin (Mar 30 2023 at 00:21):

I haven't looked into any performance measurements, I just thought since we have reflexivity for the icmp relations we should have transitivity and symmetry too

Chris Fallin (Mar 30 2023 at 00:22):

there's definitely value in that sort of completeness! but also worth considering whether the rewrite results in something cheaper :-)

kmeakin (Mar 30 2023 at 00:23):

For something like a < b && b < c && a < c it would rewrite to a < b && b < c which is definitely cheaper

Chris Fallin (Mar 30 2023 at 00:25):

ah, yes, that's a good example

kmeakin (Mar 30 2023 at 00:42):

I think to handle symmetry of icmp relations would require recognising commutative operators/relations in CSE?

Chris Fallin (Mar 30 2023 at 00:50):

That's an interesting one -- commutativity depends on the particular condition code (in particular, eq/ne only); so we can't just mark the decl and let islec expand LHSes, as is our plan for other operators

Chris Fallin (Mar 30 2023 at 00:50):

we also shouldn't prepopulate the egraph with flipped icmp operators; that's far too noisy/expensive

Chris Fallin (Mar 30 2023 at 00:50):

I'm taking off for the day but cc @Jamey Sharp @fitzgen (he/him) to think more about this (happy to talk more tomorrow)

Jamey Sharp (Mar 30 2023 at 15:48):

We can, and probably should, normalize commutative instructions when interacting with the GVN map (both on insert and lookup). That will help us deduplicate more instructions, in addition to making certain kinds of ISLE patterns in effective automatically commutative.
I think it'll suffice to sort the Value arguments (and update e.g. condition codes as appropriate) after finding their representatives in the union-find.
That raises the issue that our current trick of swapping constants to the right in ISLE rules won't work because we'll only actually store one order.
Also I think there's a bug in the GVN map currently where depending on the order in which values are declared in the input CLIF, it may not recognize two instructions as equal (which is safe but suboptimal) and may violate hash-map invariants (which might also be safe but seems potentially bad).
I'm planning to write this all up in more detail today.

Jamey Sharp (Mar 30 2023 at 22:04):

Done: https://github.com/bytecodealliance/wasmtime/issues/6129 and https://github.com/bytecodealliance/wasmtime/issues/6126, with bonus issue https://github.com/bytecodealliance/wasmtime/issues/6128

Last updated: Oct 23 2024 at 20:03 UTC