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.

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

bad inference edges being created sometime #49350

Closed
vtjnash opened this issue Apr 13, 2023 · 8 comments
Closed

bad inference edges being created sometime #49350

vtjnash opened this issue Apr 13, 2023 · 8 comments
Labels
compiler:inference Type inference compiler:latency Compiler latency

Comments

@vtjnash
Copy link
Member

vtjnash commented Apr 13, 2023

There seems to be MethodInstance edges created at some point with bad type information (while building OmniPackage), such as this one:

MethodInstance for convert(::Type, ::Tuple{Vararg{Symbol}}))

There should only be one method for this re-lookup, but obviously that fails quite badly when we try to go verify that fact in the cache. This is unnecessarily expensive. Why does it make that bad edge?

julia> methods(convert, (Type{<:Tuple}, Tuple{Vararg{Symbol}}))
convert(::Type{T}, x::Tuple{Vararg{Any, N}}) where {N, T<:Tuple}
     @ Base essentials.jl:451
@vtjnash vtjnash added compiler:inference Type inference compiler:latency Compiler latency labels Apr 13, 2023
@vtjnash
Copy link
Member Author

vtjnash commented Apr 14, 2023

There is a similar MethodInstance observed for (::Type{Base.IteratorSize})(Type) from Base.IteratorSize(::Type) @ generator.jl:94, which is sometimes making backedges also, even though this signature has >45 methods and therefore should not have edges created to it (it is merely a compilation signature, not the dispatch edge).

@vtjnash
Copy link
Member Author

vtjnash commented Apr 17, 2023

More similar bugs from inference:

 inserting cconvert(::Type{<:CUDA.CuArrayPtr}, x) @ CUDA ~/.julia/packages/CUDA/ZdCxS/src/pointer.jl:170 invalidated:
   mt_backedges: 1: signature cconvert(T::Type, x) @ Base essentials.jl:537 (formerly cconvert(T::Type, x) @ Base essentials.jl:537) triggered MethodInstance for Base.Unicode.utf8proc_decompose(::String, ::Int64, ::Vector{UInt8}, ::Int64, ::Function) (0 children)
                 2: signature cconvert(T::Type, x) @ Base essentials.jl:537 (formerly cconvert(T::Type, x) @ Base essentials.jl:537) triggered MethodInstance for Base.Unicode.utf8proc_decompose(::String, ::Int64, ::Ptr{Nothing}, ::Int64, ::Function) (0 children)
                 3: signature cconvert(T::Type, x) @ Base essentials.jl:537 (formerly cconvert(T::Type, x) @ Base essentials.jl:537) triggered MethodInstance for Parsers._widen(::T) where T<:Union{Int128, UInt128} (0 children)
   backedges: 1: superseding cconvert(T::Type, x) @ Base essentials.jl:537 with MethodInstance for Base.cconvert(::Type, ::Nothing) (3 children)
              2: superseding cconvert(T::Type, x) @ Base essentials.jl:537 with MethodInstance for Base.cconvert(::Type, ::Function) (110 children)

@gbaraldi
Copy link
Member

Could it be SnoopPrecompile doing something weird?

@vtjnash
Copy link
Member Author

vtjnash commented Apr 17, 2023

No, looks like at least some of this is a concrete-eval bug. For example, here's a what Cthulhu said about one of the calls:

 • %172 = call → cconvert(::Type{Cstring},::Union{Nothing, SubString{String}, String})::String
   %173 = unsafe_convert(::Type{Cstring},::String)::Cstring
v  %174 = cconvert(::Type{Int32},::Int64)::Int32

 • %172 = < concrete eval > cconvert(::Core.Const(Cstring),::Union{Nothing, SubString{String}, String})::String
   %172 = cconvert(::Type{Cstring},::SubString{String})::String
   %172 = cconvert(::Type{Cstring},::String)::String
   ↩
cconvert(T::Type, x) @ Base essentials.jl:537
Variables
  #self#::Core.Const(Base.cconvert)
  T::Core.Const(Cstring)
  x::Core.Const(nothing)

∘ ─ %0 = invoke cconvert(::Type{Cstring},::Nothing)::Union{}
    @ essentials.jl:537 within `cconvert`
1 ─     (x isa T)::Core.Const(false)
└──     goto #3
2 ─     Core.Const(:(return x))::Union{}
3 ┄     Base.convert(T, x)::Union{}
└──     Core.Const(:(return %4))::Union{}

Then we ended up with an edge to cconvert(::Type, ::Nothing), even though that was the wrong edge to record here.

@vtjnash
Copy link
Member Author

vtjnash commented Apr 17, 2023

Some of the Base.IteratorSize issues come from this sort of thing:

julia> trees[723]
inserting Base.IteratorSize(::Type{<:AxisArrays.Axis}) @ AxisArrays ~/.julia/packages/AxisArrays/v7vf4/src/core.jl:86 invalidated:
   backedges: 1: superseding Base.IteratorSize(::Type) @ Base generator.jl:94 with MethodInstance for Base.IteratorSize(::Type{<:AbstractString}) (26 children)
              2: superseding Base.IteratorSize(::Type) @ Base generator.jl:94 with MethodInstance for Base.IteratorSize(::Type{I} where I<:(Base.Pairs{Symbol, V, Tuple{Vararg{Symbol, N}}, NamedTuple{names, T}} where {V, N, names, T<:Tuple{Vararg{Any, N}}})) (117 children)
   18 mt_cache

julia> ans.backedges[1]
MethodInstance for Base.IteratorSize(::Type{<:AbstractString}) at depth 0 with 26 children

julia> ans.children
1-element Vector{SnoopCompile.InstanceNode}:
 MethodInstance for Base.IteratorSize(::AbstractString) at depth 1 with 25 children

julia> ans[1].children
6-element Vector{SnoopCompile.InstanceNode}:
 MethodInstance for collect(::Base.Generator{I, Makie.var"#756#757"{Int64}} where I<:AbstractString) at depth 2 with 9 children
 MethodInstance for collect(::Base.Generator{I, typeof(identity)} where I<:AbstractString) at depth 2 with 1 children
 MethodInstance for collect(::Base.Generator{I, Makie.var"#756#757"{Makie.Quaternionf}} where I<:AbstractString) at depth 2 with 3 children
 MethodInstance for collect(::Base.Generator{I, Makie.var"#756#757"{Float32}} where I<:AbstractString) at depth 2 with 2 children
 MethodInstance for collect(::Base.Generator{I, Makie.var"#758#759"{FreeTypeAbstraction.FTFont}} where I<:AbstractString) at depth 2 with 1 children
 MethodInstance for collect(::Base.Generator{I, Makie.var"#756#757"{ColorTypes.RGBA{Float32}}} where I<:AbstractString) at depth 2 with 3 children

@vtjnash
Copy link
Member Author

vtjnash commented Apr 18, 2023

I think #49404 will fix many of these. The rest likely come from recursion-limiting. I think backedge handling already could handle that case (where MethodInstance might be wider than the Method), but we don't yet have the equivalent code for staticdata_utils.c

@vtjnash
Copy link
Member Author

vtjnash commented Apr 18, 2023

Looking closer again now, we are losing this other edge too, because of the intersection with Type{Union{}} (though we haven't spent the cycles to compute and detect that)

 inserting Base.IteratorSize(::Type{<:AxisArrays.Axis}) @ AxisArrays ~/.julia/packages/AxisArrays/v7vf4/src/core.jl:86 invalidated:
   backedges: 1: superseding Base.IteratorSize(::Type) @ Base generator.jl:94 with MethodInstance for Base.IteratorSize(::Type{<:AbstractString}) (26 children)
              2: superseding Base.IteratorSize(::Type) @ Base generator.jl:94 with MethodInstance for Base.IteratorSize(::Type{I} where I<:(Base.Pairs{Symbol, V, Tuple{Vararg{Symbol, N}}, NamedTuple{names, T}} where {V, N, names, T<:Tuple{Vararg{Any, N}}})) (114 children)

vtjnash added a commit that referenced this issue Apr 19, 2023
Even if we have a new method that is more specific than the method it is
replacing, there still might exist an existing method that is more
specific than both which already covers their intersection.

An example of this pattern is adding
    Base.IteratorSize(::Type{<:NewType})
causing invalidations on
    Base.IteratorSize(::Type)
for specializations such as
    Base.IteratorSize(::Type{<:AbstractString})
even though the intersection of these is fully covered already by
    Base.IteratorSize(::Type{Union{}})
so our new method would never be selected there.

This won't detect ambiguities that already cover this intersection, but
that is why we are looking to move away from that pattern towards
explicit methods for detection in closer to O(n) instead of O(n^2): #49349.

Similarly, for this method, we were unnecessarily dropping it from the
MethodTable cache. This is not a significant latency problem (the cache
is cheap to rebuild), but it is also easy to avoid in the first place.

Refs #49350
vtjnash added a commit that referenced this issue Apr 20, 2023
Even if we have a new method that is more specific than the method it is
replacing, there still might exist an existing method that is more
specific than both which already covers their intersection.

An example of this pattern is adding
    Base.IteratorSize(::Type{<:NewType})
causing invalidations on
    Base.IteratorSize(::Type)
for specializations such as
    Base.IteratorSize(::Type{<:AbstractString})
even though the intersection of these is fully covered already by
    Base.IteratorSize(::Type{Union{}})
so our new method would never be selected there.

This won't detect ambiguities that already cover this intersection, but
that is why we are looking to move away from that pattern towards
explicit methods for detection in closer to O(n) instead of O(n^2): #49349.

Similarly, for this method, we were unnecessarily dropping it from the
MethodTable cache. This is not a significant latency problem (the cache
is cheap to rebuild), but it is also easy to avoid in the first place.

Refs #49350
@vtjnash
Copy link
Member Author

vtjnash commented Aug 16, 2024

Concrete-eval returning incorrect and bad edges will be fixed by #54894, since it will then be impossible for concrete-eval to record edges. That code is not supposed to have edges anyways, as that violates the knowledge we had of the completeness of the prior inference to conclude that the return is consistent.

@vtjnash vtjnash closed this as completed Aug 16, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler:inference Type inference compiler:latency Compiler latency
Projects
None yet
Development

No branches or pull requests

2 participants