Re: [PATCH, 10/16] Add pass_oacc_kernels pass group in passes.def

[Richard Biener <rguenther@suse.de>]

On Sat, 21 Nov 2015, Tom de Vries wrote:

> On 20/11/15 11:28, Richard Biener wrote:
> > On Thu, 19 Nov 2015, Tom de Vries wrote:
> > 
> > > >On 17/11/15 15:53, Tom de Vries wrote:
> > > > > > > >And the above LIM example
> > > > > > > >is none for why you need two LIM passes...
> > > > > >
> > > > > >Indeed. I'm planning a separate reply to explain in more detail the
> > > > need
> > > > > >for the two pass_lims.
> > > >
> > > >I.
> > > >
> > > >I managed to get rid of the two pass_lims for the motivating example that
> > > I
> > > >used until now (goacc/kernels-double-reduction.c). I found that by adding
> > > a
> > > >pass_dominator instance after pass_ch, I could get rid of the second
> > > pass_lim
> > > >(and pass_copyprop as well).
> > > >
> > > >But... then I wrote a counter example
> > > (goacc/kernels-double-reduction-n.c),
> > > >and I'm back at two pass_lims (and two pass_dominators).
> > > >Also I've split the pass group into a bit before and after pass_fre.
> > > >
> > > >So, the current pass group looks like:
> > > >...
> > > >NEXT_PASS (pass_build_ealias);
> > > >
> > > >/* Pass group that runs when the function is an offloaded function
> > > >    containing oacc kernels loops.  Part 1.  */
> > > >NEXT_PASS (pass_oacc_kernels);
> > > >PUSH_INSERT_PASSES_WITHIN (pass_oacc_kernels)
> > > >     /* We need pass_ch here, because pass_lim has no effect on
> > > >        exit-first loops (PR65442).  Ideally we want to remove both
> > > >        this pass instantiation, and the reverse transformation
> > > >        transform_to_exit_first_loop_alt, which is done in
> > > >        pass_parallelize_loops_oacc_kernels. */
> > > >     NEXT_PASS (pass_ch);
> > > >POP_INSERT_PASSES ()
> > > >
> > > >NEXT_PASS (pass_fre);
> > > >
> > > >/* Pass group that runs when the function is an offloaded function
> > > >    containing oacc kernels loops.  Part 2.  */
> > > >NEXT_PASS (pass_oacc_kernels2);
> > > >PUSH_INSERT_PASSES_WITHIN (pass_oacc_kernels2)
> > > >     /* We use pass_lim to rewrite in-memory iteration and reduction
> > > >        variable accesses in loops into local variables accesses.  */
> > > >     NEXT_PASS (pass_lim);
> > > >     NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */);
> > > >     NEXT_PASS (pass_lim);
> > > >     NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */);
> > > >     NEXT_PASS (pass_dce);
> > > >     NEXT_PASS (pass_parallelize_loops_oacc_kernels);
> > > >     NEXT_PASS (pass_expand_omp_ssa);
> > > >POP_INSERT_PASSES ()
> > > >NEXT_PASS (pass_merge_phi);
> > > >...
> > > >
> > > >
> > > >II.
> > > >
> > > >The motivating test-case kernels-double-reduction-n.c:
> > > >...
> > > >#include <stdlib.h>
> > > >
> > > >#define N 500
> > > >
> > > >unsigned int a[N][N];
> > > >
> > > >void  __attribute__((noinline,noclone))
> > > >foo (unsigned int n)
> > > >{
> > > >   int i, j;
> > > >   unsigned int sum = 1;
> > > >
> > > >#pragma acc kernels copyin (a[0:n]) copy (sum)
> > > >   {
> > > >     for (i = 0; i < n; ++i)
> > > >       for (j = 0; j < n; ++j)
> > > >         sum += a[i][j];
> > > >   }
> > > >
> > > >   if (sum != 5001)
> > > >     abort ();
> > > >}
> > > >...
> > > >
> > > >
> > > >III.
> > > >
> > > >Before first pass_lim. Note no phis on inner or outer loop header for
> > > >iteration varables or reduction variable:
> > > >...
> > > >   <bb 2>:
> > > >   _5 = *.omp_data_i_4(D).i;
> > > >   *_5 = 0;
> > > >   _44 = *.omp_data_i_4(D).n;
> > > >   _45 = *_44;
> > > >   if (_45 != 0)
> > > >     goto <bb 4>;
> > > >   else
> > > >     goto <bb 3>;
> > > >
> > > >   <bb 4>: outer loop header
> > > >   _12 = *.omp_data_i_4(D).j;
> > > >   *_12 = 0;
> > > >   if (_45 != 0)
> > > >     goto <bb 6>;
> > > >   else
> > > >     goto <bb 5>;
> > > >
> > > >   <bb 6>: inner loop header, latch
> > > >   _19 = *.omp_data_i_4(D).a;
> > > >   _21 = *_5;
> > > >   _23 = *_12;
> > > >   _24 = *_19[_21][_23];
> > > >   _25 = *.omp_data_i_4(D).sum;
> > > >   sum.0_26 = *_25;
> > > >   sum.1_27 = _24 + sum.0_26;
> > > >   *_25 = sum.1_27;
> > > >   _33 = _23 + 1;
> > > >   *_12 = _33;
> > > >   j.2_16 = (unsigned int) _33;
> > > >   if (j.2_16 < _45)
> > > >     goto <bb 6>;
> > > >   else
> > > >     goto <bb 5>;
> > > >
> > > >   <bb 5>: outer loop latch
> > > >   _36 = *_5;
> > > >   _38 = _36 + 1;
> > > >   *_5 = _38;
> > > >   i.3_9 = (unsigned int) _38;
> > > >   if (i.3_9 < _45)
> > > >     goto <bb 4>;
> > > >   else
> > > >     goto <bb 3>;
> > > >
> > > >   <bb 3>:
> > > >   return;
> > > >...
> > > >
> > > >
> > > >IV.
> > > >
> > > >After first pass_lim/pass_dom pair. Note there are phis on the inner loop
> > > >header for the reduction and the iteration variable, but not on the outer
> > > loop
> > > >header:
> > > >...
> > > >   <bb 2>:
> > > >   _5 = *.omp_data_i_4(D).i;
> > > >   *_5 = 0;
> > > >   _44 = *.omp_data_i_4(D).n;
> > > >   _45 = *_44;
> > > >   if (_45 != 0)
> > > >     goto <bb 4>;
> > > >   else
> > > >     goto <bb 3>;
> > > >
> > > >   <bb 4>:
> > > >   _12 = *.omp_data_i_4(D).j;
> > > >   _19 = *.omp_data_i_4(D).a;
> > > >   D__lsm.10_50 = *_12;
> > > >   D__lsm.11_51 = 0;
> > > >   _25 = *.omp_data_i_4(D).sum;
> > > >
> > > >   <bb 5>: outer loop header
> > > >   D__lsm.10_20 = 0;
> > > >   D__lsm.11_22 = 1;
> > > >   _21 = *_5;
> > > >   D__lsm.12_28 = *_25;
> > > >   D__lsm.13_30 = 0;
> > > >   goto <bb 7>;
> > > >
> > > >   <bb 7>: inner loop header, latch
> > > >   # D__lsm.10_47 = PHI <0(5), _33(7)>
> > > >   # D__lsm.12_49 = PHI <D__lsm.12_28(5), sum.1_27(7)>
> > > >   _23 = D__lsm.10_47;
> > > >   _24 = *_19[_21][D__lsm.10_47];
> > > >   sum.0_26 = D__lsm.12_49;
> > > >   sum.1_27 = _24 + D__lsm.12_49;
> > > >   D__lsm.12_31 = sum.1_27;
> > > >   D__lsm.13_32 = 1;
> > > >   _33 = D__lsm.10_47 + 1;
> > > >   D__lsm.10_14 = _33;
> > > >   D__lsm.11_15 = 1;
> > > >   j.2_16 = (unsigned int) _33;
> > > >   if (j.2_16 < _45)
> > > >     goto <bb 7>;
> > > >   else
> > > >     goto <bb 8>;
> > > >
> > > >   <bb 8>: outer loop latch
> > > >   # D__lsm.10_35 = PHI <_33(7)>
> > > >   # D__lsm.11_37 = PHI <1(7)>
> > > >   # D__lsm.12_7 = PHI <sum.1_27(7)>
> > > >   # D__lsm.13_8 = PHI <1(7)>
> > > >   *_25 = sum.1_27;
> > > >   _36 = *_5;
> > > >   _38 = _36 + 1;
> > > >   *_5 = _38;
> > > >   i.3_9 = (unsigned int) _38;
> > > >   if (i.3_9 < _45)
> > > >     goto <bb 5>;
> > > >   else
> > > >     goto <bb 6>;
> > > >
> > > >   <bb 6>:
> > > >   # D__lsm.10_10 = PHI <_33(8)>
> > > >   # D__lsm.11_11 = PHI <1(8)>
> > > >   *_12 = _33;
> > > >   goto <bb 3>;
> > > >
> > > >   <bb 3>:
> > > >   return;
> > > >...
> > > >
> > > >
> > > >V.
> > > >
> > > >After second pass_lim/pass_dom pair. Note there are phis on the inner and
> > > >outer loop header for the reduction and the iteration variables:
> > > >...
> > > >   <bb 2>:
> > > >   _5 = *.omp_data_i_4(D).i;
> > > >   *_5 = 0;
> > > >   _44 = *.omp_data_i_4(D).n;
> > > >   _45 = *_44;
> > > >   if (_45 != 0)
> > > >     goto <bb 4>;
> > > >   else
> > > >     goto <bb 3>;
> > > >
> > > >   <bb 4>:
> > > >   _12 = *.omp_data_i_4(D).j;
> > > >   _19 = *.omp_data_i_4(D).a;
> > > >   D__lsm.10_50 = *_12;
> > > >   D__lsm.11_51 = 0;
> > > >   _25 = *.omp_data_i_4(D).sum;
> > > >   D__lsm.14_40 = 0;
> > > >   D__lsm.15_2 = 0;
> > > >   D__lsm.16_1 = *_25;
> > > >   D__lsm.17_46 = 0;
> > > >
> > > >   <bb 5>: outer loop header
> > > >   # D__lsm.14_13 = PHI <0(4), _38(8)>
> > > >   # D__lsm.16_34 = PHI <D__lsm.16_1(4), sum.1_27(8)>
> > > >   D__lsm.10_20 = 0;
> > > >   D__lsm.11_22 = 1;
> > > >   _21 = D__lsm.14_13;
> > > >   D__lsm.12_28 = D__lsm.16_34;
> > > >   D__lsm.13_30 = 0;
> > > >   goto <bb 7>;
> > > >
> > > >   <bb 7>: inner loop header, latch
> > > >   # D__lsm.10_47 = PHI <0(5), _33(7)>
> > > >   # D__lsm.12_49 = PHI <D__lsm.16_34(5), sum.1_27(7)>
> > > >   _23 = D__lsm.10_47;
> > > >   _24 = *_19[D__lsm.14_13][D__lsm.10_47];
> > > >   sum.0_26 = D__lsm.12_49;
> > > >   sum.1_27 = _24 + D__lsm.12_49;
> > > >   D__lsm.12_31 = sum.1_27;
> > > >   D__lsm.13_32 = 1;
> > > >   _33 = D__lsm.10_47 + 1;
> > > >   D__lsm.10_14 = _33;
> > > >   D__lsm.11_15 = 1;
> > > >   j.2_16 = (unsigned int) _33;
> > > >   if (j.2_16 < _45)
> > > >     goto <bb 7>;
> > > >   else
> > > >     goto <bb 8>;
> > > >
> > > >   <bb 8>: outer loop latch
> > > >   # D__lsm.10_35 = PHI <_33(7)>
> > > >   # D__lsm.11_37 = PHI <1(7)>
> > > >   # D__lsm.12_7 = PHI <sum.1_27(7)>
> > > >   # D__lsm.13_8 = PHI <1(7)>
> > > >   # sum.1_48 = PHI <sum.1_27(7)>
> > > >   # _53 = PHI <_33(7)>
> > > >   D__lsm.16_56 = sum.1_27;
> > > >   D__lsm.17_57 = 1;
> > > >   _36 = D__lsm.14_13;
> > > >   _38 = D__lsm.14_13 + 1;
> > > >   D__lsm.14_58 = _38;
> > > >   D__lsm.15_59 = 1;
> > > >   i.3_9 = (unsigned int) _38;
> > > >   if (i.3_9 < _45)
> > > >     goto <bb 5>;
> > > >   else
> > > >     goto <bb 6>;
> > > >
> > > >   <bb 6>:
> > > >   # D__lsm.10_10 = PHI <_33(8)>
> > > >   # D__lsm.11_11 = PHI <1(8)>
> > > >   # _43 = PHI <_33(8)>
> > > >   # D__lsm.16_62 = PHI <sum.1_27(8)>
> > > >   # D__lsm.17_63 = PHI <1(8)>
> > > >   # D__lsm.14_64 = PHI <_38(8)>
> > > >   # D__lsm.15_65 = PHI <1(8)>
> > > >   *_5 = _38;
> > > >   *_25 = sum.1_27;
> > > >   *_12 = _33;
> > > >   goto <bb 3>;
> > > >
> > > >   <bb 3>:
> > > >   return;
> > > >...
> > Sorry but staring at dumps doesn't make me understand the issue you
> > run into.  Where can I reproduce this if I have time to look at this?
> 
> I've posted the state of the patch series that reproduces this problem at
> https://github.com/vries/gcc/commits/vries/master-port-kernels-test-rb , run
> goacc.exp, testcase kernels-double-reduction-n.c.
> 
> > From the dump below I understand you want no memory references in
> > the outer loop?
> > So the issue seems to be that store motion fails
> > to insert the preheader load / exit store to the outermost loop
> > possible and thus another LIM pass is needed to "store motion" those
> > again?
> 
> Yep.
> 
> >  But a simple testcase
> > 
> > int a;
> > int *p = &a;
> > int foo (int n)
> > {
> >    for (int i = 0; i < n; ++i)
> >      for (int j = 0; j < 100; ++j)
> >        *p += j + i;
> >    return a;
> > }
> > 
> > shows that LIM can do this in one step.
> 
> I've filed a FTR PR68465 - "pass_lim doesn't detect identical loop entry
> conditions" for a test-case where that doesn't happen (when using
> -fno-tree-dominator-opts).
> 
> > Which means it should
> > be investigated why it doesn't do this properly for your testcase
> > (store motion of *_25).
> 
> There seems to be two related problems:
> 1. the store has tree_could_trap_p (ref->mem.ref) true, which should be
>    false. I'll work on a fix for this.
> 2. Give that the store can trap, I  was running into PR68465. I managed
>    to eliminate the 2nd pass_lim by moving the pass_dominator instance
>    before the pass_lim instance.
> 
> Attached patch shows the pass group with only one pass_lim. I hope to be able
> to eliminate the first pass_dominator instance before pass_lim once I fix 1.
> 
> > Simply adding two LIM passes either papers over a wrong-code
> > bug (in LIM or in DOM) or over a missed-optimization in LIM.
> 
> AFAIU now, it's PR68465, a missed optimization in LIM.

Ok, it's not really LIMs job to cleanup loop header copying that way.

DOM performs jump-threading for this but FRE should also be able
to handle this just fine.  Ah, it doesn't because the outer loop
header directly contains the condition

Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c        (revision 230737)
+++ gcc/tree-ssa-sccvn.c        (working copy)
@@ -4357,20 +4402,32 @@ sccvn_dom_walker::before_dom_children (b
 
   /* If we have a single predecessor record the equivalence from a
      possible condition on the predecessor edge.  */
-  if (single_pred_p (bb))
+  edge pred_e = NULL;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      if (e->flags & EDGE_DFS_BACK)
+       continue;
+      if (! pred_e)
+       pred_e = e;
+      else
+       {
+         pred_e = NULL;
+         break;
+       }
+    }
+  if (pred_e)
     {
-      edge e = single_pred_edge (bb);
       /* Check if there are multiple executable successor edges in
         the source block.  Otherwise there is no additional info
         to be recorded.  */
       edge e2;
-      FOR_EACH_EDGE (e2, ei, e->src->succs)
-       if (e2 != e
+      FOR_EACH_EDGE (e2, ei, pred_e->src->succs)
+       if (e2 != pred_e
            && e2->flags & EDGE_EXECUTABLE)
          break;
       if (e2 && (e2->flags & EDGE_EXECUTABLE))
        {
-         gimple *stmt = last_stmt (e->src);
+         gimple *stmt = last_stmt (pred_e->src);
          if (stmt
              && gimple_code (stmt) == GIMPLE_COND)
            {
@@ -4378,11 +4435,11 @@ sccvn_dom_walker::before_dom_children (b
              tree lhs = gimple_cond_lhs (stmt);
              tree rhs = gimple_cond_rhs (stmt);
              record_conds (bb, code, lhs, rhs,
-                           (e->flags & EDGE_TRUE_VALUE) != 0);
+                           (pred_e->flags & EDGE_TRUE_VALUE) != 0);
              code = invert_tree_comparison (code, HONOR_NANS (lhs));
              if (code != ERROR_MARK)
                record_conds (bb, code, lhs, rhs,
-                             (e->flags & EDGE_TRUE_VALUE) == 0);
+                             (pred_e->flags & EDGE_TRUE_VALUE) == 0);
            }
        }
     }

fixes this for me (for a small testcase).  Does it help yours?

Otherwise untested of course (I hope EDGE_DFS_BACK is good enough,
it's supposed to match edges that have the src dominated by the dest).
Testing the above now.

Thanks,
Richard.