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
rG3bb2dbd66586 (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 :slight_smile: - 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

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.

Hi Michael,

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 :slight_smile: - but
it looks like GCC itself doesn't interpret them that way. E.g. see John
Regher's example here: https://godbolt.org/g/65jg0i
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.

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

This is pretty much what started this (and thank you very much to Sanjoy
for being willing to to get this resolved :P)

The current text for readonly is "On a function, this attribute indicates
that the function does not ... *modify any state (e.g. memory, control
registers, etc) visible to caller functions*. ... A readonly function
always returns the same value (*or unwinds an exception identically*) when
called with the same set of arguments and global state.* It cannot unwind
an exception by calling the **C++** exception throwing methods*."

Which, while, the lawyer part of me enjoys the amount of hair splitting
this allows, the other part of me is in the "what is this really trying to
mean" category :slight_smile:

Hi Michael,

> 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 :slight_smile: -
but
> it looks like GCC itself doesn't interpret them that way. E.g. see John
> Regher's example here: https://godbolt.org/g/65jg0i
> 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.

Compiler Explorer

Hah. So it does.
Eric, this was originally your change. Do I understand GCC's behavior
incorrectly?

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

Oh, ok, this makes a lot of sense.

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.

Hi Michael,

> 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 :slight_smile: -
but
> it looks like GCC itself doesn't interpret them that way. E.g. see John
> Regher's example here: https://godbolt.org/g/65jg0i
> 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.

Compiler Explorer

Hah. So it does.
Eric, this was originally your change. Do I understand GCC's behavior
incorrectly?

No, but I was in the office when Kenny wrote ipa-pure-const, which is the
equivalent to llvm's pass to find function attributions, and it mostly
wasn't thought about.

GCC isn't as consistent as one may think here.

           /* Non-looping const functions always return normally.
          Otherwise the call might not return or have side-effects
          that forbids hoisting possibly trapping expressions
          before it. */
           int flags = gimple_call_flags (stmt);
           if (!(flags & ECF_CONST)
           >> (flags & ECF_LOOPING_CONST_OR_PURE))
         BB_MAY_NOTRETURN (block) = 1;
         }

It also, for example, will do this:
double cos (double) __attribute__ ((const));
double sin (double) __attribute__ ((const));
double f(double a)
{
   double b;
   double c,d;
   double (*fp) (double) __attribute__ ((const));
   /* Partially redundant call */
   if (a < 2.0)
     {
       fp = sin;
       c = fp (a);
     }
   else
     {
       c = 1.0;
       fp = cos;
     }
   d = fp (a);
   return d + c;
}

into
double cos (double) __attribute__ ((const));
double sin (double) __attribute__ ((const));
double f(double a)
{
   double b;
   double c,d;
   double (*fp) (double) __attribute__ ((const));
   /* Partially redundant call */
   if (a < 2.0)
     {
       fp = sin;
       c = fp (a);
     }
   else
     {
       c = 1.0;
       fp = cos;
       temp = fp(a)
     }
   d = phi(c, temp)
   return d + c;
}

This only works if the second call to sin is guaranteed not to throw, no?

In any case, optimizations check throwing separately from pure/const, but
i'm not sure it's well thought out here.

Note that GCC also has a notion of possibly infinite looping pure/const as
well:)

I just realized that there's an annoying corner case to this scheme --
I can't DSE stores across readnone maythrow function calls because the
exception handler could read memory. That is, in:

try {
  *a = 10;
  call void @readnone_mayunwind_fn();
  *a = 20;
} catch (...) {
  assert(*a == 10);
}

I can't DSE the `*a = 10` store.

As far as I can tell, the most restrictive memory attribute for a
potentially throwing function is readonly. "readnone may-unwind" does
not make sense. "readonly may-unwind" is fine because even if the EH
handler writes to memory, the code in the normal execution path does
not have worry about the memory clobbers.

I thought I had this figured out, but now it looks like I gotta think more. :slight_smile:

@Danny: I agree with your assessment of the example; unless the
compiler knows that `cos` won't throw (which it may very well know
since it is the standard library function, but I don't know GCC
internals), the transform is wrong.

-- Sanjoy

I just realized that there's an annoying corner case to this scheme --
I can't DSE stores across readnone maythrow function calls because the
exception handler could read memory. That is, in:

try {
  *a = 10;
  call void @readnone_mayunwind_fn();
  *a = 20;
} catch (...) {
  assert(*a == 10);
}

I can't DSE the `*a = 10` store.

As far as I can tell, the most restrictive memory attribute for a
potentially throwing function is readonly. "readnone may-unwind" does
not make sense. "readonly may-unwind" is fine because even if the EH
handler writes to memory, the code in the normal execution path does
not have worry about the memory clobbers.

I thought I had this figured out, but now it looks like I gotta think
more. :slight_smile:

@Danny: I agree with your assessment of the example; unless the
compiler knows that `cos` won't throw (which it may very well know
since it is the standard library function, but I don't know GCC
internals), the transform is wrong.

It does not know that, actually.

I would say that GCC pretty much is a grab bag, since i wrote that for the
gcc regression testsuite, and it's still tested :slight_smile:

There are like 3 optimization testcases that use nothrow, and john's
example happens to just fall into this case:

   if (stmt_ends_bb_p (stmt)
       >> gimple_has_volatile_ops (stmt)
       >> gimple_has_side_effects (stmt)
       >> stmt_could_throw_p (stmt))
     return MOVE_IMPOSSIBLE;

Some of the passes check throwing, some of them don't.

I just realized that there's an annoying corner case to this scheme --
I can't DSE stores across readnone maythrow function calls because the
exception handler could read memory. That is, in:

try {
   *a = 10;
   call void @readnone_mayunwind_fn();
   *a = 20;
} catch (...) {
   assert(*a == 10);
}

I can't DSE the `*a = 10` store.

As far as I can tell, the most restrictive memory attribute for a
potentially throwing function is readonly. "readnone may-unwind" does
not make sense.

Why not? I've not followed this thread in detail, but it seems like you're discussing allowing the modeling of EH schemes that don't access accessible memory. In that case, a may-unwind readnone function is just one that makes its decision about if/what to throw based only on its arguments.

  -Hal

Hi Hal,

I just realized that there's an annoying corner case to this scheme --
I can't DSE stores across readnone maythrow function calls because the
exception handler could read memory. That is, in:

try {
   *a = 10;
   call void @readnone_mayunwind_fn();
   *a = 20;
} catch (...) {
   assert(*a == 10);
}

I can't DSE the `*a = 10` store.

As far as I can tell, the most restrictive memory attribute for a
potentially throwing function is readonly. "readnone may-unwind" does
not make sense.

Why not? I've not followed this thread in detail, but it seems like you're
discussing allowing the modeling of EH schemes that don't access accessible
memory. In that case, a may-unwind readnone function is just one that makes
its decision about if/what to throw based only on its arguments.

If the call to @readnone_mayunwind_fn throws and I've DSE'ed the "*a =
10" store, the exception handler will fail the *a == 10 assert (assume
*a is not 10 to begin with). The function call itself is readnone,
but its exceptional continuation may read any part of the heap.

This isn't a big deal, but it means that "readnone may-unwind" will
effectively have to be treated as "readonly may-unwind" -- I don't see
any optimization that would be applicable to one and not the other.
Maybe we should just move ahead with that (that readnone may-unwind is
allowed, but if you want readnone-like optimizations then you need to
also mark it as nounwind)?

-- Sanjoy

Hi Hal,

I just realized that there's an annoying corner case to this scheme --
I can't DSE stores across readnone maythrow function calls because the
exception handler could read memory. That is, in:

try {
    *a = 10;
    call void @readnone_mayunwind_fn();
    *a = 20;
} catch (...) {
    assert(*a == 10);
}

I can't DSE the `*a = 10` store.

As far as I can tell, the most restrictive memory attribute for a
potentially throwing function is readonly. "readnone may-unwind" does
not make sense.

Why not? I've not followed this thread in detail, but it seems like you're
discussing allowing the modeling of EH schemes that don't access accessible
memory. In that case, a may-unwind readnone function is just one that makes
its decision about if/what to throw based only on its arguments.

If the call to @readnone_mayunwind_fn throws and I've DSE'ed the "*a =
10" store, the exception handler will fail the *a == 10 assert (assume
*a is not 10 to begin with). The function call itself is readnone,
but its exceptional continuation may read any part of the heap.

This isn't a big deal, but it means that "readnone may-unwind" will
effectively have to be treated as "readonly may-unwind" -- I don't see
any optimization that would be applicable to one and not the other.
Maybe we should just move ahead with that (that readnone may-unwind is
allowed, but if you want readnone-like optimizations then you need to
also mark it as nounwind)?

Yes, I think that makes sense. The attribute only applies to the function anyway, so what exception handlers might do (which is assumed to be reading/writing any memory that might be available to them) must be reasoned about separately.

  -Hal

I don't think we need or want to do that. The way I see it, readonly
implies that the exception handler cannot write memory readable by LLVM.
Similarly, readnone should imply that the exception handler does not read
memory written by LLVM. Basically, any function that may unwind but also
has these attributes asserts that the exception handler is operating
outside of memory modeled by LLVM.

I don't think we'll do DSE in your example because the store isn't dead,
it's visible along the invoke's unwind edge, and we don't need to change
the semantics of readnone to see that.

I don’t understand why that’s desirable, and I think it would severely limit our ability to infer these attributes for functions that unwind. You’d need to prove things – likely unknowable things – about the exception handlers in place around every call site of a function in order to mark it readonly, readnone, etc. We’d have the same problem with the attribute parameters. I’m fairly certain we do need and want to separate these concerns. This way we can apply callsite specific reasoning to the potential effects of exception handlers separate from what the function itself might do. -Hal

I don’t understand why that’s desirable, and I think it would severely limit our ability to infer these attributes for functions that unwind. You’d need to prove things – likely unknowable things – about the exception handlers in place around every call site of a function in order to mark it readonly, readnone, etc. We’d have the same problem with the attribute parameters. I’m fairly certain we do need and want to separate these concerns. This way we can apply callsite specific reasoning to the potential effects of exception handlers separate from what the function itself might do.

What useful things would you be able to deduce from an “unwind readnone” function under these conditions?

I don’t think we’ll do DSE in your example because the store isn’t dead, it’s visible along the invoke’s unwind edge, and we don’t need to change the semantics of readnone to see that.

I’ve been wondering the same thing on Sanjoy’s example.

Hi Hal,

I just realized that there's an annoying corner case to this scheme --
I can't DSE stores across readnone maythrow function calls because the
exception handler could read memory. That is, in:

try {
    *a = 10;
    call void @readnone_mayunwind_fn();
    *a = 20;
} catch (...) {
    assert(*a == 10);
}

I can't DSE the `*a = 10` store.

As far as I can tell, the most restrictive memory attribute for a
potentially throwing function is readonly. "readnone may-unwind" does
not make sense.

Why not? I've not followed this thread in detail, but it seems like
you're
discussing allowing the modeling of EH schemes that don't access
accessible
memory. In that case, a may-unwind readnone function is just one that
makes
its decision about if/what to throw based only on its arguments.

If the call to @readnone_mayunwind_fn throws and I've DSE'ed the "*a =
10" store, the exception handler will fail the *a == 10 assert (assume
*a is not 10 to begin with). The function call itself is readnone,
but its exceptional continuation may read any part of the heap.

This isn't a big deal, but it means that "readnone may-unwind" will
effectively have to be treated as "readonly may-unwind" -- I don't see
any optimization that would be applicable to one and not the other.
Maybe we should just move ahead with that (that readnone may-unwind is
allowed, but if you want readnone-like optimizations then you need to
also mark it as nounwind)?

Yes, I think that makes sense. The attribute only applies to the function
anyway, so what exception handlers might do (which is assumed to be
reading/writing any memory that might be available to them) must be reasoned
about separately.

I don't think we need or want to do that. The way I see it, readonly implies
that the exception handler cannot write memory readable by LLVM. Similarly,
readnone should imply that the exception handler does not read memory
written by LLVM. Basically, any function that may unwind but also has these
attributes asserts that the exception handler is operating outside of memory
modeled by LLVM.

What Hal said, basically -- I'd rather not lose the ability to locally
reason about these attributes.

I don't think we'll do DSE in your example because the store isn't dead,
it's visible along the invoke's unwind edge, and we don't need to change the
semantics of readnone to see that.

I did not give a full example for brevity, but I was really going for:

void f(int* a) {
  *a = 20;
  call @readnone_may_unwind_fn();
  *a = 30;
}

Today EarlyCSE will DSE the first store to `a`, even though an
exception handler further up the stack could be reading from `a`. If
we allow "readnone may_unwind" functions then we'll have to be more
careful (than we are today) around implicit out-edges like this.

-- Sanjoy

Hi Mehdi,

[snip]

I don't understand why that's desirable, and I think it would severely limit
our ability to infer these attributes for functions that unwind. You'd need
to prove things -- likely unknowable things -- about the exception handlers
in place around every call site of a function in order to mark it readonly,
readnone, etc. We'd have the same problem with the attribute parameters. I'm
fairly certain we do need and want to separate these concerns. This way we
can apply callsite specific reasoning to the potential effects of exception
handlers separate from what the function itself might do.

What useful things would you be able to deduce from an “unwind readnone”
function under these conditions?

In theory you could do this transform:

void f(int*a) {
  *a = 20;
  call @mayunwind_readnone();
  *a = 30;
}

=>

void f(int*a) {
  // *a = 20;
  invoke @mayunwind_readnone() to %normal unwind %unwind

normal:
  *a = 30;
  ret void

unwind:
  %exc = landingpad
  *a = 20;
  resume %exc
}

(That is, PRE the store around the implicit edge by making it explicit.)

Generally though I don't see us doing this except under exceptional
(no pun intended!) circumstances.

-- Sanjoy

It is still only a function of its arguments, so it can be CSE’d. Also, if I have this: *a = 10; b = a_readnone_unwind_func(); *a = 10; I can still conclude that this last store is redundant and can be removed. I know that the readnone function does not touch it, and if it unwinds, than the later store is dead. If I know that &*a has not escaped to where an exception handler might access it, then I know that the first store than be removed. -Hal

In theory you could do this transform:

void f(int*a) {
  *a = 20;
  call @mayunwind_readnone();
  *a = 30;
}

=>

void f(int*a) {
  // *a = 20;
  invoke @mayunwind_readnone() to %normal unwind %unwind

normal:
  *a = 30;
  ret void

unwind:
  %exc = landingpad
  *a = 20;
  resume %exc
}

(That is, PRE the store around the implicit edge by making it explicit.)

Generally though I don't see us doing this except under exceptional
(no pun intended!) circumstances.

FWIW: I don't believe i've ever seen or written a modern PRE that doesn't
run screaming from exception edges.
(admittedly, most of them induce ordering constraints normal PRE algorithms
can't obey easily)