From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id BCF823858D39; Wed, 25 Jan 2023 11:19:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BCF823858D39 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1674645577; bh=MtwZmfXxHXKxecQ8vzvmpy6bk2MIc6mjf+Fk+YGx4So=; h=From:To:Subject:Date:In-Reply-To:References:From; b=JQ3y7YlTcitD0YzY1Y0AjkKffew4Ae4d7phEI+xlj2xOkHmbBg/iIa4e3K7ETNx/b Tkz3J+/tAGEdVl6YLojrNQ7CjtibjjOD2HvIe4mdldoVB4QxJxEurqZkolXko/Walm v03JP5ZjVNqyziOwMPia2jTNRiRI2/a9TNiPUoak= From: "rguenth at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/108523] [13 Regression] -O1 -fcode-hoisting causes long compilation time ? Date: Wed, 25 Jan 2023 11:19:37 +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 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: 13.0 X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: 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=3D108523 --- Comment #11 from Richard Biener --- So the issue is that we oscillate between recognizing the PHI as degenerate because of an equivalence recorded on the non-backedge(!) to the backedge v= alue which in turn changes because of this change: Value numbering stmt =3D g_6_lsm.126_456 =3D PHI Setting value number of g_6_lsm.126_456 to _347 ... Value numbering stmt =3D _350 =3D g_6_lsm.126_456; Setting value number of _350 to _347 (changed) _347 is available for _347 Value numbering stmt =3D _352 =3D _348 ^ _350; _347 is available for _347 Match-and-simplified _348 ^ _350 to _346 RHS _348 ^ _350 simplified to _346 Setting value number of _352 to _346 (changed) _346 is available for _346 Value numbering stmt =3D g_6_lsm.126_304 =3D _352; Setting value number of g_6_lsm.126_304 to _346 (changed) _346 is available for _346 Looking for changed values of backedge 19->20 destination PHIs Setting value number of g_481.64_448 to g_481.64_448 Setting value number of .MEM_464 to .MEM_409 Predication says _347 and _346 are equal on edge 108 -> 20 Setting value number of g_6_lsm.126_456 to _346 (changed) Iterating to 25 BB20 ... Value numbering stmt =3D g_6_lsm.126_456 =3D PHI Predication says _347 and _346 are equal on edge 108 -> 20 Setting value number of g_6_lsm.126_456 to _346 ... Value numbering stmt =3D _350 =3D g_6_lsm.126_456; Setting value number of _350 to _346 (changed) _346 is available for _346 Value numbering stmt =3D _352 =3D _348 ^ _350; _346 is available for _346 Match-and-simplified _348 ^ _350 to _347 RHS _348 ^ _350 simplified to _347 Setting value number of _352 to _347 (changed) _347 is available for _347 Value numbering stmt =3D g_6_lsm.126_304 =3D _352; Setting value number of g_6_lsm.126_304 to _347 (changed) _347 is available for _347 Looking for changed values of backedge 19->20 destination PHIs Setting value number of g_481.64_448 to g_481.64_448 Setting value number of .MEM_464 to .MEM_409 Setting value number of g_6_lsm.126_456 to _347 (changed) Iterating to 25 BB20 and repeat. And we have: _348 =3D _346 ^ _347; and [local count: 42914375]: # g_1198.66_449 =3D PHI <_358(141), 0(17)> # g_6_lsm.126_131 =3D PHI g_481_lsm.127_447 =3D 1; _57 =3D g_6_lsm.126_131; _58 =3D _57 ^ _348; g_6_lsm.126_338 =3D _58; if (_346 !=3D _347) goto ; [5.50%] else goto ; [94.50%] [local count: 40554084]: goto ; [100.00%] So when the value we compare to oscillates. Interestingly when I try to feed a similar case into FRE1 that "works": int foo (int a, int b, int n) { int val =3D a; if (a =3D=3D b) { do { val =3D (a ^ b) ^ val; } while (--n > 0); } return val; } but maybe this is by luck. So what we need to avoid is for an equivalence a =3D=3D b, to oscillate between 'a' and 'b' as result.=