[Bug analyzer/107943] New: gcc -fanalyzer hangs in openssl curve25519.c

[Bug analyzer/107943] New: gcc -fanalyzer hangs in openssl curve25519.c

[bernd.edlinger at hotmail dot de]

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

            Bug ID: 107943
           Summary: gcc -fanalyzer hangs in openssl curve25519.c
           Product: gcc
           Version: 12.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: bernd.edlinger at hotmail dot de
  Target Milestone: ---

I see a reproducible endless loop in analyzing openssl-1.1.1s
gcc  -I. -Iinclude -fPIC -pthread -m64 -Wa,--noexecstack -Wall -O3 -fanalyzer
-DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_CPUID_OBJ
-DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5
-DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DKECCAK1600_ASM
-DRC4_ASM -DMD5_ASM -DAESNI_ASM -DVPAES_ASM -DGHASH_ASM -DECP_NISTZ256_ASM
-DX25519_ASM -DPOLY1305_ASM -DOPENSSLDIR="\"/usr/local/ssl\""
-DENGINESDIR="\"/usr/local/lib/engines-1.1\"" -DNDEBUG  -MMD -MF
crypto/ec/curve25519.d.tmp -MT crypto/ec/curve25519.o -c -o
crypto/ec/curve25519.o crypto/ec/curve25519.c

observed with: gcc-12.2.1 and gcc-13.0.0
working version: gcc-11.3.1

trying to bisect that now.

[Bug analyzer/107943] gcc -fanalyzer hangs in openssl curve25519.c

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2022-12-01
     Ever confirmed|0                           |1
                 CC|                            |marxin at gcc dot gnu.org

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Can you please provide a pre-processed source file so that I can quickly bisect
it and reduce it? Thanks.

[Bug analyzer/107943] gcc -fanalyzer hangs in openssl curve25519.c

[bernd.edlinger at hotmail dot de]

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

--- Comment #2 from Bernd Edlinger <bernd.edlinger at hotmail dot de> ---
Created attachment 53998
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53998&action=edit
preprocessed source file

[Bug analyzer/107943] gcc -fanalyzer hangs in openssl curve25519.c

[bernd.edlinger at hotmail dot de]

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

--- Comment #3 from Bernd Edlinger <bernd.edlinger at hotmail dot de> ---
this is how far I got with bisecting:

$ git bisect log 
git bisect start
# good: [885f5c3d5763d46e02bd2f192765cb589b4c4fe4] Daily bump.
git bisect good 885f5c3d5763d46e02bd2f192765cb589b4c4fe4
# bad: [24b8b44ea3bc232f4fe8daf24900ccaca98e8280] Daily bump.
git bisect bad 24b8b44ea3bc232f4fe8daf24900ccaca98e8280
# good: [250f234988b6231669a720c52101d3686d645072] testsuite: Fix up
gcc.target/s390/zero-scratch-regs-1.c
git bisect good 250f234988b6231669a720c52101d3686d645072

[Bug analyzer/107943] [11/12/13 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|gcc -fanalyzer hangs in     |[11/12/13 Regression] gcc
                   |openssl curve25519.c        |-fanalyzer hangs in openssl
                   |                            |curve25519.c since
                   |                            |r11-3840-gaf66094d03779377
             Status|WAITING                     |NEW
           Keywords|                            |needs-reduction

--- Comment #4 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r11-3840-gaf66094d03779377.

[Bug analyzer/107943] [11/12/13 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[marxin at gcc dot gnu.org]

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

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
Created attachment 54000
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54000&action=edit
Partially reduced test-case

[Bug analyzer/107943] [11/12/13 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[bernd.edlinger at hotmail dot de]

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

--- Comment #6 from Bernd Edlinger <bernd.edlinger at hotmail dot de> ---
I don't know if that is relevant or not,
but I was using a slighthly different criterion in bisection.
I used .../configure --prefix=... --enable-languages=all
and defined the bad criterion using the unreduced test case
compilation took >10 minutes on Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
The original test case is available as follows:

$ wget https://www.openssl.org/source/openssl-1.1.1s.tar.gz
$ tar xf openssl-1.1.1s.tar.gz
$ ./config -fanalyzer
$ make

With this pointed to a different commit:
r12-7615-gc5288df751f

Author: Roger Sayle <roger@nextmovesoftware.com>
Date:   Fri Mar 11 17:46:50 2022 +0000

    PR tree-optimization/98335: Improvements to DSE's compute_trims.

    This patch is the main middle-end piece of a fix for PR tree-opt/98335,
    which is a code-quality regression affecting mainline.  The issue occurs
    in DSE's (dead store elimination's) compute_trims function that determines
    where a store to memory can be trimmed.  In the testcase given in the
    PR, this function notices that the first byte of a DImode store is dead,
    and replaces the 8-byte store at (aligned) offset zero, with a 7-byte store
    at (unaligned) offset one.  Most architectures can store a power-of-two
    bytes (up to a maximum) in single instruction, so writing 7 bytes requires
    more instructions than writing 8 bytes.  This patch follows Jakub Jelinek's
    suggestion in comment 5, that compute_trims needs improved heuristics.

beginning with this version the original test case, enters
a steady state after 2 minutes (observed with top:
VIRT=196296 RES=170872 SHR=21992  %CPU=100,0) and has no
progress for at least 20 hours, before I killed it.
The reduced test case does not exhibit this behaviour,
and runs just for some seconds.

But I agree that the r11-3840-gaf66094d03779377 is also special
and made the compile time raise from 0 to 2-10 minutes, however
I would not have opened this issue for that, since I was believing
there is something expensive to check that just did not give
a result in the end.

[Bug analyzer/107943] [11/12/13 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.4

[Bug analyzer/107943] [11/12/13 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Samples: 193K of event 'cycles', Event count (approx.): 206254655627            
Overhead       Samples  Command  Shared Object     Symbol                       
  12.11%         23476  cc1      cc1               [.]
ana::store_manager::get_concrete_binding
   9.71%         18828  cc1      cc1               [.]
hash_table<hash_map<ana::concrete_binding, ana::concrete_binding*,
simple_hashmap_traits<default_hash_traits<ana::concrete_binding>,
ana::concrete_binding*> >::hash_entry, false, xcallocator>::find_with_hash
   6.73%         13045  cc1      cc1               [.]
hash_table<hash_map<ana::binding_key const*, ana::svalue const*,
simple_hashmap_traits<default_hash_traits<ana::binding_key const*>, ana::svalue
const*> >::hash_entry, false, xcallocator>::find_slot_with_hash
   5.64%         10937  cc1      libc-2.31.so      [.] _int_malloc
   5.20%         10087  cc1      cc1               [.]
ana::region_model_manager::get_or_create_constant_svalue
   5.06%          9815  cc1      libc-2.31.so      [.] _int_free
   4.84%          9380  cc1      cc1               [.]
hash_table<hash_map<ana::binding_key const*, ana::svalue const*,
simple_hashmap_traits<default_hash_traits<ana::binding_key const*>, ana::svalue
const*> >::hash_entry, false, xcallocator>::expand
   4.63%          8971  cc1      cc1               [.]
hash_table<hash_map<ana::element_region::key_t, ana::element_region*,
simple_hashmap_traits<default_hash_traits<ana::element_region::key_t>,
ana::element_region*> >::hash_entry, false, xcallocator>::find_with_hash
   4.59%          8886  cc1      cc1               [.] iterative_hash
   3.30%          6396  cc1      cc1               [.]
ana::binding_cluster::bind_compound_sval
   2.58%          4995  cc1      cc1               [.] ana::store::~store
   2.19%          4250  cc1      cc1               [.]
hash_table<hash_map<ana::binding_key const*, ana::svalue const*,
simple_hashmap_traits<default_hash_traits<ana::binding_key const*>, ana::svalue
const*> >::hash_entry, false, xcallocator>::find_with_hash

looks like for larger workloads it gets memory bound - optimizing data
structures (and hash functions?) might be helpful.

[Bug analyzer/107943] [11/12/13 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2022-12-01 00:00:00         |2023-3-30
      Known to fail|                            |13.0

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Re-confirmed on trunk btw.  I killed cc1 after 55min (release checking build)

[Bug analyzer/107943] [11/12/13 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu.org
           Priority|P3                          |P2

[Bug analyzer/107943] [11/12/13/14 Regression] gcc -fanalyzer hangs in openssl curve25519.c since r11-3840-gaf66094d03779377

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.4 is being released, retargeting bugs to GCC 11.5.