#37474

pending completion

Build # #37474

Build Type

push

local

Committed by

web-flow

Commit Message

irinterp: Allow setting all IR flags (#48993)

Currently, `IR_FLAG_NOTHROW` is the only flag that irinterp is allowed to
set on statements, under the assumption that in order for a call to
be irinterp-eligible, it must have been proven `:foldable`, thus `:effect_free`,
and thus `IR_FLAG_EFFECT_FREE` was assumed to have been set. That reasoning
was sound at the time this code was written, but have since introduced
`EFFECT_FREE_IF_INACCESSIBLEMEMONLY`, which breaks the reasoning that
an `:effect_free` inference for the whole function implies the flag on
every statement. As a result, we were failing to DCE otherwise dead
statements if the IR came from irinterp.

Run Details

3 of 3 new or added lines in 1 file covered. (100.0%)

70258 of 82316 relevant lines covered (85.35%)

32461773.51 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.98

/base/compiler/typeutils.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

#####################
# lattice utilities #
#####################

# true if Type{T} is inlineable as constant T
# requires that T is a singleton, s.t. T == S implies T === S
isconstType(@nospecialize t) = isType(t) && hasuniquerep(t.parameters[1])

# test whether type T has a unique representation, s.t. T == S implies T === S
function hasuniquerep(@nospecialize t)
    # typeof(Bottom) is special since even though it is a leaftype,
    # at runtime, it might be Type{Union{}} instead, so don't attempt inference of it
    t === typeof(Union{}) && return false
    t === Union{} && return true
    isa(t, TypeVar) && return false # TypeVars are identified by address, not equality
    iskindtype(typeof(t)) || return true # non-types are always compared by egal in the type system
    isconcretetype(t) && return true # these are also interned and pointer comparable
    if isa(t, DataType) && t.name !== Tuple.name && !isvarargtype(t) # invariant DataTypes
        return _all(hasuniquerep, t.parameters)
    end
    return false
end

"""
    isTypeDataType(@nospecialize t) -> Bool

For a type `t` test whether ∀S s.t. `isa(S, rewrap_unionall(Type{t}, ...))`,
we have `isa(S, DataType)`. In particular, if a statement is typed as `Type{t}`
(potentially wrapped in some `UnionAll`), then we are guaranteed that this statement
will be a `DataType` at runtime (and not e.g. a `Union` or `UnionAll` typeequal to it).
"""
function isTypeDataType(@nospecialize t)
    isa(t, DataType) || return false
    isType(t) && return false
    # Could be Union{} at runtime
    t === Core.TypeofBottom && return false
    if t.name === Tuple.name
        # If we have a Union parameter, could have been redistributed at runtime,
        # e.g. `Tuple{Union{Int, Float64}, Int}` is a DataType, but
        # `Union{Tuple{Int, Int}, Tuple{Float64, Int}}` is typeequal to it and
        # is not.
        return all(isTypeDataType, t.parameters)
    end
    return true
end

has_extended_info(@nospecialize x) = (!isa(x, Type) && !isvarargtype(x)) || isType(x)

# Subtyping currently intentionally answers certain queries incorrectly for kind types. For
# some of these queries, this check can be used to somewhat protect against making incorrect
# decisions based on incorrect subtyping. Note that this check, itself, is broken for
# certain combinations of `a` and `b` where one/both isa/are `Union`/`UnionAll` type(s)s.
isnotbrokensubtype(@nospecialize(a), @nospecialize(b)) = (!iskindtype(b) || !isType(a) || hasuniquerep(a.parameters[1]) || b <: a)

argtypes_to_type(argtypes::Array{Any,1}) = Tuple{anymap(@nospecialize(a) -> isvarargtype(a) ? a : widenconst(a), argtypes)...}

function isknownlength(t::DataType)
    isvatuple(t) || return true
    va = t.parameters[end]
    return isdefined(va, :N) && va.N isa Int
end

# Compute the minimum number of initialized fields for a particular datatype
# (therefore also a lower bound on the number of fields)
function datatype_min_ninitialized(t::DataType)
    isabstracttype(t) && return 0
    if t.name === _NAMEDTUPLE_NAME
        names, types = t.parameters[1], t.parameters[2]
        if names isa Tuple
            return length(names)
        end
        t = argument_datatype(types)
        t isa DataType || return 0
        t.name === Tuple.name || return 0
    end
    if t.name === Tuple.name
        n = length(t.parameters)
        n == 0 && return 0
        va = t.parameters[n]
        if isvarargtype(va)
            n -= 1
            if isdefined(va, :N)
                va = va.N
                if va isa Int
                    n += va
                end
            end
        end
        return n
    end
    return length(t.name.names) - t.name.n_uninitialized
end

has_concrete_subtype(d::DataType) = d.flags & 0x0020 == 0x0020 # n.b. often computed only after setting the type and layout fields

# determine whether x is a valid lattice element tag
# For example, Type{v} is not valid if v is a value
# Accepts TypeVars also, since it assumes the user will rewrap it correctly
function valid_as_lattice(@nospecialize(x))
    x === Bottom && false
    x isa TypeVar && return valid_as_lattice(x.ub)
    x isa UnionAll && (x = unwrap_unionall(x))
    if x isa Union
        # the Union constructor ensures this (and we'll recheck after
        # operations that might remove the Union itself)
        return true
    end
    if x isa DataType
        if isType(x)
            p = x.parameters[1]
            p isa Type || p isa TypeVar || return false
        end
        return true
    end
    return false
end

function valid_typeof_tparam(@nospecialize(t))
    if t === Symbol || t === Module || isbitstype(t)
        return true
    end
    isconcretetype(t) || return false
    if t <: NamedTuple
        t = t.parameters[2]::DataType
    end
    if t <: Tuple
        for p in t.parameters
            valid_typeof_tparam(p) || return false
        end
        return true
    end
    return false
end

# test if non-Type, non-TypeVar `x` can be used to parameterize a type
valid_tparam(@nospecialize(x)) = valid_typeof_tparam(typeof(x))

function compatible_vatuple(a::DataType, b::DataType)
    vaa = a.parameters[end]
    vab = a.parameters[end]
    if !(isvarargtype(vaa) && isvarargtype(vab))
        return isvarargtype(vaa) == isvarargtype(vab)
    end
    (isdefined(vaa, :N) == isdefined(vab, :N)) || return false
    !isdefined(vaa, :N) && return true
    return vaa.N === vab.N
end

# return an upper-bound on type `a` with type `b` removed
# such that `return <: a` && `Union{return, b} == Union{a, b}`
function typesubtract(@nospecialize(a), @nospecialize(b), max_union_splitting::Int)
    if a <: b && isnotbrokensubtype(a, b)
        return Bottom
    end
    ua = unwrap_unionall(a)
    if isa(ua, Union)
        uua = typesubtract(rewrap_unionall(ua.a, a), b, max_union_splitting)
        uub = typesubtract(rewrap_unionall(ua.b, a), b, max_union_splitting)
        return Union{valid_as_lattice(uua) ? uua : Union{},
                     valid_as_lattice(uub) ? uub : Union{}}
    elseif a isa DataType
        ub = unwrap_unionall(b)
        if ub isa DataType
            if a.name === ub.name === Tuple.name &&
                    length(a.parameters) == length(ub.parameters)
                if 1 < unionsplitcost(a.parameters) <= max_union_splitting
                    ta = switchtupleunion(a)
                    return typesubtract(Union{ta...}, b, 0)
                elseif b isa DataType
                    if !compatible_vatuple(a, b)
                        return a
                    end
                    # if exactly one element is not bottom after calling typesubtract
                    # then the result is all of the elements as normal except that one
                    notbottom = fill(false, length(a.parameters))
                    for i = 1:length(notbottom)
                        ap = unwrapva(a.parameters[i])
                        bp = unwrapva(b.parameters[i])
                        notbottom[i] = !(ap <: bp && isnotbrokensubtype(ap, bp))
                    end
                    let i = findfirst(notbottom)
                        if i !== nothing && findnext(notbottom, i + 1) === nothing
                            ta = collect(a.parameters)
                            ap = a.parameters[i]
                            bp = b.parameters[i]
                            (isvarargtype(ap) || isvarargtype(bp)) && return a
                            ta[i] = typesubtract(ap, bp, min(2, max_union_splitting))
                            return Tuple{ta...}
                        end
                    end
                end
            end
        end
    end
    return a # TODO: improve this bound?
end

hasintersect(@nospecialize(a), @nospecialize(b)) = typeintersect(a, b) !== Bottom

_typename(@nospecialize a) = Union{}
_typename(a::TypeVar) = Core.TypeName
function _typename(a::Union)
    ta = _typename(a.a)
    tb = _typename(a.b)
    ta === tb && return ta # same type-name
    (ta === Union{} || tb === Union{}) && return Union{} # threw an error
    (ta isa Const && tb isa Const) && return Union{} # will throw an error (different type-names)
    return Core.TypeName # uncertain result
end
_typename(union::UnionAll) = _typename(union.body)
_typename(a::DataType) = Const(a.name)

function tuple_tail_elem(@nospecialize(init), ct::Vector{Any})
    t = init
    for x in ct
        # FIXME: this is broken: it violates subtyping relations and creates invalid types with free typevars
        t = tmerge(t, unwraptv(unwrapva(x)))
    end
    return Vararg{widenconst(t)}
end

# Gives a cost function over the effort to switch a tuple-union representation
# as a cartesian product, relative to the size of the original representation.
# Thus, we count the longest element as being roughly invariant to being inside
# or outside of the Tuple/Union nesting, though somewhat more expensive to be
# outside than inside because the representation is larger (because and it
# informs the callee whether any splitting is possible).
function unionsplitcost(argtypes::Union{SimpleVector,Vector{Any}})
    nu = 1
    max = 2
    for ti in argtypes
        # TODO remove this to implement callsite refinement of MustAlias
        if isa(ti, MustAlias) && isa(widenconst(ti), Union)
            ti = widenconst(ti)
        end
        if isa(ti, Union)
            nti = unionlen(ti)
            if nti > max
                max, nti = nti, max
            end
            nu, ovf = Core.Intrinsics.checked_smul_int(nu, nti)
            ovf && return typemax(Int)
        end
    end
    return nu
end

# take a Tuple where one or more parameters are Unions
# and return an array such that those Unions are removed
# and `Union{return...} == ty`
function switchtupleunion(@nospecialize(ty))
    tparams = (unwrap_unionall(ty)::DataType).parameters
    return _switchtupleunion(Any[tparams...], length(tparams), [], ty)
end

switchtupleunion(argtypes::Vector{Any}) = _switchtupleunion(argtypes, length(argtypes), [], nothing)

function _switchtupleunion(t::Vector{Any}, i::Int, tunion::Vector{Any}, @nospecialize(origt))
    if i == 0
        if origt === nothing
            push!(tunion, copy(t))
        else
            tpl = rewrap_unionall(Tuple{t...}, origt)
            push!(tunion, tpl)
        end
    else
        origti = ti = t[i]
        # TODO remove this to implement callsite refinement of MustAlias
        if isa(ti, MustAlias) && isa(widenconst(ti), Union)
            ti = widenconst(ti)
        end
        if isa(ti, Union)
            for ty in uniontypes(ti::Union)
                t[i] = ty
                _switchtupleunion(t, i - 1, tunion, origt)
            end
            t[i] = origti
        else
            _switchtupleunion(t, i - 1, tunion, origt)
        end
    end
    return tunion
end

# unioncomplexity estimates the number of calls to `tmerge` to obtain the given type by
# counting the Union instances, taking also into account those hidden in a Tuple or UnionAll
unioncomplexity(@nospecialize x) = _unioncomplexity(x)::Int
function _unioncomplexity(@nospecialize x)
    if isa(x, DataType)
        x.name === Tuple.name || isvarargtype(x) || return 0
        c = 0
        for ti in x.parameters
            c = max(c, unioncomplexity(ti))
        end
        return c
    elseif isa(x, Union)
        return unioncomplexity(x.a) + unioncomplexity(x.b) + 1
    elseif isa(x, UnionAll)
        return max(unioncomplexity(x.body), unioncomplexity(x.var.ub))
    elseif isa(x, TypeofVararg)
        return isdefined(x, :T) ? unioncomplexity(x.T) : 0
    else
        return 0
    end
end

# convert a Union of Tuple types to a Tuple of Unions
function unswitchtupleunion(u::Union)
    ts = uniontypes(u)
    n = -1
    for t in ts
        if t isa DataType && t.name === Tuple.name && length(t.parameters) != 0 && !isvarargtype(t.parameters[end])
            if n == -1
                n = length(t.parameters)
            elseif n != length(t.parameters)
                return u
            end
        else
            return u
        end
    end
    Tuple{Any[ Union{Any[(t::DataType).parameters[i] for t in ts]...} for i in 1:n ]...}
end

function unwraptv_ub(@nospecialize t)
    while isa(t, TypeVar)
        t = t.ub
    end
    return t
end
function unwraptv_lb(@nospecialize t)
    while isa(t, TypeVar)
        t = t.lb
    end
    return t
end
const unwraptv = unwraptv_ub

# this query is specially written for `adjust_effects` and returns true if a value of this type
# never involves inconsistency of mutable objects that are allocated somewhere within a call graph
is_consistent_argtype(@nospecialize ty) =
    is_consistent_type(widenconst(ignorelimited(ty)))
is_consistent_type(@nospecialize ty) = isidentityfree(ty)

is_immutable_argtype(@nospecialize ty) = is_immutable_type(widenconst(ignorelimited(ty)))
is_immutable_type(@nospecialize ty) = _is_immutable_type(unwrap_unionall(ty))
function _is_immutable_type(@nospecialize ty)
    if isa(ty, Union)
        return _is_immutable_type(ty.a) && _is_immutable_type(ty.b)
    end
    return !isabstracttype(ty) && !ismutabletype(ty)
end

is_mutation_free_argtype(@nospecialize argtype) =
    is_mutation_free_type(widenconst(ignorelimited(argtype)))
is_mutation_free_type(@nospecialize ty) = ismutationfree(ty)

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	#####################
4	# lattice utilities #
5	#####################
6
7	# true if Type{T} is inlineable as constant T
8	# requires that T is a singleton, s.t. T == S implies T === S
9	isconstType(@nospecialize t) = isType(t) && hasuniquerep(t.parameters[1])	78,693,728✔
10
11	# test whether type T has a unique representation, s.t. T == S implies T === S
12	function hasuniquerep(@nospecialize t)	284,831✔
13	# typeof(Bottom) is special since even though it is a leaftype,
14	# at runtime, it might be Type{Union{}} instead, so don't attempt inference of it
15	t === typeof(Union{}) && return false	7,028,466✔
16	t === Union{} && return true	7,028,394✔
17	isa(t, TypeVar) && return false # TypeVars are identified by address, not equality	4,910,068✔
18	iskindtype(typeof(t)) \|\| return true # non-types are always compared by egal in the type system	7,015,082✔
19	isconcretetype(t) && return true # these are also interned and pointer comparable	8,468,718✔
20	if isa(t, DataType) && t.name !== Tuple.name && !isvarargtype(t) # invariant DataTypes	2,106,822✔
21	return _all(hasuniquerep, t.parameters)	511,595✔
22	end
23	return false	1,595,227✔
24	end
25
26	"""
27	isTypeDataType(@nospecialize t) -> Bool
28
29	For a type `t` test whether ∀S s.t. `isa(S, rewrap_unionall(Type{t}, ...))`,
30	we have `isa(S, DataType)`. In particular, if a statement is typed as `Type{t}`
31	(potentially wrapped in some `UnionAll`), then we are guaranteed that this statement
32	will be a `DataType` at runtime (and not e.g. a `Union` or `UnionAll` typeequal to it).
33	"""
34	function isTypeDataType(@nospecialize t)	2,577✔
35	isa(t, DataType) \|\| return false	25,052✔
36	isType(t) && return false	22,352✔
37	# Could be Union{} at runtime
38	t === Core.TypeofBottom && return false	22,336✔
39	if t.name === Tuple.name	22,336✔
40	# If we have a Union parameter, could have been redistributed at runtime,
41	# e.g. `Tuple{Union{Int, Float64}, Int}` is a DataType, but
42	# `Union{Tuple{Int, Int}, Tuple{Float64, Int}}` is typeequal to it and
43	# is not.
44	return all(isTypeDataType, t.parameters)	526✔
45	end
46	return true	21,810✔
47	end
48
49	has_extended_info(@nospecialize x) = (!isa(x, Type) && !isvarargtype(x)) \|\| isType(x)	2,787,212✔
50
51	# Subtyping currently intentionally answers certain queries incorrectly for kind types. For
52	# some of these queries, this check can be used to somewhat protect against making incorrect
53	# decisions based on incorrect subtyping. Note that this check, itself, is broken for
54	# certain combinations of `a` and `b` where one/both isa/are `Union`/`UnionAll` type(s)s.
55	isnotbrokensubtype(@nospecialize(a), @nospecialize(b)) = (!iskindtype(b) \|\| !isType(a) \|\| hasuniquerep(a.parameters[1]) \|\| b <: a)	1,054,013✔
56
57	argtypes_to_type(argtypes::Array{Any,1}) = Tuple{anymap(@nospecialize(a) -> isvarargtype(a) ? a : widenconst(a), argtypes)...}	148,259,301✔
58
59	function isknownlength(t::DataType)	×
60	isvatuple(t) \|\| return true	24✔
61	va = t.parameters[end]	×
62	return isdefined(va, :N) && va.N isa Int	×
63	end
64
65	# Compute the minimum number of initialized fields for a particular datatype
66	# (therefore also a lower bound on the number of fields)
67	function datatype_min_ninitialized(t::DataType)	10,050,613✔
68	isabstracttype(t) && return 0	10,050,613✔
69	if t.name === _NAMEDTUPLE_NAME	10,050,613✔
70	names, types = t.parameters[1], t.parameters[2]	136,023✔
71	if names isa Tuple	136,023✔
72	return length(names)	136,013✔
73	end
74	t = argument_datatype(types)	10✔
75	t isa DataType \|\| return 0	10✔
76	t.name === Tuple.name \|\| return 0	10✔
77	end
78	if t.name === Tuple.name	9,914,600✔
79	n = length(t.parameters)	4,986,609✔
80	n == 0 && return 0	4,986,609✔
81	va = t.parameters[n]	4,986,609✔
82	if isvarargtype(va)	4,986,609✔
83	n -= 1	3✔
84	if isdefined(va, :N)	3✔
85	va = va.N	×
86	if va isa Int	×
87	n += va	×
88	end
89	end
90	end
91	return n	4,986,609✔
92	end
93	return length(t.name.names) - t.name.n_uninitialized	4,927,991✔
94	end
95
96	has_concrete_subtype(d::DataType) = d.flags & 0x0020 == 0x0020 # n.b. often computed only after setting the type and layout fields	2,468,594✔
97
98	# determine whether x is a valid lattice element tag
99	# For example, Type{v} is not valid if v is a value
100	# Accepts TypeVars also, since it assumes the user will rewrap it correctly
101	function valid_as_lattice(@nospecialize(x))	246,868✔
102	x === Bottom && false	9,400,869✔
103	x isa TypeVar && return valid_as_lattice(x.ub)	9,400,869✔
104	x isa UnionAll && (x = unwrap_unionall(x))	9,154,156✔
105	if x isa Union	9,154,156✔
106	# the Union constructor ensures this (and we'll recheck after
107	# operations that might remove the Union itself)
108	return true	40,191✔
109	end
110	if x isa DataType	9,113,965✔
111	if isType(x)	8,301,004✔
112	p = x.parameters[1]	86,832✔
113	p isa Type \|\| p isa TypeVar \|\| return false	162,677✔
114	end
115	return true	8,301,004✔
116	end
117	return false	812,961✔
118	end
119
120	function valid_typeof_tparam(@nospecialize(t))	502,604✔
121	if t === Symbol \|\| t === Module \|\| isbitstype(t)	804,806✔
122	return true	396,504✔
123	end
124	isconcretetype(t) \|\| return false	106,786✔
125	if t <: NamedTuple	105,414✔
126	t = t.parameters[2]::DataType	×
127	end
128	if t <: Tuple	105,414✔
129	for p in t.parameters	204,300✔
130	valid_typeof_tparam(p) \|\| return false	200,092✔
131	end	298,028✔
132	return true	102,148✔
133	end
134	return false	3,264✔
135	end
136
137	# test if non-Type, non-TypeVar `x` can be used to parameterize a type
138	valid_tparam(@nospecialize(x)) = valid_typeof_tparam(typeof(x))	266,488✔
139
140	function compatible_vatuple(a::DataType, b::DataType)	×
141	vaa = a.parameters[end]	29✔
142	vab = a.parameters[end]	29✔
143	if !(isvarargtype(vaa) && isvarargtype(vab))	29✔
144	return isvarargtype(vaa) == isvarargtype(vab)	29✔
145	end
146	(isdefined(vaa, :N) == isdefined(vab, :N)) \|\| return false	×
147	!isdefined(vaa, :N) && return true	×
148	return vaa.N === vab.N	×
149	end
150
151	# return an upper-bound on type `a` with type `b` removed
152	# such that `return <: a` && `Union{return, b} == Union{a, b}`
153	function typesubtract(@nospecialize(a), @nospecialize(b), max_union_splitting::Int)	2,531,069✔
154	if a <: b && isnotbrokensubtype(a, b)	2,531,513✔
155	return Bottom	810,730✔
156	end
157	ua = unwrap_unionall(a)	1,723,763✔
158	if isa(ua, Union)	1,720,339✔
159	uua = typesubtract(rewrap_unionall(ua.a, a), b, max_union_splitting)	813,567✔
160	uub = typesubtract(rewrap_unionall(ua.b, a), b, max_union_splitting)	813,567✔
161	return Union{valid_as_lattice(uua) ? uua : Union{},	813,567✔
162	valid_as_lattice(uub) ? uub : Union{}}
163	elseif a isa DataType	906,772✔
164	ub = unwrap_unionall(b)	917,336✔
165	if ub isa DataType	903,913✔
166	if a.name === ub.name === Tuple.name &&	903,562✔
167	length(a.parameters) == length(ub.parameters)
168	if 1 < unionsplitcost(a.parameters) <= max_union_splitting	96✔
169	ta = switchtupleunion(a)	8✔
170	return typesubtract(Union{ta...}, b, 0)	8✔
171	elseif b isa DataType	88✔
172	if !compatible_vatuple(a, b)	29✔
173	return a	×
174	end
175	# if exactly one element is not bottom after calling typesubtract
176	# then the result is all of the elements as normal except that one
177	notbottom = fill(false, length(a.parameters))	59✔
178	for i = 1:length(notbottom)	58✔
179	ap = unwrapva(a.parameters[i])	59✔
180	bp = unwrapva(b.parameters[i])	59✔
181	notbottom[i] = !(ap <: bp && isnotbrokensubtype(ap, bp))	59✔
182	end	89✔
183	let i = findfirst(notbottom)	68✔
184	if i !== nothing && findnext(notbottom, i + 1) === nothing	49✔
185	ta = collect(a.parameters)	19✔
186	ap = a.parameters[i]	19✔
187	bp = b.parameters[i]	19✔
188	(isvarargtype(ap) \|\| isvarargtype(bp)) && return a	19✔
189	ta[i] = typesubtract(ap, bp, min(2, max_union_splitting))	19✔
190	return Tuple{ta...}	19✔
191	end
192	end
193	end
194	end
195	end
196	end
197	return a # TODO: improve this bound?	906,745✔
198	end
199
200	hasintersect(@nospecialize(a), @nospecialize(b)) = typeintersect(a, b) !== Bottom	29,034,842✔
201
202	_typename(@nospecialize a) = Union{}	×
203	_typename(a::TypeVar) = Core.TypeName	5✔
204	function _typename(a::Union)	×
205	ta = _typename(a.a)	×
206	tb = _typename(a.b)	×
207	ta === tb && return ta # same type-name	×
208	(ta === Union{} \|\| tb === Union{}) && return Union{} # threw an error	×
209	(ta isa Const && tb isa Const) && return Union{} # will throw an error (different type-names)	×
210	return Core.TypeName # uncertain result	×
211	end
212	_typename(union::UnionAll) = _typename(union.body)	55✔
213	_typename(a::DataType) = Const(a.name)	87,692✔
214
215	function tuple_tail_elem(@nospecialize(init), ct::Vector{Any})	26,276✔
216	t = init	×
217	for x in ct	26,499✔
218	# FIXME: this is broken: it violates subtyping relations and creates invalid types with free typevars
219	t = tmerge(t, unwraptv(unwrapva(x)))	27,107✔
220	end	53,160✔
221	return Vararg{widenconst(t)}	26,276✔
222	end
223
224	# Gives a cost function over the effort to switch a tuple-union representation
225	# as a cartesian product, relative to the size of the original representation.
226	# Thus, we count the longest element as being roughly invariant to being inside
227	# or outside of the Tuple/Union nesting, though somewhat more expensive to be
228	# outside than inside because the representation is larger (because and it
229	# informs the callee whether any splitting is possible).
230	function unionsplitcost(argtypes::Union{SimpleVector,Vector{Any}})	21,433,140✔
231	nu = 1	×
232	max = 2	×
233	for ti in argtypes	21,433,236✔
234	# TODO remove this to implement callsite refinement of MustAlias
235	if isa(ti, MustAlias) && isa(widenconst(ti), Union)	61,253,971✔
236	ti = widenconst(ti)	×
237	end
238	if isa(ti, Union)	61,253,971✔
239	nti = unionlen(ti)	325,957✔
240	if nti > max	187,290✔
241	max, nti = nti, max	×
242	end
243	nu, ovf = Core.Intrinsics.checked_smul_int(nu, nti)	187,290✔
244	ovf && return typemax(Int)	187,290✔
245	end
246	end	82,687,053✔
247	return nu	21,433,140✔
248	end
249
250	# take a Tuple where one or more parameters are Unions
251	# and return an array such that those Unions are removed
252	# and `Union{return...} == ty`
253	function switchtupleunion(@nospecialize(ty))	×
254	tparams = (unwrap_unionall(ty)::DataType).parameters	8✔
255	return _switchtupleunion(Any[tparams...], length(tparams), [], ty)	8✔
256	end
257
258	switchtupleunion(argtypes::Vector{Any}) = _switchtupleunion(argtypes, length(argtypes), [], nothing)	172,796✔
259
260	function _switchtupleunion(t::Vector{Any}, i::Int, tunion::Vector{Any}, @nospecialize(origt))	1,198,966✔
261	if i == 0	1,198,966✔
262	if origt === nothing	407,208✔
263	push!(tunion, copy(t))	407,192✔
264	else
265	tpl = rewrap_unionall(Tuple{t...}, origt)	16✔
266	push!(tunion, tpl)	407,224✔
267	end
268	else
269	origti = ti = t[i]	791,758✔
270	# TODO remove this to implement callsite refinement of MustAlias
271	if isa(ti, MustAlias) && isa(widenconst(ti), Union)	791,758✔
272	ti = widenconst(ti)	×
273	end
274	if isa(ti, Union)	791,758✔
275	for ty in uniontypes(ti::Union)	183,568✔
276	t[i] = ty	417,972✔
277	_switchtupleunion(t, i - 1, tunion, origt)	417,972✔
278	end	601,540✔
279	t[i] = origti	183,568✔
280	else
281	_switchtupleunion(t, i - 1, tunion, origt)	608,190✔
282	end
283	end
284	return tunion	1,198,966✔
285	end
286
287	# unioncomplexity estimates the number of calls to `tmerge` to obtain the given type by
288	# counting the Union instances, taking also into account those hidden in a Tuple or UnionAll
289	unioncomplexity(@nospecialize x) = _unioncomplexity(x)::Int	5,693,037✔
290	function _unioncomplexity(@nospecialize x)	5,693,037✔
291	if isa(x, DataType)	5,693,037✔
292	x.name === Tuple.name \|\| isvarargtype(x) \|\| return 0	8,607,714✔
293	c = 0	×
294	for ti in x.parameters	1,109,206✔
295	c = max(c, unioncomplexity(ti))	952,220✔
296	end	1,352,054✔
297	return c	556,820✔
298	elseif isa(x, Union)	1,110,770✔
299	return unioncomplexity(x.a) + unioncomplexity(x.b) + 1	684,120✔
300	elseif isa(x, UnionAll)	426,650✔
301	return max(unioncomplexity(x.body), unioncomplexity(x.var.ub))	277,561✔
302	elseif isa(x, TypeofVararg)	149,089✔
303	return isdefined(x, :T) ? unioncomplexity(x.T) : 0	148,917✔
304	else
305	return 0	172✔
306	end
307	end
308
309	# convert a Union of Tuple types to a Tuple of Unions
310	function unswitchtupleunion(u::Union)	9,237✔
311	ts = uniontypes(u)	9,237✔
312	n = -1	×
313	for t in ts	9,237✔
314	if t isa DataType && t.name === Tuple.name && length(t.parameters) != 0 && !isvarargtype(t.parameters[end])	18,530✔
315	if n == -1	18,530✔
316	n = length(t.parameters)	9,237✔
317	elseif n != length(t.parameters)	9,293✔
318	return u	18,530✔
319	end
320	else
321	return u	×
322	end
323	end	27,767✔
324	Tuple{Any[ Union{Any[(t::DataType).parameters[i] for t in ts]...} for i in 1:n ]...}	9,237✔
325	end
326
327	function unwraptv_ub(@nospecialize t)	×
328	while isa(t, TypeVar)	59,801,172✔
329	t = t.ub	155,783✔
330	end	155,783✔
331	return t	59,645,389✔
332	end
333	function unwraptv_lb(@nospecialize t)	×
334	while isa(t, TypeVar)	287,492✔
335	t = t.lb	143,746✔
336	end	143,746✔
337	return t	143,746✔
338	end
339	const unwraptv = unwraptv_ub
340
341	# this query is specially written for `adjust_effects` and returns true if a value of this type
342	# never involves inconsistency of mutable objects that are allocated somewhere within a call graph
343	is_consistent_argtype(@nospecialize ty) =	115,143✔
344	is_consistent_type(widenconst(ignorelimited(ty)))
345	is_consistent_type(@nospecialize ty) = isidentityfree(ty)	120,887✔
346
347	is_immutable_argtype(@nospecialize ty) = is_immutable_type(widenconst(ignorelimited(ty)))	8,416,146✔
348	is_immutable_type(@nospecialize ty) = _is_immutable_type(unwrap_unionall(ty))	8,580,172✔
349	function _is_immutable_type(@nospecialize ty)	8,490,980✔
350	if isa(ty, Union)	8,490,980✔
351	return _is_immutable_type(ty.a) && _is_immutable_type(ty.b)	37,423✔
352	end
353	return !isabstracttype(ty) && !ismutabletype(ty)	8,456,295✔
354	end
355
356	is_mutation_free_argtype(@nospecialize argtype) =	86,304,657✔
357	is_mutation_free_type(widenconst(ignorelimited(argtype)))
358	is_mutation_free_type(@nospecialize ty) = ismutationfree(ty)	51,077,991✔

JuliaLang / julia / #37474

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous