[1.7-rc2] Base.promote_type inference

On Julia v1.7.0-rc2, Base.promote_type seems to struggle with type stability for at least the Bool and Irrational types.

To illustrate, this shows up in @code_warntype π < true, or:

julia> foo() = Base.promote_type(Bool, Irrational{:π})
foo (generic function with 1 method)

julia> @code_warntype foo()
MethodInstance for foo()
  from foo() in Main at REPL[30]:1
Arguments
  #self#::Core.Const(foo)
Body::Any
1 ─ %1 = Base.promote_type::Core.Const(promote_type)
│   %2 = Core.apply_type(Main.Irrational, :π)::Core.Const(Irrational{:π})
│   %3 = (%1)(Main.Bool, %2)::Any
└──      return %3

However, when called directly Base.promote_type seems to have no issue deducing the return type

julia> @code_warntype Base.promote_type(Bool, Irrational{:π})
MethodInstance for promote_type(::Type{Bool}, ::Type{Irrational{:π}})
  from promote_type(::Type{T}, ::Type{S}) where {T, S} in Base at promotion.jl:282
Static Parameters
  T = Bool
  S = Irrational{:π}
Arguments
  #self#::Core.Const(promote_type)
  _::Core.Const(Bool)
  _::Core.Const(Irrational{:π})
Body::Type{Float64}
1 ─      nothing
│   %2 = $(Expr(:static_parameter, 1))::Core.Const(Bool)
│   %3 = $(Expr(:static_parameter, 2))::Core.Const(Irrational{:π})
│   %4 = Base.promote_rule($(Expr(:static_parameter, 1)), $(Expr(:static_parameter, 2)))::Core.Const(Irrational{:π})
│   %5 = Base.promote_rule($(Expr(:static_parameter, 2)), $(Expr(:static_parameter, 1)))::Core.Const(Float64)
│   %6 = Base.promote_result(%2, %3, %4, %5)::Core.Const(Float64)
└──      return %6

I am not sure what to make of this. Any thoughts? :slight_smile:

Seems like a regression since it works on Julia 1.6:

julia> foo() = Base.promote_type(Bool, Irrational{:π});

julia> @code_warntype foo()
Variables
  #self#::Core.Const(foo)

Body::Type{Float64}
1 ─ %1 = Base.promote_type::Core.Const(promote_type)
│   %2 = Core.apply_type(Main.Irrational, :π)::Core.Const(Irrational{:π})
│   %3 = (%1)(Main.Bool, %2)::Core.Const(Float64)
└──      return %3

Perhaps you can open an issue?

1 Like

Done, cf. [1.7-rc2] Base.promote_type inference · Issue #42835 · JuliaLang/julia · GitHub.

2 Likes

Interestly, if you run @code_warntype Base.promote_type(Bool, Irrational{:π}) before @code_warntype true < π in a fresh session then it can work perfectly:

After some time of debugging, I think this is caused by a minor change of the function Core.Compiler.type_more_complex. It doesn’t play well with Type{Union{}} type. Though I am not an expert on Julia’s type inferencer, most of the following parts are carefully examinated and can be reproduced in different setting, so ithis should be the real cause.

Firstly, I can reproduce the same regression behavior on Julia 1.8-DEV. On Julia 1.8-DEV, evaluation of the following code returns true:

begin 
    T = TypeVar(:T)
    S = TypeVar(:S)
    t = Type{Union{}}
    c = Type{S}
    sources = svec(Tuple{typeof(Base.promote_result), Type, Type, Type{T}, Type{S}}, Tuple{typeof(promote_type), Type{Irrational{:π}}, Type{Float64}})
    depth = 2
    tupledepth = 2
    allowed_tuplelen = 0
    Core.Compiler.type_more_complex(t,c,sources,depth,tupledepth,allowed_tuplelen)
end

while in Julia 1.6 and 1.4 it returns false.

This function is invoked indirectly during type inference (with inputs specified by t,c,sources,etc.). To infer the type of foo(), Julia evaluates this function “abstractly” just like a normal evaluation, but at some time it will abstract away some information and become less precise to prevent infinite loop during type inference. Unfortunately, promote_type is exactly the function that involves a lot recursion. And here is the call stack during evaluation:

Base.promote_result(::Type{Irrational{:π}}, ::Type{Float64}, ::Type{Float64}, ::Type{Union{}})
Base.promote_result(::Type{Bool}, ::Type{Irrational{:π}}, ::Type{Irrational{:π}}, ::Type{Float64})
promote_type(::Type{Bool}, ::Type{Irrational{:π}})
foo() #entrypoint

Here are two calls Base.promote_result and Base.promote_result(::Type{Bool}, ::Type{Irrational{:π}}, ::Type{Irrational{:π}}, ::Type{Float64}) calls Base.promote_result(::Type{Irrational{:π}}, ::Type{Float64}, ::Type{Float64}, ::Type{Union{}}). Theses two calls are both the instance of method promote_result(::Type, ::Type, ::Type{T}, ::Type{S}) where {T, S} , which is defined in promotions.jl.

This is a potential recursion, so Julia decides to investigate whether it’s necessary to make type less precise by calling Core.Compiler.limit_type_size in function Core.Compiler.abstract_call_method. And then limit_type_size calls type_more_complex. In Julia 1.6 and older version, this returns false, so there’s no need to change the types. While in Julia 1.8, this return true, and Julia relaxs types to Base.promote_result(::Type{Irrational{:π}}, ::Type{Float64}, ::Type{Float64}, ::Type), note that the concrete type Type{Union{}} becomes an abstract typeType and this ruins type inference.

This can be checked by running type inference on foo() manually (be careful to run it in a fresh session, to prevent it reusing previous inference result):

# we use a custom type inference function.
# *cached* controls whether the inference result should be stored. 
function custom_typeinf(func, argtypes;cached=false)
    #get method instance
    get_mi(func,argtypes) = Core.Compiler.specialize_method(which(func, tuple(argtypes...)), Tuple{typeof(func),argtypes...}, svec())
    interp = Core.Compiler.NativeInterpreter(Core.Compiler.get_world_counter())
    mi = get_mi(func, argtypes)
    result = Core.Compiler.InferenceResult(mi)
    sv = Core.Compiler.InferenceState(result, cached, interp)
    Core.Compiler.typeinf(interp, sv)
    #display the cached
    display(map(x -> (x.linfo, (isa(x.result, Core.Compiler.LimitedAccuracy) ? x.result.typ : x.result)), interp.cache))
end

On Julia 1.8 we have:

julia> custom_typeinf(foo,();cached=false)
13-element Vector{Tuple{MethodInstance, Any}}:
 (MethodInstance for promote_type(::Type{Bool}, ::Type{Irrational{:π}}), Any)
 (MethodInstance for promote_rule(::Type{Bool}, ::Type{Irrational{:π}}), Const(Irrational{:π}))
 (MethodInstance for promote_rule(::Type{Irrational{:π}}, ::Type{Bool}), Const(Float64))
 (MethodInstance for promote_type(::Type{Float64}, ::Type{Bool}), Const(Float64))
 (MethodInstance for promote_rule(::Type{Float64}, ::Type{Bool}), Const(Float64))
 (MethodInstance for promote_rule(::Type{Bool}, ::Type{Float64}), Const(Float64))
 (MethodInstance for Base.promote_result(::Type{Float64}, ::Type{Bool}, ::Type{Float64}, ::Type{Float64}), Const(Float64))
 (MethodInstance for promote_type(::Type{Float64}, ::Type{Float64}), Const(Float64))
 (MethodInstance for Base.promote_result(::Type{Bool}, ::Type{Irrational{:π}}, ::Type{Irrational{:π}}, ::Type{Float64}), Any)
 (MethodInstance for promote_type(::Type{Irrational{:π}}, ::Type{Float64}), Any)
 (MethodInstance for promote_rule(::Type{Irrational{:π}}, ::Type{Float64}), Const(Float64))
 (MethodInstance for promote_rule(::Type{Float64}, ::Type{Irrational{:π}}), Const(Union{}))
 (MethodInstance for Base.promote_result(::Type{Irrational{:π}}, ::Type{Float64}, ::Type{Float64}, ::Type), Any)

On Julia 1.6:

julia> custom_typeinf(foo,();cached=false)
13-element Vector{Tuple{Core.MethodInstance, Core.Const}}:
 (MethodInstance for promote_type(::Type{Bool}, ::Type{Irrational{:π}}), Core.Const(Float64))
 (MethodInstance for promote_rule(::Type{Bool}, ::Type{Irrational{:π}}), Core.Const(Irrational{:π}))
 (MethodInstance for promote_rule(::Type{Irrational{:π}}, ::Type{Bool}), Core.Const(Float64))
 (MethodInstance for promote_type(::Type{Float64}, ::Type{Bool}), Core.Const(Float64))
 (MethodInstance for promote_rule(::Type{Float64}, ::Type{Bool}), Core.Const(Float64))
 (MethodInstance for promote_rule(::Type{Bool}, ::Type{Float64}), Core.Const(Float64))
 (MethodInstance for promote_result(::Type{Float64}, ::Type{Bool}, ::Type{Float64}, ::Type{Float64}), Core.Const(Float64))
 (MethodInstance for promote_type(::Type{Float64}, ::Type{Float64}), Core.Const(Float64))
 (MethodInstance for promote_result(::Type{Bool}, ::Type{Irrational{:π}}, ::Type{Irrational{:π}}, ::Type{Float64}), Core.Const(Float64))
 (MethodInstance for promote_type(::Type{Irrational{:π}}, ::Type{Float64}), Core.Const(Float64))
 (MethodInstance for promote_rule(::Type{Irrational{:π}}, ::Type{Float64}), Core.Const(Float64))
 (MethodInstance for promote_rule(::Type{Float64}, ::Type{Irrational{:π}}), Core.Const(Union{}))
 (MethodInstance for promote_result(::Type{Irrational{:π}}, ::Type{Float64}, ::Type{Float64}, ::Type{Union{}}), Core.Const(Float64)) 




Now you may ask why @code_warntype Base.promote_type(Bool, Irrational{:π}) still works fine. The secret here is that, the @code_warntype invokes code_typed and code_typed invokes typeinf_code, which uses an type inferencer that doesn’t cache (it is equivalent to custom_typeinf(func, argtypes;cached=false)). Without the addtional foo wrapper, the call stack becomes smaller (only 2 functions, foo and the uncached promote_type(::Type{Bool},::Type{Irrational{:π}}) are removed, you can check the stack above).

The edge_matches_sv function in abstract_call_method then thinks that it’s worthwile to pretend that this is not a recursion to make more progress on inference, thus there’s no need to make type coarser and the limit_type_size function is not invoked, which means that signature is still Type{Union{}}. So inference succeeds.

To demonstrate this, we can start a fresh session (in Julia1.8) and type following code:

# cached version has 3 function in stack, it fails
custom_typeinf(Base.promote_type, (Type{Bool},Type{Irrational{:π}});cached=true) 
# uncached version has 2 function in stack, it succeeds. The inference result of subfunction is cached. 
custom_typeinf(Base.promote_type, (Type{Bool},Type{Irrational{:π}});cached=false) 
# reinfer cached version, it reuses the precise result above and thus succeeds, the inference result is cached.
custom_typeinf(Base.promote_type, (Type{Bool},Type{Irrational{:π}});cached=true)
# here is the magic! foo() uses the result above and succeeds
@code_warntype foo()

We get a successful inference:

julia> @code_warntype foo()
MethodInstance for foo()
  from foo() in Main at /home/chenningcong/Documents/Code/juliaCode/TypeInferenceDebugger/src/debugger.jl:27
Arguments
  #self#::Const(foo)
Body::Type{Float64}
1 ─ %1 = Core.Bool::Const(Bool)
│   %2 = Core.apply_type(Main.Irrational, :π)::Const(Irrational{:π})
│   %3 = Main.promote_type(%1, %2)::Const(Float64)
└──      return %3

In summary, this is a bug caused by recursion detection in type inferencer. The easy fix is to restore the behavior of type_more_complex and limit_type_size to not promote Type{Union{}} to Type.

5 Likes