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

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 )

Makefile.config.in

 #DISABLE_ASSERTIONS = 1
 @DISABLE_ASSERTIONS@
 
 # When ENABLE_EXPENSIVE_CHECKS is enabled, builds of all of the LLVM
 # code will include expensive checks, otherwise they are excluded.
 #ENABLE_EXPENSIVE_CHECKS = 0
 @ENABLE_EXPENSIVE_CHECKS@
 
+# When ENABLE_ABI_BREAKING_CHECKS is enabled, LLVM will be built with
+# asserts and checks that make it ABI-incompatible with LLVM built
+# without those checks.  By default this is enabled for a with-asserts
+# build and disabled for a without-asserts build.  Projects interested
+# in keeping with-asserts builds ABI compatible with without-asserts
+# builds should clamp this to on or off via the cmake or autoconf
+# build system.
+ENABLE_ABI_BREAKING_CHECKS = @ENABLE_ABI_BREAKING_CHECKS@
+
 # When DEBUG_RUNTIME is enabled, the runtime libraries will retain debug
 # symbols.
 #DEBUG_RUNTIME = 1
 @DEBUG_RUNTIME@
 
 # When DEBUG_SYMBOLS is enabled, the compiler libraries will retain debug
 # symbols.
 #DEBUG_SYMBOLS = 1

Makefile.rules

 # If ENABLE_EXPENSIVE_CHECKS=1 is specified (make command line or
 # configured), then enable expensive checks by defining the
 # appropriate preprocessor symbols.
 ifeq ($(ENABLE_EXPENSIVE_CHECKS),1)
   BuildMode := $(BuildMode)+Checks
   CPP.Defines += -D_GLIBCXX_DEBUG -DXDEBUG
 endif
 
+# If ENABLE_ABI_BREAKING_CHECKS=1 specified (make command line or
+# configured), then enable ABI breaking checks by defining the
+# appropriate preprocessor symbols.
+ifeq ($(ENABLE_ABI_BREAKING_CHECKS), 1)
+  CPP.Defines += -DLLVM_ENABLE_ABI_BREAKING_CHECKS
+endif
+
 # LOADABLE_MODULE implies several other things so we force them to be
 # defined/on.
 ifdef LOADABLE_MODULE
   SHARED_LIBRARY := 1
   LINK_LIBS_IN_SHARED := 1
 endif
 
 ifdef SHARED_LIBRARY

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_SUBST(ENABLE_ABI_BREAKING_CHECKS,[1])
+                 else
+                   AC_SUBST(ENABLE_ABI_BREAKING_CHECKS,[0])
+     fi ;;
+  yes) AC_SUBST(ENABLE_ABI_BREAKING_CHECKS,[[1]]) ;;
+  no) AC_SUBST(ENABLE_ABI_BREAKING_CHECKS,[[0]]) ;;
+  *) 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

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 )
+    add_llvm_definitions( -DLLVM_ENABLE_ABI_BREAKING_CHECKS )
+  endif()
+elseif( uppercase_LLVM_ABI_BREAKING_CHECKS STREQUAL "FORCE_ON" )
+  add_llvm_definitions( -DLLVM_ENABLE_ABI_BREAKING_CHECKS )
+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)

configure

 CLANG_PLUGIN_SUPPORT
 ENABLE_CLANG_STATIC_ANALYZER
 ENABLE_OPTIMIZED
 ENABLE_PROFILING
 DISABLE_ASSERTIONS
 ENABLE_WERROR
 ENABLE_EXPENSIVE_CHECKS
 EXPENSIVE_CHECKS
+ENABLE_ABI_BREAKING_CHECKS
 DEBUG_RUNTIME
 DEBUG_SYMBOLS
 KEEP_SYMBOLS
 JIT
 TARGET_HAS_JIT
 TARGETS_WITH_JIT
 ENABLE_DOCS
 ENABLE_DOXYGEN
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
+                   ENABLE_ABI_BREAKING_CHECKS=1
+
+                 else
+                   ENABLE_ABI_BREAKING_CHECKS=0
+
+     fi ;;
+  yes) ENABLE_ABI_BREAKING_CHECKS=1
+ ;;
+  no) ENABLE_ABI_BREAKING_CHECKS=0
+ ;;
+  *) { { 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

 CLANG_PLUGIN_SUPPORT!$CLANG_PLUGIN_SUPPORT$ac_delim
 ENABLE_CLANG_STATIC_ANALYZER!$ENABLE_CLANG_STATIC_ANALYZER$ac_delim
 ENABLE_OPTIMIZED!$ENABLE_OPTIMIZED$ac_delim
 ENABLE_PROFILING!$ENABLE_PROFILING$ac_delim
 DISABLE_ASSERTIONS!$DISABLE_ASSERTIONS$ac_delim
 ENABLE_WERROR!$ENABLE_WERROR$ac_delim
 ENABLE_EXPENSIVE_CHECKS!$ENABLE_EXPENSIVE_CHECKS$ac_delim
 EXPENSIVE_CHECKS!$EXPENSIVE_CHECKS$ac_delim
+ENABLE_ABI_BREAKING_CHECKS!$ENABLE_ABI_BREAKING_CHECKS$ac_delim
 DEBUG_RUNTIME!$DEBUG_RUNTIME$ac_delim
-DEBUG_SYMBOLS!$DEBUG_SYMBOLS$ac_delim
 _ACEOF
 
   if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 97; then
     break
   elif $ac_last_try; then
     { { echo "$as_me:$LINENO: error: could not make $CONFIG_STATUS" >&5
 echo "$as_me: error: could not make $CONFIG_STATUS" >&2;}
    { (exit 1); exit 1; }; }

 cat >>$CONFIG_STATUS <<_ACEOF
 CEOF$ac_eof
 _ACEOF
 
 
 ac_delim='%!_!# '
 for ac_last_try in false false false false false :; do
   cat >conf$$subs.sed <<_ACEOF
+DEBUG_SYMBOLS!$DEBUG_SYMBOLS$ac_delim
 KEEP_SYMBOLS!$KEEP_SYMBOLS$ac_delim
 JIT!$JIT$ac_delim
 TARGET_HAS_JIT!$TARGET_HAS_JIT$ac_delim
 TARGETS_WITH_JIT!$TARGETS_WITH_JIT$ac_delim
 ENABLE_DOCS!$ENABLE_DOCS$ac_delim
 ENABLE_DOXYGEN!$ENABLE_DOXYGEN$ac_delim
 enable_searchengine!$enable_searchengine$ac_delim
 enable_external_search!$enable_external_search$ac_delim

 LIBXML2_LIBS!$LIBXML2_LIBS$ac_delim
 LIBXML2_INC!$LIBXML2_INC$ac_delim
 HAVE_PTHREAD!$HAVE_PTHREAD$ac_delim
 HAVE_LIBZ!$HAVE_LIBZ$ac_delim
 HUGE_VAL_SANITY!$HUGE_VAL_SANITY$ac_delim
 MMAP_FILE!$MMAP_FILE$ac_delim
 SHLIBEXT!$SHLIBEXT$ac_delim
 LLVM_PREFIX!$LLVM_PREFIX$ac_delim
-LLVM_BINDIR!$LLVM_BINDIR$ac_delim
 _ACEOF
 
   if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 97; then
     break
   elif $ac_last_try; then
     { { echo "$as_me:$LINENO: error: could not make $CONFIG_STATUS" >&5
 echo "$as_me: error: could not make $CONFIG_STATUS" >&2;}
    { (exit 1); exit 1; }; }

 cat >>$CONFIG_STATUS <<_ACEOF
 CEOF$ac_eof
 _ACEOF
 
 
 ac_delim='%!_!# '
 for ac_last_try in false false false false false :; do
   cat >conf$$subs.sed <<_ACEOF
+LLVM_BINDIR!$LLVM_BINDIR$ac_delim
 LLVM_DATADIR!$LLVM_DATADIR$ac_delim
 LLVM_DOCSDIR!$LLVM_DOCSDIR$ac_delim
 LLVM_ETCDIR!$LLVM_ETCDIR$ac_delim
 LLVM_INCLUDEDIR!$LLVM_INCLUDEDIR$ac_delim
 LLVM_INFODIR!$LLVM_INFODIR$ac_delim
 LLVM_MANDIR!$LLVM_MANDIR$ac_delim
 LLVM_CONFIGTIME!$LLVM_CONFIGTIME$ac_delim
 BINDINGS_TO_BUILD!$BINDINGS_TO_BUILD$ac_delim
 HAVE_OCAMLOPT!$HAVE_OCAMLOPT$ac_delim
 HAVE_OCAML_OUNIT!$HAVE_OCAML_OUNIT$ac_delim
 OCAML_LIBDIR!$OCAML_LIBDIR$ac_delim
 ENABLE_VISIBILITY_INLINES_HIDDEN!$ENABLE_VISIBILITY_INLINES_HIDDEN$ac_delim
 RPATH!$RPATH$ac_delim
 RDYNAMIC!$RDYNAMIC$ac_delim
 program_prefix!$program_prefix$ac_delim
 LIBOBJS!$LIBOBJS$ac_delim
 LTLIBOBJS!$LTLIBOBJS$ac_delim
 _ACEOF
 
-  if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 17; then
+  if test `sed -n "s/.*$ac_delim\$/X/p" conf$$subs.sed | grep -c X` = 18; then
     break
   elif $ac_last_try; then
     { { echo "$as_me:$LINENO: error: could not make $CONFIG_STATUS" >&5
 echo "$as_me: error: could not make $CONFIG_STATUS" >&2;}
    { (exit 1); exit 1; }; }
   else
     ac_delim="$ac_delim!$ac_delim _$ac_delim!! "
   fi

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

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();
 

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