[Bug fortran/110735] New: [OpenMP] Rejected: Non-rectangular loop nests with non-constant iteration step size

[Bug fortran/110735] New: [OpenMP] Rejected: Non-rectangular loop nests with non-constant iteration step size

[burnus at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110735

            Bug ID: 110735
           Summary: [OpenMP] Rejected: Non-rectangular loop nests with
                    non-constant iteration step size
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: openmp, rejects-valid
          Severity: normal
          Priority: P3
         Component: fortran
          Assignee: unassigned at gcc dot gnu.org
          Reporter: burnus at gcc dot gnu.org
                CC: jakub at gcc dot gnu.org
  Target Milestone: ---

Follow up for the remaining parts of PR 107424

  !$omp parallel do collapse(2)
  do i = 1, 10, istep1
    do j = 0, i, istep2  ! triangular form: uses outer index 'i'
    end do
  end do

Currently fails with:

  sorry, unimplemented: non-rectangular loop nest with non-constant step for
‘j’

The issue is that the step size is not known at compile time;
in particular, not the sign of the step size.

* * *

For non-simple loops, gfortran uses an auxiliary variable; its use has been
drastically reduced (see PR 107424 for the history) but for the case above
there is still a loop generated:

#pragma omp parallel
 #pragma omp for private(count.0) private(idx) nowait
 for (count.0 = 0; count.0 < D.4278; count.0 = count.0 + 1) {
   idx = count.0 * D.4277 + begin;

That's fine in general - but when the outer iteration variable 'idx' is
used as begin/end value for an inner loop as part of an OpenMP
(non-rectangular) loop nest, this will fail as only 'count' is readily
available but for the internal representation and further use, 'idx' is needed.

See background below for some constraints and implementation details.

* * *

TODO: Handle the general case as well.

See also https://gcc.gnu.org/pipermail/gcc-patches/2023-January/610351.html
for some ideas (some have already been implemented).

The not-yet implemented specific case is the following, which could be
implemented without much effort:

For begin and end being compile-time known - and in case of nonrectangular loop
nests, when the offsets and factors are compile-time known for begin and end
and  additionally, the factor is identical, the simple representation can be
used:

The following is needed to ensure that the loop is not iterated at all if the
step points into the wrong direction. Namely, just replacing 'end' in the 'idx
‹cond› end' condition by:

  if (begin =< end)  ! likewise for the offsets, if the factors are identical
    end' = (step > 0 || end == intmin) ? end : begin - 1
    ‹cond› := '<='
  else  ! begin > end
    end' = (step < 0 || end == intmax) ? end : begin + 1
    ‹cond› := '<='

The outer 'if' condition is compile time known while the 'step' condition is a
run-time condition. Regarding intmin/intmax, that should be for the data-type
of idx – which might be different to the one of the 'end' expression. (The
"end'" evaluation is done before the loops.)

Remark: 'end' is modified to make it easier to get 'idx = begin' as result for
a zero-trip loop with lastprivate (see below); otherwise, 'begin' could be
modified alternatively.

* * *

Background:

the begin/end for a non-rect loop nest are represented as
  idx = (outer-var,factor,offset)
and
  idx ‹cond› (outer-var,factor,offset)
where 'cond' is <= or >= and the tuple is internally a TREE_VEC.

For a Fortran loop
  DO i = m1, m2, m3
the "iteration count is established and is the value of the expression (m2 − m1
+ m3)/m3 unless that value is negative, in which case the iteration count is
0." (F2023, 11.1.7.4.1 Loop initiation).

For OpenMP, the follow needs to be handled:
(a)  do i = 10, 1, 1  -> iteration count == 0 / zero-trip loop
(b)  depending on the step size '<=' or '>=' is the right condition
     when using the simple loop 'for (i = m1; i ‹cond› m2; i += m3)'
(c)  For a zero-trip loop with lastprivate, "i" after the loop must
     have the value of "m1", see PR 110718.