# This file is a part of Julia. License is MIT: https://julialang.org/license """ AbstractInterpreter An abstract base class that allows multiple dispatch to determine the method of executing Julia code. The native Julia-LLVM pipeline is enabled by using the `NativeInterpreter` concrete instantiation of this abstract class, others can be swapped in as long as they follow the `AbstractInterpreter` API. If `interp::NewInterpreter` is an `AbstractInterpreter`, it is expected to provide at least the following methods to satisfy the `AbstractInterpreter` API requirement: - `InferenceParams(interp::NewInterpreter)` - return an `InferenceParams` instance - `OptimizationParams(interp::NewInterpreter)` - return an `OptimizationParams` instance - `get_world_counter(interp::NewInterpreter)` - return the world age for this interpreter - `get_inference_cache(interp::NewInterpreter)` - return the local inference cache - `code_cache(interp::NewInterpreter)` - return the global inference cache """ abstract type AbstractInterpreter end abstract type AbstractLattice end struct ArgInfo fargs::Union{Nothing,Vector{Any}} argtypes::Vector{Any} end struct StmtInfo """ If `used` is false, we know that the return value is statically unused and need thus not be computed. """ used::Bool end abstract type ForwardableArgtypes end """ InferenceResult(linfo::MethodInstance) InferenceResult(linfo::MethodInstance, argtypes::ForwardableArgtypes) A type that represents the result of running type inference on a chunk of code. See also [`matching_cache_argtypes`](@ref). """ mutable struct InferenceResult linfo::MethodInstance argtypes::Vector{Any} overridden_by_const::BitVector result # ::Type, or InferenceState if WIP src # ::Union{CodeInfo, IRCode, OptimizationState} if inferred copy is available, nothing otherwise valid_worlds::WorldRange # if inference and optimization is finished ipo_effects::Effects # if inference is finished effects::Effects # if optimization is finished argescapes # ::ArgEscapeCache if optimized, nothing otherwise must_be_codeinf::Bool # if this must come out as CodeInfo or leaving it as IRCode is ok function InferenceResult(linfo::MethodInstance, cache_argtypes::Vector{Any}, overridden_by_const::BitVector) return new(linfo, cache_argtypes, overridden_by_const, Any, nothing, WorldRange(), Effects(), Effects(), nothing, true) end end function InferenceResult(linfo::MethodInstance; lattice::AbstractLattice=fallback_lattice) return InferenceResult(linfo, matching_cache_argtypes(lattice, linfo)...) end function InferenceResult(linfo::MethodInstance, argtypes::ForwardableArgtypes; lattice::AbstractLattice=fallback_lattice) return InferenceResult(linfo, matching_cache_argtypes(lattice, linfo, argtypes)...) end """ inf_params::InferenceParams Parameters that control abstract interpretation-based type inference operation. --- - `inf_params.max_methods::Int = 3`\\ Type inference gives up analysis on a call when there are more than `max_methods` matching methods. This trades off between compiler latency and generated code performance. Typically, considering many methods means spending _lots_ of time obtaining poor type information, so this option should be kept low. [`Base.Experimental.@max_methods`](@ref) can have a more fine-grained control on this configuration with per-module or per-method annotation basis. --- - `inf_params.max_union_splitting::Int = 4`\\ Specifies the maximum number of union-tuples to swap or expand before computing the set of matching methods or conditional types. --- - `inf_params.max_apply_union_enum::Int = 8`\\ Specifies the maximum number of union-tuples to swap or expand when inferring a call to `Core._apply_iterate`. --- - `inf_params.max_tuple_splat::Int = 32`\\ When attempting to infer a call to `Core._apply_iterate`, abort the analysis if the tuple contains more than this many elements. --- - `inf_params.tuple_complexity_limit_depth::Int = 3`\\ Specifies the maximum depth of large tuple type that can appear as specialized method signature when inferring a recursive call graph. --- - `inf_params.ipo_constant_propagation::Bool = true`\\ If `false`, disables analysis with extended lattice information, i.e. disables any of the concrete evaluation, semi-concrete interpretation and constant propagation entirely. [`Base.@constprop :none`](@ref Base.@constprop) can have a more fine-grained control on this configuration with per-method annotation basis. --- - `inf_params.aggressive_constant_propagation::Bool = false`\\ If `true`, forces constant propagation on any methods when any extended lattice information available. [`Base.@constprop :aggressive`](@ref Base.@constprop) can have a more fine-grained control on this configuration with per-method annotation basis. --- - `inf_params.unoptimize_throw_blocks::Bool = true`\\ If `true`, skips inferring calls that are in a block that is known to `throw`. It may improve the compiler latency without sacrificing the runtime performance in common situations. --- - `inf_params.assume_bindings_static::Bool = false`\\ If `true`, assumes that no new bindings will be added, i.e. a non-existing binding at inference time can be assumed to always not exist at runtime (and thus e.g. any access to it will `throw`). Defaults to `false` since this assumption does not hold in Julia's semantics for native code execution. --- """ struct InferenceParams max_methods::Int max_union_splitting::Int max_apply_union_enum::Int max_tuple_splat::Int tuple_complexity_limit_depth::Int ipo_constant_propagation::Bool aggressive_constant_propagation::Bool unoptimize_throw_blocks::Bool assume_bindings_static::Bool function InferenceParams( max_methods::Int, max_union_splitting::Int, max_apply_union_enum::Int, max_tuple_splat::Int, tuple_complexity_limit_depth::Int, ipo_constant_propagation::Bool, aggressive_constant_propagation::Bool, unoptimize_throw_blocks::Bool, assume_bindings_static::Bool) return new( max_methods, max_union_splitting, max_apply_union_enum, max_tuple_splat, tuple_complexity_limit_depth, ipo_constant_propagation, aggressive_constant_propagation, unoptimize_throw_blocks, assume_bindings_static) end end function InferenceParams( params::InferenceParams = InferenceParams( # default constructor #=max_methods::Int=# 3, #=max_union_splitting::Int=# 4, #=max_apply_union_enum::Int=# 8, #=max_tuple_splat::Int=# 32, #=tuple_complexity_limit_depth::Int=# 3, #=ipo_constant_propagation::Bool=# true, #=aggressive_constant_propagation::Bool=# false, #=unoptimize_throw_blocks::Bool=# true, #=assume_bindings_static::Bool=# false); max_methods::Int = params.max_methods, max_union_splitting::Int = params.max_union_splitting, max_apply_union_enum::Int = params.max_apply_union_enum, max_tuple_splat::Int = params.max_tuple_splat, tuple_complexity_limit_depth::Int = params.tuple_complexity_limit_depth, ipo_constant_propagation::Bool = params.ipo_constant_propagation, aggressive_constant_propagation::Bool = params.aggressive_constant_propagation, unoptimize_throw_blocks::Bool = params.unoptimize_throw_blocks, assume_bindings_static::Bool = params.assume_bindings_static) return InferenceParams( max_methods, max_union_splitting, max_apply_union_enum, max_tuple_splat, tuple_complexity_limit_depth, ipo_constant_propagation, aggressive_constant_propagation, unoptimize_throw_blocks, assume_bindings_static) end """ opt_params::OptimizationParams Parameters that control optimizer operation. --- - `opt_params.inlining::Bool = inlining_enabled()`\\ Controls whether or not inlining is enabled. --- - `opt_params.inline_cost_threshold::Int = 100`\\ Specifies the number of CPU cycles beyond which it's not worth inlining. --- - `opt_params.inline_nonleaf_penalty::Int = 1000`\\ Specifies the penalty cost for a dynamic dispatch. --- - `opt_params.inline_tupleret_bonus::Int = 250`\\ Specifies the extra inlining willingness for a method specialization with non-concrete tuple return types (in hopes of splitting it up). `opt_params.inline_tupleret_bonus` will be added to `opt_params.inline_cost_threshold` when making inlining decision. --- - `opt_params.inline_error_path_cost::Int = 20`\\ Specifies the penalty cost for an un-optimized dynamic call in a block that is known to `throw`. See also [`(inf_params::InferenceParams).unoptimize_throw_blocks`](@ref InferenceParams). --- - `opt_params.max_tuple_splat::Int = 32`\\ When attempting to inline `Core._apply_iterate`, abort the optimization if the tuple contains more than this many elements. --- - `opt_params.compilesig_invokes::Bool = true`\\ If `true`, gives the inliner license to change which `MethodInstance` to invoke when generating `:invoke` expression based on the [`@nospecialize`](@ref) annotation, in order to avoid over-specialization. --- - `opt_params.trust_inference::Bool = false`\\ If `false`, the inliner will unconditionally generate a fallback block when union-splitting a callsite, in case of existing subtyping bugs. This option may be removed in the future. --- - `opt_params.assume_fatal_throw::Bool = false`\\ If `true`, gives the optimizer license to assume that any `throw` is fatal and thus the state after a `throw` is not externally observable. In particular, this gives the optimizer license to move side effects (that are proven not observed within a particular code path) across a throwing call. Defaults to `false`. --- """ struct OptimizationParams inlining::Bool inline_cost_threshold::Int inline_nonleaf_penalty::Int inline_tupleret_bonus::Int inline_error_path_cost::Int max_tuple_splat::Int compilesig_invokes::Bool trust_inference::Bool assume_fatal_throw::Bool function OptimizationParams( inlining::Bool, inline_cost_threshold::Int, inline_nonleaf_penalty::Int, inline_tupleret_bonus::Int, inline_error_path_cost::Int, max_tuple_splat::Int, compilesig_invokes::Bool, trust_inference::Bool, assume_fatal_throw::Bool) return new( inlining, inline_cost_threshold, inline_nonleaf_penalty, inline_tupleret_bonus, inline_error_path_cost, max_tuple_splat, compilesig_invokes, trust_inference, assume_fatal_throw) end end function OptimizationParams( params::OptimizationParams = OptimizationParams( #=inlining::Bool=# inlining_enabled(), #=inline_cost_threshold::Int=# 100, #=inline_nonleaf_penalty::Int=# 1000, #=inline_tupleret_bonus::Int=# 250, #=inline_error_path_cost::Int=# 20, #=max_tuple_splat::Int=# 32, #=compilesig_invokes::Bool=# true, #=trust_inference::Bool=# false, #=assume_fatal_throw::Bool=# false); inlining::Bool = params.inlining, inline_cost_threshold::Int = params.inline_cost_threshold, inline_nonleaf_penalty::Int = params.inline_nonleaf_penalty, inline_tupleret_bonus::Int = params.inline_tupleret_bonus, inline_error_path_cost::Int = params.inline_error_path_cost, max_tuple_splat::Int = params.max_tuple_splat, compilesig_invokes::Bool = params.compilesig_invokes, trust_inference::Bool = params.trust_inference, assume_fatal_throw::Bool = params.assume_fatal_throw) return OptimizationParams( inlining, inline_cost_threshold, inline_nonleaf_penalty, inline_tupleret_bonus, inline_error_path_cost, max_tuple_splat, compilesig_invokes, trust_inference, assume_fatal_throw) end """ NativeInterpreter This represents Julia's native type inference algorithm and the Julia-LLVM codegen backend. It contains many parameters used by the compilation pipeline. """ struct NativeInterpreter <: AbstractInterpreter # Cache of inference results for this particular interpreter cache::Vector{InferenceResult} # The world age we're working inside of world::UInt # method table to lookup for during inference on this world age method_table::CachedMethodTable{InternalMethodTable} # Parameters for inference and optimization inf_params::InferenceParams opt_params::OptimizationParams function NativeInterpreter(world::UInt = get_world_counter(); inf_params = InferenceParams(), opt_params = OptimizationParams(), ) cache = Vector{InferenceResult}() # Initially empty cache # Sometimes the caller is lazy and passes typemax(UInt). # we cap it to the current world age if world == typemax(UInt) world = get_world_counter() end method_table = CachedMethodTable(InternalMethodTable(world)) # If they didn't pass typemax(UInt) but passed something more subtly # incorrect, fail out loudly. @assert world <= get_world_counter() return new(cache, world, method_table, inf_params, opt_params) end end # Quickly and easily satisfy the AbstractInterpreter API contract InferenceParams(ni::NativeInterpreter) = ni.inf_params OptimizationParams(ni::NativeInterpreter) = ni.opt_params get_world_counter(ni::NativeInterpreter) = ni.world get_inference_cache(ni::NativeInterpreter) = ni.cache code_cache(ni::NativeInterpreter) = WorldView(GLOBAL_CI_CACHE, get_world_counter(ni)) """ already_inferred_quick_test(::AbstractInterpreter, ::MethodInstance) For the `NativeInterpreter`, we don't need to do an actual cache query to know if something was already inferred. If we reach this point, but the inference flag has been turned off, then it's in the cache. This is purely for a performance optimization. """ already_inferred_quick_test(interp::NativeInterpreter, mi::MethodInstance) = !mi.inInference already_inferred_quick_test(interp::AbstractInterpreter, mi::MethodInstance) = false """ lock_mi_inference(::AbstractInterpreter, mi::MethodInstance) Hint that `mi` is in inference to help accelerate bootstrapping. This is particularly used by `NativeInterpreter` and helps us limit the amount of wasted work we might do when inference is working on initially inferring itself by letting us detect when inference is already in progress and not running a second copy on it. This creates a data-race, but the entry point into this code from C (`jl_type_infer`) already includes detection and restriction on recursion, so it is hopefully mostly a benign problem, since it should really only happen during the first phase of bootstrapping that we encounter this flag. """ lock_mi_inference(::NativeInterpreter, mi::MethodInstance) = (mi.inInference = true; nothing) lock_mi_inference(::AbstractInterpreter, ::MethodInstance) = return """ See `lock_mi_inference`. """ unlock_mi_inference(::NativeInterpreter, mi::MethodInstance) = (mi.inInference = false; nothing) unlock_mi_inference(::AbstractInterpreter, ::MethodInstance) = return """ add_remark!(::AbstractInterpreter, sv::InferenceState, remark) Emit an analysis remark during inference for the current line (i.e. `sv.currpc`). These annotations are ignored by default, but can be used by external tooling to annotate inference results. """ function add_remark! end may_optimize(::AbstractInterpreter) = true may_compress(::AbstractInterpreter) = true may_discard_trees(::AbstractInterpreter) = true verbose_stmt_info(::AbstractInterpreter) = false """ method_table(interp::AbstractInterpreter) -> MethodTableView Returns a method table this `interp` uses for method lookup. External `AbstractInterpreter` can optionally return `OverlayMethodTable` here to incorporate customized dispatches for the overridden methods. """ method_table(interp::AbstractInterpreter) = InternalMethodTable(get_world_counter(interp)) method_table(interp::NativeInterpreter) = interp.method_table """ By default `AbstractInterpreter` implements the following inference bail out logic: - `bail_out_toplevel_call(::AbstractInterpreter, sig, ::InferenceState)`: bail out from inter-procedural inference when inferring top-level and non-concrete call site `callsig` - `bail_out_call(::AbstractInterpreter, rt, ::InferenceState)`: bail out from inter-procedural inference when return type `rt` grows up to `Any` - `bail_out_apply(::AbstractInterpreter, rt, ::InferenceState)`: bail out from `_apply_iterate` inference when return type `rt` grows up to `Any` It also bails out from local statement/frame inference when any lattice element gets down to `Bottom`, but `AbstractInterpreter` doesn't provide a specific interface for configuring it. """ function bail_out_toplevel_call end, function bail_out_call end, function bail_out_apply end """ infer_compilation_signature(::AbstractInterpreter)::Bool For some call sites (for example calls to varargs methods), the signature to be compiled and executed at run time can differ from the argument types known at the call site. This flag controls whether we should always infer the compilation signature in addition to the call site signature. """ infer_compilation_signature(::AbstractInterpreter) = false infer_compilation_signature(::NativeInterpreter) = true typeinf_lattice(::AbstractInterpreter) = InferenceLattice(BaseInferenceLattice.instance) ipo_lattice(::AbstractInterpreter) = InferenceLattice(IPOResultLattice.instance) optimizer_lattice(::AbstractInterpreter) = OptimizerLattice(SimpleInferenceLattice.instance) abstract type CallInfo end @nospecialize nsplit(info::CallInfo) = nsplit_impl(info)::Union{Nothing,Int} getsplit(info::CallInfo, idx::Int) = getsplit_impl(info, idx)::MethodLookupResult getresult(info::CallInfo, idx::Int) = getresult_impl(info, idx) nsplit_impl(::CallInfo) = nothing getsplit_impl(::CallInfo, ::Int) = error("unexpected call into `getsplit`") getresult_impl(::CallInfo, ::Int) = nothing @specialize