[Bug analyzer/110112] New: [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[Bug analyzer/110112] New: [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[bruno at clisp dot org]

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

            Bug ID: 110112
           Summary: [11/12/13 Regression] gcc -fanalyzer takes an
                    excessive amount of time
           Product: gcc
           Version: 13.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: bruno at clisp dot org
  Target Milestone: ---

Created attachment 55253
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55253&action=edit
test case uniname.c (compressed)

In a compilation unit with some large read-only static arrays, "gcc -fanalyzer"
takes an excessive amount of time: 66 seconds as opposed to less than 1 second
without '-fanalyzer'.

How to reproduce:
$ time gcc -O2 -c uniname.c 

real    0m0,819s
user    0m0,797s
sys     0m0,012s

$ time gcc -O2 -fanalyzer -c uniname.c 
<two warnings>

real    1m6,195s
user    1m6,101s
sys     0m0,088s

[Bug analyzer/110112] [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[bruno at clisp dot org]

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

Bruno Haible <bruno at clisp dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
               Host|                            |x86_64-linux-gnu
      Known to fail|                            |11.3.0, 12.3.0, 13.1.0
      Known to work|                            |10.4.0
              Build|                            |x86_64-linux-gnu
             Target|                            |x86_64-linux-gnu

--- Comment #1 from Bruno Haible <bruno at clisp dot org> ---
Compilation times with various gcc versions, with -O2 -fanalyzer:

gcc 13.1.0: 66 sec
gcc 12.3.0: 66 sec
gcc 11.3.0: 52 sec
gcc 10.4.0: 0.9 sec

[Bug analyzer/110112] [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[tlange at gcc dot gnu.org]

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

Tim Lange <tlange at gcc dot gnu.org> changed:

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

--- Comment #2 from Tim Lange <tlange at gcc dot gnu.org> ---
Seems to be related to binding_map::apply_ctor_to_region (const region *, tree,
region_model_manager *) being called quite often to bind the initial value of
the global to a region. The method is linear in the size of the elements of the
constructor node and does expensive things inside the loop.

A quick fix would be to bail out if the number of elements is too large and
resort to a unknown value.

[Bug analyzer/110112] [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.5

[Bug analyzer/110112] [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[dmalcolm at gcc dot gnu.org]

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

David Malcolm <dmalcolm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-06-08
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1

--- Comment #3 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Thanks.

I was seeing:
  real  1m31.214s

Adding a cache to region_model::get_initial_value_for_global speeds things up
greatly to:
  real  0m3.677s

Adding a further cache to decl_region::get_svalue_for_constructor gives a
further slight speedup to:
  real  0m3.069s

I'm working on a fix based on the above.

[Bug analyzer/110112] [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[cvs-commit at gcc dot gnu.org]

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

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

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

commit r14-1664-gfe9771b59f576fb37e762013ef5d9b26162e3a88
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Fri Jun 9 17:58:33 2023 -0400

    analyzer: add caching to globals with initializers [PR110112]

    PR analyzer/110112 notes that -fanalyzer is extremely slow on a source
    file with large read-only static arrays, repeatedly building the
    same compound_svalue representing the full initializer, and repeatedly
    building svalues representing parts of the the full initialiazer.

    This patch adds caches for both of these; together they reduce the time
    taken by -fanalyzer -O2 on the testcase in the bug for an optimized
    build:
      91.2s : no caches (status quo)
      32.4s : cache in decl_region::get_svalue_for_constructor
       3.7s : cache in region::get_initial_value_at_main
       3.1s : both caches (this patch)

    gcc/analyzer/ChangeLog:
            PR analyzer/110112
            * region-model.cc (region_model::get_initial_value_for_global):
            Move code to region::calc_initial_value_at_main.
            * region.cc (region::get_initial_value_at_main): New function.
            (region::calc_initial_value_at_main): New function, based on code
            in region_model::get_initial_value_for_global.
            (region::region): Initialize m_cached_init_sval_at_main.
            (decl_region::get_svalue_for_constructor): Add a cache, splitting
            out body to...
            (decl_region::calc_svalue_for_constructor): ...this new function.
            * region.h (region::get_initial_value_at_main): New decl.
            (region::calc_initial_value_at_main): New decl.
            (region::m_cached_init_sval_at_main): New field.
            (decl_region::decl_region): Initialize m_ctor_svalue.
            (decl_region::calc_svalue_for_constructor): New decl.
            (decl_region::m_ctor_svalue): New field.

    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

[Bug analyzer/110112] [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[dmalcolm at gcc dot gnu.org]

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

--- Comment #5 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Should be fixed on trunk for gcc 14 by the above patch.

Keeping this open to track backporting it.

[Bug analyzer/110112] [11/12/13 Regression] gcc -fanalyzer takes an excessive amount of time

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by David Malcolm
<dmalcolm@gcc.gnu.org>:

https://gcc.gnu.org/g:89feb3557a018893cfe50c2e07f91559bd3cde2b

commit r13-8741-g89feb3557a018893cfe50c2e07f91559bd3cde2b
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu May 9 13:09:26 2024 -0400

    analyzer: add caching to globals with initializers [PR110112]

    PR analyzer/110112 notes that -fanalyzer is extremely slow on a source
    file with large read-only static arrays, repeatedly building the
    same compound_svalue representing the full initializer, and repeatedly
    building svalues representing parts of the the full initialiazer.

    This patch adds caches for both of these; together they reduce the time
    taken by -fanalyzer -O2 on the testcase in the bug for an optimized
    build:
      91.2s : no caches (status quo)
      32.4s : cache in decl_region::get_svalue_for_constructor
       3.7s : cache in region::get_initial_value_at_main
       3.1s : both caches (this patch)

    gcc/analyzer/ChangeLog:
            PR analyzer/110112
            * region-model.cc (region_model::get_initial_value_for_global):
            Move code to region::calc_initial_value_at_main.
            * region.cc (region::get_initial_value_at_main): New function.
            (region::calc_initial_value_at_main): New function, based on code
            in region_model::get_initial_value_for_global.
            (region::region): Initialize m_cached_init_sval_at_main.
            (decl_region::get_svalue_for_constructor): Add a cache, splitting
            out body to...
            (decl_region::calc_svalue_for_constructor): ...this new function.
            * region.h (region::get_initial_value_at_main): New decl.
            (region::calc_initial_value_at_main): New decl.
            (region::m_cached_init_sval_at_main): New field.
            (decl_region::decl_region): Initialize m_ctor_svalue.
            (decl_region::calc_svalue_for_constructor): New decl.
            (decl_region::m_ctor_svalue): New field.

    (cherry picked from commit r14-1664-gfe9771b59f576f)

    Signed-off-by: David Malcolm <dmalcolm@redhat.com>

[Bug analyzer/110112] [11/12 Regression] gcc -fanalyzer takes an excessive amount of time

[dmalcolm at gcc dot gnu.org]

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

David Malcolm <dmalcolm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11/12/13 Regression] gcc   |[11/12 Regression] gcc
                   |-fanalyzer takes an         |-fanalyzer takes an
                   |excessive amount of time    |excessive amount of time

--- Comment #7 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Should be fixed for GCC 13 (for the upcoming GCC 13.3) by the above patch.

Keeping open to track backporting to older branches.