Returning data structures defined by struct in backends

I slept on the idea of implementing this and found out that we need to make a design choice. The choice will be applicable to any data structure defined by a struct (i.e., lists, tuples, class, excluding arrays though because they are already handled in array_op ASR pass). First let's note a couple of points,

Data structures defined by struct should be returned by value - We cannot return pointers to struct especially for those which are created inside the function body. The reason is simple. For example in LLVM backend, we will call struct_ptr = builder->CreateAlloca(some_struct_type, nullptr) inside the function body and as soon as the function call will complete and we will return to the caller scope, struct_ptr will become invalid (because call stack will not be active anymore).
To access any element of a struct we need to use pointer to it in LLVM backend - LLVM only allows accessing elements of a struct if we use a pointer to it. For example if list is a struct type, then you cannot call builder->CreateGEP(list, idx) or builder->CreateInBoundsGEP(list, idx). You must do, builder->CreateGEP(list*, idx) or builder->CreateInBoundsGEP(list*, idx).

So, as you can see returning pointers to struct is not possible and structs are only usable if we have pointers to them. So, to satisfy both the constraints there are two options which I can think of,

Create a temporary variable and store the returned struct into it - Let's see the code directly,

llvm::Value* CreateCallUtil(llvm::Function* fn, std::vector<llvm::Value*>& args, ASR::ttype_t* asr_return_type) {
    llvm::Value* return_value = builder->CreateCall(fn, args);
    if( !LLVM::is_llvm_struct(asr_return_type) ) {
        return return_value;
    }

    llvm::Value* pointer_to_struct = builder->CreateAlloca(fn->getFunctionType()->getReturnType(), nullptr); // Call to LLVM APIs not needed to fetch the return type of the function. We can use asr_return_type as well but anyways for compactness I did it here.
    LLVM::CreateStore(*builder, return_value, pointer_to_struct);
    return pointer_to_struct;
}

So you can see how we create a pointer to struct and then store the struct returned by value into it. We can replace all, builder->CreateCall(fn, args) with the call to above function everywhere. This idea already works in main (see https://github.com/lcompilers/lpython/blob/main/integration_tests/test_tuple_02.py) but is not generalised to all types yet.

Create an ASR to ASR pass to convert all functions returning list, tuple, class or anything defined by a struct in the backend to a function not returning anything and accepting the return value as the last argument with intent(out). We do this for arrays already (they are defined by a struct in C/C++ and LLVM backend). We can extend the same to list, tuple, class types as well. We already have the infrastructure to do this.

So what should we do? IMO, choice 1 is quick and easy, and it already works we just have to generalise it. Its very small code to write as well. Choice 2 that is ASR to ASR pass requires visiting the whole ASR again so higher overhead as compared to Choice 1 but it is sharable across all backends. I think we should go for choice 1 for now and then in future if we see it working then we can add an ASR to ASR pass to do the same job. @certik What do you say?

_Originally posted by @czgdp1807 in https://github.com/lcompilers/lpython/pull/955#discussion_r945448288_

lcompilers / lpython

Returning data structures defined by struct in backends #977