fix(ssa): Do not optimize for allocates in constant folding

[vezenovm]

Description

Problem*

Quick fix found when working on (#2446) so no issue

Summary*

In order to get dynamic slices working I included a constant folding pass before flattening. In this PR (#2460) we reuse duplicate instructions with no side effects. However, Allocate instructions are not explicitly marked as having side effects so that they can be removed in DIE.

For example in execution_success/slices executing just this method:

fn merge_slices_mutate(x: Field, y: Field) -> [Field] {
    let mut slice = [0; 2];
    if x != y {
        slice = slice.push_back(y);
        slice = slice.push_back(x);
    } else {
        slice = slice.push_back(x);
    };
    slice
}

Will lead to this SSA (with constant folding before flattening):

After Mem2Reg:
acir fn main f4 {
  b0(v0: Field, v1: Field):
    v5 = allocate
    store Field 2 at v5
    v7 = allocate
    store [Field 0, Field 0] at v7
    v10 = eq v0, v1
    v11 = not v10
    jmpif v11 then: b1, else: b2
  b1():
    v21, v22 = call slice_push_back(Field 2, [Field 0, Field 0], v1)
    v25, v26 = call slice_push_back(v21, v22, v0)
    store v25 at v5
    store v26 at v7
    jmp b3()
  b3():
    v17 = load v5
    v18 = load v7
    v27 = cast v17 as u64
    v29 = lt Field 3, v27
    constrain v29
    v30 = array_get v18, index Field 3
    v32 = eq v30, Field 5
    constrain v32
    v34 = eq v17, Field 4
    constrain v34
    return 
  b2():
    v15, v16 = call slice_push_back(Field 2, [Field 0, Field 0], v0)
    store v15 at v5
    store v16 at v7
    jmp b3()
}

After Constant Folding:
acir fn main f4 {
  b0(v0: Field, v1: Field):
    v36 = allocate
    store Field 2 at v36
    store [Field 0, Field 0] at v36
    v37 = eq v0, v1
    v38 = not v37
    jmpif v38 then: b1, else: b2
  b1():
    store Field 4 at v36
    store [Field 0, Field 0, v1, v0] at v36
    jmp b3()
  b3():
    v41 = load v36
    v42 = load v36
    v43 = cast v41 as u64
    v44 = lt Field 3, v43
    constrain v44
    v45 = array_get v42, index Field 3
    v46 = eq v45, Field 5
    constrain v46
    v47 = eq v41, Field 4
    constrain v47
    return 
  b2():
    store Field 3 at v36
    store [Field 0, Field 0, v0] at v36
    jmp b3()
}

If you look in b0 the allocate instruction are being malformed. We are fetching our results from this map HashMap<Instruction, Vec> which can lead to duplicate instructions. I included a check that we do not cache allocate instructions.

Documentation

• This PR requires documentation updates when merged.

  • I will submit a noir-lang/docs PR.
  • I will request for and support Dev Rel's help in documenting this PR.

Additional Context

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.