openmp: Handle even some combined non-rectangular loops

The number of loops computation and logical iteration -> actual iterator values
computations can now be done separately even on composite constructs (though
for triangular loops it would still be more efficient to propagate a few values
through, will handle that incrementally).
simd and taskloop are still unhandled.

2020-08-05  Jakub Jelinek  <jakub@redhat.com>

	* omp-expand.c (expand_omp_for): Don't disallow combined non-rectangular
	loops.

	* testsuite/libgomp.c/loop-22.c: New test.
	* testsuite/libgomp.c/loop-23.c: New test.

(cherry picked from commit 9f3abfb84e2a7ca115b0550c32308b5ada3e6a46)

5 files changed, 394 insertions, 5 deletions

diff --git a/gcc/ChangeLog.omp b/gcc/ChangeLog.omp
index 079e956..7335bce 100644
--- a/gcc/ChangeLog.omp
+++ b/gcc/ChangeLog.omp
@@ -3,6 +3,14 @@
 	Backport from mainline
 	2020-08-05  Jakub Jelinek  <jakub@redhat.com>
 
+	* omp-expand.c (expand_omp_for): Don't disallow combined non-rectangular
+	loops.
+
+2021-02-09  Kwok Cheung Yeung  <kcy@codesourcery.com>
+
+	Backport from mainline
+	2020-08-05  Jakub Jelinek  <jakub@redhat.com>
+
 	* omp-expand.c (expand_omp_for_init_counts): Remember
 	first_inner_iterations, factor and n1o from the number of iterations
 	computation in *fd.
diff --git a/gcc/omp-expand.c b/gcc/omp-expand.c
index 8dfdcba..055f284 100644
--- a/gcc/omp-expand.c
+++ b/gcc/omp-expand.c
@@ -7734,11 +7734,6 @@ expand_omp_for (struct omp_region *region, gimple *inner_stmt)
   else if (fd.sched_kind == OMP_CLAUSE_SCHEDULE_STATIC
 	   && !fd.have_ordered)
     {
-      if (fd.non_rect
-	  && (gimple_omp_for_combined_into_p (fd.for_stmt)
-	      || gimple_omp_for_combined_p (fd.for_stmt)))
-	sorry_at (gimple_location (fd.for_stmt),
-		  "non-rectangular OpenMP loops not supported yet");
       if (fd.chunk_size == NULL)
 	expand_omp_for_static_nochunk (region, &fd, inner_stmt);
       else
diff --git a/libgomp/ChangeLog.omp b/libgomp/ChangeLog.omp
index 364d02a..fc3c71a2 100644
--- a/libgomp/ChangeLog.omp
+++ b/libgomp/ChangeLog.omp
@@ -1,6 +1,14 @@
 2021-02-09  Kwok Cheung Yeung  <kcy@codesourcery.com>
 
 	Backport from mainline
+	2020-08-05  Jakub Jelinek  <jakub@redhat.com>
+
+	* testsuite/libgomp.c/loop-22.c: New test.
+	* testsuite/libgomp.c/loop-23.c: New test.
+
+2021-02-09  Kwok Cheung Yeung  <kcy@codesourcery.com>
+
+	Backport from mainline
 	2020-07-14  Jakub Jelinek  <jakub@redhat.com>
 
 	* testsuite/libgomp.c/loop-21.c: New test.
diff --git a/libgomp/testsuite/libgomp.c/loop-22.c b/libgomp/testsuite/libgomp.c/loop-22.c
new file mode 100644
index 0000000..b07efee
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/loop-22.c
@@ -0,0 +1,189 @@
+/* { dg-do run } */
+
+extern void abort (void);
+
+signed char v[5][7][9][21][4][42][3];
+volatile int zero = 0, one = 1, two = 2, three = 3;
+volatile int five = 5, seven = 7, nine = 9, eleven = 11;
+
+int
+main ()
+{
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int k = 0; k < 9; k++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int m = 7; m < 11; m++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    v[i][j][k][l][m - 7][n][o] = 1;
+
+  int niters = 0;
+  #pragma omp teams reduction(+:niters)
+  #pragma omp distribute collapse(7)
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int k = 0; k < 9; k++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int m = 7; m < 11; m++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    {
+      niters++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || k < 0 || k >= 9
+	  || l < 2 * j || l >= 3 * j
+	  || m < 7 || m >= 11
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][k][l][m - 7][n][o] != 1)
+	abort ();
+      v[i][j][k][l][m - 7][n][o]++;
+    }
+
+  if (niters != 117180)
+    abort ();
+
+  int niters2 = 0;
+  #pragma omp teams reduction(+:niters2)
+  #pragma omp distribute collapse(7)
+  for (int i = zero; i < five; i += one)
+  for (int j = seven - one; j >= zero; j -= one)
+  for (int k = nine - one; k >= zero; k += -one)
+  for (int l = two * j + zero; l < three * j; l += one)
+  for (int m = eleven - one; m >= seven; m -= one)
+  for (int n = two * l - one; n > one * l - one; n -= one)
+  for (int o = zero; o < three; o += one)
+    {
+      niters2++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || k < 0 || k >= 9
+	  || l < 2 * j || l >= 3 * j
+	  || m < 7 || m >= 11
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][k][l][m - 7][n][o] != 2)
+	abort ();
+      v[i][j][k][l][m - 7][n][o]++;
+    }
+
+  if (niters2 != 117180)
+    abort ();
+
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int k = 0; k < 9; k++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int m = 7; m < 11; m++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    if (v[i][j][k][l][m - 7][n][o] != 3)
+      abort ();
+
+  int niters3 = 0;
+  #pragma omp teams reduction(+:niters3)
+  #pragma omp distribute collapse(5)
+  for (int i = 4; i >= 0; i--)
+  for (int j = 6; j >= 0; --j)
+  for (int l = 3 * j - 1; l >= 2 * j; l--)
+  for (int n = 2 * l + -1; n > l - 1; --n)
+  for (int o = 2; o >= 0; o--)
+    {
+      niters3++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][0][l][0][n][o] != 3)
+	abort ();
+      v[i][j][0][l][0][n][o]++;
+    }
+
+  if (niters3 != 3255)
+    abort ();
+
+  int niters4 = 0;
+  #pragma omp teams reduction(+:niters4)
+  #pragma omp distribute collapse(5)
+  for (int i = zero; i < five; i += one)
+  for (int j = zero; j <= seven - one; j += one)
+  for (int l = j * two; l < three * j + zero; l += one)
+  for (int n = one * l; n <= l * two - one; n += one)
+  for (int o = zero; o < three; o += one)
+    {
+      niters4++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][0][l][0][n][o] != 4)
+	abort ();
+      v[i][j][0][l][0][n][o]++;
+    }
+
+  if (niters4 != 3255)
+    abort ();
+
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    if (v[i][j][0][l][0][n][o] != 5)
+      abort ();
+
+  int niters5 = 0;
+  #pragma omp teams reduction(+:niters5)
+  #pragma omp distribute collapse(3)
+  for (int j = 6; j >= 0; --j)
+  for (int l = 2 * j; l <= 3 * j - 1; l++)
+  for (int n = 2 * l + -1; n > l - 1; --n)
+    {
+      niters5++;
+      if (j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l)
+	abort ();
+      if (v[0][j][0][l][0][n][0] != 5)
+	abort ();
+      v[0][j][0][l][0][n][0]++;
+    }
+
+  if (niters5 != 217)
+    abort ();
+
+  int niters6 = 0;
+  #pragma omp teams reduction(+:niters6)
+  #pragma omp distribute collapse(3)
+  for (int j = seven - one; j > - one; j -= one)
+  for (int l = j * three - one; l >= j * two + zero; l += -one)
+  for (int n = two * l - one; n > l - one; n -= one)
+    {
+      niters6++;
+      if (j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l)
+	abort ();
+      if (v[0][j][0][l][0][n][0] != 6)
+	abort ();
+      v[0][j][0][l][0][n][0]++;
+    }
+
+  if (niters6 != 217)
+    abort ();
+
+  for (int j = 0; j < 7; j++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int n = l; n < 2 * l; n++)
+    if (v[0][j][0][l][0][n][0] != 7)
+      abort ();
+  return 0;
+}
diff --git a/libgomp/testsuite/libgomp.c/loop-23.c b/libgomp/testsuite/libgomp.c/loop-23.c
new file mode 100644
index 0000000..30bb82c
--- /dev/null
+++ b/libgomp/testsuite/libgomp.c/loop-23.c
@@ -0,0 +1,189 @@
+/* { dg-do run } */
+
+extern void abort (void);
+
+signed char v[5][7][9][21][4][42][3];
+volatile int zero = 0, one = 1, two = 2, three = 3;
+volatile int five = 5, seven = 7, nine = 9, eleven = 11;
+
+int
+main ()
+{
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int k = 0; k < 9; k++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int m = 7; m < 11; m++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    v[i][j][k][l][m - 7][n][o] = 1;
+
+  int niters = 0;
+  #pragma omp teams reduction(+:niters)
+  #pragma omp distribute parallel for collapse(7) reduction(+:niters)
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int k = 0; k < 9; k++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int m = 7; m < 11; m++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    {
+      niters++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || k < 0 || k >= 9
+	  || l < 2 * j || l >= 3 * j
+	  || m < 7 || m >= 11
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][k][l][m - 7][n][o] != 1)
+	abort ();
+      v[i][j][k][l][m - 7][n][o]++;
+    }
+
+  if (niters != 117180)
+    abort ();
+
+  int niters2 = 0;
+  #pragma omp teams reduction(+:niters2)
+  #pragma omp distribute parallel for collapse(7) reduction(+:niters2)
+  for (int i = zero; i < five; i += one)
+  for (int j = seven - one; j >= zero; j -= one)
+  for (int k = nine - one; k >= zero; k += -one)
+  for (int l = two * j + zero; l < three * j; l += one)
+  for (int m = eleven - one; m >= seven; m -= one)
+  for (int n = two * l - one; n > one * l - one; n -= one)
+  for (int o = zero; o < three; o += one)
+    {
+      niters2++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || k < 0 || k >= 9
+	  || l < 2 * j || l >= 3 * j
+	  || m < 7 || m >= 11
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][k][l][m - 7][n][o] != 2)
+	abort ();
+      v[i][j][k][l][m - 7][n][o]++;
+    }
+
+  if (niters2 != 117180)
+    abort ();
+
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int k = 0; k < 9; k++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int m = 7; m < 11; m++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    if (v[i][j][k][l][m - 7][n][o] != 3)
+      abort ();
+
+  int niters3 = 0;
+  #pragma omp teams reduction(+:niters3)
+  #pragma omp distribute parallel for collapse(5) reduction(+:niters3)
+  for (int i = 4; i >= 0; i--)
+  for (int j = 6; j >= 0; --j)
+  for (int l = 3 * j - 1; l >= 2 * j; l--)
+  for (int n = 2 * l + -1; n > l - 1; --n)
+  for (int o = 2; o >= 0; o--)
+    {
+      niters3++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][0][l][0][n][o] != 3)
+	abort ();
+      v[i][j][0][l][0][n][o]++;
+    }
+
+  if (niters3 != 3255)
+    abort ();
+
+  int niters4 = 0;
+  #pragma omp teams reduction(+:niters4)
+  #pragma omp distribute parallel for collapse(5) reduction(+:niters4)
+  for (int i = zero; i < five; i += one)
+  for (int j = zero; j <= seven - one; j += one)
+  for (int l = j * two; l < three * j + zero; l += one)
+  for (int n = one * l; n <= l * two - one; n += one)
+  for (int o = zero; o < three; o += one)
+    {
+      niters4++;
+      if (i < 0 || i >= 5
+	  || j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l
+	  || o < 0 || o >= 3)
+	abort ();
+      if (v[i][j][0][l][0][n][o] != 4)
+	abort ();
+      v[i][j][0][l][0][n][o]++;
+    }
+
+  if (niters4 != 3255)
+    abort ();
+
+  for (int i = 0; i < 5; i++)
+  for (int j = 0; j < 7; j++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int n = l; n < 2 * l; n++)
+  for (int o = 0; o < 3; o++)
+    if (v[i][j][0][l][0][n][o] != 5)
+      abort ();
+
+  int niters5 = 0;
+  #pragma omp teams reduction(+:niters5)
+  #pragma omp distribute parallel for collapse(3) reduction(+:niters5)
+  for (int j = 6; j >= 0; --j)
+  for (int l = 2 * j; l <= 3 * j - 1; l++)
+  for (int n = 2 * l + -1; n > l - 1; --n)
+    {
+      niters5++;
+      if (j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l)
+	abort ();
+      if (v[0][j][0][l][0][n][0] != 5)
+	abort ();
+      v[0][j][0][l][0][n][0]++;
+    }
+
+  if (niters5 != 217)
+    abort ();
+
+  int niters6 = 0;
+  #pragma omp teams reduction(+:niters6)
+  #pragma omp distribute parallel for collapse(3) reduction(+:niters6)
+  for (int j = seven - one; j > - one; j -= one)
+  for (int l = j * three - one; l >= j * two + zero; l += -one)
+  for (int n = two * l - one; n > l - one; n -= one)
+    {
+      niters6++;
+      if (j < 0 || j >= 7
+	  || l < 2 * j || l >= 3 * j
+	  || n < l || n >= 2 * l)
+	abort ();
+      if (v[0][j][0][l][0][n][0] != 6)
+	abort ();
+      v[0][j][0][l][0][n][0]++;
+    }
+
+  if (niters6 != 217)
+    abort ();
+
+  for (int j = 0; j < 7; j++)
+  for (int l = 2 * j; l < 3 * j; l++)
+  for (int n = l; n < 2 * l; n++)
+    if (v[0][j][0][l][0][n][0] != 7)
+      abort ();
+  return 0;
+}