[LLVMdev] LICM for function calls

Hal Finkel hfinkel at anl.gov
Sun Jul 19 21:21:56 PDT 2015 

----- Original Message -----
> From: "Hal Finkel" <hfinkel at anl.gov>
> To: "Philip Reames" <listmail at philipreames.com>
> Cc: llvmdev at cs.uiuc.edu, "Xin Tong" <trent.xin.tong at gmail.com>
> Sent: Sunday, July 19, 2015 11:14:21 PM
> Subject: Re: [LLVMdev] LICM for function calls
> 
> ----- Original Message -----
> > From: "Philip Reames" <listmail at philipreames.com>
> > To: "Hal Finkel" <hfinkel at anl.gov>, "Xin Tong"
> > <trent.xin.tong at gmail.com>
> > Cc: llvmdev at cs.uiuc.edu
> > Sent: Friday, July 17, 2015 7:38:31 PM
> > Subject: Re: [LLVMdev] LICM for function calls
> > 
> > 
> > 
> > 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)
> 
> As you might suppose from the thread I started on infinite loops, I
> don't disagree that the IR supports infinite loops (or at least
> should).
> 
> > 
> > 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.  :)
> 
> I was arguing that, in practice, readonly/readnone are used to
> represent GCC's pure/const attributes (in Clang) and weakening that
> relationship must be done carefully as to not regress existing
> users. FWIW, prior to r44273 (way back in 2007) these attributes
> were actually named pure and const; and this issue came up in 2010
> (http://permalink.gmane.org/gmane.comp.compilers.llvm.devel/31490).

Specifically, I mean that it came up in 2010 in a context supporting your conclusion that this should be fixed. It was not, however.

 -Hal

> Indeed, I agree we should fix this, but we should not do so until we
> have a mechanism to retain the current semantics for the Clang users
> who rightfully benefit from them (from their point of view,
> pure/const are behaving as documented). This was one of the major
> motivations for starting the thread on infinite loops.
> 
> Thanks again,
> Hal
> 
> > >
> > >   -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
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

More information about the llvm-dev mailing list