How to handle deallocatable function return values

[certik]

An example:

def g() -> list[i32]:
    ...
 
def f() -> list[i32]:
    a = [1, 2, 3]
    z = a+g()
    return z

Here, we need to deallocate the temporary result of the function g().

One general way is to assign the result of a function to a temporary variable first (either always do it, or only when the result is allocatable, or possibly an array). Like this:

def g() -> list[i32]:
    ...
 
def f() -> list[i32]:
    a = [1, 2, 3]
    tmp1 = g()
    z = a+tmp1
    Deallocate([tmp1, a])
    return z

It's a question whether we should do this for all functions all the time, or only for functions that return allocatable arrays/lists.

For arrays, this approach also allows to write an ASR transformation that transforms functions into subroutines:

def g() -> list[i32]:
    ...
 
def f() -> list[i32]:
    a = [1, 2, 3]
    tmp1: Allocatable[i32[:]]
    g2(tmp1)
    z = a+tmp1
    Deallocate([tmp1,a])
    return z

Which makes it easy on the LLVM backend to implement.

[certik]

There are two cases:

def g() -> list[i32]:
    ...
 
def f() -> list[i32]:
    a = [1, 2, 3]
    tmp1 = g()
    if (allocated(tmp1) then
        z = a+tmp1
    else 
        z = a
    end if
    ImplicitDeallocate([tmp1, a])
    return z

[certik]

Another open question is exactly how the ASR should look like for list[str], where the string elements also have to be deallocated before the list is deallocated.

[certik]

Should list[i32] be allocatable in ASR? The current design of ASR is that if a variable is allocatable, then the ImplicitDeallocate is properly inserted. If it is not allocatable, then it is not inserted, in which case, the backend must implement it on a stack. An example is a string: allocatable strings must have ImplicitDeallocate() node inserted. But non-allocatable strings, such as character(len=10) have a size that is known either at compile time, or inferred from arguments of a function, either way the backend can store them on a stack, so does not have to worry about deallocation. The same with arrays, that can be both allocatable and non-allocatable (stack based).

[certik]

What about DerivedTypes (struct)? Those can have allocatable components, but the derived type itself can live on a stack. The components however must be deallocated when the derived type goes out of scope.

So it seems we need to call a "Destructor" on all variables that go out of scope. Integers/Real obviously do not need it, but derived types, lists, etc. need it. As well as user classes with a finalizer / destructor.

[certik]

We can have a Destructor (or Destruct) ASR node, and it would call a "destructor" for all the variables (so list would free its elements, a derived type would deallocate all its components).

[certik]

It's a question whether we should do this for all functions all the time, or only for functions that return allocatable arrays/lists.

I would say the answer is that ASR could allow both, that is, if ImplicitDeallocate or Destructor does not need to be called (such as for an integer, non-allocatable return value), then one can either do directly a+f() or via a temporary variable tmp=f(); a+tmp, but if ImplicitDeallocate/Destructor must be called, then one must assign to a temporary first --- and it will be checked by verify.

[czgdp1807]

then one must assign to a temporary first

By this you mean deep copy the data from f() to tmp and then deallocate the pointer returned by f()?

[certik]

Yes, deep copy. Note however, that the transformation tmp = f() -> call f(tmp) avoids a deep copy, so it should be as efficient as without a temporary.

[czgdp1807]

I see. Here's my opinion,

1. We should deallocate only those allocatable variables which are local to a function body. In addition, we shouldn't automatically deallocate the argument and return variables. So, in your case I would do something like this,

def g() -> list[i32]:
    ...
 
def f() -> list[i32]:
    a = [1, 2, 3]
    g(tmp) # Convert g to a function accepting the return type as a pointer so that we don't need to do deep copy. LFortran already converts functions which return array to subroutines with the destination array as the last argument.
    z = a + tmp
    del tmp # Added automatically via ASR pass
    return z

2. We shouldn't too much of deallocation automatically. Like deallocate all the allocatable variables together at the end of a function body. Reason being too much deallocation leads to memory fragmentation (specifically external fragmentation). So, just do this at the end of a function/scope body, not anywhere in between. So, doing deep copy will just to lead to fragmentation because first you will create a new memory (which at some point of time during program execution would require double memory for the same array) and then deallocate the previous one.

[certik]

Yes, deallocation should only happen at all exit points of the functions, so at the end of a function and before every return. We don't have exceptions in ASR, so that's currently the only way the function can exit. Our ASR optimizers can do all kinds of optimizations, similar to the LLVM's mem2reg pass. The main question really is, what is required of the frontend to do, and what the "canonical" ASR way should be (checked by verify). It should not require any complicated rewriting by the frontend, just enough to get "canonical", and ASR should be explicit about the deallocation, so that it's easy to generate code from it.

[czgdp1807]

The main question really is, what is required of the frontend to do, and what the "canonical" ASR way should be (checked by verify). It should not require any complicated rewriting by the frontend, just enough to get "canonical", and ASR should be explicit about the deallocation, so that it's easy to generate code from it.

For this I would suggest the following,

deallocate only those allocatable variables which are local to a function body. In addition, we shouldn't automatically deallocate the argument and return variables

[certik]

This naturally leads to: https://gitlab.com/lfortran/lfortran/-/issues/693

[czgdp1807]

Makes sense to me. ASR pass can do everything that you mentioned in the above Gitlab issue. We should do this one by one.