[llvm-dev] Non-determinism in LLVM codegen

[Hal Finkel via llvm-dev]

----- 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.

 -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