Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-kernel

Source of release 0.1.1

0.1.1 / tools / lanes.py

#!/usr/bin/env python3
"""Write the engine's per-kind lane loops (src/engine/lanes_*.lucb) and their unit tests
(tests/engine/lanes_*_checks.lucb).

Arithmetic, bits, math, compares and conversions are the same loop in six widths; this
table states each operation once and writes one Base function per (operation, kind) plus
the dispatcher that picks it by the instruction's kind. Run it after changing the table:

    python3 tools/lanes.py
"""
from pathlib import Path

ROOT = Path(__file__).resolve().parents[1]
ENGINE = ROOT / "src" / "engine"
TESTS = ROOT / "tests" / "engine"
HEADER = "# Generated by tools/lanes.py from its tables; edit those, not this file.\n"

FLOATS = ["f32", "f64"]
SIGNED = ["i32", "i64"]
UNSIGNED = ["u32", "u64"]
INTS = SIGNED + UNSIGNED
NUMBERS = FLOATS + INTS
ALL = NUMBERS + ["mask"]
LANE = {"f32": "f32", "f64": "f64", "i32": "i32", "i64": "i64", "u32": "u32", "u64": "u64", "mask": "u8"}
VIEW = {"f32": "f32s", "f64": "f64s", "i32": "i32s", "i64": "i64s", "u32": "u32s", "u64": "u64s", "mask": "masks"}
WIDTH = {"i32": 32, "i64": 64, "u32": 32, "u64": 64}
MINIMUM = {"i32": -(2**31), "i64": -(2**63), "u32": 0, "u64": 0}
MAXIMUM = {"i32": 2**31 - 1, "i64": 2**63 - 1, "u32": 2**32 - 1, "u64": 2**64 - 1}


def math_module(kind):
    return "math32" if kind == "f32" else "math"


def lib_name(name, kind):
    """lib's scalar function for `kind`: `lerp` for f32, `lerp64` for f64."""
    if kind == "f32":
        return f"lib.{name}"
    return f"lib.{name}_64" if name[-1].isdigit() else f"lib.{name}64"


def literal(value):
    return f"({value})" if value < 0 else str(value)


# mark: binary ===============================================================================

def binary_body(op, kind):
    """(expression for lane i or None, fault template or None): a and b name the lanes."""
    m = math_module(kind)
    simple = {
        "add": "a[i] + b[i]", "sub": "a[i] - b[i]", "mul": "a[i] * b[i]", "div": "a[i] / b[i]",
        "wadd": "a[i] +% b[i]", "wsub": "a[i] -% b[i]", "wmul": "a[i] *% b[i]",
        "sadd": "a[i] +| b[i]", "ssub": "a[i] -| b[i]", "smul": "a[i] *| b[i]",
        "band": "a[i] & b[i]", "bor": "a[i] | b[i]", "bxor": "a[i] ^ b[i]",
        "pow": f"{m}.pow(a[i], b[i])", "atan2": f"{m}.atan2(a[i], b[i])",
        "fmod": f"{m}.mod(a[i], b[i])", "hypot": f"{m}.hypot(a[i], b[i])",
    }
    if op in ("min", "max"):
        if kind in FLOATS:
            return f"{m}.{op}(a[i], b[i])", None
        compare = "<" if op == "min" else ">"
        return f"a[i] if a[i] {compare} b[i] else b[i]", None
    if op in ("add", "sub", "mul") and kind in INTS:
        symbol = {"add": "+", "sub": "-", "mul": "*"}[op]
        return None, ("        if let value = a[i] {s}? b[i]:\n"
                      "            d[i] = value\n"
                      "        else:\n"
                      "            if on.at(i): return i\n"
                      "            d[i] = a[i] {s}% b[i]\n").format(s=symbol)
    if op in ("idiv", "rem"):
        symbol = "//" if op == "idiv" else "%"
        bad = "b[i] == 0"
        if kind in SIGNED:
            bad = f"b[i] == 0 or (b[i] == -1 and a[i] == {literal(MINIMUM[kind])})"
        return None, (f"        if {bad}:\n"
                      "            if on.at(i): return i\n"
                      "            d[i] = 0\n"
                      "        else:\n"
                      f"            d[i] = a[i] {symbol} b[i]\n")
    if op in ("shl", "shr"):
        symbol = "<<" if op == "shl" else ">>"
        bad = f"b[i] >= {WIDTH[kind]}"
        if kind in SIGNED:
            bad = f"b[i] < 0 or b[i] >= {WIDTH[kind]}"
        return None, (f"        if {bad}:\n"
                      "            if on.at(i): return i\n"
                      "            d[i] = 0\n"
                      "        else:\n"
                      f"            d[i] = a[i] {symbol} b[i]\n")
    return simple[op], None


BINARY = [
    ("add", NUMBERS), ("sub", NUMBERS), ("mul", NUMBERS), ("div", FLOATS),
    ("wadd", INTS), ("wsub", INTS), ("wmul", INTS), ("sadd", INTS), ("ssub", INTS), ("smul", INTS),
    ("idiv", INTS), ("rem", INTS), ("min", NUMBERS), ("max", NUMBERS),
    ("band", INTS + ["mask"]), ("bor", INTS + ["mask"]), ("bxor", INTS + ["mask"]),
    ("shl", INTS), ("shr", INTS), ("pow", FLOATS), ("atan2", FLOATS), ("fmod", FLOATS), ("hypot", FLOATS),
]

# mark: unary ================================================================================

UNARY_MATH = ["sqrt", "cbrt", "exp", "exp2", "log", "log2", "log10", "sin", "cos", "tan", "asin",
              "acos", "atan", "sinh", "cosh", "tanh", "floor", "ceil", "round", "trunc", "sign"]


def unary_body(op, kind):
    m = math_module(kind)
    if op in UNARY_MATH:
        return f"{m}.{op}(a[i])", None
    if op == "frac":
        return f"a[i] - {m}.floor(a[i])", None
    if op == "degrees":
        return f"a[i] * (180.0 / {m}.pi)", None
    if op == "radians":
        return f"a[i] * ({m}.pi / 180.0)", None
    if op == "wneg":
        return "-%a[i]", None
    if op == "bnot":
        return ("a[i] ^ 1", None) if kind == "mask" else ("~a[i]", None)
    if op in ("neg", "abs"):
        if kind in FLOATS:
            return ("-a[i]" if op == "neg" else f"{m}.abs(a[i])"), None
        result = "-a[i]" if op == "neg" else "a[i] if a[i] >= 0 else -a[i]"
        return None, (f"        if a[i] == {literal(MINIMUM[kind])}:\n"
                      "            if on.at(i): return i\n"
                      "            d[i] = a[i]\n"
                      "        else:\n"
                      f"            d[i] = {result}\n")
    raise KeyError(op)


UNARY = ([("neg", FLOATS + SIGNED), ("wneg", INTS), ("abs", FLOATS + SIGNED), ("bnot", INTS + ["mask"])]
         + [(name, FLOATS) for name in UNARY_MATH + ["frac", "degrees", "radians"]])

CLASSIFY = [("isnan", "is_nan"), ("isinf", "is_infinite"), ("isfinite", "is_finite")]
COMPARE = [("eq", "==", NUMBERS + ["mask"]), ("ne", "!=", NUMBERS + ["mask"]), ("lt", "<", NUMBERS),
           ("le", "<=", NUMBERS), ("gt", ">", NUMBERS), ("ge", ">=", NUMBERS)]


def ternary_body(op, kind):
    if op == "clamp":
        return "b[i] if a[i] < b[i] else (c[i] if a[i] > c[i] else a[i])"
    if op == "mul_add":
        return "a[i].mul_add(b[i], c[i])"
    return f"{lib_name(op, kind)}(a[i], b[i], c[i])"


TERNARY = [("mul_add", FLOATS), ("lerp", FLOATS), ("clamp", NUMBERS), ("smooth", FLOATS), ("fit01", FLOATS)]

# mark: conversions ==========================================================================


def cast_expression(source, target):
    if source == "mask" and target == "mask":
        return "a[i]"
    if target == "mask":
        zero = "0.0" if source in FLOATS else "0"
        return f"(u8)(a[i] != {zero})"
    return f"({LANE[target]})a[i]"


def convert_condition(source, target):
    """The condition under which Base's checked `target(x)` succeeds, or None for always."""
    if target in FLOATS:
        return None
    low, high = MINIMUM[target], MAXIMUM[target]
    if source in FLOATS:
        # Truncation toward zero: valid when low - 1 < x < high + 1. high + 1 is a power of
        # two, exact in either float; low - 1 only when the float can hold it exactly.
        exact = 2**24 if source == "f32" else 2**53
        top = f"a[i] < {high + 1}.0"
        if low == 0:
            bottom = "a[i] > -1.0"
        elif abs(low - 1) <= exact:
            bottom = f"a[i] > {low - 1}.0"
        else:
            bottom = f"a[i] >= {low}.0"
        return f"{bottom} and {top}"
    parts = []
    if MINIMUM[source] < low:
        parts.append(f"a[i] >= {literal(low)}")
    if MAXIMUM[source] > high:
        parts.append(f"a[i] <= {high}")
    return " and ".join(parts) if parts else None


# mark: writing ==============================================================================

def signature(name, kind, operands, faults, result_kind=None, source_kinds=None):
    lane = LANE[result_kind or kind]
    params = [f"d: {lane}[]"]
    for at, operand in enumerate(operands):
        operand_kind = source_kinds[at] if source_kinds else kind
        params.append(f"{operand}: const {LANE[operand_kind]}[]")
    if faults:
        params.append("on: Active")
    tail = " -> usize" if faults else ""
    return f"func {name}({', '.join(params)}){tail}:\n"


def loop_function(name, kind, operands, expression, fault, result_kind=None, source_kinds=None):
    text = signature(name, kind, operands, fault is not None, result_kind, source_kinds)
    if fault is None:
        # The assert of the lengths (equal by construction: every view is the chunk's live
        # lanes) lets the --opt 3 vectorizer drop the bounds checks and take the loop.
        checks = " and ".join(f"{operand}.length == d.length" for operand in operands)
        return text + f"    assert({checks})\n    for i in 0..<d.length: d[i] = {expression}\n"
    return text + "    for i in 0..<d.length:\n" + fault + "    return d.length\n"


def call_line(name, kind, operands, faults, result_kind=None, source_kinds=None):
    args = [f"w.{VIEW[result_kind or kind]}(ins.dst)"]
    for at, operand in enumerate(operands):
        operand_kind = source_kinds[at] if source_kinds else kind
        args.append(f"w.{VIEW[operand_kind]}(ins.{operand})")
    if faults:
        args.append("w.on()")
    call = f"{name}({', '.join(args)})"
    return f"return {call}" if faults else call


def dispatcher(name, doc, table):
    """table: list of (op, [(kind, function, call)])."""
    text = f"## {doc}\nfunc {name}(w: Worker*, ins: Instruction) -> usize:\n    match ins.op:\n"
    for op, rows in table:
        text += f"        .{op}:\n            match ins.kind:\n"
        for kind, call in rows:
            text += f"                .{kind}: {call}\n"
        text += "                _: return w.n\n"
    text += "        _: return w.n\n    return w.n\n"
    return text


def write(file_name, title, functions, dispatch):
    body = HEADER + f"# {title}\n\n" + dispatch + "\n" + "\n".join(functions)
    (ENGINE / file_name).write_text(body)


def generate_binary():
    functions, table = [], []
    for op, kinds in BINARY:
        rows = []
        for kind in kinds:
            expression, fault = binary_body(op, kind)
            name = f"{op}_{kind}"
            functions.append(loop_function(name, kind, ["a", "b"], expression, fault))
            rows.append((kind, call_line(name, kind, ["a", "b"], fault is not None)))
        table.append((op, rows))
    write("lanes_binary.lucb", "Binary lane operations: d = a op b, every operand of the instruction's kind.",
          functions, dispatcher("binary", "Run a binary instruction; the lowest faulting lane, or the lane count.", table))


def generate_unary():
    functions, table = [], []
    for op, kinds in UNARY:
        rows = []
        for kind in kinds:
            expression, fault = unary_body(op, kind)
            name = f"{op}_{kind}"
            functions.append(loop_function(name, kind, ["a"], expression, fault))
            rows.append((kind, call_line(name, kind, ["a"], fault is not None)))
        table.append((op, rows))
    for op, function in CLASSIFY:
        rows = []
        for kind in FLOATS:
            name = f"{op}_{kind}"
            expression = f"(u8){math_module(kind)}.{function}(a[i])"
            functions.append(loop_function(name, kind, ["a"], expression, None, result_kind="mask",
                                           source_kinds=[kind]))
            rows.append((kind, call_line(name, kind, ["a"], False, "mask", [kind])))
        table.append((op, rows))
    write("lanes_unary.lucb", "Unary lane operations and float classifications: d = op a.",
          functions, dispatcher("unary", "Run a unary or classifying instruction; the lowest faulting lane, or the lane count.", table))


def generate_compare():
    functions, table = [], []
    for op, symbol, kinds in COMPARE:
        rows = []
        for kind in kinds:
            name = f"{op}_{kind}"
            functions.append(loop_function(name, kind, ["a", "b"], f"(u8)(a[i] {symbol} b[i])", None,
                                           result_kind="mask", source_kinds=[kind, kind]))
            rows.append((kind, call_line(name, kind, ["a", "b"], False, "mask", [kind, kind])))
        table.append((op, rows))
    for op, kinds in TERNARY:
        rows = []
        for kind in kinds:
            name = f"{op}_{kind}"
            functions.append(loop_function(name, kind, ["a", "b", "c"], ternary_body(op, kind), None))
            rows.append((kind, call_line(name, kind, ["a", "b", "c"], False)))
        table.append((op, rows))
    write("lanes_compare.lucb", "Compares (mask results) and ternary lane operations.",
          functions, dispatcher("compare_or_ternary", "Run a compare or ternary instruction; never faults.", table))


def generate_conversions():
    functions = []
    text = ("## Run `cast` (C's `(T)x`) or `convert` (Base's checked `T(x)`) from `source` lanes to\n"
            "## the instruction's kind; the lowest faulting lane, or the lane count.\n"
            "func conversion(w: Worker*, ins: Instruction, source: Kind) -> usize:\n"
            "    if ins.op == .cast:\n        match source:\n")
    for source in ALL:
        text += f"            .{source}:\n                match ins.kind:\n"
        for target in ALL:
            name = f"cast_{source}_{target}"
            functions.append(loop_function(name, target, ["a"], cast_expression(source, target), None,
                                           source_kinds=[source]))
            text += f"                    .{target}: {call_line(name, target, ['a'], False, None, [source])}\n"
        text += "                    _: return w.n\n"
    text += "            _: return w.n\n        return w.n\n    match source:\n"
    for source in NUMBERS:
        text += f"        .{source}:\n            match ins.kind:\n"
        for target in NUMBERS:
            name = f"convert_{source}_{target}"
            condition = convert_condition(source, target)
            expression = f"({LANE[target]})a[i]"
            if condition is None:
                functions.append(loop_function(name, target, ["a"], expression, None, source_kinds=[source]))
                text += f"                .{target}: {call_line(name, target, ['a'], False, None, [source])}\n"
            else:
                fault = (f"        if {condition}:\n"
                         f"            d[i] = {expression}\n"
                         "        else:\n"
                         "            if on.at(i): return i\n"
                         "            d[i] = 0\n")
                functions.append(loop_function(name, target, ["a"], None, fault, source_kinds=[source]))
                text += f"                .{target}: {call_line(name, target, ['a'], True, None, [source])}\n"
        text += "                _: return w.n\n"
    text += "        _: return w.n\n    return w.n\n"
    write("lanes_convert.lucb", "Conversions between kinds: C casts and Base's checked conversions.", functions, text)


# mark: tests ================================================================================
# Each (operation, kind) runs eight lanes through the engine (in chunks of 3, on 2 threads)
# and compares every lane with a plain Base reference expression. Values stay where the
# checked operations do not fault; the fault suite covers faults.

VALUES = {
    "float_a": ["0.0", "-0.0", "1.5", "-2.25", "100.0", "0.001", "7.0", "-3.5"],
    "float_b": ["1.0", "2.0", "-0.5", "4.0", "-8.0", "0.25", "3.0", "0.5"],
    "float_c": ["2.0", "3.0", "0.5", "8.0", "1.0", "0.75", "9.0", "1.5"],
    "signed_a": ["0", "1", "-7", "100", "-1000", "12345", "77", "-2"],
    "signed_b": ["1", "2", "3", "-4", "5", "6", "7", "8"],
    "unsigned_a": ["10", "11", "70", "100", "1000", "12345", "77", "9"],
    "count_b": ["1", "2", "3", "4", "5", "6", "7", "8"],
    "mask_a": ["0", "1", "0", "1", "1", "0", "1", "0"],
    "mask_b": ["0", "0", "1", "1", "0", "1", "1", "1"],
}


def extremes(kind):
    high, low = str(MAXIMUM[kind]), literal(MINIMUM[kind])
    if kind in SIGNED:
        return [high, low, "-1", "0", "5", high, low, "3"], ["1", "-1", low, high, "7", high, low, "3"]
    return [high, "0", "1", "5", high, "2", "3", "4"], ["1", "1", high, "7", high, "3", "4", "5"]


def operands(op, kind):
    """Lane values (a, b) for an (operation, kind)."""
    if kind in FLOATS:
        return VALUES["float_a"], VALUES["float_b"]
    if kind == "mask":
        return VALUES["mask_a"], VALUES["mask_b"]
    if op in ("wadd", "wsub", "wmul", "sadd", "ssub", "smul", "band", "bor", "bxor", "min", "max", "wneg", "bnot"):
        return extremes(kind)
    a = VALUES["signed_a"] if kind in SIGNED else VALUES["unsigned_a"]
    b = VALUES["count_b"] if op in ("shl", "shr") or kind in UNSIGNED else VALUES["signed_b"]
    return a, b


def reference(op, kind):
    """The plain Base expression a lane must equal."""
    plain = {"add": "a[i] + b[i]", "sub": "a[i] - b[i]", "mul": "a[i] * b[i]", "idiv": "a[i] // b[i]",
             "rem": "a[i] % b[i]", "shl": "a[i] << b[i]", "shr": "a[i] >> b[i]"}
    if kind in INTS and op in plain:
        return plain[op]
    if op in ("neg", "abs") and kind in SIGNED:
        return "-a[i]" if op == "neg" else "a[i] if a[i] >= 0 else -a[i]"
    expression, _ = binary_body(op, kind) if op in dict(BINARY) else unary_body(op, kind)
    return expression


def array(name, kind, values):
    return f"    let {name}: {LANE[kind]}[8] = [{', '.join(values)}]\n"


def same(kind, left, right):
    if kind in FLOATS:
        return f"same_{kind}({left}, {right})"
    return f"{left} == ({right})"


def test_binary():
    text = HEADER + "# Unit checks of every binary operation in every width.\n"
    for op, kinds in BINARY:
        text += f"\ntest \"{op} in every width\":\n"
        for kind in kinds:
            a, b = operands(op, kind)
            text += array(f"a_{kind}", kind, a) + array(f"b_{kind}", kind, b)
            text += f"    var d_{kind}: {LANE[kind]}[8]\n"
            text += f"    assert(try binary_case(.{op}, .{kind}, a_{kind}, b_{kind}, d_{kind}, .{kind}) == none)\n"
            expression = reference(op, kind).replace("a[i]", f"a_{kind}[i]").replace("b[i]", f"b_{kind}[i]")
            text += f"    for i in 0..<8: assert({same(kind, f'd_{kind}[i]', expression)})\n"
    (TESTS / "lanes_binary_checks.lucb").write_text(text)


def test_unary():
    text = HEADER + "# Unit checks of every unary and classifying operation in every width.\n"
    for op, kinds in UNARY:
        text += f"\ntest \"{op} in every width\":\n"
        for kind in kinds:
            a, _ = operands(op, kind)
            text += array(f"a_{kind}", kind, a) + f"    var d_{kind}: {LANE[kind]}[8]\n"
            text += f"    assert(try unary_case(.{op}, .{kind}, a_{kind}, d_{kind}, .{kind}) == none)\n"
            expression = reference(op, kind).replace("a[i]", f"a_{kind}[i]")
            text += f"    for i in 0..<8: assert({same(kind, f'd_{kind}[i]', expression)})\n"
    for op, function in CLASSIFY:
        text += f"\ntest \"{op} in every width\":\n"
        for kind in FLOATS:
            text += array(f"a_{kind}", kind, VALUES["float_a"]) + f"    var d_{kind}: u8[8]\n"
            text += f"    assert(try unary_case(.{op}, .{kind}, a_{kind}, d_{kind}, .mask) == none)\n"
            text += f"    for i in 0..<8: assert(d_{kind}[i] == (u8){math_module(kind)}.{function}(a_{kind}[i]))\n"
    (TESTS / "lanes_unary_checks.lucb").write_text(text)


def test_compare():
    text = HEADER + "# Unit checks of every compare and ternary operation in every width.\n"
    for op, symbol, kinds in COMPARE:
        text += f"\ntest \"{op} in every width\":\n"
        for kind in kinds:
            a, b = operands(op, kind)
            b = [a[0], a[1]] + b[2:]
            text += array(f"a_{kind}", kind, a) + array(f"b_{kind}", kind, b) + f"    var d_{kind}: u8[8]\n"
            text += f"    assert(try binary_case(.{op}, .{kind}, a_{kind}, b_{kind}, d_{kind}, .mask) == none)\n"
            text += f"    for i in 0..<8: assert(d_{kind}[i] == (u8)(a_{kind}[i] {symbol} b_{kind}[i]))\n"
    for op, kinds in TERNARY:
        text += f"\ntest \"{op} in every width\":\n"
        for kind in kinds:
            a, b = operands(op, kind)
            c = VALUES["float_c"] if kind in FLOATS else [str(int(v) + 50) if kind in SIGNED else str(int(v) + 9) for v in b]
            if op == "clamp" and kind not in FLOATS:
                b = ["-5"] * 8 if kind in SIGNED else ["5"] * 8
                c = ["50"] * 8
            text += array(f"a_{kind}", kind, a) + array(f"b_{kind}", kind, b) + array(f"c_{kind}", kind, c)
            text += f"    var d_{kind}: {LANE[kind]}[8]\n"
            text += f"    assert(try ternary_case(.{op}, .{kind}, a_{kind}, b_{kind}, c_{kind}, d_{kind}) == none)\n"
            expression = ternary_body(op, kind)
            for name in "abc":
                expression = expression.replace(f"{name}[i]", f"{name}_{kind}[i]")
            text += f"    for i in 0..<8: assert({same(kind, f'd_{kind}[i]', expression)})\n"
    (TESTS / "lanes_compare_checks.lucb").write_text(text)


def conversion_values(source, target, checked):
    if source == "mask":
        return VALUES["mask_a"]
    if source in FLOATS:
        if checked and target in UNSIGNED:
            return ["0.0", "1.0", "7.5", "100.25", "126.9", "42.0", "3.0", "0.5"]
        if checked:
            return ["0.0", "-1.0", "7.5", "100.25", "-126.9", "42.0", "-3.0", "0.5"]
        return ["0.0", "-3.75", "7.5", "3000000000.0", "-126.9", "1.0e20", "-1.0e20", "0.5"]
    values = ["0", "1", "7", "100", "127", "42", "3", "9"]
    if not checked:
        values[1] = str(MAXIMUM[source])
        if source in SIGNED:
            values[2], values[3] = "-5", literal(MINIMUM[source])
    return values


def test_conversions():
    text = HEADER + "# Unit checks of every cast and checked conversion between kinds.\n"
    for checked in (False, True):
        sources = NUMBERS if checked else ALL
        op = "convert" if checked else "cast"
        for source in sources:
            text += f"\ntest \"{op} from {source}\":\n"
            for target in (NUMBERS if checked else ALL):
                values = conversion_values(source, target, checked)
                name = f"{source}_{target}"
                text += array(f"a_{name}", source, values) + f"    var d_{name}: {LANE[target]}[8]\n"
                text += f"    assert(try conversion_case(.{op}, .{source}, .{target}, a_{name}, d_{name}) == none)\n"
                expression = cast_expression(source, target).replace("a[i]", f"a_{name}[i]")
                text += f"    for i in 0..<8: assert({same(target, f'd_{name}[i]', expression)})\n"
    (TESTS / "lanes_convert_checks.lucb").write_text(text)


if __name__ == "__main__":
    generate_binary()
    generate_unary()
    generate_compare()
    generate_conversions()
    test_binary()
    test_unary()
    test_compare()
    test_conversions()