Inference

How inference works

In Julia compiler, "type inference" refers to the process of deducing the types of later values from the types of input values. Julia's approach to inference has been described in the blog posts below:

1. Shows a simplified implementation of the data-flow analysis algorithm, that Julia's type inference routine is based on.
2. Gives a high level view of inference with a focus on its inter-procedural convergence guarantee.
3. Explains a refinement on the algorithm introduced in 2.

Debugging compiler.jl

You can start a Julia session, editcompiler/*.jl (for example to insertprint statements), and then replaceCore.Compiler in your running session by navigating tobase and executinginclude("compiler/compiler.jl"). This trick typically leads to much faster development than if you rebuild Julia for each change.

Alternatively, you can use theRevise.jl package to track the compiler changes by using the commandRevise.track(Core.Compiler) at the beginning of your Julia session. As explained in theRevise documentation, the modifications to the compiler will be reflected when the modified files are saved.

A convenient entry point into inference istypeinf_code. Here's a demo running inference onconvert(Int, UInt(1)):

# Get the methodatypes = Tuple{Type{Int}, UInt}  # argument typesmths = methods(convert, atypes)  # worth checking that there is only onem = first(mths)# Create variables needed to call `typeinf_code`interp = Core.Compiler.NativeInterpreter()sparams = Core.svec()      # this particular method doesn't have type-parametersrun_optimizer = true       # run all inference optimizationstypes = Tuple{typeof(convert), atypes.parameters...} # Tuple{typeof(convert), Type{Int}, UInt}Core.Compiler.typeinf_code(interp, m, types, sparams, run_optimizer)

If your debugging adventures require aMethodInstance, you can look it up by callingCore.Compiler.specialize_method using many of the variables above. ACodeInfo object may be obtained with

# Returns the CodeInfo object for `convert(Int, ::UInt)`:ci = (@code_typed convert(Int, UInt(1)))[1]

The inlining algorithm (inline_worthy)

Much of the hardest work for inlining runs inssa_inlining_pass!. However, if your question is "why didn't my function inline?" then you will most likely be interested ininline_worthy, which makes a decision to inline the function call or not.

inline_worthy implements a cost-model, where "cheap" functions get inlined; more specifically, we inline functions if their anticipated run-time is not large compared to the time it would take toissue a call to them if they were not inlined. The cost-model is extremely simple and ignores many important details: for example, allfor loops are analyzed as if they will be executed once, and the cost of anif...else...end includes the summed cost of all branches. It's also worth acknowledging that we currently lack a suite of functions suitable for testing how well the cost model predicts the actual run-time cost, althoughBaseBenchmarks provides a great deal of indirect information about the successes and failures of any modification to the inlining algorithm.

The foundation of the cost-model is a lookup table, implemented inadd_tfunc and its callers, that assigns an estimated cost (measured in CPU cycles) to each of Julia's intrinsic functions. These costs are based onstandard ranges for common architectures (seeAgner Fog's analysis for more detail).

We supplement this low-level lookup table with a number of special cases. For example, an:invoke expression (a call for which all input and output types were inferred in advance) is assigned a fixed cost (currently 20 cycles). In contrast, a:call expression, for functions other than intrinsics/builtins, indicates that the call will require dynamic dispatch, in which case we assign a cost set byParams.inline_nonleaf_penalty (currently set at1000). Note that this is not a "first-principles" estimate of the raw cost of dynamic dispatch, but a mere heuristic indicating that dynamic dispatch is extremely expensive.

Each statement gets analyzed for its total cost in a function calledstatement_cost. You can display the cost associated with each statement as follows:

julia> Base.print_statement_costs(stdout, map, (typeof(sqrt), Tuple{Int},)) # map(sqrt, (2,))map(f, t::Tuple{Any}) @ Base tuple.jl:281  0 1 ─ %1  = $(Expr(:boundscheck, true))::Bool  0 │   %2  = Base.getfield(_3, 1, %1)::Int64  1 │   %3  = Base.sitofp(Float64, %2)::Float64  0 │   %4  = Base.lt_float(%3, 0.0)::Bool  0 └──       goto #3 if not %4  0 2 ─       invoke Base.Math.throw_complex_domainerror(:sqrt::Symbol, %3::Float64)::Union{}  0 └──       unreachable 20 3 ─ %8  = Base.Math.sqrt_llvm(%3)::Float64  0 └──       goto #4  0 4 ─       goto #5  0 5 ─ %11 = Core.tuple(%8)::Tuple{Float64}  0 └──       return %11

The line costs are in the left column. This includes the consequences of inlining and other forms of optimization.