thr3ads.net - llvm dev - [llvm-dev] invariant.load metadata semantics [Aug 2016]

If this information is useful, please help other people find it:
Share via:

Geoff Berry via llvm-dev

2016-Aug-25 19:23 UTC

[llvm-dev] invariant.load metadata semantics

I'm working on enhancing EarlyCSE to use MemorySSA and have come across 
the following issue due to differences in EarlyCSE and MemorySSA's 
handling of !invariant.load.  EarlyCSE will *not* currently optimize the 
following code by replacing %x2 with %x and removing the second load:

    B1:

       %x = load %p

       clobber()

    ...

    B2: // dominated by B1

       %x2 = load %p !invariant.load


Sanjoy (who added the !invariant.load support to EarlyCSE) and I 
discussed this, and I believe we are both in agreement that this 
optimization should be legal.  I'd like to make sure there is agreement 
on this and possibly clarify the LangRef wording on !invariant.load to 
make the legality of this transformation more clear.

Sanjoy suggested the following:

    Instead of "The existence of the !invariant.load metadata on the
    instruction tells the optimizer and code generator that the address
    operand to this load points to memory which can be assumed
    unchanged." we say "It is undefined behavior to invariant_load
from
    a location that has been changed since it became dereferenceable". 
    In the current langref, I find "The existence" somewhat confusing,
    since it seems to imply that adding dead code can change the
    behavior of the program.

    I don't want to specify the semantics in a way that:

        int* ptr = ...
        int k0 = *ptr; // normal load
        clobber();
        int k1 = *ptr; // normal load

    has a different meaning than

        int* ptr = ...
        int k0 = *ptr; // normal load
        clobber();
        int k1 = *ptr; // normal load
        if (<always false>) {
          int k2 = *ptr; // !invariant load
        }

    That is, adding dead code should not change the behavior of the
    program -- the code guarded by (<always false>) should be able to have
    any amount of junk without breaking the program, since it does not
    actually execute.


Does this seem like a clearer wording of the intended semantics?

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160825/227a277e/attachment.html>

Hal Finkel via llvm-dev

2016-Aug-25 20:05 UTC

head link

[llvm-dev] invariant.load metadata semantics

----- Original Message -----
> From: "Geoff Berry via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Thursday, August 25, 2016 2:23:01 PM
> Subject: [llvm-dev] invariant.load metadata semantics
> I'm working on enhancing EarlyCSE to use MemorySSA and have come
> across the following issue due to differences in EarlyCSE and
> MemorySSA's handling of !invariant.load. EarlyCSE will *not*
> currently optimize the following code by replacing %x2 with %x and
> removing the second load:
> > B1:
> 
> > %x = load %p
> 
> > clobber()
> 
> > ...
> 
> > B2: // dominated by B1
> 
> > %x2 = load %p !invariant.load
> 
> Sanjoy (who added the !invariant.load support to EarlyCSE) and I
> discussed this, and I believe we are both in agreement that this
> optimization should be legal. I'd like to make sure there is
> agreement on this and possibly clarify the LangRef wording on
> !invariant.load to make the legality of this transformation more
> clear.
> Sanjoy suggested the following:
> > Instead of "The existence of the !invariant.load metadata on the
> > instruction tells the optimizer and code generator that the address
> > operand to this load points to memory which can be assumed
> > unchanged." we say "It is undefined behavior to
invariant_load from
> > a location that has been changed since it became
dereferenceable".
> > In the current langref, I find "The existence" somewhat
confusing,
> > since it seems to imply that adding dead code can change the
> > behavior of the program.
> 
> > I don't want to specify the semantics in a way that:
> 
> > int* ptr = ...
> 
> > int k0 = *ptr; // normal load
> 
> > clobber();
> 
> > int k1 = *ptr; // normal load
> 
> > has a different meaning than
> 
> > int* ptr = ...
> 
> > int k0 = *ptr; // normal load
> 
> > clobber();
> 
> > int k1 = *ptr; // normal load
> 
> > if (<always false>) {
> 
> > int k2 = *ptr; // !invariant load
> 
> > }
> 
> > That is, adding dead code should not change the behavior of the
> 
> > program -- the code guarded by (<always false>) should be able
to
> > have
> 
> > any amount of junk without breaking the program, since it does not
> 
> > actually execute.
> 
I agree. 

Regarding the proposed text, I find the "since it became
dereferenceable" phrase ambiguous. Further, I think we can say something
stronger: Storing into a location previously loaded using a load tagged with
!invariant.load is undefined behavior.

-Hal 
> Does this seem like a clearer wording of the intended semantics?
> --
> 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.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160825/1a4efdb9/attachment.html>

Sanjoy Das via llvm-dev

2016-Aug-25 20:11 UTC

head link

[llvm-dev] invariant.load metadata semantics

Hi Hal,

Hal Finkel via llvm-dev wrote:
 > I agree.
 >
 > Regarding the proposed text, I find the "since it became
 > dereferenceable" phrase ambiguous. Further, I think we can say
something
 > stronger: Storing into a location previously loaded using a load tagged
 > with !invariant.load is undefined behavior.

That prevents doing the optimization Geoff suggested:

   int k = *ptr;
   clobber();
   int k2 = *ptr; // invariant

==>

   int k = *ptr;
   clobber();
   int k2 = k;

since clobber(), given what you said, could have legitimately changed
the contents of ptr.

-- Sanjoy

Hal Finkel via llvm-dev

2016-Aug-25 20:12 UTC

head link

[llvm-dev] invariant.load metadata semantics

----- Original Message -----
> From: "Hal Finkel via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "Geoff Berry" <gberry at codeaurora.org>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Thursday, August 25, 2016 3:05:48 PM
> Subject: Re: [llvm-dev] invariant.load metadata semantics
> ----- Original Message -----
> > From: "Geoff Berry via llvm-dev" <llvm-dev at
lists.llvm.org>
> 
> > To: "llvm-dev" <llvm-dev at lists.llvm.org>
> 
> > Sent: Thursday, August 25, 2016 2:23:01 PM
> 
> > Subject: [llvm-dev] invariant.load metadata semantics
> 
> > I'm working on enhancing EarlyCSE to use MemorySSA and have come
> > across the following issue due to differences in EarlyCSE and
> > MemorySSA's handling of !invariant.load. EarlyCSE will *not*
> > currently optimize the following code by replacing %x2 with %x and
> > removing the second load:
> 
> > > B1:
> > 
> 
> > > %x = load %p
> > 
> 
> > > clobber()
> > 
> 
> > > ...
> > 
> 
> > > B2: // dominated by B1
> > 
> 
> > > %x2 = load %p !invariant.load
> > 
> 
> > Sanjoy (who added the !invariant.load support to EarlyCSE) and I
> > discussed this, and I believe we are both in agreement that this
> > optimization should be legal. I'd like to make sure there is
> > agreement on this and possibly clarify the LangRef wording on
> > !invariant.load to make the legality of this transformation more
> > clear.
> 
> > Sanjoy suggested the following:
> 
> > > Instead of "The existence of the !invariant.load metadata on
the
> > > instruction tells the optimizer and code generator that the
> > > address
> > > operand to this load points to memory which can be assumed
> > > unchanged." we say "It is undefined behavior to
invariant_load
> > > from
> > > a location that has been changed since it became
> > > dereferenceable".
> > > In the current langref, I find "The existence" somewhat
> > > confusing,
> > > since it seems to imply that adding dead code can change the
> > > behavior of the program.
> > 
> 
> > > I don't want to specify the semantics in a way that:
> > 
> 
> > > int* ptr = ...
> > 
> 
> > > int k0 = *ptr; // normal load
> > 
> 
> > > clobber();
> > 
> 
> > > int k1 = *ptr; // normal load
> > 
> 
> > > has a different meaning than
> > 
> 
> > > int* ptr = ...
> > 
> 
> > > int k0 = *ptr; // normal load
> > 
> 
> > > clobber();
> > 
> 
> > > int k1 = *ptr; // normal load
> > 
> 
> > > if (<always false>) {
> > 
> 
> > > int k2 = *ptr; // !invariant load
> > 
> 
> > > }
> > 
> 
> > > That is, adding dead code should not change the behavior of the
> > 
> 
> > > program -- the code guarded by (<always false>) should be
able to
> > > have
> > 
> 
> > > any amount of junk without breaking the program, since it does
> > > not
> > 
> 
> > > actually execute.
> > 
> 
> I agree.
> Regarding the proposed text, I find the "since it became
> dereferenceable" phrase ambiguous. Further, I think we can say
> something stronger: Storing into a location previously loaded using
> a load tagged with !invariant.load is undefined behavior.
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 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).

-Hal 
> -Hal
> > Does this seem like a clearer wording of the intended semantics?
> 
> > --
> 
> > 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.
> 
> > _______________________________________________
> 
> > LLVM Developers mailing list
> 
> > llvm-dev at lists.llvm.org
> 
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160825/5482435f/attachment.html>

Maybe Matching Threads

Search for more maybe matching threads

llvm dev - Aug 2016 - invariant.load metadata semantics

[llvm-dev] invariant.load metadata semantics

[llvm-dev] invariant.load metadata semantics

[llvm-dev] invariant.load metadata semantics

[llvm-dev] invariant.load metadata semantics

Maybe Matching Threads