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

Reply via email to