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 
13
14
15
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
class RegisterAllocatableOperation(Operation, abc.ABC):
    """
    An abstract base class for operations that can be processed during register
    allocation.
    """

    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.
        """
        return (
            val.type
            for vals in (self.operands, self.results)
            for val in vals
            if isinstance(val.type, RegisterType) and val.type.is_allocated
        )

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

    @staticmethod
    def iter_all_used_registers(
        region: Region,
    ) -> Iterator[RegisterType]:
        """
        All used registers of all operations within a region.
        """
        return (
            reg
            for op in region.walk()
            if isinstance(op, RegisterAllocatableOperation)
            for reg in op.iter_used_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 
19
20
21
22
23
24
25
26
27
28
29
30
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.
    """
    return (
        val.type
        for vals in (self.operands, self.results)
        for val in vals
        if isinstance(val.type, RegisterType) and val.type.is_allocated
    )

allocate_registers(allocator: BlockAllocator) -> None abstractmethod

Allocate registers for this operation.

Source code in xdsl/backend/register_allocatable.py 
32
33
34
35
36
@abc.abstractmethod
def allocate_registers(self, allocator: BlockAllocator) -> None:
    """
    Allocate registers for this operation.
    """

iter_all_used_registers(region: Region) -> Iterator[RegisterType] staticmethod

All used registers of all operations within a region.

Source code in xdsl/backend/register_allocatable.py 
38
39
40
41
42
43
44
45
46
47
48
49
50
@staticmethod
def iter_all_used_registers(
    region: Region,
) -> Iterator[RegisterType]:
    """
    All used registers of all operations within a region.
    """
    return (
        reg
        for op in region.walk()
        if isinstance(op, RegisterAllocatableOperation)
        for reg in op.iter_used_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 
53
54
55
56
57
58
59
60
61
62
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 
65
66
67
68
69
70
71
72
73
74
75
76
77
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 
73
74
75
76
77
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 
 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
112
113
114
115
116
117
118
119
120
121
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 
90
91
92
93
94
95
96
@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 
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
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)