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
}
Is it even possible, since v3
and v4
arent mentioned in the definition of v5
?
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 icmp
s
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
so... I can't think of a way, but it does seem like a nice optimization...
I feared it might require a manual pass over the BB
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
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
(and usually both go to the general ALU so both have the same throughput, at least on x86)
also the band
may force reification of the bools into registers whereas the icmp
can be fused directly with its consumer (branch, select, etc)
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
there's definitely value in that sort of completeness! but also worth considering whether the rewrite results in something cheaper :-)
For something like a < b && b < c && a < c
it would rewrite to a < b && b < c
which is definitely cheaper
ah, yes, that's a good example
I think to handle symmetry of icmp relations would require recognising commutative operators/relations in CSE?
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
we also shouldn't prepopulate the egraph with flipped icmp operators; that's far too noisy/expensive
I'm taking off for the day but cc @Jamey Sharp @fitzgen (he/him) to think more about this (happy to talk more tomorrow)
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.
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: Dec 23 2024 at 13:07 UTC