[llvm-dev] Non-determinism in LLVM codegen

[Daniel Berlin via llvm-dev]

On Tue, Nov 15, 2016 at 3:06 PM, Grang, Mandeep Singh via llvm-dev <
llvm-dev at lists.llvm.org> 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 <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
> <http://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 am reviewing the change you made, but i do not understand why it solves
the problem in MemorySSA, so i'm taking a deeper look.
I'll comment on the review

>
>
> 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/D26704>*
> *https://reviews.llvm.org/D26705 <https://reviews.llvm.org/D26705>*
> *https://reviews.llvm.org/D26706 <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
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161115/a6f30472/attachment.html>