For the complete documentation index, see llms.txt. Markdown versions of all pages are available by appending .md to any URL (e.g. /get-started.md).
Mojo module
two_level_layout
Provides a two-level TensorLayout conformer.
A TwoLevelLayout splits a layout into an integer outer part and an F2-linear
inner part. The inner part is the map a hardware swizzle applies inside one
atom's footprint; the outer part carries the footprint bases with ordinary
integer strides. A coordinate's contribution is
Outer(o) + (x0 ^ Lambda(y))where x0 is a w-bit XOR base. x0 is zero for a whole tensor and moves
when a tile starts inside a footprint.
The inner map is given as comptime basis images, one image per inner index
bit. The low bits of each mode are its inner bits, packed mode by mode from
the low bit up. Lambda is injective, so TwoLevelLayout is not affine and
is_affine is False: code that steps through memory by adding a stride
must not do so for this layout.
Use two_level_layout_from_swizzle
to turn a Swizzle and an integer Layout into an exact TwoLevelLayout.
You can import these APIs from the layout package:
from layout.two_level_layout import TwoLevelLayoutcomptime values
SwizzledTwoLevelLayout
comptime SwizzledTwoLevelLayout[LayoutType: TensorLayout, bits: Int, base: Int, shift: Int] = TwoLevelLayout[Layout[TypeList[#kgen.param_list.tabulate(LayoutType.rank, [idx: __mlir_type.index] ComptimeInt[Int((shr LayoutType.__shape_types[idx].static_value, _log2_or_zero(LayoutType.__shape_types[idx].static_value) if (xor identical((lt _log2_or_zero(LayoutType.__shape_types[idx].static_value), Int(0) if (xor identical((lt (add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits), 0), False), True) else Int((add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits))), False), True) else Int(0) if (xor identical((lt (add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits), 0), False), True) else Int((add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits)) if identical((add LayoutType.__shape_types[idx].static_value, -1) and LayoutType.__shape_types[idx].static_value, 0) if (xor identical((xor (lt LayoutType.__shape_types[idx].static_value, 1), True), False), True) else (xor identical((xor (lt LayoutType.__shape_types[idx].static_value, 1), True), False), True) and identical((add LayoutType.__stride_types[idx].static_value, -1) and LayoutType.__stride_types[idx].static_value, 0) if (xor identical((xor (lt LayoutType.__stride_types[idx].static_value, 1), True), False), True) else (xor identical((xor (lt LayoutType.__stride_types[idx].static_value, 1), True), False), True) else Int(0)))])](), TypeList[#kgen.param_list.tabulate(LayoutType.rank, [idx: __mlir_type.index] ComptimeInt[Int((shl LayoutType.__stride_types[idx].static_value, _log2_or_zero(LayoutType.__shape_types[idx].static_value) if (xor identical((lt _log2_or_zero(LayoutType.__shape_types[idx].static_value), Int(0) if (xor identical((lt (add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits), 0), False), True) else Int((add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits))), False), True) else Int(0) if (xor identical((lt (add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits), 0), False), True) else Int((add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits)) if identical((add LayoutType.__shape_types[idx].static_value, -1) and LayoutType.__shape_types[idx].static_value, 0) if (xor identical((xor (lt LayoutType.__shape_types[idx].static_value, 1), True), False), True) else (xor identical((xor (lt LayoutType.__shape_types[idx].static_value, 1), True), False), True) and identical((add LayoutType.__stride_types[idx].static_value, -1) and LayoutType.__stride_types[idx].static_value, 0) if (xor identical((xor (lt LayoutType.__stride_types[idx].static_value, 1), True), False), True) else (xor identical((xor (lt LayoutType.__stride_types[idx].static_value, 1), True), False), True) else Int(0)))])]()], TypeList[#kgen.param_list.tabulate(LayoutType.rank, [idx: __mlir_type.index] Coord[*#kgen.param_list.tabulate(_log2_or_zero(LayoutType.__shape_types[idx].static_value) if (xor identical((lt _log2_or_zero(LayoutType.__shape_types[idx].static_value), Int(0) if (xor identical((lt (add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits), 0), False), True) else Int((add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits))), False), True) else Int(0) if (xor identical((lt (add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits), 0), False), True) else Int((add (mul _log2_or_zero(LayoutType.__stride_types[idx].static_value), -1), shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(#pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), base, bits)) if identical((add LayoutType.__shape_types[idx].static_value, -1) and LayoutType.__shape_types[idx].static_value, 0) if (xor identical((xor (lt LayoutType.__shape_types[idx].static_value, 1), True), False), True) else (xor identical((xor (lt LayoutType.__shape_types[idx].static_value, 1), True), False), True) and identical((add LayoutType.__stride_types[idx].static_value, -1) and LayoutType.__stride_types[idx].static_value, 0) if (xor identical((xor (lt LayoutType.__stride_types[idx].static_value, 1), True), False), True) else (xor identical((xor (lt LayoutType.__stride_types[idx].static_value, 1), True), False), True) else Int(0), [idx: __mlir_type.index] ComptimeInt[Int((xor (shl LayoutType.__stride_types[idx].static_value, idx), (shr (shl (add (shl 1, bits), -1), (add shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(0), base)) and (shl LayoutType.__stride_types[idx].static_value, idx), shift))) if (xor identical((xor (lt shift, 1), True), False), True) else Int((xor (shl (shl (add (shl 1, bits), -1), (add shift if (xor identical((xor (lt shift, 1), True), False), True) else Int(0), base)) and (shl LayoutType.__stride_types[idx].static_value, idx), #pop.simd_neg<#lit.struct.extract<:!lit.struct<@std::@simd::@SIMD<:!lit.struct<@std::@builtin::@dtype::@DType> {:dtype index}, :!lit.struct<@std::@builtin::@simd_length::@SIMDLength> {1}>> shift, "_mlir_value"> : !kgen.scalar<index>>), (shl LayoutType.__stride_types[idx].static_value, idx)))])])]()]
The exact TwoLevelLayout of a Swizzle[bits, base, shift] applied to a fully-static integer layout.
Parameters
- LayoutType (
TensorLayout): The integer layout the swizzle is applied to. - bits (
Int): The swizzle mask width. - base (
Int): The swizzle's constant low bits. - shift (
Int): The swizzle's mask shift.
TwoLevelLayout
comptime TwoLevelLayout[Outer: TensorLayout, Inner: TypeList[values]] = _TwoLevelLayout[Outer, TypeList[#kgen.param_list.tabulate(Outer.rank, [idx: __mlir_type.index] ComptimeInt[Int((shl Outer.__shape_types[idx].static_value, values[idx].__len__()()))] if Outer.__shape_types[idx].is_static_value else Scalar[Outer.__shape_types[idx].DTYPE])](), TypeList[#kgen.param_list.tabulate(Outer.rank, [idx: __mlir_type.index] ComptimeInt[#kgen.param_list.reduce(values[idx]._ParamListType, base=Int(-1), reducer=[PrevV: Int, VA: KGENParamList[CoordLike], idx: __mlir_type.index] PrevV if (xor identical(PrevV, -1), True) else VA[idx].static_value)] if (xor identical((xor (lt values[idx].__len__()(), 1), True), False), True) else Outer.__stride_types[idx])](), Inner]
A layout with an integer outer part and an F2-linear inner part.
Outer maps each mode's high coordinate bits to a footprint base; every one
of its offsets is a multiple of 2 ^ w. Inner holds one list of basis
images per mode, one image per low inner index bit. A coordinate x splits
per mode into x[i] >> k[i] (outer) and the low k[i] bits (inner), and
maps to
Outer(o) + (x0 ^ Lambda(y))where Lambda XORs the images of the set inner index bits and x0 is a
w-bit XOR base, zero for a whole tensor. Because the inner part is not a
sum of coordinate times stride, is_affine is False.
Parameters
- Outer (
TensorLayout): The integer outer layout. - Inner (
TypeList[values]): The inner map's basis images, one list per mode. A mode withk[i]inner index bits contributesk[i]images, low bit first; a mode without inner bits contributes an empty list.
Functions
-
two_level_layout_from_swizzle: Builds the exactTwoLevelLayoutof a swizzle and an integer layout.