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

A couple things I recall from implementing this in Phoenix:

For LTO -- do your comdat folding as part of the up-front symbol resolution
before invoking the backend (saves compile time too). Then have the linker
ensure that the comdat from the LTO bundle is the winner in the final link step.
That way during LTO you know which method body is going to be in the final
image. May not be as easy in LLVM if you can't merge all the LTO objs into a
single massive obj like we did.

For non-LTO compiles: block bottom-up propagation of facts that depend on
optimization levels -- eg register kills and parameter usage summaries. Allow
other IP information to flow upwards, since at least in our world all
comdat-foldable definitions are supposed to be "equivalent". Requires
some discipline so you are confident you know how information is derived.

We would also error out if foldable definitions did not appear to be equivalent.
I think we at least wrote the code to do some sanity checking. Maybe we never
turned this bit on.

We had real bugs reported before we fixed this properly. One annoying one was
that the comdat winner picked by the linker depended in part on the file path to
the obj, so if you linked the program in different directories, you'd get
different final binaries, and some of them would crash.

-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Sanjoy
Das via llvm-dev
Sent: Thursday, February 25, 2016 9:59 AM
To: Hal Finkel <hfinkel at anl.gov>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Possible soundness issue with available_externally
(split from "RFC: Add guard intrinsics")

Couple of other examples:

  void @foo(i32* %ptr) available_externally {
    %discard = load i32, i32* %ptr
  }
  void bar() {
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) available_externally {
  }
  void bar() {
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) available_externally {
  }
  void bar() {
    call @foo(i32* undef) ;; non optimized @foo will crash
  }

  ;; Similar example if @foo was dividing something by an integer
  ;; argument

We've actually seen the above in our VM (though back then we didn't
realize that the problem was more general than the one case above).

Another one involving `undef` (semantically same as "folding undef",
but different enough to state separately):

  void @foo(i32* %ptr) available_externally {
    store i32 undef, i32* %ptr
  }
  void bar() {
    %val = load i32, i32* %x
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) readonly available_externally {
  }
  void bar() {
    %val = load i32, i32* %x
    call @foo(i32* %x)
  }

==>

  void @foo(i32* %ptr) readonly available_externally {
  }
  void bar() {
    call @foo(i32* %x)
    %val = load i32, i32* %x
  }

With a non-optimized @foo, %val can be garbage.


I'll also note we've not really had bug reports (that I'm aware of)
around this issue.  Given that, it is possible that this is a purely theoretical
problem.

-- Sanjoy
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7candya%40microsoft.com%7cf0dc286d1dc04d5daf9408d33e0d7a98%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=ZK9BbJxV6%2bcAQn%2ftdy3%2b%2fHyOA7BR5QclvKO1egIap0w%3d

On Thu, Feb 25, 2016 at 11:27 AM, Andy Ayers <andya at microsoft.com>
wrote:
> For non-LTO compiles: block bottom-up propagation of facts that
> depend on optimization levels -- eg register kills and parameter usage
> summaries. Allow other IP information to flow upwards, since at least
> in our world all comdat-foldable definitions are supposed to be
> "equivalent". Requires some discipline so you are confident you
know
> how information is derived.
For Phoenix, what kinds of things constituted "other IP information"?

-- Sanjoy

I recall it was things we could deduce by scanning the method before we
optimized it, eg deduced noreturn/nothrow. I'd have to go check to be sure.

Once you allow inlining, you're pretty much telling your users they had
better give you compatible definitions.

We wanted to make sure that if users gave us compatible defs (mainly: same
source, but optimized in one CU and not in another), we wouldn't screw
things up.

-----Original Message-----
From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] 
Sent: Thursday, February 25, 2016 11:36 AM
To: Andy Ayers <andya at microsoft.com>
Cc: Hal Finkel <hfinkel at anl.gov>; llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Possible soundness issue with available_externally
(split from "RFC: Add guard intrinsics")

On Thu, Feb 25, 2016 at 11:27 AM, Andy Ayers <andya at microsoft.com>
wrote:
> For non-LTO compiles: block bottom-up propagation of facts that depend 
> on optimization levels -- eg register kills and parameter usage 
> summaries. Allow other IP information to flow upwards, since at least 
> in our world all comdat-foldable definitions are supposed to be 
> "equivalent". Requires some discipline so you are confident you
know
> how information is derived.
For Phoenix, what kinds of things constituted "other IP information"?

-- Sanjoy

On Thu, Feb 25, 2016 at 11:27 AM, Andy Ayers via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> A couple things I recall from implementing this in Phoenix:
>
> For LTO -- do your comdat folding as part of the up-front symbol
> resolution before invoking the backend (saves compile time too). Then have
> the linker ensure that the comdat from the LTO bundle is the winner in the
> final link step. That way during LTO you know which method body is going to
> be in the final image. May not be as easy in LLVM if you can't merge
all
> the LTO objs into a single massive obj like we did.
>
> For non-LTO compiles: block bottom-up propagation of facts that depend on
> optimization levels -- eg register kills and parameter usage summaries.
> Allow other IP information to flow upwards, since at least in our world all
> comdat-foldable definitions are supposed to be "equivalent".
Requires some
> discipline so you are confident you know how information is derived.
>
Functions which have gone through 'unsafe' transformations should be
'internalized'. Have you tried that approach?

thanks,

David

>
> We would also error out if foldable definitions did not appear to be
> equivalent. I think we at least wrote the code to do some sanity checking.
> Maybe we never turned this bit on.
>
> We had real bugs reported before we fixed this properly. One annoying one
> was that the comdat winner picked by the linker depended in part on the
> file path to the obj, so if you linked the program in different
> directories, you'd get different final binaries, and some of them would
> crash.
>
> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of
> Sanjoy Das via llvm-dev
> Sent: Thursday, February 25, 2016 9:59 AM
> To: Hal Finkel <hfinkel at anl.gov>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] Possible soundness issue with available_externally
> (split from "RFC: Add guard intrinsics")
>
> Couple of other examples:
>
>   void @foo(i32* %ptr) available_externally {
>     %discard = load i32, i32* %ptr
>   }
>   void bar() {
>     call @foo(i32* %x)
>   }
>
> ==>
>
>   void @foo(i32* %ptr) available_externally {
>   }
>   void bar() {
>     call @foo(i32* %x)
>   }
>
> ==>
>
>   void @foo(i32* %ptr) available_externally {
>   }
>   void bar() {
>     call @foo(i32* undef) ;; non optimized @foo will crash
>   }
>
>   ;; Similar example if @foo was dividing something by an integer
>   ;; argument
>
> We've actually seen the above in our VM (though back then we didn't
> realize that the problem was more general than the one case above).
>
> Another one involving `undef` (semantically same as "folding
undef", but
> different enough to state separately):
>
>   void @foo(i32* %ptr) available_externally {
>     store i32 undef, i32* %ptr
>   }
>   void bar() {
>     %val = load i32, i32* %x
>     call @foo(i32* %x)
>   }
>
> ==>
>
>   void @foo(i32* %ptr) readonly available_externally {
>   }
>   void bar() {
>     %val = load i32, i32* %x
>     call @foo(i32* %x)
>   }
>
> ==>
>
>   void @foo(i32* %ptr) readonly available_externally {
>   }
>   void bar() {
>     call @foo(i32* %x)
>     %val = load i32, i32* %x
>   }
>
> With a non-optimized @foo, %val can be garbage.
>
>
> I'll also note we've not really had bug reports (that I'm aware
of) around
> this issue.  Given that, it is possible that this is a purely theoretical
> problem.
>
> -- Sanjoy
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
>
>
https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2flists.llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev%0a&data=01%7c01%7candya%40microsoft.com%7cf0dc286d1dc04d5daf9408d33e0d7a98%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=ZK9BbJxV6%2bcAQn%2ftdy3%2b%2fHyOA7BR5QclvKO1egIap0w%3d
> _______________________________________________
> 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/20160225/666939fa/attachment.html>