Design: FIR Array operations¶
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, andMERGE.Assignments of arrays where the array appears on both the left and right-hand sides of the assignment.
Assignments of
POINTERarrays.
There are currently the following operations:
fir.array_loadfir.array_merge_storefir.array_fetchfir.array_updatefir.array_accessfir.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.
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.
%s = fir.shape_shift %lb1, %ex1, %lb2, %ex2 : (index, index, index, index) -> !fir.shapeshift<2>
// load the entire array 'a'
%v = fir.array_load %a(%s) : (!fir.ref<!fir.array<?x?xf32>>, !fir.shapeshift<2>) -> !fir.array<?x?xf32>
// 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.
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.
%v = fir.array_load %a(%shape) : ...
%r = fir.array_update %v, %f, %i, %j : (!fir.array<?x?xf32>, f32, index, index) -> !fir.array<?x?xf32>
fir.array_merge_store %v, %r to %a : !fir.ref<!fir.array<?x?xf32>>
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 chasing 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.
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.
%s = fir.shape %n, %m : (index, index) -> !fir.shape<2>
// load the entire array 'a'
%v = fir.array_load %a(%s) : (!fir.ref<!fir.array<?x?xf32>>, !fir.shape<2>) -> !fir.array<?x?xf32>
// fetch the value of one of the array value's elements
%1 = fir.array_fetch %v, %i, %j : (!fir.array<?x?xf32>, 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.
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.
%s = fir.shape %n, %m : (index, index) -> !fir.shape<2>
// load the entire array 'a'
%v = fir.array_load %a(%s) : (!fir.ref<!fir.array<?x?xf32>>, !fir.shape<2>) -> !fir.array<?x?xf32>
// 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<?x?xf32>, f32, index, index) -> !fir.array<?x?xf32>
fir.array_merge_store %v, %r to %a : !fir.ref<!fir.array<?x?xf32>>
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.
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.
%s = fir.shape %n, %m : (index, index) -> !fir.shape<2>
// load the entire array 'a'
%v = fir.array_load %a(%s) : (!fir.ref<!fir.array<?x?xf32>>, !fir.shape<2>) -> !fir.array<?x?xf32>
// fetch the value of one of the array value's elements
%1 = fir.array_access %v, %i, %j : (!fir.array<?x?xf32>, index, index) -> !fir.ref<f32>
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<!fir.array<?x!fir.char<1,?>>>, %arg1: !fir.box<!fir.array<?x!fir.char<1,?>>>, %arg2: !fir.ref<i64>) {
%0 = fir.load %arg2 : !fir.ref<i64>
%c0 = arith.constant 0 : index
%1:3 = fir.box_dims %arg0, %c0 : (!fir.box<!fir.array<?x!fir.char<1,?>>>, index) -> (index, index, index)
%2 = fir.array_load %arg0 : (!fir.box<!fir.array<?x!fir.char<1,?>>>) -> !fir.array<?x!fir.char<1,?>>
%3 = fir.array_load %arg1 : (!fir.box<!fir.array<?x!fir.char<1,?>>>) -> !fir.array<?x!fir.char<1,?>>
%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<?x!fir.char<1,?>>) {
%6 = fir.array_access %3, %arg3 : (!fir.array<?x!fir.char<1,?>>, index) -> !fir.ref<!fir.char<1,?>>
%7 = fir.array_access %arg4, %arg3 : (!fir.array<?x!fir.char<1,?>>, index) -> !fir.ref<!fir.char<1,?>>
%false = arith.constant false
%8 = fir.convert %7 : (!fir.ref<!fir.char<1,?>>) -> !fir.ref<i8>
%9 = fir.convert %6 : (!fir.ref<!fir.char<1,?>>) -> !fir.ref<i8>
fir.call @llvm.memmove.p0i8.p0i8.i64(%8, %9, %0, %false) : (!fir.ref<i8>, !fir.ref<i8>, i64, i1) -> ()
%10 = fir.array_amend %arg4, %7 : (!fir.array<?x!fir.char<1,?>>, !fir.ref<!fir.char<1,?>>) -> !fir.array<?x!fir.char<1,?>>
fir.result %10 : !fir.array<?x!fir.char<1,?>>
}
fir.array_merge_store %2, %5 to %arg0 : !fir.array<?x!fir.char<1,?>>, !fir.array<?x!fir.char<1,?>>, !fir.box<!fir.array<?x!fir.char<1,?>>>
return
}
func private @llvm.memmove.p0i8.p0i8.i64(!fir.ref<i8>, !fir.ref<i8>, 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<!fir.char<1,?>> 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.
// fetch the value of one of the array value's elements
%1 = fir.array_access %v, %i, %j : (!fir.array<?x?xT>, index, index) -> !fir.ref<T>
// 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<?x?xT>, !fir.ref<T>) -> !fir.array<?x?xT>
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.
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<!fir.array<?x!fir.type<_QFsTt{m:i32}>>>, %arg1: !fir.ref<i32>, %arg2: !fir.ref<i32>) {
%l = fir.load %arg1 : !fir.ref<i32>
%l_index = fir.convert %l : (i32) -> index
%u = fir.load %arg2 : !fir.ref<i32>
%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<?x!fir.type<_QFsTt{m:i32}>>>) -> !fir.array<?x!fir.type<_QFsTt{m:i32}>>
// 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<?x!fir.type<_QFsTt{m:i32}>>>) -> !fir.array<?x!fir.type<_QFsTt{m:i32}>>
%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<?x!fir.type<_QFsTt{m:i32}>>) {
// 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<?x!fir.type<_QFsTt{m:i32}>>, index) -> !fir.ref<!fir.type<_QFsTt{m:i32}>>
%a_src_elt = fir.load %a_src_ref : !fir.ref<!fir.type<_QFsTt{m:i32}>>
// 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<?x!fir.type<_QFsTt{m:i32}>>, index) -> !fir.ref<!fir.type<_QFsTt{m:i32}>>
// Store the value, and update the array
fir.store %a_src_elt to %a_dst_ref : !fir.ref<!fir.type<_QFsTt{m:i32}>>
%updated_array_a = fir.array_amend %array_a_dest, %a_dst_ref : (!fir.array<?x!fir.type<_QFsTt{m:i32}>>, !fir.ref<!fir.type<_QFsTt{m:i32}>>) -> !fir.array<?x!fir.type<_QFsTt{m:i32}>>
// Forward the current updated array to the next iteration.
fir.result %updated_array_a : !fir.array<?x!fir.type<_QFsTt{m:i32}>>
}
// 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<?x!fir.type<_QFsTt{m:i32}>>, !fir.array<?x!fir.type<_QFsTt{m:i32}>>, !fir.box<!fir.array<?x!fir.type<_QFsTt{m:i32}>>>
return
}