From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id AC9753856DE0; Thu, 11 Aug 2022 13:01:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AC9753856DE0 From: "cvs-commit at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/106514] [12/13 Regression] ranger slowness in path query Date: Thu, 11 Aug 2022 13:01:05 +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: cvs-commit at gcc dot gnu.org X-Bugzilla-Status: NEW X-Bugzilla-Resolution: X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: 12.2 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 X-BeenThere: gcc-bugs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-bugs mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 11 Aug 2022 13:01:05 -0000 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D106514 --- Comment #8 from CVS Commits --- The master branch has been updated by Richard Biener : https://gcc.gnu.org/g:16b013c9d9b4d950f89821476e791bf18c1295df commit r13-2020-g16b013c9d9b4d950f89821476e791bf18c1295df Author: Richard Biener Date: Tue Aug 9 13:37:26 2022 +0200 tree-optimization/106514 - revisit m_import compute in backward threadi= ng This revisits how we compute imports later used for the ranger path query during backwards threading. The compute_imports function of the path solver ends up pulling the SSA def chain of regular stmts without limit and since it starts with just the gori imports of the path exit it misses some interesting names to translate during path discovery. In fact with a still empty path this compute_imports function looks like not the correct tool. The following instead implements what it does during the path discovery and since we add the exit block we seed the initial imports and interesting names from just the exit conditional. When we then process interesting names (aka imports we did not yet see the definition of) we prune local defs but add their uses in a similar way as compute_imports would have done. compute_imports also is lacking in its walking of the def chain compared to range_def_chain::get_def_chain which for example handles &_1->x specially through range_op_handler and gimple_range_operand1, so the code copies this. A fix for compute_imports will be done separately, also fixing the unbound walk there. The patch also properly unwinds m_imports during the path discovery backtracking and from a debugging session I have verified the two sets evolve as expected now while previously behaving slightly erratic. Fortunately the m_imports set now also is shrunken significantly for the PR69592 testcase (aka PR106514) so that there's overall speedup when increasing --param max-jump-thread-duplication-stmts as 15 -> 30 -> 60 -> 120 from 1s -> 2s -> 13s -> 27s to with the patch 1s -> 2s -> 4s -> 8s. This runs into a latent issue in X which doesn't seem to expect any PHI nodes with a constant argument on an edge inside the path. But we now have those as interesting, for example for the ICEing g++.dg/torture/pr100925.C which just has sth like if (i) x =3D 1; else x =3D 5; if (x =3D=3D 1) ... where we now have the path from if (i) to if (x) and the PHI for x in the set of imports to consider for resolving x =3D=3D 1 which IMHO looks exactly like what we want. The path_range_query::ssa_range_in_phi papers over the issue and drops the range to varying instead of crashing. I didn't want to mess with this any further in this patch (but I couldn't resist replacing the loop over PHI args with PHI_ARG_DEF_FROM_EDGE, so mind the re-indenting). PR tree-optimization/106514 * tree-ssa-threadbackward.cc (back_threader::find_paths_to_name= s): Compute and unwind both m_imports and interesting on the fly du= ring path discovery. (back_threader::find_paths): Compute the original m_imports from just the SSA uses of the exit conditional. Drop handling single_succ_to_potentially_threadable_block. * gimple-range-path.cc (path_range_query::ssa_range_in_phi): Ha= ndle constant PHI arguments without crashing. Use PHI_ARG_DEF_FROM_EDGE. * gcc.dg/tree-ssa/ssa-thread-19.c: Un-XFAIL. * gcc.dg/tree-ssa/ssa-thread-20.c: New testcase.=