[llvm-dev] Non-determinism in LLVM codegen

[Grang, Mandeep Singh via llvm-dev]

Everyone,

The following patch to reverse iterate SmallPtrSet's has now been merged:
https://reviews.llvm.org/D26718

This is how LLVM behavior will change due to this patch:
- In LLVM builds with *assertions enabled*, SmallPtrSet's would always 
be reverse iterated by default.
   This default behavior can be overridden via the flag "-mllvm 
-reverse-iterate=<true/false>".

- In LLVM builds with *assertions disabled*, SmallPtrSet's would 
continue to be always forward iterated.
   This behavior cannot be overridden as the above flag is available 
only in builds with assertions enabled.

Currently, the following unit tests are failing in Release+Asserts mode 
due to the difference in SmallPtrSet iteration order:
     Clang :: Analysis/keychainAPI.m
     Clang :: Analysis/malloc.c
     Clang :: Rewriter/objc-modern-metadata-visibility.mm
     Clang :: SemaCXX/warn-loop-analysis.cpp
     LLVM :: Transforms/SimplifyCFG/bug-25299.ll

Next Steps:
I plan to extend this behavior to the iteration of other unordered 
containers (like DenseMap, etc).

Thanks,
Mandeep

On 11/15/2016 3:06 PM, Grang, Mandeep Singh wrote:
> 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/20161213/edcc2255/attachment.html>