MLIR

Multi-Level IR Compiler Framework

'polynomial' Dialect

The Polynomial dialect defines single-variable polynomial types and operations.

The simplest use of polynomial is to represent mathematical operations in a polynomial ring R[x], where R is another MLIR type like i32.

More generally, this dialect supports representing polynomial operations in a quotient ring R[X]/(f(x)) for some statically fixed polynomial f(x). Two polyomials p(x), q(x) are considered equal in this ring if they have the same remainder when dividing by f(x). When a modulus is given, ring operations are performed with reductions modulo f(x) and relative to the coefficient ring R.

Examples:

// A constant polynomial in a ring with i32 coefficients and no polynomial modulus
#ring = #polynomial.ring<coefficientType=i32>
%a = polynomial.constant <1 + x**2 - 3x**3> : polynomial.polynomial<#ring>

// A constant polynomial in a ring with i32 coefficients, modulo (x^1024 + 1)
#modulus = #polynomial.int_polynomial<1 + x**1024>
#ring = #polynomial.ring<coefficientType=i32, polynomialModulus=#modulus>
%a = polynomial.constant <1 + x**2 - 3x**3> : polynomial.polynomial<#ring>

// A constant polynomial in a ring with i32 coefficients, with a polynomial
// modulus of (x^1024 + 1) and a coefficient modulus of 17.
#modulus = #polynomial.int_polynomial<1 + x**1024>
#ring = #polynomial.ring<coefficientType=i32, coefficientModulus=17:i32, polynomialModulus=#modulus>
%a = polynomial.constant <1 + x**2 - 3x**3> : polynomial.polynomial<#ring>


Operations ¶

source

polynomial.add (polynomial::AddOp) ¶

Addition operation between polynomials.

Syntax:

operation ::= polynomial.add operands attr-dict : type($result)  Performs polynomial addition on the operands. The operands may be single polynomials or containers of identically-typed polynomials, i.e., polynomials from the same underlying ring with the same coefficient types. Addition is defined to occur in the ring defined by the ring attribute of the two operands, meaning the addition is taken modulo the coefficientModulus and the polynomialModulus of the ring. Example: // add two polynomials modulo x^1024 - 1 #poly = #polynomial.int_polynomial<x**1024 - 1> #ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly> %0 = polynomial.constant int<1 + x**2> : !polynomial.polynomial<#ring> %1 = polynomial.constant int<x**5 - x + 1> : !polynomial.polynomial<#ring> %2 = polynomial.add %0, %1 : !polynomial.polynomial<#ring>  Traits: AlwaysSpeculatableImplTrait, Commutative, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface) Effects: MemoryEffects::Effect{} Operands: ¶ OperandDescription lhspolynomial-like rhspolynomial-like Results: ¶ ResultDescription resultpolynomial-like polynomial.constant (polynomial::ConstantOp) ¶ Define a constant polynomial via an attribute. Example: !int_poly_ty = !polynomial.polynomial<ring=<coefficientType=i32>> %0 = polynomial.constant int<1 + x**2> : !int_poly_ty !float_poly_ty = !polynomial.polynomial<ring=<coefficientType=f32>> %1 = polynomial.constant float<0.5 + 1.3e06 x**2> : !float_poly_ty  Traits: AlwaysSpeculatableImplTrait, InferTypeOpAdaptor Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface) Effects: MemoryEffects::Effect{} Attributes: ¶ AttributeMLIR TypeDescription value::mlir::Attributea typed float_polynomial or a typed int_polynomial Results: ¶ ResultDescription outputAn element of a polynomial ring. polynomial.from_tensor (polynomial::FromTensorOp) ¶ Creates a polynomial from integer coefficients stored in a tensor. Syntax: operation ::= polynomial.from_tensor$input attr-dict : type($input) -> type($output)


polynomial.from_tensor creates a polynomial value from a tensor of coefficients. The input tensor must list the coefficients in degree-increasing order.

The input one-dimensional tensor may have size at most the degree of the ring’s polynomialModulus generator polynomial, with smaller dimension implying that all higher-degree terms have coefficient zero.

Example:

#poly = #polynomial.int_polynomial<x**1024 - 1>
#ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly>
%two = arith.constant 2 : i32
%five = arith.constant 5 : i32
%coeffs = tensor.from_elements %two, %two, %five : tensor<3xi32>
%poly = polynomial.from_tensor %coeffs : tensor<3xi32> -> !polynomial.polynomial<#ring>


Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands: ¶

OperandDescription
inputranked tensor of integer values

Results: ¶

ResultDescription
outputAn element of a polynomial ring.

polynomial.intt (polynomial::INTTOp) ¶

Computes the reverse integer Number Theoretic Transform (NTT).

Syntax:

operation ::= polynomial.intt $input attr-dict : qualified(type($input)) -> type($output)  polynomial.intt computes the reverse integer Number Theoretic Transform (INTT) on the input tensor. This is the inverse operation of the polynomial.ntt operation. The input tensor is interpreted as a point-value representation of the output polynomial at powers of a primitive n-th root of unity (see polynomial.ntt). The ring of the polynomial is taken from the required encoding attribute of the tensor. The choice of primitive root may be optionally specified. Traits: AlwaysSpeculatableImplTrait Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface) Effects: MemoryEffects::Effect{} Attributes: ¶ AttributeMLIR TypeDescription root::mlir::polynomial::PrimitiveRootAttr an attribute containing an integer and its degree as a root of unity A primitive root attribute stores an integer root value and an integer degree, corresponding to a primitive root of unity of the given degree in an unspecified ring. This is used as an attribute on polynomial.ntt and polynomial.intt ops to specify the root of unity used in lowering the transform. Example: #poly = #polynomial.primitive_root&lt;value=123 : i32, degree : 7 index&gt;  Operands: ¶ OperandDescription inputranked tensor of integer values Results: ¶ ResultDescription outputAn element of a polynomial ring. polynomial.leading_term (polynomial::LeadingTermOp) ¶ Compute the leading term of the polynomial. Syntax: operation ::= polynomial.leading_term operands attr-dict : type($input) -> ( type($degree) , type($coefficient) )


The degree of a polynomial is the largest $k$ for which the coefficient a_k of x^k is nonzero. The leading term is the term a_k * x^k, which this op represents as a pair of results. The first is the degree k as an index, and the second is the coefficient, whose type matches the coefficient type of the polynomial’s ring attribute.

Example:

#poly = #polynomial.int_polynomial<x**1024 - 1>
#ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly>
%0 = polynomial.constant int<1 + x**2> : !polynomial.polynomial<#ring>
%1, %2 = polynomial.leading_term %0 : !polynomial.polynomial<#ring> -> (index, i32)


Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands: ¶

OperandDescription
inputAn element of a polynomial ring.

Results: ¶

ResultDescription
degreeindex
coefficientinteger

polynomial.monic_monomial_mul (polynomial::MonicMonomialMulOp) ¶

Multiply a polynomial by a monic monomial.

Syntax:

operation ::= polynomial.monic_monomial_mul operands attr-dict : functional-type(operands, results)


Multiply a polynomial by a monic monomial, meaning a polynomial of the form 1 * x^k for an index operand k.

In some special rings of polynomials, such as a ring of polynomials modulo x^n - 1, monomial_mul can be interpreted as a cyclic shift of the coefficients of the polynomial. For some rings, this results in optimized lowerings that involve rotations and rescaling of the coefficients of the input.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands: ¶

OperandDescription
inputpolynomial-like
monomialDegreeindex

Results: ¶

ResultDescription
outputpolynomial-like

polynomial.monomial (polynomial::MonomialOp) ¶

Create a polynomial that consists of a single monomial.

Syntax:

operation ::= polynomial.monomial operands attr-dict : functional-type(operands, results)


Construct a polynomial that consists of a single monomial term, from its degree and coefficient as dynamic inputs.

The coefficient type of the output polynomial’s ring attribute must match the coefficient input type.

Example:

#poly = #polynomial.int_polynomial<x**1024 - 1>
#ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly>
%deg = arith.constant 1023 : index
%five = arith.constant 5 : i32
%0 = polynomial.monomial %five, %deg : (i32, index) -> !polynomial.polynomial<#ring>


Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands: ¶

OperandDescription
coefficientinteger
degreeindex

Results: ¶

ResultDescription
outputAn element of a polynomial ring.

polynomial.mul (polynomial::MulOp) ¶

Multiplication operation between polynomials.

Syntax:

operation ::= polynomial.mul operands attr-dict : type($result)  Performs polynomial multiplication on the operands. The operands may be single polynomials or containers of identically-typed polynomials, i.e., polynomials from the same underlying ring with the same coefficient types. Multiplication is defined to occur in the ring defined by the ring attribute of the two operands, meaning the multiplication is taken modulo the coefficientModulus and the polynomialModulus of the ring. Example: // multiply two polynomials modulo x^1024 - 1 #poly = #polynomial.int_polynomial<x**1024 - 1> #ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly> %0 = polynomial.constant int<1 + x**2> : !polynomial.polynomial<#ring> %1 = polynomial.constant int<x**5 - x + 1> : !polynomial.polynomial<#ring> %2 = polynomial.mul %0, %1 : !polynomial.polynomial<#ring>  Traits: AlwaysSpeculatableImplTrait, Commutative, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface) Effects: MemoryEffects::Effect{} Operands: ¶ OperandDescription lhspolynomial-like rhspolynomial-like Results: ¶ ResultDescription resultpolynomial-like polynomial.mul_scalar (polynomial::MulScalarOp) ¶ Multiplication by a scalar of the field. Syntax: operation ::= polynomial.mul_scalar operands attr-dict : type($polynomial) , type($scalar)  Multiplies the polynomial operand’s coefficients by a given scalar value. The operation is defined to occur in the ring defined by the ring attribute of the two operands, meaning the multiplication is taken modulo the coefficientModulus of the ring. The scalar input must have the same type as the polynomial ring’s coefficientType. Example: // multiply two polynomials modulo x^1024 - 1 #poly = #polynomial.int_polynomial<x**1024 - 1> #ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly> %0 = polynomial.constant int<1 + x**2> : !polynomial.polynomial<#ring> %1 = arith.constant 3 : i32 %2 = polynomial.mul_scalar %0, %1 : !polynomial.polynomial<#ring>, i32  Traits: AlwaysSpeculatableImplTrait, Elementwise, Scalarizable, Tensorizable, Vectorizable Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface) Effects: MemoryEffects::Effect{} Operands: ¶ OperandDescription polynomialpolynomial-like scalarinteger Results: ¶ ResultDescription outputpolynomial-like polynomial.ntt (polynomial::NTTOp) ¶ Computes point-value tensor representation of a polynomial. Syntax: operation ::= polynomial.ntt$input attr-dict : qualified(type($input)) -> type($output)


polynomial.ntt computes the forward integer Number Theoretic Transform (NTT) on the input polynomial. It returns a tensor containing a point-value representation of the input polynomial. The output tensor has shape equal to the degree of the ring’s polynomialModulus. The polynomial’s RingAttr is embedded as the encoding attribute of the output tensor.

Given an input polynomial F(x) over a ring whose polynomialModulus has degree n, and a primitive n-th root of unity omega_n, the output is the list of $n$ evaluations

f[k] = F(omega[n]^k) ; k = {0, ..., n-1}

The choice of primitive root may be optionally specified.

Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Attributes: ¶

AttributeMLIR TypeDescription
root::mlir::polynomial::PrimitiveRootAttr
an attribute containing an integer and its degree as a root of unity
A primitive root attribute stores an integer root value and an integer
degree, corresponding to a primitive root of unity of the given degree in
an unspecified ring.
This is used as an attribute on polynomial.ntt and polynomial.intt ops
to specify the root of unity used in lowering the transform.
Example:
#poly = #polynomial.primitive_root&lt;value=123 : i32, degree : 7 index&gt;


Operands: ¶

OperandDescription
inputAn element of a polynomial ring.

Results: ¶

ResultDescription
outputranked tensor of integer values

polynomial.sub (polynomial::SubOp) ¶

Subtraction operation between polynomials.

Syntax:

operation ::= polynomial.sub operands attr-dict : type($result)  Performs polynomial subtraction on the operands. The operands may be single polynomials or containers of identically-typed polynomials, i.e., polynomials from the same underlying ring with the same coefficient types. Subtraction is defined to occur in the ring defined by the ring attribute of the two operands, meaning the subtraction is taken modulo the coefficientModulus and the polynomialModulus of the ring. Example: // subtract two polynomials modulo x^1024 - 1 #poly = #polynomial.int_polynomial<x**1024 - 1> #ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly> %0 = polynomial.constant int<1 + x**2> : !polynomial.polynomial<#ring> %1 = polynomial.constant int<x**5 - x + 1> : !polynomial.polynomial<#ring> %2 = polynomial.sub %0, %1 : !polynomial.polynomial<#ring>  Traits: AlwaysSpeculatableImplTrait, Elementwise, SameOperandsAndResultType, Scalarizable, Tensorizable, Vectorizable Interfaces: ConditionallySpeculatable, InferTypeOpInterface, NoMemoryEffect (MemoryEffectOpInterface) Effects: MemoryEffects::Effect{} Operands: ¶ OperandDescription lhspolynomial-like rhspolynomial-like Results: ¶ ResultDescription resultpolynomial-like polynomial.to_tensor (polynomial::ToTensorOp) ¶ Creates a tensor containing the coefficients of a polynomial. Syntax: operation ::= polynomial.to_tensor$input attr-dict : type($input) -> type($output)


polynomial.to_tensor creates a dense tensor value containing the coefficients of the input polynomial. The output tensor contains the coefficients in degree-increasing order.

Operations that act on the coefficients of a polynomial, such as extracting a specific coefficient or extracting a range of coefficients, should be implemented by composing to_tensor with the relevant tensor dialect ops.

The output tensor has shape equal to the degree of the polynomial ring attribute’s polynomialModulus, including zeroes.

Example:

#poly = #polynomial.int_polynomial<x**1024 - 1>
#ring = #polynomial.ring<coefficientType=i32, coefficientModulus=65536:i32, polynomialModulus=#poly>
%two = arith.constant 2 : i32
%five = arith.constant 5 : i32
%coeffs = tensor.from_elements %two, %two, %five : tensor<3xi32>
%poly = polynomial.from_tensor %coeffs : tensor<3xi32> -> !polynomial.polynomial<#ring>
%tensor = polynomial.to_tensor %poly : !polynomial.polynomial<#ring> -> tensor<1024xi32>


Traits: AlwaysSpeculatableImplTrait

Interfaces: ConditionallySpeculatable, NoMemoryEffect (MemoryEffectOpInterface)

Effects: MemoryEffects::Effect{}

Operands: ¶

OperandDescription
inputAn element of a polynomial ring.

Results: ¶

ResultDescription
outputranked tensor of integer values

Attributes ¶

FloatPolynomialAttr ¶

an attribute containing a single-variable polynomial with double precision floating point coefficients

A polynomial attribute represents a single-variable polynomial with double precision floating point coefficients.

The polynomial must be expressed as a list of monomial terms, with addition or subtraction between them. The choice of variable name is arbitrary, but must be consistent across all the monomials used to define a single attribute. The order of monomial terms is arbitrary, each monomial degree must occur at most once.

Example:

#poly = #polynomial.float_polynomial<0.5 x**7 + 1.5>


Parameters: ¶

ParameterC++ typeDescription
polynomialFloatPolynomial

IntPolynomialAttr ¶

an attribute containing a single-variable polynomial with integer coefficients

A polynomial attribute represents a single-variable polynomial with integer coefficients, which is used to define the modulus of a RingAttr, as well as to define constants and perform constant folding for polynomial ops.

The polynomial must be expressed as a list of monomial terms, with addition or subtraction between them. The choice of variable name is arbitrary, but must be consistent across all the monomials used to define a single attribute. The order of monomial terms is arbitrary, each monomial degree must occur at most once.

Example:

#poly = #polynomial.int_polynomial<x**1024 + 1>


Parameters: ¶

ParameterC++ typeDescription
polynomial::mlir::polynomial::IntPolynomial

PrimitiveRootAttr ¶

an attribute containing an integer and its degree as a root of unity

Syntax:

#polynomial.primitive_root<
::mlir::IntegerAttr,   # value
::mlir::IntegerAttr   # degree
>


A primitive root attribute stores an integer root value and an integer degree, corresponding to a primitive root of unity of the given degree in an unspecified ring.

This is used as an attribute on polynomial.ntt and polynomial.intt ops to specify the root of unity used in lowering the transform.

Example:

#poly = #polynomial.primitive_root<value=123 : i32, degree : 7 index>


Parameters: ¶

ParameterC++ typeDescription
value::mlir::IntegerAttr
degree::mlir::IntegerAttr

RingAttr ¶

an attribute specifying a polynomial ring

Syntax:

#polynomial.ring<
Type,   # coefficientType
::mlir::IntegerAttr,   # coefficientModulus
::mlir::polynomial::IntPolynomialAttr   # polynomialModulus
>


A ring describes the domain in which polynomial arithmetic occurs. The ring attribute in polynomial represents the more specific case of polynomials with a single indeterminate; whose coefficients can be represented by another MLIR type (coefficientType); and, if the coefficient type is integral, whose coefficients are taken modulo some statically known modulus (coefficientModulus).

Additionally, a polynomial ring can specify a polynomialModulus, which converts polynomial arithmetic to the analogue of modular integer arithmetic, where each polynomial is represented as its remainder when dividing by the modulus. For single-variable polynomials, an “polynomialModulus” is always specificed via a single polynomial, which we call polynomialModulus.

An expressive example is polynomials with i32 coefficients, whose coefficients are taken modulo 2**32 - 5, with a polynomial modulus of x**1024 - 1.

#poly_mod = #polynomial.int_polynomial<-1 + x**1024>
#ring = #polynomial.ring<coefficientType=i32,
coefficientModulus=4294967291:i32,
polynomialModulus=#poly_mod>

%0 = ... : polynomial.polynomial<#ring>


In this case, the value of a polynomial is always “converted” to a canonical form by applying repeated reductions by setting x**1024 = 1 and simplifying.

The coefficient and polynomial modulus parameters are optional, and the coefficient modulus is only allowed if the coefficient type is integral.

Parameters: ¶

ParameterC++ typeDescription
coefficientTypeType
coefficientModulus::mlir::IntegerAttr
polynomialModulus::mlir::polynomial::IntPolynomialAttr

TypedFloatPolynomialAttr ¶

a typed float_polynomial

Syntax:

#polynomial.typed_float_polynomial<
::mlir::Type,   # type
::mlir::polynomial::FloatPolynomialAttr   # value
>


Example:

!poly_ty = !polynomial.polynomial<ring=<coefficientType=f32>>
#poly = float<1.4 x**7 + 4.5> : !poly_ty
#poly_verbose = #polynomial.typed_float_polynomial<1.4 x**7 + 4.5> : !poly_ty


Parameters: ¶

ParameterC++ typeDescription
type::mlir::Type
value::mlir::polynomial::FloatPolynomialAttr

TypedIntPolynomialAttr ¶

a typed int_polynomial

Syntax:

#polynomial.typed_int_polynomial<
::mlir::Type,   # type
::mlir::polynomial::IntPolynomialAttr   # value
>


Example:

!poly_ty = !polynomial.polynomial<ring=<coefficientType=i32>>
#poly = int<1 x**7 + 4> : !poly_ty
#poly_verbose = #polynomial.typed_int_polynomial<1 x**7 + 4> : !poly_ty


Parameters: ¶

ParameterC++ typeDescription
type::mlir::Type
value::mlir::polynomial::IntPolynomialAttr

Types ¶

PolynomialType ¶

An element of a polynomial ring.

Syntax:

!polynomial.polynomial<
::mlir::polynomial::RingAttr   # ring
>


A type for polynomials in a polynomial quotient ring.

Parameters: ¶

ParameterC++ typeDescription
ring::mlir::polynomial::RingAttran attribute specifying a polynomial ring