[Bug c/102356] New: compile-time explosion at -O3

[Bug c/102356] New: compile-time explosion at -O3

[haoxintu at gmail dot com]

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

            Bug ID: 102356
           Summary: compile-time explosion at -O3
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: haoxintu at gmail dot com
  Target Milestone: ---

Hi all.

It's quite weird that the following small valid program makes GCC spend too
much time on compiling at -O3 with the "-g" enabled. It seems GCC-11.x onwards
versions all suffer this issue.

$cat s.c
#include <stdint.h>
int8_t c_5 = 0x0;
uint8_t uc_9 = 0x09;
uint64_t uli_10 = 0xF1FBFC17225F7A57;
int32_t i_12 = 0x3A6667C6;
uint8_t func( uint32_t ui_14) {
    uint32_t *ptr_16 = &ui_14;
    if((uli_10 /= ((0 * (*ptr_16 *= uc_9)) <= 0))) 
        ;
    i_12 = 9;
    for ( ;i_12 > 2; i_12 -= 2 ) {
        uli_10 = -2;
        do      
            if ((*ptr_16 *= *ptr_16)){        
                c_5 = 4;        
                do{        
                    c_5 -=  3;         
                    if ((*ptr_16 *= *ptr_16))       
                        uc_9 = 9;              
                } while (c_5 > 2 );    
            }
        while ( uli_10 ++ );
    }
}

$time gcc -g -O3 -c s.c

real    10m25.417s
user    9m58.685s
sys     0m0.142s


$time gcc -g -O2 -c s.c

real    0m0.124s
user    0m0.045s
sys     0m0.011s


$gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/home/haoxin/haoxin-data/compilers/gcc/build/libexec/gcc/x86_64-pc-linux-gnu/12.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../configure
--prefix=/home/haoxin/haoxin-data/compilers/gcc/build/ --enable-bootstrap
--enable-checking=release --enable-languages=c,c++ --enable-multilib :
(reconfigured) ../configure
--prefix=/home/haoxin/haoxin-data/compilers/gcc/build/ --enable-bootstrap
--enable-checking=release --enable-languages=c,c++ --enable-multilib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.0.0 20210913 (experimental) (GCC) 

Reproduced in Godbolt: https://godbolt.org/z/47dqnPbad

Thanks,
Haoxin

[Bug rtl-optimization/102356] compile-time explosion at -O3 -g in var-tracking

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64-*-*
   Last reconfirmed|                            |2021-09-16
             Status|UNCONFIRMED                 |NEW
          Component|c                           |rtl-optimization
            Summary|compile-time explosion at   |compile-time explosion at
                   |-O3                         |-O3 -g in var-tracking
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  We hang in

#0  0x000000000109ceeb in HONOR_NANS (m=E_SImode)
    at ../../src/gcc-11-branch/gcc/real.c:5436
#1  0x00000000011529b2 in simplify_context::simplify_binary_operation_1 (
    this=0x7fffffffce4c, code=MULT, mode=E_SImode, op0=0x7ffff671f740, 
    op1=0x7ffff66e0cc0, trueop0=0x7ffff671f740, trueop1=0x7ffff66e0cc0)
    at ../../src/gcc-11-branch/gcc/simplify-rtx.c:3043
#2  0x000000000114fbf5 in simplify_context::simplify_binary_operation (
    this=0x7fffffffce4c, code=MULT, mode=E_SImode, op0=0x7ffff671f740, 
    op1=0x7ffff66e0cc0) at ../../src/gcc-11-branch/gcc/simplify-rtx.c:2423
#3  0x000000000114f312 in simplify_context::simplify_associative_operation (
    this=0x7fffffffce4c, code=MULT, mode=E_SImode, op0=0x7ffff63e6768, 
    op1=0x7ffff66e0cc0) at ../../src/gcc-11-branch/gcc/simplify-rtx.c:2154
#4  0x0000000001152ede in simplify_context::simplify_binary_operation_1 (
    this=0x7fffffffce4c, code=MULT, mode=E_SImode, op0=0x7ffff63e6768, 
    op1=0x7ffff66e0cc0, trueop0=0x7ffff63e6768, trueop1=0x7ffff66e0cc0)
    at ../../src/gcc-11-branch/gcc/simplify-rtx.c:3101
...
#2678 0x0000000000cd0e36 in simplify_binary_operation (code=MULT, 
    mode=E_SImode, op0=0x7ffff63b0030, op1=0x7ffff63b0030)
    at ../../src/gcc-11-branch/gcc/rtl.h:3457
#2679 0x0000000001166284 in simplify_rtx (x=0x7ffff63b0090)
    at ../../src/gcc-11-branch/gcc/simplify-rtx.c:7431

#2680 0x0000000000c17b3d in cselib_expand_value_rtx_1 (orig=0x7ffff67290f0, 
    evd=0x7fffffffcf80, max_depth=2147483647)
    at ../../src/gcc-11-branch/gcc/cselib.c:2025
#2681 0x0000000000c171b5 in cselib_expand_value_rtx_cb (orig=0x7ffff67290f0, 
    regs_active=0x32c1470, max_depth=2147483647, 
    cb=0x15433ec <vt_expand_loc_callback(rtx, bitmap, int, void*)>, 
    data=0x7fffffffd2c0) at ../../src/gcc-11-branch/gcc/cselib.c:1732
#2682 0x0000000001543222 in vt_expand_var_loc_chain (var=0x3493748, 
    regs=0x32c1470, data=0x7fffffffd2c0, pendrecp=0x7fffffffd087)
    at ../../src/gcc-11-branch/gcc/var-tracking.c:8421
#2683 0x0000000001543623 in vt_expand_loc_callback (x=0x33e6128, 
    regs=0x32c1470, max_depth=2147483647, data=0x7fffffffd2c0)
    at ../../src/gcc-11-branch/gcc/var-tracking.c:8584
#2684 0x0000000000c1765e in cselib_expand_value_rtx_1 (orig=0x33e6128, 
    evd=0x7fffffffd1c0, max_depth=2147483647)
    at ../../src/gcc-11-branch/gcc/cselib.c:1885
#2685 0x0000000000c171b5 in cselib_expand_value_rtx_cb (orig=0x33e6128, 
--Type <RET> for more, q to quit, c to continue without paging--
    regs_active=0x32c1470, max_depth=2147483647, 
    cb=0x15433ec <vt_expand_loc_callback(rtx, bitmap, int, void*)>, 
    data=0x7fffffffd2c0) at ../../src/gcc-11-branch/gcc/cselib.c:1732
#2686 0x0000000001543222 in vt_expand_var_loc_chain (var=0x3493680, 
    regs=0x32c1470, data=0x7fffffffd2c0, pendrecp=0x0)
    at ../../src/gcc-11-branch/gcc/var-tracking.c:8421
#2687 0x00000000015438b2 in vt_expand_1pvar (var=0x3493680, vars=0x34bc6f0)
    at ../../src/gcc-11-branch/gcc/var-tracking.c:8697
#2688 0x0000000001543b2a in emit_note_insn_var_location (varp=0x342e100, 
    data=0x7fffffffd650) at ../../src/gcc-11-branch/gcc/var-tracking.c:8751
#2689 0x000000000154b4af in hash_table<variable_hasher, false,
xcallocator>::traverse_noresize<emit_note_data*,
&(emit_note_insn_var_location(variable**, emit_note_data*))> (this=0x3431620,
argument=0x7fffffffd650)
    at ../../src/gcc-11-branch/gcc/hash-table.h:1081
#2690 0x0000000001549f2f in hash_table<variable_hasher, false,
xcallocator>::traverse<emit_note_data*,
&(emit_note_insn_var_location(variable**, emit_note_data*))> (this=0x3431620,
argument=0x7fffffffd650)
    at ../../src/gcc-11-branch/gcc/hash-table.h:1102
#2691 0x0000000001544e40 in emit_notes_for_changes (insn=0x7ffff670cb00, 
    where=EMIT_NOTE_BEFORE_INSN, vars=0x328d7b0)
    at ../../src/gcc-11-branch/gcc/var-tracking.c:9111
#2692 0x0000000001545d18 in emit_notes_in_bb (
    bb=<basic_block 0x7ffff66f4340 (11)>, set=0x7fffffffd7b0)
--Type <RET> for more, q to quit, c to continue without paging--
    at ../../src/gcc-11-branch/gcc/var-tracking.c:9483
#2693 0x00000000015461ae in vt_emit_notes ()
    at ../../src/gcc-11-branch/gcc/var-tracking.c:9604
#2694 0x0000000001548814 in variable_tracking_main_1 ()
    at ../../src/gcc-11-branch/gcc/var-tracking.c:10552
#2695 0x000000000154884a in variable_tracking_main ()
    at ../../src/gcc-11-branch/gcc/var-tracking.c:10566
#2696 0x00000000015488d7 in (anonymous
namespace)::pass_variable_tracking::execute (this=0x326d380) at
../../src/gcc-11-branch/gcc/var-tracking.c:10603
#2697 0x000000000105944a in execute_one_pass (
    pass=<opt_pass* 0x326d380 "vartrack"(325)>)
    at ../../src/gcc-11-branch/gcc/passes.c:2567

and at the toplevel we simplify a _very_ _very_ deep recursive RTX.  We're
passing in

/* This is the value used during expansion of locations.  We want it
   to be unbounded, so that variables expanded deep in a recursion
   nest are fully evaluated, so that their values are cached
   correctly.  We avoid recursion cycles through other means, and we
   don't unshare RTL, so excess complexity is not a problem.  */
#define EXPR_DEPTH (INT_MAX)

which might be the problem.  The debug_insns themselves are nicely flat
but the testcase results in

        movzbl  uc_9(%rip), %eax
        imull   %edi, %eax
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L20
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L21
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L37
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L11
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L11
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L11
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L11
        imull   %eax, %eax
        testl   %eax, %eax
        je      .L53

where we might be tempted to pick up the whole x*x*x*x*x... chain N times.

[Bug rtl-optimization/102356] [11/12 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|compile-time explosion at   |[11/12 Regression]
                   |-O3 -g in var-tracking      |compile-time explosion at
                   |                            |-O3 -g in var-tracking
                   |                            |since
                   |                            |r11-209-g74dc179a6da33cd0
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |vmakarov at gcc dot gnu.org

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
If I see correctly, it started with r11-209-g74dc179a6da33cd0.

[Bug rtl-optimization/102356] [11/12 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.3

[Bug rtl-optimization/102356] [11/12 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[vmakarov at gcc dot gnu.org]

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

--- Comment #3 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
(In reply to Martin Liška from comment #2)
> If I see correctly, it started with r11-209-g74dc179a6da33cd0.

Yes, I am confirming that my patch triggered the slow down.  But the actual
problem is not RA, it is in scalability of var-tracking pass.

I'll investigate more can I fix it in RA and is it worth to fix it in RA.

[Bug rtl-optimization/102356] [11/12 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 51898
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51898&action=edit
gcc12-pr102356.patch

In this case it isn't about scalability of var-tracking itself, but that
simplify-rtx.c is written with the assumption that combine or other RTL passes
typically only try to combine a few instructions together and so the resulting
expressions can't be arbitrarily large.

[Bug rtl-optimization/102356] [11/12 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:35f2c098c81118020b1d288cd739108c8747a520

commit r12-5652-g35f2c098c81118020b1d288cd739108c8747a520
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Dec 1 10:16:57 2021 +0100

    simplify-rtx: Punt on simplify_associative_operation with large operands
[PR102356]

    Seems simplify_associate_operation is quadratic, which isn't a big deal
    for use during combine and other similar RTL passes, because those never
    try to combine expressions from more than a few instructions and because
    those instructions need to be recognized the machine description also
bounds
    how many expressions can appear in there.
    var-tracking has depth limits only for some cases and unlimited depth
    for the vt_expand_loc though:
     /* This is the value used during expansion of locations.  We want it
        to be unbounded, so that variables expanded deep in a recursion
        nest are fully evaluated, so that their values are cached
        correctly.  We avoid recursion cycles through other means, and we
        don't unshare RTL, so excess complexity is not a problem.  */
     #define EXPR_DEPTH (INT_MAX)
     /* We use this to keep too-complex expressions from being emitted as
        location notes, and then to debug information.  Users can trade
        compile time for ridiculously complex expressions, although they're
        seldom useful, and they may often have to be discarded as not
        representable anyway.  */
     #define EXPR_USE_DEPTH (param_max_vartrack_expr_depth)

    IMO for very large expressions it isn't worth trying to reassociate though,
    in fact e.g. for the new testcase below keeping it as is has bigger chance
    of generating smaller debug info which the dwarf2out.c part of the change
    tries to achieve - if a binary operation has the same operands, we can
    use DW_OP_dup and not bother computing the possibly large operand again.

    The patch fixes it by adding a counter to simplify_context and counting
    how many times simplify_associative_operation has been called during
    a single outermost simplify_* call, and once it reaches some maximum
    (currently 64), it stops reassociating.

    Another possibility to deal with the power expressions in debug info
    would be to introduce some new RTL operation for the pow{,i} (x, n)
    case, allow that solely in debug insns and expand those into DWARF
    using a loop.  But that seems like quite a lot of work for something rarely
    used (especially when powi for larger n is only useful for 0 and 1 inputs
    because anything else overflows).

    2021-12-01  Jakub Jelinek  <jakub@redhat.com>

            PR rtl-optimization/102356
            * rtl.h (simplify_context): Add assoc_count member and
            max_assoc_count static member.
            * simplify-rtx.c (simplify_associative_operation): Don't
reassociate
            more than max_assoc_count times within one outermost simplify_*
call.
            * dwarf2out.c (mem_loc_descriptor): Optimize binary operation
            with both operands the same using DW_OP_dup.

            * gcc.dg/pr102356.c: New test.

[Bug rtl-optimization/102356] [11 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
            Summary|[11/12 Regression]          |[11 Regression]
                   |compile-time explosion at   |compile-time explosion at
                   |-O3 -g in var-tracking      |-O3 -g in var-tracking
                   |since                       |since
                   |r11-209-g74dc179a6da33cd0   |r11-209-g74dc179a6da33cd0
             Status|NEW                         |ASSIGNED

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed on the trunk so far.

[Bug rtl-optimization/102356] [11 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:6a43f5c64b4000233c552891abc13cbd447e5703

commit r11-9346-g6a43f5c64b4000233c552891abc13cbd447e5703
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Dec 1 10:16:57 2021 +0100

    simplify-rtx: Punt on simplify_associative_operation with large operands
[PR102356]

    Seems simplify_associate_operation is quadratic, which isn't a big deal
    for use during combine and other similar RTL passes, because those never
    try to combine expressions from more than a few instructions and because
    those instructions need to be recognized the machine description also
bounds
    how many expressions can appear in there.
    var-tracking has depth limits only for some cases and unlimited depth
    for the vt_expand_loc though:
     /* This is the value used during expansion of locations.  We want it
        to be unbounded, so that variables expanded deep in a recursion
        nest are fully evaluated, so that their values are cached
        correctly.  We avoid recursion cycles through other means, and we
        don't unshare RTL, so excess complexity is not a problem.  */
     #define EXPR_DEPTH (INT_MAX)
     /* We use this to keep too-complex expressions from being emitted as
        location notes, and then to debug information.  Users can trade
        compile time for ridiculously complex expressions, although they're
        seldom useful, and they may often have to be discarded as not
        representable anyway.  */
     #define EXPR_USE_DEPTH (param_max_vartrack_expr_depth)

    IMO for very large expressions it isn't worth trying to reassociate though,
    in fact e.g. for the new testcase below keeping it as is has bigger chance
    of generating smaller debug info which the dwarf2out.c part of the change
    tries to achieve - if a binary operation has the same operands, we can
    use DW_OP_dup and not bother computing the possibly large operand again.

    The patch fixes it by adding a counter to simplify_context and counting
    how many times simplify_associative_operation has been called during
    a single outermost simplify_* call, and once it reaches some maximum
    (currently 64), it stops reassociating.

    Another possibility to deal with the power expressions in debug info
    would be to introduce some new RTL operation for the pow{,i} (x, n)
    case, allow that solely in debug insns and expand those into DWARF
    using a loop.  But that seems like quite a lot of work for something rarely
    used (especially when powi for larger n is only useful for 0 and 1 inputs
    because anything else overflows).

    2021-12-01  Jakub Jelinek  <jakub@redhat.com>

            PR rtl-optimization/102356
            * rtl.h (simplify_context): Add assoc_count member and
            max_assoc_count static member.
            * simplify-rtx.c (simplify_associative_operation): Don't
reassociate
            more than max_assoc_count times within one outermost simplify_*
call.

            * gcc.dg/pr102356.c: New test.

    (cherry picked from commit 35f2c098c81118020b1d288cd739108c8747a520)

[Bug rtl-optimization/102356] [11 Regression] compile-time explosion at -O3 -g in var-tracking since r11-209-g74dc179a6da33cd0

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed now.