[Bug analyzer/105112] New: Speed up -fanalyzer on big-code.c

[Bug analyzer/105112] New: Speed up -fanalyzer on big-code.c

[dmalcolm at gcc dot gnu.org]

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

            Bug ID: 105112
           Summary: Speed up -fanalyzer on big-code.c
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: dmalcolm at gcc dot gnu.org
  Target Milestone: ---

Several large functions with arithmetics and one-deep loops, posted by Michael
Matz to gcc-patches:

    https://gcc.gnu.org/ml/gcc-patches/2013-09/msg00062.html

Also at:
https://github.com/davidmalcolm/gcc-benchmarking/blob/master/test-sources/big-code.c

-ftime-report shows that -fanalyzer increases compile time (without
optimizations) from 6 seconds to 30 seconds, almost all of which is spent
processing the worklist:

[...snip...]
 analyzer                           :   0.61 (  2%)   0.01 (  1%)   0.63 (  2%)
    0  (  0%)
 analyzer: supergraph               :   0.04 (  0%)   0.02 (  2%)   0.06 (  0%)
    0  (  0%)
 analyzer: state purge              :   0.57 (  2%)   0.05 (  5%)   0.62 (  2%)
    0  (  0%)
 analyzer: planning                 :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
    0  (  0%)
 analyzer: processing worklist      :  23.91 ( 82%)   0.50 ( 50%)  24.55 ( 80%)
   24M ( 12%)
 TOTAL                              :  29.32          1.00         30.51       
  200M

-Wanalyzer-too-complex shows that it eventually starts giving up.

The analyzer isn't going to have anything interesting to report on this code;
hopefully there are ways for it to go faster for this example.

[Bug analyzer/105112] Speed up -fanalyzer on big-code.c

[dmalcolm at gcc dot gnu.org]

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

--- Comment #1 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Example state (picked at random from -fdump-analyzer-exploded-nodes-2 output):

EN 113734:
preds: EN: 113733
succs: EN: 113735
callstring: []
before (SN: 12511 stmt: 0): 
if (j_8254 <= 8191)
31 |   for (j = 0; j < 8192; j++) { \
   |               ~~^~~~~~

rmodel:
stack depth: 1
  frame (index 0): frame: ‘func_schar’@1
clusters within root region
  cluster for: (*INIT_VAL(a_8725(D)))
    ESCAPED
    TOUCHED
    key:   {byte 0}
    value: ‘unsigned char’ {(CAST(unsigned char, CONJURED(_7228 = get_i ();,
(*INIT_VAL(a_8725(D)))))+(CAST(unsigned char, CONJURED(_7228 = get_i ()
;, (*INIT_VAL(b_8726(D)))))*CAST(unsigned char, CONJURED(_7228 = get_i ();,
(*INIT_VAL(c_8727(D)))))))}
    key:   {byte 1}
    value: ‘signed char’ {UNKNOWN(signed char)}
  cluster for: (*INIT_VAL(b_8726(D))): UNKNOWN(schar) (ESCAPED) (TOUCHED)
  cluster for: (*INIT_VAL(c_8727(D))): UNKNOWN(schar) (ESCAPED) (TOUCHED)
clusters within frame: ‘func_schar’@1
  cluster for: i_8127: CONJURED(i_8707 = get_i ();, i_8707)
  cluster for: accum_8740: UNKNOWN(schar)
  cluster for: z_7997: UNKNOWN(schar)
  cluster for: x_7611: UNKNOWN(schar)
  cluster for: y_7867: UNKNOWN(schar)
  cluster for: j_8254: WIDENING({after SN: 12510}, (int)1, (int)2)
m_called_unknown_fn: TRUE
constraint_manager:
  equiv classes:
    ec0: {(int)0 == [m_constant]‘0’}
    ec1: {(void *)0B == [m_constant]‘0B’}
    ec2: {INIT_VAL(a_8725(D))}
    ec3: {INIT_VAL(b_8726(D))}
    ec4: {INIT_VAL(c_8727(D))}
    ec5: {CONJURED(i_8707 = get_i ();, i_8707)}
  constraints:
    0: ec2: {INIT_VAL(a_8725(D))} != ec1: {(void *)0B == [m_constant]‘0B’}
    1: ec3: {INIT_VAL(b_8726(D))} != ec1: {(void *)0B == [m_constant]‘0B’}
    2: ec4: {INIT_VAL(c_8727(D))} != ec1: {(void *)0B == [m_constant]‘0B’}
    3: ec5: {CONJURED(i_8707 = get_i ();, i_8707)} != ec0: {(int)0 ==
[m_constant]‘0’}

[Bug analyzer/105112] Speed up -fanalyzer on big-code.c

[dmalcolm at gcc dot gnu.org]

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

--- Comment #2 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
FWIW, "perf report" shows that these are the top items in the profile:

8.72%  libc-2.31.so  [.] _int_malloc
6.68%  libc-2.31.so  [.] _int_free
2.91%  cc1           [.] ana::binding_map::binding_map
2.76%  libc-2.31.so  [.] __memset_sse2_unaligned_erms
2.52%  cc1           [.] hash_table<default_hash_traits<ana::svalue const*>,
false, xcallocator>::find_slot_with_hash
2.52%  cc1           [.] ana::reachable_regions::add
2.45%  libc-2.31.so  [.] malloc
2.37%  cc1           [.] hash_table<default_hash_traits<ana::region const*>,
false, xcallocator>::find_slot_with_hash
1.98%  libc-2.31.so  [.] __libc_calloc
1.87%  libc-2.31.so  [.] cfree@GLIBC_2.2.5
1.71%  cc1           [.] hash_table<hash_map<ana::region const*,
ana::binding_cluster*, simple_hashmap_traits<default_hash_
1.70%  cc1           [.] ana::region_model::get_reachable_svalues
1.50%  cc1           [.] hash_table_higher_prime_index
1.42%  cc1           [.] ana::store::~store
1.39%  cc1           [.] hash_table<default_hash_traits<ana::region const*>,
false, xcallocator>::find_with_hash
1.33%  cc1           [.] ana::sm_state_map::clone
1.33%  cc1           [.] ana::store::canonicalize
1.25%  cc1           [.] ana::store::get_cluster
1.22%  cc1           [.] ana::store::escaped_p
1.10%  cc1           [.] ana::function_point::hash
1.09%  cc1           [.] iterative_hash
1.06%  cc1           [.] ana::store::store
0.95%  cc1           [.] ana::reachable_regions::init_cluster
0.94%  libc-2.31.so  [.] malloc_consolidate
0.86%  cc1           [.] hash_table<default_hash_traits<ana::function_point>,
false, xcallocator>::find_with_hash
0.80%  cc1           [.] ana::reachable_regions::handle_sval
0.79%  libc-2.31.so  [.] unlink_chunk.constprop.0
0.79%  cc1           [.] ana::region::get_base_region
0.75%  cc1           [.] ana::region_model::~region_model
0.73%  cc1           [.] xcalloc
0.72%  cc1           [.] ana::program_state::prune_for_point
0.69%  cc1           [.] ana::svalue::live_p
0.69%  cc1           [.] ana::constraint_manager::canonicalize
0.68%  cc1           [.] record_reg_classes
0.65%  cc1           [.] ana::store::get_any_binding
0.64%  cc1           [.] ana::sm_state_map::on_liveness_change
0.64%  cc1           [.] ana::decl_region::get_kind
0.55%  cc1           [.] hash_table<default_hash_traits<ana::region const*>,
false, xcallocator>::expand
0.52%  cc1           [.] ana::binding_cluster::can_merge_p
0.50%  cc1           [.] ana::sm_state_map::get_state

[Bug analyzer/105112] Speed up -fanalyzer on big-code.c

[dmalcolm at gcc dot gnu.org]

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

--- Comment #3 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Possible simplification: don't try to model floating-point operations e.g. any
binop on a floating point value has unknown_svalue as the result, so that
complicated floating-point computations can be quickly handled with a "we don't
care" value.   (though do we care about tainted divisors for floating-point?)