Page MenuHomePhabricator

[llvm] Iterate SmallPtrSet in reverse order to uncover non-determinism in codegen
ClosedPublic

Authored by mgrang on Nov 15 2016, 4:47 PM.

Details

Summary

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.
This is enabled only with LLVM_ENABLE_ABI_BREAKING_CHECKS.

Diff Detail

Repository
rL LLVM

Event Timeline

mgrang updated this revision to Diff 78098.Nov 15 2016, 4:47 PM
mgrang retitled this revision from to [llvm] Iterate SmallPtrSet in reverse order to uncover codegen non-determinism.
mgrang updated this object.
mgrang set the repository for this revision to rL LLVM.
mgrang added a subscriber: llvm-commits.

+Chandler; we've chatted about similar ideas in the past.

emaste added a subscriber: emaste.Nov 15 2016, 6:19 PM
mgrang updated this revision to Diff 78914.Nov 22 2016, 12:03 PM
mgrang retitled this revision from [llvm] Iterate SmallPtrSet in reverse order to uncover codegen non-determinism to [llvm] Iterate SmallPtrSet in reverse order to uncover non-determinism in codegen.
mgrang updated this object.
mgrang removed a reviewer: zinob.

Based patch on LLVM_ENABLE_ABI_BREAKING_CHECKS.

Based on discussions on the associated email thread:

I have based this patch on LLVM_ENABLE_ABI_BREAKING_CHECKS. I have also turned it ON by default so that this is enabled in buildbot by default.
The user can toggle the behavior with the -mllvm -reverse-iterate flag.

Note: There are no associated tests with this patch as it is very difficult (not possible?) to detect "reverse" iteration since the relative order of elements in the SmallPtrSet is always undefined.
I would be happy to write tests for this if someone can suggest a good way of testing it. Otherwise the biggest test for this is to enable it in the buildbot and let the unit tests fail due to non-deterministic codegen.

mgrang updated this revision to Diff 79466.Nov 28 2016, 3:26 PM
mgrang removed rL LLVM as the repository for this revision.

Added unittest which checks for forward and reverse iteration.

Thanks @mehdi_amini for suggesting the unit test to check forward and reverse iteration.

mehdi_amini added inline comments.Nov 28 2016, 3:32 PM
include/llvm/ADT/SmallPtrSet.h
30 ↗(On Diff #79466)

This introduces a dependency from ADT to Support, I'm not sure it is OK.
Also the symbol should be in the LLVM namespace.

unittests/ADT/ReverseIterationTest.cpp
37 ↗(On Diff #79466)

The test cannot link without LLVM_ENABLE_ABI_BREAKING_CHECKS I believe.

mgrang added inline comments.Nov 28 2016, 4:13 PM
include/llvm/ADT/SmallPtrSet.h
30 ↗(On Diff #79466)

@mehdi_amini Yes, I will move ReverseIterate to LLVM namespace.

Initially I was skeptical about defining ReverseIterate in Support. But then I did not know of a better place to do this, Could you please suggest what would be a preferable place to define this?

unittests/ADT/ReverseIterationTest.cpp
37 ↗(On Diff #79466)

Will guard this test for LLVM_ENABLE_ABI_BREAKING_CHECKS.

mgrang updated this revision to Diff 79486.Nov 28 2016, 5:42 PM
  1. Moved ReverseIterate under LLVM namespace.
  2. Guarded unit test for LLVM_ENABLE_ABI_BREAKING_CHECKS.
mgrang added inline comments.Dec 2 2016, 12:47 PM
include/llvm/ADT/SmallPtrSet.h
30 ↗(On Diff #79466)

@mehdi_amini Could you please take a look at my updated patch and comment when you get a chance?

mehdi_amini added inline comments.Dec 5 2016, 6:47 PM
include/llvm/ADT/SmallPtrSet.h
30 ↗(On Diff #79466)

I don't have a good suggestion. This is quite annoying. Maybe making them weak definition in a header (possibly using template)?

mgrang added inline comments.Dec 7 2016, 12:11 PM
include/llvm/ADT/SmallPtrSet.h
30 ↗(On Diff #79466)

@mehdi_amini Thanks for the suggestion.

Variable templates are a C++14 feature and the compiler will output this warning:
"warning: variable templates are a C++14 extension [-Wc++14-extensions]"

Would we need to silence these? By passing -Wno-c++14-extensions in the CMake flags?

mehdi_amini added inline comments.Dec 7 2016, 12:15 PM
include/llvm/ADT/SmallPtrSet.h
30 ↗(On Diff #79466)

No this is not OK, LLVM builds in C++11 mode.
I didn't expect you to need a variable template, but a static member in a templated class.

mgrang added inline comments.Dec 7 2016, 12:19 PM
include/llvm/ADT/SmallPtrSet.h
30 ↗(On Diff #79466)

Ah got it. Thanks! Will push a patch.

mgrang updated this revision to Diff 81148.EditedDec 12 2016, 2:52 PM

Changed ReverseIterate to static member of a template class (it has weak definition). This breaks the dependency between ADT and Support.

mgrang marked 2 inline comments as done.Dec 12 2016, 2:54 PM
mgrang added inline comments.
unittests/ADT/CMakeLists.txt
67 ↗(On Diff #81148)

Without explicitly passing LLVM_ENABLE_ABI_BREAKING_CHECKS to the compilation line of ReverseIteration.cpp, it always complains about undefined variable "ReverseIterate".

mehdi_amini added inline comments.Dec 12 2016, 5:59 PM
include/llvm/ADT/SmallPtrSet.h
31 ↗(On Diff #81148)

Wasn't it the goal of this to have it enabled by default in assert builds?

lib/Support/CommandLine.cpp
55 ↗(On Diff #81148)

You don't need the redefinition here I think (unless libSupport never imports SmallPtrSet?)

unittests/ADT/CMakeLists.txt
67 ↗(On Diff #81148)

That's not great, but I don't see a better way right now, can you at least document it in file here?

mgrang updated this revision to Diff 81265.Dec 13 2016, 11:26 AM
mgrang added inline comments.Dec 13 2016, 11:30 AM
unittests/ADT/CMakeLists.txt
67 ↗(On Diff #81148)

Didn't realize we needed to include llvm/Config/abi-breaking.h in the header for LLVM_ABI_BREAKING_CHECKS to be used. After including this in the header we no longer need an explicit add_definitions.

mgrang marked 2 inline comments as done.Dec 13 2016, 11:32 AM
mehdi_amini added inline comments.Dec 13 2016, 11:34 AM
include/llvm/ADT/SmallPtrSet.h
290 ↗(On Diff #81265)

I'd write this:

#if LLVM_ENABLE_ABI_BREAKING_CHECKS
    if (ReverseIterate<bool>::value) {
      RetreatIfNotValid();
      return *this;
    }
#endif
    ++Bucket;
    AdvanceIfNotValid();
   return *this;
301 ↗(On Diff #81265)

Similar as a above, that makes the LLVM_ENABLE_ABI_BREAKING_CHECKS path more self-contained.

unittests/ADT/CMakeLists.txt
67 ↗(On Diff #81148)

Even if you build in Release mode?
My understanding was that the add_definitions was enabling the unittest all the time, regardless of the build configuration.

mgrang updated this revision to Diff 81290.Dec 13 2016, 1:05 PM
mgrang marked an inline comment as done.Dec 13 2016, 1:09 PM
mgrang added inline comments.
include/llvm/ADT/SmallPtrSet.h
290 ↗(On Diff #81265)

Done

unittests/ADT/CMakeLists.txt
67 ↗(On Diff #81148)

No, this test will only be enabled when LLVM_ENABLE_ABI_BREAKING_CHECKS is defined.

However, conditionally including this test file only when LLVM_ENABLE_ABI_BREAKING_CHECKS is defined produces an error in Release mode: "unknown file ReverseIteration.cpp"
So I guess we need to put the condition on the test instead of the file.

mehdi_amini edited edge metadata.Dec 13 2016, 3:43 PM

I think we reached the point of good enough!
So LGTM.

unittests/ADT/CMakeLists.txt
67 ↗(On Diff #81148)

I was trying to make the test work in release mode, and expecting the add_definitions(-DLLVM_ENABLE_ABI_BREAKING_CHECKS) to enable it even in release mode. However that wouldn't work because the include of abi-breaking.h will override the command line definition. May not worth being fixed there.

mehdi_amini accepted this revision.Dec 13 2016, 3:43 PM
mehdi_amini edited edge metadata.
This revision is now accepted and ready to land.Dec 13 2016, 3:43 PM

Thanks @mehdi_amini and @dexonsmith for all your help with this patch.
I will commit this.

This revision was automatically updated to reflect the committed changes.

I know this was turned in a while ago. But should the command line option have a description or be marked hidden or both. I believe it shows up in -help on a debug build, but has no description.