dymokomi/luce-base
Source of release 0.43.0
0.43.0 / src / back / opt / ssa.lucb
#==============================================================================================
#
# ssa - Slots into temporaries, temporaries into single-assignment form
#
# DESCRIPTION:
# The lowerer keeps every local in a frame slot and computes through block-local
# temporaries, which is the form the generators want and the form the optimiser's
# passes cannot see through. This module brings a function to static single
# assignment, in QBE's two steps (mem.c's `promote`, then ssa.c): a slot that is
# only ever loaded and stored whole, in one class, becomes a temporary that every
# store assigns and every load reads (a parameter's slot keeps one load at the entry,
# the value the prologue put there); then each temporary assigned more than once
# gets a phi at every block of its iterated dominance frontier where it is live, and
# the definitions and uses are renamed down the dominator tree so that each
# temporary has one definition. The passes that follow rely on that; `dessa` undoes
# it before a generator sees the function.
#
#==============================================================================================
import support.list
import back.ir.cfg
import back.ir.ir
## No temporary, no instruction.
let none_index: u32 = 0xFFFFFFFF
## Where the temporaries of a function are defined and used: one instruction or one call
## argument or one phi argument per use, gathered once per pass. A use site is an
## instruction index, or an argument index under `arg_site`, or a phi argument index under
## `phi_site`.
pub let arg_site: u32 = 0x40000000
## A use site index tagged as a phi argument, an index into `phi_args`.
pub let phi_site: u32 = 0x80000000
## Every definition and use of each temporary in a function, gathered once per pass.
pub struct Uses:
## The number of definitions of each temporary, indexed by temporary.
pub var def_count: u32[]
## The instruction that defines each temporary, or `none_index`; indexed by temporary.
pub var def_at: u32[]
## The start of each temporary's run in `sites`, indexed by temporary.
pub var use_start: u32[]
## The number of use sites of each temporary, indexed by temporary.
pub var use_count: u32[]
## Every use site packed by temporary: an instruction index, or one tagged with `arg_site` or `phi_site`.
pub var sites: u32[]
## Gather every definition and use of `f`'s temporaries in one pass.
pub static func over(f: ir.Function*) -> Uses!:
let n = f.temps.count + 1
var u = Uses(def_count = try new u32[n] ---, def_at = try new u32[n] ---, use_start = try new u32[n] ---, use_count = try new u32[n] ---, sites = try new u32[1] ---)
errdefer u.release()
var t: usize = 0
while t < n:
u.def_count[t] = 0
u.def_at[t] = none_index
u.use_start[t] = 0
u.use_count[t] = 0
t += 1
# count, then place
var i: usize = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
if x.dst != 0:
u.def_count[(usize)x.dst] += 1
u.def_at[(usize)x.dst] = u32(i)
count_use(u.use_count, x.a)
count_use(u.use_count, x.b)
i += 1
i = 0
while i < f.args.count:
count_use(u.use_count, f.args.get(i).value)
i += 1
i = 0
while i < f.phi_args.count:
count_use(u.use_count, f.phi_args.get(i).value)
i += 1
var total: u32 = 0
t = 0
while t < n:
u.use_start[t] = total
total += u.use_count[t]
u.use_count[t] = 0
t += 1
try u.grow_sites((usize)total + 1)
i = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
u.place_use(x.a, u32(i))
u.place_use(x.b, u32(i))
i += 1
i = 0
while i < f.args.count:
u.place_use(f.args.get(i).value, arg_site | u32(i))
i += 1
i = 0
while i < f.phi_args.count:
u.place_use(f.phi_args.get(i).value, phi_site | u32(i))
i += 1
return u
func place_use(r: ir.Ref, site: u32):
if r.kind != ir.RefKind.temp:
return
let t = (usize)r.index
self.sites[(usize)(self.use_start[t] + self.use_count[t])] = site
self.use_count[t] += 1
## The `k`th use site of temporary `t`.
pub func use(t: u32, k: u32) -> u32:
return self.sites[(usize)(self.use_start[(usize)t] + k)]
## Room for `count` use sites, in place of the old.
func grow_sites(count: usize) -> !:
free(self.sites)
self.sites = try new u32[count] ---
## Free the gathered arrays.
pub func release():
free(self.def_count)
free(self.def_at)
free(self.use_start)
free(self.use_count)
free(self.sites)
func count_use(counts: u32[], r: ir.Ref):
if r.kind == ir.RefKind.temp:
counts[(usize)r.index] += 1
# mark: Slot promotion =========================================================================
## Not promotable, undecided, promotable.
let no: u8 = 2
let open: u8 = 0
## Turn every slot that is only loaded and stored whole into a temporary: the stores become
## copies into it, the loads copies (or extensions, for a narrow slot) out of it. A
## parameter's slot keeps a load at the entry, its incoming value. Answers whether anything
## changed.
pub func promote(f: ir.Function*) -> bool!:
let ns = f.slots.count
if ns == 0:
return false
var c = try Candidates.over(f)
defer c.release()
var addr_of = try addresses_of(f)
defer free(addr_of)
rule_out(f, &c, addr_of)
var any = false
var temp_of = try new u32[ns + 1] ---
defer free(temp_of)
for s in 0..<ns:
temp_of[s] = 0
if c.kind[s] == open and c.has_store[s]:
temp_of[s] = try f.temp(c.cls[s])
any = true
if not any:
return false
try rewrite_promoted(f, &c, temp_of, addr_of)
return true
## The slots `promote` considers, by slot: whether each is still `open`, the class its
## stores write, whether it has a store, and the bytes its accesses move.
struct Candidates:
var kind: u8[]
var cls: ir.Class[]
var has_store: bool[]
var width: u32[]
## Every slot of `f` of a register's width open, but an aggregate parameter's; a scalar
## parameter's stored at the entry, in its class. A scalar parameter's width is its own,
## since its slot is a register wide or two and the body reads only the value's bytes.
static func over(f: ir.Function*) -> Candidates!:
let ns = f.slots.count
var c = Candidates(kind = try new u8[ns + 1] ---, cls = try new ir.Class[ns + 1] ---, has_store = try new bool[ns + 1] ---, width = try new u32[ns + 1] ---)
for s in 0..<ns:
c.width[s] = f.slots.get(s).size
for param in f.params.span():
if param.size == 0 and param.scalar_width != 0:
c.width[(usize)param.slot] = param.scalar_width
for s in 0..<ns:
let size = c.width[s]
c.kind[s] = open if size == 1 or size == 2 or size == 4 or size == 8 else no
c.cls[s] = ir.Class.w
c.has_store[s] = false
for param in f.params.span():
if param.size == 0:
c.has_store[(usize)param.slot] = true
c.cls[(usize)param.slot] = param.cls
if param.cls == ir.Class.v:
c.kind[(usize)param.slot] = no
else:
c.kind[(usize)param.slot] = no
return c
func release():
free(self.kind)
free(self.cls)
free(self.has_store)
free(self.width)
## The slot whose address each temporary holds, or `none_index`, by temporary.
func addresses_of(f: ir.Function*) -> u32[]!:
var addr_of = try new u32[f.temps.count + 1] ---
for t in 0..<f.temps.count + 1:
addr_of[t] = none_index
for i in 0..<f.instrs.count:
let x = f.instrs.get(i)
if x.op == ir.Op.addr and x.a.kind == ir.RefKind.slot and x.dst != 0:
addr_of[(usize)x.dst] = x.a.index
return addr_of
## Close every slot used other than as a whole load or a whole store in one class: through
## an address that escapes, a call's aggregate result, or a load of another class.
func rule_out(f: ir.Function*, c: Candidates*, addr_of: u32[]):
var i: usize = 0
# every use of a slot, or of its address, is a whole load or a whole store in one class
while i < f.instrs.count:
let x = f.instrs.get(i)
if x.op == ir.Op.addr:
i += 1
continue
let sa = slot_of(addr_of, x.a)
let sb = slot_of(addr_of, x.b)
if sa != none_index:
if is_load(x.op) and load_fits(x.op, c.width[(usize)sa]):
_ = 0
else:
c.kind[(usize)sa] = no
if sb != none_index:
if is_store(x.op) and sa != sb and store_fits(x.op, c.width[(usize)sb]):
let k = ir.store_class(x.op)
if c.has_store[(usize)sb] and c.cls[(usize)sb] != k:
c.kind[(usize)sb] = no
c.has_store[(usize)sb] = true
c.cls[(usize)sb] = k
else:
c.kind[(usize)sb] = no
i += 1
i = 0
while i < f.args.count:
let sa = slot_of(addr_of, f.args.get(i).value)
if sa != none_index:
c.kind[(usize)sa] = no
i += 1
# a call writes its aggregate result into a slot without an instruction saying so
i = 0
while i < f.calls.count:
let info = f.calls.get(i)
if info.has_result and info.result_size > 0 and not info.result_words and (usize)info.result_slot < c.kind.length - 1:
c.kind[(usize)info.result_slot] = no
i += 1
i = 0
while i < f.phi_args.count:
let sa = slot_of(addr_of, f.phi_args.get(i).value)
if sa != none_index:
c.kind[(usize)sa] = no
i += 1
# a load must read the class the stores wrote
i = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
let sa = slot_of(addr_of, x.a)
if sa != none_index and c.kind[(usize)sa] == open and is_load(x.op):
if not c.has_store[(usize)sa] or not load_reads(x.op, c.cls[(usize)sa]):
c.kind[(usize)sa] = no
i += 1
## Rewrite `f` with the promoted slots as temporaries: the parameters' entry loads first,
## then every instruction with its slot accesses turned into copies.
func rewrite_promoted(f: ir.Function*, c: Candidates*, temp_of: u32[], addr_of: u32[]) -> !:
var out = try list.List[ir.Instr].create(f.instrs.count + f.params.count)
var p: usize = 0
while p < f.params.count:
let param = f.params.get(p)
if param.size == 0 and temp_of[(usize)param.slot] != 0:
let op = ir.load_op((u64)c.width[(usize)param.slot], false, ir.is_float_class(param.cls))
try out.push(ir.Instr(op = op, cls = param.cls, dst = temp_of[(usize)param.slot], a = ir.slot_ref(param.slot), b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
try describe(f, param.slot, temp_of[(usize)param.slot], &out)
p += 1
var i: usize = 0
while i < f.instrs.count:
var x = f.instrs.get(i)
i += 1
if x.op == ir.Op.addr and x.a.kind == ir.RefKind.slot and temp_of[(usize)x.a.index] != 0:
continue
let sa = slot_of(addr_of, x.a)
let sb = slot_of(addr_of, x.b)
if sb != none_index and temp_of[(usize)sb] != 0:
# a store: the value into the temporary, and where a named local now lives
x = ir.Instr(op = ir.Op.copy, cls = c.cls[(usize)sb], dst = temp_of[(usize)sb], a = x.a, b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0)
try out.push(x)
try describe(f, sb, temp_of[(usize)sb], &out)
continue
elif sa != none_index and temp_of[(usize)sa] != 0:
# a load: the temporary, extended as the load would have
x = ir.Instr(op = load_as(x.op, x.cls), cls = x.cls, dst = x.dst, a = ir.temp_ref(temp_of[(usize)sa]), b = ir.none_ref(), extra = 0, extra2 = 0, line = 0, file = 0, scope = 0, site = 0)
try out.push(x)
f.instrs.destroy()
f.instrs = out
## `--release --debug`: a `dbg` for each named local slot `s` describes, saying it now
## holds temporary `t` (several locals may share a slot: an inlined callee's expansions do).
func describe(f: ir.Function*, s: u32, t: u32, out: list.List[ir.Instr]*) -> !:
if not f.symbols:
return
var k: usize = 0
while k < f.locals.count:
if f.locals.get(k).slot == s:
try out.push(ir.Instr(op = ir.Op.dbg, cls = f.temp_class(t), dst = 0, a = ir.temp_ref(t), b = ir.none_ref(), extra = u32(k), extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
k += 1
## The slot an operand names: directly, or through the temporary holding its address.
func slot_of(addr_of: u32[], r: ir.Ref) -> u32:
if r.kind == ir.RefKind.slot:
return r.index
if r.kind == ir.RefKind.temp and (usize)r.index < addr_of.length:
return addr_of[(usize)r.index]
return none_index
## Whether `op` is one of the typed load instructions.
pub func is_load(op: ir.Op) -> bool:
return (u8)op >= (u8)ir.Op.loadsb and (u8)op <= (u8)ir.Op.loadhf
## Whether `op` is one of the typed store instructions.
pub func is_store(op: ir.Op) -> bool:
return (u8)op >= (u8)ir.Op.storeb and (u8)op <= (u8)ir.Op.storehf
func load_width(op: ir.Op) -> u32:
match op:
.loadsb, .loadub: return 1
.loadsh, .loaduh, .loadhf: return 2
.loadsw, .loaduw, .loads: return 4
_: return 8
func store_width(op: ir.Op) -> u32:
match op:
.storeb: return 1
.storeh, .storehf: return 2
.storew, .stores: return 4
_: return 8
func load_fits(op: ir.Op, size: u32) -> bool:
return load_width(op) == size
func store_fits(op: ir.Op, size: u32) -> bool:
return store_width(op) == size
## Whether a load reads a slot the stores wrote in class `k`.
func load_reads(op: ir.Op, k: ir.Class) -> bool:
match op:
.loads: return k == ir.Class.s
.loadd: return k == ir.Class.d
.loadhf: return k == ir.Class.h
.loadl: return k == ir.Class.l
_: return k == ir.Class.w
## The instruction a load becomes when its slot is a temporary: a copy, or the extension
## the load performed.
func load_as(op: ir.Op, cls: ir.Class) -> ir.Op:
match op:
.loadsb: return ir.Op.extsb
.loadub: return ir.Op.extub
.loadsh: return ir.Op.extsh
.loaduh: return ir.Op.extuh
.loadsw: return ir.Op.extsw if cls == ir.Class.l else ir.Op.copy
.loaduw: return ir.Op.extuw if cls == ir.Class.l else ir.Op.copy
_: return ir.Op.copy
# mark: Liveness ===============================================================================
## Which temporaries are live at each block's entry and exit, as bit sets.
pub struct Liveness:
## The number of 64-bit words in each block's live set, one bit per temporary.
pub var words: usize
## Each block's live-in set, `words` words per block, indexed by block.
pub var live_in: u64[]
## Each block's live-out set, `words` words per block, indexed by block.
pub var live_out: u64[]
## Compute per-block liveness for `f` over its control-flow graph `g`.
pub static func over(f: ir.Function*, g: cfg.Graph*) -> Liveness!:
let words = (f.temps.count + 1 + 63) // 64
let nb = g.count()
var l = Liveness(words = words, live_in = try new u64[words * nb + 1] ---, live_out = try new u64[words * nb + 1] ---)
var k: usize = 0
while k < l.live_in.length:
l.live_in[k] = 0
l.live_out[k] = 0
k += 1
var gen = try new u64[words + 1] ---
defer free(gen)
var changed = true
while changed:
changed = false
var r: usize = g.order.count
while r > 0:
r -= 1
let b = g.order.get(r)
let block = g.blocks.get((usize)b)
# out = union of successors' in, with the successors' phis reading from here
k = 0
while k < words:
gen[k] = 0
k += 1
for s in block.succs.span():
l.live_on(f, g, s, b, gen)
k = 0
while k < words:
if l.live_out[(usize)b * words + k] != gen[k]:
changed = true
l.live_out[(usize)b * words + k] = gen[k]
k += 1
# in = out - defs + uses, backwards over the block
var i: u32 = block.end
while i > block.start:
i -= 1
let x = f.instrs.get((usize)i)
if x.op == ir.Op.phi:
clear_bit(gen, x.dst)
continue
if x.dst != 0:
clear_bit(gen, x.dst)
if x.op == ir.Op.dbg:
continue
set_use(gen, x.a)
set_use(gen, x.b)
let (args_start, args_count) = ir.argument_range(f, x)
var a: u32 = 0
while a < args_count:
set_use(gen, f.args.get((usize)(args_start + a)).value)
a += 1
k = 0
while k < words:
if l.live_in[(usize)b * words + k] != gen[k]:
changed = true
l.live_in[(usize)b * words + k] = gen[k]
k += 1
return l
## What successor `s` needs live at the end of `b`: its live-in, minus its phis'
## results, plus what its phis take from `b`.
func live_on(f: ir.Function*, g: cfg.Graph*, s: u32, b: u32, out: u64[]):
if s == cfg.none_block:
return
let block = g.blocks.get((usize)s)
let from_label = g.blocks.get((usize)b).label
var k: usize = 0
while k < self.words:
out[k] |= self.live_in[(usize)s * self.words + k]
k += 1
var i = block.start
while i < block.end:
let x = f.instrs.get((usize)i)
if x.op != ir.Op.phi:
break
clear_bit(out, x.dst)
var a: u32 = 0
while a < x.extra2:
let arg = f.phi_args.get((usize)(x.extra + a))
if arg.pred == from_label:
set_use(out, arg.value)
a += 1
i += 1
## Whether temporary `t` is live at the entry of block `b`.
pub func live_in_at(b: u32, t: u32) -> bool:
return (self.live_in[(usize)b * self.words + (usize)t // 64] & ((u64)1 << ((u64)t % 64))) != 0
## Free the liveness bit sets.
pub func release():
free(self.live_in)
free(self.live_out)
func set_use(bits: u64[], r: ir.Ref):
if r.kind == ir.RefKind.temp:
bits[(usize)r.index // 64] |= (u64)1 << ((u64)r.index % 64)
func clear_bit(bits: u64[], t: u32):
bits[(usize)t // 64] &= ~((u64)1 << ((u64)t % 64))
# mark: Phi insertion and renaming =============================================================
## Bring `f` to single-assignment form: phis for the temporaries assigned more than once,
## then one name per definition. `g` is the graph of `f` as it stands; the function's
## instructions are rebuilt (phis join the block heads) and the graph is built again.
pub func construct(f: ir.Function*, g: cfg.Graph*) -> cfg.Graph!:
var uses = try Uses.over(f)
defer uses.release()
let n = f.temps.count + 1
var block_at = try blocks_of_instrs(f, g)
defer free(block_at)
let (renamed, any) = try renamed_temps(&uses, block_at, n)
defer free(renamed)
if not any:
return try cfg.Graph.over(f)
var live = try Liveness.over(f, g)
defer live.release()
var phis = try place_phis(f, g, &live, renamed, block_at)
defer phis.destroy()
var origin = try insert_phis(f, g, &phis)
defer origin.destroy()
var g2 = try cfg.Graph.over(f)
# renaming down the dominator tree
var current = try new u32[n] ---
defer free(current)
for t in 0..<n:
current[t] = 0
var log = try list.List[Undo].create(64)
defer log.destroy()
try rename(f, &g2, 0, renamed, current, &log, &origin)
return g2
## The temporaries to rename, by temporary: those assigned more than once, or assigned
## outside the entry and used in another block; and whether there is any.
func renamed_temps(uses: Uses*, block_at: u32[], n: usize) -> (bool[], bool)!:
var renamed = try new bool[n] ---
var t: usize = 0
while t < n:
renamed[t] = false
t += 1
var any = false
t = 1
while t < n:
if uses.def_count[t] > 1:
renamed[t] = true
any = true
elif uses.def_count[t] == 1:
let db = block_at[(usize)uses.def_at[t]]
var k: u32 = 0
while k < uses.use_count[t]:
let site = uses.use(u32(t), k)
if (site & (arg_site | phi_site)) == 0 and block_at[(usize)site] != db:
renamed[t] = true
any = true
elif (site & arg_site) != 0:
# a call argument: the call is in some block; find it through the call
_ = 0
k += 1
t += 1
return (renamed, any)
## Where phis go: for each renamed temporary, the iterated dominance frontier of the
## blocks defining it, where it is live in.
func place_phis(f: ir.Function*, g: cfg.Graph*, live: Liveness*, renamed: bool[], block_at: u32[]) -> list.List[Pending]!:
let n = f.temps.count + 1
let nb = g.count()
var phis = try list.List[Pending].create(32)
errdefer phis.destroy()
var placed = try new u32[nb + 1] ---
defer free(placed)
var in_work = try new u32[nb + 1] ---
defer free(in_work)
var work = try new u32[nb + 1] ---
defer free(work)
var b: usize = 0
while b <= nb:
placed[b] = none_index
in_work[b] = none_index
b += 1
# the blocks defining each renamed temporary, gathered in one pass
var def_start = try new u32[n + 1] ---
defer free(def_start)
var def_fill = try new u32[n + 1] ---
defer free(def_fill)
var t: usize = 0
while t <= n:
def_start[t] = 0
def_fill[t] = 0
t += 1
var i: usize = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
if x.dst != 0 and renamed[(usize)x.dst]:
def_start[(usize)x.dst + 1] += 1
i += 1
t = 1
while t <= n:
def_start[t] += def_start[t - 1]
t += 1
var def_blocks = try new u32[(usize)def_start[n] + 1] ---
defer free(def_blocks)
i = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
if x.dst != 0 and renamed[(usize)x.dst]:
def_blocks[(usize)(def_start[(usize)x.dst] + def_fill[(usize)x.dst])] = block_at[i]
def_fill[(usize)x.dst] += 1
i += 1
t = 1
while t < n:
if not renamed[t]:
t += 1
continue
var count: usize = 0
var d = def_start[t]
while d < def_start[t + 1]:
let db = def_blocks[(usize)d]
d += 1
if db != cfg.none_block and in_work[(usize)db] != u32(t):
in_work[(usize)db] = u32(t)
work[count] = db
count += 1
while count > 0:
count -= 1
let db = work[count]
let block = g.blocks.get((usize)db)
var k: usize = 0
while k < block.frontier.count:
let fb = block.frontier.get(k)
if placed[(usize)fb] != u32(t) and live.live_in_at(fb, u32(t)):
placed[(usize)fb] = u32(t)
try phis.push(Pending(block = fb, temp = u32(t), cls = f.temp_class(u32(t))))
if in_work[(usize)fb] != u32(t):
in_work[(usize)fb] = u32(t)
work[count] = fb
count += 1
k += 1
t += 1
return phis
## Rebuild `f`'s instructions with the phis at their blocks' heads, each with one argument
## per predecessor; for each instruction, the temporary of the phi it is (0 for the rest).
func insert_phis(f: ir.Function*, g: cfg.Graph*, phis: list.List[Pending]*) -> list.List[u32]!:
let nb = g.count()
# the phis grouped by block, then the rebuild with them at their blocks' heads, each
# with one argument per predecessor
var phi_start = try new u32[nb + 2] ---
defer free(phi_start)
var b: usize = 0
while b < nb + 2:
phi_start[b] = 0
b += 1
var k: usize = 0
while k < phis.count:
phi_start[(usize)phis.get(k).block + 1] += 1
k += 1
b = 0
while b < nb:
phi_start[b + 1] += phi_start[b]
b += 1
var by_block = try new u32[phis.count + 1] ---
defer free(by_block)
var fill = try new u32[nb + 1] ---
defer free(fill)
b = 0
while b <= nb:
fill[b] = 0
b += 1
k = 0
while k < phis.count:
let pb = (usize)phis.get(k).block
by_block[(usize)(phi_start[pb] + fill[pb])] = u32(k)
fill[pb] += 1
k += 1
var out = try list.List[ir.Instr].create(f.instrs.count + phis.count)
errdefer out.destroy()
var origin = try list.List[u32].create(f.instrs.count + phis.count)
errdefer origin.destroy()
var i: usize = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
try out.push(x)
try origin.push(0)
if x.op == ir.Op.label:
let here = g.block_of(x.extra)
if here == cfg.none_block:
i += 1
continue
let block = g.blocks.get((usize)here)
var p = phi_start[(usize)here]
while p < phi_start[(usize)here + 1]:
let ph = phis.get((usize)by_block[(usize)p])
let start = u32(f.phi_args.count)
var q: usize = 0
while q < block.preds.count:
try f.phi_args.push(ir.PhiArg(value = ir.const_ref(0), pred = g.blocks.get((usize)block.preds.get(q)).label))
q += 1
try out.push(ir.Instr(op = ir.Op.phi, cls = ph.cls, dst = ph.temp, a = ir.none_ref(), b = ir.none_ref(), extra = start, extra2 = u32(block.preds.count), line = 0, file = 0, scope = 0, site = 0))
try origin.push(ph.temp)
p += 1
# `--release --debug`: a named local whose temporary a phi joins lives in the
# phi's result from here; after every phi, so the phis stay at the head
if f.symbols:
p = phi_start[(usize)here]
while p < phi_start[(usize)here + 1]:
let ph = phis.get((usize)by_block[(usize)p])
try describe_phi(f, ph.temp, &out, &origin)
p += 1
i += 1
f.instrs.destroy()
f.instrs = out
return origin
## A phi to place: at which block, for which temporary.
struct Pending:
var block: u32
var temp: u32
var cls: ir.Class
## A renaming to undo when leaving a dominator tree node.
struct Undo:
var temp: u32
var previous: u32
## The block of every instruction, a label counting as its block's.
func blocks_of_instrs(f: ir.Function*, g: cfg.Graph*) -> u32[]!:
var block_at = try new u32[f.instrs.count + 1] ---
var i: usize = 0
while i < block_at.length:
block_at[i] = cfg.none_block
i += 1
var b: usize = 0
while b < g.blocks.count:
let block = g.blocks.get(b)
var k = block.start
if block.label != 0 and k > 0:
block_at[(usize)k - 1] = u32(b)
while k < block.end:
block_at[(usize)k] = u32(b)
k += 1
b += 1
return block_at
## The current name of temporary `t`, or zero when no definition reaches here.
func name_of(current: u32[], renamed: bool[], r: ir.Ref) -> ir.Ref:
if r.kind != ir.RefKind.temp or not renamed[(usize)r.index]:
return r
let now = current[(usize)r.index]
if now == 0:
return ir.const_ref(0)
return ir.temp_ref(now)
## A `dbg` for each named local that `t` (a temporary about to be renamed) holds at its
## `dbg`s; `rename` then reads the phi's fresh name into it.
func describe_phi(f: ir.Function*, t: u32, out: list.List[ir.Instr]*, origin: list.List[u32]*) -> !:
var seen: u32[64]
var count: usize = 0
var i: usize = 0
while i < out.count:
let x = out.get(i)
if x.op == ir.Op.dbg and x.a.kind == ir.RefKind.temp and x.a.index == t:
var known = false
var k: usize = 0
while k < count:
if seen[k] == x.extra:
known = true
k += 1
if not known and count < 64:
seen[count] = x.extra
count += 1
try out.push(ir.Instr(op = ir.Op.dbg, cls = x.cls, dst = 0, a = ir.temp_ref(t), b = ir.none_ref(), extra = x.extra, extra2 = 0, line = 0, file = 0, scope = 0, site = 0))
try origin.push(0)
i += 1
## One block of the renaming walk: the block, how many of its dominator-tree children
## were visited, and the undo log's length before the block's names were pushed.
struct RenameVisit:
var block: u32
var child: usize
var mark: usize
## Rename the temporaries of block `b` and those it dominates, each block seeing the names
## its dominators left, then taking its own back. An explicit stack, not recursion, as in
## `gvn.number`: a long function is a long chain of blocks, and a frame per block
## overflowed the compiler's stack.
func rename(f: ir.Function*, g: cfg.Graph*, b: u32, renamed: bool[], current: u32[], log: list.List[Undo]*, origin: list.List[u32]*) -> !:
var stack = try list.List[RenameVisit].create(64)
defer stack.destroy()
let root_mark = log.count
try rename_block(f, g, b, renamed, current, log, origin)
try stack.push(RenameVisit(block = b, child = 0, mark = root_mark))
while stack.count > 0:
var top = stack.get(stack.count - 1)
let block = g.blocks.get((usize)top.block)
if top.child < block.children.count:
let child = block.children.get(top.child)
top.child += 1
stack.set(stack.count - 1, top)
let mark = log.count
try rename_block(f, g, child, renamed, current, log, origin)
try stack.push(RenameVisit(block = child, child = 0, mark = mark))
else:
while log.count > top.mark:
let undo = log.get(log.count - 1)
log.count -= 1
current[(usize)undo.temp] = undo.previous
stack.count -= 1
## Rename one block's temporaries under the current names, pushing each new name on the
## undo log, and hand its names to its successors' phis.
func rename_block(f: ir.Function*, g: cfg.Graph*, b: u32, renamed: bool[], current: u32[], log: list.List[Undo]*, origin: list.List[u32]*) -> !:
let block = g.blocks.get((usize)b)
var i = block.start
while i < block.end:
var x = f.instrs.get((usize)i)
if x.op != ir.Op.phi:
x.a = name_of(current, renamed, x.a)
x.b = name_of(current, renamed, x.b)
let (args_start, args_count) = ir.argument_range(f, x)
var a: u32 = 0
while a < args_count:
var arg = f.args.get((usize)(args_start + a))
arg.value = name_of(current, renamed, arg.value)
f.args.set((usize)(args_start + a), arg)
a += 1
if x.dst != 0 and renamed[(usize)x.dst]:
let old = x.dst
let fresh = try f.temp(f.temp_class(old))
try log.push(Undo(temp = old, previous = current[(usize)old]))
current[(usize)old] = fresh
x.dst = fresh
f.instrs.set((usize)i, x)
i += 1
# the successors' phis take this block's names
for s in block.succs.span():
try fill_phis(f, g, s, block.label, current, renamed, origin)
func fill_phis(f: ir.Function*, g: cfg.Graph*, s: u32, from_label: u32, current: u32[], renamed: bool[], origin: list.List[u32]*) -> !:
if s == cfg.none_block:
return
let block = g.blocks.get((usize)s)
var i = block.start
while i < block.end:
let x = f.instrs.get((usize)i)
if x.op != ir.Op.phi:
break
let t = origin.get((usize)i)
if t != 0 and renamed[(usize)t]:
var a: u32 = 0
while a < x.extra2:
var arg = f.phi_args.get((usize)(x.extra + a))
if arg.pred == from_label:
arg.value = name_of(current, renamed, ir.temp_ref(t))
f.phi_args.set((usize)(x.extra + a), arg)
a += 1
i += 1