[Bug analyzer/96653] New: Compile time and memory hog w/ -O1 -fanalyzer

[Bug analyzer/96653] New: Compile time and memory hog w/ -O1 -fanalyzer

[asolokha at gmx dot com]

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

            Bug ID: 96653
           Summary: Compile time and memory hog w/ -O1 -fanalyzer
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog, memory-hog
          Severity: normal
          Priority: P3
         Component: analyzer
          Assignee: dmalcolm at gcc dot gnu.org
          Reporter: asolokha at gmx dot com
  Target Milestone: ---

Created attachment 49068
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49068&action=edit
Testcase

gcc-11.0.0-alpha20200816 snapshot (g:c99116aeeb9644ebddec653ee8b19de4d38b65bd)
takes indefinite time and consumes ever-increasing amount of memory when
compiling the attached testcase, preprocessed and reduced from
drivers/media/v4l2-core/v4l2-ctrls.c from Linux 5.9-rc1, w/ -O1 -fanalyzer:

% timeout 60 gcc-11.0.0 -O1 -fanalyzer -c cdkkdewb.c
zsh: exit 124   timeout 60 gcc-11.0.0 -O1 -fanalyzer -c cdkkdewb.c

Typical profiles captured by perf top at different time:

  72.47%  cc1  [.] ana::constraint_manager::add_constraint_internal
  25.53%  cc1  [.] ana::constraint::implied_by
   0.80%  cc1  [.] ana::constraint_manager::get_equiv_class_by_svalue
   0.45%  cc1  [.] ana::constraint_manager::eval_condition
   0.20%  cc1  [.] ana::constraint_manager::validate
   0.15%  cc1  [.] ana::constraint_manager::eval_condition
   0.10%  cc1  [.] ana::constraint_manager::get_or_add_equiv_class
   0.10%  cc1  [.] fold_binary_loc
   0.07%  cc1  [.] ana::constraint_manager::get_ec_bounds
   0.07%  cc1  [.] tree_strip_sign_nop_conversions
   0.02%  cc1  [.] wi::lts_p<generic_wide_int<wi::extended_tree<192> >,
generic_wide_int<wi::extended_tree<192> > >
   0.02%  cc1  [.] tree_int_cst_equal

                 * * *

  48.80%  cc1           [.] ana::constraint_manager::add_constraint_internal
  25.31%  cc1           [.] ana::constraint_manager::get_equiv_class_by_svalue
  17.42%  cc1           [.] ana::constraint::implied_by
   1.40%  cc1           [.] qsort_chk
   0.95%  cc1           [.] ana::constraint_cmp
   0.62%  cc1           [.] fold_binary_loc
   0.55%  cc1           [.] cmp2to3
   0.55%  cc1           [.] ana::constraint_manager::hash
   0.55%  cc1           [.] ana::constraint_manager::eval_condition
   0.40%  cc1           [.] ana::constraint_manager::eval_condition
   0.32%  cc1           [.] hash_table<default_hash_traits<ana::equiv_class
const*>, false, xcallocator>::find_slot_with_hash
   0.30%  cc1           [.] mergesort<sort_ctx>
   0.27%  cc1           [.] ana::constraint_manager::validate
   0.22%  cc1           [.] ana::constraint_manager::eval_condition
   0.17%  cc1           [.] ana::constraint_manager::for_each_fact
   0.17%  cc1           [.] fold_relational_const
   0.17%  cc1           [.] ana::constraint_manager::get_ec_bounds
   0.15%  cc1           [.] const_binop
   0.15%  cc1           [.] ana::svalue::unwrap_any_unmergeable
   0.15%  cc1           [.] tree_int_cst_lt
   0.15%  libc-2.32.so  [.] memcpy@@GLIBC_2.14
   0.12%  cc1           [.] tree_strip_sign_nop_conversions
   0.12%  cc1           [.] ana::constant_svalue::get_kind
   0.12%  cc1           [.] wi::extended_tree<192>::extended_tree
   0.10%  cc1           [.] wi::lts_p<generic_wide_int<wi::extended_tree<192>
>, generic_wide_int<wi::extended_tree<192> > >
   0.10%  cc1           [.] constant_boolean_node
   0.10%  cc1           [.] ana::constraint_manager::constraint_manager
   0.07%  cc1           [.] ana::svalue::dyn_cast_unmergeable_svalue
   0.07%  cc1           [.] ana::constraint_manager::get_or_add_equiv_class
   0.07%  cc1           [.] ana::constraint_manager::canonicalize
   0.05%  cc1           [.] ana::equiv_class_cmp
   0.02%  libc-2.32.so  [.] _int_malloc
   0.02%  cc1           [.] ana::constraint_manager::operator==
   0.02%  cc1           [.] tree_int_cst_equal
   0.02%  cc1           [.] wi::eq_p<generic_wide_int<wi::extended_tree<192> >,
generic_wide_int<wi::extended_tree<192> > >
   0.02%  libc-2.32.so  [.] unlink_chunk.constprop.0
   0.02%  cc1           [.] ana::store::can_merge_p
   0.02%  cc1           [.] memcpy@plt
   0.02%  cc1           [.] cmp1<sort_ctx>
   0.02%  cc1           [.]
ana::constraint_manager::purge<ana::dead_svalue_purger>
   0.02%  cc1           [.] ana::store::canonicalize

[Bug analyzer/96653] Compile time and memory hog w/ -O1 -fanalyzer

[dmalcolm at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2020-08-18

--- Comment #1 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
Thanks for filing this bug; confirmed.

Appears to be creating many thousands of constraints; I think it's adding a
constraint for every pair of constants for all constants in the switch
statements, and thus O(N^2) constraints, where N is the number of constants, or
something similar.  Gah.

[Bug analyzer/96653] Compile time and memory hog w/ -O1 -fanalyzer

[cvs-commit at gcc dot gnu.org]

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

--- Comment #2 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:799dd4e10047a4aa772fd69c910c5c6a96c36b9f

commit r11-3190-g799dd4e10047a4aa772fd69c910c5c6a96c36b9f
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Thu Sep 10 21:23:38 2020 -0400

    analyzer: fix constraint explosion on many-cased switch [PR96653]

    PR analyzer/96653 reports a CPU-time and memory explosion in -fanalyzer
    seen in Linux 5.9-rc1:drivers/media/v4l2-core/v4l2-ctrls.c on a switch
    statement with many cases.

    The issue is some old code in constraint_manager::get_or_add_equiv_class
    for ensuring that comparisons between equivalence classes containing
    constants work correctly.  The old code added constraints for every
    pair of ECs containing constants, leading to O(N^2) constraints (for
    N constants).  Given that get_or_add_equiv_class also involves O(N)
    comparisons, this led to at least O(N^3) CPU time, and O(N^2) memory
    consumption when handling the "default" case, where N is the number of
    other cases in the switch statement.

    The state rewrite of r11-2694-g808f4dfeb3a95f50f15e71148e5c1067f90a126d
    added checking for comparisons between constants, making these explicit
    constraints redundant, but failed to remove the code mentioned above.

    This patch removes it, fixing the blow-up of constraints in the default
    case.

    gcc/analyzer/ChangeLog:
            PR analyzer/96653
            * constraint-manager.cc
            (constraint_manager::get_or_add_equiv_class): Don't accumulate
            transitive closure of all constraints on constants.

    gcc/testsuite/ChangeLog:
            PR analyzer/96653
            * gcc.dg/analyzer/pr96653.c: New test.

[Bug analyzer/96653] -Wanalyzer-too-complex on very large switch statement

[dmalcolm at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Compile time and memory hog |-Wanalyzer-too-complex on
                   |w/ -O1 -fanalyzer           |very large switch statement

--- Comment #3 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
The compile-time/memory blow-up should be fixed by above commit.

However, I had to add -Wno-analyzer-too-complex to the testcase.  Keeping this
bug open to track that (updating bug title accordingly).

[Bug analyzer/96653] -Wanalyzer-too-complex on very large switch statement

[cvs-commit at gcc dot gnu.org]

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

--- 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:fd111c419d146ee47c7df9a36a535e8d843d4802

commit r11-3247-gfd111c419d146ee47c7df9a36a535e8d843d4802
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Wed Sep 16 09:22:06 2020 -0400

    analyzer: fix state explosions due to SCC bug

    Debugging the state explosion of the very large switch statement in
    gcc.dg/analyzer/pr96653.c showed that the worklist was failing to
    order the exploded nodes correctly; the in-edges at the join point
    after the switch were not getting processed together, but were instead
    being rocessed in smaller batches, bloating the exploded graph until the
    per-point limit was reached.

    The root cause turned out to be a bug in creating the strongly-connected
    components for the supergraph: the code was considering interprocedural
    edges as well as intraprocedural edges, leading to unpredictable
    misorderings of the SCC and worklist, leading to bloating of the
    exploded graph.

    This patch fixes the SCC creation so it only considers intraprocedural
    edges within the supergraph.  It also tweaks worklist::key_t::cmp to
    give higher precedence to call_string over differences within a
    supernode, since enodes with different call_strings can't be merges.
    In practise, none of my test cases were affected by this latter change,
    though it seems to be the right thing to do.

    With this patch, the very large switch statement in
    gcc.dg/analyzer/pr96653.c is handled in a single call to
    exploded_graph::maybe_process_run_of_before_supernode_enodes:
       merged 358 in-enodes into 2 out-enode(s) at SN: 402
    and that testcase no longer hits the per-program-point limits.

    gcc/analyzer/ChangeLog:
            * engine.cc (strongly_connected_components::strong_connect): Only
            consider intraprocedural edges when creating SCCs.
            (worklist::key_t::cmp): Add comment.  Treat call_string
            differences as more important than differences of program_point
            within a supernode.

    gcc/testsuite/ChangeLog:
            PR analyzer/96653
            * gcc.dg/analyzer/loop-0-up-to-n-by-1-with-iter-obj.c: Update
            expected number of exploded nodes.
            * gcc.dg/analyzer/malloc-vs-local-1a.c: Update expected number
            of exploded nodes.
            * gcc.dg/analyzer/pr96653.c: Remove -Wno-analyzer-too-complex.

[Bug analyzer/96653] -Wanalyzer-too-complex on very large switch statement

[dmalcolm at gcc dot gnu.org]

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

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

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

--- Comment #5 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
(In reply to David Malcolm from comment #3)
> The compile-time/memory blow-up should be fixed by above commit.
> 
> However, I had to add -Wno-analyzer-too-complex to the testcase.  Keeping
> this bug open to track that (updating bug title accordingly).

This is fixed by r11-3247-gfd111c419d146ee47c7df9a36a535e8d843d4802; marking as
resolved.

[Bug analyzer/96653] -Wanalyzer-too-complex on very large switch statement

[dmalcolm at gcc dot gnu.org]

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

--- Comment #6 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
With a release build:

$ hyperfine -L ana "","-fanalyzer" "./xgcc -B. -S pr96653.c -O1 {ana}"
Benchmark #1: ./xgcc -B. -S pr96653.c -O1 
  Time (mean ± σ):     127.3 ms ±   0.7 ms    [User: 111.3 ms, System: 14.8 ms]
  Range (min … max):   126.1 ms … 128.7 ms    23 runs

Benchmark #2: ./xgcc -B. -S pr96653.c -O1 -fanalyzer
  Time (mean ± σ):     246.3 ms ±   1.2 ms    [User: 221.9 ms, System: 22.6 ms]
  Range (min … max):   244.5 ms … 248.7 ms    12 runs

Summary
  './xgcc -B. -S pr96653.c -O1 ' ran
    1.94 ± 0.01 times faster than './xgcc -B. -S pr96653.c -O1 -fanalyzer'

[Bug analyzer/96653] -Wanalyzer-too-complex on very large switch statement

[dmalcolm at gcc dot gnu.org]

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

--- Comment #7 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
(which is within my rough goal of -fanalyzer doubling your compile time in
return for more warnings)