Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-kernel

Source of release 0.1.3

0.1.3 / src / lower / scan.lucb

# The scan before a function is lowered: which locals differ between elements (and so
# are written under the exec mask, and their conditions become masks), which are written
# inside branches or loops (and so need registers of their own), and which columns the
# snippet reads and writes.

extend Lowerer:
    ## The struct name of a value of a host type (`Point` for a `Point*`), if it is one.
    func api_type(type_id: u32) -> str?:
        if type_id <= types.f16_id:
            return none
        var t = self.c.table.get(type_id)
        if t.kind == types.Kind.pointer:
            t = self.c.table.get(t.elem)
        if t.kind != types.Kind.struct_ or not self.host.binds(t.name):
            return none
        return t.name

    ## The binding of `owner.member` when the owner is a host API value.
    func binding_of(owner: ast.Node*?, member: str) -> Binding?:
        let value = owner else return none
        let name = self.api_type(value.type_id) else return none
        return self.host.find(name, member)

    ## The binding a call goes through: an API method, or a host function of a module.
    func call_binding(call: ast.Node*) -> Binding?:
        let callee = call.left else return none
        if callee.kind == ast.Kind.member:
            if let found = self.binding_of(callee.left, callee.text):
                return found
        let decl = call.resolved else return none
        let module = self.module_name_of(decl) else return none
        return self.host.find(module, decl.text)

    ## The declaration of the snippet's or a host helper module's function a call
    ## inlines (none for `lib`, whose bodies read no columns, and for bindings).
    func helper_of(call: ast.Node*) -> ast.Node*?:
        let decl = call.resolved else return none
        if decl.kind != ast.Kind.func_: return none
        let module = self.module_name_of(decl) else return none
        if module == self.c.modules.get(self.snippet).name or self.host.inlines(module): return decl
        return none

    ## The module whose top level declares `decl`.
    func module_name_of(decl: ast.Node*) -> str?:
        for m in self.c.modules.span():
            var cursor = m.tree.body
            while let d = cursor:
                if d == decl:
                    return m.name
                if d.kind == ast.Kind.struct_:
                    # A method or static function of the module's struct.
                    var member = d.body
                    while let inner = member:
                        if inner == decl: return m.name
                        member = inner.next
                cursor = d.next
        return none

    ## Whether `e` may differ between elements.
    func varies(e: ast.Node*?) -> bool:
        let node = e else return false
        match node.kind:
            .literal:
                return false
            .name:
                let decl = node.resolved else return false
                if self.is_varying(decl):
                    return true
                return decl.kind == ast.Kind.param and self.is_element_number(decl)
            .member:
                if let binding = self.binding_of(node.left, node.text):
                    return binding.role != .uniform and binding.role != .parameter
                return self.varies(node.left)
            .call:
                if let binding = self.call_binding(node):
                    if binding.role == .parameter or binding.role == .uniform or binding.role == .reader:
                        return false
                    if binding.role == .handle:
                        return self.varies_list(node.body)
                        return false
                    if binding.role != .builtin:
                        return true
                    return true
                # A method's receiver is an argument too.
                var receiver = false
                if let callee = node.left:
                    if callee.kind == ast.Kind.member: receiver = self.varies(callee.left)
                return receiver or self.varies_list(node.body)
            .self_:
                if self.receivers.length() == 0: return false
                return not self.receivers.at(self.receivers.length() - 1).uniform
            .argument:
                return self.varies(node.left)
            _:
                return self.varies(node.left) or self.varies(node.right) or self.varies_list(node.body) or (node.kind == ast.Kind.conditional and self.varies(node.ty))

    func varies_list(list: ast.Node*?) -> bool:
        var cursor = list
        while let node = cursor:
            if self.varies(node):
                return true
            cursor = node.next
        return false

    ## Whether `node` names a parameter of the function being lowered (an API pointer
    ## parameter such as `p` or `k`, rather than an API value an expression gives).
    func is_parameter(node: ast.Node*) -> bool:
        if node.kind != ast.Kind.name:
            return false
        let decl = node.resolved else return false
        return decl.kind == ast.Kind.param

    ## Whether a parameter of the entry is the element's number (`n: i64` of Numbers).
    func is_element_number(decl: ast.Node*) -> bool:
        if self.functions.length() == 0:
            return false
        let entry = self.functions.at(0).decl
        var cursor = entry.right
        while let parameter = cursor:
            if parameter == decl:
                return scalar_kind(decl.type_id) != none
            cursor = parameter.next
        return false

    ## Scan function body `body` until the classification settles. `all_varying` makes
    ## every context element-dependent (a function that can return early).
    func scan_function(body: ast.Node*?) -> !:
        let all_varying = has_early_return(body, 0)
        self.changed = true
        while self.changed:
            self.changed = false
            # After an early return the lanes that returned keep their values, so every
            # write is a masked one into fixed registers.
            try self.scan_list(body, all_varying, 1 if all_varying else 0)

    func mark_varying(decl: ast.Node*) -> !:
        if not self.is_varying(decl):
            try self.varying_decls.append(decl)
            self.changed = true

    func mark_pinned(decl: ast.Node*) -> !:
        if not self.is_pinned(decl):
            try self.pinned_decls.append(decl)

    func scan_list(list: ast.Node*?, context: bool, depth: u32) -> !:
        var cursor = list
        while let statement = cursor:
            try self.scan_statement(statement, context, depth)
            cursor = statement.next

    func scan_statement(s: ast.Node*, context: bool, depth: u32) -> !:
        match s.kind:
            .block:
                try self.scan_list(s.body, context, depth)
            .let_, .var_:
                try self.scan_expression(s.left, depth)
                if self.varies(s.left):
                    try self.mark_varying(s)
            .assign:
                try self.scan_expression(s.right, depth)
                try self.scan_place(s.left, context or self.varies(s.right), depth, every_lane)
            .if_:
                try self.scan_expression(s.left, depth)
                let inner = context or self.varies(s.left)
                if let then_block = s.body:
                    try self.scan_statement(then_block, inner, depth + 1)
                if let otherwise = s.right:
                    try self.scan_statement(otherwise, inner, depth + 1)
            .while_:
                try self.scan_expression(s.left, depth)
                try self.scan_list(s.body, context or self.varies(s.left) or has_exit(s.body), depth + 1)
            .for_:
                let binding = s.left else return
                try self.scan_expression(s.right, depth)
                if self.varies(s.right):
                    try self.mark_varying(binding)
                try self.scan_list(s.body, context or self.varies(s.right) or has_exit(s.body), depth + 1)
            .match_:
                try self.scan_expression(s.left, depth)
                var arms = s.body
                var inner = context or self.varies(s.left)
                while let arm = arms:
                    if self.varies(arm.right):
                        inner = true
                    arms = arm.next
                arms = s.body
                while let arm = arms:
                    if let arm_body = arm.body:
                        try self.scan_statement(arm_body, inner, depth + 1)
                    arms = arm.next
            .return_:
                try self.scan_expression(s.left, depth)
            .expr_stmt:
                try self.scan_expression(s.left, depth)
            _:
                return

    ## Columns an expression reads, through fields and accessors.
    func scan_expression(e: ast.Node*?, depth: u32) -> !:
        let node = e else return
        match node.kind:
            .member:
                if let binding = self.binding_of(node.left, node.text):
                    if binding.role == .field:
                        let at = try self.column_use(node, binding.column, binding.components, node.type_id)
                        self.mark_read(at)
                    else:
                        # A method of an API value another call gives (`g.pcopen(p.P,
                        # 0.1, 8).count()`): that call reads columns too.
                        try self.scan_expression(node.left, depth)
                    return
            .call:
                if let binding = self.call_binding(node):
                    if binding.role == .computed:
                        let at = try self.column_use(node, binding.column, binding.components, node.type_id)
                        self.mark_read(at)
                        return
                    if binding.role == .getter or binding.role == .setter:
                        let name = try self.literal_name(node, binding.column)
                        let value_type = node.type_id if binding.role == .getter else argument_type(node, 1)
                        let at = try self.column_use(node, name, binding.components, value_type)
                        if binding.role == .getter:
                            self.mark_read(at)
                        else:
                            try self.mark_written(at, every_lane, depth > 0)
                        try self.scan_expression_list(node.body, depth)
                        return
                # A helper reading the element through a parameter (`fade(p)`) uses
                # columns too: its body is walked once, its writes taken as masked.
                if let helper = self.helper_of(node):
                    if not contains(self.scanned_helpers.view(), helper):
                        try self.scanned_helpers.append(helper)
                        if let body = helper.body:
                            try self.scan_list(body.body, true, depth + 1)
            _:
                _ = 0
        try self.scan_expression(node.left, depth)
        try self.scan_expression(node.right, depth)
        try self.scan_expression(node.ty, depth)
        try self.scan_expression_list(node.body, depth)

    func scan_expression_list(list: ast.Node*?, depth: u32) -> !:
        var cursor = list
        while let node = cursor:
            try self.scan_expression(node, depth)
            cursor = node.next

    ## A written place: its root local or column, which lane (16: all), whether masked.
    func scan_place(place: ast.Node*?, varying: bool, depth: u32, lane: usize) -> !:
        let node = place else return
        match node.kind:
            .name:
                let decl = node.resolved else return
                if varying: try self.mark_varying(decl)
                if depth > 0 or lane == some_lane: try self.mark_pinned(decl)
            .index:
                try self.scan_expression(node.body, depth)
                var which: usize = some_lane
                if let index = node.body:
                    if let constant = self.c.exact_integer(index, 64, true):
                        if constant >= 0 and constant < 32: which = (usize)constant
                try self.scan_place(node.left, varying or self.varies(node.body), depth, which)
            .member:
                # A field of a record local: some lanes of the local.
                let binding = self.binding_of(node.left, node.text) else return try self.scan_place(node.left, varying, depth, some_lane)
                if binding.role != .field:
                    return
                let at = try self.column_use(node, binding.column, binding.components, node.type_id)
                try self.mark_written(at, lane, depth > 0 or lane == some_lane)
            _:
                return

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

    ## The column `name` used with a value of `type_id`, added when new.
    func column_use(node: ast.Node*, name: str, components: usize, type_id: u32) -> usize!:
        for (at, column) in self.columns.view().indexed():
            if column.name == name:
                if column.type_id != type_id:
                    try self.fail(node, "a column used with two different types")
                return at
        let (kind, width) = try self.shape_or_fail(node, type_id)
        if components > width:
            try self.fail(node, "a column has more components than its value has lanes")
        let kept = try self.texts.keep_text(name.bytes)
        var use = ColumnUse(name = kept, kind = kind, width = width, components = components, type_id = type_id, value = self.nothing(), first_use = node)
        if self.host.known_columns:
            if let stored = self.host.input_column(name):
                if stored.kind != kind or stored.components < components:
                    let text = strings.format(self.room, f"`{name}` is stored as {stored.kind.name()} with {stored.components} components") else "a column of another type"
                    try self.fail(node, text)
        try self.columns.append(use)
        return self.columns.length() - 1

    func mark_read(at: usize):
        var use = self.columns.at(at)
        use.read = true
        self.columns.set(at, use)

    func mark_written(at: usize, lane: usize, pinned: bool) -> !:
        var use = self.columns.at(at)
        for k in 0..<use.width:
            if (lane >= every_lane or k == lane) and k < use.components:
                use.written[k] = true
        use.pinned = use.pinned or pinned
        self.columns.set(at, use)

    ## The column a getter or setter call names: `prefix` and its literal first argument.
    func literal_name(call: ast.Node*, prefix: str) -> str!:
        let first = call.body else return ""
        let value = first.left else return ""
        if value.kind != ast.Kind.literal or value.text.length < 2 or value.text.bytes[0] != '"':
            try self.fail(value, "a column name must be a literal")
        let name = (str)value.text.bytes[1..<value.text.length - 1]
        var joined: u8[512]
        let text = strings.format(joined, f"{prefix}{name}") else name
        return try self.texts.keep_text(text.bytes)

## The type of argument `index` of a call.
func argument_type(call: ast.Node*, index: usize) -> u32:
    var cursor = call.body
    var at: usize = 0
    while let argument = cursor:
        if at == index:
            if let value = argument.left:
                return value.type_id
        at += 1
        cursor = argument.next
    return types.none_id

## Whether a statement list holds a `break`, `continue` or `return` (outside nested loops
## for the first two).
func has_exit(list: ast.Node*?) -> bool:
    var cursor = list
    while let s = cursor:
        match s.kind:
            .break_, .continue_, .return_:
                return true
            .while_, .for_:
                if has_return(s.body): return true
            _:
                if has_exit(s.body) or has_exit_branch(s.right):
                    return true
                if s.kind == ast.Kind.match_ and has_exit_arms(s.body):
                    return true
        cursor = s.next
    return false

func has_exit_branch(branch: ast.Node*?) -> bool:
    let node = branch else return false
    if node.kind == ast.Kind.block:
        return has_exit(node.body)
    if node.kind == ast.Kind.if_:
        return has_exit(node.body) or has_exit_branch(node.right) or has_exit_branch(node.body)
    return false

func has_exit_arms(arms: ast.Node*?) -> bool:
    var cursor = arms
    while let arm = cursor:
        if let arm_body = arm.body:
            if has_exit(arm_body.body): return true
        cursor = arm.next
    return false

## Whether a statement list holds a `return` anywhere.
func has_return(list: ast.Node*?) -> bool:
    var cursor = list
    while let s = cursor:
        if s.kind == ast.Kind.return_:
            return true
        if has_return(s.body) or has_return(s.right):
            return true
        cursor = s.next
    return false

## Whether a `return` comes anywhere but as the last statement of the function's body.
func has_early_return(body: ast.Node*?, depth: u32) -> bool:
    var cursor = body
    while let s = cursor:
        if s.kind == ast.Kind.return_:
            if depth > 0 or s.next != none:
                return true
        elif has_early_return(s.body, depth + 1) or has_early_return(s.right, depth + 1):
            return true
        cursor = s.next
    return false