[llvm-dev] RFC: Supported Optimizations attribute

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
27 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Supported Optimizations attribute

Peter Smith via llvm-dev


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.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] RFC: Supported Optimizations attribute

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev

Honestly, I think well defined nulls are a complete different problem, and the approach taken by the null-pointer-is-valid attribute is simply wrong.  We have existing mechanisms for this (data layout, implicit null checks, etc..), and don't need a separate attribute on the function.

Philip

On 12/5/18 2:31 AM, Piotr Padlewski wrote:
An additional bit to the discussion: I think that "null-pointer-is-valid" attribute should also be handled in a similar manner - if one function calls
another one marked with "null-pointer-is-valid", then after inlining the function should also be marked with "null-pointer-is-valid".
I assume this attribute was added to handle kernel or embedded code correctly and probably there was no use case to do LTO between 
modules with and without this attribute (yet).
This, unfortunately, can't be solved with our supported_optimizations attribute, as null pointer dereference is considered to be UB by default.  
We would need something like "unsupported_optimizations", but I think this shows that this is not the last time when a similar problem will arise.


śr., 5 gru 2018 o 09:57 Piotr Padlewski <[hidden email]> napisał(a):


śr., 5 gru 2018 o 00:22 John McCall via cfe-dev <[hidden email]> napisał(a):

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.

The other reason why similar scheme doesn't work for !invariant.group is that we rely on a calls to launder/strip being present for some constructs to preserve
information about invartianess of an object (like in the example from RFC).

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.

John.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] RFC: Supported Optimizations attribute

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev

I can’t help but wonder if the back-and-forth here is largely about naming.

 

> 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

 

That sounds like a pretty reasonable burden to place on good-faith optimization authors, if I’m following correctly; “preserve semantics and well-formed IR structure” is something we already require of transformations to consider them correct, right?

 

I think that some of the points raised come from a more extreme version where “supported_optimizations” are allowed to invent wild new invariants.  I wonder if it would help to shift the naming from the optimizations to the annotations.  In particular, the annotations we’re concerned with have been embedded into the semantics of the program.  I.e., if I’m following correctly, in the case of the annotations for devirtualization, these launder/strip operations have been written into the value graph – so there’s not just a store of p anymore, there’s a store of (launder of p), something like that?  So I’m wondering if a name like “semantic_annotations” would help – this function’s semantics include some operations that are really no-op annotations (but any transform that blindly treats them as opaque operations will preserve them sufficiently for the intended consumer).  But if you merge such a function into one that hasn’t had the same class of annotations written into its semantics, you get a function that’s only partially annotated and we need to convey that to the ultimate consumer.

 

-Joseph

 

From: cfe-dev <[hidden email]> On Behalf Of John McCall via cfe-dev
Sent: Tuesday, December 4, 2018 6:22 PM
To: Philip Reames <[hidden email]>
Cc: llvm-dev <[hidden email]>; Sanjoy Das <[hidden email]>; Clang Dev <[hidden email]>; Richard Smith <[hidden email]>
Subject: Re: [cfe-dev] [llvm-dev] RFC: Supported Optimizations attribute

 

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.

John.


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Supported Optimizations attribute

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev
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.
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Supported Optimizations attribute

Peter Smith via llvm-dev

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.
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] [cfe-dev] RFC: Supported Optimizations attribute

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev


śr., 5 gru 2018 o 18:10 Philip Reames <[hidden email]> napisał(a):


On 12/5/18 12:57 AM, Piotr Padlewski wrote:


śr., 5 gru 2018 o 00:22 John McCall via cfe-dev <[hidden email]> napisał(a):

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.

The other reason why similar scheme doesn't work for !invariant.group is that we rely on a calls to launder/strip being present for some constructs to preserve
information about invartianess of an object (like in the example from RFC).

I'm really not sure I buy this.  You're effectively saying that you have two points which need to share a common root: 1) the "transition point" and 2) the invariant.group marker.  If it were possible to mark the transition point with a metadata node - is it? - the exact same rules as used for TBAA work just fine. 

p.s. It would help me a lot if you'd spell out specific examples of transition points.  I checked the RFC and don't see them.


As described in previous RFC: Devirtualization v2 , whenever we compare pointers to dynamic objects, we need to use firstly strip invariant.group information with @llvm.strip.invariant.group.
If we wouldn't do that, then comparison between pointers to same memory, one pointer carring old dynamic information (with invariant.group) with another carring new information could result in
transform that replaces uses of new pointer with old one, like in example below:

void bar() {
 A *a = new A;
 foo(a);
 A * b = new (a) B;
 if (a == b)
   b->foo();
}


Now imagine that this invalid comparison is done in a module that do not follow our rules, then if !invariant.group information would still be preserved after inlining such module, it would
result in transform that we would not like to happen.  This is shown in the example from current RFC

define void @with_devirtualization(i8* %p) supported_optimizations = "clang.cxx.devirtualization" {
 %v1 = load i8, i8* %p, !invariant.group !0
 %p2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
 call void @without_devirtualization(i8* %p, i8* %p2)
 %v2 = load i8, i8* %p2, !invariant.group !0
 ret void
}

define void @without_devirtualization(i8* %p, i8* %p2) {
  %b = icmp eq i8* %p, %p2
  call void @llvm.assume(i1 %b)
  ret void
}

!0 = !{!"clang.cxx.devirtualization"}
declare void @llvm.assume(i1)
declare i8* @llvm.launder.invariant.group.p0i8(i8*)


I hope my short explanation is good enough, you can find longer explanation in the previous RFC that I linked.
 

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.

John.

_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] RFC: Supported Optimizations attribute

Peter Smith via llvm-dev
In reply to this post by Peter Smith via llvm-dev
On Wed, Dec 5, 2018 at 11:19 AM Philip Reames <[hidden email]> wrote:

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.

That is precisely the situation prior to Piotr's proposal. In an annotated function, the absence of a call to an intrinsic permits optimizations to be performed. Eg:

// case 1
f(T *a, T *b) {
  if (a == b) g(a); // may be rewritten to g(b)
 g(b);
}
g(T *p) {
  h(*p);
}

// case 2
f(T *a, T *b) {
  if (strip(a) == strip(b)) g(a); // may not be rewritten to g(b)
  g(b);
}
g(T *p) {
  h(*invar(p));
}

And the LTO problem is that some combinations of the above, such as...

f(T *a, T *b) {
  if (a == b) g(a);
  g(b);
}
g(T *p) {
  h(*invar(p)); // two loads of the "same" p load the same value
}

would allow an incorrect optimization, eg to:

f(T *a, T *b) {
  if (a == b) { T v = *b; h(v); h(v); } // no reload here
  else { h(*b); }
}

I think Piotr's proposal does essentially what you're suggesting (and I think that's the point you're making, right?). The only reasonable place to attach the annotation in this case is the function, and the proposal is that we permit (interprocedural) optimizations only if all involved functions have the same annotation, which seems the direct analogue of requiring the same TBAA root node.

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.

Right. I don't see a reason why this couldn't be function metadata instead of a function attribute, except that it violates the usual metadata rules (specifically, interprocedural optimizations that involve the annotated function cannot simply ignore the annotation). [We don't need to drop the function metadata if any !invariant.group metadata is dropped (the latter is proper metadata, and can be blindly dropped with no adverse semantic effects). We would need to drop the function metadata if any of the intrinsic calls were dropped, but there's generally no expectation that you can arbitrarily remove intrinsic calls anyway.]

Given that IPO must respect this annotation (eg, it is not correct to inline a non-supported-optimization function into a supported-optimization function without removing the annotation from the caller), it seems to me that an attribute is a better match than metadata, but I'm not well-calibrated on such issues.
 
> 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.

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
12