Cannot iterate on slices

[shuklaayush]

Aim

This code used to work, but now throws a Could not determine loop bound at compile-time error

fn sum_array(arr: [u64]) -> u64 {
    let mut sum = 0;
    for i in 0..arr.len() {
        sum += arr[i];
    }
    sum
}

fn main() {
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let sum = sum_array(arr);
    
    println(sum);
}

An alternative is to use generics

fn sum_array<N>(arr: [u64; N]) -> u64 {
    let mut sum = 0;
    for i in 0..N {
        sum += arr[i];
    }
    sum
}

This seems to work for the above case but throw a Non-numeric type variable used in expression expecting a value panic when I use them in my actual library (https://github.com/shuklaayush/noir-bigint/blob/89b8a964cf94a0c5ff897795da30e255b82b355e/crates/biguint/src/lib.nr#L52-L66)

Expected Behavior

Two scenarios:

1. It should either work
2. If it shouldn't work, then it would be great if there's some clarity on what constitutes a value that can be determined at compile-time

Bug

error: Could not determine loop bound at compile-time
   │
67 │     for i in 0..arr.len() {

To Reproduce

1. Copy the code above
2. Run nargo execute main

Installation Method

Compiled from source

Nargo Version

nargo 0.10.1 (git version hash: fd29197, is dirty: false)

Additional Context

No response

Would you like to submit a PR for this Issue?

Maybe

Support Needs

No response

[vezenovm]

This looks to be caused by us restricting optimizations for Brillig.
As this code where I do not call println:

fn sum_array(arr: [u64]) -> u64 {
    let mut sum = 0;
    for i in 0..arr.len() {
        sum += arr[i];
    }
    sum
}

fn main() {
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let sum = sum_array(arr);
    assert(sum == 55);}

Passes and does not issue the compile-time error. This snippet produces this expected SSA:

After Inlining:
acir fn main f2 {
  b0():
    v12 = allocate
    store u64 0 at v12
    jmp b1(Field 0)
  b1(v16: Field):
    v18 = lt v16, Field 10
    jmpif v18 then: b2, else: b3
  b2():
    v20 = load v12
    v21 = array_get [u64 1, u64 2, u64 3, u64 4, u64 5, u64 6, u64 7, u64 8, u64 9, u64 10], index v16
    v22 = add v20, v21
    v23 = truncate v22 to 64 bits, max_bit_size: 65
    store v23 at v12
    v25 = add v16, Field 1
    jmp b1(v25)
  b3():
    v19 = load v12
    v27 = eq v19, u64 55
    constrain v27
    return 
}

After Mem2Reg:
acir fn main f2 {
  b0():
    v12 = allocate
    store u64 0 at v12
    jmp b1(Field 0)
  b1(v16: Field):
    v18 = lt v16, Field 10
    jmpif v18 then: b2, else: b3
  b2():
    v20 = load v12
    v21 = array_get [u64 1, u64 2, u64 3, u64 4, u64 5, u64 6, u64 7, u64 8, u64 9, u64 10], index v16
    v22 = add v20, v21
    v23 = truncate v22 to 64 bits, max_bit_size: 65
    store v23 at v12
    v25 = add v16, Field 1
    jmp b1(v25)
  b3():
    v19 = load v12
    v27 = eq v19, u64 55
    constrain v27
    return 
}

While with the snippet posted in the main issue we get:

After Inlining:
acir fn main f0 {
  b0():
    v12 = call f1([u64 1, u64 2, u64 3, u64 4, u64 5, u64 6, u64 7, u64 8, u64 9, u64 10])
    call f2(v12)
    return 
}
acir fn sum_array f1 {
  b0(v0: [u64]):
    v2 = allocate
    store u64 0 at v2
    v6 = call array_len(v0)
    jmp b1(Field 0)
  b1(v3: Field):
    v7 = lt v3, v6
    jmpif v7 then: b2, else: b3
  b2():
    v8 = load v2
    v10 = array_get v0, index v3
    v11 = add v8, v10
    v12 = truncate v11 to 64 bits, max_bit_size: 65
    store v12 at v2
    v13 = add v3, Field 1
    jmp b1(v13)
  b3():
    v14 = load v2
    return v14
}
brillig fn println f2 {
  b0(v0: u64):
    call v1(v0, [Field 123, Field 34, Field 107, Field 105, Field 110, Field 100, Field 34, Field 58, Field 34, Field 105, Field 110, Field 116, Field 101, Field 103, Field 101, Field 114, Field 34, Field 44, Field 34, Field 115, Field 105, Field 103, Field 110, Field 34, Field 58, Field 34, Field 117, Field 110, Field 115, Field 105, Field 103, Field 110, Field 101, Field 100, Field 34, Field 44, Field 34, Field 119, Field 105, Field 100, Field 116, Field 104, Field 34, Field 58, Field 54, Field 52, Field 125], u1 0)
    return 
}
acir fn main f3 {
  b0():
    v12 = allocate
    store u64 0 at v12
    jmp b1(Field 0)
  b1(v16: Field):
    v18 = lt v16, Field 10
    jmpif v18 then: b2, else: b3
  b2():
    v20 = load v12
    v21 = array_get [u64 1, u64 2, u64 3, u64 4, u64 5, u64 6, u64 7, u64 8, u64 9, u64 10], index v16
    v22 = add v20, v21
    v23 = truncate v22 to 64 bits, max_bit_size: 65
    store v23 at v12
    v25 = add v16, Field 1
    jmp b1(v25)
  b3():
    v19 = load v12
    call f2(v19)
    return 
}

After Mem2Reg:
acir fn main f0 {
  b0():
    v12 = call f1([u64 1, u64 2, u64 3, u64 4, u64 5, u64 6, u64 7, u64 8, u64 9, u64 10])
    call f2(v12)
    return 
}
acir fn sum_array f1 {
  b0(v0: [u64]):
    v2 = allocate
    store u64 0 at v2
    v6 = call array_len(v0)
    jmp b1(Field 0)
  b1(v3: Field):
    v7 = lt v3, v6
    jmpif v7 then: b2, else: b3
  b2():
    v8 = load v2
    v10 = array_get v0, index v3
    v11 = add v8, v10
    v12 = truncate v11 to 64 bits, max_bit_size: 65
    store v12 at v2
    v13 = add v3, Field 1
    jmp b1(v13)
  b3():
    v14 = load v2
    return v14
}
brillig fn println f2 {
  b0(v0: u64):
    call v1(v0, [Field 123, Field 34, Field 107, Field 105, Field 110, Field 100, Field 34, Field 58, Field 34, Field 105, Field 110, Field 116, Field 101, Field 103, Field 101, Field 114, Field 34, Field 44, Field 34, Field 115, Field 105, Field 103, Field 110, Field 34, Field 58, Field 34, Field 117, Field 110, Field 115, Field 105, Field 103, Field 110, Field 101, Field 100, Field 34, Field 44, Field 34, Field 119, Field 105, Field 100, Field 116, Field 104, Field 34, Field 58, Field 54, Field 52, Field 125], u1 0)
    return 
}
acir fn main f3 {
  b0():
    v12 = allocate
    store u64 0 at v12
    jmp b1(Field 0)
  b1(v16: Field):
    v18 = lt v16, Field 10
    jmpif v18 then: b2, else: b3
  b2():
    v20 = load v12
    v21 = array_get [u64 1, u64 2, u64 3, u64 4, u64 5, u64 6, u64 7, u64 8, u64 9, u64 10], index v16
    v22 = add v20, v21
    v23 = truncate v22 to 64 bits, max_bit_size: 65
    store v23 at v12
    v25 = add v16, Field 1
    jmp b1(v25)
  b3():
    v19 = load v12
    call f2(v19)
    return 
}

[jfecher]

@vezenovm I think it is related but I don't think that is the actual reason the code is failing. Since the only unconstrained function here is println which does not contain any calls to main or sum_array internally, I'd still expect main to fully inline sum_array and unroll it successfully. It seems right now it does inline but does not unroll successfully for some reason.

[jfecher]

Ok, the error here is because the version with println contains an unconstrained function, so we can't inline all functions. Then when loop unrolling happens, it happens on all functions, even the now-unreachable old copy of sum_array which cannot be unrolled since it needs to be inlined into main to see the length of its argument. So the solution for now is to only unroll reachable functions.