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:

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:

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

From: "Mandeep Singh via llvm-dev Grang" <llvm-dev@lists.llvm.org>
To: llvm-dev@lists.llvm.org, "mehdi amini" <mehdi.amini@apple.com>, dexonsmith@apple.com, zinob@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

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
<http://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 am reviewing the change you made, but i do not understand why it solves
the problem in MemorySSA, so i'm taking a deeper look.
I'll comment on the review

From: "Mandeep Singh via llvm-dev Grang" <llvm-dev@lists.llvm.org>
To: llvm-dev@lists.llvm.org, "mehdi amini" <mehdi.amini@apple.com>, dexonsmith@apple.com, zinob@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.

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.

This is really cool!

Another potential source for non-determinism is undefined behavior. In a Debug LLVM from last night I got 22 unexpected failures when testing under Valgrind.

John

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.

This is really cool!

Another potential source for non-determinism is undefined behavior. In
a Debug LLVM from last night I got 22 unexpected failures when testing
under Valgrind.

Would be interesting to see, for those failures, whether the sanitizers can catch them, and if not, why.

Jon

Would be interesting to see, for those failures, whether the sanitizers
can catch them, and if not, why.

Yeah, I only used valgrind because lit is already setup to use it.

There seemed to be a variety of problems, once I get past a deadline or two I'll dig in and try to figure out what's going wrong.

John

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

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

Everyone,

The following patch to reverse iterate SmallPtrSet’s has now been merged:

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

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

Wait, so you committed a patch that breaks these tests? Should you fix
them first?

IIUC, LLVM_ABI_BREAKING_CHECKS is WITH_ASSERTS by default, so your
change, which is known to break things, is enabled for those of us
enabling asserts?

Or am I misunderstanding?

Looks like Mehdi reverted already.

From: llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org] On Behalf Of Hans
Wennborg via llvm-dev
Sent: Tuesday, December 13, 2016 6:42 PM
To: Grang, Mandeep Singh
Cc: llvm-dev@lists.llvm.org; Nico Weber
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
>
> Wait, so you committed a patch that breaks these tests? Should you fix
> them first?
>
> IIUC, LLVM_ABI_BREAKING_CHECKS is WITH_ASSERTS by default, so your
> change, which is known to break things, is enabled for those of us
> enabling asserts?
>
> Or am I misunderstanding?

Looks like Mehdi reverted already.

Disabled by default, not reverted, but yes turned it off.

Just to be clear, committing this intentionally with the knowledge that you
were breaking tests in LLVM and Clang without a plan to fix them in a
timely fashion was completely unacceptable. There are a lot of people who
work really hard to keep our buildbots green, and committing patches that
break them creates work for them and blinds us to issues that crop up while
the bots are red.

It sounds like everything is currently on the right track, though, so I'm
looking forward to seeing this work finished.