inference: track reaching defs for slots

[topolarity]

This PR implements the "Path-Convergence Criterion" for SSA / ϕ-nodes as part of type-inference.

The VarState.ssadef field corresponds to the "reaching definition" of the slot in SSA form, which allows us to conveniently reason about the identity of a slot across multiple program points. If the reaching def is equal at two program points, then the slot contents are guaranteed to be egal (i.e. x₀ === x₁)

Tasks:

• [x] Split StateRefinement change to separate PR
• [x] Split VarTable plumbing to separate PR
• [x] Remove old Conditional invalidation logic
• [x] Add tests

Fixes #55548 (alternative to https://github.com/JuliaLang/julia/pull/55551), by having Conditional remember the reaching definition that it narrows.

[aviatesk]

@nanosoldier runbenchmarks("inference", vs=":master")

[topolarity]

Thanks for the test case and review @aviatesk

fwiw, there's also a precision regression that I encountered w/ this PR:

function foo()
    value = @noinline rand((true, false, 1))
    is_bool = value isa Bool
    if inferencebarrier(@noinline rand(Bool))
        value = 1.0
        is_bool = false
    end
    # at this merge point, only the "false half" of the Conditional should be invalidated
    return is_bool ? value : false
end
@assert only(Base.return_types(foo, ())) === Bool # fails w/ PR

but I think this can be mostly fixed by widening the Conditional at the merge point and giving it a new .ssadef to match

[nanosoldier]

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here.

[vtjnash]

bump? are we able to land this and backport to v1.11/v1.10?

[serenity4]

As discussed with @topolarity, I will take over this PR and finish it so we can have a fix for the underlying issue.

It seems like most of the core functionality works well at the moment, so I believe it's mostly a matter of finishing up the design and related refactors, and address performance regressions.

[serenity4]

@nanosoldier runbenchmarks("inference", vs=":master")

[nanosoldier]

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here.

[serenity4]

@nanosoldier runbenchmarks("inference", vs=":master")

[nanosoldier]

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here.

[serenity4]

@nanosoldier runbenchmarks("inference", vs=":master")

[nanosoldier]

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here.

[vtjnash]

@serenity4 are you still planning to mark this ready for review in time for v1.12 backports?

[serenity4]

Thanks for the ping. Yes, I plan to work again on it soon-ish, not sure it will be ready for a backport for 1.12.0 but at least 1.12.1 would be nice. That is, unless we have a strong motivation to get it in for 1.12.0, in which case I can divert more resources to it.

[vtjnash]

@nanosoldier runbenchmarks("inference", vs=":master")

[nanosoldier]

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here.

[vtjnash]

I just had Claude finish the TODO items, since they sounded like very mechanical things. Seems to have done fine, so this seems ready to merge now, pending review and author approval.

[topolarity]

Has the regression in https://github.com/JuliaLang/julia/pull/55601#issuecomment-2318099769 been fixed?

We should also run a quick evaluation to make sure this doesn't make inference too slow (it turns inference into an semi-inefficient re-implementation of ϕ-node insertion, so it could slow down some cases)

[vtjnash]

Has the regression in #55601 (comment) been fixed?

No, I had a commit for it, but it was tricky enough that I wanted to make it a separate PR

We should also run a quick evaluation to make sure this doesn't make inference too slow (it turns inference into an semi-inefficient re-implementation of ϕ-node insertion, so it could slow down some cases)

It performed better in nanosoldier than our current implementation

[topolarity]

@nanosoldier runtests()

[nanosoldier]

The package evaluation job you requested has completed - possible new issues were detected. The full report is available.

Report summary

❗ Packages that crashed

2 packages crashed only on the current version.

• An unreachable instruction was executed: 2 packages

25 packages crashed on the previous version too.

✖ Packages that failed

11 packages failed only on the current version.

• Package fails to precompile: 3 packages
• Package has test failures: 6 packages
• Package tests unexpectedly errored: 1 packages
• Test duration exceeded the time limit: 1 packages

2802 packages failed on the previous version too.

✔ Packages that passed tests

3 packages passed tests only on the current version.

• Other: 3 packages

3924 packages passed tests on the previous version too.

~ Packages that at least loaded

3537 packages successfully loaded on the previous version too.

➖ Packages that were skipped altogether

1 packages were skipped only on the current version.

• Package could not be installed: 1 packages

916 packages were skipped on the previous version too.