Skip to content

Polynomial

polynomial

A polynomial dialect for representing unevaluated polynomial approximations, designed for use with equality saturation.

Cost estimation can be done on a single polynomial.eval op that carries all the information needed. After extraction, the selected polynomial variant will be expanded into arithmetic operations.

HEIR Documentation

Polynomial = Dialect('polynomial', [EvalOp], [ChebyshevPolynomialAttr, TypedChebyshevPolynomialAttr, RingAttr, PolynomialType]) module-attribute

EvalScheme

Bases: StrEnum

Evaluation scheme used to lower a polynomial.eval op to arithmetic ops.

Stored on the op as a builtin string attribute so that compilers like HEIR that don't know about this xDSL extension can preserve it on round-trip (the same way they ignore domain_lower/domain_upper).

Source code in xdsl/dialects/polynomial.py 
54
55
56
57
58
59
60
61
62
63
class EvalScheme(StrEnum):
    """
    Evaluation scheme used to lower a `polynomial.eval` op to arithmetic ops.

    Stored on the op as a builtin string attribute so that compilers like HEIR
    that don't know about this xDSL extension can preserve it on round-trip
    (the same way they ignore `domain_lower`/`domain_upper`).
    """

    CLENSHAW = "clenshaw"

CLENSHAW = 'clenshaw' class-attribute instance-attribute

RingAttr dataclass

Bases: ParametrizedAttribute

A polynomial ring, parameterized by the coefficient type.

Syntax: #polynomial.ring

Source code in xdsl/dialects/polynomial.py 
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
@irdl_attr_definition
class RingAttr(ParametrizedAttribute):
    """
    A polynomial ring, parameterized by the coefficient type.

    Syntax: #polynomial.ring<coefficientType=f64>
    """

    name = "polynomial.ring"

    coefficient_type: Attribute

    @classmethod
    def parse_parameters(cls, parser: AttrParser) -> Sequence[Attribute]:
        with parser.in_angle_brackets():
            parser.parse_keyword("coefficientType")
            parser.parse_punctuation("=")
            coeff_type = parser.parse_type()
        return (coeff_type,)

    def print_parameters(self, printer: Printer) -> None:
        printer.print_string("<coefficientType = ")
        printer.print_attribute(self.coefficient_type)
        printer.print_string(">")

name = 'polynomial.ring' class-attribute instance-attribute

coefficient_type: Attribute instance-attribute

parse_parameters(parser: AttrParser) -> Sequence[Attribute] classmethod

Source code in xdsl/dialects/polynomial.py 
78
79
80
81
82
83
84
@classmethod
def parse_parameters(cls, parser: AttrParser) -> Sequence[Attribute]:
    with parser.in_angle_brackets():
        parser.parse_keyword("coefficientType")
        parser.parse_punctuation("=")
        coeff_type = parser.parse_type()
    return (coeff_type,)

print_parameters(printer: Printer) -> None

Source code in xdsl/dialects/polynomial.py 
86
87
88
89
def print_parameters(self, printer: Printer) -> None:
    printer.print_string("<coefficientType = ")
    printer.print_attribute(self.coefficient_type)
    printer.print_string(">")

PolynomialType dataclass

Bases: ParametrizedAttribute, TypeAttribute

Type of an element of a polynomial ring.

Syntax: !polynomial.polynomial>

Source code in xdsl/dialects/polynomial.py 
 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
122
123
124
@irdl_attr_definition
class PolynomialType(ParametrizedAttribute, TypeAttribute):
    """
    Type of an element of a polynomial ring.

    Syntax: !polynomial.polynomial<ring=<coefficientType=f64>>
    """

    name = "polynomial.polynomial"

    ring: RingAttr

    @classmethod
    def parse_parameters(cls, parser: AttrParser) -> Sequence[Attribute]:
        with parser.in_angle_brackets():
            parser.parse_keyword("ring")
            parser.parse_punctuation("=")
            # Accept either inline form `<coefficientType=...>` or
            # attribute reference like `#alias` / `#polynomial.ring<...>`.
            # HEIR's printer often hoists ring attributes into top-level
            # aliases, so both need to be handled on round-trip.
            ring = parser.parse_optional_attribute()
            if ring is None:
                ring_params = RingAttr.parse_parameters(parser)
                ring = RingAttr.new(ring_params)
            elif not isinstance(ring, RingAttr):
                parser.raise_error(f"expected RingAttr in polynomial type, got {ring}")
        return (ring,)

    def print_parameters(self, printer: Printer) -> None:
        printer.print_string("<ring = ")
        self.ring.print_parameters(printer)
        printer.print_string(">")

name = 'polynomial.polynomial' class-attribute instance-attribute

ring: RingAttr instance-attribute

parse_parameters(parser: AttrParser) -> Sequence[Attribute] classmethod

Source code in xdsl/dialects/polynomial.py 
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
@classmethod
def parse_parameters(cls, parser: AttrParser) -> Sequence[Attribute]:
    with parser.in_angle_brackets():
        parser.parse_keyword("ring")
        parser.parse_punctuation("=")
        # Accept either inline form `<coefficientType=...>` or
        # attribute reference like `#alias` / `#polynomial.ring<...>`.
        # HEIR's printer often hoists ring attributes into top-level
        # aliases, so both need to be handled on round-trip.
        ring = parser.parse_optional_attribute()
        if ring is None:
            ring_params = RingAttr.parse_parameters(parser)
            ring = RingAttr.new(ring_params)
        elif not isinstance(ring, RingAttr):
            parser.raise_error(f"expected RingAttr in polynomial type, got {ring}")
    return (ring,)

print_parameters(printer: Printer) -> None

Source code in xdsl/dialects/polynomial.py 
121
122
123
124
def print_parameters(self, printer: Printer) -> None:
    printer.print_string("<ring = ")
    self.ring.print_parameters(printer)
    printer.print_string(">")

ChebyshevPolynomialAttr

Bases: ParametrizedAttribute

Untyped Chebyshev polynomial with double precision floating point coefficients.

For use directly inside polynomial.eval, prefer TypedChebyshevPolynomialAttr, which carries an explicit polynomial type and matches HEIR's polynomial.eval op signature.

Syntax: #polynomial.chebyshev_polynomial<[coefficients]> Example: #polynomial.chebyshev_polynomial<[0.5 : f64, 1.2 : f64, 0.3 : f64]>

Source code in xdsl/dialects/polynomial.py 
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
153
154
155
156
157
158
159
160
161
162
163
@irdl_attr_definition
class ChebyshevPolynomialAttr(ParametrizedAttribute):
    """
    Untyped Chebyshev polynomial with double precision floating point coefficients.

    For use directly inside `polynomial.eval`, prefer `TypedChebyshevPolynomialAttr`,
    which carries an explicit polynomial type and matches HEIR's `polynomial.eval`
    op signature.

    Syntax: #polynomial.chebyshev_polynomial<[coefficients]>
    Example:
        #polynomial.chebyshev_polynomial<[0.5 : f64, 1.2 : f64, 0.3 : f64]>
    """

    name = "polynomial.chebyshev_polynomial"

    coefficients: ArrayAttr[FloatAttr]

    def __init__(
        self,
        coefficients: tuple[float, ...] | ArrayAttr[FloatAttr],
    ):
        if isinstance(coefficients, ArrayAttr):
            arr = coefficients
        else:
            arr = ArrayAttr([FloatAttr(c, f64) for c in coefficients])
        super().__init__(arr)

    @property
    def degree(self) -> int:
        """Polynomial degree (number of coefficients minus one)."""
        return len(self.coefficients) - 1

    @property
    def coeff_values(self) -> tuple[float, ...]:
        """Extract coefficient values as Python floats."""
        return tuple(c.value.data for c in self.coefficients)

name = 'polynomial.chebyshev_polynomial' class-attribute instance-attribute

coefficients: ArrayAttr[FloatAttr] instance-attribute

degree: int property

Polynomial degree (number of coefficients minus one).

coeff_values: tuple[float, ...] property

Extract coefficient values as Python floats.

__init__(coefficients: tuple[float, ...] | ArrayAttr[FloatAttr])

Source code in xdsl/dialects/polynomial.py 
145
146
147
148
149
150
151
152
153
def __init__(
    self,
    coefficients: tuple[float, ...] | ArrayAttr[FloatAttr],
):
    if isinstance(coefficients, ArrayAttr):
        arr = coefficients
    else:
        arr = ArrayAttr([FloatAttr(c, f64) for c in coefficients])
    super().__init__(arr)

TypedChebyshevPolynomialAttr

Bases: ParametrizedAttribute

Chebyshev polynomial with an explicit polynomial type.

Syntax: #polynomial.typed_chebyshev_polynomial<[coefficients]> : !polynomial.polynomial<...> Example: #polynomial.typed_chebyshev_polynomial<[1.0, 2.0]> : !polynomial.polynomial>

Source code in xdsl/dialects/polynomial.py 
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
@irdl_attr_definition
class TypedChebyshevPolynomialAttr(ParametrizedAttribute):
    """
    Chebyshev polynomial with an explicit polynomial type.

    Syntax: #polynomial.typed_chebyshev_polynomial<[coefficients]> : !polynomial.polynomial<...>
    Example:
        #polynomial.typed_chebyshev_polynomial<[1.0, 2.0]> :
            !polynomial.polynomial<ring=<coefficientType=f64>>
    """

    name = "polynomial.typed_chebyshev_polynomial"

    type: Attribute
    value: ChebyshevPolynomialAttr

    def __init__(
        self,
        type: Attribute,
        value: ChebyshevPolynomialAttr | tuple[float, ...],
    ):
        if not isinstance(value, ChebyshevPolynomialAttr):
            value = ChebyshevPolynomialAttr(value)
        super().__init__(type, value)

    @classmethod
    def parse_parameters(cls, parser: AttrParser) -> Sequence[Attribute]:
        with parser.in_angle_brackets():
            coeffs = parser.parse_attribute()
        parser.parse_punctuation(":")
        poly_type = parser.parse_type()
        value = ChebyshevPolynomialAttr.new((coeffs,))
        return (poly_type, value)

    def print_parameters(self, printer: Printer) -> None:
        printer.print_string("<")
        printer.print_attribute(self.value.coefficients)
        printer.print_string("> : ")
        printer.print_attribute(self.type)

    @property
    def degree(self) -> int:
        return self.value.degree

    @property
    def coeff_values(self) -> tuple[float, ...]:
        return self.value.coeff_values

name = 'polynomial.typed_chebyshev_polynomial' class-attribute instance-attribute

type: Attribute instance-attribute

value: ChebyshevPolynomialAttr instance-attribute

degree: int property

coeff_values: tuple[float, ...] property

__init__(type: Attribute, value: ChebyshevPolynomialAttr | tuple[float, ...])

Source code in xdsl/dialects/polynomial.py 
182
183
184
185
186
187
188
189
def __init__(
    self,
    type: Attribute,
    value: ChebyshevPolynomialAttr | tuple[float, ...],
):
    if not isinstance(value, ChebyshevPolynomialAttr):
        value = ChebyshevPolynomialAttr(value)
    super().__init__(type, value)

parse_parameters(parser: AttrParser) -> Sequence[Attribute] classmethod

Source code in xdsl/dialects/polynomial.py 
191
192
193
194
195
196
197
198
@classmethod
def parse_parameters(cls, parser: AttrParser) -> Sequence[Attribute]:
    with parser.in_angle_brackets():
        coeffs = parser.parse_attribute()
    parser.parse_punctuation(":")
    poly_type = parser.parse_type()
    value = ChebyshevPolynomialAttr.new((coeffs,))
    return (poly_type, value)

print_parameters(printer: Printer) -> None

Source code in xdsl/dialects/polynomial.py 
200
201
202
203
204
def print_parameters(self, printer: Printer) -> None:
    printer.print_string("<")
    printer.print_attribute(self.value.coefficients)
    printer.print_string("> : ")
    printer.print_attribute(self.type)

EvalOp

Bases: IRDLOperation

Evaluate a polynomial at a given point.

This op is unevaluated but carries all information needed for later lowering to arithmetic ops, dispatched on scheme.

Syntax: polynomial.eval $polynomial , $value attr-dict : type($value) Example: %result = polynomial.eval #polynomial.typed_chebyshev_polynomial<[0.5, 1.2]> : !polynomial.polynomial>, %x {scheme = "clenshaw", domain_lower = -1.0 : f64, domain_upper = 1.0 : f64} : f32

Source code in xdsl/dialects/polynomial.py 
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
@irdl_op_definition
class EvalOp(IRDLOperation):
    """
    Evaluate a polynomial at a given point.

    This op is *unevaluated* but carries all information needed for
    later lowering to arithmetic ops, dispatched on `scheme`.

    Syntax: polynomial.eval $polynomial `,` $value attr-dict `:` type($value)
    Example:
        %result = polynomial.eval
            #polynomial.typed_chebyshev_polynomial<[0.5, 1.2]> :
                !polynomial.polynomial<ring=<coefficientType=f64>>,
            %x {scheme = "clenshaw",
                domain_lower = -1.0 : f64, domain_upper = 1.0 : f64}
            : f32
    """

    name = "polynomial.eval"

    T: ClassVar = VarConstraint("T", ContainerOf(AnyFloatConstr))

    value = operand_def(T)
    result = result_def(T)

    polynomial = prop_def(TypedChebyshevPolynomialAttr)

    scheme = attr_def(StringAttr)
    domain_lower = opt_attr_def(FloatAttr)
    domain_upper = opt_attr_def(FloatAttr)

    traits = traits_def(Pure(), SameOperandsAndResultType())

    # `qualified(...)` forces the full `#polynomial.typed_chebyshev_polynomial<...>`
    # form when printing/parsing, instead of the elided `<...>` form. This is
    # required for HEIR round-trip: HEIR's parser only accepts the qualified form.
    assembly_format = "qualified($polynomial) `,` $value attr-dict `:` type($value)"

    def __init__(
        self,
        value: SSAValue,
        polynomial: TypedChebyshevPolynomialAttr,
        scheme: StringAttr,
        domain_lower: FloatAttr | None = None,
        domain_upper: FloatAttr | None = None,
    ):
        attrs = {
            "scheme": scheme,
            "domain_lower": domain_lower,
            "domain_upper": domain_upper,
        }

        super().__init__(
            operands=[value],
            result_types=[value.type],
            properties={
                "polynomial": polynomial,
            },
            attributes=attrs,
        )

    @classmethod
    def get(
        cls,
        value: Operation | SSAValue,
        coefficients: tuple[float, ...],
        element_type: AnyFloat,
        scheme: EvalScheme | str,
        domain_lower: float | None = None,
        domain_upper: float | None = None,
    ) -> EvalOp:
        """
        Build an `EvalOp` from raw Python floats.

        `element_type` is the floating-point type used for the polynomial
        coefficients, the ring's coefficient type, and the domain bounds.
        """
        value = SSAValue.get(value)

        coeff_attrs = ArrayAttr([FloatAttr(c, element_type) for c in coefficients])
        polynomial = TypedChebyshevPolynomialAttr(
            PolynomialType(RingAttr(element_type)),
            ChebyshevPolynomialAttr(coeff_attrs),
        )

        scheme_attr = StringAttr(
            scheme.value if isinstance(scheme, EvalScheme) else scheme
        )
        lower_attr = (
            FloatAttr(domain_lower, element_type) if domain_lower is not None else None
        )
        upper_attr = (
            FloatAttr(domain_upper, element_type) if domain_upper is not None else None
        )
        return cls(value, polynomial, scheme_attr, lower_attr, upper_attr)

    def verify_(self) -> None:
        if self.domain_lower is not None and self.domain_upper is not None:
            lower = self.domain_lower.value.data
            upper = self.domain_upper.value.data
            if lower >= upper:
                raise VerifyException(
                    f"domain_lower ({lower}) must be strictly "
                    f"less than domain_upper ({upper})"
                )
        if self.polynomial.degree < 1:
            raise VerifyException(
                "Chebyshev polynomial must have at least degree 1 "
                f"(got {self.polynomial.degree + 1} coefficients)"
            )
        try:
            EvalScheme(self.scheme.data)
        except ValueError:
            valid = ", ".join(repr(s.value) for s in EvalScheme)
            raise VerifyException(
                f"unknown evaluation scheme {self.scheme.data!r}; "
                f"expected one of: {valid}"
            )

    @property
    def degree(self) -> int:
        return self.polynomial.degree

    @property
    def eval_scheme(self) -> EvalScheme:
        """Return the scheme as an EvalScheme enum."""
        return EvalScheme(self.scheme.data)

name = 'polynomial.eval' class-attribute instance-attribute

T: ClassVar = VarConstraint('T', ContainerOf(AnyFloatConstr)) class-attribute instance-attribute

value = operand_def(T) class-attribute instance-attribute

result = result_def(T) class-attribute instance-attribute

polynomial = prop_def(TypedChebyshevPolynomialAttr) class-attribute instance-attribute

scheme = attr_def(StringAttr) class-attribute instance-attribute

domain_lower = opt_attr_def(FloatAttr) class-attribute instance-attribute

domain_upper = opt_attr_def(FloatAttr) class-attribute instance-attribute

traits = traits_def(Pure(), SameOperandsAndResultType()) class-attribute instance-attribute

assembly_format = 'qualified($polynomial) `,` $value attr-dict `:` type($value)' class-attribute instance-attribute

degree: int property

eval_scheme: EvalScheme property

Return the scheme as an EvalScheme enum.

__init__(value: SSAValue, polynomial: TypedChebyshevPolynomialAttr, scheme: StringAttr, domain_lower: FloatAttr | None = None, domain_upper: FloatAttr | None = None)

Source code in xdsl/dialects/polynomial.py 
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
def __init__(
    self,
    value: SSAValue,
    polynomial: TypedChebyshevPolynomialAttr,
    scheme: StringAttr,
    domain_lower: FloatAttr | None = None,
    domain_upper: FloatAttr | None = None,
):
    attrs = {
        "scheme": scheme,
        "domain_lower": domain_lower,
        "domain_upper": domain_upper,
    }

    super().__init__(
        operands=[value],
        result_types=[value.type],
        properties={
            "polynomial": polynomial,
        },
        attributes=attrs,
    )

get(value: Operation | SSAValue, coefficients: tuple[float, ...], element_type: AnyFloat, scheme: EvalScheme | str, domain_lower: float | None = None, domain_upper: float | None = None) -> EvalOp classmethod

Build an EvalOp from raw Python floats.

element_type is the floating-point type used for the polynomial coefficients, the ring's coefficient type, and the domain bounds.

Source code in xdsl/dialects/polynomial.py 
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
@classmethod
def get(
    cls,
    value: Operation | SSAValue,
    coefficients: tuple[float, ...],
    element_type: AnyFloat,
    scheme: EvalScheme | str,
    domain_lower: float | None = None,
    domain_upper: float | None = None,
) -> EvalOp:
    """
    Build an `EvalOp` from raw Python floats.

    `element_type` is the floating-point type used for the polynomial
    coefficients, the ring's coefficient type, and the domain bounds.
    """
    value = SSAValue.get(value)

    coeff_attrs = ArrayAttr([FloatAttr(c, element_type) for c in coefficients])
    polynomial = TypedChebyshevPolynomialAttr(
        PolynomialType(RingAttr(element_type)),
        ChebyshevPolynomialAttr(coeff_attrs),
    )

    scheme_attr = StringAttr(
        scheme.value if isinstance(scheme, EvalScheme) else scheme
    )
    lower_attr = (
        FloatAttr(domain_lower, element_type) if domain_lower is not None else None
    )
    upper_attr = (
        FloatAttr(domain_upper, element_type) if domain_upper is not None else None
    )
    return cls(value, polynomial, scheme_attr, lower_attr, upper_attr)

verify_() -> None

Source code in xdsl/dialects/polynomial.py 
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
def verify_(self) -> None:
    if self.domain_lower is not None and self.domain_upper is not None:
        lower = self.domain_lower.value.data
        upper = self.domain_upper.value.data
        if lower >= upper:
            raise VerifyException(
                f"domain_lower ({lower}) must be strictly "
                f"less than domain_upper ({upper})"
            )
    if self.polynomial.degree < 1:
        raise VerifyException(
            "Chebyshev polynomial must have at least degree 1 "
            f"(got {self.polynomial.degree + 1} coefficients)"
        )
    try:
        EvalScheme(self.scheme.data)
    except ValueError:
        valid = ", ".join(repr(s.value) for s in EvalScheme)
        raise VerifyException(
            f"unknown evaluation scheme {self.scheme.data!r}; "
            f"expected one of: {valid}"
        )