SSA Refactor: Handle merging slice values

[vezenovm]

Problem

Slice values currently cannot be merged from separate basic blocks. See this panic here This essentially means that slices cannot be supported in if statements where the condition uses a witness. This is a big missing feature and we cannot fully release slices and the new SSA until this is resolved.

Happy Case

I should be able to do this:

fn main(x : Field, y : pub Field) {
    let mut slice = [];
    if x != y {
        slice = slice.push_back(5);
    } else {
        slice = slice.push_back(10);
    }
}

Alternatives Considered

N/A

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[kevaundray]

@vezenovm what is the status of this issue?

[jfecher]

@kevaundray still open

[iAmMichaelConnor]

Just checking in to see when you're planning to work on this issue?
If it'll be a while, our team should make a start on implementing a 'hacky' workaround in our codebase, for now (AztecProtocol/aztec-packages#1165)

[vezenovm]

@iAmMichaelConnor I am taking a look today. But I can't give a solid time estimate right now as it is not a simple issue. I do know it won't be solved by end of the week or even start of next week most likely.

[iAmMichaelConnor]

No worries - that's good to know :)
I might suggest that someone on our team tries to work around it in the mean time, in that case, by doing something a bit 'jankier' :)

[sirasistant]

We might want to reconsider indexing of slice insert/remove at the SSA level. We are currently using user-level indices (not multiplied with element_size). This is inconsistent with array accessing on SSA, which uses flattened indexing!

[jfecher]

@sirasistant was the issue you're referencing not fixed by #2150?

[sirasistant]

I think that PR fixed it for slice op simplifications, but for slice ops that are not simplified (which is supported in brillig) there still is an inconsistency

[sirasistant]

Yes, just confirmed in master:

use dep::std;

struct TwoItems {
    a: Field,
    b: Field,
}

unconstrained fn main(a: Field, b: Field) {
    let first = TwoItems { a, b };
    let second = TwoItems { a: b, b: a };

    let mut slice = [first, second];

    let item_that_will_be_removed = slice[1];
    assert(item_that_will_be_removed.a == b);

    let remove_result = slice.remove(1);
    let removed_item = remove_result.1;
    assert(removed_item.a == b);
}

Generates this ssa:

Initial SSA:
brillig fn main f0 {
  b0(v0: Field, v1: Field):
    v3 = allocate
    store [v0, v1, v1, v0] at v3
    v4 = load v3
    v7 = array_get v4, index Field 2 // slice[1]
    v9 = array_get v4, index Field 3 // slice[1]
    v10 = eq v7, v1
    constrain v10
    v12 = load v3
    v13, v14, v15 = call slice_remove(v12, Field 1) // slice.remove(1)
    v16 = eq v14, v1
    constrain v16
    return 
}

[jfecher]

@sirasistant I think we should look into fixing this in brillig since the SSA itself seems correct to me. Those are the arguments slice_remove was called with after all. We could expand it into multiple calls to slice_remove during ssa-gen if it is too difficult to fix in brillig I suppose.

For consistency it could go either way. You could argue if the indices in slice remove don't account for structs then it's inconsistent with the indices for array accesses. Or you could argue if they did account for structs then slice_remove and friends would be inconsistent with other function calls where the arguments are unchanged.

[sirasistant]

Oh, this is already handled in brillig, it's just issuing a multiplication. It's just that it was unexpected to see a "user level" index arrive for slice ops when it doesn't for array indices. But yeah It's different because slice ops are intrinsics 🤔

[jfecher]

I was thinking about changing it to have the intrinsics be expanded into multiple calls on the case of structs (what simplify_instruction does currently) during ssa-gen, but I don't think it's possible after all since you'd need to do it on a function call but don't always know what function you're calling. E.g.

let f = if x { slice_remove } else { foo };
let slice = f([], 7);

[vezenovm]

@iAmMichaelConnor This is now merged into master. I am moving onto using dynamic indices with slices, and once that is complete slices will be fully supported. If you don't need dynamic indexing immediately your team could start transitioning to using slices.

[vezenovm]

@iAmMichaelConnor I would hold off on switching to slices just yet. We have found a bug here (#2599) that would most likely cause issues for you. There is a potential fix I am hoping resolves this quickly, but if the fix turns out to not be viable it will most likely not be a simple issue.