llvm / llvm/llvm-project

[flang][OpenMP] Imperfectly nested loops with COLLAPSE are rejected

Open
#199,092 4 comments 0 reactions 1 assignee Claimed by @cenewcombe View on GitHub
flang:frontend flang:ir flang:openmp
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

## Summary

Flang rejects imperfectly nested loops when used with `collapse`, requiring a "perfect nest." However, OpenMP 5.0 (November 2018) relaxed the loop nesting requirements to explicitly allow intervening code between associated loops in a collapsed loop nest.

## Affected constructs

All loop-associated directives that accept `collapse` are affected:
- `!$omp do collapse(N)` / `!$omp parallel do collapse(N)`
- `!$omp simd collapse(N)`
- `!$omp distribute collapse(N)`
- `!$omp taskloop collapse(N)`
- All combined/composite variants (`do simd`, `parallel do simd`, etc.)

These all share the same code path in Flang's semantics checker.

## Reproducer

```fortran
program main
implicit none
integer,parameter :: N = 10
integer :: arr(N,N)
integer :: i,j

arr = 0

!$omp parallel do collapse(2)
do i=1,N
arr(1,i) = 2
do j=1,N
arr(j,i) = 1
end do
end do
!$omp end parallel do
end program main
```

## Error output

```
error: Semantic errors in collapse_imperfectly_nested.f90
collapse_imperfectly_nested.f90:10:9: error: This construct requires a perfect nest of depth 2, but the associated nest is a perfect nest of depth 1
!$omp parallel do collapse(2)
^^^^
collapse_imperfectly_nested.f90:12:5: because: This code prevents perfect nesting
arr(1,i) = 2
^^^^^^^^^^^^
collapse_imperfectly_nested.f90:10:14: because: COLLAPSE clause was specified with argument 2
!$omp parallel do collapse(2)
^^^^^^^^^^^
```

The same error is produced for `!$omp simd collapse(2)`, `!$omp distribute collapse(2)`, and `!$omp taskloop collapse(2)`.

## Expected behavior

The code should compile and execute without error.

## Standards reference

OpenMP 4.5 required perfectly nested loops for `collapse`. OpenMP 5.0 (November 2018) removed this restriction, allowing intervening code between associated loops for simd constructs, worksharing-loop constructs, distribute constructs, and taskloop constructs. Perfect nesting was required per OpenMP 5.0 when `ordered` is present, but this restriction no longer exists in the OpenMP 6.0 spec.

Per the OpenMP 6.0 specification:

> The collapse of affected loops that are imperfectly nested loops was defined for simd constructs (see Section 12.4), worksharing-loop constructs (see Section 13.6), distribute constructs (see Section 13.7) and taskloop constructs (see Section 14.2).

## Work needed

1. **Semantics** (`flang/lib/Semantics/openmp-utils.cpp`): `GetAffectedNestDepthWithReason` unconditionally sets `needPerfect = true` for any directive accepting COLLAPSE.

2. **Lowering** (`flang/lib/Lower/OpenMP/Utils.cpp`): `getNestedDoConstruct` asserts on any intervening code between loops. `collectLoopRelatedInfo` and `getCollapsedLoopEval` assume perfect nesting when walking the loop nest. These need to tolerate and emit intervening code.

3. **MLIR/LLVM** — likely no changes needed. The LLVM `OpenMPIRBuilder::collapseLoops` already handles in-between code by sinking it into the collapsed body (executing it once per combined iteration). The MLIR `omp.loop_nest` translation already feeds individual `CanonicalLoopInfo`s to `collapseLoops`. The main work is getting Flang's lowering to produce the right MLIR with the intervening code in place.

Assisted by: Copilot

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.