Design: when to use a descriptor for an array

[certik]

Currently the backend chooses how arrays are implemented, and the decision when to use a descriptor and when just a pointer is complex (and getting more complicated as we develop):

#1346 (comment)

If we can't determine this robustly ourselves, we might need to annotate the array in the source code, perhaps change i8[64] to NoDescriptor[i8[64]] or something like that, then set this in ASR.

If the decision is this complex, then I think it should be part of ASR itself and the optimizer will choose, or even the frontend (or both).

There is more to it though: an array might live on a device Device[i8[64]], etc. We also have optimization ASR->ASR passes that take a descriptor array and turn it into a pointer array.

Currently this information if it is a pointer array or a descriptor array is implicit in ASR and the rules are complex and getting more complex.

To make progress, let's do the following:

• Summarize all usages of arrays, and for each denote if it can be done with a pointer array or descriptor array or both
• Which use cases allow both?
• Which use cases require pointer arrays, but descriptor arrays would not work?
• Which use cases require descriptor arrays, but pointer arrays would not work?

Having answers to these questions will allow us to guide the design. The most obvious simpler design is to just have a flag in the Variable, if it is an array, what kind of array.

The flag can also be in the type, to allow to track this in an array expression like x(:) + y(:). If we do this, probably doing the Array type, like List, then we can add these flags there.

[czgdp1807]

Quoting from #1346 (comment),

My suggestion would be to always create data only arrays for fixed sizes and use descriptors otherwise.

I think a descriptor is only needed when the array is not fixed size which happens when at least one of the dimensions has runtime length. If we can calculate size of the array at compile time then that simply means all the dimensional information is available at compile time so no need to store it in a runtime descriptor. There will be a few catches (doable but should be made sure that we test them and make them work) though,

1. Assigning a non-descriptor array to a descriptor array and vice-versa.
2. Handling two cases in ArrayItem.
3. Passing non-descriptor array to a function accepting a descriptor based array and vice-versa.
4. Reshaping a descriptor based array and putting it into a non-descriptor array and vice-versa.

Basically inter-operating between descriptor based and non-descriptor based arrays in the backend.

[certik]

Assigning a non-descriptor array to a descriptor array and vice-versa.

This seems like casting.

It seems to me almost that we should handle this at ASR level explicitly (either different nodes, or different types, or different flags in a type), and insert casting nodes (if needed), etc. So that in the backend, you do not need to worry about any of this.

[czgdp1807]

Yes. I guess instead of asking users to specify explicitly whether they need a descriptor we can figure it out on our own and enable a flag in the type (like we do for column major/row major), i8[64] or NoDescriptor[i8[64]] should be a choice at the syntax level and not a necessary thing to be done. For example, i8[64] should always be a data only array as it has fixed size and hence fixed dimensional information, so no descriptor needed here. Backend should just see the flag and generate code accordingly.

[certik]

Yes, users should not care about this, we can almost for sure make the optimal choice ourselves (users should only need to enforce it in rare cases).

It's more about how to structure it, so that it's clean in the backend.

[czgdp1807]

It's more about how to structure it, so that it's clean in the backend.

Yes. For now I feel its a lot of ad-hoc checks. These checks will be needed anyways but they should happen in AST to ASR transition and not in the backend. I had to duplicate a lot of things to make #1346 happen. So probably let's decide a clean protocol and shift the decision making of descriptor vs no-descriptor to ASR.

[certik]

Right, exactly.

Let's enumerate the use cases, and mark what options the front end has to choose from. Or to be specific: what checks verify() has to do when. The backend would then just generate whatever is directed by the ASR. We might need to introduce casting ArrayDescriptorToPointer and PointerToArrayDescriptor, possibly.

[czgdp1807]

ArrayDescriptorToPointer and PointerToArrayDescriptor, possibly.

Its very simple to do. For ArrayDescriptorToPointer, just extract the data pointer from the descriptor and that's all you need. For PointerToArrayDescriptor, just create a new descriptor put all of the information in it (data is already available as a pointer, dimensional information is available at compile time, just needs filling in the new descriptor). If you want to do deepcopy of data pointer then we have APIs for that as well. So it won't be a problem. What we need is a good protocol to make the decision of descriptor vs no-descriptor. There are only two cases IMO,

i. Array is fixed size i.e., it possible to get the size of the array at compile time only. This would mean that the lengths of all the dimensions are already available at compile time because even if one dimension length is not available at compile then size cannot be compile time.
ii. Array is variable sized i.e., you don't know the size of the array at compile time.

Second case always needs a descriptor. First case I don't think you need a descriptor to represent it. Is there any thing I am missing out?

[certik]

Actually, ArrayDescriptorToPointer might require a temporary copy, depending on if the descriptor is continuous. That's a separate, but related, discussion. Currently I think we don't allow non-contiguous descriptors.

Yes, the cases you didn't mention is an array argument, with runtime size, but specified using other arguments integer, intent(in) :: A(n, m), versus, integer, intent(in) :: A(:,:). Both are runtime, but the first is a pointer, while the second is a descriptor. The first one does not need to be a pointer, there is a choice, it can be either one.

[czgdp1807]

Correct. But that's specific to arguments only correct? For local variables, integer :: A(n, m) it would still need a descriptor, right?

[certik]

Local variables also have a choice of a descriptor vs a pointer. Both can work.

That's why I am asking for cases when either one is required. So far pointers are required by BindC, and descriptors are required for integer, intent(in) :: A(:,:) (one can transform descriptors to pointers using an ASR pass by introducing extra arguments, but that's a separate issue). For every other use case I think one can use both pointers and descriptors.

[certik]

Here is a solution how to do this: lfortran/lfortran#1601