Optimization: Avoid validating array indices for known induction variable bounds

[vezenovm]

Problem

Validating an array index is done for every array get where the index is found to not be a numeric constant:

noir/compiler/noirc_evaluator/src/brillig/brillig_gen/brillig_block.rs

Line 749 in b2b632b

if !dfg.is_safe_index(*index, *array) {

However, there are certain variables (e.g. induction variables), where we know the upper bound of the variable.
Take this program:

fn main(x: u32) {
    array_read_loop(4, x);
}
fn array_read_loop(upper_bound: u32, x: u32) {
    let arr = [2; 5];
    for i in 0..upper_bound {
        for j in 0..upper_bound {
            assert_eq(arr[i], x);
            assert_eq(arr[j], x);
        }
    }
}

A i and j are induction variables we will generate an array access check when the maximum value i and j can take is less than the len of arr.

Happy Case

We should not generate unnecessary array index checks for induction variables with known bounds.

In the passing case, array index validation will take 3 instructions to execute (making the array pointer, and less than check, and a jmpif). For large loops this can be

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

None

Blocker Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response