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 67F1A3858C52; Tue, 21 Mar 2023 10:33:28 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 67F1A3858C52
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1679394808;
	bh=GGjphSR3nDZ6sq1Xm1+CoBoxHPYnQFizER7vXv5Dgn4=;
	h=From:To:Subject:Date:In-Reply-To:References:From;
	b=B47SlN+5xVz4EAj/IuaqKH3ouIw+ujHczzwihztTpaLoBxh3g16gQc7CyJyp8QxU8
	 Cop63jll9g6SkkYxgvjhhQ2IHJmI6pSS+vLUSZqLZpXz90j9eTsNgrEhADGTi6PgqS
	 VSMJ0a+sQZUIAKM/bfDN6ILiF0acQQb7maXoTc5Y=
From: "rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/109192] [13 Regression] timeout with -O3
 since r13-5579
Date: Tue, 21 Mar 2023 10:33:26 +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: 13.0
X-Bugzilla-Keywords: compile-time-hog, needs-reduction
X-Bugzilla-Severity: normal
X-Bugzilla-Who: rguenth at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P1
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 13.0
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: 
Message-ID: <bug-109192-4-6zpu2n01d1@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-109192-4@http.gcc.gnu.org/bugzilla/>
References: <bug-109192-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
List-Id: <gcc-bugs.sourceware.org>

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #7)
> Created attachment 54716 [details]
> proposed patch
>=20
> This is due to the latter part of the specified patch.  We normally
> terminate outgoing range calculations once the LHS has reverted to VARYING
> as we won't learn anything new.
>=20
> The original patch modified this such that if there was a relation presen=
t,
> we continued calculating as the relation may provide new information, as =
per
> the original PR.
>=20
> The problem exposed in this PR is that the presence of a relation doesn't
> mean that relation can actually affect the range.  This PR shows many
> relations, none of which are relevant, and with the quadratic nature of t=
he
> path query, it makes things quite bad.
>=20
> The attached patch is in testing.  It adds a check to determine if the
> relation can affect the outgoing range or not by checking if the operands
> are used in the calculation or not.  If they are not in the definition
> chain, they can have no impact, and we stop the attempt.

Sounds reasonable without knowing all the details in the implementation.
How does it affect compile-times on the testcase?=