Re: [PATCH] Constant fold -A - B as -B - A (take 2)

[Richard Earnshaw <rearnsha at arm dot com>]

> Fortunately, "-A - B" -> "-B - A" is a mathematical identity that
> is not affected by them.  For example, if at the tree-level, we'd
> assumed that the operation would operate on signed characters, and
> B could take the value -128, we'd expect a signed overflow.  If
> optabs is forced the promote this operation to "ints" or "longs",
> the operation no longer overflows, but it does produce identical
> results.
> 
> As an example of an "unsafe transformation", I'll draw one from the
> other code you refer to:
> 
> 	for (signed char i=126; i!=-126; i++)
> 	  foo ();
> 
> In this case, the programmer is illegally infering a behaviour from
> from signed overflow.  If the compiler has to promote the type of i
> to an integer (e.g. char has more bits that the programmer was expecting),
> clearly foo is called a different number of times.  At the RTL-level,
> this isn't a problem, it knows how many times the loop will iterate for
> "char" or "int" or "long" and can always unroll the loop, it'll just
> unroll it a different number of times on different platforms.

No, although the behaviour of the above is undefined, I don't think doing 
intermediate calculations at a higher precision should alter the number of 
times the above loop is iterated over.  However, clearly you would get 
different behaviour on a machine with 9-bit chars or on a machine that 
implemented ones' complement arithmetic.

I think it's time to go back to the mathematics of what we mean by an 
optimization (this is going to be fun on an ASCII character set :-)

Let N be the set of integer values that we define operations on (eg the C 
type "int").  Let X, Y and Z be variables that can hold any value in N.

Now let us define a function signedN(X) which takes as an argument any 
integral value and reduces it to the set N.

Now the normal C expression

	p = q + r

in reality means

	p = signedN (q + r)

and with the proviso that q and r are already in the set N.

In more general terms when it comes to optimizations we can replace any 
function f() with a simpler function f'() provided that it gives the same 
result for every possible input value that can occur.  That is

	Z = f (X, Y)

can be optimized to

	Z = f' (X, Y)

if 
	f (X, Y) == f' (X, Y) 

for all X, Y in N.  This is just a mathematical expression of the "as-if" 
rule.

Now, provided that we do not need to expose any intermediate values from 
the above transformation, it is perfectly safe *even if some of those 
intermediate values are not technically in the legal domain for the 
initial values and result*.

Now the question at issue here is whether the expression

	Z = signedN (signedN (-X) - Y)

can be replaced with the expression

	Z = signedN (signedN (-Y) - X)

ie, are there any combinations of X and Y that lead to a different result 
for Z, given that signedN means in this case reduction to 2's complement 
form with a fixed number of bits and no saturation.

Now since the answer to this question is "no" (though I'm not about to try 
and prove that here), then the optimization is safe.  However, this is 
given the proviso mentioned above, which effectively has two parts:

1) We might want to look at intermediate parts of the transformed input 
(in order to intuit other things about the values involved)
2) Some of those intermediate values are not strictly in the legal domain 
of N (in this particular case the bit pattern where only the top bit is 
set is being used to represent INT_MAX+1 rather than INT_MIN)

There is also a third proviso, but I think we've already discussed that: 
if the operations performed may trap and the transformed version will trap 
under different conditions, then the transformation is not valid either 
(this is really just exposure of intermediate values expressed in another 
way).

So Roger's assertion that the transformation is safe at a mathematical 
level is correct; but the issue really is whether we might infer something 
about the possible domain of values that X and Y might have that would 
affect how we would transform some other bits of code -- I can't think of 
anything off hand, but then I don't know all the ins and outs of the 
compiler.

R.