Re: [patch] for PR 26900

[Richard Guenther <rguenther at suse dot de>]

On Sat, 10 Feb 2007, Zdenek Dvorak wrote:

> Hello,

I will look at the patch in more detail later, but first some
observations I made from trying to tackle this PR myself in the past.

> 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

These conditions are built from tree_simplify_using_condition_1 here:

  /* Check whether COND ==> EXPR.  */
  notcond = invert_truthvalue (cond);
  e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
  if (e && integer_nonzerop (e))
    return e;

  /* Check whether COND ==> not EXPR.  */
  e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
  if (e && integer_zerop (e))
    return e;

did you find any other places that would benefit from the transformations
implemented by the patch - apart from user written code, of course?

The above cases try to implement simplifying a (single) conditional
in the context of another conditional that is known to be true.  That's
basically a poor mans VRP.

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

This is what I figured out as well - in particular we cannot fold
the conditions the above code generates for the testcase in PR26900,
one reason is that canonicalization of conditions like x + 1 > y
to x >= y loses information (that x + 1 does not overflow).

> Therefore, I have written a separate functions to fold the pair of
> inequalities in two variables.

I was thinking of re-using parts of VRP to track the symbolic value
ranges the loop header copies present.  I just didn't manage to
get around massaging enough of VRP to be reusable.

Richard.

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