[Bug c++/97623] New: Extremely slow O2 compile (>>O(n^2))

[Bug c++/97623] New: Extremely slow O2 compile (>>O(n^2))

[wsnyder at wsnyder dot org]

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

            Bug ID: 97623
           Summary: Extremely slow O2 compile (>>O(n^2))
           Product: gcc
           Version: 9.3.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: wsnyder at wsnyder dot org
  Target Milestone: ---

Created attachment 49461
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49461&action=edit
slow.cpp

The attached program compiles very slowly with -O2.  It is fast with clang
(FWIW).

This is an shortened version of a routine taking > 10 minutes.

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

time g++ -O2 -c slow.cpp
 6.457  (average)
time g++ -Os -c slow.cpp
 0.236  (average)
time g++ -O2 -DNO_BOTTOM -c slow.cpp
 0.560  (average)
time g++ -O2 -DNO_TOP -c slow.cpp
 0.702  (average)
time g++ -O2 -DNO_FINAL -c slow.cpp
 6.271  (average)
time clang++ -O2 -c slow.cpp
 0.210  (average)

Note Os is much faster.  The defines remove the top half of the function, or
bottom half, note the time is crazy faster, one would expect the whole program
to be only slightly slower than the sum of these.  Removing a single statement
from the bottom (-DNO_FINAL) also makes an enormous 0.21 second difference, so
some algorithm is not scaling correctly.

Would greatly appreciate some indication of 1. a compiler flag to bypass the
bad optimization if possible, and 2. a hint as to what operator or how to avoid
this as this is generated code so there's some flexibility for a workaround.

Thanks.

[Bug c++/97623] Extremely slow O2 compile (>>O(n^2))

[wsnyder at wsnyder dot org]

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

--- Comment #1 from Wilson Snyder <wsnyder at wsnyder dot org> ---
P.S. Note gcc -v and related information are comments at top of the attachment.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
            Summary|Extremely slow O2 compile   |[9/10/11 Regression]
                   |(>>O(n^2))                  |Extremely slow O2 compile
                   |                            |(>>O(n^2))
      Known to work|                            |7.5.0
          Component|middle-end                  |tree-optimization
   Last reconfirmed|                            |2020-10-29

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
 tree PRE                           :   6.83 ( 96%)   0.02 ( 50%)   6.90 ( 96%)
  11764 kB ( 37%)

Confirmed.

insert iterations == 187: 1
RPO blocks: 843
RPO iterations == 10: 1
compute_antic iterations == 2: 1
RPO blocks visited: 843
New PHIs: 15021
RPO num values == 7009: 1
Insertions: 23846
RPO max_rpo iterations == 0: 1
RPO blocks executable: 843
RPO block visited times == 1: 843
HOIST inserted: 13098
RPO num lattice == 7009: 1
RPO num avail == 6755: 1
Symbol to SSA rewrite: 1
Eliminated: 27807

So the number of insert iterations is troubling.

Now the testcase is a bit big to analyze what's going on there, we seem
to need about 2 insert iterations for each of the statements.

It looks like the statements are 1:1 copies besides sometimes changing
the constant index into the tbt__rvtop__swerv__ifu__bp__bht_bank_wr_data
array?

I will have a closer look.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 49462
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49462&action=edit
modified testcase

Moved the #defines, with -DNO_TOP -DNO_BOTTOM -DNO_FINAL there's now 5 insert
iterations instead of the usually expected two.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, so we have PRE and hoist insertion exposing new opportunities to each
other, making things tickle up the CFG.  Then, the way hoist insertion works
it would be better suited to a bottom-up walk since hoist inserts may
expose new hoist candidates - but a bottom-up walk makes updating AVAIL_OUT
sets harder.

The following pattern requires N hoist insert iterations for example:

void baz();
int tem;
void foo (int a, int b, int c, int d, int e, int x, int y)
{
  if (a)
    {
      if (b)
        {
          if (c)
            {
              tem = x + y;
            }
          else
            {
              if (d) baz ();
              tem = x + y;
            }
        }
      else
        {
          if (d) baz ();
          tem = x + y;
        }
    }
  else
    {
      if (d) baz ();
      tem = x + y;
    }
}

now, due to PRE insertion and hoist insertion going in different directions
the cascading cannot be avoided in general.  But I think we can improve
things by first doing hoist insertion backwards (no need to propagate
NEW sets there) and then doing PRE insertion forward, propagating NEW
sets on the fly.  That makes the above testcase take 2 iterations
and your original testcase "only" 94.  As said, the back-to-back cannot
really be avoided but the wrong order hoist insertion can be fixed.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |9.4
           Priority|P3                          |P2

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 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:82ff7e3426ea926d090777173977f8bedd086816

commit r11-4570-g82ff7e3426ea926d090777173977f8bedd086816
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 30 13:32:32 2020 +0100

    tree-optimization/97623 - avoid excessive insert iteration for hoisting

    This avoids requiring insert iteration for back-to-back hoisting
    opportunities as seen in the added testcase.  For the PR at hand
    this halves the number of insert iterations retaining only
    the hard to avoid PRE / hoist insert back-to-backs.

    2020-10-30  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/97623
            * tree-ssa-pre.c (insert): First do hoist insertion in
            a backward walk.

            * gcc.dg/tree-ssa/ssa-hoist-7.c: New testcase.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
So this is the change improving the hoist insert situation but it is not a
solution for the back-to-back of PRE vs. hoist insertion.  Will have to think
about this some more and then eventually simply add some iteration limit - we
can stop after any arbitrary number of iterations after all, the cost is just
less optimization.

As a workaround for older code bases I suggest to use -fno-code-hoisting for
now.

If you are set up to try current trunk GCC then I'd be curious to know the
effect of the patch on the "real" case.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[wsnyder at wsnyder dot org]

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

--- Comment #7 from Wilson Snyder <wsnyder at wsnyder dot org> ---
Thanks for the quick service.  I can't easily try GCC trunk, but:

-O2
  compile 98.61s
  runtime 25.76s

-O2 -fno-code-hoisting
  compile 40.13s
  runtime 26.40s (+2.5%)

-Os
  compile 4.25s
  runtime 23.42s (-10%)

That -Os runs faster is expected as this program is generally instruction-fetch
limited.  I'd have expected -fno-code-hoisting to help more, compile time wise.

Am I correct in understanding that the slowdown is roughly correlated to the
number of "if" or "?:" statements?

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Wilson Snyder from comment #7)
> Thanks for the quick service.  I can't easily try GCC trunk, but:
> 
> -O2
>   compile 98.61s
>   runtime 25.76s
> 
> -O2 -fno-code-hoisting
>   compile 40.13s
>   runtime 26.40s (+2.5%)

Hmm, OK.  Can you provide the output of -O2 -fno-code-hoisting -ftime-report?

I have a patch limiting hoist insertions to 3 and that makes the reduced
testcase drop from 13s to 2.5s and drop PRE into reasonable territory:

 tree PRE                           :   0.44 ( 18%)   0.00 (  0%)   0.45 ( 18%)
 1177k (  5%)

and with -fno-code-hoisting

 tree PRE                           :   0.37 ( 15%)   0.00 (  0%)   0.38 ( 15%)
  477k (  2%)

where it takes only two insert iterations (the last iteration is always
a no-op, so that's perfect).  Before limiting but after the already
committed patch it was

 tree PRE                           :  10.41 ( 81%)   0.01 ( 33%)  10.48 ( 81%)
   11M ( 33%)

The function is quite big and ANTIC_IN compute is costly and more
importantly AVAIL_OUT is quadratic in size (ugh).

> -Os
>   compile 4.25s
>   runtime 23.42s (-10%)
> 
> That -Os runs faster is expected as this program is generally
> instruction-fetch limited.  I'd have expected -fno-code-hoisting to help
> more, compile time wise.

Me, too.

> Am I correct in understanding that the slowdown is roughly correlated to the
> number of "if" or "?:" statements?

Yeah, that's the case.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 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:c5b49c3e092c0de5cd684b0acd244129dfaae324

commit r11-4675-gc5b49c3e092c0de5cd684b0acd244129dfaae324
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Nov 3 15:03:41 2020 +0100

    tree-optimization/97623 - limit PRE hoist insertion

    This limits insert iteration caused by PRE insertions generating
    hoist insertion opportunities and vice versa.  The patch limits
    the hoist insertion iterations to three by default.

    2020-11-03  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/97623
            * params.opt (-param=max-pre-hoist-insert-iterations): New.
            * doc/invoke.texi (max-pre-hoist-insert-iterations): Document.
            * tree-ssa-pre.c (insert): Do at most
max-pre-hoist-insert-iterations
            hoist insert iterations.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[wsnyder at wsnyder dot org]

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

--- Comment #10 from Wilson Snyder <wsnyder at wsnyder dot org> ---
Running -O2 -fno-code-hoisting -ftime-report

and I deleted the 0%/0%/0% lines:

Time variable                                   usr           sys          wall
              GGC
 phase parsing                      :   0.34 (  1%)   0.18 ( 67%)   0.52 (  1%)
  75469 kB ( 46%)
 phase lang. deferred               :   0.02 (  0%)   0.01 (  4%)   0.02 (  0%)
   3473 kB (  2%)
 phase opt and generate             :  38.01 ( 99%)   0.08 ( 30%)  38.12 ( 99%)
  85265 kB ( 51%)
 |name lookup                       :   0.06 (  0%)   0.02 (  7%)   0.10 (  0%)
   3222 kB (  2%)
 |overload resolution               :   0.02 (  0%)   0.01 (  4%)   0.03 (  0%)
   3886 kB (  2%)
 alias stmt walking                 :   0.27 (  1%)   0.00 (  0%)   0.34 (  1%)
      1 kB (  0%)
 preprocessing                      :   0.05 (  0%)   0.06 ( 22%)   0.07 (  0%)
   6448 kB (  4%)
 parser (global)                    :   0.04 (  0%)   0.04 ( 15%)   0.12 (  0%)
  29550 kB ( 18%)
 parser struct body                 :   0.03 (  0%)   0.02 (  7%)   0.10 (  0%)
  10609 kB (  6%)
 parser function body               :   0.08 (  0%)   0.02 (  7%)   0.09 (  0%)
  12779 kB (  8%)
 parser inl. func. body             :   0.02 (  0%)   0.03 ( 11%)   0.06 (  0%)
   3940 kB (  2%)
 parser inl. meth. body             :   0.05 (  0%)   0.01 (  4%)   0.05 (  0%)
   4949 kB (  3%)
 template instantiation             :   0.09 (  0%)   0.01 (  4%)   0.04 (  0%)
  10514 kB (  6%)
 tree SSA incremental               :   0.01 (  0%)   0.01 (  4%)   0.02 (  0%)
   6465 kB (  4%)
 tree operand scan                  :   0.00 (  0%)   0.01 (  4%)   0.01 (  0%)
   1875 kB (  1%)
 tree PRE                           :  36.36 ( 95%)   0.05 ( 19%)  36.34 ( 94%)
  32604 kB ( 20%)
 out of ssa                         :   0.17 (  0%)   0.00 (  0%)   0.17 (  0%)
      0 kB (  0%)
 combiner                           :   0.16 (  0%)   0.00 (  0%)   0.16 (  0%)
  11911 kB (  7%)
 integrated RA                      :   0.11 (  0%)   0.00 (  0%)   0.12 (  0%)
   4562 kB (  3%)
 initialize rtl                     :   0.00 (  0%)   0.01 (  4%)   0.00 (  0%)
     12 kB (  0%)
 TOTAL                              :  38.37          0.27         38.67       
 165692 kB

real    0m38.707s
user    0m38.398s
sys     0m0.292s

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenther at suse dot de]

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

--- Comment #11 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 6 Nov 2020, wsnyder at wsnyder dot org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97623
> 
> --- Comment #10 from Wilson Snyder <wsnyder at wsnyder dot org> ---
> Running -O2 -fno-code-hoisting -ftime-report
> 
> and I deleted the 0%/0%/0% lines:
> 
> Time variable                                   usr           sys          wall
>               GGC
>  tree PRE                           :  36.36 ( 95%)   0.05 ( 19%)  36.34 ( 94%)
>   32604 kB ( 20%)

OK, that's still all PRE :/  Can you share the full testcase somehow?

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[wsnyder at wsnyder dot org]

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

--- Comment #12 from Wilson Snyder <wsnyder at wsnyder dot org> ---
Created attachment 49515
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49515&action=edit
Larger testcase

Attached is the larger testcase.

 time g++  -O2 -c -o Vtb_top__3_ii.o Vtb_top__3_ii.cpp
 user    1m38.456s

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |needs-bisection

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, on that testcase the good news is that GCC 10 is much better than GCC 9
resulting in -O2 -fno-code-hoisting

 tree PRE                           :   2.25 ( 50%)   0.05 ( 20%)   2.32 ( 49%)
  31794 kB ( 20%)
 TOTAL                              :   4.47          0.25          4.72       
 161356 kB

compared to GCC 9 where I can indeed reproduce

 tree PRE                           :  37.81 ( 95%)   0.04 ( 13%)  37.96 ( 95%)
  32604 kB ( 20%)
 TOTAL                              :  39.63          0.30         39.99       
 161584 kB

suspicious are diffs in insertions and insert iterations:

Insertions: 1258
insert iterations == 3: 1
Eliminated: 1553

vs bad:

Insertions: 8616
insert iterations == 128: 1
Eliminated: 8955

I wonder what triggered this change ...

On patched trunk we're in the same ballpark as GCC 10 but without requiring
-fno-code-hoisting.  The testcase is still an interesting one for PRE
(50% of the compile spent there is a bit much, even if just 2 seconds).

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |

--- Comment #14 from Martin Liška <marxin at gcc dot gnu.org> ---
With -O2 -fno-code-hoisting it's fixed since r10-300-gaae6da83564549a6.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
OK, noting down low-hanging optimization fruits:

- phi-translation caching uses a hash with needless indirection, XNEW-ing
  expr_pred_trans_d
- old issue, value_id_constant_p is expensive - better would be to make
  those negative, requires separate value_expressions array for constants
- sorted_array_from_bitmap_set could be cached at least for sorting of
  ANTIC_IN during insertion since that doesn't change (helps when iterating),
  and we could remove (zero) entries we already inserted to avoid repeated
  work

going to work on a few of those.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #14)
> With -O2 -fno-code-hoisting it's fixed since r10-300-gaae6da83564549a6.

Ah, that makes sense.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[cvs-commit at gcc dot gnu.org]

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

--- Comment #17 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:bd87cc14ebdb6789e067fb1828d5808407c308b3

commit r11-4913-gbd87cc14ebdb6789e067fb1828d5808407c308b3
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Nov 11 11:51:59 2020 +0100

    tree-optimization/97623 - Avoid PRE hoist insertion iteration

    The recent previous change in this area limited hoist insertion
    iteration via a param but the following is IMHO better since
    we are not really interested in PRE opportunities exposed by
    hoisting but only the other way around.  So this moves hoist
    insertion after PRE iteration finished and removes hoist
    insertion iteration alltogether.

    2020-11-11  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/97623
            * params.opt (-param=max-pre-hoist-insert-iterations): Remove
            again.
            * doc/invoke.texi (max-pre-hoist-insert-iterations): Likewise.
            * tree-ssa-pre.c (insert): Move hoist insertion after PRE
            insertion iteration and do not iterate it.

            * gcc.dg/tree-ssa/ssa-hoist-3.c: Adjust.
            * gcc.dg/tree-ssa/ssa-hoist-7.c: Likewise.
            * gcc.dg/tree-ssa/ssa-pre-30.c: Likewise.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[tschwinge at gcc dot gnu.org]

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

Thomas Schwinge <tschwinge at gcc dot gnu.org> changed:

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

--- Comment #18 from Thomas Schwinge <tschwinge at gcc dot gnu.org> ---
Noting the following in case there's something unexpected there:

(In reply to CVS Commits from comment #17)
> commit r11-4913-gbd87cc14ebdb6789e067fb1828d5808407c308b3
> Author: Richard Biener <rguenther@suse.de>
> Date:   Wed Nov 11 11:51:59 2020 +0100
> 
>     tree-optimization/97623 - Avoid PRE hoist insertion iteration

On x84_64 GNU/Linux native, this introduced an ICE regression in
'libgomp/plugin/plugin-gcn.c' build (only! -- all other target libraries built
fine):

    during GIMPLE pass: pre
    [...]/libgomp/plugin/plugin-gcn.c: In function ‘run_kernel’:
    [...]/libgomp/plugin/plugin-gcn.c:2066:1: internal compiler error:
Segmentation fault
     2066 | run_kernel (struct kernel_info *kernel, void *vars,
          | ^~~~~~~~~~

    Program received signal SIGSEGV, Segmentation fault.
    bitmap_bit_p (head=0x20, bit=879) at [...]/gcc/bitmap.c:989
    989       if (!head->tree_form)
    (gdb) bt
    #0  bitmap_bit_p (head=0x20, bit=879) at [...]/gcc/bitmap.c:989
    #1  0x0000000001057bb3 in bitmap_set_contains_value (value_id=879, set=0x0)
at [...]/gcc/tree-ssa-pre.c:899
    #2  bitmap_value_replace_in_set (set=0x0, expr=expr@entry=0x2d7f990) at
[...]/gcc/tree-ssa-pre.c:920
    #3  0x0000000001057f35 in create_expression_by_pieces
(block=block@entry=0x7ffff63a51a0, expr=expr@entry=0x2d798f0,
stmts=stmts@entry=0x7fffffffc440, type=<optimized out>) at
[...]/gcc/tree-ssa-pre.c:3003
    #4  0x000000000105e3e9 in do_hoist_insertion (block=<optimized out>) at
[...]/gcc/tree-ssa-pre.c:3648
    #5  insert () at [...]/gcc/tree-ssa-pre.c:3764
    #6  (anonymous namespace)::pass_pre::execute (this=<optimized out>,
fun=0x7ffff6221da8) at [...]/gcc/tree-ssa-pre.c:4299
    #7  0x0000000000d50820 in execute_one_pass (pass=pass@entry=0x2c132f0) at
[...]/gcc/passes.c:2564
    #8  0x0000000000d51198 in execute_pass_list_1 (pass=0x2c132f0) at
[...]/gcc/passes.c:2653
    #9  0x0000000000d511aa in execute_pass_list_1 (pass=0x2c12220) at
[...]/gcc/passes.c:2654
    #10 0x0000000000d511f5 in execute_pass_list (fn=<optimized out>,
pass=<optimized out>) at [...]/gcc/passes.c:2664
    #11 0x000000000094ae6d in cgraph_node::expand (this=0x7ffff6220dd0) at
[...]/gcc/cgraphunit.c:1829
    #12 0x000000000094c69d in expand_all_functions () at
[...]/gcc/cgraphunit.c:1997
    #13 symbol_table::compile (this=this@entry=0x7ffff67a8100) at
[...]/gcc/cgraphunit.c:2361
    #14 0x000000000094fdde in symbol_table::compile (this=0x7ffff67a8100) at
[...]/gcc/cgraphunit.c:2274
    #15 symbol_table::finalize_compilation_unit (this=0x7ffff67a8100) at
[...]/gcc/cgraphunit.c:2542
    #16 0x0000000000e866b1 in compile_file () at [...]/gcc/toplev.c:485
    #17 0x0000000000742f4c in do_compile () at [...]/gcc/toplev.c:2320
    #18 toplev::main (this=this@entry=0x7fffffffc6e0, argc=argc@entry=62,
argv=argv@entry=0x7fffffffc7e8) at [...]/gcc/toplev.c:2459
    #19 0x0000000000746f87 in main (argc=62, argv=0x7fffffffc7e8) at
[...]/gcc/main.c:39

I find this ICE is then again cured by your follow-on commit
r11-4921-g86cca5cc14602814b98e55aae313fbe237af1b04 "Fix PRE topological
expression set sorting", but I can't easily tell if that's now all
fine/expected, or if there may be some underlying problem here, which makes the
ICE just hidden again?  If relevant, please tell if you'd like me to attach a
pre-processed source file.

[Bug tree-optimization/97623] [9/10/11 Regression] Extremely slow O2 compile (>>O(n^2))

[cvs-commit at gcc dot gnu.org]

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

--- Comment #19 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:2e8b368c3d33fd8ddafdd37f8e1b2ba45d1a122e

commit r11-4923-g2e8b368c3d33fd8ddafdd37f8e1b2ba45d1a122e
Author: Richard Biener <rguenther@suse.de>
Date:   Wed Nov 11 18:15:57 2020 +0100

    Fix PRE NEW_SETS guarding

    Accesses to NEW_SETS should be properly guarded.  Committed
    as obvious.

    2020-11-11  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/97623
            * tree-ssa-pre.c (create_expression_by_pieces): Guard
            NEW_SETS access.
            (insert_into_preds_of_block): Likewise.

[Bug tree-optimization/97623] [9/10 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |11.0
            Summary|[9/10/11 Regression]        |[9/10 Regression] Extremely
                   |Extremely slow O2 compile   |slow O2 compile (>>O(n^2))
                   |(>>O(n^2))                  |

--- Comment #20 from Richard Biener <rguenth at gcc dot gnu.org> ---
So I think we can say it is fixed for GCC 11.

[Bug tree-optimization/97623] [9/10 Regression] Extremely slow O2 compile (>>O(n^2))

[cvs-commit at gcc dot gnu.org]

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

--- Comment #21 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:0fd6247a3014038af349db3a01748b5dc17d87a0

commit r10-9245-g0fd6247a3014038af349db3a01748b5dc17d87a0
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Oct 30 13:32:32 2020 +0100

    tree-optimization/97623 - avoid excessive insert iteration for hoisting

    This avoids requiring insert iteration for back-to-back hoisting
    opportunities as seen in the added testcase.  For the PR at hand
    this halves the number of insert iterations retaining only
    the hard to avoid PRE / hoist insert back-to-backs.

    2020-10-30  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/97623
            * tree-ssa-pre.c (insert): First do hoist insertion in
            a backward walk.

            * gcc.dg/tree-ssa/ssa-hoist-7.c: New testcase.

    (cherry picked from commit 82ff7e3426ea926d090777173977f8bedd086816)

[Bug tree-optimization/97623] [9/10 Regression] Extremely slow O2 compile (>>O(n^2))

[cvs-commit at gcc dot gnu.org]

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

--- Comment #22 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:eddcb627ccfbd97e025cf366cc3f3bad76211785

commit r10-9246-geddcb627ccfbd97e025cf366cc3f3bad76211785
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Nov 3 15:03:41 2020 +0100

    tree-optimization/97623 - Avoid PRE hoist insertion iteration

    We are not really interested in PRE opportunities exposed by
    hoisting but only the other way around.  So this moves hoist
    insertion after PRE iteration finished and removes hoist
    insertion iteration alltogether.

    It also guards access to NEW_SETS properly.

    2020-11-11  Richard Biener  <rguenther@suse.de>

            PR tree-optimization/97623
            * tree-ssa-pre.c (insert): Move hoist insertion after PRE
            insertion iteration and do not iterate it.
            (create_expression_by_pieces): Guard NEW_SETS access.
            (insert_into_preds_of_block): Likewise.

            * gcc.dg/tree-ssa/ssa-hoist-3.c: Adjust.
            * gcc.dg/tree-ssa/ssa-hoist-7.c: Likewise.
            * gcc.dg/tree-ssa/ssa-pre-30.c: Likewise.

[Bug tree-optimization/97623] [9 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |10.2.0
      Known to work|                            |10.2.1
            Summary|[9/10 Regression] Extremely |[9 Regression] Extremely
                   |slow O2 compile (>>O(n^2))  |slow O2 compile (>>O(n^2))

--- Comment #23 from Richard Biener <rguenth at gcc dot gnu.org> ---
Backported to GCC 10 - I'm not planning to backport further.

[Bug tree-optimization/97623] [9 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug tree-optimization/97623] [9 Regression] Extremely slow O2 compile (>>O(n^2))

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.3
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #25 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for GCC 10.3.