StatProfilerHTML.jl report
Generated on ons 9 okt 2019 08:41:28
File source code
Line Exclusive Inclusive Code
1 # This file is a part of Julia. License is MIT: https://julialang.org/license
2
3 const COMPILER_TEMP_SYM = Symbol("#temp#")
4
5 # build (and start inferring) the inference frame for the linfo
6 function typeinf(result::InferenceResult, cached::Bool, params::Params)
7 frame = InferenceState(result, cached, params)
8 frame === nothing && return false
9 cached && (result.linfo.inInference = true)
10 return typeinf(frame)
11 end
12
13
3 (8.11%) samples spent in typeinf
0 (ex.), 2 (66.67%) (incl.) when called from abstract_call_method_with_const_args line 216
0 (ex.), 3 (100.00%) (incl.) when called from typeinf_ext line 574
function typeinf(frame::InferenceState)
14 cached = frame.cached
15 5 (13.51%)
2 (40.00%) samples spent calling typeinf_nocycle
typeinf_nocycle(frame) || return false # frame is now part of a higher cycle
16 # with no active ip's, frame is done
17 frames = frame.callers_in_cycle
18 isempty(frames) && push!(frames, frame)
19 for caller in frames
20 @assert !(caller.dont_work_on_me)
21 caller.dont_work_on_me = true
22 end
23 for caller in frames
24 finish(caller)
25 end
26 # collect results for the new expanded frame
27 results = InferenceResult[ frames[i].result for i in 1:length(frames) ]
28 # empty!(frames)
29 min_valid = frame.min_valid
30 max_valid = frame.max_valid
31 if cached || frame.parent !== nothing
32 for caller in results
33 opt = caller.src
34 if opt isa OptimizationState
35 1 (2.70%)
1 (100.00%) samples spent calling optimize
optimize(opt, caller.result)
36 finish(opt.src)
37 # finish updating the result struct
38 validate_code_in_debug_mode(opt.linfo, opt.src, "optimized")
39 if opt.const_api
40 if caller.result isa Const
41 caller.src = caller.result
42 else
43 @assert isconstType(caller.result)
44 caller.src = Const(caller.result.parameters[1])
45 end
46 elseif opt.src.inferred
47 caller.src = opt.src::CodeInfo # stash a copy of the code (for inlining)
48 else
49 caller.src = nothing
50 end
51 if min_valid < opt.min_valid
52 min_valid = opt.min_valid
53 end
54 if max_valid > opt.max_valid
55 max_valid = opt.max_valid
56 end
57 end
58 end
59 if cached
60 for caller in results
61 cache_result(caller, min_valid, max_valid)
62 end
63 end
64 end
65 # if we aren't cached, we don't need this edge
66 # but our caller might, so let's just make it anyways
67 for caller in frames
68 finalize_backedges(caller)
69 end
70 if max_valid == typemax(UInt)
71 for caller in frames
72 store_backedges(caller)
73 end
74 end
75 return true
76 end
77
78 # inference completed on `me`
79 # update the MethodInstance and notify the edges
80 function cache_result(result::InferenceResult, min_valid::UInt, max_valid::UInt)
81 def = result.linfo.def
82 toplevel = !isa(result.linfo.def, Method)
83 if toplevel
84 min_valid = UInt(0)
85 max_valid = UInt(0)
86 end
87
88 # check if the existing linfo metadata is also sufficient to describe the current inference result
89 # to decide if it is worth caching it again (which would also clear any generated code)
90 already_inferred = !result.linfo.inInference
91 if isdefined(result.linfo, :inferred)
92 inf = result.linfo.inferred
93 if !isa(inf, CodeInfo) || (inf::CodeInfo).inferred
94 if min_world(result.linfo) == min_valid && max_world(result.linfo) == max_valid
95 already_inferred = true
96 end
97 end
98 end
99
100 # don't store inferred code if we've decided to interpret this function
101 if !already_inferred && invoke_api(result.linfo) != 4
102 inferred_result = result.src
103 if inferred_result isa Const
104 # use constant calling convention
105 inferred_const = (result.src::Const).val
106 const_flags = 0x3
107 else
108 if isa(result.result, Const)
109 inferred_const = (result.result::Const).val
110 const_flags = 0x2
111 elseif isconstType(result.result)
112 inferred_const = result.result.parameters[1]
113 const_flags = 0x2
114 else
115 inferred_const = nothing
116 const_flags = 0x00
117 end
118 if !toplevel && inferred_result isa CodeInfo
119 cache_the_tree = result.src.inferred &&
120 (result.src.inlineable ||
121 ccall(:jl_isa_compileable_sig, Int32, (Any, Any), result.linfo.specTypes, def) != 0)
122 if cache_the_tree
123 # compress code for non-toplevel thunks
124 inferred_result = ccall(:jl_compress_ast, Any, (Any, Any), def, inferred_result)
125 else
126 inferred_result = nothing
127 end
128 end
129 end
130 if !isa(inferred_result, Union{CodeInfo, Vector{UInt8}})
131 inferred_result = nothing
132 end
133 cache = ccall(:jl_set_method_inferred, Ref{MethodInstance}, (Any, Any, Any, Any, Int32, UInt, UInt),
134 result.linfo, widenconst(result.result), inferred_const, inferred_result,
135 const_flags, min_valid, max_valid)
136 if cache !== result.linfo
137 result.linfo.inInference = false
138 result.linfo = cache
139 end
140 end
141 result.linfo.inInference = false
142 nothing
143 end
144
145 function finish(me::InferenceState)
146 # prepare to run optimization passes on fulltree
147 if me.limited && me.cached && me.parent !== nothing
148 # a top parent will be cached still, but not this intermediate work
149 # we can throw everything else away now
150 me.cached = false
151 me.linfo.inInference = false
152 me.src.inlineable = false
153 else
154 # annotate fulltree with type information
155 type_annotate!(me)
156 run_optimizer = (me.cached || me.parent !== nothing)
157 if run_optimizer
158 # construct the optimizer for later use, if we're building this IR to cache it
159 # (otherwise, we'll run the optimization passes later, outside of inference)
160 opt = OptimizationState(me)
161 me.result.src = opt
162 end
163 end
164 me.result.result = me.bestguess
165 nothing
166 end
167
168 function finish(src::CodeInfo)
169 # convert all type information into the form consumed by the cache for inlining and code-generation
170 widen_all_consts!(src)
171 src.inferred = true
172 nothing
173 end
174
175 function finalize_backedges(me::InferenceState)
176 # update all of the (cycle) callers with real backedges
177 # by traversing the temporary list of backedges
178 for (i, _) in me.cycle_backedges
179 add_backedge!(me.linfo, i)
180 end
181
182 # finalize and record the linfo result
183 me.inferred = true
184 nothing
185 end
186
187 # add the real backedges
188 function store_backedges(frame::InferenceState)
189 toplevel = !isa(frame.linfo.def, Method)
190 if !toplevel && (frame.cached || frame.parent !== nothing)
191 caller = frame.result.linfo
192 for edges in frame.stmt_edges
193 i = 1
194 while i <= length(edges)
195 to = edges[i]
196 if isa(to, MethodInstance)
197 ccall(:jl_method_instance_add_backedge, Cvoid, (Any, Any), to, caller)
198 i += 1
199 else
200 typeassert(to, Core.MethodTable)
201 typ = edges[i + 1]
202 ccall(:jl_method_table_add_backedge, Cvoid, (Any, Any, Any), to, typ, caller)
203 i += 2
204 end
205 end
206 end
207 end
208 end
209
210 # widen all Const elements in type annotations
211 function widen_all_consts!(src::CodeInfo)
212 for i = 1:length(src.ssavaluetypes)
213 src.ssavaluetypes[i] = widenconst(src.ssavaluetypes[i])
214 end
215
216 for i = 1:length(src.code)
217 x = src.code[i]
218 if isa(x, PiNode)
219 src.code[i] = PiNode(x.val, widenconst(x.typ))
220 end
221 end
222
223 return src
224 end
225
226 maybe_widen_conditional(@nospecialize vt) = vt
227 function maybe_widen_conditional(vt::Conditional)
228 if vt.vtype === Bottom
229 return Const(false)
230 elseif vt.elsetype === Bottom
231 return Const(true)
232 else
233 return Bool
234 end
235 end
236
237 function annotate_slot_load!(e::Expr, vtypes::VarTable, sv::InferenceState, undefs::Array{Bool,1})
238 head = e.head
239 i0 = 1
240 if is_meta_expr_head(head) || head === :const
241 return
242 end
243 if head === :(=) || head === :method
244 i0 = 2
245 end
246 for i = i0:length(e.args)
247 subex = e.args[i]
248 if isa(subex, Expr)
249 annotate_slot_load!(subex, vtypes, sv, undefs)
250 elseif isa(subex, Slot)
251 e.args[i] = visit_slot_load!(subex, vtypes, sv, undefs)
252 end
253 end
254 end
255
256 function visit_slot_load!(sl::Slot, vtypes::VarTable, sv::InferenceState, undefs::Array{Bool,1})
257 id = slot_id(sl)
258 s = vtypes[id]
259 vt = maybe_widen_conditional(s.typ)
260 if s.undef
261 # find used-undef variables
262 undefs[id] = true
263 end
264 # add type annotations where needed
265 if !(sv.slottypes[id] ⊑ vt)
266 return TypedSlot(id, vt)
267 end
268 return sl
269 end
270
271 function record_slot_assign!(sv::InferenceState)
272 # look at all assignments to slots
273 # and union the set of types stored there
274 # to compute a lower bound on the storage required
275 states = sv.stmt_types
276 body = sv.src.code::Vector{Any}
277 slottypes = sv.slottypes::Vector{Any}
278 for i = 1:length(body)
279 expr = body[i]
280 st_i = states[i]
281 # find all reachable assignments to locals
282 if isa(st_i, VarTable) && isa(expr, Expr) && expr.head === :(=)
283 lhs = expr.args[1]
284 rhs = expr.args[2]
285 if isa(lhs, Slot)
286 vt = widenconst(sv.src.ssavaluetypes[i])
287 if vt !== Bottom
288 id = slot_id(lhs)
289 otherTy = slottypes[id]
290 if otherTy === Bottom
291 slottypes[id] = vt
292 elseif otherTy === Any
293 slottypes[id] = Any
294 else
295 slottypes[id] = tmerge(otherTy, vt)
296 end
297 end
298 end
299 end
300 end
301 end
302
303 # annotate types of all symbols in AST
304 function type_annotate!(sv::InferenceState)
305 # delete dead statements only if we're building this IR to cache it
306 # (otherwise, we'll run the optimization passes later, outside of inference)
307 run_optimizer = (sv.cached || sv.parent !== nothing)
308
309 # remove all unused ssa values
310 gt = sv.src.ssavaluetypes
311 for j = 1:length(gt)
312 if gt[j] === NOT_FOUND
313 gt[j] = Union{}
314 end
315 gt[j] = maybe_widen_conditional(gt[j])
316 end
317
318 # compute the required type for each slot
319 # to hold all of the items assigned into it
320 record_slot_assign!(sv)
321
322 # annotate variables load types
323 # remove dead code optimization
324 # and compute which variables may be used undef
325 src = sv.src
326 states = sv.stmt_types
327 nargs = sv.nargs
328 nslots = length(states[1])
329 undefs = fill(false, nslots)
330 body = src.code::Array{Any,1}
331 nexpr = length(body)
332
333 # replace gotoifnot with its condition if the branch target is unreachable
334 for i = 1:nexpr
335 expr = body[i]
336 if isa(expr, Expr) && expr.head === :gotoifnot
337 tgt = expr.args[2]::Int
338 if !isa(states[tgt], VarTable)
339 body[i] = expr.args[1]
340 end
341 end
342 end
343
344 i = 1
345 oldidx = 0
346 changemap = fill(0, nexpr)
347
348 while i <= nexpr
349 oldidx += 1
350 st_i = states[i]
351 expr = body[i]
352 if isa(st_i, VarTable)
353 # st_i === () => unreached statement (see issue #7836)
354 if isa(expr, Expr)
355 annotate_slot_load!(expr, st_i, sv, undefs)
356 elseif isa(expr, Slot)
357 body[i] = visit_slot_load!(expr, st_i, sv, undefs)
358 end
359 else
360 if isa(expr, Expr) && is_meta_expr_head(expr.head)
361 # keep any lexically scoped expressions
362 elseif run_optimizer
363 deleteat!(body, i)
364 deleteat!(states, i)
365 deleteat!(src.ssavaluetypes, i)
366 deleteat!(src.codelocs, i)
367 nexpr -= 1
368 if oldidx < length(changemap)
369 changemap[oldidx + 1] = -1
370 end
371 continue
372 else
373 body[i] = Const(expr) # annotate that this statement actually is dead
374 end
375 end
376 i += 1
377 end
378
379 if run_optimizer
380 renumber_ir_elements!(body, changemap)
381 end
382
383 # finish marking used-undef variables
384 for j = 1:nslots
385 if undefs[j]
386 src.slotflags[j] |= SLOT_USEDUNDEF | SLOT_STATICUNDEF
387 end
388 end
389 nothing
390 end
391
392 # at the end, all items in b's cycle
393 # will now be added to a's cycle
394 function union_caller_cycle!(a::InferenceState, b::InferenceState)
395 callers_in_cycle = b.callers_in_cycle
396 b.parent = a.parent
397 b.callers_in_cycle = a.callers_in_cycle
398 contains_is(a.callers_in_cycle, b) || push!(a.callers_in_cycle, b)
399 if callers_in_cycle !== a.callers_in_cycle
400 for caller in callers_in_cycle
401 if caller !== b
402 caller.parent = a.parent
403 caller.callers_in_cycle = a.callers_in_cycle
404 push!(a.callers_in_cycle, caller)
405 end
406 end
407 end
408 return
409 end
410
411 function merge_call_chain!(parent::InferenceState, ancestor::InferenceState, child::InferenceState, limited::Bool)
412 # add backedge of parent <- child
413 # then add all backedges of parent <- parent.parent
414 # and merge all of the callers into ancestor.callers_in_cycle
415 # and ensure that walking the parent list will get the same result (DAG) from everywhere
416 while true
417 add_cycle_backedge!(child, parent, parent.currpc)
418 union_caller_cycle!(ancestor, child)
419 child = parent
420 parent = child.parent
421 child === ancestor && break
422 end
423 if limited
424 for caller in ancestor.callers_in_cycle
425 caller.limited = true
426 end
427 end
428 end
429
430 # Walk through `linfo`'s upstream call chain, starting at `parent`. If a parent
431 # frame matching `linfo` is encountered, then there is a cycle in the call graph
432 # (i.e. `linfo` is a descendant callee of itself). Upon encountering this cycle,
433 # we "resolve" it by merging the call chain, which entails unioning each intermediary
434 # frame's `callers_in_cycle` field and adding the appropriate backedges. Finally,
435 # we return `linfo`'s pre-existing frame. If no cycles are found, `nothing` is
436 # returned instead.
437 function resolve_call_cycle!(linfo::MethodInstance, parent::InferenceState)
438 frame = parent
439 uncached = false
440 limited = false
441 while isa(frame, InferenceState)
442 uncached |= !frame.cached # ensure we never add an uncached frame to a cycle
443 limited |= frame.limited
444 if frame.linfo === linfo
445 uncached && return true
446 merge_call_chain!(parent, frame, frame, limited)
447 return frame
448 end
449 for caller in frame.callers_in_cycle
450 if caller.linfo === linfo
451 uncached && return true
452 merge_call_chain!(parent, frame, caller, limited)
453 return caller
454 end
455 end
456 frame = frame.parent
457 end
458 return false
459 end
460
461 # compute (and cache) an inferred AST and return the current best estimate of the result type
462 function typeinf_edge(method::Method, @nospecialize(atypes), sparams::SimpleVector, caller::InferenceState)
463 code = code_for_method(method, atypes, sparams, caller.params.world)
464 code === nothing && return Any, nothing
465 code = code::MethodInstance
466 if isdefined(code, :inferred)
467 # return rettype if the code is already inferred
468 # staged functions make this hard since they have two "inferred" conditions,
469 # so need to check whether the code itself is also inferred
470 inf = code.inferred
471 if !isa(inf, CodeInfo) || (inf::CodeInfo).inferred
472 if isdefined(code, :inferred_const)
473 return AbstractEvalConstant(code.inferred_const), code
474 else
475 return code.rettype, code
476 end
477 end
478 end
479 if !caller.cached && caller.parent === nothing
480 # this caller exists to return to the user
481 # (if we asked resolve_call_cyle, it might instead detect that there is a cycle that it can't merge)
482 frame = false
483 else
484 frame = resolve_call_cycle!(code, caller)
485 end
486 if frame === false
487 # completely new
488 code.inInference = true
489 result = InferenceResult(code)
490 frame = InferenceState(result, #=cached=#true, caller.params) # always use the cache for edge targets
491 if frame === nothing
492 # can't get the source for this, so we know nothing
493 code.inInference = false
494 return Any, nothing
495 end
496 if caller.cached || caller.limited # don't involve uncached functions in cycle resolution
497 frame.parent = caller
498 end
499 typeinf(frame)
500 return frame.bestguess, frame.inferred ? frame.linfo : nothing
501 elseif frame === true
502 # unresolvable cycle
503 return Any, nothing
504 end
505 frame = frame::InferenceState
506 return frame.bestguess, nothing
507 end
508
509
510 #### entry points for inferring a MethodInstance given a type signature ####
511
512 # compute an inferred AST and return type
513 function typeinf_code(method::Method, @nospecialize(atypes), sparams::SimpleVector, run_optimizer::Bool, params::Params)
514 code = code_for_method(method, atypes, sparams, params.world)
515 code === nothing && return (nothing, Any)
516 ccall(:jl_typeinf_begin, Cvoid, ())
517 result = InferenceResult(code)
518 frame = InferenceState(result, false, params)
519 frame === nothing && return (nothing, Any)
520 if typeinf(frame) && run_optimizer
521 opt = OptimizationState(frame)
522 optimize(opt, result.result)
523 opt.src.inferred = true
524 end
525 ccall(:jl_typeinf_end, Cvoid, ())
526 frame.inferred || return (nothing, Any)
527 return (frame.src, widenconst(result.result))
528 end
529
530 # compute (and cache) an inferred AST and return type
531
3 (8.11%) samples spent in typeinf_ext
0 (ex.), 3 (100.00%) (incl.) when called from typeinf_ext line 611
function typeinf_ext(linfo::MethodInstance, params::Params)
532 for i = 1:2 # test-and-lock-and-test
533 i == 2 && ccall(:jl_typeinf_begin, Cvoid, ())
534 if isdefined(linfo, :inferred)
535 # see if this code already exists in the cache
536 # staged functions make this hard since they have two "inferred" conditions,
537 # so need to check whether the code itself is also inferred
538 if min_world(linfo) <= params.world <= max_world(linfo)
539 inf = linfo.inferred
540 if invoke_api(linfo) == 2
541 method = linfo.def::Method
542 tree = ccall(:jl_new_code_info_uninit, Ref{CodeInfo}, ())
543 tree.code = Any[ Expr(:return, quoted(linfo.inferred_const)) ]
544 tree.method_for_inference_limit_heuristics = nothing
545 tree.slotnames = Any[ COMPILER_TEMP_SYM for i = 1:method.nargs ]
546 tree.slotflags = fill(0x00, Int(method.nargs))
547 tree.ssavaluetypes = 0
548 tree.codelocs = Int32[1]
549 tree.linetable = [LineInfoNode(method.module, method.name, method.file, Int(method.line), 0)]
550 tree.inferred = true
551 tree.ssaflags = UInt8[]
552 tree.pure = true
553 tree.inlineable = true
554 i == 2 && ccall(:jl_typeinf_end, Cvoid, ())
555 return svec(linfo, tree)
556 elseif isa(inf, CodeInfo)
557 if inf.inferred
558 i == 2 && ccall(:jl_typeinf_end, Cvoid, ())
559 return svec(linfo, inf)
560 end
561 elseif isa(inf, Vector{UInt8})
562 inf = uncompressed_ast(linfo.def::Method, inf)
563 if inf.inferred
564 i == 2 && ccall(:jl_typeinf_end, Cvoid, ())
565 return svec(linfo, inf)
566 end
567 end
568 end
569 end
570 end
571 linfo.inInference = true
572 frame = InferenceState(InferenceResult(linfo), #=cached=#true, params)
573 frame === nothing && return svec(nothing, nothing)
574 3 (8.11%)
3 (100.00%) samples spent calling typeinf
typeinf(frame)
575 ccall(:jl_typeinf_end, Cvoid, ())
576 frame.src.inferred || return svec(nothing, nothing)
577 return svec(frame.result.linfo, frame.src)
578 end
579
580 # compute (and cache) an inferred AST and return the inferred return type
581 function typeinf_type(method::Method, @nospecialize(atypes), sparams::SimpleVector, params::Params)
582 if contains_is(unwrap_unionall(atypes).parameters, Union{})
583 return Union{}
584 end
585 code = code_for_method(method, atypes, sparams, params.world)
586 code === nothing && return nothing
587 code = code::MethodInstance
588 for i = 1:2 # test-and-lock-and-test
589 i == 2 && ccall(:jl_typeinf_begin, Cvoid, ())
590 if isdefined(code, :inferred)
591 # see if this rettype already exists in the cache
592 # staged functions make this hard since they have two "inferred" conditions,
593 # so need to check whether the code itself is also inferred
594 inf = code.inferred
595 if !isa(inf, CodeInfo) || (inf::CodeInfo).inferred
596 i == 2 && ccall(:jl_typeinf_end, Cvoid, ())
597 return code.rettype
598 end
599 end
600 end
601 frame = InferenceResult(code)
602 typeinf(frame, true, params)
603 ccall(:jl_typeinf_end, Cvoid, ())
604 frame.result isa InferenceState && return nothing
605 return widenconst(frame.result)
606 end
607
608
3 (8.11%) samples spent in typeinf_ext
0 (ex.), 3 (100.00%) (incl.) when called from StringVector line 71
@timeit function typeinf_ext(linfo::MethodInstance, world::UInt)
609 if isa(linfo.def, Method)
610 # method lambda - infer this specialization via the method cache
611 3 (8.11%)
3 (100.00%) samples spent calling typeinf_ext
return typeinf_ext(linfo, Params(world))
612 else
613 # toplevel lambda - infer directly
614 ccall(:jl_typeinf_begin, Cvoid, ())
615 result = InferenceResult(linfo)
616 frame = InferenceState(result, linfo.inferred::CodeInfo,
617 #=cached=#true, Params(world))
618 typeinf(frame)
619 ccall(:jl_typeinf_end, Cvoid, ())
620 @assert frame.inferred # TODO: deal with this better
621 @assert frame.linfo === linfo
622 linfo.rettype = widenconst(frame.bestguess)
623 return svec(linfo, frame.src)
624 end
625 end
626
627
628 function return_type(@nospecialize(f), @nospecialize(t))
629 params = Params(ccall(:jl_get_tls_world_age, UInt, ()))
630 rt = Union{}
631 if isa(f, Builtin)
632 rt = builtin_tfunction(f, Any[t.parameters...], nothing, params)
633 if isa(rt, TypeVar)
634 rt = rt.ub
635 else
636 rt = widenconst(rt)
637 end
638 else
639 for m in _methods(f, t, -1, params.world)
640 ty = typeinf_type(m[3], m[1], m[2], params)
641 ty === nothing && return Any
642 rt = tmerge(rt, ty)
643 rt === Any && break
644 end
645 end
646 return rt
647 end