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,263 @@ + + +# Design: FIR Array operations + +```eval_rst +.. contents:: + :local: +``` + +## General + +The array operations in FIR model the copy-in/copy-out semantics over Fortran +statements. + +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. + +`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. + +## 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`. + +## 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. + +## 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_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 +} +```