public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
* [Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow
@ 2024-04-04 8:54 rguenth at gcc dot gnu.org
2024-04-04 9:52 ` [Bug middle-end/114579] " rguenth at gcc dot gnu.org
` (3 more replies)
0 siblings, 4 replies; 5+ messages in thread
From: rguenth at gcc dot gnu.org @ 2024-04-04 8:54 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114579
Bug ID: 114579
Summary: RTL expansion add_scope_conflicts is slow
Product: gcc
Version: 14.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: middle-end
Assignee: unassigned at gcc dot gnu.org
Reporter: rguenth at gcc dot gnu.org
Target Milestone: ---
For the testcase in PR114480 at -O1 we see
> expand vars : 9.19 ( 9%)
> expand : 14.26 ( 15%)
or worse percentages after recent improvements in other areas. The main
compile-time is spent in a lot of bitmap_ior calls which almost all
originate from add_scope_conflicts_1 doing
if (for_conflict && visit == visit_op)
{
/* If this is the first real instruction in this BB we need
to add conflicts for everything live at this point now.
Unlike classical liveness for named objects we can't
rely on seeing a def/use of the names we're interested in.
There might merely be indirect loads/stores. We'd not add any
conflicts for such partitions. */
bitmap_iterator bi;
unsigned i;
EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi)
{
class stack_var *a = &stack_vars[i];
if (!a->conflicts)
a->conflicts = BITMAP_ALLOC (&stack_var_bitmap_obstack);
bitmap_ior_into (a->conflicts, work);
the testcase has a lot of live variables and this piece is obviously
quadratic in this. A better representation than a conflict bitmap might
be a O(n) unification leader map. But of course unifying two conflict sets
is then O(number-of-vars) unless you do this on-demand like PTAs 'find'
where query works recursively, updating leaders on demand.
^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug middle-end/114579] RTL expansion add_scope_conflicts is slow 2024-04-04 8:54 [Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow rguenth at gcc dot gnu.org @ 2024-04-04 9:52 ` rguenth at gcc dot gnu.org 2024-04-05 18:44 ` pinskia at gcc dot gnu.org ` (2 subsequent siblings) 3 siblings, 0 replies; 5+ messages in thread From: rguenth at gcc dot gnu.org @ 2024-04-04 9:52 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114579 --- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> --- Created attachment 57872 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57872&action=edit patch Doing this no longer will be able to handle A conflicts B, B conflicts C but A does not conflict C. But it might be something for -O1. ^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug middle-end/114579] RTL expansion add_scope_conflicts is slow 2024-04-04 8:54 [Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow rguenth at gcc dot gnu.org 2024-04-04 9:52 ` [Bug middle-end/114579] " rguenth at gcc dot gnu.org @ 2024-04-05 18:44 ` pinskia at gcc dot gnu.org 2024-05-02 6:32 ` cvs-commit at gcc dot gnu.org 2024-05-02 11:34 ` rguenth at gcc dot gnu.org 3 siblings, 0 replies; 5+ messages in thread From: pinskia at gcc dot gnu.org @ 2024-04-05 18:44 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114579 Andrew Pinski <pinskia at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|UNCONFIRMED |NEW Last reconfirmed| |2024-04-05 Ever confirmed|0 |1 --- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> --- Confirmed. ^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug middle-end/114579] RTL expansion add_scope_conflicts is slow 2024-04-04 8:54 [Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow rguenth at gcc dot gnu.org 2024-04-04 9:52 ` [Bug middle-end/114579] " rguenth at gcc dot gnu.org 2024-04-05 18:44 ` pinskia at gcc dot gnu.org @ 2024-05-02 6:32 ` cvs-commit at gcc dot gnu.org 2024-05-02 11:34 ` rguenth at gcc dot gnu.org 3 siblings, 0 replies; 5+ messages in thread From: cvs-commit at gcc dot gnu.org @ 2024-05-02 6:32 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114579 --- Comment #3 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>: https://gcc.gnu.org/g:bbe83599320288025a417c54d9afcb3885cb2766 commit r15-99-gbbe83599320288025a417c54d9afcb3885cb2766 Author: Richard Biener <rguenther@suse.de> Date: Thu Apr 4 14:00:10 2024 +0200 middle-end/114579 - speed up add_scope_conflicts The following speeds up stack variable conflict detection by recognizing that the all-to-all conflict recording is only necessary for CFG merges as it's the unioning of the live variable sets that doesn't come with explicit mentions we record conflicts for. If we employ this optimization we have to make sure to perform the all-to-all conflict recording for all CFG merges even those into empty blocks where we might previously have skipped this. I have reworded the comment before the all-to-all conflict recording since it seemed to be confusing and missing the point - but maybe I am also missing something here. Nevertheless for the testcase in the PR the compile-time spend in add_scope_conflicts at -O1 drops from previously 67s (39%) to 10s (9%). PR middle-end/114579 * cfgexpand.cc (add_scope_conflicts_1): Record all-to-all conflicts only when there's a CFG merge but for all CFG merges. ^ permalink raw reply [flat|nested] 5+ messages in thread
* [Bug middle-end/114579] RTL expansion add_scope_conflicts is slow 2024-04-04 8:54 [Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow rguenth at gcc dot gnu.org ` (2 preceding siblings ...) 2024-05-02 6:32 ` cvs-commit at gcc dot gnu.org @ 2024-05-02 11:34 ` rguenth at gcc dot gnu.org 3 siblings, 0 replies; 5+ messages in thread From: rguenth at gcc dot gnu.org @ 2024-05-02 11:34 UTC (permalink / raw) To: gcc-bugs https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114579 Richard Biener <rguenth at gcc dot gnu.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Target Milestone|--- |15.0 Resolution|--- |FIXED Status|NEW |RESOLVED --- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> --- Fixed for GCC 15, I don't have a testcase that's slow here anymore. ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2024-05-02 11:34 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2024-04-04 8:54 [Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow rguenth at gcc dot gnu.org 2024-04-04 9:52 ` [Bug middle-end/114579] " rguenth at gcc dot gnu.org 2024-04-05 18:44 ` pinskia at gcc dot gnu.org 2024-05-02 6:32 ` cvs-commit at gcc dot gnu.org 2024-05-02 11:34 ` rguenth at gcc dot gnu.org
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).