Performance regression for Union types in 1.7.0-rc1

[goerch]

The following program

mutable struct Node{K,D}
    parent::Union{Node{K,D},Nothing}
    left::Union{Node{K,D},Nothing}
    right::Union{Node{K,D},Nothing}
    key::K
    bf::Int8
    data::D
end

mutable struct AVLTree{K,D}
    root::Union{Node{K,D},Nothing}
end

@inline function rotate_left(t::AVLTree{K,D}, x::Node{K,D}, x_right::Node{K,D}) where {K,D}
    y = x_right

    if y.left !== nothing
        x.right = y.left
        y.left.parent = x
    else
        x.right = nothing
    end
    y.left = x

    xp = x.parent
    if xp === nothing
        t.root = y
    else
        if xp.left == x
            xp.left = y
        else
            xp.right = y
        end
    end

    y.parent = xp
    x.parent = y

    x.bf -= y.bf * (y.bf >= zero(Int8)) + one(Int8)
    y.bf += x.bf * (x.bf < zero(Int8)) - one(Int8)

    return y
end

t = AVLTree{Int, Nothing}(nothing)
x = Node{Int, Nothing}(nothing, nothing, nothing, 1, 0, nothing)
using BenchmarkTools
@btime rotate_left($t, $x, $x)

produces on Julia Version 1.6.3:

julia> @btime rotate_left($t, $x, $x)
  7.101 ns (0 allocations: 0 bytes)

and on 1.7.0-rc1:

julia> @btime rotate_left($t, $x, $x)
  638.982 ns (0 allocations: 0 bytes)

Related discussion: https://discourse.julialang.org/t/dynamic-dispatch-with-union-nothing/70174/3

[KristofferC]

Thanks for the info, I did a short update of the text to condense it a bit and make it explicit how to check the performance regression.

Looking at @code_warntype it seems that some calls that used to be inlined are no longer so:

- 3 ──       Base.setfield!(x, :right, nothing)
+ %6  = Base.setproperty!::typeof(setproperty!)
+ │    %7  = (isa)(%5, Nothing)::Bool
+ └───       goto #4 if not %7
+ 3 ── %9  = π (%5, Nothing)
+ │          invoke %6(_3::Node{Int64, Nothing}, :right::Symbol, %9::Nothing)

I will try bisect it.

[KristofferC]

Bisected to #39754, cc @Keno

[aviatesk]

Seems like non-inlined setproperty!s are union-split. So I guess what we need here is basically a way to use constant-prop'ed sources at union-split callsite (ref: #39305 (comment))
So in other word, we need to resolve this TODO (IIUC):

julia/base/compiler/ssair/inlining.jl

Lines 1226 to 1230 in 609a4a0

	# when multiple matches are found, bail out and later inliner will union-split this signature
	# TODO effectively use multiple constant analysis results here
	length(info.results) == 1 || return false
	result = info.results[1]
	isa(result, InferenceResult) || return false