On 01/25/2017 11:09 PM, Marc Glisse wrote:
On Wed, 25 Jan 2017, Jeff Law wrote:
As has been discussed extensively, we're not doing a good job at
simplifying overflow tests, particularly those which collapse down to
an EQ/NE test.
x + -1 > x -> x == 0
x + -1 < x -> x != 0
x + 1 < x -> x == -1U
x + 1 > x -> x != -1U
The simplifications allow us to propagate a constant for X into one
ARM of the associated IF/ELSE construct. For C++ std::vector
operations those propagations can eliminate lots of unnecessary code.
Those propagations also eliminate (by way of removing unnecessary
code) false positive warnings for memset calls that come from
std::vector operations.
This patch does two things.
1. It adds special case patterns to the A+CST CMP A pattern for cases
where CST is 1 or -1 where the result turns into A EQ/NE 0 or A EQ/NE
-1U. These special patterns are applied regardless of the single_use
status of the expression.
2. It adds a call to fold_stmt in simplify_cond_using_ranges. This
allows VRP to transform the code early and the first DOM pass to often
see the simpified conditional and thus optimize better, rather than
waiting for forwprop3 to simplify the conditional and the last DOM
pass to optimize the code.
Bootstrapped and regression tested on x86_64-linux-gnu. OK for the
trunk?
I assume this causes a regression for code like
unsigned f(unsigned a){
unsigned b=a+1;
if(b<a)return 42;
return b;
}
Yes. The transformation ruins the conversion into ADD_OVERFLOW for the
+- 1 case. However, ISTM that we could potentially recover the
ADD_OVERFLOW in phi-opt. It's a very simple pattern that would be
presented to phi-opt, so it might not be terrible to recover -- which
has the advantage that if a user wrote an optimized overflow test we'd
be able to recover ADD_OVERFLOW for it.
? On the other hand, the optimization is already very fragile, if I
write b<=a (which is equivalent since 1 != 0), it doesn't apply.
True, the existing ADD_OVERFLOW is missing this case.
Note that if we use my pattern and tried to recover ADD_OVERFLOW in
phi-opt, both the b<a and b<=a look the same, so we'd catch both.
We currently get
addl $1, %edi
movl $42, %eax
cmovnc %edi, %eax
or almost as good with b==0
movl %edi, %eax
movl $42, %edx
addl $1, %eax
cmove %edx, %eax
while with a==-1 we have the redundant comparison
leal 1(%rdi), %eax
cmpl $-1, %edi
movl $42, %edx
cmove %edx, %eax
Simplifying x + 1 < x to x + 1 == 0 might not be enough to simplify your
examples though I guess?
It's an interesting idea. But x+1 == 0 will get canonicalized back into
x == -1.
But it does raise an interesting idea that I only briefly pondered. We
could perhaps do back-propagation to arrive at a known value for x in
one arm of the conditional. That may be enough. And DOM already has
some ability to do that kind of back propagation.
So given:
_1 = _13 + 18446744073709551615;
if (_1 > _13)
goto <bb 4>; [29.56%]
else
goto <bb 27>; [70.44%]
DOM could see the conditional 1 > 13. Walk the use-def chain to the
assignment of _1 to see what values for _1 would make the condition
true. The only value that satisfies is _13 == 0. Then it would enter
_13 = 0 into its const/copies table for the duration of the THEN
conditional.
That leaves the conditional alone, so presumably it would still be seen
as ADD_OVERFLOW later, but gets the const propagation into the THEN arm
that we need.
It seems worthwhile enough to play with.
jeff
