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:49 UTC
[llvm-dev] RFC: Supported Optimizations attribute
On 4 Dec 2018, at 1:45, Sanjoy Das wrote:> 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"?Piotr's proposal unfortunately doesn't give us a good name for the class of optimizations that require being listed in `supported_optimizations`. In earlier discussions I called them "brittle", but I can understand why nobody wants to call their optimization that, so let's call them "good-faith optimizations" instead since they rely on the good faith of all the participating code. Every optimization has to know how to maintain the structural rules of LLVM IR; that's what makes them structural rules. We don't want the set of structural rules to substantially change because such-and-such good-faith optimization is in effect because that would require arbitrary transforms to check the supported_optimizations list before they knew which rules to follow. Instead, the burden is on the optimization designer to pick IR constructs that won't be messed up by an arbitrary transform with no special knowledge of the optimization. The only thing the optimization designer can rely on is this: - other transforms will preserve the apparent semantics of the function and - other transforms will maintain the standard structural rules of LLVM IR. For example, if you need arbitrary side-effects to not be re-ordered past some point in the function, you should put an instruction there that inhibits that kind of code motion, probably by making it look like a call to an unknown function. No transform can reorder arbitrary side-effects across such a call because doing so might change the apparent semantics of the program. Similarly, if you need a direct use-def link between two points in the function, you should make the first point define a token that'll be used by the second point. No transform will break or abstract that association because that would violate the basic structural rules of IR. If there's a structural rule that can't be expressed with the current tools of IR, we can talk about how to fix that --- although tokens are such a big hammer that I'd be somewhat surprised to hear that something really can't be expressed at all (but much less surprised to hear that the token rules are too strong and we'd like other transforms to have more power to change the code). So the defining property of a good-faith optimization is that: - there are rules which participating functions are expected to follow on pain of undefined behavior but which LLVM IR doesn't require every function to follow, and - those rules will be preserved by any transform that doesn't move code between functions and which preserves the apparent function semantics and maintains the standard structural rules of LLVM IR. I think that answers your question about what sort of rules we can expect supported_optimizations to guarantee. John. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181204/923cb90d/attachment.html>
Finkel, Hal J. via llvm-dev
2018-Dec-04 16:16 UTC
[llvm-dev] [cfe-dev] RFC: Supported Optimizations attribute
On 12/4/18 1:49 AM, John McCall via cfe-dev wrote: On 4 Dec 2018, at 1:45, Sanjoy Das wrote: 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"? Piotr's proposal unfortunately doesn't give us a good name for the class of optimizations that require being listed in supported_optimizations. In earlier discussions I called them "brittle", but I can understand why nobody wants to call their optimization that, so let's call them "good-faith optimizations" instead since they rely on the good faith of all the participating code. Every optimization has to know how to maintain the structural rules of LLVM IR; that's what makes them structural rules. We don't want the set of structural rules to substantially change because such-and-such good-faith optimization is in effect because that would require arbitrary transforms to check the supported_optimizations list before they knew which rules to follow. Instead, the burden is on the optimization designer to pick IR constructs that won't be messed up by an arbitrary transform with no special knowledge of the optimization. The only thing the optimization designer can rely on is this: * other transforms will preserve the apparent semantics of the function and * other transforms will maintain the standard structural rules of LLVM IR. For example, if you need arbitrary side-effects to not be re-ordered past some point in the function, you should put an instruction there that inhibits that kind of code motion, probably by making it look like a call to an unknown function. No transform can reorder arbitrary side-effects across such a call because doing so might change the apparent semantics of the program. Similarly, if you need a direct use-def link between two points in the function, you should make the first point define a token that'll be used by the second point. No transform will break or abstract that association because that would violate the basic structural rules of IR. If there's a structural rule that can't be expressed with the current tools of IR, we can talk about how to fix that --- although tokens are such a big hammer that I'd be somewhat surprised to hear that something really can't be expressed at all (but much less surprised to hear that the token rules are too strong and we'd like other transforms to have more power to change the code). So the defining property of a good-faith optimization is that: - there are rules which participating functions are expected to follow on pain of undefined behavior but which LLVM IR doesn't require every function to follow, and - those rules will be preserved by any transform that doesn't move code between functions and which preserves the apparent function semantics and maintains the standard structural rules of LLVM IR. I like these conditions, in terms of bounding what this means. We might need to be more explicit about what moves code means, as we're run into fuzzy lines before around inter-procedural optimizations (e.g., return-value propagation, using the 'returned' attribute, and variants). Would it work to say "move code with potential side effects"? Thanks again, Hal I think that answers your question about what sort of rules we can expect supported_optimizations to guarantee. John. _______________________________________________ cfe-dev mailing list cfe-dev at lists.llvm.org<mailto:cfe-dev at lists.llvm.org> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev -- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181204/bf603754/attachment.html>
Sanjoy Das via llvm-dev
2018-Dec-04 18:16 UTC
[llvm-dev] RFC: Supported Optimizations attribute
On Mon, Dec 3, 2018 at 11:49 PM John McCall <jmccall at apple.com> wrote:> Piotr's proposal unfortunately doesn't give us a good name for the class > of optimizations that require being listed in supported_optimizations. > In earlier discussions I called them "brittle", but I can understand why > nobody wants to call their optimization that, so let's call them > "good-faith optimizations" instead since they rely on the good faith of > all the participating code. > > Every optimization has to know how to maintain the structural rules of > LLVM IR; that's what makes them structural rules. We don't want the set of > structural rules to substantially change because such-and-such good-faith > optimization is in effect because that would require arbitrary transforms > to check the supported_optimizations list before they knew which rules to > follow. Instead, the burden is on the optimization designer to pick IR > constructs that won't be messed up by an arbitrary transform with no special > knowledge of the optimization. The only thing the optimization designer > can rely on is this: > > other transforms will preserve the apparent semantics of the function and > other transforms will maintain the standard structural rules of LLVM IR.Ok. Just to make sure we're on the same page, if this was all there is we would not need this attribute right? All LLVM optimizations do need to preserve semantics and structural properties anyway?> So the defining property of a good-faith optimization is that: > - there are rules which participating functions are expected to follow on > pain of undefined behavior but which LLVM IR doesn't require every function > to follow, and > - those rules will be preserved by any transform that doesn't move code > between functions and which preserves the apparent function semantics > and maintains the standard structural rules of LLVM IR.In other words, certain things are UB in functions tagged with supported_optimizations that are not UB otherwise? This breaks code hoisting transformations right? I.e. isSafeToSpeculativelyExecute(Inst) will have to return false if Inst is in a function with a non-empty supported_optimizations? -- Sanjoy