dymokomi/luce-base
Source of release 0.41.0
0.41.0 / src / back / opt / inline.lucb
#==============================================================================================
#
# inline - Small functions expanded at their call sites, on the IR
#
# DESCRIPTION:
# After lowering and before a target sees the program, every call of a small function
# of the program is replaced by the function's body: the arguments are stored into the
# callee's parameter slots, which join the caller's frame, the body's temporaries,
# slots, and labels are renumbered into the caller's, and each `ret` becomes a store
# of the result and a jump to one exit label. The callee itself stays in the program for
# the calls that are not expanded and for its address.
#
# A function is small when its body has at most `small` instructions besides labels
# and the blocks that end in a trap, measured after its own calls were expanded:
# callees are visited before callers. A function declared `inline` is expanded at
# every call up to `forced` instructions, a guard against a runaway body only. A
# function called from one place only, in its own package, is expanded there whatever
# its size up to `once`, and a function expanded at every call, which nothing else names, is dropped
# from the program. Not expanded: a variadic or naked function, one taking frame
# storage (`memory.frame`), one carrying inline assembly, atomics, or the debugger's hooks, a function calling itself, and one
# whose slots take more than `large_frame` bytes unless it is declared `inline`. The
# lowerer's discipline that a temporary is used in the block that assigned it is not
# kept across an expansion, which the register allocator does not need: it scans live
# ranges by instruction index and extends them across loop back-edges.
#
#==============================================================================================
import memory
import support.list
import support.hashed
import back.ir.ir
## The most instructions, labels aside, a function may have to be expanded at every call,
## and the most one called from one place only may have: it is expanded there, and when
## nothing else names it, dropped. Larger callees were measured on the compiler itself:
## expanding bodies of up to 64 instructions at up to four calls each grew its code by a
## tenth and made it no faster.
let small: usize = 24
let once: usize = 256
## The most a function called from one place only may have when that place is in a loop:
## the call's cost (saving registers, an aggregate result through memory, every value the
## loop keeps reloaded after it) is paid at every turn. A face's normal and its fold test,
## called once each from luce-geocore's loop over the faces, are 432 and 556 instructions
## as lowered and ran 12 % faster expanded. For every once-called function, outside loops
## too, 1024 made the compiler's own optimiser a quarter slower; in loops only, 4 %.
let once_in_loop: usize = 1024
## The most instructions an `inline` function may have and still be expanded at every
## call: `inline` is C's always_inline, and this only stops a runaway body.
let forced: usize = 1024
## The most bytes of slots a function may have and still be expanded, `inline` aside. The
## callee's slots join the caller's frame for the caller's whole call: a function called
## once holding a 16 KiB buffer made its caller's frame 35 KB on a server's worker thread,
## which overflowed the 512 KiB stack macOS gives one. Kept out of line, the buffer is on
## the stack only while the callee runs.
let large_frame: u64 = 1024
## Expand the expandable calls of `program`: callees before callers, so that a function
## reaching the callers has its own calls opened out already and is measured as it will
## stand; then drop the functions that were expanded everywhere they were called.
pub func expand(program: ir.Unit*) -> !:
var index = try Index.over(program)
defer index.release()
var census = try Census.over(program, &index)
defer census.release()
let order = try post_order(program, &index)
defer free(order)
for fi in order:
_ = try expand_in(program, &index, &census, fi)
try drop_expanded(program, &index, &census)
# Keep the inliner's call-count heuristics independent of optional standard
# modules. Pruning first could turn shared helpers into larger caller bodies.
try drop_unused_standard(program)
## After the optimiser: expand the calls of leaf functions at most `limit` instructions
## long as they now stand, the lowerer's scaffolding folded away (an accessor returning a
## two-word struct lowers to some forty instructions and optimises to under twenty).
## Answers which functions gained a body, for the optimiser to run over again; the
## callees stay in the program.
pub func expand_small(program: ir.Unit*, limit: usize) -> bool[]!:
var index = try Index.over(program)
defer index.release()
var census = try Census.over(program, &index, with_leaves = true)
defer census.release()
census.small = limit
census.once = 0
let changed = try new bool[program.functions.count] ---
clear_flags(changed)
let order = try post_order(program, &index)
defer free(order)
for fi in order:
changed[fi] = try expand_in(program, &index, &census, fi)
return changed
## Tidy a function the second pass expanded into: drop the stores its expanded bodies'
## parameters kept once the optimiser forwarded their loads, the blocks after an exit
## that nothing names any more, and each jump to the label right after it.
pub func tidy_expanded(f: ir.Function*) -> !:
try drop_unread_stores(f)
try drop_unreached(f)
## Retain standard functions reachable from application code, initializers,
## witness tables, assembly, and explicit retention attributes. User/package
## functions keep their existing linkage. In particular, merely embedding the
## window module must not require AppKit in a console program or a Linux build.
## Function addresses are graph edges too: native callbacks remain callable.
func drop_unused_standard(program: ir.Unit*) -> !:
var index = try Index.over(program)
defer index.release()
let count = program.functions.count
let retained = try new bool[count + 1] ---
defer free(retained)
clear_flags(retained)
var texts = try asm_texts_of(program)
defer texts.destroy()
var i: usize = 0
while i < count:
let f = &program.functions.items[i]
retained[i] = not f.standard or f.exported or f.used or f.weak or f.naked or f.section.length > 0 or f.name == program.init_function or f.name == program.trap_function or f.name == program.trap_at_function or f.name == program.trap_two_at_function or named_in_asm(&texts, f.name)
i += 1
# a standard global's initialiser is reached through the global, not through the
# call `lb_init_globals` makes: that call goes when the global does
let retained_globals = try new bool[program.globals.count + 1] ---
defer free(retained_globals)
clear_flags(retained_globals)
let initialisers = try new bool[count + 1] ---
defer free(initialisers)
clear_flags(initialisers)
for global in program.globals.span():
if global.init_function.length > 0:
if let position = index.find(global.init_function):
initialisers[position] = true
let retained_tables = try new bool[program.tables.count + 1] ---
defer free(retained_tables)
clear_flags(retained_tables)
# each reference finds its global and its table by name, not by a walk over all of them
var globals_by_name = try hashed.Table[str].create(program.globals.count)
defer globals_by_name.destroy()
for gi in 0..<program.globals.count:
_ = try globals_by_name.add(program.globals.get(gi).name, gi)
var tables_by_name = try hashed.Table[str].create(program.tables.count)
defer tables_by_name.destroy()
for ti in 0..<program.tables.count:
_ = try tables_by_name.add(program.tables.get(ti).name, ti)
for table in program.tables.span():
if named_in_asm(&texts, table.name):
retain_table(program, &tables_by_name, &index, retained, retained_tables, ir.global_ref(table.name))
let visited = try new bool[count + 1] ---
defer free(visited)
clear_flags(visited)
var changed = true
while changed:
changed = false
i = 0
while i < count:
if retained[i] and not visited[i]:
visited[i] = true
changed = true
let f = &program.functions.items[i]
for instruction in f.instrs.span():
note_reached(&index, retained, initialisers, instruction.a)
note_reached(&index, retained, initialisers, instruction.b)
retain_table(program, &tables_by_name, &index, retained, retained_tables, instruction.a)
retain_table(program, &tables_by_name, &index, retained, retained_tables, instruction.b)
retain_storage(&globals_by_name, retained_globals, instruction.a)
retain_storage(&globals_by_name, retained_globals, instruction.b)
for argument in f.args.span():
note_reached(&index, retained, initialisers, argument.value)
retain_table(program, &tables_by_name, &index, retained, retained_tables, argument.value)
retain_storage(&globals_by_name, retained_globals, argument.value)
i += 1
for gi in 0..<program.globals.count:
let global = program.globals.get(gi)
if retained_globals[gi] and global.init_function.length > 0:
if let position = index.find(global.init_function):
if not retained[position]:
retained[position] = true
changed = true
var kept_tables = try list.List[ir.WitnessTable].create(program.tables.count)
for ti in 0..<program.tables.count:
var table = program.tables.get(ti)
if retained_tables[ti]:
try kept_tables.push(table)
else:
table.entries.destroy()
program.tables.destroy()
program.tables = kept_tables
try keep_retained(program, &index, retained)
try drop_unused_storage(program, &texts)
try drop_unused_texts(program)
## Keep the functions `retained` marks, in order, and release the rest.
func keep_retained(program: ir.Unit*, index: Index*, retained: bool[]) -> !:
let count = program.functions.count
var kept = try list.List[ir.Function].create(count)
for i in 0..<count:
var f = program.functions.get(i)
if retained[i]:
if f.name == "lb_init_globals" or f.name == "lb_init_thread_locals":
drop_dead_initialiser_calls(&f, index, retained)
try kept.push(f)
else:
f.destroy()
program.functions.destroy()
program.functions = kept
## The calls of `lb_init_globals` and `lb_init_thread_locals` to initialisers the pruner
## dropped go with them.
func drop_dead_initialiser_calls(f: ir.Function*, index: Index*, retained: bool[]):
var kept: usize = 0
var i: usize = 0
var dropped_call = false
while i < f.instrs.count:
let instruction = f.instrs.get(i)
var live = true
if instruction.op == ir.Op.call and instruction.a.kind == ir.RefKind.function:
if let position = index.find(instruction.a.name):
live = retained[position]
dropped_call = not live
elif instruction.op == ir.Op.word:
# a dropped call's words go with it
live = not dropped_call
else:
dropped_call = false
if live:
f.instrs.items[kept] = instruction
kept += 1
i += 1
f.instrs.count = kept
## The texts no retained function names are dropped and the rest renumbered, since a
## text is only data for the instruction that takes its address.
func drop_unused_texts(program: ir.Unit*) -> !:
let used = try new bool[program.texts.count + 1] ---
defer free(used)
clear_flags(used)
for function in program.functions.span():
for instruction in function.instrs.span():
note_text(used, instruction.a)
note_text(used, instruction.b)
if ir.positioned(instruction) and (usize)instruction.extra2 <= used.length:
used[instruction.extra2 - 1] = true
for argument in function.args.span():
note_text(used, argument.value)
let renumbered = try new u32[program.texts.count + 1] ---
defer free(renumbered)
var kept = try list.List[ir.Text].create(program.texts.count)
for i in 0..<program.texts.count:
renumbered[i] = u32(kept.count)
if used[i]:
try kept.push(program.texts.get(i))
if kept.count == program.texts.count:
kept.destroy()
return
for function in program.functions.span():
for k in 0..<function.instrs.count:
function.instrs.items[k].a = renumber_text(function.instrs.items[k].a, renumbered)
function.instrs.items[k].b = renumber_text(function.instrs.items[k].b, renumbered)
if ir.positioned(function.instrs.items[k]):
function.instrs.items[k].extra2 = renumbered[function.instrs.items[k].extra2 - 1] + 1
for k in 0..<function.args.count:
function.args.items[k].value = renumber_text(function.args.items[k].value, renumbered)
program.texts.destroy()
program.texts = kept
try program.index_texts()
func note_text(used: bool[], r: ir.Ref):
if r.kind == ir.RefKind.text and (usize)r.index < used.length:
used[r.index] = true
func renumber_text(r: ir.Ref, renumbered: const u32[]) -> ir.Ref:
if r.kind != ir.RefKind.text:
return r
return ir.text_ref(renumbered[r.index])
## Retained bodies and initializers determine which standard storage exists. In
## particular, an unused OS adapter must not reserve its TLS on another target.
## Application linkage, explicit retention attributes and raw assembly stay intact.
func drop_unused_storage(program: ir.Unit*, assembly: list.List[str]*) -> !:
let retained = try new bool[program.globals.count + 1] ---
defer free(retained)
for i in 0..<program.globals.count:
let global = program.globals.get(i)
retained[i] = not global.standard or global.exported or global.used or global.weak or global.section.length > 0 or named_in_asm(assembly, global.name)
var by_name = try hashed.Table[str].create(program.globals.count)
defer by_name.destroy()
for i in 0..<program.globals.count:
_ = try by_name.add(program.globals.get(i).name, i)
for function in program.functions.span():
for instruction in function.instrs.span():
retain_storage(&by_name, retained, instruction.a)
retain_storage(&by_name, retained, instruction.b)
for argument in function.args.span():
retain_storage(&by_name, retained, argument.value)
var kept = try list.List[ir.Global].create(program.globals.count)
for i in 0..<program.globals.count:
if retained[i]:
try kept.push(program.globals.get(i))
program.globals.destroy()
program.globals = kept
func retain_storage(by_name: hashed.Table[str]*, retained: bool[], reference: ir.Ref):
if reference.kind != ir.RefKind.global:
return
if let i = by_name.find(reference.name):
retained[i] = true
test "standard storage follows retained code without changing user linkage":
var backing: u8[131072]
var arena = memory.FixedBuffer.over(backing)
with arena:
var program = try ir.Unit.create()
let names: str[8] = ["unused", "read", "initialized", "assembly", "used", "weak", "section", "user"]
for i in 0..<names.length:
try program.globals.push(ir.Global(name = names[i], standard = i != 7, size = 8, align = 8, external = false,
is_thread_local = true, used = i == 4, weak = i == 5, section = "custom" if i == 6 else ""))
var entry = try ir.Function.create("entry")
_ = try entry.load(ir.Op.loadl, ir.Class.l, ir.global_ref("read"))
try entry.store(ir.Op.storel, ir.const_ref(42), ir.global_ref("initialized"))
try program.functions.push(entry)
var dead = try ir.Function.create("dead")
dead.standard = true
_ = try dead.load(ir.Op.loadl, ir.Class.l, ir.global_ref("unused"))
try program.functions.push(dead)
try program.module_asm.push(ir.Text(bytes = "address of assembly"))
try drop_unused_standard(&program)
assert(program.functions.count == 1)
assert(program.globals.count == 7)
for i in 0..<program.globals.count:
assert(program.globals.get(i).name == names[i + 1])
## A witness table is live when reachable code or assembly takes its address.
## Treating every table as a root would pull unused platform modules into every binary.
func retain_table(program: ir.Unit*, by_name: hashed.Table[str]*, index: Index*, retained: bool[], tables: bool[], reference: ir.Ref):
if reference.kind != ir.RefKind.global and reference.kind != ir.RefKind.function:
return
let ti = by_name.find(reference.name) else return
if tables[ti]:
return
tables[ti] = true
for name in program.tables.get(ti).entries.span():
if let position = index.find(name):
retained[position] = true
## The functions in an order that puts every callee before its callers, cycles apart: a
## depth-first walk of the call graph from each function, finishing a function after the
## functions it calls.
func post_order(program: ir.Unit*, index: Index*) -> usize[]!:
let n = program.functions.count
var order = try new usize[n + 1] ---
var state = try new u8[n + 1] ---
defer free(state)
var stack = try new usize[n + 1] ---
defer free(stack)
var cursor = try new usize[n + 1] ---
defer free(cursor)
memory.set(state, 0)
var count: usize = 0
var root: usize = 0
while root < n:
if state[root] != 0:
root += 1
continue
var depth: usize = 1
stack[0] = root
cursor[0] = 0
state[root] = 1
while depth > 0:
let fi = stack[depth - 1]
let f = &program.functions.items[fi]
var pushed = false
while cursor[depth - 1] < f.instrs.count:
let ins = f.instrs.get(cursor[depth - 1])
cursor[depth - 1] += 1
if ins.op == ir.Op.call and ins.a.kind == ir.RefKind.function:
if let gi = index.find(ins.a.name):
if state[gi] == 0:
state[gi] = 1
stack[depth] = gi
cursor[depth] = 0
depth += 1
pushed = true
break
if not pushed:
state[fi] = 2
order[count] = fi
count += 1
depth -= 1
root += 1
return order[0..<count]
## Rebuild function `fi`'s instruction list with its expandable calls opened out. The
## expansions of one callee in one caller share the callee's slots: an expansion's slots
## are dead past its exit, so the next expansion may have them.
## Expand the expandable calls of function `fi`; whether there were any.
func expand_in(program: ir.Unit*, index: Index*, census: Census*, fi: usize) -> bool!:
var f = &program.functions.items[fi]
if f.debug:
return false
var looped: bool[]
if loops_matter(program, index, census, fi):
looped = try in_loops(f)
else:
looped = try new bool[f.instrs.count + 1] ---
clear_flags(looped)
defer free(looped)
if not has_expandable_call(program, index, census, fi, looped):
return false
var out = Sink(instrs = try list.List[ir.Instr].create(f.instrs.count + 64))
var bases = try new u32[program.functions.count + 1] ---
defer free(bases)
var k: usize = 0
while k < bases.length:
bases[k] = no_slots
k += 1
var ix: usize = 0
while ix < f.instrs.count:
let n = f.instrs.get(ix)
ix += 1
if let gi = expandable_callee(program, index, census, fi, n, looped[ix - 1]):
var expansion = Expansion.of(program, f, &program.functions.items[gi], n, bases[gi])
try expansion.run(&out)
bases[gi] = expansion.slot_base
census.expanded[gi] = true
# the call's words are loaded from its slot now, where the body left them
while expansion.info.result_words and ix < f.instrs.count and f.instrs.get(ix).op == ir.Op.word:
let w = f.instrs.get(ix)
ix += 1
let at = try word_address(f, &out, expansion.info.result_slot, w.extra)
try out.push(ir.Instr(op = ir.load_of(w.cls), cls = w.cls, dst = w.dst, a = at, b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
else:
try out.push(n)
f.instrs.destroy()
f.instrs = out.instrs
census.sizes[fi] = unknown
return true
## The address of word `k` of slot `slot`, formed in `out` when past the first.
func word_address(f: ir.Function*, out: Sink*, slot: u32, k: u32) -> ir.Ref!:
if k == 0:
return ir.slot_ref(slot)
let base = try f.temp(ir.Class.l)
try out.push(ir.Instr(op = ir.Op.addr, cls = ir.Class.l, dst = base, a = ir.slot_ref(slot), b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
let at = try f.temp(ir.Class.l)
try out.push(ir.Instr(op = ir.Op.add, cls = ir.Class.l, dst = at, a = ir.temp_ref(base), b = ir.const_ref((i64)k * 8), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
return ir.temp_ref(at)
## Whether any call of function `fi` can be expanded, so functions without one are left alone.
func has_expandable_call(program: ir.Unit*, index: Index*, census: Census*, fi: usize, looped: const bool[]) -> bool:
let f = &program.functions.items[fi]
var ix: usize = 0
while ix < f.instrs.count:
if expandable_callee(program, index, census, fi, f.instrs.get(ix), looped[ix]) != none:
return true
ix += 1
return false
## The index of the function that call `n` in function `fi` may be expanded with: a small
## function, or one of the caller's own package that this call alone reaches and nothing
## else names, larger when the call is in a loop (`looped`). Only the functions the program
## reaches are lowered (`lower.reach`): a library function called once by the program may be
## called from many places in its library, and expanding it into another package's code
## would copy what the library shares.
func expandable_callee(program: ir.Unit*, index: Index*, census: Census*, fi: usize, n: ir.Instr, looped: bool) -> usize?:
if n.op != ir.Op.call or n.a.kind != ir.RefKind.function:
return none
let gi = index.find(n.a.name) else return none
if gi == fi:
return none
let g = &program.functions.items[gi]
let info = program.functions.items[fi].calls.get((usize)n.extra)
if info.variadic or (usize)info.args_count != g.params.count:
return none
let size = try_size(census, program, gi) else return none
if census.leaves.length > 0 and not census.leaves[gi]:
return none
# the second pass lets a leaf that moves aggregates through memory be larger (aggregate_words)
let budget = census.small + (2 * aggregate_words(g) if census.leaves.length > 0 else 0)
if size <= budget or (g.always_inline and size <= forced):
return gi
let alone = (census.once_in_loop if looped else census.once) if census.once > 0 else 0
if size <= alone and census.calls[gi] == 1 and not census.pinned[gi] and same_package(program.functions.items[fi].package, g.package):
return gi
return none
## Whether a function of package `caller` may expand a function of package `callee` called
## from one place only: one of its own package, or any when the lowerer made the caller of
## its own (an export's C face, the entry, an initialiser), which no package shares.
func same_package(caller: str, callee: str) -> bool:
return caller.length == 0 or caller == callee
## Whether a call of function `fi` may be expanded only if it is in a loop, so that the
## function's loops are worth finding.
func loops_matter(program: ir.Unit*, index: Index*, census: Census*, fi: usize) -> bool:
for x in program.functions.items[fi].instrs.span():
if x.op == ir.Op.call and expandable_callee(program, index, census, fi, x, true) != none and expandable_callee(program, index, census, fi, x, false) == none:
return true
return false
## By instruction of `f`, whether it lies in a loop: between a label and a jump back to it
## (the lowerer writes a loop's body after its head's label and before the jump back).
func in_loops(f: ir.Function*) -> bool[]!:
let n = f.instrs.count
let looped = try new bool[n + 1] ---
clear_flags(looped)
var label_at = try new u32[(usize)f.labels + 1] ---
defer free(label_at)
for k in 0..<label_at.length:
label_at[k] = 0xFFFFFFFF
# how many loops open at each instruction, less how many closed before it
var depth = try new i32[n + 1] ---
defer free(depth)
for k in 0..<depth.length:
depth[k] = 0
for ix in 0..<n:
let x = f.instrs.get(ix)
if x.op == ir.Op.label and (usize)x.extra < label_at.length:
label_at[(usize)x.extra] = (u32)ix
elif x.op == ir.Op.jmp or x.op == ir.Op.jnz:
back_edge(label_at, depth, x.extra, ix)
if x.op == ir.Op.jnz:
back_edge(label_at, depth, x.extra2, ix)
var open: i32 = 0
for ix in 0..<n:
open += depth[ix]
looped[ix] = open > 0
return looped
## A jump at `at` to `target`: when the label came before, a loop from it to the jump.
func back_edge(label_at: const u32[], depth: i32[], target: u32, at: usize):
if (usize)target < label_at.length and label_at[(usize)target] != 0xFFFFFFFF:
depth[(usize)label_at[(usize)target]] += 1
depth[at + 1] -= 1
## The words of the aggregates a function takes by value and returns: each is copied through
## memory at every call (the argument into the callee's frame, the result out of it), which
## an expansion lets the optimiser forward into registers instead. A `Vector3.cross` of two
## 24-byte vectors moves six words so, and costs its callers more called than expanded.
func aggregate_words(g: ir.Function*) -> usize:
var words: usize = 0
for p in g.params.span():
words += ((usize)p.size + 7) // 8
if g.has_result:
words += ((usize)g.result_size + 7) // 8
return words
func try_size(census: Census*, program: ir.Unit*, gi: usize) -> usize?:
return census.size_of(program, gi)
## How many instructions, labels aside, a function's body has on its paths that do not
## trap; none when the body may not stand in for a call of it at all. A block that ends
## in a trap (an `else trap`, a failed check's message and call) is out of line and runs
## at most once, so it costs the budget nothing, nor does what follows it unlabelled.
func body_size(g: ir.Function*) -> usize?:
# frame storage (`memory.frame`) belongs to the frame the source names: in a caller's
# loop an expansion would take it again at every turn
if g.variadic or g.naked or g.noinline or g.debug or g.allocates_frame or g.instrs.count == 0:
return none
if not g.always_inline and frame_bytes(g) > large_frame:
return none
var count: usize = 0
# the current block's instructions, counted when it leaves other than by a trap
var block: usize = 0
var unreached = false
var ix: usize = 0
while ix < g.instrs.count:
let n = g.instrs.get(ix)
ix += 1
if n.op == ir.Op.label:
count += block
block = 0
unreached = false
continue
if not is_expandable_op(n.op):
return none
if unreached:
continue
block += 1
if n.op == ir.Op.trap_:
block = 0
unreached = true
elif ir.is_terminator(n.op):
count += block
block = 0
unreached = true
return count + block
## The bytes a function's slots take, before any sharing.
func frame_bytes(g: ir.Function*) -> u64:
var bytes: u64 = 0
for slot in g.slots.span():
bytes += (u64)slot.size
return bytes
## Instructions an expansion knows how to renumber; the ones that reach outside the
## function's own temporaries, slots, and labels are left to a real call.
func is_expandable_op(op: ir.Op) -> bool:
match op:
.asm_, .set_reg, .get_reg, .frame, .fence, .fill, .atomic_load, .atomic_store, .atomic_add, .atomic_sub, .atomic_or, .atomic_and_not, .atomic_xor, .atomic_swap, .atomic_max, .atomic_min, .atomic_cas:
return false
_:
return true
## Drop every function that was expanded at a call and that nothing names any more: not
## a call, not an address, not a witness table, not the object file.
func drop_expanded(program: ir.Unit*, index: Index*, census: Census*) -> !:
var referenced = try new bool[program.functions.count + 1] ---
defer free(referenced)
clear_flags(referenced)
var i: usize = 0
while i < program.functions.count:
let f = &program.functions.items[i]
var ix: usize = 0
while ix < f.instrs.count:
let n = f.instrs.get(ix)
ix += 1
note_reference(index, referenced, n.a)
note_reference(index, referenced, n.b)
var k: usize = 0
while k < f.args.count:
note_reference(index, referenced, f.args.get(k).value)
k += 1
i += 1
var kept = try list.List[ir.Function].create(program.functions.count)
i = 0
while i < program.functions.count:
var f = program.functions.get(i)
if census.expanded[i] and not census.pinned[i] and not referenced[i]:
f.destroy()
else:
try kept.push(f)
i += 1
program.functions.destroy()
program.functions = kept
func clear_flags(flags: bool[]):
var i: usize = 0
while i < flags.length:
flags[i] = false
i += 1
func note_reference(index: Index*, referenced: bool[], r: ir.Ref):
if r.kind != ir.RefKind.function:
return
if let gi = index.find(r.name):
referenced[gi] = true
## A function reference retains its function, except a global's initialiser, which the
## global retains (`drop_unused_standard`).
func note_reached(index: Index*, referenced: bool[], initialisers: bool[], r: ir.Ref):
if r.kind != ir.RefKind.function:
return
if let gi = index.find(r.name):
if not initialisers[gi]:
referenced[gi] = true
## No slots shared yet: the marker in `expand_in`'s table of slot bases.
let no_slots: u32 = 0xFFFFFFFF
## An empty own_slots: no parameter has a slot of its own.
func no_own_slots() -> u32[]:
var none_yet: u32[]
return none_yet
# mark: The census =============================================================================
## What the program says of each function before any expansion: how many calls reach it,
## and whether it must stay whatever the calls say, because the object file, a witness
## table, an address taken, or assembly text names it.
struct Census:
var calls: u32[]
var pinned: bool[]
var expanded: bool[]
## Each function's body size as last measured, `unknown` until it is; a function's size
## changes only when its own calls are expanded, which clears its entry.
var sizes: u32[]
## The most instructions a callee may have to be expanded at every call, and at its one
## call (0: no such expansion).
var small: usize
var once: usize
var once_in_loop: usize
## For the second pass, which functions were leaves, calling nothing of the program
## (the C library aside), when it began: only those are expanded, so a caller that
## became a leaf by the pass's own expansions is not opened out in turn. Empty for the
## first pass.
var leaves: bool[]
## The census of `program`; `with_leaves` for the second pass, which expands only
## the functions that were leaves when it began.
static func over(program: ir.Unit*, index: Index*, with_leaves: bool = false) -> Census!:
let n = program.functions.count + 1
var c = Census(calls = try new u32[n] ---, pinned = try new bool[n] ---, expanded = try new bool[n] ---, sizes = try new u32[n] ---, small = small, once = once, once_in_loop = once_in_loop, leaves = try new bool[program.functions.count if with_leaves else 0] ---)
for fi in 0..<c.leaves.length:
c.leaves[fi] = not calls_the_program(&program.functions.items[fi], index)
var z: usize = 0
while z < n:
c.calls[z] = 0
c.sizes[z] = unknown
z += 1
clear_flags(c.pinned)
clear_flags(c.expanded)
var asm_texts = try asm_texts_of(program)
defer asm_texts.destroy()
var i: usize = 0
while i < program.functions.count:
let f = &program.functions.items[i]
# the program's entry stays a function: a trace begins there
if f.exported or f.used or f.weak or f.naked or f.section.length > 0 or f.name == program.init_function or f.name == program.trap_function or f.name == program.trap_at_function or f.name == program.trap_two_at_function or f.name == "lb_main":
c.pinned[i] = true
if named_in_asm(&asm_texts, f.name):
c.pinned[i] = true
var ix: usize = 0
while ix < f.instrs.count:
let ins = f.instrs.get(ix)
ix += 1
if ins.op == ir.Op.call and ins.a.kind == ir.RefKind.function:
if let gi = index.find(ins.a.name):
c.calls[gi] += 1
else:
c.pin_named(index, ins.a)
c.pin_named(index, ins.b)
var k: usize = 0
while k < f.args.count:
c.pin_named(index, f.args.get(k).value)
k += 1
i += 1
i = 0
while i < program.tables.count:
let table = program.tables.get(i)
var e: usize = 0
while e < table.entries.count:
if let gi = index.find(table.entries.get(e)):
c.pinned[gi] = true
e += 1
i += 1
return c
func pin_named(index: Index*, r: ir.Ref):
if r.kind != ir.RefKind.function:
return
if let gi = index.find(r.name):
self.pinned[gi] = true
## The size of function `gi`'s body, measured once per shape of it.
func size_of(program: ir.Unit*, gi: usize) -> usize?:
if self.sizes[gi] == unknown:
if let measured = body_size(&program.functions.items[gi]):
self.sizes[gi] = u32(measured)
else:
self.sizes[gi] = not_a_body
if self.sizes[gi] == not_a_body:
return none
return (usize)self.sizes[gi]
func release():
free(self.leaves)
free(self.calls)
free(self.pinned)
free(self.expanded)
free(self.sizes)
## A body not measured yet, and one that may never stand in for a call.
let unknown: u32 = 0xFFFFFFFF
let not_a_body: u32 = 0xFFFFFFFE
## Every piece of assembly text in the program: the module-level blocks and the functions'.
func asm_texts_of(program: ir.Unit*) -> list.List[str]!:
var texts = try list.List[str].create(8)
var i: usize = 0
while i < program.module_asm.count:
try texts.push(program.module_asm.get(i).bytes)
i += 1
i = 0
while i < program.functions.count:
let f = &program.functions.items[i]
var ix: usize = 0
while ix < f.instrs.count:
let ins = f.instrs.get(ix)
ix += 1
if ins.op == ir.Op.asm_ and ins.b.kind == ir.RefKind.text:
try texts.push(program.texts.get((usize)ins.b.index).bytes)
i += 1
return texts
## Whether assembly text anywhere in the program spells `name`: a module-level block or a
## function's block may call or address a function of the program by its symbol.
func named_in_asm(texts: list.List[str]*, name: str) -> bool:
var i: usize = 0
while i < texts.count:
if contains(texts.get(i), name):
return true
i += 1
return false
func contains(text: str, name: str) -> bool:
if name.length == 0 or name.length > text.length:
return false
var i: usize = 0
while i + name.length <= text.length:
if (str)text.bytes[i..<i + name.length] == name:
return true
i += 1
return false
## The instruction list being built for a function.
struct Sink:
var instrs: ir.Instrs
func push(n: ir.Instr) -> !:
try self.instrs.push(n)
# mark: One expansion ==========================================================================
## The renumbering of one callee body into one caller, at one call.
struct Expansion:
var program: ir.Unit*
var f: ir.Function*
var g: ir.Function*
var call: ir.Instr
var info: ir.CallInfo
## The caller's counts before the body joined it: what the body's numbers shift by.
var slot_base: u32
var temp_base: u32
var label_base: u32
## Where the body's `ret` jumps to, and the slot a scalar result passes through.
var exit_label: u32
var result_slot: u32
## Whether the body's slots are an earlier expansion's, already in the caller's frame.
var shares_slots: bool
## Per body slot, when the slots are shared: a parameter's own new slot, `no_slots` for
## the shared rest. A parameter's slot is the expansion's own, so what each call passes
## (a `self` pointer among them) stays a value of its own once promoted, which the
## optimiser follows; the body's other slots are dead past its exit and shared.
var own_slots: u32[]
## `--release --debug`, both functions described: the inlined subroutine this expansion
## is in the caller (1-based), and what the body's scope numbers shift by.
var site: u32
var scope_base: u32
var locals_base: u32
var described: bool
static func of(program: ir.Unit*, f: ir.Function*, g: ir.Function*, call: ir.Instr, shared: u32) -> Expansion:
return Expansion(program = program, f = f, g = g, call = call, info = f.calls.get((usize)call.extra),
slot_base = u32(f.slots.count) if shared == no_slots else shared,
temp_base = u32(f.temps.count), label_base = f.labels, exit_label = 0, result_slot = 0,
shares_slots = shared != no_slots, own_slots = no_own_slots(), site = 0, scope_base = 0, locals_base = 0, described = false)
func run(out: Sink*) -> !:
defer self.release()
try self.join_frames()
try self.describe()
try self.bind_parameters(out)
var ix: usize = 0
while ix < self.g.instrs.count:
try self.copy_instr(self.g.instrs.get(ix), out)
ix += 1
try out.push(ir.Instr(op = ir.Op.label, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = self.exit_label, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
try self.take_result(out)
## Free the parameters' own slots, when `join_frames` made them.
func release():
if self.own_slots.length > 0:
free(self.own_slots)
self.own_slots = no_own_slots()
## The callee's slots and temporaries join the caller's; its labels get fresh numbers,
## plus one for the exit; a scalar result gets a slot to cross the exit through.
func join_frames() -> !:
var i: usize = 0
while i < self.g.slots.count and not self.shares_slots:
# the body's dynamic levels are the callee's own: expanded, their slots are the
# caller's fixed frame, and the body's `reserve`s go (copy_instr)
var s = self.g.slots.get(i)
s.level = 0
s.offset = 0
try self.f.slots.push(s)
i += 1
if self.shares_slots and self.g.params.count > 0:
self.own_slots = try new u32[self.g.slots.count] ---
for k in 0..<self.own_slots.length:
self.own_slots[k] = no_slots
for p in self.g.params.span():
if (usize)p.slot < self.own_slots.length:
self.own_slots[(usize)p.slot] = u32(self.f.slots.count)
try self.f.slots.push(self.g.slots.get((usize)p.slot))
i = 0
while i < self.g.temps.count:
try self.f.temps.push(self.g.temps.get(i))
i += 1
self.f.labels += self.g.labels
self.exit_label = self.f.label()
if self.info.has_result and self.info.result_size == 0:
self.result_slot = try self.f.slot(8, 8)
## Each argument lands in its parameter's slot: a scalar by a store, a record by a copy.
func bind_parameters(out: Sink*) -> !:
var i: usize = 0
while i < self.g.params.count:
let p = self.g.params.get(i)
let a = self.f.args.get((usize)self.info.args_start + i)
let target = ir.slot_ref(self.slot_of(p.slot))
if p.size == 0:
try out.push(ir.Instr(op = ir.store_of(p.cls), cls = ir.Class.l, dst = 0, a = a.value, b = target, extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
else:
try out.push(ir.Instr(op = ir.Op.blit, cls = ir.Class.l, dst = 0, a = target, b = a.value, extra = p.size, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
i += 1
## The caller's destination takes the result from its slot, after the exit label.
func take_result(out: Sink*) -> !:
if self.result_slot == 0 or self.call.dst == 0:
return
let cls = self.info.result_cls
try out.push(ir.Instr(op = ir.load_of(cls), cls = cls, dst = self.call.dst, a = ir.slot_ref(self.result_slot), b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
## `--release --debug`: the body is an inlined subroutine of the caller. A site names the
## callee and the call; the callee's scopes, named locals and own sites join the caller's
## under it. A body without symbols brings no lines: its instructions belong to the
## statement of the call.
func describe() -> !:
if not (self.f.symbols and self.g.symbols):
return
self.described = true
self.scope_base = u32(self.f.debug_scopes.count)
self.locals_base = u32(self.f.locals.count)
try self.f.sites.push(ir.InlineSite(name = self.g.source_name, source = self.g.source, line = self.g.source_line, result_type = self.g.result_type,
call_line = self.call.line, call_file = self.call.file, scope = self.call.scope, parent = self.call.site))
self.site = u32(self.f.sites.count)
for inner in self.g.sites.span():
try self.f.sites.push(ir.InlineSite(name = inner.name, source = inner.source, line = inner.line, result_type = inner.result_type,
call_line = inner.call_line, call_file = inner.call_file, scope = self.scope_of(inner.scope), parent = self.site_of(inner.parent)))
var k: usize = 1
while k < self.g.debug_scopes.count:
let sc = self.g.debug_scopes.get(k)
try self.f.debug_scopes.push(ir.DebugScope(parent = (usize)self.scope_of(u32(sc.parent)), start = 0, end = 0, site = self.site_of(sc.site)))
k += 1
for described in self.g.locals.span():
var moved = described
moved.slot = self.slot_of(moved.slot)
moved.scope = (usize)self.scope_of(u32(described.scope))
moved.site = self.site_of(described.site)
try self.f.locals.push(moved)
## The body's scope `old` as the caller numbers it: the body's own (0) is the site itself,
## whose root entry is not copied.
func scope_of(old: u32) -> u32:
return 0 if old == 0 else self.scope_base + old - 1
## The body's site `old` as the caller numbers it: the body's own (0) is this site.
func site_of(old: u32) -> u32:
return self.site if old == 0 else self.site + old
## One instruction of the body, renumbered; `ret` becomes the result's store and the exit.
func copy_instr(n: ir.Instr, out: Sink*) -> !:
var m = n
if m.dst != 0:
m.dst += self.temp_base
m.a = self.renumber(m.a)
m.b = self.renumber(m.b)
if self.described:
m.scope = self.scope_of(n.scope)
m.site = self.site_of(n.site)
if m.line != 0 and m.file == 0:
m.file = try self.program.file_index(self.g.source)
else:
m.scope = 0
m.site = 0
m.line = 0
m.file = 0
match m.op:
.reserve:
return
.dbg:
if not self.described:
return
m.extra += self.locals_base
.label, .jmp:
m.extra += self.label_base
.jnz:
m.extra += self.label_base
m.extra2 += self.label_base
.switch_:
m.extra += self.label_base
m.extra2 = try self.copy_table(m.extra2)
.call:
m.extra = try self.copy_call(m.extra)
.fma, .select:
m.extra2 = try self.copy_argument(m.extra2)
.ret:
if n.extra2 > 0:
try self.leave_words(n, out)
else:
try self.leave(m.a, out)
return
_:
_ = 0
try out.push(m)
## A `ret a` of the body: the value goes to where the caller expects it, then the exit.
func leave(value: ir.Ref, out: Sink*) -> !:
if self.info.has_result:
if self.info.result_size == 0:
try out.push(ir.Instr(op = ir.store_of(self.info.result_cls), cls = ir.Class.l, dst = 0, a = value, b = ir.slot_ref(self.result_slot), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
else:
# a record result is built where the caller's call sequence would have put it
try out.push(ir.Instr(op = ir.Op.blit, cls = ir.Class.l, dst = 0, a = ir.slot_ref(self.info.result_slot), b = value, extra = self.info.result_size, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
try out.push(ir.Instr(op = ir.Op.jmp, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = self.exit_label, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
## A `ret` of the body's private result words: each goes to its place in the caller's
## result slot, where the call's `word`s are loaded from after the exit (`expand_in`).
func leave_words(n: ir.Instr, out: Sink*) -> !:
var k: u32 = 0
while k < n.extra2:
let word = self.g.args.get((usize)(n.extra + k))
let at = try word_address(self.f, out, self.info.result_slot, k)
try out.push(ir.Instr(op = ir.store_of(word.cls), cls = ir.Class.l, dst = 0, a = self.renumber(word.value), b = at, extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
k += 1
try out.push(ir.Instr(op = ir.Op.jmp, cls = ir.Class.l, dst = 0, a = ir.none_ref(), b = ir.none_ref(), extra = self.exit_label, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
## A jump table of the body joins the caller's, its labels renumbered; its new index.
func copy_table(index: u32) -> u32!:
let table = self.g.jump_tables.get((usize)index)
let start = u32(self.f.jump_labels.count)
for k in 0..<table.count:
try self.f.jump_labels.push(self.g.jump_labels.get((usize)(table.start + k)) + self.label_base)
try self.f.jump_tables.push(ir.Table(low = table.low, start = start, count = table.count))
return u32(self.f.jump_tables.count - 1)
## A call inside the body: its description and arguments join the caller's lists.
func copy_call(extra: u32) -> u32!:
var info = self.g.calls.get((usize)extra)
let start = u32(self.f.args.count)
var k: u32 = 0
while k < info.args_count:
var a = self.g.args.get((usize)(info.args_start + k))
a.value = self.renumber(a.value)
try self.f.args.push(a)
k += 1
info.args_start = start
if info.has_result and info.result_size > 0:
info.result_slot = self.slot_of(info.result_slot)
try self.f.calls.push(info)
return u32(self.f.calls.count - 1)
## An argument of the body (`fma`'s addend) joins the caller's list; its new index.
func copy_argument(index: u32) -> u32!:
var a = self.g.args.get((usize)index)
a.value = self.renumber(a.value)
try self.f.args.push(a)
return u32(self.f.args.count - 1)
## A reference of the body as the caller numbers it.
func renumber(r: ir.Ref) -> ir.Ref:
var out = r
if r.kind == ir.RefKind.temp:
out.index += self.temp_base
elif r.kind == ir.RefKind.slot:
out.index = self.slot_of(r.index)
return out
## The body's slot `old` as the caller numbers it: a parameter's own when the rest are
## shared (own_slots).
func slot_of(old: u32) -> u32:
if (usize)old < self.own_slots.length and self.own_slots[(usize)old] != no_slots:
return self.own_slots[(usize)old]
return self.slot_base + old
# mark: Finding functions by name ==============================================================
## The program's functions by symbol.
struct Index:
var names: hashed.Table[str]
static func over(program: ir.Unit*) -> Index!:
var index = Index(names = try hashed.Table[str].create(program.functions.count))
for i in 0..<program.functions.count:
_ = try index.names.add(program.functions.items[i].name, i)
return index
func find(name: str) -> usize?:
return self.names.find(name)
func release():
self.names.destroy()
# mark: After the second pass =================================================================
## Whether `g` calls anything: a leaf's body is all an expansion adds.
## Whether `g` calls a function of the program: a call of the C library (`hypot` in a
## `Vector3.length`) leaves it a leaf, since nothing it calls can be expanded in turn.
func calls_the_program(g: ir.Function*, index: Index*) -> bool:
for n in g.instrs.span():
if n.op == ir.Op.call:
if n.a.kind != ir.RefKind.function or index.find(n.a.name) != none:
return true
return false
## Drop the stores into slots nothing reads. A slot counts as unread when every use of it,
## directly or through an address taken of it, is the place of a store.
func drop_unread_stores(f: ir.Function*) -> !:
let ns = f.slots.count
if ns == 0:
return
# per temporary, 1 + the slot whose address it holds
let address_of = try new u32[f.temps.count + 1] ---
defer free(address_of)
for t in 0..<address_of.length:
address_of[t] = 0
let read = try new bool[ns] ---
defer free(read)
clear_flags(read)
for n in f.instrs.span():
if n.op == ir.Op.addr and n.a.kind == ir.RefKind.slot and n.dst != 0:
address_of[n.dst] = n.a.index + 1
for n in f.instrs.span():
if n.op == ir.Op.addr and n.a.kind == ir.RefKind.slot:
continue
mark_read(n.a, address_of, read)
if not is_store_op(n.op):
mark_read(n.b, address_of, read)
let (start, count) = ir.argument_range(f, n)
for k in 0..<count:
mark_read(f.args.get(start + k).value, address_of, read)
if n.op == ir.Op.call:
let info = f.calls.get(n.extra)
if info.has_result and info.result_size > 0 and not info.result_words and (usize)info.result_slot < ns:
read[info.result_slot] = true
for parameter in f.params.span():
read[parameter.slot] = true
var kept = try list.List[ir.Instr].create(f.instrs.count)
for n in f.instrs.span():
if is_store_op(n.op):
let k = slot_named(n.b, address_of)
if k != 0 and not read[(usize)k - 1]:
continue
try kept.push(n)
f.instrs.destroy()
f.instrs = kept
## Note the slot an operand names, directly or through an address of it, as read.
func mark_read(r: ir.Ref, address_of: u32[], read: bool[]):
let k = slot_named(r, address_of)
if k != 0:
read[(usize)k - 1] = true
## The slot, 1-based, an operand names or holds the address of; 0 for none.
func slot_named(r: ir.Ref, address_of: u32[]) -> u32:
if r.kind == ir.RefKind.slot:
return r.index + 1
if r.kind == ir.RefKind.temp and (usize)r.index < address_of.length:
return address_of[r.index]
return 0
## Whether `op` stores a register to memory: `storeb` through `storehf`.
func is_store_op(op: ir.Op) -> bool:
return (u8)op >= (u8)ir.Op.storeb and (u8)op <= (u8)ir.Op.storehf
## Drop each block that follows an unconditional exit and whose label no jump names, then
## each jump to the label that follows it. Only `jmp`, `jnz` and `switch` name labels once
## the phis are gone.
func drop_unreached(f: ir.Function*) -> !:
let named = try new bool[(usize)f.labels + 1] ---
defer free(named)
clear_flags(named)
for n in f.instrs.span():
if n.op == ir.Op.jmp and (usize)n.extra < named.length:
named[n.extra] = true
elif n.op == ir.Op.jnz:
if (usize)n.extra < named.length:
named[n.extra] = true
if (usize)n.extra2 < named.length:
named[n.extra2] = true
elif n.op == ir.Op.switch_:
if (usize)n.extra < named.length:
named[n.extra] = true
for label in f.table_targets(n.extra2):
if (usize)label < named.length:
named[label] = true
var kept = try list.List[ir.Instr].create(f.instrs.count)
var skipping = false
var exited = false
for n in f.instrs.span():
if n.op == ir.Op.label:
skipping = exited and (usize)n.extra < named.length and not named[n.extra]
exited = false
if skipping:
continue
exited = n.op == ir.Op.jmp or n.op == ir.Op.ret or n.op == ir.Op.trap_
try kept.push(n)
f.instrs.destroy()
f.instrs = kept
var tidied = try list.List[ir.Instr].create(f.instrs.count)
var ix: usize = 0
while ix < f.instrs.count:
let n = f.instrs.get(ix)
ix += 1
if n.op == ir.Op.jmp and ix < f.instrs.count and f.instrs.get(ix).op == ir.Op.label and f.instrs.get(ix).extra == n.extra:
continue
try tidied.push(n)
f.instrs.destroy()
f.instrs = tidied