* Safe transposition of logical and operands
@ 2023-09-17 19:33 Paul Floyd
2023-09-17 20:51 ` Jonathan Wakely
2023-09-18 10:30 ` Andreas Schwab
0 siblings, 2 replies; 14+ messages in thread
From: Paul Floyd @ 2023-09-17 19:33 UTC (permalink / raw)
To: gcc
Hi
I'm looking at a Valgrind issue. Full details here
https://bugs.kde.org/show_bug.cgi?id=472329
This code
void foo(std::optional<int64_t> f) {
std::cout << (f ? *f : 0) << std::endl;
std::set<int64_t> test;
test.emplace(0);
auto it{test.begin()};
while (it != test.end()) {
int64_t b{*it};
// Valgrind error on next line
if (f && *f != b) {
[snip]
int main() { foo(std::nullopt); }
generates (using g++ 12.2 on FreeBSD 13.2 amd64)
movq 40(%rbx), %rax
Error on next line:
cmpq %r14, %rax # f, SR.252
je .L47
cmpb $0, -97(%rbp) #, %sfp
jne .L69
Unless I'm completely mistaken cmpq %r14, %rax is the quadword
comparison of *f != b and cmpb $0, -97(%rbp) is the
std::optional::operator bool() comparison with 0. That means that g++
has transposed the order of evaluation.
The first cmpq/je generates a
==49599== Conditional jump or move depends on uninitialised value(s)
Valgrind has machinery to detect transformations like this and to
convert them back into bit accurate bitwise ands.
However, Valgrind thinks that these transpositions can't be done when
there are potentially trapping memory loads like *f.
So who is right? Is this a safe transformation?
Regards
Paul
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-17 19:33 Safe transposition of logical and operands Paul Floyd
@ 2023-09-17 20:51 ` Jonathan Wakely
2023-09-18 7:03 ` Paul Floyd
2023-09-18 10:30 ` Andreas Schwab
1 sibling, 1 reply; 14+ messages in thread
From: Jonathan Wakely @ 2023-09-17 20:51 UTC (permalink / raw)
To: Paul Floyd; +Cc: gcc
[-- Attachment #1: Type: text/plain, Size: 1667 bytes --]
On Sun, 17 Sept 2023, 20:33 Paul Floyd via Gcc, <gcc@gcc.gnu.org> wrote:
> Hi
>
> I'm looking at a Valgrind issue. Full details here
>
> https://bugs.kde.org/show_bug.cgi?id=472329
>
> This code
>
> void foo(std::optional<int64_t> f) {
> std::cout << (f ? *f : 0) << std::endl;
> std::set<int64_t> test;
> test.emplace(0);
> auto it{test.begin()};
> while (it != test.end()) {
> int64_t b{*it};
> // Valgrind error on next line
> if (f && *f != b) {
> [snip]
>
> int main() { foo(std::nullopt); }
>
> generates (using g++ 12.2 on FreeBSD 13.2 amd64)
>
> movq 40(%rbx), %rax
> Error on next line:
> cmpq %r14, %rax # f, SR.252
> je .L47
> cmpb $0, -97(%rbp) #, %sfp
> jne .L69
>
> Unless I'm completely mistaken cmpq %r14, %rax is the quadword
> comparison of *f != b and cmpb $0, -97(%rbp) is the
> std::optional::operator bool() comparison with 0. That means that g++
> has transposed the order of evaluation.
>
>
> The first cmpq/je generates a
>
> ==49599== Conditional jump or move depends on uninitialised value(s)
>
> Valgrind has machinery to detect transformations like this and to
> convert them back into bit accurate bitwise ands.
>
> However, Valgrind thinks that these transpositions can't be done when
> there are potentially trapping memory loads like *f.
>
Why would it be trapping? It's loading an int64_t, which might be
uninitialised but it can't trap.
*f on a std::optional is not like dereferencing a pointer, the int64_t
memory location is always present as part of the object.
> So who is right? Is this a safe transformation?
>
> Regards
> Paul
>
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-17 20:51 ` Jonathan Wakely
@ 2023-09-18 7:03 ` Paul Floyd
2023-09-18 7:23 ` Jonathan Wakely
0 siblings, 1 reply; 14+ messages in thread
From: Paul Floyd @ 2023-09-18 7:03 UTC (permalink / raw)
To: gcc
On 17-09-23 22:51, Jonathan Wakely wrote:
>
> Why would it be trapping? It's loading an int64_t, which might be
> uninitialised but it can't trap.
In this context I think that Valgrind is considering that any memory
load could trap.
> *f on a std::optional is not like dereferencing a pointer, the int64_t
> memory location is always present as part of the object.
For this
movq 40(%rbx), %rax
unless you know that what RBX+40 is pointing to is safe to dereference
it's not different to dereferencing a pointer.
So I think that the problem is that Valgrind is being cautious and not
allowing any loads but GCC is accepting what it considers safe loads
from the stack.
A+
Paul
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 7:03 ` Paul Floyd
@ 2023-09-18 7:23 ` Jonathan Wakely
2023-09-18 8:00 ` Richard Biener
2023-09-18 9:36 ` Jonathan Wakely
0 siblings, 2 replies; 14+ messages in thread
From: Jonathan Wakely @ 2023-09-18 7:23 UTC (permalink / raw)
To: Paul Floyd; +Cc: gcc
[-- Attachment #1: Type: text/plain, Size: 1485 bytes --]
On Mon, 18 Sept 2023, 08:03 Paul Floyd via Gcc, <gcc@gcc.gnu.org> wrote:
>
>
> On 17-09-23 22:51, Jonathan Wakely wrote:
>
> >
> > Why would it be trapping? It's loading an int64_t, which might be
> > uninitialised but it can't trap.
>
> In this context I think that Valgrind is considering that any memory
> load could trap.
>
There are no padding bits in int64_t and all object representations are
valid values, so it has no trap representations.
> > *f on a std::optional is not like dereferencing a pointer, the int64_t
> > memory location is always present as part of the object.
>
> For this
>
> movq 40(%rbx), %rax
>
> unless you know that what RBX+40 is pointing to is safe to dereference
> it's not different to dereferencing a pointer.
>
If it isn't safe to load that integer then it isn't safe to call f.operator
bool() either. GCC knows they are part of the same object.
> So I think that the problem is that Valgrind is being cautious and not
> allowing any loads but GCC is accepting what it considers safe loads
> from the stack.
>
Yes, GCC assumes that the reference is bound to a valid object, because C++
requires that to be true. Of course memcheck can't assume that, because one
of its main reasons to exist is to find undefined behaviour where that
isn't true!
I think what GCC is doing is a valid transformation, in the context of a
valid C++ program. But I'm not sure that helps valgrind, which doesn't have
the liberty of assuming a valid program.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 7:23 ` Jonathan Wakely
@ 2023-09-18 8:00 ` Richard Biener
2023-09-18 14:46 ` Floyd, Paul
2023-09-18 9:36 ` Jonathan Wakely
1 sibling, 1 reply; 14+ messages in thread
From: Richard Biener @ 2023-09-18 8:00 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: Paul Floyd, gcc
On Mon, Sep 18, 2023 at 9:24 AM Jonathan Wakely via Gcc <gcc@gcc.gnu.org> wrote:
>
> On Mon, 18 Sept 2023, 08:03 Paul Floyd via Gcc, <gcc@gcc.gnu.org> wrote:
>
> >
> >
> > On 17-09-23 22:51, Jonathan Wakely wrote:
> >
> > >
> > > Why would it be trapping? It's loading an int64_t, which might be
> > > uninitialised but it can't trap.
> >
> > In this context I think that Valgrind is considering that any memory
> > load could trap.
> >
>
> There are no padding bits in int64_t and all object representations are
> valid values, so it has no trap representations.
>
>
>
> > > *f on a std::optional is not like dereferencing a pointer, the int64_t
> > > memory location is always present as part of the object.
> >
> > For this
> >
> > movq 40(%rbx), %rax
> >
> > unless you know that what RBX+40 is pointing to is safe to dereference
> > it's not different to dereferencing a pointer.
> >
>
> If it isn't safe to load that integer then it isn't safe to call f.operator
> bool() either. GCC knows they are part of the same object.
>
>
> > So I think that the problem is that Valgrind is being cautious and not
> > allowing any loads but GCC is accepting what it considers safe loads
> > from the stack.
> >
>
> Yes, GCC assumes that the reference is bound to a valid object, because C++
> requires that to be true. Of course memcheck can't assume that, because one
> of its main reasons to exist is to find undefined behaviour where that
> isn't true!
>
> I think what GCC is doing is a valid transformation, in the context of a
> valid C++ program. But I'm not sure that helps valgrind, which doesn't have
> the liberty of assuming a valid program.
More specifically GCC thinks it's fine to speculate loads (given it can prove
doing so doesn't trap)
Richard.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 8:00 ` Richard Biener
@ 2023-09-18 14:46 ` Floyd, Paul
2023-09-18 14:55 ` Richard Biener
0 siblings, 1 reply; 14+ messages in thread
From: Floyd, Paul @ 2023-09-18 14:46 UTC (permalink / raw)
To: gcc
[-- Attachment #1: Type: text/plain, Size: 991 bytes --]
Hi Richard and Jonathan
On 18/09/2023 10:00, Richard Biener wrote:
> On Mon, Sep 18, 2023 at 9:24 AM Jonathan Wakely via Gcc<gcc@gcc.gnu.org> wrote:
>> Yes, GCC assumes that the reference is bound to a valid object, because C++
>> requires that to be true. Of course memcheck can't assume that, because one
>> of its main reasons to exist is to find undefined behaviour where that
>> isn't true!
It's even worse than that. This transformation is being done in VEX
(which unfortunately
is also the bit I know the least). Not normally where we'd do
accessibility checks.
>> I think what GCC is doing is a valid transformation, in the context of a
>> valid C++ program. But I'm not sure that helps valgrind, which doesn't have
>> the liberty of assuming a valid program.
> More specifically GCC thinks it's fine to speculate loads (given it can prove
> doing so doesn't trap)
I don't think that will be easy for us to prove. We just don't know
enough about stack variables.
A+
Paui
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 14:46 ` Floyd, Paul
@ 2023-09-18 14:55 ` Richard Biener
2023-09-18 17:56 ` Paul Floyd
0 siblings, 1 reply; 14+ messages in thread
From: Richard Biener @ 2023-09-18 14:55 UTC (permalink / raw)
To: Floyd, Paul; +Cc: gcc
On Mon, Sep 18, 2023 at 4:49 PM Floyd, Paul via Gcc <gcc@gcc.gnu.org> wrote:
>
> Hi Richard and Jonathan
>
> On 18/09/2023 10:00, Richard Biener wrote:
> > On Mon, Sep 18, 2023 at 9:24 AM Jonathan Wakely via Gcc<gcc@gcc.gnu.org> wrote:
> >> Yes, GCC assumes that the reference is bound to a valid object, because C++
> >> requires that to be true. Of course memcheck can't assume that, because one
> >> of its main reasons to exist is to find undefined behaviour where that
> >> isn't true!
>
> It's even worse than that. This transformation is being done in VEX
> (which unfortunately
> is also the bit I know the least). Not normally where we'd do
> accessibility checks.
>
> >> I think what GCC is doing is a valid transformation, in the context of a
> >> valid C++ program. But I'm not sure that helps valgrind, which doesn't have
> >> the liberty of assuming a valid program.
> > More specifically GCC thinks it's fine to speculate loads (given it can prove
> > doing so doesn't trap)
>
> I don't think that will be easy for us to prove. We just don't know
> enough about stack variables.
What you could do is report the access only on the point of use of
the accessed value? (and disregard when the register holding the
value is re-used)
Richard.
> A+
>
> Paui
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 14:55 ` Richard Biener
@ 2023-09-18 17:56 ` Paul Floyd
2023-09-18 19:09 ` Martin Uecker
0 siblings, 1 reply; 14+ messages in thread
From: Paul Floyd @ 2023-09-18 17:56 UTC (permalink / raw)
To: gcc
On 18-09-23 16:55, Richard Biener wrote:
> What you could do is report the access only on the point of use of
> the accessed value? (and disregard when the register holding the
> value is re-used)
Hi Richard
Not sure that I follow what you're saying.
memcheck triggers errors like this at conditional branching opcodes
where it determines that the condition is undefined.
There are mechanisms to de-duplicate errors, so once an error is emitted
it won't be printed again.
However, one of our goals is no false positives. This is one example
that is slipping through the cracks.
Regards
Paul
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 17:56 ` Paul Floyd
@ 2023-09-18 19:09 ` Martin Uecker
2023-09-18 20:15 ` Paul Floyd
0 siblings, 1 reply; 14+ messages in thread
From: Martin Uecker @ 2023-09-18 19:09 UTC (permalink / raw)
To: Paul Floyd, gcc
Am Montag, dem 18.09.2023 um 19:56 +0200 schrieb Paul Floyd via Gcc:
>
> On 18-09-23 16:55, Richard Biener wrote:
>
> > What you could do is report the access only on the point of use of
> > the accessed value? (and disregard when the register holding the
> > value is re-used)
>
> Hi Richard
>
> Not sure that I follow what you're saying.
>
> memcheck triggers errors like this at conditional branching opcodes
> where it determines that the condition is undefined.
>
> There are mechanisms to de-duplicate errors, so once an error is emitted
> it won't be printed again.
>
> However, one of our goals is no false positives. This is one example
> that is slipping through the cracks.
>
I do not understand why memcheck cares about the potential trap when
deciding to do the backwards transformation that combines the two
comparisons? Can't you just remove this condition? I assume it
is meant as a filter to only transform cases which really come
from an '&&' condition in the source, but as this example show, this
is too strict. Or am I missing something?
Martin
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 19:09 ` Martin Uecker
@ 2023-09-18 20:15 ` Paul Floyd
2023-09-18 20:52 ` Martin Uecker
0 siblings, 1 reply; 14+ messages in thread
From: Paul Floyd @ 2023-09-18 20:15 UTC (permalink / raw)
To: gcc
On 18-09-23 21:09, Martin Uecker wrote:
> I do not understand why memcheck cares about the potential trap when
> deciding to do the backwards transformation that combines the two
> comparisons? Can't you just remove this condition? I assume it
> is meant as a filter to only transform cases which really come
> from an '&&' condition in the source, but as this example show, this
> is too strict. Or am I missing something?
My understanding is that this is a generic transformation of
if (a && b) [which might have been transposed from if (b && a)]
into
if (a & b) [with appropriate extension to the right size].
That means both get evaluated and we can't take that risk that one of
them traps.
A+
Paul
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 20:15 ` Paul Floyd
@ 2023-09-18 20:52 ` Martin Uecker
2023-09-19 5:03 ` Paul Floyd
0 siblings, 1 reply; 14+ messages in thread
From: Martin Uecker @ 2023-09-18 20:52 UTC (permalink / raw)
To: Paul Floyd, gcc
Am Montag, dem 18.09.2023 um 22:15 +0200 schrieb Paul Floyd via Gcc:
>
> On 18-09-23 21:09, Martin Uecker wrote:
>
> > I do not understand why memcheck cares about the potential trap when
> > deciding to do the backwards transformation that combines the two
> > comparisons? Can't you just remove this condition? I assume it
> > is meant as a filter to only transform cases which really come
> > from an '&&' condition in the source, but as this example show, this
> > is too strict. Or am I missing something?
>
> My understanding is that this is a generic transformation of
>
> if (a && b) [which might have been transposed from if (b && a)]
>
> into
>
> if (a & b) [with appropriate extension to the right size].
>
> That means both get evaluated and we can't take that risk that one of
> them traps.
Is the problem that valgrind transforms the code before it then
emulates it and the problem is that during emulation the code
could trap?
Martin
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 20:52 ` Martin Uecker
@ 2023-09-19 5:03 ` Paul Floyd
0 siblings, 0 replies; 14+ messages in thread
From: Paul Floyd @ 2023-09-19 5:03 UTC (permalink / raw)
To: gcc
On 18-09-23 22:52, Martin Uecker wrote:
> Is the problem that valgrind transforms the code before it then
> emulates it and the problem is that during emulation the code
> could trap?
Yes, roughly the process is
guest ISA -> IR -> IR transformations -> IR optimizations -> execution
The && "idiom recovery" is getting filtered out during the IR
transformations.
A+
Paul
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-18 7:23 ` Jonathan Wakely
2023-09-18 8:00 ` Richard Biener
@ 2023-09-18 9:36 ` Jonathan Wakely
1 sibling, 0 replies; 14+ messages in thread
From: Jonathan Wakely @ 2023-09-18 9:36 UTC (permalink / raw)
To: Paul Floyd; +Cc: gcc
On Mon, 18 Sept 2023 at 08:23, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>
>
>
> On Mon, 18 Sept 2023, 08:03 Paul Floyd via Gcc, <gcc@gcc.gnu.org> wrote:
>>
>>
>>
>> On 17-09-23 22:51, Jonathan Wakely wrote:
>>
>> >
>> > Why would it be trapping? It's loading an int64_t, which might be
>> > uninitialised but it can't trap.
>>
>> In this context I think that Valgrind is considering that any memory
>> load could trap.
>
>
> There are no padding bits in int64_t and all object representations are valid values, so it has no trap representations.
>
>
>>
>> > *f on a std::optional is not like dereferencing a pointer, the int64_t
>> > memory location is always present as part of the object.
>>
>> For this
>>
>> movq 40(%rbx), %rax
>>
>> unless you know that what RBX+40 is pointing to is safe to dereference
>> it's not different to dereferencing a pointer.
>
>
> If it isn't safe to load that integer then it isn't safe to call f.operator bool() either. GCC knows they are part of the same object.
>
>>
>> So I think that the problem is that Valgrind is being cautious and not
>> allowing any loads but GCC is accepting what it considers safe loads
>> from the stack.
>
>
> Yes, GCC assumes that the reference is bound to a valid object,
Sorry, replying to email too early in the morning. The parameter isn't
optional<int64_t>& it's just optional<int64_t> so there's no
reference, it's on the stack (as you said) and the compiler can assume
that if the function was called then the stack address is valid.
> because C++ requires that to be true. Of course memcheck can't assume that, because one of its main reasons to exist is to find undefined behaviour where that isn't true!
>
> I think what GCC is doing is a valid transformation, in the context of a valid C++ program. But I'm not sure that helps valgrind, which doesn't have the liberty of assuming a valid program.
>
>
>
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Safe transposition of logical and operands
2023-09-17 19:33 Safe transposition of logical and operands Paul Floyd
2023-09-17 20:51 ` Jonathan Wakely
@ 2023-09-18 10:30 ` Andreas Schwab
1 sibling, 0 replies; 14+ messages in thread
From: Andreas Schwab @ 2023-09-18 10:30 UTC (permalink / raw)
To: Paul Floyd via Gcc; +Cc: Paul Floyd
On Sep 17 2023, Paul Floyd via Gcc wrote:
> However, Valgrind thinks that these transpositions can't be done when
> there are potentially trapping memory loads like *f.
*f is not doing any pointer dereference. It just reads the _M_payload
member of f.
--
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE 1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2023-09-19 5:03 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-17 19:33 Safe transposition of logical and operands Paul Floyd
2023-09-17 20:51 ` Jonathan Wakely
2023-09-18 7:03 ` Paul Floyd
2023-09-18 7:23 ` Jonathan Wakely
2023-09-18 8:00 ` Richard Biener
2023-09-18 14:46 ` Floyd, Paul
2023-09-18 14:55 ` Richard Biener
2023-09-18 17:56 ` Paul Floyd
2023-09-18 19:09 ` Martin Uecker
2023-09-18 20:15 ` Paul Floyd
2023-09-18 20:52 ` Martin Uecker
2023-09-19 5:03 ` Paul Floyd
2023-09-18 9:36 ` Jonathan Wakely
2023-09-18 10:30 ` Andreas Schwab
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).