Two years ago I proposed a polynomial dialect, and then upstreamed an initial version of it. It has been relatively silent since then, and I have been considering removing the upstream dialect to avoid the extra maintenance burden.
I have actually been developing out-of-tree passes that do useful things with polynomial:
- A polynomial approximation solver.
- Patterns to convert math and certain arith ops to use polynomial approximations.
- Lowerings for polynomial.eval that minimize multiplicative ops (e.g., with repeated squaring and Paterson-Stockmeyer-style tricks where mul is more expensive than add)
- Lowerings for NTT/iNTT to arith/affine/etc (though those require our additional mod_arith dialect)
IMO, the most interesting thing is the approximation solver, and if that cannot be upstreamed then the rest of the polynomial dialect is somewhat weak.
I could upstream the solver, but the simplest implementation we found requires an FFT and an eigenvalue solver. (The more complicated ones require root finders and linear system solvers, and have numerical stability issues.) My sense is that LLVM is not interested in taking on additional dependencies, but out of tree we did this using the PocketFFT and eigen projects, respectively, which are well-established tools for these tasks (PocketFFT is used by numpy for its FFT routine, for example). The alternative is to reimplement the routines needed from these two projects upstream, which would be difficult.
Because there has not been much discussion about the polynomial dialect since adding it, it seems there is no demand to make a case for adding or reimplementing these dependencies.
So I am looking for feedback from the community. If there are no objections, I will remove the polynomial dialect and move its development entirely out-of-tree. If there are people who still want to use it, but haven’t yet because some of these tools we built out-of-tree are needed, I can reconsider the options.