openmp: Initial part of OpenMP 5.0 non-rectangular loop support

OpenMP 5.0 adds support for non-rectangular loop collapses, e.g.
triangular and more complex.

This patch deals just with the diagnostics so that they aren't rejected
immediately as before.  As the spec generally requires as before that the
iteration variable initializer and bound in the comparison as invariant
vs. the outermost loop, and just add some exceptional forms that can violate
that, we need to avoid folding the expressions until we can detect them and
in order to avoid folding it later on, I chose to use a TREE_VEC in those
expressions to hold the var_outer * expr1 + expr2 triplet, the patch adds
pretty-printing of that, gimplification etc. and just sorry_at during
omp expansion for now.

The next step will be to implement the different cases of that one by one.

2020-06-16  Jakub Jelinek  <jakub@redhat.com>

gcc/
	* tree.h (OMP_FOR_NON_RECTANGULAR): Define.
	* gimplify.c (gimplify_omp_for): Diagnose schedule, ordered
	or dist_schedule clause on non-rectangular loops.  Handle
	gimplification of non-rectangular lb/b expressions.  When changing
	iteration variable, adjust also non-rectangular lb/b expressions
	referencing that.
	* omp-general.h (struct omp_for_data_loop): Add m1, m2 and outer
	members.
	(struct omp_for_data): Add non_rect member.
	* omp-general.c (omp_extract_for_data): Handle non-rectangular
	loops.  Fill in non_rect, m1, m2 and outer.
	* omp-low.c (lower_omp_for): Handle non-rectangular lb/b expressions.
	* omp-expand.c (expand_omp_for): Emit sorry_at for unsupported
	non-rectangular loop cases and assert for cases that can't be
	non-rectangular.
	* tree-pretty-print.c (dump_mem_ref): Formatting fix.
	(dump_omp_loop_non_rect_expr): New function.
	(dump_generic_node): Handle non-rectangular OpenMP loops.
	* tree-pretty-print.h (dump_omp_loop_non_rect_expr): Declare.
	* gimple-pretty-print.c (dump_gimple_omp_for): Handle non-rectangular
	OpenMP loops.
gcc/c-family/
	* c-common.h (c_omp_check_loop_iv_exprs): Add an int argument.
	* c-omp.c (struct c_omp_check_loop_iv_data): Add maybe_nonrect and
	idx members.
	(c_omp_is_loop_iterator): New function.
	(c_omp_check_loop_iv_r): Use it.  Add support for silent scanning
	if outer loop iterator is present.  Perform duplicate checking through
	hash_set in the function rather than expecting caller to do that.
	Pass NULL instead of d->ppset to walk_tree_1.
	(c_omp_check_nonrect_loop_iv): New function.
	(c_omp_check_loop_iv): Use it.  Fill in new members, allow
	non-rectangular loop forms, diagnose multiple associated loops with
	the same iterator.  Pass NULL instead of &pset to walk_tree_1.
	(c_omp_check_loop_iv_exprs): Likewise.
gcc/c/
	* c-parser.c (c_parser_expr_no_commas): Save, clear and restore
	c_in_omp_for.
	(c_parser_omp_for_loop): Set c_in_omp_for around some calls to avoid
	premature c_fully_fold.  Defer explicit c_fully_fold calls to after
	c_finish_omp_for.
	* c-tree.h (c_in_omp_for): Declare.
	* c-typeck.c (c_in_omp_for): Define.
	(build_modify_expr): Avoid c_fully_fold if c_in_omp_for.
	(digest_init): Likewise.
	(build_binary_op): Likewise.
gcc/cp/
	* semantics.c (handle_omp_for_class_iterator): Adjust
	c_omp_check_loop_iv_exprs caller.
	(finish_omp_for): Likewise.  Don't call fold_build_cleanup_point_expr
	before calling c_finish_omp_for and c_omp_check_loop_iv, move it
	after those calls.
	* pt.c (tsubst_omp_for_iterator): Handle non-rectangular loops.
gcc/testsuite/
	* c-c++-common/gomp/loop-6.c: New test.
	* gcc.dg/gomp/loop-1.c: Don't expect diagnostics on valid
	non-rectangular loops.
	* gcc.dg/gomp/loop-2.c: New test.
	* g++.dg/gomp/loop-1.C: Don't expect diagnostics on valid
	non-rectangular loops.
	* g++.dg/gomp/loop-2.C: Likewise.
	* g++.dg/gomp/loop-5.C: New test.
	* g++.dg/gomp/loop-6.C: New test.

2 files changed, 298 insertions, 44 deletions

diff --git a/gcc/c-family/c-common.h b/gcc/c-family/c-common.h
index c74b23d..6162726 100644
--- a/gcc/c-family/c-common.h
+++ b/gcc/c-family/c-common.h
@@ -1196,7 +1196,7 @@ extern void c_finish_omp_taskyield (location_t);
 extern tree c_finish_omp_for (location_t, enum tree_code, tree, tree, tree,
 			      tree, tree, tree, tree, bool);
 extern bool c_omp_check_loop_iv (tree, tree, walk_tree_lh);
-extern bool c_omp_check_loop_iv_exprs (location_t, tree, tree, tree, tree,
+extern bool c_omp_check_loop_iv_exprs (location_t, tree, int, tree, tree, tree,
 				       walk_tree_lh);
 extern tree c_finish_oacc_wait (location_t, tree, tree);
 extern tree c_oacc_split_loop_clauses (tree, tree *, bool);
diff --git a/gcc/c-family/c-omp.c b/gcc/c-family/c-omp.c
index 6f8fba3..1ca2802 100644
--- a/gcc/c-family/c-omp.c
+++ b/gcc/c-family/c-omp.c
@@ -34,6 +34,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "memmodel.h"
 #include "attribs.h"
 #include "gimplify.h"
+#include "langhooks.h"
 
 
 /* Complete a #pragma oacc wait construct.  LOC is the location of
@@ -1041,13 +1042,37 @@ struct c_omp_check_loop_iv_data
 {
   tree declv;
   bool fail;
+  bool maybe_nonrect;
   location_t stmt_loc;
   location_t expr_loc;
   int kind;
+  int idx;
   walk_tree_lh lh;
   hash_set<tree> *ppset;
 };
 
+/* Return -1 if DECL is not a loop iterator in loop nest D, otherwise
+   return the index of the loop in which it is an iterator.
+   Return TREE_VEC_LENGTH (d->declv) if it is a C++ range for iterator.  */
+
+static int
+c_omp_is_loop_iterator (tree decl, struct c_omp_check_loop_iv_data *d)
+{
+  for (int i = 0; i < TREE_VEC_LENGTH (d->declv); i++)
+    if (decl == TREE_VEC_ELT (d->declv, i)
+	|| (TREE_CODE (TREE_VEC_ELT (d->declv, i)) == TREE_LIST
+	    && decl == TREE_PURPOSE (TREE_VEC_ELT (d->declv, i))))
+      return i;
+    else if (TREE_CODE (TREE_VEC_ELT (d->declv, i)) == TREE_LIST
+	     && TREE_CHAIN (TREE_VEC_ELT (d->declv, i))
+	     && (TREE_CODE (TREE_CHAIN (TREE_VEC_ELT (d->declv, i)))
+		 == TREE_VEC)
+	     && decl == TREE_VEC_ELT (TREE_CHAIN (TREE_VEC_ELT (d->declv,
+						  i)), 2))
+      return TREE_VEC_LENGTH (d->declv);
+  return -1;
+}
+
 /* Helper function called via walk_tree, to diagnose uses
    of associated loop IVs inside of lb, b and incr expressions
    of OpenMP loops.  */
@@ -1059,51 +1084,234 @@ c_omp_check_loop_iv_r (tree *tp, int *walk_subtrees, void *data)
     = (struct c_omp_check_loop_iv_data *) data;
   if (DECL_P (*tp))
     {
-      int i;
-      for (i = 0; i < TREE_VEC_LENGTH (d->declv); i++)
-	if (*tp == TREE_VEC_ELT (d->declv, i)
-	    || (TREE_CODE (TREE_VEC_ELT (d->declv, i)) == TREE_LIST
-		&& *tp == TREE_PURPOSE (TREE_VEC_ELT (d->declv, i)))
-	    || (TREE_CODE (TREE_VEC_ELT (d->declv, i)) == TREE_LIST
-		&& TREE_CHAIN (TREE_VEC_ELT (d->declv, i))
-		&& (TREE_CODE (TREE_CHAIN (TREE_VEC_ELT (d->declv, i)))
-		    == TREE_VEC)
-		&& *tp == TREE_VEC_ELT (TREE_CHAIN (TREE_VEC_ELT (d->declv,
-								  i)), 2)))
-	  {
-	    location_t loc = d->expr_loc;
-	    if (loc == UNKNOWN_LOCATION)
-	      loc = d->stmt_loc;
-	    switch (d->kind)
-	      {
-	      case 0:
-		error_at (loc, "initializer expression refers to "
-			       "iteration variable %qD", *tp);
-		break;
-	      case 1:
-		error_at (loc, "condition expression refers to "
-			       "iteration variable %qD", *tp);
-		break;
-	      case 2:
-		error_at (loc, "increment expression refers to "
-			       "iteration variable %qD", *tp);
-		break;
-	      }
-	    d->fail = true;
-	  }
+      int idx = c_omp_is_loop_iterator (*tp, d);
+      if (idx == -1)
+	return NULL_TREE;
+
+      if ((d->kind & 4) && idx < d->idx)
+	{
+	  d->maybe_nonrect = true;
+	  return NULL_TREE;
+	}
+
+      if (d->ppset->add (*tp))
+	return NULL_TREE;
+
+      location_t loc = d->expr_loc;
+      if (loc == UNKNOWN_LOCATION)
+	loc = d->stmt_loc;
+
+      switch (d->kind & 3)
+	{
+	case 0:
+	  error_at (loc, "initializer expression refers to "
+			 "iteration variable %qD", *tp);
+	  break;
+	case 1:
+	  error_at (loc, "condition expression refers to "
+			 "iteration variable %qD", *tp);
+	  break;
+	case 2:
+	  error_at (loc, "increment expression refers to "
+			 "iteration variable %qD", *tp);
+	  break;
+	}
+      d->fail = true;
     }
+  else if (d->ppset->add (*tp))
+    *walk_subtrees = 0;
   /* Don't walk dtors added by C++ wrap_cleanups_r.  */
   else if (TREE_CODE (*tp) == TRY_CATCH_EXPR
 	   && TRY_CATCH_IS_CLEANUP (*tp))
     {
       *walk_subtrees = 0;
       return walk_tree_1 (&TREE_OPERAND (*tp, 0), c_omp_check_loop_iv_r, data,
-			  d->ppset, d->lh);
+			  NULL, d->lh);
     }
 
   return NULL_TREE;
 }
 
+/* Check the allowed expressions for non-rectangular loop nest lb and b
+   expressions.  Return the outer var decl referenced in the expression.  */
+
+static tree
+c_omp_check_nonrect_loop_iv (tree *tp, struct c_omp_check_loop_iv_data *d,
+			     walk_tree_lh lh)
+{
+  d->maybe_nonrect = false;
+  if (d->fail)
+    return NULL_TREE;
+
+  hash_set<tree> pset;
+  hash_set<tree> *ppset = d->ppset;
+  d->ppset = &pset;
+
+  tree t = *tp;
+  if (TREE_CODE (t) == TREE_VEC
+      && TREE_VEC_LENGTH (t) == 3
+      && DECL_P (TREE_VEC_ELT (t, 0))
+      && c_omp_is_loop_iterator (TREE_VEC_ELT (t, 0), d) >= 0)
+    {
+      d->kind &= 3;
+      walk_tree_1 (&TREE_VEC_ELT (t, 1), c_omp_check_loop_iv_r, d, NULL, lh);
+      walk_tree_1 (&TREE_VEC_ELT (t, 1), c_omp_check_loop_iv_r, d, NULL, lh);
+      d->ppset = ppset;
+      return d->fail ? NULL_TREE : TREE_VEC_ELT (t, 0);
+    }
+
+  while (CONVERT_EXPR_P (t))
+    t = TREE_OPERAND (t, 0);
+
+  tree a1 = t, a2 = integer_zero_node;
+  bool neg_a1 = false, neg_a2 = false;
+  switch (TREE_CODE (t))
+    {
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+      a1 = TREE_OPERAND (t, 0);
+      a2 = TREE_OPERAND (t, 1);
+      while (CONVERT_EXPR_P (a1))
+	a1 = TREE_OPERAND (a1, 0);
+      while (CONVERT_EXPR_P (a2))
+	a2 = TREE_OPERAND (a2, 0);
+      if (DECL_P (a1) && c_omp_is_loop_iterator (a1, d) >= 0)
+	{
+	  a2 = TREE_OPERAND (t, 1);
+	  if (TREE_CODE (t) == MINUS_EXPR)
+	    neg_a2 = true;
+	  t = a1;
+	  break;
+	}
+      if (DECL_P (a2) && c_omp_is_loop_iterator (a2, d) >= 0)
+	{
+	  a1 = TREE_OPERAND (t, 0);
+	  if (TREE_CODE (t) == MINUS_EXPR)
+	    neg_a1 = true;
+	  t = a2;
+	  a2 = a1;
+	  break;
+	}
+      if (TREE_CODE (a1) == MULT_EXPR && TREE_CODE (a2) == MULT_EXPR)
+	{
+	  tree o1 = TREE_OPERAND (a1, 0);
+	  tree o2 = TREE_OPERAND (a1, 1);
+	  while (CONVERT_EXPR_P (o1))
+	    o1 = TREE_OPERAND (o1, 0);
+	  while (CONVERT_EXPR_P (o2))
+	    o2 = TREE_OPERAND (o2, 0);
+	  if ((DECL_P (o1) && c_omp_is_loop_iterator (o1, d) >= 0)
+	      || (DECL_P (o2) && c_omp_is_loop_iterator (o2, d) >= 0))
+	    {
+	      a2 = TREE_OPERAND (t, 1);
+	      if (TREE_CODE (t) == MINUS_EXPR)
+		neg_a2 = true;
+	      t = a1;
+	      break;
+	    }
+	}
+      if (TREE_CODE (a2) == MULT_EXPR)
+	{
+	  a1 = TREE_OPERAND (t, 0);
+	  if (TREE_CODE (t) == MINUS_EXPR)
+	    neg_a1 = true;
+	  t = a2;
+	  a2 = a1;
+	  break;
+	}
+      if (TREE_CODE (a1) == MULT_EXPR)
+	{
+	  a2 = TREE_OPERAND (t, 1);
+	  if (TREE_CODE (t) == MINUS_EXPR)
+	    neg_a2 = true;
+	  t = a1;
+	  break;
+	}
+      a2 = integer_zero_node;
+      break;
+    default:
+      break;
+    }
+
+  a1 = integer_one_node;
+  if (TREE_CODE (t) == MULT_EXPR)
+    {
+      tree o1 = TREE_OPERAND (t, 0);
+      tree o2 = TREE_OPERAND (t, 1);
+      while (CONVERT_EXPR_P (o1))
+	o1 = TREE_OPERAND (o1, 0);
+      while (CONVERT_EXPR_P (o2))
+	o2 = TREE_OPERAND (o2, 0);
+      if (DECL_P (o1) && c_omp_is_loop_iterator (o1, d) >= 0)
+	{
+	  a1 = TREE_OPERAND (t, 1);
+	  t = o1;
+	}
+      else if (DECL_P (o2) && c_omp_is_loop_iterator (o2, d) >= 0)
+	{
+	  a1 = TREE_OPERAND (t, 0);
+	  t = o2;
+	}
+    }
+
+  d->kind &= 3;
+  tree ret = NULL_TREE;
+  if (DECL_P (t) && c_omp_is_loop_iterator (t, d) >= 0)
+    {
+      location_t loc = d->expr_loc;
+      if (loc == UNKNOWN_LOCATION)
+	loc = d->stmt_loc;
+      if (!lang_hooks.types_compatible_p (TREE_TYPE (*tp), TREE_TYPE (t)))
+	{
+	  if (d->kind == 0)
+	    error_at (loc, "outer iteration variable %qD used in initializer"
+			   " expression has type other than %qT",
+		      t, TREE_TYPE (*tp));
+	  else
+	    error_at (loc, "outer iteration variable %qD used in condition"
+			   " expression has type other than %qT",
+		      t, TREE_TYPE (*tp));
+	  d->fail = true;
+	}
+      else if (!INTEGRAL_TYPE_P (TREE_TYPE (a1)))
+	{
+	  error_at (loc, "outer iteration variable %qD multiplier expression"
+			 " %qE is not integral", t, a1);
+	  d->fail = true;
+	}
+      else if (!INTEGRAL_TYPE_P (TREE_TYPE (a2)))
+	{
+	  error_at (loc, "outer iteration variable %qD addend expression"
+			 " %qE is not integral", t, a2);
+	  d->fail = true;
+	}
+      else
+	{
+	  walk_tree_1 (&a1, c_omp_check_loop_iv_r, d, NULL, lh);
+	  walk_tree_1 (&a2, c_omp_check_loop_iv_r, d, NULL, lh);
+        }
+      if (!d->fail)
+	{
+	  a1 = fold_convert (TREE_TYPE (*tp), a1);
+	  a2 = fold_convert (TREE_TYPE (*tp), a2);
+	  if (neg_a1)
+	    a1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (a1), a1);
+	  if (neg_a2)
+	    a2 = fold_build1 (NEGATE_EXPR, TREE_TYPE (a2), a2);
+	  ret = t;
+	  *tp = make_tree_vec (3);
+	  TREE_VEC_ELT (*tp, 0) = t;
+	  TREE_VEC_ELT (*tp, 1) = a1;
+	  TREE_VEC_ELT (*tp, 2) = a2;
+	}
+    }
+  else
+    walk_tree_1 (&t, c_omp_check_loop_iv_r, d, NULL, lh);
+
+  d->ppset = ppset;
+  return ret;
+}
+
 /* Diagnose invalid references to loop iterators in lb, b and incr
    expressions.  */
 
@@ -1116,6 +1324,7 @@ c_omp_check_loop_iv (tree stmt, tree declv, walk_tree_lh lh)
 
   data.declv = declv;
   data.fail = false;
+  data.maybe_nonrect = false;
   data.stmt_loc = EXPR_LOCATION (stmt);
   data.lh = lh;
   data.ppset = &pset;
@@ -1129,9 +1338,31 @@ c_omp_check_loop_iv (tree stmt, tree declv, walk_tree_lh lh)
       gcc_assert (TREE_OPERAND (cond, 0) == decl);
       tree incr = TREE_VEC_ELT (OMP_FOR_INCR (stmt), i);
       data.expr_loc = EXPR_LOCATION (TREE_OPERAND (init, 1));
-      data.kind = 0;
+      tree vec_outer1 = NULL_TREE, vec_outer2 = NULL_TREE;
+      int kind = 0;
+      if (i > 0
+	  && (unsigned) c_omp_is_loop_iterator (decl, &data) < (unsigned) i)
+	{
+	  location_t loc = data.expr_loc;
+	  if (loc == UNKNOWN_LOCATION)
+	    loc = data.stmt_loc;
+	  error_at (loc, "the same loop iteration variables %qD used in "
+			 "multiple associated loops", decl);
+	  data.fail = true;
+	}
+      /* Handle non-rectangular loop nests.  */
+      if (TREE_CODE (stmt) != OACC_LOOP
+	  && (TREE_CODE (TREE_OPERAND (init, 1)) == TREE_VEC
+	      || INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (init, 1))))
+	  && i > 0)
+	kind = 4;
+      data.kind = kind;
+      data.idx = i;
       walk_tree_1 (&TREE_OPERAND (init, 1),
-		   c_omp_check_loop_iv_r, &data, &pset, lh);
+		   c_omp_check_loop_iv_r, &data, NULL, lh);
+      if (data.maybe_nonrect)
+	vec_outer1 = c_omp_check_nonrect_loop_iv (&TREE_OPERAND (init, 1),
+						  &data, lh);
       /* Don't warn for C++ random access iterators here, the
 	 expression then involves the subtraction and always refers
 	 to the original value.  The C++ FE needs to warn on those
@@ -1141,10 +1372,24 @@ c_omp_check_loop_iv (tree stmt, tree declv, walk_tree_lh lh)
 	      && decl == TREE_PURPOSE (TREE_VEC_ELT (declv, i))))
 	{
 	  data.expr_loc = EXPR_LOCATION (cond);
-	  data.kind = 1;
+	  data.kind = kind | 1;
 	  walk_tree_1 (&TREE_OPERAND (cond, 1),
-		       c_omp_check_loop_iv_r, &data, &pset, lh);
+		       c_omp_check_loop_iv_r, &data, NULL, lh);
+	  if (data.maybe_nonrect)
+	    vec_outer2 = c_omp_check_nonrect_loop_iv (&TREE_OPERAND (cond, 1),
+						      &data, lh);
+	}
+      if (vec_outer1 && vec_outer2 && vec_outer1 != vec_outer2)
+	{
+	  location_t loc = data.expr_loc;
+	  if (loc == UNKNOWN_LOCATION)
+	    loc = data.stmt_loc;
+	  error_at (loc, "two different outer iteration variables %qD and %qD"
+			 " used in a single loop", vec_outer1, vec_outer2);
+	  data.fail = true;
 	}
+      if (vec_outer1 || vec_outer2)
+	OMP_FOR_NON_RECTANGULAR (stmt) = 1;
       if (TREE_CODE (incr) == MODIFY_EXPR)
 	{
 	  gcc_assert (TREE_OPERAND (incr, 0) == decl);
@@ -1155,13 +1400,13 @@ c_omp_check_loop_iv (tree stmt, tree declv, walk_tree_lh lh)
 	    {
 	      data.expr_loc = EXPR_LOCATION (TREE_OPERAND (incr, 0));
 	      walk_tree_1 (&TREE_OPERAND (incr, 0),
-			   c_omp_check_loop_iv_r, &data, &pset, lh);
+			   c_omp_check_loop_iv_r, &data, NULL, lh);
 	    }
 	  else
 	    {
 	      data.expr_loc = EXPR_LOCATION (TREE_OPERAND (incr, 1));
 	      walk_tree_1 (&TREE_OPERAND (incr, 1),
-			   c_omp_check_loop_iv_r, &data, &pset, lh);
+			   c_omp_check_loop_iv_r, &data, NULL, lh);
 	    }
 	}
     }
@@ -1171,7 +1416,7 @@ c_omp_check_loop_iv (tree stmt, tree declv, walk_tree_lh lh)
 /* Similar, but allows to check the init or cond expressions individually.  */
 
 bool
-c_omp_check_loop_iv_exprs (location_t stmt_loc, tree declv, tree decl,
+c_omp_check_loop_iv_exprs (location_t stmt_loc, tree declv, int i, tree decl,
 			   tree init, tree cond, walk_tree_lh lh)
 {
   hash_set<tree> pset;
@@ -1179,15 +1424,24 @@ c_omp_check_loop_iv_exprs (location_t stmt_loc, tree declv, tree decl,
 
   data.declv = declv;
   data.fail = false;
+  data.maybe_nonrect = false;
   data.stmt_loc = stmt_loc;
   data.lh = lh;
   data.ppset = &pset;
+  data.idx = i;
+  if (i > 0
+      && (unsigned) c_omp_is_loop_iterator (decl, &data) < (unsigned) i)
+    {
+      error_at (stmt_loc, "the same loop iteration variables %qD used in "
+      			  "multiple associated loops", decl);
+      data.fail = true;
+    }
   if (init)
     {
       data.expr_loc = EXPR_LOCATION (init);
       data.kind = 0;
       walk_tree_1 (&init,
-		   c_omp_check_loop_iv_r, &data, &pset, lh);
+		   c_omp_check_loop_iv_r, &data, NULL, lh);
     }
   if (cond)
     {
@@ -1196,10 +1450,10 @@ c_omp_check_loop_iv_exprs (location_t stmt_loc, tree declv, tree decl,
       data.kind = 1;
       if (TREE_OPERAND (cond, 0) == decl)
 	walk_tree_1 (&TREE_OPERAND (cond, 1),
-		     c_omp_check_loop_iv_r, &data, &pset, lh);
+		     c_omp_check_loop_iv_r, &data, NULL, lh);
       else
 	walk_tree_1 (&TREE_OPERAND (cond, 0),
-		     c_omp_check_loop_iv_r, &data, &pset, lh);
+		     c_omp_check_loop_iv_r, &data, NULL, lh);
     }
   return !data.fail;
 }