Skip to content

Register allocatable

register_allocatable

RegisterAllocatableOperation dataclass

Bases: Operation, ABC

An abstract base class for operations that can be processed during register allocation.

Source code in xdsl/backend/register_allocatable.py 
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
class RegisterAllocatableOperation(Operation, abc.ABC):
    """
    An abstract base class for operations that can be processed during register
    allocation.
    """

    @deprecated("Use register effects instead")
    def iter_used_registers(self) -> Iterator[RegisterType]:
        """
        The registers whose contents may be overwritten when executing this operation.
        By default returns the types of operands and results that are allocated
        registers.
        """
        yield from ()

    def iter_excluded_registers(self) -> Iterator[RegisterType]:
        """
        The registers that should not be used when this operation is present.
        """
        yield from ()

    @abc.abstractmethod
    def allocate_registers(self, allocator: BlockAllocator) -> None:
        """
        Allocate registers for this operation.
        """

    @staticmethod
    def all_used_registers(
        region: Region,
    ) -> AbstractSet[RegisterType]:
        """
        All used registers of all operations within a region.
        """
        return {
            reg
            for op in region.walk()
            if isinstance(op, RegisterAllocatableOperation)
            for reg in RegisterAllocatedMemoryEffect.iter_used_registers(op)
        }

    @staticmethod
    def all_excluded_registers(
        region: Region,
    ) -> AbstractSet[RegisterType]:
        """
        All excluded registers as declared by all operations within a region.
        """
        return {
            reg
            for op in region.walk()
            if isinstance(op, RegisterAllocatableOperation)
            for reg in op.iter_excluded_registers()
        }

iter_used_registers() -> Iterator[RegisterType]

The registers whose contents may be overwritten when executing this operation. By default returns the types of operands and results that are allocated registers.

Source code in xdsl/backend/register_allocatable.py 
22
23
24
25
26
27
28
29
@deprecated("Use register effects instead")
def iter_used_registers(self) -> Iterator[RegisterType]:
    """
    The registers whose contents may be overwritten when executing this operation.
    By default returns the types of operands and results that are allocated
    registers.
    """
    yield from ()

iter_excluded_registers() -> Iterator[RegisterType]

The registers that should not be used when this operation is present.

Source code in xdsl/backend/register_allocatable.py 
31
32
33
34
35
def iter_excluded_registers(self) -> Iterator[RegisterType]:
    """
    The registers that should not be used when this operation is present.
    """
    yield from ()

allocate_registers(allocator: BlockAllocator) -> None abstractmethod

Allocate registers for this operation.

Source code in xdsl/backend/register_allocatable.py 
37
38
39
40
41
@abc.abstractmethod
def allocate_registers(self, allocator: BlockAllocator) -> None:
    """
    Allocate registers for this operation.
    """

all_used_registers(region: Region) -> AbstractSet[RegisterType] staticmethod

All used registers of all operations within a region.

Source code in xdsl/backend/register_allocatable.py 
43
44
45
46
47
48
49
50
51
52
53
54
55
@staticmethod
def all_used_registers(
    region: Region,
) -> AbstractSet[RegisterType]:
    """
    All used registers of all operations within a region.
    """
    return {
        reg
        for op in region.walk()
        if isinstance(op, RegisterAllocatableOperation)
        for reg in RegisterAllocatedMemoryEffect.iter_used_registers(op)
    }

all_excluded_registers(region: Region) -> AbstractSet[RegisterType] staticmethod

All excluded registers as declared by all operations within a region.

Source code in xdsl/backend/register_allocatable.py 
57
58
59
60
61
62
63
64
65
66
67
68
69
@staticmethod
def all_excluded_registers(
    region: Region,
) -> AbstractSet[RegisterType]:
    """
    All excluded registers as declared by all operations within a region.
    """
    return {
        reg
        for op in region.walk()
        if isinstance(op, RegisterAllocatableOperation)
        for reg in op.iter_excluded_registers()
    }

RegisterConstraints

Bases: NamedTuple

Values used by an instruction. A collection of operations in inouts represents the constraint that they must be allocated to the same register.

Source code in xdsl/backend/register_allocatable.py 
72
73
74
75
76
77
78
79
80
81
class RegisterConstraints(NamedTuple):
    """
    Values used by an instruction.
    A collection of operations in `inouts` represents the constraint that they must be
    allocated to the same register.
    """

    ins: Sequence[SSAValue]
    outs: Sequence[SSAValue]
    inouts: Sequence[Sequence[SSAValue]]

ins: Sequence[SSAValue] instance-attribute

outs: Sequence[SSAValue] instance-attribute

inouts: Sequence[Sequence[SSAValue]] instance-attribute

HasRegisterConstraintsTrait dataclass

Bases: OpTrait

Trait that verifies that the operation implements HasRegisterConstraints, and that its inout operands are used only once. Using an inout operand more than once breaks SSA, as the register will hold an unexpected value after being mutated by this operation.

Source code in xdsl/backend/register_allocatable.py 
84
85
86
87
88
89
90
91
92
93
94
95
96
class HasRegisterConstraintsTrait(OpTrait):
    """
    Trait that verifies that the operation implements HasRegisterConstraints, and that
    its inout operands are used only once.
    Using an inout operand more than once breaks SSA, as the register will hold an
    unexpected value after being mutated by this operation.
    """

    def verify(self, op: Operation) -> None:
        if not isinstance(op, HasRegisterConstraints):
            raise VerifyException(
                f"Operation {op.name} is not a subclass of {HasRegisterConstraints.__name__}."
            )

verify(op: Operation) -> None

Source code in xdsl/backend/register_allocatable.py 
92
93
94
95
96
def verify(self, op: Operation) -> None:
    if not isinstance(op, HasRegisterConstraints):
        raise VerifyException(
            f"Operation {op.name} is not a subclass of {HasRegisterConstraints.__name__}."
        )

HasRegisterConstraints dataclass

Bases: RegisterAllocatableOperation, ABC

Abstract superclass for operations corresponding to assembly, with registers used as in, out, or inout registers. The use of a register value as inout must be its last use (externally verified, e.g. for x86 see pass verify-register-allocation).

Source code in xdsl/backend/register_allocatable.py 
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
class HasRegisterConstraints(RegisterAllocatableOperation, abc.ABC):
    """
    Abstract superclass for operations corresponding to assembly, with registers used
    as in, out, or inout registers.
    The use of a register value as inout must be its last use (externally verified,
    e.g. for x86 see pass verify-register-allocation).
    """

    traits = traits_def(HasRegisterConstraintsTrait())

    @abc.abstractmethod
    def get_register_constraints(self) -> RegisterConstraints:
        """
        The values with register types used by this operation, for use in register
        allocation.
        """
        raise NotImplementedError()

    def allocate_registers(self, allocator: BlockAllocator) -> None:
        ins, outs, inouts = self.get_register_constraints()

        # Allocate registers to inout operand groups since they are defined further up
        # in the use-def SSA chain
        for operand_group in inouts:
            allocator.allocate_values_same_reg(operand_group)

        new_outs: list[SSAValue] = []
        for result in outs:
            # Allocate registers to result if not already allocated
            if (new_result := allocator.allocate_value(result)) is not None:
                result = new_result
            new_outs.append(result)

        # reverse new_outs to have more optimal allocation in trivial pmov case
        # if all registers are unallocated, this is optimal allocation for pmov
        for result in reversed(new_outs):
            allocator.free_value(result)

        # Allocate registers to operands since they are defined further up
        # in the use-def SSA chain
        for operand in ins:
            allocator.allocate_value(operand)

traits = traits_def(HasRegisterConstraintsTrait()) class-attribute instance-attribute

get_register_constraints() -> RegisterConstraints abstractmethod

The values with register types used by this operation, for use in register allocation.

Source code in xdsl/backend/register_allocatable.py 
109
110
111
112
113
114
115
@abc.abstractmethod
def get_register_constraints(self) -> RegisterConstraints:
    """
    The values with register types used by this operation, for use in register
    allocation.
    """
    raise NotImplementedError()

allocate_registers(allocator: BlockAllocator) -> None

Source code in xdsl/backend/register_allocatable.py 
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
def allocate_registers(self, allocator: BlockAllocator) -> None:
    ins, outs, inouts = self.get_register_constraints()

    # Allocate registers to inout operand groups since they are defined further up
    # in the use-def SSA chain
    for operand_group in inouts:
        allocator.allocate_values_same_reg(operand_group)

    new_outs: list[SSAValue] = []
    for result in outs:
        # Allocate registers to result if not already allocated
        if (new_result := allocator.allocate_value(result)) is not None:
            result = new_result
        new_outs.append(result)

    # reverse new_outs to have more optimal allocation in trivial pmov case
    # if all registers are unallocated, this is optimal allocation for pmov
    for result in reversed(new_outs):
        allocator.free_value(result)

    # Allocate registers to operands since they are defined further up
    # in the use-def SSA chain
    for operand in ins:
        allocator.allocate_value(operand)