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

On 01/05/2017 10:55 AM, Sanjoy Das wrote:
> Hi Hal,
>
> On Thu, Jan 5, 2017 at 6:12 AM, Hal Finkel <hfinkel at anl.gov>
wrote:
>> On 01/04/2017 10:35 PM, Sanjoy Das via llvm-dev wrote:
>>> 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
>
> -- Sanjoy
>
>>   -Hal
>>
>>>    "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. :)
>>>
>>> @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
>>>
>>>
>>> On Tue, Jan 3, 2017 at 11:52 AM, Daniel Berlin <dberlin at
dberlin.org>
>>> wrote:
>>>>
>>>> On Tue, Jan 3, 2017 at 10:47 AM, Michael Kuperstein via
llvm-dev
>>>> <llvm-dev at lists.llvm.org> wrote:
>>>>>
>>>>>
>>>>> On Tue, Jan 3, 2017 at 9:59 AM, Sanjoy Das via llvm-dev
>>>>> <llvm-dev at lists.llvm.org> wrote:
>>>>>> 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
>>>>>>
>>>>> 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:)
>>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> --
>> Hal Finkel
>> Lead, Compiler Technology and Programming Languages
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

On Thu, Jan 5, 2017 at 9:19 AM, Hal Finkel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> On 01/05/2017 10:55 AM, Sanjoy Das wrote:
>
>> Hi Hal,
>>
>> On Thu, Jan 5, 2017 at 6:12 AM, Hal Finkel <hfinkel at anl.gov>
wrote:
>>
>>> On 01/04/2017 10:35 PM, Sanjoy Das via llvm-dev wrote:
>>>
>>>> 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.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170105/590b9d68/attachment-0001.html>

On 01/05/2017 12:17 PM, Reid Kleckner wrote:
> On Thu, Jan 5, 2017 at 9:19 AM, Hal Finkel via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>
>     On 01/05/2017 10:55 AM, Sanjoy Das wrote:
>
>         Hi Hal,
>
>         On Thu, Jan 5, 2017 at 6:12 AM, Hal Finkel <hfinkel at anl.gov
>         <mailto:hfinkel at anl.gov>> wrote:
>
>             On 01/04/2017 10:35 PM, Sanjoy Das via llvm-dev wrote:
>
>                 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.
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 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.
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170105/be83f732/attachment.html>

On Thu, Jan 5, 2017 at 10:17 AM, Reid Kleckner <rnk at google.com>
wrote:
> On Thu, Jan 5, 2017 at 9:19 AM, Hal Finkel via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>>
>>
>> On 01/05/2017 10:55 AM, Sanjoy Das wrote:
>>>
>>> Hi Hal,
>>>
>>> On Thu, Jan 5, 2017 at 6:12 AM, Hal Finkel <hfinkel at
anl.gov> wrote:
>>>>
>>>> On 01/04/2017 10:35 PM, Sanjoy Das via llvm-dev wrote:
>>>>>
>>>>> 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