Incorrect optimization on typejoin in 1.11+

[KristofferC]

The following PkgEval log https://s3.amazonaws.com/julialang-reports/nanosoldier/pkgeval/by_hash/0520b80_vs_997b49f/DataStructures.primary.log shows a regression in typejoin where the result inside the function is different from outside. The code below reproduces that (with a debug statement to see what is being executed inside there and with an interpreted result which agrees with the manually evaluated typejoin call):

julia> using DataStructures, JuliaInterpreter

julia> f(x) = x % 2 == 0 ? convert(Int8, x) : convert(Float16, x)
f (generic function with 1 method)

julia> n = 5
5

julia> l = MutableLinkedList{Int}(1:n...)
MutableLinkedList{Int64}(1, 2, 3, 4, 5)

julia> map(f, l)
# (typejoin(S, typeof(el)), S, typeof(el)) = (Float16, Float16, Int8)
MutableLinkedList{Float16}(1.0, 2.0, 3.0, 4.0, 5.0)

julia> typejoin(Float16, Int8)
Real

julia> @interpret map(f, l)
# (typejoin(S, typeof(el)), S, typeof(el)) = (Real, Float16, Int8)
MutableLinkedList{Real}(1.0, 2, 3.0, 4, 5.0)

The relevant code in DataStructures.jl is https://github.com/JuliaCollections/DataStructures.jl/blob/5451407b8c7e66a2e572d2f50c0f75e675016d35/src/mutable_list.jl#L75-L89

Bisected to 8307dbf (cc @vtjnash)

[vtjnash]

It sounds like an optimizer bug with handling a Union of ConcreteEval results. Inference said only correct things about typejoin:

     @ /home/vtjnash/.julia/packages/DataStructures/b0JVf/src/mutable_list.jl:83 within `map`
10 ─ %59 = DataStructures.typejoin::Core.Const(typejoin) (+c,+e,+n,+t,+s,+m,+u)
│    %60 = S::Union{Type{Float16}, Type{Int8}} (+c,+e,+n,+t,+s,+m,+u)
│    %61 = DataStructures.typeof::Core.Const(typeof) (+c,+e,+n,+t,+s,+m,+u)
│    %62 = el::Union{Float16, Int8} (+c,+e,+n,+t,+s,+m,+u)
│    %63 = (%61)(%62)::Union{Type{Float16}, Type{Int8}} (+c,+e,+n,+t,+s,+m,+u)
│          (R = (%59)(%60, %63))::Union{Type{Float16}, Type{Int8}, Type{Real}} (+c,+e,+n,+t,+s,+m,+u)
│    @ /home/vtjnash/.julia/packages/DataStructures/b0JVf/src/mutable_list.jl:84 within `map`
│    %65 = R::Union{Type{Float16}, Type{Int8}, Type{Real}} (+c,+e,+n,+t,+s,+m,+u)
│    %66 = Core.apply_type(DataStructures.MutableLinkedList, %65)::Type{MutableLinkedList{_A}} where _A (+c,+e,+n,+t,+s,+m,+u)
│    %67 = DataStructures.collect::Core.Const(collect) (+c,+e,+n,+t,+s,+m,+u)
│    %68 = l2::Any (+c,+e,+n,+t,+s,+m,+u)
│    %69 = (%67)(%68)::Any (!c,!e,!n,!t,!s,!m,!u)′
│          (l2 = Core._apply_iterate(Base.iterate, %66, %69))::Any (!c,!e,!n,!t,!s,!m,!u)′

The optimizer however did not:

     @ /home/vtjnash/.julia/packages/DataStructures/b0JVf/src/mutable_list.jl:84 within `map`
22 ─ %79 = Core.apply_type(DataStructures.MutableLinkedList, Float16)::Type{MutableLinkedList{_A}} where _A

[KristofferC]

@aviatesk, could you look at this?

[aviatesk]

yes, #53600 should fix this.