llvm dev - Dec 2018 - RFC: Supported Optimizations attribute

On Mon, Dec 3, 2018 at 11:49 PM John McCall <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?
> 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?

-- Sanjoy

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

On Tue, Dec 4, 2018 at 11:24 AM John McCall <jmccall at apple.com>
wrote:
>> 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.
I see.  Would it be correct to say that a good faith optimization `O`
assumes that a certain construct(s), `FOO`, does not occur in the
*trace* of the program within the function tagged with
supported_optimizations={O}?  Also `FOO` has to be side effecting so
LLVM cannot speculate it into existence (e.g. `FOO` can't be
"getelementptr with a certain property").

-- Sanjoy

On Tue, Dec 4, 2018 at 2:24 PM John McCall via cfe-dev <
cfe-dev at lists.llvm.org> 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 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.
>
> [...] 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.
>
Peanut gallery says: I don't fully understand the use-case or the domain,
but this description sounds unworkable to me.

AIUI, there are two players here: the "brittle optimization" (which
relies
on some invariant), and the "transform" (which has the power to break
that
invariant).

The only two mathematically workable scenarios are:
(A) The brittle optimization's invariant is "impossible to [break] for
standard semantic/structural reasons." Therefore no transform ever needs to
know anything about it. The result is a "robust" optimization, and no
need
for the supported-optimizations flagset.
(B) The brittle optimization's invariant is, in fact, brittle. Any
transform that doesn't explicitly preserve the invariant *can and will*
break the invariant. Therefore, every transform must have its own whitelist
of "invariants I know I don't break." Any flag in the
supported-optimizations flagset which is not whitelisted by a given
transform *must* be cleared when that transform is applied to the code.
(Because, by definition, a transform that doesn't explicitly preserve the
brittle invariant must be assumed to break it.)

my $.02,
–Arthur
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181204/5ec18259/attachment.html>

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>