Scheme Selection passes

[kragall]

I am currently working on a scheme selection process intended for non-expert users, enabling them to choose the most suitable FHE scheme for their task, i.e. their mlir file. The code is located at https://github.com/Fraunhofer-AISEC/heir/tree/scheme_selection. At present, I am annotating the func operation with counters for different types of computation, i.e. operations on reals, integers, etc. In a subsequent pass, I plan to use this information to select an appropriate FHE scheme for each func and annotate the module with the best scheme based on a majority vote.

I have the feeling that scheme selection is a slightly easier version of the scheme switching problem discussed in issue #300. The cost model needed for scheme selection is likely very similar to that required for scheme switching. I'd like to try to implement a more sophisticated cost model for the selection process, which could also be applied to scheme switching.

Any insights or feedback on this approach would be appreciated.

[AlexanderViand]

Could you open a (draft) PR for your branch? That way, it's a bit easier to see the changes/new code :)

The main question I have is at what abstraction level you're analyzing the IR. For example, I'd assume one of the main deciders in practice will be the presence of non-polynomial operations (e.g., comparisons, etc), which would require looking at the high-level input IR before arithmetization. However, then the analysis would need an understanding of what it'd cost to lower those operations using a given scheme, which seems like it (a straightforward solution at laest) would need to duplicate (and be kept in sync with) the existing arithmetization lowering patterns (e.g., the recently introduced polynomial approximation pipeline).

[kragall]

My current approach is relatively simple and would probably best be called directly after the data-oblivious transformations. Assigning a cost to an operation is the tricky part. As you mentioned, for an accurate estimation of the cost it would probably be best to have some sort of synchronization with the lowering patterns.

For the first draft, I planned to simply assign some cost to the different types of operations that are counted. I wanted to create a lattice populated with the information from all FuncOps in a module. But the visitOperation of the second analysis seems to get called for FuncOps.