Overhead with nested overdub

[MikeInnes]

x-ref #73

julia> versioninfo()
Julia Version 1.1.0-DEV.695
Commit 9f43871e54* (2018-11-20 05:28 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.2.0)
  CPU: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

julia> using Cassette, BenchmarkTools

julia> Cassette.@context NoOp;

julia> function loop(x, n)
         r = x/x
         while n > 0
           r *= sin(x)
           n -= 1
         end
         return r
       end

julia> loop2(x, n) = Cassette.overdub(NoOp(), loop, x, n);

julia> loop3(x, n) = Cassette.overdub(NoOp(), loop2, x, n);

julia> @btime loop(x, n) setup=(x=2; n=50);
  323.500 ns (0 allocations: 0 bytes)

julia> @btime loop2(x, n) setup=(x=2; n=50);
  324.163 ns (0 allocations: 0 bytes)

julia> @btime loop3(x, n) setup=(x=2; n=50);
  1.325 ms (7757 allocations: 147.05 KiB)

[jrevels]

I think the problem here might just be a bug in the InferenceResult cache - it seems like inference knows the answer here, it's looks like it's just not using that info properly, resulting in ::Any being inferred (maybe not grabbing it due to recursion limiting, though).

Simpler MWE:

julia> f(x) = sin(x)
f (generic function with 1 method)

julia> f2(x) = Cassette.overdub(NoOp(), f, x)
f2 (generic function with 1 method)

julia> f3(x) = Cassette.overdub(NoOp(), f2, x)
f3 (generic function with 1 method)

If you Cthulhu.@descend into this thing, you'll get to the bottom where you hit an invoke typed as:

invoke Cassette.overdub(_2::Cassette.Context{nametype(NoOp),Nothing,Cassette.NoPass,Nothing,Nothing}, Cassette.overdub::typeof(Cassette.overdub), $(QuoteNode(Cassette.Context{nametype(NoOp),Nothing,Cassette.NoPass,Nothing,Nothing}(nametype(NoOp)(), nothing, Cassette.NoPass(), nothing, nothing)))::Cassette.Context{nametype(NoOp),Nothing,Cassette.NoPass,Nothing,Nothing}, Base.AbstractFloat::Type{AbstractFloat}, %9::Int64)::Any

If you then peak into inference's cached result for that by doing one more descent, however, you see that the invoke is actually well-inferred in the cache:

invoke Cassette.overdub(::Cassette.Context{nametype(NoOp),Nothing,Cassette.NoPass,Nothing,Nothing},::typeof(Cassette.overdub),::Cassette.Context{nametype(NoOp),Nothing,Cassette.NoPass,Nothing,Nothing},::Type{AbstractFloat},::Int64)::Float64

Dropping that Float64 for no good reason is what borks inference for the rest of the function call.

@vchuravy is my model of what Cthulhu.jl doing correct - does Cthulhu look at the CodeInfo/InferenceResult that the compiler actually hits in the cache, or is it doing something weirder that would cause my above analysis to be misinformed? EDIT: okay it's calling code_typed recursively, which means this could indeed be just hitting the recursion limiting heuristic

[jrevels]

Okay I think I know how to fix this; just need to leave a note for myself: I need to propagate the primal method_for_inference_limit_heuristics through when overdubbing. Let's try it and see what happens...

[jrevels]

Note that the OP here was actually fixed by #92, which AFAICT is all that was needed for Cassette to fully avoid inference recursion issues.

Extending by one more overdub for this example ends up hitting JuliaLang/julia#28003, though (see the @test_broken here)