Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit59f14a1

Browse files
committed
Refactor lattice code to expose layering and enable easy extension
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).
1 parent682ae8a commit59f14a1

File tree

13 files changed

+374
-158
lines changed

13 files changed

+374
-158
lines changed

‎base/compiler/abstractinterpretation.jl

Lines changed: 61 additions & 49 deletions
Large diffs are not rendered by default.

‎base/compiler/abstractlattice.jl

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
abstract type AbstractLattice;end
2+
function widenend
3+
4+
"""
5+
struct JLTypeLattice
6+
7+
A singleton type representing the lattice of Julia types, without any inference
8+
extensions.
9+
"""
10+
struct JLTypeLattice<:AbstractLattice;end
11+
widen(::JLTypeLattice)=error("Type lattice is the least-precise lattice available")
12+
is_valid_lattice(::JLTypeLattice,@nospecialize(elem))=isa(elem, Type)
13+
14+
"""
15+
struct ConstsLattice
16+
17+
A lattice extending `JLTypeLattice` and adjoining `Const` and `PartialTypeVar`.
18+
"""
19+
struct ConstsLattice<:AbstractLattice;end
20+
widen(::ConstsLattice)=JLTypeLattice()
21+
is_valid_lattice(lattice::ConstsLattice,@nospecialize(elem))=
22+
is_valid_lattice(widen(lattice), elem)||isa(elem, Const)||isa(elem, PartialTypeVar)
23+
24+
"""
25+
struct PartialsLattice{L}
26+
27+
A lattice extending lattice `L` and adjoining `PartialStruct` and `PartialOpaque`.
28+
"""
29+
struct PartialsLattice{L<:AbstractLattice}<:AbstractLattice
30+
parent::L
31+
end
32+
widen(L::PartialsLattice)= L.parent
33+
is_valid_lattice(lattice::PartialsLattice,@nospecialize(elem))=
34+
is_valid_lattice(widen(lattice), elem)||
35+
isa(elem, PartialStruct)||isa(elem, PartialOpaque)
36+
37+
"""
38+
struct ConditionalsLattice{L}
39+
40+
A lattice extending lattice `L` and adjoining `Conditional`.
41+
"""
42+
struct ConditionalsLattice{L<:AbstractLattice}<:AbstractLattice
43+
parent::L
44+
end
45+
widen(L::ConditionalsLattice)= L.parent
46+
is_valid_lattice(lattice::ConditionalsLattice,@nospecialize(elem))=
47+
is_valid_lattice(widen(lattice), elem)||isa(elem, Conditional)
48+
49+
struct InterConditionalsLattice{L<:AbstractLattice}<:AbstractLattice
50+
parent::L
51+
end
52+
widen(L::InterConditionalsLattice)= L.parent
53+
is_valid_lattice(lattice::InterConditionalsLattice,@nospecialize(elem))=
54+
is_valid_lattice(widen(lattice), elem)||isa(elem, InterConditional)
55+
56+
const AnyConditionalsLattice{L}= Union{ConditionalsLattice{L}, InterConditionalsLattice{L}}
57+
const BaseInferenceLattice=typeof(ConditionalsLattice(PartialsLattice(ConstsLattice())))
58+
const IPOResultLattice=typeof(InterConditionalsLattice(PartialsLattice(ConstsLattice())))
59+
60+
"""
61+
struct OptimizerLattice
62+
63+
The lattice used by the optimizer. Extends
64+
`BaseInferenceLattice` with `MaybeUndef`.
65+
"""
66+
struct OptimizerLattice<:AbstractLattice;end
67+
widen(L::OptimizerLattice)= BaseInferenceLattice.instance
68+
is_valid_lattice(lattice::OptimizerLattice,@nospecialize(elem))=
69+
is_valid_lattice(widen(lattice), elem)||isa(elem, MaybeUndef)
70+
71+
"""
72+
struct InferenceLattice{L}
73+
74+
The full lattice used for abstract interpration during inference. Takes
75+
a base lattice and adjoins `LimitedAccuracy`.
76+
"""
77+
struct InferenceLattice{L}<:AbstractLattice
78+
parent::L
79+
end
80+
widen(L::InferenceLattice)= L.parent
81+
is_valid_lattice(lattice::InferenceLattice,@nospecialize(elem))=
82+
is_valid_lattice(widen(lattice), elem)||isa(elem, LimitedAccuracy)
83+
84+
"""
85+
tmeet(lattice, a, b::Type)
86+
87+
Compute the lattice meet of lattice elements `a` and `b` over the lattice
88+
`lattice`. If `lattice` is `JLTypeLattice`, this is equiavalent to type
89+
intersection. Note that currently `b` is restricted to being a type (interpreted
90+
as a lattice element in the JLTypeLattice sub-lattice of `lattice`).
91+
"""
92+
function tmeetend
93+
94+
"""
95+
tmerge(lattice, a, b)
96+
97+
Compute a lattice join of elements `a` and `b` over the lattice `lattice`.
98+
Note that the computed element need not be the least upper bound of `a` and
99+
`b`, but rather, we impose some heuristic limits on the complexity of the
100+
joined element, ideally without losing too much precision in common cases and
101+
remaining mostly associative and commutative.
102+
"""
103+
function tmergeend
104+
105+
"""
106+
⊑(lattice, a, b)
107+
108+
Compute the lattice ordering (i.e. less-than-or-equal) relationship between
109+
lattice elements `a` and `b` over the lattice `lattice`. If `lattice` is
110+
`JLTypeLattice`, this is equiavalent to subtyping.
111+
"""
112+
function⊑end
113+
114+
function⊑(::JLTypeLattice,@nospecialize(a::Type),@nospecialize(b::Type))
115+
a<:b
116+
end
117+
118+
119+
"""
120+
⊏(lattice, a, b) -> Bool
121+
122+
The strict partial order over the type inference lattice.
123+
This is defined as the irreflexive kernel of `⊑`.
124+
"""
125+
⊏(lattice::AbstractLattice,@nospecialize(a),@nospecialize(b))=⊑(lattice, a, b)&&!⊑(lattice, b, a)
126+
127+
"""
128+
⋤(lattice, a, b) -> Bool
129+
130+
This order could be used as a slightly more efficient version of the strict order `⊏`,
131+
where we can safely assume `a ⊑ b` holds.
132+
"""
133+
⋤(lattice::AbstractLattice,@nospecialize(a),@nospecialize(b))=!⊑(lattice, b, a)
134+
135+
"""
136+
is_lattice_equal(a, b) -> Bool
137+
138+
Check if two lattice elements are partial order equivalent.
139+
This is basically `a ⊑ b && b ⊑ a` but (optionally) with extra performance optimizations.
140+
"""
141+
functionis_lattice_equal(lattice::AbstractLattice,@nospecialize(a),@nospecialize(b))
142+
a=== b&&returntrue
143+
⊑(lattice, a, b)&&⊑(lattice, b, a)
144+
end
145+
146+
# Curried versions
147+
⊑(lattice::AbstractLattice)= (@nospecialize(a),@nospecialize(b))->⊑(lattice, a, b)
148+
⊏(lattice::AbstractLattice)= (@nospecialize(a),@nospecialize(b))->⊏(lattice, a, b)
149+
⋤(lattice::AbstractLattice)= (@nospecialize(a),@nospecialize(b))->⋤(lattice, a, b)
150+
151+
# Fallbacks for external packages using these methods
152+
const fallback_lattice=InferenceLattice(BaseInferenceLattice.instance)
153+
const fallback_ipo_lattice=InferenceLattice(IPOResultLattice.instance)
154+
155+
⊑(@nospecialize(a),@nospecialize(b))=⊑(fallback_lattice, a, b)
156+
tmeet(@nospecialize(a),@nospecialize(b))=tmeet(fallback_lattice, a, b)
157+
tmerge(@nospecialize(a),@nospecialize(b))=tmerge(fallback_lattice, a, b)
158+
⊏(@nospecialize(a),@nospecialize(b))=⊏(fallback_lattice, a, b)
159+
⋤(@nospecialize(a),@nospecialize(b))=⋤(fallback_lattice, a, b)
160+
is_lattice_equal(@nospecialize(a),@nospecialize(b))=is_lattice_equal(fallback_lattice, a, b)

‎base/compiler/compiler.jl

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -156,6 +156,7 @@ include("compiler/ssair/ir.jl")
156156
include("compiler/inferenceresult.jl")
157157
include("compiler/inferencestate.jl")
158158

159+
include("compiler/abstractlattice.jl")
159160
include("compiler/typeutils.jl")
160161
include("compiler/typelimits.jl")
161162
include("compiler/typelattice.jl")

‎base/compiler/optimize.jl

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -211,6 +211,8 @@ Returns a tuple of (effect_free_and_nothrow, nothrow) for a given statement.
211211
"""
212212
functionstmt_effect_flags(@nospecialize(stmt),@nospecialize(rt), src::Union{IRCode,IncrementalCompact})
213213
#TODO: We're duplicating analysis from inference here.
214+
lattice=OptimizerLattice()
215+
⊑ₒ=⊑(lattice)
214216
isa(stmt, PiNode)&&return (true,true)
215217
isa(stmt, PhiNode)&&return (true,true)
216218
isa(stmt, ReturnNode)&&return (false,true)
@@ -248,7 +250,7 @@ function stmt_effect_flags(@nospecialize(stmt), @nospecialize(rt), src::Union{IR
248250
return (total, total)
249251
end
250252
rt=== Bottom&&return (false,false)
251-
nothrow=_builtin_nothrow(f, Any[argextype(args[i], src)for i=2:length(args)], rt)
253+
nothrow=_builtin_nothrow(f, Any[argextype(args[i], src)for i=2:length(args)], rt, lattice)
252254
nothrow||return (false,false)
253255
return (contains_is(_EFFECT_FREE_BUILTINS, f), nothrow)
254256
elseif head===:new
@@ -277,11 +279,11 @@ function stmt_effect_flags(@nospecialize(stmt), @nospecialize(rt), src::Union{IR
277279
typ=argextype(args[1], src)
278280
typ, isexact=instanceof_tfunc(typ)
279281
isexact||return (false,false)
280-
typ⊑ Tuple||return (false,false)
282+
typ⊑ₒ Tuple||return (false,false)
281283
rt_lb=argextype(args[2], src)
282284
rt_ub=argextype(args[3], src)
283285
source=argextype(args[4], src)
284-
if!(rt_lb⊑ Type&& rt_ub⊑ Type&& source⊑ Method)
286+
if!(rt_lb⊑ₒ Type&& rt_ub⊑ₒ Type&& source⊑ₒ Method)
285287
return (false,false)
286288
end
287289
return (true,true)

‎base/compiler/ssair/inlining.jl

Lines changed: 13 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -114,6 +114,8 @@ function CFGInliningState(ir::IRCode)
114114
)
115115
end
116116

117+
⊑ₒ(@nospecialize(a),@nospecialize(b))=⊑(OptimizerLattice(), a, b)
118+
117119
# Tells the inliner that we're now inlining into block `block`, meaning
118120
# all previous blocks have been processed and can be added to the new cfg
119121
functioninline_into_block!(state::CFGInliningState, block::Int)
@@ -1080,8 +1082,8 @@ function inline_apply!(
10801082
nonempty_idx=0
10811083
for i= (arg_start+1):length(argtypes)
10821084
ti= argtypes[i]
1083-
ti⊑ Tuple{}&&continue
1084-
if ti⊑ Tuple&& nonempty_idx==0
1085+
ti⊑ₒ Tuple{}&&continue
1086+
if ti⊑ₒ Tuple&& nonempty_idx==0
10851087
nonempty_idx= i
10861088
continue
10871089
end
@@ -1123,9 +1125,9 @@ end
11231125
#TODO: this test is wrong if we start to handle Unions of function types later
11241126
is_builtin(s::Signature)=
11251127
isa(s.f, IntrinsicFunction)||
1126-
s.ft⊑ IntrinsicFunction||
1128+
s.ft⊑ₒ IntrinsicFunction||
11271129
isa(s.f, Builtin)||
1128-
s.ft⊑ Builtin
1130+
s.ft⊑ₒ Builtin
11291131

11301132
functioninline_invoke!(
11311133
ir::IRCode, idx::Int, stmt::Expr, info::InvokeCallInfo, flag::UInt8,
@@ -1165,7 +1167,7 @@ function narrow_opaque_closure!(ir::IRCode, stmt::Expr, @nospecialize(info), sta
11651167
ub, exact=instanceof_tfunc(ubt)
11661168
exact||return
11671169
# Narrow opaque closure type
1168-
newT=widenconst(tmeet(tmerge(lb, info.unspec.rt), ub))
1170+
newT=widenconst(tmeet(tmerge(OptimizerLattice(),lb, info.unspec.rt), ub))
11691171
if newT!= ub
11701172
# N.B.: Narrowing the ub requires a backdge on the mi whose type
11711173
# information we're using, since a change in that function may
@@ -1222,7 +1224,7 @@ function process_simple!(ir::IRCode, idx::Int, state::InliningState, todo::Vecto
12221224
ir.stmts[idx][:inst]= earlyres.val
12231225
returnnothing
12241226
end
1225-
if (sig.f=== modifyfield!|| sig.ft⊑typeof(modifyfield!))&&5<=length(stmt.args)<=6
1227+
if (sig.f=== modifyfield!|| sig.ft⊑ₒtypeof(modifyfield!))&&5<=length(stmt.args)<=6
12261228
let info= ir.stmts[idx][:info]
12271229
infoisa MethodResultPure&& (info= info.info)
12281230
infoisa ConstCallInfo&& (info= info.call)
@@ -1240,7 +1242,7 @@ function process_simple!(ir::IRCode, idx::Int, state::InliningState, todo::Vecto
12401242
end
12411243

12421244
ifcheck_effect_free!(ir, idx, stmt, rt)
1243-
if sig.f=== typeassert|| sig.ft⊑typeof(typeassert)
1245+
if sig.f=== typeassert|| sig.ft⊑ₒtypeof(typeassert)
12441246
# typeassert is a no-op if effect free
12451247
ir.stmts[idx][:inst]= stmt.args[2]
12461248
returnnothing
@@ -1637,7 +1639,7 @@ function early_inline_special_case(
16371639
elseifispuretopfunction(f)||contains_is(_PURE_BUILTINS, f)
16381640
returnSomeCase(quoted(val))
16391641
elseifcontains_is(_EFFECT_FREE_BUILTINS, f)
1640-
if_builtin_nothrow(f, argtypes[2:end], type)
1642+
if_builtin_nothrow(f, argtypes[2:end], type,OptimizerLattice())
16411643
returnSomeCase(quoted(val))
16421644
end
16431645
elseif f=== Core.get_binding_type
@@ -1683,17 +1685,17 @@ function late_inline_special_case!(
16831685
elseiflength(argtypes)==3&&istopfunction(f, :(>:))
16841686
# special-case inliner for issupertype
16851687
# that works, even though inference generally avoids inferring the `>:` Method
1686-
ifisa(type, Const)&&_builtin_nothrow(<:, Any[argtypes[3], argtypes[2]], type)
1688+
ifisa(type, Const)&&_builtin_nothrow(<:, Any[argtypes[3], argtypes[2]], type,OptimizerLattice())
16871689
returnSomeCase(quoted(type.val))
16881690
end
16891691
subtype_call=Expr(:call,GlobalRef(Core, :(<:)), stmt.args[3], stmt.args[2])
16901692
returnSomeCase(subtype_call)
1691-
elseif f=== TypeVar&&2<=length(argtypes)<=4&& (argtypes[2]⊑ Symbol)
1693+
elseif f=== TypeVar&&2<=length(argtypes)<=4&& (argtypes[2]⊑ₒ Symbol)
16921694
typevar_call=Expr(:call,GlobalRef(Core,:_typevar), stmt.args[2],
16931695
length(stmt.args)<4? Bottom: stmt.args[3],
16941696
length(stmt.args)==2? Any: stmt.args[end])
16951697
returnSomeCase(typevar_call)
1696-
elseif f=== UnionAll&&length(argtypes)==3&& (argtypes[2]⊑ TypeVar)
1698+
elseif f=== UnionAll&&length(argtypes)==3&& (argtypes[2]⊑ₒ TypeVar)
16971699
unionall_call=Expr(:foreigncall,QuoteNode(:jl_type_unionall), Any,svec(Any, Any),
16981700
0,QuoteNode(:ccall), stmt.args[2], stmt.args[3])
16991701
returnSomeCase(unionall_call)

‎base/compiler/ssair/passes.jl

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -289,7 +289,7 @@ function walk_to_defs(compact::IncrementalCompact, @nospecialize(defssa), @nospe
289289
# path, with a different type constraint. We may have
290290
# to redo some work here with the wider typeconstraint
291291
push!(worklist_defs, new_def)
292-
push!(worklist_constraints,tmerge(new_constraint, visited_constraints[new_def]))
292+
push!(worklist_constraints,tmerge(OptimizerLattice(),new_constraint, visited_constraints[new_def]))
293293
end
294294
continue
295295
end
@@ -348,7 +348,7 @@ function is_getfield_captures(@nospecialize(def), compact::IncrementalCompact)
348348
isa(which, Const)||returnfalse
349349
which.val===:captures||returnfalse
350350
oc=argextype(def.args[2], compact)
351-
returnoc⊑Core.OpaqueClosure
351+
return⊑(OptimizerLattice(), oc,Core.OpaqueClosure)
352352
end
353353

354354
struct LiftedValue
@@ -528,13 +528,15 @@ function lift_comparison!(::typeof(===), compact::IncrementalCompact,
528528
lift_comparison_leaves!(egal_tfunc, compact, val, cmp, lifting_cache, idx)
529529
end
530530

531+
isa_tfunc_opt(@nospecialize(v),@nospecialize(t))=isa_tfunc(OptimizerLattice(), v, t)
532+
531533
functionlift_comparison!(::typeof(isa), compact::IncrementalCompact,
532534
idx::Int, stmt::Expr, lifting_cache::IdDict{Pair{AnySSAValue, Any}, AnySSAValue})
533535
args= stmt.args
534536
length(args)==3||return
535537
cmp=argextype(args[3], compact)
536538
val= args[2]
537-
lift_comparison_leaves!(isa_tfunc, compact, val, cmp, lifting_cache, idx)
539+
lift_comparison_leaves!(isa_tfunc_opt, compact, val, cmp, lifting_cache, idx)
538540
end
539541

540542
functionlift_comparison!(::typeof(isdefined), compact::IncrementalCompact,
@@ -1446,15 +1448,15 @@ function adce_pass!(ir::IRCode)
14461448
r=searchsorted(unionphis, val.id; by= first)
14471449
if!isempty(r)
14481450
unionphi= unionphis[first(r)]
1449-
t=tmerge(unionphi[2], stmt.typ)
1451+
t=tmerge(OptimizerLattice(),unionphi[2], stmt.typ)
14501452
unionphis[first(r)]=Pair{Int,Any}(unionphi[1], t)
14511453
end
14521454
end
14531455
else
14541456
ifis_known_call(stmt, typeassert, compact)&&length(stmt.args)==3
14551457
# nullify safe `typeassert` calls
14561458
ty, isexact=instanceof_tfunc(argextype(stmt.args[3], compact))
1457-
if isexact&&argextype(stmt.args[2], compact)⊑ ty
1459+
if isexact&&⊑(OptimizerLattice(),argextype(stmt.args[2], compact), ty)
14581460
compact[idx]=nothing
14591461
continue
14601462
end
@@ -1483,7 +1485,7 @@ function adce_pass!(ir::IRCode)
14831485
if!isempty(r)
14841486
unionphi= unionphis[first(r)]
14851487
unionphis[first(r)]=Pair{Int,Any}(unionphi[1],
1486-
tmerge(unionphi[2], inst[:type]))
1488+
tmerge(OptimizerLattice(),unionphi[2], inst[:type]))
14871489
end
14881490
end
14891491
end
@@ -1499,7 +1501,7 @@ function adce_pass!(ir::IRCode)
14991501
continue
15001502
elseif t=== Any
15011503
continue
1502-
elseif compact.result[phi][:type]⊑ t
1504+
elseif⊑(OptimizerLattice(),compact.result[phi][:type], t)
15031505
continue
15041506
end
15051507
to_drop= Int[]

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp