Hal Finkel via llvm-dev
2020-Jan-30 04:58 UTC
[llvm-dev] [RFC] How to manifest information in LLVM-IR, or, revisiting llvm.assume
Hi, Johannes, Thanks for working on this. This seems like a good approach which nicely extends the set of capabilities we have now. One additional comment, as I agree with everything in your rationale, except this:> - Reconstructing information from the pattern of instructions that feed > into the `llvm.assume` is also not optimal, especially since we do > not need to "optimize" these instructions anyway.I don't understand what you mean by the reconstructing the pattern from the instructions not being optimal, but in general, we do need to optimize the instructions forming the assumption condition. The expressions might have calls that should be inlined, or as a general matter, have expressions involving temporaries that need to be simplified (especially soon as you start allowing expressions that might have side effects, you'll also have to deal with temporaries that are materialized to the stack). There is also the matter of inter-procedural code sinking that will come up (assuming that we want to, with this mechanism, get rid of the existing ephemeral-values concept and utility functions). Instructions in the function containing the assumption, that are only used by the assumption, we'll want to sink in the outlined assumption function. I believe you're thinking about addressing this with outlining, but I think that these are separate issues because the outlining needs to be done early. Regarding this late-outlining approach:> A prototype for both operand bundle assumptions and outlined assumptions > is available herehttps://reviews.llvm.org/D71692. Note that most code > is required do to the outlining [see rational in point C) below]. This > is not as actively purposed for now as the operand bundle use.I don't see how this can work in the case where you have side effects. Once you generate the code in the function containing the assume, if that code has side effects, it's can't be later deleted and moved into the assumption. One might make an argument that we can do this for non-volatile loads (because if the load is used only by the assumption it will be removed anyway), but for stores and other things that will appear from general expressions, it won't be sound to outline them later. We can't know if the side effect is supposed to be there or not, so the outlining needs to happen in the frontend. -Hal>> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory
Doerfert, Johannes via llvm-dev
2020-Jan-30 05:22 UTC
[llvm-dev] [RFC] How to manifest information in LLVM-IR, or, revisiting llvm.assume
On 01/29, Hal Finkel wrote:> Thanks for working on this. This seems like a good approach which nicely > extends the set of capabilities we have now.Great. We will move forward with the operand bundle part and hope for more feedback as we go :)> One additional comment, as I agree with everything in your rationale, except > this: > > > - Reconstructing information from the pattern of instructions that feed > > into the `llvm.assume` is also not optimal, especially since we do > > not need to "optimize" these instructions anyway. > > I don't understand what you mean by the reconstructing the pattern from the > instructions not being optimal, but in general, we do need to optimize the > instructions forming the assumption condition. The expressions might have > calls that should be inlined, or as a general matter, have expressions > involving temporaries that need to be simplified (especially soon as you > start allowing expressions that might have side effects, you'll also have to > deal with temporaries that are materialized to the stack).With "reconstructing the pattern" I meant that we need to figure out over and over again that the following 5 instructions correspond to `"align"(%a + 24, 32)` or `"align"(%a, 16)`. %ptrint = ptrtoint i32* %a to i64 %offsetptr = add i64 %ptrint, 24 %maskedptr = and i64 %offsetptr, 31 %maskcond = icmp eq i64 %maskedptr, 0 tail call void @llvm.assume(i1 %maskcond) The sequence above is basically a hard coded pattern in >=2 places. My argument now is that if you want to express property XYZ on value %V and you do it as `"XYZ"(%V)` it is straightforward to reconstruct later. If we however have to build a non-trivial sequence of instructions to "encode" XYZ into a boolean value we always have to reconstruct the sequence (=pattern).> There is also the matter of inter-procedural code sinking that will come up > (assuming that we want to, with this mechanism, get rid of the existing > ephemeral-values concept and utility functions). Instructions in the > function containing the assumption, that are only used by the assumption, > we'll want to sink in the outlined assumption function. I believe you're > thinking about addressing this with outlining, but I think that these are > separate issues because the outlining needs to be done early. Regarding this > late-outlining approach:For the record, I never intended for "late-outlining" to be used in practise. I wrote it so we can test how outlined assumptions would work. It is a prove of concept that we can outlined the code pattern above, connect the outlined function to the llvm.assume, and still determine the alignment of a pointer. If we move to outlined assumptions we would never generate anything else.> > A prototype for both operand bundle assumptions and outlined assumptions > > is available herehttps://reviews.llvm.org/D71692. Note that most code > > is required do to the outlining [see rational in point C) below]. This > > is not as actively purposed for now as the operand bundle use. > > I don't see how this can work in the case where you have side effects. Once > you generate the code in the function containing the assume, if that code > has side effects, it's can't be later deleted and moved into the assumption.I did not make that clear in my earlier email but I tried to say it above. We would not generate the assumption expression in the user function but directly in the outlined one. The prototype I have can be used to "mimic" the result without requiring me to do non-trivial things in Clang.> One might make an argument that we can do this for non-volatile loads > (because if the load is used only by the assumption it will be removed > anyway), but for stores and other things that will appear from general > expressions, it won't be sound to outline them later. We can't know if the > side effect is supposed to be there or not, so the outlining needs to happen > in the frontend.I totally agree, outlining would need to happen in the frontend, and hopefully implemented by someone other than me ;)> > > _______________________________________________ > > > LLVM Developers mailing list > > > llvm-dev at lists.llvm.org > > > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > -- > Hal Finkel > Lead, Compiler Technology and Programming Languages > Leadership Computing Facility > Argonne National Laboratory >-- Johannes Doerfert Researcher Argonne National Laboratory Lemont, IL 60439, USA jdoerfert at anl.gov -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 228 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200130/2a2b2f4b/attachment.sig>
Hal Finkel via llvm-dev
2020-Jan-30 05:31 UTC
[llvm-dev] [RFC] How to manifest information in LLVM-IR, or, revisiting llvm.assume
On 1/29/20 11:22 PM, Doerfert, Johannes wrote:> On 01/29, Hal Finkel wrote: >> Thanks for working on this. This seems like a good approach which nicely >> extends the set of capabilities we have now. > Great. We will move forward with the operand bundle part and hope for > more feedback as we go :) > > >> One additional comment, as I agree with everything in your rationale, except >> this: >> >>> - Reconstructing information from the pattern of instructions that feed >>> into the `llvm.assume` is also not optimal, especially since we do >>> not need to "optimize" these instructions anyway. >> I don't understand what you mean by the reconstructing the pattern from the >> instructions not being optimal, but in general, we do need to optimize the >> instructions forming the assumption condition. The expressions might have >> calls that should be inlined, or as a general matter, have expressions >> involving temporaries that need to be simplified (especially soon as you >> start allowing expressions that might have side effects, you'll also have to >> deal with temporaries that are materialized to the stack). > With "reconstructing the pattern" I meant that we need to figure out > over and over again that the following 5 instructions correspond to > `"align"(%a + 24, 32)` or `"align"(%a, 16)`. > > %ptrint = ptrtoint i32* %a to i64 > %offsetptr = add i64 %ptrint, 24 > %maskedptr = and i64 %offsetptr, 31 > %maskcond = icmp eq i64 %maskedptr, 0 > tail call void @llvm.assume(i1 %maskcond) > > The sequence above is basically a hard coded pattern in >=2 places. My > argument now is that if you want to express property XYZ on value %V and > you do it as `"XYZ"(%V)` it is straightforward to reconstruct later. If > we however have to build a non-trivial sequence of instructions to > "encode" XYZ into a boolean value we always have to reconstruct the > sequence (=pattern). > > >> There is also the matter of inter-procedural code sinking that will come up >> (assuming that we want to, with this mechanism, get rid of the existing >> ephemeral-values concept and utility functions). Instructions in the >> function containing the assumption, that are only used by the assumption, >> we'll want to sink in the outlined assumption function. I believe you're >> thinking about addressing this with outlining, but I think that these are >> separate issues because the outlining needs to be done early. Regarding this >> late-outlining approach: > For the record, I never intended for "late-outlining" to be used in > practise. I wrote it so we can test how outlined assumptions would work. > It is a prove of concept that we can outlined the code pattern above, > connect the outlined function to the llvm.assume, and still determine > the alignment of a pointer. If we move to outlined assumptions we would > never generate anything else. > > >>> A prototype for both operand bundle assumptions and outlined assumptions >>> is available herehttps://reviews.llvm.org/D71692. Note that most code >>> is required do to the outlining [see rational in point C) below]. This >>> is not as actively purposed for now as the operand bundle use. >> I don't see how this can work in the case where you have side effects. Once >> you generate the code in the function containing the assume, if that code >> has side effects, it's can't be later deleted and moved into the assumption. > I did not make that clear in my earlier email but I tried to say it > above. We would not generate the assumption expression in the user > function but directly in the outlined one. The prototype I have can be > used to "mimic" the result without requiring me to do non-trivial things > in Clang. > > >> One might make an argument that we can do this for non-volatile loads >> (because if the load is used only by the assumption it will be removed >> anyway), but for stores and other things that will appear from general >> expressions, it won't be sound to outline them later. We can't know if the >> side effect is supposed to be there or not, so the outlining needs to happen >> in the frontend. > I totally agree, outlining would need to happen in the frontend, and > hopefully implemented by someone other than me ;)Sounds good ;) -Hal> > > >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> -- >> Hal Finkel >> Lead, Compiler Technology and Programming Languages >> Leadership Computing Facility >> Argonne National Laboratory >>-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory