This PR proposes an alternative design of the inference lattice, and overhauls our inference
implementation based on the design.
In another PRs, I will demonstrate examples of how new lattice properties can be introduced on top of
this lattice design, hopefully with much less development costs.

Motivation

Recently I and@vtjnash have found that it is getting harder and harder to maintain the correctness
of our lattice implementations and improve the accuracy of inference especially when introducing new lattice
properties. More specifically, we have observed there are these three issues:

a extended lattice wrapper can wrap another wrapper
Under the current lattice design, there are various wrapper types that convey specific information
(I will refer to them as "extended lattice wrappers" in the following part of this description).
They require special cares in order to preserve their correctness, but if such a wrapper can wrap
another wrapper which also requires such special care, it becomes very tricky to maintain the correctness.
inference: fix #42090, make sure not to wrapConditional inPartialStruct #42091 was an example of this problem, where we broke an invariant thatConditional assumes
whenPartialStruct wrappedConditional.
messes aroundisa /widenconst /widenconditional /ignorelimited
Our inference implementation is messed up with theisa-predicate and "unwrapping" utilities
that transform a wrapper to another wrapper or native Julia type.
For example, currently native JuliaTypes and extended lattice wrappers (e.g.Const) can
appear in same places, and we need to usewidenconst(x) anywhere we want to use subtyping predicate
withx, just because the extended lattice wrappers are not valid native JuliaTypes that can be passed to<:.
The pain point here is that most parts of our inference implementation treat lattice
elements asAny-typed objects, and so it's not very clear if a variable at some point is
expected to be an extended lattice object or a native Julia type already (and accordingly JET is
also unable to detect possible invalid operations on such cases).
complex lattice implementations of⊑ andtmerge
Another pain point of having bunch of extended lattice wrappers is that implementations of lattice
operations can be very complex. Especially, the reasoning could be very tricky when some extended
lattice wrapper can be transformed to another wrapper. For example, somex::Conditional can be
converted tox::Const, and so we want to handle theisa(x, Conditional) casesbefore we
handle theisa(x, Const) cases in⊑ ortmerge in order to get the best accuracy.
This lattice complexity makes it difficult to introduce new lattice wrapper, because this sort of relational
handling needs to be reconsidered every time new lattice wrapper is added in.

Especially, the second and third ones are very problematic in my opinion, since they make it very
hard to improve inference accuracy by adding new lattice properties without introducing yet another
complexities. For instance, we're hesitate to push#41199 forward under the current situation
because of these concerns.

Proposed lattice design

In order to resolve these issues, we propose the following new lattice design:

struct LatticeElement# [corresponding wrapper]    typ# ::Type                                            # <= native Julia types    constant# ::Any (constant value) or ::PartialFields    # <= Const / PartialStruct    conditional::ConditionalInfo# <= Conditional / InterConditional    special::Special# <= PartialTypeVar / PartialOpaque / Vararg# abstract interpretation specific attributes    causes# ::IdSet{InferenceState}                        # <= LimitedAccuracy# optimization specific specific attributes    maybeundef::Bool# <= MaybeUndef# # and more in the future ...# mustalias::AnyMustAlias                  # #41199# ninitialized::Int                        # should improve `stmt_effect_free` accuracy# definedfields::Vector{Union{Int,Symbol}} # should improve `stmt_effect_free` accuracyend

As shown in the struct definition,LatticeElement encodes several lattice properties and
these attributes are combined to create a partial lattice whose height is infinite.
All the existing extended lattice wrappers likeConst will be replaced with these properties,
e.g.x.constant === 10 can hold the same information asx::Const(10).

How "2. messes aroundisa /widenconst /widenconditional /ignorelimited" will be resolved:

ThisLatticeElement object also wraps native Julia types. In other word, with this overhaul,
inference routine basically works onLatticeElement objects rather than mixing up extended lattice
wrappers and native Julia types.
For example, nowabstract_call will acceptargtypes::Vector{LatticeElement} rather thanargtypes::Vector{Any}
andframe::InferenceState will maintainframe.bestguess::LatticeElement rather thanframe.bestguess::Any.
This essentially separates contexts whereLatticeElement is expected from where native Julia types are expected,
and it allows us to reason inference logic far more easily, e.g. it would be much easier to find
places where we need to usewidenconst to get a native Julia type fromLatticeElement, hopefully
with more help of static analyses like JET.jl.

And also note thatLatticeElement conveys all the lattice properties, while under the current lattice
implementation, each wrapper conveys each lattice property independently.
It allowsLatticeElement to hold e.g.constant (corresponding toConst),conditional (Conditional)
andcauses (LimitedAccuracy) information all at the same time, so that now we don't need to use
widenconditional in order to getConst information from aConditional wrapper and now we don't
need to useignorelimited to getConditional information from aLimitedAccuracy.
Rather, nowwidenconditional andignorelimited are only used as constructors, which convert
LatticeElement with conditional/limited information to newLatticeElement without such information.
And we can just eliminate their previous usages to get wrapped information.

How "3. complex lattice implementations of⊑ andtmerge will be resolved:

One another important observation is that most of these lattice attributes are actually orthogonal
to each other. For example,causes andconditional can be compared or merged separately.
This property will allow us to vastly simplify the implementations of⊑ andtmerge:
now we can just compare or merge each attribute separately¹ and don't need to care about what
order we want handle lattice properties (wrappers previously).

Once this overhaul is done,⊑ andtmerge would look like:

function⊑(x::LatticeElement, y::LatticeElement)...# handle `conditional`ifisAnyConditional(y)ifisAnyConditional(x)issubconditional(x, y)||returnfalseendend...# handle `causes`ifisLimitedAccuracy(y)isLimitedAccuracy(x)||returnfalse        y.causes⊈ x.causes&&returnfalseend...# `LatticeElement` will guaranteed to have `typ::Type` field, which could be used alwaysreturn a<:bendfunctiontmerge(x::LatticeElement, y::LatticeElement)# handle `typ`    typ=...# join type operation (a bit complex)# handle `constant`ifisConst(x)&&isConst(y)&&constant(x)===constant(y)        constant=constant(x)else        constant=nothingend...# handle `causes`ifisLimitedAccuracy(x)&&isLimitedAccuracy(y)if x.causes⊆ y.causes            causes= y.causeselseif y.causes⊆ x.causes            causes= x.causeselse            causes=union!(copy(x.causes), y.causes)endelseifisLimitedAccuracy(x)        causes= x.causeselseifisLimitedAccuracy(y)        causes= y.causeselse        causes= _TOP_CAUSESend...returnLatticeElement(typ;..., constant,..., causes,...)end

Compared to the current implementations, I'd argue that these new implementations will be much
simpiler and I hope they can be easily enhanced with new attributes in the future.

How "1. a extended lattice wrapper can wrap another wrapper" can be resolved

The proposed lattice design won't resolve this issue on its own, because each attribute ofLatticeElement
can also beLatticeElement (thusLatticeElement's lattice has an infinite height).
I propose to address this issue by adding more constructor assertions.
For example, in order to make#42091 never happen again in the future, we can have thisPartialStruct constructor:

functionPartialStruct(@nospecialize(typ), fields::Fields)@assert (isconcretetype(typ)||istupletype(typ))"invalid PartialStruct typ"    typ= typ::DataType@assert!ismutabletype(typ)"invalid PartialStruct typ"for fieldin fields@assert!isConditional(field)"invalid PartialStruct field"endreturnLatticeElement(typ; fields)end

We still need to remember to add@assert !isMustAlias(field) "invalid PartialStruct field" when
reviving#41199 on top of this overhaul though, but I couldn't come up with any effective alternative
idea that resolves this issue.

Plan

I plan to finish this mega refactor with the following 4 big steps:

don't mix up native Julia types with extended lattice wrappers
convert existing extended lattice wrappers toLatticeElement attributes
clean up implementations (e.g. remove unnecessarywidenconditional, try to simplifytmerge)
experiment new lattice design with adding new lattice properties (maybe as another PRs)

Progress tracking

don't mix up native Julia types with extended lattice wrappers
- set up temporalAbstractLattice interface, which doesn't include native Julia types, but only contain extended lattice wrappers including newLatticeElement
- now "most" compiler code works withAbstractLattice/Vector{AbstractLattice} rather thanAny/Vector{Any}
  - bootstrap
  - sysimg
  - test
convert existing extended lattice wrappers toLatticeElement attributes
- PartialStruct
- Conditional /InterConditional
- Const
- PartialTypeVar
- LimitedAccuracy
- PartialOpaque
- MaybeUndef
- ~~DelayedTyp~~ this is not a part of lattice, and I added a hack to sneak this into aLatticeElement system
- Vararg
clean up implementations based on new lattice design, addressTODO (lattice overhaul) leftover
- replaceAbstractLattice withLatticeElement
- ⊑
- tmerge (maybe rename to⊔?)
- tmeet (maybe rename to⊓?)
- widenconditional
- ignorelimited
- abstract_iteration
- precise_container_type
- tfuncs
- tfuncs (xxx_nothrow)
- makePartialStruct wrapLatticeElement
- makeConditional/InterConditional wrapLatticeElement
- replaceAny annotation withLatticeElement
experiment new lattice design with adding new lattice properties
- MustAlias /InterMustAlias: revive#41199
- NInitialized: records # of initialized fields (when notPartialStruct-folded) in order to helpstmt_effect_free
- DefinedFields: back-propagateisdefined information in order to helpstmt_effect_free

Collaborations 🙏

Any sort of development help would besuper appreciated.
Just leave a comment if you find anything that needs a fix or can be improved,
or pick up any of the remaining tasks tracked above and make a PR against this branch.
Pro-tip: If you want to use Cthulhu on this branch,JuliaDebug/Cthulhu.jl#238 is for you.

Discussion

I'm still wondering how we should handleVarargs (andTypeVars²), because it can appear in same context asLatticeElement
but they are definitely not valid Julia types.
inference: improveTypeVar/Vararg handling #42583 should improve the situation a bit by revealing
where we currently need to special caseVarargs, but they definitely appear inargtypes.
EDIT: I decided to just wrap them in theLatticeElement.special field
now we may want to consider how to add lattice extension system on top of this refactor (, which could also be fairly tricky)

Footnotes

Of course there are exceptions, for our current lattice implementation,Const andPartialStruct
are entangled with each other and need a care about the handling ordering.↩
Fortunately, after working oninference: improveTypeVar/Vararg handling #42583 I found that we seem to have eliminated most usages ofTypeVars as argtype.↩

aviatesk added the compiler:inferenceType inference label

Oct 11, 2021

Copy link

Contributor

akawashiro commentedOct 11, 2021

How will you implementissubconditional? In general, it can be a very complex function because you must decide on a formula like(condition of x) => (condition of y).

Copy link

MemberAuthor

aviatesk commentedOct 11, 2021

issubconditional is implemented like:

under the current lattice design (wrapper hell):

julia/base/compiler/typelattice.jl

Lines 126 to 137 in592cacc

	# `Conditional` and `InterConditional` are valid in opposite contexts
	# (i.e. local inference and inter-procedural call), as such they will never be compared
	functionissubconditional(a::C, b::C)where {C<:AnyConditional}
	ifis_same_conditionals(a, b)
	if a.vtype⊑ b.vtype
	if a.elsetype⊑ b.elsetype
	returntrue
	end
	end
	end
	returnfalse
	end

this PR (as lattice attributes):

julia/base/compiler/typelattice.jl

Lines 368 to 378 in64ea14b

	functionissubconditional(a::TypeLattice, b::TypeLattice)
	ifis_same_conditionals(a, b)
	a, b= a.conditional, b.conditional
	if a.vtype⊑ b.vtype
	if a.elsetype⊑ b.elsetype
	returntrue
	end
	end
	end
	returnfalse
	end

Conditional keeps information about a variable type inthen/else branches, and we can use⊑ recursively to decide the order of twoConditinals (when they convey conditional information on the same object, otherwise they're simply notissubconditional). Currently we simply discard nestedConditionals (or we may even want to make sureConditional doesn't wrap/encode anotherConditional).

aviatesk mentioned this pull request

Oct 11, 2021

updates with the incoming type lattice overhaulJuliaDebug/Cthulhu.jl#238

Draft

aviatesk force-pushed theavi/typelattice branch 2 times, most recently from8647107 to723ed65Compare

October 11, 2021 16:37

Copy link

MemberAuthor

aviatesk commentedOct 11, 2021•
edited
Loading

Hm, even if this overhaul could help us improve the correctness/accuracy of inference, but we may end up with
performance penalties that come withTypeLattice constructions, and it could be problematic ... ?

I took this simple benchmark that compares the performance ofConst lattice element construction,
which shows the overhead ofTypeLattice:

julia>using BenchmarkToolsjulia># simulates a `Const` construction in the current lattice implmentationstruct Const           valConst(@nospecialize val)=new(val)endjulia>mkconst1(xs)= (for iin1:length(xs)           xs[i]=Const(xs[i])end; xs)mkconst1 (genericfunction with1 method)julia># actual `Const` construction in the proposed lattice designmkconst2(xs)= (for iin1:length(xs)           xs[i]= Core.Compiler.Const(xs[i])end; xs)mkconst2 (genericfunction with1 method)julia>@benchmarkmkconst1(xs) setup= (xs= Any[ifor iin1:100])BenchmarkTools.Trial:10000 samples with199 evaluations. Range (min… max):439.025 ns…12.916 μs  ┊ GC (min… max):0.00%…94.56% Time  (median):492.656 ns               ┊ GC (median):0.00% Time  (mean± σ):640.437 ns±509.804 ns  ┊ GC (mean± σ):5.02%±6.92%  █▅▃▂▃▃▃▃▂▃▄▄▄▃▂▂▁▁▁▁▁ ▁                                       ▁  █████████████████████████████▇█▇▇▇▇▆▇▇▆▆▆▅▅▅▅▅▅▄▄▅▄▃▄▂▄▄▄▃▃▄▄ █439 ns        Histogram:log(frequency) by time1.81 μs< Memory estimate:1.56 KiB, allocs estimate:100.julia>@benchmarkmkconst2(xs) setup= (xs= Any[ifor iin1:100])BenchmarkTools.Trial:10000 samples with9 evaluations. Range (min… max):2.717 μs…213.877 μs  ┊ GC (min… max):0.00%…95.28% Time  (median):2.832 μs               ┊ GC (median):0.00% Time  (mean± σ):3.435 μs±5.473 μs  ┊ GC (mean± σ):7.37%±4.69%  ▇█▅▃▃▂   ▂▂  ▁      ▁▁▁▁                                    ▁  ██████▇▇███▇██▇▅▆▆▇████████▆▅▆▃▃▄▆██▇▆▆▅▅▆█▇▇▅▆▅▄▆▃▃▄▅▃▄▂▃▃ █2.72 μs      Histogram:log(frequency) by time7.58 μs< Memory estimate:12.50 KiB, allocs estimate:200.

(and similarly, now we wrap every native JuliaTypes, which also incurs additional overheads that has never existed).

Well, inference is already costly and lattice element constructions might not be a serious bottleneck.
But at least for now, this example TTFP shot shows the inference on this PR at this point is less performing than on
master, even though I've not tried to optimize this PR yet:

# master (8985a2d629a525e42b9f12145e51b3aee95906b1)~/julia2 master aviatesk@amdci210s❯./usr/bin/julia-e'@time using Plots; @time plot(rand(10,3))'7.281519 seconds (12.80 M allocations:821.300 MiB,4.65% gc time,27.71% compilation time)2.648468 seconds (3.55 M allocations:198.837 MiB,1.31% gc time,99.79% compilation time)# this PR~/julia3 remotes/origin/avi/typelattice* aviatesk@amdci211s❯./usr/bin/julia-e'@time using Plots; @time plot(rand(10,3))'7.385233 seconds (13.16 M allocations:847.765 MiB,5.15% gc time,29.00% compilation time)2.789241 seconds (4.35 M allocations:270.663 MiB,1.92% gc time,99.82% compilation time)

Copy link

Member

vchuravy commentedOct 11, 2021

interesting is the increase in allocations, but yes I was wondering about the additional overheads sinceTypeLattice is by default large, whereas nested types are optional larger.

Copy link

MemberAuthor

aviatesk commentedOct 11, 2021•
edited
Loading

There are many unnecessary allocations/indictions because of remaining works, e.g. this line is very hot but
the vector allocation is really unnecessary once we've refactored all tfuncs so that they work withTypeLattices.:

julia/base/compiler/tfuncs.jl

Lines 1619 to 1620 in723ed65

	#FIXME, all inference tfuncs should work on `TypeLattice`s
	argtypes=anymap(a->unwraptype(a), argtypes)

I hope this sort of remaining TODOs are contributing to the performance regression,
but if the lattice construction is the bottleneck, that's a serious problem...

Copy link

MemberAuthor

aviatesk commentedOct 12, 2021•
edited
Loading

So I did some profilings.
I used this scriptCCProfiler.jl, whereCCProfiler runs inference routine while managing its own global cache,
and so it allow us profile/benchmarkCore.Compiler more reliably:

# setup new AbstractInterpreterconst CC= Core.Compilerimport.CC: MethodInstance, CodeInstance, WorldRange, WorldViewstruct CCProfilerCache    dict::IdDict{MethodInstance,CodeInstance}endstruct CCProfiler<:CC.AbstractInterpreter    interp::CC.NativeInterpreter    cache::CCProfilerCacheCCProfiler(world= Base.get_world_counter();         interp= CC.NativeInterpreter(world),         cache=CCProfilerCache(IdDict{MethodInstance,CodeInstance}())        )=new(interp, cache)endCC.InferenceParams(profiler::CCProfiler)= CC.InferenceParams(profiler.interp)CC.OptimizationParams(profiler::CCProfiler)= CC.OptimizationParams(profiler.interp)CC.get_world_counter(profiler::CCProfiler)= CC.get_world_counter(profiler.interp)CC.get_inference_cache(profiler::CCProfiler)= CC.get_inference_cache(profiler.interp)CC.code_cache(profiler::CCProfiler)=WorldView(profiler.cache,WorldRange(CC.get_world_counter(profiler)))CC.get(wvc::WorldView{<:CCProfilerCache}, mi::MethodInstance, default)=get(wvc.cache.dict, mi, default)CC.getindex(wvc::WorldView{<:CCProfilerCache}, mi::MethodInstance)=getindex(wvc.cache.dict, mi)CC.haskey(wvc::WorldView{<:CCProfilerCache}, mi::MethodInstance)=haskey(wvc.cache.dict, mi)CC.setindex!(wvc::WorldView{<:CCProfilerCache}, ci::CodeInstance, mi::MethodInstance)=setindex!(wvc.cache.dict, ci, mi)# compile things, and check that the global cache isn't shared across inferences@time Base.return_types(println, (QuoteNode,),CCProfiler());@time Base.return_types(println, (QuoteNode,),CCProfiler());@time Base.return_types(println, (QuoteNode,),CCProfiler());# profile !using Profile@profile Base.return_types(println, (QuoteNode,),CCProfiler());Profile.print(; format=:flat, sortedby=:count)Profile.print(; recur=:flat, mincount=10)

Here are the results:

on this PR (723ed65)

julia># compile things, and check that global cache isn't shared across inferences@time Base.return_types(println, (QuoteNode,),CCProfiler());4.526008 seconds (9.79 M allocations:600.839 MiB,3.07% gc time,62.95% compilation time)julia>@time Base.return_types(println, (QuoteNode,),CCProfiler());0.930251 seconds (6.52 M allocations:400.996 MiB,16.07% gc time,100.00% compilation time)julia>@time Base.return_types(println, (QuoteNode,),CCProfiler());0.909979 seconds (6.52 M allocations:400.996 MiB,15.17% gc time,100.00% compilation time)julia># profile !using Profilejulia>@profile Base.return_types(println, (QuoteNode,),CCProfiler());julia> Profile.print(; format=:flat, sortedby=:count, mincount=10) Count  Overhead File                                      Line Function=============================100@Base/compiler/typeinfer.jl361 transform_result_for_cache100@Base/compiler/ssair/ir.jl1443finish(compact::Core.Compiler.IncrementalCompact)100@Base/compiler/ssair/ir.jl1327maybe_erase_unused!(extra_worklist::Vector{Int64}, compact::Core.Compiler.Incre...100@Base/array.jl411 getindex100@Base/compiler/ssair/slot2ssa.jl899construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Core.Compi...100@Base/compiler/ssair/legacy.jl6inflate_ir(ci::Core.CodeInfo, linfo::MethodInstance)100@Base/compiler/ssair/slot2ssa.jl15scan_entry!(result::Vector{Core.Compiler.SlotInfo}, idx::Int64, stmt::Any)100@Base/range.jl870 iterate100@Base/compiler/inferenceresult.jl65most_general_argtypes(method::Method, specTypes::Any, isva::Bool, withfirst::Bool)100@Base/compiler/ssair/slot2ssa.jl807construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Core.Compi...110@Base/compiler/ssair/inlining.jl929call_sig(ir::Core.Compiler.IRCode, stmt::Expr)110@Base/compiler/ssair/ir.jl253setindex!(is::Core.Compiler.InstructionStream, newval::Core.Compiler.Instructio...110@Base/compiler/tfuncs.jl1668builtin_tfunction(interp::Core.Compiler.AbstractInterpreter, f::Any, argtypes::...110@Base/compiler/compiler.jl142anymap(f::typeof(Core.Compiler.widenconst), a::Vector{Union{Core.Compiler._Abst...110@Base/compiler/ssair/legacy.jl42inflate_ir(ci::Core.CodeInfo, sptypes::Vector{Union{Core.Compiler._AbstractLatt...110@Base/compiler/abstractinterpretation.jl547abstract_call_method_with_const_args(interp::CCProfiler, result::Core.Compiler....110@Base/compiler/typelattice.jl190 TypeLattice#265110@Base/compiler/typelattice.jl187 Type##kw110@Base/compiler/typelattice.jl231 Const120@Base/compiler/ssair/ir.jl201 Core.Compiler.InstructionStream(len::Int64)120@Base/compiler/ssair/passes.jl766getfield_elim_pass!(ir::Core.Compiler.IRCode)120@Base/compiler/ssair/ir.jl1325 maybe_erase_unused!120@Base/compiler/ssair/queries.jl87compact_exprtype(compact::Core.Compiler.IncrementalCompact, value::Any)120@Base/compiler/ssair/inlining.jl584batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode, linetab...120@Base/compiler/optimize.jl325run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)120@Base/compiler/abstractinterpretation.jl1485abstract_eval_value(interp::CCProfiler, e::Any, vtypes::Vector{Core.Compiler.Va...120@Base/compiler/ssair/ir.jl293 IRCode120@Base/compiler/types.jl35 Type##kw120@Base/compiler/abstractinterpretation.jl542abstract_call_method_with_const_args(interp::CCProfiler, result::Core.Compiler....120@Base/compiler/inferenceresult.jl53most_general_argtypes(method::Method, specTypes::Any, isva::Bool, withfirst::Bool)130@Base/compiler/ssair/slot2ssa.jl635construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Core.Compi...130@Base/boot.jl468 Array130@Base/compiler/abstractinterpretation.jl1486abstract_eval_value(interp::CCProfiler, e::Any, vtypes::Vector{Core.Compiler.Va...140@Base/compiler/optimize.jl333run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)140@Base/compiler/ssair/ir.jl1306iterate(compact::Core.Compiler.IncrementalCompact,::Tuple{Int64, Int64})140@Base/compiler/abstractinterpretation.jl1096abstract_call_builtin(interp::CCProfiler, f::Core.Builtin, fargs::Vector{Any},...150@Base/compiler/ssair/ir.jl274 NewNodeStream150@Base/array.jl921 getindex150@Base/compiler/ssair/domtree.jl204construct_domtree(blocks::Vector{Core.Compiler.BasicBlock})150@Base/compiler/ssair/passes.jl594getfield_elim_pass!(ir::Core.Compiler.IRCode)150@Base/compiler/inferencestate.jl253 Core.Compiler.InferenceState(result::Core.Compiler.InferenceResult, cache::Symb...160@Base/compiler/abstractinterpretation.jl1265abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtypes::V...160@Base/compiler/ssair/inlining.jl838 Core.Compiler.InliningTodo(mi::MethodInstance, src::Vector{UInt8})160@Base/compiler/ssair/ir.jl1035process_node!(compact::Core.Compiler.IncrementalCompact, result_idx::Int64, ins...170@Base/compiler/ssair/inlining.jl589batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode, linetab...170@Base/compiler/typeutils.jl56 argtypes_to_type170@Base/compiler/inferenceresult.jl155cache_lookup(linfo::MethodInstance, given_argtypes::Vector{Union{Core.Compiler....170@Base/compiler/typelattice.jl229 Const180@Base/compiler/ssair/legacy.jl10inflate_ir(ci::Core.CodeInfo, linfo::MethodInstance)180@Base/compiler/typeinfer.jl366 transform_result_for_cache180@Base/compiler/typeinfer.jl347maybe_compress_codeinfo(interp::CCProfiler, linfo::MethodInstance, ci::Core.Cod...190@Base/compiler/ssair/ir.jl1456compact!(code::Core.Compiler.IRCode, allow_cfg_transforms::Bool)190@Base/compiler/utilities.jl128 retrieve_code_info200@Base/compiler/ssair/ir.jl477iterate(it::Core.Compiler.UseRefIterator,#unused#::Nothing)200@Base/compiler/ssair/slot2ssa.jl27scan_entry!(result::Vector{Core.Compiler.SlotInfo}, idx::Int64, stmt::Any)200@Base/compiler/types.jl35 InferenceResult200@Base/compiler/typeinfer.jl821typeinf_edge(interp::CCProfiler, method::Method, atypes::Any, sparams::Core.Sim...210@Base/array.jl1055 push!210@Base/compiler/inferencestate.jl250 Core.Compiler.InferenceState(result::Core.Compiler.InferenceResult, cache::Symb...220@Base/compiler/ssair/ir.jl469 iterate230@Base/array.jl533 fill230@Base/array.jl531 fill240@Base/compiler/ssair/ir.jl1307iterate(compact::Core.Compiler.IncrementalCompact,::Tuple{Int64, Int64})240@Base/compiler/abstractinterpretation.jl1494collect_argtypes(interp::CCProfiler, ea::Vector{Any}, vtypes::Vector{Core.Compi...250@Base/compiler/ssair/inlining.jl1097process_simple!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64, Any}}, idx::...260@Base/compiler/ssair/ir.jl1454 compact!260@Base/compiler/abstractinterpretation.jl1518abstract_eval_statement(interp::CCProfiler, e::Any, vtypes::Vector{Core.Compile...260@Base/array.jl1008 _growend!260@Base/compiler/typeinfer.jl822typeinf_edge(interp::CCProfiler, method::Method, atypes::Any, sparams::Core.Sim...270@Base/compiler/abstractinterpretation.jl526abstract_call_method_with_const_args(interp::CCProfiler, result::Core.Compiler....280@Base/compiler/typeinfer.jl280_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)280@Base/compiler/typeinfer.jl392cache_result!(interp::CCProfiler, result::Core.Compiler.InferenceResult)280@Base/compiler/abstractinterpretation.jl1667 abstract_eval_global320@Base/compiler/types.jl35 InferenceResult#245330@Base/compiler/utilities.jl256argextype(x::Any, src::Core.Compiler.IRCode, sptypes::Vector{Union{Core.Compile...330@Base/compiler/inferenceresult.jl52most_general_argtypes(method::Method, specTypes::Any, isva::Bool)340@Base/compiler/ssair/slot2ssa.jl45scan_slot_def_use(nargs::Int64, ci::Core.CodeInfo, code::Vector{Any})340@Base/compiler/inferenceresult.jl139matching_cache_argtypes(linfo::MethodInstance,#unused#::Nothing, va_override::...350@Base/boot.jl458 Array350@Base/compiler/optimize.jl423 slot2reg380@Base/compiler/ssair/queries.jl101is_known_call(e::Expr, func::Any, src::Core.Compiler.IncrementalCompact)380@Base/compiler/ssair/queries.jl91compact_exprtype(compact::Core.Compiler.IncrementalCompact, value::Any)410@Base/compiler/ssair/inlining.jl1263assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.InliningSt...430@Base/compiler/utilities.jl234 argextype490@Base/compiler/ssair/inlining.jl73ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineInfoNod...530@Base/iddict.jl178 get!530@Base/compiler/methodtable.jl97 (::Core.Compiler.var"#259#260"{Int64, Core.Compiler.CachedMethodTable{Core.Comp...530@Base/reflection.jl908 _methods_by_ftype530@Base/compiler/methodtable.jl68#findall#256530@Base/compiler/methodtable.jl65 (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{Int64}},::ty...540@Base/compiler/methodtable.jl96#findall#258540@Base/compiler/methodtable.jl95 (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{Int64}},::ty...550@Base/compiler/abstractinterpretation.jl29abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtyp...550@Base/compiler/abstractinterpretation.jl301find_matching_methods(argtypes::Vector{Union{Core.Compiler._AbstractLattice, Co...600@Base/compiler/optimize.jl424 slot2reg620@Base/compiler/ssair/legacy.jl4inflate_ir(ci::Core.CodeInfo, linfo::MethodInstance)620@Base/compiler/inferencestate.jl321sptypes_from_meth_instance(linfo::MethodInstance)630@Base/compiler/typelattice.jl210 Core.Compiler.TypeLattice(x::Core.Compiler.TypeLattice; typ::Type, constant::Co...730@Base/boot.jl449 Array750@Base/compiler/typelattice.jl210 Core.Compiler.TypeLattice(x::Core.Compiler.TypeLattice)790@Base/compiler/optimize.jl330run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)910@Base/compiler/ssair/inlining.jl842 Core.Compiler.InliningTodo(mi::MethodInstance, src::Vector{UInt8})1030@Base/compiler/optimize.jl322run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)1050@Base/compiler/ssair/inlining.jl829analyze_method!(match::Core.MethodMatch, atypes::Vector{Union{Core.Compiler._Ab...1060@Base/compiler/ssair/inlining.jl1181analyze_single_call!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64, Any}},...1080@Base/compiler/ssair/inlining.jl779resolve_todo(todo::Core.Compiler.InliningTodo, state::Core.Compiler.InliningSta...1130@Base/compiler/ssair/inlining.jl1325assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.InliningSt...1640@Base/compiler/ssair/inlining.jl70ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineInfoNod...1740@Base/compiler/abstractinterpretation.jl550abstract_call_method_with_const_args(interp::CCProfiler, result::Core.Compiler....2040@Base/compiler/abstractinterpretation.jl103abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtyp...2150@Base/compiler/optimize.jl326run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)2660@Base/compiler/abstractinterpretation.jl1896typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)4470@Base/compiler/optimize.jl315 optimize4500@Base/compiler/typeinfer.jl255_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)7610@Base/reflection.jl1246return_types(f::Any, types::Any, interp::CCProfiler)7610@Base/compiler/typeinfer.jl8 typeinf7610@Base/compiler/typeinfer.jl934typeinf_type(interp::CCProfiler, method::Method, atypes::Any, sparams::Core.Sim...7610@Base/compiler/typeinfer.jl209typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)7610@Base/compiler/typeinfer.jl226_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)7610@Base/compiler/abstractinterpretation.jl2016typeinf_nocycle(interp::CCProfiler, frame::Core.Compiler.InferenceState)7610@Base/compiler/abstractinterpretation.jl1916typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)7610@Base/compiler/abstractinterpretation.jl1522abstract_eval_statement(interp::CCProfiler, e::Any, vtypes::Vector{Core.Compile...7610@Base/compiler/abstractinterpretation.jl1382abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{Union{Co...7610@Base/compiler/abstractinterpretation.jl1398abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{Union{Co...7610@Base/compiler/abstractinterpretation.jl1259abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtypes::V...7610@Base/compiler/abstractinterpretation.jl1004abstract_apply(interp::CCProfiler, argtypes::Vector{Union{Core.Compiler._Abstra...7610@Base/compiler/abstractinterpretation.jl1344abstract_call_known(interp::CCProfiler, f::Any, fargs::Nothing, argtypes::Vecto...7610@Base/compiler/abstractinterpretation.jl95abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Nothing, argtypes::...7610@Base/compiler/abstractinterpretation.jl498abstract_call_method(interp::CCProfiler, method::Method, sig::Any, sparams::Cor...7610@Base/compiler/typeinfer.jl831typeinf_edge(interp::CCProfiler, method::Method, atypes::Any, sparams::Core.Sim...770770@Base/client.jl497_start()7700@Base/client.jl309exec_options(opts::Base.JLOptions)7700@Base/essentials.jl718#invokelatest#27700@Base/essentials.jl716 invokelatest7700@Base/client.jl379run_main_repl(interactive::Bool, quiet::Bool, banner::Bool, history_file::Bool,...7700@Base/client.jl394 (::Base.var"#932#934"{Bool, Bool, Bool})(REPL::Module)7700@REPL/src/REPL.jl350run_repl(repl::AbstractREPL, consumer::Any)7700@REPL/src/REPL.jl363run_repl(repl::AbstractREPL, consumer::Any; backend_on_current_task::Bool)7700@REPL/src/REPL.jl230start_repl_backend(backend::REPL.REPLBackend, consumer::Any)7700@REPL/src/REPL.jl245repl_backend_loop(backend::REPL.REPLBackend)7700@Base/boot.jl368 eval7700@REPL/src/REPL.jl151eval_user_input(ast::Any, backend::REPL.REPLBackend)Total snapshots:797 (100% utilization across all threads and tasks. Use the`groupby` kwarg tobreak down by thread and/or task)julia> Profile.print(; recur=:flat, mincount=10)Overhead ╎ [+additional indent] Count File:Line; Function=========================================================  ╎770@Base/client.jl:497;_start()  ╎770@Base/client.jl:309;exec_options(opts::Base.JLOptions)  ╎770@Base/client.jl:379;run_main_repl(interactive::Bool, quiet::Bool, banner::Bool, history_file::Bool, col...  ╎770@Base/essentials.jl:716; invokelatest  ╎770@Base/essentials.jl:718;#invokelatest#2  ╎770@Base/client.jl:394; (::Base.var"#932#934"{Bool, Bool, Bool})(REPL::Module)  ╎    ╎770@REPL/src/REPL.jl:350;run_repl(repl::AbstractREPL, consumer::Any)  ╎    ╎770@REPL/src/REPL.jl:363;run_repl(repl::AbstractREPL, consumer::Any; backend_on_current_task::Bool)  ╎    ╎770@REPL/src/REPL.jl:230;start_repl_backend(backend::REPL.REPLBackend, consumer::Any)  ╎    ╎770@REPL/src/REPL.jl:245;repl_backend_loop(backend::REPL.REPLBackend)  ╎    ╎770@REPL/src/REPL.jl:151;eval_user_input(ast::Any, backend::REPL.REPLBackend)8╎    ╎    ╎770@Base/boot.jl:368; eval  ╎    ╎    ╎761@Base/reflection.jl:1246;return_types(f::Any, types::Any, interp::CCProfiler)  ╎    ╎    ╎761@Base/compiler/typeinfer.jl:934;typeinf_type(interp::CCProfiler, method::Method, atypes::Any, sparams::Core....  ╎    ╎    ╎761@Base/compiler/typeinfer.jl:8; typeinf  ╎    ╎    ╎761@Base/compiler/typeinfer.jl:209;typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎761@Base/compiler/typeinfer.jl:226;_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:2016;typeinf_nocycle(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎266@Base/compiler/abstractinterpretation.jl:1896;typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1916;typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎18@Base/compiler/abstractinterpretation.jl:1518;abstract_eval_statement(interp::CCProfiler, e::Any, vtypes::Vector{Core....  ╎    ╎    ╎    ╎17@Base/compiler/abstractinterpretation.jl:1494;collect_argtypes(interp::CCProfiler, ea::Vector{Any}, vtypes::Vector{Cor...  ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1522;abstract_eval_statement(interp::CCProfiler, e::Any, vtypes::Vector{Core....1╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1382;abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{U...2╎    ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1398;abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{...  ╎    ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1259;abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, ar...  ╎    ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1004;abstract_apply(interp::CCProfiler, argtypes::Vector{Union{Core.Compile...  ╎    ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1398;abstract_call(interp::CCProfiler, fargs::Nothing, argtypes::Vector{Un...  ╎    ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:1344;abstract_call_known(interp::CCProfiler, f::Any, fargs::Nothing, argty...  ╎    ╎    ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:95;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Nothing,...  ╎    ╎    ╎    ╎    ╎    ╎761@Base/compiler/abstractinterpretation.jl:498;abstract_call_method(interp::CCProfiler, method::Method, sig::Any, s...  ╎    ╎    ╎    ╎    ╎    ╎20@Base/compiler/typeinfer.jl:821;typeinf_edge(interp::CCProfiler, method::Method, atypes::Any, spara...  ╎    ╎    ╎    ╎    ╎    ╎20@Base/compiler/types.jl:35; InferenceResult  ╎    ╎    ╎    ╎    ╎    ╎20@Base/compiler/types.jl:35; InferenceResult#245  ╎    ╎    ╎    ╎    ╎    ╎    ╎20@Base/compiler/inferenceresult.jl:139;matching_cache_argtypes(linfo::MethodInstance,#unused#::Nothing, ...  ╎    ╎    ╎    ╎    ╎    ╎    ╎20@Base/compiler/inferenceresult.jl:52;most_general_argtypes(method::Method, specTypes::Any, isva::Bool)  ╎    ╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/inferenceresult.jl:65;most_general_argtypes(method::Method, specTypes::Any, isva::Bool...10╎    ╎    ╎    ╎    ╎    ╎    ╎10@Base/range.jl:870; iterate  ╎    ╎    ╎    ╎    ╎    ╎26@Base/compiler/typeinfer.jl:822;typeinf_edge(interp::CCProfiler, method::Method, atypes::Any, spara...  ╎    ╎    ╎    ╎    ╎    ╎15@Base/compiler/inferencestate.jl:250; Core.Compiler.InferenceState(result::Core.Compiler.InferenceResult,...13╎    ╎    ╎    ╎    ╎    ╎13@Base/compiler/utilities.jl:128; retrieve_code_info  ╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/inferencestate.jl:253; Core.Compiler.InferenceState(result::Core.Compiler.InferenceResult,...  ╎    ╎    ╎    ╎    ╎    ╎761@Base/compiler/typeinfer.jl:831;typeinf_edge(interp::CCProfiler, method::Method, atypes::Any, spara...  ╎    ╎    ╎    ╎    ╎16@Base/compiler/abstractinterpretation.jl:1265;abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, ar...  ╎    ╎    ╎    ╎    ╎14@Base/compiler/abstractinterpretation.jl:1096;abstract_call_builtin(interp::CCProfiler, f::Core.Builtin, fargs::Vect...1╎    ╎    ╎    ╎    ╎11@Base/compiler/tfuncs.jl:1668;builtin_tfunction(interp::Core.Compiler.AbstractInterpreter, f::Any,...1╎    ╎    ╎    ╎    ╎760@Base/compiler/abstractinterpretation.jl:1344;abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, ar...  ╎    ╎    ╎    ╎    ╎54@Base/compiler/abstractinterpretation.jl:29;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any...1╎    ╎    ╎    ╎    ╎54@Base/compiler/abstractinterpretation.jl:301;find_matching_methods(argtypes::Vector{Union{Core.Compiler._AbstractLa...  ╎    ╎    ╎    ╎    ╎53@Base/compiler/methodtable.jl:95; (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{Int6...  ╎    ╎    ╎    ╎    ╎    ╎53@Base/compiler/methodtable.jl:96;#findall#258  ╎    ╎    ╎    ╎    ╎    ╎52@Base/iddict.jl:178; get!  ╎    ╎    ╎    ╎    ╎    ╎52@Base/compiler/methodtable.jl:97; (::Core.Compiler.var"#259#260"{Int64, Core.Compiler.CachedMethodTabl...  ╎    ╎    ╎    ╎    ╎    ╎52@Base/compiler/methodtable.jl:65; (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{I...  ╎    ╎    ╎    ╎    ╎    ╎52@Base/compiler/methodtable.jl:68;#findall#25652╎    ╎    ╎    ╎    ╎    ╎    ╎52@Base/reflection.jl:908; _methods_by_ftype  ╎    ╎    ╎    ╎    ╎759@Base/compiler/abstractinterpretation.jl:95;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any...  ╎    ╎    ╎    ╎    ╎204@Base/compiler/abstractinterpretation.jl:103;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any...  ╎    ╎    ╎    ╎    ╎27@Base/compiler/abstractinterpretation.jl:526;abstract_call_method_with_const_args(interp::CCProfiler, result::Core....1╎    ╎    ╎    ╎    ╎17@Base/compiler/inferenceresult.jl:155;cache_lookup(linfo::MethodInstance, given_argtypes::Vector{Union{Core...  ╎    ╎    ╎    ╎    ╎12@Base/compiler/abstractinterpretation.jl:542;abstract_call_method_with_const_args(interp::CCProfiler, result::Core....  ╎    ╎    ╎    ╎    ╎12@Base/compiler/types.jl:35; Type##kw  ╎    ╎    ╎    ╎    ╎    ╎12@Base/compiler/types.jl:35; InferenceResult#245  ╎    ╎    ╎    ╎    ╎11@Base/compiler/abstractinterpretation.jl:547;abstract_call_method_with_const_args(interp::CCProfiler, result::Core....1╎    ╎    ╎    ╎    ╎174@Base/compiler/abstractinterpretation.jl:550;abstract_call_method_with_const_args(interp::CCProfiler, result::Core....  ╎    ╎    ╎    ╎450@Base/compiler/typeinfer.jl:255;_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)1╎    ╎    ╎    ╎447@Base/compiler/optimize.jl:315; optimize  ╎    ╎    ╎    ╎103@Base/compiler/optimize.jl:322;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎35@Base/compiler/optimize.jl:423; slot2reg  ╎    ╎    ╎    ╎34@Base/compiler/ssair/slot2ssa.jl:45;scan_slot_def_use(nargs::Int64, ci::Core.CodeInfo, code::Vector{Any})  ╎    ╎    ╎    ╎    ╎10@Base/compiler/ssair/slot2ssa.jl:15;scan_entry!(result::Vector{Core.Compiler.SlotInfo}, idx::Int64, stmt::Any)  ╎    ╎    ╎    ╎    ╎10@Base/array.jl:1055; push!10╎    ╎    ╎    ╎    ╎10@Base/array.jl:1008; _growend!  ╎    ╎    ╎    ╎    ╎20@Base/compiler/ssair/slot2ssa.jl:27;scan_entry!(result::Vector{Core.Compiler.SlotInfo}, idx::Int64, stmt::Any)  ╎    ╎    ╎    ╎    ╎18@Base/compiler/ssair/ir.jl:469; iterate18╎    ╎    ╎    ╎    ╎18@Base/compiler/ssair/ir.jl:477;iterate(it::Core.Compiler.UseRefIterator,#unused#::Nothing)  ╎    ╎    ╎    ╎60@Base/compiler/optimize.jl:424; slot2reg  ╎    ╎    ╎    ╎13@Base/compiler/ssair/slot2ssa.jl:635;construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Cor...  ╎    ╎    ╎    ╎10@Base/compiler/ssair/slot2ssa.jl:807;construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Cor...  ╎    ╎    ╎    ╎    ╎10@Base/array.jl:531; fill  ╎    ╎    ╎    ╎    ╎10@Base/array.jl:533; fill  ╎    ╎    ╎    ╎    ╎10@Base/boot.jl:458; Array10╎    ╎    ╎    ╎    ╎10@Base/boot.jl:449; Array  ╎    ╎    ╎    ╎10@Base/compiler/ssair/slot2ssa.jl:899;construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Cor...  ╎    ╎    ╎    ╎12@Base/compiler/optimize.jl:325;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎12@Base/compiler/ssair/ir.jl:1454; compact!2╎    ╎    ╎    ╎215@Base/compiler/optimize.jl:326;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎164@Base/compiler/ssair/inlining.jl:70;ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineI...  ╎    ╎    ╎    ╎41@Base/compiler/ssair/inlining.jl:1263;assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.Inl...  ╎    ╎    ╎    ╎    ╎25@Base/compiler/ssair/inlining.jl:1097;process_simple!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64, Any}...  ╎    ╎    ╎    ╎    ╎11@Base/compiler/ssair/inlining.jl:929;call_sig(ir::Core.Compiler.IRCode, stmt::Expr)  ╎    ╎    ╎    ╎    ╎11@Base/compiler/utilities.jl:234; argextype4╎    ╎    ╎    ╎113@Base/compiler/ssair/inlining.jl:1325;assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.Inl...  ╎    ╎    ╎    ╎    ╎106@Base/compiler/ssair/inlining.jl:1181;analyze_single_call!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64,...  ╎    ╎    ╎    ╎    ╎105@Base/compiler/ssair/inlining.jl:829;analyze_method!(match::Core.MethodMatch, atypes::Vector{Union{Core.Comp...1╎    ╎    ╎    ╎    ╎103@Base/compiler/ssair/inlining.jl:779;resolve_todo(todo::Core.Compiler.InliningTodo, state::Core.Compiler.In...16╎    ╎    ╎    ╎    ╎16@Base/compiler/ssair/inlining.jl:838; Core.Compiler.InliningTodo(mi::MethodInstance, src::Vector{UInt8})  ╎    ╎    ╎    ╎    ╎86@Base/compiler/ssair/inlining.jl:842; Core.Compiler.InliningTodo(mi::MethodInstance, src::Vector{UInt8})  ╎    ╎    ╎    ╎    ╎62@Base/compiler/ssair/legacy.jl:4;inflate_ir(ci::Core.CodeInfo, linfo::MethodInstance)  ╎    ╎    ╎    ╎    ╎    ╎62@Base/compiler/inferencestate.jl:321;sptypes_from_meth_instance(linfo::MethodInstance)1╎    ╎    ╎    ╎    ╎    ╎62@Base/compiler/typelattice.jl:210; Core.Compiler.TypeLattice(x::Core.Compiler.TypeLattice)61╎    ╎    ╎    ╎    ╎    ╎61@Base/compiler/typelattice.jl:210; Core.Compiler.TypeLattice(x::Core.Compiler.TypeLattice; typ::Type,...  ╎    ╎    ╎    ╎    ╎17@Base/compiler/ssair/legacy.jl:10;inflate_ir(ci::Core.CodeInfo, linfo::MethodInstance)  ╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/ssair/legacy.jl:42;inflate_ir(ci::Core.CodeInfo, sptypes::Vector{Union{Core.Compiler._Ab...  ╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/ssair/ir.jl:293; IRCode  ╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/ssair/ir.jl:274; NewNodeStream  ╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/ssair/ir.jl:274; NewNodeStream  ╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/ssair/ir.jl:201; Core.Compiler.InstructionStream(len::Int64)  ╎    ╎    ╎    ╎    ╎    ╎    ╎10@Base/array.jl:531; fill  ╎    ╎    ╎    ╎    ╎    ╎    ╎10@Base/array.jl:533; fill  ╎    ╎    ╎    ╎    ╎    ╎    ╎10@Base/boot.jl:458; Array10╎    ╎    ╎    ╎    ╎    ╎    ╎10@Base/boot.jl:449; Array  ╎    ╎    ╎    ╎49@Base/compiler/ssair/inlining.jl:73;ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineI...2╎    ╎    ╎    ╎12@Base/compiler/ssair/inlining.jl:584;batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode,...  ╎    ╎    ╎    ╎17@Base/compiler/ssair/inlining.jl:589;batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode,...  ╎    ╎    ╎    ╎79@Base/compiler/optimize.jl:330;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎15@Base/compiler/ssair/passes.jl:594;getfield_elim_pass!(ir::Core.Compiler.IRCode)  ╎    ╎    ╎    ╎14@Base/compiler/ssair/queries.jl:101;is_known_call(e::Expr, func::Any, src::Core.Compiler.IncrementalCompact)2╎    ╎    ╎    ╎    ╎14@Base/compiler/ssair/queries.jl:91;compact_exprtype(compact::Core.Compiler.IncrementalCompact, value::Any)  ╎    ╎    ╎    ╎    ╎12@Base/compiler/utilities.jl:234; argextype1╎    ╎    ╎    ╎    ╎12@Base/compiler/utilities.jl:256;argextype(x::Any, src::Core.Compiler.IRCode, sptypes::Vector{Union{Cor...  ╎    ╎    ╎    ╎    ╎11@Base/compiler/abstractinterpretation.jl:1667; abstract_eval_global  ╎    ╎    ╎    ╎    ╎11@Base/compiler/typelattice.jl:231; Const  ╎    ╎    ╎    ╎    ╎    ╎11@Base/compiler/typelattice.jl:187; Type##kw11╎    ╎    ╎    ╎    ╎    ╎11@Base/compiler/typelattice.jl:190; TypeLattice#265  ╎    ╎    ╎    ╎12@Base/compiler/ssair/passes.jl:766;getfield_elim_pass!(ir::Core.Compiler.IRCode)  ╎    ╎    ╎    ╎14@Base/compiler/optimize.jl:333;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎28@Base/compiler/typeinfer.jl:280;_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎28@Base/compiler/typeinfer.jl:392;cache_result!(interp::CCProfiler, result::Core.Compiler.InferenceResult)  ╎    ╎    ╎    ╎10@Base/compiler/typeinfer.jl:361; transform_result_for_cache  ╎    ╎    ╎    ╎18@Base/compiler/typeinfer.jl:366; transform_result_for_cache18╎    ╎    ╎    ╎18@Base/compiler/typeinfer.jl:347;maybe_compress_codeinfo(interp::CCProfiler, linfo::MethodInstance, ci::Co...Total snapshots:797 (100% utilization across all threads and tasks. Use the`groupby` kwarg tobreak down by thread and/or task)

onmaster

julia># compile things, and check that global cache isn't shared across inferences@time Base.return_types(println, (QuoteNode,),CCProfiler());3.631322 seconds (7.11 M allocations:385.003 MiB,3.19% gc time,64.50% compilation time)julia>@time Base.return_types(println, (QuoteNode,),CCProfiler());0.712653 seconds (5.20 M allocations:283.478 MiB,16.46% gc time,100.00% compilation time)julia>@time Base.return_types(println, (QuoteNode,),CCProfiler());0.772917 seconds (5.20 M allocations:283.478 MiB,25.16% gc time,100.00% compilation time)julia># profile !using Profilejulia>@profile Base.return_types(println, (QuoteNode,),CCProfiler());julia> Profile.print(; format=:flat, sortedby=:count, mincount=10) Count  Overhead File                                      Line Function=============================100@Base/compiler/typeinfer.jl239_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)100@Base/compiler/abstractinterpretation.jl1328abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtypes::V...100@Base/compiler/abstractinterpretation.jl553abstract_call_method_with_const_args(interp::CCProfiler, result::Core.Compiler....100@Base/compiler/ssair/ir.jl580 Core.Compiler.IncrementalCompact(code::Core.Compiler.IRCode, allow_cfg_transfor...110@Base/compiler/ssair/ir.jl1030process_node!(compact::Core.Compiler.IncrementalCompact, result_idx::Int64, ins...110@Base/compiler/optimize.jl333run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)110@Base/compiler/ssair/queries.jl91 compact_exprtype110@Base/compiler/ssair/queries.jl101is_known_call(e::Expr, func::Any, src::Core.Compiler.IncrementalCompact)110@Base/array.jl921 getindex110@Base/array.jl411 getindex110@Base/boot.jl417 LineInfoNode120@Base/compiler/ssair/domtree.jl343SNCA!(domtree::Core.Compiler.DomTree, blocks::Vector{Core.Compiler.BasicBlock},...120@Base/compiler/ssair/inlining.jl1236maybe_handle_const_call!(ir::Core.Compiler.IRCode, idx::Int64, stmt::Expr, info...120@Base/compiler/ssair/inlining.jl593batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode, linetab...120@Base/compiler/ssair/inlining.jl497ir_inline_unionsplit!(compact::Core.Compiler.IncrementalCompact, idx::Int64, ar...120@Base/compiler/ssair/inlining.jl320ir_inline_item!(compact::Core.Compiler.IncrementalCompact, idx::Int64, argexprs...130@Base/compiler/ssair/inlining.jl20 with_atype130@Base/compiler/ssair/inlining.jl1128process_simple!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64, Any}}, idx::...130@Base/compiler/typelattice.jl280 widenconst130@Base/compiler/typeutils.jl53 (::Core.Compiler.var"#257#258")(a::Core.Const)130@Base/compiler/abstractinterpretation.jl1647 abstract_eval_global130@Base/compiler/utilities.jl256argextype(x::Any, src::Core.Compiler.IRCode, sptypes::Vector{Any}, slottypes::V...130@Base/compiler/inferencestate.jl251 Core.Compiler.InferenceState(result::Core.Compiler.InferenceResult, cache::Symb...130@Base/compiler/ssair/passes.jl767getfield_elim_pass!(ir::Core.Compiler.IRCode)130@Base/compiler/ssair/slot2ssa.jl416domsort_ssa!(ir::Core.Compiler.IRCode, domtree::Core.Compiler.DomTree)130@Base/iddict.jl30 IdDict130@Base/iddict.jl33 Core.Compiler.IdDict{Int64, Int64}(itr::Core.Compiler.Generator{Core.Compiler.I...140@Base/compiler/ssair/domtree.jl217 update_domtree!140@Base/compiler/ssair/inlining.jl1285assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.InliningSt...140@Base/compiler/typeinfer.jl280_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)140@Base/compiler/typeinfer.jl365 transform_result_for_cache140@Base/compiler/typeinfer.jl391cache_result!(interp::CCProfiler, result::Core.Compiler.InferenceResult)140@Base/compiler/typeinfer.jl346maybe_compress_codeinfo(interp::CCProfiler, linfo::MethodInstance, ci::Core.Cod...140@Base/compiler/ssair/ir.jl619 Core.Compiler.IncrementalCompact(code::Core.Compiler.IRCode, allow_cfg_transfor...150@Base/compiler/utilities.jl234 argextype150@Base/compiler/ssair/inlining.jl837 Core.Compiler.InliningTodo(mi::MethodInstance, src::Vector{UInt8})160@Base/compiler/utilities.jl39anymap(f::Core.Compiler.var"#257#258", a::Vector{Any})160@Base/compiler/utilities.jl128 retrieve_code_info170@Base/compiler/ssair/passes.jl781getfield_elim_pass!(ir::Core.Compiler.IRCode)180@Base/compiler/ssair/ir.jl1451compact!(code::Core.Compiler.IRCode, allow_cfg_transforms::Bool)180@Base/compiler/ssair/ir.jl195 Core.Compiler.InstructionStream(len::Int64)190@Base/compiler/ssair/ir.jl1302iterate(compact::Core.Compiler.IncrementalCompact,::Tuple{Int64, Int64})190@Base/compiler/ssair/legacy.jl10inflate_ir(ci::Core.CodeInfo, linfo::MethodInstance)190@Base/compiler/ssair/slot2ssa.jl899construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Core.Compi...190@Base/compiler/optimize.jl336run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)200@Base/int.jl86-200@Base/int.jl982-200@Base/compiler/inferencestate.jl248 Core.Compiler.InferenceState(result::Core.Compiler.InferenceResult, cache::Symb...210@Base/compiler/inferenceresult.jl167cache_lookup(linfo::MethodInstance, given_argtypes::Vector{Any}, cache::Vector{...210@Base/compiler/ssair/ir.jl269 NewNodeStream220@Base/compiler/ssair/domtree.jl204construct_domtree(blocks::Vector{Core.Compiler.BasicBlock})220@Base/compiler/ssair/inlining.jl591batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode, linetab...230@Base/compiler/typeutils.jl53 argtypes_to_type230@Base/compiler/abstractinterpretation.jl532abstract_call_method_with_const_args(interp::CCProfiler, result::Core.Compiler....230@Base/compiler/typeinfer.jl820 typeinf_edge240@Base/compiler/ssair/inlining.jl1257assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.InliningSt...250@Base/array.jl1233 resize!250@Base/array.jl895 iterate270@Base/boot.jl471 Array310@Base/array.jl1008 _growend!310@Base/compiler/ssair/inlining.jl841 Core.Compiler.InliningTodo(mi::MethodInstance, src::Core.CodeInfo)320@Base/compiler/optimize.jl328run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)330@Base/array.jl533 fill330@Base/array.jl531 fill350@Base/compiler/ssair/ir.jl1449compact!(code::Core.Compiler.IRCode, allow_cfg_transforms::Bool)370@Base/compiler/ssair/inlining.jl828analyze_method!(match::Core.MethodMatch, atypes::Vector{Any}, state::Core.Compi...380@Base/compiler/ssair/inlining.jl1175analyze_single_call!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64, Any}},...410@Base/compiler/ssair/inlining.jl75ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineInfoNod...430@Base/compiler/ssair/inlining.jl1316assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.InliningSt...450@Base/boot.jl461 Array470@Base/compiler/ssair/inlining.jl778resolve_todo(todo::Core.Compiler.InliningTodo, state::Core.Compiler.InliningSta...520@Base/compiler/optimize.jl424 slot2reg560@Base/compiler/optimize.jl330run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)560@Base/compiler/ssair/ir.jl1449 compact!580@Base/reflection.jl908 _methods_by_ftype580@Base/compiler/methodtable.jl68#findall#252580@Base/compiler/methodtable.jl65 (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{Int64}},::ty...600@Base/iddict.jl178 get!600@Base/compiler/methodtable.jl97 (::Core.Compiler.var"#255#256"{Int64, Core.Compiler.CachedMethodTable{Core.Comp...620@Base/compiler/optimize.jl322run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)630@Base/compiler/methodtable.jl96#findall#254630@Base/compiler/methodtable.jl95 (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{Int64}},::ty...660@Base/compiler/abstractinterpretation.jl308find_matching_methods(argtypes::Vector{Any}, atype::Any, method_table::Core.Com...670@Base/compiler/abstractinterpretation.jl39abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtyp...820@Base/compiler/ssair/inlining.jl72ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineInfoNod...1020@Base/boot.jl452 Array1230@Base/compiler/optimize.jl326run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)1230@Base/compiler/abstractinterpretation.jl556abstract_call_method_with_const_args(interp::CCProfiler, result::Core.Compiler....1520@Base/compiler/abstractinterpretation.jl113abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtyp...2060@Base/compiler/abstractinterpretation.jl1871typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)3150@Base/compiler/optimize.jl315 optimize3160@Base/compiler/typeinfer.jl255_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)5380@Base/reflection.jl1246return_types(f::Any, types::Any, interp::CCProfiler)5380@Base/compiler/typeinfer.jl8 typeinf5380@Base/compiler/typeinfer.jl932typeinf_type(interp::CCProfiler, method::Method, atypes::Any, sparams::Core.Sim...5380@Base/compiler/typeinfer.jl209typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)5380@Base/compiler/typeinfer.jl226_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)5380@Base/compiler/abstractinterpretation.jl1987typeinf_nocycle(interp::CCProfiler, frame::Core.Compiler.InferenceState)5380@Base/compiler/abstractinterpretation.jl1891typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)5380@Base/compiler/abstractinterpretation.jl1505abstract_eval_statement(interp::CCProfiler, e::Any, vtypes::Vector{Core.Compile...5380@Base/compiler/abstractinterpretation.jl1369abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{Any}, sv...5380@Base/compiler/abstractinterpretation.jl1384abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{Any}, sv...5380@Base/compiler/abstractinterpretation.jl1246abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, argtypes::V...5380@Base/compiler/abstractinterpretation.jl993abstract_apply(interp::CCProfiler, argtypes::Vector{Any}, sv::Core.Compiler.Inf...5380@Base/compiler/abstractinterpretation.jl1329abstract_call_known(interp::CCProfiler, f::Any, fargs::Nothing, argtypes::Vecto...5380@Base/compiler/abstractinterpretation.jl105abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Nothing, argtypes::...5380@Base/compiler/typeinfer.jl829 typeinf_edge5380@Base/compiler/abstractinterpretation.jl504abstract_call_method(interp::CCProfiler, method::Method, sig::Any, sparams::Cor...548548@Base/client.jl497_start()5480@Base/client.jl309exec_options(opts::Base.JLOptions)5480@Base/essentials.jl725#invokelatest#25480@Base/essentials.jl723 invokelatest5480@Base/client.jl379run_main_repl(interactive::Bool, quiet::Bool, banner::Bool, history_file::Bool,...5480@Base/client.jl394 (::Base.var"#936#938"{Bool, Bool, Bool})(REPL::Module)5480@REPL/src/REPL.jl350run_repl(repl::AbstractREPL, consumer::Any)5480@REPL/src/REPL.jl363run_repl(repl::AbstractREPL, consumer::Any; backend_on_current_task::Bool)5480@REPL/src/REPL.jl230start_repl_backend(backend::REPL.REPLBackend, consumer::Any)5480@REPL/src/REPL.jl245repl_backend_loop(backend::REPL.REPLBackend)5480@Base/boot.jl368 eval5480@REPL/src/REPL.jl151eval_user_input(ast::Any, backend::REPL.REPLBackend)Total snapshots:571 (100% utilization across all threads and tasks. Use the`groupby` kwarg tobreak down by thread and/or task)julia> Profile.print(; recur=:flat, mincount=10)Overhead ╎ [+additional indent] Count File:Line; Function=========================================================  ╎548@Base/client.jl:497;_start()  ╎548@Base/client.jl:309;exec_options(opts::Base.JLOptions)  ╎548@Base/client.jl:379;run_main_repl(interactive::Bool, quiet::Bool, banner::Bool, history_file::Bool, col...  ╎548@Base/essentials.jl:723; invokelatest  ╎548@Base/essentials.jl:725;#invokelatest#2  ╎548@Base/client.jl:394; (::Base.var"#936#938"{Bool, Bool, Bool})(REPL::Module)  ╎    ╎548@REPL/src/REPL.jl:350;run_repl(repl::AbstractREPL, consumer::Any)  ╎    ╎548@REPL/src/REPL.jl:363;run_repl(repl::AbstractREPL, consumer::Any; backend_on_current_task::Bool)  ╎    ╎548@REPL/src/REPL.jl:230;start_repl_backend(backend::REPL.REPLBackend, consumer::Any)  ╎    ╎548@REPL/src/REPL.jl:245;repl_backend_loop(backend::REPL.REPLBackend)  ╎    ╎548@REPL/src/REPL.jl:151;eval_user_input(ast::Any, backend::REPL.REPLBackend)9╎    ╎    ╎548@Base/boot.jl:368; eval  ╎    ╎    ╎538@Base/reflection.jl:1246;return_types(f::Any, types::Any, interp::CCProfiler)  ╎    ╎    ╎538@Base/compiler/typeinfer.jl:932;typeinf_type(interp::CCProfiler, method::Method, atypes::Any, sparams::Core....  ╎    ╎    ╎538@Base/compiler/typeinfer.jl:8; typeinf  ╎    ╎    ╎538@Base/compiler/typeinfer.jl:209;typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎538@Base/compiler/typeinfer.jl:226;_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1987;typeinf_nocycle(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎206@Base/compiler/abstractinterpretation.jl:1871;typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1891;typeinf_local(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1505;abstract_eval_statement(interp::CCProfiler, e::Any, vtypes::Vector{Core....  ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1369;abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{A...3╎    ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1384;abstract_call(interp::CCProfiler, fargs::Vector{Any}, argtypes::Vector{...  ╎    ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1246;abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, ar...  ╎    ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:993;abstract_apply(interp::CCProfiler, argtypes::Vector{Any}, sv::Core.Com...  ╎    ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1384;abstract_call(interp::CCProfiler, fargs::Nothing, argtypes::Vector{An...  ╎    ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:1329;abstract_call_known(interp::CCProfiler, f::Any, fargs::Nothing, argty...  ╎    ╎    ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:105;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Nothing,...  ╎    ╎    ╎    ╎    ╎    ╎538@Base/compiler/abstractinterpretation.jl:504;abstract_call_method(interp::CCProfiler, method::Method, sig::Any, s...  ╎    ╎    ╎    ╎    ╎    ╎538@Base/compiler/typeinfer.jl:829; typeinf_edge  ╎    ╎    ╎    ╎    ╎10@Base/compiler/abstractinterpretation.jl:1328;abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, ar...3╎    ╎    ╎    ╎    ╎10@Base/compiler/typeutils.jl:53; argtypes_to_type  ╎    ╎    ╎    ╎    ╎536@Base/compiler/abstractinterpretation.jl:1329;abstract_call_known(interp::CCProfiler, f::Any, fargs::Vector{Any}, ar...  ╎    ╎    ╎    ╎    ╎64@Base/compiler/abstractinterpretation.jl:39;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any...3╎    ╎    ╎    ╎    ╎63@Base/compiler/abstractinterpretation.jl:308;find_matching_methods(argtypes::Vector{Any}, atype::Any, method_table:...  ╎    ╎    ╎    ╎    ╎60@Base/compiler/methodtable.jl:95; (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{Int6...  ╎    ╎    ╎    ╎    ╎    ╎60@Base/compiler/methodtable.jl:96;#findall#254  ╎    ╎    ╎    ╎    ╎    ╎57@Base/iddict.jl:178; get!2╎    ╎    ╎    ╎    ╎    ╎57@Base/compiler/methodtable.jl:97; (::Core.Compiler.var"#255#256"{Int64, Core.Compiler.CachedMethodTabl...  ╎    ╎    ╎    ╎    ╎    ╎55@Base/compiler/methodtable.jl:65; (::Core.Compiler.var"#findall##kw")(::NamedTuple{(:limit,), Tuple{I...  ╎    ╎    ╎    ╎    ╎    ╎55@Base/compiler/methodtable.jl:68;#findall#25255╎    ╎    ╎    ╎    ╎    ╎    ╎55@Base/reflection.jl:908; _methods_by_ftype  ╎    ╎    ╎    ╎    ╎536@Base/compiler/abstractinterpretation.jl:105;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any...  ╎    ╎    ╎    ╎    ╎28@Base/compiler/abstractinterpretation.jl:504;abstract_call_method(interp::CCProfiler, method::Method, sig::Any, spa...  ╎    ╎    ╎    ╎    ╎22@Base/compiler/typeinfer.jl:820; typeinf_edge  ╎    ╎    ╎    ╎    ╎    ╎14@Base/compiler/inferencestate.jl:248; Core.Compiler.InferenceState(result::Core.Compiler.InferenceResult, c...10╎    ╎    ╎    ╎    ╎    ╎10@Base/compiler/utilities.jl:128; retrieve_code_info  ╎    ╎    ╎    ╎    ╎151@Base/compiler/abstractinterpretation.jl:113;abstract_call_gf_by_type(interp::CCProfiler, f::Any, fargs::Vector{Any...  ╎    ╎    ╎    ╎    ╎23@Base/compiler/abstractinterpretation.jl:532;abstract_call_method_with_const_args(interp::CCProfiler, result::Core....  ╎    ╎    ╎    ╎    ╎21@Base/compiler/inferenceresult.jl:167;cache_lookup(linfo::MethodInstance, given_argtypes::Vector{Any}, cach...  ╎    ╎    ╎    ╎    ╎    ╎21@Base/array.jl:895; iterate  ╎    ╎    ╎    ╎    ╎    ╎20@Base/int.jl:982;-20╎    ╎    ╎    ╎    ╎    ╎20@Base/int.jl:86;-  ╎    ╎    ╎    ╎    ╎10@Base/compiler/abstractinterpretation.jl:553;abstract_call_method_with_const_args(interp::CCProfiler, result::Core....  ╎    ╎    ╎    ╎    ╎123@Base/compiler/abstractinterpretation.jl:556;abstract_call_method_with_const_args(interp::CCProfiler, result::Core....  ╎    ╎    ╎    ╎10@Base/compiler/typeinfer.jl:239;_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎316@Base/compiler/typeinfer.jl:255;_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎315@Base/compiler/optimize.jl:315; optimize  ╎    ╎    ╎    ╎62@Base/compiler/optimize.jl:322;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎52@Base/compiler/optimize.jl:424; slot2reg  ╎    ╎    ╎    ╎19@Base/compiler/ssair/slot2ssa.jl:899;construct_ssa!(ci::Core.CodeInfo, ir::Core.Compiler.IRCode, domtree::Cor...  ╎    ╎    ╎    ╎    ╎13@Base/compiler/ssair/slot2ssa.jl:416;domsort_ssa!(ir::Core.Compiler.IRCode, domtree::Core.Compiler.DomTree)  ╎    ╎    ╎    ╎    ╎13@Base/iddict.jl:33; Core.Compiler.IdDict{Int64, Int64}(itr::Core.Compiler.Generator{Core.Com...  ╎    ╎    ╎    ╎    ╎13@Base/iddict.jl:30; IdDict13╎    ╎    ╎    ╎    ╎13@Base/boot.jl:452; Array  ╎    ╎    ╎    ╎123@Base/compiler/optimize.jl:326;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎82@Base/compiler/ssair/inlining.jl:72;ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineI...  ╎    ╎    ╎    ╎24@Base/compiler/ssair/inlining.jl:1257;assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.Inl...  ╎    ╎    ╎    ╎    ╎13@Base/compiler/ssair/inlining.jl:1128;process_simple!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64, Any}...  ╎    ╎    ╎    ╎    ╎13@Base/compiler/ssair/inlining.jl:20; with_atype4╎    ╎    ╎    ╎    ╎13@Base/compiler/typeutils.jl:53; argtypes_to_type  ╎    ╎    ╎    ╎14@Base/compiler/ssair/inlining.jl:1285;assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.Inl...  ╎    ╎    ╎    ╎    ╎12@Base/compiler/ssair/inlining.jl:1236;maybe_handle_const_call!(ir::Core.Compiler.IRCode, idx::Int64, stmt::Ex...  ╎    ╎    ╎    ╎    ╎12@Base/compiler/ssair/inlining.jl:778;resolve_todo(todo::Core.Compiler.InliningTodo, state::Core.Compiler.Inl...1╎    ╎    ╎    ╎    ╎12@Base/compiler/ssair/inlining.jl:841; Core.Compiler.InliningTodo(mi::MethodInstance, src::Core.CodeInfo)  ╎    ╎    ╎    ╎43@Base/compiler/ssair/inlining.jl:1316;assemble_inline_todo!(ir::Core.Compiler.IRCode, state::Core.Compiler.Inl...  ╎    ╎    ╎    ╎    ╎38@Base/compiler/ssair/inlining.jl:1175;analyze_single_call!(ir::Core.Compiler.IRCode, todo::Vector{Pair{Int64,...1╎    ╎    ╎    ╎    ╎37@Base/compiler/ssair/inlining.jl:828;analyze_method!(match::Core.MethodMatch, atypes::Vector{Any}, state::Co...1╎    ╎    ╎    ╎    ╎35@Base/compiler/ssair/inlining.jl:778;resolve_todo(todo::Core.Compiler.InliningTodo, state::Core.Compiler.In...15╎    ╎    ╎    ╎    ╎15@Base/compiler/ssair/inlining.jl:837; Core.Compiler.InliningTodo(mi::MethodInstance, src::Vector{UInt8})  ╎    ╎    ╎    ╎    ╎19@Base/compiler/ssair/inlining.jl:841; Core.Compiler.InliningTodo(mi::MethodInstance, src::Vector{UInt8})  ╎    ╎    ╎    ╎    ╎12@Base/compiler/ssair/legacy.jl:10;inflate_ir(ci::Core.CodeInfo, linfo::MethodInstance)  ╎    ╎    ╎    ╎41@Base/compiler/ssair/inlining.jl:75;ssa_inlining_pass!(ir::Core.Compiler.IRCode, linetable::Vector{Core.LineI...  ╎    ╎    ╎    ╎22@Base/compiler/ssair/inlining.jl:591;batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode,...  ╎    ╎    ╎    ╎12@Base/compiler/ssair/inlining.jl:593;batch_inline!(todo::Vector{Pair{Int64, Any}}, ir::Core.Compiler.IRCode,...  ╎    ╎    ╎    ╎    ╎12@Base/compiler/ssair/inlining.jl:497;ir_inline_unionsplit!(compact::Core.Compiler.IncrementalCompact, idx::In...  ╎    ╎    ╎    ╎    ╎11@Base/compiler/ssair/inlining.jl:320;ir_inline_item!(compact::Core.Compiler.IncrementalCompact, idx::Int64,...11╎    ╎    ╎    ╎    ╎11@Base/boot.jl:417; LineInfoNode  ╎    ╎    ╎    ╎32@Base/compiler/optimize.jl:328;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎32@Base/compiler/ssair/ir.jl:1449; compact!  ╎    ╎    ╎    ╎24@Base/compiler/ssair/ir.jl:1449;compact!(code::Core.Compiler.IRCode, allow_cfg_transforms::Bool)  ╎    ╎    ╎    ╎    ╎10@Base/compiler/ssair/ir.jl:580; Core.Compiler.IncrementalCompact(code::Core.Compiler.IRCode, allow_cfg_t...  ╎    ╎    ╎    ╎    ╎10@Base/array.jl:531; fill  ╎    ╎    ╎    ╎    ╎10@Base/array.jl:533; fill  ╎    ╎    ╎    ╎    ╎10@Base/boot.jl:461; Array10╎    ╎    ╎    ╎    ╎10@Base/boot.jl:452; Array  ╎    ╎    ╎    ╎    ╎14@Base/compiler/ssair/ir.jl:619; Core.Compiler.IncrementalCompact(code::Core.Compiler.IRCode, allow_cfg_t...  ╎    ╎    ╎    ╎    ╎14@Base/compiler/ssair/ir.jl:269; NewNodeStream  ╎    ╎    ╎    ╎    ╎14@Base/compiler/ssair/ir.jl:269; NewNodeStream  ╎    ╎    ╎    ╎    ╎14@Base/compiler/ssair/ir.jl:195; Core.Compiler.InstructionStream(len::Int64)  ╎    ╎    ╎    ╎    ╎14@Base/array.jl:531; fill  ╎    ╎    ╎    ╎    ╎    ╎14@Base/array.jl:533; fill  ╎    ╎    ╎    ╎    ╎    ╎14@Base/boot.jl:461; Array14╎    ╎    ╎    ╎    ╎    ╎14@Base/boot.jl:452; Array  ╎    ╎    ╎    ╎56@Base/compiler/optimize.jl:330;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎13@Base/compiler/ssair/passes.jl:767;getfield_elim_pass!(ir::Core.Compiler.IRCode)  ╎    ╎    ╎    ╎17@Base/compiler/ssair/passes.jl:781;getfield_elim_pass!(ir::Core.Compiler.IRCode)  ╎    ╎    ╎    ╎17@Base/compiler/ssair/domtree.jl:204;construct_domtree(blocks::Vector{Core.Compiler.BasicBlock})  ╎    ╎    ╎    ╎    ╎13@Base/compiler/ssair/domtree.jl:217; update_domtree!  ╎    ╎    ╎    ╎    ╎12@Base/compiler/ssair/domtree.jl:343;SNCA!(domtree::Core.Compiler.DomTree, blocks::Vector{Core.Compiler.Basi...  ╎    ╎    ╎    ╎    ╎12@Base/array.jl:1233; resize!12╎    ╎    ╎    ╎    ╎12@Base/array.jl:1008; _growend!  ╎    ╎    ╎    ╎11@Base/compiler/optimize.jl:333;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎19@Base/compiler/optimize.jl:336;run_passes(ci::Core.CodeInfo, sv::Core.Compiler.OptimizationState)  ╎    ╎    ╎    ╎19@Base/compiler/ssair/ir.jl:1449; compact!  ╎    ╎    ╎    ╎10@Base/compiler/ssair/ir.jl:1449;compact!(code::Core.Compiler.IRCode, allow_cfg_transforms::Bool)  ╎    ╎    ╎    ╎14@Base/compiler/typeinfer.jl:280;_typeinf(interp::CCProfiler, frame::Core.Compiler.InferenceState)  ╎    ╎    ╎    ╎14@Base/compiler/typeinfer.jl:391;cache_result!(interp::CCProfiler, result::Core.Compiler.InferenceResult)  ╎    ╎    ╎    ╎14@Base/compiler/typeinfer.jl:365; transform_result_for_cache14╎    ╎    ╎    ╎14@Base/compiler/typeinfer.jl:346;maybe_compress_codeinfo(interp::CCProfiler, linfo::MethodInstance, ci::Co...Total snapshots:571 (100% utilization across all threads and tasks. Use the`groupby` kwarg tobreak down by thread and/or task)

So as for this specific inference onprintln(::QuoteNode):

TypeLattice constructions incurred some costs, it recorded75 out of797 snapshots;
especially these two sites seem to be hot:
- NativeType construction insptypes_from_meth_instance (62/75): this indirection has never existed
- Const construction inabstract_eval_global (11/75): we may want to delay "constant to type" retrieval ?

@vtjnash do you think we want to pay more attentions on this problem at this point ?
There are many remaining places we should/can improve, but the performance cost withTypeLattice construction is something unavoidable with this approach, so it might be a serious problem of this PR ?

Copy link

Member

vtjnash commentedOct 12, 2021

Eventually TypeLattice should end up only ever on the stack. I think we can continue working towards that.

Copy link

Member

JeffBezanson commentedOct 12, 2021

Bikeshed suggestion: could we call itLatticeElement (orLatticeElt etc.), since it is an element and not a lattice?

aviatesk force-pushed theavi/typelattice branch 3 times, most recently from3ead597 to7cbf430Compare

October 13, 2021 09:36

aviatesk commented

Oct 13, 2021

View reviewed changes

base/compiler/typelattice.jl OutdatedShow resolvedHide resolved

aviatesk force-pushed theavi/typelattice branch from7cbf430 to65473aaCompare

October 16, 2021 17:34

Copy link

MemberAuthor

aviatesk commentedOct 16, 2021

Bikeshed suggestion: could we call itLatticeElement (orLatticeElt etc.), since it is an element and not a lattice?

yeah, I decided to go withLatticeElement.

aviatesk force-pushed theavi/typelattice branch 4 times, most recently fromdae5ad3 toc059ef3Compare

December 18, 2021 02:21

Copy link

Contributor

o314 commentedDec 26, 2021

A very high level works on lattice !
Please also note, that all '|' '&', '-' etc. ops work starts at set level @ python (cf.https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset )

This IMHO lands to

a larger codebase => better growth thru pyramidal impl
a larger userbase => better code review
a better engineered product thru better pursuing of single-responsibility / solid best practices
sure there is more to say positively there

I have just (re)coded disjoint_union, ispartition above AbstractSet
Those simple shortcuts lead to way more cleaner code

Base.:(<=)(a::AbstractSet, b::AbstractSet)=issubset(a, b)# or  ⊑ ? infix op is what mattersBase.:(&)(a::AbstractSet, bs::AbstractSet...)=intersect(a, bs...)Base.:(|)(a::AbstractSet, bs::AbstractSet...)=union(a, bs...)Base.:(-)(a::AbstractSet, bs::AbstractSet...)=setdiff(a, bs...)# todo xor, disjoint_union

Those can be easily done @ abstractset too

union!(a::AbstractSet, bs...)= Base.afoldl(union!, a, bs...)setdiff!(a::AbstractSet, bs...)= Base.afoldl(setdiff!, a, bs...)intersect!(a::AbstractSet, bs...)= Base.afoldl(intersect!, a, bs...)symdiff!(a::AbstractSet, bs...)= Base.afoldl(symdiff!, a, bs...)

May be not be the exact place, but lattice is run so everywhere, coded quite unfrequently; and set/lattice are so close ...

AriMKatz mentioned this pull request

Jan 3, 2022

Index sets and constant propagation on Array shapes#43642

Open

aviatesk force-pushed theavi/typelattice branch 6 times, most recently from56b1714 to5711dc5Compare

January 6, 2022 13:46

aviatesk force-pushed theavi/typelattice branch 3 times, most recently fromc999912 tof45a8b5Compare

January 11, 2022 13:29

aviatesk force-pushed theavi/typelattice branch 6 times, most recently frome5d6d0f to0750387Compare

January 22, 2022 06:07

aviatesk added4 commits

January 25, 2022 19:07

lattice overhaul step 1: separate contexts where native Julia types a…

306b6b0

…re expected from those where extended lattice wrappers are

lattice overhaul step 2: convert existing extended lattice wrappers t…

4baf148

…o `LatticeElement` attributes- pack `PartialStruct` into `LatticeElement.fields`- pack `Conditional`/`InterConditional` into `LatticeElement.conditional`- pack `Const` into `LatticeElement.constant`- pack `PartialTypeVar` into `LatticeElement.partialtypevar`- pack `LimitedAccuracy` into `LatticeElement.causes`- pack `PartialOpaque` into `LatticeElement.partialopaque`- pack `MaybeUndef` into `LatticeElement.maybeundef`- merge `LatticeElement.partialopaque` and `LatticeElement.partialopaque`  There is not much value in keeping them separate, since a variable  usually doesn't have these "special" attributes at the same time.- wrap `Vararg` in `LatticeElement.special::Vararg`- add HACK to allow `DelayedTyp` to sneak in `LatticeElement` system  And now we can eliminate `AbstractLattice`, and our inference code  works with `LatticeElement` (mostly).- define `SSAValueType(s)` / `Argtypes` aliases

lattice overhaul step 3: clean up implementations

520b382

lattice overhaul step 3: simplifytmerge

d223d61

aviatesk force-pushed theavi/typelattice branch from0750387 tod223d61Compare

January 25, 2022 10:07

vtjnash mentioned this pull request

Mar 2, 2022

widenconst of a Const(::Type) can be quite slow#44402

Closed

Keno added a commit that referenced this pull request

Aug 29, 2022

WIP: Refactor lattice code to expose layering and enable easy extension

07ac043

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno mentioned this pull request

Aug 29, 2022

Refactor lattice code to expose layering and enable easy extension#46526

Merged

Keno added a commit that referenced this pull request

Aug 31, 2022

Refactor lattice code to expose layering and enable easy extension

0ebc57c

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Aug 31, 2022

Refactor lattice code to expose layering and enable easy extension

59f14a1

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Aug 31, 2022

Refactor lattice code to expose layering and enable easy extension

1c60614

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Aug 31, 2022

Refactor lattice code to expose layering and enable easy extension

7b0eeb9

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Aug 31, 2022

Refactor lattice code to expose layering and enable easy extension

f7f4776

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Aug 31, 2022

Refactor lattice code to expose layering and enable easy extension

b4fe1cc

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Aug 31, 2022

Refactor lattice code to expose layering and enable easy extension

b128649

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into Base.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- JLTypeLattice (Anything that's a `Type`)- ConstsLattice ( + `Const`, `PartialTypeVar`)- PartialsLattice ( + `PartialStruct` )- ConditionalsLattice ( + `Conditional` )- InferenceLattice ( + `LimitedAccuracy`, `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

aviatesk pushed a commit that referenced this pull request

Sep 1, 2022

Refactor lattice code to expose layering and enable easy extension

2cc3e9f

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the Julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into `Base`.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- `JLTypeLattice` (Anything that's a `Type`)- `ConstsLattice` ( + `Const`, `PartialTypeVar`)- `PartialsLattice` ( + `PartialStruct`, `PartialOpaque` )- `ConditionalsLattice` ( + `Conditional` )- `InferenceLattice` ( + `LimitedAccuracy` )- `OptimizerLattice` ( + `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

aviatesk pushed a commit that referenced this pull request

Sep 1, 2022

Refactor lattice code to expose layering and enable easy extension

ffadb8c

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the Julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into `Base`.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- `JLTypeLattice` (Anything that's a `Type`)- `ConstsLattice` ( + `Const`, `PartialTypeVar`)- `PartialsLattice` ( + `PartialStruct`, `PartialOpaque` )- `ConditionalsLattice` ( + `Conditional` )- `InferenceLattice` ( + `LimitedAccuracy` )- `OptimizerLattice` ( + `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Sep 1, 2022

Refactor lattice code to expose layering and enable easy extension

e83e40b

There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the Julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into `Base`.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- `JLTypeLattice` (Anything that's a `Type`)- `ConstsLattice` ( + `Const`, `PartialTypeVar`)- `PartialsLattice` ( + `PartialStruct`, `PartialOpaque` )- `ConditionalsLattice` ( + `Conditional` )- `InferenceLattice` ( + `LimitedAccuracy` )- `OptimizerLattice` ( + `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).

Keno added a commit that referenced this pull request

Sep 2, 2022

Refactor lattice code to expose layering and enable easy extension (#…

44c50ea

…46526)There's been two threads of work involving the compiler's notion ofthe inference lattice. One is that the lattice has gotten to complicatedand with too many internal constraints that are not manifest in thetype system.#42596 attempted to address this, but it's quite disruptiveas it changes the lattice types and all the signatures of the latticeoperations, which are used quite extensively throughout the ecosystem(despite being internal), so that change is quite disruptive (andsomething we'd ideally only make the ecosystem do once).The other thread of work is that people would like to experiment witha variety of extended lattices outside of base (either to prototypepotential additions to the lattice in base or to do custom abstractinterpretation over the Julia code). At the moment, the lattice isquite closely interwoven with the rest of the abstract interpreter.In response to this request in#40992, I had proposed a `CustomLattice`element with callbacks, but this doesn't compose particularly well,is cumbersome and imposes overhead on some of the hottest parts ofthe compiler, so it's a bit of a tough sell to merge into `Base`.In this PR, I'd like to propose a refactoring that is relativelynon-invasive to non-Base users, but I think would allow easierexperimentation with changes to the lattice for these two usecases. In essence, we're splitting the lattice into a ladder of5 different lattices, each containing the previous lattice as asub-lattice. These 5 lattices are:- `JLTypeLattice` (Anything that's a `Type`)- `ConstsLattice` ( + `Const`, `PartialTypeVar`)- `PartialsLattice` ( + `PartialStruct`, `PartialOpaque` )- `ConditionalsLattice` ( + `Conditional` )- `InferenceLattice` ( + `LimitedAccuracy` )- `OptimizerLattice` ( + `MaybeUndef` )The idea is that where a lattice element contains another latticeelement (e.g. in `PartialStruct` or `Conditional`), the elementcontained may only be from a wider lattice. In this PR, thisis not enforced by the type system. This is quite deliberate, asI want to retain the types and object layouts of the lattice elements,but of course a future#42596-like change could add such typeenforcement.Of particular note is that the `PartialsLattice` and `ConditionalsLattice`is parameterized and additional layers may be added in the stack.For example, in#40992, I had proposed a lattice element that refines`Int` and tracks symbolic expressions. In this setup, this couldbe accomplished by adding an appropriate lattice in between the`ConstsLattice` and the `PartialsLattice` (of course, additionalhooks would be required to make the tfuncs work, but that isoutside the scope of this PR).I don't think this is a full solution, but I think it'll help usplay with some of these extended lattice options over the next6-12 months in the packages that want to do this sort of thing.Presumably once we know what all the potential lattice extensionslook like, we will want to take another look at this (likelytogether with whatever solution we come up with for theAbstractInterpreter composability problem and a rebase of#42596).WIP because I didn't bother updating and plumbing through the latticein all the call sites yet, but that's mostly mechanical, so if welike this direction, I will make that change and hope to merge thisin short order (because otherwise it'll accumulate massive mergeconflicts).