Index: include/llvm/ADT/ADTModCountTracker.h =================================================================== --- /dev/null +++ include/llvm/ADT/ADTModCountTracker.h @@ -0,0 +1,62 @@ +//===- llvm/ADT/ADTModCountTracker.h - ADT mod-count 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 ADTModCountTracker class, useful in writing fail-fast +// iterators. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ITERATOR_EPOCH_H +#define LLVM_ADT_ITERATOR_EPOCH_H + +namespace llvm { + +template struct ADTModCountTracker; + +template <> struct ADTModCountTracker { + struct Parent { + void bumpModCount() {} + }; + + struct Child { + Child() {} + explicit Child(const ADTModCountTracker::Parent *) {} + + bool isMatchingModCount() const { return true; } + }; +}; + +template <> struct ADTModCountTracker { + struct Parent { + uint64_t ModCount; + + Parent() : ModCount(0) {} + + void bumpModCount() { ModCount++; } + + ~Parent() { bumpModCount(); } + }; + + struct Child { + const uint64_t *ParentModCountAddress; + uint64_t ModCountEpoch; + + Child() : ParentModCountAddress(nullptr), ModCountEpoch(-1) {} + + explicit Child(const ADTModCountTracker::Parent *P) + : ParentModCountAddress(&P->ModCount), ModCountEpoch(P->ModCount) {} + + bool isMatchingModCount() const { + return ParentModCountAddress && *ParentModCountAddress == ModCountEpoch; + } + }; +}; +}; + +#endif Index: include/llvm/ADT/DenseMap.h =================================================================== --- include/llvm/ADT/DenseMap.h +++ include/llvm/ADT/DenseMap.h @@ -15,6 +15,7 @@ #define LLVM_ADT_DENSEMAP_H #include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/ADTModCountTracker.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" @@ -48,9 +49,17 @@ typename Bucket = detail::DenseMapPair, bool IsConst = false> class DenseMapIterator; +#ifndef NDEBUG +typedef ADTModCountTracker DenseMapModCountTracker; +#else +typedef ADTModCountTracker DenseMapModCountTracker; +#endif + template class DenseMapBase { + DenseMapModCountTracker::Parent ModCountParent; + public: typedef unsigned size_type; typedef KeyT key_type; @@ -62,16 +71,19 @@ 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(), &ModCountParent); } inline iterator end() { - return iterator(getBucketsEnd(), getBucketsEnd(), true); + return iterator(getBucketsEnd(), getBucketsEnd(), &ModCountParent, true); } inline const_iterator begin() const { - return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); + return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd(), + &ModCountParent); } inline const_iterator end() const { - return const_iterator(getBucketsEnd(), getBucketsEnd(), true); + return const_iterator(getBucketsEnd(), getBucketsEnd(), &ModCountParent, + true); } bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { @@ -81,11 +93,13 @@ /// Grow the densemap so that it has at least Size buckets. Does not shrink void resize(size_type Size) { + ModCountParent.bumpModCount(); if (Size > getNumBuckets()) grow(Size); } void clear() { + ModCountParent.bumpModCount(); if (getNumEntries() == 0 && getNumTombstones() == 0) return; // If the capacity of the array is huge, and the # elements used is small, @@ -118,13 +132,13 @@ iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), true); + return iterator(TheBucket, getBucketsEnd(), &ModCountParent, 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(), &ModCountParent, true); return end(); } @@ -137,14 +151,14 @@ iterator find_as(const LookupKeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), true); + return iterator(TheBucket, getBucketsEnd(), &ModCountParent, true); return end(); } template 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(), &ModCountParent, true); return end(); } @@ -163,12 +177,14 @@ std::pair insert(const std::pair &KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), - false); // Already in map. + return std::make_pair( + iterator(TheBucket, getBucketsEnd(), &ModCountParent, 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(), &ModCountParent, true), true); } // Inserts key,value pair into the map if the key isn't already in the map. @@ -177,14 +193,16 @@ std::pair insert(std::pair &&KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), - false); // Already in map. - + return std::make_pair( + iterator(TheBucket, getBucketsEnd(), &ModCountParent, 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(), &ModCountParent, true), true); } /// insert - Range insertion of pairs. @@ -431,6 +449,8 @@ } BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { + ModCountParent.bumpModCount(); + // 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. @@ -990,6 +1010,7 @@ class DenseMapIterator { typedef DenseMapIterator ConstIterator; friend class DenseMapIterator; + DenseMapModCountTracker::Child ModCountChild; public: typedef ptrdiff_t difference_type; @@ -1003,8 +1024,10 @@ public: DenseMapIterator() : Ptr(nullptr), End(nullptr) {} - DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) - : Ptr(Pos), End(E) { + DenseMapIterator(pointer Pos, pointer E, + const DenseMapModCountTracker::Parent *FFP, + bool NoAdvance = false) + : ModCountChild(FFP), Ptr(Pos), End(E) { if (!NoAdvance) AdvancePastEmptyBuckets(); } @@ -1013,12 +1036,14 @@ // Otherwise this is a copy constructor for iterator. DenseMapIterator( const DenseMapIterator &I) - : Ptr(I.Ptr), End(I.End) {} + : ModCountChild(I.ModCountChild), Ptr(I.Ptr), End(I.End) {} reference operator*() const { + assert(ModCountChild.isMatchingModCount() && "invalid iterator access!"); return *Ptr; } pointer operator->() const { + assert(ModCountChild.isMatchingModCount() && "invalid iterator access!"); return Ptr; } @@ -1030,11 +1055,13 @@ } inline DenseMapIterator& operator++() { // Preincrement + assert(ModCountChild.isMatchingModCount() && "invalid iterator access!"); ++Ptr; AdvancePastEmptyBuckets(); return *this; } DenseMapIterator operator++(int) { // Postincrement + assert(ModCountChild.isMatchingModCount() && "invalid iterator access!"); DenseMapIterator tmp = *this; ++*this; return tmp; }