Push ArrayGet instructions backwards through IfElse instructions to avoid expensive array merges

[TomAFrench]

Consider the program

fn main(array_a: [Field; 1000], array_b: [Field; 1000], is_b: bool, whatever_index: u32) {
    let mut array = array_a;
    if is_b {
        array = array_b;
    } 

    assert(array[whatever_index] == 0);
}

After flattening the control flow graph we end up with the instructions

// Here v0 and v1 are `array_a` and `array_b`
v7 = if v2 then v1 else if v5 then v0
v8 = array_get v7, index v3

This results in us merging two 1000 element arrays (performing 2000 array reads, merging these values into a new 1000 element array) and then performing a single read at whatever_index.

Ideally users would refactor their code to do single reads from the two arrays and then merge that single index, e.g.

let value = if is_b { array_b[whatever_index] } else { array_a[whatever_index] };
assert(value == 0);

We can perform this optimisation automatically however, we can recognise that we're performing an array read from the output of an IfElse instruction and pull out reads from the original arrays and generate a new IfElse for that single array element. We then get the SSA

v9 = array_get v0, index v3
v10 = array_get v1, index v3
v11 = if v2 then v9 else if v5 then v10
v7 = if v2 then v1 else if v5 then v0 // preserve original merged array in case used elsewhere.

Constant folding will prevent any extra gates being produced should v7 survive DIE.

[jfecher]

This strikes me as vaguely similar to what we do in try_merge_only_changed_indices here https://github.com/noir-lang/noir/blob/master/compiler/noirc_evaluator/src/ssa/opt/flatten_cfg/value_merger.rs#L147. Only that instead of finding changed indices to shortcut the array merge we're finding only the indices that are actually checked later on and removing the merger of the rest of the array entirely.