QIR Array Slicing does not match spec

[swernli]

Array slicing is supposed to work like copy, where it includes a force parameter and will behave differently based on that and how many alias counts the target array has. In the QIR spec it has signature %Array*(%Array*, %Range, i1) and describes it as:

Creates and returns an array that is a slice of an existing 1-dimensional array. The slice may be accessing the same memory as the given array unless its alias count is larger than 0 or the last argument is true. The %Range specifies the indices that should be the elements of the returned array. The reference count of the elements remains unchanged.

Meanwhile the runtime currently defines __quantum__rt__array_slice_1d as:

https://github.com/microsoft/qsharp-runtime/blob/c84d56d98ae58bbf99aa980d1a063a81005611f9/src/Qir/Runtime/lib/QIR/bridge-rt.ll#L294 And the implementation always copies.

__quantum__rt__array_slice has the same problem.

@bettinaheim, @kuzminrobin, @alan-geller FYI

[bettinaheim]

Hm, I think it would be reasonable (and more reasonable) to not require the runtime to implement that optimization. I'd leave it up to the runtime to make a judgement on what cases exactly it wants to optimize; this optimization specifically requires a particular choice regarding representation, which we shouldn't prescribe - full opacity of arrays has been appreciated. Let me transfer this to the spec repo.

[swernli]

I agree, I think it does make the implementation much, much easier to not support this kind of copy. We have the same force-copy vs alias semantics on tuples, is it worth re-evaluating that one as well?

For slices, just to be clear, would removing this explicit copy description mean it is up to the implementation whether a slice is a view or a copy or would it imply that the returned array is always a shallow copy (what our current implementation does). If it's the latter, then the reference counting semantics are easier, since array slicing is exactly like a create. If it's the former, then we might need a dedicated slice type with lifetime somehow tied to the originating array and that gets much trickier.

[kuzminrobin]

Looks like we need to review the QIR Spec, at least the Arrays section regarding __quantum__rt__array_slice[_1d]. If during slicing we always create a copy then we likely don't need the alias count any more.

[swernli]

Yeah, I agree that more discussion is needed here. I think the concepts of alias count and and force copy parameters make sense in theory for allowing runtimes to decide when to create copies and when not, but in practice it is hard to do well, especially with array slicing. I don't know if that means we remove them from the spec explicitly or not though. While I like leaving room for future possible optimizations I'm not sure this one is that helpful.