| Line | Exclusive | Inclusive | Code |
|---|---|---|---|
| 1 | # This file is a part of Julia. License is MIT: https://julialang.org/license | ||
| 2 | |||
| 3 | ############# | ||
| 4 | # constants # | ||
| 5 | ############# | ||
| 6 | |||
| 7 | const CoreNumType = Union{Int32, Int64, Float32, Float64} | ||
| 8 | |||
| 9 | const _REF_NAME = Ref.body.name | ||
| 10 | |||
| 11 | ######### | ||
| 12 | # logic # | ||
| 13 | ######### | ||
| 14 | |||
| 15 | # see if the inference result might affect the final answer | ||
| 16 | call_result_unused(frame::InferenceState, pc::LineNum=frame.currpc) = | ||
| 17 | isexpr(frame.src.code[frame.currpc], :call) && isempty(frame.ssavalue_uses[pc]) | ||
| 18 | |||
| 19 |
2 (5.41%) samples spent in abstract_call_gf_by_type
function abstract_call_gf_by_type(@nospecialize(f), argtypes::Vector{Any}, @nospecialize(atype), sv::InferenceState)
0 (ex.), 2 (100.00%) (incl.) when called from abstract_call line 829 |
||
| 20 | atype_params = unwrap_unionall(atype).parameters | ||
| 21 | ft = unwrap_unionall(atype_params[1]) # TODO: ccall jl_first_argument_datatype here | ||
| 22 | isa(ft, DataType) || return Any # the function being called is unknown. can't properly handle this backedge right now | ||
| 23 | ftname = ft.name | ||
| 24 | isdefined(ftname, :mt) || return Any # not callable. should be Bottom, but can't track this backedge right now | ||
| 25 | if ftname === _TYPE_NAME | ||
| 26 | tname = ft.parameters[1] | ||
| 27 | if isa(tname, TypeVar) | ||
| 28 | tname = tname.ub | ||
| 29 | end | ||
| 30 | tname = unwrap_unionall(tname) | ||
| 31 | if !isa(tname, DataType) | ||
| 32 | # can't track the backedge to the ctor right now | ||
| 33 | # for things like Union | ||
| 34 | return Any | ||
| 35 | end | ||
| 36 | end | ||
| 37 | min_valid = UInt[typemin(UInt)] | ||
| 38 | max_valid = UInt[typemax(UInt)] | ||
| 39 | splitunions = 1 < countunionsplit(atype_params) <= sv.params.MAX_UNION_SPLITTING | ||
| 40 | if splitunions | ||
| 41 | splitsigs = switchtupleunion(atype) | ||
| 42 | applicable = Any[] | ||
| 43 | for sig_n in splitsigs | ||
| 44 | xapplicable = _methods_by_ftype(sig_n, sv.params.MAX_METHODS, sv.params.world, min_valid, max_valid) | ||
| 45 | xapplicable === false && return Any | ||
| 46 | append!(applicable, xapplicable) | ||
| 47 | end | ||
| 48 | else | ||
| 49 | 1 (2.70%) |
1 (100.00%)
samples spent calling
_methods_by_ftype
applicable = _methods_by_ftype(atype, sv.params.MAX_METHODS, sv.params.world, min_valid, max_valid)
|
|
| 50 | if applicable === false | ||
| 51 | # this means too many methods matched | ||
| 52 | # (assume this will always be true, so we don't compute / update valid age in this case) | ||
| 53 | return Any | ||
| 54 | end | ||
| 55 | end | ||
| 56 | update_valid_age!(min_valid[1], max_valid[1], sv) | ||
| 57 | applicable = applicable::Array{Any,1} | ||
| 58 | napplicable = length(applicable) | ||
| 59 | rettype = Bottom | ||
| 60 | edgecycle = false | ||
| 61 | edges = Any[] | ||
| 62 | nonbot = 0 # the index of the only non-Bottom inference result if > 0 | ||
| 63 | seen = 0 # number of signatures actually inferred | ||
| 64 | for i in 1:napplicable | ||
| 65 | match = applicable[i]::SimpleVector | ||
| 66 | method = match[3]::Method | ||
| 67 | sig = match[1] | ||
| 68 | sigtuple = unwrap_unionall(sig)::DataType | ||
| 69 | splitunions = false | ||
| 70 | this_rt = Bottom | ||
| 71 | # TODO: splitunions = 1 < countunionsplit(sigtuple.parameters) * napplicable <= sv.params.MAX_UNION_SPLITTING | ||
| 72 | # currently this triggers a bug in inference recursion detection | ||
| 73 | if splitunions | ||
| 74 | splitsigs = switchtupleunion(sig) | ||
| 75 | for sig_n in splitsigs | ||
| 76 | rt, edgecycle1, edge = abstract_call_method(method, sig_n, svec(), sv) | ||
| 77 | if edge !== nothing | ||
| 78 | push!(edges, edge) | ||
| 79 | end | ||
| 80 | edgecycle |= edgecycle1::Bool | ||
| 81 | this_rt = tmerge(this_rt, rt) | ||
| 82 | this_rt === Any && break | ||
| 83 | end | ||
| 84 | else | ||
| 85 | this_rt, edgecycle, edge = abstract_call_method(method, sig, match[2]::SimpleVector, sv) | ||
| 86 | if edge !== nothing | ||
| 87 | push!(edges, edge) | ||
| 88 | end | ||
| 89 | end | ||
| 90 | if this_rt !== Bottom | ||
| 91 | if nonbot === 0 | ||
| 92 | nonbot = i | ||
| 93 | else | ||
| 94 | nonbot = -1 | ||
| 95 | end | ||
| 96 | end | ||
| 97 | seen += 1 | ||
| 98 | rettype = tmerge(rettype, this_rt) | ||
| 99 | rettype === Any && break | ||
| 100 | end | ||
| 101 | # try constant propagation if only 1 method is inferred to non-Bottom | ||
| 102 | # this is in preparation for inlining, or improving the return result | ||
| 103 | if nonbot > 0 && seen == napplicable && !edgecycle && isa(rettype, Type) && sv.params.ipo_constant_propagation | ||
| 104 | # if there's a possibility we could constant-propagate a better result | ||
| 105 | # (hopefully without doing too much work), try to do that now | ||
| 106 | # TODO: it feels like this could be better integrated into abstract_call_method / typeinf_edge | ||
| 107 | 3 (8.11%) |
2 (66.67%)
samples spent calling
abstract_call_method_with_const_args
const_rettype = abstract_call_method_with_const_args(f, argtypes, applicable[nonbot]::SimpleVector, sv)
|
|
| 108 | if const_rettype ⊑ rettype | ||
| 109 | # use the better result, if it's a refinement of rettype | ||
| 110 | rettype = const_rettype | ||
| 111 | end | ||
| 112 | end | ||
| 113 | if call_result_unused(sv) && !(rettype === Bottom) | ||
| 114 | # We're mainly only here because the optimizer might want this code, | ||
| 115 | # but we ourselves locally don't typically care about it locally | ||
| 116 | # (beyond checking if it always throws). | ||
| 117 | # So avoid adding an edge, since we don't want to bother attempting | ||
| 118 | # to improve our result even if it does change (to always throw), | ||
| 119 | # and avoid keeping track of a more complex result type. | ||
| 120 | rettype = Any | ||
| 121 | end | ||
| 122 | if !(rettype === Any) # adding a new method couldn't refine (widen) this type | ||
| 123 | for edge in edges | ||
| 124 | add_backedge!(edge::MethodInstance, sv) | ||
| 125 | end | ||
| 126 | fullmatch = false | ||
| 127 | for i in napplicable:-1:1 | ||
| 128 | match = applicable[i]::SimpleVector | ||
| 129 | method = match[3]::Method | ||
| 130 | if atype <: method.sig | ||
| 131 | fullmatch = true | ||
| 132 | break | ||
| 133 | end | ||
| 134 | end | ||
| 135 | if !fullmatch | ||
| 136 | # also need an edge to the method table in case something gets | ||
| 137 | # added that did not intersect with any existing method | ||
| 138 | add_mt_backedge!(ftname.mt, atype, sv) | ||
| 139 | end | ||
| 140 | end | ||
| 141 | #print("=> ", rettype, "\n") | ||
| 142 | return rettype | ||
| 143 | end | ||
| 144 | |||
| 145 |
2 (5.41%) samples spent in abstract_call_method_with_const_args
function abstract_call_method_with_const_args(@nospecialize(f), argtypes::Vector{Any}, match::SimpleVector, sv::InferenceState)
0 (ex.), 2 (100.00%) (incl.) when called from abstract_call_gf_by_type line 107 |
||
| 146 | method = match[3]::Method | ||
| 147 | nargs::Int = method.nargs | ||
| 148 | method.isva && (nargs -= 1) | ||
| 149 | length(argtypes) >= nargs || return Any | ||
| 150 | haveconst = false | ||
| 151 | for a in argtypes | ||
| 152 | a = maybe_widen_conditional(a) | ||
| 153 | if isa(a, Const) && !isdefined(typeof(a.val), :instance) && !(isa(a.val, Type) && issingletontype(a.val)) | ||
| 154 | # have new information from argtypes that wasn't available from the signature | ||
| 155 | if isa(a.val, Symbol) || isa(a.val, Type) || (!isa(a.val, String) && isimmutable(a.val)) | ||
| 156 | # don't consider mutable values or Strings useful constants | ||
| 157 | haveconst = true | ||
| 158 | break | ||
| 159 | end | ||
| 160 | end | ||
| 161 | end | ||
| 162 | haveconst || return Any | ||
| 163 | sig = match[1] | ||
| 164 | sparams = match[2]::SimpleVector | ||
| 165 | code = code_for_method(method, sig, sparams, sv.params.world) | ||
| 166 | code === nothing && return Any | ||
| 167 | code = code::MethodInstance | ||
| 168 | # decide if it's likely to be worthwhile | ||
| 169 | declared_inline = isdefined(method, :source) && ccall(:jl_ast_flag_inlineable, Bool, (Any,), method.source) | ||
| 170 | cache_inlineable = declared_inline | ||
| 171 | if isdefined(code, :inferred) && !cache_inlineable | ||
| 172 | cache_inf = code.inferred | ||
| 173 | if !(cache_inf === nothing) | ||
| 174 | cache_src_inferred = ccall(:jl_ast_flag_inferred, Bool, (Any,), cache_inf) | ||
| 175 | cache_src_inlineable = ccall(:jl_ast_flag_inlineable, Bool, (Any,), cache_inf) | ||
| 176 | cache_inlineable = cache_src_inferred && cache_src_inlineable | ||
| 177 | end | ||
| 178 | end | ||
| 179 | if !cache_inlineable && !sv.params.aggressive_constant_propagation | ||
| 180 | tm = _topmod(sv) | ||
| 181 | if !istopfunction(f, :getproperty) && !istopfunction(f, :setproperty!) | ||
| 182 | # in this case, see if all of the arguments are constants | ||
| 183 | for a in argtypes | ||
| 184 | a = maybe_widen_conditional(a) | ||
| 185 | if !isa(a, Const) && !isconstType(a) | ||
| 186 | return Any | ||
| 187 | end | ||
| 188 | end | ||
| 189 | end | ||
| 190 | end | ||
| 191 | inf_result = cache_lookup(code, argtypes, sv.params.cache) | ||
| 192 | if inf_result === nothing | ||
| 193 | inf_result = InferenceResult(code) | ||
| 194 | atypes = get_argtypes(inf_result) | ||
| 195 | if method.isva | ||
| 196 | vargs = argtypes[(nargs + 1):end] | ||
| 197 | for i in 1:length(vargs) | ||
| 198 | a = maybe_widen_conditional(vargs[i]) | ||
| 199 | if i > length(inf_result.vargs) | ||
| 200 | push!(inf_result.vargs, a) | ||
| 201 | elseif a isa Const | ||
| 202 | inf_result.vargs[i] = a | ||
| 203 | end | ||
| 204 | end | ||
| 205 | end | ||
| 206 | for i in 1:nargs | ||
| 207 | a = maybe_widen_conditional(argtypes[i]) | ||
| 208 | if a isa Const | ||
| 209 | atypes[i] = a # inject Const argtypes into inference | ||
| 210 | end | ||
| 211 | end | ||
| 212 | frame = InferenceState(inf_result, #=cache=#false, sv.params) | ||
| 213 | frame.limited = true | ||
| 214 | frame.parent = sv | ||
| 215 | push!(sv.params.cache, inf_result) | ||
| 216 | 3 (8.11%) |
2 (66.67%)
samples spent calling
typeinf
typeinf(frame) || return Any
|
|
| 217 | end | ||
| 218 | result = inf_result.result | ||
| 219 | isa(result, InferenceState) && return Any # TODO: is this recursive constant inference? | ||
| 220 | add_backedge!(inf_result.linfo, sv) | ||
| 221 | return result | ||
| 222 | end | ||
| 223 | |||
| 224 | function abstract_call_method(method::Method, @nospecialize(sig), sparams::SimpleVector, sv::InferenceState) | ||
| 225 | if method.name === :depwarn && isdefined(Main, :Base) && method.module === Main.Base | ||
| 226 | return Any, false, nothing | ||
| 227 | end | ||
| 228 | topmost = nothing | ||
| 229 | # Limit argument type tuple growth of functions: | ||
| 230 | # look through the parents list to see if there's a call to the same method | ||
| 231 | # and from the same method. | ||
| 232 | # Returns the topmost occurrence of that repeated edge. | ||
| 233 | cyclei = 0 | ||
| 234 | infstate = sv | ||
| 235 | edgecycle = false | ||
| 236 | # The `method_for_inference_heuristics` will expand the given method's generator if | ||
| 237 | # necessary in order to retrieve this field from the generated `CodeInfo`, if it exists. | ||
| 238 | # The other `CodeInfo`s we inspect will already have this field inflated, so we just | ||
| 239 | # access it directly instead (to avoid regeneration). | ||
| 240 | method2 = method_for_inference_heuristics(method, sig, sparams, sv.params.world) # Union{Method, Nothing} | ||
| 241 | sv_method2 = sv.src.method_for_inference_limit_heuristics # limit only if user token match | ||
| 242 | sv_method2 isa Method || (sv_method2 = nothing) # Union{Method, Nothing} | ||
| 243 | while !(infstate === nothing) | ||
| 244 | infstate = infstate::InferenceState | ||
| 245 | if method === infstate.linfo.def | ||
| 246 | if infstate.linfo.specTypes == sig | ||
| 247 | # avoid widening when detecting self-recursion | ||
| 248 | # TODO: merge call cycle and return right away | ||
| 249 | if call_result_unused(sv) | ||
| 250 | # since we don't use the result (typically), | ||
| 251 | # we have a self-cycle in the call-graph, but not in the inference graph (typically): | ||
| 252 | # break this edge now (before we record it) by returning early | ||
| 253 | # (non-typically, this means that we lose the ability to detect a guaranteed StackOverflow in some cases) | ||
| 254 | return Any, false, nothing | ||
| 255 | end | ||
| 256 | topmost = nothing | ||
| 257 | edgecycle = true | ||
| 258 | break | ||
| 259 | end | ||
| 260 | inf_method2 = infstate.src.method_for_inference_limit_heuristics # limit only if user token match | ||
| 261 | inf_method2 isa Method || (inf_method2 = nothing) # Union{Method, Nothing} | ||
| 262 | if topmost === nothing && method2 === inf_method2 | ||
| 263 | # inspect the parent of this edge, | ||
| 264 | # to see if they are the same Method as sv | ||
| 265 | # in which case we'll need to ensure it is convergent | ||
| 266 | # otherwise, we don't | ||
| 267 | for parent in infstate.callers_in_cycle | ||
| 268 | # check in the cycle list first | ||
| 269 | # all items in here are mutual parents of all others | ||
| 270 | parent_method2 = parent.src.method_for_inference_limit_heuristics # limit only if user token match | ||
| 271 | parent_method2 isa Method || (parent_method2 = nothing) # Union{Method, Nothing} | ||
| 272 | if parent.linfo.def === sv.linfo.def && sv_method2 === parent_method2 | ||
| 273 | topmost = infstate | ||
| 274 | edgecycle = true | ||
| 275 | break | ||
| 276 | end | ||
| 277 | end | ||
| 278 | let parent = infstate.parent | ||
| 279 | # then check the parent link | ||
| 280 | if topmost === nothing && parent !== nothing | ||
| 281 | parent = parent::InferenceState | ||
| 282 | parent_method2 = parent.src.method_for_inference_limit_heuristics # limit only if user token match | ||
| 283 | parent_method2 isa Method || (parent_method2 = nothing) # Union{Method, Nothing} | ||
| 284 | if (parent.cached || parent.limited) && parent.linfo.def === sv.linfo.def && sv_method2 === parent_method2 | ||
| 285 | topmost = infstate | ||
| 286 | edgecycle = true | ||
| 287 | end | ||
| 288 | end | ||
| 289 | end | ||
| 290 | end | ||
| 291 | end | ||
| 292 | # iterate through the cycle before walking to the parent | ||
| 293 | if cyclei < length(infstate.callers_in_cycle) | ||
| 294 | cyclei += 1 | ||
| 295 | infstate = infstate.callers_in_cycle[cyclei] | ||
| 296 | else | ||
| 297 | cyclei = 0 | ||
| 298 | infstate = infstate.parent | ||
| 299 | end | ||
| 300 | end | ||
| 301 | |||
| 302 | if !(topmost === nothing) | ||
| 303 | topmost = topmost::InferenceState | ||
| 304 | sigtuple = unwrap_unionall(sig)::DataType | ||
| 305 | msig = unwrap_unionall(method.sig)::DataType | ||
| 306 | spec_len = length(msig.parameters) + 1 | ||
| 307 | ls = length(sigtuple.parameters) | ||
| 308 | if method === sv.linfo.def | ||
| 309 | # Under direct self-recursion, permit much greater use of reducers. | ||
| 310 | # here we assume that complexity(specTypes) :>= complexity(sig) | ||
| 311 | comparison = sv.linfo.specTypes | ||
| 312 | l_comparison = length(unwrap_unionall(comparison).parameters) | ||
| 313 | spec_len = max(spec_len, l_comparison) | ||
| 314 | else | ||
| 315 | comparison = method.sig | ||
| 316 | end | ||
| 317 | # see if the type is actually too big (relative to the caller), and limit it if required | ||
| 318 | newsig = limit_type_size(sig, comparison, sv.linfo.specTypes, sv.params.TUPLE_COMPLEXITY_LIMIT_DEPTH, spec_len) | ||
| 319 | |||
| 320 | if newsig !== sig | ||
| 321 | # continue inference, but note that we've limited parameter complexity | ||
| 322 | # on this call (to ensure convergence), so that we don't cache this result | ||
| 323 | if call_result_unused(sv) | ||
| 324 | # if we don't (typically) actually care about this result, | ||
| 325 | # don't bother trying to examine some complex abstract signature | ||
| 326 | # since it's very unlikely that we'll try to inline this, | ||
| 327 | # or want make an invoke edge to its calling convention return type. | ||
| 328 | # (non-typically, this means that we lose the ability to detect a guaranteed StackOverflow in some cases) | ||
| 329 | return Any, false, nothing | ||
| 330 | end | ||
| 331 | infstate = sv | ||
| 332 | topmost = topmost::InferenceState | ||
| 333 | while !(infstate === topmost.parent) | ||
| 334 | if call_result_unused(infstate) | ||
| 335 | # If we won't propagate the result any further (since it's typically unused), | ||
| 336 | # it's OK that we keep and cache the "limited" result in the parents | ||
| 337 | # (non-typically, this means that we lose the ability to detect a guaranteed StackOverflow in some cases) | ||
| 338 | # TODO: we might be able to halt progress much more strongly here, | ||
| 339 | # since now we know we won't be able to keep anything much that we learned. | ||
| 340 | # We were mainly only here to compute the calling convention return type, | ||
| 341 | # but in most situations now, we are unlikely to be able to use that information. | ||
| 342 | break | ||
| 343 | end | ||
| 344 | infstate.limited = true | ||
| 345 | for infstate_cycle in infstate.callers_in_cycle | ||
| 346 | infstate_cycle.limited = true | ||
| 347 | end | ||
| 348 | infstate = infstate.parent | ||
| 349 | end | ||
| 350 | sig = newsig | ||
| 351 | sparams = svec() | ||
| 352 | end | ||
| 353 | end | ||
| 354 | |||
| 355 | # if sig changed, may need to recompute the sparams environment | ||
| 356 | if isa(method.sig, UnionAll) && isempty(sparams) | ||
| 357 | recomputed = ccall(:jl_type_intersection_with_env, Any, (Any, Any), sig, method.sig)::SimpleVector | ||
| 358 | #@assert recomputed[1] !== Bottom | ||
| 359 | # We must not use `sig` here, since that may re-introduce structural complexity that | ||
| 360 | # our limiting heuristic sought to eliminate. The alternative would be to not increment depth over covariant contexts, | ||
| 361 | # but we prefer to permit inference of tuple-destructuring, so we don't do that right now | ||
| 362 | # For example, with a signature such as `Tuple{T, Ref{T}} where {T <: S}` | ||
| 363 | # we might want to limit this to `Tuple{S, Ref}`, while type-intersection can instead give us back the original type | ||
| 364 | # (which moves `S` back up to a lower comparison depth) | ||
| 365 | # Optionally, we could try to drive this to a fixed point, but I think this is getting too complex, | ||
| 366 | # and this would only cause more questions and more problems | ||
| 367 | # (the following is only an example, most of the statements are probable in the wrong order): | ||
| 368 | # newsig = sig | ||
| 369 | # seen = IdSet() | ||
| 370 | # while !(newsig in seen) | ||
| 371 | # push!(seen, newsig) | ||
| 372 | # lsig = length((unwrap_unionall(sig)::DataType).parameters) | ||
| 373 | # newsig = limit_type_size(newsig, sig, sv.linfo.specTypes, sv.params.TUPLE_COMPLEXITY_LIMIT_DEPTH, lsig) | ||
| 374 | # recomputed = ccall(:jl_type_intersection_with_env, Any, (Any, Any), newsig, method.sig)::SimpleVector | ||
| 375 | # newsig = recomputed[2] | ||
| 376 | # end | ||
| 377 | # sig = ? | ||
| 378 | sparams = recomputed[2]::SimpleVector | ||
| 379 | end | ||
| 380 | |||
| 381 | rt, edge = typeinf_edge(method, sig, sparams, sv) | ||
| 382 | if edge === nothing | ||
| 383 | edgecycle = true | ||
| 384 | end | ||
| 385 | return rt, edgecycle, edge | ||
| 386 | end | ||
| 387 | |||
| 388 | # This is only for use with `Conditional`. | ||
| 389 | # In general, usage of this is wrong. | ||
| 390 | function ssa_def_expr(@nospecialize(arg), sv::InferenceState) | ||
| 391 | while isa(arg, SSAValue) | ||
| 392 | arg = sv.src.code[arg.id] | ||
| 393 | end | ||
| 394 | return arg | ||
| 395 | end | ||
| 396 | |||
| 397 | # `typ` is the inferred type for expression `arg`. | ||
| 398 | # if the expression constructs a container (e.g. `svec(x,y,z)`), | ||
| 399 | # refine its type to an array of element types. | ||
| 400 | # Union of Tuples of the same length is converted to Tuple of Unions. | ||
| 401 | # returns an array of types | ||
| 402 | function precise_container_type(@nospecialize(arg), @nospecialize(typ), vtypes::VarTable, sv::InferenceState) | ||
| 403 | if isa(typ, Const) | ||
| 404 | val = typ.val | ||
| 405 | if isa(val, SimpleVector) || isa(val, Tuple) | ||
| 406 | return Any[ Const(val[i]) for i in 1:length(val) ] # avoid making a tuple Generator here! | ||
| 407 | end | ||
| 408 | end | ||
| 409 | |||
| 410 | arg = ssa_def_expr(arg, sv) | ||
| 411 | if is_specializable_vararg_slot(arg, sv.nargs, sv.result.vargs) | ||
| 412 | return sv.result.vargs | ||
| 413 | end | ||
| 414 | |||
| 415 | tti0 = widenconst(typ) | ||
| 416 | tti = unwrap_unionall(tti0) | ||
| 417 | if isa(arg, Expr) && arg.head === :call && (abstract_evals_to_constant(arg.args[1], svec, vtypes, sv) || | ||
| 418 | abstract_evals_to_constant(arg.args[1], tuple, vtypes, sv)) | ||
| 419 | aa = arg.args | ||
| 420 | result = Any[ abstract_eval(aa[j],vtypes,sv) for j=2:length(aa) ] | ||
| 421 | if _any(isvarargtype, result) | ||
| 422 | return Any[Vararg{Any}] | ||
| 423 | end | ||
| 424 | return result | ||
| 425 | elseif isa(tti, Union) | ||
| 426 | utis = uniontypes(tti) | ||
| 427 | if _any(t -> !isa(t,DataType) || !(t <: Tuple) || !isknownlength(t), utis) | ||
| 428 | return Any[Vararg{Any}] | ||
| 429 | end | ||
| 430 | result = Any[rewrap_unionall(p, tti0) for p in utis[1].parameters] | ||
| 431 | for t in utis[2:end] | ||
| 432 | if length(t.parameters) != length(result) | ||
| 433 | return Any[Vararg{Any}] | ||
| 434 | end | ||
| 435 | for j in 1:length(t.parameters) | ||
| 436 | result[j] = tmerge(result[j], rewrap_unionall(t.parameters[j], tti0)) | ||
| 437 | end | ||
| 438 | end | ||
| 439 | return result | ||
| 440 | elseif isa(tti0,DataType) && tti0 <: Tuple | ||
| 441 | if isvatuple(tti0) && length(tti0.parameters) == 1 | ||
| 442 | return Any[Vararg{unwrapva(tti0.parameters[1])}] | ||
| 443 | else | ||
| 444 | return Any[ p for p in tti0.parameters ] | ||
| 445 | end | ||
| 446 | elseif tti0 <: Array | ||
| 447 | return Any[Vararg{eltype(tti0)}] | ||
| 448 | else | ||
| 449 | return abstract_iteration(typ, vtypes, sv) | ||
| 450 | end | ||
| 451 | end | ||
| 452 | |||
| 453 | # simulate iteration protocol on container type up to fixpoint | ||
| 454 | function abstract_iteration(@nospecialize(itertype), vtypes::VarTable, sv::InferenceState) | ||
| 455 | if !isdefined(Main, :Base) || !isdefined(Main.Base, :iterate) || !isconst(Main.Base, :iterate) | ||
| 456 | return Any[Vararg{Any}] | ||
| 457 | end | ||
| 458 | iteratef = getfield(Main.Base, :iterate) | ||
| 459 | stateordonet = abstract_call(iteratef, (), Any[Const(iteratef), itertype], vtypes, sv) | ||
| 460 | # Return Bottom if this is not an iterator. | ||
| 461 | # WARNING: Changes to the iteration protocol must be reflected here, | ||
| 462 | # this is not just an optimization. | ||
| 463 | stateordonet === Bottom && return Any[Bottom] | ||
| 464 | valtype = statetype = Bottom | ||
| 465 | ret = Any[] | ||
| 466 | stateordonet = widenconst(stateordonet) | ||
| 467 | while !(Nothing <: stateordonet) && length(ret) < sv.params.MAX_TUPLE_SPLAT | ||
| 468 | if !isa(stateordonet, DataType) || !(stateordonet <: Tuple) || isvatuple(stateordonet) || length(stateordonet.parameters) != 2 | ||
| 469 | break | ||
| 470 | end | ||
| 471 | if stateordonet.parameters[2] <: statetype | ||
| 472 | # infinite (or failing) iterator | ||
| 473 | return Any[Bottom] | ||
| 474 | end | ||
| 475 | valtype = stateordonet.parameters[1] | ||
| 476 | statetype = stateordonet.parameters[2] | ||
| 477 | push!(ret, valtype) | ||
| 478 | stateordonet = abstract_call(iteratef, (), Any[Const(iteratef), itertype, statetype], vtypes, sv) | ||
| 479 | stateordonet = widenconst(stateordonet) | ||
| 480 | end | ||
| 481 | if stateordonet === Nothing | ||
| 482 | return ret | ||
| 483 | end | ||
| 484 | while valtype !== Any | ||
| 485 | nounion = typesubtract(stateordonet, Nothing) | ||
| 486 | if !isa(nounion, DataType) || !(nounion <: Tuple) || isvatuple(nounion) || length(nounion.parameters) != 2 | ||
| 487 | valtype = Any | ||
| 488 | break | ||
| 489 | end | ||
| 490 | if nounion.parameters[1] <: valtype && nounion.parameters[2] <: statetype | ||
| 491 | break | ||
| 492 | end | ||
| 493 | valtype = tmerge(valtype, nounion.parameters[1]) | ||
| 494 | statetype = tmerge(statetype, nounion.parameters[2]) | ||
| 495 | stateordonet = abstract_call(iteratef, (), Any[Const(iteratef), itertype, statetype], vtypes, sv) | ||
| 496 | stateordonet = widenconst(stateordonet) | ||
| 497 | end | ||
| 498 | push!(ret, Vararg{valtype}) | ||
| 499 | return ret | ||
| 500 | end | ||
| 501 | |||
| 502 | # do apply(af, fargs...), where af is a function value | ||
| 503 | function abstract_apply(@nospecialize(aft), fargs::Union{Tuple{},Vector{Any}}, aargtypes::Vector{Any}, vtypes::VarTable, sv::InferenceState) | ||
| 504 | if !isa(aft, Const) && (!isType(aft) || has_free_typevars(aft)) | ||
| 505 | if !isconcretetype(aft) || (aft <: Builtin) | ||
| 506 | # non-constant function of unknown type: bail now, | ||
| 507 | # since it seems unlikely that abstract_call will be able to do any better after splitting | ||
| 508 | # this also ensures we don't call abstract_call_gf_by_type below on an IntrinsicFunction or Builtin | ||
| 509 | return Any | ||
| 510 | end | ||
| 511 | end | ||
| 512 | res = Union{} | ||
| 513 | nargs = length(aargtypes) | ||
| 514 | @assert fargs === () || nargs == length(fargs) | ||
| 515 | splitunions = 1 < countunionsplit(aargtypes) <= sv.params.MAX_APPLY_UNION_ENUM | ||
| 516 | ctypes = Any[Any[aft]] | ||
| 517 | for i = 1:nargs | ||
| 518 | ctypes´ = [] | ||
| 519 | for ti in (splitunions ? uniontypes(aargtypes[i]) : Any[aargtypes[i]]) | ||
| 520 | cti = precise_container_type(fargs === () ? nothing : fargs[i], ti, vtypes, sv) | ||
| 521 | if _any(t -> t === Bottom, cti) | ||
| 522 | continue | ||
| 523 | end | ||
| 524 | for ct in ctypes | ||
| 525 | if isvarargtype(ct[end]) | ||
| 526 | tail = tuple_tail_elem(unwrapva(ct[end]), cti) | ||
| 527 | push!(ctypes´, push!(ct[1:(end - 1)], tail)) | ||
| 528 | else | ||
| 529 | push!(ctypes´, append_any(ct, cti)) | ||
| 530 | end | ||
| 531 | end | ||
| 532 | end | ||
| 533 | ctypes = ctypes´ | ||
| 534 | end | ||
| 535 | for ct in ctypes | ||
| 536 | if isa(aft, Const) | ||
| 537 | rt = abstract_call(aft.val, (), ct, vtypes, sv) | ||
| 538 | elseif isconstType(aft) | ||
| 539 | rt = abstract_call(aft.parameters[1], (), ct, vtypes, sv) | ||
| 540 | else | ||
| 541 | astype = argtypes_to_type(ct) | ||
| 542 | rt = abstract_call_gf_by_type(nothing, ct, astype, sv) | ||
| 543 | end | ||
| 544 | res = tmerge(res, rt) | ||
| 545 | if res === Any | ||
| 546 | break | ||
| 547 | end | ||
| 548 | end | ||
| 549 | return res | ||
| 550 | end | ||
| 551 | |||
| 552 | function pure_eval_call(@nospecialize(f), argtypes::Vector{Any}, @nospecialize(atype), sv::InferenceState) | ||
| 553 | for i = 2:length(argtypes) | ||
| 554 | a = maybe_widen_conditional(argtypes[i]) | ||
| 555 | if !(isa(a, Const) || isconstType(a)) | ||
| 556 | return false | ||
| 557 | end | ||
| 558 | end | ||
| 559 | |||
| 560 | min_valid = UInt[typemin(UInt)] | ||
| 561 | max_valid = UInt[typemax(UInt)] | ||
| 562 | meth = _methods_by_ftype(atype, 1, sv.params.world, min_valid, max_valid) | ||
| 563 | if meth === false || length(meth) != 1 | ||
| 564 | return false | ||
| 565 | end | ||
| 566 | meth = meth[1]::SimpleVector | ||
| 567 | method = meth[3]::Method | ||
| 568 | # TODO: check pure on the inferred thunk | ||
| 569 | if isdefined(method, :generator) || !method.pure | ||
| 570 | return false | ||
| 571 | end | ||
| 572 | |||
| 573 | args = Any[ (a = maybe_widen_conditional(argtypes[i]); isa(a, Const) ? a.val : a.parameters[1]) for i in 2:length(argtypes) ] | ||
| 574 | try | ||
| 575 | value = Core._apply_pure(f, args) | ||
| 576 | # TODO: add some sort of edge(s) | ||
| 577 | return Const(value, true) | ||
| 578 | catch | ||
| 579 | return false | ||
| 580 | end | ||
| 581 | end | ||
| 582 | |||
| 583 |
2 (5.41%) samples spent in abstract_call
function abstract_call(@nospecialize(f), fargs::Union{Tuple{},Vector{Any}}, argtypes::Vector{Any}, vtypes::VarTable, sv::InferenceState)
0 (ex.), 2 (100.00%) (incl.) when called from abstract_eval_call line 858 |
||
| 584 | if f === _apply | ||
| 585 | return abstract_apply(argtypes[2], fargs[3:end], argtypes[3:end], vtypes, sv) | ||
| 586 | end | ||
| 587 | |||
| 588 | la = length(argtypes) | ||
| 589 | for i = 2:(la - 1) | ||
| 590 | if isvarargtype(argtypes[i]) | ||
| 591 | return Any | ||
| 592 | end | ||
| 593 | end | ||
| 594 | |||
| 595 | if isa(f, Builtin) || isa(f, IntrinsicFunction) | ||
| 596 | if f === ifelse && fargs isa Vector{Any} && length(argtypes) == 4 && argtypes[2] isa Conditional | ||
| 597 | # try to simulate this as a real conditional (`cnd ? x : y`), so that the penalty for using `ifelse` instead isn't too high | ||
| 598 | cnd = argtypes[2]::Conditional | ||
| 599 | tx = argtypes[3] | ||
| 600 | ty = argtypes[4] | ||
| 601 | a = ssa_def_expr(fargs[3], sv) | ||
| 602 | b = ssa_def_expr(fargs[4], sv) | ||
| 603 | if isa(a, Slot) && slot_id(cnd.var) == slot_id(a) | ||
| 604 | tx = typeintersect(tx, cnd.vtype) | ||
| 605 | end | ||
| 606 | if isa(b, Slot) && slot_id(cnd.var) == slot_id(b) | ||
| 607 | ty = typeintersect(ty, cnd.elsetype) | ||
| 608 | end | ||
| 609 | return tmerge(tx, ty) | ||
| 610 | end | ||
| 611 | rt = builtin_tfunction(f, argtypes[2:end], sv) | ||
| 612 | if f === getfield && isa(fargs, Vector{Any}) && length(argtypes) == 3 && isa(argtypes[3], Const) && isa(argtypes[3].val, Int) && argtypes[2] ⊑ Tuple | ||
| 613 | cti = precise_container_type(fargs[2], argtypes[2], vtypes, sv) | ||
| 614 | idx = argtypes[3].val | ||
| 615 | if 1 <= idx <= length(cti) | ||
| 616 | rt = unwrapva(cti[idx]) | ||
| 617 | end | ||
| 618 | elseif (rt === Bool || (isa(rt, Const) && isa(rt.val, Bool))) && isa(fargs, Vector{Any}) | ||
| 619 | # perform very limited back-propagation of type information for `is` and `isa` | ||
| 620 | if f === isa | ||
| 621 | a = ssa_def_expr(fargs[2], sv) | ||
| 622 | if isa(a, Slot) | ||
| 623 | aty = widenconst(argtypes[2]) | ||
| 624 | if rt === Const(false) | ||
| 625 | return Conditional(a, Union{}, aty) | ||
| 626 | elseif rt === Const(true) | ||
| 627 | return Conditional(a, aty, Union{}) | ||
| 628 | end | ||
| 629 | tty_ub, isexact_tty = instanceof_tfunc(argtypes[3]) | ||
| 630 | if isexact_tty && !isa(tty_ub, TypeVar) | ||
| 631 | tty_lb = tty_ub # TODO: this would be wrong if !isexact_tty, but instanceof_tfunc doesn't preserve this info | ||
| 632 | if !has_free_typevars(tty_lb) && !has_free_typevars(tty_ub) | ||
| 633 | ifty = typeintersect(aty, tty_ub) | ||
| 634 | elty = typesubtract(aty, tty_lb) | ||
| 635 | return Conditional(a, ifty, elty) | ||
| 636 | end | ||
| 637 | end | ||
| 638 | end | ||
| 639 | elseif f === (===) | ||
| 640 | a = ssa_def_expr(fargs[2], sv) | ||
| 641 | b = ssa_def_expr(fargs[3], sv) | ||
| 642 | aty = argtypes[2] | ||
| 643 | bty = argtypes[3] | ||
| 644 | # if doing a comparison to a singleton, consider returning a `Conditional` instead | ||
| 645 | if isa(aty, Const) && isa(b, Slot) | ||
| 646 | if rt === Const(false) | ||
| 647 | aty = Union{} | ||
| 648 | elseif rt === Const(true) | ||
| 649 | bty = Union{} | ||
| 650 | elseif bty isa Type && isdefined(typeof(aty.val), :instance) # can only widen a if it is a singleton | ||
| 651 | bty = typesubtract(bty, typeof(aty.val)) | ||
| 652 | end | ||
| 653 | return Conditional(b, aty, bty) | ||
| 654 | end | ||
| 655 | if isa(bty, Const) && isa(a, Slot) | ||
| 656 | if rt === Const(false) | ||
| 657 | bty = Union{} | ||
| 658 | elseif rt === Const(true) | ||
| 659 | aty = Union{} | ||
| 660 | elseif aty isa Type && isdefined(typeof(bty.val), :instance) # same for b | ||
| 661 | aty = typesubtract(aty, typeof(bty.val)) | ||
| 662 | end | ||
| 663 | return Conditional(a, bty, aty) | ||
| 664 | end | ||
| 665 | if isa(b, Slot) | ||
| 666 | return Conditional(b, bty, bty) | ||
| 667 | end | ||
| 668 | if isa(a, Slot) | ||
| 669 | return Conditional(a, aty, aty) | ||
| 670 | end | ||
| 671 | elseif f === Core.Compiler.not_int | ||
| 672 | aty = argtypes[2] | ||
| 673 | if isa(aty, Conditional) | ||
| 674 | ifty = aty.elsetype | ||
| 675 | elty = aty.vtype | ||
| 676 | if rt === Const(false) | ||
| 677 | ifty = Union{} | ||
| 678 | elseif rt === Const(true) | ||
| 679 | elty = Union{} | ||
| 680 | end | ||
| 681 | return Conditional(aty.var, ifty, elty) | ||
| 682 | end | ||
| 683 | end | ||
| 684 | end | ||
| 685 | return isa(rt, TypeVar) ? rt.ub : rt | ||
| 686 | elseif f === Core.kwfunc | ||
| 687 | if length(argtypes) == 2 | ||
| 688 | ft = widenconst(argtypes[2]) | ||
| 689 | if isa(ft, DataType) && isdefined(ft.name, :mt) && isdefined(ft.name.mt, :kwsorter) | ||
| 690 | return Const(ft.name.mt.kwsorter) | ||
| 691 | end | ||
| 692 | end | ||
| 693 | return Any | ||
| 694 | elseif f === TypeVar | ||
| 695 | lb = Union{} | ||
| 696 | ub = Any | ||
| 697 | ub_certain = lb_certain = true | ||
| 698 | if length(argtypes) >= 2 && isa(argtypes[2], Const) | ||
| 699 | nv = argtypes[2].val | ||
| 700 | ubidx = 3 | ||
| 701 | if length(argtypes) >= 4 | ||
| 702 | ubidx = 4 | ||
| 703 | if isa(argtypes[3], Const) | ||
| 704 | lb = argtypes[3].val | ||
| 705 | elseif isType(argtypes[3]) | ||
| 706 | lb = argtypes[3].parameters[1] | ||
| 707 | lb_certain = false | ||
| 708 | else | ||
| 709 | return TypeVar | ||
| 710 | end | ||
| 711 | end | ||
| 712 | if length(argtypes) >= ubidx | ||
| 713 | if isa(argtypes[ubidx], Const) | ||
| 714 | ub = argtypes[ubidx].val | ||
| 715 | elseif isType(argtypes[ubidx]) | ||
| 716 | ub = argtypes[ubidx].parameters[1] | ||
| 717 | ub_certain = false | ||
| 718 | else | ||
| 719 | return TypeVar | ||
| 720 | end | ||
| 721 | end | ||
| 722 | tv = TypeVar(nv, lb, ub) | ||
| 723 | return PartialTypeVar(tv, lb_certain, ub_certain) | ||
| 724 | end | ||
| 725 | return TypeVar | ||
| 726 | elseif f === UnionAll | ||
| 727 | if length(argtypes) == 3 | ||
| 728 | canconst = true | ||
| 729 | if isa(argtypes[3], Const) | ||
| 730 | body = argtypes[3].val | ||
| 731 | elseif isType(argtypes[3]) | ||
| 732 | body = argtypes[3].parameters[1] | ||
| 733 | canconst = false | ||
| 734 | else | ||
| 735 | return Any | ||
| 736 | end | ||
| 737 | if !isa(body, Type) && !isa(body, TypeVar) | ||
| 738 | return Any | ||
| 739 | end | ||
| 740 | if has_free_typevars(body) | ||
| 741 | if isa(argtypes[2], Const) | ||
| 742 | tv = argtypes[2].val | ||
| 743 | elseif isa(argtypes[2], PartialTypeVar) | ||
| 744 | ptv = argtypes[2] | ||
| 745 | tv = ptv.tv | ||
| 746 | canconst = false | ||
| 747 | else | ||
| 748 | return Any | ||
| 749 | end | ||
| 750 | !isa(tv, TypeVar) && return Any | ||
| 751 | body = UnionAll(tv, body) | ||
| 752 | end | ||
| 753 | ret = canconst ? AbstractEvalConstant(body) : Type{body} | ||
| 754 | return ret | ||
| 755 | end | ||
| 756 | return Any | ||
| 757 | elseif f === return_type | ||
| 758 | rt_rt = return_type_tfunc(argtypes, vtypes, sv) | ||
| 759 | if rt_rt !== NOT_FOUND | ||
| 760 | return rt_rt | ||
| 761 | end | ||
| 762 | elseif length(argtypes) == 2 && istopfunction(f, :!) | ||
| 763 | # handle Conditional propagation through !Bool | ||
| 764 | aty = argtypes[2] | ||
| 765 | if isa(aty, Conditional) | ||
| 766 | abstract_call_gf_by_type(f, Any[Const(f), Bool], Tuple{typeof(f), Bool}, sv) # make sure we've inferred `!(::Bool)` | ||
| 767 | return Conditional(aty.var, aty.elsetype, aty.vtype) | ||
| 768 | end | ||
| 769 | elseif length(argtypes) == 3 && istopfunction(f, :!==) | ||
| 770 | # mark !== as exactly a negated call to === | ||
| 771 | rty = abstract_call((===), fargs, argtypes, vtypes, sv) | ||
| 772 | if isa(rty, Conditional) | ||
| 773 | return Conditional(rty.var, rty.elsetype, rty.vtype) # swap if-else | ||
| 774 | elseif isa(rty, Const) | ||
| 775 | return Const(rty.val === false) | ||
| 776 | end | ||
| 777 | return rty | ||
| 778 | elseif length(argtypes) == 3 && istopfunction(f, :(>:)) | ||
| 779 | # mark issupertype as a exact alias for issubtype | ||
| 780 | # swap T1 and T2 arguments and call <: | ||
| 781 | if length(fargs) == 3 | ||
| 782 | fargs = Any[<:, fargs[3], fargs[2]] | ||
| 783 | else | ||
| 784 | fargs = () | ||
| 785 | end | ||
| 786 | argtypes = Any[typeof(<:), argtypes[3], argtypes[2]] | ||
| 787 | rty = abstract_call(<:, fargs, argtypes, vtypes, sv) | ||
| 788 | return rty | ||
| 789 | elseif length(argtypes) == 2 && isa(argtypes[2], Const) && isa(argtypes[2].val, SimpleVector) && istopfunction(f, :length) | ||
| 790 | # mark length(::SimpleVector) as @pure | ||
| 791 | return Const(length(argtypes[2].val)) | ||
| 792 | elseif length(argtypes) == 3 && isa(argtypes[2], Const) && isa(argtypes[3], Const) && | ||
| 793 | isa(argtypes[2].val, SimpleVector) && isa(argtypes[3].val, Int) && istopfunction(f, :getindex) | ||
| 794 | # mark getindex(::SimpleVector, i::Int) as @pure | ||
| 795 | svecval = argtypes[2].val::SimpleVector | ||
| 796 | idx = argtypes[3].val::Int | ||
| 797 | if 1 <= idx <= length(svecval) && isassigned(svecval, idx) | ||
| 798 | return Const(getindex(svecval, idx)) | ||
| 799 | end | ||
| 800 | elseif length(argtypes) == 2 && istopfunction(f, :typename) | ||
| 801 | return typename_static(argtypes[2]) | ||
| 802 | end | ||
| 803 | |||
| 804 | atype = argtypes_to_type(argtypes) | ||
| 805 | t = pure_eval_call(f, argtypes, atype, sv) | ||
| 806 | t !== false && return t | ||
| 807 | |||
| 808 | if istopfunction(f, :typejoin) || f === return_type | ||
| 809 | return Type # don't try to infer these function edges directly -- it won't actually come up with anything useful | ||
| 810 | end | ||
| 811 | |||
| 812 | if sv.params.inlining | ||
| 813 | # need to model the special inliner for ^ | ||
| 814 | # to ensure we have added the same edge | ||
| 815 | if isdefined(Main, :Base) && | ||
| 816 | ((isdefined(Main.Base, :^) && f === Main.Base.:^) || | ||
| 817 | (isdefined(Main.Base, :.^) && f === Main.Base.:.^)) && | ||
| 818 | length(argtypes) == 3 && (argtypes[3] ⊑ Int32 || argtypes[3] ⊑ Int64) | ||
| 819 | |||
| 820 | a1 = argtypes[2] | ||
| 821 | basenumtype = Union{CoreNumType, Main.Base.ComplexF32, Main.Base.ComplexF64, Main.Base.Rational} | ||
| 822 | if a1 ⊑ basenumtype | ||
| 823 | ftimes = Main.Base.:* | ||
| 824 | ta1 = widenconst(a1) | ||
| 825 | abstract_call_gf_by_type(ftimes, Any[ftimes, a1, a1], Tuple{typeof(ftimes), ta1, ta1}, sv) | ||
| 826 | end | ||
| 827 | end | ||
| 828 | end | ||
| 829 | 4 (10.81%) |
2 (50.00%)
samples spent calling
abstract_call_gf_by_type
return abstract_call_gf_by_type(f, argtypes, atype, sv)
|
|
| 830 | end | ||
| 831 | |||
| 832 | # wrapper around `abstract_call` for first computing if `f` is available | ||
| 833 | function abstract_eval_call(fargs::Union{Tuple{},Vector{Any}}, argtypes::Vector{Any}, vtypes::VarTable, sv::InferenceState) | ||
| 834 |
2 (5.41%) samples spent in abstract_eval_call
#print("call ", e.args[1], argtypes, "\n\n")
0 (ex.), 2 (100.00%) (incl.) when called from abstract_eval line 943 |
||
| 835 | for x in argtypes | ||
| 836 | x === Bottom && return Bottom | ||
| 837 | end | ||
| 838 | ft = argtypes[1] | ||
| 839 | if isa(ft, Const) | ||
| 840 | f = ft.val | ||
| 841 | elseif isconstType(ft) | ||
| 842 | f = ft.parameters[1] | ||
| 843 | elseif isa(ft, DataType) && isdefined(ft, :instance) | ||
| 844 | f = ft.instance | ||
| 845 | else | ||
| 846 | for i = 2:(length(argtypes) - 1) | ||
| 847 | if isvarargtype(argtypes[i]) | ||
| 848 | return Any | ||
| 849 | end | ||
| 850 | end | ||
| 851 | # non-constant function, but the number of arguments is known | ||
| 852 | # and the ft is not a Builtin or IntrinsicFunction | ||
| 853 | if typeintersect(widenconst(ft), Builtin) != Union{} | ||
| 854 | return Any | ||
| 855 | end | ||
| 856 | return abstract_call_gf_by_type(nothing, argtypes, argtypes_to_type(argtypes), sv) | ||
| 857 | end | ||
| 858 | 4 (10.81%) |
2 (50.00%)
samples spent calling
abstract_call
return abstract_call(f, fargs, argtypes, vtypes, sv)
|
|
| 859 | end | ||
| 860 | |||
| 861 | function sp_type_rewrap(@nospecialize(T), linfo::MethodInstance, isreturn::Bool) | ||
| 862 | isref = false | ||
| 863 | if T === Bottom | ||
| 864 | return Bottom | ||
| 865 | elseif isa(T, Type) | ||
| 866 | if isa(T, DataType) && (T::DataType).name === _REF_NAME | ||
| 867 | isref = true | ||
| 868 | T = T.parameters[1] | ||
| 869 | if isreturn && T === Any | ||
| 870 | return Bottom # a return type of Ref{Any} is invalid | ||
| 871 | end | ||
| 872 | end | ||
| 873 | else | ||
| 874 | return Any | ||
| 875 | end | ||
| 876 | if isa(linfo.def, Method) | ||
| 877 | spsig = linfo.def.sig | ||
| 878 | if isa(spsig, UnionAll) | ||
| 879 | if !isempty(linfo.sparam_vals) | ||
| 880 | env = pointer_from_objref(linfo.sparam_vals) + sizeof(Ptr{Cvoid}) | ||
| 881 | T = ccall(:jl_instantiate_type_in_env, Any, (Any, Any, Ptr{Any}), T, spsig, env) | ||
| 882 | isref && isreturn && T === Any && return Bottom # catch invalid return Ref{T} where T = Any | ||
| 883 | for v in linfo.sparam_vals | ||
| 884 | if isa(v, TypeVar) | ||
| 885 | T = UnionAll(v, T) | ||
| 886 | end | ||
| 887 | end | ||
| 888 | else | ||
| 889 | T = rewrap_unionall(T, spsig) | ||
| 890 | end | ||
| 891 | end | ||
| 892 | end | ||
| 893 | while isa(T, TypeVar) | ||
| 894 | T = T.ub | ||
| 895 | end | ||
| 896 | return T | ||
| 897 | end | ||
| 898 | |||
| 899 | function abstract_eval_cfunction(e::Expr, vtypes::VarTable, sv::InferenceState) | ||
| 900 | f = abstract_eval(e.args[2], vtypes, sv) | ||
| 901 | # rt = sp_type_rewrap(e.args[3], sv.linfo, true) | ||
| 902 | at = Any[ sp_type_rewrap(argt, sv.linfo, false) for argt in e.args[4]::SimpleVector ] | ||
| 903 | pushfirst!(at, f) | ||
| 904 | # this may be the wrong world for the call, | ||
| 905 | # but some of the result is likely to be valid anyways | ||
| 906 | # and that may help generate better codegen | ||
| 907 | abstract_eval_call((), at, vtypes, sv) | ||
| 908 | nothing | ||
| 909 | end | ||
| 910 | |||
| 911 | # convert an inferred static parameter value to the inferred type of a static_parameter expression | ||
| 912 | function sparam_type(@nospecialize(val)) | ||
| 913 | if isa(val, TypeVar) | ||
| 914 | if Any <: val.ub | ||
| 915 | # static param bound to typevar | ||
| 916 | # if the tvar is not known to refer to anything more specific than Any, | ||
| 917 | # the static param might actually be an integer, symbol, etc. | ||
| 918 | return Any | ||
| 919 | else | ||
| 920 | return UnionAll(val, Type{val}) | ||
| 921 | end | ||
| 922 | end | ||
| 923 | return AbstractEvalConstant(val) | ||
| 924 | end | ||
| 925 | |||
| 926 |
2 (5.41%) samples spent in abstract_eval
function abstract_eval(@nospecialize(e), vtypes::VarTable, sv::InferenceState)
0 (ex.), 1 (50.00%) (incl.) when called from abstract_eval line 942 0 (ex.), 2 (100.00%) (incl.) when called from typeinf_local line 1169 |
||
| 927 | if isa(e, QuoteNode) | ||
| 928 | return AbstractEvalConstant((e::QuoteNode).value) | ||
| 929 | elseif isa(e, SSAValue) | ||
| 930 | return abstract_eval_ssavalue(e::SSAValue, sv.src) | ||
| 931 | elseif isa(e, Slot) | ||
| 932 | return vtypes[slot_id(e)].typ | ||
| 933 | elseif isa(e, GlobalRef) | ||
| 934 | 1 (2.70%) |
1 (100.00%)
samples spent calling
abstract_eval_global
return abstract_eval_global(e.mod, e.name)
|
|
| 935 | end | ||
| 936 | |||
| 937 | if !isa(e, Expr) | ||
| 938 | return AbstractEvalConstant(e) | ||
| 939 | end | ||
| 940 | e = e::Expr | ||
| 941 | if e.head === :call | ||
| 942 | 1 (2.70%) |
1 (100.00%)
samples spent calling
abstract_eval
argtypes = Any[ abstract_eval(a, vtypes, sv) for a in e.args ]
|
|
| 943 | 4 (10.81%) |
2 (50.00%)
samples spent calling
abstract_eval_call
t = abstract_eval_call(e.args, argtypes, vtypes, sv)
|
|
| 944 | elseif e.head === :new | ||
| 945 | t = instanceof_tfunc(abstract_eval(e.args[1], vtypes, sv))[1] | ||
| 946 | for i = 2:length(e.args) | ||
| 947 | if abstract_eval(e.args[i], vtypes, sv) === Bottom | ||
| 948 | rt = Bottom | ||
| 949 | end | ||
| 950 | end | ||
| 951 | elseif e.head === :& | ||
| 952 | abstract_eval(e.args[1], vtypes, sv) | ||
| 953 | t = Any | ||
| 954 | elseif e.head === :foreigncall | ||
| 955 | abstract_eval(e.args[1], vtypes, sv) | ||
| 956 | t = sp_type_rewrap(e.args[2], sv.linfo, true) | ||
| 957 | for i = 3:length(e.args) | ||
| 958 | if abstract_eval(e.args[i], vtypes, sv) === Bottom | ||
| 959 | t = Bottom | ||
| 960 | end | ||
| 961 | end | ||
| 962 | elseif e.head === :cfunction | ||
| 963 | t = e.args[1] | ||
| 964 | isa(t, Type) || (t = Any) | ||
| 965 | abstract_eval_cfunction(e, vtypes, sv) | ||
| 966 | elseif e.head === :static_parameter | ||
| 967 | n = e.args[1] | ||
| 968 | t = Any | ||
| 969 | if 1 <= n <= length(sv.sp) | ||
| 970 | t = sparam_type(sv.sp[n]) | ||
| 971 | end | ||
| 972 | elseif e.head === :method | ||
| 973 | t = (length(e.args) == 1) ? Any : Nothing | ||
| 974 | elseif e.head === :copyast | ||
| 975 | t = abstract_eval(e.args[1], vtypes, sv) | ||
| 976 | if t isa Const && t.val isa Expr | ||
| 977 | # `copyast` makes copies of Exprs | ||
| 978 | t = Expr | ||
| 979 | end | ||
| 980 | elseif e.head === :invoke | ||
| 981 | error("type inference data-flow error: tried to double infer a function") | ||
| 982 | elseif e.head === :boundscheck | ||
| 983 | return Bool | ||
| 984 | elseif e.head === :isdefined | ||
| 985 | sym = e.args[1] | ||
| 986 | t = Bool | ||
| 987 | if isa(sym, Slot) | ||
| 988 | vtyp = vtypes[slot_id(sym)] | ||
| 989 | if vtyp.typ === Bottom | ||
| 990 | t = Const(false) # never assigned previously | ||
| 991 | elseif !vtyp.undef | ||
| 992 | t = Const(true) # definitely assigned previously | ||
| 993 | end | ||
| 994 | elseif isa(sym, Symbol) | ||
| 995 | if isdefined(sv.mod, sym.name) | ||
| 996 | t = Const(true) | ||
| 997 | end | ||
| 998 | elseif isa(sym, GlobalRef) | ||
| 999 | if isdefined(sym.mod, sym.name) | ||
| 1000 | t = Const(true) | ||
| 1001 | end | ||
| 1002 | elseif isa(sym, Expr) && sym.head === :static_parameter | ||
| 1003 | n = sym.args[1] | ||
| 1004 | if 1 <= n <= length(sv.sp) | ||
| 1005 | val = sv.sp[n] | ||
| 1006 | if !isa(val, TypeVar) | ||
| 1007 | t = Const(true) | ||
| 1008 | end | ||
| 1009 | end | ||
| 1010 | end | ||
| 1011 | else | ||
| 1012 | t = Any | ||
| 1013 | end | ||
| 1014 | @assert !isa(t, TypeVar) | ||
| 1015 | if isa(t, DataType) && isdefined(t, :instance) | ||
| 1016 | # replace singleton types with their equivalent Const object | ||
| 1017 | t = Const(t.instance) | ||
| 1018 | end | ||
| 1019 | return t | ||
| 1020 | end | ||
| 1021 | |||
| 1022 | function abstract_eval_global(M::Module, s::Symbol) | ||
| 1023 | if isdefined(M,s) && isconst(M,s) | ||
| 1024 | 1 (2.70%) | 1 (2.70%) |
1 (2.70%) samples spent in abstract_eval_global
return AbstractEvalConstant(getfield(M,s))
1 (100.00%) (ex.), 1 (100.00%) (incl.) when called from abstract_eval line 934 |
| 1025 | end | ||
| 1026 | return Any | ||
| 1027 | end | ||
| 1028 | |||
| 1029 | function abstract_eval_ssavalue(s::SSAValue, src::CodeInfo) | ||
| 1030 | typ = src.ssavaluetypes[s.id] | ||
| 1031 | if typ === NOT_FOUND | ||
| 1032 | return Bottom | ||
| 1033 | end | ||
| 1034 | return typ | ||
| 1035 | end | ||
| 1036 | |||
| 1037 | # determine whether `ex` abstractly evals to constant `c` | ||
| 1038 | function abstract_evals_to_constant(@nospecialize(ex), @nospecialize(c), vtypes::VarTable, sv::InferenceState) | ||
| 1039 | av = abstract_eval(ex, vtypes, sv) | ||
| 1040 | return isa(av, Const) && av.val === c | ||
| 1041 | end | ||
| 1042 | |||
| 1043 | # make as much progress on `frame` as possible (without handling cycles) | ||
| 1044 |
2 (5.41%) samples spent in typeinf_local
function typeinf_local(frame::InferenceState)
0 (ex.), 2 (100.00%) (incl.) when called from typeinf_nocycle line 1225 |
||
| 1045 | @assert !frame.inferred | ||
| 1046 | frame.dont_work_on_me = true # mark that this function is currently on the stack | ||
| 1047 | W = frame.ip | ||
| 1048 | s = frame.stmt_types | ||
| 1049 | n = frame.nstmts | ||
| 1050 | while frame.pc´´ <= n | ||
| 1051 | # make progress on the active ip set | ||
| 1052 | local pc::Int = frame.pc´´ # current program-counter | ||
| 1053 | while true # inner loop optimizes the common case where it can run straight from pc to pc + 1 | ||
| 1054 | #print(pc,": ",s[pc],"\n") | ||
| 1055 | local pc´::Int = pc + 1 # next program-counter (after executing instruction) | ||
| 1056 | if pc == frame.pc´´ | ||
| 1057 | # need to update pc´´ to point at the new lowest instruction in W | ||
| 1058 | min_pc = _bits_findnext(W.bits, pc + 1) | ||
| 1059 | frame.pc´´ = min_pc == -1 ? n + 1 : min_pc | ||
| 1060 | end | ||
| 1061 | delete!(W, pc) | ||
| 1062 | frame.currpc = pc | ||
| 1063 | frame.cur_hand = frame.handler_at[pc] | ||
| 1064 | frame.stmt_edges[pc] === () || empty!(frame.stmt_edges[pc]) | ||
| 1065 | stmt = frame.src.code[pc] | ||
| 1066 | changes = s[pc]::VarTable | ||
| 1067 | t = nothing | ||
| 1068 | |||
| 1069 | hd = isa(stmt, Expr) ? stmt.head : nothing | ||
| 1070 | |||
| 1071 | if isa(stmt, NewvarNode) | ||
| 1072 | sn = slot_id(stmt.slot) | ||
| 1073 | changes[sn] = VarState(Bottom, true) | ||
| 1074 | elseif isa(stmt, GotoNode) | ||
| 1075 | pc´ = (stmt::GotoNode).label | ||
| 1076 | elseif hd === :gotoifnot | ||
| 1077 | condt = abstract_eval(stmt.args[1], s[pc], frame) | ||
| 1078 | if condt === Bottom | ||
| 1079 | break | ||
| 1080 | end | ||
| 1081 | condval = maybe_extract_const_bool(condt) | ||
| 1082 | l = stmt.args[2]::Int | ||
| 1083 | # constant conditions | ||
| 1084 | if condval === true | ||
| 1085 | elseif condval === false | ||
| 1086 | pc´ = l | ||
| 1087 | else | ||
| 1088 | # general case | ||
| 1089 | frame.handler_at[l] = frame.cur_hand | ||
| 1090 | changes_else = changes | ||
| 1091 | if isa(condt, Conditional) | ||
| 1092 | if condt.elsetype !== Any && condt.elsetype !== changes[slot_id(condt.var)] | ||
| 1093 | changes_else = StateUpdate(condt.var, VarState(condt.elsetype, false), changes_else) | ||
| 1094 | end | ||
| 1095 | if condt.vtype !== Any && condt.vtype !== changes[slot_id(condt.var)] | ||
| 1096 | changes = StateUpdate(condt.var, VarState(condt.vtype, false), changes) | ||
| 1097 | end | ||
| 1098 | end | ||
| 1099 | newstate_else = stupdate!(s[l], changes_else) | ||
| 1100 | if newstate_else !== false | ||
| 1101 | # add else branch to active IP list | ||
| 1102 | if l < frame.pc´´ | ||
| 1103 | frame.pc´´ = l | ||
| 1104 | end | ||
| 1105 | push!(W, l) | ||
| 1106 | s[l] = newstate_else | ||
| 1107 | end | ||
| 1108 | end | ||
| 1109 | elseif hd === :return | ||
| 1110 | pc´ = n + 1 | ||
| 1111 | rt = maybe_widen_conditional(abstract_eval(stmt.args[1], s[pc], frame)) | ||
| 1112 | if !isa(rt, Const) && !isa(rt, Type) | ||
| 1113 | # only propagate information we know we can store | ||
| 1114 | # and is valid inter-procedurally | ||
| 1115 | rt = widenconst(rt) | ||
| 1116 | end | ||
| 1117 | if tchanged(rt, frame.bestguess) | ||
| 1118 | # new (wider) return type for frame | ||
| 1119 | frame.bestguess = tmerge(frame.bestguess, rt) | ||
| 1120 | for (caller, caller_pc) in frame.cycle_backedges | ||
| 1121 | # notify backedges of updated type information | ||
| 1122 | typeassert(caller.stmt_types[caller_pc], VarTable) # we must have visited this statement before | ||
| 1123 | if !(caller.src.ssavaluetypes[caller_pc] === Any) | ||
| 1124 | # no reason to revisit if that call-site doesn't affect the final result | ||
| 1125 | if caller_pc < caller.pc´´ | ||
| 1126 | caller.pc´´ = caller_pc | ||
| 1127 | end | ||
| 1128 | push!(caller.ip, caller_pc) | ||
| 1129 | end | ||
| 1130 | end | ||
| 1131 | end | ||
| 1132 | elseif hd === :enter | ||
| 1133 | l = stmt.args[1]::Int | ||
| 1134 | frame.cur_hand = (l, frame.cur_hand) | ||
| 1135 | # propagate type info to exception handler | ||
| 1136 | l = frame.cur_hand[1] | ||
| 1137 | old = s[l] | ||
| 1138 | new = s[pc]::Array{Any,1} | ||
| 1139 | newstate_catch = stupdate!(old, new) | ||
| 1140 | if newstate_catch !== false | ||
| 1141 | if l < frame.pc´´ | ||
| 1142 | frame.pc´´ = l | ||
| 1143 | end | ||
| 1144 | push!(W, l) | ||
| 1145 | s[l] = newstate_catch | ||
| 1146 | end | ||
| 1147 | typeassert(s[l], VarTable) | ||
| 1148 | frame.handler_at[l] = frame.cur_hand | ||
| 1149 | elseif hd === :leave | ||
| 1150 | for i = 1:((stmt.args[1])::Int) | ||
| 1151 | frame.cur_hand = frame.cur_hand[2] | ||
| 1152 | end | ||
| 1153 | else | ||
| 1154 | if hd === :(=) | ||
| 1155 | t = abstract_eval(stmt.args[2], changes, frame) | ||
| 1156 | t === Bottom && break | ||
| 1157 | frame.src.ssavaluetypes[pc] = t | ||
| 1158 | lhs = stmt.args[1] | ||
| 1159 | if isa(lhs, Slot) | ||
| 1160 | changes = StateUpdate(lhs, VarState(t, false), changes) | ||
| 1161 | end | ||
| 1162 | elseif hd === :method | ||
| 1163 | fname = stmt.args[1] | ||
| 1164 | if isa(fname, Slot) | ||
| 1165 | changes = StateUpdate(fname, VarState(Any, false), changes) | ||
| 1166 | end | ||
| 1167 | elseif hd === :inbounds || hd === :meta || hd === :simdloop | ||
| 1168 | else | ||
| 1169 | 5 (13.51%) |
2 (40.00%)
samples spent calling
abstract_eval
t = abstract_eval(stmt, changes, frame)
|
|
| 1170 | t === Bottom && break | ||
| 1171 | if !isempty(frame.ssavalue_uses[pc]) | ||
| 1172 | record_ssa_assign(pc, t, frame) | ||
| 1173 | else | ||
| 1174 | frame.src.ssavaluetypes[pc] = t | ||
| 1175 | end | ||
| 1176 | end | ||
| 1177 | if frame.cur_hand !== () && isa(changes, StateUpdate) | ||
| 1178 | # propagate new type info to exception handler | ||
| 1179 | # the handling for Expr(:enter) propagates all changes from before the try/catch | ||
| 1180 | # so this only needs to propagate any changes | ||
| 1181 | l = frame.cur_hand[1] | ||
| 1182 | if stupdate1!(s[l]::VarTable, changes::StateUpdate) !== false | ||
| 1183 | if l < frame.pc´´ | ||
| 1184 | frame.pc´´ = l | ||
| 1185 | end | ||
| 1186 | push!(W, l) | ||
| 1187 | end | ||
| 1188 | end | ||
| 1189 | end | ||
| 1190 | |||
| 1191 | if t === nothing | ||
| 1192 | # mark other reached expressions as `Any` to indicate they don't throw | ||
| 1193 | frame.src.ssavaluetypes[pc] = Any | ||
| 1194 | end | ||
| 1195 | |||
| 1196 | pc´ > n && break # can't proceed with the fast-path fall-through | ||
| 1197 | frame.handler_at[pc´] = frame.cur_hand | ||
| 1198 | newstate = stupdate!(s[pc´], changes) | ||
| 1199 | if isa(stmt, GotoNode) && frame.pc´´ < pc´ | ||
| 1200 | # if we are processing a goto node anyways, | ||
| 1201 | # (such as a terminator for a loop, if-else, or try block), | ||
| 1202 | # consider whether we should jump to an older backedge first, | ||
| 1203 | # to try to traverse the statements in approximate dominator order | ||
| 1204 | if newstate !== false | ||
| 1205 | s[pc´] = newstate | ||
| 1206 | end | ||
| 1207 | push!(W, pc´) | ||
| 1208 | pc = frame.pc´´ | ||
| 1209 | elseif newstate !== false | ||
| 1210 | s[pc´] = newstate | ||
| 1211 | pc = pc´ | ||
| 1212 | elseif pc´ in W | ||
| 1213 | pc = pc´ | ||
| 1214 | else | ||
| 1215 | break | ||
| 1216 | end | ||
| 1217 | end | ||
| 1218 | end | ||
| 1219 | frame.dont_work_on_me = false | ||
| 1220 | nothing | ||
| 1221 | end | ||
| 1222 | |||
| 1223 | # make as much progress on `frame` as possible (by handling cycles) | ||
| 1224 |
2 (5.41%) samples spent in typeinf_nocycle
function typeinf_nocycle(frame::InferenceState)
0 (ex.), 2 (100.00%) (incl.) when called from typeinf line 15 |
||
| 1225 | 5 (13.51%) |
2 (40.00%)
samples spent calling
typeinf_local
typeinf_local(frame)
|
|
| 1226 | |||
| 1227 | # If the current frame is part of a cycle, solve the cycle before finishing | ||
| 1228 | no_active_ips_in_callers = false | ||
| 1229 | while !no_active_ips_in_callers | ||
| 1230 | no_active_ips_in_callers = true | ||
| 1231 | for caller in frame.callers_in_cycle | ||
| 1232 | caller.dont_work_on_me && return false # cycle is above us on the stack | ||
| 1233 | if caller.pc´´ <= caller.nstmts # equivalent to `isempty(caller.ip)` | ||
| 1234 | # Note that `typeinf_local(caller)` can potentially modify the other frames | ||
| 1235 | # `frame.callers_in_cycle`, which is why making incremental progress requires the | ||
| 1236 | # outer while loop. | ||
| 1237 | typeinf_local(caller) | ||
| 1238 | no_active_ips_in_callers = false | ||
| 1239 | end | ||
| 1240 | if caller.min_valid < frame.min_valid | ||
| 1241 | caller.min_valid = frame.min_valid | ||
| 1242 | end | ||
| 1243 | if caller.max_valid > frame.max_valid | ||
| 1244 | caller.max_valid = frame.max_valid | ||
| 1245 | end | ||
| 1246 | end | ||
| 1247 | end | ||
| 1248 | return true | ||
| 1249 | end |