dymokomi/luce-base
Source of release 0.46.0
0.46.0 / src / back / opt / load.lucb
#==============================================================================================
#
# load - Loads answered by the stores and loads before them
#
# DESCRIPTION:
# A load reads what the last store to its address wrote, or what the last load from
# it read, when nothing in between could have written there. This pass finds that
# value for each load and makes the load a copy of it, following QBE's load.c: an
# address is classified (`Alias`) as an offset from a frame slot, from a symbol, from
# a constant, or from an unknown pointer, so that two accesses either must overlap,
# may, or cannot; the search runs backwards through the load's block and, at its
# head, into the predecessors, a phi joining what several paths supply, so a value
# stored before a loop is read from a temporary inside it. Where the search meets a
# store that may alias, a call that may write (a slot whose address escaped, or any
# other memory), an atomic, or a fence, the load stays. Only a whole match of one
# class is taken: a value of another width or class stays a load too.
#
# A store whose bytes a later store writes again on every path from it, before
# anything could read them, goes (`dead_stores`): `if (rng & 1) != 0: chip.rng ^= k`
# followed by `chip.rng >>= 1` leaves the arm only a value to choose, which `ifconvert`
# then chooses without a branch. The search goes forward from the store through
# blocks that have one way on, past stores and loads that cannot touch its bytes and
# work that cannot trap; anything else keeps the store.
#
#==============================================================================================
import support.list
import back.ir.cfg
import back.ir.ir
## How an address is known: what it is an offset from.
pub enum Kind as u8:
unknown = 0
slot = 1
symbol = 2
constant = 3
## The alias class of an address: what it is an offset from, and by how much.
pub struct Alias:
## What the address is an offset from.
pub var kind: Kind
## The slot index, or the temporary an unknown address is based on.
pub var base: u32
## The symbol name, when the address is a symbol offset.
pub var name: str
## The byte offset from the base.
pub var offset: i64
## Two addresses that cannot overlap.
pub let no_alias: u8 = 0
## Two addresses that might overlap.
pub let may_alias: u8 = 1
## Two addresses that refer to the same location.
pub let must_alias: u8 = 2
## The alias classes of every temporary of `f` (single-assignment form), and which slots'
## addresses escape: are used as anything but the address of a load or a store.
pub struct Aliases:
## The alias class of every temporary, indexed by temporary.
pub var of: Alias[]
## Whether each slot's address escapes, indexed by slot.
pub var escapes: bool[]
## Classify every temporary of `f`, and find which slots' addresses escape.
pub static func over(f: ir.Function*, g: cfg.Graph*) -> Aliases!:
let n = f.temps.count + 1
var a = Aliases(of = try new Alias[n] ---, escapes = try new bool[f.slots.count + 1] ---)
var t: usize = 0
while t < n:
a.of[t] = Alias(kind = Kind.unknown, base = u32(t), name = "", offset = 0)
t += 1
var s: usize = 0
while s < a.escapes.length:
a.escapes[s] = false
s += 1
# in reverse post-order, a definition comes before its uses
var o: usize = 0
while o < g.order.count:
let block = g.blocks.get((usize)g.order.get(o))
var i = block.start
while i < block.end:
let x = f.instrs.get((usize)i)
if x.dst != 0:
a.of[(usize)x.dst] = a.classify(x)
i += 1
o += 1
# escapes
var i: usize = 0
while i < f.instrs.count:
let x = f.instrs.get(i)
if x.op == ir.Op.addr or x.op == ir.Op.copy or x.op == ir.Op.phi:
i += 1
continue
if x.op == ir.Op.add and (x.a.kind == ir.RefKind.constant or x.b.kind == ir.RefKind.constant):
i += 1
continue
if is_load(x.op):
i += 1
continue
if is_store(x.op):
a.escape(x.a)
i += 1
continue
if x.op == ir.Op.blit or x.op == ir.Op.zero or x.op == ir.Op.fill:
i += 1
continue
a.escape(x.a)
a.escape(x.b)
i += 1
i = 0
while i < f.args.count:
a.escape(f.args.get(i).value)
i += 1
i = 0
while i < f.phi_args.count:
a.escape(f.phi_args.get(i).value)
i += 1
return a
func classify(x: ir.Instr) -> Alias:
if x.op == ir.Op.addr:
if x.a.kind == ir.RefKind.slot:
return Alias(kind = Kind.slot, base = x.a.index, name = "", offset = 0)
if x.a.kind == ir.RefKind.global or x.a.kind == ir.RefKind.function:
return Alias(kind = Kind.symbol, base = 0, name = x.a.name, offset = x.a.value)
return Alias(kind = Kind.unknown, base = x.dst, name = "", offset = 0)
if x.op == ir.Op.copy:
return self.of_ref(x.a, x.dst)
if x.op == ir.Op.add:
if x.b.kind == ir.RefKind.constant:
var based = self.of_ref(x.a, x.dst)
based.offset = based.offset +% x.b.value
return based
if x.a.kind == ir.RefKind.constant:
var based = self.of_ref(x.b, x.dst)
based.offset = based.offset +% x.a.value
return based
return Alias(kind = Kind.unknown, base = x.dst, name = "", offset = 0)
## The class of an operand: a temporary's, a constant's, or a symbol's; `self_temp`
## names the temporary being classified, the base of an unknown.
func of_ref(r: ir.Ref, self_temp: u32) -> Alias:
if r.kind == ir.RefKind.temp:
return self.of[(usize)r.index]
if r.kind == ir.RefKind.constant:
return Alias(kind = Kind.constant, base = 0, name = "", offset = r.value)
if r.kind == ir.RefKind.slot:
return Alias(kind = Kind.slot, base = r.index, name = "", offset = 0)
if r.kind == ir.RefKind.global or r.kind == ir.RefKind.function:
return Alias(kind = Kind.symbol, base = 0, name = r.name, offset = r.value)
return Alias(kind = Kind.unknown, base = self_temp, name = "", offset = 0)
func escape(r: ir.Ref):
let a = self.of_ref(r, 0)
if a.kind == Kind.slot and (usize)a.base < self.escapes.length:
self.escapes[(usize)a.base] = true
## Whether an access of `sp` bytes at `ap` and one of `sq` bytes at `q` overlap.
pub func relation(ap: Alias, sp: i64, q: ir.Ref, sq: i64) -> u8:
let aq = self.of_ref(q, 0)
let overlap = ap.offset < aq.offset +% sq and aq.offset < ap.offset +% sp
if ap.kind == Kind.slot and aq.kind == Kind.slot:
if ap.base == aq.base:
return must_alias if overlap else no_alias
return no_alias
if ap.kind == Kind.symbol and aq.kind == Kind.symbol:
if ap.name != aq.name:
return may_alias
return must_alias if overlap else no_alias
if (ap.kind == Kind.constant and aq.kind == Kind.constant) or (ap.kind == aq.kind and ap.base == aq.base):
return must_alias if overlap else no_alias
# an unknown pointer may reach anything but a slot whose address never escaped
if ap.kind == Kind.unknown and not self.is_local(aq):
return may_alias
if aq.kind == Kind.unknown and not self.is_local(ap):
return may_alias
return no_alias
func is_local(a: Alias) -> bool:
return a.kind == Kind.slot and (usize)a.base < self.escapes.length and not self.escapes[(usize)a.base]
## Whether an access through `a` can be reached by memory outside this analysis.
pub func escaped(a: Alias) -> bool:
return not self.is_local(a)
## The location `bytes` past `r`'s.
pub func at(r: ir.Ref, bytes: i64) -> Alias:
var a = self.of_ref(r, 0)
a.offset = a.offset +% bytes
return a
## Free the alias tables.
pub func release():
free(self.of)
free(self.escapes)
## 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) -> i64:
match op:
.loadsb, .loadub: return 1
.loadsh, .loaduh, .loadhf: return 2
.loadsw, .loaduw, .loads: return 4
_: return 8
func store_width(op: ir.Op) -> i64:
match op:
.storeb: return 1
.storeh, .storehf: return 2
.storew, .stores: return 4
_: return 8
func load_takes(op: ir.Op, cls: ir.Class, k: ir.Class) -> bool:
match op:
.loadl: return k == ir.Class.l
.loads: return k == ir.Class.s
.loadd: return k == ir.Class.d
.loadhf: return k == ir.Class.h
.loadsw, .loaduw: return k == ir.Class.w and cls == ir.Class.w
_: return false
# mark: The pass ===============================================================================
## A phi the search wants at a block's head: for which load's location, with what.
struct Join:
var block: u32
var address: Alias
var width: i64
var cls: ir.Class
var temp: u32
var args_start: u32
var args_count: u32
## Whether the search that made it succeeded; a failed one is not placed.
var placed: bool
struct Search:
var f: ir.Function*
var g: cfg.Graph*
var aliases: Aliases*
var joins: list.List[Join]
## The arguments of the joins, by pred label, filled as the search returns.
var join_args: list.List[ir.PhiArg]
## How many instructions one load's search may still visit: a bound keeps the pass
## linear on a long block of loads.
var budget: u32
func find(address: ir.Ref, width: i64, op: ir.Op, cls: ir.Class, b: u32, at: u32) -> ir.Ref?!:
return try find_value(&self, self.aliases.at(address, 0), width, op, cls, b, at)
## The joins that succeeded become phis at their blocks' heads.
func place() -> !:
var out = try list.List[ir.Instr].create(self.f.instrs.count + self.joins.count)
var b: usize = 0
while b < self.g.blocks.count:
let block = self.g.blocks.get(b)
if block.rpo == cfg.none_block and block.end > block.start:
# an unreachable block keeps its instructions as they are
var i = block.start
if block.label != 0 and i > 0:
try out.push(self.f.instrs.get((usize)i - 1))
while i < block.end:
try out.push(self.f.instrs.get((usize)i))
i += 1
b += 1
continue
var i = block.start
if block.label != 0 and i > 0:
try out.push(self.f.instrs.get((usize)i - 1))
# the block's own phis first, then the joins
while i < block.end and self.f.instrs.get((usize)i).op == ir.Op.phi:
try out.push(self.f.instrs.get((usize)i))
i += 1
var j: usize = 0
while j < self.joins.count:
let join = self.joins.get(j)
if join.placed and join.block == u32(b):
let start = u32(self.f.phi_args.count)
var q: u32 = 0
while q < join.args_count:
try self.f.phi_args.push(self.join_args.get((usize)(join.args_start + q)))
q += 1
try out.push(ir.Instr(op = ir.Op.phi, cls = join.cls, dst = join.temp, a = ir.none_ref(), b = ir.none_ref(), extra = start, extra2 = join.args_count, line = 0, file = 0, scope = 0, site = 0))
j += 1
while i < block.end:
try out.push(self.f.instrs.get((usize)i))
i += 1
b += 1
self.f.instrs.destroy()
self.f.instrs = out
## Resolve the loads of `f` (single-assignment form, graph `g`); answers whether any load
## became a copy. New phis join the block heads, so the graph must be built again.
pub func run(f: ir.Function*, g: cfg.Graph*) -> bool!:
var aliases = try Aliases.over(f, g)
defer aliases.release()
var search = Search(f = f, g = g, aliases = &aliases, joins = try list.List[Join].create(16), join_args = try list.List[ir.PhiArg].create(32), budget = 0)
defer search.joins.destroy()
defer search.join_args.destroy()
var block_at = try new u32[f.instrs.count + 1] ---
defer free(block_at)
var b: usize = 0
while b < g.blocks.count:
let block = g.blocks.get(b)
var k = block.start
while k < block.end:
block_at[(usize)k] = u32(b)
k += 1
b += 1
# the answers are recorded and applied after: a load answered stays a load while the
# later loads search, so that they may find it
var answers = try new ir.Ref[f.instrs.count + 1] ---
defer free(answers)
var changed = false
var i: usize = 0
while i < f.instrs.count:
answers[i] = ir.none_ref()
let x = f.instrs.get(i)
if is_load(x.op) and x.dst != 0 and block_at[i] != cfg.none_block and g.blocks.get((usize)block_at[i]).rpo != cfg.none_block:
let before = search.joins.count
let before_args = search.join_args.count
search.budget = 4096
if let value = try search.find(x.a, load_width(x.op), x.op, x.cls, block_at[i], u32(i)):
answers[i] = value
changed = true
else:
search.joins.count = before
search.join_args.count = before_args
i += 1
i = 0
while i < f.instrs.count:
if answers[i].kind != ir.RefKind.none_:
var y = f.instrs.get(i)
y.op = ir.Op.copy
y.a = answers[i]
y.b = ir.none_ref()
f.instrs.set(i, y)
i += 1
if search.joins.count > 0:
try search.place()
return changed
## A load of `width` bytes at `start_address`, of class `cls`, in block `start_block`
## before instruction `start_at` (or at the block's end when that is the end): the value
## there, or none.
func find_value(s: Search*, start_address: Alias, width: i64, op: ir.Op, cls: ir.Class, start_block: u32, start_at: u32) -> ir.Ref?!:
# a block with one predecessor, and a copy read back to its source, carry the search
# on in this loop rather than in a call each: chains of them are long
var address = start_address
var b = start_block
var at = start_at
outer: while true:
let block = s.g.blocks.get((usize)b)
var i = at
while i > block.start:
i -= 1
if s.budget == 0:
return none
s.budget -= 1
let x = s.f.instrs.get((usize)i)
if x.op == ir.Op.phi:
continue
# the address's own base is defined here: nothing before it holds the value
if x.dst != 0 and address.kind == Kind.unknown and address.base == x.dst:
return none
if x.op == ir.Op.call:
# a call writes any memory whose address escaped, and its own result's slot
if s.aliases.escaped(address):
return none
let info = s.f.calls.get((usize)x.extra)
if info.has_result and info.result_size > 0 and not info.result_words and s.aliases.relation(address, width, ir.slot_ref(info.result_slot), (i64)info.result_size) != no_alias:
return none
continue
if is_store(x.op):
let rel = s.aliases.relation(address, width, x.b, store_width(x.op))
if rel == must_alias:
if store_width(x.op) == width and load_takes(op, cls, ir.store_class(x.op)) and s.aliases.at(x.b, 0).offset == address.offset:
return x.a
return none
if rel == may_alias:
return none
continue
if is_load(x.op):
let rel = s.aliases.relation(address, width, x.a, load_width(x.op))
if rel == must_alias and load_width(x.op) == width and x.op == op and x.cls == cls and s.aliases.at(x.a, 0).offset == address.offset:
return ir.temp_ref(x.dst)
continue
if x.op == ir.Op.blit:
# a copy of the bytes: read them where they came from, when they are all there
let rel_to = s.aliases.relation(address, width, x.a, (i64)x.extra)
if rel_to == no_alias:
continue
let target = s.aliases.at(x.a, 0)
if rel_to == must_alias and address.offset >= target.offset and address.offset + width <= target.offset +% (i64)x.extra:
address = s.aliases.at(x.b, address.offset - target.offset)
at = i
continue outer
return none
if x.op == ir.Op.zero:
let rel = s.aliases.relation(address, width, x.a, (i64)x.extra)
if rel == no_alias:
continue
let target = s.aliases.at(x.a, 0)
if rel == must_alias and address.offset >= target.offset and address.offset + width <= target.offset +% (i64)x.extra:
return ir.const_ref(0)
return none
if x.op == ir.Op.fill:
if s.aliases.relation(address, width, x.a, (i64)x.extra) != no_alias:
return none
continue
if x.op == ir.Op.storev:
if s.aliases.relation(address, width, x.b, (i64)ir.vector_bytes(x.extra)) != no_alias:
return none
continue
if (u8)x.op >= (u8)ir.Op.atomic_load and (u8)x.op <= (u8)ir.Op.fence:
return none
if x.op == ir.Op.asm_ or x.op == ir.Op.set_reg or x.op == ir.Op.get_reg:
return none
# the block's head: a join already made for this location, or the predecessors
var j: usize = 0
while j < s.joins.count:
let join = s.joins.get(j)
if join.block == b and join.width == width and join.cls == cls and same_alias(join.address, address):
return ir.temp_ref(join.temp)
j += 1
if block.preds.count == 0:
return none
if block.preds.count == 1:
b = block.preds.get(0)
at = s.g.blocks.get((usize)b).end
continue
return try join_value(s, address, width, op, cls, b)
## The value at `address` where block `b`'s several predecessors meet: a phi of the value
## each one holds, or none when one of them holds none.
func join_value(s: Search*, address: Alias, width: i64, op: ir.Op, cls: ir.Class, b: u32) -> ir.Ref?!:
let block = s.g.blocks.get((usize)b)
let temp = try s.f.temp(cls)
let start = u32(s.join_args.count)
var q: usize = 0
while q < block.preds.count:
try s.join_args.push(ir.PhiArg(value = ir.const_ref(0), pred = s.g.blocks.get((usize)block.preds.get(q)).label))
q += 1
try s.joins.push(Join(block = b, address = address, width = width, cls = cls, temp = temp, args_start = start, args_count = u32(block.preds.count), placed = true))
let index = s.joins.count - 1
q = 0
while q < block.preds.count:
let pred = block.preds.get(q)
let found = try find_value(s, address, width, op, cls, pred, s.g.blocks.get((usize)pred).end)
if let value = found:
var arg = s.join_args.get((usize)start + q)
arg.value = value
s.join_args.set((usize)start + q, arg)
else:
var failed = s.joins.get(index)
failed.placed = false
s.joins.set(index, failed)
return none
q += 1
return ir.temp_ref(temp)
func same_alias(a: Alias, b: Alias) -> bool:
return a.kind == b.kind and a.base == b.base and a.offset == b.offset and a.name == b.name
# mark: Dead stores ============================================================================
## The most instructions the search from one store visits.
let dead_store_reach: u32 = 64
## Remove the stores of `f` (single-assignment form, graph `g`) that a later store
## overwrites before anything reads them; whether any went. The graph is then stale.
pub func dead_stores(f: ir.Function*, g: cfg.Graph*) -> bool!:
var aliases = try Aliases.over(f, g)
defer aliases.release()
var dead = try new bool[f.instrs.count + 1] ---
defer free(dead)
var any = false
for b in 0..<g.blocks.count:
let block = g.blocks.get(b)
if block.rpo == cfg.none_block:
continue
for i in block.start..<block.end:
dead[(usize)i] = false
let x = f.instrs.get((usize)i)
if is_store(x.op) and overwritten(f, g, &aliases, u32(b), i):
dead[(usize)i] = true
any = true
if not any:
return false
var out = try list.List[ir.Instr].create(f.instrs.count)
for b in 0..<g.blocks.count:
let block = g.blocks.get(b)
if block.label != 0 and block.start > 0:
try out.push(f.instrs.get((usize)block.start - 1))
for i in block.start..<block.end:
if block.rpo == cfg.none_block or not dead[(usize)i]:
try out.push(f.instrs.get((usize)i))
f.instrs.destroy()
f.instrs = out
return true
## Whether the store at `at`, in block `b`, is written over by a later store on the one
## path from it before anything may read its bytes, trap, or leave.
func overwritten(f: ir.Function*, g: cfg.Graph*, aliases: Aliases*, start_block: u32, at: u32) -> bool:
let store = f.instrs.get((usize)at)
let width = store_width(store.op)
let address = aliases.at(store.b, 0)
var b = start_block
var i = at + 1
var budget = dead_store_reach
while budget > 0:
let block = g.blocks.get((usize)b)
while i < block.end:
if budget == 0:
return false
budget -= 1
let x = f.instrs.get((usize)i)
i += 1
# the address's own base defined again: the search went round a loop
if x.dst != 0 and address.kind == Kind.unknown and address.base == x.dst:
return false
if is_store(x.op):
let rel = aliases.relation(address, width, x.b, store_width(x.op))
if rel == must_alias:
let over = aliases.at(x.b, 0)
return over.offset <= address.offset and address.offset + width <= over.offset + store_width(x.op)
continue
if is_load(x.op):
if aliases.relation(address, width, x.a, load_width(x.op)) != no_alias:
return false
continue
if x.op == ir.Op.jmp:
break
if not harmless(x.op):
return false
# on to the one block this one goes to, by its jump or by falling in
if block.succs.count != 1:
return false
b = block.succs.get(0)
i = g.blocks.get((usize)b).start
return false
## Whether `op` only computes a value: it reads no memory, cannot trap, and does not leave.
func harmless(op: ir.Op) -> bool:
match op:
.copy, .addr, .add, .sub, .mul, .and_, .or_, .xor, .shl, .lshr, .ashr, .neg: return true
.ceq, .cne, .cslt, .csle, .csgt, .csge, .cult, .cule, .cugt, .cuge: return true
.extsb, .extub, .extsh, .extuh, .extsw, .extuw, .exts, .truncd, .cast: return true
.select, .phi, .label, .dbg: return true
_: return false