[flang] [openmp] performance issue due to code generation for private variables

[shivaramaarao]

consider the following program

program parallel_do_example
  implicit none
  integer :: i, n, k
  real, dimension(4096) :: a, b, c , x

  n = 4096

  ! Initialize arrays
  do i = 1, n
    a(i) = real(i)
    b(i) = 2.0 * real(i)
    x(k) = 0.0
  end do

  !$OMP PARALLEL DO PRIVATE(x)
  do i = 1, n
    do k = 1, n
      x(k) =  x(k) + a(k) + b(k)
    enddo
    c(i) = a(i) + b(i) * x(i)
  end do
  !$OMP END PARALLEL DO

  ! Print a few results to verify
  print *, 'c(1) = ', c(1)
  print *, 'c(50) = ', c(50)
  print *, 'c(100) = ', c(100)

end program parallel_do_example

$flang -O3 -march=znver5 -fopenmp -S mytest.f90

The generated assembly shows memory allocated for x array through malloc and it is freed at the end of function call

    pushq   %rbp
    pushq   %r15
    pushq   %r14
    pushq   %r13
    pushq   %r12
    pushq   %rbx
    subq    $232, %rsp
    movq    (%rdx), %r15
    movl    $16384, %edi
    movl    (%r15), %ebp
    callq   malloc@PLT

     vzeroupper
        callq   __kmpc_for_static_fini@PLT
.LBB1_30:
        movq    %rbx, %rdi
        callq   free@PLT

This causes significant performance degradation compared to classic flang and ifx compiler. This type of code is present in 350.md benchmark of omp2012. In the benchmark there is an array of size 3 is used and it is being allocated and freed.

A solution would be to allocate the variables in stack rather than malloc and free. that would help to improve the benchmark performance.

[tblah]

The use of heap allocations was because it is difficult to be certain whether these allocations are going to be inserted in a loop body or not (given nested directives, outlined functions, etc). One alternative would be to use stack save/restore, but @Meinersbur has pointed out in the past that this might lead to suboptimal codegen. Or we could try just using a normal alloca and see if this theoretical problem actually bites us in practice (perhaps not if other compilers get away with it).

@ergawy @Meinersbur do you have any preference?

Note: we likely have the same performance issue with reductions.

[ergawy]

This is why we moved from malloc to stack allocations for (at least some parts of) reductions on the GPU: #146667. We were seeing performance degradations that were alleviated by stack allocations. However, as Tom said, Michael might have some reservations. I am interested to learn more as well about the limitation of stack save/restore here.

[yus3710-fj]

FYI: I found a performance degradation on SPEChpc 2021, and its cause seems to be similar to this issue.

[Meinersbur]

There were proposals of a heap-to-stack optimization that might have optimized this: https://reviews.llvm.org/D53362

The optimization problem @tblah mentions is that LLVM nearly only optimizes allocas in a function's entry basic block. stacksave/stackrestore is rarely used and therefore almost never considered for optimization. It is also difficult because suddenly you have to preserve (Post-)Dominance.

Howver, if the allocation size is constant (like in this example), the alloca can be directly inserted into the basic block. We would need malloc only as a fallback. However, 4096 array elements is quite big (16 kB, typical recommendation is 1kB max array size on the stack), which introduces issues on its own:

1. Risk of stack overflow in recursive functions. Max stack size varies between platforms, e.g just 128kB with musl.

2. Compilers start to emit stack probing for security reasons

I think it would be fine to allocate fixed-size arrays below a threshold size in the function's exit block (if we had a heap-to-stack optimization, that would happen automatically), but I would not do it implicitly for 16kB arrays.

[tblah]

Flang already (by default) assumes a large stack size is configured. In base fortran (no OpenMP) even very large local arrays are allocated on the stack by default. Many popular programs (e.g. spec2017) only run with an unlimited stack size configured.

There is a pass for moving these arrays to the heap but I don't think there are even flags for users to enable that.

[Meinersbur]

From the GNU pthread_create man page:

Larger stacks might be possible for the main thread (which traditionally starts at the end of the virtual address space, which in 64 bit is a looong way down until it reaches something from at the beginng of the address space).

The problem is that having too big arrays on the stack degrades worse than having too many mallocs: The program crashes compared to the program running slower that it could. I'd use a safe default for the max size of arrays on the stack, with larger one possible with -fstack-arrays/-fmax-stack-var-size like gfortran does. Its sensible to assume gfortran had good reasons to do it this way.

https://flang.llvm.org/docs/fstack-arrays.html describes it the other way around, but IMHO data should be moved to the stack only if there is positive confirmation it is safe to do so. Too big objects on the stack are not safe. Since you already got the design document approves, I will not object. I guess we have different perspectives. Intel does this and has -heap-arrays off by default.

Note that this discussion is distinct from variable-sized allocas that may need stacksave/stackrestore when used in a loop. If I remember correctly, the issue was that we were using an alloca within a loop without a stacksave/stackrestore, causing the stack to grow arbitrarily large with each iteration. Optimizations such as SROA only work if for allocas in the entry block. One should never use
stacksave/stackrestore for allocas of constant size, but move it to the entry block (and there is no LLVM pass that does this for you). However, if the allocation size is not loop-invariant, alloca/stacksave/stackrestore is not necessarily worse than malloc/free, apart from the issue of too large stack objects. They are also more challanging to optimize since stackrestore may invalidate any pointer, even allocas that are not passed as an argument. Moreover, there are pointer provenance issues.

Many popular programs (e.g. spec2017) only run with an unlimited stack size configured.

I would consider this a bug. A well-defined program that could run successfully does not.

[tblah]

It goes beyond -fstack-arrays. This was a design decision (predating me) in flang lowering. If you would like to change this behaviour in your downstream compiler so that spec2017 can run without changing the default stack size, you can turn on this pass: https://github.com/llvm/llvm-project/blob/main/flang/lib/Optimizer/Transforms/MemoryAllocation.cpp, but note that even on CPU I would expect this to worsen performance.

I see your point about OpenMP (and thank you for checking the pthread documentation). It is quite a different thing to do this in OpenMP when the stack is partitioned between potentially very many threads.

From this discussion I wonder if large private variables inside of target regions are just a software bug. If the malloc performance is terrible and using large allocas in heavily multithreaded environments is not advisable, then there isn't much that can be done to run that code correctly. Perhaps we should match whatever classic flang did in this situation?

At this point I would lean towards keeping malloc for CPU for the reasons Michael has put forward but I would be very happy to see it if anyone wanted to add a flag to change the default.