Safe transposition of logical and operands

Safe transposition of logical and operands

[Paul Floyd]

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

Re: Safe transposition of logical and operands

[Jonathan Wakely]

[-- 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
>

Re: Safe transposition of logical and operands

[Paul Floyd]

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

Re: Safe transposition of logical and operands

[Jonathan Wakely]

[-- 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.

Re: Safe transposition of logical and operands

[Richard Biener]

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.

Re: Safe transposition of logical and operands

[Jonathan Wakely]

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.
>
>
>

Re: Safe transposition of logical and operands

[Andreas Schwab]

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."

Re: Safe transposition of logical and operands

[Floyd, Paul]

[-- 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

Re: Safe transposition of logical and operands

[Richard Biener]

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

Re: Safe transposition of logical and operands

[Paul Floyd]

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

Re: Safe transposition of logical and operands

[Martin Uecker]

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

Re: Safe transposition of logical and operands

[Paul Floyd]

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

Re: Safe transposition of logical and operands

[Martin Uecker]

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

Re: Safe transposition of logical and operands

[Paul Floyd]

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