[Bug tree-optimization/103821] New: [12 Regression] huge compile time (jump threading) at -O3 for simple code

[Bug tree-optimization/103821] New: [12 Regression] huge compile time (jump threading) at -O3 for simple code

[pinskia at gcc dot gnu.org]

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

            Bug ID: 103821
           Summary: [12 Regression] huge compile time (jump threading) at
                    -O3 for simple code
           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: pinskia at gcc dot gnu.org
  Target Milestone: ---

Take:
    #include <inttypes.h>
    uint16_t int_sqrt32(uint32_t x)
    {
        uint16_t res=0;
        uint16_t add= 0x8000;   
        do {
            uint16_t temp=res | add;
            uint32_t g2=temp*temp;      
            if (x>=g2)
                res=temp;           
            add>>=1;
        } while(add);
        return res;
    }
----- CUT -----
Compile this at -O3 and GCC takes a long time:
 backwards jump threading           :  20.12 ( 81%)   0.01 ( 50%)  20.12 ( 78%)
   26M ( 79%)

[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0

[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=103815

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I found this while looking into PR 103815.

[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com,
                   |                            |marxin at gcc dot gnu.org
   Last reconfirmed|                            |2021-12-28
            Summary|[12 Regression] huge        |[12 Regression] huge
                   |compile time (jump          |compile time (jump
                   |threading) at -O3 for       |threading) at -O3 for
                   |simple code                 |simple code since
                   |                            |r12-4790-g4b3a325f07acebf47
                   |                            |e82de227ce1d5ba62f5bcae

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

[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
Interesting.  This isn't caused by jump threading, just exposed by it.

We end up unrolling this loop, and the pattern of code creates a set of
cascading multiplies for which we can precisely evaluate them with subranges.

For instance, we calculate:

_38 = int [8192, 8192][24576, 24576][40960, 40960][57344, 57344]

so _38 has 4 subranges, and then we calculate:

_39 = _38 * _38;

we do 16 multiplications and end up with:  int [67108864, 67108864][201326592,
201326592][335544320, 335544320][469762048, 469762048][603979776,
603979776][1006632960, 1006632960][1409286144, 1409286144][1677721600,
1677721600][+INF, +INF]

This feeds other multiplies and progresses rapidly to blow up the number of
subranges, which are then propagated via PHIs and other operations.

Folding of subranges is an O(n*m) process. We perform the operation on each
pair of subranges and union them.   Values like _38 * _38 that continue feeding
each other quickly become exponential.

Then combining that with union (an inherently linear operation over the number
of subranges) at each step of the way adds an additional quadratic operation on
top of the exponential factor. 

I will adjust the wi_fold routine to recognize when the calculation is moving
in an exponential direction, simply produce a summary a result instead of a
precise one.  Longer term, we could consider merging some of the subranges to
prevent the exponential growth, but still retain some precision.

[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae

[cvs-commit at gcc dot gnu.org]

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

--- 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:71b72132011a47a4b39950d95718f18d1218978c

commit r12-6477-g71b72132011a47a4b39950d95718f18d1218978c
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Jan 10 13:33:44 2022 -0500

    Prevent exponential range calculations.

    Produce a summary result for any operation involving too many subranges.

            PR tree-optimization/103821
            * range-op.cc (range_operator::fold_range): Only do precise ranges
            when there are not too many subranges.

[Bug tree-optimization/103821] [12 Regression] huge compile time (jump threading) at -O3 for simple code since r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae

[amacleod at redhat dot com]

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

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.