# 2024-08-12 FHE compiler next steps

## Polygeist

### 8/16 bit arithmetic

Modify the compiler so that all arithmetic operations happen at the lowest common denominator instead of always being raised to 32 bit arithmetic.

## HEIR

### Attributes removal

Write a pass to remove `func.func` attributes. Then we can avoid this hack:

cat main.mlir | sed 's/attributes {[^}]*}//g' > main-noattrs.mlir

### Remove unused functions

After inlining we still have the functions around. Write a pass that removes all function except for the circuit entrypoint. Then we can avoid this hack:

sed -nE "/^  func.func @${func}/,/^  }$/p" main-inline.mlir > main-inline-clean.mlir

### Translate llvm.struct to memref array

In some cases when structs are used Ploygeist emits MLIR like this:

%alloca = memref.alloca() : memref<1x!llvm.struct<(i32, array<8 x i32>, array<64 x i8>, i8)>>

HEIR is not happy about the `!`.

### Missing arith.rem_i to Verilog

Missing `RemUIOp` in:
- https://github.com/google/heir/blob/5d265644599b9303d258a951d89c6f434ed6d6a5/lib/Target/Verilog/VerilogEmitter.cpp#L212
- missing `printOperation` for `RemUIOp`

Veronica made a fix that works, next steps are upstreaming the patch.

### Parallelism

The tfhe-bool Rust transpiler currently doesn't support parallelism.
I personally find the Rust code generation a bit ugly and fragile, and I have a better proposal.

Create a new dialect "logic" for logic circuits. This dialect supports a single type encrypted bool, and the following operations:
- 1/2 input gates (NOT, OR, AND, XOR, NAND, XNOR)
- N input lookup tables

This dialect will be used to represent logic circuits. Then we implement a single translate transpilation that takes:
- A single function `func.func` with:
- `memref` loads at the beginning
- `memref` stores at the end
- `logic` operations in the middle
And returns the circuit in JSON format already layered by levels.

This is agnostic to any particular FHE boolean library. Then we can easily write code that consumes this JSON circuit and evaluates it under FHE (we can even mix ciphertext and plaintext and let the library dynamically handle each case). Since the circuit description is already layered by levels, it's easy to evaluate gates in parallel.

Example:

{
inputs: [1, 2, 3, 4, 5],
outputs: [9, 10],
circuit: [
    [["AND", 6, 1, 2], ["AND", 7, 3, 4], ["NAND", 8, 1, 5]],
    [["OR", 9, 6, 7], ["AND", 10, 3, 8]] 
],
prunning: [
    ["TODO: nodes that become orphan after level i"]
]
}

Example with lookups:

{
inputs: [1, 2, 3, 4, 5],
outputs: [9, 10],
circuit: [
    [["AND", 6, 1, 2], ["AND", 7, 3, 4], ["NAND", 8, 1, 5]],
    [["OR", 9, 6, 7], ["AND", 10, 3, 8]] 
],
prunning: [
    ["TODO: nodes that become orphan after level i"]
]
tables: {
    "AND": [0, 0, 0, 1],
    "NAND": [1, 1, 1, 0],
    "OR": [0, 1, 1, 1]
    "GATE3": [1, 0, 0, 1, 0, 1, 1, 1]
    // AutoHog requires defining how the inputs are prepared for each lookup table
    // a + 2b + 4c + 8d => 12
    // a + 2(b + c + d) => 9
}
}

GATE3
| x | y | z | res |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 1 |