llvm dev - Dec 2018 - RFC: Supported Optimizations attribute

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?

On 12/4/18 11:24 AM, John McCall via llvm-dev wrote:
>
> On 4 Dec 2018, at 13:16, Sanjoy Das wrote:
>
>     On Mon, Dec 3, 2018 at 11:49 PM John McCall jmccall at apple.com
>     <mailto:jmccall at apple.com> wrote:
>
>         Piotr's proposal unfortunately doesn't give us a good name
for
>         the class
>         of optimizations that require being listed in
>         supported_optimizations.
>         In earlier discussions I called them "brittle", but I can
>         understand why
>         nobody wants to call their optimization that, so let's call
them
>         "good-faith optimizations" instead since they rely on the
good
>         faith of
>         all the participating code.
>
>         Every optimization has to know how to maintain the structural
>         rules of
>         LLVM IR; that's what makes them structural rules. We don't
>         want the set of
>         structural rules to substantially change because such-and-such
>         good-faith
>         optimization is in effect because that would require arbitrary
>         transforms
>         to check the supported_optimizations list before they knew
>         which rules to
>         follow. Instead, the burden is on the optimization designer to
>         pick IR
>         constructs that won't be messed up by an arbitrary transform
>         with no special
>         knowledge of the optimization. The only thing the optimization
>         designer
>         can rely on is this:
>
>         other transforms will preserve the apparent semantics of the
>         function and
>         other transforms will maintain the standard structural rules
>         of LLVM IR.
>
>     Ok. Just to make sure we're on the same page, if this was all there
>     is we would not need this attribute right? All LLVM optimizations do
>     need to preserve semantics and structural properties anyway?
>
> We need this attribute because interprocedural optimizations otherwise
> break good-faith optimizations, so yes, my suummary here is missing some
> qualification (that I included in the next paragraph, but with a slightly
> different spin). So let me restate this.
>
> The designer of a good-faith optimization can rely on this:
>
>   * other transforms will preserve the apparent semantics of the function,
>   * other transforms will maintain the standard structural rules of
>     LLVM IR, and
>   * interprocedural transforms will honor supported_optimizations as
>     mentioned in Piotr's proposal --- and, in particular, will
>     intersect the supported_optimizations list whenever moving code
>     into a function.
>
> 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.
>
>         So the defining property of a good-faith optimization is that:
>         - there are rules which participating functions are expected
>         to follow on
>         pain of undefined behavior but which LLVM IR doesn't require
>         every function
>         to follow, and
>         - those rules will be preserved by any transform that doesn't
>         move code
>         between functions and which preserves the apparent function
>         semantics
>         and maintains the standard structural rules of LLVM IR.
>
>     In other words, certain things are UB in functions tagged with
>     supported_optimizations that are not UB otherwise? This breaks code
>     hoisting transformations right? I.e.
>     isSafeToSpeculativelyExecute(Inst) will have to return false if Inst
>     is in a function with a non-empty supported_optimizations?
>
> Good question. I would consider that to be an unacceptable intrusion:
> intraprocedural transforms should never have to be aware of
> supported_optimizations (unless they're implementing a good-faith
> optimization, of course) and interprocedural transforms should only have
> to be aware of supported_optimizations in the narrow sense outlined
> by Piotr. If something about the optimization's representation in IR
> is unsafe to speculate, it should be made impossible to speculate for
> standard semantic/structural reasons, like having apparently arbitrary
> side-effects.
>
> I think the right way to formalize this is to say that, while the
> good-faith optimization may impose additional UB rules on the function,
> it must guarantee that transforms that are well-behaved as described
> above --- i.e. that preserve standard structure and semantics and which,
> if interprocedural, appropriately honor supported_optimizations --- will
> never introduce new UB.
>
> John.
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181204/9d9fb51c/attachment.html>

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

śr., 5 gru 2018 o 00:22 John McCall via cfe-dev <cfe-dev at
lists.llvm.org>
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
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181205/92190366/attachment.html>

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>

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 <cfe-dev-bounces at lists.llvm.org> On Behalf Of John McCall
via cfe-dev
Sent: Tuesday, December 4, 2018 6:22 PM
To: Philip Reames <listmail at philipreames.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>; Sanjoy Das <sanjoy at
playingwithpointers.com>; Clang Dev <cfe-dev at lists.llvm.org>;
Richard Smith <RichardSmith at google.com>
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181205/cee712b3/attachment-0001.html>