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

Wed Feb 24 20:52:08 PST 2016

Sent from my Verizon Wireless 4G LTE DROID
On Feb 24, 2016 9:33 PM, Richard Smith via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
>
> On Wed, Feb 24, 2016 at 7:17 PM, Chandler Carruth via llvm-dev
> <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
> > On Wed, Feb 24, 2016 at 7:10 PM Sanjoy Das via llvm-dev
> > <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
> >>
> >> On Wed, Feb 24, 2016 at 6:51 PM, Duncan P. N. Exon Smith
> >> <dexonsmith at apple.com<mailto:dexonsmith at apple.com>> wrote:
> >> >> If we do not inline @foo(), and instead re-link the call site in @main
> >> >> to some non-optimized copy (or differently optimized copy) of @foo,
> >> >> then it is possible for the program to have the behavior {print("Y");
> >> >> print ("X")}, which was disallowed in the earlier program.
> >> >>
> >> >> In other words, opt refined the semantics of @foo() (i.e. reduced the
> >> >> set of behaviors it may have) in ways that would make later
> >> >> optimizations invalid if we de-refine the implementation of @foo().
> >> >
> >> > I'm probably missing something obvious here.  How could the result of
> >> > `%t0 != %t1` be different at optimization time in one file than from
> >> > runtime in the "real" implementation?  Doesn't this make the CSE
> >> > invalid?
> >>
> >> `%t0` and `%t1` are "allowed" to "always be the same", i.e. an
> >> implementation of @foo that always feeds in the same
> >> value for `%t0` and `%t1` is a valid implementation (which is why the
> >> CSE was valid); but it is not the *only* valid implementation.  If I
> >> don't CSE the two load instructions (also a valid thing to do), and
> >> this is a second thread writing to `%par`, then the two values loaded
> >> can be different, and you could end up printing `"X"` in `@foo`.
> >>
> >> Did that make sense?
> >>
> >> > Does linkonce_odr linkage have the same problem?
> >> > - If so, do you want to change it too?
> >> > - Else, why not?
> >>
> >> Going by the specification in the LangRef, I'd say it depends on how
> >> you define "definitive".  If you're allowed to replace the body of a
> >> function with a differently optimized body, then the above problem
> >> exists.
> >
> >
> > I believe that is the case, and I strongly believe the problem you outline
> > exists for linkonce_odr exactly as it does for available_externally.
> >
> > Which is what makes this scary: every C++ inline function today can trigger
> > this.
>
> More generally, the same problem applies to all entities within
> comdats (we can view available_externally and linkonce_odr as special
> cases of single-symbol comdats). Similar problems show up with static
> local variables in inline functions (where the comdats may be
> equivalent across object files, but aren't necessarily identical -- in
> particular, one can use constant initialization for a static local
> variable where the other uses dynamic initialization, and inlining the
> one with constant initialization then selecting the one with dynamic
> initialization results in the variable not being initialized).

Is this initialization choice currently a choice we make in the backend or the frontend?

-Hal

>
> One approach that appears superficially correct would be to say that
> we cannot move information across a comdat / available_externally /
> linkonce_odr boundary unless doing so allows us to completely remove
> that reference to the comdat / function / global. (In particular, you
> can't use the attrs on a function in a comdat from outside that comdat
> -- unless you somehow know they're present for all versions of that
> comdat.) But that seems to have a pretty huge impact on optimizability
> of comdats.
>
> >> >> The above example is clearly fabricated, but such cases can come up
> >> >> even if everything is optimized to the same level.  E.g. one of the
> >> >> atomic loads in the unrefined implementation of @foo() could have been
> >> >> hidden behind a function call, whose body existed in only one module.
> >> >> That module would then be able to refine @foo() to `ret void` but
> >> >> other modules won't.
> >> >>
> >> >> The only solution I can think of is to redefine available_externally
> >> >> to mean "the only kind of IPO/IPA you can do over a call to this
> >> >> function is to inline it".  Redefining available_externally this way
> >> >> will also let us soundly use it to represent calls to functions that
> >> >> have guard intrinsics, since a failed guard intrinsic basically
> >> >> replaces the function with a "very de-refined" implementation (the
> >> >> interpreter).
> >> >>
> >> >> What do you think?  I don't think implementing the above above will be
> >> >> very difficult, but needless to say, it will still be a fairly
> >> >> non-trivial semantic change (hence I'm not directly jumping to
> >> >> implementation).
> >> >
> >> > This linkage is used in three places (that I know of) by clang:
> >> >
> >> >   1. C-style `inline` functions.
> >> >   2. Functions defined in C++ template classes with external explicit
> >> >      instantiations, e.g. S::foo() in:
> >> >
> >> >          template <class T> struct S { void foo() {} };
> >> >          void bar() { S<int>().foo(); }
> >> >          extern template struct S<int>;
> >> >
> >> >   3. -flto=thin cross-module function importing.
> >> >
> >> > (No comment on (1); its exact semantics are a little fuzzy to me.)
> >> > For (2) and (3), the current behaviour seems correct, and I'd be
> >> > hesitant to lose optimizing power.  (2) is under the "ODR" rule, and
> >> > I think we've been applying the same logic to (3).  Unless, are you
> >> > saying ODR isn't enough?
> >>
> >> By ODR, do you mean you only have one definition of the function in
> >> the whole link (i.e. across all modules you'll link together)?
> >> Then yes, ODR should be enough to avoid this.  But in any place where
> >> the linker sees two differently optimized definitions for a function
> >> and picks one as the definitive version all non-inlined calls link to,
> >> we have this problem.
> >
> >
> > No, different levels of optimization must be allowed within ODR. So this is
> > a problem within an ODR context.
> >
> > (The term ODR applies to one *source* definition, not one optimized
> > definition)
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org<mailto: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/20160225/8e38119e/attachment-0001.html>