Non-rectangular loop nests with non-constant iteration step size (original) (raw)

| Description Tobias Burnus 2023-07-19 07:51:21 UTC 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. | | | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | |