Piotr Padlewski via llvm-dev
2018-Dec-02 17:47 UTC
[llvm-dev] RFC: Supported Optimizations attribute
Hi folks, please check out our RFC: Supported Optimizations attribute https://docs.google.com/document/d/1s0n-JVaSNML1Z9SCZVg2bgisxswIJAK2Tp9DahucW10/edit?usp=sharing Pasting it here for the record: RFC: supported_optimizations attribute Piotr Padlewski - piotr.padlewski at gmail.com Krzysztof Pszeniczny - kpszeniczny at google.com December 2018 Introduction Sometimes a possible class of optimizations requires very precise use of metadata and/or intrinsics, at least to achieve a clean implementation thereof. Our primary example is devirtualization[RFC: Devirtualization v2 <https://docs.google.com/document/d/16GVtCpzK8sIHNc2qZz6RN8amICNBtvjWUod2SujZVEo/edit>], which requires that the LLVM IR be annotated with certain intrinsic calls, viz. launder.invariant.group and strip.invariant.group, in certain places, e.g. when the dynamic type of an object changes. This currently makes it impossible to merge IR created with this kind of optimization in mind and without it, as this can lead to miscompilation when the optimizer relies on the lack of intrinsics and/or metadata to make certain assumptions about the code in question. For now, in case of devirtualization, we plainly refuse to merge such pieces of IR. This predominantly affects cross-language link-time optimization. Solution We propose a fine-grained, function-level solution to this problem, originally suggested by John McCall: mark each function with a list of such optimization requirements it complies with, by the means of an attribute for now called supported_optimizations. The exact naming of this attribute is of course subject to bikeshedding, so we kindly request the community to provide us with a better name, if found. When performing inter-procedural optimizations (mostly inlining), the list of supported optimizations by the both functions should be considered to be to the intersection of their previous lists of supported optimizations. This effectively hinders any optimization relying on precise annotations from happening if such precise annotations can no longer be guaranteed. More precisely, when doing an IPO other than inlining, such a pass must treat the functions in question as if they had the supported optimizations lists set to the intersection of their original ones. This in general obviously does not require modifying those lists. In the case of inlining, the list of optimizations supported by the callee is left intact, but the list of optimizations supported by the caller must be set to the said intersection. invariant.group The !invariant.group metadata should be equipped with an argument referring to the supported_optimization it is related to. In the existing case, it will be set to "clang.cxx.devirtualization". If this supported_optimization is not present in the list of optimizations supported by the enclosing function, the !invariant.group metadata has no effect and cannot be relied upon by the optimizer. Of course, in this case the metadata in question is not useful anymore and can be safely removed. We kindly thank Richard Smith for suggesting this approach. As a transitional measure and for backwards compatibility reasons, any !invariant.group metadata with an empty argument (i.e. as before this RFC), shall not be subject to the above restrictions and shall remain applicable even when there is no supported_optimizations list provided for the enclosing function. Example: define void @with_devirtualization(i8* %p) supported_optimizations "clang.cxx.devirtualization" { %v1 = load i8, i8* %p, !invariant.group !0 %p2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %p) call void @without_devirtualization(i8* %p, i8* %p2) %v2 = load i8, i8* %p2, !invariant.group !0 ret void } define void @without_devirtualization(i8* %p, i8* %p2) { %b = icmp eq i8* %p, %p2 call void @llvm.assume(i1 %b) ret void } !0 = !{!"clang.cxx.devirtualization"} declare void @llvm.assume(i1) declare i8* @llvm.launder.invariant.group.p0i8(i8*) After inlining: define void @with_devirtualization(i8* %p) { ; !invariant.group is inactive now, so it can be stripped. %v1 = load i8, i8* %p, !invariant.group !0 %p2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %p) %b = icmp eq i8* %p, %p2 call void @llvm.assume(i1 %b) %v2 = load i8, i8* %p2, !invariant.group !0 ret void } Possible extensions Instead of indiscriminately taking the intersection of supported optimizations' lists, we may imagine that some of such optimizations may be able to provide a conservative set of annotations to a function lacking them. By doing so, we may retain at least some level of information available to the optimizer, by preserving the annotations already present in the optimization-compliant function. For example, devirtualization may conservatively pass every load and function argument through a strip and every store and return value through a launder, which is a way of conservatively making an arbitrary function compliant with the requirements of this particular optimization. Bikeshedding Other possible names: - compilant_with - brittle_representations (John McCall's original suggestion) -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181202/c900a6f9/attachment-0001.html>
Reid Kleckner via llvm-dev
2018-Dec-03 19:37 UTC
[llvm-dev] RFC: Supported Optimizations attribute
Replying on llvm-dev, since I mainly want to brainstorm the IR attribute name... This attribute is really a promise that the IR in this function obeys certain invariants. In this case, it's that every virtual pointer load uses a particular pattern to support a C++-specific optimization. That suggests a name something along the lines of "lso_invariants" (language-specific optimization = LSO) or "opt_invariants_preserved". What do you think of those names or that direction? On Sun, Dec 2, 2018 at 9:47 AM Piotr Padlewski via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Hi folks, > > please check out our RFC: Supported Optimizations attribute > > > https://docs.google.com/document/d/1s0n-JVaSNML1Z9SCZVg2bgisxswIJAK2Tp9DahucW10/edit?usp=sharing > > Pasting it here for the record: > > RFC: supported_optimizations attribute > > Piotr Padlewski - piotr.padlewski at gmail.com > Krzysztof Pszeniczny - kpszeniczny at google.com > December 2018 > > Introduction > > Sometimes a possible class of optimizations requires very precise use of > metadata and/or intrinsics, at least to achieve a clean implementation > thereof. > > Our primary example is devirtualization[RFC: Devirtualization v2 > <https://docs.google.com/document/d/16GVtCpzK8sIHNc2qZz6RN8amICNBtvjWUod2SujZVEo/edit>], > which requires that the LLVM IR be annotated with certain intrinsic calls, > viz. launder.invariant.group and strip.invariant.group, in certain > places, e.g. when the dynamic type of an object changes. > > This currently makes it impossible to merge IR created with this kind of > optimization in mind and without it, as this can lead to miscompilation > when the optimizer relies on the lack of intrinsics and/or metadata to make > certain assumptions about the code in question. For now, in case of > devirtualization, we plainly refuse to merge such pieces of IR. This > predominantly affects cross-language link-time optimization. > Solution > > We propose a fine-grained, function-level solution to this problem, > originally suggested by John McCall: mark each function with a list of such > optimization requirements it complies with, by the means of an attribute > for now called supported_optimizations. The exact naming of this > attribute is of course subject to bikeshedding, so we kindly request the > community to provide us with a better name, if found. > > When performing inter-procedural optimizations (mostly inlining), the list > of supported optimizations by the both functions should be considered to be > to the intersection of their previous lists of supported optimizations. > This effectively hinders any optimization relying on precise annotations > from happening if such precise annotations can no longer be guaranteed. > > More precisely, when doing an IPO other than inlining, such a pass must > treat the functions in question as if they had the supported optimizations > lists set to the intersection of their original ones. This in general > obviously does not require modifying those lists. > > In the case of inlining, the list of optimizations supported by the callee > is left intact, but the list of optimizations supported by the caller must > be set to the said intersection. > > invariant.group > > The !invariant.group metadata should be equipped with an argument > referring to the supported_optimization it is related to. In the existing > case, it will be set to "clang.cxx.devirtualization". If this > supported_optimization is not present in the list of optimizations > supported by the enclosing function, the !invariant.group metadata has no > effect and cannot be relied upon by the optimizer. Of course, in this case > the metadata in question is not useful anymore and can be safely removed. > We kindly thank Richard Smith for suggesting this approach. > > As a transitional measure and for backwards compatibility reasons, any > !invariant.group metadata with an empty argument (i.e. as before this > RFC), shall not be subject to the above restrictions and shall remain > applicable even when there is no supported_optimizations list provided > for the enclosing function. > Example: > > define void @with_devirtualization(i8* %p) supported_optimizations > "clang.cxx.devirtualization" { > %v1 = load i8, i8* %p, !invariant.group !0 > %p2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %p) > call void @without_devirtualization(i8* %p, i8* %p2) > %v2 = load i8, i8* %p2, !invariant.group !0 > ret void > } > > define void @without_devirtualization(i8* %p, i8* %p2) { > %b = icmp eq i8* %p, %p2 > call void @llvm.assume(i1 %b) > ret void > } > > !0 = !{!"clang.cxx.devirtualization"} > declare void @llvm.assume(i1) > declare i8* @llvm.launder.invariant.group.p0i8(i8*) > > After inlining: > > define void @with_devirtualization(i8* %p) { > ; !invariant.group is inactive now, so it can be stripped. > %v1 = load i8, i8* %p, !invariant.group !0 > %p2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %p) > %b = icmp eq i8* %p, %p2 > call void @llvm.assume(i1 %b) > %v2 = load i8, i8* %p2, !invariant.group !0 > ret void > } > > Possible extensions > > Instead of indiscriminately taking the intersection of supported > optimizations' lists, we may imagine that some of such optimizations may be > able to provide a conservative set of annotations to a function lacking > them. By doing so, we may retain at least some level of information > available to the optimizer, by preserving the annotations already present > in the optimization-compliant function. > > For example, devirtualization may conservatively pass every load and > function argument through a strip and every store and return value through > a launder, which is a way of conservatively making an arbitrary function > compliant with the requirements of this particular optimization. > Bikeshedding > > Other possible names: > > - > > compilant_with > - > > brittle_representations (John McCall's original suggestion) > > _______________________________________________ > 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/20181203/95cc485b/attachment-0001.html>
John McCall via llvm-dev
2018-Dec-04 04:52 UTC
[llvm-dev] RFC: Supported Optimizations attribute
Thank you for pushing this forward. On 2 Dec 2018, at 12:47, Piotr Padlewski wrote:> We propose a fine-grained, function-level solution to this problem, > originally suggested by John McCall: mark each function with a list of > such > optimization requirements it compliescompiles> invariant.groupIn this proposal, it seems like you're assuming that only the invariant.group metadata needs to be parameterized with a supported_optimization. Should you also decorate all the other structures used as part of this optimization, e.g. the calls to llvm.strip.invariant.group and llvm.launder.invariant.group? This would also allow these intrinsics to be more explicit about exactly which family of invariant.group metadata they're supposed to be laundering/stripping, and correspondingly it would allow LLVM to remove these intrinsics when it strips invariant.group optimization information.> As a transitional measure and for backwards compatibility reasons, any > !invariant.group metadata with an empty argument (i.e. as before this > RFC), > shall not be subject to the above restrictions and shall remain > applicable > even when there is no supported_optimizations list provided for the > enclosing function.I don't think it's important to support this transitionally. AFAIK, there are no existing, non-experimental optimizations using invariant.group where it's crucial that we continue to perform the optimization when linking existing .bc files. We should just insist that invariant.group has a tag and otherwise strip it during deserialization.> Possible extensions > > Instead of indiscriminately taking the intersection of supported > optimizations' lists, we may imagine that some of such optimizations > may be > able to provide a conservative set of annotations to a function > lacking > them. By doing so, we may retain at least some level of information > available to the optimizer, by preserving the annotations already > present > in the optimization-compliant function. > > For example, devirtualization may conservatively pass every load and > function argument through a strip and every store and return value > through > a launder, which is a way of conservatively making an arbitrary > function > compliant with the requirements of this particular optimization.Sure, that's a theoretical future enhancement that we could provide. John.
Sanjoy Das via llvm-dev
2018-Dec-04 06:45 UTC
[llvm-dev] RFC: Supported Optimizations attribute
I think we should have some bounds on how "badly" a supported_optimizations tag on a function can affect its semantics. For instance, can a "supported_optimizations" invariant be that "the CFG is always structured"? Or (exaggerating to illustrate the point) "the function has an equal number of loads and stores"? -- Sanjoy On Mon, Dec 3, 2018 at 8:52 PM John McCall via llvm-dev <llvm-dev at lists.llvm.org> wrote:> > Thank you for pushing this forward. > > On 2 Dec 2018, at 12:47, Piotr Padlewski wrote: > > We propose a fine-grained, function-level solution to this problem, > > originally suggested by John McCall: mark each function with a list of > > such > > optimization requirements it complies > > compiles > > > invariant.group > > In this proposal, it seems like you're assuming that only the > invariant.group > metadata needs to be parameterized with a supported_optimization. > Should you > also decorate all the other structures used as part of this > optimization, e.g. > the calls to llvm.strip.invariant.group and > llvm.launder.invariant.group? > This would also allow these intrinsics to be more explicit about exactly > which > family of invariant.group metadata they're supposed to be > laundering/stripping, > and correspondingly it would allow LLVM to remove these intrinsics when > it > strips invariant.group optimization information. > > > As a transitional measure and for backwards compatibility reasons, any > > !invariant.group metadata with an empty argument (i.e. as before this > > RFC), > > shall not be subject to the above restrictions and shall remain > > applicable > > even when there is no supported_optimizations list provided for the > > enclosing function. > > I don't think it's important to support this transitionally. AFAIK, > there are > no existing, non-experimental optimizations using invariant.group where > it's > crucial that we continue to perform the optimization when linking > existing .bc > files. We should just insist that invariant.group has a tag and > otherwise > strip it during deserialization. > > > Possible extensions > > > > Instead of indiscriminately taking the intersection of supported > > optimizations' lists, we may imagine that some of such optimizations > > may be > > able to provide a conservative set of annotations to a function > > lacking > > them. By doing so, we may retain at least some level of information > > available to the optimizer, by preserving the annotations already > > present > > in the optimization-compliant function. > > > > For example, devirtualization may conservatively pass every load and > > function argument through a strip and every store and return value > > through > > a launder, which is a way of conservatively making an arbitrary > > function > > compliant with the requirements of this particular optimization. > > Sure, that's a theoretical future enhancement that we could provide. > > John. > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
John McCall via llvm-dev
2018-Dec-04 07:02 UTC
[llvm-dev] RFC: Supported Optimizations attribute
On 3 Dec 2018, at 23:52, John McCall wrote:> On 2 Dec 2018, at 12:47, Piotr Padlewski wrote: >> We propose a fine-grained, function-level solution to this problem, >> originally suggested by John McCall: mark each function with a list >> of such >> optimization requirements it complies > > compiles...I have no idea what I was thinking here, "complies" is obviously the right word. Apologies. John.