explain deoptimized

[goretkin]

I see e.g.

Advanced: dump [P]arams cache.
   %3  = invoke alias_continue(…,…,…)::Any
   %4  = call #!(::Any)::Any
   %25  = invoke push!(::typename(DiscretePathSearch.NodeHandle){…},::typename(DiscretePathSearch.NodeAugmentation){…})::Any
   %31  = invoke throw_inexacterror(::Symbol,::Type{Int32},::Int64)::Union{}
   %40  = invoke error(::String)::Union{}
   %56  = invoke alias_tally!(…,…,…)::Any
   %78  = call ArgumentError(::String)::Any
   %115  = invoke throw_inexacterror(::Symbol,::Type{UInt64},::Int64)::Union{}
 • %133  = deoptimized successors!(::typename(DiscretePathSearch.PathAndSummary){…},::typename(DiscretePathSearch.Algorithm){…})::Any

and I don't know what deoptimized is. (I cannot even find how the string is emitted).

[aviatesk]

FWIW "deoptimized" no longer exists for the current Cthulhu version (which is only compatible with v1.7 and higher).
In recent Cthulhu, you will see "uncached" or "limited" callsites instead.

So what they mean ?
They usually mean there are mutually recursive method calls, and type inference intentionally loosen its accuracy using some heuristics. The "recursion" here means recursive method calls within a static call graph, and it doesn't mean the recursive calls of the same generic function. To say roughly, if there are calls of the same method call signature, type inference might give up because otherwise it may not guarantee the termination of itself (, and it can cause problems for succeeding optimizations).

[jishnub]

Slightly unrelated to the original post, but why does an inferred type differ between Cthulhu and @code_warntype? As an example:

julia> using ApproxFunOrthogonalPolynomials
          
julia> using Cthulhu

julia> @descend_code_warntype TensorSpace((Chebyshev(0..1), ApproxFunBase.UnsetSpace()))
TensorSpace(sp::Tuple) in ApproxFunBase at /home/jishnu/Dropbox/JuliaPackages/ApproxFunBase/src/Multivariate/TensorSpace.jl:226
Body::TensorSpace{Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}, _A, Union{}} where _A
226 1 ─ %1 = ApproxFunBase.mapreduce::Core.Const(mapreduce)                                                                                                             │ 
    │   %2 = ApproxFunBase.domain::Core.Const(ApproxFunBase.domain)                                                                                                     │ 
    │   %3 = ApproxFunBase.:×::Core.Const(LinearAlgebra.cross)                                                                                                          │ 
    │   %4 = invoke Base.:(var"#mapreduce#263")($(QuoteNode(Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}}()))::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}}, %1::typeof(mapreduce), %2::Function, %3::Function, sp::Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace})::Any
    │   %5 = ApproxFunBase.typeof(%4)::DataType                                                                                                                         │ 
    │   %6 = Core.apply_type(ApproxFunBase.TensorSpace, Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}, %5, Union{})::Type{TensorSpace{Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}, _A, Union{}}} where _A
    │   %7 = (%6)(sp)::TensorSpace{Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}, _A, Union{}} where _A                       │ 
    └──      return %7                                                                                                                                                  │ 
Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.
Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.
Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code
Actions: [E]dit source code, [R]evise and redisplay
Advanced: dump [P]arams cache.
 • %4 =  = < uncached > #mapreduce#263(::Pairs{…},::#mapreduce,::#domain,::#cross,::Tuple{…})::Any
   %7 = call TensorSpace(::Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace})::…
   ↩

julia> @code_warntype TensorSpace((Chebyshev(0..1), ApproxFunBase.UnsetSpace()))
MethodInstance for TensorSpace(::Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace})
  from TensorSpace(sp::Tuple) in ApproxFunBase at /home/jishnu/Dropbox/JuliaPackages/ApproxFunBase/src/Multivariate/TensorSpace.jl:226
Arguments
  #self#::Type{TensorSpace}
  sp::Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}
Locals
  #473::ApproxFunBase.var"#473#474"
Body::TensorSpace{Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}, DomainSets.VcatDomain{2, Int64, (1, 1), Tuple{IntervalSets.ClosedInterval{Int64}, DomainSets.FullSpace{Int64}}}, Union{}}
1 ─ %1 = ApproxFunBase.typeof(sp)::Core.Const(Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace})
│   %2 = ApproxFunBase.mapreduce(ApproxFunBase.domain, ApproxFunBase.:×, sp)::DomainSets.VcatDomain{2, Int64, (1, 1), Tuple{IntervalSets.ClosedInterval{Int64}, DomainSets.FullSpace{Int64}}}
│   %3 = ApproxFunBase.typeof(%2)::Core.Const(DomainSets.VcatDomain{2, Int64, (1, 1), Tuple{IntervalSets.ClosedInterval{Int64}, DomainSets.FullSpace{Int64}}})
│        (#473 = %new(ApproxFunBase.:(var"#473#474")))
│   %5 = #473::Core.Const(ApproxFunBase.var"#473#474"())
│   %6 = ApproxFunBase.mapreduce(ApproxFunBase.rangetype, %5, sp)::Core.Const(Union{})
│   %7 = Core.apply_type(ApproxFunBase.TensorSpace, %1, %3, %6)::Core.Const(TensorSpace{Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}, DomainSets.VcatDomain{2, Int64, (1, 1), Tuple{IntervalSets.ClosedInterval{Int64}, DomainSets.FullSpace{Int64}}}, Union{}})
│   %8 = (%7)(sp)::TensorSpace{Tuple{Chebyshev{IntervalSets.ClosedInterval{Int64}, Float64}, ApproxFunBase.UnsetSpace}, DomainSets.VcatDomain{2, Int64, (1, 1), Tuple{IntervalSets.ClosedInterval{Int64}, DomainSets.FullSpace{Int64}}}, Union{}}
└──      return %8

Here, @code_warntype reports a concrete result, whereas Cthulhu reports a UnionAll. It appears that the uncached is preventing type inference, but then how is Base able to infer the type?

Edit: this is possibly related to #256