[llvm-dev] Non-determinism in LLVM codegen

[Duncan P. N. Exon Smith via llvm-dev]

> On 2016-Nov-15, at 15:16, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> ----- Original Message -----
>> From: "Mandeep Singh via llvm-dev Grang" <llvm-dev at lists.llvm.org>
>> To: llvm-dev at lists.llvm.org, "mehdi amini" <mehdi.amini at apple.com>, dexonsmith at apple.com, zinob at codeaurora.org
>> Sent: Tuesday, November 15, 2016 5:06:29 PM
>> Subject: [llvm-dev] Non-determinism in LLVM codegen
>> 
>> 
>> 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
> 
> Great, thanks for working on this! Unfortunately, you did not subscribe llvm-commits when you created these, so the list did not receive the customary notification. Please re-post these subscribing llvm-commits so that we all get the notification.
> 
>> 
>> 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
> 
> I'm not sure there is a good way of doing this, but we could certainly have a build mode which does this (and a buildbot running with that mode). I suspect we don't want to do this based on NDEBUG anyway to avoid ODR problems from external client code.

It would be possible to base this on LLVM_ENABLE_ABI_BREAKING_CHECKS instead of NDEBUG (there's a CMake option to control this).
- Asserts builds -DLLVM_ENABLE_ABI_BREAKING_CHECKS by default.
- No-asserts builds -ULLVM_ENABLE_ABI_BREAKING_CHECKS by default.
- Clients that mix-and-match Asserts/No-asserts can pick one or the other.

> 
> -Hal
> 
>> 
>> 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
>> 
> 
> -- 
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory