[Bug tree-optimization/109192] [13 Regression] timeout with -O3 since r13-5579

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-03-20
            Summary|[13 Regression] timeout     |[13 Regression] timeout
                   |with -O3 -fno-var-tracking  |with -O3 since r13-5579
                   |since r13-5579              |
           Priority|P3                          |P1

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed - this has nothing to do with -fno-var-tracking btw but reproduces
with just -O3 vs -O2.  An interrupted (after a minute) perf profile shows

+   55.46%     0.66%          1769  cc1      cc1                 [.]
operator_cast::op1_range                          #
+   48.68%     0.05%           141  cc1      cc1                 [.]
operator_cast::fold_range                         #
+   48.63%     3.06%          8238  cc1      cc1                 [.]
operator_cast::fold_range                         #
+   27.27%     1.18%          3160  cc1      cc1                 [.]
irange::set_nonzero_bits                          #
+   25.39%     1.68%          4512  cc1      cc1                 [.]
irange::set_range_from_nonzero_bits               #
+   21.08%     0.74%          1998  cc1      cc1                 [.]
irange::get_nonzero_bits                          #
+   20.34%    14.24%         38289  cc1      cc1                 [.]
irange::get_nonzero_bits_from_range               

and we're in the 'thread'(200) pass

      NEXT_PASS (pass_fre, false /* may_iterate */);
      /* After late FRE we rewrite no longer addressed locals into SSA
         form if possible.  */
      NEXT_PASS (pass_thread_jumps, /*first=*/false);
      NEXT_PASS (pass_dominator, false /* may_peel_loop_headers_p */);
      NEXT_PASS (pass_strlen);

interrupting gives a backtrace like

#2  0x000000000196ec95 in gori_compute::compute_operand_range (
    this=this@entry=0x47bd5e0, r=..., stmt=<gimple_assign 0x7f9b81bbe5f0>, 
    lhs=..., name=name@entry=<ssa_name 0x7f9b81b21ab0 373>, src=..., 
    rel=<optimized out>)
    at /space/rguenther/src/gcc/gcc/gimple-range-gori.cc:700
...
#211 0x000000000196f37b in gori_compute::compute_operand_range (
    this=this@entry=0x47bd5e0, r=..., 
    stmt=stmt@entry=<gimple_cond 0x7f9b81bac5a0>, lhs=..., 
    name=name@entry=<ssa_name 0x7f9b81b21ab0 373>, src=..., 
    rel=<optimized out>)
    at /space/rguenther/src/gcc/gcc/gimple-range-gori.cc:702
#212 0x0000000001970ec9 in gori_compute::outgoing_edge_range_p (
    this=this@entry=0x47bd5e0, r=..., 
    e=e@entry=<edge 0x7f9b81dddba0 (122 -> 126)>, 

    name=name@entry=<ssa_name 0x7f9b81b21ab0 373>, q=...)
    at /space/rguenther/src/gcc/gcc/gimple-range-gori.cc:1358
#213 0x0000000000e4aa79 in path_range_query::compute_ranges_in_block (
    this=this@entry=0x7fff9c936a40, 
    bb=bb@entry=<basic_block 0x7f9b81ba7ba0 (122)>)
    at /space/rguenther/src/gcc/gcc/gimple-range-path.cc:454

so 200 frames worth of recursion (just luck from some random gdb attach).
There are just 201 BBs in the function (func_36.constprop) and 1525
SSA names, so this seems to be quadraticness / missed caching.