dymokomi/luce-kernel
Source of release 0.1.3
#!/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()