public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug c++/101240] New: [missed optimization] Transitivity of less-than and less-or-equal
@ 2021-06-28 12:03 kyrylo.bohdanenko at gmail dot com
2021-06-29 7:01 ` [Bug tree-optimization/101240] " rguenth at gcc dot gnu.org
` (4 more replies)
0 siblings, 5 replies; 6+ messages in thread
From: kyrylo.bohdanenko at gmail dot com @ 2021-06-28 12:03 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101240
Bug ID: 101240
Summary: [missed optimization] Transitivity of less-than and
less-or-equal
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c++
Assignee: unassigned at gcc dot gnu.org
Reporter: kyrylo.bohdanenko at gmail dot com
Target Milestone: ---
Consider the following C++ code
#define ALWAYS_TRUE(x) do { if (x) __builtin_unreachable(); } while (false)
int divide(int a, int b) {
ALWAYS_TRUE(a == b);
return a / b;
}
void test_array(unsigned (&arr)[3]) {
ALWAYS_TRUE(a[0] < a[1] && a[1] < a[2]);
return a[0] < a[2];
}
The first function is optimiozed away:
divide(int, int):
mov eax, 1
ret
While the second still does the comparison:
test_array(unsigned int (&) [3]):
mov eax, DWORD PTR [rdi+8]
cmp DWORD PTR [rdi], eax
setb al
ret
It would be nice if GCC could deduce that
a < b && b < c --> a < c
And optimize that second function (provided no other UB is involved)
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/101240] [missed optimization] Transitivity of less-than and less-or-equal
2021-06-28 12:03 [Bug c++/101240] New: [missed optimization] Transitivity of less-than and less-or-equal kyrylo.bohdanenko at gmail dot com
@ 2021-06-29 7:01 ` rguenth at gcc dot gnu.org
2021-06-29 7:04 ` rguenth at gcc dot gnu.org
` (3 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-06-29 7:01 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101240
Richard Biener <rguenth at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Blocks| |85316
Last reconfirmed| |2021-06-29
CC| |amacleod at redhat dot com
Status|UNCONFIRMED |NEW
Ever confirmed|0 |1
--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
EVRP sees
<bb 2> :
_1 = (*a_8(D))[0];
_2 = (*a_8(D))[1];
if (_1 < _2)
goto <bb 3>; [INV]
else
goto <bb 5>; [INV]
<bb 3> :
_4 = (*a_8(D))[2];
if (_2 < _4)
goto <bb 4>; [INV]
else
goto <bb 5>; [INV]
<bb 4> :
__builtin_unreachable ();
<bb 5> :
_6 = (*a_8(D))[2];
_9 = _1 < _6;
so predicate analysis should handle this (but it does not). Btw, I fixed
the testcase for you:
#define ALWAYS_TRUE(x) do { if (x) __builtin_unreachable(); } while (false)
bool test_array(unsigned (&a)[3]) {
ALWAYS_TRUE(a[0] < a[1] && a[1] < a[2]);
return a[0] < a[2];
}
Referenced Bugs:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316
[Bug 85316] [meta-bug] VRP range propagation missed cases
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/101240] [missed optimization] Transitivity of less-than and less-or-equal
2021-06-28 12:03 [Bug c++/101240] New: [missed optimization] Transitivity of less-than and less-or-equal kyrylo.bohdanenko at gmail dot com
2021-06-29 7:01 ` [Bug tree-optimization/101240] " rguenth at gcc dot gnu.org
@ 2021-06-29 7:04 ` rguenth at gcc dot gnu.org
2021-11-05 21:31 ` amacleod at redhat dot com
` (2 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-06-29 7:04 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101240
--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Note will require a VRP pass after PRE since only there we'll be able to
CSE the a[2] load.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/101240] [missed optimization] Transitivity of less-than and less-or-equal
2021-06-28 12:03 [Bug c++/101240] New: [missed optimization] Transitivity of less-than and less-or-equal kyrylo.bohdanenko at gmail dot com
2021-06-29 7:01 ` [Bug tree-optimization/101240] " rguenth at gcc dot gnu.org
2021-06-29 7:04 ` rguenth at gcc dot gnu.org
@ 2021-11-05 21:31 ` amacleod at redhat dot com
2021-11-05 22:04 ` aldyh at gcc dot gnu.org
2023-07-13 18:27 ` pinskia at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: amacleod at redhat dot com @ 2021-11-05 21:31 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101240
Andrew Macleod <amacleod at redhat dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |aldyh at redhat dot com
--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
in VRP2 we see:
<bb 2> [local count: 1073741824]:
_1 = (*a_6(D))[0];
_2 = (*a_6(D))[1];
pretmp_8 = (*a_6(D))[2];
if (_1 < _2)
goto <bb 3>; [50.00%]
else
goto <bb 5>; [50.00%]
<bb 3> [local count: 536870913]:
if (_2 < pretmp_8)
goto <bb 4>; [0.00%]
else
goto <bb 5>; [100.00%]
<bb 4> [count: 0]:
__builtin_unreachable ();
<bb 5> [local count: 1073741824]:
_7 = _1 < pretmp_8;
return _7;
There isnt much VRP can do about this because if we take the path 2->5, we have
no way of resolving _1 < pretmp_8 because the comparison has not been made yet.
interestingly, if this were to be threaded,
2->3 would register _1 < _2
3->5 would register _2 >= ptrtmp_8
then in bb5' _1 < pretmp_8 should be answered by the path oracle as TRUE and
then be folded to return true. at least it should :-)
I guess the next question would be... why doesn't the threader think this is
worth threading?
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/101240] [missed optimization] Transitivity of less-than and less-or-equal
2021-06-28 12:03 [Bug c++/101240] New: [missed optimization] Transitivity of less-than and less-or-equal kyrylo.bohdanenko at gmail dot com
` (2 preceding siblings ...)
2021-11-05 21:31 ` amacleod at redhat dot com
@ 2021-11-05 22:04 ` aldyh at gcc dot gnu.org
2023-07-13 18:27 ` pinskia at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: aldyh at gcc dot gnu.org @ 2021-11-05 22:04 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101240
Aldy Hernandez <aldyh at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |aldyh at gcc dot gnu.org
--- Comment #4 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #3)
> in VRP2 we see:
>
> <bb 2> [local count: 1073741824]:
> _1 = (*a_6(D))[0];
> _2 = (*a_6(D))[1];
> pretmp_8 = (*a_6(D))[2];
> if (_1 < _2)
> goto <bb 3>; [50.00%]
> else
> goto <bb 5>; [50.00%]
>
> <bb 3> [local count: 536870913]:
> if (_2 < pretmp_8)
> goto <bb 4>; [0.00%]
> else
> goto <bb 5>; [100.00%]
>
> <bb 4> [count: 0]:
> __builtin_unreachable ();
>
> <bb 5> [local count: 1073741824]:
> _7 = _1 < pretmp_8;
> return _7;
>
> There isnt much VRP can do about this because if we take the path 2->5, we
> have no way of resolving _1 < pretmp_8 because the comparison has not been
> made yet.
>
> interestingly, if this were to be threaded,
> 2->3 would register _1 < _2
> 3->5 would register _2 >= ptrtmp_8
> then in bb5' _1 < pretmp_8 should be answered by the path oracle as TRUE
> and then be folded to return true. at least it should :-)
>
> I guess the next question would be... why doesn't the threader think this is
> worth threading?
The threader only looks at paths that end in a block with multiple exits:
FOR_EACH_BB_FN (bb, m_fun)
if (EDGE_COUNT (bb->succs) > 1)
maybe_thread_block (bb);
so...a switch or a cond.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug tree-optimization/101240] [missed optimization] Transitivity of less-than and less-or-equal
2021-06-28 12:03 [Bug c++/101240] New: [missed optimization] Transitivity of less-than and less-or-equal kyrylo.bohdanenko at gmail dot com
` (3 preceding siblings ...)
2021-11-05 22:04 ` aldyh at gcc dot gnu.org
@ 2023-07-13 18:27 ` pinskia at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-07-13 18:27 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101240
--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
here is a better testcase:
```
int test_array(unsigned (&a)[3]) {
int t = (a[0]+a[1]+a[2]);
ALWAYS_TRUE(a[0] < a[1] && a[1] < a[2]);
return (a[0] < a[2])+t;
}
```
(just to make sure VRP is only dealing with SSA names).
We should be able to optimize the above to just
return a[0]+a[1]+a[2]+1;
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2023-07-13 18:27 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-06-28 12:03 [Bug c++/101240] New: [missed optimization] Transitivity of less-than and less-or-equal kyrylo.bohdanenko at gmail dot com
2021-06-29 7:01 ` [Bug tree-optimization/101240] " rguenth at gcc dot gnu.org
2021-06-29 7:04 ` rguenth at gcc dot gnu.org
2021-11-05 21:31 ` amacleod at redhat dot com
2021-11-05 22:04 ` aldyh at gcc dot gnu.org
2023-07-13 18:27 ` pinskia at gcc dot gnu.org
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).