subtyping hang when precompiling some packages

[JeffBezanson]

For example try precompiling Mux.jl. Works in 1.9, hangs on master somewhere in subtyping:

│  in expression starting at /home/jeff/.julia/packages/Mux/PipQ9/src/Mux.jl:35
│  may_contain_union_decision at /home/jeff/src/julia/src/subtype.c:1440
│  may_contain_union_decision at /home/jeff/src/julia/src/subtype.c:1425
│  may_contain_union_decision at /home/jeff/src/julia/src/subtype.c:1425
│  may_contain_union_decision at /home/jeff/src/julia/src/subtype.c:1425
│  may_contain_union_decision at /home/jeff/src/julia/src/subtype.c:1425
│  may_contain_union_decision at /home/jeff/src/julia/src/subtype.c:1425
│  local_forall_exists_subtype at /home/jeff/src/julia/src/subtype.c:1448
│  forall_exists_equal at /home/jeff/src/julia/src/subtype.c:1497
│  subtype at /home/jeff/src/julia/src/subtype.c:1375
│  local_forall_exists_subtype at /home/jeff/src/julia/src/subtype.c:1469
│  forall_exists_equal at /home/jeff/src/julia/src/subtype.c:1497
│  subtype at /home/jeff/src/julia/src/subtype.c:1375
│  local_forall_exists_subtype at /home/jeff/src/julia/src/subtype.c:1469
│  forall_exists_equal at /home/jeff/src/julia/src/subtype.c:1498
│  subtype at /home/jeff/src/julia/src/subtype.c:1375
│  local_forall_exists_subtype at /home/jeff/src/julia/src/subtype.c:1469
│  forall_exists_equal at /home/jeff/src/julia/src/subtype.c:1498
│  subtype at /home/jeff/src/julia/src/subtype.c:1375
...

[N5N3]

MWE

mux(m, f) = x -> m(f, x)
stack(m, n) = (f, x) -> m(mux(n, f), x)
stack(ms...) = foldl(stack, ms)

foldl(stack, (+, +, +, +)) # this works
stack(+, +, +, +) # this hangs

[N5N3]

Bisect points to 51e3bc3 :

51e3bc33dec9be9ebe5ad5fe5f4da56a3bab33c9 is the first bad commit
commit 51e3bc33dec9be9ebe5ad5fe5f4da56a3bab33c9
Author: Keno Fischer <keno@juliacomputing.com>
Date:   Sun Feb 5 11:18:18 2023 -0500

    typelimits: Prevent accidental infinite growth in size limiting (#48421)

    * typelimits: Prevent accidental infinite growth in size limiting

    There's a few related issues here:
    1. Type size limiting depended on the identity of contained TypeVars.
       E.g. `Base.rewrap_unionall(Foo{Base.unwrap_unionall(A)}, A)`, would
       not be limited while the equivalent with typevars substituted would be.
       This is obviously undesirable because the identity of typevars is an
       implementation detail.
    2. We were forcing `tupledepth` to 1 in the typevar case to allow replacing
       typevars by something concrete. However, this also allowed typevars being
       replaced by something derived from `sources`, which could be huge and itself
       contain TypeVars, allowing infinite growth.
    3. There was a type query that was run on types containg free typevars. This
       would have asserted in a debug build and gave wrong answers in a release build.

    Fix all three issues, which together addresses an inference non-termination seen in #48329.

    * wip: fix `apply_type_tfunc` accuracy (#48329)

    ---------

    Co-authored-by: Shuhei Kadowaki <40514306+aviatesk@users.noreply.github.com>

 base/compiler/tfuncs.jl     | 36 ++++++++++++++++--------------------
 base/compiler/typelimits.jl | 16 ++++++++--------
 test/compiler/inference.jl  | 27 ++++++++++++++++++++++-----
 3 files changed, 46 insertions(+), 33 deletions(-)

[N5N3]

MWE for subtyping hangs

struct FP{m,n} <: Function end
a = [TypeVar(Symbol(:V, i), Union{}, Function) for i in 1:32];
S = foldr((v, d) -> UnionAll(v, d), a; init = foldl((i, j) -> FP{i, j}, a))
T = foldr((v, d) -> UnionAll(v, d), a[1:end-1]; init = foldl((i, j) -> FP{i, j}, a[1:end-1]))
S<:T # also hangs on v1.9-rc1/1.6/1.8

If we reduce the layer of S and T, then we can confirm that master is about 4x slower than v1.9rc1 for this specific problem.