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 @inline isexpr(@nospecialize(stmt), head::Symbol) = isa(stmt, Expr) && stmt.head === head
4 @eval Core.UpsilonNode() = $(Expr(:new, Core.UpsilonNode))
5 Core.PhiNode() = Core.PhiNode(Any[], Any[])
6
7 struct Argument
8 n::Int
9 end
10
11 struct GotoIfNot
12 cond::Any
13 dest::Int
14 GotoIfNot(@nospecialize(cond), dest::Int) = new(cond, dest)
15 end
16
17 struct ReturnNode
18 val::Any
19 ReturnNode(@nospecialize(val)) = new(val)
20 # unassigned val indicates unreachable
21 ReturnNode() = new()
22 end
23
24 """
25 Like UnitRange{Int}, but can handle the `last` field, being temporarily
26 < first (this can happen during compacting)
27 """
28 struct StmtRange <: AbstractUnitRange{Int}
29 first::Int
30 last::Int
31 end
32 first(r::StmtRange) = r.first
33 last(r::StmtRange) = r.last
34 iterate(r::StmtRange, state=0) = (r.last - r.first < state) ? nothing : (r.first + state, state + 1)
35
36 StmtRange(range::UnitRange{Int}) = StmtRange(first(range), last(range))
37
38 struct BasicBlock
39 stmts::StmtRange
40 preds::Vector{Int}
41 succs::Vector{Int}
42 end
43 function BasicBlock(stmts::StmtRange)
44 return BasicBlock(stmts, Int[], Int[])
45 end
46 function BasicBlock(old_bb, stmts)
47 return BasicBlock(stmts, old_bb.preds, old_bb.succs)
48 end
49 copy(bb::BasicBlock) = BasicBlock(bb.stmts, copy(bb.preds), copy(bb.succs))
50
51 struct CFG
52 blocks::Vector{BasicBlock}
53 index::Vector{Int} # map from instruction => basic-block number
54 # TODO: make this O(1) instead of O(log(n_blocks))?
55 end
56 copy(c::CFG) = CFG(copy(c.blocks), copy(c.index))
57
58 function block_for_inst(index::Vector{Int}, inst::Int)
59 return searchsortedfirst(index, inst, lt=(<=))
60 end
61 block_for_inst(cfg::CFG, inst::Int) = block_for_inst(cfg.index, inst)
62
63 function basic_blocks_starts(stmts::Vector{Any})
64 jump_dests = BitSet()
65 push!(jump_dests, 1) # function entry point
66 # First go through and compute jump destinations
67 for idx in 1:length(stmts)
68 stmt = stmts[idx]
69 # Terminators
70 if isa(stmt, GotoIfNot)
71 push!(jump_dests, idx+1)
72 push!(jump_dests, stmt.dest)
73 elseif isa(stmt, ReturnNode)
74 idx < length(stmts) && push!(jump_dests, idx+1)
75 elseif isa(stmt, GotoNode)
76 # This is a fake dest to force the next stmt to start a bb
77 idx < length(stmts) && push!(jump_dests, idx+1)
78 push!(jump_dests, stmt.label)
79 elseif isa(stmt, Expr)
80 if stmt.head === :leave
81 # :leave terminates a BB
82 push!(jump_dests, idx+1)
83 elseif stmt.head == :enter
84 # :enter starts/ends a BB
85 push!(jump_dests, idx)
86 push!(jump_dests, idx+1)
87 # The catch block is a jump dest
88 push!(jump_dests, stmt.args[1])
89 elseif stmt.head === :gotoifnot
90 # also tolerate expr form of IR
91 push!(jump_dests, idx+1)
92 push!(jump_dests, stmt.args[2])
93 elseif stmt.head === :return
94 # also tolerate expr form of IR
95 # This is a fake dest to force the next stmt to start a bb
96 idx < length(stmts) && push!(jump_dests, idx+1)
97 end
98 end
99 end
100 # and add add one more basic block start after the last statement
101 for i = length(stmts):-1:1
102 if stmts[i] != nothing
103 push!(jump_dests, i+1)
104 break
105 end
106 end
107 return jump_dests
108 end
109
110 function compute_basic_blocks(stmts::Vector{Any})
111 bb_starts = basic_blocks_starts(stmts)
112 # Compute ranges
113 pop!(bb_starts, 1)
114 basic_block_index = collect(bb_starts)
115 blocks = BasicBlock[]
116 sizehint!(blocks, length(basic_block_index))
117 let first = 1
118 for last in basic_block_index
119 push!(blocks, BasicBlock(StmtRange(first, last - 1)))
120 first = last
121 end
122 end
123 # Compute successors/predecessors
124 for (num, b) in enumerate(blocks)
125 terminator = stmts[last(b.stmts)]
126 if isa(terminator, ReturnNode)
127 # return never has any successors
128 continue
129 end
130 if isa(terminator, GotoNode)
131 block′ = block_for_inst(basic_block_index, terminator.label)
132 push!(blocks[block′].preds, num)
133 push!(b.succs, block′)
134 continue
135 end
136 # Conditional Branch
137 if isa(terminator, GotoIfNot)
138 block′ = block_for_inst(basic_block_index, terminator.dest)
139 if block′ == num + 1
140 # This GotoIfNot acts like a noop - treat it as such.
141 # We will drop it during SSA renaming
142 else
143 push!(blocks[block′].preds, num)
144 push!(b.succs, block′)
145 end
146 elseif isa(terminator, Expr) && terminator.head == :enter
147 # :enter gets a virtual edge to the exception handler and
148 # the exception handler gets a virtual edge from outside
149 # the function.
150 # See the devdocs on exception handling in SSA form (or
151 # bug Keno to write them, if you're reading this and they
152 # don't exist)
153 block′ = block_for_inst(basic_block_index, terminator.args[1])
154 push!(blocks[block′].preds, num)
155 push!(blocks[block′].preds, 0)
156 push!(b.succs, block′)
157 end
158 # statement fall-through
159 if num + 1 <= length(blocks)
160 push!(blocks[num + 1].preds, num)
161 push!(b.succs, num + 1)
162 end
163 end
164 return CFG(blocks, basic_block_index)
165 end
166
167 function first_insert_for_bb(code, cfg::CFG, block::Int)
168 for idx in cfg.blocks[block].stmts
169 stmt = code[idx]
170 if !isa(stmt, PhiNode)
171 return idx
172 end
173 end
174 end
175
176 struct NewNode
177 # Insertion position (interpretation depends on which array this is in)
178 pos::Int
179 # Place the new instruction after this instruction (but in the same BB if this is an implicit terminator)
180 attach_after::Bool
181 # The type of the instruction to insert
182 typ::Any
183 # The node itself
184 node::Any
185 # The index into the line number table of this entry
186 line::Int32
187
188 NewNode(pos::Int, attach_after::Bool, @nospecialize(typ), @nospecialize(node), line::Int32) =
189 new(pos, attach_after, typ, node, line)
190 end
191
192 struct IRCode
193 stmts::Vector{Any}
194 types::Vector{Any}
195 lines::Vector{Int32}
196 flags::Vector{UInt8}
197 argtypes::Vector{Any}
198 spvals::SimpleVector
199 linetable::Vector{LineInfoNode}
200 cfg::CFG
201 new_nodes::Vector{NewNode}
202 meta::Vector{Any}
203
204 function IRCode(stmts::Vector{Any}, types::Vector{Any}, lines::Vector{Int32}, flags::Vector{UInt8},
205 cfg::CFG, linetable::Vector{LineInfoNode}, argtypes::Vector{Any}, meta::Vector{Any},
206 spvals::SimpleVector)
207 return new(stmts, types, lines, flags, argtypes, spvals, linetable, cfg, NewNode[], meta)
208 end
209 function IRCode(ir::IRCode, stmts::Vector{Any}, types::Vector{Any}, lines::Vector{Int32}, flags::Vector{UInt8},
210 cfg::CFG, new_nodes::Vector{NewNode})
211 return new(stmts, types, lines, flags, ir.argtypes, ir.spvals, ir.linetable, cfg, new_nodes, ir.meta)
212 end
213 end
214 copy(code::IRCode) = IRCode(code, copy(code.stmts), copy(code.types),
215 copy(code.lines), copy(code.flags), copy(code.cfg), copy(code.new_nodes))
216
217 function getindex(x::IRCode, s::SSAValue)
218 if s.id <= length(x.stmts)
219 return x.stmts[s.id]
220 else
221 return x.new_nodes[s.id - length(x.stmts)].node
222 end
223 end
224
225 function setindex!(x::IRCode, @nospecialize(repl), s::SSAValue)
226 @assert s.id <= length(x.stmts)
227 x.stmts[s.id] = repl
228 nothing
229 end
230
231
232 struct OldSSAValue
233 id::Int
234 end
235
236 struct NewSSAValue
237 id::Int
238 end
239
240 const AnySSAValue = Union{SSAValue, OldSSAValue, NewSSAValue}
241
242 mutable struct UseRef
243 stmt::Any
244 op::Int
245 UseRef(@nospecialize(a)) = new(a, 0)
246 end
247 struct UseRefIterator
248 use::Tuple{UseRef, Nothing}
249 relevant::Bool
250 UseRefIterator(@nospecialize(a), relevant::Bool) = new((UseRef(a), nothing), relevant)
251 end
252 getindex(it::UseRefIterator) = it.use[1].stmt
253
254 # TODO: stack-allocation
255 #struct UseRef
256 # urs::UseRefIterator
257 # use::Int
258 #end
259
260 struct OOBToken
261 end
262
263 struct UndefToken
264 end
265
266 function getindex(x::UseRef)
267 stmt = x.stmt
268 if isa(stmt, Expr) && stmt.head === :(=)
269 rhs = stmt.args[2]
270 if isa(rhs, Expr)
271 if is_relevant_expr(rhs)
272 x.op > length(rhs.args) && return OOBToken()
273 return rhs.args[x.op]
274 end
275 end
276 x.op == 1 || return OOBToken()
277 return rhs
278 elseif isa(stmt, Expr) # @assert is_relevant_expr(stmt)
279 x.op > length(stmt.args) && return OOBToken()
280 return stmt.args[x.op]
281 elseif isa(stmt, GotoIfNot)
282 x.op == 1 || return OOBToken()
283 return stmt.cond
284 elseif isa(stmt, ReturnNode)
285 isdefined(stmt, :val) || return OOBToken()
286 x.op == 1 || return OOBToken()
287 return stmt.val
288 elseif isa(stmt, PiNode)
289 isdefined(stmt, :val) || return OOBToken()
290 x.op == 1 || return OOBToken()
291 return stmt.val
292 elseif isa(stmt, UpsilonNode)
293 isdefined(stmt, :val) || return OOBToken()
294 x.op == 1 || return OOBToken()
295 return stmt.val
296 elseif isa(stmt, PhiNode)
297 x.op > length(stmt.values) && return OOBToken()
298 isassigned(stmt.values, x.op) || return UndefToken()
299 return stmt.values[x.op]
300 elseif isa(stmt, PhiCNode)
301 x.op > length(stmt.values) && return OOBToken()
302 isassigned(stmt.values, x.op) || return UndefToken()
303 return stmt.values[x.op]
304 else
305 return OOBToken()
306 end
307 end
308
309 function is_relevant_expr(e::Expr)
310 return e.head in (:call, :invoke, :new, :(=), :(&),
311 :gc_preserve_begin, :gc_preserve_end,
312 :foreigncall, :isdefined, :copyast,
313 :undefcheck, :throw_undef_if_not,
314 :cfunction, :method,
315 #=legacy IR format support=# :gotoifnot, :return)
316 end
317
318 function setindex!(x::UseRef, @nospecialize(v))
319 stmt = x.stmt
320 if isa(stmt, Expr) && stmt.head === :(=)
321 rhs = stmt.args[2]
322 if isa(rhs, Expr)
323 if is_relevant_expr(rhs)
324 x.op > length(rhs.args) && throw(BoundsError())
325 rhs.args[x.op] = v
326 return v
327 end
328 end
329 x.op == 1 || throw(BoundsError())
330 stmt.args[2] = v
331 elseif isa(stmt, Expr) # @assert is_relevant_expr(stmt)
332 x.op > length(stmt.args) && throw(BoundsError())
333 stmt.args[x.op] = v
334 elseif isa(stmt, GotoIfNot)
335 x.op == 1 || throw(BoundsError())
336 x.stmt = GotoIfNot(v, stmt.dest)
337 elseif isa(stmt, ReturnNode)
338 x.op == 1 || throw(BoundsError())
339 x.stmt = typeof(stmt)(v)
340 elseif isa(stmt, UpsilonNode)
341 x.op == 1 || throw(BoundsError())
342 x.stmt = typeof(stmt)(v)
343 elseif isa(stmt, PiNode)
344 x.op == 1 || throw(BoundsError())
345 x.stmt = typeof(stmt)(v, stmt.typ)
346 elseif isa(stmt, PhiNode)
347 x.op > length(stmt.values) && throw(BoundsError())
348 isassigned(stmt.values, x.op) || throw(BoundsError())
349 stmt.values[x.op] = v
350 elseif isa(stmt, PhiCNode)
351 x.op > length(stmt.values) && throw(BoundsError())
352 isassigned(stmt.values, x.op) || throw(BoundsError())
353 stmt.values[x.op] = v
354 else
355 throw(BoundsError())
356 end
357 return x
358 end
359
360 function userefs(@nospecialize(x))
361 relevant = (isa(x, Expr) && is_relevant_expr(x)) ||
362 isa(x, GotoIfNot) || isa(x, ReturnNode) ||
363 isa(x, PiNode) || isa(x, PhiNode) || isa(x, PhiCNode) || isa(x, UpsilonNode)
364 return UseRefIterator(x, relevant)
365 end
366
367 iterate(it::UseRefIterator) = (it.use[1].op = 0; iterate(it, nothing))
368 @noinline function iterate(it::UseRefIterator, ::Nothing)
369 it.relevant || return nothing
370 use = it.use[1]
371 while true
372 use.op += 1
373 y = use[]
374 y === OOBToken() && return nothing
375 y === UndefToken() || return it.use
376 end
377 end
378
379 # This function is used from the show code, which may have a different
380 # `push!`/`used` type since it's in Base.
381 function scan_ssa_use!(push!, used, @nospecialize(stmt))
382 if isa(stmt, SSAValue)
383 push!(used, stmt.id)
384 end
385 for useref in userefs(stmt)
386 val = useref[]
387 if isa(val, SSAValue)
388 push!(used, val.id)
389 end
390 end
391 end
392
393 # Manually specialized copy of the above with push! === Compiler.push!
394 function scan_ssa_use!(used::IdSet, @nospecialize(stmt))
395 if isa(stmt, SSAValue)
396 push!(used, stmt.id)
397 end
398 for useref in userefs(stmt)
399 val = useref[]
400 if isa(val, SSAValue)
401 push!(used, val.id)
402 end
403 end
404 end
405
406 function ssamap(f, @nospecialize(stmt))
407 urs = userefs(stmt)
408 for op in urs
409 val = op[]
410 if isa(val, SSAValue)
411 op[] = f(val)
412 end
413 end
414 return urs[]
415 end
416
417 function foreachssa(f, @nospecialize(stmt))
418 for op in userefs(stmt)
419 val = op[]
420 if isa(val, SSAValue)
421 f(val)
422 end
423 end
424 end
425
426 function insert_node!(ir::IRCode, pos::Int, @nospecialize(typ), @nospecialize(val), attach_after::Bool=false)
427 line = ir.lines[pos]
428 push!(ir.new_nodes, NewNode(pos, attach_after, typ, val, line))
429 return SSAValue(length(ir.stmts) + length(ir.new_nodes))
430 end
431
432 # For bootstrapping
433 function my_sortperm(v)
434 p = Vector{Int}(undef, length(v))
435 for i = 1:length(v)
436 p[i] = i
437 end
438 sort!(p, Sort.DEFAULT_UNSTABLE, Order.Perm(Sort.Forward,v))
439 p
440 end
441
442 mutable struct IncrementalCompact
443 ir::IRCode
444 result::Vector{Any}
445 result_types::Vector{Any}
446 result_lines::Vector{Int32}
447 result_flags::Vector{UInt8}
448 result_bbs::Vector{BasicBlock}
449 ssa_rename::Vector{Any}
450 used_ssas::Vector{Int}
451 late_fixup::Vector{Int}
452 # This could be Stateful, but bootstrapping doesn't like that
453 perm::Vector{Int}
454 new_nodes_idx::Int
455 # This supports insertion while compacting
456 new_new_nodes::Vector{NewNode} # New nodes that were before the compaction point at insertion time
457 # TODO: Switch these two to a min-heap of some sort
458 pending_nodes::Vector{NewNode} # New nodes that were after the compaction point at insertion time
459 pending_perm::Vector{Int}
460 # State
461 idx::Int
462 result_idx::Int
463 active_result_bb::Int
464 renamed_new_nodes::Bool
465 function IncrementalCompact(code::IRCode)
466 # Sort by position with attach after nodes affter regular ones
467 perm = my_sortperm(Int[(code.new_nodes[i].pos*2 + Int(code.new_nodes[i].attach_after)) for i in 1:length(code.new_nodes)])
468 new_len = length(code.stmts) + length(code.new_nodes)
469 result = Array{Any}(undef, new_len)
470 result_types = Array{Any}(undef, new_len)
471 result_lines = fill(Int32(0), new_len)
472 result_flags = fill(0x00, new_len)
473 used_ssas = fill(0, new_len)
474 ssa_rename = Any[SSAValue(i) for i = 1:new_len]
475 late_fixup = Vector{Int}()
476 new_new_nodes = NewNode[]
477 pending_nodes = NewNode[]
478 pending_perm = Int[]
479 return new(code, result, result_types, result_lines, result_flags, code.cfg.blocks, ssa_rename, used_ssas, late_fixup, perm, 1,
480 new_new_nodes, pending_nodes, pending_perm,
481 1, 1, 1, false)
482 end
483
484 # For inlining
485 function IncrementalCompact(parent::IncrementalCompact, code::IRCode, result_offset)
486 perm = my_sortperm(Int[code.new_nodes[i].pos for i in 1:length(code.new_nodes)])
487 new_len = length(code.stmts) + length(code.new_nodes)
488 ssa_rename = Any[SSAValue(i) for i = 1:new_len]
489 used_ssas = fill(0, new_len)
490 late_fixup = Vector{Int}()
491 new_new_nodes = NewNode[]
492 pending_nodes = NewNode[]
493 pending_perm = Int[]
494 return new(code, parent.result, parent.result_types, parent.result_lines, parent.result_flags,
495 parent.result_bbs, ssa_rename, parent.used_ssas,
496 late_fixup, perm, 1,
497 new_new_nodes, pending_nodes, pending_perm,
498 1, result_offset, parent.active_result_bb, false)
499 end
500 end
501
502 struct TypesView
503 ir::Union{IRCode, IncrementalCompact}
504 end
505 types(ir::Union{IRCode, IncrementalCompact}) = TypesView(ir)
506
507 function getindex(compact::IncrementalCompact, idx::Int)
508 if idx < compact.result_idx
509 return compact.result[idx]
510 else
511 return compact.ir.stmts[idx]
512 end
513 end
514
515 function getindex(compact::IncrementalCompact, ssa::SSAValue)
516 @assert ssa.id < compact.result_idx
517 return compact.result[ssa.id]
518 end
519
520 function getindex(compact::IncrementalCompact, ssa::OldSSAValue)
521 id = ssa.id
522 if id <= length(compact.ir.stmts)
523 return compact.ir.stmts[id]
524 end
525 id -= length(compact.ir.stmts)
526 if id <= length(compact.ir.new_nodes)
527 return compact.ir.new_nodes[id].node
528 end
529 id -= length(compact.ir.new_nodes)
530 return compact.pending_nodes[id].node
531 end
532
533 function getindex(compact::IncrementalCompact, ssa::NewSSAValue)
534 return compact.new_new_nodes[ssa.id].node
535 end
536
537 function count_added_node!(compact::IncrementalCompact, @nospecialize(v))
538 needs_late_fixup = isa(v, NewSSAValue)
539 if isa(v, SSAValue)
540 compact.used_ssas[v.id] += 1
541 else
542 for ops in userefs(v)
543 val = ops[]
544 if isa(val, SSAValue)
545 compact.used_ssas[val.id] += 1
546 elseif isa(val, NewSSAValue)
547 needs_late_fixup = true
548 end
549 end
550 end
551 needs_late_fixup
552 end
553
554 function resort_pending!(compact)
555 sort!(compact.pending_perm, DEFAULT_STABLE, Order.By(x->compact.pending_nodes[x].pos))
556 end
557
558 function insert_node!(compact::IncrementalCompact, before, @nospecialize(typ), @nospecialize(val), attach_after::Bool=false)
559 if isa(before, SSAValue)
560 if before.id < compact.result_idx
561 count_added_node!(compact, val)
562 line = compact.result_lines[before.id]
563 push!(compact.new_new_nodes, NewNode(before.id, attach_after, typ, val, line))
564 return NewSSAValue(length(compact.new_new_nodes))
565 else
566 line = compact.ir.lines[before.id]
567 push!(compact.pending_nodes, NewNode(before.id, attach_after, typ, val, line))
568 push!(compact.pending_perm, length(compact.pending_nodes))
569 resort_pending!(compact)
570 os = OldSSAValue(length(compact.ir.stmts) + length(compact.ir.new_nodes) + length(compact.pending_nodes))
571 push!(compact.ssa_rename, os)
572 push!(compact.used_ssas, 0)
573 return os
574 end
575 elseif isa(before, OldSSAValue)
576 pos = before.id
577 if pos > length(compact.ir.stmts)
578 #@assert attach_after
579 entry = compact.pending_nodes[pos - length(compact.ir.stmts) - length(compact.ir.new_nodes)]
580 pos, attach_after = entry.pos, entry.attach_after
581 end
582 line = compact.ir.lines[pos]
583 push!(compact.pending_nodes, NewNode(pos, attach_after, typ, val, line))
584 push!(compact.pending_perm, length(compact.pending_nodes))
585 resort_pending!(compact)
586 os = OldSSAValue(length(compact.ir.stmts) + length(compact.ir.new_nodes) + length(compact.pending_nodes))
587 push!(compact.ssa_rename, os)
588 push!(compact.used_ssas, 0)
589 return os
590 elseif isa(before, NewSSAValue)
591 before_entry = compact.new_new_nodes[before.id]
592 push!(compact.new_new_nodes, NewNode(before_entry.pos, attach_after, typ, val, before_entry.line))
593 return NewSSAValue(length(compact.new_new_nodes))
594 else
595 error("Unsupported")
596 end
597 end
598
599 function insert_node_here!(compact::IncrementalCompact, @nospecialize(val), @nospecialize(typ), ltable_idx::Int32, reverse_affinity::Bool=false)
600 if compact.result_idx > length(compact.result)
601 @assert compact.result_idx == length(compact.result) + 1
602 resize!(compact, compact.result_idx)
603 end
604 refinish = false
605 if compact.result_idx == first(compact.result_bbs[compact.active_result_bb].stmts) && reverse_affinity
606 compact.active_result_bb -= 1
607 refinish = true
608 end
609 compact.result[compact.result_idx] = val
610 compact.result_types[compact.result_idx] = typ
611 compact.result_lines[compact.result_idx] = ltable_idx
612 compact.result_flags[compact.result_idx] = 0x00
613 if count_added_node!(compact, val)
614 push!(compact.late_fixup, compact.result_idx)
615 end
616 ret = SSAValue(compact.result_idx)
617 compact.result_idx += 1
618 refinish && finish_current_bb!(compact)
619 ret
620 end
621
622 function getindex(view::TypesView, v::OldSSAValue)
623 id = v.id
624 if id <= length(view.ir.ir.types)
625 return view.ir.ir.types[id]
626 end
627 id -= length(view.ir.ir.types)
628 if id <= length(view.ir.ir.new_nodes)
629 return view.ir.ir.new_nodes[id].typ
630 end
631 id -= length(view.ir.ir.new_nodes)
632 return view.ir.pending_nodes[id].typ
633 end
634
635 function setindex!(compact::IncrementalCompact, @nospecialize(v), idx::SSAValue)
636 @assert idx.id < compact.result_idx
637 (compact.result[idx.id] === v) && return
638 # Kill count for current uses
639 for ops in userefs(compact.result[idx.id])
640 val = ops[]
641 if isa(val, SSAValue)
642 @assert compact.used_ssas[val.id] >= 1
643 compact.used_ssas[val.id] -= 1
644 end
645 end
646 compact.result[idx.id] = v
647 # Add count for new use
648 if count_added_node!(compact, v)
649 push!(compact.late_fixup, idx.id)
650 end
651 end
652
653 function setindex!(compact::IncrementalCompact, @nospecialize(v), idx::Int)
654 if idx < compact.result_idx
655 compact[SSAValue(idx)] = v
656 else
657 compact.ir.stmts[idx] = v
658 end
659 return nothing
660 end
661
662 function getindex(view::TypesView, idx)
663 isa(idx, SSAValue) && (idx = idx.id)
664 if isa(view.ir, IncrementalCompact) && idx < view.ir.result_idx
665 return view.ir.result_types[idx]
666 elseif isa(view.ir, IncrementalCompact) && view.ir.renamed_new_nodes
667 if idx <= length(view.ir.result_types)
668 return view.ir.result_types[idx]
669 else
670 return view.ir.new_new_nodes[idx - length(view.ir.result_types)].typ
671 end
672 else
673 ir = isa(view.ir, IncrementalCompact) ? view.ir.ir : view.ir
674 if idx <= length(ir.types)
675 return ir.types[idx]
676 else
677 return ir.new_nodes[idx - length(ir.types)].typ
678 end
679 end
680 end
681
682 function getindex(view::TypesView, idx::NewSSAValue)
683 if isa(view.ir, IncrementalCompact)
684 compact = view.ir
685 compact.new_new_nodes[idx.id].typ
686 else
687 view.ir.new_nodes[idx.id].typ
688 end
689 end
690
691 function process_phinode_values(old_values::Vector{Any}, late_fixup::Vector{Int},
692 processed_idx::Int, result_idx::Int,
693 ssa_rename::Vector{Any}, used_ssas::Vector{Int},
694 do_rename_ssa::Bool)
695 values = Vector{Any}(undef, length(old_values))
696 for i = 1:length(old_values)
697 isassigned(old_values, i) || continue
698 val = old_values[i]
699 if isa(val, SSAValue)
700 if do_rename_ssa
701 if val.id > processed_idx
702 push!(late_fixup, result_idx)
703 val = OldSSAValue(val.id)
704 else
705 val = renumber_ssa2(val, ssa_rename, used_ssas, do_rename_ssa)
706 end
707 else
708 used_ssas[val.id] += 1
709 end
710 elseif isa(val, OldSSAValue)
711 if val.id > processed_idx
712 push!(late_fixup, result_idx)
713 else
714 # Always renumber these. do_rename_ssa applies only to actual SSAValues
715 val = renumber_ssa2(SSAValue(val.id), ssa_rename, used_ssas, true)
716 end
717 elseif isa(val, NewSSAValue)
718 push!(late_fixup, result_idx)
719 end
720 values[i] = val
721 end
722 return values
723 end
724
725 function renumber_ssa2(val::SSAValue, ssanums::Vector{Any}, used_ssa::Vector{Int}, do_rename_ssa::Bool)
726 id = val.id
727 if id > length(ssanums)
728 return val
729 end
730 if do_rename_ssa
731 val = ssanums[id]
732 end
733 if isa(val, SSAValue) && used_ssa !== nothing
734 used_ssa[val.id] += 1
735 end
736 return val
737 end
738
739 function renumber_ssa2!(@nospecialize(stmt), ssanums::Vector{Any}, used_ssa::Vector{Int}, late_fixup::Vector{Int}, result_idx::Int, do_rename_ssa::Bool)
740 urs = userefs(stmt)
741 for op in urs
742 val = op[]
743 if isa(val, OldSSAValue) || isa(val, NewSSAValue)
744 push!(late_fixup, result_idx)
745 end
746 if isa(val, SSAValue)
747 val = renumber_ssa2(val, ssanums, used_ssa, do_rename_ssa)
748 end
749 if isa(val, OldSSAValue) || isa(val, NewSSAValue)
750 push!(late_fixup, result_idx)
751 end
752 op[] = val
753 end
754 return urs[]
755 end
756
757 function process_node!(result::Vector{Any}, result_idx::Int, ssa_rename::Vector{Any},
758 late_fixup::Vector{Int}, used_ssas::Vector{Int}, @nospecialize(stmt),
759 idx::Int, processed_idx::Int, do_rename_ssa::Bool)
760 ssa_rename[idx] = SSAValue(result_idx)
761 if stmt === nothing
762 ssa_rename[idx] = stmt
763 elseif isa(stmt, OldSSAValue)
764 ssa_rename[idx] = ssa_rename[stmt.id]
765 elseif isa(stmt, GotoNode) || isa(stmt, GlobalRef)
766 result[result_idx] = stmt
767 result_idx += 1
768 elseif isa(stmt, Expr) || isa(stmt, PiNode) || isa(stmt, GotoIfNot) || isa(stmt, ReturnNode) || isa(stmt, UpsilonNode)
769 result[result_idx] = renumber_ssa2!(stmt, ssa_rename, used_ssas, late_fixup, result_idx, do_rename_ssa)
770 result_idx += 1
771 elseif isa(stmt, PhiNode)
772 result[result_idx] = PhiNode(stmt.edges, process_phinode_values(stmt.values, late_fixup, processed_idx, result_idx, ssa_rename, used_ssas, do_rename_ssa))
773 result_idx += 1
774 elseif isa(stmt, PhiCNode)
775 result[result_idx] = PhiCNode(process_phinode_values(stmt.values, late_fixup, processed_idx, result_idx, ssa_rename, used_ssas, do_rename_ssa))
776 result_idx += 1
777 elseif isa(stmt, SSAValue)
778 # identity assign, replace uses of this ssa value with its result
779 if do_rename_ssa
780 stmt = ssa_rename[stmt.id]
781 end
782 ssa_rename[idx] = stmt
783 else
784 # Constant assign, replace uses of this ssa value with its result
785 ssa_rename[idx] = stmt
786 end
787 return result_idx
788 end
789 function process_node!(compact::IncrementalCompact, result_idx::Int, @nospecialize(stmt), idx::Int, processed_idx::Int, do_rename_ssa::Bool)
790 return process_node!(compact.result, result_idx, compact.ssa_rename,
791 compact.late_fixup, compact.used_ssas, stmt, idx, processed_idx,
792 do_rename_ssa)
793 end
794
795 function resize!(compact::IncrementalCompact, nnewnodes)
796 old_length = length(compact.result)
797 resize!(compact.result, nnewnodes)
798 resize!(compact.result_types, nnewnodes)
799 resize!(compact.result_lines, nnewnodes)
800 resize!(compact.result_flags, nnewnodes)
801 resize!(compact.used_ssas, nnewnodes)
802 for i in (old_length+1):nnewnodes
803 compact.used_ssas[i] = 0
804 end
805 nothing
806 end
807
808 function finish_current_bb!(compact, old_result_idx=compact.result_idx)
809 bb = compact.result_bbs[compact.active_result_bb]
810 # If this was the last statement in the BB and we decided to skip it, insert a
811 # dummy `nothing` node, to prevent changing the structure of the CFG
812 if compact.result_idx == first(bb.stmts)
813 length(compact.result) < old_result_idx && resize!(compact, old_result_idx)
814 compact.result[old_result_idx] = nothing
815 compact.result_types[old_result_idx] = Nothing
816 compact.result_lines[old_result_idx] = 0
817 compact.result_flags[old_result_idx] = 0x00
818 compact.result_idx = old_result_idx + 1
819 end
820 compact.result_bbs[compact.active_result_bb] = BasicBlock(bb, StmtRange(first(bb.stmts), compact.result_idx-1))
821 compact.active_result_bb += 1
822 if compact.active_result_bb <= length(compact.result_bbs)
823 new_bb = compact.result_bbs[compact.active_result_bb]
824 compact.result_bbs[compact.active_result_bb] = BasicBlock(new_bb,
825 StmtRange(compact.result_idx, last(new_bb.stmts)))
826 end
827 end
828
829 function attach_after_stmt_after(compact::IncrementalCompact, idx::Int)
830 compact.new_nodes_idx > length(compact.perm) && return false
831 entry = compact.ir.new_nodes[compact.perm[compact.new_nodes_idx]]
832 entry.pos == idx && entry.attach_after
833 end
834
835 function process_newnode!(compact, new_idx, new_node_entry, idx, active_bb, do_rename_ssa)
836 old_result_idx = compact.result_idx
837 bb = compact.ir.cfg.blocks[active_bb]
838 compact.result_types[old_result_idx] = new_node_entry.typ
839 compact.result_lines[old_result_idx] = new_node_entry.line
840 result_idx = process_node!(compact, old_result_idx, new_node_entry.node, new_idx, idx - 1, do_rename_ssa)
841 compact.result_idx = result_idx
842 # If this instruction has reverse affinity and we were at the end of a basic block,
843 # finish it now.
844 if new_node_entry.attach_after && idx == last(bb.stmts)+1 && !attach_after_stmt_after(compact, idx-1)
845 active_bb += 1
846 finish_current_bb!(compact, old_result_idx)
847 end
848 (old_result_idx == result_idx) && return iterate(compact, (idx, active_bb))
849 return Pair{Int, Any}(old_result_idx, compact.result[old_result_idx]), (compact.idx, active_bb)
850 end
851
852 function iterate(compact::IncrementalCompact, (idx, active_bb)::Tuple{Int, Int}=(compact.idx, 1))
853 old_result_idx = compact.result_idx
854 if idx > length(compact.ir.stmts) && (compact.new_nodes_idx > length(compact.perm))
855 return nothing
856 end
857 if length(compact.result) < old_result_idx
858 resize!(compact, old_result_idx)
859 end
860 bb = compact.ir.cfg.blocks[active_bb]
861 if compact.new_nodes_idx <= length(compact.perm) &&
862 (entry = compact.ir.new_nodes[compact.perm[compact.new_nodes_idx]];
863 entry.attach_after ? entry.pos == idx - 1 : entry.pos == idx)
864 new_idx = compact.perm[compact.new_nodes_idx]
865 compact.new_nodes_idx += 1
866 new_node_entry = compact.ir.new_nodes[new_idx]
867 new_idx += length(compact.ir.stmts)
868 return process_newnode!(compact, new_idx, new_node_entry, idx, active_bb, true)
869 elseif !isempty(compact.pending_perm) &&
870 (entry = compact.pending_nodes[compact.pending_perm[1]];
871 entry.attach_after ? entry.pos == idx - 1 : entry.pos == idx)
872 new_idx = popfirst!(compact.pending_perm)
873 new_node_entry = compact.pending_nodes[new_idx]
874 new_idx += length(compact.ir.stmts) + length(compact.ir.new_nodes)
875 return process_newnode!(compact, new_idx, new_node_entry, idx, active_bb, false)
876 end
877 # This will get overwritten in future iterations if
878 # result_idx is not, incremented, but that's ok and expected
879 compact.result_types[old_result_idx] = compact.ir.types[idx]
880 compact.result_lines[old_result_idx] = compact.ir.lines[idx]
881 compact.result_flags[old_result_idx] = compact.ir.flags[idx]
882 result_idx = process_node!(compact, old_result_idx, compact.ir.stmts[idx], idx, idx, true)
883 stmt_if_any = old_result_idx == result_idx ? nothing : compact.result[old_result_idx]
884 compact.result_idx = result_idx
885 if idx == last(bb.stmts) && !attach_after_stmt_after(compact, idx)
886 active_bb += 1
887 finish_current_bb!(compact, old_result_idx)
888 end
889 (old_result_idx == compact.result_idx) && return iterate(compact, (idx + 1, active_bb))
890 compact.idx = idx + 1
891 if !isassigned(compact.result, old_result_idx)
892 @assert false
893 end
894 return Pair{Int, Any}(old_result_idx, compact.result[old_result_idx]), (compact.idx, active_bb)
895 end
896
897
1 (2.70%) samples spent in maybe_erase_unused!
0 (ex.), 1 (100.00%) (incl.) when called from maybe_erase_unused! line 898
function maybe_erase_unused!(extra_worklist, compact, idx, callback = x->nothing)
898 1 (2.70%)
1 (2.70%) samples spent in maybe_erase_unused!
0 (ex.), 1 (100.00%) (incl.) when called from simple_dce! line 991
1 (100.00%) samples spent calling maybe_erase_unused!
stmt = compact.result[idx]
899 stmt === nothing && return false
900 if compact_exprtype(compact, SSAValue(idx)) === Bottom
901 effect_free = false
902 else
903 1 (2.70%)
1 (100.00%) samples spent calling stmt_effect_free
effect_free = stmt_effect_free(stmt, compact.result_types[idx], compact, compact.ir.spvals)
904 end
905 if effect_free
906 for ops in userefs(stmt)
907 val = ops[]
908 # If the pass we ran inserted new nodes, it's possible for those
909 # to be outside our used_ssas count.
910 if isa(val, SSAValue) && val.id <= length(compact.used_ssas)
911 if compact.used_ssas[val.id] == 1
912 if val.id < idx
913 push!(extra_worklist, val.id)
914 end
915 end
916 compact.used_ssas[val.id] -= 1
917 callback(val)
918 end
919 end
920 compact.result[idx] = nothing
921 return true
922 end
923 return false
924 end
925
926 function fixup_phinode_values!(compact::IncrementalCompact, old_values::Vector{Any})
927 values = Vector{Any}(undef, length(old_values))
928 for i = 1:length(old_values)
929 isassigned(old_values, i) || continue
930 val = old_values[i]
931 if isa(val, OldSSAValue)
932 val = compact.ssa_rename[val.id]
933 if isa(val, SSAValue)
934 compact.used_ssas[val.id] += 1
935 end
936 elseif isa(val, NewSSAValue)
937 val = SSAValue(length(compact.result) + val.id)
938 end
939 values[i] = val
940 end
941 values
942 end
943
944 function fixup_node(compact::IncrementalCompact, @nospecialize(stmt))
945 if isa(stmt, PhiNode)
946 return PhiNode(stmt.edges, fixup_phinode_values!(compact, stmt.values))
947 elseif isa(stmt, PhiCNode)
948 return PhiCNode(fixup_phinode_values!(compact, stmt.values))
949 elseif isa(stmt, NewSSAValue)
950 return SSAValue(length(compact.result) + stmt.id)
951 elseif isa(stmt, OldSSAValue)
952 return compact.ssa_rename[stmt.id]
953 else
954 urs = userefs(stmt)
955 urs === () && return stmt
956 for ur in urs
957 val = ur[]
958 if isa(val, NewSSAValue)
959 ur[] = SSAValue(length(compact.result) + val.id)
960 elseif isa(val, OldSSAValue)
961 ur[] = compact.ssa_rename[val.id]
962 end
963 end
964 return urs[]
965 end
966 end
967
968 function just_fixup!(compact::IncrementalCompact)
969 for idx in compact.late_fixup
970 stmt = compact.result[idx]
971 new_stmt = fixup_node(compact, stmt)
972 (stmt !== new_stmt) && (compact.result[idx] = new_stmt)
973 end
974 for idx in 1:length(compact.new_new_nodes)
975 node = compact.new_new_nodes[idx]
976 new_stmt = fixup_node(compact, node.node)
977 if node.node !== new_stmt
978 compact.new_new_nodes[idx] = NewNode(
979 node.pos, node.attach_after, node.typ,
980 new_stmt, node.line)
981 end
982 end
983 end
984
985 function simple_dce!(compact::IncrementalCompact)
986
1 (2.70%) samples spent in simple_dce!
0 (ex.), 1 (100.00%) (incl.) when called from finish line 1014
# Perform simple DCE for unused values
987 extra_worklist = Int[]
988 for (idx, nused) in Iterators.enumerate(compact.used_ssas)
989 idx >= compact.result_idx && break
990 nused == 0 || continue
991 1 (2.70%)
1 (100.00%) samples spent calling maybe_erase_unused!
maybe_erase_unused!(extra_worklist, compact, idx)
992 end
993 while !isempty(extra_worklist)
994 maybe_erase_unused!(extra_worklist, compact, pop!(extra_worklist))
995 end
996 end
997
998 function non_dce_finish!(compact::IncrementalCompact)
999 result_idx = compact.result_idx
1000 resize!(compact.result, result_idx-1)
1001 resize!(compact.result_types, result_idx-1)
1002 resize!(compact.result_lines, result_idx-1)
1003 resize!(compact.result_flags, result_idx-1)
1004 just_fixup!(compact)
1005 bb = compact.result_bbs[end]
1006 compact.result_bbs[end] = BasicBlock(bb,
1007 StmtRange(first(bb.stmts), result_idx-1))
1008 compact.renamed_new_nodes = true
1009 nothing
1010 end
1011
1012 function finish(compact::IncrementalCompact)
1013 non_dce_finish!(compact)
1014 1 (2.70%)
1 (2.70%) samples spent in finish
0 (ex.), 1 (100.00%) (incl.) when called from compact! line 1027
1 (100.00%) samples spent calling simple_dce!
simple_dce!(compact)
1015 return complete(compact)
1016 end
1017
1018 function complete(compact::IncrementalCompact)
1019 cfg = CFG(compact.result_bbs, Int[first(bb.stmts) for bb in compact.result_bbs[2:end]])
1020 return IRCode(compact.ir, compact.result, compact.result_types, compact.result_lines, compact.result_flags, cfg, compact.new_new_nodes)
1021 end
1022
1023
1 (2.70%) samples spent in compact!
0 (ex.), 1 (100.00%) (incl.) when called from run_passes line 121
function compact!(code::IRCode)
1024 compact = IncrementalCompact(code)
1025 # Just run through the iterator without any processing
1026 foreach(x -> nothing, compact) # x isa Pair{Int, Any}
1027 1 (2.70%)
1 (100.00%) samples spent calling finish
return finish(compact)
1028 end
1029
1030 struct BBIdxIter
1031 ir::IRCode
1032 end
1033
1034 bbidxiter(ir::IRCode) = BBIdxIter(ir)
1035
1036 function iterate(x::BBIdxIter, (idx, bb)::Tuple{Int, Int}=(1, 1))
1037 idx > length(x.ir.stmts) && return nothing
1038 active_bb = x.ir.cfg.blocks[bb]
1039 next_bb = bb
1040 if idx == last(active_bb.stmts)
1041 next_bb += 1
1042 end
1043 return (bb, idx), (idx + 1, next_bb)
1044 end