If the input CLIF does not define values in increasing numeric order, then the egraph GVN map may not recognize that two instructions are the same.

.clif Test Case

test optimize precise-output
set opt_level=speed
set use_egraphs=true
target x86_64

; In this example, iconst defines v2, and later an identical iconst defines v1. 
; In between, v2 is used in an iadd instruction that's added to the GVN map.
; Finally, v1 is used in another iadd which should unify with the first one.
function %unordered(i32) -> i32, i32 {
block0(v0: i32):
    v2 = iconst.i32 42
    v3 = iadd v0, v2
    v1 = iconst.i32 42
    v4 = iadd v0, v1
    return v3, v4
}

; function %unordered(i32) -> i32, i32 fast {
; block0(v0: i32):
;     v2 = iconst.i32 42
;     v3 = iadd v0, v2  ; v2 = 42
;     return v3, v3
; }

Steps to Reproduce

Run the above test with cargo run -p cranelift-tools test.

Expected Results

The above test should pass, with both iadd instructions merged into one.

Actual Results

The iadd instructions are not merged:

; function %unordered(i32) -> i32, i32 fast {
; block0(v0: i32):
;     v2 = iconst.i32 42
;     v3 = iadd v0, v2  ; v2 = 42
;     v4 = iadd v0, v2  ; v2 = 42
;     return v3, v4
; }

Versions and Environment

Cranelift version or commit: main (94f2ff0)

Operating system: Linux

Architecture: x86-64

Extra Info

The hash key and equality definition in the GVN map are based on the set representative returned by the union-find data structure. So once we've added an instruction to the GVN map, every value it uses must have a stable set representative.

This union-find implementation always returns the minimum Value from the set as the set's representative. So a value has a stable set representative if it is never unioned with another set having a smaller set representative.

Most of the time we satisfy this condition. Any newly-created instructions from ISLE rules have value numbers greater than all existing instructions, and within a basic block frontends normally allocate value numbers at the same time that they insert instructions.

As this test case demonstrates though, it's easy to produce a different value order by writing CLIF by hand. I think the same bug can also be triggered if the frontend builds basic blocks in a different order than we visit them during equality saturation, which I suspect is not uncommon.

If the only consequence of this bug is that we sometimes fail to merge identical instructions, then it's not a correctness bug, just a missed optimization. I'm concerned though because this means the hash value for a key in the GVN map can change over time, which violates a hash-map invariant, and I'm not certain of the consequences of that. I don't think we'll trigger undefined behavior or panics, but clearly we can fail to find keys which are already in the map, and insert duplicate keys.

I'm not sure how to fix this.

One half-baked idea: when building the union tree of all results from simplify, if exactly one of the results was already in the GVN map, we use its representative as the representative of the new set. I suspect there can be more than one such result though, so I think that just delays the problem. Also it's a rather invasive change to how we build nodes from ISLE rules.

I think when we're about to union two values together we have enough information to notice that one of them will have its set representative changed. But the only thing I can think to do with that information is to find all the other instructions in the GVN map that refer to the changed value, and remove and reinsert them. That sounds awful.

Another option I don't like is to renumber all the values in the function so that they're in increasing order with respect to the order we're actually going to visit the blocks in.

A variant of renumbering is to keep a map of the values we've seen so far, mapping them to sequentially increasing integers, and use those integers as the union-find IDs. I think that might work, but I haven't followed the idea through far enough to be sure.

cc: @cfallin