[llvm-dev] Non-determinism in LLVM codegen

Thu Nov 17 11:14:42 PST 2016

Assuming that we get an option toggleable from clang (via an -mllvm flag or
however), we could also consider adding a new check to
clang/utils/check_cfc for this.  At Sony we've been using it very
successfully to find codegen differences between -g and non-g builds using
the 'dash_g_no_change' check.  Essentially put it on your path in place of
the clang/clang++ executables and build test-suite/chromium/your project of
choice as per normal.  Underneath it will build it in both modes and fail
the compile if the resulting codegen they produce differs from each other.

See:
http://llvm.org/devmtg/2015-04/slides/Verifying_code_gen_dash_g_final.pdf

-Greg

On 17 November 2016 at 01:56, Grang, Mandeep Singh via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> 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
>>>
>>
> _______________________________________________
> 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/20161117/9f231c5a/attachment.html>