[llvm-dev] RFC: Supported Optimizations attribute

[John McCall via llvm-dev]

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>