[Inference] Not all problems [...] can be solved by another level of indirection

[vchuravy]

@peterahrens encountered an interesting type-inference corner case, where adding a level of indirection would trigger type-inferences recursion heuristic and in his case prevent inlining to happen. The code Peter was written looked a lot like this:

f(arr::AbstractArray{T, 0}) where T = arr
indirect(arr) = f(arr)
f(arr::AbstractArray{T, N}) where {T, N} = indirect(view(arr, 1, ntuple(i->:, Val(N-1))...))

Inspecting this code with @code_typed f(zeros(3,3,3,3,3)) yields:

7 ─ %82 = invoke Main.f(%80::SubArray{Float64,4,Array{Float64,5},Tuple{Int64,Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}}},true})::SubArray{T,0,P,I,L} where L where I where P where T

whereas removing that level of indirection

f(arr::AbstractArray{T, 0}) where T = arr
f(arr::AbstractArray{T, N}) where {T, N} = f(view(arr, 1, ntuple(i->:, Val(N-1))...))

yields:

7 ─ %82 = invoke Main.f(%80::SubArray{Float64,4,Array{Float64,5},Tuple{Int64,Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}},Base.Slice{Base.OneTo{Int64}}},true})::SubArray{Float64,0,Array{Float64,5},NTuple{5,Int64},true}

The issue reminds me of #24852 and #26822

[vchuravy]

Looking into this a bit more:

sig = Tuple{typeof(Main.indirect), Base.SubArray{Float64, 2, Array{Float64, 5}, Tuple{Int64, Int64, Int64, Base.Slice{Base.OneTo{Int64}}, Base.Slice{Base.OneTo{Int64}}}, true}}
comparison = Tuple{typeof(Main.indirect), Any}
specTypes = Tuple{typeof(Main.f), Base.SubArray{Float64, 3, Array{Float64, 5}, Tuple{Int64, Int64, Base.Slice{Base.OneTo{Int64}}, Base.Slice{Base.OneTo{Int64}}, Base.Slice{Base.OneTo{Int64}}}, true}}

julia> Core.Compiler.type_more_complex(sig, specTypes, Core.svec(), 1, 1000, 1000)
false

julia> Core.Compiler.limit_type_size(sig, comparison, specTypes, 11, 3)
SubArray

Looking at

julia/base/compiler/abstractinterpretation.jl

Line 323 in 91151ab

# see if the type is actually too big (relative to the caller), and limit it if required

the comment implies that we want calls in the function to have signatures with less or equal complexity to our own. Stepping through limit_type_size shows that we recurse twice and end up in a situation where:

import Core.Compiler: unwrap_unionall
source = Core.svec(unwrap_unionall(comparison), unwrap_unionall(specTypes))
source[1] === source[2] && (source = svec(source[1]))

# first iteration
# Core.Compiler._limit_type_size(sig, comparison, source, 1, 3)
#
# second iteration
sig = Base.SubArray{Float64, 2, Array{Float64, 5}, Tuple{Int64, Int64, Int64, Base.Slice{Base.OneTo{Int64}}, Base.Slice{Base.OneTo{Int64}}}, true}
comparison = Any
# Core.Compiler._limit_type_size(sig, comparison, source, 2, 3)

which due to the Any falls through to

julia/base/compiler/typelimits.jl

Line 185 in a399780

return widert

Meh. Unsure how to proceed here so ideas would be welcomed.

[vtjnash]

It seems like we might be able to fix this by making limit_type_size non-transitive. Keno pioneered that recently for his current work on Defractor.jl, so perhaps it is doable.