]> git.ipfire.org Git - thirdparty/gcc.git/commit
unroll: Run VN on unrolled-and-jammed loops
authorRichard Sandiford <richard.sandiford@arm.com>
Wed, 21 Jul 2021 06:50:20 +0000 (07:50 +0100)
committerRichard Sandiford <richard.sandiford@arm.com>
Wed, 21 Jul 2021 06:50:20 +0000 (07:50 +0100)
commit957952ce64e067c56e58df5ee36bbb004eecffa1
treec8bd8c976b9c5821d706f166eef3808691337a42
parent62acc72a957b561462a436fcb2d6caac5b363190
unroll: Run VN on unrolled-and-jammed loops

Unroll and jam can sometimes leave redundancies.  E.g. for:

  for (int j = 0; j < 100; ++j)
    for (int i = 0; i < 100; ++i)
      x[i] += y[i] * z[j][i];

the new loop will do the equivalent of:

  for (int j = 0; j < 100; j += 2)
    for (int i = 0; i < 100; ++i)
      {
        x[i] += y[i] * z[j][i];
        x[i] += y[i] * z[j + 1][i];
      }

with two reads of y[i] and with a round trip through memory for x[i].

At the moment these redundancies survive till vectorisation, so if
vectorisation succeeds, we're reliant on being able to remove the
redundancies from the vector form.  This can be hard to do if
a vector loop uses predication.  E.g. on SVE we end up with:

.L3:
        ld1w    z3.s, p0/z, [x3, x0, lsl 2]
        ld1w    z0.s, p0/z, [x5, x0, lsl 2]
        ld1w    z1.s, p0/z, [x2, x0, lsl 2]
        mad     z1.s, p1/m, z0.s, z3.s
        ld1w    z2.s, p0/z, [x4, x0, lsl 2]
        st1w    z1.s, p0, [x3, x0, lsl 2]    // store to x[i]
        ld1w    z1.s, p0/z, [x3, x0, lsl 2]  // load back from x[i]
        mad     z0.s, p1/m, z2.s, z1.s
        st1w    z0.s, p0, [x3, x0, lsl 2]
        add     x0, x0, x6
        whilelo p0.s, w0, w1
        b.any   .L3

This patch runs a value-numbering pass on loops after a successful
unroll-and-jam, which gets rid of the unnecessary load and gives
a more accurate idea of vector costs.  Unfortunately the redundant
store still persists without a pre-vect DSE, but that feels like
a separate issue.

Note that the pass requires the loop to have a single exit,
hence the simple calculation of exit_bbs.

gcc/
* gimple-loop-jam.c: Include tree-ssa-sccvn.h.
(tree_loop_unroll_and_jam): Run value-numbering on a loop that
has been successfully unrolled.

gcc/testsuite/
* gcc.dg/unroll-10.c: New test.
gcc/gimple-loop-jam.c
gcc/testsuite/gcc.dg/unroll-10.c [new file with mode: 0644]