Re: [PATCH] Fix PR66313

[Joseph Myers <joseph@codesourcery.com>]

On Thu, 29 Oct 2015, Richard Biener wrote:

> We still regress gcc.dg/tree-ssa/tailrecursion-6.c with it though.
> There we have
> 
> int
> foo (int a)
> {
>         if (a)
>                 return a * (2 * (foo (a - 1))) + a + 1;
>         else
>                 return 0;
> }
> 
> and tailrecursion detection requires the expression to be
> in the form (2 * (foo (a - 1)) + 1) * a + 1 but folding
> can't see that (2 * (foo (a - 1)) + 1) might not be INT_MIN
> when a is -1.  Well, I can't trivially either, maybe its
> just because of the recursion or maybe it's because here
> we are sure that C in C * A is odd (2 * sth + 1) or
> simply because we know that C in (B + C)*A is positive
> and non-zero?
> 
> But I guess for the isolated view of the
> a * (2 * X) + a expression we can't factor it using signed
> arithmetic because of the a == 0 case as then the sum
> might trivially overflow (of course here a is not zero
> because of the guard...)

In that isolated view, a transformation a * (2 * X) + a -> 
a * (2 * X + 1) is always safe (because Y + 1 only overflows when Y is 
INT_MAX, which is odd, so adding 1 to 2 * X cannot overflow).  That could 
be generalized to cover a * (C * X) + a * D (for C constant, D positive 
constant) if (INT_MAX % C) >= D, and similarly for negative constants.  
I've no idea if such transformations are useful outside this test.

[Safe = not introducing overflows, but might lose them which is a 
consideration for sanitization.]

-- 
Joseph S. Myers
joseph@codesourcery.com