Re: [PATCH 15/40] graphite: Extend SCoP detection dump output

["Harwath, Frederik" <Frederik_Harwath@mentor.com>]

[-- Attachment #1: Type: text/plain, Size: 2576 bytes --]

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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-graphite-Extend-SCoP-detection-dump-output.patch --]
[-- Type: text/x-patch; name="0001-graphite-Extend-SCoP-detection-dump-output.patch", Size: 11601 bytes --]

From fb268a37704b1598a84051c735514ff38adad038 Mon Sep 17 00:00:00 2001
From: Frederik Harwath <frederik@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