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!
function maybe_erase_unused!(extra_worklist, compact, idx, callback = x->nothing)
0 (ex.), 1 (100.00%) (incl.) when called from maybe_erase_unused! line 898 |
||
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!
# Perform simple DCE for unused values
0 (ex.), 1 (100.00%) (incl.) when called from finish line 1014 |
||
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 (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!
function compact!(code::IRCode)
0 (ex.), 1 (100.00%) (incl.) when called from run_passes line 121 |
||
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 |