[flang][docs] Add lowering design doc for parameterized derived-type

[clementval]

Summary

This document aims to give insights at the representation of parameterized
derived-type (PDTs) in FIR and how PDTs are lowered to FIR and interact
with the runtime.

[jeanPerier]

Thanks for writing all this down !

flang/docs/ParameterizedDerivedTypes.md

217

"to rely" -> "to not rely" ?

824

"will " -> "will be updated" ?

[kiranchandramohan]

Thanks, @clementval for this detailed Design Document. I did a quick read and have a few nit comments or questions.

flang/docs/ParameterizedDerivedTypes.md

24

109

Nit: The parameters are missing here.

125

Nit: The parameters are missing here.

153

Nit: parameters are missing here.

160

Nit: parameters are missing here.

674

687

824

Nit: Something is missing in this sentence.

825

In all the following operations could you clarify whether any operation is being extended to accomodate type parameters?

927

I understand that no change is proposed here but is the typeparams field required here give that both res and buffer have the parameters in their type?

932

Are any changes required for the ArrayValueCopy pass?

[clementval]

Address review comments

flang/docs/ParameterizedDerivedTypes.md

825

The operation design is already accommodating type parameters. Lowering and codegen will need to use them accordingly.

927

the actual length parameters value is available only if the buffer or res is boxed since they are stored in the addendum.

932

Likely not in term of design but any part that is handling type parameter right now will need to be double check and adapted to the chosen solution and implementation.

[klausler]

flang/docs/ParameterizedDerivedTypes.md

143

It turned out that the runtime had to traverse components anyway in order to perform byte-swapped unformatted I/O, so this part is already done now.

flang/docs/ParameterizedDerivedTypes.md

+# 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<?xi32>}>(%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<none>, ) -> ()
+// The AllocatableSetDerivedLength functions is called for each length type parameters.
+%6 = fir.call @_FortranAAllocatableSetDerivedLength(%desc, %pos, %value) : (!fir.box<none>, i32, i64) -> ()
+%7 = fir.call @_FortranAAllocatableAllocate(%3) : (!fir.box<none>) -> ()
+
+// For pointer
+%5 = fir.call @_FortranAPointerNullifyDerived(%desc, %type) : (!fir.box<none>, ) -> ()
+// The PointerSetDerivedLength functions is called for each length type parameters.
+%6 = fir.call @_FortranAPointerSetDerivedLength(%desc, %pos, %value) : (!fir.box<none>, i32, i64) -> ()
+%7 = fir.call @_FortranAPointerAllocate(%3) : (!fir.box<none>) -> ()
+```
+
+`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<none>) -> (i32)
+
+// For pointer
+%8 = fir.call @_FortranAPointerDeallocate(%desc1) : (!fir.box<none>) -> (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<none>, !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<?xi32>}> (%l : i32) {bindc_name = "x", uniq_name = "_QMpdt_initFlocalEx"}
+  %1 = fir.embox %0 : (!fir.ref<!fir.type<_QMpdtTt{l:i32,i:!fir.array<?xi32>}>>) (typeparams %l : i32) -> !fir.box<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<2xi32>}>> 
+  %2 = fir.address_of(@_QQcl.2E2F6669725F7064745F6578616D706C652E66393000) : !fir.ref<!fir.char<1,22>>
+  %c8_i32 = arith.constant 8 : i32
+  %3 = fir.convert %1 : (!fir.box<!fir.type<_QMpdtTt{l:i32,i:!fir.array<?xi32>}>>) -> !fir.box<none>
+  %4 = fir.convert %2 : (!fir.ref<!fir.char<1,22>>) -> !fir.ref<i8>
+  %5 = fir.call @_FortranAInitialize(%3, %4, %c8_i32) : (!fir.box<none>, !fir.ref<i8>, i32) -> none
+  %c-1_i32 = arith.constant -1 : i32
+  %6 = fir.address_of(@_QQcl.2E2F6669725F7064745F6578616D706C652E66393000) : !fir.ref<!fir.char<1,22>>
+  %7 = fir.convert %6 : (!fir.ref<!fir.char<1,22>>) -> !fir.ref<i8>
+  %c10_i32 = arith.constant 10 : i32
+  %8 = fir.call @_FortranAioBeginExternalListOutput(%c-1_i32, %7, %c10_i32) : (i32, !fir.ref<i8>, i32) -> !fir.ref<i8>
+  %9 = fir.embox %0 : (!fir.ref<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>) (typeparams %l : i32) -> !fir.box<!fir.type<_QMpdtTt{l:i32,i:!fir.array<?xi32>}>>
+  %10 = fir.convert %9 : (!fir.box<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>) -> !fir.box<none>
+  %11 = fir.call @_FortranAioOutputDescriptor(%8, %10) : (!fir.ref<i8>, !fir.box<none>) -> i1
+  %12 = fir.call @_FortranAioEndIoStatement(%8) : (!fir.ref<i8>) -> 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<?xf32>}> (%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<?xf32>}> (%i : i32)
+// ...
+fir.freemem %0 : !fir.type<_QMmod1Tpdt{i:i32,data:!fir.array<?xf32>}>
+```
+
+#### `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<?xi32>}> (%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<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>) (typeparams %c2 : i32)
+       -> !fir.box<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>
+  %2 = fir.address_of(@_QQcl.2E2F6669725F7064745F6578616D706C652E66393000) : !fir.ref<!fir.char<1,22>>
+  %c8_i32 = arith.constant 8 : i32
+  %3 = fir.convert %1 : (!fir.box<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>) -> !fir.box<none>
+  %4 = fir.convert %2 : (!fir.ref<!fir.char<1,22>>) -> !fir.ref<i8>
+  %5 = fir.call @_FortranAInitialize(%3, %4, %c8_i32) : (!fir.box<none>, !fir.ref<i8>, 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<i32>
+%3 = fir.load %2 : !fir.ref<i32>
+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<!fir.type<t1{l:i32,!fir.array<?xi32>}>>) -> i32 {
+  %0 = fir.len_param_index l, !fir.box<!fir.type<t1{l:i32,!fir.array<?xi32>}>>
+  %1 = fir.coordinate_of %arg0, %0 : (!fir.box<!fir.type<t1{l:i32,!fir.array<?xi32>}>>, !fir.len) -> !fir.ref<i32>
+  %2 = fir.load %1 : !fir.ref<i32>
+  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<!fir.type<t2(l1:i32,l2:i32){x:f32}>>) {
+  %l1 = arith.constant 3 : i32
+  %l2 = arith.constant 5 : i32
+  %res = fir.call @foo() : () -> !fir.type<t2(l1:i32,l2:i32){x:f32}>
+  fir.save_result %res to %buffer typeparams %l1, %l2 : !fir.type<t2(l1:i32,l2:i32){x:f32}>, !fir.ref<!fir.type<t2(l1:i32,l2:i32){x:f32}>>, 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<fir.array<?x?xfir.type<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>>>, index, index) -> !fir.ref<fir.type<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>>
+
+// 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<fir.array<?x?xfir.type<!fir.type<_QMpdt_initTt{l:i32,i:!fir.array<?xi32>}>>>>, index, index, index) -> !fir.ref<fir.type<PDT>>
+```
+
+---
+
+## 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