Eliminate Subzero's dependency on llvm::FoldingSet
Bug: b/155971541
Change-Id: I039fb24b31f01fff1ca2190fd6fe3b3e8118990e
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/44929
Kokoro-Result: kokoro <noreply+kokoro@google.com>
Tested-by: Nicolas Capens <nicolascapens@google.com>
Reviewed-by: Sean Risser <srisser@google.com>
diff --git a/src/Reactor/BUILD.gn b/src/Reactor/BUILD.gn
index 737e00f..eb72fd9 100644
--- a/src/Reactor/BUILD.gn
+++ b/src/Reactor/BUILD.gn
@@ -222,7 +222,6 @@
"$subzero_llvm_dir/lib/Support/Debug.cpp",
"$subzero_llvm_dir/lib/Support/Errno.cpp",
"$subzero_llvm_dir/lib/Support/ErrorHandling.cpp",
- "$subzero_llvm_dir/lib/Support/FoldingSet.cpp",
"$subzero_llvm_dir/lib/Support/Hashing.cpp",
"$subzero_llvm_dir/lib/Support/ManagedStatic.cpp",
"$subzero_llvm_dir/lib/Support/MemoryBuffer.cpp",
diff --git a/third_party/llvm-subzero/Android.bp b/third_party/llvm-subzero/Android.bp
index bf70dc5..f5e1c3a 100644
--- a/third_party/llvm-subzero/Android.bp
+++ b/third_party/llvm-subzero/Android.bp
@@ -82,7 +82,6 @@
"lib/Support/Debug.cpp",
"lib/Support/Errno.cpp",
"lib/Support/ErrorHandling.cpp",
- "lib/Support/FoldingSet.cpp",
"lib/Support/Hashing.cpp",
"lib/Support/ManagedStatic.cpp",
"lib/Support/MemoryBuffer.cpp",
diff --git a/third_party/llvm-subzero/CMakeLists.txt b/third_party/llvm-subzero/CMakeLists.txt
index 03b63b7..d8be547 100644
--- a/third_party/llvm-subzero/CMakeLists.txt
+++ b/third_party/llvm-subzero/CMakeLists.txt
@@ -44,7 +44,6 @@
"include/llvm/ADT/DenseMapInfo.h"
"include/llvm/ADT/edit_distance.h"
"include/llvm/ADT/EpochTracker.h"
- "include/llvm/ADT/FoldingSet.h"
"include/llvm/ADT/Hashing.h"
"include/llvm/ADT/ilist_base.h"
"include/llvm/ADT/ilist_iterator.h"
@@ -166,7 +165,6 @@
"lib/Support/Debug.cpp"
"lib/Support/Errno.cpp"
"lib/Support/ErrorHandling.cpp"
- "lib/Support/FoldingSet.cpp"
"lib/Support/Hashing.cpp"
"lib/Support/ManagedStatic.cpp"
"lib/Support/MemoryBuffer.cpp"
diff --git a/third_party/llvm-subzero/include/llvm/ADT/FoldingSet.h b/third_party/llvm-subzero/include/llvm/ADT/FoldingSet.h
deleted file mode 100644
index dab1829..0000000
--- a/third_party/llvm-subzero/include/llvm/ADT/FoldingSet.h
+++ /dev/null
@@ -1,777 +0,0 @@
-//===-- llvm/ADT/FoldingSet.h - Uniquing Hash Set ---------------*- 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 a hash set that can be used to remove duplication of nodes
-// in a graph. This code was originally created by Chris Lattner for use with
-// SelectionDAGCSEMap, but was isolated to provide use across the llvm code set.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ADT_FOLDINGSET_H
-#define LLVM_ADT_FOLDINGSET_H
-
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/iterator.h"
-#include "llvm/Support/Allocator.h"
-#include <cassert>
-#include <cstddef>
-#include <cstdint>
-#include <utility>
-
-namespace llvm {
-
-/// This folding set used for two purposes:
-/// 1. Given information about a node we want to create, look up the unique
-/// instance of the node in the set. If the node already exists, return
-/// it, otherwise return the bucket it should be inserted into.
-/// 2. Given a node that has already been created, remove it from the set.
-///
-/// This class is implemented as a single-link chained hash table, where the
-/// "buckets" are actually the nodes themselves (the next pointer is in the
-/// node). The last node points back to the bucket to simplify node removal.
-///
-/// Any node that is to be included in the folding set must be a subclass of
-/// FoldingSetNode. The node class must also define a Profile method used to
-/// establish the unique bits of data for the node. The Profile method is
-/// passed a FoldingSetNodeID object which is used to gather the bits. Just
-/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class.
-/// NOTE: That the folding set does not own the nodes and it is the
-/// responsibility of the user to dispose of the nodes.
-///
-/// Eg.
-/// class MyNode : public FoldingSetNode {
-/// private:
-/// std::string Name;
-/// unsigned Value;
-/// public:
-/// MyNode(const char *N, unsigned V) : Name(N), Value(V) {}
-/// ...
-/// void Profile(FoldingSetNodeID &ID) const {
-/// ID.AddString(Name);
-/// ID.AddInteger(Value);
-/// }
-/// ...
-/// };
-///
-/// To define the folding set itself use the FoldingSet template;
-///
-/// Eg.
-/// FoldingSet<MyNode> MyFoldingSet;
-///
-/// Four public methods are available to manipulate the folding set;
-///
-/// 1) If you have an existing node that you want add to the set but unsure
-/// that the node might already exist then call;
-///
-/// MyNode *M = MyFoldingSet.GetOrInsertNode(N);
-///
-/// If The result is equal to the input then the node has been inserted.
-/// Otherwise, the result is the node existing in the folding set, and the
-/// input can be discarded (use the result instead.)
-///
-/// 2) If you are ready to construct a node but want to check if it already
-/// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to
-/// check;
-///
-/// FoldingSetNodeID ID;
-/// ID.AddString(Name);
-/// ID.AddInteger(Value);
-/// void *InsertPoint;
-///
-/// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint);
-///
-/// If found then M with be non-NULL, else InsertPoint will point to where it
-/// should be inserted using InsertNode.
-///
-/// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new
-/// node with FindNodeOrInsertPos;
-///
-/// InsertNode(N, InsertPoint);
-///
-/// 4) Finally, if you want to remove a node from the folding set call;
-///
-/// bool WasRemoved = RemoveNode(N);
-///
-/// The result indicates whether the node existed in the folding set.
-
-class FoldingSetNodeID;
-class StringRef;
-
-//===----------------------------------------------------------------------===//
-/// FoldingSetImpl - Implements the folding set functionality. The main
-/// structure is an array of buckets. Each bucket is indexed by the hash of
-/// the nodes it contains. The bucket itself points to the nodes contained
-/// in the bucket via a singly linked list. The last node in the list points
-/// back to the bucket to facilitate node removal.
-///
-class FoldingSetImpl {
- virtual void anchor(); // Out of line virtual method.
-
-protected:
- /// Buckets - Array of bucket chains.
- ///
- void **Buckets;
-
- /// NumBuckets - Length of the Buckets array. Always a power of 2.
- ///
- unsigned NumBuckets;
-
- /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes
- /// is greater than twice the number of buckets.
- unsigned NumNodes;
-
- explicit FoldingSetImpl(unsigned Log2InitSize = 6);
- FoldingSetImpl(FoldingSetImpl &&Arg);
- FoldingSetImpl &operator=(FoldingSetImpl &&RHS);
- ~FoldingSetImpl();
-
-public:
- //===--------------------------------------------------------------------===//
- /// Node - This class is used to maintain the singly linked bucket list in
- /// a folding set.
- ///
- class Node {
- private:
- // NextInFoldingSetBucket - next link in the bucket list.
- void *NextInFoldingSetBucket;
-
- public:
- Node() : NextInFoldingSetBucket(nullptr) {}
-
- // Accessors
- void *getNextInBucket() const { return NextInFoldingSetBucket; }
- void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; }
- };
-
- /// clear - Remove all nodes from the folding set.
- void clear();
-
- /// RemoveNode - Remove a node from the folding set, returning true if one
- /// was removed or false if the node was not in the folding set.
- bool RemoveNode(Node *N);
-
- /// GetOrInsertNode - If there is an existing simple Node exactly
- /// equal to the specified node, return it. Otherwise, insert 'N' and return
- /// it instead.
- Node *GetOrInsertNode(Node *N);
-
- /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
- /// return it. If not, return the insertion token that will make insertion
- /// faster.
- Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
-
- /// InsertNode - Insert the specified node into the folding set, knowing that
- /// it is not already in the folding set. InsertPos must be obtained from
- /// FindNodeOrInsertPos.
- void InsertNode(Node *N, void *InsertPos);
-
- /// InsertNode - Insert the specified node into the folding set, knowing that
- /// it is not already in the folding set.
- void InsertNode(Node *N) {
- Node *Inserted = GetOrInsertNode(N);
- (void)Inserted;
- assert(Inserted == N && "Node already inserted!");
- }
-
- /// size - Returns the number of nodes in the folding set.
- unsigned size() const { return NumNodes; }
-
- /// empty - Returns true if there are no nodes in the folding set.
- bool empty() const { return NumNodes == 0; }
-
- /// reserve - Increase the number of buckets such that adding the
- /// EltCount-th node won't cause a rebucket operation. reserve is permitted
- /// to allocate more space than requested by EltCount.
- void reserve(unsigned EltCount);
-
- /// capacity - Returns the number of nodes permitted in the folding set
- /// before a rebucket operation is performed.
- unsigned capacity() {
- // We allow a load factor of up to 2.0,
- // so that means our capacity is NumBuckets * 2
- return NumBuckets * 2;
- }
-
-private:
- /// GrowHashTable - Double the size of the hash table and rehash everything.
- void GrowHashTable();
-
- /// GrowBucketCount - resize the hash table and rehash everything.
- /// NewBucketCount must be a power of two, and must be greater than the old
- /// bucket count.
- void GrowBucketCount(unsigned NewBucketCount);
-
-protected:
- /// GetNodeProfile - Instantiations of the FoldingSet template implement
- /// this function to gather data bits for the given node.
- virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0;
-
- /// NodeEquals - Instantiations of the FoldingSet template implement
- /// this function to compare the given node with the given ID.
- virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
- FoldingSetNodeID &TempID) const=0;
-
- /// ComputeNodeHash - Instantiations of the FoldingSet template implement
- /// this function to compute a hash value for the given node.
- virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0;
-};
-
-//===----------------------------------------------------------------------===//
-
-/// DefaultFoldingSetTrait - This class provides default implementations
-/// for FoldingSetTrait implementations.
-///
-template<typename T> struct DefaultFoldingSetTrait {
- static void Profile(const T &X, FoldingSetNodeID &ID) {
- X.Profile(ID);
- }
- static void Profile(T &X, FoldingSetNodeID &ID) {
- X.Profile(ID);
- }
-
- // Equals - Test if the profile for X would match ID, using TempID
- // to compute a temporary ID if necessary. The default implementation
- // just calls Profile and does a regular comparison. Implementations
- // can override this to provide more efficient implementations.
- static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
- FoldingSetNodeID &TempID);
-
- // ComputeHash - Compute a hash value for X, using TempID to
- // compute a temporary ID if necessary. The default implementation
- // just calls Profile and does a regular hash computation.
- // Implementations can override this to provide more efficient
- // implementations.
- static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID);
-};
-
-/// FoldingSetTrait - This trait class is used to define behavior of how
-/// to "profile" (in the FoldingSet parlance) an object of a given type.
-/// The default behavior is to invoke a 'Profile' method on an object, but
-/// through template specialization the behavior can be tailored for specific
-/// types. Combined with the FoldingSetNodeWrapper class, one can add objects
-/// to FoldingSets that were not originally designed to have that behavior.
-template<typename T> struct FoldingSetTrait
- : public DefaultFoldingSetTrait<T> {};
-
-/// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but
-/// for ContextualFoldingSets.
-template<typename T, typename Ctx>
-struct DefaultContextualFoldingSetTrait {
- static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) {
- X.Profile(ID, Context);
- }
-
- static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash,
- FoldingSetNodeID &TempID, Ctx Context);
- static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID,
- Ctx Context);
-};
-
-/// ContextualFoldingSetTrait - Like FoldingSetTrait, but for
-/// ContextualFoldingSets.
-template<typename T, typename Ctx> struct ContextualFoldingSetTrait
- : public DefaultContextualFoldingSetTrait<T, Ctx> {};
-
-//===--------------------------------------------------------------------===//
-/// FoldingSetNodeIDRef - This class describes a reference to an interned
-/// FoldingSetNodeID, which can be a useful to store node id data rather
-/// than using plain FoldingSetNodeIDs, since the 32-element SmallVector
-/// is often much larger than necessary, and the possibility of heap
-/// allocation means it requires a non-trivial destructor call.
-class FoldingSetNodeIDRef {
- const unsigned *Data = nullptr;
- size_t Size = 0;
-
-public:
- FoldingSetNodeIDRef() = default;
- FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {}
-
- /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
- /// used to lookup the node in the FoldingSetImpl.
- unsigned ComputeHash() const;
-
- bool operator==(FoldingSetNodeIDRef) const;
-
- bool operator!=(FoldingSetNodeIDRef RHS) const { return !(*this == RHS); }
-
- /// Used to compare the "ordering" of two nodes as defined by the
- /// profiled bits and their ordering defined by memcmp().
- bool operator<(FoldingSetNodeIDRef) const;
-
- const unsigned *getData() const { return Data; }
- size_t getSize() const { return Size; }
-};
-
-//===--------------------------------------------------------------------===//
-/// FoldingSetNodeID - This class is used to gather all the unique data bits of
-/// a node. When all the bits are gathered this class is used to produce a
-/// hash value for the node.
-///
-class FoldingSetNodeID {
- /// Bits - Vector of all the data bits that make the node unique.
- /// Use a SmallVector to avoid a heap allocation in the common case.
- SmallVector<unsigned, 32> Bits;
-
-public:
- FoldingSetNodeID() = default;
-
- FoldingSetNodeID(FoldingSetNodeIDRef Ref)
- : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {}
-
- /// Add* - Add various data types to Bit data.
- ///
- void AddPointer(const void *Ptr);
- void AddInteger(signed I);
- void AddInteger(unsigned I);
- void AddInteger(long I);
- void AddInteger(unsigned long I);
- void AddInteger(long long I);
- void AddInteger(unsigned long long I);
- void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); }
- void AddString(StringRef String);
- void AddNodeID(const FoldingSetNodeID &ID);
-
- template <typename T>
- inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); }
-
- /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID
- /// object to be used to compute a new profile.
- inline void clear() { Bits.clear(); }
-
- /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used
- /// to lookup the node in the FoldingSetImpl.
- unsigned ComputeHash() const;
-
- /// operator== - Used to compare two nodes to each other.
- ///
- bool operator==(const FoldingSetNodeID &RHS) const;
- bool operator==(const FoldingSetNodeIDRef RHS) const;
-
- bool operator!=(const FoldingSetNodeID &RHS) const { return !(*this == RHS); }
- bool operator!=(const FoldingSetNodeIDRef RHS) const { return !(*this ==RHS);}
-
- /// Used to compare the "ordering" of two nodes as defined by the
- /// profiled bits and their ordering defined by memcmp().
- bool operator<(const FoldingSetNodeID &RHS) const;
- bool operator<(const FoldingSetNodeIDRef RHS) const;
-
- /// Intern - Copy this node's data to a memory region allocated from the
- /// given allocator and return a FoldingSetNodeIDRef describing the
- /// interned data.
- FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const;
-};
-
-// Convenience type to hide the implementation of the folding set.
-typedef FoldingSetImpl::Node FoldingSetNode;
-template<class T> class FoldingSetIterator;
-template<class T> class FoldingSetBucketIterator;
-
-// Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which
-// require the definition of FoldingSetNodeID.
-template<typename T>
-inline bool
-DefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID,
- unsigned /*IDHash*/,
- FoldingSetNodeID &TempID) {
- FoldingSetTrait<T>::Profile(X, TempID);
- return TempID == ID;
-}
-template<typename T>
-inline unsigned
-DefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) {
- FoldingSetTrait<T>::Profile(X, TempID);
- return TempID.ComputeHash();
-}
-template<typename T, typename Ctx>
-inline bool
-DefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X,
- const FoldingSetNodeID &ID,
- unsigned /*IDHash*/,
- FoldingSetNodeID &TempID,
- Ctx Context) {
- ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
- return TempID == ID;
-}
-template<typename T, typename Ctx>
-inline unsigned
-DefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X,
- FoldingSetNodeID &TempID,
- Ctx Context) {
- ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context);
- return TempID.ComputeHash();
-}
-
-//===----------------------------------------------------------------------===//
-/// FoldingSet - This template class is used to instantiate a specialized
-/// implementation of the folding set to the node class T. T must be a
-/// subclass of FoldingSetNode and implement a Profile function.
-///
-/// Note that this set type is movable and move-assignable. However, its
-/// moved-from state is not a valid state for anything other than
-/// move-assigning and destroying. This is primarily to enable movable APIs
-/// that incorporate these objects.
-template <class T> class FoldingSet final : public FoldingSetImpl {
-private:
- /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
- /// way to convert nodes into a unique specifier.
- void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const override {
- T *TN = static_cast<T *>(N);
- FoldingSetTrait<T>::Profile(*TN, ID);
- }
-
- /// NodeEquals - Instantiations may optionally provide a way to compare a
- /// node with a specified ID.
- bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash,
- FoldingSetNodeID &TempID) const override {
- T *TN = static_cast<T *>(N);
- return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID);
- }
-
- /// ComputeNodeHash - Instantiations may optionally provide a way to compute a
- /// hash value directly from a node.
- unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const override {
- T *TN = static_cast<T *>(N);
- return FoldingSetTrait<T>::ComputeHash(*TN, TempID);
- }
-
-public:
- explicit FoldingSet(unsigned Log2InitSize = 6)
- : FoldingSetImpl(Log2InitSize) {}
-
- FoldingSet(FoldingSet &&Arg) : FoldingSetImpl(std::move(Arg)) {}
- FoldingSet &operator=(FoldingSet &&RHS) {
- (void)FoldingSetImpl::operator=(std::move(RHS));
- return *this;
- }
-
- typedef FoldingSetIterator<T> iterator;
- iterator begin() { return iterator(Buckets); }
- iterator end() { return iterator(Buckets+NumBuckets); }
-
- typedef FoldingSetIterator<const T> const_iterator;
- const_iterator begin() const { return const_iterator(Buckets); }
- const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
-
- typedef FoldingSetBucketIterator<T> bucket_iterator;
-
- bucket_iterator bucket_begin(unsigned hash) {
- return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
- }
-
- bucket_iterator bucket_end(unsigned hash) {
- return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
- }
-
- /// GetOrInsertNode - If there is an existing simple Node exactly
- /// equal to the specified node, return it. Otherwise, insert 'N' and
- /// return it instead.
- T *GetOrInsertNode(Node *N) {
- return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N));
- }
-
- /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
- /// return it. If not, return the insertion token that will make insertion
- /// faster.
- T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
- return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos));
- }
-};
-
-//===----------------------------------------------------------------------===//
-/// ContextualFoldingSet - This template class is a further refinement
-/// of FoldingSet which provides a context argument when calling
-/// Profile on its nodes. Currently, that argument is fixed at
-/// initialization time.
-///
-/// T must be a subclass of FoldingSetNode and implement a Profile
-/// function with signature
-/// void Profile(FoldingSetNodeID &, Ctx);
-template <class T, class Ctx>
-class ContextualFoldingSet final : public FoldingSetImpl {
- // Unfortunately, this can't derive from FoldingSet<T> because the
- // construction vtable for FoldingSet<T> requires
- // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn
- // requires a single-argument T::Profile().
-
-private:
- Ctx Context;
-
- /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a
- /// way to convert nodes into a unique specifier.
- void GetNodeProfile(FoldingSetImpl::Node *N,
- FoldingSetNodeID &ID) const override {
- T *TN = static_cast<T *>(N);
- ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context);
- }
-
- bool NodeEquals(FoldingSetImpl::Node *N, const FoldingSetNodeID &ID,
- unsigned IDHash, FoldingSetNodeID &TempID) const override {
- T *TN = static_cast<T *>(N);
- return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID,
- Context);
- }
-
- unsigned ComputeNodeHash(FoldingSetImpl::Node *N,
- FoldingSetNodeID &TempID) const override {
- T *TN = static_cast<T *>(N);
- return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context);
- }
-
-public:
- explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6)
- : FoldingSetImpl(Log2InitSize), Context(Context)
- {}
-
- Ctx getContext() const { return Context; }
-
- typedef FoldingSetIterator<T> iterator;
- iterator begin() { return iterator(Buckets); }
- iterator end() { return iterator(Buckets+NumBuckets); }
-
- typedef FoldingSetIterator<const T> const_iterator;
- const_iterator begin() const { return const_iterator(Buckets); }
- const_iterator end() const { return const_iterator(Buckets+NumBuckets); }
-
- typedef FoldingSetBucketIterator<T> bucket_iterator;
-
- bucket_iterator bucket_begin(unsigned hash) {
- return bucket_iterator(Buckets + (hash & (NumBuckets-1)));
- }
-
- bucket_iterator bucket_end(unsigned hash) {
- return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true);
- }
-
- /// GetOrInsertNode - If there is an existing simple Node exactly
- /// equal to the specified node, return it. Otherwise, insert 'N'
- /// and return it instead.
- T *GetOrInsertNode(Node *N) {
- return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N));
- }
-
- /// FindNodeOrInsertPos - Look up the node specified by ID. If it
- /// exists, return it. If not, return the insertion token that will
- /// make insertion faster.
- T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
- return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos));
- }
-};
-
-//===----------------------------------------------------------------------===//
-/// FoldingSetVector - This template class combines a FoldingSet and a vector
-/// to provide the interface of FoldingSet but with deterministic iteration
-/// order based on the insertion order. T must be a subclass of FoldingSetNode
-/// and implement a Profile function.
-template <class T, class VectorT = SmallVector<T*, 8>>
-class FoldingSetVector {
- FoldingSet<T> Set;
- VectorT Vector;
-
-public:
- explicit FoldingSetVector(unsigned Log2InitSize = 6)
- : Set(Log2InitSize) {
- }
-
- typedef pointee_iterator<typename VectorT::iterator> iterator;
- iterator begin() { return Vector.begin(); }
- iterator end() { return Vector.end(); }
-
- typedef pointee_iterator<typename VectorT::const_iterator> const_iterator;
- const_iterator begin() const { return Vector.begin(); }
- const_iterator end() const { return Vector.end(); }
-
- /// clear - Remove all nodes from the folding set.
- void clear() { Set.clear(); Vector.clear(); }
-
- /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
- /// return it. If not, return the insertion token that will make insertion
- /// faster.
- T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) {
- return Set.FindNodeOrInsertPos(ID, InsertPos);
- }
-
- /// GetOrInsertNode - If there is an existing simple Node exactly
- /// equal to the specified node, return it. Otherwise, insert 'N' and
- /// return it instead.
- T *GetOrInsertNode(T *N) {
- T *Result = Set.GetOrInsertNode(N);
- if (Result == N) Vector.push_back(N);
- return Result;
- }
-
- /// InsertNode - Insert the specified node into the folding set, knowing that
- /// it is not already in the folding set. InsertPos must be obtained from
- /// FindNodeOrInsertPos.
- void InsertNode(T *N, void *InsertPos) {
- Set.InsertNode(N, InsertPos);
- Vector.push_back(N);
- }
-
- /// InsertNode - Insert the specified node into the folding set, knowing that
- /// it is not already in the folding set.
- void InsertNode(T *N) {
- Set.InsertNode(N);
- Vector.push_back(N);
- }
-
- /// size - Returns the number of nodes in the folding set.
- unsigned size() const { return Set.size(); }
-
- /// empty - Returns true if there are no nodes in the folding set.
- bool empty() const { return Set.empty(); }
-};
-
-//===----------------------------------------------------------------------===//
-/// FoldingSetIteratorImpl - This is the common iterator support shared by all
-/// folding sets, which knows how to walk the folding set hash table.
-class FoldingSetIteratorImpl {
-protected:
- FoldingSetNode *NodePtr;
-
- FoldingSetIteratorImpl(void **Bucket);
-
- void advance();
-
-public:
- bool operator==(const FoldingSetIteratorImpl &RHS) const {
- return NodePtr == RHS.NodePtr;
- }
- bool operator!=(const FoldingSetIteratorImpl &RHS) const {
- return NodePtr != RHS.NodePtr;
- }
-};
-
-template <class T> class FoldingSetIterator : public FoldingSetIteratorImpl {
-public:
- explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {}
-
- T &operator*() const {
- return *static_cast<T*>(NodePtr);
- }
-
- T *operator->() const {
- return static_cast<T*>(NodePtr);
- }
-
- inline FoldingSetIterator &operator++() { // Preincrement
- advance();
- return *this;
- }
- FoldingSetIterator operator++(int) { // Postincrement
- FoldingSetIterator tmp = *this; ++*this; return tmp;
- }
-};
-
-//===----------------------------------------------------------------------===//
-/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support
-/// shared by all folding sets, which knows how to walk a particular bucket
-/// of a folding set hash table.
-
-class FoldingSetBucketIteratorImpl {
-protected:
- void *Ptr;
-
- explicit FoldingSetBucketIteratorImpl(void **Bucket);
-
- FoldingSetBucketIteratorImpl(void **Bucket, bool)
- : Ptr(Bucket) {}
-
- void advance() {
- void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket();
- uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1;
- Ptr = reinterpret_cast<void*>(x);
- }
-
-public:
- bool operator==(const FoldingSetBucketIteratorImpl &RHS) const {
- return Ptr == RHS.Ptr;
- }
- bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const {
- return Ptr != RHS.Ptr;
- }
-};
-
-template <class T>
-class FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl {
-public:
- explicit FoldingSetBucketIterator(void **Bucket) :
- FoldingSetBucketIteratorImpl(Bucket) {}
-
- FoldingSetBucketIterator(void **Bucket, bool) :
- FoldingSetBucketIteratorImpl(Bucket, true) {}
-
- T &operator*() const { return *static_cast<T*>(Ptr); }
- T *operator->() const { return static_cast<T*>(Ptr); }
-
- inline FoldingSetBucketIterator &operator++() { // Preincrement
- advance();
- return *this;
- }
- FoldingSetBucketIterator operator++(int) { // Postincrement
- FoldingSetBucketIterator tmp = *this; ++*this; return tmp;
- }
-};
-
-//===----------------------------------------------------------------------===//
-/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary
-/// types in an enclosing object so that they can be inserted into FoldingSets.
-template <typename T>
-class FoldingSetNodeWrapper : public FoldingSetNode {
- T data;
-
-public:
- template <typename... Ts>
- explicit FoldingSetNodeWrapper(Ts &&... Args)
- : data(std::forward<Ts>(Args)...) {}
-
- void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); }
-
- T &getValue() { return data; }
- const T &getValue() const { return data; }
-
- operator T&() { return data; }
- operator const T&() const { return data; }
-};
-
-//===----------------------------------------------------------------------===//
-/// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores
-/// a FoldingSetNodeID value rather than requiring the node to recompute it
-/// each time it is needed. This trades space for speed (which can be
-/// significant if the ID is long), and it also permits nodes to drop
-/// information that would otherwise only be required for recomputing an ID.
-class FastFoldingSetNode : public FoldingSetNode {
- FoldingSetNodeID FastID;
-
-protected:
- explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {}
-
-public:
- void Profile(FoldingSetNodeID &ID) const { ID.AddNodeID(FastID); }
-};
-
-//===----------------------------------------------------------------------===//
-// Partial specializations of FoldingSetTrait.
-
-template<typename T> struct FoldingSetTrait<T*> {
- static inline void Profile(T *X, FoldingSetNodeID &ID) {
- ID.AddPointer(X);
- }
-};
-template <typename T1, typename T2>
-struct FoldingSetTrait<std::pair<T1, T2>> {
- static inline void Profile(const std::pair<T1, T2> &P,
- FoldingSetNodeID &ID) {
- ID.Add(P.first);
- ID.Add(P.second);
- }
-};
-
-} // end namespace llvm
-
-#endif // LLVM_ADT_FOLDINGSET_H
diff --git a/third_party/llvm-subzero/include/llvm/IR/Attributes.h b/third_party/llvm-subzero/include/llvm/IR/Attributes.h
index 1578385..cbcefd8 100644
--- a/third_party/llvm-subzero/include/llvm/IR/Attributes.h
+++ b/third_party/llvm-subzero/include/llvm/IR/Attributes.h
@@ -16,12 +16,11 @@
#ifndef LLVM_IR_ATTRIBUTES_H
#define LLVM_IR_ATTRIBUTES_H
+#include "llvm-c/Types.h"
#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/Optional.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/PointerLikeTypeTraits.h"
-#include "llvm-c/Types.h"
#include <bitset>
#include <cassert>
#include <map>
@@ -167,10 +166,6 @@
/// \brief Less-than operator. Useful for sorting the attributes list.
bool operator<(Attribute A) const;
- void Profile(FoldingSetNodeID &ID) const {
- ID.AddPointer(pImpl);
- }
-
/// \brief Return a raw pointer that uniquely identifies this attribute.
void *getRawPointer() const {
return pImpl;
diff --git a/third_party/llvm-subzero/include/llvm/Support/CommandLine.h b/third_party/llvm-subzero/include/llvm/Support/CommandLine.h
index 204672f..37c2856 100644
--- a/third_party/llvm-subzero/include/llvm/Support/CommandLine.h
+++ b/third_party/llvm-subzero/include/llvm/Support/CommandLine.h
@@ -21,13 +21,13 @@
#define LLVM_SUPPORT_COMMANDLINE_H
#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/iterator_range.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
+#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/ManagedStatic.h"
#include <cassert>
diff --git a/third_party/llvm-subzero/lib/Support/APInt.cpp b/third_party/llvm-subzero/lib/Support/APInt.cpp
index 0c0b498..d7f56f5 100644
--- a/third_party/llvm-subzero/lib/Support/APInt.cpp
+++ b/third_party/llvm-subzero/lib/Support/APInt.cpp
@@ -14,7 +14,6 @@
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/StringRef.h"
@@ -163,20 +162,6 @@
return clearUnusedBits();
}
-/// This method 'profiles' an APInt for use with FoldingSet.
-void APInt::Profile(FoldingSetNodeID& ID) const {
- ID.AddInteger(BitWidth);
-
- if (isSingleWord()) {
- ID.AddInteger(VAL);
- return;
- }
-
- unsigned NumWords = getNumWords();
- for (unsigned i = 0; i < NumWords; ++i)
- ID.AddInteger(pVal[i]);
-}
-
/// This function adds a single "digit" integer, y, to the multiple
/// "digit" integer array, x[]. x[] is modified to reflect the addition and
/// 1 is returned if there is a carry out, otherwise 0 is returned.
diff --git a/third_party/llvm-subzero/lib/Support/FoldingSet.cpp b/third_party/llvm-subzero/lib/Support/FoldingSet.cpp
deleted file mode 100644
index c9bca7f..0000000
--- a/third_party/llvm-subzero/lib/Support/FoldingSet.cpp
+++ /dev/null
@@ -1,462 +0,0 @@
-//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements a hash set that can be used to remove duplication of
-// nodes in a graph.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/ADT/FoldingSet.h"
-#include "llvm/ADT/Hashing.h"
-#include "llvm/Support/Allocator.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/Host.h"
-#include "llvm/Support/MathExtras.h"
-#include <cassert>
-#include <cstring>
-using namespace llvm;
-
-//===----------------------------------------------------------------------===//
-// FoldingSetNodeIDRef Implementation
-
-/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
-/// used to lookup the node in the FoldingSetImpl.
-unsigned FoldingSetNodeIDRef::ComputeHash() const {
- return static_cast<unsigned>(hash_combine_range(Data, Data+Size));
-}
-
-bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
- if (Size != RHS.Size) return false;
- return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
-}
-
-/// Used to compare the "ordering" of two nodes as defined by the
-/// profiled bits and their ordering defined by memcmp().
-bool FoldingSetNodeIDRef::operator<(FoldingSetNodeIDRef RHS) const {
- if (Size != RHS.Size)
- return Size < RHS.Size;
- return memcmp(Data, RHS.Data, Size*sizeof(*Data)) < 0;
-}
-
-//===----------------------------------------------------------------------===//
-// FoldingSetNodeID Implementation
-
-/// Add* - Add various data types to Bit data.
-///
-void FoldingSetNodeID::AddPointer(const void *Ptr) {
- // Note: this adds pointers to the hash using sizes and endianness that
- // depend on the host. It doesn't matter, however, because hashing on
- // pointer values is inherently unstable. Nothing should depend on the
- // ordering of nodes in the folding set.
- static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
- "unexpected pointer size");
- AddInteger(reinterpret_cast<uintptr_t>(Ptr));
-}
-void FoldingSetNodeID::AddInteger(signed I) {
- Bits.push_back(I);
-}
-void FoldingSetNodeID::AddInteger(unsigned I) {
- Bits.push_back(I);
-}
-void FoldingSetNodeID::AddInteger(long I) {
- AddInteger((unsigned long)I);
-}
-void FoldingSetNodeID::AddInteger(unsigned long I) {
- if (sizeof(long) == sizeof(int))
- AddInteger(unsigned(I));
- else if (sizeof(long) == sizeof(long long)) {
- AddInteger((unsigned long long)I);
- } else {
- llvm_unreachable("unexpected sizeof(long)");
- }
-}
-void FoldingSetNodeID::AddInteger(long long I) {
- AddInteger((unsigned long long)I);
-}
-void FoldingSetNodeID::AddInteger(unsigned long long I) {
- AddInteger(unsigned(I));
- AddInteger(unsigned(I >> 32));
-}
-
-void FoldingSetNodeID::AddString(StringRef String) {
- unsigned Size = String.size();
- Bits.push_back(Size);
- if (!Size) return;
-
- unsigned Units = Size / 4;
- unsigned Pos = 0;
- const unsigned *Base = (const unsigned*) String.data();
-
- // If the string is aligned do a bulk transfer.
- if (!((intptr_t)Base & 3)) {
- Bits.append(Base, Base + Units);
- Pos = (Units + 1) * 4;
- } else {
- // Otherwise do it the hard way.
- // To be compatible with above bulk transfer, we need to take endianness
- // into account.
- static_assert(sys::IsBigEndianHost || sys::IsLittleEndianHost,
- "Unexpected host endianness");
- if (sys::IsBigEndianHost) {
- for (Pos += 4; Pos <= Size; Pos += 4) {
- unsigned V = ((unsigned char)String[Pos - 4] << 24) |
- ((unsigned char)String[Pos - 3] << 16) |
- ((unsigned char)String[Pos - 2] << 8) |
- (unsigned char)String[Pos - 1];
- Bits.push_back(V);
- }
- } else { // Little-endian host
- for (Pos += 4; Pos <= Size; Pos += 4) {
- unsigned V = ((unsigned char)String[Pos - 1] << 24) |
- ((unsigned char)String[Pos - 2] << 16) |
- ((unsigned char)String[Pos - 3] << 8) |
- (unsigned char)String[Pos - 4];
- Bits.push_back(V);
- }
- }
- }
-
- // With the leftover bits.
- unsigned V = 0;
- // Pos will have overshot size by 4 - #bytes left over.
- // No need to take endianness into account here - this is always executed.
- switch (Pos - Size) {
- case 1: V = (V << 8) | (unsigned char)String[Size - 3]; LLVM_FALLTHROUGH;
- case 2: V = (V << 8) | (unsigned char)String[Size - 2]; LLVM_FALLTHROUGH;
- case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
- default: return; // Nothing left.
- }
-
- Bits.push_back(V);
-}
-
-// AddNodeID - Adds the Bit data of another ID to *this.
-void FoldingSetNodeID::AddNodeID(const FoldingSetNodeID &ID) {
- Bits.append(ID.Bits.begin(), ID.Bits.end());
-}
-
-/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to
-/// lookup the node in the FoldingSetImpl.
-unsigned FoldingSetNodeID::ComputeHash() const {
- return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
-}
-
-/// operator== - Used to compare two nodes to each other.
-///
-bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS) const {
- return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
-}
-
-/// operator== - Used to compare two nodes to each other.
-///
-bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
- return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
-}
-
-/// Used to compare the "ordering" of two nodes as defined by the
-/// profiled bits and their ordering defined by memcmp().
-bool FoldingSetNodeID::operator<(const FoldingSetNodeID &RHS) const {
- return *this < FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
-}
-
-bool FoldingSetNodeID::operator<(FoldingSetNodeIDRef RHS) const {
- return FoldingSetNodeIDRef(Bits.data(), Bits.size()) < RHS;
-}
-
-/// Intern - Copy this node's data to a memory region allocated from the
-/// given allocator and return a FoldingSetNodeIDRef describing the
-/// interned data.
-FoldingSetNodeIDRef
-FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
- unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
- std::uninitialized_copy(Bits.begin(), Bits.end(), New);
- return FoldingSetNodeIDRef(New, Bits.size());
-}
-
-//===----------------------------------------------------------------------===//
-/// Helper functions for FoldingSetImpl.
-
-/// GetNextPtr - In order to save space, each bucket is a
-/// singly-linked-list. In order to make deletion more efficient, we make
-/// the list circular, so we can delete a node without computing its hash.
-/// The problem with this is that the start of the hash buckets are not
-/// Nodes. If NextInBucketPtr is a bucket pointer, this method returns null:
-/// use GetBucketPtr when this happens.
-static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) {
- // The low bit is set if this is the pointer back to the bucket.
- if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)
- return nullptr;
-
- return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr);
-}
-
-
-/// testing.
-static void **GetBucketPtr(void *NextInBucketPtr) {
- intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
- assert((Ptr & 1) && "Not a bucket pointer");
- return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
-}
-
-/// GetBucketFor - Hash the specified node ID and return the hash bucket for
-/// the specified ID.
-static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {
- // NumBuckets is always a power of 2.
- unsigned BucketNum = Hash & (NumBuckets-1);
- return Buckets + BucketNum;
-}
-
-/// AllocateBuckets - Allocated initialized bucket memory.
-static void **AllocateBuckets(unsigned NumBuckets) {
- void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*)));
- // Set the very last bucket to be a non-null "pointer".
- Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
- return Buckets;
-}
-
-//===----------------------------------------------------------------------===//
-// FoldingSetImpl Implementation
-
-void FoldingSetImpl::anchor() {}
-
-FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) {
- assert(5 < Log2InitSize && Log2InitSize < 32 &&
- "Initial hash table size out of range");
- NumBuckets = 1 << Log2InitSize;
- Buckets = AllocateBuckets(NumBuckets);
- NumNodes = 0;
-}
-
-FoldingSetImpl::FoldingSetImpl(FoldingSetImpl &&Arg)
- : Buckets(Arg.Buckets), NumBuckets(Arg.NumBuckets), NumNodes(Arg.NumNodes) {
- Arg.Buckets = nullptr;
- Arg.NumBuckets = 0;
- Arg.NumNodes = 0;
-}
-
-FoldingSetImpl &FoldingSetImpl::operator=(FoldingSetImpl &&RHS) {
- free(Buckets); // This may be null if the set is in a moved-from state.
- Buckets = RHS.Buckets;
- NumBuckets = RHS.NumBuckets;
- NumNodes = RHS.NumNodes;
- RHS.Buckets = nullptr;
- RHS.NumBuckets = 0;
- RHS.NumNodes = 0;
- return *this;
-}
-
-FoldingSetImpl::~FoldingSetImpl() {
- free(Buckets);
-}
-
-void FoldingSetImpl::clear() {
- // Set all but the last bucket to null pointers.
- memset(Buckets, 0, NumBuckets*sizeof(void*));
-
- // Set the very last bucket to be a non-null "pointer".
- Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
-
- // Reset the node count to zero.
- NumNodes = 0;
-}
-
-void FoldingSetImpl::GrowBucketCount(unsigned NewBucketCount) {
- assert((NewBucketCount > NumBuckets) && "Can't shrink a folding set with GrowBucketCount");
- assert(isPowerOf2_32(NewBucketCount) && "Bad bucket count!");
- void **OldBuckets = Buckets;
- unsigned OldNumBuckets = NumBuckets;
- NumBuckets = NewBucketCount;
-
- // Clear out new buckets.
- Buckets = AllocateBuckets(NumBuckets);
- NumNodes = 0;
-
- // Walk the old buckets, rehashing nodes into their new place.
- FoldingSetNodeID TempID;
- for (unsigned i = 0; i != OldNumBuckets; ++i) {
- void *Probe = OldBuckets[i];
- if (!Probe) continue;
- while (Node *NodeInBucket = GetNextPtr(Probe)) {
- // Figure out the next link, remove NodeInBucket from the old link.
- Probe = NodeInBucket->getNextInBucket();
- NodeInBucket->SetNextInBucket(nullptr);
-
- // Insert the node into the new bucket, after recomputing the hash.
- InsertNode(NodeInBucket,
- GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
- Buckets, NumBuckets));
- TempID.clear();
- }
- }
-
- free(OldBuckets);
-}
-
-/// GrowHashTable - Double the size of the hash table and rehash everything.
-///
-void FoldingSetImpl::GrowHashTable() {
- GrowBucketCount(NumBuckets * 2);
-}
-
-void FoldingSetImpl::reserve(unsigned EltCount) {
- // This will give us somewhere between EltCount / 2 and
- // EltCount buckets. This puts us in the load factor
- // range of 1.0 - 2.0.
- if(EltCount < capacity())
- return;
- GrowBucketCount(PowerOf2Floor(EltCount));
-}
-
-/// FindNodeOrInsertPos - Look up the node specified by ID. If it exists,
-/// return it. If not, return the insertion token that will make insertion
-/// faster.
-FoldingSetImpl::Node
-*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
- void *&InsertPos) {
- unsigned IDHash = ID.ComputeHash();
- void **Bucket = GetBucketFor(IDHash, Buckets, NumBuckets);
- void *Probe = *Bucket;
-
- InsertPos = nullptr;
-
- FoldingSetNodeID TempID;
- while (Node *NodeInBucket = GetNextPtr(Probe)) {
- if (NodeEquals(NodeInBucket, ID, IDHash, TempID))
- return NodeInBucket;
- TempID.clear();
-
- Probe = NodeInBucket->getNextInBucket();
- }
-
- // Didn't find the node, return null with the bucket as the InsertPos.
- InsertPos = Bucket;
- return nullptr;
-}
-
-/// InsertNode - Insert the specified node into the folding set, knowing that it
-/// is not already in the map. InsertPos must be obtained from
-/// FindNodeOrInsertPos.
-void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
- assert(!N->getNextInBucket());
- // Do we need to grow the hashtable?
- if (NumNodes+1 > capacity()) {
- GrowHashTable();
- FoldingSetNodeID TempID;
- InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
- }
-
- ++NumNodes;
-
- /// The insert position is actually a bucket pointer.
- void **Bucket = static_cast<void**>(InsertPos);
-
- void *Next = *Bucket;
-
- // If this is the first insertion into this bucket, its next pointer will be
- // null. Pretend as if it pointed to itself, setting the low bit to indicate
- // that it is a pointer to the bucket.
- if (!Next)
- Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
-
- // Set the node's next pointer, and make the bucket point to the node.
- N->SetNextInBucket(Next);
- *Bucket = N;
-}
-
-/// RemoveNode - Remove a node from the folding set, returning true if one was
-/// removed or false if the node was not in the folding set.
-bool FoldingSetImpl::RemoveNode(Node *N) {
- // Because each bucket is a circular list, we don't need to compute N's hash
- // to remove it.
- void *Ptr = N->getNextInBucket();
- if (!Ptr) return false; // Not in folding set.
-
- --NumNodes;
- N->SetNextInBucket(nullptr);
-
- // Remember what N originally pointed to, either a bucket or another node.
- void *NodeNextPtr = Ptr;
-
- // Chase around the list until we find the node (or bucket) which points to N.
- while (true) {
- if (Node *NodeInBucket = GetNextPtr(Ptr)) {
- // Advance pointer.
- Ptr = NodeInBucket->getNextInBucket();
-
- // We found a node that points to N, change it to point to N's next node,
- // removing N from the list.
- if (Ptr == N) {
- NodeInBucket->SetNextInBucket(NodeNextPtr);
- return true;
- }
- } else {
- void **Bucket = GetBucketPtr(Ptr);
- Ptr = *Bucket;
-
- // If we found that the bucket points to N, update the bucket to point to
- // whatever is next.
- if (Ptr == N) {
- *Bucket = NodeNextPtr;
- return true;
- }
- }
- }
-}
-
-/// GetOrInsertNode - If there is an existing simple Node exactly
-/// equal to the specified node, return it. Otherwise, insert 'N' and it
-/// instead.
-FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) {
- FoldingSetNodeID ID;
- GetNodeProfile(N, ID);
- void *IP;
- if (Node *E = FindNodeOrInsertPos(ID, IP))
- return E;
- InsertNode(N, IP);
- return N;
-}
-
-//===----------------------------------------------------------------------===//
-// FoldingSetIteratorImpl Implementation
-
-FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
- // Skip to the first non-null non-self-cycle bucket.
- while (*Bucket != reinterpret_cast<void*>(-1) &&
- (!*Bucket || !GetNextPtr(*Bucket)))
- ++Bucket;
-
- NodePtr = static_cast<FoldingSetNode*>(*Bucket);
-}
-
-void FoldingSetIteratorImpl::advance() {
- // If there is another link within this bucket, go to it.
- void *Probe = NodePtr->getNextInBucket();
-
- if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
- NodePtr = NextNodeInBucket;
- else {
- // Otherwise, this is the last link in this bucket.
- void **Bucket = GetBucketPtr(Probe);
-
- // Skip to the next non-null non-self-cycle bucket.
- do {
- ++Bucket;
- } while (*Bucket != reinterpret_cast<void*>(-1) &&
- (!*Bucket || !GetNextPtr(*Bucket)));
-
- NodePtr = static_cast<FoldingSetNode*>(*Bucket);
- }
-}
-
-//===----------------------------------------------------------------------===//
-// FoldingSetBucketIteratorImpl Implementation
-
-FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
- Ptr = (!*Bucket || !GetNextPtr(*Bucket)) ? (void*) Bucket : *Bucket;
-}
