Daniel Berlin via llvm-dev
2017-Jul-06 20:08 UTC
[llvm-dev] Uncovering non-determinism in LLVM - The Next Steps
On Thu, Jul 6, 2017 at 12:34 PM, Sean Silva <chisophugis at gmail.com> wrote:> > > On Thu, Jul 6, 2017 at 10:20 AM, Daniel Berlin via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> >> >> On Thu, Jul 6, 2017 at 8:02 AM, Robinson, Paul via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> >>> >>> > -----Original Message----- >>> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of >>> > Grang, Mandeep Singh via llvm-dev >>> > Sent: Thursday, July 06, 2017 2:56 AM >>> > To: llvm-dev at lists.llvm.org >>> > Subject: [llvm-dev] Uncovering non-determinism in LLVM - The Next Steps >>> > >>> > Hi all, >>> > >>> > Last year I had shared with the community my findings about instances >>> of >>> > non-determinism in llvm codegen. The major source of which was the >>> > iteration of unordered containers resulting in non-deterministic >>> > iteration order. In order to uncover such instances we had introduced >>> > "reverse iteration" of unordered containers (currently only enabled for >>> > SmallPtrSet). >>> > I would now like to take this effort forward and propose to do the >>> > following: >>> > >>> > 1. We are in the process of setting up an internal nightly buildbot >>> > which would build llvm with the cmake flag - >>> > DLLVM_REVERSE_ITERATION:BOOL=ON. >>> > This will make all supported containers iterate in reverse order by >>> >>> I hope you mean all supported *unordered* containers here. :-) >>> >>> > default. We would then run "ninja check-all". Any failing unit test is >>> a >>> > sign of a potential non-determinism. >>> >>> When you did this with SmallPtrSet, were there tests that failed but >>> did not actually indicate non-determinism? >>> >> >> An example of this is the order of predecessors in the IR in phi nodes. >> There are passes that will create them in different orders depending on >> smallptrset iteration. >> This is "non-deterministic" in the sense that the textual form is >> different, but has the same semantic meaning either way. >> (Let's put aside the fact that allowing them to have a different order >> than the actual block predecessors is a pointless waste of time :P) >> >> Whether you consider this non-deterministic depends on your goal. >> >> I would argue that any pass that behaves differently given >> phi [[1, block 1], [2, block 2]] >> and >> phi [[2, block 2], [1, block 1]] >> >> is just flat out broken (and we have some that break due to poor design, >> etc) >> >> So i wouldn't consider the above to be non-deterministic in any >> meaningful sense, despite it outputting different textual form. >> > > One of our definitions of non-determinism is simply "output from command > line tools should always be bit identical given identical inputs", which is > suitable for content-based caching build systems like Bazel. >Just to point out: These systems already often have to ignore whitespace differences, etc. I'd also argue any of these content-based caching build systems is going to be rarely used if they require every single tool that uses them to produce bit identical output (IE boiling the ocean), as opposed to letting the tools define what identical means or something.> I don't know how our bitcode encoding compares to the textual IR in the > case of your phi example, but assuming that that difference makes it into > the bitcode too, it would cause e.g. ThinLTO bitcode artifacts to violate > the content-based caching assumptions, even if semantically to the compiler > the difference is immaterial. >You are certainly welcome to try to make all these things that are semantically identical try to be completely syntactically identical as well, but i'm pretty uninterested in slowing down or banning passes from doing certain things to do that. IE if you want this to happen, IMHO, this should be happening in output writing, not somewhere else. To give another example: Currently, IIRC, the order of basic blocks the function iterator goes through is "as they appear in input". There is no real defined or required ordering (IE it's not, for example, sorted in a preorder walk from the entry block or something) for correctness. I could make a pass that randomizes the list which for (auto &BB : F) walks, and nothing else in the compiler should change :) I don't think you can say such a pass is broken. Hence I think if you want such constraints, they need to be placed on output orderings, not on what passes do. I know that Richard has mentioned in the past at least for Clang the> intention is bit-identical output for bit-identical input. > > -- Sean Silva > > >> >> >> >> _______________________________________________ >> 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/20170706/6e1ebdb1/attachment.html>
Sean Silva via llvm-dev
2017-Jul-07 00:14 UTC
[llvm-dev] Uncovering non-determinism in LLVM - The Next Steps
On Thu, Jul 6, 2017 at 1:08 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> > > On Thu, Jul 6, 2017 at 12:34 PM, Sean Silva <chisophugis at gmail.com> wrote: > >> >> >> On Thu, Jul 6, 2017 at 10:20 AM, Daniel Berlin via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> >>> >>> On Thu, Jul 6, 2017 at 8:02 AM, Robinson, Paul via llvm-dev < >>> llvm-dev at lists.llvm.org> wrote: >>> >>>> >>>> >>>> > -----Original Message----- >>>> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of >>>> > Grang, Mandeep Singh via llvm-dev >>>> > Sent: Thursday, July 06, 2017 2:56 AM >>>> > To: llvm-dev at lists.llvm.org >>>> > Subject: [llvm-dev] Uncovering non-determinism in LLVM - The Next >>>> Steps >>>> > >>>> > Hi all, >>>> > >>>> > Last year I had shared with the community my findings about instances >>>> of >>>> > non-determinism in llvm codegen. The major source of which was the >>>> > iteration of unordered containers resulting in non-deterministic >>>> > iteration order. In order to uncover such instances we had introduced >>>> > "reverse iteration" of unordered containers (currently only enabled >>>> for >>>> > SmallPtrSet). >>>> > I would now like to take this effort forward and propose to do the >>>> > following: >>>> > >>>> > 1. We are in the process of setting up an internal nightly buildbot >>>> > which would build llvm with the cmake flag - >>>> > DLLVM_REVERSE_ITERATION:BOOL=ON. >>>> > This will make all supported containers iterate in reverse order by >>>> >>>> I hope you mean all supported *unordered* containers here. :-) >>>> >>>> > default. We would then run "ninja check-all". Any failing unit test >>>> is a >>>> > sign of a potential non-determinism. >>>> >>>> When you did this with SmallPtrSet, were there tests that failed but >>>> did not actually indicate non-determinism? >>>> >>> >>> An example of this is the order of predecessors in the IR in phi nodes. >>> There are passes that will create them in different orders depending on >>> smallptrset iteration. >>> This is "non-deterministic" in the sense that the textual form is >>> different, but has the same semantic meaning either way. >>> (Let's put aside the fact that allowing them to have a different order >>> than the actual block predecessors is a pointless waste of time :P) >>> >>> Whether you consider this non-deterministic depends on your goal. >>> >>> I would argue that any pass that behaves differently given >>> phi [[1, block 1], [2, block 2]] >>> and >>> phi [[2, block 2], [1, block 1]] >>> >>> is just flat out broken (and we have some that break due to poor design, >>> etc) >>> >>> So i wouldn't consider the above to be non-deterministic in any >>> meaningful sense, despite it outputting different textual form. >>> >> >> One of our definitions of non-determinism is simply "output from command >> line tools should always be bit identical given identical inputs", which is >> suitable for content-based caching build systems like Bazel. >> > Just to point out: These systems already often have to ignore whitespace > differences, etc. > > I'd also argue any of these content-based caching build systems is going > to be rarely used if they require every single tool that uses them to > produce bit identical output (IE boiling the ocean), as opposed to letting > the tools define what identical means or something. > > >> I don't know how our bitcode encoding compares to the textual IR in the >> case of your phi example, but assuming that that difference makes it into >> the bitcode too, it would cause e.g. ThinLTO bitcode artifacts to violate >> the content-based caching assumptions, even if semantically to the compiler >> the difference is immaterial. >> > > You are certainly welcome to try to make all these things that are > semantically identical try to be completely syntactically identical as > well, but i'm pretty uninterested in slowing down or banning passes from > doing certain things to do that. > > IE if you want this to happen, IMHO, this should be happening in output > writing, not somewhere else. > > To give another example: Currently, IIRC, the order of basic blocks the > function iterator goes through is "as they appear in input". > There is no real defined or required ordering (IE it's not, for example, > sorted in a preorder walk from the entry block or something) for > correctness. > > I could make a pass that randomizes the list which for (auto &BB : F) > walks, and nothing else in the compiler should change :) > > I don't think you can say such a pass is broken. > > Hence I think if you want such constraints, they need to be placed on > output orderings, not on what passes do. >Yeah, I agree it is mostly (if not entirely) an output canonicalization issue in these cases. -- Sean Silva> > I know that Richard has mentioned in the past at least for Clang the >> intention is bit-identical output for bit-identical input. >> >> -- Sean Silva >> >> >>> >>> >>> >>> _______________________________________________ >>> 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/20170706/4f5e99f5/attachment.html>
David Blaikie via llvm-dev
2017-Jul-07 16:01 UTC
[llvm-dev] Uncovering non-determinism in LLVM - The Next Steps
On Thu, Jul 6, 2017 at 1:08 PM Daniel Berlin via llvm-dev < llvm-dev at lists.llvm.org> wrote:> On Thu, Jul 6, 2017 at 12:34 PM, Sean Silva <chisophugis at gmail.com> wrote: > >> >> >> On Thu, Jul 6, 2017 at 10:20 AM, Daniel Berlin via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> >>> >>> On Thu, Jul 6, 2017 at 8:02 AM, Robinson, Paul via llvm-dev < >>> llvm-dev at lists.llvm.org> wrote: >>> >>>> >>>> >>>> > -----Original Message----- >>>> > From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of >>>> > Grang, Mandeep Singh via llvm-dev >>>> > Sent: Thursday, July 06, 2017 2:56 AM >>>> > To: llvm-dev at lists.llvm.org >>>> > Subject: [llvm-dev] Uncovering non-determinism in LLVM - The Next >>>> Steps >>>> > >>>> > Hi all, >>>> > >>>> > Last year I had shared with the community my findings about instances >>>> of >>>> > non-determinism in llvm codegen. The major source of which was the >>>> > iteration of unordered containers resulting in non-deterministic >>>> > iteration order. In order to uncover such instances we had introduced >>>> > "reverse iteration" of unordered containers (currently only enabled >>>> for >>>> > SmallPtrSet). >>>> > I would now like to take this effort forward and propose to do the >>>> > following: >>>> > >>>> > 1. We are in the process of setting up an internal nightly buildbot >>>> > which would build llvm with the cmake flag - >>>> > DLLVM_REVERSE_ITERATION:BOOL=ON. >>>> > This will make all supported containers iterate in reverse order by >>>> >>>> I hope you mean all supported *unordered* containers here. :-) >>>> >>>> > default. We would then run "ninja check-all". Any failing unit test >>>> is a >>>> > sign of a potential non-determinism. >>>> >>>> When you did this with SmallPtrSet, were there tests that failed but >>>> did not actually indicate non-determinism? >>>> >>> >>> An example of this is the order of predecessors in the IR in phi nodes. >>> There are passes that will create them in different orders depending on >>> smallptrset iteration. >>> This is "non-deterministic" in the sense that the textual form is >>> different, but has the same semantic meaning either way. >>> (Let's put aside the fact that allowing them to have a different order >>> than the actual block predecessors is a pointless waste of time :P) >>> >>> Whether you consider this non-deterministic depends on your goal. >>> >>> I would argue that any pass that behaves differently given >>> phi [[1, block 1], [2, block 2]] >>> and >>> phi [[2, block 2], [1, block 1]] >>> >>> is just flat out broken (and we have some that break due to poor design, >>> etc) >>> >>> So i wouldn't consider the above to be non-deterministic in any >>> meaningful sense, despite it outputting different textual form. >>> >> >> One of our definitions of non-determinism is simply "output from command >> line tools should always be bit identical given identical inputs", which is >> suitable for content-based caching build systems like Bazel. >> > Just to point out: These systems already often have to ignore whitespace > differences, etc. > > I'd also argue any of these content-based caching build systems is going > to be rarely used if they require every single tool that uses them to > produce bit identical output (IE boiling the ocean), as opposed to letting > the tools define what identical means or something. >This seems inconsistent with my understanding of LLVM's (& Google's, re: Bazel) goals.. So far as I know, LLVM has fixed pretty much any "the same input causes different output bits, even if they're semantically equivalent" bug that's reported (well, they're considered bugs at least - sometimes takes a while for someone to prioritize them) While it doesn't outright break Bazel when that property doesn't hold, I believe it can cause more cache invalidation than is ideal (eg: build system evicts an object file from the cache, but still has the resulting executable in the cache - to do the link step it goes to rebuild the objects*, finds a new/different object and then reruns the link because of it) Also for LLVM testing purposes, I believe any case where the output text/bits are different are usually fixed so the tests are reliable. * maybe this scenario doesn't really happen - if Bazel assumes reproducibility is transitive, it could observe that the input hashes are the same so it doesn't need to run the task at all if all the other object files are available - could just assume the resulting binary would be the same as the one it already has> > >> I don't know how our bitcode encoding compares to the textual IR in the >> case of your phi example, but assuming that that difference makes it into >> the bitcode too, it would cause e.g. ThinLTO bitcode artifacts to violate >> the content-based caching assumptions, even if semantically to the compiler >> the difference is immaterial. >> > > You are certainly welcome to try to make all these things that are > semantically identical try to be completely syntactically identical as > well, but i'm pretty uninterested in slowing down or banning passes from > doing certain things to do that. > > IE if you want this to happen, IMHO, this should be happening in output > writing, not somewhere else. > > To give another example: Currently, IIRC, the order of basic blocks the > function iterator goes through is "as they appear in input". > There is no real defined or required ordering (IE it's not, for example, > sorted in a preorder walk from the entry block or something) for > correctness. > > I could make a pass that randomizes the list which for (auto &BB : F) > walks, and nothing else in the compiler should change :) >No optimizations should change, but I think it'd be pretty difficult to support testing that pass (granted with LLVM's testing approach, at least that would be fairly isolated to only the tests for the pass - it wouldn't pollute other pass tests with nondeterminism of output, so might not be too painful)> I don't think you can say such a pass is broken. >I kind of would say it's broken. Arbitrarily reordering, I'd be OK with, nondeterministically reordering would seem not OK to me (again, based on the sentiments I've heard expressed from Chandler and others (though I may've misunderstood/may be incorrectly representing their perspective) on the project/my best understanding of the goals, etc - and I tend to agree with them, but could well be wrong)> Hence I think if you want such constraints, they need to be placed on > output orderings, not on what passes do. >Ah, hmm, maybe there's a point of confusion. Changing the order of BBs in a Function would change the output ordering, right? Presumably that would be reflected in printed IR, bitcode, and possibly in block layout (at least at -O0, but I could imagine some aspects of that ordering leak out even when LLVM does advanced block layout optimizations).> > I know that Richard has mentioned in the past at least for Clang the >> intention is bit-identical output for bit-identical input. >> >> -- Sean Silva >> >> >>> >>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> 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 > 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/20170707/c2517f18/attachment.html>
Daniel Berlin via llvm-dev
2017-Jul-07 16:58 UTC
[llvm-dev] Uncovering non-determinism in LLVM - The Next Steps
> > >>> >>> One of our definitions of non-determinism is simply "output from command >>> line tools should always be bit identical given identical inputs", which is >>> suitable for content-based caching build systems like Bazel. >>> >> Just to point out: These systems already often have to ignore whitespace >> differences, etc. >> >> I'd also argue any of these content-based caching build systems is going >> to be rarely used if they require every single tool that uses them to >> produce bit identical output (IE boiling the ocean), as opposed to letting >> the tools define what identical means or something. >> > > This seems inconsistent with my understanding of LLVM's (& Google's, re: > Bazel) goals.. >My point is that they are certainly welcome to try this path, but it's been tried before. There are reasons ccache, et al have various "slop" modes. I suspect, but can't prove, a system that is so rigid will not be adopted in practice. (So far: Only one major player has done so, and did so by fiat!)> > So far as I know, LLVM has fixed pretty much any "the same input causes > different output bits, even if they're semantically equivalent" bug that's > reported (well, they're considered bugs at least - sometimes takes a while > for someone to prioritize them) >Which, again, i'm fine with as long as we don't muck up passes a ton to do it. I'd rather design them properly and fix things like "random limits", etc.> > While it doesn't outright break Bazel when that property doesn't hold, I > believe it can cause more cache invalidation than is ideal (eg: build > system evicts an object file from the cache, but still has the resulting > executable in the cache - to do the link step it goes to rebuild the > objects*, finds a new/different object and then reruns the link because of > it) > > Also for LLVM testing purposes, I believe any case where the output > text/bits are different are usually fixed so the tests are reliable. >FWIW: In the cases i cited the tests can already be made reliable in the face of these differences :)> > * maybe this scenario doesn't really happen - if Bazel assumes > reproducibility is transitive, it could observe that the input hashes are > the same so it doesn't need to run the task at all if all the other object > files are available - could just assume the resulting binary would be the > same as the one it already has >Right. This is definitely faster :)> No optimizations should change, but I think it'd be pretty difficult to > support testing that pass (granted with LLVM's testing approach, at least > that would be fairly isolated to only the tests for the pass - it wouldn't > pollute other pass tests with nondeterminism of output, so might not be too > painful) > > >> I don't think you can say such a pass is broken. >> > > I kind of would say it's broken. >Why? It makes literally no semantic change to the code that is incorrect. This is precisely why my view is that if you want *output* to look a certain way, you need to cause the *output emission* to handle that.> Arbitrarily reordering, I'd be OK with, nondeterministically reordering > would seem not OK to me (again, based on the sentiments I've heard > expressed from Chandler and others (though I may've misunderstood/may be > incorrectly representing their perspective) on the project/my best > understanding of the goals, etc - and I tend to agree with them, but could > well be wrong) >> > >> Hence I think if you want such constraints, they need to be placed on >> output orderings, not on what passes do. >> > > Ah, hmm, maybe there's a point of confusion. Changing the order of BBs in > a Function would change the output ordering, right? >Yes> Presumably that would be reflected in printed IR, bitcode, and possibly in > block layout (at least at -O0, but I could imagine some aspects of that > ordering leak out even when LLVM does advanced block layout optimizations). >Again, any ordering changes that cause optimization differences are clear bugs in the pass. Yes, i know that this means we have a lot of bugs :) I consider any case where, due to a limit, identical [1] code optimizes differently, to be a bug. You should too! block1: foo block2: bar should optimize the same as block2: bar block1: foo Let me try to put this another way: My argument is precisely that code that is literally identical (but subject to expression in multiple textual forms) should be optimized the same way, and that's the avoidance of non-determinism you should shoot for, *not* the simple subset of "same crap in, same crap out" :P. This form does *not* preclude the output form from being different for things that meet [1], and if you want the output form to look the same, that is a function of ordering output, not of "stopping passes from doing things": If you aren't ordering output, and just try to get the "same crap in produces same crap out" form of non-determinism, you are going to get screwed by all the random limits, etc, anyway as you improve the passes in that you will have gratuitous, but deterministic, output change, and probably some non-determinism anyway. [1] For the purposes of this discussion, let's define this to mean the following: Code that is subject to multiple textual forms that have precisely the same meaning to llvm, but generate different orderings in our containers/output: IE textual input block1: foo block2: bar should generate the same results as as textual input: block2: bar block1: foo -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170707/e296398c/attachment.html>