llvm dev - Dec 2018 - [cfe-dev] RFC: Supported Optimizations attribute

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>

On Tue, Dec 4, 2018 at 12:04 PM Arthur O'Dwyer
<arthur.j.odwyer at gmail.com> wrote:
> 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.)
I think the overarching idea here is that good faith opts will only
rely on invariants that can only be broken by inter-procedural
optimizations.  So intra-procedural opts should not need any changes.

In a sense this proposal makes function call edges semantically
special; functions calls are no longer yet another kind of control
flow, but they can act as bridges between LLVM IR with different
semantics.  Collapsing a function call edge is now a semantically
interesting operation.

-- Sanjoy
>
> my $.02,
> –Arthur

On 4 Dec 2018, at 15:36, Sanjoy Das wrote:
> On Tue, Dec 4, 2018 at 12:04 PM Arthur O'Dwyer
> <arthur.j.odwyer at gmail.com> wrote:
>> 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.)
>
> I think the overarching idea here is that good faith opts will only
> rely on invariants that can only be broken by inter-procedural
> optimizations.  So intra-procedural opts should not need any changes.
>
> In a sense this proposal makes function call edges semantically
> special; functions calls are no longer yet another kind of control
> flow, but they can act as bridges between LLVM IR with different
> semantics.  Collapsing a function call edge is now a semantically
> interesting operation.
Note that this has always been true in some ways.  For example, naively
cloning call sites during inlining can change exception semantics; to
make this work correctly you have to reconcile the EH contexts of the
inner and outer calls, which is not always possible if the personalities
differ.  Or to pick an even grosser example, you can't just clone a call
to `llvm.returnaddress` during inlining.

Note also that IPO between functions with the same set of supported
optimizations also doesn't involve any change in semantics.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20181204/b27eb838/attachment.html>