llvm dev - Dec 2018 - RFC: Supported Optimizations attribute

On 12/4/18 3:21 PM, John McCall wrote:
>
> On 4 Dec 2018, at 17:50, Philip Reames wrote:
>
>     Skimming along, apologies if I'm repeating something which already
>     got said.
>
>     If I understand this correctly, the basic problem we're trying to
>     solve is to use a local hint (the invariant.group) to make a
>     global assumption about other code which might exist elsewhere
>     outside the function. The attribute proposed can basically be
>     phrased as describing a universe of functions within which our
>     desired global property holds.  There's an ambiguity about what is
>     allowed to be assumed about code outside that universe.
>
>     I think it's important to note that we have a precedent of
>     something similar to this in TBAA.  TBAA information coming from
>     different modules has the same base problem. We solve it by using
>     the "root" of the TBAA tree as a scope descriptor, and
essentially
>     making two TBAA nodes from distinct roots incomparable.
>
>     Can someone explain concisely why a similar scheme couldn't be
>     used to solve this problem?
>
> TBAA is conservative in /two/ ways:
> - It allows two accesses to alias if they have TBAA nodes with 
> different roots.
> - It allows two accesses to alias if only one of them has a TBAA node.
>
> The second is what doesn't generalize: there are optimizations where 
> you need to
> rely on transition points being explicitly identified. Looking at a 
> function
> with no identified transition points, you don't know whether it 
> actually doesn't
> transition or whether it was compiled without the transitions being 
> explicitly
> marked. There's no way to extend the TBAA idea to make that work.
>
>     On 12/4/18 11:24 AM, John McCall via llvm-dev wrote:
>
>         Note that IPO is generally permitted to partially inline or
>         outline code,
>         and so good-faith optimizations that e.g. require two
>         instructions to be moved
>         in tandem or not at all must use tokens to establish that
>         unbreakable
>         relationship.
>
>     I think the way your framing this is dangerous.  We absolutely can
>     not allow any annotation of this form to *weaken* the semantics of
>     the existing IR. We can and should impose a criteria that any
>     extension of this variety strictly add information to the IR which
>     might not have been previously inferred.  We can then design rules
>     for how to preserve our new information as long as possible, but
>     framing this in terms of disallowed transformations is really a
>     non-starter.
>
> That's exactly what I was trying to convey here. Authors of good-faith
> optimizations need to design their representations so that transformations
> that know nothing about their optimizations but merely preserve semantics
> and well-formed IR structure will not break their representations. The 
> only
> transforms that need to know about the existence of good-faith 
> optimizations
> are interprocedural optimizations; furthermore, those optimizations
don't
> need to know about any good-faith optimizations specifically, they 
> just need
> to understand how to correctly update the supported_optimizations list.
> That is a very small burden on IPO that enables an interesting class of
> language-specific optimizations.
>
Two responses:

1) My comment was on *framing*, not substance.  I'm not debating the 
*semantics* you've proposed (here), just the way they're described.  The
way they're described here is very likely to lead to problematic 
misinterpretation.

2) Reading back through your description again, it really sounds like 
you've reinvented the rules for metadata with an alternate framing.  The 
only part which is possibly new is the IPO rules you want to apply.  
Worth noting is that we already have existing support for metadata on 
both instructions and functions.

If we frame all of this as being *metadata*, then your 
supported_optimization attribute reduces to the need to define an 
intersect rule for metadata on functions during inlining and IPO. Note 
that we already have precedence for conservative-by-default handling at 
the instruction level, so extending that to the function scope seems 
natural.

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

On 5 Dec 2018, at 12:19, Philip Reames wrote:
> On 12/4/18 3:21 PM, John McCall wrote:
>>
>> On 4 Dec 2018, at 17:50, Philip Reames wrote:
>>
>>     Skimming along, apologies if I'm repeating something which 
>> already
>>     got said.
>>
>>     If I understand this correctly, the basic problem we're trying
to
>>     solve is to use a local hint (the invariant.group) to make a
>>     global assumption about other code which might exist elsewhere
>>     outside the function. The attribute proposed can basically be
>>     phrased as describing a universe of functions within which our
>>     desired global property holds.  There's an ambiguity about what
>> is
>>     allowed to be assumed about code outside that universe.
>>
>>     I think it's important to note that we have a precedent of
>>     something similar to this in TBAA.  TBAA information coming from
>>     different modules has the same base problem. We solve it by using
>>     the "root" of the TBAA tree as a scope descriptor, and 
>> essentially
>>     making two TBAA nodes from distinct roots incomparable.
>>
>>     Can someone explain concisely why a similar scheme couldn't be
>>     used to solve this problem?
>>
>> TBAA is conservative in /two/ ways:
>> - It allows two accesses to alias if they have TBAA nodes with 
>> different roots.
>> - It allows two accesses to alias if only one of them has a TBAA 
>> node.
>>
>> The second is what doesn't generalize: there are optimizations
where
>> you need to
>> rely on transition points being explicitly identified. Looking at a 
>> function
>> with no identified transition points, you don't know whether it 
>> actually doesn't
>> transition or whether it was compiled without the transitions being 
>> explicitly
>> marked. There's no way to extend the TBAA idea to make that work.
>>
>>     On 12/4/18 11:24 AM, John McCall via llvm-dev wrote:
>>
>>         Note that IPO is generally permitted to partially inline or
>>         outline code,
>>         and so good-faith optimizations that e.g. require two
>>         instructions to be moved
>>         in tandem or not at all must use tokens to establish that
>>         unbreakable
>>         relationship.
>>
>>     I think the way your framing this is dangerous.  We absolutely 
>> can
>>     not allow any annotation of this form to *weaken* the semantics 
>> of
>>     the existing IR. We can and should impose a criteria that any
>>     extension of this variety strictly add information to the IR 
>> which
>>     might not have been previously inferred.  We can then design 
>> rules
>>     for how to preserve our new information as long as possible, but
>>     framing this in terms of disallowed transformations is really a
>>     non-starter.
>>
>> That's exactly what I was trying to convey here. Authors of 
>> good-faith
>> optimizations need to design their representations so that 
>> transformations
>> that know nothing about their optimizations but merely preserve 
>> semantics
>> and well-formed IR structure will not break their representations. 
>> The only
>> transforms that need to know about the existence of good-faith 
>> optimizations
>> are interprocedural optimizations; furthermore, those optimizations 
>> don't
>> need to know about any good-faith optimizations specifically, they 
>> just need
>> to understand how to correctly update the supported_optimizations 
>> list.
>> That is a very small burden on IPO that enables an interesting class 
>> of
>> language-specific optimizations.
>>
> Two responses:
>
> 1) My comment was on *framing*, not substance.  I'm not debating the 
> *semantics* you've proposed (here), just the way they're
described. 
> The way they're described here is very likely to lead to problematic 
> misinterpretation.
Yes, and I'm trying to improve the way I'm talking about it, so I would 
appreciate feedback on whether you feel that my clarifications are still 
prone to problematic misinterpretations.
> 2) Reading back through your description again, it really sounds like 
> you've reinvented the rules for metadata with an alternate framing.  
> The only part which is possibly new is the IPO rules you want to 
> apply.  Worth noting is that we already have existing support for 
> metadata on both instructions and functions.
Optimizations relying wholly on metadata can't have this problem because 
of the existing rules for metadata: if the optimization is correct even 
when metadata is randomly dropped, it's correct when metadata is 
incompletely added in the first place.  The problem is specific to 
intrinsic-centric optimizations, as intrinsics cannot be summarily 
dropped like metadata (which is necessary for the correctness of the 
optimization) but may not have been added to all functions in the module 
because of e.g. LTO.

Would this conversation would be more productive if we worked through an 
example optimization so that you could see the issues involved?

John.

On 12/5/18 9:45 AM, John McCall wrote:
> On 5 Dec 2018, at 12:19, Philip Reames wrote:
>> On 12/4/18 3:21 PM, John McCall wrote:
>>>
>>> On 4 Dec 2018, at 17:50, Philip Reames wrote:
>>>
>>>     Skimming along, apologies if I'm repeating something which
already
>>>     got said.
>>>
>>>     If I understand this correctly, the basic problem we're
trying to
>>>     solve is to use a local hint (the invariant.group) to make a
>>>     global assumption about other code which might exist elsewhere
>>>     outside the function. The attribute proposed can basically be
>>>     phrased as describing a universe of functions within which our
>>>     desired global property holds.  There's an ambiguity about
what is
>>>     allowed to be assumed about code outside that universe.
>>>
>>>     I think it's important to note that we have a precedent of
>>>     something similar to this in TBAA.  TBAA information coming
from
>>>     different modules has the same base problem. We solve it by
using
>>>     the "root" of the TBAA tree as a scope descriptor,
and essentially
>>>     making two TBAA nodes from distinct roots incomparable.
>>>
>>>     Can someone explain concisely why a similar scheme couldn't
be
>>>     used to solve this problem?
>>>
>>> TBAA is conservative in /two/ ways:
>>> - It allows two accesses to alias if they have TBAA nodes with 
>>> different roots.
>>> - It allows two accesses to alias if only one of them has a TBAA
node.
>>>
>>> The second is what doesn't generalize: there are optimizations
where
>>> you need to
>>> rely on transition points being explicitly identified. Looking at a
>>> function
>>> with no identified transition points, you don't know whether it
>>> actually doesn't
>>> transition or whether it was compiled without the transitions being
>>> explicitly
>>> marked. There's no way to extend the TBAA idea to make that
work.
>>>
>>>     On 12/4/18 11:24 AM, John McCall via llvm-dev wrote:
>>>
>>>         Note that IPO is generally permitted to partially inline or
>>>         outline code,
>>>         and so good-faith optimizations that e.g. require two
>>>         instructions to be moved
>>>         in tandem or not at all must use tokens to establish that
>>>         unbreakable
>>>         relationship.
>>>
>>>     I think the way your framing this is dangerous.  We absolutely
can
>>>     not allow any annotation of this form to *weaken* the semantics
of
>>>     the existing IR. We can and should impose a criteria that any
>>>     extension of this variety strictly add information to the IR
which
>>>     might not have been previously inferred.  We can then design
rules
>>>     for how to preserve our new information as long as possible,
but
>>>     framing this in terms of disallowed transformations is really a
>>>     non-starter.
>>>
>>> That's exactly what I was trying to convey here. Authors of
good-faith
>>> optimizations need to design their representations so that 
>>> transformations
>>> that know nothing about their optimizations but merely preserve 
>>> semantics
>>> and well-formed IR structure will not break their representations. 
>>> The only
>>> transforms that need to know about the existence of good-faith 
>>> optimizations
>>> are interprocedural optimizations; furthermore, those optimizations
>>> don't
>>> need to know about any good-faith optimizations specifically, they 
>>> just need
>>> to understand how to correctly update the supported_optimizations
list.
>>> That is a very small burden on IPO that enables an interesting
class of
>>> language-specific optimizations.
>>>
>> Two responses:
>>
>> 1) My comment was on *framing*, not substance.  I'm not debating
the
>> *semantics* you've proposed (here), just the way they're
described. 
>> The way they're described here is very likely to lead to
problematic
>> misinterpretation.
>
> Yes, and I'm trying to improve the way I'm talking about it, so I 
> would appreciate feedback on whether you feel that my clarifications 
> are still prone to problematic misinterpretations.
Ah, I'd misread your intent with the last response.  I'd read it as 
disputing my previous point, not accepting it and proposing a reframing 
in that spirit.  Rereading with those eyes, yes, I think your last 
description is much better than the previous ones.
>
>> 2) Reading back through your description again, it really sounds like 
>> you've reinvented the rules for metadata with an alternate
framing. 
>> The only part which is possibly new is the IPO rules you want to 
>> apply.  Worth noting is that we already have existing support for 
>> metadata on both instructions and functions.
>
> Optimizations relying wholly on metadata can't have this problem 
> because of the existing rules for metadata: if the optimization is 
> correct even when metadata is randomly dropped, it's correct when 
> metadata is incompletely added in the first place.  The problem is 
> specific to intrinsic-centric optimizations, as intrinsics cannot be 
> summarily dropped like metadata (which is necessary for the 
> correctness of the optimization) but may not have been added to all 
> functions in the module because of e.g. LTO.
How is this not handled by the second rule for TBAA about comparing two 
nodes where one has metadata and the other doesn't? In general, as long 
as the *absence* of a annotation is enough to *disable* an optimization 
then there's no problem with using the root scheme.  The only 
problematic case would be if the *absence* of an annotation signaled the 
*legality* of an optimization which wouldn't otherwise be legal if the 
annotation was present.

If we do have to handle the last case, we can probably do it by 
requiring the function have metadata of the same name which is dropped 
if any node within the scope is dropped.  This also bears a lot of 
similarity to your proposed attribute semantics, but reframed entirely 
as metadata.
>
> Would this conversation would be more productive if we worked through 
> an example optimization so that you could see the issues involved?
Might be.  I'd also be happy to jump on a quick call so that we can 
explain points with higher bandwidth.
>
> John.