llvm dev - Feb 2016 - Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")

On Wed, Feb 24, 2016 at 7:38 PM, Chandler Carruth <chandlerc at
google.com> wrote:
> On Wed, Feb 24, 2016 at 7:34 PM Duncan P. N. Exon Smith
> <dexonsmith at apple.com> wrote:
>>
>>
>> > On 2016-Feb-24, at 19:17, Chandler Carruth <chandlerc at
google.com> wrote:
>> >
>> > On Wed, Feb 24, 2016 at 7:10 PM Sanjoy Das via llvm-dev
>> > <llvm-dev at lists.llvm.org> wrote:
>> > On Wed, Feb 24, 2016 at 6:51 PM, Duncan P. N. Exon Smith
>> > <dexonsmith at apple.com> wrote:
>> > >> If we do not inline @foo(), and instead re-link the call
site in
>> > >> @main
>> > >> to some non-optimized copy (or differently optimized
copy) of @foo,
>> > >> then it is possible for the program to have the behavior
{print("Y");
>> > >> print ("X")}, which was disallowed in the
earlier program.
>> > >>
>> > >> In other words, opt refined the semantics of @foo() (i.e.
reduced the
>> > >> set of behaviors it may have) in ways that would make
later
>> > >> optimizations invalid if we de-refine the implementation
of @foo().
>> > >
>> > > I'm probably missing something obvious here.  How could
the result of
>> > > `%t0 != %t1` be different at optimization time in one file
than from
>> > > runtime in the "real" implementation?  Doesn't
this make the CSE
>> > > invalid?
>> >
>> > `%t0` and `%t1` are "allowed" to "always be the
same", i.e. an
>> > implementation of @foo that always feeds in the same
>> > value for `%t0` and `%t1` is a valid implementation (which is why
the
>> > CSE was valid); but it is not the *only* valid implementation.  If
I
>> > don't CSE the two load instructions (also a valid thing to
do), and
>> > this is a second thread writing to `%par`, then the two values
loaded
>> > can be different, and you could end up printing `"X"` in
`@foo`.
>> >
>> > Did that make sense?
>>
>> Yes.  To be sure I understand the scope: this is only a problem for
>> atomics, correct?  (Because multi-threaded behaviour with other globals
>> is UB?)
>>
>> > > Does linkonce_odr linkage have the same problem?
>> > > - If so, do you want to change it too?
>> > > - Else, why not?
>> >
>> > Going by the specification in the LangRef, I'd say it depends
on how
>> > you define "definitive".  If you're allowed to
replace the body of a
>> > function with a differently optimized body, then the above problem
>> > exists.
>> >
>> > I believe that is the case, and I strongly believe the problem you
>> > outline exists for linkonce_odr exactly as it does for
available_externally.
>> >
>> > Which is what makes this scary: every C++ inline function today
can
>> > trigger this.
>>
>> Every C/C++ inline or template function.  But only the ones that use
>> atomics, right?
>
>
> Well, with *this* example...
Atomic are one source of non-determinism that compilers can reason
about.  I don't know if the following snippet is well defined or not,
but you could have similar issues with


  void foo() {
    int *p = malloc(sizeof(int));
    if (*p < 10) print("X");
  }

or (again, I don't know if this is actually well defined)

  void foo() {
    int t;  // it is probably reasonable to fold compares with
ptrtoint(alloca) to undef
    if ((intptr_t)(&t) < 10) print("X");
  }

-- Sanjoy
>
>>
>>
>> Not that I'm sure that will end up being a helpful distinction.
>
>
> Right. See Richard's comment. I think that sums up the real issue here.
=/

> On 2016-Feb-24, at 19:46, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> On Wed, Feb 24, 2016 at 7:38 PM, Chandler Carruth <chandlerc at
google.com> wrote:
>> On Wed, Feb 24, 2016 at 7:34 PM Duncan P. N. Exon Smith
>> <dexonsmith at apple.com> wrote:
>>> 
>>> 
>>>> On 2016-Feb-24, at 19:17, Chandler Carruth <chandlerc at
google.com> wrote:
>>>> 
>>>> On Wed, Feb 24, 2016 at 7:10 PM Sanjoy Das via llvm-dev
>>>> <llvm-dev at lists.llvm.org> wrote:
>>>> On Wed, Feb 24, 2016 at 6:51 PM, Duncan P. N. Exon Smith
>>>> <dexonsmith at apple.com> wrote:
>>>>>> If we do not inline @foo(), and instead re-link the
call site in
>>>>>> @main
>>>>>> to some non-optimized copy (or differently optimized
copy) of @foo,
>>>>>> then it is possible for the program to have the
behavior {print("Y");
>>>>>> print ("X")}, which was disallowed in the
earlier program.
>>>>>> 
>>>>>> In other words, opt refined the semantics of @foo()
(i.e. reduced the
>>>>>> set of behaviors it may have) in ways that would make
later
>>>>>> optimizations invalid if we de-refine the
implementation of @foo().
>>>>> 
>>>>> I'm probably missing something obvious here.  How could
the result of
>>>>> `%t0 != %t1` be different at optimization time in one file
than from
>>>>> runtime in the "real" implementation? 
Doesn't this make the CSE
>>>>> invalid?
>>>> 
>>>> `%t0` and `%t1` are "allowed" to "always be the
same", i.e. an
>>>> implementation of @foo that always feeds in the same
>>>> value for `%t0` and `%t1` is a valid implementation (which is
why the
>>>> CSE was valid); but it is not the *only* valid implementation. 
If I
>>>> don't CSE the two load instructions (also a valid thing to
do), and
>>>> this is a second thread writing to `%par`, then the two values
loaded
>>>> can be different, and you could end up printing `"X"`
in `@foo`.
>>>> 
>>>> Did that make sense?
>>> 
>>> Yes.  To be sure I understand the scope: this is only a problem for
>>> atomics, correct?  (Because multi-threaded behaviour with other
globals
>>> is UB?)
>>> 
>>>>> Does linkonce_odr linkage have the same problem?
>>>>> - If so, do you want to change it too?
>>>>> - Else, why not?
>>>> 
>>>> Going by the specification in the LangRef, I'd say it
depends on how
>>>> you define "definitive".  If you're allowed to
replace the body of a
>>>> function with a differently optimized body, then the above
problem
>>>> exists.
>>>> 
>>>> I believe that is the case, and I strongly believe the problem
you
>>>> outline exists for linkonce_odr exactly as it does for
available_externally.
>>>> 
>>>> Which is what makes this scary: every C++ inline function today
can
>>>> trigger this.
>>> 
>>> Every C/C++ inline or template function.  But only the ones that
use
>>> atomics, right?
>> 
>> 
>> Well, with *this* example...
> 
> Atomic are one source of non-determinism that compilers can reason
> about.  I don't know if the following snippet is well defined or not,
> but you could have similar issues with
> 
> 
>  void foo() {
>    int *p = malloc(sizeof(int));
>    if (*p < 10) print("X");
>  }
> 
> or (again, I don't know if this is actually well defined)
> 
>  void foo() {
>    int t;  // it is probably reasonable to fold compares with
> ptrtoint(alloca) to undef
>    if ((intptr_t)(&t) < 10) print("X");
>  }
> 
The first one at least is UB, but as Richard pointed out the scope
is certainly broader than atomics (it's not even just well-defined
non-deterministism).

I'm kind of terrified by the implications.
> -- Sanjoy
> 
>> 
>>> 
>>> 
>>> Not that I'm sure that will end up being a helpful distinction.
>> 
>> 
>> Right. See Richard's comment. I think that sums up the real issue
here. =/

On 02/24/2016 08:10 PM, Duncan P. N. Exon Smith via llvm-dev
wrote:
>> On 2016-Feb-24, at 19:46, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
>>
>> On Wed, Feb 24, 2016 at 7:38 PM, Chandler Carruth <chandlerc at
google.com> wrote:
>>> On Wed, Feb 24, 2016 at 7:34 PM Duncan P. N. Exon Smith
>>> <dexonsmith at apple.com> wrote:
>>>>
>>>>> On 2016-Feb-24, at 19:17, Chandler Carruth <chandlerc at
google.com> wrote:
>>>>>
>>>>> On Wed, Feb 24, 2016 at 7:10 PM Sanjoy Das via llvm-dev
>>>>> <llvm-dev at lists.llvm.org> wrote:
>>>>> On Wed, Feb 24, 2016 at 6:51 PM, Duncan P. N. Exon Smith
>>>>> <dexonsmith at apple.com> wrote:
>>>>>>> If we do not inline @foo(), and instead re-link the
call site in
>>>>>>> @main
>>>>>>> to some non-optimized copy (or differently
optimized copy) of @foo,
>>>>>>> then it is possible for the program to have the
behavior {print("Y");
>>>>>>> print ("X")}, which was disallowed in the
earlier program.
>>>>>>>
>>>>>>> In other words, opt refined the semantics of @foo()
(i.e. reduced the
>>>>>>> set of behaviors it may have) in ways that would
make later
>>>>>>> optimizations invalid if we de-refine the
implementation of @foo().
>>>>>> I'm probably missing something obvious here.  How
could the result of
>>>>>> `%t0 != %t1` be different at optimization time in one
file than from
>>>>>> runtime in the "real" implementation? 
Doesn't this make the CSE
>>>>>> invalid?
>>>>> `%t0` and `%t1` are "allowed" to "always be
the same", i.e. an
>>>>> implementation of @foo that always feeds in the same
>>>>> value for `%t0` and `%t1` is a valid implementation (which
is why the
>>>>> CSE was valid); but it is not the *only* valid
implementation.  If I
>>>>> don't CSE the two load instructions (also a valid thing
to do), and
>>>>> this is a second thread writing to `%par`, then the two
values loaded
>>>>> can be different, and you could end up printing
`"X"` in `@foo`.
>>>>>
>>>>> Did that make sense?
>>>> Yes.  To be sure I understand the scope: this is only a problem
for
>>>> atomics, correct?  (Because multi-threaded behaviour with other
globals
>>>> is UB?)
>>>>
>>>>>> Does linkonce_odr linkage have the same problem?
>>>>>> - If so, do you want to change it too?
>>>>>> - Else, why not?
>>>>> Going by the specification in the LangRef, I'd say it
depends on how
>>>>> you define "definitive".  If you're allowed
to replace the body of a
>>>>> function with a differently optimized body, then the above
problem
>>>>> exists.
>>>>>
>>>>> I believe that is the case, and I strongly believe the
problem you
>>>>> outline exists for linkonce_odr exactly as it does for
available_externally.
>>>>>
>>>>> Which is what makes this scary: every C++ inline function
today can
>>>>> trigger this.
>>>> Every C/C++ inline or template function.  But only the ones
that use
>>>> atomics, right?
>>>
>>> Well, with *this* example...
>> Atomic are one source of non-determinism that compilers can reason
>> about.  I don't know if the following snippet is well defined or
not,
>> but you could have similar issues with
>>
>>
>>   void foo() {
>>     int *p = malloc(sizeof(int));
>>     if (*p < 10) print("X");
>>   }
>>
>> or (again, I don't know if this is actually well defined)
>>
>>   void foo() {
>>     int t;  // it is probably reasonable to fold compares with
>> ptrtoint(alloca) to undef
>>     if ((intptr_t)(&t) < 10) print("X");
>>   }
>>
> The first one at least is UB, but as Richard pointed out the scope
> is certainly broader than atomics (it's not even just well-defined
> non-deterministism).
>
> I'm kind of terrified by the implications.
Me too.  :(
>
>> -- Sanjoy
>>
>>>>
>>>> Not that I'm sure that will end up being a helpful
distinction.
>>>
>>> Right. See Richard's comment. I think that sums up the real
issue here. =/
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev