Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-kernel

Source of release 0.1.1

0.1.1 / src / lower / lowerer.lucb

# The lowering's state: values in registers, the locals and columns they live in, the
# exec-mask frames of branches and loops, and the first refusal with its position.

## A value in registers: `width` lanes of `kind` (1 for a scalar; a vector or a small
## array has more), lane k in register `lanes[k]`.
struct Value:
    var kind: Kind
    var width: usize
    var lanes: u16[32]
    ## A record's lanes differ in kind (`kinds`); everything else is `kind` throughout.
    var kinds: Kind[32]
    var mixed: bool
    ## An API value (`k.input(1)`): the lane holds what names it, passed to its methods.
    var handle: bool
    ## Every element has the same value (built from constants and uniforms only).
    var uniform: bool
    ## The registers belong to a variable that may still change: a copy keeps the value.
    var borrowed: bool
    ## The Base type.
    var type_id: u32

    ## The kind of lane `k`.
    func lane_kind(k: usize) -> Kind:
        return self.kinds[k] if self.mixed else self.kind

## A record type's lanes and their kinds.
struct Record:
    var width: usize
    var kinds: Kind[32]

## A local variable or `let`: its declaration and the registers holding it.
struct Local:
    var decl: ast.Node*
    var value: Value
    ## Its registers stay fixed (it is written inside a branch or loop): writes go into
    ## them. Otherwise a write just makes the new value the local's.
    var pinned: bool
    ## Written in no element-dependent context: writes ignore the exec mask.
    var uniform: bool

## A column the snippet reads or writes through a field or accessor.
struct ColumnUse:
    var name: str
    var kind: Kind
    ## Lanes of the Base value (4 for an `f32[4]`) and values per element in the column.
    var width: usize
    var components: usize
    var type_id: u32
    var read: bool
    var written: bool[32]
    var pinned: bool
    var value: Value
    ## Where the snippet first names it, for diagnostics.
    var first_use: ast.Node*?

## A loop being lowered: lanes still looping (`alive`, when it has a `break`), lanes that
## did not `continue` this round (`going`, when it has a `continue`), and its label.
struct Loop:
    var label: str
    var alive: u16
    var going: u16

## A function being lowered, the entry or an inlined helper: the lanes that have not
## returned (`live`, when a `return` can come before its end) and a helper's result.
struct Function:
    var decl: ast.Node*
    var live: u16
    var result: Value
    var has_result: bool

## Everything the walk over one entry function keeps.
struct Lowerer:
    var c: const check.Checker*
    var host: const Host*
    var b: Builder
    var snippet: usize
    var locals: collections.List[Local]
    var columns: collections.List[ColumnUse]
    var frames: collections.List[u16]
    var loops: collections.List[Loop]
    var functions: collections.List[Function]
    var inlining: collections.List[ast.Node*]
    ## The receivers of the methods being inlined (`self` is the last).
    var receivers: collections.List[Value]
    ## How deep the walk is in `lib` bodies, and the snippet's call that entered them:
    ## positions and refusals there point at that call.
    var library_depth: usize
    var library_call: ast.Node*?
    var varying_decls: collections.List[ast.Node*]
    ## The helpers whose bodies the scan has walked for the columns they use.
    var scanned_helpers: collections.List[ast.Node*]
    var pinned_decls: collections.List[ast.Node*]
    var texts: collections.TextPool
    var exec_now: u16 = 0xFFFF
    var exec_dirty: bool
    var changed: bool
    ## The first refusal: where and why.
    var failed: bool
    var failure_offset: usize
    var failure_module: usize
    var failure: str
    var room: u8[512]

    func destroy():
        self.b.destroy()
        self.locals.destroy()
        self.columns.destroy()
        self.frames.destroy()
        self.loops.destroy()
        self.functions.destroy()
        self.inlining.destroy()
        self.receivers.destroy()
        self.varying_decls.destroy()
        self.scanned_helpers.destroy()
        self.pinned_decls.destroy()
        self.texts.destroy()

    # mark: Refusals ==========================================================================

    ## Stop with `message` at `node`.
    func fail(node: ast.Node*, message: str) -> !:
        if not self.failed:
            let at = self.snippet_node(node)
            self.failed = true
            self.failure_offset = at.start
            self.failure_module = self.module_of(at)
            self.failure = self.texts.keep_text(message.bytes) catch failure:
                recover "out of memory"
        error(refused, message)

    ## `node`, or inside a `lib` body the snippet's call that entered it.
    func snippet_node(node: ast.Node*) -> ast.Node*:
        if self.library_depth > 0:
            if let call = self.library_call: return call
        return node

    func fail_value(node: ast.Node*, message: str) -> Value!:
        try self.fail(node, message)
        return self.nothing()

    ## "`name` is not available in a kernel", at `node`.
    func not_available(node: ast.Node*, what: str) -> Value!:
        let text = strings.format(self.room, f"{what} is not available in a kernel") else "not available in a kernel"
        return try self.fail_value(node, text)

    ## The snippet module, where every node the lowering meets lives.
    func module_of(node: ast.Node*) -> usize:
        _ = node
        return self.snippet

    func nothing() -> Value:
        var value: Value
        value.uniform = true
        value.type_id = types.none_id
        return value

    # mark: Types =============================================================================

    ## The engine kind and lane count of a Base type a kernel holds: a scalar, or a vector
    ## or array of up to 16 scalars.
    func shape(type_id: u32) -> (Kind, usize)?:
        if let kind = scalar_kind(type_id):
            return (kind, 1)
        if type_id <= types.f16_id:
            return none
        let t = self.c.table.get(type_id)
        if t.kind != types.Kind.array or t.length == 0 or t.length > 32:
            return none
        let element = scalar_kind(t.elem) else return none
        return (element, (usize)t.length)

    ## A record's lanes: each field's lanes in declaration order (a scalar, a vector or a
    ## small array each), at most 32 in all; none for any other type.
    func record(type_id: u32) -> Record?:
        if type_id <= types.f16_id:
            return none
        let t = self.c.table.get(type_id)
        if t.kind != types.Kind.struct_:
            return none
        let decl = t.decl else return none
        var found: Record
        var cursor = decl.body
        while let member = cursor:
            cursor = member.next
            if member.kind != ast.Kind.field:
                continue
            let shaped = self.shape(member.type_id) else return none
            let (kind, width) = shaped
            if found.width + width > 32:
                return none
            for k in 0..<width: found.kinds[found.width + k] = kind
            found.width += width
        if found.width == 0:
            return none
        return found

    ## Field `name` of record type `type_id`: its first lane, kind and lane count.
    func field_of(type_id: u32, name: str) -> (usize, Kind, usize, u32)?:
        let decl = self.c.table.get(type_id).decl else return none
        var offset: usize = 0
        var cursor = decl.body
        while let member = cursor:
            cursor = member.next
            if member.kind != ast.Kind.field:
                continue
            let shaped = self.shape(member.type_id) else return none
            let (kind, width) = shaped
            if member.text == name:
                return (offset, kind, width, member.type_id)
            offset += width
        return none

    ## A record of `type_id` whose every lane is 0 of its kind.
    func zero_record(shape: Record, type_id: u32) -> Value:
        var value = self.nothing()
        value.width = shape.width
        value.mixed = true
        value.type_id = type_id
        value.kind = shape.kinds[0]
        for k in 0..<shape.width:
            value.kinds[k] = shape.kinds[k]
            value.lanes[k] = self.b.constant(shape.kinds[k], 0)
        return value

    ## The zero of `type_id`: a scalar's, a vector's or a record's; a refusal at `node`
    ## for any other type.
    func zero_value(node: ast.Node*, type_id: u32) -> Value!:
        if let shape = self.record(type_id):
            return self.zero_record(shape, type_id)
        let (kind, width) = try self.shape_or_fail(node, type_id)
        return self.zero(kind, width, type_id)

    ## The shape of `type_id`, or a refusal at `node`.
    func shape_or_fail(node: ast.Node*, type_id: u32) -> (Kind, usize)!:
        if let found = self.shape(type_id):
            return found
        var described: u8[200]
        let name = self.type_name(described, type_id)
        let text = strings.format(self.room, f"a value of type `{name}` is not available in a kernel") else "this type is not available in a kernel"
        try self.fail(node, text)
        return (Kind.f32, 1)

    func type_name(buffer: u8[], type_id: u32) -> str:
        let t = self.c.table.get(type_id)
        if t.name.length > 0:
            return t.name
        if type_id == types.i8_id: return "i8"
        if type_id == types.i16_id: return "i16"
        if type_id == types.u8_id: return "u8"
        if type_id == types.u16_id: return "u16"
        if type_id == types.str_id: return "str"
        return strings.format(buffer, f"type {type_id}") else "this type"

    # mark: Values ============================================================================

    ## A scalar value in `register`.
    func scalar(kind: Kind, register: u16, uniform: bool, type_id: u32) -> Value:
        var value = self.nothing()
        value.kind = kind
        value.width = 1
        value.lanes[0] = register
        value.uniform = uniform
        value.type_id = type_id
        return value

    ## Fresh registers holding a copy of `value` (consecutive, so vector operations take
    ## them), written on every lane.
    func copied(value: Value) -> Value:
        var copy = value
        let first = self.b.record(value.kinds[..<value.width]) if value.mixed else self.b.vector(value.kind, value.width)
        for k in 0..<value.width:
            let kind = value.lane_kind(k)
            copy.lanes[k] = first +% (u16)k
            self.b.emit(.copy, kind, first +% (u16)k, value.lanes[k], 0, 0)
        copy.borrowed = false
        return copy

    ## `value` in consecutive registers (the first of them), copying when its lanes are not.
    func consecutive(value: Value) -> u16:
        var ordered = true
        for k in 1..<value.width:
            if value.lanes[k] != value.lanes[0] +% (u16)k:
                ordered = false
        if ordered and not value.borrowed:
            return value.lanes[0]
        return self.copied(value).lanes[0]

    ## The zero of a type's shape.
    func zero(kind: Kind, width: usize, type_id: u32) -> Value:
        var value = self.scalar(kind, self.b.constant(kind, 0), true, type_id)
        value.width = width
        for k in 1..<width:
            value.lanes[k] = value.lanes[0]
        return value

    # mark: Exec masks ========================================================================

    ## Narrow the active lanes to `mask` (and every frame already open).
    func push_frame(mask: u16) -> !:
        try self.frames.append(mask)
        self.exec_dirty = true

    func pop_frame():
        self.frames.truncate(self.frames.length() - 1)
        self.exec_dirty = true

    ## Make the exec mask the frames' intersection, if anything changed since it was set.
    ## Jump targets mark it changed: the paths into a label may have left different masks.
    func sync():
        if not self.exec_dirty:
            return
        self.exec_dirty = false
        let count = self.frames.length()
        if count == 0:
            self.b.exec_all()
            self.exec_now = no_register
            return
        var mask = self.frames.at(0)
        for at in 1..<count:
            mask = self.b.binary(.band, mask, self.frames.at(at))
        self.b.exec(mask)
        self.exec_now = mask

    ## Bind `label` (a join: the mask is set again before the next masked instruction).
    func join(label: engine.Label):
        self.b.bind(label)
        self.exec_dirty = true

    ## Skip to `label` when no lane is active now.
    func skip_if_idle(label: engine.Label):
        self.sync()
        if self.exec_now != no_register:
            self.b.jump_if_none(self.exec_now, label)

    # mark: Locals ============================================================================

    func find_local(decl: ast.Node*) -> usize?:
        var at = self.locals.length()
        while at > 0:
            at -= 1
            if self.locals.at(at).decl == decl:
                return at
        return none

    func is_varying(decl: ast.Node*) -> bool:
        return contains(self.varying_decls.view(), decl)

    func is_pinned(decl: ast.Node*) -> bool:
        return contains(self.pinned_decls.view(), decl)

    ## Declare `decl` holding `value`: pinned locals get registers of their own.
    func declare(decl: ast.Node*, value: Value) -> !:
        let pinned = self.is_pinned(decl)
        var held = value
        if pinned or value.borrowed:
            held = self.copied(value)
        held.uniform = value.uniform and not self.is_varying(decl)
        try self.locals.append(Local(decl = decl, value = held, pinned = pinned, uniform = not self.is_varying(decl)))

    ## The value of local `at`, marked borrowed when it may still change.
    func local_value(at: usize) -> Value:
        let local = self.locals.at(at)
        var value = local.value
        value.borrowed = local.pinned
        value.uniform = local.uniform
        return value

    ## Write `value` (already of the local's shape) into local `at`, lane `lane` only when
    ## `lane` is below 16.
    func write_local(at: usize, value: Value, lane: usize = every_lane):
        var local = self.locals.at(at)
        if not local.pinned:
            if lane < every_lane:
                local.value.lanes[lane] = value.lanes[0]
            else:
                local.value.lanes = (self.copied(value) if value.borrowed else value).lanes
            self.locals.set(at, local)
            return
        self.write_registers(local.value, value, lane, local.uniform)

    ## Write `value` into `target`'s registers: every lane, or just `lane`; masked by the
    ## exec mask unless the target is uniform.
    func write_registers(target: Value, value: Value, lane: usize, uniform: bool):
        if not uniform: self.sync()
        for k in 0..<target.width:
            if lane < every_lane and k != lane:
                continue
            let source = value.lanes[0] if lane < every_lane else value.lanes[k]
            if uniform:
                self.b.emit(.copy, target.lane_kind(k), target.lanes[k], source, 0, 0)
            else:
                self.b.assign(target.lanes[k], source)

## A lane number standing for every lane, and for a lane known only at run time.
let every_lane: usize = 64
let some_lane: usize = 65

## Whether `list` holds `node`.
func contains(list: const (ast.Node*)[], node: ast.Node*) -> bool:
    for item in list:
        if item == node:
            return true
    return false

## The engine kind of a scalar type (literals take i64 and f64 when nothing typed them).
func scalar_kind(type_id: u32) -> Kind?:
    if type_id == types.bool_id: return Kind.mask
    if type_id == types.i32_id: return Kind.i32
    if type_id == types.i64_id or type_id == types.isize_id or type_id == types.untyped_int_id: return Kind.i64
    if type_id == types.u32_id: return Kind.u32
    if type_id == types.u64_id or type_id == types.usize_id: return Kind.u64
    if type_id == types.f32_id: return Kind.f32
    if type_id == types.f64_id or type_id == types.untyped_float_id: return Kind.f64
    return none