Hi Richard,
On Tue, 2022-05-17 at 08:21 +0000, Richard Biener wrote:
> On Mon, 16 May 2022, Tobias Burnus wrote:
>
> > As requested by Richard: Rediffed patch.
> >
> > Changes: s/.c/.cc/ + some whitespace changes.
> > (At least in my email reader, some <tab> were lost. I also fixed
> > too-long line
> > issues.)
> >
> > In addition, FOR_EACH_LOOP was replaced by 'for (auto loop : ...'
> > (macro was removed late in GCC 12 development ? r12-2605-
> > ge41ba804ba5f5c)
> >
> > Otherwise, it should be identical to Frederik's patch, earlier in
> > this thread.
> >
> > On 15.12.21 16:54, Frederik Harwath wrote:
> > > Extend dump output to make understanding why Graphite rejects to
> > > include a loop in a SCoP easier (for GCC developers).
> >
> > OK for mainline?
>
> + if (printed)
> + fprintf (file, "\b\b");
>
> please find other means of omitting ", ", like by printing it
> _before_ the number but only for the second and following loop
> number.
Done.
>
> I'll also note that
>
> +static void
> +print_sese_loop_numbers (FILE *file, sese_l sese)
> +{
> + bool printed = false;
> + for (auto loop : loops_list (cfun, 0))
> + {
> + if (loop_in_sese_p (loop, sese))
> + fprintf (file, "%d, ", loop->num);
> + printed = true;
> + }
>
> is hardly optimal. Please instead iterate over
> sese.entry->dest->loop_father and children instead which you can do
> by passing that as extra argument to loops_list.
Done.
This had to be extended a little bit, because a SCoP
can consist of consecutive loop-nests and iterating
only over "loops_list (cfun, LI_INCLUDE_ROOT, sese.entry->dest-
>loop_father))" would output only the loops from the first
loop-nest in the SCoP (cf. the test file scop-22a.c that I added).
>
> +
> + if (dump_file && dump_flags & TDF_DETAILS)
> + {
> + fprintf (dump_file, "Loops in SCoP: ");
> + for (auto loop : loops_list (cfun, 0))
> + if (loop_in_sese_p (loop, s))
> + fprintf (dump_file, "%d ", loop->num);
> + fprintf (dump_file, "\n");
> + }
>
> you are duplicating functionality of the function you just added ...
>
Fixed.
> Otherwise looks OK to me.
Can I commit the revised patch?
Thanks for your review,
Frederik
-----------------
Siemens Electronic Design Automation GmbH; Anschrift: Arnulfstraße 201, 80634
München; Gesellschaft mit beschränkter Haftung; Geschäftsführer: Thomas
Heurung, Frank Thürauf; Sitz der Gesellschaft: München; Registergericht
München, HRB 106955
From fb268a37704b1598a84051c735514ff38adad038 Mon Sep 17 00:00:00 2001
From: Frederik Harwath <frede...@codesourcery.com>
Date: Wed, 18 May 2022 07:59:42 +0200
Subject: [PATCH] graphite: Extend SCoP detection dump output
Extend dump output to make understanding why Graphite rejects to
include a loop in a SCoP easier (for GCC developers).
gcc/ChangeLog:
* graphite-scop-detection.cc (scop_detection::can_represent_loop):
Output reason for failure to dump file.
(scop_detection::harmful_loop_in_region): Likewise.
(scop_detection::graphite_can_represent_expr): Likewise.
(scop_detection::stmt_has_simple_data_refs_p): Likewise.
(scop_detection::stmt_simple_for_scop_p): Likewise.
(print_sese_loop_numbers): New function.
(scop_detection::add_scop): Use from here.
gcc/testsuite/ChangeLog:
* gcc.dg/graphite/scop-22a.c: New test.
---
gcc/graphite-scop-detection.cc | 184 ++++++++++++++++++++---
gcc/testsuite/gcc.dg/graphite/scop-22a.c | 56 +++++++
2 files changed, 219 insertions(+), 21 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/graphite/scop-22a.c
diff --git a/gcc/graphite-scop-detection.cc b/gcc/graphite-scop-detection.cc
index 8c0ee9975579..9792d87ee0ae 100644
--- a/gcc/graphite-scop-detection.cc
+++ b/gcc/graphite-scop-detection.cc
@@ -69,12 +69,27 @@ public:
fprintf (output.dump_file, "%d", i);
return output;
}
+
friend debug_printer &
operator<< (debug_printer &output, const char *s)
{
fprintf (output.dump_file, "%s", s);
return output;
}
+
+ friend debug_printer &
+ operator<< (debug_printer &output, gimple* stmt)
+ {
+ print_gimple_stmt (output.dump_file, stmt, 0, TDF_VOPS | TDF_MEMSYMS);
+ return output;
+ }
+
+ friend debug_printer &
+ operator<< (debug_printer &output, tree t)
+ {
+ print_generic_expr (output.dump_file, t, TDF_SLIM);
+ return output;
+ }
} dp;
#define DEBUG_PRINT(args) do \
@@ -506,6 +521,27 @@ scop_detection::merge_sese (sese_l first, sese_l second) const
return combined;
}
+/* Print the loop numbers of the loops contained in SESE to FILE. */
+
+static void
+print_sese_loop_numbers (FILE *file, sese_l sese)
+{
+ bool first_loop = true;
+ for (loop_p nest = sese.entry->dest->loop_father; nest; nest = nest->next)
+ {
+ if (!loop_in_sese_p (nest, sese))
+ break;
+
+ for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT, nest))
+ {
+ gcc_assert (loop_in_sese_p (loop, sese));
+
+ fprintf (file, "%s%d", first_loop ? "" : ", ", loop->num);
+ first_loop = false;
+ }
+ }
+}
+
/* Build scop outer->inner if possible. */
void
@@ -519,6 +555,10 @@ scop_detection::build_scop_depth (loop_p loop)
if (! next
|| harmful_loop_in_region (next))
{
+ if (next)
+ DEBUG_PRINT (dp << "[scop-detection] Discarding SCoP on loops ";
+ print_sese_loop_numbers (dump_file, next);
+ dp << " because of harmful loops\n");
if (s)
add_scop (s);
build_scop_depth (loop);
@@ -560,14 +600,63 @@ scop_detection::can_represent_loop (loop_p loop, sese_l scop)
|| !single_pred_p (loop->latch)
|| exit->src != single_pred (loop->latch)
|| !empty_block_p (loop->latch))
- return false;
+ {
+ DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop shape unsupported.\n");
+ return false;
+ }
+
+ bool edge_irreducible = (loop_preheader_edge (loop)->flags
+ & EDGE_IRREDUCIBLE_LOOP);
+ if (edge_irreducible)
+ {
+ DEBUG_PRINT (dp << "[can_represent_loop-fail] "
+ "Loop is not a natural loop.\n");
+ return false;
+ }
+
+ bool niter_is_unconditional = number_of_iterations_exit (loop,
+ single_exit (loop),
+ &niter_desc, false);
+
+ if (!niter_is_unconditional)
+ {
+ DEBUG_PRINT (dp << "[can_represent_loop-fail] "
+ "Loop niter not unconditional.\n"
+ "Condition: " << niter_desc.assumptions << "\n");
+ return false;
+ }
+
+ niter = number_of_latch_executions (loop);
+ if (!niter)
+ {
+ DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter unknown.\n");
+ return false;
+ }
+ if (!niter_desc.control.no_overflow)
+ {
+ DEBUG_PRINT (dp << "[can_represent_loop-fail] Loop niter can overflow.\n");
+ return false;
+ }
- return !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
- && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
- && niter_desc.control.no_overflow
- && (niter = number_of_latch_executions (loop))
- && !chrec_contains_undetermined (niter)
- && graphite_can_represent_expr (scop, loop, niter);
+ bool undetermined_coefficients = chrec_contains_undetermined (niter);
+ if (undetermined_coefficients)
+ {
+ DEBUG_PRINT (dp << "[can_represent_loop-fail] "
+ "Loop niter chrec contains undetermined "
+ "coefficients.\n");
+ return false;
+ }
+
+ bool can_represent_expr = graphite_can_represent_expr (scop, loop, niter);
+ if (!can_represent_expr)
+ {
+ DEBUG_PRINT (dp << "[can_represent_loop-fail] "
+ << "Loop niter expression cannot be represented: "
+ << niter << "\n");
+ return false;
+ }
+
+ return true;
}
/* Return true when BEGIN is the preheader edge of a loop with a single exit
@@ -640,6 +729,13 @@ scop_detection::add_scop (sese_l s)
scops.safe_push (s);
DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
+
+ if (dump_file && dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "Loops in SCoP: ");
+ print_sese_loop_numbers (dump_file, s);
+ fprintf (dump_file, "\n");
+ }
}
/* Return true when a statement in SCOP cannot be represented by Graphite. */
@@ -665,7 +761,12 @@ scop_detection::harmful_loop_in_region (sese_l scop) const
/* The basic block should not be part of an irreducible loop. */
if (bb->flags & BB_IRREDUCIBLE_LOOP)
- return true;
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] Found bb in irreducible "
+ "loop.\n");
+
+ return true;
+ }
/* Check for unstructured control flow: CFG not generated by structured
if-then-else. */
@@ -676,7 +777,11 @@ scop_detection::harmful_loop_in_region (sese_l scop) const
FOR_EACH_EDGE (e, ei, bb->succs)
if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
&& !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
- return true;
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] Found unstructured "
+ "control flow.\n");
+ return true;
+ }
}
/* Collect all loops in the current region. */
@@ -688,7 +793,11 @@ scop_detection::harmful_loop_in_region (sese_l scop) const
for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
!gsi_end_p (gsi); gsi_next (&gsi))
if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
- return true;
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] "
+ "Found harmful statement.\n");
+ return true;
+ }
for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
dom;
@@ -731,9 +840,10 @@ scop_detection::harmful_loop_in_region (sese_l scop) const
&& ! loop_nest_has_data_refs (loop))
{
DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
- << "does not have any data reference.\n");
+ << " does not have any data reference.\n");
return true;
}
+ DEBUG_PRINT (dp << "[scop-detection] loop_" << loop->num << " is harmless.\n");
}
return false;
@@ -922,7 +1032,21 @@ scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
tree expr)
{
tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
- return graphite_can_represent_scev (scop, scev);
+ bool can_represent = graphite_can_represent_scev (scop, scev);
+
+ if (!can_represent)
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "[graphite_can_represent_expr] Cannot represent scev \"");
+ print_generic_expr (dump_file, scev, TDF_SLIM);
+ fprintf (dump_file, "\" of expression ");
+ print_generic_expr (dump_file, expr, TDF_SLIM);
+ fprintf (dump_file, " in loop %d\n", loop->num);
+ }
+ }
+ return can_represent;
}
/* Return true if the data references of STMT can be represented by Graphite.
@@ -938,7 +1062,11 @@ scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
auto_vec<data_reference_p> drs;
if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
- return false;
+ {
+ DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
+ "Unanalyzable statement.\n");
+ return false;
+ }
int j;
data_reference_p dr;
@@ -946,7 +1074,12 @@ scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
{
for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
- return false;
+ {
+ DEBUG_PRINT (dp << "[stmt_has_simple_data_refs_p] "
+ "Cannot represent access function SCEV: "
+ << DR_ACCESS_FN (dr, i) << "\n");
+ return false;
+ }
}
return true;
@@ -1027,14 +1160,23 @@ scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
for (unsigned i = 0; i < 2; ++i)
{
tree op = gimple_op (stmt, i);
- if (!graphite_can_represent_expr (scop, loop, op)
- /* We can only constrain on integer type. */
- || ! INTEGRAL_TYPE_P (TREE_TYPE (op)))
+ if (!graphite_can_represent_expr (scop, loop, op))
+ {
+ DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
+ "[scop-detection-fail] "
+ "Graphite cannot represent cond "
+ "stmt operator expression.\n"));
+ DEBUG_PRINT (dp << op << "\n");
+ return false;
+ }
+
+ if (! INTEGRAL_TYPE_P (TREE_TYPE (op)))
{
- DEBUG_PRINT (dp << "[scop-detection-fail] "
- << "Graphite cannot represent stmt:\n";
- print_gimple_stmt (dump_file, stmt, 0,
- TDF_VOPS | TDF_MEMSYMS));
+ DEBUG_PRINT (dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
+ "[scop-detection-fail] "
+ "Graphite cannot represent cond "
+ "statement operator. "
+ "Type must be integral.\n"));
return false;
}
}
diff --git a/gcc/testsuite/gcc.dg/graphite/scop-22a.c b/gcc/testsuite/gcc.dg/graphite/scop-22a.c
new file mode 100644
index 000000000000..00d4b5315aeb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/scop-22a.c
@@ -0,0 +1,56 @@
+/* { dg-require-effective-target size32plus } */
+double u[1782225];
+
+void foo(int N, int *res)
+{
+ int i, j;
+ double a, b;
+ double sum = 0.0;
+
+ for (j = 3; j < N; j = j * j)
+ {
+ sum += a + b;
+ }
+
+ /* Next two loops form first SCoP */
+ for (i = 0; i < N; i++)
+ sum += u[i];
+
+ for (i = 0; i < N; i++)
+ {
+ a = u[i];
+ u[i] = i * i;
+ b = u[i];
+ sum += a + b;
+ }
+
+ for (j = 3; j < N; j = j * j)
+ {
+ sum += a + b;
+ }
+
+ for (j = 3; j < N; j = j * j)
+ {
+ sum += a + b;
+ }
+
+ /* Next two loop-nests form second SCoP */
+ for (i = 0; i < N; i++)
+ sum += u[i];
+
+ for (i = 0; i < N; i++)
+ for (j = 0; j < N; j++)
+ {
+ a = u[i];
+ u[i] = i * i;
+ b = u[j];
+ sum += a + b;
+ }
+
+ *res = sum + N;
+}
+
+/* { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite"} } */
+/* { dg-final { scan-tree-dump-times "Loops in SCoP" 2 "graphite"} } */
+/* { dg-final { scan-tree-dump "Loops in SCoP: 2, 3" "graphite"} } */
+/* { dg-final { scan-tree-dump "Loops in SCoP: 6, 7, 8" "graphite"} } */
--
2.36.0
