Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Incorrect optimization on typejoin in 1.11+ #53590

Closed
KristofferC opened this issue Mar 4, 2024 · 7 comments · Fixed by #53600
Closed

Incorrect optimization on typejoin in 1.11+ #53590

KristofferC opened this issue Mar 4, 2024 · 7 comments · Fixed by #53600
Assignees
@aviatesk
Labels
compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) regression Regression in behavior compared to a previous version
Milestone
1.11

Comments

@KristofferC
Copy link
Member

KristofferC commented Mar 4, 2024 •
edited
Loading

The following PkgEval log https://s3.amazonaws.com/julialang-reports/nanosoldier/pkgeval/by_hash/0520b80_vs_997b49f/DataStructures.primary.log shows a regression in typejoin where the result inside the function is different from outside. The code below reproduces that (with a debug statement to see what is being executed inside there and with an interpreted result which agrees with the manually evaluated typejoin call):

julia> using DataStructures, JuliaInterpreter

julia> f(x) = x % 2 == 0 ? convert(Int8, x) : convert(Float16, x)
f (generic function with 1 method)

julia> n = 5
5

julia> l = MutableLinkedList{Int}(1:n...)
MutableLinkedList{Int64}(1, 2, 3, 4, 5)

julia> map(f, l)
# (typejoin(S, typeof(el)), S, typeof(el)) = (Float16, Float16, Int8)
MutableLinkedList{Float16}(1.0, 2.0, 3.0, 4.0, 5.0)

julia> typejoin(Float16, Int8)
Real

julia> @interpret map(f, l)
# (typejoin(S, typeof(el)), S, typeof(el)) = (Real, Float16, Int8)
MutableLinkedList{Real}(1.0, 2, 3.0, 4, 5.0)

The relevant code in DataStructures.jl is https://github.com/JuliaCollections/DataStructures.jl/blob/5451407b8c7e66a2e572d2f50c0f75e675016d35/src/mutable_list.jl#L75-L89

Bisected to 8307dbf (cc @vtjnash)
@KristofferC KristofferC added regression Regression in behavior compared to a previous version compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) labels Mar 4, 2024
@KristofferC KristofferC added this to the 1.11 milestone Mar 4, 2024
@vtjnash
Copy link
Member

vtjnash commented Mar 4, 2024

It sounds like an optimizer bug with handling a Union of ConcreteEval results. Inference said only correct things about typejoin:

     @ /home/vtjnash/.julia/packages/DataStructures/b0JVf/src/mutable_list.jl:83 within `map`
10 ─ %59 = DataStructures.typejoin::Core.Const(typejoin) (+c,+e,+n,+t,+s,+m,+u)
│    %60 = S::Union{Type{Float16}, Type{Int8}} (+c,+e,+n,+t,+s,+m,+u)
│    %61 = DataStructures.typeof::Core.Const(typeof) (+c,+e,+n,+t,+s,+m,+u)
│    %62 = el::Union{Float16, Int8} (+c,+e,+n,+t,+s,+m,+u)
│    %63 = (%61)(%62)::Union{Type{Float16}, Type{Int8}} (+c,+e,+n,+t,+s,+m,+u)
│          (R = (%59)(%60, %63))::Union{Type{Float16}, Type{Int8}, Type{Real}} (+c,+e,+n,+t,+s,+m,+u)
│    @ /home/vtjnash/.julia/packages/DataStructures/b0JVf/src/mutable_list.jl:84 within `map`
│    %65 = R::Union{Type{Float16}, Type{Int8}, Type{Real}} (+c,+e,+n,+t,+s,+m,+u)
│    %66 = Core.apply_type(DataStructures.MutableLinkedList, %65)::Type{MutableLinkedList{_A}} where _A (+c,+e,+n,+t,+s,+m,+u)
│    %67 = DataStructures.collect::Core.Const(collect) (+c,+e,+n,+t,+s,+m,+u)
│    %68 = l2::Any (+c,+e,+n,+t,+s,+m,+u)
│    %69 = (%67)(%68)::Any (!c,!e,!n,!t,!s,!m,!u)′
│          (l2 = Core._apply_iterate(Base.iterate, %66, %69))::Any (!c,!e,!n,!t,!s,!m,!u)′

The optimizer however did not:

     @ /home/vtjnash/.julia/packages/DataStructures/b0JVf/src/mutable_list.jl:84 within `map`
22 ─ %79 = Core.apply_type(DataStructures.MutableLinkedList, Float16)::Type{MutableLinkedList{_A}} where _A

@vtjnash vtjnash removed their assignment Mar 4, 2024
@KristofferC
Copy link
Member Author

@aviatesk, could you look at this?

aviatesk added a commit that referenced this issue Mar 5, 2024
@aviatesk
inlining: use method match signature for union-spliting
d083e99 
In cases where the results of constant inference, like concrete-eval,
are used for union-split inlining, `isa`-blocks are generated using the
`result.edge.specTypes` stored within each `result`. However, it's been
found that the `edge` returned by abstract interpretation may have been
widened by the new `@nospecializeinfer`, which can result in invalid
union-splitting. To address this problem, this commit tweaks the
inlining algorithm so that it performs union-split inlining using the
original signatures that abstract interpretation used for union-split
inference, by using `match::MethodMatch`.

- fixes #53590
@aviatesk aviatesk mentioned this issue Mar 5, 2024
Merged
@aviatesk
Copy link
Member

aviatesk commented Mar 5, 2024

yes, #53600 should fix this.

aviatesk added a commit that referenced this issue Mar 7, 2024
@aviatesk
inlining: use method match signature for union-spliting (#53600)
d45581c 
In cases where the results of constant inference, like concrete-eval,
are used for union-split inlining, `isa`-blocks are generated using the
`result.edge.specTypes` stored within each `result`. However, it's been
found that the `edge` returned by abstract interpretation may have been
widened by the new `@nospecializeinfer`, which can result in invalid
union-splitting. To address this problem, this commit tweaks the
inlining algorithm so that it performs union-split inlining using the
original signatures that abstract interpretation used for union-split
inference, by using `match::MethodMatch`.

- fixes #53590
aviatesk added a commit that referenced this issue Mar 7, 2024
@aviatesk
inlining: use method match signature for union-spliting (#53600)
2a7100a 
In cases where the results of constant inference, like concrete-eval,
are used for union-split inlining, `isa`-blocks are generated using the
`result.edge.specTypes` stored within each `result`. However, it's been
found that the `edge` returned by abstract interpretation may have been
widened by the new `@nospecializeinfer`, which can result in invalid
union-splitting. To address this problem, this commit tweaks the
inlining algorithm so that it performs union-split inlining using the
original signatures that abstract interpretation used for union-split
inference, by using `match::MethodMatch`.

- fixes #53590
aviatesk added a commit that referenced this issue Mar 7, 2024
@aviatesk
inlining: use method match signature for union-spliting (#53600)
94273e6 
In cases where the results of constant inference, like concrete-eval,
are used for union-split inlining, `isa`-blocks are generated using the
`result.edge.specTypes` stored within each `result`. However, it's been
found that the `edge` returned by abstract interpretation may have been
widened by the new `@nospecializeinfer`, which can result in invalid
union-splitting. To address this problem, this commit tweaks the
inlining algorithm so that it performs union-split inlining using the
original signatures that abstract interpretation used for union-split
inference, by using `match::MethodMatch`.

- fixes #53590
@vtjnash vtjnash reopened this Mar 7, 2024
aviatesk added a commit that referenced this issue Mar 7, 2024
@aviatesk
inlining: use method match signature for union-spliting (#53600)
caf97c3 
In cases where the results of constant inference, like concrete-eval,
are used for union-split inlining, `isa`-blocks are generated using the
`result.edge.specTypes` stored within each `result`. However, it's been
found that the `edge` returned by abstract interpretation may have been
widened by the new `@nospecializeinfer`, which can result in invalid
union-splitting. To address this problem, this commit tweaks the
inlining algorithm so that it performs union-split inlining using the
original signatures that abstract interpretation used for union-split
inference, by using `match::MethodMatch`.

- fixes #53590
@aviatesk
Copy link
Member

aviatesk commented Mar 8, 2024 •
edited
Loading

This particular issue has been fixed?

@vtjnash
Copy link
Member

vtjnash commented Mar 8, 2024

The linked PR seemed to fix the symptom but not the cause

@vtjnash
Copy link
Member

vtjnash commented Mar 8, 2024

Actually, it looks like this might have been a duplicate of #52644 reported earlier

@aviatesk
Copy link
Member

I think now the cause has been fixed.

mkitti pushed a commit to mkitti/julia that referenced this issue Apr 13, 2024
@aviatesk @mkitti
inlining: use method match signature for union-spliting (JuliaLang#53600
0472893 
)

In cases where the results of constant inference, like concrete-eval,
are used for union-split inlining, `isa`-blocks are generated using the
`result.edge.specTypes` stored within each `result`. However, it's been
found that the `edge` returned by abstract interpretation may have been
widened by the new `@nospecializeinfer`, which can result in invalid
union-splitting. To address this problem, this commit tweaks the
inlining algorithm so that it performs union-split inlining using the
original signatures that abstract interpretation used for union-split
inference, by using `match::MethodMatch`.

- fixes JuliaLang#53590
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@aviatesk aviatesk

Labels
compiler:optimizer Optimization passes (mostly in base/compiler/ssair/) regression Regression in behavior compared to a previous version
Projects
None yet
Milestone
1.11
Development

Successfully merging a pull request may close this issue.

inlining: use method match signature for union-spliting JuliaLang/julia
3 participants
@vtjnash @KristofferC @aviatesk