public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
@ 2023-05-18 0:43 richard.yao at alumni dot stonybrook.edu
2023-05-18 0:56 ` [Bug tree-optimization/109901] " pinskia at gcc dot gnu.org
` (8 more replies)
0 siblings, 9 replies; 10+ messages in thread
From: richard.yao at alumni dot stonybrook.edu @ 2023-05-18 0:43 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
Bug ID: 109901
Summary: Optimization opportunity: ((((a) > (b)) - ((a) < (b)))
< 0) -> ((a) < (b))
Product: gcc
Version: 14.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: middle-end
Assignee: unassigned at gcc dot gnu.org
Reporter: richard.yao at alumni dot stonybrook.edu
Target Milestone: ---
LLVM/Clang also misses this optimization opportunity, so I also filed an issue
with them:
https://github.com/llvm/llvm-project/issues/62790
The following transformations can be done as an optimization:
((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
((((a) > (b)) - ((a) < (b))) <= 0) -> ((a) <= (b))
((((a) > (b)) - ((a) < (b))) == -1) -> ((a) < (b))
((((a) > (b)) - ((a) < (b))) == 1) -> ((a) > (b))
((((a) > (b)) - ((a) < (b))) == 0) -> ((a) == (b))
((((a) > (b)) - ((a) < (b))) > 0) -> ((a) > (b))
((((a) > (b)) - ((a) < (b))) >= 0) -> ((a) >= (b))
((((a) >= (b)) - ((a) <= (b))) < 0) -> ((a) < (b))
((((a) >= (b)) - ((a) <= (b))) <= 0) -> ((a) <= (b))
((((a) >= (b)) - ((a) <= (b))) == -1) -> ((a) < (b))
((((a) >= (b)) - ((a) <= (b))) == 1) -> ((a) > (b))
((((a) >= (b)) - ((a) <= (b))) == 0) -> ((a) == (b))
((((a) >= (b)) - ((a) <= (b))) > 0) -> ((a) > (b))
((((a) >= (b)) - ((a) <= (b))) >= 0) -> ((a) >= (b))
Both (((a) > (b)) - ((a) < (b))) and (((a) >= (b)) - ((a) <= (b))) will
generate -1, 0 or 1 when comparing two integers (signed or unsigned). When
comparators using this trick are inlined into the caller, the above
transformations become applicable.
I noticed that neither compiler exploits this high level optimization
opportunity when I was working on using a faster binary search implementation
for the OpenZFS b-tree code. It relied on a macro to achieve C++-style inlining
of the comparator into the implementation by making different versions of the
same function.
The following example at godbolt does not use a macro to make it easier to see
which lines of assembly correspond to which lines of high level C:
https://gcc.godbolt.org/z/cdedccxae
On amd64, GCC generates 15 instructions for the loop. If you comment out line
35 and uncomment line 37, GCC will generate 11 instructions for the loop. This
is the output GCC would produce if it supported that high level optimization.
Had the comparator returned 1 for less than and 0 for greater than or equal to,
we would have had the 11-instruction version of the loop without any need for
this optimization. Changing the semantics because our compilers lack this
optimization would be painful in part because the entire code base expects the
-1, 0 or 1 return value semantics and other code depends on these comparators.
It would be nice if GCC implemented this optimization.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
@ 2023-05-18 0:56 ` pinskia at gcc dot gnu.org
2023-05-18 1:07 ` pinskia at gcc dot gnu.org
` (7 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-18 0:56 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Component|middle-end |tree-optimization
Severity|normal |enhancement
Keywords| |missed-optimization
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
2023-05-18 0:56 ` [Bug tree-optimization/109901] " pinskia at gcc dot gnu.org
@ 2023-05-18 1:07 ` pinskia at gcc dot gnu.org
2023-05-18 1:08 ` pinskia at gcc dot gnu.org
` (6 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-18 1:07 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
See Also| |https://gcc.gnu.org/bugzill
| |a/show_bug.cgi?id=101807,
| |https://gcc.gnu.org/bugzill
| |a/show_bug.cgi?id=101703
--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.
Basically the rule is
bool0 - bool1 < 0 -> !bool0 & bool1 -> bool1 < bool0
bool0 - bool1 == -1 -> !bool0 & bool1 -> bool1 < bool0
bool0 - bool1 == 0 -> !bool0 & !bool1 -> !(bool0 | bool1)
bool0 - bool1 == 1 -> bool0 & !bool1 -> bool0 < bool1
bool0 - bool1 > 0 -> bool0 & !bool1 -> bool0 < bool1
and see if that reduces.
Note
!bool0 & bool1 -> bool1 < bool0 (see PR 101807 for the opposite there)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
2023-05-18 0:56 ` [Bug tree-optimization/109901] " pinskia at gcc dot gnu.org
2023-05-18 1:07 ` pinskia at gcc dot gnu.org
@ 2023-05-18 1:08 ` pinskia at gcc dot gnu.org
2023-05-18 1:11 ` pinskia at gcc dot gnu.org
` (5 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-18 1:08 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Last reconfirmed| |2023-05-18
Status|UNCONFIRMED |NEW
Ever confirmed|0 |1
--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
` (2 preceding siblings ...)
2023-05-18 1:08 ` pinskia at gcc dot gnu.org
@ 2023-05-18 1:11 ` pinskia at gcc dot gnu.org
2023-05-18 1:12 ` pinskia at gcc dot gnu.org
` (4 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-18 1:11 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #1)
> bool0 - bool1 == 0 -> !bool0 & !bool1 -> !(bool0 | bool1)
Sorry I messed this one up:
bool0 - bool1 == 0 -> (bool0 & bool1) | (!bool0 & !bool1)
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
` (3 preceding siblings ...)
2023-05-18 1:11 ` pinskia at gcc dot gnu.org
@ 2023-05-18 1:12 ` pinskia at gcc dot gnu.org
2023-05-18 1:13 ` pinskia at gcc dot gnu.org
` (3 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-18 1:12 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> (In reply to Andrew Pinski from comment #1)
> > bool0 - bool1 == 0 -> !bool0 & !bool1 -> !(bool0 | bool1)
> Sorry I messed this one up:
> bool0 - bool1 == 0 -> (bool0 & bool1) | (!bool0 & !bool1)
or rather just bool0 == bool1
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
` (4 preceding siblings ...)
2023-05-18 1:12 ` pinskia at gcc dot gnu.org
@ 2023-05-18 1:13 ` pinskia at gcc dot gnu.org
2023-05-18 1:43 ` richard.yao at alumni dot stonybrook.edu
` (2 subsequent siblings)
8 siblings, 0 replies; 10+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-18 1:13 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
See Also| |https://gcc.gnu.org/bugzill
| |a/show_bug.cgi?id=107881
--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> (In reply to Andrew Pinski from comment #3)
> > (In reply to Andrew Pinski from comment #1)
> > > bool0 - bool1 == 0 -> !bool0 & !bool1 -> !(bool0 | bool1)
> > Sorry I messed this one up:
> > bool0 - bool1 == 0 -> (bool0 & bool1) | (!bool0 & !bool1)
>
> or rather just bool0 == bool1
Which then that makes it related to PR 107881 too.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
` (5 preceding siblings ...)
2023-05-18 1:13 ` pinskia at gcc dot gnu.org
@ 2023-05-18 1:43 ` richard.yao at alumni dot stonybrook.edu
2023-05-18 4:12 ` richard.yao at alumni dot stonybrook.edu
2023-05-27 3:33 ` richard.yao at alumni dot stonybrook.edu
8 siblings, 0 replies; 10+ messages in thread
From: richard.yao at alumni dot stonybrook.edu @ 2023-05-18 1:43 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
--- Comment #6 from Richard Yao <richard.yao at alumni dot stonybrook.edu> ---
(In reply to Andrew Pinski from comment #1)
> bool0 - bool1 == 1 -> bool0 & !bool1 -> bool0 < bool1
> bool0 - bool1 > 0 -> bool0 & !bool1 -> bool0 < bool1
That should be:
bool0 - bool1 == 1 -> bool0 & !bool1 -> bool0 > bool1
bool0 - bool1 > 0 -> bool0 & !bool1 -> bool0 > bool1
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
` (6 preceding siblings ...)
2023-05-18 1:43 ` richard.yao at alumni dot stonybrook.edu
@ 2023-05-18 4:12 ` richard.yao at alumni dot stonybrook.edu
2023-05-27 3:33 ` richard.yao at alumni dot stonybrook.edu
8 siblings, 0 replies; 10+ messages in thread
From: richard.yao at alumni dot stonybrook.edu @ 2023-05-18 4:12 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
--- Comment #7 from Richard Yao <richard.yao at alumni dot stonybrook.edu> ---
Two more rules:
bool0 - bool1 >= 0 -> bool0 | !bool1 -> bool1 >= bool0
bool0 - bool1 <= 0 -> !bool0 | bool1 -> bool0 <= bool1
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug tree-optimization/109901] Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
` (7 preceding siblings ...)
2023-05-18 4:12 ` richard.yao at alumni dot stonybrook.edu
@ 2023-05-27 3:33 ` richard.yao at alumni dot stonybrook.edu
8 siblings, 0 replies; 10+ messages in thread
From: richard.yao at alumni dot stonybrook.edu @ 2023-05-27 3:33 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109901
--- Comment #8 from Richard Yao <richard.yao at alumni dot stonybrook.edu> ---
Created attachment 55177
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55177&action=edit
Source code for micro-benchmark.
Here is an example of how not having this optimization slows us down:
https://gcc.godbolt.org/z/nxdrb17G7
custom_binary_search_slow() and custom_binary_search_fast() are the same
function. The only difference is that I manually applied the ((((a) > (b)) -
((a) < (b))) <= 0) -> ((a) <= (b)) transformation to see what GCC would
generate if it were able to do this transformation.
This optimization alone makes binary search ~78% faster on my Ryzen 7 5800X:
Benchmark: array size: 1024, runs: 1000, repetitions: 10000, seed: 1685158101,
density: 10
Even distribution with 1024 32 bit integers, random access
| Name | Items | Hits
| Misses | Time |
| ---------- | ---------- | ----------
| ---------- | ---------- |
| custom_binary_search_slow | 1024 | 983
| 9017 | 0.000313 |
| custom_binary_search_fast | 1024 | 983
| 9017 | 0.000176 |
I modified the microbenchmark from scandum/binary_search to better suit a
workload that I am micro-optimizing:
https://github.com/scandum/binary_search
In specific, I wanted to test on small arrays, but avoid cache effects
contaminating the results. One could easily add the search functions from my
modified version into the original to get get numbers for bigger array sizes.
I have attached the source code for the modified micro-benchmark. The above run
was done after compiling with -O2 -fno-inline. Compiling with just -O2 does not
make much difference, since I deleted the code where -fno-inline makes a
difference from that file since it was not relevant to this issue.
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2023-05-27 3:33 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-05-18 0:43 [Bug middle-end/109901] New: Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b)) richard.yao at alumni dot stonybrook.edu
2023-05-18 0:56 ` [Bug tree-optimization/109901] " pinskia at gcc dot gnu.org
2023-05-18 1:07 ` pinskia at gcc dot gnu.org
2023-05-18 1:08 ` pinskia at gcc dot gnu.org
2023-05-18 1:11 ` pinskia at gcc dot gnu.org
2023-05-18 1:12 ` pinskia at gcc dot gnu.org
2023-05-18 1:13 ` pinskia at gcc dot gnu.org
2023-05-18 1:43 ` richard.yao at alumni dot stonybrook.edu
2023-05-18 4:12 ` richard.yao at alumni dot stonybrook.edu
2023-05-27 3:33 ` richard.yao at alumni dot stonybrook.edu
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).