[llvm-dev] Non-determinism in LLVM codegen

[Robinson, Paul via llvm-dev]

Do you have fixes for all of these problems ready to go?  If not, please make the flag off by default always.
You can put it back to default-on for Release+Asserts after all the problems are fixed.
Thanks,
--paulr

From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Grang, Mandeep Singh via llvm-dev
Sent: Tuesday, December 13, 2016 4:58 PM
To: llvm-dev at lists.llvm.org; zinob at codeaurora.org
Subject: Re: [llvm-dev] Non-determinism in LLVM codegen


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/20161214/f3f0a886/attachment.html>