[gomp4.1] fold ordered depend(sink) clauses

On 07/31/2015 09:38 AM, Jakub Jelinek wrote:
> On Thu, Jul 30, 2015 at 07:27:51PM -0700, Aldy Hernandez wrote:
>> +static gimple
>> +gimplify_omp_ordered (tree expr, gimple_seq body)
>> +{
>> +  tree c, decls;
>> +  int failures = 0;
>> +  unsigned int i;
>> +
>> +  if (gimplify_omp_ctxp)
>> +    for (c = OMP_ORDERED_CLAUSES (expr); c; c = OMP_CLAUSE_CHAIN (c))
>> +      if (OMP_CLAUSE_CODE (c) == OMP_CLAUSE_DEPEND
>> +	  && OMP_CLAUSE_DEPEND_KIND (c) == OMP_CLAUSE_DEPEND_SINK)
>> +	{
>> +	  bool fail = false;
>> +	  for (decls = OMP_CLAUSE_DECL (c), i = 0;
>> +	       decls && TREE_CODE (decls) == TREE_LIST;
>> +	       decls = TREE_CHAIN (decls), ++i)
>> +	    if (i < gimplify_omp_ctxp->loop_iter_var.length ()
>> +		&& TREE_VALUE (decls) != gimplify_omp_ctxp->loop_iter_var[i])
>> +	      {
>> +		error_at (OMP_CLAUSE_LOCATION (c),
>> +			  "variable %qE is not an iteration "
>> +			  "of outermost loop %d, expected %qE",
>> +			  TREE_VALUE (decls), i + 1,
>> +			  gimplify_omp_ctxp->loop_iter_var[i]);
>> +		fail = true;
>> +		failures++;
>> +	      }
>> +	  /* Avoid being too redundant.  */
>> +	  if (!fail && i != gimplify_omp_ctxp->loop_iter_var.length ())
>> +	    {
>> +	      error_at (OMP_CLAUSE_LOCATION (c),
>> +			"number of variables in depend(sink) "
>> +			"clause does not match number of "
>> +			"iteration variables");
>> +	      failures++;
>> +	    }
>
> failures seems to be a write only variable.
> Perhaps if fail is true (set it to true after this error too),
> don't create the ordered at all?  Or drop the bogus clauses.

Oops.  Left over from when we were doing everything in the gimplifier.

I think we can just emit a NOP when error here.  There's no sense in 
removing individual clauses and all that since lower_omp_1 is going to 
ignore sources with error anyhow:

   /* If we have issued syntax errors, avoid doing any heavy lifting.
      Just replace the OMP directives with a NOP to avoid
      confusing RTL expansion.  */
   if (seen_error () && is_gimple_omp (stmt))
     {
       gsi_replace (gsi_p, gimple_build_nop (), true);
       return;
     }

>
>> +
>> +  /* ?? This is stupid.  We need to call extract_omp_for_data just
>> +     to get the number of ordered loops... */
>> +  extract_omp_for_data (as_a <gomp_for *> (ctx->outer->stmt), &fd, NULL);
>> +  if (!fd.ordered)
>> +    return;
>> +  struct omp_for_data_loop *loops
>> +    = (struct omp_for_data_loop *)
>> +    alloca (fd.ordered * sizeof (struct omp_for_data_loop));
>
> You can do just what expand_omp_for does:
>    struct omp_for_data fd;
>    struct omp_for_data_loop *loops;
>
>    loops
>      = (struct omp_for_data_loop *)
>        alloca (gimple_omp_for_collapse (ctx->outer->stmt)
>                * sizeof (struct omp_for_data_loop));
>    extract_omp_for_data (as_a <gomp_for *> (ctx->outer_stmt), &fd, loops);

Ah!  The collapse of the the outer statement!  Done.

>
>> +     For example:
>> +
>> +	     for (i=0; i < N; ++i)
>> +		depend(sink:i-8,j-1)
>> +		depend(sink:i,j-2)	// Completely ignored because i+0.
>> +		depend(sink:i-4,j+3)
>> +		depend(sink:i-6,j+2)
>
> Even when writing comments, it is better to make it valid:
> 	#pragma omp for ordered(2)
> 	for (i=0; i < N; ++i)
> 	  for (j=0; j < M; ++j)
> 	    {
> 	      #pragma omp ordered \
> 		depend(sink:i-8,j-1) \
> 		depend(sink:i,j-2) \	// Completely ignored because i+0.
> 		depend(sink:i-4,j+3) \
> 		depend(sink:i-6,j+2)
> 	      #pragma omp ordered depend(source)
> 	    }

You have _got_ to be kidding?  Really?  Oh well...done.

>
>> +
>> +     Folded clause is:
>> +
>> +        depend(sink:-gcd(8,4,6),min(-1,3,2))
>
> Spaces here instead of desirable tab.

Done.

>
>> +	  -or-
>> +	depend(sink:-2,-1)
>> +  */
>> +
>> +  /* FIXME: Computing GCD's where the first element is zero is
>> +     non-trivial in the presence of collapsed loops.  Do this later.  */
>> +  if (fd.collapse > 1)
>> +    return;
>
> Better ad an gcc_assert for now.

Done.

>
>> +	  enum {
>> +	    DIR_UNKNOWN,
>> +	    DIR_FORWARD,
>> +	    DIR_BACKWARD
>> +	  } loop_dir;
>> +	  switch (fd.loops[i].cond_code)
>> +	    {
>> +	    case LT_EXPR:
>> +	    case LE_EXPR:
>> +	      loop_dir = DIR_FORWARD;
>> +	      break;
>> +	    case GT_EXPR:
>> +	    case GE_EXPR:
>> +	      loop_dir = DIR_BACKWARD;
>> +	      break;
>> +	    default:
>> +	      loop_dir = DIR_UNKNOWN;
>> +	      gcc_unreachable ();
>> +	    }
>
> I think there is no point in doing this, extract_omp_for_data
> canonicalizes cond_code already, so it is always
> LT_EXPR or GT_EXPR.  So just gcc_assert it is these two and

Well, [LG]E_EXPR can sneak through for i >= fd->collapse in 
extract_omp_for_data:

	case LE_EXPR:
	  if (i >= fd->collapse)
	    break;
	  if (POINTER_TYPE_P (TREE_TYPE (loop->n2)))
	    loop->n2 = fold_build_pointer_plus_hwi_loc (loc, loop->n2, 1);
	  else
	    loop->n2 = fold_build2_loc (loc,
				    PLUS_EXPR, TREE_TYPE (loop->n2), loop->n2,
				    build_int_cst (TREE_TYPE (loop->n2), 1));
	  loop->cond_code = LT_EXPR;
	  break;

How about we assert that it's LE/LT/GT/GE and set a `bool forward' as 
suggested?

> compare it directly, or add bool forward = fd.loops[i].cond_code == LT_EXPR;
> ?
>> +
>> +	  /* While the committee makes up its mind, bail if we have any
>> +	     non-constant steps.  */
>> +	  if (TREE_CODE (fd.loops[i].step) != INTEGER_CST)
>> +	    goto gimplify_omp_ordered_ret;
>
> Misnamed label.  lower instead?

Fixed.

>
>> +	  wide_int offset = TREE_PURPOSE (decls);
>> +	  if (!iter_vars[i])
>> +	    iter_vars[i] = TREE_VALUE (decls);
>> +
>> +	  /* Ignore invalid offsets that are not multiples of the step.  */
>> +	  if (!wi::multiple_of_p
>> +	      (wi::abs (offset), wi::abs ((wide_int) fd.loops[i].step),
>> +	       UNSIGNED))
>
> What does wi::abs do with very large unsigned integers?
>    #pragma omp ordered(2)
>    for (unsigned int i = 64; i > 32; i += -1)
>      for (unsigned int j = 0; j < 32; j++)
> ?
> step of i is 0xffffffff and cond_code is GT_EXPR.  I suppose for unsigned
> steps you don't want to use wi::abs, but just negate the step if
> iterating downward?

Seems to work just fine for:

    #pragma omp parallel for ordered(2)
     for (unsigned int i = N; i > 32; i += -1)
           for (unsigned int j = 0; j < 32; j++)
     {
#pragma omp ordered depend(sink:i+1,j-2) depend(sink:i+2,j-3)
...
...

(gdb) call debug_generic_stmt(fd.loops[i].step)
4294967295

(gdb) p/x 4294967295
$17 = 0xffffffff

The conversion from tree -> wide-int correctly interprets this:

(gdb) print x
$18 = (const generic_wide_int<wide_int_storage> &) @0x7fffffffd5d0: 
{<wide_int_storage> = {val = {-1, 29799175824, 140737488344576}, len = 1,
     precision = 32}, static is_sign_extended = <optimized out>}
(gdb) call x.dump()
[0xffffffffffffffff], precision = 32

..and then negates it correctly.  For the i+1,j-2, we end up with 
(correctly):

(gdb) call x.dump()
[0x2], precision = 32
(gdb) call y.dump()
[0x1], precision = 32

Then the folded dependence is depend(sink:i+1,j+4294967293), which is -3 
and what I would expect.  Unless I'm missing something...

How does the attached look?

Aldy
commit 92e33750f31c7954b8a92763d20630f4e1af9b6b
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Wed Jul 29 13:39:06 2015 -0700

    	* wide-int.h (wi::gcd): New.
    	* gimplify.c (struct gimplify_omp_ctx): Rename iter_vars to
    	loop_iter_var.
    	(delete_omp_context): Same.
    	(gimplify_expr): Move code handling OMP_ORDERED into...
    	(gimplify_omp_ordered): ...here.  New.
    	* omp-low.c (lower_omp_ordered_clauses): New.
    	(lower_omp_ordered): Call lower_omp_ordered_clauses.
    testsuite/
    	* gcc.dg/gomp/sink-fold-1.c: New.
    	* gcc.dg/gomp/sink-fold-2.c: New.
    	* gcc.dg/gomp/sink-fold-3.c: New.
    	* c-c++-common/gomp/sink-4.c: Look in omplower dump file instead.
    	* g++.dg/gomp/sink-3.C: Have sink offset be in the opposite
    	direction.  Make variables more readable.

[gomp4.1] fold ordered depend(sink) clauses

Commit Message

Comments

Patch