llvm dev - Jan 2017 - RFC: Allow readnone and readonly functions to throw exceptions

LLVM today does not clearly specify if a function specified to not
write to memory (i.e. readonly or readnone) is allowed to throw
exceptions.

LangRef is ambiguous on this issue.  The normative statement is
"[readnone/readonly functions] cannot unwind exceptions by calling the
C++ exception throwing methods" which does not decide an answer for
non C++ languages.  It used to say (h/t Daniel Berlin): "This means
that it cannot unwind exceptions by calling the C++ exception throwing
methods, but could use the unwind instruction.", but that bit of
documentation died with the unwind instruction.

I'd like to separate unwindability from memory effects, and officially
change our stance to be "readonly / readnone functions are allowed to
throw exceptions".

Here are two supporting reasons:

# `resume` is already modeled as readnone

The easiest way to verify this is via FunctionAttrs; it infers the
following function as readnone:

define void @f() personality i8 42 {
  resume i32 0
}


Modeling `resume` as `readnone` is defensible -- it is a control flow
transfer instruction, not so different from `ret`.  Moreover, it
_cannot_ be modeled as having observable side effects or writes to
memory (`resume` cannot send packets over the network or write to a
global) because otherwise we'd be unable to inline @f into @g below:

define void @f(i32 %x) personality i32 3 {
  resume i32 %x
}

define i32 @g(i32 %x) personality i32 3 {
  invoke void @f(i32 %x) to label %normal unwind label %unwind

normal:
  ret i32 0

unwind:
  %t = landingpad i32 cleanup
  ret i32 %t
}

since it gets rid of a `resume` and thus a side effect (by
assumption).


# We're probably already there (but we need an audit)

All said and done, the situation is not as "loosey goosey" as I made
it sound like.  mayHaveSideEffects() is defined as "mayWriteToMemory()
|| mayThrow()"; and this shows in e.g. EarlyCSE which will refuse to
DCE the call to @f in @g

declare void @f() readnone

define void @g() {
  call void @f()
  ret void
}

unless @f is also marked nounwind.

I've already fixed the one other instance I was aware of in
https://reviews.llvm.org/rL290794 (but I will revert that patch if we
decide against this RFC).

We won't lose any expressive power either -- if there are situations
where we have important optimizations firing under the "readonly
implies nounwind" assumption, we can either

 - Teach FunctionAttrs to infer nounwind for readonly functions with
   C++ unwind personalities.

 - For external declarations generated by the compiler (say from the
   standard library): if the functions are actually nounwind, mark
   them as nounwind; and not rely on LLVM inferring nounwind from
   readonly.


My (unrealistic?) hope is that this would mostly be a specification
change and not involve a lot of code fixes.

The change is also trivially upgrade-safe for older bitcode -- calls
to readonly / readnone functions that do not throw _may_ get optimized
less, but that should not be a correctness problem.

What do you think?

-- Sanjoy

This sounds right to me.

IIUC, historically, readonly and readnone are meant to model the
"pure" and
"const" GCC attributes. These attributes make pretty strong
guarantees:

"[a pure] function can be subject to common subexpression elimination and
loop optimization just as an arithmetic operator would be. These functions
should be declared with the attribute pure [...] Interesting non-pure
functions are functions with infinite loops or those depending on volatile
memory or other system resource, that may change between two consecutive
calls (such as feof in a multithreading environment)."

In particular, pure/const imply termination - something that's not entirely
clear w.r.t readonly. However, apparently, they don't imply nothrow.
I've
actually always thought they *do* imply it - and said so on-list :-) - but
it looks like GCC itself doesn't interpret them that way. E.g. see John
Regher's example here: https://t.co/REzy5m1tT3
So there's at least one use-case for possibly throwing readonly/readnone.

As a side note, I'm slightly less optimistic about the amount of required
code fixes. One thing that comes to mind is that we need to make sure we
mark all(?) the intrinsics currently marked readonly/argmemonly/readnone as
nothrow. This should be mostly mechanical, I hope, but it's a decent amount
of churn.

Michael




On 2 January 2017 at 22:18, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org
> wrote:
> LLVM today does not clearly specify if a function specified to not
> write to memory (i.e. readonly or readnone) is allowed to throw
> exceptions.
>
> LangRef is ambiguous on this issue.  The normative statement is
> "[readnone/readonly functions] cannot unwind exceptions by calling the
> C++ exception throwing methods" which does not decide an answer for
> non C++ languages.  It used to say (h/t Daniel Berlin): "This means
> that it cannot unwind exceptions by calling the C++ exception throwing
> methods, but could use the unwind instruction.", but that bit of
> documentation died with the unwind instruction.
>
> I'd like to separate unwindability from memory effects, and officially
> change our stance to be "readonly / readnone functions are allowed to
> throw exceptions".
>
> Here are two supporting reasons:
>
> # `resume` is already modeled as readnone
>
> The easiest way to verify this is via FunctionAttrs; it infers the
> following function as readnone:
>
> define void @f() personality i8 42 {
>   resume i32 0
> }
>
>
> Modeling `resume` as `readnone` is defensible -- it is a control flow
> transfer instruction, not so different from `ret`.  Moreover, it
> _cannot_ be modeled as having observable side effects or writes to
> memory (`resume` cannot send packets over the network or write to a
> global) because otherwise we'd be unable to inline @f into @g below:
>
> define void @f(i32 %x) personality i32 3 {
>   resume i32 %x
> }
>
> define i32 @g(i32 %x) personality i32 3 {
>   invoke void @f(i32 %x) to label %normal unwind label %unwind
>
> normal:
>   ret i32 0
>
> unwind:
>   %t = landingpad i32 cleanup
>   ret i32 %t
> }
>
> since it gets rid of a `resume` and thus a side effect (by
> assumption).
>
>
> # We're probably already there (but we need an audit)
>
> All said and done, the situation is not as "loosey goosey" as I
made
> it sound like.  mayHaveSideEffects() is defined as "mayWriteToMemory()
> || mayThrow()"; and this shows in e.g. EarlyCSE which will refuse to
> DCE the call to @f in @g
>
> declare void @f() readnone
>
> define void @g() {
>   call void @f()
>   ret void
> }
>
> unless @f is also marked nounwind.
>
> I've already fixed the one other instance I was aware of in
> https://reviews.llvm.org/rL290794 (but I will revert that patch if we
> decide against this RFC).
>
> We won't lose any expressive power either -- if there are situations
> where we have important optimizations firing under the "readonly
> implies nounwind" assumption, we can either
>
>  - Teach FunctionAttrs to infer nounwind for readonly functions with
>    C++ unwind personalities.
>
>  - For external declarations generated by the compiler (say from the
>    standard library): if the functions are actually nounwind, mark
>    them as nounwind; and not rely on LLVM inferring nounwind from
>    readonly.
>
>
> My (unrealistic?) hope is that this would mostly be a specification
> change and not involve a lot of code fixes.
>
> The change is also trivially upgrade-safe for older bitcode -- calls
> to readonly / readnone functions that do not throw _may_ get optimized
> less, but that should not be a correctness problem.
>
> What do you think?
>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170102/04a305f9/attachment.html>

I like the direction of this RFC and agree with Michael's points about it.

The "pure" and "const" history is definitely there, but I
don't think it
makes sense any more. I think narrow, precise, and well specified
attributes are *much* better for LLVM's IR, especially as we diversify the
set of frontends and language semantics we support.

There will be plenty of code changes required, but I think the changes are
tractable (these are relatively easy to audit for) and not risky. If Sanjoy
has the cycles to run with this, fantastic.

One thing we should make sure to do is update the langref to be *really
clear* here. =] But I suspect Sanjoy is all over that.

On Mon, Jan 2, 2017 at 11:49 PM Michael Kuperstein via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> This sounds right to me.
>
> IIUC, historically, readonly and readnone are meant to model the
"pure"
> and "const" GCC attributes. These attributes make pretty strong
guarantees:
>
> "[a pure] function can be subject to common subexpression elimination
and
> loop optimization just as an arithmetic operator would be. These functions
> should be declared with the attribute pure [...] Interesting non-pure
> functions are functions with infinite loops or those depending on volatile
> memory or other system resource, that may change between two consecutive
> calls (such as feof in a multithreading environment)."
>
> In particular, pure/const imply termination - something that's not
> entirely clear w.r.t readonly. However, apparently, they don't imply
> nothrow. I've actually always thought they *do* imply it - and said so
> on-list :-) - but it looks like GCC itself doesn't interpret them that
way.
> E.g. see John Regher's example here: https://t.co/REzy5m1tT3
> So there's at least one use-case for possibly throwing
readonly/readnone.
>
> As a side note, I'm slightly less optimistic about the amount of
required
> code fixes. One thing that comes to mind is that we need to make sure we
> mark all(?) the intrinsics currently marked readonly/argmemonly/readnone as
> nothrow. This should be mostly mechanical, I hope, but it's a decent
amount
> of churn.
>
> Michael
>
>
>
>
> On 2 January 2017 at 22:18, Sanjoy Das via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> LLVM today does not clearly specify if a function specified to not
> write to memory (i.e. readonly or readnone) is allowed to throw
> exceptions.
>
> LangRef is ambiguous on this issue.  The normative statement is
> "[readnone/readonly functions] cannot unwind exceptions by calling the
> C++ exception throwing methods" which does not decide an answer for
> non C++ languages.  It used to say (h/t Daniel Berlin): "This means
> that it cannot unwind exceptions by calling the C++ exception throwing
> methods, but could use the unwind instruction.", but that bit of
> documentation died with the unwind instruction.
>
> I'd like to separate unwindability from memory effects, and officially
> change our stance to be "readonly / readnone functions are allowed to
> throw exceptions".
>
> Here are two supporting reasons:
>
> # `resume` is already modeled as readnone
>
> The easiest way to verify this is via FunctionAttrs; it infers the
> following function as readnone:
>
> define void @f() personality i8 42 {
>   resume i32 0
> }
>
>
> Modeling `resume` as `readnone` is defensible -- it is a control flow
> transfer instruction, not so different from `ret`.  Moreover, it
> _cannot_ be modeled as having observable side effects or writes to
> memory (`resume` cannot send packets over the network or write to a
> global) because otherwise we'd be unable to inline @f into @g below:
>
> define void @f(i32 %x) personality i32 3 {
>   resume i32 %x
> }
>
> define i32 @g(i32 %x) personality i32 3 {
>   invoke void @f(i32 %x) to label %normal unwind label %unwind
>
> normal:
>   ret i32 0
>
> unwind:
>   %t = landingpad i32 cleanup
>   ret i32 %t
> }
>
> since it gets rid of a `resume` and thus a side effect (by
> assumption).
>
>
> # We're probably already there (but we need an audit)
>
> All said and done, the situation is not as "loosey goosey" as I
made
> it sound like.  mayHaveSideEffects() is defined as "mayWriteToMemory()
> || mayThrow()"; and this shows in e.g. EarlyCSE which will refuse to
> DCE the call to @f in @g
>
> declare void @f() readnone
>
> define void @g() {
>   call void @f()
>   ret void
> }
>
> unless @f is also marked nounwind.
>
> I've already fixed the one other instance I was aware of in
> https://reviews.llvm.org/rL290794 (but I will revert that patch if we
> decide against this RFC).
>
> We won't lose any expressive power either -- if there are situations
> where we have important optimizations firing under the "readonly
> implies nounwind" assumption, we can either
>
>  - Teach FunctionAttrs to infer nounwind for readonly functions with
>    C++ unwind personalities.
>
>  - For external declarations generated by the compiler (say from the
>    standard library): if the functions are actually nounwind, mark
>    them as nounwind; and not rely on LLVM inferring nounwind from
>    readonly.
>
>
> My (unrealistic?) hope is that this would mostly be a specification
> change and not involve a lot of code fixes.
>
> The change is also trivially upgrade-safe for older bitcode -- calls
> to readonly / readnone functions that do not throw _may_ get optimized
> less, but that should not be a correctness problem.
>
> What do you think?
>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170103/7dee56f8/attachment-0001.html>

Hi Michael,

On Mon, Jan 2, 2017 at 11:49 PM, Michael Kuperstein
<michael.kuperstein at gmail.com> wrote:
> This sounds right to me.
>
> IIUC, historically, readonly and readnone are meant to model the
"pure" and
> "const" GCC attributes. These attributes make pretty strong
guarantees:
>
> "[a pure] function can be subject to common subexpression elimination
and
> loop optimization just as an arithmetic operator would be. These functions
> should be declared with the attribute pure [...] Interesting non-pure
> functions are functions with infinite loops or those depending on volatile
> memory or other system resource, that may change between two consecutive
> calls (such as feof in a multithreading environment)."
>
> In particular, pure/const imply termination - something that's not
entirely
> clear w.r.t readonly. However, apparently, they don't imply nothrow.
I've
> actually always thought they *do* imply it - and said so on-list :-) - but
> it looks like GCC itself doesn't interpret them that way. E.g. see John
> Regher's example here: https://t.co/REzy5m1tT3
> So there's at least one use-case for possibly throwing
readonly/readnone.
One important thing to note then: clang marks const and pure functions
as nounwind *explicitly*.  That needs to be fixed.

https://godbolt.org/g/SMF4C9
> As a side note, I'm slightly less optimistic about the amount of
required
> code fixes. One thing that comes to mind is that we need to make sure we
> mark all(?) the intrinsics currently marked readonly/argmemonly/readnone as
> nothrow. This should be mostly mechanical, I hope, but it's a decent
amount
> of churn.
The behavior around intrinsics today is that they're implicitly marked
NoUnwind unless they're specifically annotated as [Throws], of which
there are very few instances (statepoints, stackmap, patchpoint,
coro_*).  My intent was to (document and) keep this behavior.

-- Sanjoy

I've always been in the "readnone implies nounwind" camp, but
I've changed
my mind, and I'm in favor of this RFC now.

I think in the past I was hung up on the idea that every language typically
has some "exception object" that is stored in memory, and the user
code
interrogates it by loading, so we need to model stores when throwing an
exception. Right now I'm imagining an EH personality that uses i32 error
codes as its exceptional return value, which would look like this:

  invoke void @f() to label %next unwind label %lpad ; could be readnone
...
lpad:
  %vals = i32 landingpad ... ; suppose there is no selector value in this
personality

define void @f() readnone {
  resume i32 42  ; imagine that resume could initiate exceptional control
flow like the old 'unwind' instruction
}

With a personality like this, there are no llvm-visible memory operations
looking at the exception, so it makes sense for @f to be readnone.

On Mon, Jan 2, 2017 at 10:18 PM, Sanjoy Das via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> LLVM today does not clearly specify if a function specified to not
> write to memory (i.e. readonly or readnone) is allowed to throw
> exceptions.
>
> LangRef is ambiguous on this issue.  The normative statement is
> "[readnone/readonly functions] cannot unwind exceptions by calling the
> C++ exception throwing methods" which does not decide an answer for
> non C++ languages.  It used to say (h/t Daniel Berlin): "This means
> that it cannot unwind exceptions by calling the C++ exception throwing
> methods, but could use the unwind instruction.", but that bit of
> documentation died with the unwind instruction.
>
> I'd like to separate unwindability from memory effects, and officially
> change our stance to be "readonly / readnone functions are allowed to
> throw exceptions".
>
> Here are two supporting reasons:
>
> # `resume` is already modeled as readnone
>
> The easiest way to verify this is via FunctionAttrs; it infers the
> following function as readnone:
>
> define void @f() personality i8 42 {
>   resume i32 0
> }
>
>
> Modeling `resume` as `readnone` is defensible -- it is a control flow
> transfer instruction, not so different from `ret`.  Moreover, it
> _cannot_ be modeled as having observable side effects or writes to
> memory (`resume` cannot send packets over the network or write to a
> global) because otherwise we'd be unable to inline @f into @g below:
>
> define void @f(i32 %x) personality i32 3 {
>   resume i32 %x
> }
>
> define i32 @g(i32 %x) personality i32 3 {
>   invoke void @f(i32 %x) to label %normal unwind label %unwind
>
> normal:
>   ret i32 0
>
> unwind:
>   %t = landingpad i32 cleanup
>   ret i32 %t
> }
>
> since it gets rid of a `resume` and thus a side effect (by
> assumption).
>
>
> # We're probably already there (but we need an audit)
>
> All said and done, the situation is not as "loosey goosey" as I
made
> it sound like.  mayHaveSideEffects() is defined as "mayWriteToMemory()
> || mayThrow()"; and this shows in e.g. EarlyCSE which will refuse to
> DCE the call to @f in @g
>
> declare void @f() readnone
>
> define void @g() {
>   call void @f()
>   ret void
> }
>
> unless @f is also marked nounwind.
>
> I've already fixed the one other instance I was aware of in
> https://reviews.llvm.org/rL290794 (but I will revert that patch if we
> decide against this RFC).
>
> We won't lose any expressive power either -- if there are situations
> where we have important optimizations firing under the "readonly
> implies nounwind" assumption, we can either
>
>  - Teach FunctionAttrs to infer nounwind for readonly functions with
>    C++ unwind personalities.
>
>  - For external declarations generated by the compiler (say from the
>    standard library): if the functions are actually nounwind, mark
>    them as nounwind; and not rely on LLVM inferring nounwind from
>    readonly.
>
>
> My (unrealistic?) hope is that this would mostly be a specification
> change and not involve a lot of code fixes.
>
> The change is also trivially upgrade-safe for older bitcode -- calls
> to readonly / readnone functions that do not throw _may_ get optimized
> less, but that should not be a correctness problem.
>
> What do you think?
>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170103/230d4a56/attachment-0001.html>