Re: [patch] for PR 26900

[Richard Guenther <rguenther at suse dot de>]

On Fri, 16 Feb 2007, Zdenek Dvorak wrote:

> Hello,
> 
> > > to get rid of the assumptions for # of iterations of the loop in this
> > > PR, we need to be able to fold expressions like
> > > 
> > > x <= y + 1 && x - 1 > y
> > > 
> > > to false (of course assuming that the arithmetics does not overflow,
> > > otherwise the conditions may be satisfied by x == INT_MIN).
> > > 
> > > Another class of comparisons that we currently do not simplify is
> > > 
> > > x > y + 10 && x > y + 20
> > > 
> > > which is equivalent to just x > y + 20.
> > > 
> > > Originally, I thought I might be able to rewrite the inequalities as x -
> > > y <= 1 && x - y > 1 and use fold_range_test (the transformation itself
> > > is invalid, since it may introduce overflows, but thought that as long
> > > as I am only interested in true/false return values, I won't mind).
> > > However, this transformation may break things -- x <= y + INT_MAX is a
> > > nontrivial inequality, while x - y <= INT_MAX is always true.
> > > 
> > > Therefore, I have written a separate functions to fold the pair of
> > > inequalities in two variables.
> > 
> > See below for comments.  I think the overall idea is sound, but I'm
> > worried we get some corner cases wrong.  For example we can fold
> > 
> >   i1 + 1 >= i0 && i0 - 1 > i1
> > 
> > to false only because we know that changing the second term to
> > i0 > i1 + 1 will not introduce overflow that was not there before.
> > As you are canonicalizing comparisons i1 + cst1 CMP i2 + cst2 to
> > i1 - i2 CMP cst2 - cst1 we seem to lose the information on which
> > overflows we had seen already and which not.  Can you convince me
> > that there are no corner cases we get wrong with your patch?
> 
> the transformation to i1 - i2 CMP cst2 - cst1 is interpreted as if
> performed in unbounded precision, i.e., with its mathematical meaning.
> Note that we check TREE_OVERFLOW everywhere, to ensure that the
> transformations are correct.

That didn't really answer my question - of course we can check if
cst2 - cst1 overflows.  But we cannot check if i1 - i2 overflows
(but we can assume that i1 + 1 and i0 - 1 do not overflow).  My question
is whether we use more than the assumptions we can derive from the
_original_ expressions about overflow in later transformations that lead
to the folding result?

> > > + /* Tries to determine with what sign a simple term X appears in TERM.  If it
> > > +    succeeds, *SIGN is set to true if the X appears positively and to false if
> > > +    it appears negated, and true is returned.  Otherwise, false is returned.  */
> > > + static bool
> > > + sign_of_subterm_1 (tree term, tree x, bool *sign)
> > > + {
> > ...
> > > + }
> > > + 
> > > + /* Tries to determine with what sign SUBTERM appears in TERM.  If it succeeds,
> > > +    *SIGN is set to true if the SUBTERM appears positively and to false if
> > > +    it appears negated, and true is returned.  Otherwise, false is returned.  */
> > > + 
> > > + static bool
> > > + sign_of_subterm (tree term, tree subterm, bool *sign)
> > > + {
> > ...
> > > + }
> > 
> > These functions sound too generic, as far as I can see they are
> > used to invert a - b to b - a if the other comparison looked like that.
> > Why not simply ...
> > 
> > > +   /* The comparison is now in shape XL cmp XR + *R.  Move both variable
> > > +      terms to the left-hand side.  */
> > > + 
> > > +   if (xr)
> > > +     {
> > > +       if (xl)
> > > + 	*l = fold_build2 (MINUS_EXPR, type, xl, xr);
> > > +       else
> > > + 	*l = fold_build1 (NEGATE_EXPR, type, xr);
> > > +     }
> > 
> > ... canonicalize based on the DECL_UID of xl/xr here?
> 
> because xl/xr do not have to be DECLs.

Even in the set of testcases you included?  I see that 
simplify_using_condition is using expand_simple_operations on the
comparisons, so it should be easy to construct a testcase that
excercises the more complex parts?

Did you check what is the compile-time impact of this patch?

> > > + 
> > > +   /* If the variable appears negated in VAR, negate the whole expression.  */
> > > +   if (sign_of_subterm (var, *l, &positive)
> > > +       && !positive)
> > > +     {
> > > +       *l = fold_build1 (NEGATE_EXPR, type, *l);
> > > +       *r = fold_unary (NEGATE_EXPR, type, *r);
> > > +       if (TREE_OVERFLOW (*r))
> > > + 	return false;
> > > +       *cmp = swap_tree_comparison (*cmp);
> > > +     }
> > > + 
> > > +   return true;
> > > + }
> > 
> > static bool
> > separate_term (tree term, tree *x, tree *cst)
> > {
> >   tree op0, op1, type = TREE_TYPE (term);
> > 
> >   *x = term;
> >   *cst = build_int_cst (type, 0);
> > 
> >   if (TREE_CODE (term) == PLUS_EXPR)
> >     {
> >       op0 = TREE_OPERAND (term, 0);
> >       op1 = TREE_OPERAND (term, 1);
> >       if (TREE_CODE (op1) == INTEGER_CST)
> >         {
> >           *x = op0;
> >           *cst = op1;
> >         }
> >       else
> >         {
> >           *x = term;
> >           *cst = build_int_cst (type, 0);
> >         }
> > 
> > Does this happen?  Why not
> > 
> > static void
> > separate_term (tree term, tree *x, tree *cst)
> > {
> >   if (TREE_CODE (term) == PLUS_EXPR)
> >       && TREE_CODE (TREE_OPERAND (term, 1)) == INTEGER_CST)
> >     {
> >       *x = TREE_OPERAND (term, 0);
> >       *cst = TREE_OPERAND (term, 1);
> >     }
> >   else
> >     {
> >       *x = term;
> >       *cst = build_int_cst (TREE_TYPE (term), 0);
> >     }
> > }
> > 
> > which always succeeds (we canonicalize x - cst to x + -cst if -cst does
> > not overflow).
> 
> because this does not handle the case cst - x.

Hm, right.

Richard.

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs