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 
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
70
71
72
73
74
75
76
77
78
79
80
81
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.
        """

    @abc.abstractmethod
    def update_liveness(self, ctx: LivenessContext) -> None:
        """
        Update `ctx.alive` from live-after to live-before 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 
28
29
30
31
32
33
34
35
@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 
37
38
39
40
41
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 
43
44
45
46
47
@abc.abstractmethod
def allocate_registers(self, allocator: BlockAllocator) -> None:
    """
    Allocate registers for this operation.
    """

update_liveness(ctx: LivenessContext) -> None abstractmethod

Update ctx.alive from live-after to live-before this operation.

Source code in xdsl/backend/register_allocatable.py 
49
50
51
52
53
@abc.abstractmethod
def update_liveness(self, ctx: LivenessContext) -> None:
    """
    Update `ctx.alive` from live-after to live-before 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 
55
56
57
58
59
60
61
62
63
64
65
66
67
@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 
69
70
71
72
73
74
75
76
77
78
79
80
81
@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 
84
85
86
87
88
89
90
91
92
93
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[OpResult]
    inouts: Sequence[tuple[SSAValue, OpResult]]

ins: Sequence[SSAValue] instance-attribute

outs: Sequence[OpResult] instance-attribute

inouts: Sequence[tuple[SSAValue, OpResult]] instance-attribute

HasRegisterConstraintsTrait dataclass

Bases: OpTrait

Trait that verifies that the operation implements HasRegisterConstraints, and that its constraints account for each operand and result as many times as it occurs. An operand is declared by ins or inouts, a result by outs or inouts. A value occupying several operands is declared once per operand, so an operation may read a value as an in register and also clobber it as an inout register.

Source code in xdsl/backend/register_allocatable.py 
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
class HasRegisterConstraintsTrait(OpTrait):
    """
    Trait that verifies that the operation implements HasRegisterConstraints, and that
    its constraints account for each operand and result as many times as it occurs.
    An operand is declared by `ins` or `inouts`, a result by `outs` or `inouts`. A value
    occupying several operands is declared once per operand, so an operation may read a
    value as an `in` register and also clobber it as an `inout` register.
    """

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

        declared_operands = Counter(ins)
        declared_results = Counter(outs)
        # A value cannot be both an operand and a result of the same operation, so
        # membership tells which side of the constraint each inout value belongs to.
        for operand, result in inouts:
            declared_operands[operand] += 1
            declared_results[result] += 1
        _verify_declared_once(
            op.name, "operand", op.operands, declared_operands, "`in` or `inout`"
        )
        _verify_declared_once(
            op.name, "result", op.results, declared_results, "`out` or `inout`"
        )

verify(op: Operation) -> None

Source code in xdsl/backend/register_allocatable.py 
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
def verify(self, op: Operation) -> None:
    if not isinstance(op, HasRegisterConstraints):
        raise VerifyException(
            f"Operation {op.name} is not a subclass of {HasRegisterConstraints.__name__}."
        )
    ins, outs, inouts = op.get_register_constraints()

    declared_operands = Counter(ins)
    declared_results = Counter(outs)
    # A value cannot be both an operand and a result of the same operation, so
    # membership tells which side of the constraint each inout value belongs to.
    for operand, result in inouts:
        declared_operands[operand] += 1
        declared_results[result] += 1
    _verify_declared_once(
        op.name, "operand", op.operands, declared_operands, "`in` or `inout`"
    )
    _verify_declared_once(
        op.name, "result", op.results, declared_results, "`out` or `inout`"
    )

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. see pass x86-regalloc-verify-liveness).

Source code in xdsl/backend/register_allocatable.py 
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
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. see pass x86-regalloc-verify-liveness).
    """

    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 update_liveness(self, ctx: LivenessContext) -> None:
        ins, _, inouts = self.get_register_constraints()
        clobbered: set[SSAValue] = set()
        for operand, _ in inouts:
            # Each inout slot needs its own register, so a value already claimed by an
            # earlier slot must be handled even when nothing reads it afterwards.
            use_after_inout = operand in ctx.alive
            duplicate_inout = operand in clobbered
            if use_after_inout or duplicate_inout:
                new_operand = ctx.handle_live_inout(
                    self, operand, duplicate_inout=duplicate_inout
                )
                # Replacing a position clears the value from it, so the first
                # position still holding it is the one for this slot.
                self.operands[self.operands.index(operand)] = new_operand
            clobbered.add(operand)
        # The constraints were read before any replacement, so a replaced operand is
        # still counted here, as it is read by the copy inserted above this operation.
        ctx.alive.update(ins, clobbered)

    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 
165
166
167
168
169
170
171
@abc.abstractmethod
def get_register_constraints(self) -> RegisterConstraints:
    """
    The values with register types used by this operation, for use in register
    allocation.
    """
    raise NotImplementedError()

update_liveness(ctx: LivenessContext) -> None

Source code in xdsl/backend/register_allocatable.py 
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
def update_liveness(self, ctx: LivenessContext) -> None:
    ins, _, inouts = self.get_register_constraints()
    clobbered: set[SSAValue] = set()
    for operand, _ in inouts:
        # Each inout slot needs its own register, so a value already claimed by an
        # earlier slot must be handled even when nothing reads it afterwards.
        use_after_inout = operand in ctx.alive
        duplicate_inout = operand in clobbered
        if use_after_inout or duplicate_inout:
            new_operand = ctx.handle_live_inout(
                self, operand, duplicate_inout=duplicate_inout
            )
            # Replacing a position clears the value from it, so the first
            # position still holding it is the one for this slot.
            self.operands[self.operands.index(operand)] = new_operand
        clobbered.add(operand)
    # The constraints were read before any replacement, so a replaced operand is
    # still counted here, as it is read by the copy inserted above this operation.
    ctx.alive.update(ins, clobbered)

allocate_registers(allocator: BlockAllocator) -> None

Source code in xdsl/backend/register_allocatable.py 
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
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)