This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH][RFA][PR tree-optimization/79095] Improve overflow test optimization and avoid invalid warnings


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]