Bug in subtyping/method lookup that causes unreacheable reached

[kpamnany]

Testing with Julia 1.10.1 + some patches, we see:

...
Unreachable reached at 0x7fff395e787b
make: *** [Makefile:160: hydra/benchmark.micro.sorting] Illegal instruction (core dumped)
...

@Drvi then ran this test with a debug build of Julia and got:

φ node 207 is not at the beginning of the basic block 53
Internal error: encountered unexpected error in runtime:
MethodError(f=Base.Multimedia.display, args=(Core.Compiler.IRCode(stmts=Core.Compiler.InstructionStream(inst=Array{Any, (272,)}[
  Core.UpsilonNode(val=Core.Argument(n=2)),
  Expr(:enter, 76),
  Expr(:call, Base.getfield, Core.Argument(n=2), :(:cond)),
...

We will share the entire error separately.

[kpamnany]

Attn: @vchuravy and @Keno

[topolarity]

Do you have an MWE?

φ node 207 is not at the beginning of the basic block 53

This indicates that Julia produced invalid IR at some point.

[kpamnany]

I spent some time on this with @gbaraldi and we were able to find the broken IR and also narrow the problem down further. He should also be able to reproduce the error.

Over the last few days, we found that the PackageCompiler step for our system occasionally segfaults with no stack trace. Trying this with a debug build of Julia 1.10.1 with LLVM assertions on reveals many such invalid IR errors:

...
φ node 163 is not at the beginning of the basic block 39
...
φ node 207 is not at the beginning of the basic block 53
...
φ node 320 is not at the beginning of the basic block 105
...
φ node 371 is not at the beginning of the basic block 120
...
φ node 436 is not at the beginning of the basic block 135
...

This has blocked our plan to upgrade to Julia 1.10.1 this week. :(

[kpamnany]

Cc: @KristofferC whom @Drvi had pinged about this, and @Keno, who added this error report.

[topolarity]

I spent some time on this with @gbaraldi and we were able to find the broken IR and also narrow the problem down further. He should also be able to reproduce the error.

Do you have some IR or an MWE? There's still no code attached to this issue...

[kpamnany]

Shared privately.

Edited to add: sorry for the brevity here; there's more discussion on Slack. To summarize, we have not yet been able to reduce the code that triggers this error enough to share it here -- the "MWE" still contains a bunch of proprietary code.

However, @gbaraldi is able to reproduce, and hopefully the problem will be tracked down quickly!

[gbaraldi]

So me and @topolarity reduced this to

function flush!(sc::Threads.Condition)
    @lock sc begin
        try
            if Core.Compiler.inferencebarrier(true)
                return nothing
            end

            return nothing
        finally
        end
    end
end
code_typed(flush!, (Threads.Condition,))

Note that this does not fail if you do a manual macro expansion. It also does not fail on master, so somewhere along the line we fixed this.

[NHDaly]

Awesome! Thanks for that! Is the issue present on 1.9 as well? Can you see from the code that's being generated, even though the assertion isn't present in 1.9?

[topolarity]

The problem with the bad ϕ-nodes has been resolved, but this issue persists unfortunately.

[gbaraldi]

So after @topolarity and me stared at this for way too long, this got minimized to

struct Foo{T} end
struct Bar{T} end
struct Baz{T} end
struct Lala{T} end

function swap!(pg::Foo{T}, page::Bar{Baz{T}}) where T
        return nothing
end

TT1 = Tuple{
    typeof(swap!),
    Foo{Lala{T}} where T,
    Bar{T} where T<:Baz
}

A = Foo{Lala{T}} where T
T = TypeVar(:T, UnionAll(A.var, Baz{A.var}))
B = UnionAll(T, Bar{T})
TT2 = Tuple{typeof(swap!), A, B}

@assert TT1 == TT2

@assert TT1 === TT2
matches1 = Base._methods_by_ftype(TT1, nothing, -1, ccall(:jl_get_world_counter, UInt, ())) # 1 match
matches2 = Base._methods_by_ftype(TT2, nothing, -1, ccall(:jl_get_world_counter, UInt, ())) # 0 matches

@show matches1 matches2

This is probably a bug in subtyping somewhere. Note that TT1 is considered egal and isequal to TT2 but they behave differently

[topolarity]

This is probably a bug in subtyping somewhere

Either that or it's illegal to construct a type with a shared TypeVar like this, in which case the bug is that we ended up doing that somewhere in inference

[N5N3]

Either that or it's illegal to construct a type with a shared TypeVar like this

jl_rename_unionall should take care of this though.
I haven't verified it locally, but this bug seems to be caused by this TODO

julia/src/subtype.c

Lines 3059 to 3075 in 2b95956

	// if the var for this unionall (based on identity) already appears somewhere
	// in the environment, rename to get a fresh var.
	// TODO: might need to look inside types in btemp->lb and btemp->ub
	int envsize = 0;
	while (btemp != NULL) {
	envsize++;
	if (envsize > 120) {
	vb->limited = 1;
	return t;
	}
	if (btemp->var == u->var || btemp->lb == (jl_value_t*)u->var ||
	btemp->ub == (jl_value_t*)u->var) {
	u = jl_rename_unionall(u);
	break;
	}
	btemp = btemp->prev;
	}

An easy fix is fusing unalias_unionall here.

[topolarity]

Between #53512 and #53553, I believe this is fully resolved now!