From 15256e28a5351f788b66e574bf1ad53a23fbdda1 Mon Sep 17 00:00:00 2001 From: Aditya Kumar Date: Fri, 4 Dec 2015 21:36:55 +0000 Subject: [PATCH] fix PR68693: Check for loop structure when extending the SCoP The check for dominance while extending the scop assumed that multiple successors meant a loop which is not true in case of conditionals around the loop. Improved pretty printers for better debugging. PR tree-optimization/68693 * graphite-scop-detection.c (dot_all_sese): New (dot_all_scops_1): Renamed to dot_all_sese. (dot_all_scops): Removed. (dot_sese): New. (dot_cfg): New. (scop_detection::get_nearest_dom_with_single_entry): Check that preds are from different loop levels. (scop_detection::get_nearest_pdom_with_single_exit): Check that succs are from different loop levels. (scop_detection::print_sese): Inlined. (scop_detection::print_edge): New. (scop_detection::merge_sese): Added dumps. * graphite.h: Add declarations. gcc/testsuite/ChangeLog: * gfortran.dg/graphite/pr68693.f90: New test. Co-Authored-By: Sebastian Pop From-SVN: r231309 --- gcc/ChangeLog | 18 +++ gcc/graphite-scop-detection.c | 153 +++++++++--------- gcc/graphite.h | 6 +- gcc/testsuite/ChangeLog | 6 + .../gfortran.dg/graphite/pr68693.f90 | 35 ++++ 5 files changed, 134 insertions(+), 84 deletions(-) create mode 100644 gcc/testsuite/gfortran.dg/graphite/pr68693.f90 diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 06e0d7b6b64..4223a1ecb5b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,21 @@ +2015-12-04 Aditya Kumar + Sebastian Pop + + PR tree-optimization/68693 + * graphite-scop-detection.c (dot_all_sese): New + (dot_all_scops_1): Renamed to dot_all_sese. + (dot_all_scops): Removed. + (dot_sese): New. + (dot_cfg): New. + (scop_detection::get_nearest_dom_with_single_entry): Check that + preds are from different loop levels. + (scop_detection::get_nearest_pdom_with_single_exit): Check that + succs are from different loop levels. + (scop_detection::print_sese): Inlined. + (scop_detection::print_edge): New. + (scop_detection::merge_sese): Added dumps. + * graphite.h: Add declarations. + 2015-12-04 James Greenhalgh * config/aarch64/aarch64.md (add3_pluslong): Add register diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 2f4231a4582..729a5fd5588 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -98,22 +98,16 @@ public: - "()" around the node number denotes the entry or the exit nodes of the SCOP. These are not part of SCoP. */ -static void -dot_all_scops_1 (FILE *file, vec scops) +DEBUG_FUNCTION void +dot_all_sese (FILE *file, vec& scops) { - basic_block bb; - edge e; - edge_iterator ei; - scop_p scop; - const char *color; - int i; - /* Disable debugging while printing graph. */ int tmp_dump_flags = dump_flags; dump_flags = 0; fprintf (file, "digraph all {\n"); + basic_block bb; FOR_ALL_BB_FN (bb, cfun) { int part_of_scop = false; @@ -126,12 +120,15 @@ dot_all_scops_1 (FILE *file, vec scops) fprintf (file, "CELLSPACING=\"0\">\n"); /* Select color for SCoP. */ - FOR_EACH_VEC_ELT (scops, i, scop) + sese_l *region; + int i; + FOR_EACH_VEC_ELT (scops, i, region) { - sese_l region = scop->scop_info->region; - if (bb_in_sese_p (bb, region) || (region.exit->dest == bb) - || (region.entry->dest == bb)) + bool sese_in_region = bb_in_sese_p (bb, *region); + if (sese_in_region || (region->exit->dest == bb) + || (region->entry->dest == bb)) { + const char *color; switch (i % 17) { case 0: /* red */ @@ -192,21 +189,21 @@ dot_all_scops_1 (FILE *file, vec scops) fprintf (file, " ", color); - if (!bb_in_sese_p (bb, region)) + if (!sese_in_region) fprintf (file, " ("); - if (bb == region.entry->dest && bb == region.exit->dest) + if (bb == region->entry->dest && bb == region->exit->dest) fprintf (file, " %d*# ", bb->index); - else if (bb == region.entry->dest) + else if (bb == region->entry->dest) fprintf (file, " %d* ", bb->index); - else if (bb == region.exit->dest) + else if (bb == region->exit->dest) fprintf (file, " %d# ", bb->index); else fprintf (file, " %d ", bb->index); fprintf (file, "{lp_%d}", bb->loop_father->num); - if (!bb_in_sese_p (bb, region)) + if (!sese_in_region) fprintf (file, ")"); fprintf (file, "\n"); @@ -225,6 +222,8 @@ dot_all_scops_1 (FILE *file, vec scops) FOR_ALL_BB_FN (bb, cfun) { + edge e; + edge_iterator ei; FOR_EACH_EDGE (e, ei, bb->succs) fprintf (file, "%d -> %d;\n", bb->index, e->dest->index); } @@ -235,52 +234,29 @@ dot_all_scops_1 (FILE *file, vec scops) dump_flags = tmp_dump_flags; } -/* Display all SCoPs using dotty. */ - -DEBUG_FUNCTION void -dot_all_scops (vec scops) -{ - /* When debugging, enable the following code. This cannot be used - in production compilers because it calls "system". */ -#if 0 - int x; - FILE *stream = fopen ("/tmp/allscops.dot", "w"); - gcc_assert (stream); - - dot_all_scops_1 (stream, scops); - fclose (stream); - - x = system ("dotty /tmp/allscops.dot &"); -#else - dot_all_scops_1 (stderr, scops); -#endif -} - -/* Display all SCoPs using dotty. */ +/* Display SCoP on stderr. */ DEBUG_FUNCTION void -dot_scop (scop_p scop) +dot_sese (sese_l& scop) { - auto_vec scops; + vec scops; + scops.create (1); if (scop) scops.safe_push (scop); - /* When debugging, enable the following code. This cannot be used - in production compilers because it calls "system". */ -#if 0 - { - int x; - FILE *stream = fopen ("/tmp/allscops.dot", "w"); - gcc_assert (stream); + dot_all_sese (stderr, scops); - dot_all_scops_1 (stream, scops); - fclose (stream); - x = system ("dotty /tmp/allscops.dot &"); - } -#else - dot_all_scops_1 (stderr, scops); -#endif + scops.release (); +} + +DEBUG_FUNCTION void +dot_cfg () +{ + vec scops; + scops.create (1); + dot_all_sese (stderr, scops); + scops.release (); } /* Return true if BB is empty, contains only DEBUG_INSNs. */ @@ -552,9 +528,20 @@ public: static edge get_nearest_pdom_with_single_exit (basic_block dom); - /* Print S to FILE. */ - static void print_sese (FILE *file, sese_l s); + /* Pretty printers. */ + + static void print_edge (FILE *file, const_edge e) + { + fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index); + } + + static void print_sese (FILE *file, sese_l s) + { + fprintf (file, "(entry_"); print_edge (file, s.entry); + fprintf (file, ", exit_"); print_edge (file, s.exit); + fprintf (file, ")\n"); + } /* Merge scops at same loop depth and returns the new sese. Returns a new SESE when merge was successful, INVALID_SESE otherwise. */ @@ -717,9 +704,14 @@ scop_detection::get_nearest_dom_with_single_entry (basic_block dom) { edge e1 = (*dom->preds)[0]; edge e2 = (*dom->preds)[1]; - if (dominated_by_p (CDI_DOMINATORS, e2->src, e1->src)) + loop_p l = dom->loop_father; + loop_p l1 = e1->src->loop_father; + loop_p l2 = e2->src->loop_father; + if (l != l1 + && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src)) return e1; - if (dominated_by_p (CDI_DOMINATORS, e1->src, e2->src)) + if (l != l2 + && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src)) return e2; } @@ -738,39 +730,35 @@ scop_detection::get_nearest_dom_with_single_entry (basic_block dom) back-loop the back-edge is not counted. */ edge -scop_detection::get_nearest_pdom_with_single_exit (basic_block dom) +scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom) { - if (!dom->succs) + if (!pdom->succs) return NULL; - if (dom->succs->length () == 2) + if (pdom->succs->length () == 2) { - edge e1 = (*dom->succs)[0]; - edge e2 = (*dom->succs)[1]; - if (dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest)) + edge e1 = (*pdom->succs)[0]; + edge e2 = (*pdom->succs)[1]; + loop_p l = pdom->loop_father; + loop_p l1 = e1->dest->loop_father; + loop_p l2 = e2->dest->loop_father; + if (l != l1 + && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest)) return e1; - if (dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest)) + if (l != l2 + && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest)) return e2; } - while (dom->succs->length () != 1) + while (pdom->succs->length () != 1) { - if (dom->succs->length () < 1) + if (pdom->succs->length () < 1) return NULL; - dom = get_immediate_dominator (CDI_POST_DOMINATORS, dom); - if (!dom->succs) + pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom); + if (!pdom->succs) return NULL; } - return (*dom->succs)[0]; -} - -/* Print S to FILE. */ -void -scop_detection::print_sese (FILE *file, sese_l s) -{ - fprintf (file, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n", - s.entry->src->index, s.entry->dest->index, - s.exit->src->index, s.exit->dest->index); + return (*pdom->succs)[0]; } /* Merge scops at same loop depth and returns the new sese. @@ -815,6 +803,9 @@ scop_detection::merge_sese (sese_l first, sese_l second) const sese_l combined (entry, exit); + DEBUG_PRINT (dp << "checking combined sese: "; + print_sese (dump_file, combined)); + /* FIXME: We could iterate to find the dom which dominates pdom, and pdom which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and EXIT->DEST should be in the same loop nest. */ diff --git a/gcc/graphite.h b/gcc/graphite.h index 30272bbc46c..c7589baef4f 100644 --- a/gcc/graphite.h +++ b/gcc/graphite.h @@ -465,7 +465,7 @@ extern bool build_poly_scop (scop_p); extern bool graphite_regenerate_ast_isl (scop_p); extern void build_scops (vec *); -extern void dot_all_scops (vec); -extern void dot_scop (scop_p); - +extern void dot_all_sese (FILE *, vec &); +extern void dot_sese (sese_l &); +extern void dot_cfg (); #endif diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index ebeab6b423c..312224800be 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2015-12-04 Aditya Kumar + Sebastian Pop + + PR tree-optimization/68693 + * gfortran.dg/graphite/pr68693.f90: New test. + 2015-12-04 James Greenhalgh * gcc.c-torture/compile/20151204.c: New. diff --git a/gcc/testsuite/gfortran.dg/graphite/pr68693.f90 b/gcc/testsuite/gfortran.dg/graphite/pr68693.f90 new file mode 100644 index 00000000000..24b85e3b0d6 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/graphite/pr68693.f90 @@ -0,0 +1,35 @@ +! { dg-options "-floop-nest-optimize -O2" } +MODULE dbcsr_index_operations + INTERFACE dbcsr_build_row_index + END INTERFACE +CONTAINS + SUBROUTINE merge_index_arrays (new_row_i, new_col_i, new_blk_p, new_size,& + old_row_i, old_col_i, old_blk_p, old_size,& + add_ip, add_size, new_blk_d, old_blk_d,& + added_size_offset, added_sizes, added_size, added_nblks, error) + INTEGER, DIMENSION(new_size), & + INTENT(OUT) :: new_blk_p, new_col_i, & + new_row_i + INTEGER, INTENT(IN) :: old_size + INTEGER, DIMENSION(old_size), INTENT(IN) :: old_blk_p, old_col_i, & + old_row_i + INTEGER, DIMENSION(new_size), & + INTENT(OUT), OPTIONAL :: new_blk_d + INTEGER, DIMENSION(old_size), & + INTENT(IN), OPTIONAL :: old_blk_d + INTEGER, DIMENSION(:), INTENT(IN), & + OPTIONAL :: added_sizes + INTEGER, INTENT(OUT), OPTIONAL :: added_size, added_nblks + LOGICAL :: multidata + IF (add_size .GT. 0) THEN + IF (old_size .EQ. 0) THEN + IF (PRESENT (added_size)) added_size = SUM (added_sizes) + ENDIF + ELSE + new_row_i(1:old_size) = old_row_i(1:old_size) + new_col_i(1:old_size) = old_col_i(1:old_size) + new_blk_p(1:old_size) = old_blk_p(1:old_size) + IF (multidata) new_blk_d(1:old_size) = old_blk_d(1:old_size) + ENDIF + END SUBROUTINE merge_index_arrays +END MODULE dbcsr_index_operations -- 2.30.2