[Bug tree-optimization/103254] New: [12 Regression] Compile time hog in compare_values_warnv

[Bug tree-optimization/103254] New: [12 Regression] Compile time hog in compare_values_warnv

[asolokha at gmx dot com]

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

            Bug ID: 103254
           Summary: [12 Regression] Compile time hog in
                    compare_values_warnv
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: asolokha at gmx dot com
  Target Milestone: ---

gcc-12.0.0-alpha20111107 snapshot (g:962ff7d2849e1fa6a1fe0535aa2dec5c2b9a32a6)
takes indefinite time to compile the following testcase w/ -O3:

short int i;

void
foo (void)
{
  for (i = 1; i < 2; i += 4)
    {
      int j;

      for (j = 0; j < 5; j += 4)
        {
          int k;

          for (k = 0; k < 68; k += 4)
            {
              i &= j;
              j &= i;
            }
        }
    }
}

% timeout 10 gcc-12.0.0 -O3 -c mgyelpiv.c
zsh: exit 124   timeout 10 gcc-12.0.0 -O3 -c mgyelpiv.c

Several top entries from perf top output:

   8.03%  cc1        [.] wide_int_to_tree_1
   5.93%  cc1        [.] compare_values_warnv
   5.38%  cc1        [.] irange::irange_union
   4.72%  cc1        [.] irange::varying_compatible_p
   4.34%  cc1        [.] wi::to_wide
   3.23%  cc1        [.] irange::irange_intersect
   3.12%  cc1        [.] tree_int_cst_compare
   3.07%  cc1        [.] wi::force_to_size
   2.76%  cc1        [.] useless_type_conversion_p
   2.67%  cc1        [.] irange::lower_bound
   2.38%  cc1        [.] irange::set_varying
   2.31%  cc1        [.] wi::shifted_mask
   2.17%  cc1        [.] get_single_symbol
   1.91%  cc1        [.] int_cst_hasher::hash
   1.86%  cc1        [.] irange::verify_range
   1.84%  cc1        [.] wi::min_value
   1.84%  cc1        [.] irange::irange_set_anti_range
   1.63%  cc1        [.] wi::lts_p<generic_wide_int<wide_int_ref_storage<false,
false> >, generic_wide_int<wide_int_ref_storage<false, f
   1.46%  cc1        [.] operand_compare::operand_equal_p
   1.37%  cc1        [.] operator_cast::fold_pair
   1.35%  cc1        [.] gori_compute::compute_operand_range

[Bug tree-optimization/103254] [12 Regression] Compile time hog in compare_values_warnv since r12-4790-g4b3a325f07acebf4

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |11.2.0
     Ever confirmed|0                           |1
            Summary|[12 Regression] Compile     |[12 Regression] Compile
                   |time hog in                 |time hog in
                   |compare_values_warnv        |compare_values_warnv since
                   |                            |r12-4790-g4b3a325f07acebf4
   Target Milestone|---                         |12.0
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |marxin at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
           Priority|P3                          |P1
   Last reconfirmed|                            |2021-11-16
      Known to fail|                            |12.0

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r12-4790-g4b3a325f07acebf4.

[Bug tree-optimization/103254] [12 Regression] Compile time hog in compare_values_warnv since r12-4790-g4b3a325f07acebf4

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #2 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
GORI is taking forever to query the outgoing range of _14 on the 3->4 edge. 
The cunroll pass has expanded the block to this:

  <bb 3> [local count: 59700049]:
  # j_32 = PHI <j_20(8), 0(5)>
  # i_lsm.10_31 = PHI <_3(8), i_lsm.10_6(5)>
  _45 = (short int) j_32;
  _44 = i_lsm.10_31 & _45;
  _43 = (int) _44;
  j_42 = _43 & j_32;
  _19 = (short int) j_42;
  _14 = _19 & _44;
  _13 = (int) _14;
  j_12 = _13 & j_42;
  _29 = (short int) j_12;
  _26 = _29 & _14;
  _15 = (int) _26;
  j_27 = _15 & j_12;
  _56 = (short int) j_27;
  _57 = _56 & _26;
  _58 = (int) _57;
  j_59 = _58 & j_27;
  _65 = (short int) j_59;
  _66 = _65 & _57;
  _67 = (int) _66;
  j_68 = _67 & j_59;
  _74 = (short int) j_68;
  _75 = _74 & _66;
  _76 = (int) _75;
  j_77 = _76 & j_68;
  _83 = (short int) j_77;
  _84 = _83 & _75;
  _85 = (int) _84;
  j_86 = _85 & j_77;
  _92 = (short int) j_86;
  _93 = _92 & _84;
  _94 = (int) _93;
  j_95 = _94 & j_86;
  _101 = (short int) j_95;
  _102 = _101 & _93;
  _103 = (int) _102;
  j_104 = _103 & j_95;
  _110 = (short int) j_104;
  _111 = _110 & _102;
  _112 = (int) _111;
  j_113 = _112 & j_104;
  _119 = (short int) j_113;
  _120 = _119 & _111;
  _121 = (int) _120;
  j_122 = _121 & j_113;
  _128 = (short int) j_122;
  _129 = _128 & _120;
  _130 = (int) _129;
  j_131 = _130 & j_122;
  _137 = (short int) j_131;
  _138 = _137 & _129;
  _139 = (int) _138;
  j_140 = _139 & j_131;
  _146 = (short int) j_140;
  _147 = _146 & _138;
  _148 = (int) _147;
  j_149 = _148 & j_140;
  _155 = (short int) j_149;
  _156 = _155 & _147;
  _157 = (int) _156;
  j_158 = _157 & j_149;
  _164 = (short int) j_158;
  _165 = _164 & _156;
  _166 = (int) _165;
  j_167 = _166 & j_158;
  _1 = (short int) j_167;
  _3 = _1 & _165;
  _5 = (int) _3;
  j_22 = _5 & j_167;
  j_20 = j_22 + 4;
  if (j_20 <= 4)
    goto <bb 8>; [89.00%]
  else
    goto <bb 4>; [11.00%]

Andrew, didn't we talk about clamping gori if the series of dependencies was
greater than some number, because a long chain of events was unlikely to yield
meaningful ranges?

Interestingly vrp2 doesn't hang even with -fno-thread-jumps, but
-fno-thread-jumps -fdump-tree-vrp-details
does make gori hang, since it's now asking for all the outgoing ranges, _14 and
friends included.

[Bug tree-optimization/103254] [12 Regression] Compile time hog in compare_values_warnv since r12-4790-g4b3a325f07acebf4

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
This is a long sequence, made from the following pattern:

  _156 = _155 & _147;
  _157 = (int) _156;
  j_158 = _157 & j_149;
  _164 = (short int) j_158;
  _165 = _164 & _156;

Since GORI doesn't yet cache anything, each name evaluation is a "new" request.
 to resolve _165 it calculates  _164 and _156.
Note that _164 is also ultimately defined by _156 (in combination with _j_149).
so that means we evaluate _156 twice to get _165.

This rapidly triggers the same exponential growth we encountered with PR
100081, so we will need to limit this sort of thing in general until GORI
starts caching outgoing values.

[Bug tree-optimization/103254] [12 Regression] Compile time hog in compare_values_warnv since r12-4790-g4b3a325f07acebf4

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

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

commit r12-5409-gee448a523d377f9ed882dac806d2f5001bfa2432
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Wed Nov 17 14:14:06 2021 -0500

    Limit depth for all GORI expressions.

    Apply the logical_depth limit ranger uses to all stmts with multiple
ssa-names
    to avoid excessive outgoing calculations.

            gcc/
            PR tree-optimization/103254
            * gimple-range-gori.cc (range_def_chain::get_def_chain): Limit the
            depth for all statements with multple ssa names.

            gcc/testsuite/
            * gcc.dg/pr103254.c: New.

[Bug tree-optimization/103254] [12 Regression] Compile time hog in compare_values_warnv since r12-4790-g4b3a325f07acebf4

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
fixed.

[Bug tree-optimization/103254] [12 Regression] Compile time hog in compare_values_warnv since r12-4790-g4b3a325f07acebf4

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

https://gcc.gnu.org/g:8acbd7bef6edbf537e3037174907029b530212f6

commit r12-5514-g8acbd7bef6edbf537e3037174907029b530212f6
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Wed Nov 24 09:43:36 2021 +0100

    path solver: Compute ranges in path in gimple order.

    Andrew's patch for this PR103254 papered over some underlying
    performance issues in the path solver that I'd like to address.

    We are currently solving the SSA's defined in the current block in
    bitmap order, which amounts to random order for all purposes.  This is
    causing unnecessary recursion in gori.  This patch changes the order
    to gimple order, thus solving dependencies before uses.

    There is no change in threadable paths with this change.

    Tested on x86-64 & ppc64le Linux.

    gcc/ChangeLog:

            PR tree-optimization/103254
            * gimple-range-path.cc (path_range_query::compute_ranges_defined):
New
            (path_range_query::compute_ranges_in_block): Move to
            compute_ranges_defined.
            * gimple-range-path.h (compute_ranges_defined): New.

[Bug tree-optimization/103254] [12 Regression] Compile time hog in compare_values_warnv since r12-4790-g4b3a325f07acebf4

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

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

commit r12-5515-gd1c1919ef8a18eea9d5c1741f8c9adaabf5571f2
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Wed Nov 24 17:58:43 2021 +0100

    path solver: Move boolean import code to compute_imports.

    In a follow-up patch I will be pruning the set of exported ranges
    within blocks to avoid unnecessary work.  In order to do this, all the
    interesting SSA names must be in the internal import bitmap ahead of
    time.  I had already abstracted them out into compute_imports, but I
    missed the boolean code.  This fixes the oversight.

    There's a net gain of 25 threadable paths, which is unexpected but
    welcome.

    Tested on x86-64 & ppc64le Linux.

    gcc/ChangeLog:

            PR tree-optimization/103254
            * gimple-range-path.cc (path_range_query::compute_ranges): Move
            exported boolean code...
            (path_range_query::compute_imports): ...here.