Dead Instruction Elimination pass removes out of bounds array sets

[Thunkar]

Aim

While moving some tests from constrained to unconstrained so they run faster (we're only checking function logic and assume circuit generation is fine), the code that used to work started failing with "Array index out of bounds" errors.

Expected Behavior

Behavior should be consistent between constrained and unconstrained contexts.

Bug

Out of bounds errors can be masked in certain scenarios, specifically when copying array positions from one to another. However, illegal acceses are always detected as expected in unconstrained functions.

To Reproduce

// Taken from noir-protocol-circuits
fn arr_copy_slice<T, N, M>(src: [T; N], mut dst: [T; M], offset: u32) -> [T; M] {
    for i in 0..dst.len() {
        // We are illegally accessing the src array here if dst.len() > src.len()
        dst[i] = src[i + offset];
    }
    dst
}

unconstrained fn boom<N, M>(src: [Field; N], dst: [Field; M]) -> [Field; M] {
    arr_copy_slice(src, dst, 0)
}


fn main() {
    // This shouldn't work
    let small_array_src = [1; 5];
    let mut big_array_dst = [0; 6];
    let mut result = arr_copy_slice(small_array_src, big_array_dst, 0);

    // Uncomment for fireworks. This *always* get caught in unconstrained land
    //let result = boom();

    // This is fine
    let first = result[0];
    dep::std::println(first);
    // This is also fine, since we are overwriting the "illegal" position.
    // BUT if we comment this line out, fireworks again (since we are now "using" the illegal position)
    result[5] = 1;

    dep::std::println(result[5]);
}

Project Impact

Nice-to-have

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

Compiled from source

Nargo Version

No response

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[jfecher]

Interesting, it looks like the pass to remove unused code removes the array_set instruction in question since it was unused in the final program. This explains why it also still catches it if that index is later printed out without being mutated first.

[asterite]

Reduced:

fn main() {
    let src = [1];
    let mut dst = [1];
    dst[0] = src[10];
    dst[0] = 1; // commenting this line will produce Index Out of Bounds when executing
    println(dst[0])
}

[asterite]

One solution could be to not remove array_get operations if the index might be out of bounds (if the index is a constant and it's out of bounds, or if the index is not known at compile-time)

[asterite]

This program also doesn't give index out of bounds at runtime, but probably should:

fn main() {
    let mut dst = [1];
    dst[10] = 1;
}

[vezenovm]

Posting discussion from scrum for visibility:

We are going to try a new approach. Instead of always inserting a length assertion on array gets/sets, when we remove an unused array operation during DIE, we will replace it with a length assertion. This should hopefully let us avoid any extra constraints on dynamic array gets/sets which are still used elsewhere in the circuit.

[vezenovm]

Closed due to #5691 being merged