[patch,openacc] Propagate independent clause for OpenACC kernels pass

[patch,openacc] Propagate independent clause for OpenACC kernels pass

[Cesar Philippidis]

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

This is another old patch teaches the omp expansion pass how to
propagate the acc loop independent clause to the later stages throughout
compilation. Unfortunately, it didn't include any test cases. I'm not
sure how effective this will be with the existing kernel parloops pass.
But as I noted in my Cauldron talk, we would like to convert acc kernels
regions to acc parallel regions, and this patch could help in that regard.

Chung-Lin, do you have anymore state on this patch?

Anyway, I bootstrapped and regtested it for x86_64 Linux with nvptx
offloading and it didn't introduce any regressions. We do have a couple
of other standalone kernels patches in og8, but those depend on other
patches.

Thanks,
Cesar

[-- Attachment #2: 0001-Propagate-independent-clause-for-OpenACC-kernels-pas.patch --]
[-- Type: text/x-patch, Size: 4410 bytes --]

[OpenACC] Propagate independent clause for OpenACC kernels pass

2018-XX-YY  Chung-Lin Tang <cltang@codesourcery.com>
	    Cesar Philippidis  <cesar@codesourcery.com>

	gcc/
	* cfgloop.h (struct loop): Add 'bool marked_independent' field.
	* omp-expand.c (struct omp_region): Add 'int kind' and
	'bool independent' fields.
	(expand_omp_for): Set 'marked_independent' field for loop
	corresponding to region.
	(find_omp_for_region_data): New function.
	(build_omp_regions_1): Set kind field.  Call
	find_omp_for_region_data for GIMPLE_OMP_FOR statements.

(cherry picked from gomp-4_0-branch r225759)
---
 gcc/cfgloop.h    |  4 ++++
 gcc/omp-expand.c | 46 ++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 48 insertions(+), 2 deletions(-)

diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 80a31c416ca..7928681b514 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -221,6 +221,10 @@ struct GTY ((chain_next ("%h.next"))) loop {
   /* True if the loop is part of an oacc kernels region.  */
   unsigned in_oacc_kernels_region : 1;
 
+  /* True if loop is tagged as having independent iterations by user,
+     e.g. the OpenACC independent clause.  */
+  bool marked_independent;
+
   /* The number of times to unroll the loop.  0 means no information given,
      just do what we always do.  A value of 1 means do not unroll the loop.
      A value of USHRT_MAX means unroll with no specific unrolling factor.
diff --git a/gcc/omp-expand.c b/gcc/omp-expand.c
index 9b03f62e065..427f329d35f 100644
--- a/gcc/omp-expand.c
+++ b/gcc/omp-expand.c
@@ -107,6 +107,12 @@ struct omp_region
 
   /* True if this is nested inside an OpenACC kernels construct.  */
   bool inside_kernels_p;
+
+  /* Records a generic kind field.  */
+  int kind;
+
+  /* For an OpenACC loop directive, true if has the 'independent' clause.  */
+  bool independent;
 };
 
 static struct omp_region *root_omp_region;
@@ -5705,8 +5711,15 @@ expand_omp_for (struct omp_region *region, gimple *inner_stmt)
     loops_state_set (LOOPS_NEED_FIXUP);
 
   if (region->inside_kernels_p)
-    expand_omp_for_generic (region, &fd, BUILT_IN_NONE, BUILT_IN_NONE,
-			    inner_stmt);
+    {
+      expand_omp_for_generic (region, &fd, BUILT_IN_NONE, BUILT_IN_NONE,
+			      inner_stmt);
+      if (region->independent && region->cont->loop_father)
+	{
+	  struct loop *loop = region->cont->loop_father;
+	  loop->marked_independent = true;
+	}
+    }
   else if (gimple_omp_for_kind (fd.for_stmt) & GF_OMP_FOR_SIMD)
     expand_omp_simd (region, &fd);
   else if (gimple_omp_for_kind (fd.for_stmt) == GF_OMP_FOR_KIND_OACC_LOOP)
@@ -7887,6 +7900,31 @@ expand_omp (struct omp_region *region)
     }
 }
 
+/* Fill in additional data for a region REGION associated with an
+   OMP_FOR STMT.  */
+
+static void
+find_omp_for_region_data (struct omp_region *region, gomp_for *stmt)
+{
+  region->kind = gimple_omp_for_kind (stmt);
+
+  if (region->kind == GF_OMP_FOR_KIND_OACC_LOOP)
+    {
+      struct omp_region *target_region = region->outer;
+      while (target_region
+	     && target_region->type != GIMPLE_OMP_TARGET)
+	target_region = target_region->outer;
+      if (!target_region)
+	return;
+
+      tree clauses = gimple_omp_for_clauses (stmt);
+
+      if (target_region->kind == GF_OMP_TARGET_KIND_OACC_KERNELS
+	  && omp_find_clause (clauses, OMP_CLAUSE_INDEPENDENT))
+	region->independent = true;
+    }
+}
+
 /* Helper for build_omp_regions.  Scan the dominator tree starting at
    block BB.  PARENT is the region that contains BB.  If SINGLE_TREE is
    true, the function ends once a single tree is built (otherwise, whole
@@ -7953,6 +7991,8 @@ build_omp_regions_1 (basic_block bb, struct omp_region *parent,
 		case GF_OMP_TARGET_KIND_OACC_KERNELS:
 		case GF_OMP_TARGET_KIND_OACC_DATA:
 		case GF_OMP_TARGET_KIND_OACC_HOST_DATA:
+		  if (is_gimple_omp_oacc (stmt))
+		    region->kind = gimple_omp_target_kind (stmt);
 		  break;
 		case GF_OMP_TARGET_KIND_UPDATE:
 		case GF_OMP_TARGET_KIND_ENTER_DATA:
@@ -7974,6 +8014,8 @@ build_omp_regions_1 (basic_block bb, struct omp_region *parent,
 	    /* #pragma omp ordered depend is also just a stand-alone
 	       directive.  */
 	    region = NULL;
+	  else if (code == GIMPLE_OMP_FOR)
+	    find_omp_for_region_data (region, as_a <gomp_for *> (stmt));
 	  /* ..., this directive becomes the parent for a new region.  */
 	  if (region)
 	    parent = region;
-- 
2.17.1

Re: [patch,openacc] Propagate independent clause for OpenACC kernels pass

[Julian Brown]

On Thu, 20 Sep 2018 11:06:40 -0700
Cesar Philippidis <cesar@codesourcery.com> wrote:

> This is another old patch teaches the omp expansion pass how to
> propagate the acc loop independent clause to the later stages
> throughout compilation. Unfortunately, it didn't include any test
> cases. I'm not sure how effective this will be with the existing
> kernel parloops pass. But as I noted in my Cauldron talk, we would
> like to convert acc kernels regions to acc parallel regions, and this
> patch could help in that regard.
> 
> Chung-Lin, do you have anymore state on this patch?
> 
> Anyway, I bootstrapped and regtested it for x86_64 Linux with nvptx
> offloading and it didn't introduce any regressions. We do have a
> couple of other standalone kernels patches in og8, but those depend
> on other patches.

It's not surprising that there are no new tests and no regressions: the
new "marked_independent" field is not used anywhere, either within this
patch, or on the gomp4 branch where it originated, nor currently on the
og8 branch! It looks like the planned use by the parloops pass (etc.)
has not materialised so far.

Jakub asked in the following email at the time of the patch submission
for the gomp4 branch what the difference was between the new
marked_independent flag and safelen == INT_MAX:

  https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01100.html

If I understand the followup correctly,

  https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01117.html

a setting of safelen > 1 means that up to that number of loop
iterations can run together in lockstep (as if each insn in the loop
was blindly rewritten to a safelen-width SIMD equivalent) -- but
anything that happens in iteration N + 1 cannot happen before something
that happens in iteration N. Chung-Lin pointed out that OpenACC's
semantics are even less strict (allowing iterations to proceed fully
independently in an arbitrary order), so the marked_independent flag
does carry non-redundant information -- even with safelen set to
INT_MAX.

Actually I think that given the above, setting safelen to a value
greater than 32 (the warp size) may not be safe for NVPTX on OpenACC,
depending on the vagaries of warp scheduling. But that's not the
subject of this patch.

Anyway: given that the information recorded by this patch is not used
at present, and further work on the kernels pass may head in a
different direction, I'm not sure that it makes sense to commit it
at this point.

Also, it occurs to me that if the independent flag is set on loops
within kernels regions with an explicit "independent" clause, it should
also be set by default on loops in parallel regions without clauses
that disable the independent-iteration semantics.

Julian

Re: [patch,openacc] Propagate independent clause for OpenACC kernels pass

[Jakub Jelinek]

On Mon, Dec 03, 2018 at 11:40:39PM +0000, Julian Brown wrote:
> Jakub asked in the following email at the time of the patch submission
> for the gomp4 branch what the difference was between the new
> marked_independent flag and safelen == INT_MAX:
> 
>   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01100.html
> 
> If I understand the followup correctly,
> 
>   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01117.html
> 
> a setting of safelen > 1 means that up to that number of loop
> iterations can run together in lockstep (as if each insn in the loop
> was blindly rewritten to a safelen-width SIMD equivalent) -- but
> anything that happens in iteration N + 1 cannot happen before something
> that happens in iteration N. Chung-Lin pointed out that OpenACC's
> semantics are even less strict (allowing iterations to proceed fully
> independently in an arbitrary order), so the marked_independent flag
> does carry non-redundant information -- even with safelen set to
> INT_MAX.

OpenMP 5 (not implemented in GCC 9 though) has order(concurrent) clause
for this (no cross-iteration dependencies at all, iterations can be run in
any order, in parallel etc.).

I believe it matches the can_be_parallel flag we now have, but I remember
there were some issues with that flag for use in DO CONCURRENT.

Or do we want to have some other flag for really independent iterations?
What passes could use that?  Would the vectorizer appreciate the stronger
assertion in some cases?

	Jakub

Re: [patch,openacc] Propagate independent clause for OpenACC kernels pass

[Richard Biener]

On Tue, 4 Dec 2018, Jakub Jelinek wrote:

> On Mon, Dec 03, 2018 at 11:40:39PM +0000, Julian Brown wrote:
> > Jakub asked in the following email at the time of the patch submission
> > for the gomp4 branch what the difference was between the new
> > marked_independent flag and safelen == INT_MAX:
> > 
> >   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01100.html
> > 
> > If I understand the followup correctly,
> > 
> >   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01117.html
> > 
> > a setting of safelen > 1 means that up to that number of loop
> > iterations can run together in lockstep (as if each insn in the loop
> > was blindly rewritten to a safelen-width SIMD equivalent) -- but
> > anything that happens in iteration N + 1 cannot happen before something
> > that happens in iteration N. Chung-Lin pointed out that OpenACC's
> > semantics are even less strict (allowing iterations to proceed fully
> > independently in an arbitrary order), so the marked_independent flag
> > does carry non-redundant information -- even with safelen set to
> > INT_MAX.
> 
> OpenMP 5 (not implemented in GCC 9 though) has order(concurrent) clause
> for this (no cross-iteration dependencies at all, iterations can be run in
> any order, in parallel etc.).
> 
> I believe it matches the can_be_parallel flag we now have, but I remember
> there were some issues with that flag for use in DO CONCURRENT.
> 
> Or do we want to have some other flag for really independent iterations?
> What passes could use that?  Would the vectorizer appreciate the stronger
> assertion in some cases?

The vectorizer doesn't really care.  It would be autopar that should.
The issue with using can_be_parallel for DO CONCURRENT was that the
middle-end introduces non-trivial sharing between iterations, introducing
dependences that then make the loop no longer can_be_parallel.  I
believe similar things could happen with ->safelen (consider loop
reversal and existing forward dependences).  I guess we're simply
lucky in that area ;)

Richard.

Re: [patch,openacc] Propagate independent clause for OpenACC kernels pass

[Julian Brown]

On Tue, 4 Dec 2018 14:55:03 +0100
Richard Biener <rguenther@suse.de> wrote:

> On Tue, 4 Dec 2018, Jakub Jelinek wrote:
> 
> > On Mon, Dec 03, 2018 at 11:40:39PM +0000, Julian Brown wrote:  
> > > Jakub asked in the following email at the time of the patch
> > > submission for the gomp4 branch what the difference was between
> > > the new marked_independent flag and safelen == INT_MAX:
> > > 
> > >   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01100.html
> > > 
> > > If I understand the followup correctly,
> > > 
> > >   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01117.html
> > > 
> > > a setting of safelen > 1 means that up to that number of loop
> > > iterations can run together in lockstep (as if each insn in the
> > > loop was blindly rewritten to a safelen-width SIMD equivalent) --
> > > but anything that happens in iteration N + 1 cannot happen before
> > > something that happens in iteration N. Chung-Lin pointed out that
> > > OpenACC's semantics are even less strict (allowing iterations to
> > > proceed fully independently in an arbitrary order), so the
> > > marked_independent flag does carry non-redundant information --
> > > even with safelen set to INT_MAX.  
> > 
> > OpenMP 5 (not implemented in GCC 9 though) has order(concurrent)
> > clause for this (no cross-iteration dependencies at all, iterations
> > can be run in any order, in parallel etc.).
> > 
> > I believe it matches the can_be_parallel flag we now have, but I
> > remember there were some issues with that flag for use in DO
> > CONCURRENT.
> > 
> > Or do we want to have some other flag for really independent
> > iterations? What passes could use that?  Would the vectorizer
> > appreciate the stronger assertion in some cases?  
> 
> The vectorizer doesn't really care.  It would be autopar that should.
> The issue with using can_be_parallel for DO CONCURRENT was that the
> middle-end introduces non-trivial sharing between iterations,
> introducing dependences that then make the loop no longer
> can_be_parallel.  I believe similar things could happen with
> ->safelen (consider loop reversal and existing forward dependences).
> I guess we're simply lucky in that area ;)

I wondered if I should try modifying the patch to set the
can_be_parallel flag for kernels loops with an "independent" clause
instead (and try to address Jakub's other comments). Do I understand
right that the issue with the can_be_parallel flag is that it does not
necessarily guarantee safety of optimisations for loops which are
supposed to have fully-independent iterations, rather than that it has
different semantics from the proposed marked_independent flag?

However, it turns out that this patch has a dependency on this one:

  https://gcc.gnu.org/ml/gcc-patches/2018-09/msg01179.html

and, according to Cesar, that in turn has a dependency on another patch:

  https://gcc.gnu.org/ml/gcc-patches/2018-09/msg01189.html

so, it might take me a little time to untangle all that. Does the rough
idea sound plausible, though? Or is modifying this patch to use
can_be_parallel likely to just cause problems at present?

Thanks,

Julian

Re: [patch,openacc] Propagate independent clause for OpenACC kernels pass

[Richard Biener]

On Wed, 5 Dec 2018, Julian Brown wrote:

> On Tue, 4 Dec 2018 14:55:03 +0100
> Richard Biener <rguenther@suse.de> wrote:
> 
> > On Tue, 4 Dec 2018, Jakub Jelinek wrote:
> > 
> > > On Mon, Dec 03, 2018 at 11:40:39PM +0000, Julian Brown wrote:  
> > > > Jakub asked in the following email at the time of the patch
> > > > submission for the gomp4 branch what the difference was between
> > > > the new marked_independent flag and safelen == INT_MAX:
> > > > 
> > > >   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01100.html
> > > > 
> > > > If I understand the followup correctly,
> > > > 
> > > >   https://gcc.gnu.org/ml/gcc-patches/2015-07/msg01117.html
> > > > 
> > > > a setting of safelen > 1 means that up to that number of loop
> > > > iterations can run together in lockstep (as if each insn in the
> > > > loop was blindly rewritten to a safelen-width SIMD equivalent) --
> > > > but anything that happens in iteration N + 1 cannot happen before
> > > > something that happens in iteration N. Chung-Lin pointed out that
> > > > OpenACC's semantics are even less strict (allowing iterations to
> > > > proceed fully independently in an arbitrary order), so the
> > > > marked_independent flag does carry non-redundant information --
> > > > even with safelen set to INT_MAX.  
> > > 
> > > OpenMP 5 (not implemented in GCC 9 though) has order(concurrent)
> > > clause for this (no cross-iteration dependencies at all, iterations
> > > can be run in any order, in parallel etc.).
> > > 
> > > I believe it matches the can_be_parallel flag we now have, but I
> > > remember there were some issues with that flag for use in DO
> > > CONCURRENT.
> > > 
> > > Or do we want to have some other flag for really independent
> > > iterations? What passes could use that?  Would the vectorizer
> > > appreciate the stronger assertion in some cases?  
> > 
> > The vectorizer doesn't really care.  It would be autopar that should.
> > The issue with using can_be_parallel for DO CONCURRENT was that the
> > middle-end introduces non-trivial sharing between iterations,
> > introducing dependences that then make the loop no longer
> > can_be_parallel.  I believe similar things could happen with
> > ->safelen (consider loop reversal and existing forward dependences).
> > I guess we're simply lucky in that area ;)
> 
> I wondered if I should try modifying the patch to set the
> can_be_parallel flag for kernels loops with an "independent" clause
> instead (and try to address Jakub's other comments). Do I understand
> right that the issue with the can_be_parallel flag is that it does not
> necessarily guarantee safety of optimisations for loops which are
> supposed to have fully-independent iterations, rather than that it has
> different semantics from the proposed marked_independent flag?
> 
> However, it turns out that this patch has a dependency on this one:
> 
>   https://gcc.gnu.org/ml/gcc-patches/2018-09/msg01179.html
> 
> and, according to Cesar, that in turn has a dependency on another patch:
> 
>   https://gcc.gnu.org/ml/gcc-patches/2018-09/msg01189.html
> 
> so, it might take me a little time to untangle all that. Does the rough
> idea sound plausible, though? Or is modifying this patch to use
> can_be_parallel likely to just cause problems at present?

For Fortran DO CONCURRENT it caused problems.  can_be_parallel causes
auto-parallelization to omit all dependence checking which works
fine for the small time this flag is usually set by the graphite
dependence analysis (which marks loops that way) and autopar itself
(which is also the only consumer of the flag right now).  But if
the frontend already sets the flag there's too much chance for the
middle-end to mess up dependences and thus the autopar code would
need to double-check (also making the flag somewhat useless).

Richard.

> Thanks,
> 
> Julian
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [patch,openacc] Propagate independent clause for OpenACC kernels pass

[Jakub Jelinek]

On Thu, Sep 20, 2018 at 11:06:40AM -0700, Cesar Philippidis wrote:
> 2018-XX-YY  Chung-Lin Tang <cltang@codesourcery.com>
> 	    Cesar Philippidis  <cesar@codesourcery.com>
> 
> 	gcc/
> 	* cfgloop.h (struct loop): Add 'bool marked_independent' field.
> 	* omp-expand.c (struct omp_region): Add 'int kind' and
> 	'bool independent' fields.
> 	(expand_omp_for): Set 'marked_independent' field for loop
> 	corresponding to region.
> 	(find_omp_for_region_data): New function.
> 	(build_omp_regions_1): Set kind field.  Call
> 	find_omp_for_region_data for GIMPLE_OMP_FOR statements.

In addition to what I've just mentioned in another mail:

> --- a/gcc/omp-expand.c
> +++ b/gcc/omp-expand.c
> @@ -107,6 +107,12 @@ struct omp_region
>  
>    /* True if this is nested inside an OpenACC kernels construct.  */
>    bool inside_kernels_p;
> +
> +  /* Records a generic kind field.  */
> +  int kind;
> +
> +  /* For an OpenACC loop directive, true if has the 'independent' clause.  */
> +  bool independent;
>  };

I'm not sure why you need kind cached, you can get from the region at the
stmt and from there at the kind easily.  And even if it would be a good idea
to cache it, you don't want to mix bool and non-bool members in the
structure to avoid padding gaps.

	Jakub