[patch] for PR 26900

[Zdenek Dvorak]

Hello,

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

sorry if I was unclear.  Both "-"-ses in the transformation are
performed in the unbounded precision, i.e., without overflows.
Note that we do not really compute the difference i1 - i2, this is
just a justification of correctness.

Formally, suppose that cst2-cst1, i1 + cst1 and i2 + cst2  do not overflow (in the limited
precision).  Then,

i1 + cst1 cmp i2 + cst2 (both computations are performed in limited
  precision)

is equivalent to

i1 + cst1 cmp i2 + cst2 (both computations are performed in unbounded
  precision)

which in turn is equivalent to

i1 - i2 cmp cst2 - cst1 (both computations are performed in unlimited
   precision; since cst2 - cst1 do not overflow, for the rhs it does not
   matter).

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

no, in general.  You can replace the variables by arbitrary
subexpresions.  For example, I guess if in the testcase for PR 29600
the upper bound is replaced by 2*i1 + 1, we would need to handle
more complicated expressions than just DECLs/SSA_NAMEs.

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

Do you expect any?  I can probably create artificial testcases where
this simplification takes long time (if you create a huge expressions,
then operand_equal_p will be slow), but that is true for most of the
fold.

More concretely, there is no measurable compile-time impact on
gcc compilation.

Zdenek