On Tue, 17 Dec 2024, Marek Polacek wrote: > On Tue, Dec 17, 2024 at 10:43:49AM -0500, Patrick Palka wrote: > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look > > OK for trunk? Shall we also backport this to release branches? > > It's not a regression but seems like a safe fix for an inconvenient > > issue. > > > > -- >8 -- > > > > For the testcase in the PR we hang during constraint normalization > > 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 a 64-bit unsigned int during DNF/CNF size > > calculation which is enough to avoid overflow in the testcase, and we now > > compile it in ~3 seconds. > > Sorry for a silly question, but is there a reason to prefer > unsigned HOST_WIDE_INT over uint64_t?
Using HOST_WIDE_INT seems to be the more common practice, probably for historical reasons. It seems neither u?int64_t nor long long are used anywhere in the C++ FE currently, though they are used in other parts of the compiler though so I guess it'd be fine to start using them in the C++ FE. > > Patch seems fine, though, thanks. > > > In theory doubling the precision will only let us handle a ~2x bigger > > constraint before risking overflow in the worst case given the > > exponential-ness, but I suppose it should suffice for now. > > > > PR c++/118069 > > > > gcc/cp/ChangeLog: > > > > * logic.cc (dnf_size_r): Use unsigned HOST_WIDE_INT instead of int. > > (cnf_size_r): Likewise. > > (dnf_size): Likewise. > > (cnf_size): Likewise. > > --- > > gcc/cp/logic.cc | 24 ++++++++++++------------ > > 1 file changed, 12 insertions(+), 12 deletions(-) > > > > diff --git a/gcc/cp/logic.cc b/gcc/cp/logic.cc > > index fab2c357dc4..e46ea0ebb78 100644 > > --- a/gcc/cp/logic.cc > > +++ b/gcc/cp/logic.cc > > @@ -349,7 +349,7 @@ atomic_p (tree t) > > distributing. In general, a conjunction for which this flag is set > > is considered a disjunction for the purpose of counting. */ > > > > -static std::pair<int, bool> > > +static std::pair<unsigned HOST_WIDE_INT, bool> > > dnf_size_r (tree t) > > { > > if (atomic_p (t)) > > @@ -360,9 +360,9 @@ dnf_size_r (tree t) > > the results. */ > > tree lhs = TREE_OPERAND (t, 0); > > tree rhs = TREE_OPERAND (t, 1); > > - std::pair<int, bool> p1 = dnf_size_r (lhs); > > - std::pair<int, bool> p2 = dnf_size_r (rhs); > > - int n1 = p1.first, n2 = p2.first; > > + auto p1 = dnf_size_r (lhs); > > + auto p2 = dnf_size_r (rhs); > > + unsigned HOST_WIDE_INT n1 = p1.first, n2 = p2.first; > > bool d1 = p1.second, d2 = p2.second; > > > > if (disjunction_p (t)) > > @@ -457,7 +457,7 @@ dnf_size_r (tree t) > > distributing. In general, a disjunction for which this flag is set > > is considered a conjunction for the purpose of counting. */ > > > > -static std::pair<int, bool> > > +static std::pair<unsigned HOST_WIDE_INT, bool> > > cnf_size_r (tree t) > > { > > if (atomic_p (t)) > > @@ -468,9 +468,9 @@ cnf_size_r (tree t) > > the results. */ > > tree lhs = TREE_OPERAND (t, 0); > > tree rhs = TREE_OPERAND (t, 1); > > - std::pair<int, bool> p1 = cnf_size_r (lhs); > > - std::pair<int, bool> p2 = cnf_size_r (rhs); > > - int n1 = p1.first, n2 = p2.first; > > + auto p1 = cnf_size_r (lhs); > > + auto p2 = cnf_size_r (rhs); > > + unsigned HOST_WIDE_INT n1 = p1.first, n2 = p2.first; > > bool d1 = p1.second, d2 = p2.second; > > > > if (disjunction_p (t)) > > @@ -560,10 +560,10 @@ cnf_size_r (tree t) > > /* Count the number conjunctive clauses that would be created > > when rewriting T to DNF. */ > > > > -static int > > +static unsigned HOST_WIDE_INT > > dnf_size (tree t) > > { > > - std::pair<int, bool> result = dnf_size_r (t); > > + auto result = dnf_size_r (t); > > return result.first == 0 ? 1 : result.first; > > } > > > > @@ -571,10 +571,10 @@ dnf_size (tree t) > > /* Count the number disjunctive clauses that would be created > > when rewriting T to CNF. */ > > > > -static int > > +static unsigned HOST_WIDE_INT > > cnf_size (tree t) > > { > > - std::pair<int, bool> result = cnf_size_r (t); > > + auto result = cnf_size_r (t); > > return result.first == 0 ? 1 : result.first; > > } > > > > -- > > 2.48.0.rc0 > > > > Marek > >