predictive commoning: reduce load instructions

[vfdff]

• inner loop of test: https://gcc.godbolt.org/z/r3G9EWPrb

  for (k = 1; k < nx-1; k ++) {
      __builtin_prefetch(aa + POffset +  0, 0, 0);
      b[k+i*nx+j*nx*ny] = aa[ 0] * xx( 0, 0, 0)
                        + aa[ 1] * xx( 0,-1, 0)
                        + aa[ 2] * xx( 0, 1, 0)
                        + aa[ 3] * xx( 0, 0,-1)
                        + aa[ 4] * xx( 0, 0, 1)
                        + aa[ 5] * xx( 0, 1, 1)
                        + aa[ 6] * xx( 0, 1,-1)
                        + aa[ 7] * xx( 0,-1,-1)
                        + aa[ 8] * xx( 0,-1, 1)
                        + aa[ 9] * xx(-1, 0, 0)
                        + aa[10] * xx(-1,-1, 0)
                        + aa[11] * xx(-1, 1, 0)
                        + aa[12] * xx(-1, 0,-1)
                        + aa[13] * xx(-1, 0, 1)
                        + aa[14] * xx( 1, 0, 0)
                        + aa[15] * xx( 1,-1, 0)
                        + aa[16] * xx( 1, 1, 0)
                        + aa[17] * xx( 1, 0,-1)
                        + aa[18] * xx( 1, 0, 1);
      aa += 19;
    }

• the comparision of insn number for the above inner loop body

  #1 = clang.s
  #2 = gcc.s
  ||=                             Insn =||=      1 =||=      2 =||=  Diff  =||
  ||                                add ||       12 ||        2 ||       10 ||
  ||                               b.ne ||        1 ||        0 ||        1 ||
  ||                                bgt ||        0 ||        1 ||       -1 ||
  ||                                cmp ||        1 ||        1 ||          ||
  ||                              fmadd ||       18 ||       18 ||          ||
  ||                               fmov ||        0 ||       10 ||      -10 ||         ---  it seems gcc use fmov to reuse the load value
  ||                               fmul ||        1 ||        1 ||          ||
  ||                                ldp ||       11 ||        9 ||        2 ||
  ||                                ldr ||       16 ||       10 ||        6 ||
  ||                               prfm ||        1 ||        1 ||          ||
  ||                                str ||        1 ||        1 ||          ||
  ||              **Total**             ||       62 ||       54 ||        8 ||

[vfdff]

some smarter case, https://gcc.godbolt.org/z/Ej9Ker6v1

[pinskia]

Note the improvement for GCC comes from GCC's Predictive commoning pass which can be read up about via IBM's slides from 2004 on their XLC compiler implementation: http://www.cs.ualberta.ca/~amaral/cascon/CDP04/slides/tal.pdf.

https://lists.llvm.org/pipermail/llvm-dev/2012-December/056550.html was the last reference I saw mentioned for LLVM.

[sjoerdmeijer]

I have removed the "[AArch64]" tag as I don't think this is target specific.

The first test case testsuite/gcc.dg/tree-ssa/predcom-1.c from GCC's test suite nicely illustrates the missed opportunity with a simple fibonacci example:

https://godbolt.org/z/zTf9YMzbo

There is another example of dead store elimination in testsuite/gcc.dg/tree-ssa/predcom-dse-1.c:

https://godbolt.org/z/83rWKsvYc

[madhur13490]

Is anyone (except @sjoerdmeijer) planning to work on this?