Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-kernel

Source of release 0.1.0

0.1.0 / src / lower / statements.lucb

# Statements. Element-dependent conditions push an exec-mask frame and run each side on
# its own lanes (skipped when a chunk has none); uniform ones are real jumps. Loops count
# their rounds with a `loop_step`; `break`, `continue` and `return` clear lanes from the
# masks that keep them running.

extend Lowerer:
    func statements(list: ast.Node*?) -> !:
        var cursor = list
        while let s = cursor:
            try self.statement(s)
            cursor = s.next

    func statement(s: ast.Node*) -> !:
        match s.kind:
            .block: try self.statements(s.body)
            .let_, .var_: try self.declaration(s)
            .assign: try self.assignment(s)
            .if_: try self.branch(s)
            .while_: try self.while_loop(s)
            .for_: try self.for_loop(s)
            .match_: try self.match_statement(s)
            .return_: try self.return_statement(s)
            .break_: try self.leave_loop(s, true)
            .continue_: try self.leave_loop(s, false)
            .expr_stmt:
                let call = s.left else return
                _ = try self.expression(call)
            _: try self.fail(s, "this statement is not available in a kernel")

    func declaration(s: ast.Node*) -> !:
        # An API value (`let g = k.input(1)`) or a record (`let hit = g.intersect(...)`)
        # holds what its initializer gives.
        if self.api_type(s.type_id) != none or self.record(s.type_id) != none:
            var value: Value
            if let initial = s.left:
                value = try self.expression(initial)
            elif let shape = self.record(s.type_id):
                value = self.zero_record(shape, s.type_id)
            else:
                return try self.fail(s, "an API value needs a value")
            # An API value written again inside a loop or branch (`s = s.concat(t)`) gets
            # registers of its own like any variable; otherwise it is the value itself.
            if value.handle and not self.is_pinned(s):
                try self.locals.append(Local(decl = s, value = value, pinned = false, uniform = value.uniform))
                return
            try self.declare(s, value)
            return
        let (kind, width) = try self.shape_or_fail(s, s.type_id)
        var value = self.zero(kind, width, s.type_id)
        if let initial = s.left:
            value = try self.converted(try self.expression(initial), s.type_id, initial)
        try self.declare(s, value)

    # mark: Assignment ========================================================================

    func assignment(s: ast.Node*) -> !:
        let place = s.left else return
        let operand = s.right else return
        var value = try self.expression(operand)
        if s.text != "=":
            let current = try self.expression(place)
            let symbol = (str)s.text.bytes[..<s.text.length - 1]
            value = try self.operate(s, symbol, current, try self.converted_operand(value, current, operand))
        try self.store(place, try self.converted(value, place.type_id, operand))

    ## Write `value` (of the place's type) to a local, a column field, or a lane of either.
    func store(place: ast.Node*, value: Value) -> !:
        match place.kind:
            .name:
                let decl = place.resolved else return
                let at = self.find_local(decl) else return try self.fail(place, "this name cannot be assigned in a kernel")
                self.write_local(at, value)
            .member:
                let binding = self.binding_of(place.left, place.text) else return try self.store_field(place, value)
                if binding.role != .field:
                    return try self.fail(place, "this member cannot be assigned")
                try self.write_column(place, binding.column, value, every_lane)
            .index:
                let owner = place.left else return
                let index = place.body else return
                if let constant = self.c.exact_integer(index, 64, true):
                    try self.store_lane(owner, value, try self.lane_number(index, constant, owner))
                    return
                try self.store_indexed(owner, index, value)
            _:
                try self.fail(place, "this place cannot be assigned in a kernel")

    ## Write `value` into a field of a record local (`m.x = row`).
    func store_field(place: ast.Node*, value: Value) -> !:
        let owner = place.left else return
        let found = self.field_of(owner.type_id, place.text) else return try self.fail(place, "this member cannot be assigned in a kernel")
        if owner.kind != ast.Kind.name:
            return try self.fail(place, "only a field of a local can be assigned in a kernel")
        let decl = owner.resolved else return
        let at = self.find_local(decl) else return try self.fail(owner, "this name cannot be assigned in a kernel")
        let (offset, kind, width, type_id) = found
        _ = kind
        _ = type_id
        for k in 0..<width:
            var lane = value
            lane.width = 1
            lane.lanes[0] = value.lanes[k if value.width > 1 else 0]
            self.write_local(at, lane, offset + k)

    ## Write `value` into lane `lane` of the local or column `owner` names.
    func store_lane(owner: ast.Node*, value: Value, lane: usize) -> !:
        if owner.kind == ast.Kind.name:
            let decl = owner.resolved else return
            let at = self.find_local(decl) else return try self.fail(owner, "this name cannot be assigned in a kernel")
            self.write_local(at, value, lane)
            return
        if owner.kind == ast.Kind.member:
            if let binding = self.binding_of(owner.left, owner.text):
                if binding.role == .field:
                    try self.write_column(owner, binding.column, value, lane)
                    return
        try self.fail(owner, "this place cannot be assigned in a kernel")

    ## Write `value` into the lane an element-dependent index picks (`v[i] = x`).
    func store_indexed(owner: ast.Node*, index: ast.Node*, value: Value) -> !:
        let target = try self.expression(owner)
        let at = try self.expression(index)
        if not target.borrowed:
            return try self.fail(owner, "this place cannot be assigned in a kernel")
        self.sync()
        self.b.place(target.lanes[0], target.width, at.lanes[0], value.lanes[0])

    ## The lane a constant index names, checked against the value's width.
    func lane_number(index: ast.Node*, constant: i64, owner: ast.Node*) -> usize!:
        let (kind, width) = try self.shape_or_fail(owner, owner.type_id)
        _ = kind
        if constant < 0 or (usize)constant >= width:
            try self.fail(index, "index out of bounds")
        return (usize)constant

    # mark: Columns ===========================================================================

    func column_index(node: ast.Node*, name: str) -> usize!:
        for (at, column) in self.columns.view().indexed():
            if column.name == name:
                return at
        try self.fail(node, "a column the scan did not see")
        return 0

    ## Write a column's value: every lane, or lane `lane`.
    func write_column(node: ast.Node*, name: str, value: Value, lane: usize) -> !:
        let at = try self.column_index(node, name)
        var use = self.columns.at(at)
        if use.pinned:
            self.write_registers(use.value, value, lane, false)
            return
        if lane < every_lane:
            use.value.lanes[lane] = value.lanes[0]
        else:
            use.value.lanes = (self.copied(value) if value.borrowed else value).lanes
        self.columns.set(at, use)

    # mark: Branches ==========================================================================

    func branch(s: ast.Node*) -> !:
        let condition = s.left else return
        let decision = try self.expression(condition)
        if decision.uniform:
            let otherwise = self.b.label()
            let done = self.b.label()
            self.b.jump_if_false(decision.lanes[0], otherwise)
            if let then_block = s.body: try self.statement(then_block)
            self.b.jump(done)
            self.join(otherwise)
            if let other = s.right: try self.statement(other)
            self.join(done)
            return
        try self.masked(decision.lanes[0], s.body)
        if let other = s.right:
            try self.masked(self.b.unary(.bnot, decision.lanes[0]), other)
        else:
            self.exec_dirty = true

    ## Run `body` on the active lanes in `mask`, skipping it when a chunk has none.
    func masked(mask: u16, body: ast.Node*?) -> !:
        let skip = self.b.label()
        try self.push_frame(mask)
        self.skip_if_idle(skip)
        if let statement = body: try self.statement(statement)
        self.pop_frame()
        self.join(skip)

    # mark: Loops =============================================================================

    func while_loop(s: ast.Node*) -> !:
        try self.loop_over(s, s.left, none)

    ## `for x in a..<b`, `a..=b`, or over the lanes of a vector or array.
    func for_loop(s: ast.Node*) -> !:
        let binding = s.left else return
        let range = s.right else return
        let (kind, width) = try self.shape_or_fail(binding, binding.type_id)
        if width != 1:
            return try self.fail(binding, "a loop variable must be a scalar")
        var counting = Counting(binding = binding, counter = self.nothing(), limit = self.nothing(), inclusive = false, source = self.nothing(), over_lanes = false)
        var first: Value
        if range.kind == ast.Kind.binary and (range.text == "..<" or range.text == "..="):
            let low = range.left else return
            let high = range.right else return
            first = try self.converted(try self.expression(low), binding.type_id, low)
            counting.limit = try self.converted(try self.expression(high), binding.type_id, high)
            counting.inclusive = range.text == "..="
        else:
            counting.source = try self.expression(range)
            if counting.source.kind != kind:
                return try self.fail(range, "a loop over lanes of another type")
            counting.over_lanes = true
            first = self.scalar(.i64, self.b.constant_i64(0), true, types.i64_id)
            counting.limit = self.scalar(.i64, self.b.constant_i64((i64)counting.source.width), true, types.i64_id)
        # The counter is written on every lane (only active lanes read it), so a loop with
        # uniform bounds keeps a uniform counter and its test stays a jump.
        let counter = self.b.register(first.kind)
        self.b.emit(.copy, first.kind, counter, first.lanes[0], 0, 0)
        counting.counter = self.scalar(first.kind, counter, first.uniform and counting.limit.uniform, first.type_id)
        try self.loop_over(s, none, &counting)

    ## A loop: test `condition` (or the counter) at the top of every round, run the body,
    ## count the round, go round again.
    func loop_over(s: ast.Node*, condition: ast.Node*?, counting: Counting*?) -> !:
        let exits = has_breaks(s.body, s.text)
        let continues = has_continues(s.body, s.text)
        var record = Loop(label = s.text, alive = no_register, going = no_register)
        let slot = self.b.loop_slot()
        var varying_test = condition != none and self.varies(condition)
        if let count = counting:
            varying_test = varying_test or not count.counter.uniform
        if exits or varying_test:
            record.alive = self.b.register(.mask)
            self.b.emit(.copy, .mask, record.alive, self.b.constant_mask(true), 0, 0)
            try self.push_frame(record.alive)
        if continues:
            record.going = self.b.register(.mask)
        try self.loops.append(record)
        self.b.loop_start(slot)
        let top = self.b.label()
        let done = self.b.label()
        self.join(top)
        if continues:
            self.b.emit(.copy, .mask, record.going, self.b.constant_mask(true), 0, 0)
            try self.push_frame(record.going)
        var decision: Value
        if let expression = condition:
            decision = try self.expression(expression)
        elif let count = counting:
            let compare: Op = .le if count.inclusive else .lt
            let uniform = count.counter.uniform
            decision = self.scalar(.mask, self.b.compare(compare, count.counter.lanes[0], count.limit.lanes[0]), uniform, types.bool_id)
        else:
            decision = self.scalar(.mask, self.b.constant_mask(true), true, types.bool_id)
        if decision.uniform:
            self.b.jump_if_false(decision.lanes[0], done)
        else:
            self.b.emit(.copy, .mask, record.alive, self.b.binary(.band, record.alive, decision.lanes[0]), 0, 0)
            self.exec_dirty = true
        self.skip_if_idle(done)
        let locals_before = self.locals.length()
        if let count = counting:
            var element = count.counter
            element.borrowed = false
            if count.over_lanes:
                let picked = self.b.pick(self.consecutive(count.source), count.source.width, count.counter.lanes[0])
                element = self.scalar(count.source.kind, picked, count.source.uniform and count.counter.uniform, count.binding.type_id)
            try self.declare(count.binding, element)
        try self.statements(s.body)
        self.locals.truncate(locals_before)
        if continues:
            self.pop_frame()
        if let count = counting:
            let counter = count.counter.lanes[0]
            let one = self.b.constant(count.counter.kind, 1)
            self.b.emit(.copy, count.counter.kind, counter, self.b.binary(.wadd, counter, one), 0, 0)
        self.sync()
        self.b.loop_step(slot, self.exec_now)
        self.b.jump(top)
        self.join(done)
        self.loops.truncate(self.loops.length() - 1)
        if exits or varying_test:
            self.pop_frame()

    ## `break` clears the active lanes from the loop's `alive` mask, `continue` from its
    ## `going` mask; the rest of the round runs without them.
    func leave_loop(s: ast.Node*, breaking: bool) -> !:
        var at = self.loops.length()
        while at > 0:
            at -= 1
            let found = self.loops.at(at)
            if s.text.length > 0 and found.label != s.text:
                continue
            let mask = found.alive if breaking else found.going
            if mask == no_register:
                return try self.fail(s, "internal: a loop without the mask its exits need")
            self.sync()
            self.b.assign(mask, self.b.constant_mask(false))
            if breaking and found.going != no_register:
                self.b.assign(found.going, self.b.constant_mask(false))
            self.exec_dirty = true
            return
        try self.fail(s, "a break or continue outside a loop")

    # mark: Match =============================================================================

    ## `match` on an integer: each arm runs on the lanes its patterns take that no earlier
    ## arm took.
    func match_statement(s: ast.Node*) -> !:
        let subject_node = s.left else return
        let subject = try self.expression(subject_node)
        if subject.width != 1 or subject.kind == .f32 or subject.kind == .f64:
            return try self.fail(subject_node, "match on this type is not available in a kernel")
        let remaining = self.b.register(.mask)
        self.b.emit(.copy, .mask, remaining, self.b.constant_mask(true), 0, 0)
        var arms = s.body
        while let arm = arms:
            var taken = self.b.constant_mask(false)
            var patterns = arm.left
            while let pattern = patterns:
                taken = self.b.binary(.bor, taken, try self.pattern(pattern, subject))
                patterns = pattern.next
            taken = self.b.binary(.band, taken, remaining)
            try self.push_frame(taken)
            if let guard_expression = arm.right:
                let guard_value = try self.expression(guard_expression)
                self.pop_frame()
                taken = self.b.binary(.band, taken, guard_value.lanes[0])
                try self.push_frame(taken)
            self.sync()
            self.b.emit(.copy, .mask, remaining, self.b.binary(.band, remaining, self.b.unary(.bnot, taken)), 0, 0)
            let skip = self.b.label()
            self.skip_if_idle(skip)
            if let arm_body = arm.body: try self.statement(arm_body)
            self.pop_frame()
            self.join(skip)
            arms = arm.next

    ## The lanes a pattern takes.
    func pattern(p: ast.Node*, subject: Value) -> u16!:
        if p.has(ast.flag_wildcard):
            return self.b.constant_mask(true)
        let low_node = p.left else return self.b.constant_mask(true)
        let low = try self.converted(try self.expression(low_node), subject.type_id, low_node)
        if let high_node = p.right:
            let high = try self.converted(try self.expression(high_node), subject.type_id, high_node)
            let above = self.b.compare(.ge, subject.lanes[0], low.lanes[0])
            return self.b.binary(.band, above, self.b.compare(.le, subject.lanes[0], high.lanes[0]))
        return self.b.compare(.eq, subject.lanes[0], low.lanes[0])

    # mark: Return ============================================================================

    func return_statement(s: ast.Node*) -> !:
        let at = self.functions.length() - 1
        let function = self.functions.at(at)
        if let value_node = s.left:
            let value = try self.converted(try self.expression(value_node), function.result.type_id, value_node)
            self.write_registers(function.result, value, every_lane, false)
        if function.live != no_register:
            self.sync()
            self.b.assign(function.live, self.b.constant_mask(false))
            for loop in self.loops.view():
                if loop.alive != no_register: self.b.assign(loop.alive, self.b.constant_mask(false))
            self.exec_dirty = true

## A `for` loop's counter: its register, its limit, and the lanes it walks when it runs
## over a vector or array.
struct Counting:
    var binding: ast.Node*
    var counter: Value
    var limit: Value
    var inclusive: bool
    var source: Value
    var over_lanes: bool

## Whether a loop body (of a loop labeled `label`) has a `break` that leaves it: its own,
## or a nested loop's naming its label; or a `return`.
func has_breaks(list: ast.Node*?, label: str) -> bool:
    return has_jump(list, ast.Kind.break_, label, false)

func has_continues(list: ast.Node*?, label: str) -> bool:
    return has_jump(list, ast.Kind.continue_, label, false)

func has_jump(list: ast.Node*?, kind: ast.Kind, label: str, nested: bool) -> bool:
    var cursor = list
    while let s = cursor:
        if s.kind == ast.Kind.return_:
            return true
        if s.kind == kind and (not nested or (label.length > 0 and s.text == label)):
            return true
        let inner = nested or s.kind == ast.Kind.while_ or s.kind == ast.Kind.for_
        if has_jump(s.body, kind, label, inner) or has_jump(s.right, kind, label, nested):
            return true
        if s.kind == ast.Kind.match_:
            var arms = s.body
            while let arm = arms:
                if has_jump(arm.body, kind, label, nested): return true
                arms = arm.next
        cursor = s.next
    return false