Julia 1.9.0 freezes in subtyping

[kpamnany]

julia> versioninfo()
Julia Version 1.9.0
Commit 8e630552924 (2023-05-07 11:25 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 12 × Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, skylake)
  Threads: 1 on 12 virtual cores

Reproducer:

julia> x = Tuple{Type{Array{Union{Nothing, Bool, Char, Float16, Float32, Float64, Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8, Missing, Base.Regex, String, Symbol, Tuple, Base.Rational{T} where T<:Integer}, 1}}, UndefInitializer, Tuple{Int64}}
Tuple{Type{Vector{Union{Missing, Nothing, Bool, Char, Float16, Float32, Float64, Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8, Regex, String, Symbol, Tuple, Rational}}}, UndefInitializer, Tuple{Int64}}

julia> y = Tuple{Type{Array{T, N} where N}, UndefInitializer, Tuple{Vararg{Integer, N}}} where N where T
Tuple{Type{Array{T}}, UndefInitializer, Tuple{Vararg{Integer, N}}} where {T, N}

julia> x <: y  # freezes

This worked on 1.8 and is also fixed on master.

[kpamnany]

@quinnj bisected this and found the commit that introduces the freeze.

Subsequently, this commit fixes the freeze.

Unfortunately, there are manymany commits in between. It seems intractable to backport all of them.

[quinnj]

I think my question is where to go from here; the options seem to be 1) try to backport a good chunk of the subtyping changes or 2) revert the 1 commit from 1.9. The tricky part is that the commit that caused the perf regression also fixed #40865, so I guess another question is what do we think is more common/problematic: the original #40865 issue? Or people running into the perf regression we're seeing here?

Maybe @vtjnash has a sense for the best path forward here?

[kpamnany]

Related: #49323 and #48582

[kpamnany]

This is fixed for 1.9.1 by #49875.