[ADT][CMake][AutoConf] fail-fast iterators for DenseMap

[sanjoy]

Summary

This is a re-do of D7931 with the following changes:

• the EpochTracker class is now conditional on LLVM_ENABLE_FAIL_FAST_ITERATORS and not NDEBUG.
• The most significant change: LLVM_ENABLE_FAIL_FAST_ITERATORS can be forced to be set or unset independent of NDEBUG. By default, cmake and autoconf set it (thus enabling fail-fast iterators) for with-asserts builds and unset it for without-asserts builds.

With these changes, projects that require ABI compatibility between
defined(NDEBUG) builds and !defined(NDEBUG) builds can get that by
clamping LLVM_ENABLE_FAIL_FAST_ITERATORS to on or off.

Minor changes from D7931

• HandleBase::getEpochAddress returns a void * to emphasise that the result is for comparison, not derefernecing.
• HandleBase::getEpochAddress was missing in the fail-fast-disabled version of HandleBase. This was not a problem earlier since the function is only called from asserts and when asserts were enabled, we'd always choose the fail-fast-enabled version of HandleBase. Since this is no longer the case (a with-asserts build may be using the fail-fast-disabled version of HandleBase), the missing method shows up as an obvious compiler error.

Original summary for D7931:
This patch is an attempt at making DenseMapIterators "fail-fast".
Fail-fast iterators that have been invalidated due to insertion into
the host DenseMap deterministically trip an assert (in debug mode)
on access, instead of non-deterministically hitting memory corruption
issues.

[zturner]

If I understand correctly, this broke before because LLDB would redefine
_NDEBUG sometimes, but not other times when including clang headers.

Now, since this isn't based on _NDEBUG, this is no longer an issue. If so,
looks good to me.

[echristo]

The configure portions are OK with me.

-eric

[rnk]

This seems like a reasonably good compromise. I'd really like to have this iterator invalidation enabled when assertions are enabled, but we have the ability to flip it off when ABI compatibility is important. Being ABI incompatible by default is really just acknowledging that LLVM's ABI isn't very stable.

Are there any more places we should be documenting this check? http://llvm.org/docs/ReleaseProcess.html or http://lldb.llvm.org/build.html? I know that Chromium for example uses a Release+Asserts build of Clang. This might be too much overhead for them.

LLDB for example might want to have a check like:

if (NOT LLVM_FAIL_FAST_ITERATORS STREQUAL "FORCE_OFF")
  message(FATAL_ERROR "LLDB requires a stable LLVM ABI, set LLVM_FAIL_FAST_ITERATORS to FORCE_OFF")
endif()

[sanjoy]

Are there any more places we should be documenting this check? http://llvm.org/docs/ReleaseProcess.html or http://lldb.llvm.org/build.html? I know that Chromium for example uses a Release+Asserts build of Clang. This might be too much overhead for them.

That's a good idea. Do you think it is reasonable to have a blurb
about this in the LLVM Programmer’s Manual also?

LLDB for example might want to have a check like:

if (NOT LLVM_FAIL_FAST_ITERATORS STREQUAL "FORCE_OFF")
  message(FATAL_ERROR "LLDB requires a stable LLVM ABI, set LLVM_FAIL_FAST_ITERATORS to FORCE_OFF")
endif()

http://reviews.llvm.org/D8351

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[sanjoy]

Address review: rename flag to LLVM_*ABI_BREAKING_CHECKS

[sanjoy]

So the current status of this change is

• the actual code changes have already been LGTM'ed, before this

revision was uploaded

• the autoconf changes have been LGTM'ed by Eric

Can someone please take a look at the cmake changes?

I still have to make address Reid's review of adding more
documentation, I should be able to get to it by the end of day
tomorrow.

Thanks!

• Sanjoy

[rnk]

cmake changes lgtm

[sanjoy]

When I was looking for a place to add a small blurb documenting this
new flag, I noticed this

`--disable-assertions`

Builds LLVM with ``NDEBUG`` defined.  Changes the LLVM ABI.  Also available

in Packaging.rst.

If disabling assertions is *specified* to change the LLVM ABI then all
of this extra LLVM_ENABLE_ABI_BREAKING_CHANGES work is unneeded
complexity. If not, then should this clause be removed from
Packaging.{rst|html}?

Thanks,

• Sanjoy

[sanjoy]

• Add LLVM_ENABLE_ABI_BREAKING_CHECKS to the generated config.h. I think this is a better model since this way clients do not have to remember to add -DLLVM_ENABLE_ABI_BREAKING_CHECKS when pulling in LLVM headers.
• Add a blurb in the programmers manual.

Given that this change has received a fair amount of review already, I
plan to check the change in sometime this week in its current form
unless someone has objections or further review.

[sanjoy]

• move LLVM_ENABLE_ABI_BREAKING_CHECKS to llvm-config.h. config.h is not meant to be included in exported headers.

I'll be checking this patch in today.

llvm/trunk/CMakeLists.txt

 option(LLVM_ENABLE_WERROR "Fail and stop if a warning is triggered." OFF)
 
 if( NOT uppercase_CMAKE_BUILD_TYPE STREQUAL "DEBUG" )
   option(LLVM_ENABLE_ASSERTIONS "Enable assertions" OFF)
 else()
   option(LLVM_ENABLE_ASSERTIONS "Enable assertions" ON)
 endif()
 
+set(LLVM_ABI_BREAKING_CHECKS "WITH_ASSERTS" CACHE STRING
+  "Enable abi-breaking checks.  Can be WITH_ASSERTS, FORCE_ON or FORCE_OFF.")
+
 option(LLVM_FORCE_USE_OLD_HOST_TOOLCHAIN
        "Set to ON to force using an old, unsupported host toolchain." OFF)
 
 option(LLVM_USE_INTEL_JITEVENTS
   "Use Intel JIT API to inform Intel(R) VTune(TM) Amplifier XE 2011 about JIT code"
   OFF)
 
 if( LLVM_USE_INTEL_JITEVENTS )

llvm/trunk/autoconf/configure.ac

else
   AC_SUBST(ENABLE_PROFILING,[[ENABLE_PROFILING=1]])
 fi
 
 dnl --enable-assertions : check whether they want to turn on assertions or not:
 AC_ARG_ENABLE(assertions,AS_HELP_STRING(
   --enable-assertions,[Compile with assertion checks enabled (default is YES)]),, enableval="yes")
 if test ${enableval} = "yes" ; then
   AC_SUBST(DISABLE_ASSERTIONS,[[]])
+  assertions_enabled="yes"
 else
   AC_SUBST(DISABLE_ASSERTIONS,[[DISABLE_ASSERTIONS=1]])
+  assertions_enabled="no"
 fi
 
 dnl --enable-werror : check whether we want Werror on by default
 AC_ARG_ENABLE(werror,AS_HELP_STRING(
   --enable-werror,[Compile with -Werror enabled (default is NO)]),, enableval="no")
 case "$enableval" in
   yes) AC_SUBST(ENABLE_WERROR,[1]) ;;
   no)  AC_SUBST(ENABLE_WERROR,[0]) ;;
   default) AC_SUBST(ENABLE_WERROR,[0]);;
   *) AC_MSG_ERROR([Invalid setting for --enable-werror. Use "yes" or "no"]) ;;
 esac
 
 dnl --enable-expensive-checks : check whether they want to turn on expensive debug checks:
 AC_ARG_ENABLE(expensive-checks,AS_HELP_STRING(
   --enable-expensive-checks,[Compile with expensive debug checks enabled (default is NO)]),, enableval="no")
 if test ${enableval} = "yes" ; then
   AC_SUBST(ENABLE_EXPENSIVE_CHECKS,[[ENABLE_EXPENSIVE_CHECKS=1]])
   AC_SUBST(EXPENSIVE_CHECKS,[[yes]])
 else
   AC_SUBST(ENABLE_EXPENSIVE_CHECKS,[[]])
   AC_SUBST(EXPENSIVE_CHECKS,[[no]])
 fi
 
+dnl --enable-abi-breaking-checks : decide whether we should compile in asserts and
+dnl checks that make the build ABI incompatible with an llvm built without these
+dnl checks enabled.
+AC_ARG_ENABLE(abi-breaking-checks,AS_HELP_STRING(
+  --enable-abi-breaking-checks,[Compile with abi-breaking asserts support (default is with-asserts)]),, enableval="with-asserts")
+case "$enableval" in
+  with-asserts)  if test ${assertions_enabled} = "yes" ; then
+                   AC_DEFINE([LLVM_ENABLE_ABI_BREAKING_CHECKS],[1],[Define to enable checks that alter the LLVM C++ ABI])
+     fi ;;
+  yes) AC_DEFINE([LLVM_ENABLE_ABI_BREAKING_CHECKS],[1],[Define to enable checks that alter the LLVM C++ ABI]) ;;
+  no) ;;
+  *) AC_MSG_ERROR([Invalid setting for --enable-abi-breaking-checks.  Use "with-asserts", "yes" or "no"])
+esac
+
 dnl --enable-debug-runtime : should runtime libraries have debug symbols?
 AC_ARG_ENABLE(debug-runtime,
    AS_HELP_STRING(--enable-debug-runtime,[Build runtime libs with debug symbols (default is NO)]),,enableval=no)
 if test ${enableval} = "no" ; then
   AC_SUBST(DEBUG_RUNTIME,[[]])
 else
   AC_SUBST(DEBUG_RUNTIME,[[DEBUG_RUNTIME=1]])
 fi

llvm/trunk/cmake/modules/HandleLLVMOptions.cmake

foreach (flags_var_to_scrub
         CMAKE_C_FLAGS_RELWITHDEBINFO
         CMAKE_C_FLAGS_MINSIZEREL)
       string (REGEX REPLACE "(^| )[/-]D *NDEBUG($| )" " "
         "${flags_var_to_scrub}" "${${flags_var_to_scrub}}")
     endforeach()
   endif()
 endif()
 
+string(TOUPPER "${LLVM_ABI_BREAKING_CHECKS}" uppercase_LLVM_ABI_BREAKING_CHECKS)
+
+if( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "WITH_ASSERTS" )
+  if( LLVM_ENABLE_ASSERTIONS )
+    set( LLVM_ENABLE_ABI_BREAKING_CHECKS 1 )
+  endif()
+elseif( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "FORCE_ON" )
+  set( LLVM_ENABLE_ABI_BREAKING_CHECKS 1 )
+elseif( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "FORCE_OFF" )
+  # We don't need to do anything special to turn off ABI breaking checks.
+else()
+  message(FATAL_ERROR "Unknown value for LLVM_ABI_BREAKING_CHECKS: \"${LLVM_ABI_BREAKING_CHECKS}\"!")
+endif()
+
 if(WIN32)
   set(LLVM_HAVE_LINK_VERSION_SCRIPT 0)
   if(CYGWIN)
     set(LLVM_ON_WIN32 0)
     set(LLVM_ON_UNIX 1)
   else(CYGWIN)
     set(LLVM_ON_WIN32 1)
     set(LLVM_ON_UNIX 0)

llvm/trunk/configure

Optional Features:
   --enable-optimized      Compile with optimizations enabled (default is NO)
   --enable-profiling      Compile with profiling enabled (default is NO)
   --enable-assertions     Compile with assertion checks enabled (default is
                           YES)
   --enable-werror         Compile with -Werror enabled (default is NO)
   --enable-expensive-checks
                           Compile with expensive debug checks enabled (default
                           is NO)
+  --enable-abi-breaking-checks
+                          Compile with abi-breaking asserts support (default
+                          is with-asserts)
   --enable-debug-runtime  Build runtime libs with debug symbols (default is
                           NO)
   --enable-debug-symbols  Build compiler with debug symbols (default is NO if
                           optimization is on and YES if it's off)
   --enable-keep-symbols   Do not strip installed executables)
   --enable-jit            Enable Just In Time Compiling (default is YES)
   --enable-docs           Build documents (default is YES)
   --enable-doxygen        Build doxygen documentation (default is NO)
if test "${enable_assertions+set}" = set; then
   enableval=$enable_assertions;
 else
   enableval="yes"
 fi
 
 if test ${enableval} = "yes" ; then
   DISABLE_ASSERTIONS=
 
+  assertions_enabled="yes"
 else
   DISABLE_ASSERTIONS=DISABLE_ASSERTIONS=1
 
+  assertions_enabled="no"
 fi
 
 # Check whether --enable-werror was given.
 if test "${enable_werror+set}" = set; then
   enableval=$enable_werror;
 else
   enableval="no"
 fi

 
 else
   ENABLE_EXPENSIVE_CHECKS=
 
   EXPENSIVE_CHECKS=no
 
 fi
 
+# Check whether --enable-abi-breaking-checks was given.
+if test "${enable_abi_breaking_checks+set}" = set; then
+  enableval=$enable_abi_breaking_checks;
+else
+  enableval="with-asserts"
+fi
+
+case "$enableval" in
+  with-asserts)  if test ${assertions_enabled} = "yes" ; then
+
+cat >>confdefs.h <<\_ACEOF
+#define LLVM_ENABLE_ABI_BREAKING_CHECKS 1
+_ACEOF
+
+     fi ;;
+  yes)
+cat >>confdefs.h <<\_ACEOF
+#define LLVM_ENABLE_ABI_BREAKING_CHECKS 1
+_ACEOF
+ ;;
+  no) ;;
+  *) { { echo "$as_me:$LINENO: error: Invalid setting for --enable-abi-breaking-checks.  Use \"with-asserts\", \"yes\" or \"no\"" >&5
+echo "$as_me: error: Invalid setting for --enable-abi-breaking-checks.  Use \"with-asserts\", \"yes\" or \"no\"" >&2;}
+   { (exit 1); exit 1; }; }
+esac
+
 # Check whether --enable-debug-runtime was given.
 if test "${enable_debug_runtime+set}" = set; then
   enableval=$enable_debug_runtime;
 else
   enableval=no
 fi
 
 if test ${enableval} = "no" ; then

llvm/trunk/docs/CMake.rst

 
 **LLVM_ENABLE_PEDANTIC**:BOOL
   Enable pedantic mode. This disables compiler specific extensions, if
   possible. Defaults to ON.
 
 **LLVM_ENABLE_WERROR**:BOOL
   Stop and fail build, if a compiler warning is triggered. Defaults to OFF.
 
+**LLVM_ABI_BREAKING_CHECKS**:STRING
+  Used to decide if LLVM should be built with ABI breaking checks or
+  not.  Allowed values are `WITH_ASSERTS` (default), `FORCE_ON` and
+  `FORCE_OFF`.  `WITH_ASSERTS` turns on ABI breaking checks in an
+  assertion enabled build.  `FORCE_ON` (`FORCE_OFF`) turns them on
+  (off) irrespective of whether normal (`NDEBUG` based) assertions are
+  enabled or not.  A version of LLVM built with ABI breaking checks
+  is not ABI compatible with a version built without it.
+
 **LLVM_BUILD_32_BITS**:BOOL
   Build 32-bits executables and libraries on 64-bits systems. This option is
   available only on some 64-bits unix systems. Defaults to OFF.
 
 **LLVM_TARGET_ARCH**:STRING
   LLVM target to use for native code generation. This is required for JIT
   generation. It defaults to "host", meaning that it shall pick the architecture
   of the machine where LLVM is being built. If you are cross-compiling, set it

llvm/trunk/docs/ProgrammersManual.rst

 generate significantly more efficient code. We have also found that a large
 amount of our usage of type hierarchies fits better with tag-based pattern
 matching rather than dynamic dispatch across a common interface. Within LLVM we
 have built custom helpers to facilitate this design. See this document's
 section on :ref:`isa and dyn_cast <isa>` and our :doc:`detailed document
 <HowToSetUpLLVMStyleRTTI>` which describes how you can implement this
 pattern for use with the LLVM helpers.
 
+.. _abi_breaking_checks:
+
+ABI Breaking Checks
+-------------------
+
+Checks and asserts that alter the LLVM C++ ABI are predicated on the
+preprocessor symbol `LLVM_ENABLE_ABI_BREAKING_CHECKS` -- LLVM
+libraries built with `LLVM_ENABLE_ABI_BREAKING_CHECKS` are not ABI
+compatible LLVM libraries built without it defined.  By default,
+turning on assertions also turns on `LLVM_ENABLE_ABI_BREAKING_CHECKS`
+so a default +Asserts build is not ABI compatible with a
+default -Asserts build.  Clients that want ABI compatibility
+between +Asserts and -Asserts builds should use the CMake or autoconf
+build systems to set `LLVM_ENABLE_ABI_BREAKING_CHECKS` independently
+of `LLVM_ENABLE_ASSERTIONS`.
+
 .. _coreclasses:
 
 The Core LLVM Class Hierarchy Reference
 =======================================
 
 ``#include "llvm/IR/Type.h"``
 
 header source: `Type.h <http://llvm.org/doxygen/Type_8h-source.html>`_

llvm/trunk/include/llvm/ADT/DenseMap.h

 // This file defines the DenseMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_DENSEMAP_H
 #define LLVM_ADT_DENSEMAP_H
 
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/EpochTracker.h"
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>

 
 template <
     typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>,
     typename Bucket = detail::DenseMapPair<KeyT, ValueT>, bool IsConst = false>
 class DenseMapIterator;
 
 template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
           typename BucketT>
-class DenseMapBase {
+class DenseMapBase : public DebugEpochBase {
 public:
   typedef unsigned size_type;
   typedef KeyT key_type;
   typedef ValueT mapped_type;
   typedef BucketT value_type;
 
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT> iterator;
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>
       const_iterator;
   inline iterator begin() {
     // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
-    return empty() ? end() : iterator(getBuckets(), getBucketsEnd());
+    return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline iterator end() {
-    return iterator(getBucketsEnd(), getBucketsEnd(), true);
+    return iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
   inline const_iterator begin() const {
-    return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd());
+    return empty() ? end()
+                   : const_iterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline const_iterator end() const {
-    return const_iterator(getBucketsEnd(), getBucketsEnd(), true);
+    return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
 
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
     return getNumEntries() == 0;
   }
   unsigned size() const { return getNumEntries(); }
 
   /// Grow the densemap so that it has at least Size buckets. Does not shrink
   void resize(size_type Size) {
+    incrementEpoch();
     if (Size > getNumBuckets())
       grow(Size);
   }
 
   void clear() {
+    incrementEpoch();
     if (getNumEntries() == 0 && getNumTombstones() == 0) return;
 
     // If the capacity of the array is huge, and the # elements used is small,
     // shrink the array.
     if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
       shrink_and_clear();
       return;
     }
public:
   size_type count(const KeyT &Val) const {
     const BucketT *TheBucket;
     return LookupBucketFor(Val, TheBucket) ? 1 : 0;
   }
 
   iterator find(const KeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, getBucketsEnd(), true);
+      return iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
   const_iterator find(const KeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, getBucketsEnd(), true);
+      return const_iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
 
   /// Alternate version of find() which allows a different, and possibly
   /// less expensive, key type.
   /// The DenseMapInfo is responsible for supplying methods
   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
   /// type used.
   template<class LookupKeyT>
   iterator find_as(const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, getBucketsEnd(), true);
+      return iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
   template<class LookupKeyT>
   const_iterator find_as(const LookupKeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, getBucketsEnd(), true);
+      return const_iterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
 
   /// lookup - Return the entry for the specified key, or a default
   /// constructed value if no such entry exists.
   ValueT lookup(const KeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
       return TheBucket->getSecond();
     return ValueT();
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // If the key is already in the map, it returns false and doesn't update the
   // value.
   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     BucketT *TheBucket;
     if (LookupBucketFor(KV.first, TheBucket))
-      return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
+      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
                             false); // Already in map.
 
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
-    return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
+    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+                          true);
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // If the key is already in the map, it returns false and doesn't update the
   // value.
   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     BucketT *TheBucket;
     if (LookupBucketFor(KV.first, TheBucket))
-      return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
+      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
                             false); // Already in map.
-    
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucket(std::move(KV.first),
                                  std::move(KV.second),
                                  TheBucket);
-    return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
+    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+                          true);
   }
 
   /// insert - Range insertion of pairs.
   template<typename InputIt>
   void insert(InputIt I, InputIt E) {
     for (; I != E; ++I)
       insert(*I);
   }
BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) {
     TheBucket = InsertIntoBucketImpl(Key, TheBucket);
 
     TheBucket->getFirst() = std::move(Key);
     new (&TheBucket->getSecond()) ValueT(std::move(Value));
     return TheBucket;
   }
 
   BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
+    incrementEpoch();
+
     // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
     // the buckets are empty (meaning that many are filled with tombstones),
     // grow the table.
     //
     // The later case is tricky.  For example, if we had one empty bucket with
     // tons of tombstones, failing lookups (e.g. for insertion) would have to
     // probe almost the entire table until it found the empty bucket.  If the
     // table completely filled with tombstones, no lookup would ever succeed,
LargeRep Rep = {
       static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num
     };
     return Rep;
   }
 };
 
 template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket,
           bool IsConst>
-class DenseMapIterator {
+class DenseMapIterator : DebugEpochBase::HandleBase {
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true> ConstIterator;
   friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>;
+  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>;
 
 public:
   typedef ptrdiff_t difference_type;
   typedef typename std::conditional<IsConst, const Bucket, Bucket>::type
   value_type;
   typedef value_type *pointer;
   typedef value_type &reference;
   typedef std::forward_iterator_tag iterator_category;
 private:
   pointer Ptr, End;
 public:
   DenseMapIterator() : Ptr(nullptr), End(nullptr) {}
 
-  DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false)
-    : Ptr(Pos), End(E) {
+  DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
+                   bool NoAdvance = false)
+      : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
+    assert(isHandleInSync() && "invalid construction!");
     if (!NoAdvance) AdvancePastEmptyBuckets();
   }
 
   // Converting ctor from non-const iterators to const iterators. SFINAE'd out
   // for const iterator destinations so it doesn't end up as a user defined copy
   // constructor.
   template <bool IsConstSrc,
             typename = typename std::enable_if<!IsConstSrc && IsConst>::type>
   DenseMapIterator(
       const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
-      : Ptr(I.Ptr), End(I.End) {}
+      : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}
 
   reference operator*() const {
+    assert(isHandleInSync() && "invalid iterator access!");
     return *Ptr;
   }
   pointer operator->() const {
+    assert(isHandleInSync() && "invalid iterator access!");
     return Ptr;
   }
 
   bool operator==(const ConstIterator &RHS) const {
-    return Ptr == RHS.operator->();
+    assert((!Ptr || isHandleInSync()) && "handle not in sync!");
+    assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
+    assert(getEpochAddress() == RHS.getEpochAddress() &&
+           "comparing incomparable iterators!");
+    return Ptr == RHS.Ptr;
   }
   bool operator!=(const ConstIterator &RHS) const {
-    return Ptr != RHS.operator->();
+    assert((!Ptr || isHandleInSync()) && "handle not in sync!");
+    assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
+    assert(getEpochAddress() == RHS.getEpochAddress() &&
+           "comparing incomparable iterators!");
+    return Ptr != RHS.Ptr;
   }
 
   inline DenseMapIterator& operator++() {  // Preincrement
+    assert(isHandleInSync() && "invalid iterator access!");
     ++Ptr;
     AdvancePastEmptyBuckets();
     return *this;
   }
   DenseMapIterator operator++(int) {  // Postincrement
+    assert(isHandleInSync() && "invalid iterator access!");
     DenseMapIterator tmp = *this; ++*this; return tmp;
   }
 
 private:
   void AdvancePastEmptyBuckets() {
     const KeyT Empty = KeyInfoT::getEmptyKey();
     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 

llvm/trunk/include/llvm/ADT/EpochTracker.h

+//===- llvm/ADT/EpochTracker.h - ADT epoch tracking --------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.
+// These can be used to write iterators that are fail-fast when LLVM is built
+// with asserts enabled.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_EPOCH_TRACKER_H
+#define LLVM_ADT_EPOCH_TRACKER_H
+
+#include "llvm/Config/llvm-config.h"
+
+#include <cstdint>
+
+namespace llvm {
+
+#ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
+
+class DebugEpochBase {
+public:
+  void incrementEpoch() {}
+
+  class HandleBase {
+  public:
+    HandleBase() {}
+    explicit HandleBase(const DebugEpochBase *) {}
+    bool isHandleInSync() const { return true; }
+    const void *getEpochAddress() const { return nullptr; }
+  };
+};
+
+#else
+
+/// \brief A base class for data structure classes wishing to make iterators
+/// ("handles") pointing into themselves fail-fast.  When building without
+/// asserts, this class is empty and does nothing.
+///
+/// DebugEpochBase does not by itself track handles pointing into itself.  The
+/// expectation is that routines touching the handles will poll on
+/// isHandleInSync at appropriate points to assert that the handle they're using
+/// is still valid.
+///
+class DebugEpochBase {
+  uint64_t Epoch;
+
+public:
+  DebugEpochBase() : Epoch(0) {}
+
+  /// \brief Calling incrementEpoch invalidates all handles pointing into the
+  /// calling instance.
+  void incrementEpoch() { ++Epoch; }
+
+  /// \brief The destructor calls incrementEpoch to make use-after-free bugs
+  /// more likely to crash deterministically.
+  ~DebugEpochBase() { incrementEpoch(); }
+
+  /// \brief A base class for iterator classes ("handles") that wish to poll for
+  /// iterator invalidating modifications in the underlying data structure.
+  /// When LLVM is built without asserts, this class is empty and does nothing.
+  ///
+  /// HandleBase does not track the parent data structure by itself.  It expects
+  /// the routines modifying the data structure to call incrementEpoch when they
+  /// make an iterator-invalidating modification.
+  ///
+  class HandleBase {
+    const uint64_t *EpochAddress;
+    uint64_t EpochAtCreation;
+
+  public:
+    HandleBase() : EpochAddress(nullptr), EpochAtCreation(UINT64_MAX) {}
+
+    explicit HandleBase(const DebugEpochBase *Parent)
+        : EpochAddress(&Parent->Epoch), EpochAtCreation(Parent->Epoch) {}
+
+    /// \brief Returns true if the DebugEpochBase this Handle is linked to has
+    /// not called incrementEpoch on itself since the creation of this
+    /// HandleBase instance.
+    bool isHandleInSync() const { return *EpochAddress == EpochAtCreation; }
+
+    /// \brief Returns a pointer to the epoch word stored in the data structure
+    /// this handle points into.  Can be used to check if two iterators point
+    /// into the same data structure.
+    const void *getEpochAddress() const { return EpochAddress; }
+  };
+};
+
+#endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
+
+} // namespace llvm
+
+#endif

llvm/trunk/include/llvm/Config/config.h.in

 #undef LLVM_DATADIR
 
 /* Target triple LLVM will generate code for by default */
 #undef LLVM_DEFAULT_TARGET_TRIPLE
 
 /* Installation directory for documentation */
 #undef LLVM_DOCSDIR
 
+/* Define to enable checks that alter the LLVM C++ ABI */
+#undef LLVM_ENABLE_ABI_BREAKING_CHECKS
+
 /* Define if threads enabled */
 #undef LLVM_ENABLE_THREADS
 
 /* Define if zlib is enabled */
 #undef LLVM_ENABLE_ZLIB
 
 /* Installation directory for config files */
 #undef LLVM_ETCDIR

llvm/trunk/include/llvm/Config/llvm-config.h.cmake

 #define LLVM_VERSION_PATCH ${LLVM_VERSION_PATCH}
 
 /* LLVM version string */
 #define LLVM_VERSION_STRING "${PACKAGE_VERSION}"
 
 /* Define if we link Polly to the tools */
 #cmakedefine LINK_POLLY_INTO_TOOLS
 
+/* Define if LLVM is built with asserts and checks that change the layout of
+   client-visible data structures.  */
+#cmakedefine LLVM_ENABLE_ABI_BREAKING_CHECKS
+
 #endif

llvm/trunk/include/llvm/Config/llvm-config.h.in

 #undef LLVM_VERSION_MINOR
 
 /* Patch version of the LLVM API */
 #undef LLVM_VERSION_PATCH
 
 /* LLVM version string */
 #undef LLVM_VERSION_STRING
 
+/* Define to enable checks that alter the LLVM C++ ABI */
+#undef LLVM_ENABLE_ABI_BREAKING_CHECKS
+
 #endif