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.