search

JuliaDebug / Cthulhu.jl

The slow descent into madness
MIT License
650 stars 41 forks source link

explain `deoptimized` #213

Open goretkin opened 3 years ago

goretkin commented 3 years ago

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 commented 3 years ago

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 commented 2 years ago

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 https://github.com/JuliaDebug/Cthulhu.jl/issues/256