Skip to content

Index

LogicFuseMerger

Bases: LoopOrderedForm, LogicLoader

Pass a program in LoopOrderedForm to ctx, after merging its sibling Fuse nodes, as merge_sibling_fuses does, wherever the merged program is still in LoopOrderedForm, whose Fuse nodes may only run statements together when running them for each value of the field in turn means the same.

Source code in src/finch/autoschedule/fuse_merger/fuse_merger.py
class LogicFuseMerger(LoopOrderedForm, LogicLoader):
    """
    Pass a program in LoopOrderedForm to ctx, after merging its sibling Fuse
    nodes, as merge_sibling_fuses does, wherever the merged program is still
    in LoopOrderedForm, whose Fuse nodes may only run statements together when
    running them for each value of the field in turn means the same.
    """

    def __init__(self, ctx: LogicLoader):
        self.ctx = ctx

    def lower(
        self,
        prgm: LogicStatement,
        bindings: dict[Alias, TensorFType],
        stats: dict[Alias, TensorStats],
        stats_factory: StatsFactory,
    ) -> tuple[AssemblyLibrary, dict[Alias, TensorFType]]:
        def legal(merged: LogicStatement) -> bool:
            assert isinstance(merged, Plan)
            try:
                LoopOrderedForm.validate_inputs(merged, bindings, stats, stats_factory)
            except ValueError:
                return False
            return True

        prgm = merge_sibling_fuses(prgm, legal)
        return self.ctx(prgm, bindings, stats, stats_factory)

merge_fuses(first, second)

A Fuse which runs the bodies of first and second, in order, for each value of the field of first, which renames the field of second, or None if their fields read different tensors or positions, or the field of first already occurs in second.

Source code in src/finch/autoschedule/fuse_merger/fuse_merger.py
def merge_fuses(first: Fuse, second: Fuse) -> Fuse | None:
    """
    A Fuse which runs the bodies of first and second, in order, for each value
    of the field of first, which renames the field of second, or None if
    their fields read different tensors or positions, or the field of first
    already occurs in second.
    """
    reads = field_reads(first)
    if not reads or field_reads(second) != reads:
        return None
    idx, other = first.idx, second.idx
    if idx != other and any(node == idx for node in PostOrderDFS(second.body)):
        return None
    body = Rewrite(PostWalk(lambda node: idx if node == other else None))(second.body)
    return Fuse(idx, Plan((*statements(first.body), *statements(body))))

merge_sibling_fuses(prgm, legal)

Merge Fuse nodes of the same Plan of prgm, which have the same enclosing Fuse nodes and whose fields read the same tensors in the same positions, one pair at a time, as long as legal accepts the merged program, until no pair merges. A merge runs the bodies of both for each value of one field, so a single pass over the tensors they read serves both. The pair needn't be adjacent, as sibling_merges moves the statements between them.

Source code in src/finch/autoschedule/fuse_merger/fuse_merger.py
def merge_sibling_fuses(
    prgm: LogicStatement, legal: Callable[[LogicStatement], bool]
) -> LogicStatement:
    """
    Merge Fuse nodes of the same Plan of prgm, which have the same enclosing
    Fuse nodes and whose fields read the same tensors in the same positions,
    one pair at a time, as long as legal accepts the merged program, until no
    pair merges. A merge runs the bodies of both for each value of one field,
    so a single pass over the tensors they read serves both. The pair needn't
    be adjacent, as sibling_merges moves the statements between them.
    """
    while True:
        for merged in sibling_merges(prgm):
            if legal(merged):
                prgm = merged
                break
        else:
            return prgm