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

[mgrang]

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.

[dexonsmith]

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

[mgrang]

Based patch on LLVM_ENABLE_ABI_BREAKING_CHECKS.

[mgrang]

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.

[mgrang]

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]

Added unittest which checks for forward and reverse iteration.

[mgrang]

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

[mehdi_amini]

include/llvm/ADT/SmallPtrSet.h

30

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

38

The test cannot link without LLVM_ENABLE_ABI_BREAKING_CHECKS I believe.

[mgrang]

include/llvm/ADT/SmallPtrSet.h

30

@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

38

Will guard this test for LLVM_ENABLE_ABI_BREAKING_CHECKS.

[mgrang]

1. Moved ReverseIterate under LLVM namespace.
2. Guarded unit test for LLVM_ENABLE_ABI_BREAKING_CHECKS.

[mgrang]

include/llvm/ADT/SmallPtrSet.h

30

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

[mehdi_amini]

include/llvm/ADT/SmallPtrSet.h

30

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

[mgrang]

include/llvm/ADT/SmallPtrSet.h

30

@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]

include/llvm/ADT/SmallPtrSet.h

30

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]

include/llvm/ADT/SmallPtrSet.h

30

Ah got it. Thanks! Will push a patch.

[mgrang]

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

[mgrang]

unittests/ADT/CMakeLists.txt

67

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

[mehdi_amini]

include/llvm/ADT/SmallPtrSet.h

32

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

lib/Support/CommandLine.cpp

55

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

unittests/ADT/CMakeLists.txt

67

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

[mgrang]

unittests/ADT/CMakeLists.txt

67

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.

[mehdi_amini]

include/llvm/ADT/SmallPtrSet.h

290

I'd write this:

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

301

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

unittests/ADT/CMakeLists.txt

67

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]

include/llvm/ADT/SmallPtrSet.h

290

Done

unittests/ADT/CMakeLists.txt

67

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]

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

unittests/ADT/CMakeLists.txt

67

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.

[mgrang]

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

[craig.topper]

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.

include/llvm/ADT/SmallPtrSet.h

 // This file defines the SmallPtrSet class.  See the doxygen comment for
 // SmallPtrSetImplBase for more details on the algorithm used.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_SMALLPTRSET_H
 #define LLVM_ADT_SMALLPTRSET_H
 
+#include "llvm/Config/abi-breaking.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include <cassert>
 #include <cstddef>
 #include <cstring>
 #include <cstdlib>
 #include <initializer_list>
 #include <iterator>
 #include <utility>
 
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+namespace llvm {
+template <class T = void> struct ReverseIterate { static bool value; };
+template <class T> bool ReverseIterate<T>::value = true;
+}
+#endif
+
 namespace llvm {
 
 /// SmallPtrSetImplBase - This is the common code shared among all the
 /// SmallPtrSet<>'s, which is almost everything.  SmallPtrSet has two modes, one
 /// for small and one for large sets.
 ///
 /// Small sets use an array of pointers allocated in the SmallPtrSet object,
 /// which is treated as a simple array of pointers.  When a pointer is added to

 class SmallPtrSetIteratorImpl {
 protected:
   const void *const *Bucket;
   const void *const *End;
 
 public:
   explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
     : Bucket(BP), End(E) {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value)
+      RetreatIfNotValid();
+    else
+#endif
       AdvanceIfNotValid();
   }
 
   bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
     return Bucket == RHS.Bucket;
   }
   bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
     return Bucket != RHS.Bucket;
   }
 
 protected:
   /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
   /// that is.   This is guaranteed to stop because the end() bucket is marked
   /// valid.
   void AdvanceIfNotValid() {
     assert(Bucket <= End);
     while (Bucket != End &&
            (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
             *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
       ++Bucket;
   }
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+  void RetreatIfNotValid() {
+    --Bucket;
+    assert(Bucket <= End);
+    while (Bucket != End &&
+           (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
+            *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) {
+      --Bucket;
+    }
+  }
+#endif
 };
 
 /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
 template<typename PtrTy>
 class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
   typedef PointerLikeTypeTraits<PtrTy> PtrTraits;
 
 public:
public:
   // Most methods provided by baseclass.
 
   const PtrTy operator*() const {
     assert(Bucket < End);
     return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
   }
 
   inline SmallPtrSetIterator& operator++() {          // Preincrement
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value)
+      RetreatIfNotValid();
+    else {
+      ++Bucket;
+      AdvanceIfNotValid();
+    }
+#else
     ++Bucket;
     AdvanceIfNotValid();
+#endif
     return *this;
   }
 
   SmallPtrSetIterator operator++(int) {        // Postincrement
-    SmallPtrSetIterator tmp = *this; ++*this; return tmp;
+    SmallPtrSetIterator tmp = *this;
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value)
+      --*this;
+    else
+#endif
+    ++*this;
+    return tmp;
   }
 };
 
 /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
 /// power of two (which means N itself if N is already a power of two).
 template<unsigned N>
 struct RoundUpToPowerOfTwo;
 
for (; I != E; ++I)
       insert(*I);
   }
 
   void insert(std::initializer_list<PtrType> IL) {
     insert(IL.begin(), IL.end());
   }
 
   inline iterator begin() const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value)
+      return endPtr();
+#endif
     return iterator(CurArray, EndPointer());
   }
   inline iterator end() const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value)
+      return iterator(CurArray, CurArray);
+#endif
+    return endPtr();
+  }
+
+private:
+  inline iterator endPtr() const {
     const void *const *End = EndPointer();
     return iterator(End, End);
   }
 };
 
 /// SmallPtrSet - This class implements a set which is optimized for holding
 /// SmallSize or less elements.  This internally rounds up SmallSize to the next
 /// power of two if it is not already a power of two.  See the comments above

lib/Support/CommandLine.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <map>
 using namespace llvm;
 using namespace cl;
 
 #define DEBUG_TYPE "commandline"
 
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+namespace llvm {
+// If LLVM_ENABLE_ABI_BREAKING_CHECKS is set the flag -mllvm -reverse-iterate
+// can be used to toggle forward/reverse iteration of unordered containers.
+// This will help uncover differences in codegen caused due to undefined
+// iteration order.
+static cl::opt<bool, true> ReverseIteration("reverse-iterate",
+  cl::location(ReverseIterate<bool>::value), cl::init(true));
+}
+#endif
+
 //===----------------------------------------------------------------------===//
 // Template instantiations and anchors.
 //
 namespace llvm {
 namespace cl {
 template class basic_parser<bool>;
 template class basic_parser<boolOrDefault>;
 template class basic_parser<int>;

unittests/ADT/CMakeLists.txt

set(ADTSources
   StringRefTest.cpp
   StringSwitchTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
   VariadicFunctionTest.cpp
  )
 
+if(DEFINED LLVM_ENABLE_ABI_BREAKING_CHECKS)
+  list(APPEND ADTSources ReverseIterationTest.cpp)
+endif()
+
 add_llvm_unittest(ADTTests
   ${ADTSources}
   )
 
 add_dependencies(ADTTests intrinsics_gen)

unittests/ADT/ReverseIterationTest.cpp

+//===- llvm/unittest/ADT/ReverseIterationTest.cpp ------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// ReverseIteration unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+using namespace llvm;
+
+TEST(ReverseIterationTest, SmallPtrSetTest) {
+
+  SmallPtrSet<void*, 4> Set;
+  void *Ptrs[] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 };
+  void *ReversePtrs[] = { (void*)0x4, (void*)0x3, (void*)0x2, (void*)0x1 };
+
+  for (auto *Ptr: Ptrs)
+    Set.insert(Ptr);
+
+  // Check forward iteration.
+  ReverseIterate<bool>::value = false;
+  for (const auto &Tuple : zip(Set, Ptrs))
+    ASSERT_EQ(std::get<0>(Tuple), std::get<1>(Tuple));
+
+  // Check reverse iteration.
+  ReverseIterate<bool>::value = true;
+  for (const auto &Tuple : zip(Set, ReversePtrs))
+    ASSERT_EQ(std::get<0>(Tuple), std::get<1>(Tuple));
+}