diff --git a/flang/docs/ParameterizedDerivedTypes.md b/flang/docs/ParameterizedDerivedTypes.md new file mode 100644 --- /dev/null +++ b/flang/docs/ParameterizedDerivedTypes.md @@ -0,0 +1,1027 @@ +# Parameterized Derived Types (PDTs) + +Derived types can be parameterized with type parameters. A type parameter is +either a kind type parameter or a length type parameter. Both kind and length +type parameters are of integer type. + +This document aims to give insights at the representation of PDTs in FIR and how +PDTs related constructs and features are lowered to FIR. + +# Fortran standard + +Here is a list of the sections and constraints of the Fortran standard involved +for parameterized derived types. + +- 7.2 Type parameters + - C701 + - C702 +- 9.4.5: Type parameter inquiry +- 9.7.1: ALLOCATE statement +- 9.7.2: NULLIFY +- 9.7.3: DEALLOCATE + +The constraints are implemented and tested in flang. + +### PDT with kind type parameter + +PDTs with kind type parameter are already implemented in flang. Since the kind +type parameter shall be a constant expression, it can be determined at +compile-time and is folded in the type itself. Kind type parameters also play +a role in determining a specific type instance according to the Fortran +standard. + +**Fortran** +```fortran +type t(k) + integer, kind :: k +end type + +type(t(1)) :: tk1 +type(t(2)) :: tk2 +``` + +In the example above, `tk1` and `tk2` have distinct types. + +Lowering makes the distinction between the two types by giving them different +names `@_QFE.kp.t.1` and `@_QFE.kp.t.2`. More information about the unique names +can be found here: `flang/docs/BijectiveInternalNameUniquing.md` + +### PDT with length type parameter + +Two PDTs with the same derived type and the same kind type parameters but +different length type parameters are not distinct types. Unlike the kind type +parameter, the length type parameters do not play a role in determining a +specific type instance. +PDTs with length type parameter can be seen as dependent types[1]. + +In the example below, `tk1` and `tk2` have the same type but may have different +layout in memory. They have different value for the length type parameter `l`. +`tk1` and `tk2` are not convertible unlike `CHARACTER` types. +Assigning `tk2` to `tk1` is not a valid program. + +**Fortran** +```fortran +type t(k,l) + integer, kind :: k + integer, len :: l +end type + +type(t(1, i+1)) :: tk1 +type(t(1, i+2)) :: tk2 + +! This is invalid +tk2 = tk1 +``` + +Components with length type parameters cannot be folded into the type at +compile-time like the one with kind type parameters since their size is not +known. There are multiple ways to implement length type parameters and here are +two possibilities. + +1. Directly encapsulate the components in the derived type. This will be referred + as the "inlined" solution in the rest of the document. The size of the + descriptor will not be fixed and be computed at runtime. Size, offset need + to be computed at runtime as well. + +2. Use a level of indirection for the components outside of the descriptor. This + will be referred as the "outlined" solution in the rest of the document. + The descriptor size will then remain the same. + +These solutions have pros and cons and more details are given in the next few +sections. + +#### Implementing PDT with inlined components + +In case of `len_type1`, the size, offset, etc. of `fld1` and `fld2` depend on +the runtime values of `i` and `j` when the components are inlined into the +derived type. At runtime, this information needs to be computed to be retrieved. +While lowering the PDT, compiler generated functions can be created in order to +compute this information. + +Note: The type description tables generated by semantics and used throughout the +runtime have component offsets as constants. Inlining component would require +this representation to be extended. + +**Fortran** +```fortran +! PDT with one level of inlined components. +type len_type1(i, j) + integer, len :: i, j + character(i+j) :: fld1 + character(j-i+2) :: fld2 +end type +``` + +#### Implementing PDT with outlined components + +A level of indirection can be used and `fld1` and `fld2` are then outlined +as shown in `len_type2`. _compiler_allocatable_ is here only to show which +components have an indirection. + +**Fortran** +```fortran +! PDT with one level of indirection. +type len_type2(i, j) + integer, len :: i, j + ! The two following components are not directly stored in the type but + ! allocatable components managed by the compiler. The + ! `compiler_managed_allocatable` is not a proper keyword but just added here + ! to have a better understanding. + character(i+j), compiler_managed_allocatable :: fld1 + character(j-i+2), compiler_managed_allocatable :: fld2 +end type +``` + +This solution has performance drawback because of the added indirections. It +also has to deal with compiler managed allocation/deallocation of the components +pointed by the indirections. + +These indirections are more problematic when we deal with array slice of derived +types as it could require temporaries depending how the memory is allocated. + +The outlined solution is also problematic for unformatted I/O as the +indirections need to be followed correctly when reading or writing records. + +#### Example of nested PDTs + +PDTs can be nested. Here are some example used later in the document. + +**Fortran** +```fortran +! PDT with second level of inlined components. +type len_type3(i, j) + integer, len :: i, j + character(2*j) :: name + type(len_type1(i*2, j+4)) :: field +end type + +! PDT with second level of indirection +type len_type4(i, j) + integer, len :: i, j + character(2*j), compiler_allocatable :: name + type(len_type2(i-1, 2**j)), compiler_allocatable :: field +end type +``` + +#### Example with array slice + +Let's take an example with an array slice to see the advantages and +disadvantages of the two solutions. + +For all derived types that do not have LEN type parameter (only have +compile-time constants) a standard descriptor can be set with the correct offset +and strides such that `array%field%fld2` can be encoded in the descriptor, is +not contiguous, and does not require a copy. This is what is implemented in +flang. + +**Fortran** +```fortran +! Declare arrays of PDTs +type(len_type3(exp1,exp2)) :: pdt_inlined_array(exp3) +type(len_type4(exp1,exp2)) :: pdt_outlined_array(exp3) + +! Passing/accessing a slice of PDTs array +pdt_inlined_array%field%fld2 +``` + +For a derived type with length type parameters inlined the expression +`pdt_inlined_array%field%fld2` can be encoded in the standard descriptor because +the components of `pdt_inlined_array` are inlined such that the array is laid +out with all its subcomponents in a contiguous range of memory. + +For the `pdt_outlined_array` array, the implementation has to insert several +level of indirections and therefore cannot be encoded in the standard +descriptor. +The different indirections levels break the property of the large contiguous +block in memory if the allocation is done for each components. This would make +the `pdt_outlined_array` a ragged array. The memory can also be allocated for +components with length type parameters while allocating the base object (in this +case the `pdt_outlined_array`). + +For each non-allocatable/non-pointer leaf automatic component of a PDT base +entity (`pdt_outlined_array` here) or a base entity containing PDTs, the +initialization will allocate a single block in memory for all the leaf +components reachable in the base entity (`pdt_outlined_array(i)%field%fld1`). +The size of this block will be `N * sizeof(leaf-component)` where `N` is the +multiplication of the size of each part-ref from the base entity to the leaf +component. The descriptor for each leaf component can then point to the correct +location in the block `block[i*sizeof(leaf-component)]`. + +Outlining the components has the advantage that the size of the PDTs are +compile-time constant as each field is encoded as a descriptor pointing to the +data. It has a disadvantage to require non-standard descriptors and comes with +additional runtime cost. + +With components inlining, the size of the PDTs are not compile-time constant. +This solution has the advantage to not add a performance drawback with +additional indirections but requires to compute the size of the descriptor +at runtime. +The size of the PDTs need to be computed at runtime. This is already the case +for dynamic allocation sizes since it is possible for arrays to have dynamic +shapes, etc. + +### Support of PDTs in other compilers + +1) Nested PDTs +2) Array of PDTs +3) Allocatable array of PDTs +4) Pointer to array section +5) Formatted I/O +6) Unformatted I/O +7) User-defined I/O +8) FINAL subroutine +9) ELEMENTAL FINAL subroutine + +| Compiler | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | +| --------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | +| gfortran | crash | ok | crash | ok | ok | ok | no | no | no | +| nag | ok | ok | ok | crash | ok | ok | ok | no | no | +| nvfortran | crash | ok | ok | ok | ok | ok | ok | ok | no | +| xlf | ok | ok | ok | ok | wrong | ok | wrong | no | no | +| ifort | ok | ok | ok | ok | ok | ok | ok | crash | crash | + +_Legends of results in the table_ +``` +ok = compile + run + good result +wrong = compile + run + wrong result +crash = compiler crash or runtime crash +no = doesn't compile with no crash +``` + +#### Field inlining in lowering + +A PDT with length type parameters has a list of 1 or more type parameters that +are runtime values. These length type parameter values can be present in +specification of other type parameters, array bounds expressions, etc. +All these expressions are integer specifications expressions and can be +evaluated at any given point with the length type parameters value of the PDT +instance. This is possible because constraints C750 and C754 from Fortran 2018 +standard that restrict what can appear in the specification expression. + +_note: C750 and C754 are partially enforced in the semantic at the moment._ + +These expressions can be lowered into small simple functions. For example, +the offset of `fld1` in `len_type1` could be 0; its size would be computed as +`sizeof(char) * (i+j)`. `size` can be lowered into a compiler generated +function. + +**FIR** +```c +// Example of compiler generated functions to compute offsets, size, etc. +// This is just an example and actual implementation might have more functions. + +// name field offset. +func.func @_len_type3.offset.name() -> index { + %0 = arith.constant 0 : index + return %0 : index +} + +// size for `name`: sizeof(char) * (2 * i) + padding +func.func @_len_type3.memsize.name(%i: index, %j: index) -> index { + %0 = arith.constant 2 : index + %1 = arith.constant 8 : index + %2 = arith.muli %0, %i : index + %3 = arith.muli %1, %2 : index + // padding not added here + return %3 : index +} + +// `fld` field offset. +func.func @_len_type3.offset.field(%i: index, %j: index) -> index { + %0 = call @_len_type3.offset.name() : () -> index + %1 = call @_len_type3.memsize.name(%i, %j) : (index, index) -> index + %2 = arith.addi %0, %1 : index + return %2 : index +} + +// 1st type parameter used for field `fld`: i*2 +func.func @_len_type3.field.typeparam.1(%i : index, %j : index) -> index { + %0 = arith.constant 2 : index + %1 = arith.muli %0, %i : index + return %1 : index +} + +// 2nd type parameter used for field `fld`: j+4 +func.func @_len_type3.field.typeparam.2(%i : index, %j : index) -> index { + %0 = arith.constant 4 : index + %1 = arith.addi %j, %0 : index + return %1 : index +} + +// `fld1` offset in `len_type1`. +func.func @_len_type1.offset.fld1() -> index { + %0 = arith.constant 0 : index + return %0 : index +} + +// size for `fld1`. +func.func @_len_type1.memsize.fld1(%i : index, %j : index) -> index { + %0 = arith.constant 8 : index + %1 = arith.addi %i, %j : index + %2 = arith.muli %0, %1 : index + return %2 : index +} + +// `fld2` offset in `len_type1`. +func.func @_len_type1.offset.fld2(%i : index, %j : index) -> index { + %0 = call @_len_type1.offset.fld1() : () -> index + %1 = call @_len_type1.memsize.fld1(%i, %j) : (index, index) -> index + %2 = arith.addi %0, %1 : index + return %2 : index +} +``` + +Access a field +```fortran +pdt_inlined_array(1)%field%fld2 +``` + +Example of offset computation in the PDTs. +```c +%0 = call @_len_type3.field.typeparam.1(%i, %j) : (index, index) -> index +%1 = call @_len_type3.field.typeparam.2(%i, %j) : (index, index) -> index +%2 = call @_len_type3.offset.fld(%i, %j) : (index, index) -> index +%3 = call @_len_type1.offset.fld2(%0, %1) : (index, index) -> index +%offset_of_1st_element = arith.addi %2, %3 : index +// Use the value computed offset_of_1st_element +``` + +In the case where the length type parameters values `(i,j)` are compile-time +constants then function inlining and constant folding will transform these +dependent types into statically defined types with no runtime cost. + +**Fortran** +```fortran +type t(l) + integer, len :: l + integer :: i(l) +end type + +type(t(n)), target :: a(10) +integer, pointer :: p(:) +p => a(:)%i(5) +``` + +When making a new descriptor like for pointer association, the `field_index` +operation can take the length type parameters needed for size/offset +computation. + +**FIR** +```c +%5 = fir.field_index i, !fir.type<_QMmod1Tt{l:i32,i:!fir.array}>(%n : i32) +``` + +### Length type parameter with expression + +The component of a PDT can be defined with expressions including the length +type parameters. + +**Fortran** +```fortran +type t1(n, m) + integer, len :: n = 2 + integer, len :: m = 4 + real :: data(n*m) +end type +``` + +The idea would be to replace the expression with an extra length type parameter +with a compiler generated name and a default value of `n*m`. All instance of the +expression would then reference the new name. + +**Fortran** +```fortran +type t1(n, m) + integer, len :: n = 2 + integer, len :: m = 4 + integer, len :: _t1_n_m = 8 ! hidden extra length type parameter + real :: data(_t1_n_m) +end type +``` + +At any place where the a PDT is initialized, the lowering would make the +evaluation and their values saved in the addendum and pointed to by the +descriptor. + +### `ALLOCATE`/`DEALLOCATE` statements + +The allocation and deallocation of PDTs are delegated to the runtime. + +The corresponding function can be found in +`flang/include/flang/Runtime/allocatable.h` and +`flang/include/flang/Runtime/pointer.h` for pointer allocation. + +`ALLOCATE` + +The `ALLOCATE` statement is lowered to a sequence of function calls as shown in +the example below. + +**Fortran** +```fortran +type t1(i) + integer, len :: i = 4 + character(i) :: c +end type + +type(t1), allocatable :: t +type(t1), pointer :: p + +allocate(t1(2)::t) +allocate(t1(2)::p) +``` + +**FIR** +```c +// For allocatable +%5 = fir.call @_FortranAAllocatableInitDerived(%desc, %type) : (!fir.box, ) -> () +// The AllocatableSetDerivedLength functions is called for each length type parameters. +%6 = fir.call @_FortranAAllocatableSetDerivedLength(%desc, %pos, %value) : (!fir.box, i32, i64) -> () +%7 = fir.call @_FortranAAllocatableAllocate(%3) : (!fir.box) -> () + +// For pointer +%5 = fir.call @_FortranAPointerNullifyDerived(%desc, %type) : (!fir.box, ) -> () +// The PointerSetDerivedLength functions is called for each length type parameters. +%6 = fir.call @_FortranAPointerSetDerivedLength(%desc, %pos, %value) : (!fir.box, i32, i64) -> () +%7 = fir.call @_FortranAPointerAllocate(%3) : (!fir.box) -> () +``` + +`DEALLOCATE` + +The `DEALLOCATE` statement is lowered to a runtime call to +`AllocatableDeallocate` and `PointerDeallocate` for pointers. + +**Fortran** +```fortran +deallocate(pdt1) +``` + +**FIR** +```c +// For allocatable +%8 = fir.call @_FortranAAllocatableDeallocate(%desc1) : (!fir.box) -> (i32) + +// For pointer +%8 = fir.call @_FortranAPointerDeallocate(%desc1) : (!fir.box) -> (i32) +``` + +### `NULLIFY` + +The `NULLIFY` statement is lowered to a call to the corresponding runtime +function `PointerNullifyDerived` in `flang/include/flang/Runtime/pointer.h`. + +**Fortran** +```fortran +NULLIFY(p) +``` + +**FIR** +```c +%0 = fir.call @_FortranAPointerNullifyDerived(%desc, %type) : (!fir.box, !fir.tdesc) -> () +``` + +### Formatted I/O + +The I/O runtime internals are described in this file: +`flang/docs/IORuntimeInternals.md`. + +When an I/O statement with a derived-type is encountered in lowering, the +derived-type is emboxed in a descriptor if it is not already and a call to the +runtime library is issued with the descriptor (as shown in the example below). +The function is `_FortranAioOutputDescriptor`. The call make a call to +`FormattedDerivedTypeIO` in `flang/runtime/descriptor-io.h` for derived-type. +This function will need to be updated to support the chosen solution for PDTs. + +**Fortran** +```fortran +type t + integer, len :: l + integer :: i(l) = 42 +end type + +! ... + +subroutine print_pdt + type(t(10)) :: x + print*, x +end subroutine +``` + +**FIR** +```c +func.func @_QMpdtPprint_pdt() { + %l = arith.constant = 10 + %0 = fir.alloca !fir.type<_QMpdtTt{l:i32,i:!fir.array}> (%l : i32) {bindc_name = "x", uniq_name = "_QMpdt_initFlocalEx"} + %1 = fir.embox %0 : (!fir.ref}>>) (typeparams %l : i32) -> !fir.box}>> + %2 = fir.address_of(@_QQcl.2E2F6669725F7064745F6578616D706C652E66393000) : !fir.ref> + %c8_i32 = arith.constant 8 : i32 + %3 = fir.convert %1 : (!fir.box}>>) -> !fir.box + %4 = fir.convert %2 : (!fir.ref>) -> !fir.ref + %5 = fir.call @_FortranAInitialize(%3, %4, %c8_i32) : (!fir.box, !fir.ref, i32) -> none + %c-1_i32 = arith.constant -1 : i32 + %6 = fir.address_of(@_QQcl.2E2F6669725F7064745F6578616D706C652E66393000) : !fir.ref> + %7 = fir.convert %6 : (!fir.ref>) -> !fir.ref + %c10_i32 = arith.constant 10 : i32 + %8 = fir.call @_FortranAioBeginExternalListOutput(%c-1_i32, %7, %c10_i32) : (i32, !fir.ref, i32) -> !fir.ref + %9 = fir.embox %0 : (!fir.ref}>>) (typeparams %l : i32) -> !fir.box}>> + %10 = fir.convert %9 : (!fir.box}>>) -> !fir.box + %11 = fir.call @_FortranAioOutputDescriptor(%8, %10) : (!fir.ref, !fir.box) -> i1 + %12 = fir.call @_FortranAioEndIoStatement(%8) : (!fir.ref) -> i32 + return +} +``` + +### Unformatted I/O + +The entry point in the runtime for unformatted I/O is similar than the one for +formatted I/O. A call to `_FortranAioOutputDescriptor` with the correct +descriptor is also issued by the lowering. For unformatted I/O, the runtime is +calling `UnformattedDescriptorIO` from `flang/runtime/descriptor-io.h`. +This function will need to be updated to support the chosen solution for PDTs. + +### Default component initialization of local variables + +Default initializers for components with length type parameters need to be +processed as the derived type instance is created. +The length parameters block must also be created and attached to the addendum. +See _New f18addendum_ section for more information. + +### Assignment + +As mentioned in 10.2.1.2 (8), for an assignment, each length type parameter of +the variable shall have the same value as the corresponding type parameter +unless the lhs is allocatable. + +**Fortran** +```fortran +type t(l) + integer, len :: l + integer :: i(l) +end type + +! ... + +type(t(10)) :: a, b +type(t(20)) :: c +type(t(:)), allocatable :: d +a = b ! Legal assignment +c = b ! Illegal assignment because `c` does not have the same length type + ! parameter value than `b`. +d = c ! Legal because `d` is allocatable +``` + +A simple intrinsic assignment without allocatable or pointer follows the same +path than the traditional derived-type (addressing of component is different) +since the length type parameter values are identical and do not need to be +copied or reallocated. The length type parameters values are retrieved when +copying the data. + +Assignment of PDTs with allocatable or pointer components are done with the help +of the runtime. A call to `_FortranAAssign` is done with the lhs and rhs +descriptors. The length type parameters are available in the descriptors. + +For allocatable PDTs, if the rhs side has different length type parameters than +the lhs, it is deallocated first and allocated with the rhs length type +parameters information (F'2018 10.2.1.3(3)). There is code in the runtime to +handle this already. It will need to be updated for the new f18addendum. + +### Finalization + +A final subroutine is called for a PDT if the subroutine has the same kind type +parameters and rank as the entity to be finalized. The final subroutine is +called with the entity as the actual argument. +If there is an elemental final subroutine whose dummy argument has the same kind +type parameters as the entity to be finalized, or a final subroutine whose dummy +argument is assumed-rank with the same kind type parameters as the entity to be +finalized, the subroutine is called with the entity as the actual argument. +Otherwise, no subroutine is called. + +**Example from the F2018 standard** +```fortran +module m + + type t(k) + integer, kind :: k + real(k), pointer :: vector(:) => NULL() + contains + final :: finalize_t1s, finalize_t1v, finalize_t2e + end type + +contains + + subroutine finalize_t1s(x) + type(t(kind(0.0))) x + if (associated(x%vector)) deallocate(x%vector) + END subroutine + + subroutine finalize_t1v(x) + type(t(kind(0.0))) x(:) + do i = lbound(x,1), ubound(x,1) + if (associated(x(i)%vector)) deallocate(x(i)%vector) + end do + end subroutine + + elemental subroutine finalize_t2e(x) + type(t(kind(0.0d0))), intent(inout) :: x + if (associated(x%vector)) deallocate(x%vector) + end subroutine +end module + +subroutine example(n) +use m + +type(t(kind(0.0))) a, b(10), c(n,2) +type(t(kind(0.0d0))) d(n,n) +... +! Returning from this subroutine will effectively do +! call finalize_t1s(a) +! call finalize_t1v(b) +! call finalize_t2e(d) +! No final subroutine will be called for variable C because the user +! omitted to define a suitable specific procedure for it. +end subroutine +``` + +### Type parameter inquiry + +Type parameter inquiry is used to get the value of a type parameter in a PDT. + +**Fortran** +```fortran +module t +type t1(i, j) + integer, len :: i = 4 + integer, len :: j = 2 + character(i*j) :: c +end type +end + +program main +use t +type(t1(2, 2)) :: ti +print*, ti%c%len +print*, ti%i +print*, ti%j +end + +! Should print: +! 4 +! 2 +! 2 +``` + +These values are present in the `f18Addendum` and can be retrieved from it with +the correct index. If the length type parameter for a field is an expression, +a compiler generated function is used to computed its value. +The length type parameters are indexed in declaration order; i.e., 0 is the +first length type parameter in the deepest base type. + +### PDTs and polymorphism + +In some cases with polymorphic entities, it is necessary to copy the length +type parameters from a descriptor to another. With the current design this is +not possible since the descriptor cannot be reallocated and the addendum is +allocated with a fixed number of length type parameters. + +**Fortran** +```fortran +! The example below illustrates a case where the number of length type +! parameters are different and need to be copied to an existing descriptor +! addendum. +module m1 +type t1 + integer :: i +end type + +! This type could be defined in another compilation unit. +type, extends(t1) :: t2(l1, l2) + integer, len :: l1, l2 +end type + +contains + +subroutine reallocate(x) + class(t1), allocatable :: x + allocate(t2(l1=1, l2=2):: x) +end subroutine + +end module + +program p + use m1 + + class(t1), allocatable :: x + + call reallocate(x) + ! The new length type parameters need to be propagated at this point. + + ! rest of code using `x` +end program +``` + +The proposed solution is to add indirection in the `f18Addendum` and store the +length type parameters in a separate block instead of directly in the addendum. +At the moment the storage for the length type parameters is allocated once as +a `std::int64_t` array. + +**New f18Addendum** +```cpp +{*derivedType_, *lenParamValues_} +``` + +Adding the indirection in the descriptor's addendum requires to manage the +lifetime of the block holding the length type parameter values. + +Here are some thoughts of how to manage it: +- For allocatables, the space for the LEN parameters can be allocated as part of + the same malloc as the payload data. +- For automatics, same thing, if we implement automatics as allocatables. +- For monomorphic local variables, the LEN parameters would be in a little array + on the stack. Or we could treat any variable or component with LEN parameters + as being automatic even when it's monomorphic. +- For pointers and dummy arguments, we can just copy the pointer in the addendum + from the target to the pointer or dummy descriptor. +- For dynamically allocated descriptors, the LEN parameter values could just + follow the addendum in the same malloc. + +The addendum of an array sections/sub-objects would point to the same block than +the base object. + +In some special cases, a descriptor needs to be passed between the caller and +the callee. This includes array of PDTs and derived-type with PDT components. +The example describe one of the corner case where the length type parameter +would be lost if the descriptor is not passed. + +### Example that require a descriptor + +Because of the length type parameters store in the addendum, it is required in +some case to pass the PDT with a descriptor to preserve the length type +parameters information. The example below illustrates such a case. + +**Fortran** +```fortran +module m +type t + integer :: i +end type + +type, extends(t) :: t2(l) + integer, len :: l + real :: x(l) +end type + +type base + type(t2(20)) :: pdt_component +end type + +class(t), pointer :: p(:) + +contains + +subroutine foo(x, n) + integer :: n + type(base), target :: x(n) + ! Without descriptor, the actual argument is a zero-sized array. The length + ! type parameters of `x(n)%pdt_component` are not propagated from the caller. + + ! A descriptor local to this function is created to pass the array section + ! in bar. + call bar(x%pdt_component) +end subroutine + +subroutine bar(x) + type(t2(*)), target :: x(:) + p => x +end subroutine + +subroutine test() + type(base), target :: x(100) + call foo(x(1:-1:1), 0) + select type (p) + type is (t2(*)) + ! This type parameters of x(1:60:3) in foo must still live here + print *, p%l + class default + print *, "something else" + end select +end subroutine +end module + + use m + call test() +end +``` + +Because of the use case described above, PDTs, array of PDTs or derived-type +with PDT components will be passed by descriptor. + +## FIR operations with length type parameters + +Couple of operations have length type parameters as operands already in their +design. For some operations, length type parameters are likely needed with +the two proposed solution. Some other operation like the array operations, the +operands are not needed when dealing with a descriptor since the length type +parameters are in it. + +The operations will be updated if needed during the implementation of the +chosen solution. + +#### `fir.alloca` + +This primitive operation is used to allocate an object on the stack. When +allocating a PDT, the length type parameters are passed to the +operation so its size can be computed accordingly. + +**FIR** +```c +%i = arith.constant 10 : i32 +%0 = fir.alloca !fir.type<_QMmod1Tpdt{i:i32,data:!fir.array}> (%i : i32) +// %i is the ssa value of the length type parameter +``` + +#### `fir.allocmem` + +This operation is used to create a heap memory reference suitable for storing a +value of the given type. When creating a PDT, the length type parameters are +passed so the size can be computed accordingly. + +**FIR** +```c +%i = arith.constant 10 : i32 +%0 = fir.alloca !fir.type<_QMmod1Tpdt{i:i32,data:!fir.array}> (%i : i32) +// ... +fir.freemem %0 : !fir.type<_QMmod1Tpdt{i:i32,data:!fir.array}> +``` + +#### `fir.embox` + +The `fir.embox` operation create a boxed reference value. In the case of PDTs +the length type parameters can be passed as well to the operation. + +**Fortran** +```fortran +subroutine local() + type(t(2)) :: x ! simple local PDT + ! ... +end subroutine +``` + +**FIR** +```c +func.func @_QMpdt_initPlocal() { + %c2_i32 = arith.constant 2 : i32 + %0 = fir.alloca !fir.type<_QMpdt_initTt{l:i32,i:!fir.array}> (%c2 : i32) + {bindc_name = "x", uniq_name = "_QMpdt_initFlocalEx"} + // The fir.embox operation is responsible to place the provided length type + // parameters in the descriptor addendum so they are available to the runtime + // call later. + %1 = fir.embox %0 : (!fir.ref}>>) (typeparams %c2 : i32) + -> !fir.box}>> + %2 = fir.address_of(@_QQcl.2E2F6669725F7064745F6578616D706C652E66393000) : !fir.ref> + %c8_i32 = arith.constant 8 : i32 + %3 = fir.convert %1 : (!fir.box}>>) -> !fir.box + %4 = fir.convert %2 : (!fir.ref>) -> !fir.ref + %5 = fir.call @_FortranAInitialize(%3, %4, %c8_i32) : (!fir.box, !fir.ref, i32) -> none + return +} +``` + +#### `fir.field_index` + +The `fir.field_index` operation is used to generate a field offset value from +a field identifier in a derived-type. The operation takes length type parameter +values with a PDT so it can compute a correct offset. + +**FIR** +```c +%l = arith.constant 10 : i32 +%1 = fir.field_index i, !fir.type<_QMpdt_initTt{l:i32,i:i32}> (%l : i32) +%2 = fir.coordinate_of %ref, %1 : (!fir.type<_QMpdt_initTt{l:i32,i:i32}>, !fir.field) -> !fir.ref +%3 = fir.load %2 : !fir.ref +return %3 +``` + +#### `fir.len_param_index` + +This operation is used to get the length type parameter offset in from a PDT. + +**FIR** +```c +func.func @_QPpdt_len_value(%arg0: !fir.box}>>) -> i32 { + %0 = fir.len_param_index l, !fir.box}>> + %1 = fir.coordinate_of %arg0, %0 : (!fir.box}>>, !fir.len) -> !fir.ref + %2 = fir.load %1 : !fir.ref + return %2 : i32 +} +``` + +#### `fir.save_result` + +Save the result of a function returning an array, box, or record type value into +a memory location given the shape and LEN parameters of the result. Length type +parameters is passed if the PDT is not boxed. + +**FIR** +```c +func.func @return_pdt(%buffer: !fir.ref>) { + %l1 = arith.constant 3 : i32 + %l2 = arith.constant 5 : i32 + %res = fir.call @foo() : () -> !fir.type + fir.save_result %res to %buffer typeparams %l1, %l2 : !fir.type, !fir.ref>, i32, i32 + return +} +``` + +#### `fir.array_*` operations + +The current design of the different `fir.array_*` operations include length type +parameters operands. This is designed to use PDT without descriptor directly in +FIR. + +**FIR** +```c +// Operation used with a boxed PDT does not need the length type parameters as +// they are directly retrieved from the box. +%0 = fir.array_coor %boxed_pdt, %i, %j (fir.box}>>>>, index, index) -> !fir.ref}>>> + +// In case the PDT would not be boxed, the length type parameters are needed to +// compute the correct addressing. +%0 = fir.array_coor %pdt_base, %i, %j typeparams %l (fir.ref}>>>>, index, index, index) -> !fir.ref> +``` + +--- + +## Implementation choice + +While both solutions have pros and cons, we want to implement the outlined +solution. +- The runtime was implemented with this solution in mind. +- The size of the descriptor does not need to be computed at runtime. + +--- + +# Testing + +- Lowering part is tested with LIT tests in tree +- PDTs involved a lot of runtime information so executable + tests will be useful for full testing. + +--- + +# Current TODOs +Current list of TODOs in lowering: +- `flang/lib/Lower/Allocatable.cpp:461` not yet implement: derived type length parameters in allocate +- `flang/lib/Lower/Allocatable.cpp:645` not yet implement: deferred length type parameters +- `flang/lib/Lower/Bridge.cpp:454` not yet implemented: get length parameters from derived type BoxValue +- `flang/lib/Lower/ConvertExpr.cpp:341` not yet implemented: copy derived type with length parameters +- `flang/lib/Lower/ConvertExpr.cpp:993` not yet implemented: component with length parameters in structure constructor +- `flang/lib/Lower/ConvertExpr.cpp:1063` not yet implemented: component with length parameters in structure constructor +- `flang/lib/Lower/ConvertExpr.cpp:1146` not yet implemented: type parameter inquiry +- `flang/lib/Lower/ConvertExpr.cpp:2424` not yet implemented: creating temporary for derived type with length parameters +- `flang/lib/Lower/ConvertExpr.cpp:3742` not yet implemented: gather rhs LEN parameters in assignment to allocatable +- `flang/lib/Lower/ConvertExpr.cpp:4725` not yet implemented: derived type array expression temp with LEN parameters +- `flang/lib/Lower/ConvertExpr.cpp:6400` not yet implemented: PDT size +- `flang/lib/Lower/ConvertExpr.cpp:6419` not yet implemented: PDT offset +- `flang/lib/Lower/ConvertExpr.cpp:6679` not yet implemented: array expr type parameter inquiry +- `flang/lib/Lower/ConvertExpr.cpp:7135` not yet implemented: need to adjust type parameter(s) to reflect the final component +- `flang/lib/Lower/ConvertType.cpp:334` not yet implemented: parameterized derived types +- `flang/lib/Lower/ConvertType.cpp:370` not yet implemented: derived type length parameters +- `flang/lib/Lower/ConvertVariable.cpp:169` not yet implemented: initial-data-target with derived type length parameters +- `flang/lib/Lower/ConvertVariable.cpp:197` not yet implemented: initial-data-target with derived type length parameters +- `flang/lib/Lower/VectorSubscripts.cpp:121` not yet implemented: threading length parameters in field index op +- `flang/lib/Optimizer/Builder/BoxValue.cpp:60` not yet implemented: box value is missing type parameters +- `flang/lib/Optimizer/Builder/BoxValue.cpp:67` not yet implemented: mutable box value is missing type parameters +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:688` not yet implemented: read fir.box with length parameters +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:746` not yet implemented: generate code to get LEN type parameters +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:779` not yet implemented: derived type with type parameters +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:905` not yet implemented: allocatable and pointer components non deferred length parameters +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:917` not yet implemented: array component shape depending on length parameters +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:924` not yet implemented: get character component length from length type parameters +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:934` not yet implemented: lower component ref that is a derived type with length parameter +- `flang/lib/Optimizer/Builder/FIRBuilder.cpp:956` not yet implemented: get length parameters from derived type BoxValue +- `flang/lib/Optimizer/Builder/MutableBox.cpp:70` not yet implemented: updating mutablebox of derived type with length parameters +- `flang/lib/Optimizer/Builder/MutableBox.cpp:168` not yet implemented: read allocatable or pointer derived type LEN parameters +- `flang/lib/Optimizer/Builder/MutableBox.cpp:310` not yet implemented: update allocatable derived type length parameters +- `flang/lib/Optimizer/Builder/MutableBox.cpp:505` not yet implemented: pointer assignment to derived with length parameters +- `flang/lib/Optimizer/Builder/MutableBox.cpp:597` not yet implemented: pointer assignment to derived with length parameters +- `flang/lib/Optimizer/Builder/MutableBox.cpp:740` not yet implemented: reallocation of derived type entities with length parameters + + +Current list of TODOs in code generation: + +- `flang/lib/Optimizer/CodeGen/CodeGen.cpp:1034` not yet implemented: fir.allocmem codegen of derived type with length parameters +- `flang/lib/Optimizer/CodeGen/CodeGen.cpp:1581` not yet implemented: generate call to calculate size of PDT +- `flang/lib/Optimizer/CodeGen/CodeGen.cpp:1708` not yet implemented: fir.embox codegen of derived with length parameters +- `flang/lib/Optimizer/CodeGen/CodeGen.cpp:1749` not yet implemented: reboxing descriptor of derived type with length parameters +- `flang/lib/Optimizer/CodeGen/CodeGen.cpp:2229` not yet implemented: derived type with type parameters +- `flang/lib/Optimizer/CodeGen/CodeGen.cpp:2256` not yet implemented: compute size of derived type with type parameters +- `flang/lib/Optimizer/CodeGen/TypeConverter.h:257` not yet implemented: extended descriptor derived with length parameters + +Current list of TODOs in optimizations: + +- `flang/lib/Optimizer/Transforms/ArrayValueCopy.cpp:1007` not yet implemented: unhandled dynamic type parameters + +--- + +Resources: +- [0] Fortran standard +- [1] https://en.wikipedia.org/wiki/Dependent_type