Sanjoy Das via llvm-dev
2016-Feb-25 16:33 UTC
[llvm-dev] Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
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
Sanjoy Das via llvm-dev
2016-Feb-25 17:59 UTC
[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
Andy Ayers via llvm-dev
2016-Feb-25 19:27 UTC
[llvm-dev] 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
Duncan P. N. Exon Smith via llvm-dev
2016-Feb-26 02:35 UTC
[llvm-dev] Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
> On 2016-Feb-25, at 08:33, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: > > > 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.I'm pretty sure the `if (c)` is UB because it's branching on an uninitialized value, which could have a trap representation.> > -- Sanjoy
Sanjoy Das via llvm-dev
2016-Feb-26 04:11 UTC
[llvm-dev] Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
On Thu, Feb 25, 2016 at 6:35 PM, Duncan P. N. Exon Smith <dexonsmith at apple.com> wrote:>> // 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. > > I'm pretty sure the `if (c)` is UB because it's branching on an uninitialized > value, which could have a trap representation.I am *way* out of my depth here, but what if 'c' was an 'unsigned char' (and not an 'int')? Wouldn't that prevent UB, since it is escaped (cannot be a register variable), and is an 'unsigned char' (doesn't have a trap representation)? -- Sanjoy
Hal Finkel via llvm-dev
2016-Feb-27 02:10 UTC
[llvm-dev] Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
Hi Sanjoy, These are both very interesting examples, and demonstrate that the problems extends beyond function attributes (encompassing dead-argument elimination, etc.). I'm beginning to think that the best solution, at least when optimizing for speed, is the one that David Li suggested: we need to internalize functions that have been optimized in certain ways (e.g. instructions with potential side effects are removed). The trick here may be to be as intelligent about this as possible to minimize the effect on code size. Maybe this is as easy as checking whether isSafeToSpeculativelyExecute returns false on the deleted instruction? Perhaps when optimizing for size, we need to forbid such deletions. Thanks again, Hal ----- Original Message -----> From: "Sanjoy Das" <sanjoy at playingwithpointers.com> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "Chandler Carruth" <chandlerc at google.com>, "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 11:59:27 AM > 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 >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Sanjoy Das via llvm-dev
2016-Feb-27 03:08 UTC
[llvm-dev] Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
On Thu, Feb 25, 2016 at 9:59 AM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:> 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).^ This particular case above is already fixed in DeadArgElim: bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn) { // We cannot change the arguments if this TU does not define the function or // if the linker may choose a function body from another TU, even if the // nominal linkage indicates that other copies of the function have the same // semantics. In the below example, the dead load from %p may not have been // eliminated from the linker-chosen copy of f, so replacing %p with undef // in callers may introduce undefined behavior. // // define linkonce_odr void @f(i32* %p) { // %v = load i32 %p // ret void // } if (!Fn.isStrongDefinitionForLinker()) return false; -- Sanjoy
Possibly Parallel Threads
- Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
- Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
- Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
- Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")
- Possible soundness issue with available_externally (split from "RFC: Add guard intrinsics")