Hal Finkel via llvm-dev
2016-Aug-25 20:12 UTC
[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>
Hal Finkel via llvm-dev
2016-Aug-25 20:17 UTC
[llvm-dev] invariant.load metadata semantics
----- Original Message -----> From: "Hal Finkel" <hfinkel at anl.gov> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "Geoff Berry" > <gberry at codeaurora.org> > Sent: Thursday, August 25, 2016 3:12:08 PM > Subject: Re: [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).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? Do atomic loads of invariant locations really need to be atomic? -Hal> -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-- 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/fef90cd2/attachment.html>
Caldarale, Charles R via llvm-dev
2016-Aug-25 20:46 UTC
[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.> 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
Sanjoy Das via llvm-dev
2016-Aug-25 21:01 UTC
[llvm-dev] invariant.load metadata semantics
Hi Hal, Hal Finkel via llvm-dev wrote: > 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. I'm okay if we s/any of the loads/any of the loads that execute at runtime/. Otherwise we end up in the same "dead code changes semantics" soup. > 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). Not sure if we gain much b allowing "changing it to the same value" (except perhaps "invariant_load(ptr); *ptr = 40" is not provably UB), but I don't mind it either. -- Sanjoy
Sanjoy Das via llvm-dev
2016-Aug-25 23:09 UTC
[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. > 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". > 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. -- Sanjoy