public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "rguenther at suse dot de" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/102943] [12 Regression] Jump threader compile-time hog with 521.wrf_r Date: Wed, 03 Nov 2021 13:17:44 +0000 [thread overview] Message-ID: <bug-102943-4-tFQT6MnEHb@http.gcc.gnu.org/bugzilla/> (raw) In-Reply-To: <bug-102943-4@http.gcc.gnu.org/bugzilla/> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102943 --- Comment #12 from rguenther at suse dot de <rguenther at suse dot de> --- On Wed, 3 Nov 2021, aldyh at gcc dot gnu.org wrote: > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102943 > > Aldy Hernandez <aldyh at gcc dot gnu.org> changed: > > What |Removed |Added > ---------------------------------------------------------------------------- > CC| |amacleod at redhat dot com > > --- Comment #10 from Aldy Hernandez <aldyh at gcc dot gnu.org> --- > I tried all sorts of knobs limiting the behavior for large BBs (one function > has over 20k blocks), a large number of imports (dependencies on the final > conditional), and even the max number of blocks to look back. None of them > made a difference. > > Then I realized that this PR was originally reported against the hybrid VRP > threader, which used a different path discovery engine altogether (the old > forward threader). So, the problem can't be in the backward threader path > discovery bits, but in something the solver is doing. > > I timed all the threaders using the solver by functionality (simple versus > fully resolving mode): > > backwards simple : 4.85 ( 2%) 0.00 ( 0%) 4.84 ( 2%) > 932k ( 0%) > backwards full : 54.60 ( 17%) 0.01 ( 1%) 54.70 ( 17%) > 664k ( 0%) > > This confirms my hypothesis that it's not the backward threader discovery bits, > since the above two entries use the same engine. So clearly, it's something > that the fully resolving threader does that was common with the hybrid > threader, i.e. our use of the ranger. > > A callgrind session shows that the majority of the back threader's time is > being spent in: > > path_range_query::range_on_path_entry (irange &r, tree name) > > ...which is understandable, because when we can't resolve an SSA within the > path, we ask the ranger what the range on entry to the path is. > > Curiously though, most of the time is spent in propagate_cache, especially > add_to_update, which is accounting for 37.5% of the threader's time: > > - if (!bitmap_bit_p (m_propfail, bb->index) && !m_update_list.contains (bb)) > - m_update_list.quick_push (bb); > > This is a large CFG, so a linear search of a BB, is bound to be slow. Indeed, vec should never have gotten ::contains () ... I'd have used a regular bitmap, not sbitmap, because we do bb = m_update_list.pop (); and bitmap_first_set_bit is O(n) for an sbitmap bit O(1) for a bitmap. > Just > replacing it with an sbitmap knocks a good 12 seconds: > > backwards jump threading : 48.40 ( 28%) 0.02 ( 1%) 48.57 ( 27%) > 1597k ( 0%) > backwards jump threading : 32.96 ( 22%) 0.09 ( 4%) 33.12 ( 22%) > 1499k ( 0%) > > Not ideal, but a good improvement IMO. > > I'll post my proposed patch, but I suspect Andrew may have other tricks up his > sleeve. > >
next prev parent reply other threads:[~2021-11-03 13:17 UTC|newest] Thread overview: 57+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-10-26 11:13 [Bug tree-optimization/102943] New: VRP " rguenth at gcc dot gnu.org 2021-10-26 11:15 ` [Bug tree-optimization/102943] [12 Regression] " rguenth at gcc dot gnu.org 2021-10-26 11:25 ` rguenth at gcc dot gnu.org 2021-10-26 11:49 ` rguenth at gcc dot gnu.org 2021-10-26 14:57 ` pinskia at gcc dot gnu.org 2021-10-26 14:58 ` marxin at gcc dot gnu.org 2021-10-26 15:06 ` marxin at gcc dot gnu.org 2021-10-30 6:31 ` aldyh at gcc dot gnu.org 2021-10-31 20:06 ` hubicka at gcc dot gnu.org 2021-11-02 7:25 ` [Bug tree-optimization/102943] [12 Regression] Jump " rguenth at gcc dot gnu.org 2021-11-02 7:29 ` aldyh at gcc dot gnu.org 2021-11-03 10:57 ` aldyh at gcc dot gnu.org 2021-11-03 10:58 ` aldyh at gcc dot gnu.org 2021-11-03 13:17 ` rguenther at suse dot de [this message] 2021-11-03 14:33 ` amacleod at redhat dot com 2021-11-03 14:42 ` rguenther at suse dot de 2021-11-04 14:40 ` cvs-commit at gcc dot gnu.org 2021-11-04 14:40 ` cvs-commit at gcc dot gnu.org 2021-11-04 14:40 ` cvs-commit at gcc dot gnu.org 2021-11-04 15:24 ` aldyh at gcc dot gnu.org 2021-11-04 17:00 ` Jan Hubicka 2021-11-04 17:00 ` hubicka at kam dot mff.cuni.cz 2021-11-05 9:08 ` aldyh at gcc dot gnu.org 2021-11-05 11:10 ` marxin at gcc dot gnu.org 2021-11-05 11:13 ` aldyh at gcc dot gnu.org 2021-11-05 11:23 ` marxin at gcc dot gnu.org 2021-11-05 17:16 ` cvs-commit at gcc dot gnu.org 2021-11-07 17:17 ` hubicka at gcc dot gnu.org 2021-11-07 18:16 ` aldyh at gcc dot gnu.org 2021-11-07 18:59 ` Jan Hubicka 2021-11-07 18:59 ` hubicka at kam dot mff.cuni.cz 2021-11-12 22:14 ` hubicka at gcc dot gnu.org 2021-11-14 9:58 ` hubicka at gcc dot gnu.org 2021-11-26 12:38 ` cvs-commit at gcc dot gnu.org 2021-11-30 10:55 ` aldyh at gcc dot gnu.org 2021-12-09 20:17 ` hubicka at gcc dot gnu.org 2022-01-03 8:47 ` rguenth at gcc dot gnu.org 2022-01-03 11:20 ` hubicka at kam dot mff.cuni.cz 2022-01-19 7:06 ` rguenth at gcc dot gnu.org 2022-03-10 11:37 ` rguenth at gcc dot gnu.org 2022-03-10 12:40 ` cvs-commit at gcc dot gnu.org 2022-03-10 13:22 ` rguenth at gcc dot gnu.org 2022-03-10 13:42 ` cvs-commit at gcc dot gnu.org 2022-03-10 13:45 ` rguenth at gcc dot gnu.org 2022-03-10 13:49 ` rguenth at gcc dot gnu.org 2022-03-10 14:01 ` amacleod at redhat dot com 2022-03-10 14:17 ` amacleod at redhat dot com 2022-03-10 14:23 ` rguenth at gcc dot gnu.org 2022-03-10 14:26 ` rguenth at gcc dot gnu.org 2022-03-10 14:33 ` amacleod at redhat dot com 2022-03-10 14:36 ` amacleod at redhat dot com 2022-03-16 19:48 ` amacleod at redhat dot com 2022-03-17 11:14 ` rguenth at gcc dot gnu.org 2022-03-17 13:05 ` amacleod at redhat dot com 2022-03-17 14:18 ` hubicka at kam dot mff.cuni.cz 2022-03-17 20:44 ` cvs-commit at gcc dot gnu.org 2022-03-23 10:40 ` rguenth at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-102943-4-tFQT6MnEHb@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).