[llvm-dev] Uncovering non-determinism in LLVM - The Next Steps

[Robinson, Paul via llvm-dev]

> -----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?

> 
> 2. With the toolchain built by the above buildbot we also want to run
> LNT tests and our entire internal testing suite. We then want to compare
> the objdump for every obj file against the obj file compiled by a
> forward/default iteration toolchain.

Sounds like a plan.

> We ideally want to compare rel vs
> rel+asserts vs debug with Linux vs Windows toolchains. Any differences
> in objdumps could signal a potential non-determinism.

You might want to do this part first, partly because you can do it
today with no further patches to LLVM.  I would not be surprised if
the set of differences between rel/rel+asserts was non-empty, as
(I think) +asserts enables some things that actually do different
computations, and not just add some internal-consistency checks.
Also doing this first would let you smoke out any infrastructure
issues in the mechanics of comparing the output of two different
compilers, without the complication of a (relatively) untried option.

My team has done something like your proposal, but comparing with/without 
-g and -S.  In those cases there are a number of innocuous differences 
that we have had to teach our comparison tool to ignore.  But we also 
found some real bugs and that was very satisfying.

When you start talking about Linux vs Windows, though... I assume you
mean comparing the output from different *hosts* but the same *target.*
Is LNT set up to do cross-compilation?  This is just my ignorance of 
LNT asking.

There might also be differences across hosts that you just have to live
with.  I remember a compiler that had different output depending on
whether it was a 32-bit or 64-bit host, because the constant folder
depended on host arithmetic.  (The compiled programs *worked* identically,
but the one compiled on a 32-bit host was a tiny bit less optimized.)
I don't know that LLVM has any issues like this, but it's something to 
be aware of.

> 
> 3. Currently reverse iteration is enabled only for SmallPtrSet. I am in
> the process of implementing it for more containers. I have already put
> up a patch for DenseMap: https://reviews.llvm.org/D35043
> 
> 4. Simply compiling with -mllvm -reverse-iterate will help us uncover
> non-determinism due to iteration order of containers. But once we have
> enabled reverse iteration for several containers then pinpointing the
> exact container causing the problem would be more tedious. So I propose
> to add an optional value field to this flag, like -mllvm
> -reverse-iterate=smallptrset -mllvm -reverse-iterate=densemap, etc.

Seems quite reasonable.

> 
> I would like to hear the community's thoughts on these proposals.

I think it's great.  There's the obvious potential for combinatoric
explosion of test runs you *could* compare, and I think some of the
other possibilities (+/-asserts, different hosts) are equally
interesting, but I'm really pleased to see this kind of creative
approach to testing.

Thanks!
--paulr

> 
> Thanks,
> Mandeep
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev