From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
 id D44E93861012; Mon, 31 May 2021 09:32:00 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D44E93861012
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/100817] ICE with -O2: in compute_antic, at
 tree-ssa-pre.c:2513
Date: Mon, 31 May 2021 09:32:00 +0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 12.0
X-Bugzilla-Keywords: ice-on-valid-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: ASSIGNED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: rguenth at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: attachments.created
Message-ID: <bug-100817-4-ffhSbUw0pI@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-100817-4@http.gcc.gnu.org/bugzilla/>
References: <bug-100817-4@http.gcc.gnu.org/bugzilla/>
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
X-BeenThere: gcc-bugs@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Gcc-bugs mailing list <gcc-bugs.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Mon, 31 May 2021 09:32:00 -0000

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 50897
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=3D50897&action=3Dedit
patch

(In reply to Richard Biener from comment #3)
> The number of iterations grows linear with loop depth, starting with 6 for
>=20
> for (; a;)
>  for (; a >=3D 0;)
>   for (; a;)
>    for (; a; a +=3D 2)
>     ;
>=20
> adding 2 for every
>=20
>  for (; a;)
>   for (; a >=3D 0;)
>=20
> added.  The issue is that the postorder on the inverted graph chosen for
> iteration is "worst" in how it iterates over the loop nest.  Adding an
> exit to the innermost loop makes antic iteration iterate two times
> independent
> on loop depth.  For anti iteration it's important to minimize the number =
of
> blocks that are visited before all sucessors are visited, but here the wh=
ole
> loop nest is only backwards reachable via backedges but there walking the
> nest outer-to-inner producing N such blocks.
>=20
> Now, doing reverse program order iteration after the initial postorder
> traversal would fix this, so I'm going to explore this idea.

It's measurably worse for regular CFGs (gcc/*.c), just as example:

 attribs.c.334t.statistics:146 pre "compute_antic iterations =3D=3D 2" 39
-attribs.c.334t.statistics:146 pre "compute_antic iterations =3D=3D 3" 27
+attribs.c.334t.statistics:146 pre "compute_antic iterations =3D=3D 3" 17
+attribs.c.334t.statistics:146 pre "compute_antic iterations =3D=3D 4" 9
+attribs.c.334t.statistics:146 pre "compute_antic iterations =3D=3D 5" 1

still only the very first "iteration" technically requires the
postorder on the inverted graph iteration order.  I've attached the patch
I've used for the measurement.

The immediate "fix" would be to remove the assert replacing it with a comme=
nt
refering to this PR.  But not sure if action is really required.=