Zdenek Dvorak - Re: [patch] for PR 26900 (original) (raw)

This is the mail archive of the gcc-patches@gcc.gnu.orgmailing list for the GCC project.

• From: Zdenek Dvorak
• To: Richard Guenther
• Cc: gcc-patches at gcc dot gnu dot org
• Date: Fri, 16 Feb 2007 14:46:10 +0100
• Subject: Re: [patch] for PR 26900
• References: <20070210200651.GA6389@atrey.karlin.mff.cuni.cz> <Pine.LNX.4.64.0702161342510.18923@zhemvz.fhfr.qr>

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.

• }

• if (swapped)

• {

•   tmp = *i1_subset_i2; *i1_subset_i2 = *i2_subset_i1; *i2_subset_i1 = tmp;

Please use separate lines (above, too).

I somewhat like to put swap on single line, since it is just one operation. I have tried to find what the coding standard says about that, but it does not seem to mention putting one statement per line at all.

• /* 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.

+

• /* 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.

Zdenek

• Follow-Ups:
  • Re: [patch] for PR 26900
    * From: Richard Guenther
• References:
  • [patch] for PR 26900
    * From: Zdenek Dvorak
  • Re: [patch] for PR 26900
    * From: Richard Guenther