llvm dev - Aug 2016 - invariant.load metadata semantics

> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Hal
Finkel via llvm-dev
> Subject: Re: [llvm-dev] invariant.load metadata semantics
> Alternatively, we might phrase this as: The optimizer may assume that all
values loaded
> from a location, where any of the loads are tagged with !invariant.load,
are identical.
This would seem to limit the usefulness of the invariant attribute.  I would
expect invariant to indicate that loads reachable from the one marked invariant
are guaranteed to read the same value, but that prior ones are not.  This would
allow updates to be made to the location of interest up to the point of declared
invariance, but not after.
> This has the benefit of covering the fact that no outside entity (i.e. the
operating system)
> changes the value, and that we can change it, but only to the same value it
had before (if
> we'll later be able to observe the difference).
> Some questions: Do we allow stores to these locations at all? Only if the
value is the same?
> Must any change be observable to be a problem? 
An alternative semantic is that a store would remove the invariant attribute for
subsequent loads.
> Do atomic loads of invariant locations really need to be atomic?
Ordering would still seem to be important, unless invariant applies
function-wide with no reachability concerns.

 - Chuck

On Thu, Aug 25, 2016 at 1:46 PM, Caldarale, Charles R via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf
Of
> Hal Finkel via llvm-dev
> > Subject: Re: [llvm-dev] invariant.load metadata semantics
>
> > Alternatively, we might phrase this as: The optimizer may assume that
> all values loaded
> > from a location, where any of the loads are tagged with
!invariant.load,
> are identical.
>
> This would seem to limit the usefulness of the invariant attribute.  I
> would expect invariant to indicate that loads reachable from the one marked
> invariant are guaranteed to read the same value, but that prior ones are
> not.

Define "reachable".

Do you mean there is any path from the load to the new load?

If so, what about loop backedges?

:)

This is one of the reasons they are explicitly marked.


> This would allow updates to be made to the location of interest up to the
> point of declared invariance, but not after.
>
This has the same problem.

for loop:

  store a
  load a !invariant.load


Legal or not if we can prove the loop iterates >1 time?
What does it mean?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160825/cdf3c492/attachment.html>

----- Original Message -----
> From: "Charles R Caldarale" <Chuck.Caldarale at unisys.com>
> To: "Hal Finkel" <hfinkel at anl.gov>, llvm-dev at
lists.llvm.org
> Sent: Thursday, August 25, 2016 3:46:17 PM
> Subject: RE: [llvm-dev] invariant.load metadata semantics
> 
> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf
> > Of Hal Finkel via llvm-dev
> > Subject: Re: [llvm-dev] invariant.load metadata semantics
> 
> > Alternatively, we might phrase this as: The optimizer may assume
> > that all values loaded
> > from a location, where any of the loads are tagged with
> > !invariant.load, are identical.
> 
> This would seem to limit the usefulness of the invariant attribute.
>  I would expect invariant to indicate that loads reachable from the
> one marked invariant are guaranteed to read the same value, but that
> prior ones are not.  This would allow updates to be made to the
> location of interest up to the point of declared invariance, but not
> after.
> 
> > This has the benefit of covering the fact that no outside entity
> > (i.e. the operating system)
> > changes the value, and that we can change it, but only to the same
> > value it had before (if
> > we'll later be able to observe the difference).
> 
> > Some questions: Do we allow stores to these locations at all? Only
> > if the value is the same?
> > Must any change be observable to be a problem?
> 
> An alternative semantic is that a store would remove the invariant
> attribute for subsequent loads.
I don't see how this would be useful. If we could prove the lack of
intervening stores, then we'd not need the metadata.

 -Hal
> 
> > Do atomic loads of invariant locations really need to be atomic?
> 
> Ordering would still seem to be important, unless invariant applies
> function-wide with no reachability concerns.
> 
>  - Chuck
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

----- Original Message -----
> From: "Charles R Caldarale" <Chuck.Caldarale at unisys.com>
> To: "Hal Finkel" <hfinkel at anl.gov>, llvm-dev at
lists.llvm.org
> Sent: Thursday, August 25, 2016 3:46:17 PM
> Subject: RE: [llvm-dev] invariant.load metadata semantics
> 
> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf
> > Of Hal Finkel via llvm-dev
> > Subject: Re: [llvm-dev] invariant.load metadata semantics
> 
> > Alternatively, we might phrase this as: The optimizer may assume
> > that all values loaded
> > from a location, where any of the loads are tagged with
> > !invariant.load, are identical.
> 
> This would seem to limit the usefulness of the invariant attribute.
>  I would expect invariant to indicate that loads reachable from the
> one marked invariant are guaranteed to read the same value, but that
> prior ones are not.  This would allow updates to be made to the
> location of interest up to the point of declared invariance, but not
> after.
No, this is a different use case, and we invariant.group/invariant.group.barrier
and invariant.start/invariant.end for that.

 -Hal
> 
> > This has the benefit of covering the fact that no outside entity
> > (i.e. the operating system)
> > changes the value, and that we can change it, but only to the same
> > value it had before (if
> > we'll later be able to observe the difference).
> 
> > Some questions: Do we allow stores to these locations at all? Only
> > if the value is the same?
> > Must any change be observable to be a problem?
> 
> An alternative semantic is that a store would remove the invariant
> attribute for subsequent loads.
> 
> > Do atomic loads of invariant locations really need to be atomic?
> 
> Ordering would still seem to be important, unless invariant applies
> function-wide with no reachability concerns.
> 
>  - Chuck
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

> From: Daniel Berlin [mailto:dberlin at dberlin.org] 
> Subject: Re: [llvm-dev] invariant.load metadata semantics
> > This would seem to limit the usefulness of the invariant attribute.  I
would expect invariant
> > to indicate that loads reachable from the one marked invariant are
guaranteed to read the same
> > value, but that prior ones are not. 
> Define "reachable".
> Do you mean there is any path from the load to the new load?
Yes.
> If so, what about loop backedges?
Depends on the details of the desired semantic definition.  The conservative
approach would be to drop the invariance; could also declare the situation to be
UB and perhaps catch it in the verifier.
 
> > This would allow updates to be made to the location of interest up to
the point of declared
> > invariance, but not after.
> This has the same problem.
> for loop:
>  store a
>  load a !invariant.load
> Legal or not if we can prove the loop iterates >1 time?
> What does it mean?
See above.  My (slight) preference is to treat it as UB, but that might be a bit
strong, considering this is metadata.

 - Chuck

> From: Hal Finkel [mailto:hfinkel at anl.gov] 
> Subject: Re: [llvm-dev] invariant.load metadata semantics
> > I would expect invariant to indicate that loads reachable from the
> > one marked invariant are guaranteed to read the same value, but that
> > prior ones are not.  This would allow updates to be made to the
> > location of interest up to the point of declared invariance, but not
> > after.
> No, this is a different use case, and we
invariant.group/invariant.group.barrier and
> invariant.start/invariant.end for that.
Good point; I'd forgotten about those.

 - Chuck

Hi Charles,

Caldarale, Charles R via llvm-dev wrote:
 >> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf
Of
Hal Finkel via llvm-dev
 >> Subject: Re: [llvm-dev] invariant.load metadata semantics
 >
 >> Alternatively, we might phrase this as: The optimizer may assume 
that all values loaded
 >> from a location, where any of the loads are tagged with 
!invariant.load, are identical.
 >

 > This would seem to limit the usefulness of the invariant attribute. 
I would expect invariant to indicate that loads reachable from the one 
marked invariant are guaranteed to read the same value, but that prior 
ones are not.  This would allow updates to be made to the location of 
interest up to the point of declared invariance, but not after.

That is a very defensible point, but depending on your use case you
consider these "initial" writes part of making the memory
dereferenceable.  For instance, for us (JVM) loading array lengths
satisfy the requirements of invariant loads, and we bake in the length
of the array as part of the array's allocation routine.  LLVM never
"sees" a store the the length field of an array.

However, I can imagine more complex use cases for which the above
approach won't work.

-- Sanjoy

Sanjoy, can you clarify this bit about JVM array lengths?

Presumably the same pointer can point to two arrays of different lengths
during a program's execution.  Does this mean that you're relying on
invariant.load having function scope?  That is, correctness depends on the
pointer not being reused for an array of a different length between the
first invariant load of that array length in a function and the last
(possibly not invariant) load in the function?

This seems like a very weak form of invariance.  For example, when you
inline, you would have to transform invariant loads to the scoped invariant
thing.

In NVPTX I am on a quest to use invariant loads for loads that must never
change during the execution of a kernel.  If the metadata signaled this
more restricted scope, I guess I'd have to figure something else out.

-Justin

On Aug 25, 2016 7:13 PM, "Sanjoy Das via llvm-dev" <llvm-dev at
lists.llvm.org>
wrote:
> Hi Charles,
>
> Caldarale, Charles R via llvm-dev wrote:
> >> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On
Behalf Of
> Hal Finkel via llvm-dev
> >> Subject: Re: [llvm-dev] invariant.load metadata semantics
> >
> >> Alternatively, we might phrase this as: The optimizer may assume
that
> all values loaded
> >> from a location, where any of the loads are tagged with
> !invariant.load, are identical.
> >
>
> > This would seem to limit the usefulness of the invariant attribute. I
> would expect invariant to indicate that loads reachable from the one marked
> invariant are guaranteed to read the same value, but that prior ones are
> not.  This would allow updates to be made to the location of interest up to
> the point of declared invariance, but not after.
>
> That is a very defensible point, but depending on your use case you
> consider these "initial" writes part of making the memory
> dereferenceable.  For instance, for us (JVM) loading array lengths
> satisfy the requirements of invariant loads, and we bake in the length
> of the array as part of the array's allocation routine.  LLVM never
> "sees" a store the the length field of an array.
>
> However, I can imagine more complex use cases for which the above
> approach won't work.
>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160829/07563ccf/attachment.html>