Compiler/src/typeinfer.jl - master - githubmirror/julia

Compiler/src/typeinfer.jl
2 278 строк98 KB
Keno Fischer
compiler: Separate local inference proofs from code instances (#62359)
05 авг 2026, 07:29
05 авг 2026, 07:29311f373
# This file is a part of Julia. License is MIT: https://julialang.org/license

"""
The module `Core.Compiler.Timings` provides a simple implementation of nested timers that
can be used to measure the exclusive time spent inferring each method instance that is
recursively inferred during type inference.

This is meant to be internal to the compiler, and makes some specific assumptions about
being used for this purpose alone.
"""
module Timings

using ..Core
using ..Compiler: -, +, :, Vector, length, first, empty!, push!, pop!, @inline,
    @inbounds, copy, backtrace, _time_ns

# What we record for any given frame we infer during type inference.
struct InferenceFrameInfo
    mi::Core.MethodInstance
    sptypes::Vector{Compiler.VarState}
    slottypes::Vector{Any}
    nargs::Int
end

function _typeinf_identifier(frame::Compiler.InferenceState)
    mi_info = InferenceFrameInfo(
        frame.linfo,
        copy(frame.sptypes),
        copy(frame.slottypes),
        length(frame.result.argtypes),
    )
    return mi_info
end

_typeinf_identifier(frame::InferenceFrameInfo) = frame

"""
    Compiler.Timing(mi_info, start_time, ...)

Internal type containing the timing result for running type inference on a single
MethodInstance.
"""
struct Timing
    mi_info::InferenceFrameInfo
    start_time::UInt64
    cur_start_time::UInt64
    time::UInt64
    children::Core.Array{Timing,1}
    bt         # backtrace collected upon initial entry to typeinf
end
Timing(mi_info, start_time, cur_start_time, time, children) = Timing(mi_info, start_time, cur_start_time, time, children, nothing)
Timing(mi_info, start_time) = Timing(mi_info, start_time, start_time, UInt64(0), Timing[])

# We keep a stack of the Timings for each of the MethodInstances currently being timed.
# Since type inference currently operates via a depth-first search (during abstract
# evaluation), this vector operates like a call stack. The last node in _timings is the
# node currently being inferred, and its parent is directly before it, etc.
# Each Timing also contains its own vector for all of its children, so that the tree
# call structure through type inference is recorded. (It's recorded as a tree, not a graph,
# because we create a new node for duplicates.)
const _timings = Timing[]
# ROOT() is an empty function used as the top-level Timing node to measure all time spent
# *not* in type inference during a given recording trace. It is used as a "dummy" node.
function ROOT() end
const ROOTmi = Compiler.specialize_method(
    first(Compiler.methods(ROOT)), Tuple{typeof(ROOT)}, Core.svec())
"""
    Compiler.reset_timings()

Empty out the previously recorded type inference timings (`Compiler._timings`), and
start the ROOT() timer again. `ROOT()` measures all time spent _outside_ inference.
"""
function reset_timings() end
push!(_timings, Timing(
    # The MethodInstance for ROOT(), and default empty values for other fields.
    InferenceFrameInfo(ROOTmi, Compiler.VarState[], Any[Core.Const(ROOT)], 1),
    _time_ns()))
function close_current_timer() end
function enter_new_timer(frame) end
function exit_current_timer(_expected_frame_) end

end  # module Timings

"""
    Compiler.__set_measure_typeinf(onoff::Bool)

If set to `true`, record per-method-instance timings within type inference in the Compiler.
"""
__set_measure_typeinf(onoff::Bool) = __measure_typeinf__[] = onoff
const __measure_typeinf__ = RefValue{Bool}(false)

function internal_result_edges(caller::InferenceState)
    result = caller.result
    opt = result.src
    if isa(opt, OptimizationState)
        return opt.inlining.edges
    else
        return caller.edges
    end
end

result_edges(::AbstractInterpreter, caller::InferenceState) =
    materialize_inference_edges(internal_result_edges(caller))

function finish!(interp::AbstractInterpreter, caller::InferenceState, validation_world::UInt, time_before::UInt64)
    result = caller.result
    valid_worlds = caller.valid_worlds
    min_world, max_world = first(valid_worlds), last(valid_worlds)
    result.valid_worlds = valid_worlds
    caller.src.min_world = min_world
    caller.src.max_world = max_world
    if isdefined(result, :ci)
        edges = result_edges(interp, caller)
        #@assert max_world <= get_world_counter() || isempty(edges)
        ci = result.ci
        mi = result.linfo
        result_type = result.result
        result_type isa LimitedAccuracy && (result_type = result_type.typ)
        @assert !(result_type === nothing)
        const_flag = is_result_constabi_eligible(result)
        if isa(result_type, Const)
            rettype_const = result_type.val
            const_flags = const_flag ? 0x3 : 0x2
        elseif isa(result_type, PartialTask)
            rettype_const = result_type
            const_flags = 0x2
        elseif isa(result_type, PartialOpaque)
            rettype_const = result_type
            const_flags = 0x2
        elseif isconstType(result_type)
            rettype_const = type_parameter(result_type)
            const_flags = 0x2
        elseif isa(result_type, PartialStruct)
            rettype_const = (_getundefs(result_type), result_type.fields)
            const_flags = 0x2
        elseif isa(result_type, InterConditional)
            rettype_const = result_type
            const_flags = 0x2
        elseif isa(result_type, InterMustAlias)
            rettype_const = result_type
            const_flags = 0x2
        else
            rettype_const = nothing
            const_flags = 0x0
        end
        inferred_result = nothing
        debuginfo = nothing
        const_flag = is_result_constabi_eligible(result)
        discard_src = caller.cache_mode === CACHE_MODE_NULL || (const_flag && may_discard_trees(interp))
        if !discard_src
            inferred_result = transform_result_for_cache(interp, result, edges)
            if inferred_result !== nothing
                result.src = inferred_result
                debuginfo = get_debuginfo(inferred_result)
            else
                if isa(result.src, OptimizationState)
                    debuginfo = get_debuginfo(ir_to_codeinf!(result.src))
                elseif isa(result.src, CodeInfo)
                    debuginfo = get_debuginfo(result.src)
                end
            end
            # TODO: do we want to augment edges here with any :invoke targets that we got from inlining (such that we didn't have a direct edge to it already)?
            if inferred_result isa CodeInfo
                if may_compress(interp)
                    nslots = length(inferred_result.slotflags)
                    resize!(inferred_result.slottypes::Vector{Any}, nslots)
                    resize!(inferred_result.slotnames, nslots)
                end
                inferred_result = maybe_compress_codeinfo(interp, mi, inferred_result)
            elseif ci.owner === nothing
                # The global cache can only handle objects that codegen understands (nothing or CodeInfo)
                inferred_result = nothing
            end
        else
            result.src = nothing
        end
        if debuginfo === nothing
            debuginfo = DebugInfo(mi)
        end
        # if we aren't cached, we don't need this edge
        # but our caller might, so let's just make it anyways
        if max_world >= validation_world
            # if we can record all of the backedges in the global reverse-cache,
            # we can now widen our applicability in the global cache too
            store_backedges(ci, edges)
        end
        ipo_effects = encode_effects(result.ipo_effects)
        time_now = _time_ns()
        time_self_ns = caller.time_self_ns + (time_now - time_before)
        time_total = (time_now - caller.time_start - caller.time_paused) * 1e-9
        ccall(:jl_fill_codeinst, Cvoid, (Any, Any, Any, Any, Any, Int32, UInt, UInt, UInt32, Any, Float64, Float64, Float64, Any, Any),
            ci, widenconst(result_type), widenconst(result.exc_result), rettype_const, inferred_result,
            const_flags, min_world, max_world,
            ipo_effects, result.analysis_results, time_total, caller.time_caches, time_self_ns * 1e-9, debuginfo, edges)
    elseif caller.cache_mode === CACHE_MODE_LOCAL
        result.src = transform_result_for_local_cache(interp, result)
    end
    nothing
end

function promotecache!(interp::AbstractInterpreter, caller::InferenceState)
    result = caller.result
    if isdefined(result, :ci)
        ci = result.ci
        mi = result.linfo
        # Only an early winner kept `ci` out of `opt_cache`, so only that case may
        # still be demoted here. If a winner appeared during optimization, `ci` may
        # already occur in optimized IR and must be published even if equivalent.
        if result.replacement_ci !== nothing
            equivalent = find_equivalent_cached_ci(
                interp, ci, result.valid_worlds)
            if equivalent === nothing
                # The early winner was sufficient to keep this provisional CI out
                # of optimizer state, but it cannot represent the completed result's
                # return ABI. Publish the now-complete CI normally.
                caller.cache_mode |= CACHE_MODE_GLOBAL
                caller.cache_mode &= ~CACHE_MODE_LOCAL
                result.replacement_ci = nothing
            else
                result.replacement_ci = equivalent
            end
        end
        if !iszero(caller.cache_mode & CACHE_MODE_GLOBAL)
            code_cache(interp)[mi] = ci
        end
        # A globally committed exact CI becomes visible before its reservation is
        # released and any waiters wake. A publication loser is still filled as a
        # session-local ephemeral CI before its reservation is released: it may carry
        # source required by this interpreter even when the global winner does not.
        engine_reject(interp, ci)
        codegen = codegen_cache(interp)
        if codegen !== nothing
            uncompressed = result.src
            if isa(uncompressed, OptimizationState)
                uncompressed = ir_to_codeinf!(uncompressed, ci.edges)
                result.src = uncompressed
            end
            if isa(uncompressed, CodeInfo)
                # record that the caller could use this result to generate code when required, if desired, to avoid repeating n^2 work
                codegen[ci] = uncompressed
                if bootstrapping_compiler && !(ci.inferred isa MaybeCompressed)
                    # This is necessary to get decent bootstrapping performance
                    # when compiling the compiler to inject everything eagerly
                    # where codegen can start finding and using it right away
                    if mi.def isa Method && isa_compileable_sig(mi) && is_cached(caller)
                        ccall(:jl_add_codeinsts_to_jit, Cvoid, (Any, Any), Any[ci], Any[uncompressed])
                    end
                end
            end
        end
    end
    if !iszero(caller.cache_mode & CACHE_MODE_LOCAL)
        if result.tombstone
            # Preserve rejected constant-propagation work as an internal marker. It is
            # never exposed as a completed call result.
            result.cache_world = get_inference_world(interp)
            push!(get_inference_cache(interp), result)
        elseif result.result !== nothing && result.overridden_by_const === nothing
            # Local work is reusable only through its explicit dependency proof. Its
            # provisional CI, if any, is deliberately not allowed to escape as a target.
            proof = LocalInferenceProof(result.valid_worlds,
                Core.svec(internal_result_edges(caller)...))
            local_result = LocalInferenceResult(result, proof, get_inference_world(interp))
            push!(get_inference_cache(interp), local_result)
        end
        # Successful constant propagation is published by `const_prop_call` only after
        # concrete-evaluation overrides have been finalized.
    end
    nothing
end

function finish!(interp::AbstractInterpreter, mi::MethodInstance, ci::CodeInstance, src::CodeInfo)
    user_edges = src.edges
    edges = user_edges isa SimpleVector ? user_edges : user_edges === nothing ? Core.svec() : Core.svec(user_edges...)
    di = src.debuginfo
    rettype = Any
    exctype = Any
    const_flags = 0x0
    ipo_effects = zero(UInt32)
    min_world = src.min_world
    max_world = src.max_world
    if max_world >= get_world_counter()
        max_world = typemax(UInt)
    end
    if max_world == typemax(UInt)
        # if we can record all of the backedges in the global reverse-cache,
        # we can now widen our applicability in the global cache too
        store_backedges(ci, edges)
    end
    ccall(:jl_fill_codeinst, Cvoid, (Any, Any, Any, Any, Any, Int32, UInt, UInt, UInt32, Any, Float64, Float64, Float64, Any, Any),
        ci, rettype, exctype, nothing, nothing, const_flags, min_world, max_world, ipo_effects, nothing, 0.0, 0.0, 0.0, di, edges)
    code_cache(interp)[mi] = ci
    codegen = codegen_cache(interp)
    if codegen !== nothing
        codegen[ci] = src
    end
    engine_reject(interp, ci)
    return nothing
end

function finish_nocycle(interp::AbstractInterpreter, frame::InferenceState{I}, time_before::UInt64) where {I<:AbstractInterpreter}
    opt_cache = IdDict{MethodInstance,CodeInstance}()
    finishinfer!(frame, interp::I, frame.cycleid, opt_cache)
    opt = frame.result.src
    if opt isa OptimizationState # implies `may_optimize(interp) === true`
        optimize(interp::I, opt::OptimizationState{I}, frame.result)
        # check the valid_worlds hasn't been narrowed by added :invoke edges
        valid_worlds = intersect(frame.valid_worlds, compute_recursive_worlds(opt.inlining.edges))
        update_valid_age!(frame, get_inference_world(interp::I), valid_worlds)
    end
    empty!(opt_cache)
    validation_world = get_world_counter()
    finish!(interp::I, frame, validation_world, time_before)
    promotecache!(interp::I, frame)
    if (!iszero(frame.cache_mode & CACHE_MODE_GLOBAL) &&
            isdefined(frame.result, :ci))
        # 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, Cvoid, (Any, UInt), frame.result.ci, validation_world)
    end
    if frame.cycleid != 0
        frames = frame.callstack
        @assert frames[end] === frame
        pop!(frames)
    end
    return nothing
end

function propagate_unpublished_cycle_proof!(
        frames::Vector{AbsIntState{I}}, cycleid::Int, world::UInt,
        cycle_valid_worlds::WorldRange
    ) where {I<:AbstractInterpreter}
    unpublished = InferenceState{I}[]
    for frameid = cycleid:length(frames)
        caller = frames[frameid]::InferenceState
        if iszero(caller.cache_mode & CACHE_MODE_GLOBAL)
            push!(unpublished, caller)
        end
    end
    isempty(unpublished) && return nothing

    proof_edges = Any[]
    for frameid = cycleid:length(frames)
        append!(proof_edges, internal_result_edges(frames[frameid]::InferenceState))
    end
    cycle_proof = LocalInferenceProof(cycle_valid_worlds, Core.svec(proof_edges...))
    # An unpublished member needs the shared fixed-point proof for later local
    # reuse. Any caller that directly consumed that member while it was in progress
    # needs the same proof. Other published SCC members remain connected through
    # their ordinary CI edges, so copying the union onto every member would only
    # multiply serialized edge streams by the SCC size.
    consumers = IdSet{InferenceState{I}}()
    for callee in unpublished
        push!(consumers, callee)
        for (caller, _) in callee.cycle_backedges
            push!(consumers, caller)
        end
    end
    for caller in consumers
        add_inference_proof!(internal_result_edges(caller), cycle_proof)
        update_valid_age!(caller, world, proof_worlds(cycle_proof))
    end
    return nothing
end

function finish_cycle(interp::AbstractInterpreter, frames::Vector{AbsIntState{I}}, cycleid::Int, time_before::UInt64) where {I<:AbstractInterpreter}
    world = get_inference_world(interp::I)
    cycle_valid_worlds = WorldRange()
    cycle_valid_effects = EFFECTS_TOTAL
    for frameid = cycleid:length(frames)
        caller = frames[frameid]::InferenceState
        @assert caller.cycleid == cycleid
        # converge the world age range and effects for this cycle here:
        # all frames in the cycle should have the same bits of `valid_worlds` and `effects`
        # that are simply the intersection of each partial computation, without having
        # dependencies on each other (unlike rt and exct)
        cycle_valid_worlds = intersect(cycle_valid_worlds, caller.valid_worlds)
        cycle_valid_effects = merge_effects(cycle_valid_effects, caller.ipo_effects)
    end
    opt_cache = IdDict{MethodInstance,CodeInstance}()
    for frameid = cycleid:length(frames)
        caller = frames[frameid]::InferenceState
        adjust_cycle_frame!(caller, world, cycle_valid_worlds, cycle_valid_effects)
        finishinfer!(caller, caller.interp::I, cycleid, opt_cache)
        time_now = _time_ns()
        caller.time_self_ns += (time_now - time_before)
        time_before = time_now
    end
    time_caches = 0.0 # the total and adjusted time of every entry in the cycle are the same
    time_paused = UInt64(0)
    for frameid = cycleid:length(frames)
        caller = frames[frameid]::InferenceState
        opt = caller.result.src
        if opt isa OptimizationState # implies `may_optimize(caller.interp) === true`
            optimize(caller.interp::I, opt::OptimizationState{I}, caller.result)
            cycle_valid_worlds = intersect(cycle_valid_worlds, compute_recursive_worlds(opt.inlining.edges))
            time_now = _time_ns()
            caller.time_self_ns += (time_now - time_before)
            time_before = time_now
        end
        time_caches += caller.time_caches
        time_paused += caller.time_paused
        caller.time_paused = UInt64(0)
        caller.time_caches = 0.0
    end
    # Calls to an already in-progress SCC member consume its current facts
    # immediately and record only a cycle backedge. Usually the member's published
    # CI later certifies those facts. If any member will not publish its exact CI
    # (for example, it was demoted in favor of a reentrant cached winner or its
    # source was tombstoned), preserve the SCC's external dependencies explicitly.
    # One shared proof for the whole SCC avoids constructing a cyclic proof graph.
    propagate_unpublished_cycle_proof!(frames, cycleid, world, cycle_valid_worlds)
    empty!(opt_cache)
    cycletop = frames[cycleid]::InferenceState
    time_start = cycletop.time_start
    validation_world = get_world_counter()
    cis = CodeInstance[]
    for frameid = cycleid:length(frames)
        caller = frames[frameid]::InferenceState
        caller.time_start = time_start
        caller.time_caches = time_caches
        caller.time_paused = time_paused
        update_valid_age!(caller, world, cycle_valid_worlds)
        finish!(caller.interp::I, caller, validation_world, time_before)
    end
    if cycletop.parentid != 0
        parent = frames[cycletop.parentid]
        parent.time_caches += time_caches
        parent.time_paused += time_paused
    end
    # After everything is finished, promote the work into visible caches
    for frameid = cycleid:length(frames)
        caller = frames[frameid]::InferenceState
        promotecache!(caller.interp::I, caller)
        if (!iszero(caller.cache_mode & CACHE_MODE_GLOBAL) &&
                isdefined(caller.result, :ci))
            push!(cis, caller.result.ci)
        end
    end
    # 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_cis_to_current, Cvoid, (Ptr{CodeInstance}, Csize_t, UInt), cis, length(cis), validation_world)
    resize!(frames, cycleid - 1)
    return nothing
end

function adjust_cycle_frame!(sv::InferenceState, world::UInt, cycle_valid_worlds::WorldRange, cycle_valid_effects::Effects)
    update_valid_age!(sv, world, cycle_valid_worlds)
    sv.ipo_effects = cycle_valid_effects
    # traverse the callees of this cycle that are tracked within `sv.cycle_backedges`
    # and adjust their statements so that they are consistent with the new `cycle_valid_effects`
    new_flags = flags_for_effects(cycle_valid_effects)
    for (callee, pc) in sv.cycle_backedges
        old_currpc = callee.currpc
        callee.currpc = pc
        set_curr_ssaflag!(callee, new_flags, IR_FLAGS_EFFECTS)
        callee.currpc = old_currpc
    end
    return nothing
end

function get_debuginfo(src)
    isa(src, CodeInfo) && return src.debuginfo
    isa(src, OptimizationState) && return src.src.debuginfo
    return nothing
end

function is_result_constabi_eligible(result::InferenceResult)
    result_type = result.result
    return isa(result_type, Const) && is_foldable_nothrow(result.ipo_effects) && is_inlineable_constant(result_type.val)
end

function compute_inlining_cost(interp::AbstractInterpreter, result::InferenceResult)
    src = result.src
    isa(src, OptimizationState) || return MAX_INLINE_COST
    compute_inlining_cost(interp, result, src.optresult)
end

function compute_inlining_cost(interp::AbstractInterpreter, result::InferenceResult, optresult#=::OptimizationResult=#)
    return inline_cost_model(interp, result, optresult.inline_flag, optresult.ir)
end

function inline_cost_model(interp::AbstractInterpreter, result::InferenceResult,
        inline_flag::UInt8, ir::IRCode)

    inline_flag === SRC_FLAG_DECLARED_NOINLINE && return MAX_INLINE_COST

    mi = result.linfo
    (; def, specTypes) = mi
    if !isa(def, Method)
        return MAX_INLINE_COST
    end

    declared_inline = inline_flag === SRC_FLAG_DECLARED_INLINE

    rt = result.result
    @assert !(rt isa LimitedAccuracy)
    rt = widenslotwrapper(rt)

    sig = unwrap_unionall(specTypes)
    if !(isa(sig, DataType) && sig.name === Tuple.name)
        return MAX_INLINE_COST
    end
    if !declared_inline && rt === Bottom
        return MAX_INLINE_COST
    end

    if declared_inline && isdispatchtuple(specTypes)
        # obey @inline declaration if a dispatch barrier would not help
        return MIN_INLINE_COST
    else
        # compute the cost (size) of inlining this code
        params = OptimizationParams(interp)
        cost_threshold = default = params.inline_cost_threshold
        if ⊑(optimizer_lattice(interp), rt, Tuple) && !isconcretetype(widenconst(rt))
            cost_threshold += params.inline_tupleret_bonus
        end
        # if the method is declared as `@inline`, increase the cost threshold 20x
        if declared_inline
            cost_threshold += 19*default
        end
        # a few functions get special treatment
        if def.module === _topmod(def.module)
            name = def.name
            if name === :iterate || name === :unsafe_convert || name === :cconvert
                cost_threshold += 4*default
            end
        end
        return inline_cost_model(ir, params, cost_threshold)
    end
end

function transform_result_for_local_cache(interp::AbstractInterpreter, result::InferenceResult)
    ## XXX: this must perform the exact same operations as transform_result_for_cache to avoid introducing soundness bugs
    if may_discard_trees(interp) && is_result_constabi_eligible(result)
        return nothing
    end
    src = result.src
    if isa(src, OptimizationState)
        # Compute and store any information required to determine the inlineability of the callee.
        opt = src
        opt.src.inlining_cost = compute_inlining_cost(interp, result)
    end
    return src
end

function transform_result_for_cache(interp::AbstractInterpreter, result::InferenceResult, edges::SimpleVector)
    inlining_cost = nothing
    src = result.src
    if isa(src, OptimizationState)
        opt = src
        inlining_cost = compute_inlining_cost(interp, result, opt.optresult)
        discard_optimized_result(interp, inlining_cost) && return nothing
        src = ir_to_codeinf!(opt)
    end
    if isa(src, CodeInfo)
        src.edges = edges
        if inlining_cost !== nothing
            src.inlining_cost = inlining_cost
        elseif may_optimize(interp)
            src.inlining_cost = compute_inlining_cost(interp, result)
        end
    end
    return src
end

function discard_optimized_result(interp::AbstractInterpreter, inlining_cost::InlineCostType)
    may_discard_trees(interp) || return false
    inlining_cost == MAX_INLINE_COST || return false
    precompile_keep_ir(interp) && return false
    return true
end

function maybe_compress_codeinfo(interp::AbstractInterpreter, mi::MethodInstance, ci::CodeInfo)
    def = mi.def
    isa(def, Method) || return ci # don't compress toplevel code
    can_discard_trees = may_discard_trees(interp)
    inlineable = is_inlineable(ci)
    if can_discard_trees && !inlineable
        # Precompile-keep-ir mode: retain non-inlineable IR as raw CodeInfo so
        # irgen's typeinf_ext can reuse it instead of re-inferring.
        # jl_finalize_precompile_inferred nulls it before save.
        precompile_keep_ir(interp) && return ci
        return nothing
    end
    # TODO: do we want to augment edges here with any :invoke targets that we got from inlining (such that we didn't have a direct edge to it already)?
    may_compress(interp) && return ccall(:jl_compress_ir, String, (Any, Any), def, ci)
    return ci
end

function cycle_fix_limited(@nospecialize(typ), sv::InferenceState, cycleid::Int)
    if typ isa LimitedAccuracy
        frames = sv.callstack
        causes = typ.causes
        for frameid = cycleid:length(frames)
            caller = frames[frameid]::InferenceState
            caller in causes || continue
            causes === typ.causes && (causes = copy(causes))
            pop!(causes, caller)
            if isempty(causes)
                return typ.typ
            end
        end
        @assert sv.parentid != 0
        if causes !== typ.causes
            return LimitedAccuracy(typ.typ, causes)
        end
    end
    return typ
end

function adjust_effects(ipo_effects::Effects, def::Method)
    # override the analyzed effects using manually annotated effect settings
    override = decode_effects_override(def.purity)
    if is_effect_overridden(override, :consistent)
        ipo_effects = Effects(ipo_effects; consistent=ALWAYS_TRUE)
    end
    if is_effect_overridden(override, :effect_free)
        ipo_effects = Effects(ipo_effects; effect_free=ALWAYS_TRUE)
    end
    if is_effect_overridden(override, :nothrow)
        ipo_effects = Effects(ipo_effects; nothrow=true)
    end
    if is_effect_overridden(override, :terminates_globally)
        ipo_effects = Effects(ipo_effects; terminates=true)
    end
    if is_effect_overridden(override, :notaskstate)
        ipo_effects = Effects(ipo_effects; notaskstate=true)
    end
    if is_effect_overridden(override, :inaccessiblememonly)
        ipo_effects = Effects(ipo_effects; inaccessiblememonly=ALWAYS_TRUE)
    end
    if is_effect_overridden(override, :noub)
        ipo_effects = Effects(ipo_effects; noub=ALWAYS_TRUE)
    elseif is_effect_overridden(override, :noub_if_noinbounds) && ipo_effects.noub !== ALWAYS_TRUE
        ipo_effects = Effects(ipo_effects; noub=NOUB_IF_NOINBOUNDS)
    end
    if is_effect_overridden(override, :consistent_overlay)
        ipo_effects = Effects(ipo_effects; nonoverlayed=CONSISTENT_OVERLAY)
    end
    if is_effect_overridden(override, :nortcall)
        ipo_effects = Effects(ipo_effects; nortcall=true)
    end
    return ipo_effects
end

function adjust_effects(sv::InferenceState)
    ipo_effects = sv.ipo_effects

    # refine :consistent-cy effect using the return type information
    # TODO this adjustment tries to compromise imprecise :consistent-cy information,
    # that is currently modeled in a flow-insensitive way: ideally we want to model it
    # with a proper dataflow analysis instead
    rt = sv.bestguess
    if rt === Bottom
        # always throwing an error counts or never returning both count as consistent
        ipo_effects = Effects(ipo_effects; consistent=ALWAYS_TRUE)
    end
    if sv.exc_bestguess === Bottom
        # if the exception type of this frame is known to be `Bottom`,
        # this frame is known to be safe
        ipo_effects = Effects(ipo_effects; nothrow=true)
    end
    if is_inaccessiblemem_or_argmemonly(ipo_effects) && all(1:narguments(sv, #=include_va=#true)) do i::Int
            return is_mutation_free_argtype(sv.slottypes[i])
        end
        ipo_effects = Effects(ipo_effects; inaccessiblememonly=ALWAYS_TRUE)
    end
    if is_consistent_if_notreturned(ipo_effects) && is_identity_free_argtype(rt)
        # in a case when the :consistent-cy here is only tainted by mutable allocations
        # (indicated by `CONSISTENT_IF_NOTRETURNED`), we may be able to refine it if the return
        # type guarantees that the allocations are never returned
        consistent = ipo_effects.consistent & ~CONSISTENT_IF_NOTRETURNED
        ipo_effects = Effects(ipo_effects; consistent)
    end
    if is_consistent_if_inaccessiblememonly(ipo_effects)
        if is_inaccessiblememonly(ipo_effects)
            consistent = ipo_effects.consistent & ~CONSISTENT_IF_INACCESSIBLEMEMONLY
            ipo_effects = Effects(ipo_effects; consistent)
        elseif is_inaccessiblemem_or_argmemonly(ipo_effects)
        else # `:inaccessiblememonly` is already tainted, there will be no chance to refine this
            ipo_effects = Effects(ipo_effects; consistent=ALWAYS_FALSE)
        end
    end
    if is_effect_free_if_inaccessiblememonly(ipo_effects)
        if is_inaccessiblememonly(ipo_effects)
            effect_free = ipo_effects.effect_free & ~EFFECT_FREE_IF_INACCESSIBLEMEMONLY
            ipo_effects = Effects(ipo_effects; effect_free)
        elseif is_inaccessiblemem_or_argmemonly(ipo_effects)
        else # `:inaccessiblememonly` is already tainted, there will be no chance to refine this
            ipo_effects = Effects(ipo_effects; effect_free=ALWAYS_FALSE)
        end
    end

    # override the analyzed effects using manually annotated effect settings
    def = sv.linfo.def
    if isa(def, Method)
        ipo_effects = adjust_effects(ipo_effects, def)
    end

    return ipo_effects
end

function refine_exception_type(@nospecialize(exc_bestguess), ipo_effects::Effects)
    ipo_effects.nothrow && return Bottom
    return exc_bestguess
end

const empty_edges = Core.svec()

# inference completed on `me`
# update the MethodInstance
function finishinfer!(me::InferenceState, interp::AbstractInterpreter, cycleid::Int,
                      opt_cache::IdDict{MethodInstance, CodeInstance})
    # prepare to run optimization passes on fulltree
    @assert isempty(me.ip)
    # inspect whether our inference had a limited result accuracy,
    # else it may be suitable to cache
    bestguess = me.bestguess = cycle_fix_limited(me.bestguess, me, cycleid)
    exc_bestguess = me.exc_bestguess = cycle_fix_limited(me.exc_bestguess, me, cycleid)
    limited_ret = bestguess isa LimitedAccuracy || exc_bestguess isa LimitedAccuracy
    limited_src = false
    if limited_ret
        @assert me.parentid != 0
    else
        gt = me.ssavaluetypes
        for j = 1:length(gt)
            gt[j] = gtj = cycle_fix_limited(gt[j], me, cycleid)
            if gtj isa LimitedAccuracy
                @assert me.parentid != 0
                limited_src = true
                break
            end
        end
    end
    result = me.result
    result.result = bestguess
    ipo_effects = result.ipo_effects = me.ipo_effects = adjust_effects(me)
    result.exc_result = me.exc_bestguess = refine_exception_type(me.exc_bestguess, ipo_effects)
    src = me.src
    src.rettype = widenconst(ignorelimited(bestguess))
    src.ssaflags = me.ssaflags
    valid_worlds = me.valid_worlds
    result.valid_worlds = valid_worlds
    min_world, max_world = first(valid_worlds), last(valid_worlds)
    src.min_world = min_world
    src.max_world = max_world
    istoplevel = !(me.linfo.def isa Method)
    istoplevel || compute_edges!(me) # don't add backedges to toplevel method instance

    if limited_ret || limited_src
        # A parent may be cached still, but not this intermediate work:
        # we can throw everything else away now. Caching anything can confuse later
        # heuristics to consider it worth trying to pursue compiling this further and
        # finding infinite work as a result. Avoiding global caching helps to ensure there
        # is only a finite amount of work that can be discovered later (although potentially
        # still a large multiplier on it). We still allow local caching so that tombstoned
        # entries can be found by `constprop_cache_lookup` to prevent re-attempting the same
        # const-prop work that would hit the same limit.
        result.src = nothing
        result.tombstone = true
        me.cache_mode &= ~CACHE_MODE_GLOBAL
        set_inlineable!(src, false)
    else
        # annotate fulltree with type information,
        # either because we are the outermost code, or we might use this later
        type_annotate!(interp, me)
        mayopt = may_optimize(interp)
        doopt = mayopt &&
                # disable optimization if we don't use this later (because it is not cached)
                me.cache_mode != CACHE_MODE_NULL &&
                # disable optimization if we've already obtained very accurate result
                !result_is_constabi(interp, result)
        if doopt
            result.src = OptimizationState(me, interp, opt_cache)
        else
            result.src = src # for reflection etc.
        end
    end

    maybe_validate_code(me.linfo, src, "inferred")

    # check global cache again for :invoke use, and put in the opt_cache if it wasn't there at this time
    if isdefined(result, :ci)
        ci = result.ci
        ipo_effects = encode_effects(result.ipo_effects)
        # populate a few fields that won't change again (and are inspected by optimization)
        @atomic :monotonic ci.ipo_purity_bits = ipo_effects
        ci.analysis_results = result.analysis_results
        if !iszero(me.cache_mode & CACHE_MODE_GLOBAL)
            ci = result.ci
            replacement_ci = find_cached_ci(interp, result)
            if replacement_ci !== nothing
                # Make the publication decision before this CI can enter `opt_cache`.
                # The provisional object remains private to this inference session and
                # is filled only after optimization, so no published caller can observe
                # it as an executable edge.
                result.replacement_ci = replacement_ci
                me.cache_mode = CACHE_MODE_LOCAL
            else
                opt_cache[result.linfo] = ci
            end
        end
    end
    nothing
end

function find_cached_ci(interp::AbstractInterpreter, result::InferenceResult)
    # Any inferred global CI covering this result is sufficient to defer publication
    # until the new result's ABI is known. `promotecache!` then keeps an equivalent
    # result local, or publishes the completed CI normally when no equivalent winner
    # exists.
    return find_cached_ci(interp, result.linfo, result.valid_worlds,
        SOURCE_MODE_NOT_REQUIRED)
end

# Iterate a series of back-edges that need registering, based on the provided forward edge list.
# Back-edges are returned as (invokesig, item), where the item is a Binding, MethodInstance, or
# MethodTable.
struct ForwardToBackedgeIterator
    forward_edges::SimpleVector
end

function Base.iterate(it::ForwardToBackedgeIterator, i::Int = 1)
    edges = it.forward_edges
    i > length(edges) && return nothing
    while i ≤ length(edges)
        item = edges[i]
        if item isa Int
            i += 2
            continue # ignore the query information if present but process the contents
        elseif isa(item, Method)
            # ignore `Method`-edges (from e.g. failed `abstract_call_method`)
            i += 1
            continue
        elseif isa(item, Core.Binding)
            return ((nothing, item), i + 1)
        end
        if isa(item, CodeInstance)
            item = get_ci_mi(item)
            return ((nothing, item), i + 1)
        elseif isa(item, MethodInstance) # regular dispatch
            return ((nothing, item), i + 1)
        else
            invokesig = item
            callee = edges[i+1]
            isa(callee, Method) && (i += 2; continue) # ignore `Method`-edges (from e.g. failed `abstract_call_method`)
            if isa(callee, MethodTable)
                # abstract dispatch (legacy style edges)
                return ((invokesig, callee), i + 2)
            else
                # `invoke` edge
                callee = isa(callee, CodeInstance) ? get_ci_mi(callee) : callee::MethodInstance
                return ((invokesig, callee), i + 2)
            end
        end
    end
    return nothing
end

# record the backedges

function maybe_add_binding_backedge!(b::Core.Binding, edge::Union{Method, CodeInstance})
    meth = isa(edge, Method) ? edge : get_ci_mi(edge).def
    ccall(:jl_maybe_add_binding_backedge, Cint, (Any, Any, Any), b, edge, meth)
    return nothing
end

function store_backedges(caller::CodeInstance, edges::SimpleVector)
    isa(get_ci_mi(caller).def, Method) || return # don't add backedges to toplevel method instance

    backedges = ForwardToBackedgeIterator(edges)
    # `Compiler` is loaded before `Set` during bootstrap, so keep the signatures
    # for each identity-keyed dependency in a small vector.
    seen = IdDict{Any,Vector{Any}}()
    for (invokesig, item) in backedges
        if haskey(seen, item)
            signatures = seen[item]
            duplicate_found = false
            for signature in signatures
                if signature == invokesig
                    duplicate_found = true
                    break
                end
            end
            duplicate_found && continue
            push!(signatures, invokesig)
        else
            seen[item] = Any[invokesig]
        end
        if item isa Core.Binding
            maybe_add_binding_backedge!(item, caller)
        elseif item isa MethodTable
            ccall(:jl_method_table_add_backedge, Cvoid, (Any, Any), invokesig, caller)
        else
            item::MethodInstance
            ccall(:jl_method_instance_add_backedge, Cvoid, (Any, Any, Any), item, invokesig, caller)
        end
    end
    nothing
end

function compute_edges!(sv::InferenceState)
    edges = sv.edges
    for i in 1:length(sv.stmt_info)
        add_edges!(edges, sv.stmt_info[i])
    end
    user_edges = sv.src.edges::Union{Nothing, SimpleVector, Vector{Any}}
    if user_edges !== nothing && user_edges !== empty_edges
        append!(edges, user_edges)
    end
    nothing
end

function compute_recursive_worlds(edges::Vector{Any})
    range = WorldRange(typemin(UInt), typemax(UInt))
    for edge in edges
        if edge isa CodeInstance
            wr = WorldRange(edge.min_world, edge.max_world)
            iszero(last(wr.max_world)) && continue # part of the current cycle, not yet valid
            range = intersect(range, wr)
        elseif edge isa LocalInferenceProof
            range = intersect(range, edge.valid_worlds)
        end
    end
    return range
end

function record_slot_assign!(sv::InferenceState)
    # look at all assignments to slots
    # and union the set of types stored there
    # to compute a lower bound on the storage required
    body = sv.src.code::Vector{Any}
    slottypes = sv.slottypes::Vector{Any}
    ssavaluetypes = sv.ssavaluetypes
    for i = 1:length(body)
        expr = body[i]
        # find all reachable assignments to locals
        if was_reached(sv, i) && isexpr(expr, :(=))
            lhs = expr.args[1]
            if isa(lhs, SlotNumber)
                typ = ssavaluetypes[i]
                @assert typ !== NOT_FOUND "active slot in unreached region"
                vt = widenconst(typ)
                if vt !== Bottom
                    id = slot_id(lhs)
                    otherTy = slottypes[id]
                    if otherTy === Bottom
                        slottypes[id] = vt
                    elseif otherTy === Any
                        slottypes[id] = Any
                    else
                        slottypes[id] = tmerge(otherTy, vt)
                    end
                end
            end
        end
    end
    sv.src.slottypes = slottypes
    return nothing
end

# find the dominating assignment to the slot `id` in the block containing statement `idx`,
# returns `nothing` otherwise
function find_dominating_assignment(id::Int, idx::Int, sv::InferenceState)
    block = block_for_inst(sv.cfg, idx)
    for pc in reverse(sv.cfg.blocks[block].stmts) # N.B. reverse since the last assignment is dominating this block
        pc < idx || continue # N.B. needs pc ≠ idx as `id` can be assigned at `idx`
        stmt = sv.src.code[pc]
        isexpr(stmt, :(=)) || continue
        lhs = stmt.args[1]
        isa(lhs, SlotNumber) || continue
        slot_id(lhs) == id || continue
        return pc
    end
    return nothing
end

# annotate types of all symbols in AST, preparing for optimization
function type_annotate!(::AbstractInterpreter, sv::InferenceState)
    # widen slot wrappers from `slottypes`
    slottypes = sv.slottypes
    for i = 1:length(slottypes)
        slottypes[i] = widenslotwrapper(slottypes[i])
    end

    # compute the required type for each slot
    # to hold all of the items assigned into it
    record_slot_assign!(sv)

    # annotate variables load types
    src = sv.src
    stmts = src.code
    nstmt = length(stmts)
    ssavaluetypes = sv.ssavaluetypes
    nslots = length(src.slotflags)

    # widen slot wrappers (`Conditional` and `MustAlias`) and remove `NOT_FOUND` from `ssavaluetypes`
    # and mark any unreachable statements by wrapping them in Const(...), to distinguish them from
    # must-throw statements which also have type Bottom
    for i = 1:nstmt
        expr = stmts[i]
        if was_reached(sv, i)
            ssavaluetypes[i] = widenslotwrapper(ssavaluetypes[i]) # 3
        else # i.e. any runtime execution will never reach this statement
            push!(sv.unreachable, i)
            if is_meta_expr(expr) # keep any lexically scoped expressions
                ssavaluetypes[i] = Any # 3
            else
                ssavaluetypes[i] = Bottom # 3
                # annotate that this statement actually is dead
                stmts[i] = Const(expr)
            end
        end
    end

    # widen slot wrappers (`Conditional` and `MustAlias`) in `bb_states`
    for bbstate in sv.bb_states
        if bbstate !== nothing
            vartable = bbstate.vartable
            for slot in 1:nslots
                vt = vartable[slot]
                widened_type = widenslotwrapper(ignorelimited(vt.typ))
                vartable[slot] = VarState(widened_type, vt.ssadef, vt.undef)
            end
        end
    end

    return nothing
end

function merge_call_chain!(::AbstractInterpreter, parent::InferenceState, child::InferenceState)
    # update all cycleid to be in the same group
    frames = parent.callstack
    @assert child.callstack === frames
    ancestorid = child.cycleid
    # ensure that walking the callstack has the same cycleid (DAG)
    for frameid = reverse(ancestorid:length(frames))
        frame = frames[frameid]::InferenceState
        frame.cycleid == ancestorid && break
        @assert frame.cycleid > ancestorid
        frame.cycleid = ancestorid
    end
end

function add_cycle_backedge!(caller::InferenceState, frame::InferenceState)
    backedge = (caller, caller.currpc)
    contains_is(frame.cycle_backedges, backedge) || push!(frame.cycle_backedges, backedge)
    return frame
end

function is_same_frame(interp::I, mi::MethodInstance, frame::InferenceState) where {I<:AbstractInterpreter}
    return mi === frame_instance(frame) && cache_owner(interp) === cache_owner(frame.interp::I)
end

function poison_callstack!(infstate::InferenceState, topmost::InferenceState)
    push!(infstate.pclimitations, topmost)
    nothing
end

# Walk through `mi`'s upstream call chain, starting at `parent`. If a parent
# frame matching `mi` is encountered, then there is a cycle in the call graph
# (i.e. `mi` is a descendant callee of itself). Upon encountering this cycle,
# we "resolve" it by merging the call chain, which entails updating each intermediary
# frame's `cycleid` field. Finally, we return `mi`'s pre-existing frame.
# If no cycles are found, `nothing` is returned instead.
function resolve_call_cycle!(interp::AbstractInterpreter, mi::MethodInstance, parent::AbsIntState)
    # TODO (#48913) implement a proper recursion handling for irinterp:
    # This works most of the time currently just because the irinterp code doesn't get used much with
    # `@assume_effects`, so it never sees a cycle normally, but that may not be a sustainable solution.
    parent isa InferenceState || return false
    frames = parent.callstack
    uncached = false
    for frameid = reverse(1:length(frames))
        frame = frames[frameid]
        isa(frame, InferenceState) || break
        uncached |= !is_cached(frame) # ensure we never add a (globally) uncached frame to a cycle
        if is_same_frame(interp, mi, frame)
            if uncached
                # our attempt to speculate into a constant call lead to an undesired self-cycle
                # that cannot be converged: if necessary, poison our call-stack (up to the discovered duplicate frame)
                # with the limited flag and abort (set return type to Any) now
                poison_callstack!(parent, frame)
                return true
            end
            merge_call_chain!(interp, parent, frame)
            return frame
        end
    end
    return false
end

ipo_effects(code::CodeInstance) = decode_effects(code.ipo_purity_bits)

# return cached result of regular inference
function return_cached_result(interp::AbstractInterpreter, method::Method, codeinst::CodeInstance, @nospecialize(src), caller::AbsIntState, edgecycle::Bool, edgelimited::Bool)
    rt = cached_return_type(codeinst)
    exct = codeinst.exctype
    effects = ipo_effects(codeinst)
    valid_worlds = WorldRange(min_world(codeinst), max_world(codeinst))
    if src !== nothing
        # Create an InferenceResult to preserve cached source lookup
        inf_result = InferenceResult(codeinst.def, typeinf_lattice(interp))
        inf_result.result = rt
        inf_result.exc_result = exct
        inf_result.src = src::CodeInfo
        inf_result.ipo_effects = effects
        inf_result.ci = codeinst
        inf_result.valid_worlds = valid_worlds
        local_result = LocalInferenceResult(inf_result, codeinst, get_inference_world(interp))
        push!(get_inference_cache(interp), local_result)
    else
        local_result = nothing
    end
    update_valid_age!(caller, get_inference_world(interp), valid_worlds)
    caller.time_caches += reinterpret(Float16, codeinst.time_infer_total)
    caller.time_caches += reinterpret(Float16, codeinst.time_infer_cache_saved)
    return Future(MethodCallResult(interp, caller, method, rt, exct, effects, codeinst,
        edgecycle, edgelimited, local_result))
end

function return_cached_result(interp::AbstractInterpreter, method::Method,
                              local_result::LocalInferenceResult,
                              codeinst::Union{Nothing,CodeInstance},
                              caller::AbsIntState, edgecycle::Bool, edgelimited::Bool)
    inf_result = local_result.result
    rt = inf_result.result
    exct = inf_result.exc_result
    effects = inf_result.ipo_effects
    world = get_inference_world(interp)
    update_valid_age!(caller, world, proof_worlds(local_result.proof))
    if codeinst !== nothing
        update_valid_age!(caller, world, WorldRange(codeinst.min_world, codeinst.max_world))
        caller.time_caches += reinterpret(Float16, codeinst.time_infer_total)
        caller.time_caches += reinterpret(Float16, codeinst.time_infer_cache_saved)
    end
    return Future(MethodCallResult(interp, caller, method, rt, exct, effects,
        codeinst, edgecycle, edgelimited, local_result))
end

function lookup_cached_edge(interp::AbstractInterpreter, method::Method,
                            mi::MethodInstance, caller::AbsIntState, force_inline::Bool,
                            edgecycle::Bool, edgelimited::Bool)
    local_result = lookup_local_inference_result(interp, mi)
    codeinst = get(code_cache(interp), mi, nothing)
    if !(codeinst isa CodeInstance)
        local_result === nothing && return nothing, nothing
        return return_cached_result(interp, method, local_result, nothing, caller,
            edgecycle, edgelimited), nothing
    end
    @assert codeinst.def === mi "MethodInstance for cached edge does not match"

    if local_result !== nothing
        return return_cached_result(interp, method, local_result, codeinst, caller,
            edgecycle, edgelimited), nothing
    end

    inferred = @atomic :monotonic codeinst.inferred
    need_inlineable_code = (may_optimize(interp) &&
        (force_inline || is_inlineable(inferred) || use_const_api(codeinst)))
    if need_inlineable_code
        src = ci_get_source(interp, codeinst, inferred)
        src === nothing && return nothing, codeinst
        return return_cached_result(interp, method, codeinst, src, caller,
            edgecycle, edgelimited), nothing
    end
    return return_cached_result(interp, method, codeinst, nothing, caller,
        edgecycle, edgelimited), nothing
end


function MethodCallResult(::AbstractInterpreter, sv::AbsIntState, method::Method,
                          @nospecialize(rt), @nospecialize(exct), effects::Effects,
                          edge::Union{Nothing,CodeInstance}, edgecycle::Bool, edgelimited::Bool,
                          call_result::Union{Nothing,InferredCallResult} = nothing;
                          force_edgecycle::Bool = true, needs_mi_edge::Bool = false)
    if force_edgecycle && edge === nothing && call_result === nothing
        edgecycle = edgelimited = true
    end

    # we look for the termination effect override here as well, since the :terminates effect
    # may have been tainted due to recursion at this point even if it's overridden
    if is_effect_overridden(sv, :terminates_globally)
        # this frame is known to terminate
        effects = Effects(effects, terminates=true)
    elseif is_effect_overridden(method, :terminates_globally)
        # this edge is known to terminate
        effects = Effects(effects; terminates=true)
    elseif edgecycle
        # Some sort of recursion was detected.
        edge_mi = if edge !== nothing
            edge.def
        elseif call_result isa LocalInferenceResult
            call_result.result.linfo
        end
        if edge_mi !== nothing && !edgelimited && !is_edge_recursed(edge_mi, sv)
            # no `MethodInstance` cycles -- don't taint :terminate
        else
            # we cannot guarantee that the call will terminate
            effects = Effects(effects; terminates=false)
        end
    end

    return MethodCallResult(rt, exct, effects, edge, edgecycle, edgelimited, call_result;
        needs_mi_edge)
end

function completed_inference_result(interp::AbstractInterpreter, frame::InferenceState)
    result = frame.result
    @assert result.result !== nothing
    @assert !result.tombstone
    if (!iszero(frame.cache_mode & CACHE_MODE_GLOBAL) && isdefined(result, :ci) &&
            get(code_cache(interp, result.valid_worlds), result.linfo, nothing) === result.ci)
        proof = result.ci
    else
        cache = get_inference_cache(interp)
        indices = get_indices(cache, result.linfo)
        for i in length(indices):-1:1
            cached = cache.results[indices[i]]
            if cached isa LocalInferenceResult && cached.result === result
                return cached
            end
        end
        proof = LocalInferenceProof(result.valid_worlds,
            Core.svec(internal_result_edges(frame)...))
    end
    return LocalInferenceResult(result, proof, get_inference_world(interp))
end

function _schedule_edge_infer_task!(caller::AbsIntState, frame::InferenceState, result::InferenceResult,
                                    method::Method, edge_ci::Union{Nothing,CodeInstance},
                                    edgecycle::Bool, edgelimited::Bool)
    mresult = Future{MethodCallResult}()
    push!(caller.tasks, function get_infer_result(interp, caller)
        update_valid_age!(caller, get_inference_world(interp), frame.valid_worlds)
        isinferred = is_inferred(frame)
        effects = nothing
        call_result = nothing
        edge = edge_ci
        if isinferred
            if !result.tombstone
                call_result = completed_inference_result(interp, frame)
                update_valid_age!(caller, get_inference_world(interp),
                    proof_worlds(call_result.proof))
            else
                # A limited source can still produce clean return/effect facts. Retain
                # their dependencies without exposing the tombstoned source as reusable.
                proof = LocalInferenceProof(result.valid_worlds,
                    Core.svec(internal_result_edges(frame)...))
                add_inference_proof!(caller.edges, proof)
                update_valid_age!(caller, get_inference_world(interp), proof_worlds(proof))
            end
            effects = result.ipo_effects # effects are adjusted already within `finish` for ipo_effects
            if !iszero(frame.cache_mode & CACHE_MODE_GLOBAL) && isdefined(result, :ci)
                edge = result.ci
            else
                cached = get(code_cache(interp), result.linfo, nothing)
                cached isa CodeInstance && (edge = cached)
            end
        else
            # Do not expose this frame's provisional CI. The ordinary Method/MI lookup
            # edge is sufficient until the cycle resolves, and an existing published
            # target may still be reused when one was available at scheduling time.
            effects = adjust_effects(effects_for_cycle(frame.ipo_effects), method)
            add_cycle_backedge!(caller, frame)
        end
        # Both provisional SCC results and completed tombstones can contribute body
        # facts without a CI target or reusable local result. Their transitive proof
        # edges do not replace the dispatch dependency on this MethodInstance.
        needs_mi_edge = edge === nothing && call_result === nothing
        if edge !== nothing
            update_valid_age!(caller, get_inference_world(interp), proof_worlds(edge))
        end
        bestguess = frame.bestguess
        exc_bestguess = refine_exception_type(frame.exc_bestguess, effects)
        # Propagate newly inferred source to the inliner, allowing efficient inlining
        # without deserialization.
        # A missing target here is deliberate; preserve the cycle/limiting decision made
        # by `abstract_call_method` instead of inferring a new cycle from target absence.
        mresult[] = MethodCallResult(interp, caller, method, bestguess, exc_bestguess, effects,
            edge, edgecycle, edgelimited, call_result;
            force_edgecycle=false, needs_mi_edge)
        return true
    end)
    return mresult
end

# compute (and cache) an inferred AST and return the current best estimate of the result type
function typeinf_edge(interp::AbstractInterpreter, method::Method, @nospecialize(atype), sparams::SimpleVector, caller::AbsIntState, edgecycle::Bool, edgelimited::Bool)
    mi = specialize_method(method, atype, sparams)
    cache_mode = CACHE_MODE_GLOBAL # cache edge targets globally by default
    force_inline = is_stmt_inline(get_curr_ssaflag(caller))
    edge_ci = nothing
    cached, missing_source_edge = lookup_cached_edge(interp, method, mi, caller,
        force_inline, edgecycle, edgelimited)
    if cached !== nothing
        return cached
    elseif missing_source_edge !== nothing
        # A globally published executable target exists, but its source was discarded.
        # Re-infer only the source/facts and certify that local work with a local proof.
        cache_mode = CACHE_MODE_LOCAL
        edge_ci = missing_source_edge
    end
    if !InferenceParams(interp).force_enable_inference && ccall(:jl_get_module_infer, Cint, (Any,), method.module) == 0
        add_remark!(interp, caller, "[typeinf_edge] Inference is disabled for the target module")
        return Future(MethodCallResult(interp, caller, method, Any, Any, Effects(), nothing, edgecycle, edgelimited))
    end
    if !is_cached(caller) && frame_parent(caller) === nothing
        # this caller exists to return to the user
        # (if we asked resolve_call_cycle!, it might instead detect that there is a cycle that it can't merge)
        frame = false
    else
        frame = resolve_call_cycle!(interp, mi, caller)
    end
    if frame === false
        # completely new, but check again after reserving in the engine
        if cache_mode == CACHE_MODE_GLOBAL
            reserve_start = _time_ns() # subtract engine_reserve (thread-synchronization) time from callers to avoid double-counting
            ci_from_engine = engine_reserve(interp, mi)
            caller.time_paused += (_time_ns() - reserve_start)
            cached, missing_source_edge = lookup_cached_edge(interp, method, mi, caller,
                force_inline, edgecycle, edgelimited)
            if cached !== nothing
                engine_reject(interp, ci_from_engine)
                return cached
            elseif missing_source_edge !== nothing
                engine_reject(interp, ci_from_engine)
                ci_from_engine = nothing
                cache_mode = CACHE_MODE_LOCAL
                edge_ci = missing_source_edge
            end
        else
            ci_from_engine = nothing
        end
        result = InferenceResult(mi, typeinf_lattice(interp))
        if ci_from_engine !== nothing
            result.ci = ci_from_engine
        elseif !iszero(cache_mode & CACHE_MODE_GLOBAL)
            result.ci = ccall(:jl_new_codeinst_uninit, Any, (Any, Any),
                mi, cache_owner(interp))::CodeInstance
        end
        frame = InferenceState(result, cache_mode, interp) # always use the cache for edge targets
        if frame === nothing
            add_remark!(interp, caller, "[typeinf_edge] Failed to retrieve source")
            # can't get the source for this, so we know nothing
            if ci_from_engine !== nothing
                engine_reject(interp, ci_from_engine)
            end
            return Future(MethodCallResult(interp, caller, method, Any, Any, Effects(), nothing, edgecycle, edgelimited))
        end
        assign_parentchild!(frame, caller)
        # the actual inference task for this edge is going to be scheduled within `typeinf_local` via the callstack queue
        # while splitting off the rest of the work for this caller into a separate workq thunk
        return _schedule_edge_infer_task!(caller, frame, result, method, edge_ci, edgecycle, edgelimited)
    elseif frame === true
        # unresolvable cycle
        add_remark!(interp, caller, "[typeinf_edge] Unresolvable cycle")
        return Future(MethodCallResult(interp, caller, method, Any, Any, Effects(), nothing, edgecycle, edgelimited))
    end
    # return the current knowledge about this cycle
    frame = frame::InferenceState
    update_valid_age!(caller, get_inference_world(interp), frame.valid_worlds)
    effects = adjust_effects(effects_for_cycle(frame.ipo_effects), method)
    bestguess = frame.bestguess
    exc_bestguess = refine_exception_type(frame.exc_bestguess, effects)
    add_cycle_backedge!(caller, frame)
    result = frame.result
    edge = get(code_cache(interp), result.linfo, nothing)
    edge isa CodeInstance || (edge = nothing)
    if edge !== nothing
        update_valid_age!(caller, get_inference_world(interp), proof_worlds(edge))
    end
    return Future(MethodCallResult(interp, caller, method, bestguess, exc_bestguess, effects,
        edge, edgecycle, edgelimited;
        force_edgecycle=false, needs_mi_edge=edge === nothing))
end

# The `:terminates` effect bit must be conservatively tainted unless recursion cycle has
# been fully resolved. As for other effects, there's no need to taint them at this moment
# because they will be tainted as we try to resolve the cycle.
effects_for_cycle(effects::Effects) = Effects(effects; terminates=false)

function cached_return_type(code::CodeInstance)
    rettype = code.rettype
    isdefined(code, :rettype_const) || return rettype
    rettype_const = code.rettype_const
    # the second subtyping/egal conditions are necessary to distinguish usual cases
    # from rare cases when `Const` wrapped those extended lattice type objects
    if isa(rettype_const, Tuple{Vector{Union{Nothing,Bool}}, Vector{Any}}) && !(Tuple{Vector{Union{Nothing,Bool}}, Vector{Any}} <: rettype)
        undefs, fields = rettype_const
        return PartialStruct(fallback_lattice, rettype, undefs, fields)
    elseif isa(rettype_const, PartialOpaque) && rettype <: Core.OpaqueClosure
        return rettype_const
    elseif isa(rettype_const, PartialTask) && rettype <: Task
        return rettype_const
    elseif isa(rettype_const, InterConditional) && rettype !== InterConditional
        return rettype_const
    elseif isa(rettype_const, InterMustAlias) && rettype !== InterMustAlias
        return rettype_const
    else
        return Const(rettype_const)
    end
end

#### entry points for inferring a MethodInstance given a type signature ####

"""
    codeinfo_for_const(interp::AbstractInterpreter, mi::MethodInstance, worlds::WorldRange, edges::SimpleVector, @nospecialize(val))

Return a fake CodeInfo that just contains `return \$val`. This function is used in various reflection APIs when asking
for the code of a function that inference has found to just return a constant. For such functions, no code is actually
stored - the constant is used directly. However, because this is an ABI implementation detail, it is nice to maintain
consistency and just synthesize a CodeInfo when the reflection APIs ask for them - this function does that.
"""
function codeinfo_for_const(::AbstractInterpreter, mi::MethodInstance, worlds::WorldRange, edges::SimpleVector, @nospecialize(val))
    method = mi.def::Method
    tree = ccall(:jl_new_code_info_uninit, Ref{CodeInfo}, ())
    tree.code = Any[ ReturnNode(quoted(val)) ]
    nargs = Int(method.nargs)
    tree.slotnames = ccall(:jl_uncompress_argnames, Vector{Symbol}, (Any,), method.slot_syms)
    tree.slotflags = fill(0x00, nargs)
    tree.ssavaluetypes = 1
    tree.debuginfo = DebugInfo(mi)
    tree.ssaflags = [IR_FLAG_NULL]
    tree.rettype = Core.Typeof(val)
    tree.min_world = first(worlds)
    tree.max_world = last(worlds)
    tree.edges = edges
    tree.nargs = UInt(nargs)
    tree.isva = method.isva
    set_inlineable!(tree, true)
    tree.parent = mi
    return tree
end

result_is_constabi(interp::AbstractInterpreter, result::InferenceResult) =
    may_discard_trees(interp) && is_result_constabi_eligible(result)

# compute an inferred AST and return type
typeinf_code(interp::AbstractInterpreter, match::MethodMatch, run_optimizer::Bool) =
    typeinf_code(interp, specialize_method(match), run_optimizer)
typeinf_code(interp::AbstractInterpreter, method::Method, @nospecialize(atype), sparams::SimpleVector,
             run_optimizer::Bool) =
    typeinf_code(interp, specialize_method(method, atype, sparams), run_optimizer)
function typeinf_code(interp::AbstractInterpreter, mi::MethodInstance, run_optimizer::Bool)
    frame = typeinf_frame(interp, mi, run_optimizer)
    frame === nothing && return nothing
    return frame.src
end

"""
    typeinf_ircode(interp::AbstractInterpreter, match::MethodMatch,
                   optimize_until::Union{Int,String,Nothing}) -> (ir::Union{IRCode,Nothing}, returntype::Type)
    typeinf_ircode(interp::AbstractInterpreter,
                   method::Method, atype, sparams::SimpleVector,
                   optimize_until::Union{Int,String,Nothing}) -> (ir::Union{IRCode,Nothing}, returntype::Type)
    typeinf_ircode(interp::AbstractInterpreter, mi::MethodInstance,
                   optimize_until::Union{Int,String,Nothing}) -> (ir::Union{IRCode,Nothing}, returntype::Type)

Infer a `method` and return an `IRCode` with inferred `returntype` on success.
"""
typeinf_ircode(interp::AbstractInterpreter, match::MethodMatch,
               optimize_until::Union{Int,String,Nothing}) =
    typeinf_ircode(interp, specialize_method(match), optimize_until)
typeinf_ircode(interp::AbstractInterpreter, method::Method, @nospecialize(atype), sparams::SimpleVector,
               optimize_until::Union{Int,String,Nothing}) =
    typeinf_ircode(interp, specialize_method(method, atype, sparams), optimize_until)
function typeinf_ircode(interp::AbstractInterpreter, mi::MethodInstance,
                        optimize_until::Union{Int,String,Nothing})
    frame = typeinf_frame(interp, mi, false)
    if frame === nothing
        return nothing, Any
    end
    (; result) = frame
    opt = OptimizationState(frame, interp)
    ir = run_passes_ipo_safe(opt.src, opt, optimize_until)
    rt = widenconst(ignorelimited(result.result))
    return ir, rt
end

# compute an inferred frame
typeinf_frame(interp::AbstractInterpreter, match::MethodMatch, run_optimizer::Bool) =
    typeinf_frame(interp, specialize_method(match), run_optimizer)
typeinf_frame(interp::AbstractInterpreter, method::Method, @nospecialize(atype), sparams::SimpleVector,
              run_optimizer::Bool) =
    typeinf_frame(interp, specialize_method(method, atype, sparams), run_optimizer)
function typeinf_frame(interp::AbstractInterpreter, mi::MethodInstance, run_optimizer::Bool)
    result = InferenceResult(mi, typeinf_lattice(interp))
    frame = InferenceState(result, #=cache_mode=#:no, interp)
    frame === nothing && return nothing
    typeinf(interp, frame)
    is_inferred(frame) || return nothing
    if run_optimizer
        if result_is_constabi(interp, frame.result)
            rt = frame.result.result::Const
            edges = materialize_inference_edges(frame.edges)
            src = codeinfo_for_const(interp, frame.linfo, frame.valid_worlds, edges, rt.val)
        else
            opt = OptimizationState(frame, interp)
            optimize(interp, opt, frame.result)
            src = ir_to_codeinf!(opt, frame, materialize_inference_edges(opt.inlining.edges))
        end
        result.src = frame.src = src
    end
    return frame
end

# N.B.: These need to be aligned with the C side headers
"""
    SOURCE_MODE_NOT_REQUIRED

Indicates to inference that the source is not required and the only fields of
the resulting `CodeInstance` that the caller is interested in are return or
exception types and IPO effects. Inference is still free to create source for
it or add it to the JIT even, but is not required or expected to do so.
"""
const SOURCE_MODE_NOT_REQUIRED = 0x0

"""
    SOURCE_MODE_ABI

Indicates to inference that it should return a CodeInstance that can
be `->invoke`'d (because it has already been compiled).
"""
const SOURCE_MODE_ABI = 0x1

"""
    SOURCE_MODE_GET_SOURCE

Indicates to inference that it should return a CodeInstance after it has
prepared interp to be able to provide source code for it.
"""
const SOURCE_MODE_GET_SOURCE = 0xf

"""
    ci_has_abi(interp::AbstractInterpreter, code::CodeInstance)

Determine whether this CodeInstance is something that could be invoked if
interp gave it to the runtime system (either because it already has an ->invoke
ptr, or because interp has source that could be compiled).
"""
function ci_has_abi(interp::AbstractInterpreter, code::CodeInstance)
    (@atomic :acquire code.invoke) !== C_NULL && return true
    return ci_has_source(interp, code)
end

"""
    ci_has_source(interp::AbstractInterpreter, code::CodeInstance)

Determine whether this CodeInstance is something that will return something
compileable by ci_get_source.
"""
function ci_has_source(interp::AbstractInterpreter, code::CodeInstance)
    codegen = codegen_cache(interp)
    codegen === nothing && return false
    use_const_api(code) && return true
    inf = get(codegen, code, nothing)
    inf === nothing || return true
    inf = @atomic :monotonic code.inferred
    if isa(inf, String)
        inf = _uncompressed_ir(code, inf)
    end
    if isa(inf, CodeInfo)
        codegen[code] = inf
        return true
    end
    return false
end

# Get source if available for inlining, otherwise return nothing
# populates codegen cache for code, if successful
function ci_get_source(interp::AbstractInterpreter, code::CodeInstance, @nospecialize src)
    codegen = codegen_cache(interp)
    if codegen !== nothing
        inf = get(codegen, code, nothing)
        inf === nothing || return inf
    end
    if use_const_api(code)
        return codeinfo_for_const(interp, get_ci_mi(code), WorldRange(code.min_world, code.max_world), code.edges, code.rettype_const)
    end
    if isa(src, String)
        src = _uncompressed_ir(code, src)
    end
    if isa(src, CodeInfo)
        if codegen !== nothing
            codegen[code] = src
        end
        return src
    elseif isa(src, IRCode)
        error("IRCode is unexpected")
    end
    return nothing
end

function ci_get_source(interp::AbstractInterpreter, code::CodeInstance)
    return ci_get_source(interp, code, isdefined(code, :inferred) ? code.inferred : nothing)
end

function ci_has_invoke(code::CodeInstance)
    return (@atomic :monotonic code.invoke) !== C_NULL
end

function ci_meets_requirement(interp::AbstractInterpreter, code::CodeInstance, source_mode::UInt8)
    source_mode == SOURCE_MODE_NOT_REQUIRED && return true
    source_mode == SOURCE_MODE_ABI && return ci_has_abi(interp, code)
    source_mode == SOURCE_MODE_GET_SOURCE && return ci_has_source(interp, code)
    return false
end

function ci_worlds_cover(code::CodeInstance, valid_worlds::WorldRange)
    min_world = @atomic :acquire code.min_world
    max_world = @atomic :acquire code.max_world
    return min_world <= first(valid_worlds) && last(valid_worlds) <= max_world
end

function ci_cache_head(mi::MethodInstance)
    isdefined(mi, :cache, :acquire) || return nothing
    return @atomic :acquire mi.cache
end

function ci_cache_next(code::CodeInstance)
    isdefined(code, :next, :acquire) || return nothing
    return @atomic :acquire code.next
end

function find_cached_ci(interp::AbstractInterpreter, mi::MethodInstance,
                        valid_worlds::WorldRange, source_mode::UInt8)
    cache = code_cache(interp, valid_worlds)
    return find_cached_ci(interp, cache, mi, valid_worlds, source_mode)
end

function find_cached_ci(interp::AbstractInterpreter, cache, mi::MethodInstance,
                        valid_worlds::WorldRange, source_mode::UInt8)
    code = get(cache, mi, nothing)
    if (code isa CodeInstance &&
            ci_worlds_cover(code, valid_worlds) &&
            isdefined(code, :inferred, :acquire) &&
            ci_meets_requirement(interp, code, source_mode))
        return code
    end
    return nothing
end

function find_cached_ci(interp::AbstractInterpreter, cache::OverlayCodeCache,
                        mi::MethodInstance, valid_worlds::WorldRange, source_mode::UInt8)
    return find_cached_ci(interp, cache.globalcache, mi, valid_worlds, source_mode)
end

function find_cached_ci(interp::AbstractInterpreter, cache::InternalCodeCache,
                        mi::MethodInstance, valid_worlds::WorldRange, source_mode::UInt8)
    # `jl_rettype_inferred` returns the first inferred CI spanning the requested
    # worlds, without considering whether it carries source or an ABI. Once a
    # source-less CI is at the head of the native cache, repeatedly looking only at
    # that entry would publish a new source-capable CI for every ABI/source request.
    # Walk the native cache chain to find the first entry that satisfies the full
    # request. Cache wrappers dispatch back to this implementation through their
    # underlying global cache. A concurrent `jl_mi_cache_insert` may briefly make
    # the chain circular while moving an existing CI; like the C-side walkers
    # (e.g. `jl_get_ci_equiv`), keep following `next` until the writer's fixup
    # store lands.
    code = ci_cache_head(mi)
    while code !== nothing
        if (ci_worlds_cover(code, valid_worlds) &&
                code.owner === cache.owner &&
                isdefined(code, :inferred, :acquire) &&
                ci_meets_requirement(interp, code, source_mode))
            return code
        end
        code = ci_cache_next(code)
    end
    return nothing
end

function ci_is_equivalent_winner(candidate::CodeInstance, ci::CodeInstance,
                                 valid_worlds::WorldRange)
    return (candidate !== ci &&
        ci_worlds_cover(candidate, valid_worlds) &&
        candidate.def === ci.def &&
        candidate.owner === ci.owner &&
        isdefined(candidate, :inferred, :acquire) &&
        isdefined(candidate, :rettype) &&
        candidate.rettype === ci.rettype)
end

function find_equivalent_cached_ci(interp::AbstractInterpreter, cache,
                                   ci::CodeInstance, valid_worlds::WorldRange)
    candidate = get(cache, get_ci_mi(ci), nothing)
    return (candidate isa CodeInstance &&
        ci_is_equivalent_winner(candidate, ci, valid_worlds)) ? candidate : nothing
end

function find_equivalent_cached_ci(interp::AbstractInterpreter,
                                   cache::OverlayCodeCache, ci::CodeInstance,
                                   valid_worlds::WorldRange)
    return find_equivalent_cached_ci(
        interp, cache.globalcache, ci, valid_worlds)
end

function find_equivalent_cached_ci(::AbstractInterpreter,
                                   ::InternalCodeCache, ci::CodeInstance,
                                   valid_worlds::WorldRange)
    candidate = ci_cache_head(get_ci_mi(ci))
    while candidate !== nothing
        ci_is_equivalent_winner(candidate, ci, valid_worlds) && return candidate
        candidate = ci_cache_next(candidate)
    end
    return nothing
end

function find_equivalent_cached_ci(interp::AbstractInterpreter, ci::CodeInstance,
                                   valid_worlds::WorldRange)
    cache = code_cache(interp, valid_worlds)
    return find_equivalent_cached_ci(interp, cache, ci, valid_worlds)
end

function find_local_cached_ci(interp::AbstractInterpreter, mi::MethodInstance,
                              valid_worlds::WorldRange, source_mode::UInt8)
    cache = get_inference_cache(interp)
    indices = get_indices(cache, mi)
    world = get_inference_world(interp)
    for i in length(indices):-1:1
        cached = cache.results[indices[i]]
        cached isa LocalInferenceResult || continue
        result = cached.result
        result.overridden_by_const === nothing || continue
        result.cache_world == world || continue
        world in proof_worlds(cached.proof) || continue
        isdefined(result, :ci) || continue
        code = result.ci
        if (ci_worlds_cover(code, valid_worlds) &&
                isdefined(code, :inferred, :acquire) &&
                ci_meets_requirement(interp, code, source_mode))
            return code
        end
    end
    return nothing
end

function find_typeinf_cached_ci(interp::AbstractInterpreter, mi::MethodInstance,
                                valid_worlds::WorldRange, source_mode::UInt8)
    code = find_cached_ci(interp, mi, valid_worlds, source_mode)
    code === nothing || return code
    return find_local_cached_ci(interp, mi, valid_worlds, source_mode)
end

# compute (and cache) an inferred AST and return type
function typeinf_ext(interp::AbstractInterpreter, mi::MethodInstance, source_mode::UInt8)
    start_time = ccall(:jl_typeinf_timing_begin, UInt64, ())
    valid_worlds = WorldRange(get_inference_world(interp))
    let code = find_typeinf_cached_ci(interp, mi, valid_worlds, source_mode)
        if code !== nothing
            ccall(:jl_typeinf_timing_end, Cvoid, (UInt64, Cint), start_time, 0)
            return code
        end
    end
    def = mi.def
    ci = engine_reserve(interp, mi)
    # check cache again if it is still new after reserving in the engine
    let code = find_typeinf_cached_ci(interp, mi, valid_worlds, source_mode)
        if code !== nothing
            engine_reject(interp, ci)
            ccall(:jl_typeinf_timing_end, Cvoid, (UInt64, Cint), start_time, 0)
            return code
        end
    end
    if !InferenceParams(interp).force_enable_inference
        if isa(def, Method) && ccall(:jl_get_module_infer, Cint, (Any,), def.module) == 0
            src = retrieve_code_info(mi, get_inference_world(interp))
            if src isa CodeInfo
                finish!(interp, mi, ci, src)
            else
                engine_reject(interp, ci)
                ccall(:jl_typeinf_timing_end, Cvoid, (UInt64, Cint), start_time, 0)
                return nothing
            end
            ccall(:jl_typeinf_timing_end, Cvoid, (UInt64, Cint), start_time, 0)
            return ci
        end
    end
    result = InferenceResult(mi, typeinf_lattice(interp))
    result.ci = ci
    frame = InferenceState(result, #=cache_mode=#:global, interp)
    if frame === nothing
        engine_reject(interp, ci)
        ccall(:jl_typeinf_timing_end, Cvoid, (UInt64, Cint), start_time, 0)
        return nothing
    end
    typeinf(interp, frame)
    ccall(:jl_typeinf_timing_end, Cvoid, (UInt64, Cint), start_time, 0)

    publication_winner = result.replacement_ci
    ci = if (publication_winner !== nothing &&
             ci_meets_requirement(interp, publication_winner, source_mode))
        publication_winner
    else
        result.ci
    end
    codegen = codegen_cache(interp)
    @assert frame.cache_mode != CACHE_MODE_NULL
    @assert isdefined(ci, :inferred) "interpreter did not fulfill our expectations"
    @assert codegen === nothing || ci_meets_requirement(interp, ci, source_mode)
    if ci === result.ci
        @assert is_result_constabi_eligible(result) || codegen === nothing || haskey(codegen, ci)
        @assert is_result_constabi_eligible(result) == use_const_api(ci)
    end
    return ci
end

# compute (and cache) an inferred AST and return the inferred return type
function typeinf_type(interp::AbstractInterpreter, method::Method, @nospecialize(atype), sparams::SimpleVector)
    if contains_is(unwrap_unionall(atype).parameters, Union{})
        return Union{} # don't ask: it does weird and unnecessary things, if it occurs during bootstrap
    end
    return typeinf_type(interp, specialize_method(method, atype, sparams))
end
typeinf_type(interp::AbstractInterpreter, match::MethodMatch) =
    typeinf_type(interp, specialize_method(match))
function typeinf_type(interp::AbstractInterpreter, mi::MethodInstance)
    ci = typeinf_ext(interp, mi, SOURCE_MODE_NOT_REQUIRED)
    ci isa CodeInstance || return nothing
    return ci.rettype
end

# Resolve a call, as described by `argtype` to a single matching
# Method and return a compilable MethodInstance for the call, if
# it will be runtime-dispatched to exactly that MethodInstance
function compileable_specialization_for_call(interp::AbstractInterpreter, @nospecialize(argtype))
    mt = ccall(:jl_method_table_for, Any, (Any,), argtype)
    if mt === nothing
        # this would require scanning all method tables, so give up instead
        return nothing
    end

    matches = findall(argtype, method_table(interp); limit = 1)
    matches === nothing && return nothing
    length(matches.matches) == 0 && return nothing
    match = only(matches.matches)

    compileable_atype = get_compileable_sig(match.method, match.spec_types, match.sparams)
    compileable_atype === nothing && return nothing
    if match.spec_types !== compileable_atype
        (_, sparams) = typeintersect_env(compileable_atype, match.method.sig)
        mi = specialize_method(match.method, compileable_atype, sparams)
    else
        mi = specialize_method(match.method, compileable_atype, match.sparams)
    end

    return mi
end

const QueueItems = Union{CodeInstance,MethodInstance,SimpleVector}

struct CompilationQueue
    tocompile::Vector{QueueItems}
    inspected::IdSet{QueueItems}
    interp::Union{AbstractInterpreter,Nothing}

    CompilationQueue(;
        interp::Union{AbstractInterpreter,Nothing}
    ) = new(QueueItems[], IdSet{QueueItems}(), interp)

    CompilationQueue(queue::CompilationQueue;
        interp::Union{AbstractInterpreter,Nothing}
    ) = new(empty!(queue.tocompile), empty!(queue.inspected), interp)
end

Base.push!(queue::CompilationQueue, item) = push!(queue.tocompile, item)
Base.append!(queue::CompilationQueue, items) = append!(queue.tocompile, items)
Base.pop!(queue::CompilationQueue) = pop!(queue.tocompile)
Base.empty!(queue::CompilationQueue) = (empty!(queue.tocompile); empty!(queue.inspected))
markinspected!(queue::CompilationQueue, item) = push!(queue.inspected, item)
isinspected(queue::CompilationQueue, item) = item in queue.inspected
Base.isempty(queue::CompilationQueue) = isempty(queue.tocompile)

function has_valid_abi_sparams(mi::MethodInstance)
    isa(mi.specTypes, UnionAll) && return false
    def = mi.def
    isa(def, Method) || return true
    unionall_depth(def.sig) == length(mi.sparam_vals) || return false
    for i = 1:length(mi.sparam_vals)
        sp = mi.sparam_vals[i]
        if isa(sp, SimpleVector) || isvarargtype(sp)
            return false
        end
    end
    return true
end

# collect a list of all code that is needed along with CodeInstance to codegen it fully
function collectinvokes!(workqueue::CompilationQueue, ci::CodeInfo, sptypes::Vector{VarState};
                         invokelatest_queue::Union{CompilationQueue,Nothing} = nothing,
                         enqueue_unprepared_invokes::Bool = false)
    src = ci.code
    for i = 1:length(src)
        stmt = src[i]
        isexpr(stmt, :(=)) && (stmt = stmt.args[2])
        if isexpr(stmt, :invoke) || isexpr(stmt, :invoke_modify)
            edge = stmt.args[1]
            if edge isa CodeInstance && has_valid_abi_sparams(get_ci_mi(edge)) &&
                    (enqueue_unprepared_invokes ||
                     ci_has_invoke(edge) || ci_has_source(workqueue.interp, edge) ||
                     !iszero(ccall(:jl_mi_cache_has_ci, Cint, (Any, Any), get_ci_mi(edge), edge)))
                # The globally-cached check keeps batches closed under invoke
                # edges even when the edge's source lives only in another
                # interpreter's codegen cache (activation clears `inferred`,
                # so `ci_has_source` cannot see it): the drain loops re-infer
                # such edges, preventing them from silently leaking to
                # permanent `tojlinvoke` fallbacks at link time. Uncached
                # speculative edges must NOT be enqueued unconditionally:
                # resolved invoke edges of recursion that inference widened
                # (e.g. self-recursion with a growing tuple argument) form an
                # unbounded chain of fresh signatures, and re-inferring each
                # one would enqueue the next forever.
                push!(workqueue, edge)
            elseif enqueue_unprepared_invokes && edge isa MethodInstance && has_valid_abi_sparams(edge)
                push!(workqueue, edge)
            end
        end

        invokelatest_queue === nothing && continue
        if isexpr(stmt, :call)
            farg = stmt.args[1]
            !applicable(argextype, farg, ci, sptypes) && continue # TODO: Why is this failing during bootstrap
            ftyp = argextype_widened(farg, ci, sptypes)

            if ftyp === typeof(Core.finalizer) && 3 <= length(stmt.args) <= 5
                finalizer = argextype(stmt.args[2], ci, sptypes)
                obj = argextype(stmt.args[3], ci, sptypes)
                atype = argtypes_to_type(Any[finalizer, obj])
            else
                # No dynamic dispatch to resolve / enqueue
                continue
            end
        elseif isexpr(stmt, :cfunction) && length(stmt.args) == 5
            (_, f, _, at, _) = stmt.args
            linfo = ci.parent

            linfo isa MethodInstance || continue
            at isa SimpleVector || continue

            ft = argextype(f, ci, sptypes)
            argtypes = Any[ft]
            for i = 1:length(at)
                push!(argtypes, sp_type_rewrap(at[i], linfo, #= isreturn =# false))
            end
            atype = argtypes_to_type(argtypes)
        elseif isexpr(stmt, :new)
            # When creating a struct of Function type, check to see if we should
            # proactively compile the lambda
            t, _, _, _ = instanceof_tfunc(argextype(stmt.args[1], ci, sptypes))
            t <: Function || continue
            atype = Tuple{t, Vararg}
        else
            # TODO: handle other StmtInfo like OpaqueClosure?
            continue
        end
        let workqueue = invokelatest_queue
            # make a best-effort attempt to enqueue the relevant code for the dynamic invokelatest call
            mi = compileable_specialization_for_call(workqueue.interp, atype)
            mi === nothing && continue

            push!(workqueue, mi)
        end
    end
end

function add_codeinsts_to_jit!(interp::AbstractInterpreter, ci, source_mode::UInt8)
    source_mode == SOURCE_MODE_ABI || return ci
    ci isa CodeInstance && !ci_has_invoke(ci) || return ci
    codegen = codegen_cache(interp)
    codegen === nothing && return ci
    workqueue = CompilationQueue(; interp)
    push!(workqueue, ci)
    codeinsts, srcs = Any[], Any[]
    while !isempty(workqueue)
        # ci_has_real_invoke(ci) && return ci # optimization: cease looping if ci happens to get compiled (not just jl_fptr_wait_for_compiled, but fully jl_is_compiled_codeinst)
        callee = pop!(workqueue)
        ci_has_invoke(callee) && continue
        isinspected(workqueue, callee) && continue
        if !has_valid_abi_sparams(get_ci_mi(callee))
            markinspected!(workqueue, callee)
            continue
        end
        let cached = ccall(:jl_get_ci_equiv, Any, (Any, UInt), callee, get_inference_world(workqueue.interp))::CodeInstance
            if cached !== callee
                markinspected!(workqueue, callee)
                continue
            end
        end
        src = ci_get_source(interp, callee)
        if !isa(src, CodeInfo)
            newcallee = typeinf_ext(workqueue.interp, callee.def, source_mode) # always SOURCE_MODE_ABI
            if newcallee isa CodeInstance
                callee === ci && (ci = newcallee) # ci stopped meeting the requirements after typeinf_ext last checked, try again with newcallee
                push!(workqueue, newcallee)
            end
            if newcallee !== callee
                markinspected!(workqueue, callee)
            end
            continue
        end
        markinspected!(workqueue, callee)
        mi = get_ci_mi(callee)
        sptypes = sptypes_from_meth_instance(mi)
        collectinvokes!(workqueue, src, sptypes)
        if iszero(ccall(:jl_mi_cache_has_ci, Cint, (Any, Any), mi, callee))
            valid_worlds = WorldRange(get_inference_world(workqueue.interp))
            cached = find_equivalent_cached_ci(
                workqueue.interp, callee, valid_worlds)
            if cached === nothing
                # make sure callee is gc-rooted and cached, as required by jl_add_codeinsts_to_jit
                code_cache(workqueue.interp)[mi] = callee
            else
                # use an existing CI from the cache, if there is available one that is compatible
                callee === ci && (ci = cached)
                callee = cached
            end
        end
        push!(codeinsts, callee)
        push!(srcs, src)
    end
    ccall(:jl_add_codeinsts_to_jit, Cvoid, (Any, Any), codeinsts, srcs)
    return ci
end

function typeinf_ext_toplevel(interp::AbstractInterpreter, mi::MethodInstance, source_mode::UInt8)
    mi2 = ccall(:jl_normalize_to_compilable_mi, Any, (Any,), mi)::MethodInstance
    ci = typeinf_ext(interp, mi2, source_mode)
    ci = add_codeinsts_to_jit!(interp, ci, source_mode)
    return ci
end

# This is a bridge for the C code calling `jl_typeinf_func()` on a single Method match
function typeinf_ext_toplevel(mi::MethodInstance, world::UInt, source_mode::UInt8, trim_mode::UInt8)
    inf_params = InferenceParams(; force_enable_inference = trim_mode != TRIM_NO)
    interp = NativeInterpreter(world; inf_params)
    return typeinf_ext_toplevel(interp, mi, source_mode)
end

function compile!(codeinfos::Vector{Any}, workqueue::CompilationQueue;
    invokelatest_queue::Union{CompilationQueue,Nothing} = nothing,
    enqueue_unprepared_invokes::Bool = false,
)
    interp = workqueue.interp
    world = get_inference_world(interp)
    while !isempty(workqueue)
        item = pop!(workqueue)
        # each item in this list is either a MethodInstance indicating something
        # to compile, or an svec(rettype, sig) describing a C-callable alias to create.
        if item isa MethodInstance
            isinspected(workqueue, item) && continue
            # if this method is generally visible to the current compilation world,
            # and this is either the primary world, or not applicable in the primary world
            # then we want to compile and emit this
            if item.def.primary_world <= world
                ci = typeinf_ext(interp, item, SOURCE_MODE_GET_SOURCE)
                ci isa CodeInstance && push!(workqueue, ci)
            end
            markinspected!(workqueue, item)
        elseif item isa SimpleVector
            invokelatest_queue === nothing && continue
            (rt::Type, sig::Type) = item
            # make a best-effort attempt to enqueue the relevant code for the ccallable
            mi = ccall(:jl_get_specialization1, Any, (Any, Csize_t), sig, world)
            if mi !== nothing
                mi = mi::MethodInstance
                ci = typeinf_ext(interp, mi, SOURCE_MODE_GET_SOURCE)
                ci isa CodeInstance && push!(invokelatest_queue, ci)
            end
            # additionally enqueue the ccallable entrypoint / adapter, which implicitly
            # invokes the above ci
            push!(codeinfos, item)
        elseif item isa CodeInstance
            callee = item
            isinspected(workqueue, callee) && continue
            mi = get_ci_mi(callee)
            if !has_valid_abi_sparams(mi)
                markinspected!(workqueue, callee)
                continue
            end
            # now make sure everything has source code, if desired
            if use_const_api(callee)
                src = codeinfo_for_const(interp, mi, WorldRange(callee.min_world, callee.max_world), callee.edges, callee.rettype_const)
            else
                src = get(interp.codegen, callee, nothing)
                if src === nothing
                    newcallee = typeinf_ext(interp, mi, SOURCE_MODE_GET_SOURCE)
                    if newcallee isa CodeInstance
                        @assert use_const_api(newcallee) || haskey(interp.codegen, newcallee)
                        push!(workqueue, newcallee)
                    end
                    if newcallee !== callee
                        markinspected!(workqueue, callee)
                    end
                    continue
                end
            end
            markinspected!(workqueue, callee)
            if src isa CodeInfo
                sptypes = sptypes_from_meth_instance(mi)
                collectinvokes!(workqueue, src, sptypes; invokelatest_queue,
                                enqueue_unprepared_invokes)
                # try to reuse an existing CodeInstance from before to avoid making duplicates in the cache
                if iszero(ccall(:jl_mi_cache_has_ci, Cint, (Any, Any), mi, callee))
                    cached = find_equivalent_cached_ci(
                        interp, callee, WorldRange(world))
                    if cached === nothing
                        code_cache(interp)[mi] = callee
                    else
                        # Use an existing CI from the cache, if there is available one that is compatible
                        callee = cached
                    end
                end
                push!(codeinfos, callee)
                push!(codeinfos, src)
            end
        else @assert false "unexpected item in queue" end
    end
    return codeinfos
end

# This is a bridge for the C code calling `jl_typeinf_func()` on set of Method matches
# The trim_mode can be any of:
const TRIM_NO = 0x0
const TRIM_SAFE = 0x1
const TRIM_UNSAFE = 0x2
const TRIM_UNSAFE_WARN = 0x3
function typeinf_ext_toplevel(methods::Vector{Any}, worlds::Vector{UInt}, trim_mode::UInt8)
    # During `--trim`, infer against an isolated cache namespace. The owner is re-stamped
    # back to `nothing` at serialization time (see `src/staticdata.c`).
    cache_owner = trim_mode == TRIM_NO ? nothing : :trim
    inf_params = InferenceParams(; force_enable_inference = trim_mode != TRIM_NO, cache_owner)

    # Create an "invokelatest" queue to enable eager compilation of speculative
    # invokelatest calls such as from `Core.finalizer` and `ccallable`
    invokelatest_queue = CompilationQueue(;
        interp = NativeInterpreter(get_world_counter(); inf_params)
    )

    codeinfos = []
    workqueue = CompilationQueue(; interp = nothing)
    for this_world in reverse!(sort!(worlds))
        workqueue = CompilationQueue(workqueue;
            interp = NativeInterpreter(this_world; inf_params)
        )

        append!(workqueue, methods)
        compile!(codeinfos, workqueue; invokelatest_queue,
                 enqueue_unprepared_invokes = trim_mode != TRIM_NO)
    end

    if invokelatest_queue !== nothing
        # This queue is intentionally aliased, to handle e.g. a `finalizer` calling `Core.finalizer`
        # (it will enqueue into itself and immediately drain)
        compile!(codeinfos, invokelatest_queue; invokelatest_queue,
                 enqueue_unprepared_invokes = trim_mode != TRIM_NO)
    end

    if trim_mode != TRIM_NO && trim_mode != TRIM_UNSAFE
        verify_typeinf_trim(codeinfos, trim_mode == TRIM_UNSAFE_WARN)
    end

    # Build the ordered list of CodeInstances to store in the image's method
    # caches. This is kept as its own array (rather than being recovered from
    # `codeinfos` by the caller) so the set and ordering of cached entries can be
    # chosen independently of what native code gets emitted. The linked list of
    # each MethodInstance's cache is rebuilt from this order during serialization
    # (see jl_rewrite_mi_caches in staticdata.c).
    #
    # First the compiled entries, in compilation order: every entry paired with a
    # CodeInfo in `codeinfos` is inferred and about to be compiled, so it lands in
    # the single invoke+inferred group that jl_mi_cache_insert (gf.c) keeps at the
    # front, and the compilation order already lists higher-`max_world` entries
    # first (worlds are processed newest-first).
    cis = Any[]
    seen = IdSet{CodeInstance}()
    for i = 1:length(codeinfos)
        item = codeinfos[i]
        if item isa CodeInstance && !(item in seen)
            push!(seen, item)
            push!(cis, item)
        end
    end

    # Then walk each CodeInstance's forward `edges` recursively and append every
    # reachable CodeInstance. These callees are inferred but were not compiled
    # (no `invoke` assigned), so appending them after the compiled entries places
    # them in gf.c's inferred (post-invoke) group within each MethodInstance's
    # cache. Preserving them keeps the inference results callers depend on from
    # being dropped by the cache-clearing pass in staticdata.c. `cis` doubles as
    # the worklist, so edges discovered from appended entries are visited too.
    #
    # Skip under `--trim` where inferred-but-not-compiled entries are not useful
    # at runtime without a Compiler / JIT.
    if trim_mode == TRIM_NO
        i = 1
        while i <= length(cis)
            ci = cis[i]::CodeInstance
            if isdefined(ci, :edges)
                edges = ci.edges
                for j = 1:length(edges)
                    isassigned(edges, j) || continue
                    edge = edges[j]
                    if edge isa CodeInstance && !(edge in seen)
                        push!(seen, edge)
                        push!(cis, edge)
                    end
                end
            end
            i += 1
        end
    end

    # Keep cache CodeInstances that represent an existing cache entry: either they are
    # already linked into their MethodInstance's cache, or jl_get_ci_equiv finds
    # another equivalent already cached for them.
    # This hack avoids putting badly inferred edges in the cache, while still trying to populate the cache sufficiently.
    filter!(cis) do ci
        ci = ci::CodeInstance
        mi = get_ci_mi(ci)
        return !iszero(ccall(:jl_mi_cache_has_ci, Cint, (Any, Any), mi, ci)) ||
            ccall(:jl_get_ci_equiv, Any, (Any, UInt), ci, 0x0)::CodeInstance !== ci
    end

    return Core.svec(codeinfos, cis)
end

const _verify_trim_world_age = RefValue{UInt}(typemax(UInt))
verify_typeinf_trim(codeinfos::Vector{Any}, onlywarn::Bool) = Core._call_in_world(_verify_trim_world_age[], verify_typeinf_trim, Base.stderr, codeinfos, onlywarn)

function _return_type_opaque_closure(@nospecialize(oc::Core.OpaqueClosure), t::DataType)
    ocargt, ocrt = typeof(oc).parameters
    hasintersect(t, ocargt) || return Union{}
    return ocrt
end

function return_type(@nospecialize(f), t::DataType) # this method has a special tfunc
    isa(f, Core.OpaqueClosure) && return _return_type_opaque_closure(f, t)
    world = tls_world_age()
    args = Any[_return_type, NativeInterpreter(world), Tuple{Core.Typeof(f), t.parameters...}]
    return ccall(:jl_call_in_typeinf_world, Any, (Ptr{Any}, Cint), args, length(args))
end

function return_type(@nospecialize(f), t::DataType, world::UInt)
    isa(f, Core.OpaqueClosure) && return _return_type_opaque_closure(f, t)
    return return_type(Tuple{Core.Typeof(f), t.parameters...}, world)
end

function return_type(t::DataType)
    world = tls_world_age()
    return return_type(t, world)
end

function return_type(t::DataType, world::UInt)
    args = Any[_return_type, NativeInterpreter(world), t]
    return ccall(:jl_call_in_typeinf_world, Any, (Ptr{Any}, Cint), args, length(args))
end

function _return_type(interp::AbstractInterpreter, t::DataType)
    rt = Union{}
    f = singleton_type(t.parameters[1])
    if isa(f, Builtin)
        args = Any[t.parameters...]
        popfirst!(args)
        rt = builtin_tfunction(interp, f, args, nothing)
        rt = widenconst(rt)
    else
        for match in _methods_by_ftype(t, -1, get_inference_world(interp))::Vector
            ty = typeinf_type(interp, match::MethodMatch)
            ty === nothing && return Any
            rt = tmerge(rt, ty)
            rt === Any && break
        end
    end
    return rt
end