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
jos...@codesourcery.com
