Optimization: Check whether binary ops can be unchecked based upon the induction variable

[vezenovm]

Problem

When performing binary operations we default to checked operations. However, when we know we have a known upper loop bound we can determine whether there will be an overflow at compilation time.
For example:

fn main(six_as_u32: u32) {
    for i in 0..64 {
        let z: u32 = i * 64;
        assert(z != six_as_u32);
    }
}

We know the maximum loop bound is going to be 63 and the 63*64 will fit into a u32. This operation should be unchecked.

However, let's look at the output from noir-profiler execution-opcodes:

45.3% (448 samples) of the executed opcodes comes from i * 64, while only 6.47% (64 samples as expected) are actual Brillig operations. The rest of the operations for i * 64 are from overflow checks.

Happy Case

Get rid of unnecessary overflow checks when we know from the induction variable that the operation will never overflow.
e.g. The above example should only see 64 opcode samples from i * 64.

This PR #6910 is of similar style but only checks induction variables from outer loops and hoists binary ops into the outer loop based upon the induction variable upper bound.

Workaround

None

Workaround Description

There is no ability to workaround this at the moment, this requires compiler changes.

Additional Context

No response

Project Impact

Blocker

Blocker Context

I am marking this as a blocker as improving unconstrained execution is of general benefit to all Noir devs and this this specific optimization is only possible through compile changesr.

Would you like to submit a PR for this Issue?

None

Support Needs

No response