[Bug c++/118069] g++ hangs during constraint subsumption

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-14 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:83646dd4859b8c64b63a5b441c1673a3db5ccdaf

commit r14-11113-g83646dd4859b8c64b63a5b441c1673a3db5ccdaf
Author: Patrick Palka <ppalka@redhat.com>
Date:   Thu Dec 19 12:00:29 2024 -0500

    c++: integer overflow during constraint subsumption [PR118069]

    For the testcase in the PR we hang during constraint subsumption
    ultimately because one of the constraints is complex enough that its
    conjunctive normal form is calculated to have more than 2^31 clauses,
    which causes the size calculation (through an int) to overflow and so
    the optimization in subsumes_constraints_nonnull

      if (dnf_size (lhs) <= cnf_size (rhs))
        // iterate over DNF of LHS
      else
        // iterate over CNF of RHS

    incorrectly decides to loop over the CNF (>> billions of clauses)
    instead of the DNF (thousands of clauses).

    I haven't verified that the result of cnf_size is correct for the
    problematic constraint but integer overflow is definitely plausible
    given that CNF/DNF can be exponentially larger than the original
    constraint in the worst case.

    This patch fixes this by using 64-bit saturating arithmetic during
    these size calculations (via new add/mul_sat_hwi functions) so that
    overflow is less likely and if it does occur we handle it gracefully.
    It should be highly unlikely that both the DNF and CNF sizes overflow,
    and if they do then it doesn't matter which form we select, subsumption
    will take forever either way.  The testcase now compiles in ~3 seconds
    on my machine after this change.

            PR c++/118069

    gcc/ChangeLog:

            * hwint.h (add_sat_hwi): New function.
            (mul_sat_hwi): Likewise.

    gcc/cp/ChangeLog:

            * logic.cc (dnf_size_r): Use HOST_WIDE_INT instead of int, and
            handle overflow gracefully via add_sat_hwi and mul_sat_hwi.
            (cnf_size_r): Likewise.
            (dnf_size): Use HOST_WIDE_INT instead of int.
            (cnf_size): Likewise.

    Reviewed-by: Jason Merrill <jason@redhat.com>
    (cherry picked from commit 875f14e15d49dce7de501a6357a3d5811b5c36d4)