[llvm-dev] Non-determinism in LLVM codegen

[Grang, Mandeep Singh via llvm-dev]

Thanks for the suggestions!

We can do this on LLVM_ENABLE_ABI_BREAKING_CHECKS but we would still need to provide the user the capability to toggle the behavior via flag, right?
Otherwise debugging issues would be difficult if reverse iteration cannot be turned ON/OFF dynamically.
  
< 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.

--Mandeep


On 11/15/2016 5:08 PM, Duncan P. N. Exon Smith wrote:
>> 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