Local array indexed dynamic is re-initialized unnecessarily

[vezenovm]

Aim

In this base64 repo @zac-williamson noticed a blow-up when the same array as a local variable vs. when it was returned from a function.

A smaller reproduction can be found here:

fn main(x: [u8; 2]) {
    let _: [u8; 32] = base64_decode_without_struct(x);
    // let _: [u8; 32] = base64_decode_with_struct(x);
}
global BASE64_DECODE_BE: [Field; 128] = [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,// 0-9
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,// 10-19
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,// 20-29
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0,// 30-39
        0, 0, 0,// 40-42
        62,// 43
        0, 0, 0,// 44-46
        63,// 47
        52, 53, 54, 55, 56, 57, 58, 59, 60, 61,// 48-57
        0, 0, 0, 0, 0, 0, 0,// 58-64
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,// 65-90 (A-Z)
        0, 0, 0, 0, 0, 0,// 91-96
        26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,// 97-122 (a-z)
        0, 0, 0, 0, 0// 123-127
    ];
fn base64_decode_without_struct<let InputElements: u64, let OutputBytes: u64>(input: [u8; InputElements]) -> [u8; OutputBytes] {
    let mut result: [u8; OutputBytes] = [0; OutputBytes];
    let mut slice: Field = 0;
    for j in 0..InputElements {
        slice += BASE64_DECODE_BE[input[j]];
    }
    let _: [u8; 30] = slice.to_be_bytes(30).as_array();
    result
}
// #### METHOD 2. When lookup table is in a struct, lookups are much cheaper and ROM table is used in backend
struct Lookup {
    table: [Field; 128]
}
impl Lookup {
    fn new() -> Self {
        Lookup {
            table: BASE64_DECODE_BE
        }
    }

    fn get(self, idx: Field) -> Field {
        self.table[idx]
    }
}
fn base64_decode_with_struct<let InputElements: u64, let OutputBytes: u64>(input: [u8; InputElements]) -> [u8; OutputBytes] {
    let mut BASE64_DECODE_BE = Lookup::new();
    let mut result: [u8; OutputBytes] = [0; OutputBytes];
    let mut slice: Field = 0;
    for j in 0..InputElements {
        slice += BASE64_DECODE_BE.get(input[j] as Field);
    }
    let _: [u8; 30] = slice.to_be_bytes(30).as_array();
    result
}

Expected Behavior

As the size of the x input to main is increased the acir count of using base64_decode_without_struct and base64_decode_with_struct should stay the same.

Bug

Even with x.len() == 2 we have one extra gate for base64_decode_without_struct. This continues to increase as we increase the size of the x array.

The size of the x array does determine how many loop iterations we perform, where in each iteration we are reading from the provided constant array. The gate increase between the two versions looks to always be x.len() - 1. In fact, when looking at the final ACIR it looks like we have x.len() - 1 more memory INIT operations in the local variable array version. So it looks to me like we are reinitializing the local array for each loop iteration when it can actually be re-used.

To Reproduce

1. Run the code above with nargo info
2. Uncomment base64_decode_with_struct and compare the acir counts
3. Increase the size of the x input to main to see the blow-up increase with the input.

Project Impact

Nice-to-have

Impact Context

This isn't blocking but forces people to work around the blow-up.

Workaround

Yes

Workaround Description

The work around is provided in the main description of the bug.

Additional Context

No response

Installation Method

None

Nargo Version

No response

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[vezenovm]

In fact, when looking at the final ACIR it looks like we have x.len() - 1 more memory INIT operations in the local variable array version. So it looks to me like we are reinitializing the local array for each loop iteration when it can actually be re-used.

To further back this up this is the SSA and printed memory_blocks array from our ACIR gen Context for the local array version:

After Array Set Optimizations:
acir(inline) fn main f0 {
  b0(v0: [u8; 2]):
    v253 = array_get v0, index u32 0
    v254 = cast v253 as u32
    v255 = array_get [Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 62, Field 0, Field 0, Field 0, Field 63, Field 52, Field 53, Field 54, Field 55, Field 56, Field 57, Field 58, Field 59, Field 60, Field 61, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 1, Field 2, Field 3, Field 4, Field 5, Field 6, Field 7, Field 8, Field 9, Field 10, Field 11, Field 12, Field 13, Field 14, Field 15, Field 2⁴, Field 17, Field 18, Field 19, Field 20, Field 21, Field 22, Field 23, Field 24, Field 25, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 26, Field 27, Field 28, Field 29, Field 30, Field 31, Field 2⁵, Field 33, Field 34, Field 35, Field 36, Field 37, Field 38, Field 39, Field 40, Field 41, Field 42, Field 43, Field 44, Field 45, Field 46, Field 47, Field 2⁴×3, Field 49, Field 50, Field 51, Field 0, Field 0, Field 0, Field 0, Field 0], index v254
    v256 = array_get v0, index u32 1
    v257 = cast v256 as u32
    v258 = array_get [Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 62, Field 0, Field 0, Field 0, Field 63, Field 52, Field 53, Field 54, Field 55, Field 56, Field 57, Field 58, Field 59, Field 60, Field 61, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 1, Field 2, Field 3, Field 4, Field 5, Field 6, Field 7, Field 8, Field 9, Field 10, Field 11, Field 12, Field 13, Field 14, Field 15, Field 2⁴, Field 17, Field 18, Field 19, Field 20, Field 21, Field 22, Field 23, Field 24, Field 25, Field 0, Field 0, Field 0, Field 0, Field 0, Field 0, Field 26, Field 27, Field 28, Field 29, Field 30, Field 31, Field 2⁵, Field 33, Field 34, Field 35, Field 36, Field 37, Field 38, Field 39, Field 40, Field 41, Field 42, Field 43, Field 44, Field 45, Field 46, Field 47, Field 2⁴×3, Field 49, Field 50, Field 51, Field 0, Field 0, Field 0, Field 0, Field 0], index v257
    v259 = add v255, v258
    v260, v261 = call to_be_radix(v259, u32 2⁸, u32 30)
    constrain v260 == u32 30
    return 
}

[compiler/noirc_evaluator/src/ssa/acir_gen/mod.rs:434] self.memory_blocks.clone() = {
    Id(
        0,
    ): BlockId(
        0,
    ),
    Id(
        72,
    ): BlockId(
        1,
    ),
    Id(
        77,
    ): BlockId(
        2,
    ),
    Id(
        261,
    ): BlockId(
        3,
    ),
}
[compiler/noirc_evaluator/src/ssa/acir_gen/mod.rs:435] self.memory_blocks.len() = 4

For the struct version the SSA is essentially identical (with only the exact value IDs differing). Here is the printed memory_blocks:

[compiler/noirc_evaluator/src/ssa/acir_gen/mod.rs:434] self.memory_blocks.clone() = {
    Id(
        0,
    ): BlockId(
        0,
    ),
    Id(
        65,
    ): BlockId(
        1,
    ),
    Id(
        269,
    ): BlockId(
        2,
    ),
}
[compiler/noirc_evaluator/src/ssa/acir_gen/mod.rs:435] self.memory_blocks.len() = 3

It looks as though we have v65 being re-used for both array gets in the struct version, while the array_gets in the local array version have separate value ids for v71 and v77. As memory_blocks maps from value id -> memory block id, the code gen re-initializes the array.

[vezenovm]

Looks to be a repeat issue of (#5286) but for this case we still have the duplication.