llvm dev - Aug 2016 - invariant.load metadata semantics

I believe the following is a reasonable attempt at boiling down this 
discussion.  It does allow stores of the same value.  It avoids the dead 
invariant.load issue Sanjoy brought up.  It does not allow final stores 
of a different value, the issue Hal most recently brought up in this thread:

     If a load instruction tagged with the ``!invariant.load`` metadata 
is executed, the optimizer may assume the memory location referenced by 
the load contains the same value at all points in the program where the 
memory location is known to be dereferenceable.

Thoughts?

On 8/25/2016 7:23 PM, Hal Finkel via llvm-dev wrote:
> ----- Original Message -----
>> From: "Sanjoy Das" <sanjoy at playingwithpointers.com>
>> To: "Hal Finkel" <hfinkel at anl.gov>
>> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
>> Sent: Thursday, August 25, 2016 6:09:14 PM
>> Subject: Re: [llvm-dev] invariant.load metadata semantics
>>
>> Hi Hal,
>>
>> Hal Finkel via llvm-dev wrote:
>>   > Some questions: Do we allow stores to these locations at all?
Only
>>   > if
>>
>> I'd vote for disallowing stores to these locations, but if
"stores
>> allowed only if the value is the same" is helpful in some
situation
>> then I don't have specific reasons why that would be problematic.
> I would as well; and from what I understand, this is consistent with
current use cases.
>
>>   > the value is the same? Must any change be observable to be a
>>   > problem? Do
>>
>> Not sure what you mean by "Must any change be observable".
> If we allow stores, if we have an invariant load from some location, and
then a store to that location (value arbitrary), is that a problem if the IR
being analyzed never loads from it again? I don't just mean dead stores:
just because the IR in question does not load from it again, that does not mean
that "the system" doesn't.
>
>>   > atomic loads of invariant locations really need to be atomic?
>>
>> It depends on the answer to "Do we allow stores to these locations
at
>> all?".  If we don't allow stores to these locations at all
then
>> atomic
>> loads are not required, since we can't have racing stores to that
>> location.
>>
>> However, syntactically, I'd be tempted to allow invariant loads to
be
>> atomic; and maybe have a later pass strip out the atomic bit if the
>> semantics we decide allow that.
> I agree. We should allow atomic loads to be marked as !invariant.load. We
might, if we decide on semantics that allow it, canonicalize by demoting to a
non-atomic load.
>
>   -Hal
>
>> -- Sanjoy
>>
-- 
Geoff Berry
Employee of Qualcomm Datacenter Technologies, Inc.
  Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the Code Aurora
Forum, a Linux Foundation Collaborative Project.

----- Original Message -----
> From: "Geoff Berry" <gberry at codeaurora.org>
> To: "Hal Finkel" <hfinkel at anl.gov>, "Sanjoy
Das" <sanjoy at playingwithpointers.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Tuesday, August 30, 2016 2:48:05 PM
> Subject: Re: [llvm-dev] invariant.load metadata semantics
> 
> I believe the following is a reasonable attempt at boiling down this
> discussion.  It does allow stores of the same value.  It avoids the
> dead
> invariant.load issue Sanjoy brought up.  It does not allow final
> stores
> of a different value, the issue Hal most recently brought up in this
> thread:
> 
>      If a load instruction tagged with the ``!invariant.load``
>      metadata
> is executed, the optimizer may assume the memory location referenced
> by
> the load contains the same value at all points in the program where
> the
> memory location is known to be dereferenceable.
Sounds reasonable to me.

 -Hal
> 
> Thoughts?
> 
> On 8/25/2016 7:23 PM, Hal Finkel via llvm-dev wrote:
> > ----- Original Message -----
> >> From: "Sanjoy Das" <sanjoy at
playingwithpointers.com>
> >> To: "Hal Finkel" <hfinkel at anl.gov>
> >> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> >> Sent: Thursday, August 25, 2016 6:09:14 PM
> >> Subject: Re: [llvm-dev] invariant.load metadata semantics
> >>
> >> Hi Hal,
> >>
> >> Hal Finkel via llvm-dev wrote:
> >>   > Some questions: Do we allow stores to these locations at
all?
> >>   > Only
> >>   > if
> >>
> >> I'd vote for disallowing stores to these locations, but if
"stores
> >> allowed only if the value is the same" is helpful in some
> >> situation
> >> then I don't have specific reasons why that would be
problematic.
> > I would as well; and from what I understand, this is consistent
> > with current use cases.
> >
> >>   > the value is the same? Must any change be observable to be
a
> >>   > problem? Do
> >>
> >> Not sure what you mean by "Must any change be
observable".
> > If we allow stores, if we have an invariant load from some
> > location, and then a store to that location (value arbitrary), is
> > that a problem if the IR being analyzed never loads from it again?
> > I don't just mean dead stores: just because the IR in question
> > does not load from it again, that does not mean that "the
system"
> > doesn't.
> >
> >>   > atomic loads of invariant locations really need to be
atomic?
> >>
> >> It depends on the answer to "Do we allow stores to these
locations
> >> at
> >> all?".  If we don't allow stores to these locations at
all then
> >> atomic
> >> loads are not required, since we can't have racing stores to
that
> >> location.
> >>
> >> However, syntactically, I'd be tempted to allow invariant
loads to
> >> be
> >> atomic; and maybe have a later pass strip out the atomic bit if
> >> the
> >> semantics we decide allow that.
> > I agree. We should allow atomic loads to be marked as
> > !invariant.load. We might, if we decide on semantics that allow
> > it, canonicalize by demoting to a non-atomic load.
> >
> >   -Hal
> >
> >> -- Sanjoy
> >>
> 
> --
> Geoff Berry
> Employee of Qualcomm Datacenter Technologies, Inc.
>   Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
>   Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the
>   Code Aurora Forum, a Linux Foundation Collaborative Project.
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On 08/30/2016 01:09 PM, Hal Finkel via llvm-dev wrote:
> ----- Original Message -----
>> From: "Geoff Berry" <gberry at codeaurora.org>
>> To: "Hal Finkel" <hfinkel at anl.gov>, "Sanjoy
Das" <sanjoy at playingwithpointers.com>
>> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
>> Sent: Tuesday, August 30, 2016 2:48:05 PM
>> Subject: Re: [llvm-dev] invariant.load metadata semantics
>>
>> I believe the following is a reasonable attempt at boiling down this
>> discussion.  It does allow stores of the same value.  It avoids the
>> dead
>> invariant.load issue Sanjoy brought up.  It does not allow final
>> stores
>> of a different value, the issue Hal most recently brought up in this
>> thread:
>>
>>       If a load instruction tagged with the ``!invariant.load``
>>       metadata
>> is executed, the optimizer may assume the memory location referenced
>> by
>> the load contains the same value at all points in the program where
>> the
>> memory location is known to be dereferenceable.
> Sounds reasonable to me.
Same.

Though let Sanjoy reply before changing; he's good at spotting semantic 
problems in this which seemed fine to me.  :)
>
>   -Hal
>
>> Thoughts?
>>
>> On 8/25/2016 7:23 PM, Hal Finkel via llvm-dev wrote:
>>> ----- Original Message -----
>>>> From: "Sanjoy Das" <sanjoy at
playingwithpointers.com>
>>>> To: "Hal Finkel" <hfinkel at anl.gov>
>>>> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
>>>> Sent: Thursday, August 25, 2016 6:09:14 PM
>>>> Subject: Re: [llvm-dev] invariant.load metadata semantics
>>>>
>>>> Hi Hal,
>>>>
>>>> Hal Finkel via llvm-dev wrote:
>>>>    > Some questions: Do we allow stores to these locations
at all?
>>>>    > Only
>>>>    > if
>>>>
>>>> I'd vote for disallowing stores to these locations, but if
"stores
>>>> allowed only if the value is the same" is helpful in some
>>>> situation
>>>> then I don't have specific reasons why that would be
problematic.
>>> I would as well; and from what I understand, this is consistent
>>> with current use cases.
>>>
>>>>    > the value is the same? Must any change be observable to
be a
>>>>    > problem? Do
>>>>
>>>> Not sure what you mean by "Must any change be
observable".
>>> If we allow stores, if we have an invariant load from some
>>> location, and then a store to that location (value arbitrary), is
>>> that a problem if the IR being analyzed never loads from it again?
>>> I don't just mean dead stores: just because the IR in question
>>> does not load from it again, that does not mean that "the
system"
>>> doesn't.
>>>
>>>>    > atomic loads of invariant locations really need to be
atomic?
>>>>
>>>> It depends on the answer to "Do we allow stores to these
locations
>>>> at
>>>> all?".  If we don't allow stores to these locations at
all then
>>>> atomic
>>>> loads are not required, since we can't have racing stores
to that
>>>> location.
>>>>
>>>> However, syntactically, I'd be tempted to allow invariant
loads to
>>>> be
>>>> atomic; and maybe have a later pass strip out the atomic bit if
>>>> the
>>>> semantics we decide allow that.
>>> I agree. We should allow atomic loads to be marked as
>>> !invariant.load. We might, if we decide on semantics that allow
>>> it, canonicalize by demoting to a non-atomic load.
>>>
>>>    -Hal
>>>
>>>> -- Sanjoy
>>>>
>> --
>> Geoff Berry
>> Employee of Qualcomm Datacenter Technologies, Inc.
>>    Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
>>    Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the
>>    Code Aurora Forum, a Linux Foundation Collaborative Project.
>>
>>

Hi Geoff,

Geoff Berry wrote:
 > I believe the following is a reasonable attempt at boiling down this
 > discussion. It does allow stores of the same value. It avoids the dead
 > invariant.load issue Sanjoy brought up. It does not allow final stores
 > of a different value, the issue Hal most recently brought up in this
 > thread:
 >
 > If a load instruction tagged with the ``!invariant.load`` metadata is
 > executed, the optimizer may assume the memory location referenced by the
 > load contains the same value at all points in the program where the
 > memory location is known to be dereferenceable.

This seems fine, but it does disallow introduction of dead stores.
That is, given:

void f() {
   %x = calloc()
   call void @g(nocapture %x)
}

we cannot transform it to

void f() {
   %x = calloc()
   *(%x) = 100
   *(%x) = 0
   call void @g(nocapture %x)
}

(after proving that %x is not visible to other threads), since @g
could have invariant loads from %x.

I don't have a good way of avoiding this issue, but given that the
transform above does not seem very useful I'm inclined to say the
definition above is okay for now.

-- Sanjoy

On 8/30/2016 4:53 PM, Sanjoy Das via llvm-dev wrote:
> This seems fine, but it does disallow introduction of dead stores.
> That is, given:
>
> void f() {
>   %x = calloc()
>   call void @g(nocapture %x)
> }
>
> we cannot transform it to
>
> void f() {
>   %x = calloc()
>   *(%x) = 100
>   *(%x) = 0
>   call void @g(nocapture %x)
> }
>
> (after proving that %x is not visible to other threads), since @g
> could have invariant loads from %x.
>
> I don't have a good way of avoiding this issue, but given that the
> transform above does not seem very useful I'm inclined to say the
> definition above is okay for now.
LICM performs precisely this transformation... see "If this is a thread 
local location" etc. in LICM.cpp.  That said, I doubt this case matters; 
nobody is going to use invariant.load on the result of calloc().

-Eli


-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project