dymokomi/luce-base
Source of release 0.44.0
0.44.0 / src / back / native / regalloc.lucb
#==============================================================================================
#
# back/native/regalloc - Registers for the temporaries, by their exact lives
#
# DESCRIPTION:
# Linear scan over intervals with holes (Wimmer and Franz), after the optimiser has
# brought a function out of single-assignment form. Liveness is computed by dataflow
# over the blocks, so a temporary's interval is exactly the positions it is live at:
# a value defined in one arm of a branch and used after the join does not hold its
# register through the other arm. A target offers two pools per register class: the
# callee-saved registers, which a call preserves, and the caller-saved ones, which a
# call or an asm block may clobber, so a temporary that crosses neither takes a
# caller-saved register first and leaves the callee-saved ones, which cost a save and
# a restore, to the temporaries that need them. A copy's destination prefers its
# source's register, so the parallel copies `dessa` wrote for the phis cost nothing
# when the two do not overlap. A temporary that crosses a call takes a callee-saved
# register if one is free, else a caller-saved one that the generator saves to the
# temporary's frame home before each barrier it crosses and reloads after (`saved`).
# When every register is taken, the temporaries whose reads and writes weigh least
# for the span of their lives, ten times as much in a loop as outside it (`cost`,
# `density`), go to the frame for their whole life: a value read at once keeps its
# register before one read rarely across a long stretch. Nothing is split, since the
# generators read a temporary from one place.
#
#==============================================================================================
import back.ir.cfg
import back.ir.ir
import back.opt.ssa
import memory
import support.list
## The sentinel position meaning "no instruction"; a doubled index never reaches it.
pub let no_position: u32 = 0xFFFFFFFF
# mark: Register pools ========================================================================
## What a target offers the temporaries, as runs of register codes: the callee-saved
## integer registers are codes 1 to `callee_ints`, the callee-saved float registers follow,
## then the caller-saved integer ones, then the caller-saved float ones, which vectors
## also take.
pub struct Pools:
## The number of callee-saved integer registers (codes 1..callee_ints).
pub var callee_ints: u8
## The number of callee-saved float registers, following the integer ones.
pub var callee_floats: u8
## The number of caller-saved integer registers, following the callee-saved ones.
pub var scratch_ints: u8
## The number of caller-saved float (and vector) registers, last.
pub var scratch_floats: u8
## How many register codes the pools hold in all.
pub func count() -> u8:
return self.callee_ints + self.callee_floats + self.scratch_ints + self.scratch_floats
## Whether `code` names a float register.
pub func is_float(code: u8) -> bool:
let callee = self.callee_ints + self.callee_floats
return (code > self.callee_ints and code <= callee) or code > callee + self.scratch_ints
## An instruction that names registers of the pools itself (x86-64's division in rdx:rax,
## a shift by a count in cl): no temporary live across it may hold one of `codes`. Its
## operands and result may; the generator moves them around it.
pub struct Clobber:
## The instruction's index.
pub var at: u32
## Bit `c - 1` for each register code `c` it overwrites.
pub var codes: u64
# mark: Live ranges ===========================================================================
## One run of positions a temporary is live at: `from` to `to`, one past the last.
struct Range:
var low: u32
var high: u32
var next: u32
## A position a temporary is read at.
struct Use:
var at: u32
var next: u32
## The lives of a function's temporaries: each one's ranges, earliest first, its uses, and
## whether a call or an asm block lies inside it. Positions are doubled: instruction `i`
## reads its operands at `2i` and writes its result at `2i + 1`, so a result may take the
## register of an operand that dies there, as the generators compute in place.
pub struct Lives:
var count: usize
var start: u32[]
var end: u32[]
var head: u32[]
var use_head: u32[]
var crosses: bool[]
## Whether an asm block reads or writes the temporary: it may never be in a caller-saved
## register, since loading the block's operands clobbers them.
var asm_bound: bool[]
## Whether the temporary, crossing a call, holds a caller-saved register all the same and
## is saved to its frame home before each barrier it crosses and reloaded after
## (`crossed_barriers`): the callee-saved ones were all taken.
pub var saved: bool[]
## The temporary whose register this one prefers, 0 for none: a copy's source.
var hint: u32[]
## What a read at each instruction weighs: its block's loop weight (`cfg.loops`), ten
## for each loop the block is inside, so the paths that leave a loop weigh as little
## as code outside it, however the blocks are laid out.
var weights: u32[]
## By temporary, the weight of the instructions that write it: the stores it would take
## living in the frame.
var writes: u64[]
var ranges: list.List[Range]
var uses: list.List[Use]
## The doubled position temporary `t`'s life begins at, `no_position` when it has none.
pub func life_start(t: u32) -> u32:
return self.start[(usize)t]
## Temporary `t` needs no register nor home (`remat`): it has no life to allocate.
pub func forget(t: u32):
self.start[(usize)t] = no_position
self.head[(usize)t] = no_position
## The doubled position temporary `t`'s life ends at, 0 when it has none.
pub func life_end(t: u32) -> u32:
return self.end[(usize)t] if self.start[(usize)t] != no_position else 0
## The lives of `f`'s temporaries over its graph `g`, whose loops are found
## (`cfg.Graph.loops`). Every allocation is the current allocator's; `release` gives
## them back.
pub static func over(f: ir.Function*, g: cfg.Graph*) -> Lives!:
let n = f.temps.count
let m = f.instrs.count
var l = Lives(count = n, start = try new u32[n + 1] ---, end = try new u32[n + 1] ---, head = try new u32[n + 1] ---, use_head = try new u32[n + 1] ---,
crosses = try new bool[n + 1] ---, asm_bound = try new bool[n + 1] ---, saved = try new bool[n + 1] ---, hint = try new u32[n + 1] ---, weights = try new u32[m + 1] ---, writes = try new u64[n + 1] ---, ranges = try list.List[Range].create(2 * m + n + 2),
uses = try list.List[Use].create(3 * m + 2))
var t: usize = 0
while t <= n:
l.start[t] = no_position
l.end[t] = 0
l.head[t] = no_position
l.use_head[t] = no_position
l.crosses[t] = false
l.asm_bound[t] = false
l.saved[t] = false
l.hint[t] = 0
l.writes[t] = 0
t += 1
l.weigh(f, g)
var live = try ssa.Liveness.over(f, g)
defer live.release()
# blocks from the last to the first, and each backwards, so that a range is always
# added before the ranges that precede it and only the head can merge
var bi = g.blocks.count
while bi > 0:
bi -= 1
let block = g.blocks.get(bi)
if block.end <= block.start:
continue
var w: usize = 0
while w < live.words:
var bits = live.live_out[bi * live.words + w]
var bit: u32 = 0
while bits != 0:
if (bits & 1) != 0:
let t2 = u32(w * 64) + bit
if t2 >= 1 and (usize)t2 <= n:
try l.add_range(t2, 2 * block.start, 2 * block.end)
bits >>= 1
bit += 1
w += 1
var i = block.end
while i > block.start:
i -= 1
let x = f.instrs.get((usize)i)
if x.dst != 0 and (usize)x.dst <= n:
# a call's words are all written as it returns (`word`), so they are all
# defined where the first is: an unread one still keeps its own register
try l.define_at(x.dst, 2 * word_start(f, i) + 1 if x.op == ir.Op.word else 2 * i + 1)
if x.op == ir.Op.dbg:
# what a debugger reads is no use: the value's life is its own
continue
try l.use_at(x.a, 2 * block.start, 2 * i)
try l.use_at(x.b, 2 * block.start, 2 * i)
let (args_start, args_count) = ir.argument_range(f, x)
var a: u32 = 0
while a < args_count:
try l.use_at(f.args.get((usize)(args_start + a)).value, 2 * block.start, 2 * i)
a += 1
# a copy, and a word's zero-extension, which the generator leaves out when
# the two share a register and the word's upper half is zero already
if (x.op == ir.Op.copy or x.op == ir.Op.extuw) and x.a.kind == ir.RefKind.temp and x.dst != 0:
l.hint[(usize)x.dst] = x.a.index
# A loop phi is usually allocated before its backedge value.
# The reverse preference lets that later value reuse the phi's
# register when their live ranges do not overlap.
if l.hint[(usize)x.a.index] == 0:
l.hint[(usize)x.a.index] = x.dst
try l.mark_barriers(f)
return l
## Which temporaries a call or an asm block clobbers (`crosses`), and which an asm block
## binds (`asm_bound`).
func mark_barriers(f: ir.Function*) -> !:
let n = self.count
let m = f.instrs.count
# what a call or an asm block clobbers: the caller-saved registers of every
# temporary live across it; a copy, a zeroing, or a fill of many bytes is a call
# to the C library's routine in either generator. The barriers' positions in
# order, and each temporary's ranges searched for one inside
var barriers = try list.List[u32].create(16)
defer barriers.destroy()
# an asm block's operands go into the registers it names, any of them, one after
# another before it (`set_reg`), and its outputs are stored through their addresses
# (`get_reg`) after its text: what an operand reads, an output's address, and every
# value live across an operand's move stay out of the caller-saved registers
var operands = try list.List[u32].create(4)
defer operands.destroy()
var p: usize = 0
while p < m:
let x = f.instrs.get(p)
if x.op == ir.Op.set_reg or x.op == ir.Op.get_reg:
self.mark_at(x.a, n)
if x.op == ir.Op.set_reg:
try operands.push(u32(2 * p))
if is_barrier(x):
try barriers.push(u32(2 * p))
# an asm block's operands are loaded into registers the lowerer chose from
# the same caller-saved set, in an order that may clobber an operand still
# to be read: a value the block reads or writes stays out of them
if x.op == ir.Op.asm_:
self.mark_at(x.a, n)
self.mark_at(x.b, n)
if x.dst != 0 and (usize)x.dst <= n:
self.crosses[(usize)x.dst] = true
self.asm_bound[(usize)x.dst] = true
p += 1
if barriers.count > 0:
var t3: usize = 1
while t3 <= n:
if not self.crosses[t3] and self.spans_barrier(u32(t3), barriers.span()):
self.crosses[t3] = true
if operands.count > 0 and not self.asm_bound[t3] and self.spans_barrier(u32(t3), operands.span()):
self.crosses[t3] = true
self.asm_bound[t3] = true
t3 += 1
## The temporary `r` names, when it is one, must survive an asm block.
func mark_at(r: ir.Ref, n: usize):
if r.kind == ir.RefKind.temp and (usize)r.index <= n:
self.crosses[(usize)r.index] = true
self.asm_bound[(usize)r.index] = true
## Whether one of the sorted barrier positions lies inside a range of `t`: a barrier
## at `p` is inside when `low <= p` and `high > p + 1`, so the value is live at the
## instruction's reads and still after its result.
func spans_barrier(t: u32, barriers: u32[]) -> bool:
var r = self.head[(usize)t]
while r != no_position:
let range = self.ranges.items[(usize)r]
# the first barrier at or after the range's start
var lo: usize = 0
var hi: usize = barriers.length
while lo < hi:
let mid = (lo + hi) // 2
if barriers[mid] < range.low:
lo = mid + 1
else:
hi = mid
if lo < barriers.length and barriers[lo] + 1 < range.high:
return true
r = range.next
return false
## Free the lives' backing storage.
pub func release():
free(self.start)
free(self.end)
free(self.head)
free(self.use_head)
free(self.crosses)
free(self.asm_bound)
free(self.saved)
free(self.hint)
free(self.weights)
free(self.writes)
self.ranges.destroy()
self.uses.destroy()
## Each instruction's weight, its block's loop weight, and what the writes of each
## temporary weigh.
func weigh(f: ir.Function*, g: cfg.Graph*):
for i in 0..<self.weights.length:
self.weights[i] = 1
for block in g.blocks.span():
# a label belongs to the block it heads
let labelled = block.start > 0 and f.instrs.get((usize)block.start - 1).op == ir.Op.label
let first = block.start - 1 if labelled else block.start
for i in first..<block.end:
self.weights[(usize)i] = block.loop_weight if block.loop_weight > 0 else 1
for i in 0..<f.instrs.count:
let x = f.instrs.get(i)
if x.dst != 0 and (usize)x.dst <= self.count:
self.writes[(usize)x.dst] += (u64)self.weights[i]
## Add `[low, high)` to temporary `t`: merged into the head range when they touch.
func add_range(t: u32, low: u32, high: u32) -> !:
let h = self.head[(usize)t]
let k = (usize)h
if h != no_position and self.ranges.items[k].low <= high:
if low < self.ranges.items[k].low:
self.ranges.items[k].low = low
if high > self.ranges.items[k].high:
self.ranges.items[k].high = high
else:
self.head[(usize)t] = u32(self.ranges.count)
try self.ranges.push(Range(low = low, high = high, next = h))
if low < self.start[(usize)t]:
self.start[(usize)t] = low
if high > self.end[(usize)t]:
self.end[(usize)t] = high
## Temporary `t` is defined at `at`: its head range begins there; a value nothing reads
## still occupies its register at the instruction that writes it.
func define_at(t: u32, at: u32) -> !:
let h = self.head[(usize)t]
let k = (usize)h
if h != no_position and self.ranges.items[k].low <= at and at < self.ranges.items[k].high:
# the blocks are walked last first, so the head range is the lowest and the
# temporary's life now starts at its definition, not where its block does: a
# value read for the last time by the instruction defining another leaves its
# register to that one (a loop's `acc |= x` keeps acc's register)
self.ranges.items[k].low = at
self.start[(usize)t] = at
return
try self.add_range(t, at, at + 1)
## `r`, when a temporary, is read at `at` inside a block beginning at `block_start`.
func use_at(r: ir.Ref, block_start: u32, at: u32) -> !:
if r.kind != ir.RefKind.temp or (usize)r.index > self.count:
return
try self.add_range(r.index, block_start, at + 1)
let previous = self.use_head[(usize)r.index]
self.use_head[(usize)r.index] = u32(self.uses.count)
try self.uses.push(Use(at = at, next = previous))
## Whether a range of `t` reaches across the instruction reading at position `p`: the
## value is live at `p` (defined earlier, or live into the block there) and still
## after the instruction's own result at `p + 1`, so it must survive what `p` clobbers.
pub func covers_across(t: u32, p: u32) -> bool:
var r = self.head[(usize)t]
while r != no_position:
let range = self.ranges.items[(usize)r]
if range.low > p:
return false
if range.high > p + 1:
return true
r = range.next
return false
## Whether `t` is live at `p`; the ranges ascend from the head, so the walk stops at
## the first that begins after `p`.
func covers(t: u32, p: u32) -> bool:
var r = self.head[(usize)t]
while r != no_position:
let range = self.ranges.items[(usize)r]
if range.low > p:
return false
if p < range.high:
return true
r = range.next
return false
## The first position where `a` and `b` are both live, or `no_position`: one walk
## down both ascending range lists.
func first_intersection(a: u32, b: u32) -> u32:
var ra = self.head[(usize)a]
var rb = self.head[(usize)b]
while ra != no_position and rb != no_position:
let x = self.ranges.items[(usize)ra]
let y = self.ranges.items[(usize)rb]
let low = x.low if x.low > y.low else y.low
let high = x.high if x.high < y.high else y.high
if low < high:
return low
if x.high <= y.high:
ra = x.next
else:
rb = y.next
return no_position
## What keeping `t` in the frame for its whole life costs, as eviction would: a load
## for each read and a store for each write, each weighing its block's loop weight.
func cost(t: u32) -> u64:
var total: u64 = 0
var u = self.use_head[(usize)t]
while u != no_position:
let use = self.uses.items[(usize)u]
let i = (usize)(use.at // 2)
total += (u64)(self.weights[i] if i < self.weights.length else 1)
u = use.next
return total + self.writes[(usize)t]
## What keeping `t` in the frame costs for each position of its life it holds a register
## (`cost` over its span, scaled): a value read often in a short life weighs more than one
## read as often over a long one, which would hold the register through other lives.
func density(t: u32) -> u64:
let total = self.cost(t)
if self.start[(usize)t] == no_position:
return total
let span = (u64)(self.end[(usize)t] - self.start[(usize)t]) + 2
return total * 65536 // span
## The most temporaries of each class live at one position: integers, then floats.
pub func pressure(f: ir.Function*) -> (u32, u32)!:
let m = 2 * f.instrs.count + 3
var delta_int = try new i32[m] ---
defer free(delta_int)
var delta_float = try new i32[m] ---
defer free(delta_float)
var k: usize = 0
while k < m:
delta_int[k] = 0
delta_float[k] = 0
k += 1
var t: usize = 1
while t <= self.count:
let c = f.temp_class(u32(t))
let is_int = c == ir.Class.w or c == ir.Class.l
if is_int or ir.is_float_class(c):
var r = self.head[t]
while r != no_position:
let range = self.ranges.items[(usize)r]
if is_int:
delta_int[(usize)range.low] += 1
delta_int[(usize)range.high] -= 1
else:
delta_float[(usize)range.low] += 1
delta_float[(usize)range.high] -= 1
r = range.next
t += 1
var ints: i32 = 0
var floats: i32 = 0
var live_int: i32 = 0
var live_float: i32 = 0
k = 0
while k < m:
live_int += delta_int[k]
live_float += delta_float[k]
if live_int > ints:
ints = live_int
if live_float > floats:
floats = live_float
k += 1
return ((u32)ints, (u32)floats)
## Give each temporary a register code, 0 for the frame: `held` is the mask of codes the
## promoted slots keep for the whole function, `fixed` the instructions that overwrite
## registers of the pools themselves, in order; `regs` receives a code per temporary and
## the mask of every code used comes back. A linear scan over the intervals by start.
pub func allocate(f: ir.Function*, pools: Pools, held: u64, regs: u8[], fixed: const Clobber[]) -> u64!:
let n = self.count
for t in 0..<n:
regs[t] = 0
if n == 0:
return 0
let (order, alive) = try self.by_start(f)
defer free(order)
var scan = try Scan.create(alive)
defer scan.release()
let codes = (usize)pools.count()
var free_until = try new u32[codes + 1] ---
defer free(free_until)
var holders_cost = try new u64[codes + 1] ---
defer free(holders_cost)
# what each temporary would cost in the frame for its span, once: eviction asks it of
# every holder
var costs = try new u64[n + 1] ---
defer free(costs)
for each in 1..<costs.length:
costs[each] = self.density(u32(each))
var used: u64 = 0
for i in 0..<alive:
let cur = order[i]
scan.advance(&self, self.start[(usize)cur])
let cls = f.temp_class(cur)
let is_int = cls == ir.Class.w or cls == ir.Class.l
let is_vector = cls == ir.Class.v
if not is_int and not is_vector and not ir.is_float_class(cls):
continue
let ranges = self.ranges_of(cur, is_int, is_vector, pools)
self.fill_free_until(&scan, regs, cur, free_until)
let my_end = self.end[(usize)cur]
# the promoted slots' registers, and those an instruction inside the life overwrites
let barred = held | self.overwritten(cur, fixed)
var chosen: usize = 0
# the hint: a copy's source, when its register is free for the whole life
let wanted = self.hint[(usize)cur]
if wanted != 0 and regs[(usize)wanted - 1] != 0:
let r = (usize)regs[(usize)wanted - 1]
let in_pool = (r >= ranges.low_scratch and r <= ranges.high_scratch) or (r >= ranges.low_callee and r <= ranges.high_callee)
if in_pool and (barred & ((u64)1 << (u64)(r - 1))) == 0 and free_until[r] >= my_end:
chosen = r
if chosen == 0:
chosen = pick_free(free_until, barred, ranges.low_scratch, ranges.high_scratch, my_end)
if chosen == 0:
chosen = pick_free(free_until, barred, ranges.low_callee, ranges.high_callee, my_end)
if chosen == 0 and ranges.low_saved != 0:
chosen = pick_free(free_until, barred, ranges.low_saved, ranges.high_saved, my_end)
if chosen == 0 and costs[(usize)cur] > 0:
chosen = self.evict(&scan, regs, cur, ranges, barred, costs, holders_cost)
if chosen != 0:
if ranges.low_saved != 0 and chosen >= ranges.low_saved and chosen <= ranges.high_saved:
self.saved[(usize)cur] = true
regs[(usize)cur - 1] = (u8)chosen
used = used | ((u64)1 << (u64)(chosen - 1))
scan.activate(cur)
return used
## The codes the instructions of `fixed` overwrite while `t` lives across them: live at
## an instruction's reads and still after its result (`covers_across`).
func overwritten(t: u32, fixed: const Clobber[]) -> u64:
var codes: u64 = 0
if fixed.length == 0:
return codes
var r = self.head[(usize)t]
while r != no_position:
let range = self.ranges.items[(usize)r]
# the first instruction reading at or after the range's start
var lo: usize = 0
var hi: usize = fixed.length
while lo < hi:
let mid = (lo + hi) // 2
if 2 * fixed[mid].at < range.low:
lo = mid + 1
else:
hi = mid
while lo < fixed.length and 2 * fixed[lo].at + 1 < range.high:
codes = codes | fixed[lo].codes
lo += 1
r = range.next
return codes
## The live temporaries in order of their starts, by counting, and how many there are.
func by_start(f: ir.Function*) -> (u32[], usize)!:
let n = self.count
let m = 2 * f.instrs.count + 2
var bucket = try new u32[m + 1] ---
defer free(bucket)
for k in 0..<m + 1:
bucket[k] = 0
var alive: usize = 0
for t in 1..<n + 1:
if self.start[t] != no_position:
bucket[(usize)self.start[t] + 1] += 1
alive += 1
for k in 1..<m + 1:
bucket[k] += bucket[k - 1]
var order = try new u32[alive + 1] ---
for t in 1..<n + 1:
if self.start[t] != no_position:
order[(usize)bucket[(usize)self.start[t]]] = u32(t)
bucket[(usize)self.start[t]] += 1
return (order, alive)
## The codes temporary `cur` may draw on: caller-saved first when it crosses no
## barrier, then callee-saved, then caller-saved saved around the barriers it crosses.
func ranges_of(cur: u32, is_int: bool, is_vector: bool, pools: Pools) -> Ranges:
let codes = (usize)pools.count()
let callee = (usize)pools.callee_ints + (usize)pools.callee_floats
var r = Ranges()
let crosses = self.crosses[(usize)cur]
if is_int:
if not crosses:
r.low_scratch = callee + 1
r.high_scratch = callee + (usize)pools.scratch_ints
r.low_callee = 1
r.high_callee = (usize)pools.callee_ints
else:
if not crosses:
r.low_scratch = callee + (usize)pools.scratch_ints + 1
r.high_scratch = codes
if not is_vector:
r.low_callee = (usize)pools.callee_ints + 1
r.high_callee = callee
# a temporary crossing a barrier may still take a caller-saved register, saved
# before each barrier it crosses and reloaded after, rather than the frame for its
# whole life: the barriers are usually off the hot path (a table's slow lookup, an
# error's report), the value's reads are not
if crosses and not self.asm_bound[(usize)cur]:
if is_int:
r.low_saved = callee + 1
r.high_saved = callee + (usize)pools.scratch_ints
elif not is_vector:
r.low_saved = callee + (usize)pools.scratch_ints + 1
r.high_saved = codes
return r
## Where each register is next needed at or after `cur`'s start: at once for an active
## interval's, at its first meeting with `cur` for an inactive one's, never otherwise.
func fill_free_until(scan: Scan*, regs: u8[], cur: u32, free_until: u32[]):
for c in 1..<free_until.length:
free_until[c] = no_position
for a in 0..<scan.active_count:
free_until[(usize)regs[(usize)scan.active[a] - 1]] = 0
for a in 0..<scan.inactive_count:
let h = scan.inactive[a]
let r = (usize)regs[(usize)h - 1]
let meet = self.first_intersection(h, cur)
if meet != no_position and meet < free_until[r]:
free_until[r] = meet
## Every register is taken: the one whose holders would cost least in the frame for the
## span they hold it (a read or write in a loop ten times one outside it, `density`) goes
## to `cur` when they cost less than it would, its holders moving to the frame; 0 when
## `cur` should.
func evict(scan: Scan*, regs: u8[], cur: u32, ranges: Ranges, held: u64, costs: u64[], holders_cost: u64[]) -> usize:
for c in 1..<holders_cost.length:
holders_cost[c] = 0
for a in 0..<scan.active_count:
let h = scan.active[a]
holders_cost[(usize)regs[(usize)h - 1]] += costs[(usize)h]
for a in 0..<scan.inactive_count:
let h = scan.inactive[a]
if self.first_intersection(h, cur) != no_position:
holders_cost[(usize)regs[(usize)h - 1]] += costs[(usize)h]
var far: usize = 0
var far_cost: u64 = 0xFFFFFFFFFFFFFFFF
for c in 1..<holders_cost.length:
if ranges.holds(c) and (held & ((u64)1 << (u64)(c - 1))) == 0 and holders_cost[c] < far_cost:
far_cost = holders_cost[c]
far = c
if far == 0 or far_cost >= costs[(usize)cur]:
return 0
scan.drop_holders(regs, far)
return far
## The codes a temporary may draw on, each pool a range `low..high`; an empty one is 0..0.
struct Ranges:
var low_scratch: usize = 0
var high_scratch: usize = 0
var low_callee: usize = 0
var high_callee: usize = 0
var low_saved: usize = 0
var high_saved: usize = 0
## Whether code `c` is in one of the ranges.
func holds(c: usize) -> bool:
return (c >= self.low_scratch and c <= self.high_scratch) or (c >= self.low_callee and c <= self.high_callee) or (c >= self.low_saved and c <= self.high_saved)
## The intervals that hold a register at the scan's position: the active ones cover it,
## the inactive ones have a hole there and resume later.
struct Scan:
var active: u32[]
var active_count: usize
var inactive: u32[]
var inactive_count: usize
## Room for `alive` intervals in each set.
static func create(alive: usize) -> Scan!:
let active = try new u32[alive + 1] ---
errdefer free(active)
return Scan(active = active, active_count = 0, inactive = try new u32[alive + 1] ---, inactive_count = 0)
func release():
free(self.active)
free(self.inactive)
## Move to position `s`: what ended is dropped, what has a hole here becomes inactive,
## and what resumes here active again.
func advance(lives: Lives*, s: u32):
var a: usize = 0
while a < self.active_count:
let h = self.active[a]
if lives.end[(usize)h] <= s:
self.active[a] = self.active[self.active_count - 1]
self.active_count -= 1
elif not lives.covers(h, s):
self.inactive[self.inactive_count] = h
self.inactive_count += 1
self.active[a] = self.active[self.active_count - 1]
self.active_count -= 1
else:
a += 1
a = 0
while a < self.inactive_count:
let h = self.inactive[a]
if lives.end[(usize)h] <= s:
self.inactive[a] = self.inactive[self.inactive_count - 1]
self.inactive_count -= 1
elif lives.covers(h, s):
self.active[self.active_count] = h
self.active_count += 1
self.inactive[a] = self.inactive[self.inactive_count - 1]
self.inactive_count -= 1
else:
a += 1
func activate(t: u32):
self.active[self.active_count] = t
self.active_count += 1
## Send every interval holding register `code` to the frame.
func drop_holders(regs: u8[], code: usize):
var a: usize = 0
while a < self.active_count:
if (usize)regs[(usize)self.active[a] - 1] == code:
regs[(usize)self.active[a] - 1] = 0
self.active[a] = self.active[self.active_count - 1]
self.active_count -= 1
else:
a += 1
a = 0
while a < self.inactive_count:
if (usize)regs[(usize)self.inactive[a] - 1] == code:
regs[(usize)self.inactive[a] - 1] = 0
self.inactive[a] = self.inactive[self.inactive_count - 1]
self.inactive_count -= 1
else:
a += 1
## The index of the first of the `word`s in a row that the one at `i` belongs to.
func word_start(f: ir.Function*, i: u32) -> u32:
var j = i
while j > 0 and f.instrs.get((usize)j - 1).op == ir.Op.word:
j -= 1
return j
# mark: Barriers and free registers ===========================================================
## An instruction that may clobber the caller-saved registers: a call, an asm block, and
## the block operations the generators hand to `memcpy` and `memset` past their inline size.
pub func is_barrier(x: ir.Instr) -> bool:
# a copy or zeroing of up to `inline_block` bytes is loads and stores through registers no
# temporary takes (x16/x17 on arm64, %rax/%xmm8 on x86_64): a struct copy in a loop does
# not push the values live across it out of the caller-saved registers
if (x.op == ir.Op.blit or x.op == ir.Op.zero) and x.extra <= inline_block:
return false
# `addr_tls` calls the loader's resolver on Mach-O, which keeps only the callee-saved registers
return x.op == ir.Op.call or x.op == ir.Op.asm_ or x.op == ir.Op.blit or x.op == ir.Op.zero or x.op == ir.Op.fill or x.op == ir.Op.addr_tls
## No instruction overwriting registers of the pools itself, for the tests.
let no_fixed: Clobber[1] = [Clobber(at = 0, codes = 0)]
## The most bytes the generators copy or zero with loads and stores instead of a call.
pub let inline_block: u32 = 128
## The code in `[low, high]` that stays free the longest, when one stays free for the whole
## life ending at `end`; 0 otherwise. The first of equals wins, so the lowest register.
func pick_free(free_until: u32[], held: u64, low: usize, high: usize, end: u32) -> usize:
var best: usize = 0
var best_until: u32 = 0
var c = low
while c != 0 and c <= high:
if (held & ((u64)1 << (u64)(c - 1))) == 0 and free_until[c] > best_until:
best_until = free_until[c]
best = c
c += 1
if best != 0 and best_until >= end:
return best
return 0
test "a temporary across a call keeps a callee-saved register and one beside it a scratch one":
var backing: u8[1048576]
var arena = memory.FixedBuffer.over(backing)
with arena:
var f = try ir.Function.create("t")
# t1 = 1; t2 = 2; call g(); t3 = t1 + t2 (t1, t2 cross the call); t4 = t3 + 1 (t4 does not)
let t1 = try f.temp(ir.Class.l)
let t2 = try f.temp(ir.Class.l)
try f.emit(ir.Op.copy, ir.Class.l, t1, ir.const_ref(1), ir.none_ref(), 0)
try f.emit(ir.Op.copy, ir.Class.l, t2, ir.const_ref(2), ir.none_ref(), 0)
try f.calls.push(ir.CallInfo(args_start = 0, args_count = 0, fixed_count = 0, variadic = false, result_cls = ir.Class.w, has_result = false, result_size = 0, result_align = 8, result_type = 0, result_slot = 0, result_shape = 0))
try f.emit(ir.Op.call, ir.Class.w, 0, ir.function_ref("g"), ir.none_ref(), 0)
let t3 = try f.temp(ir.Class.l)
try f.emit(ir.Op.add, ir.Class.l, t3, ir.temp_ref(t1), ir.temp_ref(t2), 0)
let t4 = try f.temp(ir.Class.l)
try f.emit(ir.Op.add, ir.Class.l, t4, ir.temp_ref(t3), ir.const_ref(1), 0)
let t5 = try f.temp(ir.Class.l)
try f.emit(ir.Op.copy, ir.Class.l, t5, ir.temp_ref(t4), ir.none_ref(), 0)
try f.emit(ir.Op.ret, ir.Class.l, 0, ir.temp_ref(t5), ir.none_ref(), 0)
var g = try cfg.Graph.over(&f)
var lives = try Lives.over(&f, &g)
assert(lives.crosses[(usize)t1])
assert(lives.crosses[(usize)t2])
assert(not lives.crosses[(usize)t3])
assert(not lives.crosses[(usize)t4])
let (ints, floats) = try lives.pressure(&f)
assert(ints == 2)
assert(floats == 0)
var regs: u8[8]
let pools = Pools(callee_ints = 2, callee_floats = 1, scratch_ints = 2, scratch_floats = 1)
let used = try lives.allocate(&f, pools, 0, regs[..<5], no_fixed[0..<0])
assert(regs[0] == 1 and regs[1] == 2)
# t3 does not cross the call: the first scratch code, 4
assert(regs[2] == 4)
# t4 is a copy's source and t5 its destination: t5 takes t4's register
assert(regs[3] != 0 and regs[4] == regs[3])
assert((used & 1) != 0 and (used & 8) != 0)
lives.release()
g.release()
test "intervals have holes: two values alive in different arms share one register":
var backing: u8[1048576]
var arena = memory.FixedBuffer.over(backing)
with arena:
var f = try ir.Function.create("t")
# c = ...; jnz c, L1, L2; L1: a = 1; jmp L3; L2: b = 2; jmp L3; L3: (a used in L1 only, b in L2 only)
let c = try f.temp(ir.Class.w)
try f.emit(ir.Op.copy, ir.Class.w, c, ir.const_ref(1), ir.none_ref(), 0)
let l1 = f.label()
let l2 = f.label()
let l3 = f.label()
try f.branch(ir.temp_ref(c), l1, l2)
try f.place_label(l1)
let a = try f.temp(ir.Class.l)
try f.emit(ir.Op.copy, ir.Class.l, a, ir.const_ref(1), ir.none_ref(), 0)
let a2 = try f.temp(ir.Class.l)
try f.emit(ir.Op.add, ir.Class.l, a2, ir.temp_ref(a), ir.const_ref(1), 0)
try f.jump(l3)
try f.place_label(l2)
let b = try f.temp(ir.Class.l)
try f.emit(ir.Op.copy, ir.Class.l, b, ir.const_ref(2), ir.none_ref(), 0)
let b2 = try f.temp(ir.Class.l)
try f.emit(ir.Op.add, ir.Class.l, b2, ir.temp_ref(b), ir.const_ref(1), 0)
try f.jump(l3)
try f.place_label(l3)
try f.emit(ir.Op.ret, ir.Class.l, 0, ir.none_ref(), ir.none_ref(), 0)
var g = try cfg.Graph.over(&f)
var lives = try Lives.over(&f, &g)
assert(not lives.covers(a, lives.start[(usize)b]))
var regs: u8[8]
let pools = Pools(callee_ints = 1, callee_floats = 0, scratch_ints = 0, scratch_floats = 0)
_ = try lives.allocate(&f, pools, 0, regs[..<5], no_fixed[0..<0])
# one callee-saved register serves both arms: a and b never meet
assert(regs[(usize)a - 1] == 1 and regs[(usize)b - 1] == 1)
lives.release()
g.release()
test "a call's words take their own registers even when one is never read":
var backing: u8[1048576]
var arena = memory.FixedBuffer.over(backing)
with arena:
var f = try ir.Function.create("t")
# call g() -> two words; w0 = word 0 (unread); w1 = word 1; t = w1 + 1
try f.calls.push(ir.CallInfo(args_start = 0, args_count = 0, fixed_count = 0, variadic = false, result_cls = ir.Class.l, has_result = true, result_size = 16, result_align = 8, result_type = 0, result_slot = 0, result_shape = 0, result_private = true, result_words = true))
try f.emit(ir.Op.call, ir.Class.l, 0, ir.function_ref("g"), ir.none_ref(), 0)
let w0 = try f.temp(ir.Class.w)
try f.emit(ir.Op.word, ir.Class.w, w0, ir.none_ref(), ir.none_ref(), 0)
let w1 = try f.temp(ir.Class.w)
try f.emit(ir.Op.word, ir.Class.w, w1, ir.none_ref(), ir.none_ref(), 1)
let t = try f.temp(ir.Class.w)
try f.emit(ir.Op.add, ir.Class.w, t, ir.temp_ref(w1), ir.const_ref(1), 0)
try f.emit(ir.Op.ret, ir.Class.w, 0, ir.temp_ref(t), ir.none_ref(), 0)
var g = try cfg.Graph.over(&f)
var lives = try Lives.over(&f, &g)
# both are written as the call returns, so both live from the first word on
assert(lives.start[(usize)w0] == lives.start[(usize)w1])
var regs: u8[8]
let pools = Pools(callee_ints = 1, callee_floats = 0, scratch_ints = 2, scratch_floats = 0)
_ = try lives.allocate(&f, pools, 0, regs[..<3], no_fixed[0..<0])
assert(regs[(usize)w0 - 1] != regs[(usize)w1 - 1])
lives.release()
g.release()
test "no temporary holds a register across an instruction that overwrites it itself":
var backing: u8[1048576]
var arena = memory.FixedBuffer.over(backing)
with arena:
var f = try ir.Function.create("t")
# t1 = 1; t2 = 2; t3 = t1 / t2 (overwrites code 2); t4 = t3 + t1 (t1 crosses it)
let t1 = try f.temp(ir.Class.l)
let t2 = try f.temp(ir.Class.l)
try f.emit(ir.Op.copy, ir.Class.l, t1, ir.const_ref(1), ir.none_ref(), 0)
try f.emit(ir.Op.copy, ir.Class.l, t2, ir.const_ref(2), ir.none_ref(), 0)
let t3 = try f.temp(ir.Class.l)
try f.emit(ir.Op.udiv, ir.Class.l, t3, ir.temp_ref(t1), ir.temp_ref(t2), 0)
let t4 = try f.temp(ir.Class.l)
try f.emit(ir.Op.add, ir.Class.l, t4, ir.temp_ref(t3), ir.temp_ref(t1), 0)
try f.emit(ir.Op.ret, ir.Class.l, 0, ir.temp_ref(t4), ir.none_ref(), 0)
var g = try cfg.Graph.over(&f)
var lives = try Lives.over(&f, &g)
var regs: u8[8]
let pools = Pools(callee_ints = 0, callee_floats = 0, scratch_ints = 2, scratch_floats = 0)
var fixed: Clobber[1] = [Clobber(at = 2, codes = 2)]
_ = try lives.allocate(&f, pools, 0, regs[..<4], fixed[0..])
# t1 lives across the division: code 1, never 2; t2, its operand, and t3, its
# result, may take 2
assert(regs[(usize)t1 - 1] == 1)
assert(regs[(usize)t2 - 1] == 2)
assert(regs[(usize)t3 - 1] == 2)
lives.release()
g.release()
test "a short life read at once keeps the register a long one read rarely gives up":
var backing: u8[1048576]
var arena = memory.FixedBuffer.over(backing)
with arena:
var f = try ir.Function.create("t")
# long = 1; short = 2; a few unrelated steps; long read three times far apart, short
# once at once: by cost alone long (4) outweighs short (2) and keeps the one register;
# by cost over its span short does
_ = try f.slot(8, 8)
let long = try f.temp(ir.Class.l)
try f.emit(ir.Op.copy, ir.Class.l, long, ir.const_ref(1), ir.none_ref(), 0)
let early = try f.temp(ir.Class.l)
try f.emit(ir.Op.add, ir.Class.l, early, ir.temp_ref(long), ir.const_ref(1), 0)
try f.emit(ir.Op.storel, ir.Class.l, 0, ir.temp_ref(early), ir.slot_ref(0), 0)
let short = try f.temp(ir.Class.l)
try f.emit(ir.Op.copy, ir.Class.l, short, ir.const_ref(2), ir.none_ref(), 0)
try f.emit(ir.Op.storel, ir.Class.l, 0, ir.temp_ref(short), ir.slot_ref(0), 0)
for _ in 0..<8:
try f.emit(ir.Op.storel, ir.Class.l, 0, ir.const_ref(3), ir.slot_ref(0), 0)
let late = try f.temp(ir.Class.l)
try f.emit(ir.Op.add, ir.Class.l, late, ir.temp_ref(long), ir.temp_ref(long), 0)
try f.emit(ir.Op.ret, ir.Class.l, 0, ir.temp_ref(late), ir.none_ref(), 0)
var g = try cfg.Graph.over(&f)
var lives = try Lives.over(&f, &g)
assert(lives.cost(long) > lives.cost(short))
var regs: u8[8]
let pools = Pools(callee_ints = 1, callee_floats = 0, scratch_ints = 0, scratch_floats = 0)
_ = try lives.allocate(&f, pools, 0, regs[..<5], no_fixed[0..<0])
assert(regs[(usize)short - 1] == 1)
assert(regs[(usize)long - 1] == 0)
lives.release()
g.release()