ppcg get_schedule cannot fuse loops

[le yin]

1. source code

#define M 1024

#define N 1024

#define K 32

...

for (int i = 0; i < M; i++)

  for (int j = 0; j < N; j++)

  {

      d[i][j] = 0.0;                                         // S_0

      for (int k = 0; k < K; k++)

          d[i][j] += a[i][k] * b[k][j];                  // S_1

  }

for (int i = 0; i < M; i++)

  for (int j = 0; j < N; j++)

  {

      c[i][j] = d[i][j] + e[i][j];                          // S_2

  }

2. ppcg --target= c ... will generates the following code:

for (int i = 0; i <= 1023; i++)

  for (int j = 0; j <= 1023; j++)

  {

      d[i][j] = 0.0;                                         // S_0

      for (int k = 0; k <= 31; k++)

          d[i][j] += a[i][k] * b[k][j];                  // S_1

      c[i][j] = d[i][j] + e[i][j];                          // S_2

  }

3. modify one line in input source code: 

const int K = 32;

Then ppcg --target=c ... will generate the following code:

for (int i = 0; i <= 1023; i++)

  for (int j = 0; j <= 1023; j++)

      d[i][j] = 0.0;                                         // S_0

for (int i = 0; i <= 1023; i++)

  for (int j = 0; j <= 1023; j++)

  {

      for (int k = 0; k < K; k++)

          d[i][j] += a[i][k] * b[k][j];                  // S_1

      c[i][j] = d[i][j] + e[i][j];                          // S_2

  }

S_0 cannot be fused with S_1 and S_2.

Is there any method making loop fusion work even when K is declared as variable?

Thanks in advance~

-Leo

[Sven Verdoolaege]

It may be doing that because it doesn't know anything about K,
including its sign.
It may help if you add something like

__builtin_assume(K > 0);

If you send a complete input, I could have a look.

skimo

[Sven Verdoolaege]

On Fri, Feb 03, 2023 at 05:54:26PM +0100, Sven Verdoolaege wrote:
> It may be doing that because it doesn't know anything about K,
> including its sign.
> It may help if you add something like
>
> __builtin_assume(K > 0);

Note that you can also use the --assume-non-negative-parameters
to add this assumption about all parameters.

It turns out, though, that this information is not fully
exploited yet.
First, PPCG needs to forward this information to isl (ppcg.patch) and
then isl also needs to exploit it in some way (for example isl.patch).

skimo