Does nounwind have semantics?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
21 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Does nounwind have semantics?

Andrew Trick
Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...

int32_t foo(int32_t* ptr) {
  int i = 0;
  int result;
  do {
    bar(ptr);
    result = *ptr;
    bar(ptr);
  } while (i++ < *ptr);
  return result;
}

Say we have a front end that declares bar as...

declare void @bar(i32*) readonly;

So 'bar' is 'readonly' and 'may-unwind'.

When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...

There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.

-Andy
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Eli Friedman-2
On Sun, Jul 21, 2013 at 5:56 PM, Andrew Trick <[hidden email]> wrote:

> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>
> int32_t foo(int32_t* ptr) {
>   int i = 0;
>   int result;
>   do {
>     bar(ptr);
>     result = *ptr;
>     bar(ptr);
>   } while (i++ < *ptr);
>   return result;
> }
>
> Say we have a front end that declares bar as...
>
> declare void @bar(i32*) readonly;
>
> So 'bar' is 'readonly' and 'may-unwind'.

It's impossible to write a readonly function which throws a DWARF
exception.  Given that, I would imagine there are all sorts of bugs
nobody has ever run into.

-Eli
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Nick Lewycky
In reply to this post by Andrew Trick
Andrew Trick wrote:

> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>
> int32_t foo(int32_t* ptr) {
>    int i = 0;
>    int result;
>    do {
>      bar(ptr);
>      result = *ptr;
>      bar(ptr);
>    } while (i++<  *ptr);
>    return result;
> }
>
> Say we have a front end that declares bar as...
>
> declare void @bar(i32*) readonly;
>
> So 'bar' is 'readonly' and 'may-unwind'.
>
> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...
>
> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.

Yes, we went through a phase where people would try to use
"nounwind+readonly == no side-effects" to optimize. All such
optimizations are wrong. Unless otherwise proven, a function may
inf-loop, terminate the program, or longjmp.

I tried to add 'halting' to help solve part of this a long time ago, but
it never went in. The problem is that determining whether you have loops
requires a FunctionPass (LoopInfo to find loops and SCEV to determine an
upper bound) and applying function attributes is an SCC operation
(indeed, an SCC is itself a loop), so it's all blocked behind fixing the
PassManager to allow CGSGGPasses to depend on FunctionPasses.
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html

I'm now in a similar situation where I want 'nounwind' to mean "only
exits by terminating the program or a return instruction" but
unfortunately functions which longjmp are considered nounwind. I would
like to change llvm to make longjmp'ing a form of unwinding (an
exceptional exit to the function), but if I were to apply that rule
today then we'd start putting dwarf eh tables on all our C code, oops.

Nick
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Kuperstein, Michael M
I'm not sure I understand why it's blocked on that, by the way.
Even if we can't apply the attribute ourselves, I don't see why we wouldn't expose that ability to frontends.

I'm not entirely sure "halting" is the right attribute either, by the way.
What I, personally, would like to see is a way to specify a function call is safe to speculatively execute. That implies readnone (not just readonly), nounwind, halting - and Eris knows what else. Nick, is that too strong for you?

Michael

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Nick Lewycky
Sent: Monday, July 22, 2013 07:08
To: Andrew Trick
Cc: [hidden email]
Subject: Re: [LLVMdev] Does nounwind have semantics?

Andrew Trick wrote:

> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>
> int32_t foo(int32_t* ptr) {
>    int i = 0;
>    int result;
>    do {
>      bar(ptr);
>      result = *ptr;
>      bar(ptr);
>    } while (i++<  *ptr);
>    return result;
> }
>
> Say we have a front end that declares bar as...
>
> declare void @bar(i32*) readonly;
>
> So 'bar' is 'readonly' and 'may-unwind'.
>
> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...
>
> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.

Yes, we went through a phase where people would try to use "nounwind+readonly == no side-effects" to optimize. All such optimizations are wrong. Unless otherwise proven, a function may inf-loop, terminate the program, or longjmp.

I tried to add 'halting' to help solve part of this a long time ago, but it never went in. The problem is that determining whether you have loops requires a FunctionPass (LoopInfo to find loops and SCEV to determine an upper bound) and applying function attributes is an SCC operation (indeed, an SCC is itself a loop), so it's all blocked behind fixing the PassManager to allow CGSGGPasses to depend on FunctionPasses.
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html

I'm now in a similar situation where I want 'nounwind' to mean "only exits by terminating the program or a return instruction" but unfortunately functions which longjmp are considered nounwind. I would like to change llvm to make longjmp'ing a form of unwinding (an exceptional exit to the function), but if I were to apply that rule today then we'd start putting dwarf eh tables on all our C code, oops.

Nick
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Duncan Sands
In reply to this post by Andrew Trick
Hi Andrew,

On 22/07/13 02:56, Andrew Trick wrote:

> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>
> int32_t foo(int32_t* ptr) {
>    int i = 0;
>    int result;
>    do {
>      bar(ptr);
>      result = *ptr;
>      bar(ptr);
>    } while (i++ < *ptr);
>    return result;
> }
>
> Say we have a front end that declares bar as...
>
> declare void @bar(i32*) readonly;
>
> So 'bar' is 'readonly' and 'may-unwind'.
>
> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...

is your worry here about the following case?
  - the load will trap if executed
  - bar throws an exception
Thus with the original code the trap will not occur, because an exception will
be thrown first, while if you move the first bar call below the load then the
tap will occur.

>
> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program.

I'm pretty sure that exiting the program is considered to write memory, so bar
can't do that itself.

Ciao, Duncan.

  This is interesting, because that is the way runtime checks for safe languages
would like to be defined. I'm perfectly happy telling front ends to generate
control flow for well-defined traps, since I like lots of basic blocks in my IR.
But I'm still curious how others deal with this.
>
> -Andy
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Duncan Sands
In reply to this post by Eli Friedman-2
Hi Eli,

On 22/07/13 03:37, Eli Friedman wrote:

> On Sun, Jul 21, 2013 at 5:56 PM, Andrew Trick <[hidden email]> wrote:
>> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>>
>> int32_t foo(int32_t* ptr) {
>>    int i = 0;
>>    int result;
>>    do {
>>      bar(ptr);
>>      result = *ptr;
>>      bar(ptr);
>>    } while (i++ < *ptr);
>>    return result;
>> }
>>
>> Say we have a front end that declares bar as...
>>
>> declare void @bar(i32*) readonly;
>>
>> So 'bar' is 'readonly' and 'may-unwind'.
>
> It's impossible to write a readonly function which throws a DWARF
> exception.  Given that, I would imagine there are all sorts of bugs
> nobody has ever run into.

very true.  That said, it is a pity not to support other ways of doing
exception handling.  For example, you could declare every function to return
two results, the usual one and an additional i1 result.  If the i1 value
returned is 1 then this means that "an exception is being unwound", and the
caller should jump to the landing pad if there is one; and if there isn't then
it itself should return 1.  This scheme doesn't write memory.  OK, now imagine
implementing this scheme where the additional return value is hidden, only
implicitly present.  You can argue that the function still doesn't write
memory, though I admit you could also argue that the only way we have to model
this extra parameter is to say that the function writes memory.  What is a bit
more problematic is that there is then also an implicit control flow construct
("if exception_value == 1 then return 1; end if") after every call.  If
everything was explicit then the above code
   bar(ptr);
   result = *ptr;
   bar(ptr);
would be
   exc = bar(ptr);
   if (exc) return 1;
   result = *ptr;
   exc = bar(ptr);
   if (exc) return 1;
At this point it is clear that because bar is readonly, the second bar call can
be dropped, giving
   exc = bar(ptr);
   if (exc) return 1;
   result = *ptr;
However it would have been wrong to drop the first bar call.  This is all
obvious when there are no hidden parameters and everything is explicit.  I
can't help feeling that either we should require everything to be explicit
like this, or if it is implicit then probably we should say that bar does
write memory (the invisible return parameter).  But even then the implicit
control flow after the bar call isn't modelled (already the case with the
usual exception handling) which is an endless source of little bugs, though
in practice as people don't raise exceptions much the bugs aren't noticed...

Ciao, Duncan.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Nick Lewycky
In reply to this post by Kuperstein, Michael M
Kuperstein, Michael M wrote:
> I'm not sure I understand why it's blocked on that, by the way.

It blocks our ability to automatically deduce the halting attribute in
the optimizer, which was necessary for the use case I had at the time.
If you have a use case of your own, feel free to propose the patch!

(Technically it's not *blocked* -- see how my patch does it! -- but the
workarounds are too horrible to be committed.)

> Even if we can't apply the attribute ourselves, I don't see why we wouldn't expose that ability to frontends.

Frontends are free to put attributes on functions if they want to. Go
for it!

> I'm not entirely sure "halting" is the right attribute either, by the way.
> What I, personally, would like to see is a way to specify a function call is safe to speculatively execute. That implies readnone (not just readonly), nounwind, halting - and Eris knows what else. Nick, is that too strong for you?

I strongly prefer the approach of having orthogonal attributes. There
are optimizations that you can do with each of these attributes on their
own. In particular I think that readonly+halting+nounwind+nolongjmp is
going to be common and I'd feel  silly if we had a special case for
readnone+halting+nounwind+nolongjmp and thus couldn't optimize the more
common case.

That said, I'm also going to feel silly if we don't end up with enough
attributes to allow isSafeToSpeculate to deduce it, which is where we
are right now. I was planning to get back to fixing this after
Chandler's promised PassManager work.

Nick

>
> Michael
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Nick Lewycky
> Sent: Monday, July 22, 2013 07:08
> To: Andrew Trick
> Cc: [hidden email]
> Subject: Re: [LLVMdev] Does nounwind have semantics?
>
> Andrew Trick wrote:
>> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>>
>> int32_t foo(int32_t* ptr) {
>>     int i = 0;
>>     int result;
>>     do {
>>       bar(ptr);
>>       result = *ptr;
>>       bar(ptr);
>>     } while (i++<   *ptr);
>>     return result;
>> }
>>
>> Say we have a front end that declares bar as...
>>
>> declare void @bar(i32*) readonly;
>>
>> So 'bar' is 'readonly' and 'may-unwind'.
>>
>> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...
>>
>> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.
>
> Yes, we went through a phase where people would try to use "nounwind+readonly == no side-effects" to optimize. All such optimizations are wrong. Unless otherwise proven, a function may inf-loop, terminate the program, or longjmp.
>
> I tried to add 'halting' to help solve part of this a long time ago, but it never went in. The problem is that determining whether you have loops requires a FunctionPass (LoopInfo to find loops and SCEV to determine an upper bound) and applying function attributes is an SCC operation (indeed, an SCC is itself a loop), so it's all blocked behind fixing the PassManager to allow CGSGGPasses to depend on FunctionPasses.
> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html
>
> I'm now in a similar situation where I want 'nounwind' to mean "only exits by terminating the program or a return instruction" but unfortunately functions which longjmp are considered nounwind. I would like to change llvm to make longjmp'ing a form of unwinding (an exceptional exit to the function), but if I were to apply that rule today then we'd start putting dwarf eh tables on all our C code, oops.
>
> Nick
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Andrew Trick
In reply to this post by Duncan Sands

On Jul 21, 2013, at 11:55 PM, Duncan Sands <[hidden email]> wrote:

Hi Andrew,

On 22/07/13 02:56, Andrew Trick wrote:
Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...

int32_t foo(int32_t* ptr) {
  int i = 0;
  int result;
  do {
    bar(ptr);
    result = *ptr;
    bar(ptr);
  } while (i++ < *ptr);
  return result;
}

Say we have a front end that declares bar as...

declare void @bar(i32*) readonly;

So 'bar' is 'readonly' and 'may-unwind'.

When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...

is your worry here about the following case?
- the load will trap if executed
- bar throws an exception
Thus with the original code the trap will not occur, because an exception will
be thrown first, while if you move the first bar call below the load then the
tap will occur.

Essentially, yes. My takeaway from looking into it is:

- nounwind means no dwarf EH. Absence of nounwind means absence of dwarf EH. It would be unwise for optimization passes to reason about the semantics beyond that. I was momentarily mislead by the LICM code that handles MayThrow specially.

- Things that throw exceptions or trap in defined ways are not readonly.

- Runtime checks for overflow, div-by-zero, bounds checks, etc. should be implemented at the IR level as branches to noreturn calls because it can be done that way and I haven’t seen concrete evidence that it’s too expensive. Don’t try to do something fancy with intrinsics and attributes unless absolutely required.

- Optimizing readonly calls in C is a tangentially related issue, as Nick explained. My answer to that problem is that C compilers are effectively forced to assume that calls terminate, so developers should not expect otherwise. If C developers don’t want the compiler to optimize their infinite loop or infinite recursion, they need to throw in a volatile dereference.

-Andy


There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program.

I'm pretty sure that exiting the program is considered to write memory, so bar
can't do that itself.

Ciao, Duncan.

This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.

-Andy
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Duncan Sands
Hi Andrew,

On 22/07/13 09:32, Andrew Trick wrote:

>
> On Jul 21, 2013, at 11:55 PM, Duncan Sands <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>> Hi Andrew,
>>
>> On 22/07/13 02:56, Andrew Trick wrote:
>>> Does 'nounwind' have semantics that inform optimization passes? It seems to
>>> in some cases, but not consistently. For example...
>>>
>>> int32_t foo(int32_t* ptr) {
>>>   int i = 0;
>>>   int result;
>>>   do {
>>>     bar(ptr);
>>>     result = *ptr;
>>>     bar(ptr);
>>>   } while (i++ < *ptr);
>>>   return result;
>>> }
>>>
>>> Say we have a front end that declares bar as...
>>>
>>> declare void @bar(i32*) readonly;
>>>
>>> So 'bar' is 'readonly' and 'may-unwind'.
>>>
>>> When LICM tries to hoist the load it interprets the 'may-unwind' as
>>> "MayThrow" in LICM-language and bails. However, when it tries to sink the
>>> call itself it sees the 'readonly', assumes no side effects and sinks it
>>> below the loads. Hmm...
>>
>> is your worry here about the following case?
>> - the load will trap if executed
>> - bar throws an exception
>> Thus with the original code the trap will not occur, because an exception will
>> be thrown first, while if you move the first bar call below the load then the
>> tap will occur.
>
> Essentially, yes. My takeaway from looking into it is:

my understanding is different.  I'm pretty sure that what I'm about to say is
the traditional way these things have been viewed in LLVM.  That doesn't mean
that it's the best way to view these things.

> - nounwind means no dwarf EH. Absence

I guess you mean presence.

  of nounwind means absence of dwarf EH. It
> would be unwise for optimization passes to reason about the semantics beyond
> that. I was momentarily mislead by the LICM code that handles MayThrow specially.

nounwind has nothing to do with dwarf, since exceptions themselves need have
nothing to do with dwarf (which is just one way of implementing exception
handling).  Don't forget setjmp/longjmp exception handling, and also exception
handling by returning an extra invisible parameter (which I mentioned in
another email) which IIRC was actually implemented by someone at the codegen
level at some point as it was faster than dwarf for code that throws exceptions
a lot.  An additional point is that while in C++ you create an exception object,
not all languages associate an object with an exception, some just want to do
the equivalent of a non-local goto.  Creating an exception object means
allocating memory, mucking around with global data structures and obviously
writing memory.  A non-local goto doesn't have to do more than unwind the stack
until it gets to the right frame then do a jump.  It's not clear to me that that
should be considered as writing memory.

Here's my take: a call to an function marked nounwind either never returns
(eg infinite loop or exits the program) or returns normally.  It doesn't
"return" by unwinding the stack out of the caller.  On the other hand a
function that is not marked nounwind may "return" by unwinding the stack;
control in this case doesn't continue in the caller, it continues at least one
further up the stack.  Thus in this case the instructions after the call
instruction are not executed.  Note I'm talking about an ordinary call here,
not an invoke.  In the case of an invoke control may continue in the caller
function, but only at a well-defined point (the landing pad).

> - Things that throw exceptions or trap in defined ways are not readonly.

See above for why throwing an exception doesn't have to write memory.  Dwarf
exception handling, and anything which can be used to implement C++ exception
handling, is clearly writing memory and thus cannot be used inside a readonly
function.  So yes, any function Clang produces that throws an exception is not
going to be readonly.  But as I mentioned above some languages have no
exception object and just unwind the stack.  For these the expression "throwing
an exception" (which implicitly includes the idea that there is an exception
object) is not really appropriate; "unwinds the stack" is the basic concept
here.  This is basically orthogonal to readonly.

> - Runtime checks for overflow, div-by-zero, bounds checks, etc. should be
> implemented at the IR level as branches to noreturn calls because it can be done
> that way and I haven’t seen concrete evidence that it’s too expensive. Don’t try
> to do something fancy with intrinsics and attributes unless absolutely required.

I agree with this.

Ciao, Duncan.

> - Optimizing readonly calls in C is a tangentially related issue, as Nick
> explained. My answer to that problem is that C compilers are effectively forced
> to assume that calls terminate, so developers should not expect otherwise. If C
> developers don’t want the compiler to optimize their infinite loop or infinite
> recursion, they need to throw in a volatile dereference.
>
> -Andy
>
>>>
>>> There doesn't appear to be a way to declare a function that is guaranteed not
>>> to write to memory in a way that affects the caller, but may have another
>>> well-defined side effect like aborting the program.
>>
>> I'm pretty sure that exiting the program is considered to write memory, so bar
>> can't do that itself.
>>
>> Ciao, Duncan.
>>
>> This is interesting, because that is the way runtime checks for safe languages
>> would like to be defined. I'm perfectly happy telling front ends to generate
>> control flow for well-defined traps, since I like lots of basic blocks in my
>> IR. But I'm still curious how others deal with this.
>>>
>>> -Andy
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> [hidden email] <mailto:[hidden email]>http://llvm.cs.uiuc.edu
>>> <http://llvm.cs.uiuc.edu/>
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> [hidden email] <mailto:[hidden email]>http://llvm.cs.uiuc.edu
>> <http://llvm.cs.uiuc.edu/>
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Kuperstein, Michael M
In reply to this post by Nick Lewycky
Of course frontends are free to put attributes, but it would be nice if optimizations actually used them. ;-)
My use case is that of proprietary frontend that happens to know some library function calls - which are only resolved at link time - have no side effects and are safe to execute speculatively, and wants to tell the optimizer it can move them around however it likes. I'll gladly submit a patch that uses these hints, but I'd like to reach some consensus on what the desired attributes actually are first. The last thing I want is to add attributes that are only useful to myself.

Regarding having several orthogonal attributes vs. things like "safetospeculate":

To know a function is safe to speculatively execute, I need at least:
1) readnone (readonly is insufficient, unless I know all accessed pointers are valid)
2) nounwind
3) nolongjmp (I guess?)
4) no undefined behavior. This includes things like "halting" and "no division by zero", but that's not, by far, an exhaustive list.

I guess there are several ways to handle (4).
Ideally, I agree with you, we'd like a set of orthogonal attributes that, taken together, imply that the function's behavior is not undefined.
But that requires mapping all sources of undefined behavior (I don't think this is currently documented for LLVM IR, at least not in a centralized fashion) and adding a very specific attribute for each of them. I'm not sure having function declarations with "readnone, nounwind, nolongjmp, halting, nodivbyzero, nopoisonval, nocomparelabels, nounreachable, ..." is desirable.

We could also have a "welldefined" attribute and a "halting" attribute where "welldefined" subsumes "halting", if the specific case of a function which halts but may have undefined behavior is important.
While the two are not orthogonal, it's similar to the situation with "readnone" and "readonly". Does that sound reasonable?

Michael

-----Original Message-----
From: Nick Lewycky [mailto:[hidden email]]
Sent: Monday, July 22, 2013 10:24
To: Kuperstein, Michael M
Cc: Andrew Trick; [hidden email]
Subject: Re: [LLVMdev] Does nounwind have semantics?

Kuperstein, Michael M wrote:
> I'm not sure I understand why it's blocked on that, by the way.

It blocks our ability to automatically deduce the halting attribute in the optimizer, which was necessary for the use case I had at the time.
If you have a use case of your own, feel free to propose the patch!

(Technically it's not *blocked* -- see how my patch does it! -- but the workarounds are too horrible to be committed.)

> Even if we can't apply the attribute ourselves, I don't see why we wouldn't expose that ability to frontends.

Frontends are free to put attributes on functions if they want to. Go for it!

> I'm not entirely sure "halting" is the right attribute either, by the way.
> What I, personally, would like to see is a way to specify a function call is safe to speculatively execute. That implies readnone (not just readonly), nounwind, halting - and Eris knows what else. Nick, is that too strong for you?

I strongly prefer the approach of having orthogonal attributes. There are optimizations that you can do with each of these attributes on their own. In particular I think that readonly+halting+nounwind+nolongjmp is going to be common and I'd feel  silly if we had a special case for
readnone+halting+nounwind+nolongjmp and thus couldn't optimize the more
common case.

That said, I'm also going to feel silly if we don't end up with enough
attributes to allow isSafeToSpeculate to deduce it, which is where we
are right now. I was planning to get back to fixing this after
Chandler's promised PassManager work.

Nick

>
> Michael
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Nick Lewycky
> Sent: Monday, July 22, 2013 07:08
> To: Andrew Trick
> Cc: [hidden email]
> Subject: Re: [LLVMdev] Does nounwind have semantics?
>
> Andrew Trick wrote:
>> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>>
>> int32_t foo(int32_t* ptr) {
>>     int i = 0;
>>     int result;
>>     do {
>>       bar(ptr);
>>       result = *ptr;
>>       bar(ptr);
>>     } while (i++<   *ptr);
>>     return result;
>> }
>>
>> Say we have a front end that declares bar as...
>>
>> declare void @bar(i32*) readonly;
>>
>> So 'bar' is 'readonly' and 'may-unwind'.
>>
>> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...
>>
>> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.
>
> Yes, we went through a phase where people would try to use "nounwind+readonly == no side-effects" to optimize. All such optimizations are wrong. Unless otherwise proven, a function may inf-loop, terminate the program, or longjmp.
>
> I tried to add 'halting' to help solve part of this a long time ago, but it never went in. The problem is that determining whether you have loops requires a FunctionPass (LoopInfo to find loops and SCEV to determine an upper bound) and applying function attributes is an SCC operation (indeed, an SCC is itself a loop), so it's all blocked behind fixing the PassManager to allow CGSGGPasses to depend on FunctionPasses.
> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html
>
> I'm now in a similar situation where I want 'nounwind' to mean "only exits by terminating the program or a return instruction" but unfortunately functions which longjmp are considered nounwind. I would like to change llvm to make longjmp'ing a form of unwinding (an exceptional exit to the function), but if I were to apply that rule today then we'd start putting dwarf eh tables on all our C code, oops.
>
> Nick
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
>

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Andrew Trick
In reply to this post by Duncan Sands

On Jul 22, 2013, at 12:56 AM, Duncan Sands <[hidden email]> wrote:

my understanding is different.  I'm pretty sure that what I'm about to say is
the traditional way these things have been viewed in LLVM.  That doesn't mean
that it's the best way to view these things.

- nounwind means no dwarf EH. Absence

I guess you mean presence.

of nounwind means absence of dwarf EH. It
would be unwise for optimization passes to reason about the semantics beyond
that. I was momentarily mislead by the LICM code that handles MayThrow specially.

nounwind has nothing to do with dwarf, since exceptions themselves need have
nothing to do with dwarf (which is just one way of implementing exception
handling).  Don't forget setjmp/longjmp exception handling, and also exception
handling by returning an extra invisible parameter (which I mentioned in
another email) which IIRC was actually implemented by someone at the codegen
level at some point as it was faster than dwarf for code that throws exceptions
a lot.  An additional point is that while in C++ you create an exception object,
not all languages associate an object with an exception, some just want to do
the equivalent of a non-local goto.  Creating an exception object means
allocating memory, mucking around with global data structures and obviously
writing memory.  A non-local goto doesn't have to do more than unwind the stack
until it gets to the right frame then do a jump.  It's not clear to me that that
should be considered as writing memory.

Here's my take: a call to an function marked nounwind either never returns
(eg infinite loop or exits the program) or returns normally.  It doesn't
"return" by unwinding the stack out of the caller.  On the other hand a
function that is not marked nounwind may "return" by unwinding the stack;
control in this case doesn't continue in the caller, it continues at least one
further up the stack.  Thus in this case the instructions after the call
instruction are not executed.  Note I'm talking about an ordinary call here,
not an invoke.  In the case of an invoke control may continue in the caller
function, but only at a well-defined point (the landing pad).

Good explanation. Your definition of nounwind is completely logical. I would prefer not to rely on it though because
- Realistically, the semantics won’t be well tested.
- It doesn’t seem terribly important to treat nonlocal gotos as readonly (though maybe it is to you :)
- When it is important to optimize memory access around nonlocal gotos, I prefer to expose control flow to the optimizer explicitly.
e.g. why not just use invokes for all your may-throw calls, then you’re free to mark them readonly?

-Andy

- Things that throw exceptions or trap in defined ways are not readonly.

See above for why throwing an exception doesn't have to write memory.  Dwarf
exception handling, and anything which can be used to implement C++ exception
handling, is clearly writing memory and thus cannot be used inside a readonly
function.  So yes, any function Clang produces that throws an exception is not
going to be readonly.  But as I mentioned above some languages have no
exception object and just unwind the stack.  For these the expression "throwing
an exception" (which implicitly includes the idea that there is an exception
object) is not really appropriate; "unwinds the stack" is the basic concept
here.  This is basically orthogonal to readonly.

- Runtime checks for overflow, div-by-zero, bounds checks, etc. should be
implemented at the IR level as branches to noreturn calls because it can be done
that way and I haven’t seen concrete evidence that it’s too expensive. Don’t try
to do something fancy with intrinsics and attributes unless absolutely required.

I agree with this.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Duncan Sands
Hi Andrew,

On 22/07/13 10:23, Andrew Trick wrote:

>
> On Jul 22, 2013, at 12:56 AM, Duncan Sands <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>> my understanding is different.  I'm pretty sure that what I'm about to say is
>> the traditional way these things have been viewed in LLVM.  That doesn't mean
>> that it's the best way to view these things.
>>
>>> - nounwind means no dwarf EH. Absence
>>
>> I guess you mean presence.
>>
>> of nounwind means absence of dwarf EH. It
>>> would be unwise for optimization passes to reason about the semantics beyond
>>> that. I was momentarily mislead by the LICM code that handles MayThrow specially.
>>
>> nounwind has nothing to do with dwarf, since exceptions themselves need have
>> nothing to do with dwarf (which is just one way of implementing exception
>> handling).  Don't forget setjmp/longjmp exception handling, and also exception
>> handling by returning an extra invisible parameter (which I mentioned in
>> another email) which IIRC was actually implemented by someone at the codegen
>> level at some point as it was faster than dwarf for code that throws exceptions
>> a lot.  An additional point is that while in C++ you create an exception object,
>> not all languages associate an object with an exception, some just want to do
>> the equivalent of a non-local goto.  Creating an exception object means
>> allocating memory, mucking around with global data structures and obviously
>> writing memory.  A non-local goto doesn't have to do more than unwind the stack
>> until it gets to the right frame then do a jump.  It's not clear to me that that
>> should be considered as writing memory.
>>
>> Here's my take: a call to an function marked nounwind either never returns
>> (eg infinite loop or exits the program) or returns normally.  It doesn't
>> "return" by unwinding the stack out of the caller.  On the other hand a
>> function that is not marked nounwind may "return" by unwinding the stack;
>> control in this case doesn't continue in the caller, it continues at least one
>> further up the stack.  Thus in this case the instructions after the call
>> instruction are not executed.  Note I'm talking about an ordinary call here,
>> not an invoke.  In the case of an invoke control may continue in the caller
>> function, but only at a well-defined point (the landing pad).
>
> Good explanation. Your definition of nounwind is completely logical. I would
> prefer not to rely on it though because
> - Realistically, the semantics won’t be well tested.

this is true.  Those who need this will have to do careful testing and bug
fixing themselves.  But to my mind this is not a reason to abandon these
semantics.  A good reason to abandon these semantics is if they created trouble
for a large number of users, e.g. clang, for example by making it hard to do
important optimizations.  Do they?  Are these semantics actively harmful?
If not I'd prefer to keep them since they are fairly clean.

> - It doesn’t seem terribly important to treat nonlocal gotos as readonly (though
> maybe it is to you :)

It's not a problem for me, I just like to keep orthogonal things orthogonal.
Maybe that's a mistake and we should rename readonly to "nothing funky happens".

> - When it is important to optimize memory access around nonlocal gotos, I prefer
> to expose control flow to the optimizer explicitly.
> e.g. why not just use invokes for all your may-throw calls, then you’re free to
> mark them readonly?

Let's say that we are in function foo.  We call bar.  We were called by qaz.
I'm not talking about non-local gotos that jump from bar to somewhere in us
(foo).  These indeed need to be modelled with invoke.  I'm talking about those
that jump from bar to somewhere in qaz.  That means that the place in qaz that
called us (foo) will need to use an invoke.  But from the point of view of foo,
the call to bar never returns to foo, it just instantly leaps across foo all the
way up to qaz and execution continues there.  So foo doesn't need to do anything
much, all the heavy lifting is in bar and in qaz.  All foo has to do is keep in
mind that control may never get to the next instruction after the call to bar.

Ciao, Duncan.

>
> -Andy
>
>>> - Things that throw exceptions or trap in defined ways are not readonly.
>>
>> See above for why throwing an exception doesn't have to write memory.  Dwarf
>> exception handling, and anything which can be used to implement C++ exception
>> handling, is clearly writing memory and thus cannot be used inside a readonly
>> function.  So yes, any function Clang produces that throws an exception is not
>> going to be readonly.  But as I mentioned above some languages have no
>> exception object and just unwind the stack.  For these the expression "throwing
>> an exception" (which implicitly includes the idea that there is an exception
>> object) is not really appropriate; "unwinds the stack" is the basic concept
>> here.  This is basically orthogonal to readonly.
>>
>>> - Runtime checks for overflow, div-by-zero, bounds checks, etc. should be
>>> implemented at the IR level as branches to noreturn calls because it can be done
>>> that way and I haven’t seen concrete evidence that it’s too expensive. Don’t try
>>> to do something fancy with intrinsics and attributes unless absolutely required.
>>
>> I agree with this.
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Andrew Trick

On Jul 22, 2013, at 1:37 AM, Duncan Sands <[hidden email]> wrote:

Good explanation. Your definition of nounwind is completely logical. I would
prefer not to rely on it though because
- Realistically, the semantics won’t be well tested.

this is true.  Those who need this will have to do careful testing and bug
fixing themselves.  But to my mind this is not a reason to abandon these
semantics.  A good reason to abandon these semantics is if they created trouble
for a large number of users, e.g. clang, for example by making it hard to do
important optimizations.  Do they?  Are these semantics actively harmful?
If not I'd prefer to keep them since they are fairly clean.

I was justifying my decision not to pursue fixing bugs related to this because of the futility. But you’re right, they can probably be fixed without anyone complaining about performance.

- It doesn’t seem terribly important to treat nonlocal gotos as readonly (though
maybe it is to you :)

It's not a problem for me, I just like to keep orthogonal things orthogonal.
Maybe that's a mistake and we should rename readonly to "nothing funky happens".

- When it is important to optimize memory access around nonlocal gotos, I prefer
to expose control flow to the optimizer explicitly.
e.g. why not just use invokes for all your may-throw calls, then you’re free to
mark them readonly?

Let's say that we are in function foo.  We call bar.  We were called by qaz.
I'm not talking about non-local gotos that jump from bar to somewhere in us
(foo).  These indeed need to be modelled with invoke.  I'm talking about those
that jump from bar to somewhere in qaz.  That means that the place in qaz that
called us (foo) will need to use an invoke.  But from the point of view of foo,
the call to bar never returns to foo, it just instantly leaps across foo all the
way up to qaz and execution continues there.  So foo doesn't need to do anything
much, all the heavy lifting is in bar and in qaz.  All foo has to do is keep in
mind that control may never get to the next instruction after the call to bar.

I’m saying that in some hypothetical language where we need to optimize across readonly exception throwing calls, that both calls to foo and qaz could be invokes (assuming the optimizer doesn’t downgrade the invoke-foo). The concept of a may-throw call with implicit control flow is a shortcut for implementing C++ exceptions that makes the IR a tad prettier. The shortcut happens to work most of the time because the calls always write memory. My only point here is that runtimes can still do exceptions however they like and the front end doesn't need your semantics to do it.

-Andy

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Nick Lewycky-2
In reply to this post by Kuperstein, Michael M
On 22 July 2013 01:11, Kuperstein, Michael M <[hidden email]> wrote:
Of course frontends are free to put attributes, but it would be nice if optimizations actually used them. ;-)
My use case is that of proprietary frontend that happens to know some library function calls - which are only resolved at link time - have no side effects and are safe to execute speculatively, and wants to tell the optimizer it can move them around however it likes. I'll gladly submit a patch that uses these hints, but I'd like to reach some consensus on what the desired attributes actually are first. The last thing I want is to add attributes that are only useful to myself.

Regarding having several orthogonal attributes vs. things like "safetospeculate":

To know a function is safe to speculatively execute, I need at least:
1) readnone (readonly is insufficient, unless I know all accessed pointers are valid)
2) nounwind
3) nolongjmp (I guess?)
4) no undefined behavior. This includes things like "halting" and "no division by zero", but that's not, by far, an exhaustive list.

I guess there are several ways to handle (4).
Ideally, I agree with you, we'd like a set of orthogonal attributes that, taken together, imply that the function's behavior is not undefined.
But that requires mapping all sources of undefined behavior (I don't think this is currently documented for LLVM IR, at least not in a centralized fashion) and adding a very specific attribute for each of them. I'm not sure having function declarations with "readnone, nounwind, nolongjmp, halting, nodivbyzero, nopoisonval, nocomparelabels, nounreachable, ..." is desirable.

We could also have a "welldefined" attribute and a "halting" attribute where "welldefined" subsumes "halting", if the specific case of a function which halts but may have undefined behavior is important.
While the two are not orthogonal, it's similar to the situation with "readnone" and "readonly". Does that sound reasonable?

You're entirely right. I forgot about undefined behaviour.

If you want a 'speculatable' attribute, I would review that patch. Please audit the intrinsics (at least the target-independent ones) and appropriate library functions for whether you can apply this attribute to them. I think the only optimization that it can trigger is that "isSafeToSpeculativelyExecute" returns true on it. Anything else? Is it safe to infer readnone and nounwind from speculatable?

I should mention that speculatable functions are extraordinarily limited in what they can do in the general (nonLLVM-as-a-library) case. They may be hoisted above calls to fork or pthread_create, they may be moved into global constructors (and thus can't depend on global state), etc. However, since you have a specific library you want to generate code against, you have the power to make use of it. I don't expect clang or dragonegg to be able to make use of it.

Nick
 
-----Original Message-----
From: Nick Lewycky [mailto:[hidden email]]
Sent: Monday, July 22, 2013 10:24
To: Kuperstein, Michael M
Cc: Andrew Trick; [hidden email]
Subject: Re: [LLVMdev] Does nounwind have semantics?

Kuperstein, Michael M wrote:
> I'm not sure I understand why it's blocked on that, by the way.

It blocks our ability to automatically deduce the halting attribute in the optimizer, which was necessary for the use case I had at the time.
If you have a use case of your own, feel free to propose the patch!

(Technically it's not *blocked* -- see how my patch does it! -- but the workarounds are too horrible to be committed.)

> Even if we can't apply the attribute ourselves, I don't see why we wouldn't expose that ability to frontends.

Frontends are free to put attributes on functions if they want to. Go for it!

> I'm not entirely sure "halting" is the right attribute either, by the way.
> What I, personally, would like to see is a way to specify a function call is safe to speculatively execute. That implies readnone (not just readonly), nounwind, halting - and Eris knows what else. Nick, is that too strong for you?

I strongly prefer the approach of having orthogonal attributes. There are optimizations that you can do with each of these attributes on their own. In particular I think that readonly+halting+nounwind+nolongjmp is going to be common and I'd feel  silly if we had a special case for
readnone+halting+nounwind+nolongjmp and thus couldn't optimize the more
common case.

That said, I'm also going to feel silly if we don't end up with enough
attributes to allow isSafeToSpeculate to deduce it, which is where we
are right now. I was planning to get back to fixing this after
Chandler's promised PassManager work.

Nick

>
> Michael
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Nick Lewycky
> Sent: Monday, July 22, 2013 07:08
> To: Andrew Trick
> Cc: [hidden email]
> Subject: Re: [LLVMdev] Does nounwind have semantics?
>
> Andrew Trick wrote:
>> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>>
>> int32_t foo(int32_t* ptr) {
>>     int i = 0;
>>     int result;
>>     do {
>>       bar(ptr);
>>       result = *ptr;
>>       bar(ptr);
>>     } while (i++<   *ptr);
>>     return result;
>> }
>>
>> Say we have a front end that declares bar as...
>>
>> declare void @bar(i32*) readonly;
>>
>> So 'bar' is 'readonly' and 'may-unwind'.
>>
>> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...
>>
>> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.
>
> Yes, we went through a phase where people would try to use "nounwind+readonly == no side-effects" to optimize. All such optimizations are wrong. Unless otherwise proven, a function may inf-loop, terminate the program, or longjmp.
>
> I tried to add 'halting' to help solve part of this a long time ago, but it never went in. The problem is that determining whether you have loops requires a FunctionPass (LoopInfo to find loops and SCEV to determine an upper bound) and applying function attributes is an SCC operation (indeed, an SCC is itself a loop), so it's all blocked behind fixing the PassManager to allow CGSGGPasses to depend on FunctionPasses.
> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html
>
> I'm now in a similar situation where I want 'nounwind' to mean "only exits by terminating the program or a return instruction" but unfortunately functions which longjmp are considered nounwind. I would like to change llvm to make longjmp'ing a form of unwinding (an exceptional exit to the function), but if I were to apply that rule today then we'd start putting dwarf eh tables on all our C code, oops.
>
> Nick
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
>

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Kuperstein, Michael M

A patch is attached.

 

Not sure I’m happy with this due to the aforementioned orthogonality concerns, but I really don’t have any better ideas. If anyone does, feel free to offer them, I don’t mind throwing this patch into the trash.

(Also, not happy with the name, using “speculatable” as Nick suggested, for the lack of other options. If the name stays I’ll add it to the documentation.)

 

Regarding auditing the intrinsics – I’d prefer to do this in stages.

Here I’m just preserving the current behavior by marking intrinsics that used to be explicitly handled in isSafeToSpeculativelyExecute(), so there should be no functional change.

 

From: Nick Lewycky [mailto:[hidden email]]
Sent: Tuesday, July 23, 2013 02:29
To: Kuperstein, Michael M
Cc: Nick Lewycky; [hidden email]
Subject: Re: [LLVMdev] Does nounwind have semantics?

 

On 22 July 2013 01:11, Kuperstein, Michael M <[hidden email]> wrote:

Of course frontends are free to put attributes, but it would be nice if optimizations actually used them. ;-)
My use case is that of proprietary frontend that happens to know some library function calls - which are only resolved at link time - have no side effects and are safe to execute speculatively, and wants to tell the optimizer it can move them around however it likes. I'll gladly submit a patch that uses these hints, but I'd like to reach some consensus on what the desired attributes actually are first. The last thing I want is to add attributes that are only useful to myself.

Regarding having several orthogonal attributes vs. things like "safetospeculate":

To know a function is safe to speculatively execute, I need at least:
1) readnone (readonly is insufficient, unless I know all accessed pointers are valid)
2) nounwind
3) nolongjmp (I guess?)
4) no undefined behavior. This includes things like "halting" and "no division by zero", but that's not, by far, an exhaustive list.

I guess there are several ways to handle (4).
Ideally, I agree with you, we'd like a set of orthogonal attributes that, taken together, imply that the function's behavior is not undefined.
But that requires mapping all sources of undefined behavior (I don't think this is currently documented for LLVM IR, at least not in a centralized fashion) and adding a very specific attribute for each of them. I'm not sure having function declarations with "readnone, nounwind, nolongjmp, halting, nodivbyzero, nopoisonval, nocomparelabels, nounreachable, ..." is desirable.

We could also have a "welldefined" attribute and a "halting" attribute where "welldefined" subsumes "halting", if the specific case of a function which halts but may have undefined behavior is important.
While the two are not orthogonal, it's similar to the situation with "readnone" and "readonly". Does that sound reasonable?

 

You're entirely right. I forgot about undefined behaviour.

 

If you want a 'speculatable' attribute, I would review that patch. Please audit the intrinsics (at least the target-independent ones) and appropriate library functions for whether you can apply this attribute to them. I think the only optimization that it can trigger is that "isSafeToSpeculativelyExecute" returns true on it. Anything else? Is it safe to infer readnone and nounwind from speculatable?

 

I should mention that speculatable functions are extraordinarily limited in what they can do in the general (nonLLVM-as-a-library) case. They may be hoisted above calls to fork or pthread_create, they may be moved into global constructors (and thus can't depend on global state), etc. However, since you have a specific library you want to generate code against, you have the power to make use of it. I don't expect clang or dragonegg to be able to make use of it.

 

Nick

 

-----Original Message-----
From: Nick Lewycky [mailto:[hidden email]]
Sent: Monday, July 22, 2013 10:24
To: Kuperstein, Michael M
Cc: Andrew Trick; [hidden email]
Subject: Re: [LLVMdev] Does nounwind have semantics?

Kuperstein, Michael M wrote:
> I'm not sure I understand why it's blocked on that, by the way.

It blocks our ability to automatically deduce the halting attribute in the optimizer, which was necessary for the use case I had at the time.
If you have a use case of your own, feel free to propose the patch!

(Technically it's not *blocked* -- see how my patch does it! -- but the workarounds are too horrible to be committed.)

> Even if we can't apply the attribute ourselves, I don't see why we wouldn't expose that ability to frontends.

Frontends are free to put attributes on functions if they want to. Go for it!

> I'm not entirely sure "halting" is the right attribute either, by the way.
> What I, personally, would like to see is a way to specify a function call is safe to speculatively execute. That implies readnone (not just readonly), nounwind, halting - and Eris knows what else. Nick, is that too strong for you?

I strongly prefer the approach of having orthogonal attributes. There are optimizations that you can do with each of these attributes on their own. In particular I think that readonly+halting+nounwind+nolongjmp is going to be common and I'd feel  silly if we had a special case for
readnone+halting+nounwind+nolongjmp and thus couldn't optimize the more
common case.

That said, I'm also going to feel silly if we don't end up with enough
attributes to allow isSafeToSpeculate to deduce it, which is where we
are right now. I was planning to get back to fixing this after
Chandler's promised PassManager work.

Nick

>
> Michael
>
> -----Original Message-----
> From: [hidden email] [mailto:[hidden email]] On Behalf Of Nick Lewycky
> Sent: Monday, July 22, 2013 07:08
> To: Andrew Trick
> Cc: [hidden email]
> Subject: Re: [LLVMdev] Does nounwind have semantics?
>
> Andrew Trick wrote:
>> Does 'nounwind' have semantics that inform optimization passes? It seems to in some cases, but not consistently. For example...
>>
>> int32_t foo(int32_t* ptr) {
>>     int i = 0;
>>     int result;
>>     do {
>>       bar(ptr);
>>       result = *ptr;
>>       bar(ptr);
>>     } while (i++<   *ptr);
>>     return result;
>> }
>>
>> Say we have a front end that declares bar as...
>>
>> declare void @bar(i32*) readonly;
>>
>> So 'bar' is 'readonly' and 'may-unwind'.
>>
>> When LICM tries to hoist the load it interprets the 'may-unwind' as "MayThrow" in LICM-language and bails. However, when it tries to sink the call itself it sees the 'readonly', assumes no side effects and sinks it below the loads. Hmm...
>>
>> There doesn't appear to be a way to declare a function that is guaranteed not to write to memory in a way that affects the caller, but may have another well-defined side effect like aborting the program. This is interesting, because that is the way runtime checks for safe languages would like to be defined. I'm perfectly happy telling front ends to generate control flow for well-defined traps, since I like lots of basic blocks in my IR. But I'm still curious how others deal with this.
>
> Yes, we went through a phase where people would try to use "nounwind+readonly == no side-effects" to optimize. All such optimizations are wrong. Unless otherwise proven, a function may inf-loop, terminate the program, or longjmp.
>
> I tried to add 'halting' to help solve part of this a long time ago, but it never went in. The problem is that determining whether you have loops requires a FunctionPass (LoopInfo to find loops and SCEV to determine an upper bound) and applying function attributes is an SCC operation (indeed, an SCC is itself a loop), so it's all blocked behind fixing the PassManager to allow CGSGGPasses to depend on FunctionPasses.
> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html
>
> I'm now in a similar situation where I want 'nounwind' to mean "only exits by terminating the program or a return instruction" but unfortunately functions which longjmp are considered nounwind. I would like to change llvm to make longjmp'ing a form of unwinding (an exceptional exit to the function), but if I were to apply that rule today then we'd start putting dwarf eh tables on all our C code, oops.
>
> Nick
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>
>

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

speculatable.diff (26K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Nick Lewycky
Kuperstein, Michael M wrote:
> A patch is attached.

+    const CallInst* CI = dyn_cast<CallInst>(Inst);
+    return CI->isSafeToSpeculativelyExecute();

"return cast<CallInst>(Inst)->isSafeToSpeculativelyExecute();"?

Use cast<> instead of dyn_cast<>. See
http://llvm.org/docs/ProgrammersManual.html#isa . Then I don't think it
needs to be two lines. You can even remove the extra curly braces around
this case.

> Not sure I’m happy with this due to the aforementioned orthogonality
> concerns, but I really don’t have any better ideas. If anyone does, feel
> free to offer them, I don’t mind throwing this patch into the trash.
>
> (Also, not happy with the name, using “speculatable” as Nick suggested,
> for the lack of other options. If the name stays I’ll add it to the
> documentation.)

That reminds me, the patch needs to come with an update to LangRef.rst.

> Regarding auditing the intrinsics – I’d prefer to do this in stages.

Sounds fine. I'd like Eric to take a quick look and agree that marking
debug intrinsics speculatable is sane. (Yes they already are, but that
doesn't mean it's sane. I also want Eric to know that 'speculatable' is
going to start showing up in his debug info.)

One other thing, your patch and Tobias Grosser's patch (subject "Make
.bc en/decoding of AttrKind stable") are in conflict. Whoever lands
second will need to merge.

Nick

> Here I’m just preserving the current behavior by marking intrinsics that
> used to be explicitly handled in isSafeToSpeculativelyExecute(), so
> there should be no functional change.
>
> *From:*Nick Lewycky [mailto:[hidden email]]
> *Sent:* Tuesday, July 23, 2013 02:29
> *To:* Kuperstein, Michael M
> *Cc:* Nick Lewycky; [hidden email]
> *Subject:* Re: [LLVMdev] Does nounwind have semantics?
>
> On 22 July 2013 01:11, Kuperstein, Michael M
> <[hidden email] <mailto:[hidden email]>>
> wrote:
>
>     Of course frontends are free to put attributes, but it would be nice
>     if optimizations actually used them. ;-)
>     My use case is that of proprietary frontend that happens to know
>     some library function calls - which are only resolved at link time -
>     have no side effects and are safe to execute speculatively, and
>     wants to tell the optimizer it can move them around however it
>     likes. I'll gladly submit a patch that uses these hints, but I'd
>     like to reach some consensus on what the desired attributes actually
>     are first. The last thing I want is to add attributes that are only
>     useful to myself.
>
>     Regarding having several orthogonal attributes vs. things like
>     "safetospeculate":
>
>     To know a function is safe to speculatively execute, I need at least:
>     1) readnone (readonly is insufficient, unless I know all accessed
>     pointers are valid)
>     2) nounwind
>     3) nolongjmp (I guess?)
>     4) no undefined behavior. This includes things like "halting" and
>     "no division by zero", but that's not, by far, an exhaustive list.
>
>     I guess there are several ways to handle (4).
>     Ideally, I agree with you, we'd like a set of orthogonal attributes
>     that, taken together, imply that the function's behavior is not
>     undefined.
>     But that requires mapping all sources of undefined behavior (I don't
>     think this is currently documented for LLVM IR, at least not in a
>     centralized fashion) and adding a very specific attribute for each
>     of them. I'm not sure having function declarations with "readnone,
>     nounwind, nolongjmp, halting, nodivbyzero, nopoisonval,
>     nocomparelabels, nounreachable, ..." is desirable.
>
>     We could also have a "welldefined" attribute and a "halting"
>     attribute where "welldefined" subsumes "halting", if the specific
>     case of a function which halts but may have undefined behavior is
>     important.
>     While the two are not orthogonal, it's similar to the situation with
>     "readnone" and "readonly". Does that sound reasonable?
>
> You're entirely right. I forgot about undefined behaviour.
>
> If you want a 'speculatable' attribute, I would review that patch.
> Please audit the intrinsics (at least the target-independent ones) and
> appropriate library functions for whether you can apply this attribute
> to them. I think the only optimization that it can trigger is that
> "isSafeToSpeculativelyExecute" returns true on it. Anything else? Is it
> safe to infer readnone and nounwind from speculatable?
>
> I should mention that speculatable functions are extraordinarily limited
> in what they can do in the general (non–LLVM-as-a-library) case. They
> may be hoisted above calls to fork or pthread_create, they may be moved
> into global constructors (and thus can't depend on global state), etc.
> However, since you have a specific library you want to generate code
> against, you have the power to make use of it. I don't expect clang or
> dragonegg to be able to make use of it.
>
> Nick
>
>     -----Original Message-----
>     From: Nick Lewycky [mailto:[hidden email] <mailto:[hidden email]>]
>     Sent: Monday, July 22, 2013 10:24
>     To: Kuperstein, Michael M
>     Cc: Andrew Trick; [hidden email] <mailto:[hidden email]>
>     Subject: Re: [LLVMdev] Does nounwind have semantics?
>
>     Kuperstein, Michael M wrote:
>      > I'm not sure I understand why it's blocked on that, by the way.
>
>     It blocks our ability to automatically deduce the halting attribute
>     in the optimizer, which was necessary for the use case I had at the
>     time.
>     If you have a use case of your own, feel free to propose the patch!
>
>     (Technically it's not *blocked* -- see how my patch does it! -- but
>     the workarounds are too horrible to be committed.)
>
>      > Even if we can't apply the attribute ourselves, I don't see why
>     we wouldn't expose that ability to frontends.
>
>     Frontends are free to put attributes on functions if they want to.
>     Go for it!
>
>      > I'm not entirely sure "halting" is the right attribute either, by
>     the way.
>      > What I, personally, would like to see is a way to specify a
>     function call is safe to speculatively execute. That implies
>     readnone (not just readonly), nounwind, halting - and Eris knows
>     what else. Nick, is that too strong for you?
>
>     I strongly prefer the approach of having orthogonal attributes.
>     There are optimizations that you can do with each of these
>     attributes on their own. In particular I think that
>     readonly+halting+nounwind+nolongjmp is going to be common and I'd
>     feel silly if we had a special case for
>     readnone+halting+nounwind+nolongjmp and thus couldn't optimize the more
>     common case.
>
>     That said, I'm also going to feel silly if we don't end up with enough
>     attributes to allow isSafeToSpeculate to deduce it, which is where we
>     are right now. I was planning to get back to fixing this after
>     Chandler's promised PassManager work.
>
>     Nick
>
>      >
>      > Michael
>      >
>      > -----Original Message-----
>      > From: [hidden email]
>     <mailto:[hidden email]>
>     [mailto:[hidden email]
>     <mailto:[hidden email]>] On Behalf Of Nick Lewycky
>      > Sent: Monday, July 22, 2013 07:08
>      > To: Andrew Trick
>      > Cc: [hidden email] <mailto:[hidden email]>
>      > Subject: Re: [LLVMdev] Does nounwind have semantics?
>      >
>      > Andrew Trick wrote:
>      >> Does 'nounwind' have semantics that inform optimization passes?
>     It seems to in some cases, but not consistently. For example...
>      >>
>      >> int32_t foo(int32_t* ptr) {
>      >> int i = 0;
>      >> int result;
>      >> do {
>      >> bar(ptr);
>      >> result = *ptr;
>      >> bar(ptr);
>      >> } while (i++< *ptr);
>      >> return result;
>      >> }
>      >>
>      >> Say we have a front end that declares bar as...
>      >>
>      >> declare void @bar(i32*) readonly;
>      >>
>      >> So 'bar' is 'readonly' and 'may-unwind'.
>      >>
>      >> When LICM tries to hoist the load it interprets the 'may-unwind'
>     as "MayThrow" in LICM-language and bails. However, when it tries to
>     sink the call itself it sees the 'readonly', assumes no side effects
>     and sinks it below the loads. Hmm...
>      >>
>      >> There doesn't appear to be a way to declare a function that is
>     guaranteed not to write to memory in a way that affects the caller,
>     but may have another well-defined side effect like aborting the
>     program. This is interesting, because that is the way runtime checks
>     for safe languages would like to be defined. I'm perfectly happy
>     telling front ends to generate control flow for well-defined traps,
>     since I like lots of basic blocks in my IR. But I'm still curious
>     how others deal with this.
>      >
>      > Yes, we went through a phase where people would try to use
>     "nounwind+readonly == no side-effects" to optimize. All such
>     optimizations are wrong. Unless otherwise proven, a function may
>     inf-loop, terminate the program, or longjmp.
>      >
>      > I tried to add 'halting' to help solve part of this a long time
>     ago, but it never went in. The problem is that determining whether
>     you have loops requires a FunctionPass (LoopInfo to find loops and
>     SCEV to determine an upper bound) and applying function attributes
>     is an SCC operation (indeed, an SCC is itself a loop), so it's all
>     blocked behind fixing the PassManager to allow CGSGGPasses to depend
>     on FunctionPasses.
>      >
>     http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html
>      >
>      > I'm now in a similar situation where I want 'nounwind' to mean
>     "only exits by terminating the program or a return instruction" but
>     unfortunately functions which longjmp are considered nounwind. I
>     would like to change llvm to make longjmp'ing a form of unwinding
>     (an exceptional exit to the function), but if I were to apply that
>     rule today then we'd start putting dwarf eh tables on all our C
>     code, oops.
>      >
>      > Nick
>      > _______________________________________________
>      > LLVM Developers mailing list
>      > [hidden email] <mailto:[hidden email]>
>     http://llvm.cs.uiuc.edu
>      > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>      > ---------------------------------------------------------------------
>      > Intel Israel (74) Limited
>      >
>      > This e-mail and any attachments may contain confidential material for
>      > the sole use of the intended recipient(s). Any review or distribution
>      > by others is strictly prohibited. If you are not the intended
>      > recipient, please contact the sender and delete all copies.
>      >
>      >
>
>     ---------------------------------------------------------------------
>     Intel Israel (74) Limited
>
>     This e-mail and any attachments may contain confidential material for
>     the sole use of the intended recipient(s). Any review or distribution
>     by others is strictly prohibited. If you are not the intended
>     recipient, please contact the sender and delete all copies.
>
>
>     _______________________________________________
>     LLVM Developers mailing list
>     [hidden email] <mailto:[hidden email]> http://llvm.cs.uiuc.edu
>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Kuperstein, Michael M
Right, will fix the CallInst, copy/pasted from a different case and didn't notice what I was doing, thanks.

Re LangRef.rst, that's what I meant, I'm still hoping for better suggestions regarding the name...

As to the conflict - Tobias, feel free to go first, I'll merge.

-----Original Message-----
From: Nick Lewycky [mailto:[hidden email]]
Sent: Thursday, July 25, 2013 12:11
To: Kuperstein, Michael M
Cc: Nick Lewycky; [hidden email]; Tobias Grosser; [hidden email]
Subject: Re: [LLVMdev] Does nounwind have semantics?

Kuperstein, Michael M wrote:
> A patch is attached.

+    const CallInst* CI = dyn_cast<CallInst>(Inst);
+    return CI->isSafeToSpeculativelyExecute();

"return cast<CallInst>(Inst)->isSafeToSpeculativelyExecute();"?

Use cast<> instead of dyn_cast<>. See
http://llvm.org/docs/ProgrammersManual.html#isa . Then I don't think it needs to be two lines. You can even remove the extra curly braces around this case.

> Not sure I'm happy with this due to the aforementioned orthogonality
> concerns, but I really don't have any better ideas. If anyone does,
> feel free to offer them, I don't mind throwing this patch into the trash.
>
> (Also, not happy with the name, using "speculatable" as Nick
> suggested, for the lack of other options. If the name stays I'll add
> it to the
> documentation.)

That reminds me, the patch needs to come with an update to LangRef.rst.

> Regarding auditing the intrinsics - I'd prefer to do this in stages.

Sounds fine. I'd like Eric to take a quick look and agree that marking debug intrinsics speculatable is sane. (Yes they already are, but that doesn't mean it's sane. I also want Eric to know that 'speculatable' is going to start showing up in his debug info.)

One other thing, your patch and Tobias Grosser's patch (subject "Make .bc en/decoding of AttrKind stable") are in conflict. Whoever lands second will need to merge.

Nick

> Here I'm just preserving the current behavior by marking intrinsics
> that used to be explicitly handled in isSafeToSpeculativelyExecute(),
> so there should be no functional change.
>
> *From:*Nick Lewycky [mailto:[hidden email]]
> *Sent:* Tuesday, July 23, 2013 02:29
> *To:* Kuperstein, Michael M
> *Cc:* Nick Lewycky; [hidden email]
> *Subject:* Re: [LLVMdev] Does nounwind have semantics?
>
> On 22 July 2013 01:11, Kuperstein, Michael M
> <[hidden email]
> <mailto:[hidden email]>>
> wrote:
>
>     Of course frontends are free to put attributes, but it would be nice
>     if optimizations actually used them. ;-)
>     My use case is that of proprietary frontend that happens to know
>     some library function calls - which are only resolved at link time -
>     have no side effects and are safe to execute speculatively, and
>     wants to tell the optimizer it can move them around however it
>     likes. I'll gladly submit a patch that uses these hints, but I'd
>     like to reach some consensus on what the desired attributes actually
>     are first. The last thing I want is to add attributes that are only
>     useful to myself.
>
>     Regarding having several orthogonal attributes vs. things like
>     "safetospeculate":
>
>     To know a function is safe to speculatively execute, I need at least:
>     1) readnone (readonly is insufficient, unless I know all accessed
>     pointers are valid)
>     2) nounwind
>     3) nolongjmp (I guess?)
>     4) no undefined behavior. This includes things like "halting" and
>     "no division by zero", but that's not, by far, an exhaustive list.
>
>     I guess there are several ways to handle (4).
>     Ideally, I agree with you, we'd like a set of orthogonal attributes
>     that, taken together, imply that the function's behavior is not
>     undefined.
>     But that requires mapping all sources of undefined behavior (I don't
>     think this is currently documented for LLVM IR, at least not in a
>     centralized fashion) and adding a very specific attribute for each
>     of them. I'm not sure having function declarations with "readnone,
>     nounwind, nolongjmp, halting, nodivbyzero, nopoisonval,
>     nocomparelabels, nounreachable, ..." is desirable.
>
>     We could also have a "welldefined" attribute and a "halting"
>     attribute where "welldefined" subsumes "halting", if the specific
>     case of a function which halts but may have undefined behavior is
>     important.
>     While the two are not orthogonal, it's similar to the situation with
>     "readnone" and "readonly". Does that sound reasonable?
>
> You're entirely right. I forgot about undefined behaviour.
>
> If you want a 'speculatable' attribute, I would review that patch.
> Please audit the intrinsics (at least the target-independent ones) and
> appropriate library functions for whether you can apply this attribute
> to them. I think the only optimization that it can trigger is that
> "isSafeToSpeculativelyExecute" returns true on it. Anything else? Is
> it safe to infer readnone and nounwind from speculatable?
>
> I should mention that speculatable functions are extraordinarily
> limited in what they can do in the general (non-LLVM-as-a-library)
> case. They may be hoisted above calls to fork or pthread_create, they
> may be moved into global constructors (and thus can't depend on global state), etc.
> However, since you have a specific library you want to generate code
> against, you have the power to make use of it. I don't expect clang or
> dragonegg to be able to make use of it.
>
> Nick
>
>     -----Original Message-----
>     From: Nick Lewycky [mailto:[hidden email] <mailto:[hidden email]>]
>     Sent: Monday, July 22, 2013 10:24
>     To: Kuperstein, Michael M
>     Cc: Andrew Trick; [hidden email] <mailto:[hidden email]>
>     Subject: Re: [LLVMdev] Does nounwind have semantics?
>
>     Kuperstein, Michael M wrote:
>      > I'm not sure I understand why it's blocked on that, by the way.
>
>     It blocks our ability to automatically deduce the halting attribute
>     in the optimizer, which was necessary for the use case I had at the
>     time.
>     If you have a use case of your own, feel free to propose the patch!
>
>     (Technically it's not *blocked* -- see how my patch does it! -- but
>     the workarounds are too horrible to be committed.)
>
>      > Even if we can't apply the attribute ourselves, I don't see why
>     we wouldn't expose that ability to frontends.
>
>     Frontends are free to put attributes on functions if they want to.
>     Go for it!
>
>      > I'm not entirely sure "halting" is the right attribute either, by
>     the way.
>      > What I, personally, would like to see is a way to specify a
>     function call is safe to speculatively execute. That implies
>     readnone (not just readonly), nounwind, halting - and Eris knows
>     what else. Nick, is that too strong for you?
>
>     I strongly prefer the approach of having orthogonal attributes.
>     There are optimizations that you can do with each of these
>     attributes on their own. In particular I think that
>     readonly+halting+nounwind+nolongjmp is going to be common and I'd
>     feel silly if we had a special case for
>     readnone+halting+nounwind+nolongjmp and thus couldn't optimize the more
>     common case.
>
>     That said, I'm also going to feel silly if we don't end up with enough
>     attributes to allow isSafeToSpeculate to deduce it, which is where we
>     are right now. I was planning to get back to fixing this after
>     Chandler's promised PassManager work.
>
>     Nick
>
>      >
>      > Michael
>      >
>      > -----Original Message-----
>      > From: [hidden email]
>     <mailto:[hidden email]>
>     [mailto:[hidden email]
>     <mailto:[hidden email]>] On Behalf Of Nick Lewycky
>      > Sent: Monday, July 22, 2013 07:08
>      > To: Andrew Trick
>      > Cc: [hidden email] <mailto:[hidden email]>
>      > Subject: Re: [LLVMdev] Does nounwind have semantics?
>      >
>      > Andrew Trick wrote:
>      >> Does 'nounwind' have semantics that inform optimization passes?
>     It seems to in some cases, but not consistently. For example...
>      >>
>      >> int32_t foo(int32_t* ptr) {
>      >> int i = 0;
>      >> int result;
>      >> do {
>      >> bar(ptr);
>      >> result = *ptr;
>      >> bar(ptr);
>      >> } while (i++< *ptr);
>      >> return result;
>      >> }
>      >>
>      >> Say we have a front end that declares bar as...
>      >>
>      >> declare void @bar(i32*) readonly;
>      >>
>      >> So 'bar' is 'readonly' and 'may-unwind'.
>      >>
>      >> When LICM tries to hoist the load it interprets the 'may-unwind'
>     as "MayThrow" in LICM-language and bails. However, when it tries to
>     sink the call itself it sees the 'readonly', assumes no side effects
>     and sinks it below the loads. Hmm...
>      >>
>      >> There doesn't appear to be a way to declare a function that is
>     guaranteed not to write to memory in a way that affects the caller,
>     but may have another well-defined side effect like aborting the
>     program. This is interesting, because that is the way runtime checks
>     for safe languages would like to be defined. I'm perfectly happy
>     telling front ends to generate control flow for well-defined traps,
>     since I like lots of basic blocks in my IR. But I'm still curious
>     how others deal with this.
>      >
>      > Yes, we went through a phase where people would try to use
>     "nounwind+readonly == no side-effects" to optimize. All such
>     optimizations are wrong. Unless otherwise proven, a function may
>     inf-loop, terminate the program, or longjmp.
>      >
>      > I tried to add 'halting' to help solve part of this a long time
>     ago, but it never went in. The problem is that determining whether
>     you have loops requires a FunctionPass (LoopInfo to find loops and
>     SCEV to determine an upper bound) and applying function attributes
>     is an SCC operation (indeed, an SCC is itself a loop), so it's all
>     blocked behind fixing the PassManager to allow CGSGGPasses to depend
>     on FunctionPasses.
>      >
>     http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html
>      >
>      > I'm now in a similar situation where I want 'nounwind' to mean
>     "only exits by terminating the program or a return instruction" but
>     unfortunately functions which longjmp are considered nounwind. I
>     would like to change llvm to make longjmp'ing a form of unwinding
>     (an exceptional exit to the function), but if I were to apply that
>     rule today then we'd start putting dwarf eh tables on all our C
>     code, oops.
>      >
>      > Nick
>      > _______________________________________________
>      > LLVM Developers mailing list
>      > [hidden email] <mailto:[hidden email]>
>     http://llvm.cs.uiuc.edu
>      > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>      > ---------------------------------------------------------------------
>      > Intel Israel (74) Limited
>      >
>      > This e-mail and any attachments may contain confidential material for
>      > the sole use of the intended recipient(s). Any review or distribution
>      > by others is strictly prohibited. If you are not the intended
>      > recipient, please contact the sender and delete all copies.
>      >
>      >
>
>     ---------------------------------------------------------------------
>     Intel Israel (74) Limited
>
>     This e-mail and any attachments may contain confidential material for
>     the sole use of the intended recipient(s). Any review or distribution
>     by others is strictly prohibited. If you are not the intended
>     recipient, please contact the sender and delete all copies.
>
>
>     _______________________________________________
>     LLVM Developers mailing list
>     [hidden email] <mailto:[hidden email]> http://llvm.cs.uiuc.edu
>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
>
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
>

---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Eric Christopher
In reply to this post by Nick Lewycky
>> Regarding auditing the intrinsics – I’d prefer to do this in stages.
>
>
> Sounds fine. I'd like Eric to take a quick look and agree that marking debug
> intrinsics speculatable is sane. (Yes they already are, but that doesn't
> mean it's sane. I also want Eric to know that 'speculatable' is going to
> start showing up in his debug info.)
>

Sure, seems reasonable so far.

-eric

> One other thing, your patch and Tobias Grosser's patch (subject "Make .bc
> en/decoding of AttrKind stable") are in conflict. Whoever lands second will
> need to merge.
>
> Nick
>
>> Here I’m just preserving the current behavior by marking intrinsics that
>> used to be explicitly handled in isSafeToSpeculativelyExecute(), so
>> there should be no functional change.
>>
>> *From:*Nick Lewycky [mailto:[hidden email]]
>> *Sent:* Tuesday, July 23, 2013 02:29
>> *To:* Kuperstein, Michael M
>> *Cc:* Nick Lewycky; [hidden email]
>> *Subject:* Re: [LLVMdev] Does nounwind have semantics?
>>
>>
>> On 22 July 2013 01:11, Kuperstein, Michael M
>> <[hidden email] <mailto:[hidden email]>>
>>
>> wrote:
>>
>>     Of course frontends are free to put attributes, but it would be nice
>>     if optimizations actually used them. ;-)
>>     My use case is that of proprietary frontend that happens to know
>>     some library function calls - which are only resolved at link time -
>>     have no side effects and are safe to execute speculatively, and
>>     wants to tell the optimizer it can move them around however it
>>     likes. I'll gladly submit a patch that uses these hints, but I'd
>>     like to reach some consensus on what the desired attributes actually
>>     are first. The last thing I want is to add attributes that are only
>>     useful to myself.
>>
>>     Regarding having several orthogonal attributes vs. things like
>>     "safetospeculate":
>>
>>     To know a function is safe to speculatively execute, I need at least:
>>     1) readnone (readonly is insufficient, unless I know all accessed
>>     pointers are valid)
>>     2) nounwind
>>     3) nolongjmp (I guess?)
>>     4) no undefined behavior. This includes things like "halting" and
>>     "no division by zero", but that's not, by far, an exhaustive list.
>>
>>     I guess there are several ways to handle (4).
>>     Ideally, I agree with you, we'd like a set of orthogonal attributes
>>     that, taken together, imply that the function's behavior is not
>>     undefined.
>>     But that requires mapping all sources of undefined behavior (I don't
>>     think this is currently documented for LLVM IR, at least not in a
>>     centralized fashion) and adding a very specific attribute for each
>>     of them. I'm not sure having function declarations with "readnone,
>>     nounwind, nolongjmp, halting, nodivbyzero, nopoisonval,
>>     nocomparelabels, nounreachable, ..." is desirable.
>>
>>     We could also have a "welldefined" attribute and a "halting"
>>     attribute where "welldefined" subsumes "halting", if the specific
>>     case of a function which halts but may have undefined behavior is
>>     important.
>>     While the two are not orthogonal, it's similar to the situation with
>>     "readnone" and "readonly". Does that sound reasonable?
>>
>> You're entirely right. I forgot about undefined behaviour.
>>
>> If you want a 'speculatable' attribute, I would review that patch.
>> Please audit the intrinsics (at least the target-independent ones) and
>> appropriate library functions for whether you can apply this attribute
>> to them. I think the only optimization that it can trigger is that
>> "isSafeToSpeculativelyExecute" returns true on it. Anything else? Is it
>> safe to infer readnone and nounwind from speculatable?
>>
>> I should mention that speculatable functions are extraordinarily limited
>> in what they can do in the general (non–LLVM-as-a-library) case. They
>> may be hoisted above calls to fork or pthread_create, they may be moved
>> into global constructors (and thus can't depend on global state), etc.
>> However, since you have a specific library you want to generate code
>> against, you have the power to make use of it. I don't expect clang or
>> dragonegg to be able to make use of it.
>>
>> Nick
>>
>>     -----Original Message-----
>>     From: Nick Lewycky [mailto:[hidden email] <mailto:[hidden email]>]
>>     Sent: Monday, July 22, 2013 10:24
>>     To: Kuperstein, Michael M
>>     Cc: Andrew Trick; [hidden email] <mailto:[hidden email]>
>>     Subject: Re: [LLVMdev] Does nounwind have semantics?
>>
>>     Kuperstein, Michael M wrote:
>>      > I'm not sure I understand why it's blocked on that, by the way.
>>
>>     It blocks our ability to automatically deduce the halting attribute
>>     in the optimizer, which was necessary for the use case I had at the
>>     time.
>>     If you have a use case of your own, feel free to propose the patch!
>>
>>     (Technically it's not *blocked* -- see how my patch does it! -- but
>>     the workarounds are too horrible to be committed.)
>>
>>      > Even if we can't apply the attribute ourselves, I don't see why
>>     we wouldn't expose that ability to frontends.
>>
>>     Frontends are free to put attributes on functions if they want to.
>>     Go for it!
>>
>>      > I'm not entirely sure "halting" is the right attribute either, by
>>     the way.
>>      > What I, personally, would like to see is a way to specify a
>>     function call is safe to speculatively execute. That implies
>>     readnone (not just readonly), nounwind, halting - and Eris knows
>>     what else. Nick, is that too strong for you?
>>
>>     I strongly prefer the approach of having orthogonal attributes.
>>     There are optimizations that you can do with each of these
>>     attributes on their own. In particular I think that
>>     readonly+halting+nounwind+nolongjmp is going to be common and I'd
>>     feel silly if we had a special case for
>>     readnone+halting+nounwind+nolongjmp and thus couldn't optimize the
>> more
>>     common case.
>>
>>     That said, I'm also going to feel silly if we don't end up with enough
>>     attributes to allow isSafeToSpeculate to deduce it, which is where we
>>     are right now. I was planning to get back to fixing this after
>>     Chandler's promised PassManager work.
>>
>>     Nick
>>
>>      >
>>      > Michael
>>      >
>>      > -----Original Message-----
>>      > From: [hidden email]
>>     <mailto:[hidden email]>
>>     [mailto:[hidden email]
>>     <mailto:[hidden email]>] On Behalf Of Nick Lewycky
>>      > Sent: Monday, July 22, 2013 07:08
>>      > To: Andrew Trick
>>      > Cc: [hidden email] <mailto:[hidden email]>
>>      > Subject: Re: [LLVMdev] Does nounwind have semantics?
>>      >
>>      > Andrew Trick wrote:
>>      >> Does 'nounwind' have semantics that inform optimization passes?
>>     It seems to in some cases, but not consistently. For example...
>>      >>
>>      >> int32_t foo(int32_t* ptr) {
>>      >> int i = 0;
>>      >> int result;
>>      >> do {
>>      >> bar(ptr);
>>      >> result = *ptr;
>>      >> bar(ptr);
>>      >> } while (i++< *ptr);
>>      >> return result;
>>      >> }
>>      >>
>>      >> Say we have a front end that declares bar as...
>>      >>
>>      >> declare void @bar(i32*) readonly;
>>      >>
>>      >> So 'bar' is 'readonly' and 'may-unwind'.
>>      >>
>>      >> When LICM tries to hoist the load it interprets the 'may-unwind'
>>     as "MayThrow" in LICM-language and bails. However, when it tries to
>>     sink the call itself it sees the 'readonly', assumes no side effects
>>     and sinks it below the loads. Hmm...
>>      >>
>>      >> There doesn't appear to be a way to declare a function that is
>>     guaranteed not to write to memory in a way that affects the caller,
>>     but may have another well-defined side effect like aborting the
>>     program. This is interesting, because that is the way runtime checks
>>     for safe languages would like to be defined. I'm perfectly happy
>>     telling front ends to generate control flow for well-defined traps,
>>     since I like lots of basic blocks in my IR. But I'm still curious
>>     how others deal with this.
>>      >
>>      > Yes, we went through a phase where people would try to use
>>     "nounwind+readonly == no side-effects" to optimize. All such
>>     optimizations are wrong. Unless otherwise proven, a function may
>>     inf-loop, terminate the program, or longjmp.
>>      >
>>      > I tried to add 'halting' to help solve part of this a long time
>>     ago, but it never went in. The problem is that determining whether
>>     you have loops requires a FunctionPass (LoopInfo to find loops and
>>     SCEV to determine an upper bound) and applying function attributes
>>     is an SCC operation (indeed, an SCC is itself a loop), so it's all
>>     blocked behind fixing the PassManager to allow CGSGGPasses to depend
>>     on FunctionPasses.
>>      >
>>
>> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20100705/103670.html
>>      >
>>      > I'm now in a similar situation where I want 'nounwind' to mean
>>     "only exits by terminating the program or a return instruction" but
>>     unfortunately functions which longjmp are considered nounwind. I
>>     would like to change llvm to make longjmp'ing a form of unwinding
>>     (an exceptional exit to the function), but if I were to apply that
>>     rule today then we'd start putting dwarf eh tables on all our C
>>     code, oops.
>>      >
>>      > Nick
>>      > _______________________________________________
>>      > LLVM Developers mailing list
>>      > [hidden email] <mailto:[hidden email]>
>>
>>     http://llvm.cs.uiuc.edu
>>      > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>      >
>> ---------------------------------------------------------------------
>>      > Intel Israel (74) Limited
>>      >
>>      > This e-mail and any attachments may contain confidential material
>> for
>>      > the sole use of the intended recipient(s). Any review or
>> distribution
>>      > by others is strictly prohibited. If you are not the intended
>>      > recipient, please contact the sender and delete all copies.
>>      >
>>      >
>>
>>     ---------------------------------------------------------------------
>>     Intel Israel (74) Limited
>>
>>     This e-mail and any attachments may contain confidential material for
>>     the sole use of the intended recipient(s). Any review or distribution
>>     by others is strictly prohibited. If you are not the intended
>>     recipient, please contact the sender and delete all copies.
>>
>>
>>     _______________________________________________
>>     LLVM Developers mailing list
>>     [hidden email] <mailto:[hidden email]>
>> http://llvm.cs.uiuc.edu
>>
>>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>> ---------------------------------------------------------------------
>> Intel Israel (74) Limited
>>
>> This e-mail and any attachments may contain confidential material for
>> the sole use of the intended recipient(s). Any review or distribution
>> by others is strictly prohibited. If you are not the intended
>> recipient, please contact the sender and delete all copies.
>>
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Tobias Grosser-5
In reply to this post by Kuperstein, Michael M
On 07/25/2013 02:14 AM, Kuperstein, Michael M wrote:
> Right, will fix the CallInst, copy/pasted from a different case and didn't notice what I was doing, thanks.
>
> Re LangRef.rst, that's what I meant, I'm still hoping for better suggestions regarding the name...
>
> As to the conflict - Tobias, feel free to go first, I'll merge.

I am still waiting for a review. The merge will be trivial, so just
commit whenever you are ready.

Tobi

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Does nounwind have semantics?

Tobias Grosser-5
In reply to this post by Kuperstein, Michael M
On 07/25/2013 02:14 AM, Kuperstein, Michael M wrote:
> Right, will fix the CallInst, copy/pasted from a different case and didn't notice what I was doing, thanks.
>
> Re LangRef.rst, that's what I meant, I'm still hoping for better suggestions regarding the name...
>
> As to the conflict - Tobias, feel free to go first, I'll merge.

Hi Michael,

my patch is in. Feel free to commit your patch on top of it.

Also, if you could add a test case into test/Bitcode/attributes.ll, this
would be great.

Tobi
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
12