# examples/welder/tile_graph.py
"""CPU teaching model of tile propagation, tile traffic and tile search.

Uses only Python's standard library. Run with --json for deterministic output.
This is an independently authored model, not Welder's code. It runs no GPU
kernel, models none of the hardware penalties of the paper's Section 4.1, and
predicts no latency.
"""

import argparse
import dataclasses
import json
import math

FP32_BYTES = 4
MIB = 1024 * 1024
LEVELS = ("register", "shared", "global")  # Fastest first.


# region: propagate
@dataclasses.dataclass(frozen=True)
class Matmul:
    """C[m, n] = A[m, k] @ B[k, n], with the reduction axis left untiled."""

    k: int

    def propagate(self, out_tile):
        """Return (chain input tile, side input tiles) for an output tile."""
        rows, cols = out_tile
        return (rows, self.k), [(self.k, cols)]


@dataclasses.dataclass(frozen=True)
class RowSoftmax:
    """Softmax over the last axis, so a tile must hold whole rows."""

    width: int

    def propagate(self, out_tile):
        rows, cols = out_tile
        if cols != self.width:
            raise ValueError("Softmax tiles must span the full row width")
        return (rows, cols), []


@dataclasses.dataclass(frozen=True)
class Elementwise:
    """ReLU and other pointwise operators keep the tile shape."""

    def propagate(self, out_tile):
        return tuple(out_tile), []


@dataclasses.dataclass(frozen=True)
class Window:
    """A sliding window over (height, width, channels); padding is ignored.

    Set in_channels for a convolution. Leave it unset for pooling.
    """

    kernel: int
    stride: int
    in_channels: int | None = None

    def propagate(self, out_tile):
        height, width, channels = out_tile

        def extent(size):
            return (size - 1) * self.stride + self.kernel

        if self.in_channels is None:
            return (extent(height), extent(width), channels), []
        weights = (self.kernel, self.kernel, self.in_channels, channels)
        return (extent(height), extent(width), self.in_channels), [weights]


def propagate_chain(operators, out_tile):
    """Propagate an output tile from the last operator back to the first.

    Returns (tiles, side_tiles). tiles[0] feeds operators[0], tiles[i] is the
    reuse tile between operators[i - 1] and operators[i], and tiles[-1] is the
    output tile. side_tiles holds weights and other non-chain inputs.
    """
    tiles = [tuple(out_tile)]
    side_tiles = []
    for operator in reversed(operators):
        chain_tile, sides = operator.propagate(tiles[0])
        tiles.insert(0, chain_tile)
        side_tiles.extend(sides)
    return tiles, side_tiles
# endregion: propagate


# region: traffic
def tile_count(tensor_shape, tile):
    """Count the tile-graphs needed to cover the output tensor exactly."""
    if len(tensor_shape) != len(tile):
        raise ValueError("Tile and tensor need the same rank")
    if any(size % step for size, step in zip(tensor_shape, tile)):
        raise ValueError("Tile must divide the output tensor evenly")
    return math.prod(size // step for size, step in zip(tensor_shape, tile))


def tile_graph_bytes(tiles, side_tiles, bytes_per_element=FP32_BYTES):
    """Count global bytes for one tile-graph: input, side inputs, output.

    Reuse tiles between operators stay on chip and are not counted.
    """
    moved = [tiles[0], tiles[-1], *side_tiles]
    return sum(math.prod(tile) for tile in moved) * bytes_per_element


def footprint_bytes(tiles, side_tiles, bytes_per_element=FP32_BYTES):
    """Sum every tile; an upper bound, since the paper reuses buffers."""
    every = [*tiles, *side_tiles]
    return sum(math.prod(tile) for tile in every) * bytes_per_element


def traffic(operators, tensor_shape, out_tile, bytes_per_element=FP32_BYTES):
    """Return per-tile bytes, tile count, total bytes and footprint."""
    tiles, side_tiles = propagate_chain(operators, out_tile)
    per_tile = tile_graph_bytes(tiles, side_tiles, bytes_per_element)
    count = tile_count(tensor_shape, out_tile)
    return {
        "bytesPerTile": per_tile,
        "tileCount": count,
        "totalBytes": per_tile * count,
        "footprintBytes": footprint_bytes(tiles, side_tiles, bytes_per_element),
    }
# endregion: traffic


# region: connect
def connected_groups(edge_levels, layer):
    """Group a chain of operators at one memory layer.

    edge_levels[i] names the layer that holds the tile reused between operators
    i and i + 1. Neighbors share a group at `layer` when their edge is reused at
    that layer or a faster one.
    """
    rank = {name: index for index, name in enumerate(LEVELS)}
    if layer not in rank or any(level not in rank for level in edge_levels):
        raise ValueError(f"Levels must be one of {LEVELS}")
    groups = [[0]]
    for index, level in enumerate(edge_levels, start=1):
        if rank[level] <= rank[layer]:
            groups[-1].append(index)
        else:
            groups.append([index])
    return groups
# endregion: connect


# region: schedule
def search_tiles(operators, tensor_shape, candidates, capacity_bytes, top_k,
                 bytes_per_element=FP32_BYTES):
    """Mimic SubGraphTiling: propagate, drop over capacity, rank by traffic."""
    kept = []
    for out_tile in candidates:
        cost = traffic(operators, tensor_shape, out_tile, bytes_per_element)
        if cost["footprintBytes"] > capacity_bytes:
            continue
        kept.append((cost["totalBytes"], tuple(out_tile), cost))
    kept.sort(key=lambda entry: entry[:2])
    return [{"outTile": list(tile), **cost} for _, tile, cost in kept[:top_k]]
# endregion: schedule


def matmul_softmax(rows=98304, k=64, cols=128):
    """Return the paper's Section 2 chain and its output tensor shape."""
    return [Matmul(k), RowSoftmax(cols)], (rows, cols)


def row_candidates(total_rows, cols, limit=256):
    """List power-of-two row counts that tile the output exactly."""
    candidates, rows = [], 1
    while rows <= limit and total_rows % rows == 0:
        candidates.append((rows, cols))
        rows *= 2
    return candidates


def conv_relu_maxpool(in_channels, out_channels):
    """Return named operators for the paper's Figure 5 chain."""
    return [
        ("Conv3x3", Window(3, 1, in_channels)),
        ("ReLU", Elementwise()),
        ("MaxPool2x2", Window(2, 2)),
    ], out_channels


def layer_plan(edge_levels, in_channels=3, out_channels=8):
    """Propagate a 1 x 1 output tile through each group at each layer."""
    named, channels = conv_relu_maxpool(in_channels, out_channels)
    plan = {}
    for layer in LEVELS[:2]:
        groups = []
        for members in connected_groups(edge_levels, layer):
            operators = [named[index][1] for index in members]
            tiles, _ = propagate_chain(operators, (1, 1, channels))
            groups.append({
                "operators": [named[index][0] for index in members],
                "spatialTiles": [list(tile[:2]) for tile in tiles],
            })
        plan[layer] = groups
    return plan


def self_check():
    """Reproduce the paper's worked numbers and exercise the edge cases."""
    operators, shape = matmul_softmax()
    four = traffic(operators, shape, (4, 128))
    sixteen = traffic(operators, shape, (16, 128))
    assert four["bytesPerTile"] == (4 * 64 + 64 * 128 + 4 * 128) * 4 == 35840
    assert four["tileCount"] == 24576
    assert four["totalBytes"] == 880803840 and four["totalBytes"] == 840 * MIB
    assert sixteen["bytesPerTile"] == 45056 and sixteen["tileCount"] == 6144
    assert sixteen["totalBytes"] == 276824064
    assert sixteen["totalBytes"] == 264 * MIB
    assert sixteen["footprintBytes"] == 53248

    candidates = row_candidates(shape[0], shape[1])
    costs = [traffic(operators, shape, tile) for tile in candidates]
    assert [tile[0] for tile in candidates] == [2**i for i in range(9)]
    totals = [cost["totalBytes"] for cost in costs]
    sizes = [cost["footprintBytes"] for cost in costs]
    assert totals == sorted(totals, reverse=True)
    assert sizes == sorted(sizes)

    best = search_tiles(operators, shape, candidates, 64 * 1024, top_k=3)
    assert [entry["outTile"] for entry in best] == [[16, 128], [8, 128],
                                                    [4, 128]]
    assert search_tiles(operators, shape, candidates, 1024, top_k=3) == []
    assert len(search_tiles(operators, shape, candidates, 10**9, top_k=2)) == 2

    for invalid, error in (((4, 64), "full row"), ((5, 128), "evenly")):
        try:
            traffic(operators, shape, invalid)
        except ValueError as problem:
            assert error in str(problem)
        else:
            raise AssertionError("Invalid tile was accepted")

    named, channels = conv_relu_maxpool(3, 8)
    chain = [operator for _, operator in named]
    tiles, sides = propagate_chain(chain, (1, 1, channels))
    assert tiles == [(4, 4, 3), (2, 2, 8), (2, 2, 8), (1, 1, 8)]
    assert sides == [(3, 3, 3, 8)]
    assert propagate_chain(chain, (2, 2, channels))[0][0] == (6, 6, 3)

    assert connected_groups(("register", "shared"), "register") == [[0, 1], [2]]
    assert connected_groups(("register", "shared"), "shared") == [[0, 1, 2]]
    assert connected_groups(("global", "global"), "shared") == [[0], [1], [2]]
    assert connected_groups(("global", "global"), "global") == [[0, 1, 2]]
    return {
        "shape": {"rows": shape[0], "k": 64, "cols": shape[1],
                  "bytesPerElement": FP32_BYTES},
        "candidates": [
            {"rows": tile[0], **cost} for tile, cost in zip(candidates, costs)
        ],
        "search": {"capacityBytes": 64 * 1024, "topK": 3, "ranked": best},
        "figure5": layer_plan(("register", "shared")),
        "allGlobal": layer_plan(("global", "global")),
    }


def main():
    """Print deterministic arithmetic after running correctness checks."""
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("--json", action="store_true")
    args = parser.parse_args()
    result = self_check()
    if args.json:
        print(json.dumps(result))
    else:
        print("Tile-graph checks passed: 35,840 B, 840 MiB and 264 MiB.")
        print(json.dumps(result, indent=2))


if __name__ == "__main__":
    main()
