[Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow

[Bug middle-end/114579] New: RTL expansion add_scope_conflicts is slow

[rguenth at gcc dot gnu.org]

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.

[Bug middle-end/114579] RTL expansion add_scope_conflicts is slow

[rguenth at gcc dot gnu.org]

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.

[Bug middle-end/114579] RTL expansion add_scope_conflicts is slow

[pinskia at gcc dot gnu.org]

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.

[Bug middle-end/114579] RTL expansion add_scope_conflicts is slow

[cvs-commit at gcc dot gnu.org]

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.

[Bug middle-end/114579] RTL expansion add_scope_conflicts is slow

[rguenth at gcc dot gnu.org]

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.