llvm dev - Sep 2015 - [PATCH] D12923: Add support for function attribute "notail"

On Tue, Sep 29, 2015 at 10:49 AM, Philip Reames <listmail at
philipreames.com>
wrote:
>
>
> On 09/28/2015 10:38 PM, Sanjoy Das wrote:
>
>>
>> > That was what I had in mind: the function attribute blocks tail
call
>> for statically direct calls but doesn't promise
>> > anything (in fact, does nothing) for indirect calls.
>> >
>> > Do you think we shouldn't make any promises for statically
direct calls
>> either? I don't see why it's hard to keep the
>> > promise that direct tail calls will be blocked. Do you have a
>> particular optimization in mind that would be difficult or
>> > impossible to implement if we promised to block direct calls?
>>
>> I think in this scheme we'll have problems around devirtualization.
>> For instance, you could start with a indirect call to a notail target
>> that would get TCO'ed (as an indirect call), after which
>> devirtualization or load/store motion would turn the indirect call
>> into a direct call; and you'd end up with a direct tail call to a
>> notail target.
>>
> Sanjoy hits on some of the same concerns I had with this.  In particular,
> there's a distinction between what the language specification defines
as a
> direct call and what the optimizer/compiler might turn into a direct call.
> At the source layer, we can *only* make guarantees about the former.  Any
> specification we write has to account for the fact the later are an
> implementation detail entirely under the control of the compiler. i.e.
> optimizations can not break the semantics.  You have to ensure this when
> defining the semantics.

By "statically direct calls", I meant the set of calls that can be
determined to be direct at the source level, which is normally a subset of
the calls that end up being direct calls after all the optimization passes
are run. I agree that we can probably promise or guarantee that tail call
will be blocked for direct calls at the source level. We don't guarantee
anything for indirect calls at the source level.

>
>
>> I don't know what your requirements are, but if I were you I'd
design
>> the `notail` marker to be logically part of a function's calling
>> convention.  That way functions marked `notail` get to do things that
>> are legal only if the call to them wasn't a tail call, because all
>> well-defined calls constrain the caller to match callee's
expectation
>> with respect to tail calls.  In the CFE, you could make the `notail`
>> attribute have the same restrictions / conventions as things like
>> `fastcall`.
>>
> I disagree with this slightly.  As I've stated previously, I think
there
> are two distinct semantics here: a) this call must be a notail call, and b)
> we'd "like" this to be a no tail, but it's optional. We
need to not mix
> them.
>
>>
>>
The semantics of the tail call marker I'm looking for is close to b), but
differs in whether we say it's optional or we guarantee that we block tail
call for a certain subset of calls (direct calls at the source level). I'm
inclined to have the tail call marker mean "notail is guaranteed if the
call is direct at the source level", but I wonder if it'll come back to
bite us.

Also, this tail call marker won't be used to enable optimizations on the
marked function that would be available only if it were known the call to
the function isn't TCO'ed. That might be an interesting idea to other
people, but it's not something that is needed for our use case.

> -- Sanjoy
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150929/5772b4b3/attachment.html>

On 09/29/2015 11:38 AM, Akira Hatanaka wrote:
> On Tue, Sep 29, 2015 at 10:49 AM, Philip Reames 
> <listmail at philipreames.com <mailto:listmail at
philipreames.com>> wrote:
>
>
>
>     On 09/28/2015 10:38 PM, Sanjoy Das wrote:
>
>
>         > That was what I had in mind: the function attribute blocks
>         tail call for statically direct calls but doesn't promise
>         > anything (in fact, does nothing) for indirect calls.
>         >
>         > Do you think we shouldn't make any promises for statically
>         direct calls either? I don't see why it's hard to keep the
>         > promise that direct tail calls will be blocked. Do you have
>         a particular optimization in mind that would be difficult or
>         > impossible to implement if we promised to block direct calls?
>
>         I think in this scheme we'll have problems around
>         devirtualization.
>         For instance, you could start with a indirect call to a notail
>         target
>         that would get TCO'ed (as an indirect call), after which
>         devirtualization or load/store motion would turn the indirect call
>         into a direct call; and you'd end up with a direct tail call to
a
>         notail target.
>
>     Sanjoy hits on some of the same concerns I had with this. In
>     particular, there's a distinction between what the language
>     specification defines as a direct call and what the
>     optimizer/compiler might turn into a direct call.  At the source
>     layer, we can *only* make guarantees about the former.  Any
>     specification we write has to account for the fact the later are
>     an implementation detail entirely under the control of the
>     compiler. i.e. optimizations can not break the semantics.  You
>     have to ensure this when defining the semantics.
>
>
> By "statically direct calls", I meant the set of calls that can
be
> determined to be direct at the source level, which is normally a 
> subset of the calls that end up being direct calls after all the 
> optimization passes are run. I agree that we can probably promise or 
> guarantee that tail call will be blocked for direct calls at the 
> source level. We don't guarantee anything for indirect calls at the 
> source level.
>
>
>
>         I don't know what your requirements are, but if I were you
I'd
>         design
>         the `notail` marker to be logically part of a function's
calling
>         convention.  That way functions marked `notail` get to do
>         things that
>         are legal only if the call to them wasn't a tail call, because
all
>         well-defined calls constrain the caller to match callee's
>         expectation
>         with respect to tail calls.  In the CFE, you could make the
>         `notail`
>         attribute have the same restrictions / conventions as things like
>         `fastcall`.
>
>     I disagree with this slightly.  As I've stated previously, I think
>     there are two distinct semantics here: a) this call must be a
>     notail call, and b) we'd "like" this to be a no tail, but
it's
>     optional. We need to not mix them.
>
>
>
> The semantics of the tail call marker I'm looking for is close to b), 
> but differs in whether we say it's optional or we guarantee that we 
> block tail call for a certain subset of calls (direct calls at the 
> source level). I'm inclined to have the tail call marker mean
"notail
> is guaranteed if the call is direct at the source level", but I wonder
> if it'll come back to bite us.
I think this is probably fine, but you need someone with clang/C++ spec 
knowledge that I don't have to help with the
definition.
>
> Also, this tail call marker won't be used to enable optimizations on 
> the marked function that would be available only if it were known the 
> call to the function isn't TCO'ed. That might be an interesting
idea
> to other people, but it's not something that is needed for our use
case.
>
>         -- Sanjoy
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150929/516eaf07/attachment.html>

I've been discussing the clang-side patch and making changes based on the
feedback I got for the last few weeks. Aaron has reviewed the patch and he
thinks it's OK now.

http://reviews.llvm.org/D12922

Do you have further comments on the llvm-side patch or the semantics of the
function attribute? Since the last time we discussed on the list, I've made
changes to disallow virtual functions and objective-c methods to be marked
not_tail_called, which further reduces unpredictability due to optimization.

On Tue, Sep 29, 2015 at 5:37 PM, Philip Reames <listmail at
philipreames.com>
wrote:
>
>
> On 09/29/2015 11:38 AM, Akira Hatanaka wrote:
>
> On Tue, Sep 29, 2015 at 10:49 AM, Philip Reames <listmail at
philipreames.com
> > wrote:
>
>>
>>
>> On 09/28/2015 10:38 PM, Sanjoy Das wrote:
>>
>>>
>>> > That was what I had in mind: the function attribute blocks
tail call
>>> for statically direct calls but doesn't promise
>>> > anything (in fact, does nothing) for indirect calls.
>>> >
>>> > Do you think we shouldn't make any promises for statically
direct
>>> calls either? I don't see why it's hard to keep the
>>> > promise that direct tail calls will be blocked. Do you have a
>>> particular optimization in mind that would be difficult or
>>> > impossible to implement if we promised to block direct calls?
>>>
>>> I think in this scheme we'll have problems around
devirtualization.
>>> For instance, you could start with a indirect call to a notail
target
>>> that would get TCO'ed (as an indirect call), after which
>>> devirtualization or load/store motion would turn the indirect call
>>> into a direct call; and you'd end up with a direct tail call to
a
>>> notail target.
>>>
>> Sanjoy hits on some of the same concerns I had with this.  In
particular,
>> there's a distinction between what the language specification
defines as a
>> direct call and what the optimizer/compiler might turn into a direct
call.
>> At the source layer, we can *only* make guarantees about the former. 
Any
>> specification we write has to account for the fact the later are an
>> implementation detail entirely under the control of the compiler. i.e.
>> optimizations can not break the semantics.  You have to ensure this
when
>> defining the semantics.
>
>
> By "statically direct calls", I meant the set of calls that can
be
> determined to be direct at the source level, which is normally a subset of
> the calls that end up being direct calls after all the optimization passes
> are run. I agree that we can probably promise or guarantee that tail call
> will be blocked for direct calls at the source level. We don't
guarantee
> anything for indirect calls at the source level.
>
>
>>
>>
>>> I don't know what your requirements are, but if I were you
I'd design
>>> the `notail` marker to be logically part of a function's
calling
>>> convention.  That way functions marked `notail` get to do things
that
>>> are legal only if the call to them wasn't a tail call, because
all
>>> well-defined calls constrain the caller to match callee's
expectation
>>> with respect to tail calls.  In the CFE, you could make the
`notail`
>>> attribute have the same restrictions / conventions as things like
>>> `fastcall`.
>>>
>> I disagree with this slightly.  As I've stated previously, I think
there
>> are two distinct semantics here: a) this call must be a notail call,
and b)
>> we'd "like" this to be a no tail, but it's optional.
We need to not mix
>> them.
>>
>>>
>>>
> The semantics of the tail call marker I'm looking for is close to b),
but
> differs in whether we say it's optional or we guarantee that we block
tail
> call for a certain subset of calls (direct calls at the source level).
I'm
> inclined to have the tail call marker mean "notail is guaranteed if
the
> call is direct at the source level", but I wonder if it'll come
back to
> bite us.
>
> I think this is probably fine, but you need someone with clang/C++ spec
> knowledge that I don't have to help with the definition.
>
>
> Also, this tail call marker won't be used to enable optimizations on
the
> marked function that would be available only if it were known the call to
> the function isn't TCO'ed. That might be an interesting idea to
other
> people, but it's not something that is needed for our use case.
>
>
>> -- Sanjoy
>>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151104/678f3238/attachment.html>