From 673c512eedd5f8ead06667c114013635ca67933d Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 23 Dec 2009 07:50:12 +0000 Subject: [PATCH] Fix PR42334: correct the update of the LST on loop interchange and distribution. 2009-12-15 Sebastian Pop PR middle-end/42178 PR middle-end/42334 * graphite-interchange.c (lst_perfect_nestify): Reset to NULL the LSTs that are empty. (lst_do_interchange_1): Renamed lst_interchange_select_inner. (lst_try_interchange): Reimplemented. (lst_interchange_select_inner): Same. (lst_do_interchange): Renamed lst_interchange_select_outer. Reimplemented. (scop_do_interchange): Update use of lst_interchange_select_outer. * graphite-interchange.c (lst_try_interchange): Do not increment the the OUTER index when there is no AFTER kernel. Do not increment the OUTER index for after processing the AFTER kernel. (lst_interchange_select_inner): Call lst_try_interchange only on loops. (lst_interchange_select_outer): Do not pass in a pointer to the OUTER index. Do not pass to lst_interchange_select_inner the OUTER index. (scop_do_interchange): Update use of lst_interchange_select_outer. * graphite-interchange.c (lst_try_interchange): Do not modify OUTER index. Call lst_interchange_select_inner only once. (lst_interchange_select_inner): Update use of lst_try_interchange. (lst_interchange_select_outer): Update. * testsuite/g++.dg/graphite/pr42130.C: Add -fgraphite-identity. * testsuite/gcc.dg/graphite/block-0.c: Un-XFAILed. * testsuite/gcc.dg/graphite/pr42211.c: New. * testsuite/gfortran.dg/graphite/pr42334.f90: New. * testsuite/gfortran.dg/graphite/graphite.exp (DEFAULT_FLAGS_GRAPHITE_IDENTITY): Remove -fdump-tree-graphite-all. * testsuite/gfortran.dg/graphite/interchange-1.f: Add comment. Clean the graphite dump file. * testsuite/gfortran.dg/graphite/interchange-2.f: Same. * testsuite/gfortran.dg/graphite/pr42334-1.f: New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@155418 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog.graphite | 46 +++++++++ gcc/graphite-interchange.c | 104 +++++++++++---------- gcc/testsuite/g++.dg/graphite/pr42130.C | 4 +- gcc/testsuite/gcc.dg/graphite/block-0.c | 2 +- gcc/testsuite/gcc.dg/graphite/pr42211.c | 22 +++++ gcc/testsuite/gfortran.dg/graphite/graphite.exp | 2 +- gcc/testsuite/gfortran.dg/graphite/interchange-1.f | 5 + gcc/testsuite/gfortran.dg/graphite/interchange-2.f | 7 +- gcc/testsuite/gfortran.dg/graphite/pr42334-1.f | 16 ++++ gcc/testsuite/gfortran.dg/graphite/pr42334.f90 | 20 ++++ 10 files changed, 174 insertions(+), 54 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/graphite/pr42211.c create mode 100644 gcc/testsuite/gfortran.dg/graphite/pr42334-1.f create mode 100644 gcc/testsuite/gfortran.dg/graphite/pr42334.f90 diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index b17f3d4392c..232e13d7696 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,3 +1,49 @@ +2009-12-17 Sebastian Pop + + PR middle-end/42178 + PR middle-end/42334 + * graphite-interchange.c (lst_try_interchange): Do not modify OUTER + index. Call lst_interchange_select_inner only once. + (lst_interchange_select_inner): Update use of lst_try_interchange. + (lst_interchange_select_outer): Update. + +2009-12-15 Sebastian Pop + + PR middle-end/42178 + PR middle-end/42334 + * graphite-interchange.c (lst_try_interchange): Do not increment the + the OUTER index when there is no AFTER kernel. Do not increment the + OUTER index for after processing the AFTER kernel. + (lst_interchange_select_inner): Call lst_try_interchange only on loops. + (lst_interchange_select_outer): Do not pass in a pointer to the OUTER + index. Do not pass to lst_interchange_select_inner the OUTER index. + (scop_do_interchange): Update use of lst_interchange_select_outer. + + * testsuite/gfortran.dg/graphite/graphite.exp + (DEFAULT_FLAGS_GRAPHITE_IDENTITY): Remove -fdump-tree-graphite-all. + * testsuite/gfortran.dg/graphite/interchange-1.f: Add comment. Clean + the graphite dump file. + * testsuite/gfortran.dg/graphite/interchange-2.f: Same. + * testsuite/gfortran.dg/graphite/pr42334-1.f: New. + +2009-12-15 Sebastian Pop + + PR middle-end/42178 + PR middle-end/42334 + * graphite-interchange.c (lst_perfect_nestify): Reset to NULL the LSTs + that are empty. + (lst_do_interchange_1): Renamed lst_interchange_select_inner. + (lst_try_interchange): Reimplemented. + (lst_interchange_select_inner): Same. + (lst_do_interchange): Renamed lst_interchange_select_outer. + Reimplemented. + (scop_do_interchange): Update use of lst_interchange_select_outer. + + * testsuite/g++.dg/graphite/pr42130.C: Add -fgraphite-identity. + * testsuite/gcc.dg/graphite/block-0.c: Un-XFAILed. + * testsuite/gcc.dg/graphite/pr42211.c: New. + * testsuite/gfortran.dg/graphite/pr42334.f90: New. + 2009-12-14 Sebastian Pop PR middle-end/42181 diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c index 280a14e6d45..d4bc232ed16 100644 --- a/gcc/graphite-interchange.c +++ b/gcc/graphite-interchange.c @@ -585,6 +585,13 @@ lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before, lst_remove_all_before_excluding_pbb (*nest, first, true); lst_remove_all_before_excluding_pbb (*nest, last, false); + + if (lst_empty_p (*before)) + *before = NULL; + if (lst_empty_p (*after)) + *after = NULL; + if (lst_empty_p (*nest)) + *nest = NULL; } /* Try to interchange LOOP1 with LOOP2 for all the statements of the @@ -650,92 +657,91 @@ lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2, return false; } -static bool lst_do_interchange_1 (scop_p, lst_p, int *); +static bool lst_interchange_select_inner (scop_p, lst_p, int, lst_p); -/* Try to interchange LOOP with all the loops contained in the body of - LST. Return true if it did interchanged some loops. INDEX points - to the next element to be processed by lst_do_interchange. */ +/* Try to interchange loop OUTER of LST_SEQ (OUTER_FATHER) with all + the loop INNER and with all the loops contained in the body of + INNER. Return true if it did interchanged some loops. */ static bool -lst_try_interchange (scop_p scop, lst_p loop, lst_p lst, int *index) +lst_try_interchange (scop_p scop, lst_p outer_father, int outer, lst_p inner) { - int i; - lst_p l; lst_p before, nest, after; bool res; + lst_p loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer); + lst_p loop2 = inner; - if (!lst || !LST_LOOP_P (lst)) - return false; + gcc_assert (LST_LOOP_P (loop1) + && LST_LOOP_P (loop2)); - res = lst_try_interchange_loops (scop, loop, lst, &before, &nest, &after); + res = lst_try_interchange_loops (scop, loop1, loop2, &before, &nest, &after); if (before) - { - res |= lst_do_interchange_1 (scop, before, index); - (*index)++; - } - - if (nest) - res |= lst_do_interchange_1 (scop, nest, index); + res |= lst_interchange_select_inner (scop, outer_father, outer, before); + else if (nest) + res |= lst_interchange_select_inner (scop, outer_father, outer, nest); else - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) - res |= lst_try_interchange (scop, loop, l, index); + res |= lst_interchange_select_inner (scop, outer_father, outer, loop2); - if (after) - { - res |= lst_do_interchange_1 (scop, after, index); - (*index)++; - } - - (*index)++; return res; } -/* Interchanges all the loops of LOOP that are considered profitable - to interchange. Return true if it did interchanged some loops. - INDEX points to the next element to be processed by - lst_do_interchange. */ +/* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged + with the loop OUTER in LST_SEQ (OUTER_FATHER). */ static bool -lst_do_interchange_1 (scop_p scop, lst_p loop, int *index) +lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer, + lst_p inner_father) { - int i; lst_p l; bool res = false; + int inner; - if (!loop || !LST_LOOP_P (loop)) - return false; + gcc_assert (outer_father + && LST_LOOP_P (outer_father) + && LST_LOOP_P (VEC_index (lst_p, LST_SEQ (outer_father), outer)) + && inner_father + && LST_LOOP_P (inner_father)); - for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++) - res |= lst_try_interchange (scop, loop, l, index); + for (inner = 0; VEC_iterate (lst_p, LST_SEQ (inner_father), inner, l); inner++) + if (LST_LOOP_P (l)) + res |= lst_try_interchange (scop, outer_father, outer, l); return res; } /* Interchanges all the loops of LOOP and the loops of its body that are considered profitable to interchange. Return true if it did - interchanged some loops. INDEX points to the next element to be - processed in the LST_SEQ (LOOP) vector. */ + interchanged some loops. OUTER is the index in LST_SEQ (LOOP) that + points to the next outer loop to be considered for interchange. */ static bool -lst_do_interchange (scop_p scop, lst_p loop, int *index) +lst_interchange_select_outer (scop_p scop, lst_p loop, int outer) { lst_p l; bool res = false; + int i = 0; + lst_p father; if (!loop || !LST_LOOP_P (loop)) return false; - if (lst_depth (loop) >= 0) - res = lst_do_interchange_1 (scop, loop, index); + father = LST_LOOP_FATHER (loop); + if (father) + { + res = lst_interchange_select_inner (scop, father, outer, loop); + + if (VEC_length (lst_p, LST_SEQ (father)) <= (unsigned) outer) + return res; - while (VEC_iterate (lst_p, LST_SEQ (loop), *index, l)) - if (LST_LOOP_P (l)) - res |= lst_do_interchange (scop, l, index); - else - (*index)++; + loop = VEC_index (lst_p, LST_SEQ (father), outer); + } + + if (LST_LOOP_P (loop)) + for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++) + if (LST_LOOP_P (l)) + res |= lst_interchange_select_outer (scop, l, i); - (*index)++; return res; } @@ -744,8 +750,8 @@ lst_do_interchange (scop_p scop, lst_p loop, int *index) bool scop_do_interchange (scop_p scop) { - int i = 0; - bool res = lst_do_interchange (scop, SCOP_TRANSFORMED_SCHEDULE (scop), &i); + bool res = lst_interchange_select_outer + (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0); lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop)); diff --git a/gcc/testsuite/g++.dg/graphite/pr42130.C b/gcc/testsuite/g++.dg/graphite/pr42130.C index ca002279e53..ee31abad0ee 100644 --- a/gcc/testsuite/g++.dg/graphite/pr42130.C +++ b/gcc/testsuite/g++.dg/graphite/pr42130.C @@ -1,4 +1,4 @@ -/* { dg-options "-O2 -fno-tree-ch" } */ +/* { dg-options "-O2 -fgraphite-identity -fno-tree-ch" } */ #include using std::vector; @@ -9,11 +9,11 @@ vector & __attribute__((noinline, noclone)) foo(unsigned n) return *vv; } - int main() { foo(0); return 0; } + /* { dg-do run } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c index 55b903650e2..a00694ca406 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-0.c +++ b/gcc/testsuite/gcc.dg/graphite/block-0.c @@ -19,5 +19,5 @@ main() return toto(); } -/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr42211.c b/gcc/testsuite/gcc.dg/graphite/pr42211.c new file mode 100644 index 00000000000..d8fb915f377 --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/pr42211.c @@ -0,0 +1,22 @@ +/* { dg-options "-O3 -floop-interchange" } */ + +typedef unsigned char uint8_t; + +void border_mirror(uint8_t *outer_img, int w, int h, int rb, int border) +{ + uint8_t *img = outer_img + border * rb + border; + int x, y; + + for (y = -border; y < 0; y++) { + for (x = -border; x < 0; x++) + img[y*rb + x] = img[(-y)*rb + (-x)]; + + for (x = 0; x < w; x++) + img[y*rb + x] = img[(-y)*rb + x]; + } +} + +void border_mirror_480(uint8_t *outer_img) +{ + border_mirror(outer_img, 640, 480, 640 + 16*2, 16); +} diff --git a/gcc/testsuite/gfortran.dg/graphite/graphite.exp b/gcc/testsuite/gfortran.dg/graphite/graphite.exp index 997453dd440..99b46def818 100644 --- a/gcc/testsuite/gfortran.dg/graphite/graphite.exp +++ b/gcc/testsuite/gfortran.dg/graphite/graphite.exp @@ -49,7 +49,7 @@ gfortran-dg-runtest $block_files $DEFAULT_FLAGS_GRAPHITE_BLOCK foreach block_file $block_files {lremove wait_to_run_files $block_file} # Flags using for id-* files. -set DEFAULT_FLAGS_GRAPHITE_IDENTITY "-O2 -fgraphite-identity -fdump-tree-graphite-all" +set DEFAULT_FLAGS_GRAPHITE_IDENTITY "-O2 -fgraphite-identity" set id_files [lsort [glob -nocomplain $srcdir/$subdir/id-*.\[fF\]{,90,95,03,08} ] ] gfortran-dg-runtest $id_files $DEFAULT_FLAGS_GRAPHITE_IDENTITY foreach id_file $id_files {lremove wait_to_run_files $id_file} diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-1.f b/gcc/testsuite/gfortran.dg/graphite/interchange-1.f index 0440de67469..334fbd8246a 100644 --- a/gcc/testsuite/gfortran.dg/graphite/interchange-1.f +++ b/gcc/testsuite/gfortran.dg/graphite/interchange-1.f @@ -37,4 +37,9 @@ end +! We should be able to interchange this as the number of iterations is +! known to be 4 in the inner two loops. See interchange-2.f for the +! kernel from bwaves. + ! { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } +! { dg-final { cleanup-tree-dump "graphite" } } diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-2.f b/gcc/testsuite/gfortran.dg/graphite/interchange-2.f index 6418c0c89e6..8e2e87f12ab 100644 --- a/gcc/testsuite/gfortran.dg/graphite/interchange-2.f +++ b/gcc/testsuite/gfortran.dg/graphite/interchange-2.f @@ -32,7 +32,12 @@ enddo enddo enddo - enddo + enddo return end +! This is the kernel extracted from bwaves: this cannot be interchanged +! as the number of iterations for f4 is not known. + +! { dg-final { scan-tree-dump-times "will be interchanged" 0 "graphite" } } +! { dg-final { cleanup-tree-dump "graphite" } } diff --git a/gcc/testsuite/gfortran.dg/graphite/pr42334-1.f b/gcc/testsuite/gfortran.dg/graphite/pr42334-1.f new file mode 100644 index 00000000000..2503dc3e8f2 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/graphite/pr42334-1.f @@ -0,0 +1,16 @@ +! { dg-options "-O2 -floop-interchange" } + + subroutine linel(icmdl,stre,anisox) + real*8 stre(6),tkl(3,3),ekl(3,3),anisox(3,3,3,3) + do m1=1,3 + do m2=1,m1 + do m3=1,3 + do m4=1,3 + tkl(m1,m2)=tkl(m1,m2)+ + & anisox(m1,m2,m3,m4)*ekl(m3,m4) + enddo + enddo + enddo + enddo + stre(1)=tkl(1,1) + end diff --git a/gcc/testsuite/gfortran.dg/graphite/pr42334.f90 b/gcc/testsuite/gfortran.dg/graphite/pr42334.f90 new file mode 100644 index 00000000000..4080c9f2ab3 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/graphite/pr42334.f90 @@ -0,0 +1,20 @@ +! { dg-options "-O2 -floop-interchange -ftree-loop-distribution" } + +subroutine blockdis(bl1eg,bl2eg) + implicit real*8 (a-h,o-z) + parameter(nblo=300) + common/str /mblo + common/str2 /mel(nblo) + dimension h(nblo,2,6),g(nblo,2,6) + dimension bl1eg(nblo,2,6),bl2eg(nblo,2,6) + do k=1,mblo + jm=mel(k) + do l=1,2 + do m=1,6 + bl1eg(k,l,m)=h(jm,l,m) + bl2eg(k,l,m)=g(jm,l,m) + enddo + enddo + enddo + return +end subroutine blockdis -- 2.11.4.GIT