LICM for function calls

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.)

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

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. 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.

From: "Philip Reames" <listmail@philipreames.com>
To: "Thomas F Raoux" <thomas.f.raoux@intel.com>, llvmdev@cs.uiuc.edu
Sent: Tuesday, July 14, 2015 11:59:49 PM
Subject: Re: [LLVMdev] LICM for function calls

> 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.

-Hal

From: "Philip Reames" <listmail@philipreames.com>
To: "Thomas F Raoux" <thomas.f.raoux@intel.com>, llvmdev@cs.uiuc.edu
Sent: Tuesday, July 14, 2015 11:59:49 PM
Subject: Re: [LLVMdev] LICM for function calls

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.

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

From: "Xin Tong" <trent.xin.tong@gmail.com>
To: "Philip Reames" <listmail@philipreames.com>
Cc: "Hal Finkel" <hfinkel@anl.gov>, llvmdev@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

From: "Thomas F Raoux" <thomas.f.raoux@intel.com>
To: llvmdev@cs.uiuc.edu
Sent: Tuesday, July 14, 2015 9:45:20 AM
Subject: [LLVMdev] LICM for function calls

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.)

Does anybody have a suggestion on what would be the best way to
implement such functionality? Or do you think such optimization is
undesirable?

I think we'd need some kind of 'safe_to_speculate' attribute on the function. Regarding the optimization, under what circumstances would you want to speculate a function? I can imagine doing this only if I knew the function would be lowered in the backend to some simple set of instructions.

-Hal

The common case is wanting LICM to hoist a loop-invariant function call into the pre-header of a loop where the trip count is unknown - and, in particular, not known to be > 0.

The common case is wanting LICM to hoist a loop-invariant function call into the pre-header of a loop where the trip count is unknown - and, in particular, not known to be > 0.

Just to clarify, I assume that you mean a read only idempotent function right? (i.e. running it only once is not observable vs running it many times in the loop) Or do you mean a read only side effect free function (i.e. running it once is indistinguishable from 0 or many runs)? We could - and should - support both, but they're slightly different.

(I'm assuming no aliasing writes in both cases above.)

From: "Xin Tong" <trent.xin.tong@gmail.com>
To: "Philip Reames" <listmail@philipreames.com>
Cc: "Hal Finkel" <hfinkel@anl.gov>, llvmdev@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. :slight_smile: (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. :slight_smile:

I meant side-effect free.

You cannot hoist an idempotent function with possible side-effects unless you know the loop is going to execute for at least one iteration, in which case, it's not speculation (assuming the function is called within the loop unconditionally, that is).

From: "Philip Reames" <listmail@philipreames.com>
To: "Hal Finkel" <hfinkel@anl.gov>, "Xin Tong" <trent.xin.tong@gmail.com>
Cc: llvmdev@cs.uiuc.edu
Sent: Friday, July 17, 2015 7:38:31 PM
Subject: Re: [LLVMdev] LICM for function calls

>> From: "Xin Tong" <trent.xin.tong@gmail.com>
>> To: "Philip Reames" <listmail@philipreames.com>
>> Cc: "Hal Finkel" <hfinkel@anl.gov>, llvmdev@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. :slight_smile: (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. :slight_smile:

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). 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

From: "Hal Finkel" <hfinkel@anl.gov>
To: "Philip Reames" <listmail@philipreames.com>
Cc: llvmdev@cs.uiuc.edu, "Xin Tong" <trent.xin.tong@gmail.com>
Sent: Sunday, July 19, 2015 11:14:21 PM
Subject: Re: [LLVMdev] LICM for function calls

> From: "Philip Reames" <listmail@philipreames.com>
> To: "Hal Finkel" <hfinkel@anl.gov>, "Xin Tong"
> <trent.xin.tong@gmail.com>
> Cc: llvmdev@cs.uiuc.edu
> Sent: Friday, July 17, 2015 7:38:31 PM
> Subject: Re: [LLVMdev] LICM for function calls
>
>
>
> >> From: "Xin Tong" <trent.xin.tong@gmail.com>
> >> To: "Philip Reames" <listmail@philipreames.com>
> >> Cc: "Hal Finkel" <hfinkel@anl.gov>, llvmdev@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. :slight_smile: (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. :slight_smile:

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