[Bug target/104686] New: [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[Bug target/104686] New: [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

            Bug ID: 104686
           Summary: [12 Regression] Huge compile-time regression building
                    SPEC 2017 538.imagick_r with -march=skylake
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

We see a recent compile-time regression on 538.imagick_r for intel
architectures
(not reproducible with -march=znver2):

https://lnt.opensuse.org/db_default/v4/SPEC/graph?plot.0=32.507.8

it happens on the magick/enhance.c file when building with -Ofast
-march=skylake

I will attach preprocessed source.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64-*-*
   Target Milestone|---                         |12.0
           Keywords|                            |compile-time-hog,
                   |                            |needs-bisection

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 52514
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52514&action=edit
preprocessed source

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ra

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Samples: 204K of event 'cycles', Event count (approx.): 222925904390            
Overhead       Samples  Command  Shared Object                     Symbol       
  92.53%        189096  cc1      cc1                               [.]
update_conflict_hard_regno_costs  #
   0.51%          1043  cc1      cc1                               [.]
build_object_conflicts

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marxin at gcc dot gnu.org

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
I see 2 regressions:

1) r12-7246-g4963079769c99c40
5.77s -> 35.56s

and then:

2) r12-7319-g90d693bdc9d71841

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #4 from Martin Liška <marxin at gcc dot gnu.org> ---
> 
> 2) r12-7319-g90d693bdc9d71841

to 57s

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
Created attachment 52515
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52515&action=edit
Partially reduced test-case

For the test-case I get:

Bisecting latest revisions
  a9e2ebe839d56416(24 Feb 2022 22:16)(oliva@adacore.com): [took: 16.38 s]
result: OK
  250f234988b62316(20 Apr 2021 09:51)(stefansf@linux.ibm.com): [took: 1.75 s]
result: OK

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Both revisions affect vectorizer cost modeling only.  With -fno-vect-cost-model
it compiles faster for me but still a slow 30s and 91% in RA.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #7 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #6)
> Both revisions affect vectorizer cost modeling only.  With
> -fno-vect-cost-model it compiles faster for me but still a slow 30s and 91%
> in RA.

There are numbers with -fno-vect-cost-model:

Bisecting latest revisions
  a9e2ebe839d56416(24 Feb 2022 22:16)(oliva@adacore.com): [took: 36.06 s]
result: OK
  250f234988b62316(20 Apr 2021 09:51)(stefansf@linux.ibm.com): [took: 18.35 s]
result: OK

I'm going to find out where the change happensed.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |crazylht at gmail dot com

--- Comment #8 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #7)
> (In reply to Richard Biener from comment #6)
> > Both revisions affect vectorizer cost modeling only.  With
> > -fno-vect-cost-model it compiles faster for me but still a slow 30s and 91%
> > in RA.
> 
> There are numbers with -fno-vect-cost-model:
> 
> Bisecting latest revisions
>   a9e2ebe839d56416(24 Feb 2022 22:16)(oliva@adacore.com): [took: 36.06 s]
> result: OK
>   250f234988b62316(20 Apr 2021 09:51)(stefansf@linux.ibm.com): [took: 18.35
> s] result: OK
> 
> I'm going to find out where the change happensed.

Which started with r12-2463-ga6291d88d5b6c17d.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vmakarov at gcc dot gnu.org

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #8)
> (In reply to Martin Liška from comment #7)
> > (In reply to Richard Biener from comment #6)
> > > Both revisions affect vectorizer cost modeling only.  With
> > > -fno-vect-cost-model it compiles faster for me but still a slow 30s and 91%
> > > in RA.
> > 
> > There are numbers with -fno-vect-cost-model:
> > 
> > Bisecting latest revisions
> >   a9e2ebe839d56416(24 Feb 2022 22:16)(oliva@adacore.com): [took: 36.06 s]
> > result: OK
> >   250f234988b62316(20 Apr 2021 09:51)(stefansf@linux.ibm.com): [took: 18.35
> > s] result: OK
> > 
> > I'm going to find out where the change happensed.
> 
> Which started with r12-2463-ga6291d88d5b6c17d.

I think you want to keep r12-7293 in the tree - the above introduced a huge
regression that was already fixed.  So this testcase was probably always
slow to compile and spending all time in RA?

When using callgrind on the reduced testcase and a -O0 compiler
I see most time spent in ira_object_conflict_iter_cond, in particular
the loop

      /* Skip bits that are zero.  */
      for (; (word & 1) == 0; word >>= 1)
        bit_num++;

and the load

      obj = ira_object_id_map[bit_num + i->base_conflict_id];

maybe we can use ctz_hwi here (hopefully we optimize this loop with -O2).

This function is most called from allocnos_conflict_p which is called
from update_conflict_hard_regno_costs.

In particular we have 677544 calls to get_next_upate_cost () and
1824339 calls to allocnos_conflict () there from just 34480 calls
to update_conflict_hard_regno_costs.  queue_update_cost is called
1365947 times.

Maybe we can improve things or at least cut things off with decreasing
precision somehow?  Vlad?

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
diff --git a/gcc/ira-int.h b/gcc/ira-int.h
index 957604b22e9..7465af72e98 100644
--- a/gcc/ira-int.h
+++ b/gcc/ira-int.h
@@ -1379,8 +1379,9 @@ ira_object_conflict_iter_cond
(ira_object_conflict_iterator *i,
        }

       /* Skip bits that are zero.  */
-      for (; (word & 1) == 0; word >>= 1)
-       bit_num++;
+      int off = ctz_hwi (word);
+      bit_num += off;
+      word >>= off;

       obj = ira_object_id_map[bit_num + i->base_conflict_id];
       i->bit_num = bit_num + 1;


improves compile-time from 31s to 24s for the full preprocessed source with
-fno-vect-cost-model.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[crazylht at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #11 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Martin Liška from comment #8)
> (In reply to Martin Liška from comment #7)
> > (In reply to Richard Biener from comment #6)
> > > Both revisions affect vectorizer cost modeling only.  With
> > > -fno-vect-cost-model it compiles faster for me but still a slow 30s and 91%
> > > in RA.
> > 
> > There are numbers with -fno-vect-cost-model:
> > 
> > Bisecting latest revisions
> >   a9e2ebe839d56416(24 Feb 2022 22:16)(oliva@adacore.com): [took: 36.06 s]
> > result: OK
> >   250f234988b62316(20 Apr 2021 09:51)(stefansf@linux.ibm.com): [took: 18.35
> > s] result: OK
> > 
> > I'm going to find out where the change happensed.
> 
> Which started with r12-2463-ga6291d88d5b6c17d.

Wonder if it's related to hard register usage in pass_expand
op1 = ix86_gen_scratch_sse_rtx (mode);

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[crazylht at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #12 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Hongtao.liu from comment #11)
> (In reply to Martin Liška from comment #8)
> > (In reply to Martin Liška from comment #7)
> > > (In reply to Richard Biener from comment #6)
> > > > Both revisions affect vectorizer cost modeling only.  With
> > > > -fno-vect-cost-model it compiles faster for me but still a slow 30s and 91%
> > > > in RA.
> > > 
> > > There are numbers with -fno-vect-cost-model:
> > > 
> > > Bisecting latest revisions
> > >   a9e2ebe839d56416(24 Feb 2022 22:16)(oliva@adacore.com): [took: 36.06 s]
> > > result: OK
> > >   250f234988b62316(20 Apr 2021 09:51)(stefansf@linux.ibm.com): [took: 18.35
> > > s] result: OK
> > > 
> > > I'm going to find out where the change happensed.
> > 
> > Which started with r12-2463-ga6291d88d5b6c17d.
> 
> Wonder if it's related to hard register usage in pass_expand
in ix86_expand_vector_move which will be called by emit_move_insn.
> op1 = ix86_gen_scratch_sse_rtx (mode);

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #13 from CVS 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:a8250bbaeb2e8250c20db477fe67fd085214be7c

commit r12-7401-ga8250bbaeb2e8250c20db477fe67fd085214be7c
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Feb 25 14:19:44 2022 +0100

    rtl-optimization/104686 - speed up conflict iteration

    The following replaces

           /* Skip bits that are zero.  */
           for (; (word & 1) == 0; word >>= 1)
             bit_num++;

    idioms in ira-int.h in the attempt to speedup
update_conflict_hard_regno_costs
    which we're bound on in PR104686.  The trick is to use ctz_hwi here
    which should pay off even with dense bitmaps on architectures that
    have HW support for this.

    For the PR in question this speeds up compile-time from 31s to 24s for
    me.

    2022-02-25  Richard Biener  <rguenther@suse.de>

            PR rtl-optimization/104686
            * ira-int.h (minmax_set_iter_cond): Use ctz_hwi to elide loop
            skipping bits that are zero.
            (ira_object_conflict_iter_cond): Likewise.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
The pushed change is a micro-optimization not really addressing the underlying
issue which needs more analysis.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-03-01
             Status|UNCONFIRMED                 |NEW

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
So we have a lot of allocnos and do

      Popping a2027(r13053,l1)  --         assign reg 46
      Popping a2217(r12829,l1)  --         assign reg 46
      Popping a2407(r12603,l1)  --         assign reg 45
      Popping a2015(r162,l1)  --         assign reg 48
...

thus pop_allocnos_from_stack () which will eventually call
assign_hard_reg (allocno, false) which then calls
update_conflict_hard_regno_costs twice for the ALLOCNO_CLASS.

I wonder if it makes sense to pop allocnos of the same class w/o updating
the hard regno cost and do the update only after each such group.

I know nothing about IRA but

diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
index 8b6db1bb417..3a531c0e537 100644
--- a/gcc/ira-color.cc
+++ b/gcc/ira-color.cc
@@ -2905,7 +2905,11 @@ pop_allocnos_from_stack (void)
          if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
            fprintf (ira_dump_file, "assign memory\n");
        }
-      else if (assign_hard_reg (allocno, false))
+      else if (assign_hard_reg (allocno,
+                               allocno_stack_vec.is_empty ()
+                               || (ALLOCNO_CLASS (allocno_stack_vec.last ())
+                                   != aclass)
+                               ? false : true))
        {
          if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
            fprintf (ira_dump_file, "        assign reg %d\n",

speeds up compilation (with -O0 cc1) to

 integrated RA                      :   5.27 ( 29%)   0.27 ( 13%)   5.67 ( 28%)
 3429k ( 11%)
 TOTAL                              :  18.26          2.02         20.52       
   31M

from

 integrated RA                      :  74.11 ( 94%)   0.02 ( 29%)  74.67 ( 94%)
 3429k ( 11%)
 TOTAL                              :  78.73          0.07         79.39       
   31M

on the partially reduced testcase.

Maybe that's too aggressive of course.  From the dump we also see we
assign the same hardreg to adjacent popped allocnos so maybe that's
another way to "group" the cost adjustments:

      Popping a20939(r7366,l0: a16841(r7366,l1: a8854(r7366,l2)))  --        
assign reg 50
      Popping a20951(r7347,l0: a16853(r7347,l1: a8866(r7347,l2)))  --        
assign reg 50
...  172 times assigning reg 50
      Popping a21383(r6857,l0: a17285(r6857,l1: a9298(r6857,l2)))  --        
assign reg 50

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
it doesn't make a difference for this testcase but profiling shows that
allocnos_conflict_p is quite expensive so it's best to do it after the other
continue checks like the following.  I also notice that the comment of
allocnos_conflict_p says

/* Return TRUE if allocnos A1 and A2 conflicts. Here we are
   interesting only in conflicts of allocnos with intersected allocno
   classes. */

so doing it after the ira_reg_classes_intersect_p check makes even more
sense(?)

diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
index 8b6db1bb417..a5fd79484eb 100644
--- a/gcc/ira-color.cc
+++ b/gcc/ira-color.cc
@@ -1572,15 +1572,14 @@ update_conflict_hard_regno_costs (int *costs, enum
reg_class aclass,
        else
          gcc_unreachable ();

+       another_aclass = ALLOCNO_CLASS (another_allocno);
        if (another_allocno == from
+           || ALLOCNO_ASSIGNED_P (another_allocno)
+           || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p
+           || ! ira_reg_classes_intersect_p[aclass][another_aclass]
            || allocnos_conflict_p (another_allocno, start))
          continue;

-       another_aclass = ALLOCNO_CLASS (another_allocno);
-       if (! ira_reg_classes_intersect_p[aclass][another_aclass]
-           || ALLOCNO_ASSIGNED_P (another_allocno)
-           || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
-         continue;
        class_size = ira_class_hard_regs_num[another_aclass];
        ira_allocate_and_copy_costs
          (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),


Now, what's more odd is that we sometimes have a nice bitmap representation
for the conflicts but we always iterate.  So it _seems_ we should be able
to do sth like

diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
index 8b6db1bb417..682d1ef7562 100644
--- a/gcc/ira-color.cc
+++ b/gcc/ira-color.cc
@@ -1352,9 +1352,23 @@ allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
     {
       obj = ALLOCNO_OBJECT (a1, word);
       /* Take preferences of conflicting allocnos into account.  */
-      FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
-       if (OBJECT_ALLOCNO (conflict_obj) == a2)
-         return true;
+      if  (!OBJECT_CONFLICT_VEC_P (obj))
+       {
+         for (int w2 = 0; w2 < ALLOCNO_NUM_OBJECTS (a2); w2++)
+           {
+             ira_object_t obj2 = ALLOCNO_OBJECT (a2, w2);
+             if (OBJECT_CONFLICT_ID (obj2) >= OBJECT_MIN (obj)
+                 && OBJECT_CONFLICT_ID (obj2) <= OBJECT_MAX (obj)
+                 && TEST_MINMAX_SET_BIT (OBJECT_CONFLICT_BITVEC (obj),
+                                         OBJECT_CONFLICT_ID (obj2),
+                                         OBJECT_MIN (obj), OBJECT_MAX (obj)))
+               return true;
+           }
+       }
+      else
+       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
+         if (OBJECT_ALLOCNO (conflict_obj) == a2)
+           return true;
     }
   return false;
 }  

which reduces compile-time from 10s to 1s for me ... the above should
be split out so we can "optimally" use the bit test for
object vs. allocno when possible.

Vlad - any thoughts about the above two things?  Shall I try to polish and
optimize the bit test or would you be willing to pick those two speedups up?

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #17 from Richard Biener <rguenth at gcc dot gnu.org> ---
For OBJECT_CONFLICT_VEC_P it might be possible to add a bit to ira_object
indicating on whether the conflict array is sorted and if not, sort it
in allocnos_conflict_p so we can use a binary search there.  Not sure
if always maintaining a sorted array is easy (I only found add_to_conflicts
that would change conflicts, dependent on how often we call it doing
sorted insertion might be prohibitive).

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #18 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #16)
> it doesn't make a difference for this testcase but profiling shows that
> allocnos_conflict_p is quite expensive so it's best to do it after the other
> continue checks like the following.  I also notice that the comment of
> allocnos_conflict_p says
> 
> /* Return TRUE if allocnos A1 and A2 conflicts. Here we are
>    interesting only in conflicts of allocnos with intersected allocno
>    classes. */
> 
> so doing it after the ira_reg_classes_intersect_p check makes even more
> sense(?)
> 
> diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
> index 8b6db1bb417..a5fd79484eb 100644
> --- a/gcc/ira-color.cc
> +++ b/gcc/ira-color.cc
> @@ -1572,15 +1572,14 @@ update_conflict_hard_regno_costs (int *costs, enum
> reg_class aclass,
>         else
>           gcc_unreachable ();
>  
> +       another_aclass = ALLOCNO_CLASS (another_allocno);
>         if (another_allocno == from
> +           || ALLOCNO_ASSIGNED_P (another_allocno)
> +           || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p
> +           || ! ira_reg_classes_intersect_p[aclass][another_aclass]
>             || allocnos_conflict_p (another_allocno, start))
>           continue;
>  
> -       another_aclass = ALLOCNO_CLASS (another_allocno);
> -       if (! ira_reg_classes_intersect_p[aclass][another_aclass]
> -           || ALLOCNO_ASSIGNED_P (another_allocno)
> -           || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
> -         continue;
>         class_size = ira_class_hard_regs_num[another_aclass];
>         ira_allocate_and_copy_costs
>           (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
> 
> 
> Now, what's more odd is that we sometimes have a nice bitmap representation
> for the conflicts but we always iterate.  So it _seems_ we should be able
> to do sth like
> 
> diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
> index 8b6db1bb417..682d1ef7562 100644
> --- a/gcc/ira-color.cc
> +++ b/gcc/ira-color.cc
> @@ -1352,9 +1352,23 @@ allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t
> a2)
>      {
>        obj = ALLOCNO_OBJECT (a1, word);
>        /* Take preferences of conflicting allocnos into account.  */
> -      FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
> -       if (OBJECT_ALLOCNO (conflict_obj) == a2)
> -         return true;
> +      if  (!OBJECT_CONFLICT_VEC_P (obj))
> +       {
> +         for (int w2 = 0; w2 < ALLOCNO_NUM_OBJECTS (a2); w2++)
> +           {
> +             ira_object_t obj2 = ALLOCNO_OBJECT (a2, w2);
> +             if (OBJECT_CONFLICT_ID (obj2) >= OBJECT_MIN (obj)
> +                 && OBJECT_CONFLICT_ID (obj2) <= OBJECT_MAX (obj)
> +                 && TEST_MINMAX_SET_BIT (OBJECT_CONFLICT_BITVEC (obj),
> +                                         OBJECT_CONFLICT_ID (obj2),
> +                                         OBJECT_MIN (obj), OBJECT_MAX
> (obj)))
> +               return true;
> +           }
> +       }
> +      else
> +       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
> +         if (OBJECT_ALLOCNO (conflict_obj) == a2)
> +           return true;
>      }
>    return false;
>  }  
> 
> which reduces compile-time from 10s to 1s for me ... the above should
> be split out so we can "optimally" use the bit test for
> object vs. allocno when possible.
> 
> Vlad - any thoughts about the above two things?  Shall I try to polish and
> optimize the bit test or would you be willing to pick those two speedups up?

Bootstrapped / tested ok on x86_64-unknown-linux-gnu.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[vmakarov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #19 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #16)
> it doesn't make a difference for this testcase but profiling shows that
> allocnos_conflict_p is quite expensive so it's best to do it after the other
> continue checks like the following.  I also notice that the comment of
> allocnos_conflict_p says
> 
> /* Return TRUE if allocnos A1 and A2 conflicts. Here we are
>    interesting only in conflicts of allocnos with intersected allocno
>    classes. */
> 
> so doing it after the ira_reg_classes_intersect_p check makes even more
> sense(?)
> 
> diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
> index 8b6db1bb417..a5fd79484eb 100644
> --- a/gcc/ira-color.cc
> +++ b/gcc/ira-color.cc
> @@ -1572,15 +1572,14 @@ update_conflict_hard_regno_costs (int *costs, enum
> reg_class aclass,
>         else
>           gcc_unreachable ();
>  
> +       another_aclass = ALLOCNO_CLASS (another_allocno);
>         if (another_allocno == from
> +           || ALLOCNO_ASSIGNED_P (another_allocno)
> +           || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p
> +           || ! ira_reg_classes_intersect_p[aclass][another_aclass]
>             || allocnos_conflict_p (another_allocno, start))
>           continue;
>  
> -       another_aclass = ALLOCNO_CLASS (another_allocno);
> -       if (! ira_reg_classes_intersect_p[aclass][another_aclass]
> -           || ALLOCNO_ASSIGNED_P (another_allocno)
> -           || ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p)
> -         continue;
>         class_size = ira_class_hard_regs_num[another_aclass];
>         ira_allocate_and_copy_costs
>           (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
> 
> 

If it is allocnos_conflict_p takes significant time, this change definitely has
sense.  On my estimation it will decrease allocnos_conflict_p calls in about 4
times (assuming fp and int reg classes and half allocnos already assigned).

In any case, the above change is profitable as allocnos_conflict_p practically
always takes more time than the condition tests moved up.

> Now, what's more odd is that we sometimes have a nice bitmap representation
> for the conflicts but we always iterate.  So it _seems_ we should be able
> to do sth like
> 
> diff --git a/gcc/ira-color.cc b/gcc/ira-color.cc
> index 8b6db1bb417..682d1ef7562 100644
> --- a/gcc/ira-color.cc
> +++ b/gcc/ira-color.cc
> @@ -1352,9 +1352,23 @@ allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t
> a2)
>      {
>        obj = ALLOCNO_OBJECT (a1, word);
>        /* Take preferences of conflicting allocnos into account.  */
> -      FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
> -       if (OBJECT_ALLOCNO (conflict_obj) == a2)
> -         return true;
> +      if  (!OBJECT_CONFLICT_VEC_P (obj))
> +       {
> +         for (int w2 = 0; w2 < ALLOCNO_NUM_OBJECTS (a2); w2++)
> +           {
> +             ira_object_t obj2 = ALLOCNO_OBJECT (a2, w2);
> +             if (OBJECT_CONFLICT_ID (obj2) >= OBJECT_MIN (obj)
> +                 && OBJECT_CONFLICT_ID (obj2) <= OBJECT_MAX (obj)
> +                 && TEST_MINMAX_SET_BIT (OBJECT_CONFLICT_BITVEC (obj),
> +                                         OBJECT_CONFLICT_ID (obj2),
> +                                         OBJECT_MIN (obj), OBJECT_MAX
> (obj)))
> +               return true;
> +           }
> +       }
> +      else
> +       FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
> +         if (OBJECT_ALLOCNO (conflict_obj) == a2)
> +           return true;
>      }
>    return false;
>  }  
> 
> which reduces compile-time from 10s to 1s for me ... the above should
> be split out so we can "optimally" use the bit test for
> object vs. allocno when possible.
> 
> Vlad - any thoughts about the above two things?  Shall I try to polish and
> optimize the bit test or would you be willing to pick those two speedups up?

This change also has sense.  Usually for big functions conflict sets are very
sparse and bit vectors are not used.  But it seems this is not the case for the
PR.

Please, polish and optimize the change as you proposed and I approve the final
version promptly.

Thank you for working on this PR, Richard.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #20 from Richard Biener <rguenth at gcc dot gnu.org> ---
Testing the final patch.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

--- Comment #21 from CVS 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:8fede2876a751d53a28442dcca32466daa929daa

commit r12-7451-g8fede2876a751d53a28442dcca32466daa929daa
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Mar 2 08:55:58 2022 +0100

    rtl-optimization/104686 - speedup IRA allocno conflict test

    In this PR allocnos_conflict_p takes 90% of the compile-time via
    the calls from update_conflict_hard_regno_costs.  This is due to
    the high number of conflicts recorded in the dense bitvector
    representation.  Fortunately we can take advantage of the bitvector
    representation here and turn the O(n) conflict test into an O(1) one,
    greatly speeding up the compile of the testcase from 39s to just 4s
    (93% IRA time to 26% IRA time).

    While for the testcase in question the first allocno is almost always
    the nice one the patch tries a more systematic approach to finding
    the allocno to iterate object conflicts over.  That does reduce
    the actual number of compares for the testcase but it doesn't make
    a measurable difference wall-clock wise.  That's not guaranteed
    though I think so I've kept this systematic way of choosing the
    cheapest allocno.

    2022-03-02  Richard Biener  <rguenther@suse.de>

            PR rtl-optimization/104686
            * ira-color.cc (object_conflicts_with_allocno_p): New function
            using a bitvector test instead of iterating when possible.
            (allocnos_conflict_p): Choose the best allocno to iterate over
            object conflicts.
            (update_conflict_hard_regno_costs): Do allocnos_conflict_p test
            last.

[Bug target/104686] [12 Regression] Huge compile-time regression building SPEC 2017 538.imagick_r with -march=skylake

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104686

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #22 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.  The issue at hand is of course old and the identified revs triggered it
(whether they do sth "bad" or not).