#38052

Committed 25 Apr 2025 04:34PM UTC coverage: 25.765% (-0.002%) from 25.767%

Build # #38052

Build Type

push

local

Committed by

web-flow

Commit Message

optimize Type method table queries and insertions (#58216)

Ensure a total split of constructors and non-constructors, so they do
not end up seaching the opposing table. Instead cache all kind lookups
as keyed by typename(Type). Not really needed on its own, but it avoids
a minor performance regression in
https://github.com/JuliaLang/julia/pull/58131.

Run Details

0 of 1 new or added line in 1 file covered. (0.0%)

479 existing lines in 3 files now uncovered.

12885 of 50010 relevant lines covered (25.76%)

1078891.92 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

19.55

/base/staticdata.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

module StaticData

using .Core: CodeInstance, MethodInstance
using .Base: JLOptions, Compiler, get_world_counter, _methods_by_ftype, get_methodtable

const WORLD_AGE_REVALIDATION_SENTINEL::UInt = 1
const _jl_debug_method_invalidation = Ref{Union{Nothing,Vector{Any}}}(nothing)
debug_method_invalidation(onoff::Bool) =
    _jl_debug_method_invalidation[] = onoff ? Any[] : nothing

function get_ci_mi(codeinst::CodeInstance)
    def = codeinst.def
    if def isa Core.ABIOverride
        return def.def
    else
        return def::MethodInstance
    end
end

# Restore backedges to external targets
# `edges` = [caller1, ...], the list of worklist-owned code instances internally
# `ext_ci_list` = [caller1, ...], the list of worklist-owned code instances externally
function insert_backedges(edges::Vector{Any}, ext_ci_list::Union{Nothing,Vector{Any}}, extext_methods::Vector{Any}, internal_methods::Vector{Any})
    # determine which CodeInstance objects are still valid in our image
    # to enable any applicable new codes
    backedges_only = unsafe_load(cglobal(:jl_first_image_replacement_world, UInt)) == typemax(UInt)
    methods_with_invalidated_source = Base.scan_new_methods(extext_methods, internal_methods, backedges_only)
    stack = CodeInstance[]
    visiting = IdDict{CodeInstance,Int}()
    _insert_backedges(edges, stack, visiting, methods_with_invalidated_source)
    if ext_ci_list !== nothing
        _insert_backedges(ext_ci_list, stack, visiting, methods_with_invalidated_source, #=external=#true)
    end
end

function _insert_backedges(edges::Vector{Any}, stack::Vector{CodeInstance}, visiting::IdDict{CodeInstance,Int}, mwis::IdSet{Method}, external::Bool=false)
    for i = 1:length(edges)
        codeinst = edges[i]::CodeInstance
        validation_world = get_world_counter()
        verify_method_graph(codeinst, stack, visiting, mwis, validation_world)
        # After validation, under the world_counter_lock, set max_world to typemax(UInt) for all dependencies
        # (recursively). From that point onward the ordinary backedge mechanism is responsible for maintaining
        # validity.
        @ccall jl_promote_ci_to_current(codeinst::Any, validation_world::UInt)::Cvoid
        minvalid = codeinst.min_world
        maxvalid = codeinst.max_world
        # Finally, if this CI is still valid in some world age and and belongs to an external method(specialization),
        # poke it that mi's cache
        if maxvalid ≥ minvalid && external
            caller = get_ci_mi(codeinst)
            @assert isdefined(codeinst, :inferred) # See #53586, #53109
            inferred = @ccall jl_rettype_inferred(
                codeinst.owner::Any, caller::Any, minvalid::UInt, maxvalid::UInt)::Any
            if inferred !== nothing
                # We already got a code instance for this world age range from
                # somewhere else - we don't need this one.
            else
                @ccall jl_mi_cache_insert(caller::Any, codeinst::Any)::Cvoid
            end
        end
    end
end

function verify_method_graph(codeinst::CodeInstance, stack::Vector{CodeInstance}, visiting::IdDict{CodeInstance,Int}, mwis::IdSet{Method}, validation_world::UInt)
    @assert isempty(stack); @assert isempty(visiting);
    child_cycle, minworld, maxworld = verify_method(codeinst, stack, visiting, mwis, validation_world)
    @assert child_cycle == 0
    @assert isempty(stack); @assert isempty(visiting);
    nothing
end

get_require_world() = unsafe_load(cglobal(:jl_require_world, UInt))

function gen_staged_sig(def::Method, mi::MethodInstance)
    isdefined(def, :generator) || return nothing
    isdispatchtuple(mi.specTypes) || return nothing
    gen = Core.Typeof(def.generator)
    return Tuple{gen, UInt, Method, Vararg}
    ## more precise method lookup, but more costly and likely not actually better?
    #tts = (mi.specTypes::DataType).parameters
    #sps = Any[Core.Typeof(mi.sparam_vals[i]) for i in 1:length(mi.sparam_vals)]
    #if def.isva
    #    return Tuple{gen, UInt, Method, sps..., tts[1:def.nargs - 1]..., Tuple{tts[def.nargs - 1:end]...}}
    #else
    #    return Tuple{gen, UInt, Method, sps..., tts...}
    #end
end

function needs_instrumentation(codeinst::CodeInstance, mi::MethodInstance, def::Method, validation_world::UInt)
    if JLOptions().code_coverage != 0 || JLOptions().malloc_log != 0
        # test if the code needs to run with instrumentation, in which case we cannot use existing generated code
        if isdefined(def, :debuginfo) ? # generated_only functions do not have debuginfo, so fall back to considering their codeinst debuginfo though this may be slower (and less accurate?)
            Compiler.should_instrument(def.module, def.debuginfo) :
            Compiler.should_instrument(def.module, codeinst.debuginfo)
            return true
        end
        gensig = gen_staged_sig(def, mi)
        if gensig !== nothing
            # if this is defined by a generator, try to consider forcing re-running the generators too, to add coverage for them
            minworld = Ref{UInt}(1)
            maxworld = Ref{UInt}(typemax(UInt))
            has_ambig = Ref{Int32}(0)
            result = _methods_by_ftype(gensig, nothing, -1, validation_world, #=ambig=#false, minworld, maxworld, has_ambig)
            if result !== nothing
                for k = 1:length(result)
                    match = result[k]::Core.MethodMatch
                    genmethod = match.method
                    # no, I refuse to refuse to recurse into your cursed generated function generators and will only test one level deep here
                    if isdefined(genmethod, :debuginfo) && Compiler.should_instrument(genmethod.module, genmethod.debuginfo)
                        return true
                    end
                end
            end
        end
    end
    return false
end

# Test all edges relevant to a method:
# - Visit the entire call graph, starting from edges[idx] to determine if that method is valid
# - Implements Tarjan's SCC (strongly connected components) algorithm, simplified to remove the count variable
#   and slightly modified with an early termination option once the computation reaches its minimum
function verify_method(codeinst::CodeInstance, stack::Vector{CodeInstance}, visiting::IdDict{CodeInstance,Int}, mwis::IdSet{Method}, validation_world::UInt)
    world = codeinst.min_world
    let max_valid2 = codeinst.max_world
        if max_valid2 ≠ WORLD_AGE_REVALIDATION_SENTINEL
            return 0, world, max_valid2
        end
    end
    mi = get_ci_mi(codeinst)
    def = mi.def::Method
    if needs_instrumentation(codeinst, mi, def, validation_world)
        return 0, world, UInt(0)
    end

    # Implicitly referenced bindings in the current module do not get explicit edges.
    # If they were invalidated, they'll be in `mwis`. If they weren't, they imply a minworld
    # of `get_require_world`. In principle, this is only required for methods that do reference
    # an implicit globalref. However, we already don't perform this validation for methods that
    # don't have any (implicit or explicit) edges at all. The remaining corner case (some explicit,
    # but no implicit edges) is rare and there would be little benefit to lower the minworld for it
    # in any case, so we just always use `get_require_world` here.
    local minworld::UInt, maxworld::UInt = get_require_world(), validation_world
    if haskey(visiting, codeinst)
        return visiting[codeinst], minworld, maxworld
    end
    push!(stack, codeinst)
    depth = length(stack)
    visiting[codeinst] = depth
    # TODO JL_TIMING(VERIFY_IMAGE, VERIFY_Methods)
    callees = codeinst.edges
    # Check for invalidation of the implicit edges from GlobalRef in the Method source
    if def in mwis
        maxworld = 0
        invalidations = _jl_debug_method_invalidation[]
        if invalidations !== nothing
            push!(invalidations, def, "method_globalref", codeinst, nothing)
        end
    end
    # verify current edges
    if isempty(callees)
        # quick return: no edges to verify (though we probably shouldn't have gotten here from WORLD_AGE_REVALIDATION_SENTINEL)
    elseif maxworld == get_require_world()
        # if no new worlds were allocated since serializing the base module, then no new validation is worth doing right now either
    else
        j = 1
        while j ≤ length(callees)
            local min_valid2::UInt, max_valid2::UInt
            edge = callees[j]
            @assert !(edge isa Method) # `Method`-edge isn't allowed for the optimized one-edge format
            if edge isa CodeInstance
                edge = get_ci_mi(edge)
            end
            if edge isa MethodInstance
                sig = edge.specTypes
                min_valid2, max_valid2, matches = verify_call(sig, callees, j, 1, world)
                j += 1
            elseif edge isa Int
                sig = callees[j+1]
                min_valid2, max_valid2, matches = verify_call(sig, callees, j+2, edge, world)
                j += 2 + edge
                edge = sig
            elseif edge isa Core.Binding
                j += 1
                min_valid2 = minworld
                max_valid2 = maxworld
                if !Base.binding_was_invalidated(edge)
                    if isdefined(edge, :partitions)
                        min_valid2 = edge.partitions.min_world
                        max_valid2 = edge.partitions.max_world
                    end
                else
                    # Binding was previously invalidated
                    min_valid2 = 1
                    max_valid2 = 0
                end
                matches = nothing
            else
                callee = callees[j+1]
                if callee isa Core.MethodTable # skip the legacy edge (missing backedge)
                    j += 2
                    continue
                end
                if callee isa CodeInstance
                    callee = get_ci_mi(callee)
                end
                if callee isa MethodInstance
                    meth = callee.def::Method
                else
                    meth = callee::Method
                end
                min_valid2, max_valid2, matches = verify_invokesig(edge, meth, world)
                j += 2
            end
            if minworld < min_valid2
                minworld = min_valid2
            end
            if maxworld > max_valid2
                maxworld = max_valid2
            end
            invalidations = _jl_debug_method_invalidation[]
            if max_valid2 ≠ typemax(UInt) && invalidations !== nothing
                push!(invalidations, edge, "insert_backedges_callee", codeinst, matches)
            end
            if max_valid2 == 0 && invalidations === nothing
                break
            end
        end
    end
    # verify recursive edges (if valid, or debugging)
    cycle = depth
    cause = codeinst
    if maxworld ≠ 0 || _jl_debug_method_invalidation[] !== nothing
        for j = 1:length(callees)
            edge = callees[j]
            if !(edge isa CodeInstance)
                continue
            end
            callee = edge
            local min_valid2::UInt, max_valid2::UInt
            child_cycle, min_valid2, max_valid2 = verify_method(callee, stack, visiting, mwis, validation_world)
            if minworld < min_valid2
                minworld = min_valid2
            end
            if minworld > max_valid2
                max_valid2 = 0
            end
            if maxworld > max_valid2
                cause = callee
                maxworld = max_valid2
            end
            if max_valid2 == 0
                # found what we were looking for, so terminate early
                break
            elseif child_cycle ≠ 0 && child_cycle < cycle
                # record the cycle will resolve at depth "cycle"
                cycle = child_cycle
            end
        end
    end
    if maxworld ≠ 0 && cycle ≠ depth
        return cycle, minworld, maxworld
    end
    # If we are the top of the current cycle, now mark all other parts of
    # our cycle with what we found.
    # Or if we found a failed edge, also mark all of the other parts of the
    # cycle as also having a failed edge.
    while length(stack) ≥ depth
        child = pop!(stack)
        if maxworld ≠ 0
            @atomic :monotonic child.min_world = minworld
        end
        @atomic :monotonic child.max_world = maxworld
        if maxworld == validation_world && validation_world == get_world_counter()
            Compiler.store_backedges(child, child.edges)
        end
        @assert visiting[child] == length(stack) + 1
        delete!(visiting, child)
        invalidations = _jl_debug_method_invalidation[]
        if invalidations !== nothing && maxworld < validation_world
            push!(invalidations, child, "verify_methods", cause)
        end
    end
    return 0, minworld, maxworld
end

function verify_call(@nospecialize(sig), expecteds::Core.SimpleVector, i::Int, n::Int, world::UInt)
    # verify that these edges intersect with the same methods as before
    lim = _jl_debug_method_invalidation[] !== nothing ? Int(typemax(Int32)) : n
    minworld = Ref{UInt}(1)
    maxworld = Ref{UInt}(typemax(UInt))
    has_ambig = Ref{Int32}(0)
    result = _methods_by_ftype(sig, nothing, lim, world, #=ambig=#false, minworld, maxworld, has_ambig)
    if result === nothing
        maxworld[] = 0
    else
        # setdiff!(result, expected)
        if length(result) ≠ n
            maxworld[] = 0
        end
        ins = 0
        for k = 1:length(result)
            match = result[k]::Core.MethodMatch
            local found = false
            for j = 1:n
                t = expecteds[i+j-1]
                if t isa Method
                    meth = t
                else
                    if t isa CodeInstance
                        t = get_ci_mi(t)
                    else
                        t = t::MethodInstance
                    end
                    meth = t.def::Method
                end
                if match.method == meth
                    found = true
                    break
                end
            end
            if !found
                # intersection has a new method or a method was
                # deleted--this is now probably no good, just invalidate
                # everything about it now
                maxworld[] = 0
                if _jl_debug_method_invalidation[] === nothing
                    break
                end
                ins += 1
                result[ins] = match.method
            end
        end
        if maxworld[] ≠ typemax(UInt) && _jl_debug_method_invalidation[] !== nothing
            resize!(result, ins)
        end
    end
    return minworld[], maxworld[], result
end

function verify_invokesig(@nospecialize(invokesig), expected::Method, world::UInt)
    @assert invokesig isa Type
    local minworld::UInt, maxworld::UInt
    matched = nothing
    if invokesig === expected.sig
        # the invoke match is `expected` for `expected->sig`, unless `expected` is invalid
        # TODO: this is broken since PR #53415
        minworld = expected.primary_world
        maxworld = expected.deleted_world
        @assert minworld ≤ world
        if maxworld < world
            maxworld = 0
        end
    else
        minworld = 1
        maxworld = typemax(UInt)
        mt = get_methodtable(expected)
        if mt === nothing
            maxworld = 0
        else
            matched, valid_worlds = Compiler._findsup(invokesig, mt, world)
            minworld, maxworld = valid_worlds.min_world, valid_worlds.max_world
            if matched === nothing
                maxworld = 0
            else
                matched = Any[matched.method]
                if matched[] !== expected
                    maxworld = 0
                end
            end
        end
    end
    return minworld, maxworld, matched
end

end # module StaticData

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	module StaticData
4
5	using .Core: CodeInstance, MethodInstance
6	using .Base: JLOptions, Compiler, get_world_counter, _methods_by_ftype, get_methodtable
7
8	const WORLD_AGE_REVALIDATION_SENTINEL::UInt = 1
9	const _jl_debug_method_invalidation = Ref{Union{Nothing,Vector{Any}}}(nothing)
10	debug_method_invalidation(onoff::Bool) =	×
11	_jl_debug_method_invalidation[] = onoff ? Any[] : nothing
12
13	function get_ci_mi(codeinst::CodeInstance)
14	def = codeinst.def	18,366✔
15	if def isa Core.ABIOverride	18,366✔
16	return def.def	×
17	else
18	return def::MethodInstance	18,366✔
19	end
20	end
21
22	# Restore backedges to external targets
23	# `edges` = [caller1, ...], the list of worklist-owned code instances internally
24	# `ext_ci_list` = [caller1, ...], the list of worklist-owned code instances externally
25	function insert_backedges(edges::Vector{Any}, ext_ci_list::Union{Nothing,Vector{Any}}, extext_methods::Vector{Any}, internal_methods::Vector{Any})
26	# determine which CodeInstance objects are still valid in our image
27	# to enable any applicable new codes
28	backedges_only = unsafe_load(cglobal(:jl_first_image_replacement_world, UInt)) == typemax(UInt)	38✔
29	methods_with_invalidated_source = Base.scan_new_methods(extext_methods, internal_methods, backedges_only)	38✔
30	stack = CodeInstance[]	38✔
31	visiting = IdDict{CodeInstance,Int}()	38✔
32	_insert_backedges(edges, stack, visiting, methods_with_invalidated_source)	38✔
33	if ext_ci_list !== nothing	×
34	_insert_backedges(ext_ci_list, stack, visiting, methods_with_invalidated_source, #=external=#true)	38✔
35	end
36	end
37
38	function _insert_backedges(edges::Vector{Any}, stack::Vector{CodeInstance}, visiting::IdDict{CodeInstance,Int}, mwis::IdSet{Method}, external::Bool=false)	36✔
39	for i = 1:length(edges)	74✔
40	codeinst = edges[i]::CodeInstance	18,366✔
41	validation_world = get_world_counter()	18,366✔
42	verify_method_graph(codeinst, stack, visiting, mwis, validation_world)	18,366✔
43	# After validation, under the world_counter_lock, set max_world to typemax(UInt) for all dependencies
44	# (recursively). From that point onward the ordinary backedge mechanism is responsible for maintaining
45	# validity.
46	@ccall jl_promote_ci_to_current(codeinst::Any, validation_world::UInt)::Cvoid	18,366✔
47	minvalid = codeinst.min_world	18,366✔
48	maxvalid = codeinst.max_world	18,366✔
49	# Finally, if this CI is still valid in some world age and and belongs to an external method(specialization),
50	# poke it that mi's cache
51	if maxvalid ≥ minvalid && external	18,366✔
52	caller = get_ci_mi(codeinst)	2,290✔
53	@assert isdefined(codeinst, :inferred) # See #53586, #53109	1,145✔
54	inferred = @ccall jl_rettype_inferred(	1,145✔
55	codeinst.owner::Any, caller::Any, minvalid::UInt, maxvalid::UInt)::Any
56	if inferred !== nothing	1,145✔
57	# We already got a code instance for this world age range from
58	# somewhere else - we don't need this one.
59	else
60	@ccall jl_mi_cache_insert(caller::Any, codeinst::Any)::Cvoid	1,145✔
61	end
62	end
63	end	18,366✔
64	end
65
66	function verify_method_graph(codeinst::CodeInstance, stack::Vector{CodeInstance}, visiting::IdDict{CodeInstance,Int}, mwis::IdSet{Method}, validation_world::UInt)	18,366✔
67	@assert isempty(stack); @assert isempty(visiting);	18,366✔
68	child_cycle, minworld, maxworld = verify_method(codeinst, stack, visiting, mwis, validation_world)	18,366✔
69	@assert child_cycle == 0	18,366✔
70	@assert isempty(stack); @assert isempty(visiting);	18,366✔
71	nothing	18,366✔
72	end
73
74	get_require_world() = unsafe_load(cglobal(:jl_require_world, UInt))	×
75
76	function gen_staged_sig(def::Method, mi::MethodInstance)
77	isdefined(def, :generator) \|\| return nothing	×
78	isdispatchtuple(mi.specTypes) \|\| return nothing	×
79	gen = Core.Typeof(def.generator)	×
80	return Tuple{gen, UInt, Method, Vararg}	×
81	## more precise method lookup, but more costly and likely not actually better?
82	#tts = (mi.specTypes::DataType).parameters
83	#sps = Any[Core.Typeof(mi.sparam_vals[i]) for i in 1:length(mi.sparam_vals)]
84	#if def.isva
85	# return Tuple{gen, UInt, Method, sps..., tts[1:def.nargs - 1]..., Tuple{tts[def.nargs - 1:end]...}}
86	#else
87	# return Tuple{gen, UInt, Method, sps..., tts...}
88	#end
89	end
90
91	function needs_instrumentation(codeinst::CodeInstance, mi::MethodInstance, def::Method, validation_world::UInt)	17,221✔
92	if JLOptions().code_coverage != 0 \|\| JLOptions().malloc_log != 0	17,221✔
93	# test if the code needs to run with instrumentation, in which case we cannot use existing generated code
94	if isdefined(def, :debuginfo) ? # generated_only functions do not have debuginfo, so fall back to considering their codeinst debuginfo though this may be slower (and less accurate?)	17,221✔
95	Compiler.should_instrument(def.module, def.debuginfo) :
96	Compiler.should_instrument(def.module, codeinst.debuginfo)
97	return true	17,221✔
98	end
99	gensig = gen_staged_sig(def, mi)	×
100	if gensig !== nothing	×
101	# if this is defined by a generator, try to consider forcing re-running the generators too, to add coverage for them
102	minworld = Ref{UInt}(1)	×
103	maxworld = Ref{UInt}(typemax(UInt))	×
104	has_ambig = Ref{Int32}(0)	×
105	result = _methods_by_ftype(gensig, nothing, -1, validation_world, #=ambig=#false, minworld, maxworld, has_ambig)	×
106	if result !== nothing	×
107	for k = 1:length(result)	×
108	match = result[k]::Core.MethodMatch	×
109	genmethod = match.method	×
110	# no, I refuse to refuse to recurse into your cursed generated function generators and will only test one level deep here
111	if isdefined(genmethod, :debuginfo) && Compiler.should_instrument(genmethod.module, genmethod.debuginfo)	×
112	return true	×
113	end
114	end	×
115	end
116	end
117	end
118	return false	×
119	end
120
121	# Test all edges relevant to a method:
122	# - Visit the entire call graph, starting from edges[idx] to determine if that method is valid
123	# - Implements Tarjan's SCC (strongly connected components) algorithm, simplified to remove the count variable
124	# and slightly modified with an early termination option once the computation reaches its minimum
125	function verify_method(codeinst::CodeInstance, stack::Vector{CodeInstance}, visiting::IdDict{CodeInstance,Int}, mwis::IdSet{Method}, validation_world::UInt)	18,366✔
126	world = codeinst.min_world	18,366✔
127	let max_valid2 = codeinst.max_world	18,366✔
128	if max_valid2 ≠ WORLD_AGE_REVALIDATION_SENTINEL	18,366✔
129	return 0, world, max_valid2	1,145✔
130	end
131	end
132	mi = get_ci_mi(codeinst)	34,442✔
133	def = mi.def::Method	17,221✔
134	if needs_instrumentation(codeinst, mi, def, validation_world)	17,221✔
135	return 0, world, UInt(0)	17,221✔
136	end
137
138	# Implicitly referenced bindings in the current module do not get explicit edges.
139	# If they were invalidated, they'll be in `mwis`. If they weren't, they imply a minworld
140	# of `get_require_world`. In principle, this is only required for methods that do reference
141	# an implicit globalref. However, we already don't perform this validation for methods that
142	# don't have any (implicit or explicit) edges at all. The remaining corner case (some explicit,
143	# but no implicit edges) is rare and there would be little benefit to lower the minworld for it
144	# in any case, so we just always use `get_require_world` here.
145	local minworld::UInt, maxworld::UInt = get_require_world(), validation_world	×
146	if haskey(visiting, codeinst)	×
147	return visiting[codeinst], minworld, maxworld	×
148	end
149	push!(stack, codeinst)	×
150	depth = length(stack)	×
151	visiting[codeinst] = depth	×
152	# TODO JL_TIMING(VERIFY_IMAGE, VERIFY_Methods)
153	callees = codeinst.edges	×
154	# Check for invalidation of the implicit edges from GlobalRef in the Method source
155	if def in mwis	×
156	maxworld = 0	×
157	invalidations = _jl_debug_method_invalidation[]	×
158	if invalidations !== nothing	×
159	push!(invalidations, def, "method_globalref", codeinst, nothing)	×
160	end
161	end
162	# verify current edges
163	if isempty(callees)	×
164	# quick return: no edges to verify (though we probably shouldn't have gotten here from WORLD_AGE_REVALIDATION_SENTINEL)
165	elseif maxworld == get_require_world()	×
166	# if no new worlds were allocated since serializing the base module, then no new validation is worth doing right now either
167	else
168	j = 1	×
169	while j ≤ length(callees)	×
170	local min_valid2::UInt, max_valid2::UInt	×
171	edge = callees[j]	×
172	@assert !(edge isa Method) # `Method`-edge isn't allowed for the optimized one-edge format	×
173	if edge isa CodeInstance	×
174	edge = get_ci_mi(edge)	×
175	end
176	if edge isa MethodInstance	×
NEW 177	sig = edge.specTypes	×
178	min_valid2, max_valid2, matches = verify_call(sig, callees, j, 1, world)	×
179	j += 1	×
180	elseif edge isa Int	×
181	sig = callees[j+1]	×
182	min_valid2, max_valid2, matches = verify_call(sig, callees, j+2, edge, world)	×
183	j += 2 + edge	×
184	edge = sig	×
185	elseif edge isa Core.Binding	×
186	j += 1	×
187	min_valid2 = minworld	×
188	max_valid2 = maxworld	×
189	if !Base.binding_was_invalidated(edge)	×
190	if isdefined(edge, :partitions)	×
191	min_valid2 = edge.partitions.min_world	×
192	max_valid2 = edge.partitions.max_world	×
193	end
194	else
195	# Binding was previously invalidated
196	min_valid2 = 1	×
197	max_valid2 = 0	×
198	end
199	matches = nothing	×
200	else
201	callee = callees[j+1]	×
202	if callee isa Core.MethodTable # skip the legacy edge (missing backedge)	×
203	j += 2	×
204	continue	×
205	end
206	if callee isa CodeInstance	×
207	callee = get_ci_mi(callee)	×
208	end
209	if callee isa MethodInstance	×
210	meth = callee.def::Method	×
211	else
212	meth = callee::Method	×
213	end
214	min_valid2, max_valid2, matches = verify_invokesig(edge, meth, world)	×
215	j += 2	×
216	end
217	if minworld < min_valid2	×
218	minworld = min_valid2	×
219	end
220	if maxworld > max_valid2	×
221	maxworld = max_valid2	×
222	end
223	invalidations = _jl_debug_method_invalidation[]	×
224	if max_valid2 ≠ typemax(UInt) && invalidations !== nothing	×
225	push!(invalidations, edge, "insert_backedges_callee", codeinst, matches)	×
226	end
227	if max_valid2 == 0 && invalidations === nothing	×
228	break	×
229	end
230	end	×
231	end
232	# verify recursive edges (if valid, or debugging)
233	cycle = depth	×
234	cause = codeinst	×
235	if maxworld ≠ 0 \|\| _jl_debug_method_invalidation[] !== nothing	×
236	for j = 1:length(callees)	×
237	edge = callees[j]	×
238	if !(edge isa CodeInstance)	×
239	continue	×
240	end
241	callee = edge	×
242	local min_valid2::UInt, max_valid2::UInt
243	child_cycle, min_valid2, max_valid2 = verify_method(callee, stack, visiting, mwis, validation_world)	×
244	if minworld < min_valid2	×
245	minworld = min_valid2	×
246	end
247	if minworld > max_valid2	×
248	max_valid2 = 0	×
249	end
250	if maxworld > max_valid2	×
251	cause = callee	×
252	maxworld = max_valid2	×
253	end
254	if max_valid2 == 0	×
255	# found what we were looking for, so terminate early
256	break	×
257	elseif child_cycle ≠ 0 && child_cycle < cycle	×
258	# record the cycle will resolve at depth "cycle"
259	cycle = child_cycle	×
260	end
261	end	×
262	end
263	if maxworld ≠ 0 && cycle ≠ depth	×
264	return cycle, minworld, maxworld	×
265	end
266	# If we are the top of the current cycle, now mark all other parts of
267	# our cycle with what we found.
268	# Or if we found a failed edge, also mark all of the other parts of the
269	# cycle as also having a failed edge.
270	while length(stack) ≥ depth	×
271	child = pop!(stack)	×
272	if maxworld ≠ 0	×
273	@atomic :monotonic child.min_world = minworld	×
274	end
275	@atomic :monotonic child.max_world = maxworld	×
276	if maxworld == validation_world && validation_world == get_world_counter()	×
277	Compiler.store_backedges(child, child.edges)	×
278	end
279	@assert visiting[child] == length(stack) + 1	×
280	delete!(visiting, child)	×
281	invalidations = _jl_debug_method_invalidation[]	×
282	if invalidations !== nothing && maxworld < validation_world	×
283	push!(invalidations, child, "verify_methods", cause)	×
284	end
285	end	×
286	return 0, minworld, maxworld	×
287	end
288
289	function verify_call(@nospecialize(sig), expecteds::Core.SimpleVector, i::Int, n::Int, world::UInt)
290	# verify that these edges intersect with the same methods as before
291	lim = _jl_debug_method_invalidation[] !== nothing ? Int(typemax(Int32)) : n	×
292	minworld = Ref{UInt}(1)	×
293	maxworld = Ref{UInt}(typemax(UInt))	×
294	has_ambig = Ref{Int32}(0)	×
295	result = _methods_by_ftype(sig, nothing, lim, world, #=ambig=#false, minworld, maxworld, has_ambig)	×
296	if result === nothing	×
297	maxworld[] = 0	×
298	else
299	# setdiff!(result, expected)
300	if length(result) ≠ n	×
301	maxworld[] = 0	×
302	end
303	ins = 0	×
304	for k = 1:length(result)	×
305	match = result[k]::Core.MethodMatch	×
306	local found = false	×
307	for j = 1:n	×
308	t = expecteds[i+j-1]	×
309	if t isa Method	×
310	meth = t	×
311	else
312	if t isa CodeInstance	×
313	t = get_ci_mi(t)	×
314	else
315	t = t::MethodInstance	×
316	end
317	meth = t.def::Method	×
318	end
319	if match.method == meth	×
320	found = true	×
321	break	×
322	end
323	end	×
324	if !found	×
325	# intersection has a new method or a method was
326	# deleted--this is now probably no good, just invalidate
327	# everything about it now
328	maxworld[] = 0	×
329	if _jl_debug_method_invalidation[] === nothing	×
330	break	×
331	end
332	ins += 1	×
333	result[ins] = match.method	×
334	end
335	end	×
336	if maxworld[] ≠ typemax(UInt) && _jl_debug_method_invalidation[] !== nothing	×
337	resize!(result, ins)	×
338	end
339	end
340	return minworld[], maxworld[], result	×
341	end
342
343	function verify_invokesig(@nospecialize(invokesig), expected::Method, world::UInt)
344	@assert invokesig isa Type	×
345	local minworld::UInt, maxworld::UInt
346	matched = nothing	×
347	if invokesig === expected.sig	×
348	# the invoke match is `expected` for `expected->sig`, unless `expected` is invalid
349	# TODO: this is broken since PR #53415
350	minworld = expected.primary_world	×
351	maxworld = expected.deleted_world	×
352	@assert minworld ≤ world	×
353	if maxworld < world	×
354	maxworld = 0	×
355	end
356	else
357	minworld = 1	×
358	maxworld = typemax(UInt)	×
359	mt = get_methodtable(expected)	×
360	if mt === nothing	×
361	maxworld = 0	×
362	else
363	matched, valid_worlds = Compiler._findsup(invokesig, mt, world)	×
364	minworld, maxworld = valid_worlds.min_world, valid_worlds.max_world	×
365	if matched === nothing	×
366	maxworld = 0	×
367	else
368	matched = Any[matched.method]	×
369	if matched[] !== expected	×
370	maxworld = 0	×
371	end
372	end
373	end
374	end
375	return minworld, maxworld, matched	×
376	end
377
378	end # module StaticData

JuliaLang / julia / #38052

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous