On Wed, May 15, 2024 at 5:24 PM Richard Biener <richard.guent...@gmail.com> wrote: > > On Wed, May 15, 2024 at 4:15 AM Hongtao Liu <crazy...@gmail.com> wrote: > > > > On Mon, May 13, 2024 at 3:40 PM Richard Biener > > <richard.guent...@gmail.com> wrote: > > > > > > On Mon, May 13, 2024 at 4:29 AM liuhongt <hongtao....@intel.com> wrote: > > > > > > > > As testcase in the PR, O3 cunrolli may prevent vectorization for the > > > > innermost loop and increase register pressure. > > > > The patch removes the 1/3 reduction of unr_insn for innermost loop for > > > > UL_ALL. > > > > ul != UR_ALL is needed since some small loop complete unrolling at O2 > > > > relies > > > > the reduction. > > > > > > > > Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}. > > > > No big impact for SPEC2017. > > > > Ok for trunk? > > > > > > This removes the 1/3 reduction when unrolling a loop nest (the case I was > > > concerned about). Unrolling of a nest is by iterating in > > > tree_unroll_loops_completely > > > so the to be unrolled loop appears innermost. So I think you need a new > > > parameter on tree_unroll_loops_completely_1 indicating whether we're in > > > the > > > first iteration (or whether to assume inner most loops will "simplify"). > > yes, it would be better. > > > > > > Few comments below > > > > > > > gcc/ChangeLog: > > > > > > > > PR tree-optimization/112325 > > > > * tree-ssa-loop-ivcanon.cc (estimated_unrolled_size): Add 2 > > > > new parameters: loop and ul, and remove unr_insns reduction > > > > for innermost loop. > > > > (try_unroll_loop_completely): Pass loop and ul to > > > > estimated_unrolled_size. > > > > > > > > gcc/testsuite/ChangeLog: > > > > > > > > * gcc.dg/tree-ssa/pr112325.c: New test. > > > > * gcc.dg/vect/pr69783.c: Add extra option --param > > > > max-completely-peeled-insns=300. > > > > --- > > > > gcc/testsuite/gcc.dg/tree-ssa/pr112325.c | 57 ++++++++++++++++++++++++ > > > > gcc/testsuite/gcc.dg/vect/pr69783.c | 2 +- > > > > gcc/tree-ssa-loop-ivcanon.cc | 16 +++++-- > > > > 3 files changed, 71 insertions(+), 4 deletions(-) > > > > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr112325.c > > > > > > > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr112325.c > > > > b/gcc/testsuite/gcc.dg/tree-ssa/pr112325.c > > > > new file mode 100644 > > > > index 00000000000..14208b3e7f8 > > > > --- /dev/null > > > > +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr112325.c > > > > @@ -0,0 +1,57 @@ > > > > +/* { dg-do compile } */ > > > > +/* { dg-options "-O2 -fdump-tree-cunrolli-details" } */ > > > > + > > > > +typedef unsigned short ggml_fp16_t; > > > > +static float table_f32_f16[1 << 16]; > > > > + > > > > +inline static float ggml_lookup_fp16_to_fp32(ggml_fp16_t f) { > > > > + unsigned short s; > > > > + __builtin_memcpy(&s, &f, sizeof(unsigned short)); > > > > + return table_f32_f16[s]; > > > > +} > > > > + > > > > +typedef struct { > > > > + ggml_fp16_t d; > > > > + ggml_fp16_t m; > > > > + unsigned char qh[4]; > > > > + unsigned char qs[32 / 2]; > > > > +} block_q5_1; > > > > + > > > > +typedef struct { > > > > + float d; > > > > + float s; > > > > + char qs[32]; > > > > +} block_q8_1; > > > > + > > > > +void ggml_vec_dot_q5_1_q8_1(const int n, float * restrict s, const > > > > void * restrict vx, const void * restrict vy) { > > > > + const int qk = 32; > > > > + const int nb = n / qk; > > > > + > > > > + const block_q5_1 * restrict x = vx; > > > > + const block_q8_1 * restrict y = vy; > > > > + > > > > + float sumf = 0.0; > > > > + > > > > + for (int i = 0; i < nb; i++) { > > > > + unsigned qh; > > > > + __builtin_memcpy(&qh, x[i].qh, sizeof(qh)); > > > > + > > > > + int sumi = 0; > > > > + > > > > + for (int j = 0; j < qk/2; ++j) { > > > > + const unsigned char xh_0 = ((qh >> (j + 0)) << 4) & 0x10; > > > > + const unsigned char xh_1 = ((qh >> (j + 12)) ) & 0x10; > > > > + > > > > + const int x0 = (x[i].qs[j] & 0xF) | xh_0; > > > > + const int x1 = (x[i].qs[j] >> 4) | xh_1; > > > > + > > > > + sumi += (x0 * y[i].qs[j]) + (x1 * y[i].qs[j + qk/2]); > > > > + } > > > > + > > > > + sumf += (ggml_lookup_fp16_to_fp32(x[i].d)*y[i].d)*sumi + > > > > ggml_lookup_fp16_to_fp32(x[i].m)*y[i].s; > > > > + } > > > > + > > > > + *s = sumf; > > > > +} > > > > + > > > > +/* { dg-final { scan-tree-dump {(?n)Not unrolling loop [1-9] \(--param > > > > max-completely-peel-times limit reached} "cunrolli"} } */ > > > > diff --git a/gcc/testsuite/gcc.dg/vect/pr69783.c > > > > b/gcc/testsuite/gcc.dg/vect/pr69783.c > > > > index 5df95d0ce4e..a1f75514d72 100644 > > > > --- a/gcc/testsuite/gcc.dg/vect/pr69783.c > > > > +++ b/gcc/testsuite/gcc.dg/vect/pr69783.c > > > > @@ -1,6 +1,6 @@ > > > > /* { dg-do compile } */ > > > > /* { dg-require-effective-target vect_float } */ > > > > -/* { dg-additional-options "-Ofast -funroll-loops" } */ > > > > +/* { dg-additional-options "-Ofast -funroll-loops --param > > > > max-completely-peeled-insns=300" } */ > > > > > > If we rely on unrolling of a loop can you put #pragma unroll [N] > > > before the respective loop > > > instead? > > > > > > > #define NXX 516 > > > > #define NYY 516 > > > > diff --git a/gcc/tree-ssa-loop-ivcanon.cc b/gcc/tree-ssa-loop-ivcanon.cc > > > > index bf017137260..5e0eca647a1 100644 > > > > --- a/gcc/tree-ssa-loop-ivcanon.cc > > > > +++ b/gcc/tree-ssa-loop-ivcanon.cc > > > > @@ -444,7 +444,9 @@ tree_estimate_loop_size (class loop *loop, edge > > > > exit, edge edge_to_cancel, > > > > > > > > static unsigned HOST_WIDE_INT > > > > estimated_unrolled_size (struct loop_size *size, > > > > - unsigned HOST_WIDE_INT nunroll) > > > > + unsigned HOST_WIDE_INT nunroll, > > > > + enum unroll_level ul, > > > > + class loop* loop) > > > > { > > > > HOST_WIDE_INT unr_insns = ((nunroll) > > > > * (HOST_WIDE_INT) (size->overall > > > > @@ -453,7 +455,15 @@ estimated_unrolled_size (struct loop_size *size, > > > > unr_insns = 0; > > > > unr_insns += size->last_iteration - > > > > size->last_iteration_eliminated_by_peeling; > > > > > > > > - unr_insns = unr_insns * 2 / 3; > > > > + /* For innermost loop, loop body is not likely to be simplied as > > > > much as 1/3. > > > > + and may increase a lot of register pressure. > > > > + UL != UL_ALL is need to unroll small loop at O2. */ > > > > + class loop *loop_father = loop_outer (loop); > > > > + if (loop->inner || !loop_father > > > > > > Do we ever get here for !loop_father? We shouldn't. > > > > > > > + || loop_father->latch == EXIT_BLOCK_PTR_FOR_FN (cfun) > > > > > > This means you excempt all loops that are direct children of the loop > > > root tree. That doesn't make much sense. > > > > > > > + || ul != UL_ALL) > > > > > > This is also quite odd - we're being more optimistic for UL_NO_GROWTH > > > than for UL_ALL? This doesn't make much sense. > > > > > > Overall I think this means removal of being optimistic doesn't work so > > > well? > > They're mostly used to avoid testcase regressions., the regressed > > testcases rely on the behavior of complete unroll from the first > > unroll, but now it's only unrolled by the second unroll. > > I checked some, the codegen are the same, I need to go through all of > > them, if the final codegen are the same or optimal, I'll just adjust > > testcases? > > > > ++: g++.dg/warn/Warray-bounds-20.C -std=gnu++14 LP64 note (test for > > > > g++warnings, line 56) > > > > g++: g++.dg/warn/Warray-bounds-20.C -std=gnu++14 note (test for > > > > g++warnings, line 66) > > > > g++: g++.dg/warn/Warray-bounds-20.C -std=gnu++17 LP64 note (test for > > > > g++warnings, line 56) > > > > g++: g++.dg/warn/Warray-bounds-20.C -std=gnu++17 note (test for > > > > g++warnings, line 66) > > > > g++: g++.dg/warn/Warray-bounds-20.C -std=gnu++20 LP64 note (test for > > > > g++warnings, line 56) > > > > g++: g++.dg/warn/Warray-bounds-20.C -std=gnu++20 note (test for > > > > g++warnings, line 66) > > > > g++: g++.dg/warn/Warray-bounds-20.C -std=gnu++98 LP64 note (test for > > > > g++warnings, line 56) > > > > g++: g++.dg/warn/Warray-bounds-20.C -std=gnu++98 note (test for > > > > g++warnings, line 66) > > This seems to expect unrolling for an init loop rolling 1 times. I don't > see 1/3 of the stmts vanishing but it's definitely an interesting corner > case. That's why I was thinking of maybe adding a --param specifying > an absolute growth we consider "no growth" - but of course that's > ugly as well but it would cover these small loops. > > How do the sizes play out here after your change? Before it's > > size: 13-3, last_iteration: 2-2 > Loop size: 13 > Estimated size after unrolling: 13 > > and the init is quite complex with virtual pointer inits. We do have > > size: 1 _14 = _5 + -1; > Induction variable computation will be folded away. > size: 1 _15 = _4 + 40; > BB: 3, after_exit: 1 > > where we don't realize the + 40 of _15 will be folded into the dereferences > but that would only subtract 1. > > size: 3 C::C (_23, &MEM <const void *[8]> [(void *)&_ZTT2D1 + 48B]); > > that's the biggest cost. > > To diagnose the array bound issue we rely on early unrolling since we avoid > -Warray-bounds after late unrolling due to false positives. > > This is definitely not an unrolling that preserves code size. > > > gcc: gcc.dg/Warray-bounds-68.c (test for warnings, line 18) > > > > gcc: gcc.dg/graphite/interchange-8.c execution test > > An execute fail is bad ... can we avoid this (but file a bugreport!) when > placing #pragma GCC unroll before the innermost loop? We should > probably honor that in early unrolling (not sure if we do). > > > gcc: gcc.dg/tree-prof/update-cunroll-2.c scan-tree-dump-not optimized > > "Invalid sum" > > > > gcc: gcc.dg/tree-ssa/cunroll-1.c scan-tree-dump cunrolli "Last > > iteration exit edge was proved true." > > > > gcc: gcc.dg/tree-ssa/cunroll-1.c scan-tree-dump cunrolli "loop with 2 > > iterations completely unrolled" > > again the current estimate is the same before/after unrolling, here > we expect to retain one compare & branch. > > > gcc: gcc.dg/tree-ssa/dump-6.c scan-tree-dump store-merging "MEM > > <unsigned long> \\[\\(char \\*\\)\\&a8] = " > > > > gcc: gcc.dg/tree-ssa/loop-36.c scan-tree-dump-not dce3 "c.array" > > again the 2/3 scaling is difficult to warrant. The goal of the early > unrolling > pass was abstraction penalty removal which works for low trip-count loops. > So maybe that new --param for allowed growth should scale but instead > of scaling by the loop size as 2/3 does it should scale by the number of > times we peel which means offsetting the body size estimate by a constant. > > Honza? Any idea how to go forward here? > > Thanks, > Richard. > > > gcc: gcc.dg/tree-ssa/ssa-dom-cse-5.c scan-tree-dump-times dom2 "return 3;" 1 > > > > gcc: gcc.dg/tree-ssa/update-cunroll.c scan-tree-dump-times optimized > > "Invalid sum" 0 > > > > gcc: gcc.dg/tree-ssa/vrp88.c scan-tree-dump vrp1 "Folded into: if.*" > > > > gcc: gcc.dg/vect/no-vfa-vect-dv-2.c scan-tree-dump-times vect > > "vectorized 3 loops" 1 > > > > > > > > If we need some extra leeway for UL_NO_GROWTH for what we expect > > > to unroll it might be better to add sth like --param > > > nogrowth-completely-peeled-insns Hard to find a default value satisfying all testcases. some require loop unroll with 7 insns increment, some don't want loop unroll w/ 5 insn increment. The original 2/3 reduction happened to meet all those testcases(or the testcases are constructed based on the old 2/3). Can we define the parameter as the size of the loop, below the size we still do the reduction, so the small loop can be unrolled? > > > specifying a fixed surplus size? Or we need to look at what's the problem > > > with the testcases regressing or the one you are trying to fix. > > > > > > I did experiment with better estimating cleanup done at some point > > > (see attached), > > > but didn't get to finishing that (and as said, as we're running VN on the > > > result > > > we'd ideally do that as part of the estimation somehow). > > > > > > Richard. > > > > > > > + unr_insns = unr_insns * 2 / 3; > > > > + > > > > if (unr_insns <= 0) > > > > unr_insns = 1; > > > > > > > > @@ -837,7 +847,7 @@ try_unroll_loop_completely (class loop *loop, > > > > > > > > unsigned HOST_WIDE_INT ninsns = size.overall; > > > > unsigned HOST_WIDE_INT unr_insns > > > > - = estimated_unrolled_size (&size, n_unroll); > > > > + = estimated_unrolled_size (&size, n_unroll, ul, loop); > > > > if (dump_file && (dump_flags & TDF_DETAILS)) > > > > { > > > > fprintf (dump_file, " Loop size: %d\n", (int) ninsns); > > > > -- > > > > 2.31.1 > > > > > > > > > > > > -- > > BR, > > Hongtao
-- BR, Hongtao