Non-determinism in the LLVM compiler

Grang, Mandeep Singh mgrang at
Fri Oct 20 20:42:10 UTC 2017


I contribute to the LLVM compiler ( and my recent work 
has been to uncover and fix instances of *non-determinism in LLVM*.

I recently presented a poster titled /"Non-determinism in LLVM Code 
Generation"/ at this year's LLVM Dev Meet: 

It would be great to know if my work is of interest to the reproducible 
builds community and if someone has already done/doing something similar.

Here is an abstract of my work:

/The code generation phase in LLVM suffers from the problem of 
non-determinism. This means that the same input program might have 
different object code generated depending on the way the LLVM toolchain 
was built. We might get different output between release only and 
release plus asserts builds, between a Windows and a Linux build or even 
different back-to-back runs of the same toolchain./


/While the generated code might not necessarily be “wrong code”, this 
non-determinism might result in unexpected runtime crashes or simply 
hard to reproduce bugs on the customer side making it harder to debug 
and fix./


/A common cause of non-determinism is the iteration of unordered 
containers in LLVM. Many such cases of non-deterministic behavior can be 
uncovered by forcing reverse iteration of these unordered containers and 
checking if the generated code changes. Reverse iteration simply means 
reversing the direction of iteration of a container. It is transparent 
to the user and comes with almost zero runtime cost./


/Our reverse iteration technique is currently implemented for 
SmallPtrSet, DenseMap and DenseSet and it already uncovers problems that 
resulted in the failure of several test cases in LLVM. We plan to extend 
this work by including more containers in the test and providing further 



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Reproducible-builds mailing list