[Patch, fortran] [00/66] PR fortran/43829 Inline sum and product (AKA scalarization of reductions)
Mikael Morin
mikael.morin@sfr.fr
Thu Oct 27 23:29:00 GMT 2011
Hello,
these patches enable sum and product inlining in the non-scalar case
(before, they were inlined in the scalar case only).
Let's consider the scalar expression:
sum(a(:,1,1,:,:))
This is currently inlined (scalar expression), and the scalarizer has a dim
array designating array dimensions used for scalarization. In the case above,
dim = {0, 3, 4}, and the scalarizer state corresponding to `a' has non-NULL
values in the corresponding lbound[0], lbound[3], lbound[4] (same, for ubound,
stride,...) as presented in the scheme below.
loop
\
--- (...) ---- ss(a) --- (...) ----> gfc_ss_terminator
|\
| descriptor
| |\
| | lbound ( ) ( ) ( ) ( ) ( )
| \
| ubound ( ) ( ) ( ) ( ) ( )
| ^ ^ ^
\ +----+ | |
dim | +-----------------+ |
\ | | +--------------------+
---> 0 3 4
Now if one considers the non-scalar expression:
sum(a(:,1,1,:,:), dim=2)
the dim array would now be only {3} as we are suming on the second non-scalar
dimension only, which means that lbound[0] and lbound[4] (same for ubound,
stride...) are left available for another scalarizer. This set of patches
make the necessary changes so that another scalarizer can use those dimensions
left available as below.
loop
\
--- (...) ---- ss(sum(a,2)) --- (...) ----> gfc_ss_terminator
|\
| dim
| \
| ---> 0 4
| | +----------------------+
| +----+ |
\ | |
descriptor | |
/ |\ V V
| | lbound ( ) ( ) ( ) ( ) ( )
| \
| ubound ( ) ( ) ( ) ( ) ( )
| ^
| +-------------------+
| ---> 3
| /
| dim
|/
--- (...) ---- nested_ss(a) --- (...) ----> gfc_ss_terminator
/
nested_loop
* Structure changes.
Between the outer scalarizer loop (using dimensions 0 and 4 above) and the inner
one (using dimension 3) almost all the information is the same:
type, expression, descriptor, string_length, ...
So, in order to not have to update many structs at the same type, if one
item needs to be updated, a new struct is created containing all the shared
content, and all the gfc_ss structs have a pointer to it instead of holding
the content directly.
Left in the gfc_ss structs are dim array and dimension for the obvious that
they depend on the loop. This requires that those fields are moved from
gfc_ss_info, and is the reason for most of the 13..19 patches.
Also left in the gfc_ss structs are the linked list pointers, for the same
reason that they depend on the loop. They don't need to be moved though.
All the rest is moved to the new shared struct.
See patches 20..30 for details.
A bunch of new pointers are added to ease retrieval of related content: loop
associated with a gfc_ss struct, parent gfc_ss struct (i.e. the one in the outer
loop), associated gfc_ss struct in the inner loop.
The gfc_loopinfo structs get the same kind of changes: three additional fields;
one for the outer loop, and two for a linked list of nested loop pointers.
See patches 31..53 for details
* Code changes
All the changes above require the whole scalarizer to be updated, not only
because its core structures have changed, but also to handle more than one loop:
- In cases we were previously looping over all the dimensions of a loop,
we'll now need to loop over all the dimensions and over all the loops
available. For example gfc_trans_create_temp_array uses loop bounds to guess
allocation size; it has to consider more than one loop now.
- In cases we were focusing on one single array, we have to take into account
the fact that the array information can be scattered across multiple loops.
- The code that was executed before the loop previously has to be taken out
of the outermost loop now. This implies that the inner loop is already
available when handling the outer loop. It will in fact be created at walk
time.
See patches 31..53 for details.
A few corner cases not in the core of the scalarizer need additional fixes to
prevent regressions, in patches 54..61. The rest (62..66) takes care of inlining
sum (and product).
The full patch is attached for the compulsive testers.
To ease (well, somewhat) review, the patch has been split into pieces.
See my follow-up mails for details. The general outline is below.
There is no need to spend too much reviewing power on the 1..30 patches, unless
there is a concern about the core struct changes.
01..06: Step by step gfc_trans_preloop_setup rewrite.
07..12: Various preliminary cleanups.
13..19: Function interfaces changes.
20..30: Core structs reorganisation.
31..53: Update the scalarizer.
54..61: Prevent regressions.
62..66: Inline sum.
Regression tested on x86_64-unknown-freebsd8.2. OK for trunk?
Mikael
PS: I hereby confess my failure to not split the patch too much. :-(
-------------- next part --------------
2011-10-19 Mikael Morin <mikael@gcc.gnu.org>
PR fortran/43829
* gfortran.dg/function_optimize_7.f90: Disable sum inlining.
* gfortran.dg/inline_sum_1.f90: New.
* gfortran.dg/inline_sum_2.f90: New.
* gfortran.dg/inline_sum_bounds_check_1.f90: New.
* gfortran.dg/inline_sum_bounds_check_2.f90: New.
* gfortran.dg/inline_product_1.f90: New.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: function_optimize_7.f90.diff
Type: text/x-diff
Size: 848 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20111027/b7d43bdb/attachment.bin>
-------------- next part --------------
! { dg-do run }
! PR fortran/43829
! Scalarization of reductions.
! Test that inlined sum is correct.
! We can't check for the absence of temporary arrays generated on the run-time
! testcase, as inlining is disabled at -Os, so it will fail in that case.
! Thus, the test is splitted into two independant files, one checking for
! the absence of temporaries, and one (this one) checking that the code
! generated remains valid at all optimization levels.
include 'inline_sum_1.f90'
-------------- next part --------------
! { dg-do compile }
! { dg-options "-Warray-temporaries -O -fdump-tree-original" }
!
! PR fortran/43829
! Scalarization of reductions.
! Test that sum is properly inlined.
! This is the compile time test only; for the runtime test see inline_sum_2.f90
! We can't test for temporaries on the run time test directly, as it tries
! several optimization options among which -Os, and sum inlining is disabled
! at -Os.
implicit none
integer :: i, j, k
integer, parameter :: q = 2
integer, parameter :: nx=3, ny=2*q, nz=5
integer, parameter, dimension(nx,ny,nz) :: p = &
& reshape ((/ (i**2, i=1,size(p)) /), shape(p))
integer, parameter, dimension( ny,nz) :: px = &
& reshape ((/ (( &
& nx*( nx*j+nx*ny*k+1)*( nx*j+nx*ny*k+1+ (nx-1)) &
& + nx*(nx-1)*(2*nx-1)/6, &
& j=0,ny-1), k=0,nz-1) /), shape(px))
integer, parameter, dimension(nx, nz) :: py = &
& reshape ((/ (( &
& ny*(i +nx*ny*k+1)*(i +nx*ny*k+1+nx *(ny-1)) &
& +(nx )**2*ny*(ny-1)*(2*ny-1)/6, &
& i=0,nx-1), k=0,nz-1) /), shape(py))
integer, parameter, dimension(nx,ny ) :: pz = &
& reshape ((/ (( &
& nz*(i+nx*j +1)*(i+nx*j +1+nx*ny*(nz-1)) &
& +(nx*ny)**2*nz*(nz-1)*(2*nz-1)/6, &
& i=0,nx-1), j=0,ny-1) /), shape(pz))
integer, dimension(nx,ny,nz) :: a
integer, dimension( ny,nz) :: ax
integer, dimension(nx, nz) :: ay
integer, dimension(nx,ny ) :: az
logical, dimension(nx,ny,nz) :: m, true
integer, dimension(nx,ny) :: b
integer, dimension(nx,nx) :: onesx
integer, dimension(ny,ny) :: onesy
integer, dimension(nz,nz) :: onesz
a = p
m = reshape((/ ((/ .true., .false. /), i=1,size(m)/2) /), shape(m))
true = reshape((/ (.true., i=1,size(true)) /), shape(true))
onesx = reshape((/ ((1, j=1,i),(0,j=1,nx-i),i=1,size(onesx,2)) /), shape(onesx))
onesy = reshape((/ ((1, j=1,i),(0,j=1,ny-i),i=1,size(onesy,2)) /), shape(onesy))
onesz = reshape((/ ((1, j=1,i),(0,j=1,nz-i),i=1,size(onesz,2)) /), shape(onesz))
! Correct results in simple cases
ax = sum(a,1)
if (any(ax /= px)) call abort
ay = sum(a,2)
if (any(ay /= py)) call abort
az = sum(a,3)
if (any(az /= pz)) call abort
! Masks work
if (any(sum(a,1,.false.) /= 0)) call abort
if (any(sum(a,2,.true.) /= py)) call abort
if (any(sum(a,3,m) /= merge(pz,0,m(:,:,1)))) call abort
if (any(sum(a,2,m) /= merge(sum(a(:, ::2,:),2),&
sum(a(:,2::2,:),2),&
m(:,1,:)))) call abort
! It works too with array constructors ...
if (any(sum( &
reshape((/ (i*i,i=1,size(a)) /), shape(a)), &
1, &
true) /= ax)) call abort
! ... and with vector subscripts
if (any(sum( &
a((/ (i,i=1,nx) /), &
(/ (i,i=1,ny) /), &
(/ (i,i=1,nz) /)), &
1) /= ax)) call abort
if (any(sum( &
a(sum(onesx(:,:),1), & ! unnecessary { dg-warning "Creating array temporary" }
sum(onesy(:,:),1), & ! unnecessary { dg-warning "Creating array temporary" }
sum(onesz(:,:),1)), & ! unnecessary { dg-warning "Creating array temporary" }
1) /= ax)) call abort
! Nested sums work
if (sum(sum(sum(a,1),1),1) /= sum(a)) call abort
if (sum(sum(sum(a,1),2),1) /= sum(a)) call abort
if (sum(sum(sum(a,3),1),1) /= sum(a)) call abort
if (sum(sum(sum(a,3),2),1) /= sum(a)) call abort
if (any(sum(sum(a,1),1) /= sum(sum(a,2),1))) call abort
if (any(sum(sum(a,1),2) /= sum(sum(a,3),1))) call abort
if (any(sum(sum(a,2),2) /= sum(sum(a,3),2))) call abort
! Temps are unavoidable here (function call's argument or result)
ax = sum(neid3(a),1) ! { dg-warning "Creating array temporary" }
! Sums as part of a bigger expr work
if (any(1+sum(eid(a),1)+ax+sum( &
neid3(a), & ! { dg-warning "Creating array temporary" }
1)+1 /= 3*ax+2)) call abort
if (any(1+eid(sum(a,2))+ay+ &
neid2( & ! { dg-warning "Creating array temporary" }
sum(a,2) & ! { dg-warning "Creating array temporary" }
)+1 /= 3*ay+2)) call abort
if (any(sum(eid(sum(a,3))+az+2* &
neid2(az) & ! { dg-warning "Creating array temporary" }
,1)+1 /= 4*sum(az,1)+1)) call abort
if (any(sum(transpose(sum(a,1)),1)+sum(az,1) /= sum(ax,2)+sum(sum(a,3),1))) call abort
! Creates a temp when needed.
a(1,:,:) = sum(a,1) ! unnecessary { dg-warning "Creating array temporary" }
if (any(a(1,:,:) /= ax)) call abort
b = p(:,:,1)
call set(b(2:,1), sum(b(:nx-1,:),2)) ! { dg-warning "Creating array temporary" }
if (any(b(2:,1) /= ay(1:nx-1,1))) call abort
b = p(:,:,1)
call set(b(:,1), sum(b,2)) ! unnecessary { dg-warning "Creating array temporary" }
if (any(b(:,1) /= ay(:,1))) call abort
b = p(:,:,1)
call tes(sum(eid(b(:nx-1,:)),2), b(2:,1)) ! { dg-warning "Creating array temporary" }
if (any(b(2:,1) /= ay(1:nx-1,1))) call abort
b = p(:,:,1)
call tes(eid(sum(b,2)), b(:,1)) ! unnecessary { dg-warning "Creating array temporary" }
if (any(b(:,1) /= ay(:,1))) call abort
contains
elemental function eid (x)
integer, intent(in) :: x
integer :: eid
eid = x
end function eid
function neid2 (x)
integer, intent(in) :: x(:,:)
integer :: neid2(size(x,1),size(x,2))
neid2 = x
end function neid2
function neid3 (x)
integer, intent(in) :: x(:,:,:)
integer :: neid3(size(x,1),size(x,2),size(x,3))
neid3 = x
end function neid3
elemental subroutine set (o, i)
integer, intent(in) :: i
integer, intent(out) :: o
o = i
end subroutine set
elemental subroutine tes (i, o)
integer, intent(in) :: i
integer, intent(out) :: o
o = i
end subroutine tes
end
! { dg-final { scan-tree-dump-times "struct array._integer\\(kind=4\\) atmp" 13 "original" } }
! { dg-final { scan-tree-dump-times "struct array\[^\\n\]*atmp" 13 "original" } }
! { dg-final { scan-tree-dump-times "_gfortran_sum_" 0 "original" } }
! { dg-final { cleanup-tree-dump "original" } }
-------------- next part --------------
! { dg-do run }
! { dg-options "-fbounds-check" }
integer, parameter :: nx = 3, ny = 4
integer :: i, j, too_big
integer, parameter, dimension(nx,ny) :: p = &
reshape((/ (i*i, i=1,size(p)) /), shape(p))
integer, dimension(nx,ny) :: a
integer, dimension(:), allocatable :: b
allocate(b(nx))
a = p
too_big = ny + 1
b = sum(a(:,1:too_big),2)
end
! { dg-shouldfail "outside of expected range" }
-------------- next part --------------
! { dg-do run }
! { dg-options "-fbounds-check" }
integer, parameter :: nx = 3, ny = 4
integer :: i, j, too_big
integer, parameter, dimension(nx,ny) :: p = &
reshape((/ (i*i, i=1,size(p)) /), shape(p))
integer, dimension(nx,ny) :: a
integer, dimension(:), allocatable :: c
allocate(c(ny))
a = p
too_big = nx + 1
c = sum(a(1:too_big,:),2)
end
! { dg-shouldfail "outside of expected range" }
-------------- next part --------------
! { dg-do compile }
! { dg-options "-Warray-temporaries -O -fdump-tree-original" }
!
! PR fortran/43829
! Scalarization of reductions.
! Test that product is properly inlined.
! For more extended tests, see inline_sum_1.f90
implicit none
integer :: i
integer, parameter :: q = 2
integer, parameter :: nx=3, ny=2*q, nz=5
integer, parameter, dimension(nx,ny,nz) :: p = &
& reshape ((/ (i, i=1,size(p)) /), shape(p))
integer, dimension(nx,ny,nz) :: a
integer, dimension(nx, nz) :: ay
a = p
ay = product(a,2)
end
! { dg-final { scan-tree-dump-times "struct array._integer\\(kind=4\\) atmp" 0 "original" } }
! { dg-final { scan-tree-dump-times "struct array\[^\\n\]*atmp" 0 "original" } }
! { dg-final { scan-tree-dump-times "_gfortran_product_" 0 "original" } }
! { dg-final { cleanup-tree-dump "original" } }
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr43829-full.diff
Type: text/x-diff
Size: 141602 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20111027/b7d43bdb/attachment-0001.bin>
More information about the Fortran
mailing list