[llvm-dev] Non-determinism in LLVM codegen

[Grang, Mandeep Singh via llvm-dev]

Everyone,

There is non-determinism in LLVM codegen in the following scenarios:

1. Between back-to-back runs of the same LLVM toolchain
2. Between Release vs Release+Asserts toolchains
3. Between Linux vs Windows toolchains

The main reasons for the non-determinism in codegen are:

1. Iteration of unordered containers (like SmallPtrSet, DenseMap, etc) 
where the iteration order is undefined
2. Use of non-stable sorts (like std:sort which uses quicksort) where 
the relative order of elements with the same key is undefined

I wanted a way to uncover instances where iteration of unordered 
containers results in different codegen.
So I have written the following patch:
*https://reviews.llvm.org/D26703*

Given a flag (-mllvm -reverse-iterate) this patch will enable iteration 
of SmallPtrSet in reverse order. The idea is to compile the same source 
with and without this flag and expect the code to not change.
If there is a difference in codegen then it would mean that the codegen 
is sensitive to the iteration order of SmallPtrSet.

I ran make check-all with and without my patch and I see the following 
additional failures due to iteration of SmallPtrSet in reverse order:
/    Clang :: Analysis/keychainAPI.m//
//    Clang :: Analysis/malloc.c//
//    Clang :: Rewriter/objc-modern-metadata-visibility.mm//
//    Clang :: SemaCXX/warn-loop-analysis.cpp//
//    LLVM :: Transforms/LoopVectorize/consecutive-ptr-uniforms.ll//
//    LLVM :: Transforms/SimplifyCFG/bug-25299.ll//
//    LLVM :: Transforms/Util/MemorySSA/cyclicphi.ll//
//    LLVM :: Transforms/Util/MemorySSA/many-dom-backedge.ll//
//    LLVM :: Transforms/Util/MemorySSA/many-doms.ll//
//    LLVM :: Transforms/Util/MemorySSA/phi-translation.ll/

I have posted the following patches which fix some of the above failures 
by changing SmallPtrSet to SmallSetVector:
*https://reviews.llvm.org/D26704**
**https://reviews.llvm.org/D26705**
**https://reviews.llvm.org/D26706*

Here are the next steps which I would like to do:
1. Replicate this patch for other containers (like DenseMap)
2. Somehow enable reverse iteration in the lit framework for all tests 
so that we can uncover these issues quickly

Please feel free to review my patch for reverse iteration. I would 
welcome comments/suggestions for improving/extending the patch and 
enabling it in lit.

Thanks,
Mandeep



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161115/7af827c4/attachment.html>