clang: 18: hangs with a short program in Polly's runIslScheduleOptimizer

[wierton]

Reproducer: https://godbolt.org/z/8K3cs6ood
When compile below program with -O1 -mllvm -polly, clang hangs:

#define IND(x, y) ((x) + (y)*516)
float **a, **b, **c;
__attribute__((noinline)) void foo(
    int I, int J, int K1, int K2, int L1, int L2) {
  for (int i = 0; i < I; i++) {
    float *v = c[i];

    for (volatile int j = 0; j < J; j++) {
      float *in = a[j];
      float *out = b[j];
      for (int l = L1; l < L2; l++) {
        for (int k = K1; k < K2; k++) {
          float sum = 0;
          int offset = 0;
          for (int m = -2; m <= 2; m++) {
            for (int n = -2; n <= 2; n++, offset++)
              sum += in[IND((k + n), (l + m))] * v[offset];
          }
          out[IND(k, l)] = sum;
        }
      }
    }
  }
}

[llvmbot]

@llvm/issue-subscribers-polly

Author: wt.cc (wierton)

Reproducer: https://godbolt.org/z/8K3cs6ood When compile below program with `-O1 -mllvm -polly`, clang hangs:

#define IND(x, y) ((x) + (y)*516)
float **a, **b, **c;
__attribute__((noinline)) void foo(
    int I, int J, int K1, int K2, int L1, int L2) {
  for (int i = 0; i < I; i++) {
    float *v = c[i];

    for (volatile int j = 0; j < J; j++) {
      float *in = a[j];
      float *out = b[j];
      for (int l = L1; l < L2; l++) {
        for (int k = K1; k < K2; k++) {
          float sum = 0;
          int offset = 0;
          for (int m = -2; m <= 2; m++) {
            for (int n = -2; n <= 2; n++, offset++)
              sum += in[IND((k + n), (l + m))] * v[offset];
          }
          out[IND(k, l)] = sum;
        }
      }
    }
  }
}

[kartcq]

Hi @wierton
The hang is due to a very long compile time issue in Polly's Schedule Optimizer in function runIslScheduleOptimizer. It is calling compute_schedule which is taking a very long time to compute the schedule for this test. Will post a patch to address this.

[chrisj-quic]

@kartcq It looks like the computation steps for compule_schedule by isl needs to be bounded. (You can refer Dependences::calculateDependences for an example)