[OpenMP] Compilation times increase as the openmp collapse clause argument value increases

[itou-fj]

In gcc, the compilation time does not increase, but in clang, the compilation time increases exponentially as the argument value of the collapse clause increases.

clang(20.1.0-rc1) compilation time
collapse(10): 0.111s
collapse(12): 0.287s
collapse(14): 3.444s
collapse(16): 55.497s
collapse(18): 27m11.931s

gcc(13.3.1-2) compilation time
collapse(10): 0.044s
collapse(12): 0.037s
collapse(14): 0.040s
collapse(16): 0.037s
collapse(18): 0.038s
collapse(20): 0.037s

The testcase

#pragma omp parallel for collapse(20) private(a1,b1,c1,d1,e1,f1,g1,h1,i1,j1,k1,l1,m1,n1,o1,p1,q1,r1,s1,t1,u1,v1,w1,x1,y1,z1)
 for(a1=0; a1<=1; ++a1) {
  for(b1=0; b1<1; ++b1) {
   for(c1=0; c1<1; ++c1) {
    for(d1=0; d1<1; ++d1) {
     for(e1=0; e1<1; ++e1) {
      for(f1=0; f1<1; ++f1) {
       for(g1=0; g1<1; ++g1) {
        for(h1=0; h1<1; ++h1) {
         for(i1=0; i1<1; ++i1) {
          for(j1=0; j1<1; ++j1) {
           for(k1=0; k1<1; ++k1) {
            for(l1=0; l1<1; ++l1) {
             for(m1=0; m1<2; ++m1) {
              for(n1=0; n1<1; ++n1) {
               for(o1=0; o1<1; ++o1) {
                for(p1=0; p1<1; ++p1) {
                 for(q1=0; q1<1; ++q1) {
                  for(r1=0; r1<1; ++r1) {
                   for(s1=0; s1<1; ++s1) {
                    for(t1=0; t1<1; ++t1) {
                     for(u1=0; u1<1; ++u1) {
                      for(v1=0; v1<1; ++v1) {
                       for(w1=0; w1<1; ++w1) {
                        for(x1=0; x1<1; ++x1) {
                         for(y1=0; y1<1; ++y1) {
                          for(z1=0; z1<=1; ++z1) {

  }}}}}}}}}}}}}}}}}}}}}}}}}}

https://godbolt.org/z/En657o8aM

[kawashima-fj]

Complete but simplified reporducer:

void foo() {
#pragma omp parallel for collapse(20)
 for (int a1=0; a1<1; ++a1)
  for (int b1=0; b1<1; ++b1)
   for (int c1=0; c1<1; ++c1)
    for (int d1=0; d1<1; ++d1)
     for (int e1=0; e1<1; ++e1)
      for (int f1=0; f1<1; ++f1)
       for (int g1=0; g1<1; ++g1)
        for (int h1=0; h1<1; ++h1)
         for (int i1=0; i1<1; ++i1)
          for (int j1=0; j1<1; ++j1)
           for (int k1=0; k1<1; ++k1)
            for (int l1=0; l1<1; ++l1)
             for (int m1=0; m1<2; ++m1)
              for (int n1=0; n1<1; ++n1)
               for (int o1=0; o1<1; ++o1)
                for (int p1=0; p1<1; ++p1)
                 for (int q1=0; q1<1; ++q1)
                  for (int r1=0; r1<1; ++r1)
                   for (int s1=0; s1<1; ++s1)
                    for (int t1=0; t1<1; ++t1)
                     for (int u1=0; u1<1; ++u1)
                      for (int v1=0; v1<1; ++v1)
                       for (int w1=0; w1<1; ++w1)
                        for (int x1=0; x1<1; ++x1)
                         for (int y1=0; y1<1; ++y1)
                          for (int z1=0; z1<1; ++z1)
                           ;
}

Quick analysis:

• clang -fopenmp -fsyntax-only finishes soon.
• clang -fopenmp -Xclang -ast-dump finishes soon and the output AST is not so large (479 lines).
• clang -fopenmp -S -emit-llvm takes time and the output IR is large (4194586 lines).
• clang -fopenmp -S takes much more time.

I don't know this matters in real applications.

[foxtran]

The largest collapse, which I saw, is collapse(8). But it was in Fortran code.