Re: [patch] for PR 26900

[Richard Guenther <rguenther at suse dot de>]

On Fri, 16 Feb 2007, Zdenek Dvorak wrote:

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

Ok, thanks.

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

Hm, but we require later in analyzing that the arbitrary subexpressions
match.  So we would for example have

 D.42_1 = 2 * i1_3;
 D.43_1 = D.42_1 + 1;
 if (D.43_1 > 0)  /* loop header copy */
   {
     do {
     } while (...)
   }

and now simplify_using_condition asks if D.43_1 < 0.  I would expect
we don't expand all the way down to 2 * i1_3.  Indeed if modifying
the testcase for PR29600 we ask only to simplify
D.1625_15 + 1 >= i0_4(D) && i0_4(D) + -1 > D.1625_15
for which we have
D.1625_15 = i1_6(D) * 2;
If I change the bound to 2*i1 (without the plus) we don't expand
that either and get
i0_4(D) <= D.1625_14 && i0_4(D) > D.1625_14
Even 2*(i1+1) or 2*(i1+i0+1)+1 does not make it more complex than
name + CST.

Maybe you are more successful in finding a testcase that ends
up calling fold_two_comparisons with more complex expressions
(single-line handwritten does not count! ;))

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

That's good enough.  We always can find artificial testcases, but
as my tries on expansion above showed the expression complexity
is limited.

Richard.

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