feat(acir_gen): Width aware ACIR gen addition

[vezenovm]

Description

Problem*

Resolves #4629

Summary*

This PR updates how we add vars in ACIR gen to account for an expression width. This is under a compile time flag --bounded-codegen.

If the sum of two expressions is going to go over the specified expression width we automatically create witnesses for either the lhs, the rhs, or both, before then generating a sum expression.

This new bounded codegen could provide an easy way for developers to tell whether their program can be optimized using as_witness. Reference the additional context section below for some numbers.

Additional Context

There are some limitations in this approach as it is pretty naive in how it decides to when to generate a new witness. It doesn't look ahead at all other than for whether the two AcirVar's being added are going to create an expression over the specified ACIR width.

For example we can see the following gate counts for poseidonsponge_x5_254:

No width awareness:
+-----------------------+----------+----------------------+--------------+
| Package               | Function | Expression Width     | ACIR Opcodes |
+-----------------------+----------+----------------------+--------------+
| poseidonsponge_x5_254 | main     | Bounded { width: 4 } | 3096         |
+-----------------------+----------+----------------------+--------------+

No width awareness w/ as_witness (this is the currently optimized poseidon we have in the stdlib):
+-----------------------+----------+----------------------+--------------+
| Package               | Function | Expression Width     | ACIR Opcodes |
+-----------------------+----------+----------------------+--------------+
| poseidonsponge_x5_254 | main     | Bounded { width: 4 } | 1302         |
+-----------------------+----------+----------------------+--------------+

Width awareness:
+-----------------------+----------+----------------------+--------------+
| Package               | Function | Expression Width     | ACIR Opcodes |
+-----------------------+----------+----------------------+--------------+
| poseidonsponge_x5_254 | main     | Bounded { width: 4 } | 2114         |
+-----------------------+----------+----------------------+--------------+

Width awareness w/ as_witness:
+-----------------------+----------+----------------------+--------------+
| Package               | Function | Expression Width     | ACIR Opcodes |
+-----------------------+----------+----------------------+--------------+
| poseidonsponge_x5_254 | main     | Bounded { width: 4 } | 1792         |
+-----------------------+----------+----------------------+--------------+

From the above we can see that we actually have a degradation when using the addition strategy used in this PR with a hand optimized program using as_witness. Although this PR still gives an improvement in the default.

Another example is the following program:

fn main(x: Field, y: pub Field) {
    let state = [x, y];
    let state = oh_no_not_again(state);

    // This assert will fail if we execute
    assert(state[0] + state[1] == 0);
}

fn oh_no_not_again(mut state: [Field; 2]) -> [Field; 2] {
    for _ in 0..200 {
        state[0] = state[0] * state[0] + state[1];
        state[1] += state[0];
    }
    state
}

Without any width awareness we get 1150 ACIR gates. With this PR we will get 399 gates. If we substitute oh_no_not_again for the following:

fn oh_no_not_again_as_witness(mut state: [Field; 2]) -> [Field; 2] {
    for i in 0..200 {
        state[0] = state[0] * state[0] + state[1];
        std::as_witness(state[0]);
        state[1] += state[0];
        if (i & 1 == 1) {
            std::as_witness(state[1]);
        }
    }
    state
}

We will get 301 gates if the method above is called instead of oh_no_not_again.

Documentation*

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[vezenovm]

bench_poseidon_hash 447 (+40) +9.83% 453 (+40) +9.69%

Here are some extra numbers to give the full perspective.

Baseline no width awareness gives 1220 ACIR gates.
No width awareness w/ as_witness gives 407 ACIR gates (what we currently have on master).

Width awareness gives 592 gates.
Width awareness w/ as_witness gives 440 ACIR gates.

With the new updates:
Width awareness gives 577 gates
Width awareness w/ as_witness gives 435 ACIR gates.

[TomAFrench]

Generally looks good. Will review again after responses to comments