dymokomi/luce-base
Source of release 0.44.0
0.44.0 / src / back / ir / ir.lucb
#==============================================================================================
#
# ir - The intermediate representation of the native backend
#
# DESCRIPTION:
# A small machine-neutral form between the checked tree and a target (base.md §19.1),
# in the spirit of QBE: instructions over typed temporaries in four classes, `w` (32-bit
# integer), `l` (64-bit integer or address), `s`, and `d`; stack slots for everything
# that has an address; calls that carry enough about each argument for a target to
# classify it. Aggregates never live in temporaries; they live in memory and are
# moved by `blit`.
#
# Temporaries are assigned once and used within the block that assigned them. A value
# that must cross a block, the result of a conditional or a `match` expression, goes
# through a slot. That keeps register allocation a per-block affair, with no dataflow
# across the control flow graph.
#
#==============================================================================================
import memory
import support.hashed
import support.list
# mark: Classes and references =================================================================
## The register class of a temporary.
pub enum Class as u8:
w = 1
l = 2
s = 3
d = 4
## a half-precision float, in the low half of a `v` register
h = 5
## a vector of eight or sixteen bytes (§5.12), in a vector register; its lane shape is
## on the instruction (`lanes`)
v = 6
## The ten comparisons: their result is a word whatever they compare.
pub func is_comparison(op: Op) -> bool:
return (u8)op >= (u8)Op.ceq and (u8)op <= (u8)Op.cuge
## The comparison true exactly when `op` is false, on integers (and on floats for the two
## equalities): what a fused branch tests when its fall-through is the taken side, and
## what folds `x == 0` of a comparison.
pub func negated(op: Op) -> Op:
match op:
.ceq: return Op.cne
.cne: return Op.ceq
.cslt: return Op.csge
.csle: return Op.csgt
.csgt: return Op.csle
.csge: return Op.cslt
.cult: return Op.cuge
.cule: return Op.cugt
.cugt: return Op.cule
_: return Op.cult
## Whether `cls` is a float or half-precision register class.
pub func is_float_class(cls: Class) -> bool:
return cls == Class.s or cls == Class.d or cls == Class.h
## The lane shape of a vector instruction, in its `extra`: the lanes' width in bits, how
## many, and whether they are floats and signed. A vector is `lane_bits * lane_count / 8`
## bytes: eight or sixteen.
pub func lanes(bits: u32, count: u32, is_float: bool, signed: bool) -> u32:
return bits | (count << 8) | ((1 if is_float else 0) << 16) | ((1 if signed else 0) << 17)
## The lanes' width in bits, from a vector shape.
pub func lane_bits(shape: u32) -> u32:
return shape & 0xFF
## How many lanes a vector shape has.
pub func lane_count(shape: u32) -> u32:
return (shape >> 8) & 0xFF
## Whether a vector shape's lanes are floats.
pub func lanes_float(shape: u32) -> bool:
return (shape & (1 << 16)) != 0
## Whether a vector shape's lanes are signed.
pub func lanes_signed(shape: u32) -> bool:
return (shape & (1 << 17)) != 0
## The total byte width of a vector shape, eight or sixteen.
pub func vector_bytes(shape: u32) -> u32:
return lane_bits(shape) * lane_count(shape) // 8
## The bytes of one level of a function's dynamic area (`Op.reserve`): a format buffer's
## 1024 characters and its 24-byte state, to sixteen.
pub let level_bytes: u32 = 1056
## Whether `op` ends a basic block: control leaves through it, or never returns.
pub func is_terminator(op: Op) -> bool:
return op == Op.jmp or op == Op.jnz or op == Op.switch_ or op == Op.ret or op == Op.trap_
## Whether `op` computes on vectors (§5.12), lane shape in `extra`.
pub func is_vector_op(op: Op) -> bool:
return ((u8)op >= (u8)Op.loadv and (u8)op <= (u8)Op.vsplat) or ((u8)op >= (u8)Op.vinsert and (u8)op <= (u8)Op.vtruncd)
## What an operand refers to.
pub enum RefKind as u8:
none_ = 0
temp = 1
constant = 2
slot = 3
global = 4
function = 5
text = 6
## An operand: a temporary, a constant, the address of a slot, global, function, or text.
pub struct Ref:
## What the operand refers to.
pub var kind: RefKind
## The temporary, slot, or text index; unused for the rest.
pub var index: u32
## A constant's value, or 1 marking an imported global.
pub var value: i64
## The symbol of a global or function; the bytes of a text literal.
pub var name: str
## No operand.
pub func none_ref() -> Ref:
return Ref(kind = RefKind.none_, index = 0, value = 0, name = "")
## The temporary numbered `index`.
pub func temp_ref(index: u32) -> Ref:
return Ref(kind = RefKind.temp, index = index, value = 0, name = "")
## The integer constant `value`.
pub func const_ref(value: i64) -> Ref:
return Ref(kind = RefKind.constant, index = 0, value = value, name = "")
## The address of slot `index`.
pub func slot_ref(index: u32) -> Ref:
return Ref(kind = RefKind.slot, index = index, value = 0, name = "")
## The address of the global named `name`.
pub func global_ref(name: str) -> Ref:
return Ref(kind = RefKind.global, index = 0, value = 0, name = name)
## A data symbol another image defines, `__stderrp` or an `extern var`: reached through the
## GOT, since a direct page address to a dylib's data does not link.
pub func import_ref(name: str) -> Ref:
return Ref(kind = RefKind.global, index = 0, value = 1, name = name)
## The address of the function named `name`.
pub func function_ref(name: str) -> Ref:
return Ref(kind = RefKind.function, index = 0, value = 0, name = name)
## The address of text literal `index`.
pub func text_ref(index: u32) -> Ref:
return Ref(kind = RefKind.text, index = index, value = 0, name = "")
# mark: Instructions ===========================================================================
pub enum Op as u8:
## `dst = a`
copy = 1
## integer and float arithmetic on the class of `dst`
add = 10
sub = 11
mul = 12
sdiv = 13
udiv = 14
srem = 15
urem = 16
and_ = 17
or_ = 18
xor = 19
## shifts read the count's low five (`w`) or six (`l`) bits, of either integer class,
## as every target's shift instruction does; the lowering traps on a count past them
shl = 20
lshr = 21
ashr = 22
neg = 23
## the float functions of the C library a target computes in one instruction
## (`isa.float_function`), on the single or double `cls`, bit for bit as the library:
## the square root, rounding toward negative infinity, toward positive infinity, toward
## zero, to nearest with halves away from zero (C's `round`), and the magnitude
fsqrt = 24
ffloor = 25
fceil = 26
ftrunc = 27
fround = 28
fabs = 29
## comparisons: `dst` is `w`, 1 or 0; the class on the instruction is the operands'
ceq = 30
cne = 31
cslt = 32
csle = 33
csgt = 34
csge = 35
cult = 36
cule = 37
cugt = 38
cuge = 39
## loads: `a` is an address; the width and extension are in the op
loadsb = 40
loadub = 41
loadsh = 42
loaduh = 43
loadsw = 44
loaduw = 45
loadl = 46
loads = 47
loadd = 48
## `dst = load [a]`, a half float
loadhf = 49
## stores: `a` is the value, `b` the address
storeb = 50
storeh = 51
storew = 52
storel = 53
stores = 54
stored = 55
## `store a -> [b]`, a half float
storehf = 56
## conversions between classes
extsb = 60
extub = 61
extsh = 62
extuh = 63
extsw = 64
extuw = 65
exts = 66
truncd = 67
stosi = 68
stoui = 69
dtosi = 70
dtoui = 71
swtof = 72
uwtof = 73
sltof = 74
ultof = 75
cast = 76
## a half to the single or double `cls`; a single to a half
exth = 77
truncs = 78
## `dst = address of a` (a slot, global, function, or text)
addr = 80
## `blit a <- b, extra bytes`: copy memory
blit = 81
## `zero a, extra bytes`
zero = 82
## `fill a, extra bytes` with the byte constant `b`: the diagnostic profile's pattern
fill = 83
## `call`: `a` is the callee, arguments follow in the function's argument list
call = 90
## `dst = word extra`: word `extra` of the result of the call just before, which comes
## back in registers (`CallInfo.result_words`), a float word (class `s` or `d`) in the
## next float result register and any other in the next integer one; a call's words
## follow it directly, every one of them in order, and the generator moves them all out
## as the call returns.
## `extra2` is 1 for a failure flag, which is 0 or 1.
word = 92
## `dst = phi` at a block's head: the value from each predecessor, in `phi_args` from
## `extra` for `extra2` entries. Only the optimiser's passes see phis: `dessa` turns
## them into copies before a generator does.
phi = 91
## control: `label extra`, `jmp extra`, `jnz a, extra (then), value (else)`, `ret [a]`;
## a `ret` with `extra2` words returns the arguments from index `extra` of the
## function's `args` as the words of a private result (`Function.result_private`)
label = 100
jmp = 101
jnz = 102
ret = 103
## `trap a` where `a` names the reason text
trap_ = 104
## `check a < b` else trap "index out of bounds"; `a <= b` when `extra` is 1, the
## one-past-the-end bound of `&owner[i]` and of a slice's ends, which `b + 1` would wrap
bounds = 105
## `switch a, extra (default), table extra2`: a jump through table `extra2` of the
## function's `jump_tables` to the label of entry `a - low`, computed at the class of the
## instruction; to `extra` when that is not below the table's `count` (unsigned)
switch_ = 106
## `arith` variants that trap on overflow: `dst = a op b` with the op in `extra`
addo = 110
subo = 111
mulo = 112
## `addr_tls`: `dst = address of the thread-local global a`
addr_tls = 113
## `asm a, b`: architecture text `a`, raw lines `b`, no operands
asm_ = 114
## atomics: `extra` is the width in bytes, `extra2` the C memory order;
## `atomic_load dst <- [a]`, `atomic_store a -> [b]`, read-modify-write `dst = old; [b] op= a`,
## `atomic_cas dst = old; expected and desired are args from index b.value`
atomic_load = 120
atomic_store = 121
atomic_add = 122
atomic_sub = 123
atomic_or = 124
atomic_and_not = 125
atomic_xor = 126
atomic_swap = 127
atomic_max = 128
atomic_min = 129
atomic_cas = 130
## `fence a`: a full fence with the C memory order in `a`
fence = 131
## Vectors (§5.12): the lanes compute exactly as the scalar operators would, and a
## checked lane's overflow traps. `loadv`/`storev` move the shape's bytes; `vshl`/`vshr`
## take a scalar count in `b`, already checked against the lane width; `vsplat` takes a
## scalar of the lane's class in `a`.
loadv = 140
storev = 141
vadd = 142
vsub = 143
vmul = 144
vdiv = 145
vand = 146
vor = 147
vxor = 148
vneg = 149
vnot = 150
vaddw = 151
vsubw = 152
vmulw = 153
vaddo = 154
vsubo = 155
vadds = 156
vsubs = 157
vshl = 158
vshr = 159
vsplat = 160
## `--release --debug`: from here, named local `extra` (an index into `locals`) holds
## `a`, a temporary or a constant, until the next `dbg` of it or the end of the
## temporary's life; no code, no use of `a` (`ssa.promote` places them, the DWARF
## emitter reads them)
dbg = 161
## `fma dst = a * b + c`, rounded once (`mul_add`, §7.2): `c` is the argument at index
## `extra2`; `extra` is a vector's lane shape and 0 for a scalar of class `cls`
fma = 162
## `dst = select a, b, c`: `b` when the word `a` is not 0, else `c`, the argument at
## index `extra2`; neither is evaluated for it, both are values already (`ifconvert`)
select = 163
## `reserve extra`: from here the dynamic area below the fixed frame holds `extra`
## levels of `level_bytes` each (0: none), and the stack pointer is below them, so the
## calls made meanwhile leave them be; a statement's format buffers live in its levels.
reserve = 107
## `dst = alloca a`: the stack pointer moves down by `a` bytes, a multiple of sixteen and
## at most 4096, the new bottom is touched, and `dst` is its address: storage in the
## function's frame until it returns (`memory.frame`, §12.7). The bytes the function's
## calls pass on the stack go below it.
alloca = 108
## Lanes the optimiser packs from scalars (`opt/slp`), lane `extra2` of a vector of
## shape `extra`: `vinsert dst = a with lane extra2 set to the scalar b` (`a` none: the
## other lanes are anything), `vextract dst = lane extra2 of a`, at the lane's class, and
## `vsqrt dst = the square root of every lane of a`, as `fsqrt` computes each.
vinsert = 164
vextract = 165
vsqrt = 166
## Two lanes between widths, as `exts` and `truncd` convert each: `vexts dst = the
## singles of a as doubles`, `vtruncd dst = the doubles of a as singles`; `extra` is the
## result's shape.
vexts = 167
vtruncd = 168
## The frame pointer of the running function, for the debugger.
frame = 200
## Inline assembly operands: `set_reg a -> named register b` before an `asm` block,
## `get_reg [a] <- named register b` after it; `cls` is the width.
set_reg = 210
get_reg = 211
## The instructions of a function, as it holds them and as the inliner rebuilds them.
pub type Instrs = list.List[Instr]
## One instruction. `dst` is 0 when there is none. `extra` carries a label, a
## byte count, or a call's argument range.
pub struct Instr:
## The operation.
pub var op: Op
## The class of `dst` and of the operation.
pub var cls: Class
## The result temporary, 0 for none.
pub var dst: u32
## The first operand.
pub var a: Ref
## The second operand.
pub var b: Ref
## A label, a byte count, or a call's argument range.
pub var extra: u32
## A branch's else label, or a second count.
pub var extra2: u32
## The source line and file (an index into the unit's `files`, 1-based, 0 for none)
## the instruction came from, for the line table of an optimised build (`--release
## --debug`); the passes carry them with the instruction.
pub var line: u32
## The file the line refers to, an index into the unit's `files`.
pub var file: u32
## The lexical scope (an index into the function's `debug_scopes`, 0 for the function's
## own) the instruction came from; the passes carry it, and a build with symbols
## describes each scope's locals over the addresses its instructions reach.
pub var scope: u32
## The inlined subroutine (an index into the function's `sites`, 1-based, 0 for the
## function's own body) the instruction came from, the same way.
pub var site: u32
## Whether `instruction`, a `bounds` or checked operation, names its statement's position
## text in `extra2` (the text's index + 1) for the trap it may raise; 0 names none.
pub func positioned(instruction: Instr) -> bool:
let op = instruction.op
return (op == Op.bounds or op == Op.addo or op == Op.subo or op == Op.mulo or op == Op.vaddo or op == Op.vsubo) and instruction.extra2 > 0
## `words` in ascending order: a bottom-up merge sort, n log n, in the heap (the compiler's
## sources keep to what the seed's library has, which has no sort).
func sort_words(words: u64[]) -> !:
let n = words.length
with memory.heap:
var other = try new u64[n] ---
defer free(other)
var source = words
var target = other
var width: usize = 1
while width < n:
var start: usize = 0
while start < n:
let middle = start + width if start + width < n else n
let end = start + 2 * width if start + 2 * width < n else n
var i = start
var j = middle
var k = start
while k < end:
if i < middle and (j >= end or source[i] <= source[j]):
target[k] = source[i]
i += 1
else:
target[k] = source[j]
j += 1
k += 1
start = end
let swap = source
source = target
target = swap
width *= 2
if source.data != words.data:
memory.copy(words, source, n)
## One scalar member of an aggregate, wherever it lies: what a calling convention reads to
## classify the aggregate. A union's members overlap; padding has no leaf.
pub struct Leaf:
## The member's byte offset in the aggregate.
pub var offset: u32
## The member's size in bytes.
pub var size: u8
## The member's register class.
pub var cls: Class
## An aggregate's leaves, as a range of the unit's `leaves`; shape 0 is no shape, the
## aggregate is passed in memory whatever the convention.
pub struct Shape:
## The first leaf's index in the unit's `leaves`.
pub var start: u32
## How many leaves the shape has.
pub var count: u32
## One argument of a call: the operand, its class, and for an aggregate its byte size,
## alignment, and shape (0 size means a scalar). The convention is the target's: the IR
## says what the value is made of, and the generator decides where it goes.
pub struct Arg:
## The argument operand.
pub var value: Ref
## The argument's register class.
pub var cls: Class
## The aggregate's byte size, 0 for a scalar.
pub var size: u32
## The aggregate's alignment.
pub var align: u32
## The argument's type.
pub var type_id: u32
## The aggregate's shape (1-based), 0 for none.
pub var shape: u32
## Scalar storage width before register promotion; zero uses the IR class width.
## Apple arm64 packs fixed stack arguments using this width, even for i8/u16.
pub var scalar_width: u32
## A call's result: a scalar class, or an aggregate written to `slot` of `size` bytes.
pub struct CallInfo:
## The first argument's index in the function's `args`.
pub var args_start: u32
## How many arguments the call passes.
pub var args_count: u32
## How many arguments are fixed, before any variadic tail.
pub var fixed_count: u32
## Whether the call is variadic.
pub var variadic: bool
## The result's register class.
pub var result_cls: Class
## Whether the call returns a value.
pub var has_result: bool
## The result's byte size, 0 for a scalar.
pub var result_size: u32
## The result's alignment.
pub var result_align: u32
## The result's type.
pub var result_type: u32
## The slot an aggregate result is written into.
pub var result_slot: u32
## The result aggregate's shape (1-based), 0 for none.
pub var result_shape: u32
## Whether the result comes back in the program's own convention rather than the C one:
## a fallible result or a tuple of at most four words, each word holding one float in
## the next of the first four float result registers (d0-d3, or xmm0-xmm3) and any other
## in the next of the first four integer ones (x0-x3, or rax, rdx, rcx and r8), never
## through a hidden pointer (`Unit.word_class`). Nothing outside the program calls a
## function whose result is either: neither is C-representable (§17.6's status form
## wraps a fallible export).
pub var result_private: bool = false
## Whether the private result's words are left in their registers for the `word`
## instructions right after the call, which store them to `result_slot`: the call
## itself writes no memory for its result.
pub var result_words: bool = false
## The jump table of a `switch`: its labels are `jump_labels[start ..< start + count]`,
## entry `k` for the value `low + k`.
pub struct Table:
## The value of the first entry.
pub var low: i64
## The first label's index in the function's `jump_labels`.
pub var start: u32
## How many entries the table has.
pub var count: u32
## A jump table needs this many values at least, of which one entry in `table_density`
## percent names one (the rest go to the fallback), and no more than `table_entries`.
let table_cases: usize = 4
let table_density: u64 = 40
let table_entries: u64 = 4095
## How many entries a jump table over the sorted `values` has, from the first to the
## last, when they are enough and dense enough for one; none when a search does better. The
## lowerer's `match` and `opt/switches`' chains of tests decide alike.
pub func dense_range(values: i64[]) -> usize?:
if values.length < table_cases:
return none
# sorted signed or unsigned, the last is above the first either way: the distance
# is the same in 64-bit arithmetic that wraps
let distance = (u64)values[values.length - 1] -% (u64)values[0]
if distance >= table_entries:
return none
let entries = distance + 1
if (u64)values.length * 100 < entries * table_density:
return none
return (usize)entries
## A stack slot: `size` bytes at `align`.
pub struct Slot:
## The slot's size in bytes.
pub var size: u32
## The slot's alignment.
pub var align: u32
## 0 for a slot of the fixed frame; `k` for one in level `k` of the dynamic area below
## it (`Op.reserve`), at `offset` bytes into the level.
pub var level: u32 = 0
## Where in its level a dynamic slot starts.
pub var offset: u32 = 0
## A parameter as the function receives it.
pub struct Param:
## The parameter's register class.
pub var cls: Class
## The parameter's byte size, 0 for a scalar.
pub var size: u32
## The parameter's alignment.
pub var align: u32
## The parameter's type.
pub var type_id: u32
## The slot the parameter is stored into on entry.
pub var slot: u32
## The parameter aggregate's shape (1-based), 0 for none.
pub var shape: u32
## The scalar storage width before promotion; 0 uses the class width.
pub var scalar_width: u32
## Whether the scalar parameter is signed.
pub var scalar_signed: bool
## The class a load produces.
pub func load_class(op: Op) -> Class:
match op:
.loadsb, .loadub, .loadsh, .loaduh, .loaduw: return Class.w
.loadsw, .loadl: return Class.l
.loads: return Class.s
.loadhf: return Class.h
_: return Class.d
## The class a store writes: `w` for the narrow integer stores, as wide as a word.
pub func store_class(op: Op) -> Class:
match op:
.storeb, .storeh, .storew: return Class.w
.stores: return Class.s
.stored: return Class.d
.storehf: return Class.h
_: return Class.l
## The class a float conversion reads: `exth` a half, `exts` and `truncs` a single, `truncd` a double.
pub func float_source_class(op: Op) -> Class:
match op:
.exth: return Class.h
.exts, .truncs: return Class.s
_: return Class.d
## The class whose bits `cast` moves into `cls`: the integer as wide as a float, and back.
pub func cast_partner(cls: Class) -> Class:
match cls:
.h, .s: return Class.w
.d: return Class.l
.w: return Class.s
_: return Class.d
# mark: Functions and the unit ================================================================
## One incoming value of a phi: what the block whose label is `pred` supplies.
pub struct PhiArg:
## The value this predecessor supplies.
pub var value: Ref
## The predecessor block's label.
pub var pred: u32
## A named local as the debugger sees it (`--debug`): its slot, its type's spelling.
pub struct LocalInfo:
## The local's name.
pub var name: str
## The slot the local lives in.
pub var slot: u32
## The local's type, spelled for the debugger.
pub var kind: str
## The local's byte size.
pub var size: u32
## The local's type.
pub var type_id: u32
## The line the local is declared on.
pub var line: u32
## Whether the local is a parameter.
pub var parameter: bool
## The lexical scope the local belongs to.
pub var scope: usize
## The inlined subroutine the local belongs to (`Instr.site`), 0 for the function's own.
pub var site: u32
## A statement boundary the in-program debugger stops at (`--debug`).
pub struct DebugPoint:
## The instruction index the statement begins at.
pub var instruction: usize
## The statement's source file.
pub var file: str
## The statement's line.
pub var line: u32
## The statement's column.
pub var column: u32
## A lexical scope (`--debug`), for the locals visible within it.
pub struct DebugScope:
## The enclosing scope's index, 0 for the function's own.
pub var parent: usize
## The instruction index the scope opens at.
pub var start: usize
## The instruction index the scope closes at.
pub var end: usize
## The inlined subroutine the scope belongs to (`Instr.site`), 0 for the function's own.
pub var site: u32
## A call a build with symbols opened out (`opt/inline.lucb`): the callee, for its abstract
## description, and where the call was, for the inlined subroutine's own.
pub struct InlineSite:
## The callee's name.
pub var name: str
## The callee's source file.
pub var source: str
## The line the callee is declared on.
pub var line: u32
## The callee's result type.
pub var result_type: u32
## The line and file (`Instr.file`) of the call.
pub var call_line: u32
## The file of the call, 0 for the caller's own source.
pub var call_file: u32
## The caller's scope the call was in.
pub var scope: u32
## The site the call itself was in, 0 for the caller's own body.
pub var parent: u32
## One lowered function: its instructions, slots and temporaries, with the metadata the generators and the debugger need.
pub struct Function:
## The function's symbol.
pub var name: str
## Whether the function has C linkage (§9.8).
pub var exported: bool
## Optional standard modules must not impose link dependencies on every program.
pub var standard: bool
## The package its declaration belongs to (`(standard)` for the standard library's),
## empty for a function the lowerer makes of its own: a function called from one place
## only is expanded there when that place is in its own package, or in such a function
## (`inline`).
pub var package: str = ""
## `--debug`: the source file, and every named local for the frame's descriptor.
pub var debug: bool
## `--release --debug`: DWARF for the optimised function, lines on every instruction,
## the named locals pinned to their slots; no hooks, no descriptor.
pub var symbols: bool
## The position `emit` stamps on each instruction.
pub var at_line: u32
## The file `emit` stamps on each instruction.
pub var at_file: u32
## The scope the lowerer is in, stamped on each instruction it emits (`Instr.scope`).
pub var at_scope: u32
## The function's source file.
pub var source: str
## The function's source-level name.
pub var source_name: str
## The line the function is declared on.
pub var source_line: u32
## The statement boundaries, for the in-program debugger.
pub var points: list.List[DebugPoint]
## The lexical scopes.
pub var debug_scopes: list.List[DebugScope]
## The calls the inliner opened out in a build with symbols, 1-based by `Instr.site`.
pub var sites: list.List[InlineSite]
## The named locals.
pub var locals: list.List[LocalInfo]
## The parameters as received.
pub var params: list.List[Param]
## The stack slots.
pub var slots: list.List[Slot]
## The instructions, in order.
pub var instrs: list.List[Instr]
## The call arguments and atomic operands, pooled.
pub var args: list.List[Arg]
## The call descriptions, indexed by `Instr.extra`.
pub var calls: list.List[CallInfo]
## The class of each temporary, by index.
pub var temps: list.List[Class]
## The phi arguments, pooled.
pub var phi_args: list.List[PhiArg]
## The jump tables of the `switch` instructions, indexed by `Instr.extra2`.
pub var jump_tables: list.List[Table]
## The jump tables' labels, pooled.
pub var jump_labels: list.List[u32]
## How many labels have been handed out.
pub var labels: u32
## The most levels the dynamic area below the frame holds (`Op.reserve`).
pub var dynamic_levels: u32 = 0
## Whether the function takes storage from its frame as it runs (`Op.alloca`): its stack
## pointer then moves by amounts only known at run time.
pub var allocates_frame: bool = false
## Whether the function returns a value.
pub var has_result: bool
## The result's register class.
pub var result_cls: Class
## The result's byte size, 0 for a scalar.
pub var result_size: u32
## The result's alignment.
pub var result_align: u32
## The result's type.
pub var result_type: u32
## The result aggregate's shape (1-based), 0 for none.
pub var result_shape: u32
## Whether the result goes back in the program's own convention (CallInfo.result_private).
pub var result_private: bool = false
## Whether the function is variadic.
pub var variadic: bool
## The attributes of §9.8 that reach the object file.
pub var naked: bool
## Whether the symbol is weak (§9.8).
pub var weak: bool
## Whether the symbol is retained even if unreferenced (§9.8).
pub var used: bool
## The section the function is placed in, empty for the default.
pub var section: str
## `noinline`: the body stands in for no call of it (§9.8).
pub var noinline: bool
## `inline`: the body stands in for every call of it that can be expanded, whatever its
## size up to `opt/inline`'s `forced` (§9.8).
pub var always_inline: bool = false
## An empty function named `name`.
pub static func create(name: str) -> Function!:
return Function(name = name, exported = false, debug = false, symbols = false, at_line = 0, at_file = 0, at_scope = 0, source = "", source_name = name, source_line = 1, points = try list.List[DebugPoint].create(0), debug_scopes = try list.List[DebugScope].create(0), sites = try list.List[InlineSite].create(0), locals = try list.List[LocalInfo].create(8),
params = try list.List[Param].create(8),
slots = try list.List[Slot].create(32), instrs = try list.List[Instr].create(256),
args = try list.List[Arg].create(32), calls = try list.List[CallInfo].create(16),
temps = try list.List[Class].create(128), phi_args = try list.List[PhiArg].create(16), jump_tables = try list.List[Table].create(0), jump_labels = try list.List[u32].create(0), labels = 0, has_result = false,
result_cls = Class.l, result_size = 0, result_align = 0, result_type = 0,
result_shape = 0, variadic = false)
## Free the function's lists, when it is dropped from its unit.
pub func destroy():
self.points.destroy()
self.debug_scopes.destroy()
self.sites.destroy()
self.locals.destroy()
self.params.destroy()
self.slots.destroy()
self.instrs.destroy()
self.args.destroy()
self.calls.destroy()
self.temps.destroy()
self.phi_args.destroy()
self.jump_tables.destroy()
self.jump_labels.destroy()
## A fresh temporary of class `cls`; its 1-based number.
pub func temp(cls: Class) -> u32!:
try self.temps.push(cls)
return u32(self.temps.count)
## The class of temporary `index`.
pub func temp_class(index: u32) -> Class:
return self.temps.get((usize)index - 1)
## A fresh slot of `wanted` bytes at `align`; its index.
pub func slot(wanted: u32, align: u32) -> u32!:
# an aggregate that travels in two registers lands as two words
let size = 16 if wanted > 8 and wanted < 16 else wanted
try self.slots.push(Slot(size = size if size > 0 else 1, align = align if align > 0 else 1))
return u32(self.slots.count - 1)
## A slot of `size` bytes at `offset` into level `level` of the dynamic area: the
## stack pointer moves below it while the level is reserved, rather than the fixed
## frame keeping its bytes for the whole call (a format buffer of an error path in a
## recursive function).
pub func dynamic_slot(level: u32, offset: u32, size: u32, align: u32) -> u32!:
try self.slots.push(Slot(size = size, align = align, level = level, offset = offset))
self.dynamic_levels = level if level > self.dynamic_levels else self.dynamic_levels
return u32(self.slots.count - 1)
## A fresh label number.
pub func label() -> u32:
self.labels += 1
return self.labels
## Append an instruction, stamping the current source position on it.
pub func emit(op: Op, cls: Class, dst: u32, a: Ref, b: Ref, extra: u32) -> !:
try self.instrs.push(Instr(op = op, cls = cls, dst = dst, a = a, b = b, extra = extra, extra2 = 0, line = self.at_line, file = self.at_file, scope = self.at_scope, site = 0))
## `dst = op a, b` with a fresh temporary.
## `dst = a op b` at class `cls`; a comparison compares at `cls` and answers a word.
pub func binary(op: Op, cls: Class, a: Ref, b: Ref) -> Ref!:
let t = try self.temp(Class.w if is_comparison(op) else cls)
try self.emit(op, cls, t, a, b, 0)
return temp_ref(t)
## `dst = op a` at class `cls`, into a fresh temporary.
pub func unary(op: Op, cls: Class, a: Ref) -> Ref!:
let t = try self.temp(cls)
try self.emit(op, cls, t, a, none_ref(), 0)
return temp_ref(t)
## Mark where label `label` lands.
pub func place_label(label: u32) -> !:
try self.emit(Op.label, Class.l, 0, none_ref(), none_ref(), label)
## An unconditional jump to `label`.
pub func jump(label: u32) -> !:
try self.emit(Op.jmp, Class.l, 0, none_ref(), none_ref(), label)
## Branch on `condition` being nonzero, tested at its own width: a pointer's low word
## may be zero while the pointer is not.
pub func branch(condition: Ref, then_label: u32, else_label: u32) -> !:
var cls = Class.l
if condition.kind == RefKind.temp and (usize)condition.index <= self.temps.count:
cls = self.temps.get((usize)condition.index - 1)
try self.instrs.push(Instr(op = Op.jnz, cls = cls, dst = 0, a = condition, b = none_ref(), extra = then_label, extra2 = else_label, line = 0, file = 0, scope = 0, site = 0))
## Jump to `labels[value - low]`, or to `default` when `value - low`, at class `cls`, is
## not below the number of labels (compared unsigned).
pub func switch(value: Ref, cls: Class, low: i64, labels: u32[], default: u32) -> !:
try self.jump_tables.push(Table(low = low, start = u32(self.jump_labels.count), count = u32(labels.length)))
for label in labels:
try self.jump_labels.push(label)
try self.instrs.push(Instr(op = Op.switch_, cls = cls, dst = 0, a = value, b = none_ref(), extra = default, extra2 = u32(self.jump_tables.count - 1), line = self.at_line, file = self.at_file, scope = self.at_scope, site = 0))
## The labels of jump table `index`.
pub func table_targets(index: u32) -> u32[]:
let t = self.jump_tables.get((usize)index)
return self.jump_labels.span()[(usize)t.start..<(usize)(t.start + t.count)]
## Load through `address` with `op`, into a fresh temporary.
pub func load(op: Op, cls: Class, address: Ref) -> Ref!:
let t = try self.temp(cls)
try self.emit(op, cls, t, address, none_ref(), 0)
return temp_ref(t)
## Store `value` through `address` with `op`.
pub func store(op: Op, value: Ref, address: Ref) -> !:
try self.emit(op, Class.l, 0, value, address, 0)
## The address of what `r` refers to, in a fresh temporary.
pub func address_of(r: Ref) -> Ref!:
let t = try self.temp(Class.l)
try self.emit(Op.addr, Class.l, t, r, none_ref(), 0)
return temp_ref(t)
## Copy `size` bytes from `source` to `target`.
pub func copy_bytes(target: Ref, source: Ref, size: u32) -> !:
try self.emit(Op.blit, Class.l, 0, target, source, size)
## Zero `size` bytes at `target`.
pub func zero_bytes(target: Ref, size: u32) -> !:
try self.emit(Op.zero, Class.l, 0, target, none_ref(), size)
## A text literal of the unit, emitted once with a NUL after it.
pub struct Text:
## The literal's bytes.
pub var bytes: str
## Data for a global: its symbol, its size, its alignment, and whether it is thread-local.
pub struct Global:
## The global's symbol.
pub var name: str
## Whether it belongs to a standard module.
pub var standard: bool
## The global's byte size.
pub var size: u32
## The global's alignment.
pub var align: u32
## Whether it is thread-local.
pub var is_thread_local: bool
## Whether it has C linkage.
pub var exported: bool
## Whether the symbol is weak.
pub var weak: bool
## Whether it is retained even if unreferenced.
pub var used: bool
## The section it is placed in, empty for the default.
pub var section: str
## `linked`: another object defines the storage; the program only refers to it.
pub var external: bool
## A standard global's initialiser, a function of its own that `lb_init_globals`
## calls, so the pruner keeps it with the global; empty for the rest.
pub var init_function: str = ""
## The bytes the global starts with, when its initialiser is literals laid out at
## compile time (`Lowerer.static_data`): the object holds them and no code stores them.
## None for storage that starts zero or is given its value by an initialiser.
pub var data: u8[]? = none
## Whether `data` is a top-level `let`'s, which the object keeps read-only.
pub var read_only: bool = false
## A witness table: the symbol and the functions it points at, in requirement order.
pub struct WitnessTable:
## The table's symbol.
pub var name: str
## The function symbols, in requirement order.
pub var entries: list.List[str]
## The whole program as the target sees it.
pub struct Unit:
## The program's functions.
pub var functions: list.List[Function]
## The source files instructions name by index (`Instr.file`), 1-based.
pub var files: list.List[str]
## The program's globals.
pub var globals: list.List[Global]
## The program's text literals.
pub var texts: list.List[Text]
## Where each text of `texts` is, by its bytes.
var text_index: hashed.Table[str]
## The witness tables.
pub var tables: list.List[WitnessTable]
## Module-level `asm` blocks for this target, verbatim (§8.9).
pub var module_asm: list.List[Text]
## The shapes of the aggregates passed and returned, and their leaves.
pub var shapes: list.List[Shape]
## The aggregate members, referenced by shapes.
pub var leaves: list.List[Leaf]
## The function the loader runs when the image is loaded, empty when there is none:
## a library's initialiser (§17.6). The generator places it in its object format's
## initialiser section.
pub var init_function: str
## The function a `trap` or a failed `bounds` calls with the reason's text: named here
## so the generators spell no symbol of the program, and the inliner keeps it.
pub var trap_function: str
## The same with the position first (§11.5): `trap_at(position, reason)` and, for an
## assertion whose message is computed, `trap_two_at(position, reason, detail)`.
pub var trap_at_function: str
## The function for an assertion whose message is computed (`trap_two_at`).
pub var trap_two_at_function: str
## An empty unit.
pub static func create() -> Unit!:
return Unit(functions = try list.List[Function].create(64), files = try list.List[str].create(8), globals = try list.List[Global].create(32),
texts = try list.List[Text].create(64), tables = try list.List[WitnessTable].create(16),
module_asm = try list.List[Text].create(4), shapes = try list.List[Shape].create(64), leaves = try list.List[Leaf].create(256),
init_function = "", trap_function = "", trap_at_function = "", trap_two_at_function = "", text_index = try hashed.Table[str].create(64))
## Which functions `marked` marks or one of those calls: the functions whose optimised
## bodies the marked ones' expansions read (`inline.expand_small`), in the heap.
pub func called_by(marked: const bool[]) -> bool[]!:
let n = self.functions.count
with memory.heap:
var names = try hashed.Table[str].create(n)
defer names.destroy()
for i in 0..<n:
_ = try names.add(self.functions.items[i].name, i)
var reached = try new bool[n] ---
for i in 0..<n:
reached[i] = marked[i]
for i in 0..<n:
if not marked[i]:
continue
for x in self.functions.items[i].instrs.span():
if x.op == Op.call and x.a.kind == RefKind.function:
if let g = names.find(x.a.name):
reached[g] = true
return reached
## The first `n` functions, the most instructions first (by index among equals), in
## the heap: the order threads take them in (`parallel.each_ordered`), so that no
## large one starts last and keeps one thread busy after the others are done.
pub func largest_first(n: usize) -> usize[]!:
with memory.heap:
var keys = try new u64[n] ---
defer free(keys)
for i in 0..<n:
let size = self.functions.items[i].instrs.count
let clamped = (u64)size if size < 0xFFFFFFFF else 0xFFFFFFFF
keys[i] = ((0xFFFFFFFF - clamped) << 32) | (u64)i
try sort_words(keys)
var order = try new usize[n] ---
for i in 0..<n:
order[i] = (usize)(keys[i] & 0xFFFFFFFF)
return order
## The index of a source file in `files`, adding it when new; 1-based.
pub func file_index(path: str) -> u32!:
var i: usize = 0
while i < self.files.count:
if self.files.get(i) == path:
return u32(i + 1)
i += 1
try self.files.push(path)
return u32(self.files.count)
## The index of a text literal, adding it when new.
## The leaves of shape `shape` (1-based), empty for 0.
pub func leaves_of(shape: u32) -> Leaf[]:
if shape == 0 or (usize)shape > self.shapes.count:
return self.leaves.span()[..<0]
let s = self.shapes.get((usize)shape - 1)
return self.leaves.span()[(usize)s.start..<(usize)(s.start + s.count)]
## The class word `k` (bytes `8k ..< 8k + 8`) of an aggregate of shape `shape` travels
## in when the aggregate comes back in registers word by word: `d` or `s` when the word
## holds one float leaf, at its start, and nothing else, in a float register; `l` for
## any other word, in an integer one. The program's own convention (`CallInfo.
## result_private`) takes every word so, and System V's eightbytes agree where it
## returns them a word at a time.
pub func word_class(shape: u32, k: u32) -> Class:
let low = k * 8
var found = Class.l
var count: u32 = 0
for leaf in self.leaves_of(shape):
if leaf.offset < low + 8 and leaf.offset + (u32)leaf.size > low:
count += 1
found = leaf.cls if leaf.offset == low and (leaf.cls == Class.d or leaf.cls == Class.s) else Class.l
return found if count == 1 else Class.l
## How many bytes of word `k` of an aggregate of shape `shape` its leaves reach, one to
## eight; eight for a word without one. A word read only so far leaves its padding
## behind, so a fallible result's flag word, a byte, comes back 0 or 1 even from a slot
## (`opt.failure_flags`).
pub func word_reach(shape: u32, k: u32) -> u32:
let low = k * 8
var reach: u32 = 0
for leaf in self.leaves_of(shape):
let end = leaf.offset + (u32)leaf.size
if leaf.offset < low + 8 and end > low and end - low > reach:
reach = end - low
return 8 if reach == 0 or reach > 8 else reach
## Record a shape from the leaves pushed since `start`; its 1-based index.
pub func shape_from(start: usize) -> u32!:
try self.shapes.push(Shape(start = u32(start), count = u32(self.leaves.count - start)))
return u32(self.shapes.count)
## The index of text literal `bytes` when the unit has it. It reads and never adds, so
## the generators' threads may ask it at once (`back.parallel`).
pub func find_text(bytes: str) -> u32?:
let index = self.text_index.find(bytes) else return none
return u32(index)
## The index of text literal `bytes`, adding it when new.
pub func text(bytes: str) -> u32!:
if let found = self.find_text(bytes):
return found
try self.texts.push(Text(bytes = bytes))
let index = self.texts.count - 1
_ = try self.text_index.add(bytes, index)
return u32(index)
## Index every text again, after `texts` is replaced (`inline` drops the unread ones).
pub func index_texts() -> !:
self.text_index.destroy()
self.text_index = try hashed.Table[str].create(self.texts.count)
for index in 0..<self.texts.count:
_ = try self.text_index.add(self.texts.get(index).bytes, index)
## A text a generator needed was not among the unit's texts when its function was generated.
pub let missing_text: ErrorCode = ErrorCode.package(44)
## The arguments an instruction reads from the function's argument list, as a start and a
## count: a call's, the expected and desired values of `atomic_cas`, and the addend of
## `fma`, which sit there too. Every pass that walks a call's arguments walks these, so a cas's operands are
## renamed, resolved, counted live, and kept out of promoted slots like any other use.
pub func argument_range(f: Function*, x: Instr) -> (u32, u32):
if x.op == Op.call:
let info = f.calls.get((usize)x.extra)
return (info.args_start, info.args_count)
if x.op == Op.atomic_cas:
return ((u32)x.b.value, 2)
if x.op == Op.fma or x.op == Op.select:
return (x.extra2, 1)
if x.op == Op.ret and x.extra2 > 0:
return (x.extra, x.extra2)
return (0, 0)
## The load op for a scalar of a size and signedness, or a float.
pub func load_op(size: u64, signed: bool, is_float: bool) -> Op:
if is_float:
return Op.loadhf if size == 2 else (Op.loads if size == 4 else Op.loadd)
if size == 1:
return Op.loadsb if signed else Op.loadub
if size == 2:
return Op.loadsh if signed else Op.loaduh
if size == 4:
return Op.loadsw if signed else Op.loaduw
return Op.loadl
## The store op for a scalar of a size, or a float.
pub func store_op(size: u64, is_float: bool) -> Op:
if is_float:
return Op.storehf if size == 2 else (Op.stores if size == 4 else Op.stored)
if size == 1:
return Op.storeb
if size == 2:
return Op.storeh
if size == 4:
return Op.storew
return Op.storel
## The load of a whole register of class `cls`: a word, a long, a float of its width, or
## a vector.
pub func load_of(cls: Class) -> Op:
match cls:
.w: return Op.loaduw
.l: return Op.loadl
.v: return Op.loadv
_: return load_op(8 if cls == Class.d else (2 if cls == Class.h else 4), false, true)
## The store of a whole register of class `cls`.
pub func store_of(cls: Class) -> Op:
match cls:
.w: return Op.storew
.l: return Op.storel
.v: return Op.storev
_: return store_op(8 if cls == Class.d else (2 if cls == Class.h else 4), true)
test "a function collects temporaries, slots, and instructions":
var backing: u8[262144]
var arena = memory.FixedBuffer.over(backing)
with arena:
var f = try Function.create("f")
let a = try f.binary(Op.add, Class.l, const_ref(1), const_ref(2))
let s = try f.slot(8, 8)
try f.store(Op.storel, a, slot_ref(s))
let back = try f.load(Op.loadl, Class.l, slot_ref(s))
assert(f.instrs.count == 3)
assert(f.temps.count == 2)
assert(back.index == 2)
var u = try Unit.create()
assert((try u.text("hi")) == 0)
assert((try u.text("hi")) == 0)
assert((try u.text("yo")) == 1)