-
-
Notifications
You must be signed in to change notification settings - Fork 5.4k
/
abstractlattice.jl
311 lines (259 loc) Β· 13 KB
/
abstractlattice.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
# TODO add more documentations
function widenlattice end
function is_valid_lattice_norec end
"""
struct JLTypeLattice <: AbstractLattice
A singleton type representing the lattice of Julia types, without any inference extensions.
"""
struct JLTypeLattice <: AbstractLattice; end
widenlattice(::JLTypeLattice) = error("Type lattice is the least-precise lattice available")
is_valid_lattice_norec(::JLTypeLattice, @nospecialize(elem)) = isa(elem, Type)
"""
struct ConstsLattice <: AbstractLattice
A lattice extending `JLTypeLattice` and adjoining `Const` and `PartialTypeVar`.
"""
struct ConstsLattice <: AbstractLattice; end
widenlattice(::ConstsLattice) = JLTypeLattice()
is_valid_lattice_norec(::ConstsLattice, @nospecialize(elem)) = isa(elem, Const) || isa(elem, PartialTypeVar)
"""
struct PartialsLattice{π<:AbstractLattice} <: AbstractLattice
A lattice extending a base lattice `π` and adjoining `PartialStruct` and `PartialOpaque`.
"""
struct PartialsLattice{π<:AbstractLattice} <: AbstractLattice
parent::π
end
widenlattice(π::PartialsLattice) = π.parent
is_valid_lattice_norec(::PartialsLattice, @nospecialize(elem)) = isa(elem, PartialStruct) || isa(elem, PartialOpaque)
"""
struct ConditionalsLattice{π<:AbstractLattice} <: AbstractLattice
A lattice extending a base lattice `π` and adjoining `Conditional`.
"""
struct ConditionalsLattice{π<:AbstractLattice} <: AbstractLattice
parent::π
end
widenlattice(π::ConditionalsLattice) = π.parent
is_valid_lattice_norec(::ConditionalsLattice, @nospecialize(elem)) = isa(elem, Conditional)
"""
struct InterConditionalsLattice{π<:AbstractLattice} <: AbstractLattice
A lattice extending a base lattice `π` and adjoining `InterConditional`.
"""
struct InterConditionalsLattice{π<:AbstractLattice} <: AbstractLattice
parent::π
end
widenlattice(π::InterConditionalsLattice) = π.parent
is_valid_lattice_norec(::InterConditionalsLattice, @nospecialize(elem)) = isa(elem, InterConditional)
"""
struct MustAliasesLattice{π<:AbstractLattice}
A lattice extending lattice `π` and adjoining `MustAlias`.
"""
struct MustAliasesLattice{π<:AbstractLattice} <: AbstractLattice
parent::π
end
widenlattice(π::MustAliasesLattice) = π.parent
is_valid_lattice_norec(::MustAliasesLattice, @nospecialize(elem)) = isa(elem, MustAlias)
"""
struct InterMustAliasesLattice{π<:AbstractLattice}
A lattice extending lattice `π` and adjoining `InterMustAlias`.
"""
struct InterMustAliasesLattice{π<:AbstractLattice} <: AbstractLattice
parent::π
end
widenlattice(π::InterMustAliasesLattice) = π.parent
is_valid_lattice_norec(::InterMustAliasesLattice, @nospecialize(elem)) = isa(elem, InterMustAlias)
const AnyConditionalsLattice{π<:AbstractLattice} = Union{ConditionalsLattice{π}, InterConditionalsLattice{π}}
const AnyMustAliasesLattice{π<:AbstractLattice} = Union{MustAliasesLattice{π}, InterMustAliasesLattice{π}}
const SimpleInferenceLattice = typeof(PartialsLattice(ConstsLattice()))
const BaseInferenceLattice = typeof(ConditionalsLattice(SimpleInferenceLattice.instance))
const IPOResultLattice = typeof(InterConditionalsLattice(SimpleInferenceLattice.instance))
"""
struct InferenceLattice{π<:AbstractLattice} <: AbstractLattice
The full lattice used for abstract interpretation during inference.
Extends a base lattice `π` and adjoins `LimitedAccuracy`.
"""
struct InferenceLattice{π<:AbstractLattice} <: AbstractLattice
parent::π
end
widenlattice(π::InferenceLattice) = π.parent
is_valid_lattice_norec(::InferenceLattice, @nospecialize(elem)) = isa(elem, LimitedAccuracy)
"""
tmeet(π::AbstractLattice, a, b::Type)
Compute the lattice meet of lattice elements `a` and `b` over the lattice `π`,
dropping any results that will not be inhabited at runtime.
If `π` is `JLTypeLattice`, this is equivalent to type intersection plus the
elimination of results that have no concrete subtypes.
Note that currently `b` is restricted to being a type
(interpreted as a lattice element in the `JLTypeLattice` sub-lattice of `π`).
"""
function tmeet end
function tmeet(::JLTypeLattice, @nospecialize(a::Type), @nospecialize(b::Type))
ti = typeintersect(a, b)
valid_as_lattice(ti, true) || return Bottom
return ti
end
"""
tmerge(π::AbstractLattice, a, b)
Compute a lattice join of elements `a` and `b` over the lattice `π`.
Note that the computed element need not be the least upper bound of `a` and
`b`, but rather, we impose additional limitations on the complexity of the
joined element, ideally without losing too much precision in common cases and
remaining mostly associative and commutative.
"""
function tmerge end
"""
tmerge_field(π::AbstractLattice, a, b) -> nothing or lattice element
Compute a lattice join of elements `a` and `b` over the lattice `π`,
where `a` and `b` are fields of `PartialStruct` or `Const`.
This is an opt-in interface to allow external lattice implementation to provide its own
field-merge strategy. If it returns `nothing`, `tmerge(::PartialsLattice, ...)`
will use the default aggressive type merge implementation that does not use `tmerge`
recursively to reach convergence.
"""
function tmerge_field end
function tmerge_field(π::AbstractLattice, @nospecialize(a), @nospecialize(b))
return tmerge_field(widenlattice(π), a, b)
end
tmerge_field(::JLTypeLattice, @nospecialize(a), @nospecialize(b)) = nothing
"""
β(π::AbstractLattice, a, b)
Compute the lattice ordering (i.e. less-than-or-equal) relationship between
lattice elements `a` and `b` over the lattice `π`.
If `π` is `JLTypeLattice`, this is equivalent to subtyping.
"""
function β end
@nospecializeinfer β(::JLTypeLattice, @nospecialize(a::Type), @nospecialize(b::Type)) = a <: b
"""
β(π::AbstractLattice, a, b) -> Bool
The strict partial order over the type inference lattice.
This is defined as the irreflexive kernel of `β`.
"""
@nospecializeinfer β(π::AbstractLattice, @nospecialize(a), @nospecialize(b)) = β(π, a, b) && !β(π, b, a)
"""
β€(π::AbstractLattice, a, b) -> Bool
This order could be used as a slightly more efficient version of the strict order `β`,
where we can safely assume `a β b` holds.
"""
@nospecializeinfer β€(π::AbstractLattice, @nospecialize(a), @nospecialize(b)) = !β(π, b, a)
"""
is_lattice_equal(π::AbstractLattice, a, b) -> Bool
Check if two lattice elements are partial order equivalent.
This is basically `a β b && b β a` in the lattice of `π`
but (optionally) with extra performance optimizations.
"""
@nospecializeinfer function is_lattice_equal(π::AbstractLattice, @nospecialize(a), @nospecialize(b))
a === b && return true
return β(π, a, b) && β(π, b, a)
end
"""
has_nontrivial_extended_info(π::AbstractLattice, t) -> Bool
Determines whether the given lattice element `t` of `π` has non-trivial extended lattice
information that would not be available from the type itself.
"""
@nospecializeinfer has_nontrivial_extended_info(π::AbstractLattice, @nospecialize t) =
has_nontrivial_extended_info(widenlattice(π), t)
@nospecializeinfer function has_nontrivial_extended_info(π::PartialsLattice, @nospecialize t)
isa(t, PartialStruct) && return true
isa(t, PartialOpaque) && return true
return has_nontrivial_extended_info(widenlattice(π), t)
end
@nospecializeinfer function has_nontrivial_extended_info(π::ConstsLattice, @nospecialize t)
isa(t, PartialTypeVar) && return true
if isa(t, Const)
val = t.val
return !issingletontype(typeof(val)) && !(isa(val, Type) && hasuniquerep(val))
end
return has_nontrivial_extended_info(widenlattice(π), t)
end
@nospecializeinfer has_nontrivial_extended_info(::JLTypeLattice, @nospecialize(t)) = false
"""
is_const_prop_profitable_arg(π::AbstractLattice, t) -> Bool
Determines whether the given lattice element `t` of `π` has new extended lattice information
that should be forwarded along with constant propagation.
"""
@nospecializeinfer is_const_prop_profitable_arg(π::AbstractLattice, @nospecialize t) =
is_const_prop_profitable_arg(widenlattice(π), t)
@nospecializeinfer function is_const_prop_profitable_arg(π::PartialsLattice, @nospecialize t)
if isa(t, PartialStruct)
return true # might be a bit aggressive, may want to enable some check like follows:
# for i = 1:length(t.fields)
# fld = t.fields[i]
# isconstType(fld) && return true
# is_const_prop_profitable_arg(fld) && return true
# fld β fieldtype(t.typ, i) && return true
# end
# return false
end
isa(t, PartialOpaque) && return true
return is_const_prop_profitable_arg(widenlattice(π), t)
end
@nospecializeinfer function is_const_prop_profitable_arg(π::ConstsLattice, @nospecialize t)
if isa(t, Const)
# don't consider mutable values useful constants
val = t.val
return isa(val, Symbol) || isa(val, Type) || !ismutable(val)
end
isa(t, PartialTypeVar) && return false # this isn't forwardable
return is_const_prop_profitable_arg(widenlattice(π), t)
end
@nospecializeinfer is_const_prop_profitable_arg(::JLTypeLattice, @nospecialize t) = false
@nospecializeinfer is_forwardable_argtype(π::AbstractLattice, @nospecialize(x)) =
is_forwardable_argtype(widenlattice(π), x)
@nospecializeinfer function is_forwardable_argtype(π::ConditionalsLattice, @nospecialize x)
isa(x, Conditional) && return true
return is_forwardable_argtype(widenlattice(π), x)
end
@nospecializeinfer function is_forwardable_argtype(π::PartialsLattice, @nospecialize x)
isa(x, PartialStruct) && return true
isa(x, PartialOpaque) && return true
return is_forwardable_argtype(widenlattice(π), x)
end
@nospecializeinfer function is_forwardable_argtype(π::ConstsLattice, @nospecialize x)
isa(x, Const) && return true
return is_forwardable_argtype(widenlattice(π), x)
end
@nospecializeinfer is_forwardable_argtype(::JLTypeLattice, @nospecialize x) = false
"""
widenreturn(πα΅’::AbstractLattice, @nospecialize(rt), info::BestguessInfo) -> new_bestguess
widenreturn_noslotwrapper(πα΅’::AbstractLattice, @nospecialize(rt), info::BestguessInfo) -> new_bestguess
Appropriately converts inferred type of a return value `rt` to such a type
that we know we can store in the cache and is valid and good inter-procedurally,
E.g. if `rt isa Conditional` then `rt` should be converted to `InterConditional`
or the other cacheable lattice element.
External lattice `πα΅’::ExternalLattice` may overload:
- `widenreturn(πα΅’::ExternalLattice, @nospecialize(rt), info::BestguessInfo)`
- `widenreturn_noslotwrapper(πα΅’::ExternalLattice, @nospecialize(rt), info::BestguessInfo)`
"""
function widenreturn end, function widenreturn_noslotwrapper end
@nospecializeinfer is_valid_lattice(π::AbstractLattice, @nospecialize(elem)) =
is_valid_lattice_norec(π, elem) && is_valid_lattice(widenlattice(π), elem)
@nospecializeinfer is_valid_lattice(π::JLTypeLattice, @nospecialize(elem)) = is_valid_lattice_norec(π, elem)
has_conditional(π::AbstractLattice) = has_conditional(widenlattice(π))
has_conditional(::AnyConditionalsLattice) = true
has_conditional(::JLTypeLattice) = false
has_mustalias(π::AbstractLattice) = has_mustalias(widenlattice(π))
has_mustalias(::AnyMustAliasesLattice) = true
has_mustalias(::JLTypeLattice) = false
has_extended_unionsplit(π::AbstractLattice) = has_extended_unionsplit(widenlattice(π))
has_extended_unionsplit(::AnyMustAliasesLattice) = true
has_extended_unionsplit(::JLTypeLattice) = false
# Curried versions
β(π::AbstractLattice) = (@nospecialize(a), @nospecialize(b)) -> β(π, a, b)
β(π::AbstractLattice) = (@nospecialize(a), @nospecialize(b)) -> β(π, a, b)
β€(π::AbstractLattice) = (@nospecialize(a), @nospecialize(b)) -> β€(π, a, b)
partialorder(π::AbstractLattice) = β(π)
strictpartialorder(π::AbstractLattice) = β(π)
strictneqpartialorder(π::AbstractLattice) = β€(π)
# Fallbacks for external packages using these methods
const fallback_lattice = InferenceLattice(BaseInferenceLattice.instance)
const fallback_ipo_lattice = InferenceLattice(IPOResultLattice.instance)
@nospecializeinfer @nospecialize(a) β @nospecialize(b) = β(fallback_lattice, a, b)
@nospecializeinfer @nospecialize(a) β @nospecialize(b) = β(fallback_lattice, a, b)
@nospecializeinfer @nospecialize(a) β€ @nospecialize(b) = β€(fallback_lattice, a, b)
@nospecializeinfer tmeet(@nospecialize(a), @nospecialize(b)) = tmeet(fallback_lattice, a, b)
@nospecializeinfer tmerge(@nospecialize(a), @nospecialize(b)) = tmerge(fallback_lattice, a, b)
@nospecializeinfer is_lattice_equal(@nospecialize(a), @nospecialize(b)) = is_lattice_equal(fallback_lattice, a, b)
# Widenlattice with argument
widenlattice(::JLTypeLattice, @nospecialize(t)) = widenconst(t)
function widenlattice(π::AbstractLattice, @nospecialize(t))
is_valid_lattice_norec(π, t) && return t
widenlattice(widenlattice(π), t)
end