llvm dev - Feb 2016 - Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")

On Wed, Feb 24, 2016 at 11:18 PM Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "Chandler Carruth" <chandlerc at google.com>
> > To: "Sanjoy Das" <sanjoy at playingwithpointers.com>,
"Hal Finkel" <
> hfinkel at anl.gov>
> > Cc: "llvm-dev" <llvm-dev at lists.llvm.org>,
"Philip Reames" <
> listmail at philipreames.com>, "Duncan P. N. Exon Smith"
> > <dexonsmith at apple.com>
> > Sent: Thursday, February 25, 2016 12:40:53 AM
> > Subject: Re: [llvm-dev] Possible soundness issue with
> available_externally (split from "RFC: Add guard intrinsics")
> >
> >
> >
> >
> > On Wed, Feb 24, 2016 at 10:25 PM Sanjoy Das <
> > sanjoy at playingwithpointers.com > wrote:
> >
> >
> >
> > Hal Finkel wrote:
> >
> > > But it is not all optimizations that are the problem. Rather, it
> > > seems like a select few (e.g. things involving collapsing allowed
> > > non-determinism in atomics), and losing those optimizations seems
> > > better than generally losing function-attribute deduction.
> >
> > If we go by the langref, then optimizations that fold undef are also
> > problematic (though most C/C++ programs resulting in such IR would
> > have UB in practice).
> >
> >
> >
> > I'm also concerned about undef. It isn't clear that we can
reasonably
> > ensure that all things involving undef suitably stem from UB in the
> > face of speculation to preclude all "impossible" results
coming from
> > interposition.
> >
> >
> > I think trying to enumerate the function-local optimizations which
> > are unsafe is *much* more challenging than identifying the
> > interprocedural optimizations which are unsafe, which is essentially
> > what disabling function attribute deduction is doing.
> >
>
> It might be much more challenging, but let's try. This is not an issue
we
> need to fix by the end of the month, and the potential optimization
> regressions are significant. Our deductions of
> readonly/readnone/nocapture/etc. are really important for enabling other
> optimizations. Given that all of our C++ constructors, inline functions,
> etc. end up in comdat sections, this is really important.
>
Well, no one has really commented on my ideas to mitigate the issue.. I'm
actually much less concerned in the face of those ideas.

But given that we can't even formulate a good statement of what transforms
would necessarily have to be forbidden, I think we should get to a sound
state first, and then work on more aggressive models to use.

I think that coming up with something that is really sound is going to be
incredibly hard here because I think it will be tantamount to removing the
concept of undef entirely and the entire optimizer's reliance on it. And
most of the obvious ideas to replace it I think will have the same
challenges as undef.

We're also, meanwhile, going to have to dramatically curtail our
investigation of more exciting IPO opportunities because all of them bust
be carefully examined to not trigger these issues more directly.
> All of this makes me think we're just seeing the tip of the iceberg
> > of ways in which local optimizations can combine with attributes to
> > break this. =/ I really think the problem is as Richard describes
> > the interprocedural movement of information across a comdat-like
> > boundary where replacements may occur with differently transformed
> > code.
>
> Yes, but it is not *all* information that is relevant here.
>
True. It is any information which is not necessarily the same in all
(possibly transformed or untransformed) variants of the function.

My only confident summary of that is: "the information we can deduce prior
to any transformations". It sounds like you think we can effectively
preclude any such transformations on functions with ODR. I think that this
will end up being extraordinarily limiting if we can do it at all. It
certainly isn't the optimizer we have today, and would require changes all
over...

>  -Hal
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160225/42c4de60/attachment.html>

----- Original Message -----
> From: "Chandler Carruth" <chandlerc at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "Philip
Reames"
> <listmail at philipreames.com>, "Duncan P. N. Exon Smith"
> <dexonsmith at apple.com>, "Sanjoy Das"
> <sanjoy at playingwithpointers.com>
> Sent: Thursday, February 25, 2016 1:36:52 AM
> Subject: Re: [llvm-dev] Possible soundness issue with
> available_externally (split from "RFC: Add guard intrinsics")
> On Wed, Feb 24, 2016 at 11:18 PM Hal Finkel < hfinkel at anl.gov >
> wrote:
> > ----- Original Message -----
> 
> > > From: "Chandler Carruth" < chandlerc at google.com
>
> 
> > > To: "Sanjoy Das" < sanjoy at playingwithpointers.com
>, "Hal Finkel"
> > > <
> > > hfinkel at anl.gov >
> 
> > > Cc: "llvm-dev" < llvm-dev at lists.llvm.org >,
"Philip Reames" <
> > > listmail at philipreames.com >, "Duncan P. N. Exon
Smith"
> 
> > > < dexonsmith at apple.com >
> 
> > > Sent: Thursday, February 25, 2016 12:40:53 AM
> 
> > > Subject: Re: [llvm-dev] Possible soundness issue with
> > > available_externally (split from "RFC: Add guard
intrinsics")
> 
> > >
> 
> > >
> 
> > >
> 
> > >
> 
> > > On Wed, Feb 24, 2016 at 10:25 PM Sanjoy Das <
> 
> > > sanjoy at playingwithpointers.com > wrote:
> 
> > >
> 
> > >
> 
> > >
> 
> > > Hal Finkel wrote:
> 
> > >
> 
> > > > But it is not all optimizations that are the problem.
Rather,
> > > > it
> 
> > > > seems like a select few (e.g. things involving collapsing
> > > > allowed
> 
> > > > non-determinism in atomics), and losing those optimizations
> > > > seems
> 
> > > > better than generally losing function-attribute deduction.
> 
> > >
> 
> > > If we go by the langref, then optimizations that fold undef are
> > > also
> 
> > > problematic (though most C/C++ programs resulting in such IR
> > > would
> 
> > > have UB in practice).
> 
> > >
> 
> > >
> 
> > >
> 
> > > I'm also concerned about undef. It isn't clear that we
can
> > > reasonably
> 
> > > ensure that all things involving undef suitably stem from UB in
> > > the
> 
> > > face of speculation to preclude all "impossible"
results coming
> > > from
> 
> > > interposition.
> 
> > >
> 
> > >
> 
> > > I think trying to enumerate the function-local optimizations
> > > which
> 
> > > are unsafe is *much* more challenging than identifying the
> 
> > > interprocedural optimizations which are unsafe, which is
> > > essentially
> 
> > > what disabling function attribute deduction is doing.
> 
> > >
> 
> > It might be much more challenging, but let's try. This is not an
> > issue we need to fix by the end of the month, and the potential
> > optimization regressions are significant. Our deductions of
> > readonly/readnone/nocapture/etc. are really important for enabling
> > other optimizations. Given that all of our C++ constructors, inline
> > functions, etc. end up in comdat sections, this is really
> > important.
> 
> Well, no one has really commented on my ideas to mitigate the issue..
> I'm actually much less concerned in the face of those ideas.
I think that, should we need to go down that path, your plan is a good base.
I'm still not convinced that is necessary.
> But given that we can't even formulate a good statement of what
> transforms would necessarily have to be forbidden, I think we should
> get to a sound state first, and then work on more aggressive models
> to use.
Right, we've not done so in the last half day; I think the discussions on
this issue have been very productive, and the examples being discussed are
helping to frame what such a statement might contain. We should exhaust this
line of reasoning before making a decision.
> I think that coming up with something that is really sound is going
> to be incredibly hard here because I think it will be tantamount to
> removing the concept of undef entirely and the entire optimizer's
> reliance on it. And most of the obvious ideas to replace it I think
> will have the same challenges as undef.
I'll await an example here that does not rely on a safe-to-speculate
attribute that we don't yet have before drawing any conclusions.
> We're also, meanwhile, going to have to dramatically curtail our
> investigation of more exciting IPO opportunities because all of them
> bust be carefully examined to not trigger these issues more
> directly.
> > > All of this makes me think we're just seeing the tip of the
> > > iceberg
> 
> > > of ways in which local optimizations can combine with attributes
> > > to
> 
> > > break this. =/ I really think the problem is as Richard describes
> 
> > > the interprocedural movement of information across a comdat-like
> 
> > > boundary where replacements may occur with differently
> > > transformed
> 
> > > code.
> 
> > Yes, but it is not *all* information that is relevant here.
> 
> True. It is any information which is not necessarily the same in all
> (possibly transformed or untransformed) variants of the function.
> My only confident summary of that is: "the information we can deduce
> prior to any transformations". It sounds like you think we can
> effectively preclude any such transformations on functions with ODR.
> I think that this will end up being extraordinarily limiting if we
> can do it at all. It certainly isn't the optimizer we have today,
> and would require changes all over...
That summary needs unnecessarily broad. So far we've learned that: a) There
are issues with atomics b) there are issues with a safe-to-speculate attribute
we don't yet have c) there might be issues with folding undefs independent
of the previous two items, but we thus-far lack a concrete example. We don't
yet have enough information.

-Hal 
> > -Hal
> 
> > --
> 
> > Hal Finkel
> 
> > Assistant Computational Scientist
> 
> > Leadership Computing Facility
> 
> > Argonne National Laboratory
> 
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160225/a380409d/attachment-0001.html>

Hal Finkel wrote:
 > That summary needs unnecessarily broad. So far we've learned that: a)
There are issues with atomics b) there are issues
 > with a safe-to-speculate attribute we don't yet have c) there might be
issues with folding undefs independent of the
 > previous two items, but we thus-far lack a concrete example. We don't
yet have enough information.


I don't have a good example for (c), but if you go by the textbook "is
a non-deterministic value" definition for undef then

   void foo() available_externally {
     %x = create_undef();
     if (%x) print("X");
   }

is just as problematic as the two atomic loads case.  This isn't a
good example though, since we can specify as part of `undef` s
semantics: "if the program has different observable behavior based on
undef's non-determinism, then it is undefined".  However, if we do
that, we'll get stuck in cases like

   // In C
   void foo() {
     int c;
     if (c) print("X");
     escape(&c);  // escape is an empty function
   }

which I think is not UB in C (is it?), but will boil down to the kind
of IR above.

-- Sanjoy