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

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.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.