Bug 56719 - missed optimization: i > 0xffff || i*4 > 0xffff
missed optimization: i > 0xffff || i*4 > 0xffff
Status: NEW
Product: gcc
Classification: Unclassified
Component: middle-end
4.7.2
: P3 normal
: ---
Assigned To: Not yet assigned to anyone
: missed-optimization
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2013-03-25 11:27 UTC by felix-gcc
Modified: 2013-03-25 16:01 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2013-03-25 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description felix-gcc 2013-03-25 11:27:43 UTC
This is the test code:

int foo(unsigned int i) {
  if (i > 0xffff || i*4 > 0xffff)
    baz();
}

gcc -O2 generates a cmp, a shift, and another cmp.

Why does this not generate a single cmp with 0x3fff?
Comment 1 Kai Tietz 2013-03-25 11:41:15 UTC
0x3fff is wrong as 0x3fff * 4 is just 0xfffc.  So proper optimization here is i > 0x3fffu.  That is a missed opportunity in VRP.
Comment 2 Richard Biener 2013-03-25 12:21:21 UTC
I don't think this has anything to do with VRP.  VRP does not propagate
"backwards", that is, optimize away the first compare in

  if (i > 0xffff)
    if (i*4 > 0xffff)

from ranges derived from a compare following it.

This is a missed optimization in fold instead.  Not sure if practically
relevant though.
Comment 3 felix-gcc 2013-03-25 14:41:10 UTC
@comment 1: maybe it's me but that does not make any sense.  3fff is wrong and the correct value is 3fff?  Huh?

@comment 2: I extracted this code from a piece of commercial production software compiled with gcc.  Not sure where you draw the line but to me that makes it relevant :-)
Comment 4 Richard Biener 2013-03-25 14:55:45 UTC
(In reply to comment #3)
> @comment 2: I extracted this code from a piece of commercial production
> software compiled with gcc.  Not sure where you draw the line but to me that
> makes it relevant :-)

Did it occur in this simplified form, that is, as a single if statement?
Comment 5 felix-gcc 2013-03-25 15:06:02 UTC
Yes.  However I'd hope that fixing this case would mean that gcc also catches the case where it is split to multiple if statements.

I think this statement came about because they had a range check and someone pointed out that checking foo*4>0xffff could be circumvented via an integer overflow if foo is untrusted and very large.

There are smarter ways to do this but it's not completely mind-bogglingly incomprehensible why this code would come about.

I have in fact been advocating for a while that programmers should rather spell out their security checks as plainly as possible and let the compiler optimize them and remove superfluous checks.  See

  http://www.fefe.de/source-code-optimization.pdf

if you are interested.
Comment 6 Jakub Jelinek 2013-03-25 15:25:53 UTC
This actually isn't about optimizing away the first compare, but about merging the two conditions into one that is equivalent to those two ored together.
The first condition is for range of i [0x10000U, 0xffffffffU] while the latter for ranges [0x4000U, 0x3fffffffU] or [0x40004000U, 0x7fffffffU] or [0x80004000U, 0xbfffffffU] or [0xc0004000U, 0xfffffffU], and all the 5 ranges together are
[0x4000U, 0xffffffffU].
Perhaps optimize_range_tests (or its fold-const.c counterpart) could both do it, but the really ugly thing is that either we'd need to expand i*4 into 4 range tests and teach the code that those 4 are really already represented by one range tests and thus an optimization would be only if we can even fewer range tests than that (with some cap on number of ranges we'd generate, like 8-16 or so), or have some way to mark some range fuzzy (i.e. in that range we don't know if it is in the range or out of it), and represent i*4 > 0xffffU as
[0x4000, 0x3fffffffU] range ored with fuzzy range [0x40004000U, 0xffffffffU].
Fuzzy range would then be treated for | as only optimizable if other non-fuzzy ranges together completely cover that range (and for & that non-fuzzy ranges anded together don't cover any of the values in the fuzzy range).

Anyway, I agree with Richard that it is questionable how often this would actually hit in real-world code, i.e. whether this really is something to spend lots of work on.
Comment 7 felix-gcc 2013-03-25 16:01:14 UTC
I filed this bug because I was under the impression that gcc was already supposed to optimize this out as part of the value range optimizations.

You probably know better than me whether the required effort would be disproportionate.  I'd still vote for supporting this case because then I can go around and tell people to worry about writing readable code instead of worrying about code that the compiler will compile well.