diff --git a/flang/docs/FIRArrayOperations.md b/flang/docs/FIRArrayOperations.md new file mode 100644 --- /dev/null +++ b/flang/docs/FIRArrayOperations.md @@ -0,0 +1,342 @@ + + +# Design: FIR Array operations + +```eval_rst +.. contents:: + :local: +``` + +## General + +The array operations in FIR model the copy-in/copy-out semantics over Fortran +statements. + +Fortran language semantics sometimes require the compiler to make a temporary +copy of an array or array slice. Situations where this can occur include: + +* Passing a non-contiguous array to a procedure that does not declare it as + assumed-shape. +* Array expressions, especially those involving `RESHAPE`, `PACK`, and `MERGE`. +* Assignments of arrays where the array appears on both the left and right-hand + sides of the assignment. +* Assignments of `POINTER` arrays. + +There are currently the following operations: +- `fir.array_load` +- `fir.array_merge_store` +- `fir.array_fetch` +- `fir.array_update` +- `fir.array_access` +- `fir.array_amend` + +`array_load`(s) and `array_merge_store` are a pairing that brackets the lifetime +of the array copies. + +`array_fetch` and `array_update` are defined to work as getter/setter pairs on +values of elements from loaded array copies. These have "GEP-like" syntax and +semantics. + +Fortran arrays are implicitly memory bound as are some other Fortran type/kind +entities. For entities that can be atomically promoted to the value domain, +we use `array_fetch` and `array_update`. + +`array_access` and `array_amend` are defined to work as getter/setter pairs on +references to elements in loaded array copies. `array_access` has "GEP-like" +syntax. `array_amend` annotates which loaded array copy is being written to. +It is invalid to update an array copy without `array_amend`; doing so will +result in undefined behavior. +For those type/kinds that cannot be promoted to values, we must leave them in a +memory reference domain, and we use `array_access` and `array_amend`. + +## array_load + +This operation taken with `array_merge_store` captures Fortran's +copy-in/copy-out semantics. One way to think of this is that array_load +creates a snapshot copy of the entire array. This copy can then be used +as the "original value" of the array while the array's new value is +computed. The `array_merge_store` operation is the copy-out semantics, which +merge the updates with the original array value to produce the final array +result. This abstracts the copy operations as opposed to always creating +copies or requiring dependence analysis be performed on the syntax trees +and before lowering to the IR. + +Load an entire array as a single SSA value. + +```fortran + real :: a(o:n,p:m) + ... + ... = ... a ... +``` + +One can use `fir.array_load` to produce an ssa-value that captures an +immutable value of the entire array `a`, as in the Fortran array expression +shown above. Subsequent changes to the memory containing the array do not +alter its composite value. This operation lets one load an array as a +value while applying a runtime shape, shift, or slice to the memory +reference, and its semantics guarantee immutability. + +```mlir +%s = fir.shape_shift %lb1, %ex1, %lb2, %ex2 : (index, index, index, index) -> !fir.shape<2> +// load the entire array 'a' +%v = fir.array_load %a(%s) : (!fir.ref>, !fir.shape<2>) -> !fir.array +// a fir.store here into array %a does not change %v +``` + +# array_merge_store + +The `array_merge_store` operation stores a merged array value to memory. + + +```fortran + real :: a(n,m) + ... + a = ... +``` + +One can use `fir.array_merge_store` to merge/copy the value of `a` in an +array expression as shown above. + +```mlir + %v = fir.array_load %a(%shape) : ... + %r = fir.array_update %v, %f, %i, %j : (!fir.array, f32, index, index) -> !fir.array + fir.array_merge_store %v, %r to %a : !fir.ref> +``` + +This operation merges the original loaded array value, `%v`, with the +chained updates, `%r`, and stores the result to the array at address, `%a`. + +This operation taken with `array_load`'s captures Fortran's +copy-in/copy-out semantics. The first operands of `array_merge_store` is the +result of the initial `array_load` operation. While this value could be +retrieved by reference chasiing through the different array operations it is +useful to have it on hand directly for analysis passes since this directly +defines the "bounds" of the Fortran statement represented by these operations. +The intention is to allow copy-in/copy-out regions to be easily delineated, +analyzed, and optimized. + +## array_fetch + +The `array_fetch` operation fetches the value of an element in an array value. + +```fortran + real :: a(n,m) + ... + ... a ... + ... a(r,s+1) ... +``` + +One can use `fir.array_fetch` to fetch the (implied) value of `a(i,j)` in +an array expression as shown above. It can also be used to extract the +element `a(r,s+1)` in the second expression. + +```mlir + %s = fir.shape %n, %m : (index, index) -> !fir.shape<2> + // load the entire array 'a' + %v = fir.array_load %a(%s) : (!fir.ref>, !fir.shape<2>) -> !fir.array + // fetch the value of one of the array value's elements + %1 = fir.array_fetch %v, %i, %j : (!fir.array, index, index) -> f32 +``` + +It is only possible to use `array_fetch` on an `array_load` result value or a +value that can be trace back transitively to an `array_load` as the dominating +source. Other array operation such as `array_update` can be in between. + +## array_update + +The `array_update` operation is used to update the value of an element in an +array value. A new array value is returned where all element values of the input +array are identical except for the selected element which is the value passed in +the update. + +```fortran + real :: a(n,m) + ... + a = ... +``` + +One can use `fir.array_update` to update the (implied) value of `a(i,j)` +in an array expression as shown above. + +```mlir + %s = fir.shape %n, %m : (index, index) -> !fir.shape<2> + // load the entire array 'a' + %v = fir.array_load %a(%s) : (!fir.ref>, !fir.shape<2>) -> !fir.array + // update the value of one of the array value's elements + // %r_{ij} = %f if (i,j) = (%i,%j), %v_{ij} otherwise + %r = fir.array_update %v, %f, %i, %j : (!fir.array, f32, index, index) -> !fir.array + fir.array_merge_store %v, %r to %a : !fir.ref> +``` + +An array value update behaves as if a mapping function from the indices +to the new value has been added, replacing the previous mapping. These +mappings can be added to the ssa-value, but will not be materialized in +memory until the `fir.array_merge_store` is performed. +`fir.array_update` can be seen as an array access with a notion that the array +will be changed at the accessed position when `fir.array_merge_store` is +performed. + +## array_access + +The `array_access` provides a reference to a single element from an array value. +This is *not* a view in the immutable array, otherwise it couldn't be stored to. +It can be see as a logical copy of the element and its position in the array. +Tis reference can be written to and modified withoiut changing the original +array. + +The `array_access` operation is used to fetch the memory reference of an element +in an array value. + +```fortran + real :: a(n,m) + ... + ... a ... + ... a(r,s+1) ... +``` + +One can use `fir.array_access` to recover the implied memory reference to +the element `a(i,j)` in an array expression `a` as shown above. It can also +be used to recover the reference element `a(r,s+1)` in the second +expression. + +```mlir + %s = fir.shape %n, %m : (index, index) -> !fir.shape<2> + // load the entire array 'a' + %v = fir.array_load %a(%s) : (!fir.ref>, !fir.shape<2>) -> !fir.array + // fetch the value of one of the array value's elements + %1 = fir.array_access %v, %i, %j : (!fir.array, index, index) -> !fir.ref +``` + +It is only possible to use `array_access` on an `array_load` result value or a +value that can be trace back transitively to an `array_load` as the dominating +source. Other array operation such as `array_amend` can be in between. + +`array_access` if mainly used with `character`'s arrays and arrays of derived +types where because they might have a non-compile time sizes that would be +useless too load entirely or too big to load. + +Here is a simple example with a `character` array assignment. + +Fortran +``` +subroutine foo(c1, c2, n) + integer(8) :: n + character(n) :: c1(:), c2(:) + c1 = c2 +end subroutine +``` + +It results in this cleaned-up FIR: +``` +func @_QPfoo(%arg0: !fir.box>>, %arg1: !fir.box>>, %arg2: !fir.ref) { + %0 = fir.load %arg2 : !fir.ref + %c0 = arith.constant 0 : index + %1:3 = fir.box_dims %arg0, %c0 : (!fir.box>>, index) -> (index, index, index) + %2 = fir.array_load %arg0 : (!fir.box>>) -> !fir.array> + %3 = fir.array_load %arg1 : (!fir.box>>) -> !fir.array> + %c1 = arith.constant 1 : index + %4 = arith.subi %1#1, %c1 : index + %5 = fir.do_loop %arg3 = %c0 to %4 step %c1 unordered iter_args(%arg4 = %2) -> (!fir.array>) { + %6 = fir.array_access %3, %arg3 : (!fir.array>, index) -> !fir.ref> + %7 = fir.array_access %arg4, %arg3 : (!fir.array>, index) -> !fir.ref> + %false = arith.constant false + %8 = fir.convert %7 : (!fir.ref>) -> !fir.ref + %9 = fir.convert %6 : (!fir.ref>) -> !fir.ref + fir.call @llvm.memmove.p0i8.p0i8.i64(%8, %9, %0, %false) : (!fir.ref, !fir.ref, i64, i1) -> () + %10 = fir.array_amend %arg4, %7 : (!fir.array>, !fir.ref>) -> !fir.array> + fir.result %10 : !fir.array> + } + fir.array_merge_store %2, %5 to %arg0 : !fir.array>, !fir.array>, !fir.box>> + return + } + func private @llvm.memmove.p0i8.p0i8.i64(!fir.ref, !fir.ref, i64, i1) +} +``` + +`fir.array_access` and `fir.array_amend` split the two purposes of +`fir.array_update` into two distinct operations to work on type/kind that must +reside in the memory reference domain. `fir.array_access` captures the array +access semantics and `fir.array_amend` denotes which `fir.array_access` is the +lhs. + +We do not want to start loading the entire `!fir.ref>` here since +it has dynamic length, and even if constant, could be too long to do so. + +## array_amend + +The `array_amend` operation marks an array value as having been changed via a +reference obtain by an `array_access`. It acts as a logical transaction log +that is used to merge the final result back with an `array_merge_store` +operation. + +```mlir + // fetch the value of one of the array value's elements + %1 = fir.array_access %v, %i, %j : (!fir.array, index, index) -> !fir.ref + // modify the element by storing data using %1 as a reference + %2 = ... %1 ... + // mark the array value + %new_v = fir.array_amend %v, %2 : (!fir.array, !fir.ref) -> !fir.array +``` + +## Example + +Here is an example of a FIR code using several array operations together. The +example below is a simplified version of the FIR code comiing from the +following Fortran code snippet. + +```fortran +subroutine s(a,l,u) + type t + integer m + end type t + type(t) :: a(:) + integer :: l, u + forall (i=l:u) + a(i) = a(u-i+1) + end forall +end +``` + +``` +func @_QPs(%arg0: !fir.box>>, %arg1: !fir.ref, %arg2: !fir.ref) { + %l = fir.load %arg1 : !fir.ref + %l_index = fir.convert %l : (i32) -> index + %u = fir.load %arg2 : !fir.ref + %u_index = fir.convert %u : (i32) -> index + %c1 = arith.constant 1 : index + // This is the "copy-in" array used on the RHS of the expression. It will be indexed into and loaded at each iteration. + %array_a_src = fir.array_load %arg0 : (!fir.box>>) -> !fir.array> + + // This is the "seed" for the "copy-out" array on the LHS. It'll flow from iteration to iteration and gets + // updated at each iteration. + %array_a_dest_init = fir.array_load %arg0 : (!fir.box>>) -> !fir.array> + + %array_a_final = fir.do_loop %i = %l_index to %u_index step %c1 unordered iter_args(%array_a_dest = %array_a_dest_init) -> (!fir.array>) { + // Compute indexing for the RHS and array the element. + %u_minus_i = arith.subi %u_index, %i : index // u-i + %u_minus_i_plus_one = arith.addi %u_minus_i, %c1: index // u-i+1 + %a_src_ref = fir.array_access %array_a_src, %u_minus_i_plus_one {Fortran.offsets} : (!fir.array>, index) -> !fir.ref> + %a_src_elt = fir.load %a_src_ref : !fir.ref> + + // Get the reference to the element in the array on the LHS + %a_dst_ref = fir.array_access %array_a_dest, %i {Fortran.offsets} : (!fir.array>, index) -> !fir.ref> + + // Store the value, and update the array + fir.store %a_src_elt to %a_dst_ref : !fir.ref> + %updated_array_a = fir.array_amend %array_a_dest, %a_dst_ref : (!fir.array>, !fir.ref>) -> !fir.array> + + // Forward the current updated array to the next iteration. + fir.result %updated_array_a : !fir.array> + } + // Store back the result by merging the initial value loaded before the loop + // with the final one produced by the loop. + fir.array_merge_store %array_a_dest_init, %array_a_final to %arg0 : !fir.array>, !fir.array>, !fir.box>> + return +} +```