Inline results from brillig function calls for which all arguments are known during SSA

[TomAFrench]

We currently execution any brillig function calls for which all arguments are known during ACIR gen at compile-time in order to optimize the generated circuit by replacing the call with its intended results.

Performing this optimization during ACIR-gen however means that this occurs after most of our optimization passes have already run (and so they cannot benefit from the removal of these brillig calls). In SSA we retain the brillig calls which completely block any constant propagation from occurring.

An example of this is shown in the SSA below where the program should be able to be optimized down to an empty program in SSA but because we have some brillig calls we're unable to propagate these results forwards.

After Array Set Optimizations:
acir(inline) fn main f0 {
  b0():
    v8, v9 = call f4([Field 1225638183666705271503180972154335964, Field 1149176344733214219505367673588801074, Field 28650], [Field 12, Field 0, Field 0])
    v33, v34, v35 = call f6(u1 0, [Field 0, Field 0, Field 2¹⁶], [u64 0, u64 0, u64 0, u64 0, u64 2¹⁶, u64 0], [u64 0, u64 0, u64 0, u64 0, u64 2¹⁶, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0], [Field 2¹²⁰, Field 1329227995784915872903807060280344575, Field 131071], [Field 0, Field 0, Field 2²²], [[v8]], [[u1 0]], [[[Field 12, Field 0, Field 0]]], [[u1 0]], [[Field 1225638183666705271503180972154335964, Field 1149176344733214219505367673588801074, Field 28650], v9], [u1 1, u1 0])
    v37 = array_get v33, index u32 0
    range_check v37 to 120 bits
    v39 = array_get v33, index u32 1
    range_check v39 to 120 bits
    v41 = array_get v33, index u32 2
    range_check v41 to 120 bits
    range_check v41 to 23 bits
    v42 = array_get v8, index u32 0
    v43 = array_get v8, index u32 1
    v44 = array_get v8, index u32 2
    v45 = array_get v9, index u32 0
    v47 = add Field 103589812118210601400626088126008612, v45
    v48 = array_get v9, index u32 1
    v50 = add Field 180051651051701653398439386691543501, v48
    v51 = array_get v9, index u32 2
 // snip

We can address this by

• Create a copy of the brillig function being called
• Replace all function arguments with the constants the function is being called with.
• Run the optimization passes until the function is reduced to its terminator instruction
• Inline these results in place of the brillig call instruction.

There will be a couple of gotchas related to failing assertions or oracle calls which will need to be handled with some care. As a first cut we can just abort this process if we hit these cases for now.

We started touching on this work with #5839

[TomAFrench]

One thought on this (can also be done in a follow up). If we're partially solving a brillig function call then we need to consider whether we have other calls to the same function. We'll want to avoid blowing up the amounts of bytecode we have for unconstrained functions.

[asterite]

If we're partially solving a brillig function call then we need to consider whether we have other calls to the same function. We'll want to avoid blowing up the amounts of bytecode we have for unconstrained functions.

Sorry, I couldn't understand this.

[TomAFrench]

Essentially, imagine we have a brillig function foo(x: Field) which does a lot of computation and then has a foreign call. If we have a single call to foo in the program which we know the inputs for, then we can perform a lot of constant folding up to the foreign call instruction to avoid having to do this at runtime. The brillig bytecode for that function call is then modified to be specific to those constant arguments and is smaller, all very nice.

If we have 100 calls to foo in the program which all have inputs which are constant but different then we could end up with 100 different sets of brillig bytecode in the final program artifact. While we've cut out some computation this has come at the expense of having a lot of duplicated bytecode in the final artifact.