Polynomial evaluation IR

[j2kun]

As part of the broader polynomial approximation system, we would like to materialize polynomial approximations in the IR.

We should create a polynomial.eval op, which takes as input a static polynomial attribute and an SSA value (AnyType), and semantically this represents the evaluation of the polynomial at the input.

Then we would implement possible lowerings of eval to a sequence of add/mul ops in an appropriate dialect (see below). One lowering would be a Horner's method, while another would correspond to Paterson-Stockmeyer. We'd expect the latter to be more efficient for FHE due to the imbalance in add/mul costs.

We should start by implementing this for integer/float types, with the lowering lower to addi/mui/add/mulf. Ideally we could generalize this to an interface, so that the interface would decide what is the "right" add/mul op to use for a given type. Maybe the interface would be in charge of actually constructing the op in question.

[j2kun]

Note that polynomial.eval is checked in, and a first pass at polynomial patterns to generate polynomial.eval ops is #1449

After that is in, the remaining work required is to:

• Add more patterns for special neural network activation functions like ReLU ops, or any more complex patterns that coincide with activation functions we might see (like matching on arith.maximumf 0, %x and similar)
• Implement the lowering of polynomial.eval using Paterson-Stockmeyer.

I recall @eymay was planning to work on the second bullet. Do you have any updates on that front? We are hoping to include this before a paper submission deadline on April 15, so if you're not able to work on it, one of our other collaborators may take it over.

[j2kun]

Ah, perhaps it was actually @zmbekdemir who was going to work on Paterson-Stockmeyer?

[zmbekdemir]

@j2kun yes, I am working on it.

[j2kun]

@j2kun yes, I am working on it.

Would you be so kind as to post a draft PR with your partial work? We are happy to look at it and provide advice.

[zmbekdemir]

@j2kun yes, I am working on it.

Would you be so kind as to post a draft PR with your partial work? We are happy to look at it and provide advice.

I will tidy things up and then I can post a draft PR, it shouldn't really take much time, just a couple days at max.