i think attributes have taken control flow into account. I think readnone and nounwind functions are not safe to speculative execute because the function could run indefinitely, e.g. an infinite loop. -Xin On Tuesday, July 14, 2015, Philip Reames <listmail at philipreames.com> wrote:> On 07/14/2015 10:25 PM, Hal Finkel wrote: > >> ----- Original Message ----- >> >>> From: "Philip Reames" <listmail at philipreames.com> >>> To: "Thomas F Raoux" <thomas.f.raoux at intel.com>, llvmdev at cs.uiuc.edu >>> Sent: Tuesday, July 14, 2015 11:59:49 PM >>> Subject: Re: [LLVMdev] LICM for function calls >>> >>> On 07/14/2015 07:45 AM, Raoux, Thomas F wrote: >>> >>>> Hi, >>>> >>>> Right now in LICM (and many other transformations) we always assume >>>> it is never safe to speculatively execute a function call. >>>> >>>> The following function always return false for all function calls >>>> except for few intrinsics: >>>> bool llvm::isSafeToSpeculativelyExecute(const Value *V, >>>> const DataLayout *TD) { >>>> ... >>>> case Instruction::Call: { >>>> if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { >>>> ... >>>> } >>>> return false; // The called function could have undefined >>>> behavior or >>>> // side-effects, even if marked readnone >>>> nounwind. >>>> >>>> In some cases this could have an important performance impact so >>>> I'm looking for a potential way to improve it. >>>> >>>> Is there any combination of attributes which would guarantee that a >>>> function is safe to speculatively execute a function call? (As far >>>> as I can tell there isn't.) >>>> >>> In general, no there isn't. The challenge is that a function's >>> attributes can be control dependent. For example, you can have a >>> function which is "readnone argmemonly nounwind" which writes the >>> entire >>> heap if the global "c" is true. Hoisting a call to such a function >>> above "if (!c)" would be problematic. I think that in practice this >>> is >>> mostly an issue with call site attributes, but I believe the same >>> conceptual problem applies to attributes on function declarations as >>> well. >>> >> I'm fairly certain we already consider declaration attributes to have no >> control dependencies. >> > If true, this would be great. I wasn't sure what the rules here were and > was trying to be conservative. If nothing else, we need to clarify the > docs and make sure everyone is actually in agreement about this. > >> >> -Hal >> >> Changing that might be reasonable, but we'd need to spec it >>> carefully. I think there's room here for improvement, but it'll >>> likely >>> be a slow process at first. >>> >>> One area you might look into is the "guaranteed to execute" notion in >>> LICM. This gives a basis for hoisting a call out of a loop which >>> doesn't require speculating it past any relevant control dependence. >>> You still have to worry about aliasing for safety, but reasoning >>> about >>> the semantics of attributes and faults should be a bit more straight >>> forward. >>> >>>> Does anybody have a suggestion on what would be the best way to >>>> implement such functionality? Or do you think such optimization is >>>> undesirable? >>>> >>>> Cheers, >>>> Thomas >>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >>> > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150715/8ac9e970/attachment.html>
----- Original Message -----> From: "Xin Tong" <trent.xin.tong at gmail.com> > To: "Philip Reames" <listmail at philipreames.com> > Cc: "Hal Finkel" <hfinkel at anl.gov>, llvmdev at cs.uiuc.edu > Sent: Wednesday, July 15, 2015 6:35:11 PM > Subject: Re: [LLVMdev] LICM for function calls > > i think attributes have taken control flow into account. I think > readnone and nounwind functions are not safe to speculative execute > because the function could run indefinitely, e.g. an infinite loop.Yes and no. Our readnone is meant to be modeled on GCC's 'pure' attribute, and as documented (https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes) cannot be applied to functions containing infinite loops. It says specifically, "Interesting non-pure functions are functions with infinite loops or those depending on volatile memory or ..." And so, no, readnone functions must return normally in a finite period of time. However, we also have a long-standing issue here, in that, the FunctionAttrs transformation will add readnone to functions that don't have side effects, regardless of whether or not they potentially have infinite loops. This is not wrong for C/C++, etc. where we get to assume termination of loops, but may cause problems for other languages where infinite loops are well defined. However, infrastructure-wise, it is hard to fix this problem, because FunctionAttrs runs well before the loop canonicalization that would make it easy to determine loop trip counts (even assuming the pass manager were fixed to allow a CGSCC pass to use SCEV in the first place). What we really need here, I suspect, is some attribute indicating C-like termination semantics that can be attached to functions from such languages and will allow us to infer things like readnone without actually doing loop analysis when the semantics of the source language allows it. -Hal> -Xin > > On Tuesday, July 14, 2015, Philip Reames < listmail at philipreames.com > > wrote: > > > On 07/14/2015 10:25 PM, Hal Finkel wrote: > > > ----- Original Message ----- > > > From: "Philip Reames" < listmail at philipreames.com > > To: "Thomas F Raoux" < thomas.f.raoux at intel.com >, > llvmdev at cs.uiuc.edu > Sent: Tuesday, July 14, 2015 11:59:49 PM > Subject: Re: [LLVMdev] LICM for function calls > > On 07/14/2015 07:45 AM, Raoux, Thomas F wrote: > > > Hi, > > Right now in LICM (and many other transformations) we always assume > it is never safe to speculatively execute a function call. > > The following function always return false for all function calls > except for few intrinsics: > bool llvm::isSafeToSpeculativelyExecute(const Value *V, > const DataLayout *TD) { > ... > case Instruction::Call: { > if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { > ... > } > return false; // The called function could have undefined > behavior or > // side-effects, even if marked readnone > nounwind. > > In some cases this could have an important performance impact so > I'm looking for a potential way to improve it. > > Is there any combination of attributes which would guarantee that a > function is safe to speculatively execute a function call? (As far > as I can tell there isn't.) > In general, no there isn't. The challenge is that a function's > attributes can be control dependent. For example, you can have a > function which is "readnone argmemonly nounwind" which writes the > entire > heap if the global "c" is true. Hoisting a call to such a function > above "if (!c)" would be problematic. I think that in practice this > is > mostly an issue with call site attributes, but I believe the same > conceptual problem applies to attributes on function declarations as > well. > I'm fairly certain we already consider declaration attributes to have > no control dependencies. > If true, this would be great. I wasn't sure what the rules here were > and was trying to be conservative. If nothing else, we need to > clarify the docs and make sure everyone is actually in agreement > about this. > > > > -Hal > > > > Changing that might be reasonable, but we'd need to spec it > carefully. I think there's room here for improvement, but it'll > likely > be a slow process at first. > > One area you might look into is the "guaranteed to execute" notion in > LICM. This gives a basis for hoisting a call out of a loop which > doesn't require speculating it past any relevant control dependence. > You still have to worry about aliasing for safety, but reasoning > about > the semantics of attributes and faults should be a bit more straight > forward. > > > Does anybody have a suggestion on what would be the best way to > implement such functionality? Or do you think such optimization is > undesirable? > > Cheers, > Thomas > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
On 07/15/2015 07:05 PM, Hal Finkel wrote:> ----- Original Message ----- >> From: "Xin Tong" <trent.xin.tong at gmail.com> >> To: "Philip Reames" <listmail at philipreames.com> >> Cc: "Hal Finkel" <hfinkel at anl.gov>, llvmdev at cs.uiuc.edu >> Sent: Wednesday, July 15, 2015 6:35:11 PM >> Subject: Re: [LLVMdev] LICM for function calls >> >> i think attributes have taken control flow into account. I think >> readnone and nounwind functions are not safe to speculative execute >> because the function could run indefinitely, e.g. an infinite loop. > Yes and no. Our readnone is meant to be modeled on GCC's 'pure' attribute, and as documented (https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes) cannot be applied to functions containing infinite loops. It says specifically, "Interesting non-pure functions are functions with infinite loops or those depending on volatile memory or ..." > > And so, no, readnone functions must return normally in a finite period of time. > > However, we also have a long-standing issue here, in that, the FunctionAttrs transformation will add readnone to functions that don't have side effects, regardless of whether or not they potentially have infinite loops. This is not wrong for C/C++, etc. where we get to assume termination of loops, but may cause problems for other languages where infinite loops are well defined. > > However, infrastructure-wise, it is hard to fix this problem, because FunctionAttrs runs well before the loop canonicalization that would make it easy to determine loop trip counts (even assuming the pass manager were fixed to allow a CGSCC pass to use SCEV in the first place). What we really need here, I suspect, is some attribute indicating C-like termination semantics that can be attached to functions from such languages and will allow us to infer things like readnone without actually doing loop analysis when the semantics of the source language allows it.Hal, I disagree with your take here. I agree that the current optimizer is a bit muddied about how it treats potentially infinite loops, but I see nothing in the documentation that says we can assume C++ semantics for llvm IR. In fact, there's an example of an infinite loop given in the LangRef as an example of valid code. :) (PHI Instruction example) Given the lack of that, I would argue that the current state is that readonly is pretty clearly different from gcc's pure attribute. I would argue that the bugs is that we DCE readonly functions which might contain infinite loops. :)> > -Hal > >> -Xin >> >> On Tuesday, July 14, 2015, Philip Reames < listmail at philipreames.com >>> wrote: >> >> On 07/14/2015 10:25 PM, Hal Finkel wrote: >> >> >> ----- Original Message ----- >> >> >> From: "Philip Reames" < listmail at philipreames.com > >> To: "Thomas F Raoux" < thomas.f.raoux at intel.com >, >> llvmdev at cs.uiuc.edu >> Sent: Tuesday, July 14, 2015 11:59:49 PM >> Subject: Re: [LLVMdev] LICM for function calls >> >> On 07/14/2015 07:45 AM, Raoux, Thomas F wrote: >> >> >> Hi, >> >> Right now in LICM (and many other transformations) we always assume >> it is never safe to speculatively execute a function call. >> >> The following function always return false for all function calls >> except for few intrinsics: >> bool llvm::isSafeToSpeculativelyExecute(const Value *V, >> const DataLayout *TD) { >> ... >> case Instruction::Call: { >> if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { >> ... >> } >> return false; // The called function could have undefined >> behavior or >> // side-effects, even if marked readnone >> nounwind. >> >> In some cases this could have an important performance impact so >> I'm looking for a potential way to improve it. >> >> Is there any combination of attributes which would guarantee that a >> function is safe to speculatively execute a function call? (As far >> as I can tell there isn't.) >> In general, no there isn't. The challenge is that a function's >> attributes can be control dependent. For example, you can have a >> function which is "readnone argmemonly nounwind" which writes the >> entire >> heap if the global "c" is true. Hoisting a call to such a function >> above "if (!c)" would be problematic. I think that in practice this >> is >> mostly an issue with call site attributes, but I believe the same >> conceptual problem applies to attributes on function declarations as >> well. >> I'm fairly certain we already consider declaration attributes to have >> no control dependencies. >> If true, this would be great. I wasn't sure what the rules here were >> and was trying to be conservative. If nothing else, we need to >> clarify the docs and make sure everyone is actually in agreement >> about this. >> >> >> >> -Hal >> >> >> >> Changing that might be reasonable, but we'd need to spec it >> carefully. I think there's room here for improvement, but it'll >> likely >> be a slow process at first. >> >> One area you might look into is the "guaranteed to execute" notion in >> LICM. This gives a basis for hoisting a call out of a loop which >> doesn't require speculating it past any relevant control dependence. >> You still have to worry about aliasing for safety, but reasoning >> about >> the semantics of attributes and faults should be a bit more straight >> forward. >> >> >> Does anybody have a suggestion on what would be the best way to >> implement such functionality? Or do you think such optimization is >> undesirable? >> >> Cheers, >> Thomas >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>