Reintroduce shifts in SSA

[sirasistant]

Problem

SSA no longer has shifts, so any shift operation is polyfilled at the SSA level. However, brillig does support shifts, and the polyfill generates a huge amount of operations. This program:

unconstrained fn main(a: u64, b: u64) -> pub u64 {
    a >> b
}

Generates this SSA:

After Dead Instruction Elimination:
brillig fn main f0 {
  b0(v0: u32, v1: u32):
    v1189, v1190 = call to_le_bits(v1, Field 2⁵)
    v1191 = array_get v1190, index Field 31
    v1192 = not v1191
    v1193 = cast v1191 as Field
    v1194 = cast v1192 as Field
    v1195 = mul Field 2, v1193
    v1196 = add v1195, v1194
    v1197 = mul v1196, v1196
    v1198 = mul v1197, Field 2
    ... Repeated 30 more times
    v1469 = array_get v1190, index Field 0
    v1470 = not v1469
    v1471 = cast v1469 as Field
    v1472 = cast v1470 as Field
    v1473 = mul v1468, v1471
    v1474 = mul v1467, v1472
    v1475 = add v1473, v1474
    v1476 = div v0, v1475
    return v1476
}

This generates huge brillig programs for shifts that are natively supported by brillig.

Happy Case

We could reintroduce shifts in SSA, and polyfill them for ACIR functions in a step after inlining. After inlining all functions are colored (they'll only target their runtime) so we can convert any SSA level shift to the ACIR-compatible instructions and leave functions that target brillig unchanged.

Alternatives Considered

We could also implement shifts in acir_gen but that would miss on SSA-level optimizations.

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response