Skip to content

Liveness analysis

liveness_analysis

Liveness analysis: a sparse backward dataflow analysis that, for every SSA value, determines whether it is "live".

A value is considered "live" iff it:

(1) has memory effects, OR (2) is returned by a public function, OR (3) is used to compute a value of type (1) or (2), OR (4) is returned by a return-like op whose parent isn't a callable nor a RegionBranchOpInterface (e.g. linalg.yield, gpu.yield, ...). Such ops have op-specific semantics, so we conservatively mark the yielded value live.

Note: support for branch operands, call operands, and non-control-flow region arguments are not yet implemented. They should be added together with the corresponding op interfaces (BranchOpInterface, CallOpInterface, RegionBranchOpInterface).

Liveness

Bases: PropagatingLattice

Boolean liveness lattice attached to an SSA value.

Starts pessimistic (is_live = False) and only ever moves towards True. The lattice ordering is dead ⊑ live; meet is OR — a value is live if either side says so.

Source code in xdsl/analysis/liveness_analysis.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Liveness(PropagatingLattice):
    """
    Boolean liveness lattice attached to an SSA value.

    Starts pessimistic (`is_live = False`) and only ever moves towards `True`.
    The lattice ordering is `dead ⊑ live`; `meet` is OR — a value is live if
    either side says so.
    """

    is_live: bool

    def __init__(self, anchor: SSAValue):
        super().__init__(anchor)
        self.is_live = False

    def mark_live(self) -> ChangeResult:
        if self.is_live:
            return ChangeResult.NO_CHANGE
        self.is_live = True
        return ChangeResult.CHANGE

    def mark_dead(self) -> ChangeResult:
        if not self.is_live:
            return ChangeResult.NO_CHANGE
        self.is_live = False
        return ChangeResult.CHANGE

    def meet(self, other: Liveness) -> ChangeResult:
        if other.is_live:
            return self.mark_live()
        return ChangeResult.NO_CHANGE

    def join(self, other: Liveness) -> ChangeResult:
        if not other.is_live:
            return self.mark_dead()
        return ChangeResult.NO_CHANGE

    def __str__(self) -> str:
        return "live" if self.is_live else "dead"

is_live: bool = False instance-attribute

__init__(anchor: SSAValue)

Source code in xdsl/analysis/liveness_analysis.py 
43
44
45
def __init__(self, anchor: SSAValue):
    super().__init__(anchor)
    self.is_live = False

mark_live() -> ChangeResult

Source code in xdsl/analysis/liveness_analysis.py 
47
48
49
50
51
def mark_live(self) -> ChangeResult:
    if self.is_live:
        return ChangeResult.NO_CHANGE
    self.is_live = True
    return ChangeResult.CHANGE

mark_dead() -> ChangeResult

Source code in xdsl/analysis/liveness_analysis.py 
53
54
55
56
57
def mark_dead(self) -> ChangeResult:
    if not self.is_live:
        return ChangeResult.NO_CHANGE
    self.is_live = False
    return ChangeResult.CHANGE

meet(other: Liveness) -> ChangeResult

Source code in xdsl/analysis/liveness_analysis.py 
59
60
61
62
def meet(self, other: Liveness) -> ChangeResult:
    if other.is_live:
        return self.mark_live()
    return ChangeResult.NO_CHANGE

join(other: Liveness) -> ChangeResult

Source code in xdsl/analysis/liveness_analysis.py 
64
65
66
67
def join(self, other: Liveness) -> ChangeResult:
    if not other.is_live:
        return self.mark_dead()
    return ChangeResult.NO_CHANGE

__str__() -> str

Source code in xdsl/analysis/liveness_analysis.py 
69
70
def __str__(self) -> str:
    return "live" if self.is_live else "dead"

LivenessAnalysis

Bases: SparseBackwardDataFlowAnalysis[Liveness]

Backward sparse dataflow analysis annotating each SSA value with whether it is live.

Source code in xdsl/analysis/liveness_analysis.py 
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
class LivenessAnalysis(SparseBackwardDataFlowAnalysis[Liveness]):
    """
    Backward sparse dataflow analysis annotating each SSA value with whether it
    is live.
    """

    def __init__(self, solver: DataFlowSolver):
        super().__init__(solver, Liveness)

    def visit_operation_impl(
        self,
        op: Operation,
        operand_lattices: list[Liveness],
        result_lattices: list[Liveness],
    ) -> None:
        # (1.a)/(4) If the op is not trivially dead (has side effects, is a
        # terminator, is a symbol op, ...), every operand is live.
        if not would_be_trivially_dead(op):
            for operand in operand_lattices:
                self.propagate_if_changed(operand, operand.mark_live())

        # (3) If any result is live, every operand is live. The assumption
        # — matching MLIR — is that every operand can contribute to every
        # result, so a single live result suffices to mark all operands live.
        for result in result_lattices:
            if result.is_live:
                for operand in operand_lattices:
                    self.meet(operand, result)
                break

    def set_to_exit_state(self, lattice: Liveness) -> None:
        """
        Called for lattices that reach a backward-propagation boundary
        (e.g. operands of a public-function return). Marks them live (2).
        """
        if lattice.is_live:
            return
        lattice.is_live = True
        self.propagate_if_changed(lattice, ChangeResult.CHANGE)

__init__(solver: DataFlowSolver)

Source code in xdsl/analysis/liveness_analysis.py 
79
80
def __init__(self, solver: DataFlowSolver):
    super().__init__(solver, Liveness)

visit_operation_impl(op: Operation, operand_lattices: list[Liveness], result_lattices: list[Liveness]) -> None

Source code in xdsl/analysis/liveness_analysis.py 
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
def visit_operation_impl(
    self,
    op: Operation,
    operand_lattices: list[Liveness],
    result_lattices: list[Liveness],
) -> None:
    # (1.a)/(4) If the op is not trivially dead (has side effects, is a
    # terminator, is a symbol op, ...), every operand is live.
    if not would_be_trivially_dead(op):
        for operand in operand_lattices:
            self.propagate_if_changed(operand, operand.mark_live())

    # (3) If any result is live, every operand is live. The assumption
    # — matching MLIR — is that every operand can contribute to every
    # result, so a single live result suffices to mark all operands live.
    for result in result_lattices:
        if result.is_live:
            for operand in operand_lattices:
                self.meet(operand, result)
            break

set_to_exit_state(lattice: Liveness) -> None

Called for lattices that reach a backward-propagation boundary (e.g. operands of a public-function return). Marks them live (2).

Source code in xdsl/analysis/liveness_analysis.py 
103
104
105
106
107
108
109
110
111
def set_to_exit_state(self, lattice: Liveness) -> None:
    """
    Called for lattices that reach a backward-propagation boundary
    (e.g. operands of a public-function return). Marks them live (2).
    """
    if lattice.is_live:
        return
    lattice.is_live = True
    self.propagate_if_changed(lattice, ChangeResult.CHANGE)