From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id B8E073858C33; Wed, 19 Jul 2023 07:51:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B8E073858C33 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1689753081; bh=tzbdB8xkuNhEN7y3F2KkHKrPOlI0izRhOzMaP0PCofU=; h=From:To:Subject:Date:From; b=WMwWVMWGZjluiNj/P8UWimry6ud5rMzDVkrkb550mLBQMCOc0LPPNEjuXbnCCUv+z WCaJQ8CdFoOpZm8B16x6IcRCLybe08Xub/4KZtw+0OJFua2GfeF21EhjdQnenXkFZr zSvowBk8SHhK/a+u1PrNvomDqzGX9uJ+0ORzljGg= From: "burnus at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug fortran/110735] New: [OpenMP] Rejected: Non-rectangular loop nests with non-constant iteration step size Date: Wed, 19 Jul 2023 07:51:21 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: fortran X-Bugzilla-Version: 14.0 X-Bugzilla-Keywords: openmp, rejects-valid X-Bugzilla-Severity: normal X-Bugzilla-Who: burnus at gcc dot gnu.org X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status keywords bug_severity priority component assigned_to reporter cc target_milestone Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D110735 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 =3D 1, 10, istep1 do j =3D 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 =E2=80=98j=E2=80=99 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 =3D 0; count.0 < D.4278; count.0 =3D count.0 + 1) { idx =3D 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 nee= ded. 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 t= he step points into the wrong direction. Namely, just replacing 'end' in the '= idx =E2=80=B9cond=E2=80=BA end' condition by: if (begin =3D< end) ! likewise for the offsets, if the factors are ident= ical end' =3D (step > 0 || end =3D=3D intmin) ? end : begin - 1 =E2=80=B9cond=E2=80=BA :=3D '<=3D' else ! begin > end end' =3D (step < 0 || end =3D=3D intmax) ? end : begin + 1 =E2=80=B9cond=E2=80=BA :=3D '<=3D' The outer 'if' condition is compile time known while the 'step' condition i= s a run-time condition. Regarding intmin/intmax, that should be for the data-ty= pe of idx =E2=80=93 which might be different to the one of the 'end' expressio= n. (The "end'" evaluation is done before the loops.) Remark: 'end' is modified to make it easier to get 'idx =3D begin' as resul= t 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 =3D (outer-var,factor,offset) and idx =E2=80=B9cond=E2=80=BA (outer-var,factor,offset) where 'cond' is <=3D or >=3D and the tuple is internally a TREE_VEC. For a Fortran loop DO i =3D m1, m2, m3 the "iteration count is established and is the value of the expression (m2 = =E2=88=92 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 =3D 10, 1, 1 -> iteration count =3D=3D 0 / zero-trip loop (b) depending on the step size '<=3D' or '>=3D' is the right condition when using the simple loop 'for (i =3D m1; i =E2=80=B9cond=E2=80=BA m2= ; i +=3D m3)' (c) For a zero-trip loop with lastprivate, "i" after the loop must have the value of "m1", see PR 110718.=