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
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:
My point is that they are certainly welcome to try this path, but it's been
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
(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",
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
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
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
I don't think you can say such a pass is broken.
I kind of would say it's broken.
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?
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  code optimizes differently, to be a
bug. You should too!
should optimize the same as
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 , and if you want the output form to look the same,
that is a function of ordering output, not of "stopping passes from doing
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.
 For the purposes of this discussion, let's define this to mean the
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
should generate the same results as as textual input: