Lowering of large basic blocks takes a very long time (>40s)

[topolarity]

For functions with very large basic blocks, it looks like lowering can take 10's of seconds.

MWE (bad_expr.zip):

function (var"###out###", var"###in 1###", var"###in 2###", var"###in 3###")
    begin
        var"%1" = var"###in 1###"[1]
        var"%2" = var"###in 1###"[17]
        var"%3" = var"###in 1###"[33]
        # 61319 statements in total ... 
        var"###out###"[1599] = var"%59720"
        var"%59721" = var"%59280" - var"%201"
        var"%59722" = var"%59721"
        var"###out###"[1600] = var"%59722"
    end
    var"###out###"
end

julia> using Serialization

julia> @time x = deserialize("bad_expr.bin");
  0.112304 seconds (769.46 k allocations: 32.307 MiB, 12.52% compilation time)

julia> @time eval(x)
 48.518390 seconds (781.37 k allocations: 37.859 MiB, 0.11% gc time, 0.01% compilation time)
#3 (generic function with 1 method)

julia> ^C
ROOT                      : 13.98 %   20699030420
GC                        :  0.09 %   138341866
LOWERING                  : 85.48 %   126515511024
PARSING                   :  0.00 %   2666354
INFERENCE                 :  0.02 %   31406442
CODEGEN                   :  0.01 %   16032428
METHOD_LOOKUP_SLOW        :  0.00 %   2124039
METHOD_LOOKUP_FAST        :  0.00 %   5955236
LLVM_OPT                  :  0.07 %   97929049
LLVM_MODULE_FINISH        :  0.16 %   233183754
METHOD_MATCH              :  0.00 %   3165948
TYPE_CACHE_LOOKUP         :  0.00 %   4470193
TYPE_CACHE_INSERT         :  0.00 %   63332
MACRO_INVOCATION          :  0.00 %   500950
AST_COMPRESS              :  0.02 %   28212211
AST_UNCOMPRESS            :  0.00 %   4355650
SYSIMG_LOAD               :  0.15 %   218148962
ADD_METHOD                :  0.00 %   14826
INIT_MODULE               :  0.01 %   11298046

Notice the >85% time spent LOWERING

Julia also cannot respond to interrupts while lowering, so the user has no way to interrupt this ~40 second pause.

[quinnj]

I wonder if this is similar to what I was seeing in #41684

[topolarity]

I wonder if this is similar to what I was seeing in #41684

Upon reviewing some trace information, I think that's a separate problem. The time on that issue is spent almost entirely in LLVM, instead of lowering.

#45131 potentially is related to this issue, as another lowering performance issue.

[ToucheSir]

While we're on the topic of things which cause superlinear scaling of compilation latency, is there a related issue for functions with lots of slots? In TuringLang/Turing.jl#1754 (comment) we were seeing 20+ min compile times and actual OOMs because of those.

[topolarity]

Not that I know of. Do you have an MWE that bypasses the Turing/Zygote pipeline and just shows the expensive eval?

If so, please do go ahead and file an issue for it.

The closer you can get to a function that is dead simple but happens to have a lot of slots and demonstrates the scaling issue, the easier it will be to investigate improvements in the compiler.

[JeffBezanson]

I found that this is due to linear lookup of variables in closure conversion and a couple other places. Can be fixed pretty easily by throwing a hash table at it.