10e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===-- llvm/ADT/FoldingSet.h - Uniquing Hash Set ---------------*- C++ -*-===// 20e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 30e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// The LLVM Compiler Infrastructure 40e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 70e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 80e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===----------------------------------------------------------------------===// 90e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 100e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// This file defines a hash set that can be used to remove duplication of nodes 110e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// in a graph. This code was originally created by Chris Lattner for use with 120cf717d6b84a0b5fbc68b5e35cb19aa9300dac34Zhongxing Xu// SelectionDAGCSEMap, but was isolated to provide use across the llvm code set. 130e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey// 140e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===----------------------------------------------------------------------===// 150e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 160e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey#ifndef LLVM_ADT_FOLDINGSET_H 170e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey#define LLVM_ADT_FOLDINGSET_H 180e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 191f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 200e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey#include "llvm/ADT/SmallVector.h" 2127dba671c3f158a33c8cbdf5196a6fd16489be03Daniel Dunbar#include "llvm/ADT/StringRef.h" 220e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 230e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskeynamespace llvm { 24be2c4596cb562bbb216af2a0dd5c3b5c489e722cChris Lattner class APFloat; 25167b8bc24d4cc2789c682962b123877a73ad0568Dan Gohman class APInt; 26c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman class BumpPtrAllocator; 270e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 280e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// This folding set used for two purposes: 290e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 1. Given information about a node we want to create, look up the unique 300e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// instance of the node in the set. If the node already exists, return 310e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// it, otherwise return the bucket it should be inserted into. 320e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 2. Given a node that has already been created, remove it from the set. 333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman/// 340e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// This class is implemented as a single-link chained hash table, where the 350e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// "buckets" are actually the nodes themselves (the next pointer is in the 36c35595fd2ac733ff0c35a1e43992f59f35816411Duncan Sands/// node). The last node points back to the bucket to simplify node removal. 370e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 380e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// Any node that is to be included in the folding set must be a subclass of 390e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// FoldingSetNode. The node class must also define a Profile method used to 400e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// establish the unique bits of data for the node. The Profile method is 413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman/// passed a FoldingSetNodeID object which is used to gather the bits. Just 420e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// call one of the Add* functions defined in the FoldingSetImpl::NodeID class. 4318529f35151f18345519e38496ac72350ee15f38Jim Laskey/// NOTE: That the folding set does not own the nodes and it is the 4418529f35151f18345519e38496ac72350ee15f38Jim Laskey/// responsibility of the user to dispose of the nodes. 450e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 460e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// Eg. 470e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// class MyNode : public FoldingSetNode { 480e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// private: 490e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// std::string Name; 500e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// unsigned Value; 510e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// public: 520e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// MyNode(const char *N, unsigned V) : Name(N), Value(V) {} 530e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// ... 541d3b26ac023b519077811e55f3f9e56de9c2e6f7Dan Gohman/// void Profile(FoldingSetNodeID &ID) const { 550e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// ID.AddString(Name); 560e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// ID.AddInteger(Value); 5783fb63d5b3669aec8925af23907ca2b404a51f74Dan Gohman/// } 5883fb63d5b3669aec8925af23907ca2b404a51f74Dan Gohman/// ... 5983fb63d5b3669aec8925af23907ca2b404a51f74Dan Gohman/// }; 600e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 610e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// To define the folding set itself use the FoldingSet template; 620e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 630e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// Eg. 640e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// FoldingSet<MyNode> MyFoldingSet; 650e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman/// Four public methods are available to manipulate the folding set; 670e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 680e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 1) If you have an existing node that you want add to the set but unsure 690e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// that the node might already exist then call; 700e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 710e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// MyNode *M = MyFoldingSet.GetOrInsertNode(N); 720e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 730e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// If The result is equal to the input then the node has been inserted. 740e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// Otherwise, the result is the node existing in the folding set, and the 750e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// input can be discarded (use the result instead.) 760e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 770e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 2) If you are ready to construct a node but want to check if it already 780e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// exists, then call FindNodeOrInsertPos with a FoldingSetNodeID of the bits to 790e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// check; 800e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 810e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// FoldingSetNodeID ID; 820e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// ID.AddString(Name); 830e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// ID.AddInteger(Value); 840e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// void *InsertPoint; 850e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 860e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// MyNode *M = MyFoldingSet.FindNodeOrInsertPos(ID, InsertPoint); 870e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 880e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// If found then M with be non-NULL, else InsertPoint will point to where it 890e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// should be inserted using InsertNode. 900e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 9118529f35151f18345519e38496ac72350ee15f38Jim Laskey/// 3) If you get a NULL result from FindNodeOrInsertPos then you can as a new 920e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// node with FindNodeOrInsertPos; 930e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 940e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// InsertNode(N, InsertPoint); 950e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 960e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 4) Finally, if you want to remove a node from the folding set call; 970e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 980e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// bool WasRemoved = RemoveNode(N); 990e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// 10018529f35151f18345519e38496ac72350ee15f38Jim Laskey/// The result indicates whether the node existed in the folding set. 1013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1020a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenekclass FoldingSetNodeID; 1033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1040e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey//===----------------------------------------------------------------------===// 1050e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// FoldingSetImpl - Implements the folding set functionality. The main 1060e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// structure is an array of buckets. Each bucket is indexed by the hash of 1070e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// the nodes it contains. The bucket itself points to the nodes contained 1080e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// in the bucket via a singly linked list. The last node in the list points 1090e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey/// back to the bucket to facilitate node removal. 1103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman/// 1110e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskeyclass FoldingSetImpl { 1128092406e59e44633e45c3ec71a1a1d12ef0b926bTed Kremenekprotected: 11318529f35151f18345519e38496ac72350ee15f38Jim Laskey /// Buckets - Array of bucket chains. 11418529f35151f18345519e38496ac72350ee15f38Jim Laskey /// 1150e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void **Buckets; 1163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 11718529f35151f18345519e38496ac72350ee15f38Jim Laskey /// NumBuckets - Length of the Buckets array. Always a power of 2. 11818529f35151f18345519e38496ac72350ee15f38Jim Laskey /// 1190e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey unsigned NumBuckets; 1203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 121ea516cce65e7c9f1c49dd2e0634d73f89bb954a4Chris Lattner /// NumNodes - Number of nodes in the folding set. Growth occurs when NumNodes 12218529f35151f18345519e38496ac72350ee15f38Jim Laskey /// is greater than twice the number of buckets. 1230e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey unsigned NumNodes; 1243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1250e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskeypublic: 12681975f6dfd9d306d0ea7ce3ef22561c949de9af9Dan Gohman explicit FoldingSetImpl(unsigned Log2InitSize = 6); 1272f6d4c9766e920602326cfe26f5985077156d890Jim Laskey virtual ~FoldingSetImpl(); 1283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1290e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey //===--------------------------------------------------------------------===// 1300e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// Node - This class is used to maintain the singly linked bucket list in 1310e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// a folding set. 1320e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// 1330e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey class Node { 1340e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey private: 13518529f35151f18345519e38496ac72350ee15f38Jim Laskey // NextInFoldingSetBucket - next link in the bucket list. 13618529f35151f18345519e38496ac72350ee15f38Jim Laskey void *NextInFoldingSetBucket; 1373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1380e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey public: 1390e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 14018529f35151f18345519e38496ac72350ee15f38Jim Laskey Node() : NextInFoldingSetBucket(0) {} 1413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1420e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey // Accessors 14318529f35151f18345519e38496ac72350ee15f38Jim Laskey void *getNextInBucket() const { return NextInFoldingSetBucket; } 14418529f35151f18345519e38496ac72350ee15f38Jim Laskey void SetNextInBucket(void *N) { NextInFoldingSetBucket = N; } 1450e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey }; 1460e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 147535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman /// clear - Remove all nodes from the folding set. 148535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman void clear(); 149535de1a8c14fdfeb3912d3192accb58d9aa1e9e7Dan Gohman 1500e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// RemoveNode - Remove a node from the folding set, returning true if one 1510e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// was removed or false if the node was not in the folding set. 1520e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey bool RemoveNode(Node *N); 1533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1540e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// GetOrInsertNode - If there is an existing simple Node exactly 1550e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// equal to the specified node, return it. Otherwise, insert 'N' and return 1560e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// it instead. 1570e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey Node *GetOrInsertNode(Node *N); 1583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1590e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 1600e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// return it. If not, return the insertion token that will make insertion 1610e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// faster. 1620a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek Node *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos); 1633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1640e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// InsertNode - Insert the specified node into the folding set, knowing that 1653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman /// it is not already in the folding set. InsertPos must be obtained from 1660e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey /// FindNodeOrInsertPos. 1670e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey void InsertNode(Node *N, void *InsertPos); 1683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 169d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis /// InsertNode - Insert the specified node into the folding set, knowing that 170d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis /// it is not already in the folding set. 171d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis void InsertNode(Node *N) { 172d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis Node *Inserted = GetOrInsertNode(N); 173d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis (void)Inserted; 174d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis assert(Inserted == N && "Node already inserted!"); 175d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis } 176d6afb09a0021aea5789053cbe59fe7550915f6acArgyrios Kyrtzidis 17720b7907c1cb7074a2e6be5f534bb742752dd25d4Ted Kremenek /// size - Returns the number of nodes in the folding set. 17820b7907c1cb7074a2e6be5f534bb742752dd25d4Ted Kremenek unsigned size() const { return NumNodes; } 17955beb6ded8804a82e9e59017e596ae141ba381feDan Gohman 18055beb6ded8804a82e9e59017e596ae141ba381feDan Gohman /// empty - Returns true if there are no nodes in the folding set. 18155beb6ded8804a82e9e59017e596ae141ba381feDan Gohman bool empty() const { return NumNodes == 0; } 1823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18318529f35151f18345519e38496ac72350ee15f38Jim Laskeyprivate: 18418529f35151f18345519e38496ac72350ee15f38Jim Laskey 18518529f35151f18345519e38496ac72350ee15f38Jim Laskey /// GrowHashTable - Double the size of the hash table and rehash everything. 18618529f35151f18345519e38496ac72350ee15f38Jim Laskey /// 18718529f35151f18345519e38496ac72350ee15f38Jim Laskey void GrowHashTable(); 1883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18918529f35151f18345519e38496ac72350ee15f38Jim Laskeyprotected: 1900e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 19118529f35151f18345519e38496ac72350ee15f38Jim Laskey /// GetNodeProfile - Instantiations of the FoldingSet template implement 19218529f35151f18345519e38496ac72350ee15f38Jim Laskey /// this function to gather data bits for the given node. 1936616f7e2f147c2320973993cbfb241a82262b764Dan Gohman virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const = 0; 1943063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// NodeEquals - Instantiations of the FoldingSet template implement 1953063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// this function to compare the given node with the given ID. 196f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, 1973063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID) const=0; 198f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer /// ComputeNodeHash - Instantiations of the FoldingSet template implement 1993063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// this function to compute a hash value for the given node. 200f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const = 0; 20118529f35151f18345519e38496ac72350ee15f38Jim Laskey}; 2020e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 2031f801fa5ada9cb40fb97ae755c282e91af54a1bcTed Kremenek//===----------------------------------------------------------------------===// 2043063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2053063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T> struct FoldingSetTrait; 2063063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2073063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// DefaultFoldingSetTrait - This class provides default implementations 2083063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// for FoldingSetTrait implementations. 2093063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// 2103063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T> struct DefaultFoldingSetTrait { 2116311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner static void Profile(const T &X, FoldingSetNodeID &ID) { 2123063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman X.Profile(ID); 2133063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman } 2146311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner static void Profile(T &X, FoldingSetNodeID &ID) { 2153063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman X.Profile(ID); 2163063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman } 2173063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2183063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // Equals - Test if the profile for X would match ID, using TempID 2193063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // to compute a temporary ID if necessary. The default implementation 2203063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // just calls Profile and does a regular comparison. Implementations 2213063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // can override this to provide more efficient implementations. 222f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 2233063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID); 2243063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2253063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // ComputeHash - Compute a hash value for X, using TempID to 2263063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // compute a temporary ID if necessary. The default implementation 2273063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // just calls Profile and does a regular hash computation. 2283063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // Implementations can override this to provide more efficient 2293063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman // implementations. 2303063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID); 2313063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman}; 2323063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2331f801fa5ada9cb40fb97ae755c282e91af54a1bcTed Kremenek/// FoldingSetTrait - This trait class is used to define behavior of how 2340ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman/// to "profile" (in the FoldingSet parlance) an object of a given type. 2350ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman/// The default behavior is to invoke a 'Profile' method on an object, but 2360ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman/// through template specialization the behavior can be tailored for specific 2370ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman/// types. Combined with the FoldingSetNodeWrapper class, one can add objects 2380ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman/// to FoldingSets that were not originally designed to have that behavior. 2393063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T> struct FoldingSetTrait 2403063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman : public DefaultFoldingSetTrait<T> {}; 2413063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2423063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T, typename Ctx> struct ContextualFoldingSetTrait; 2433063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2443063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// DefaultContextualFoldingSetTrait - Like DefaultFoldingSetTrait, but 2453063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// for ContextualFoldingSets. 2463063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T, typename Ctx> 2473063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmanstruct DefaultContextualFoldingSetTrait { 2483063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman static void Profile(T &X, FoldingSetNodeID &ID, Ctx Context) { 249edce58fbd94fd8f274b34729c182fc156a2bda37John McCall X.Profile(ID, Context); 250edce58fbd94fd8f274b34729c182fc156a2bda37John McCall } 251f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer static inline bool Equals(T &X, const FoldingSetNodeID &ID, unsigned IDHash, 2523063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID, Ctx Context); 2533063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman static inline unsigned ComputeHash(T &X, FoldingSetNodeID &TempID, 2543063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman Ctx Context); 2551f801fa5ada9cb40fb97ae755c282e91af54a1bcTed Kremenek}; 2563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2573063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// ContextualFoldingSetTrait - Like FoldingSetTrait, but for 2583063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman/// ContextualFoldingSets. 2593063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T, typename Ctx> struct ContextualFoldingSetTrait 2603063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman : public DefaultContextualFoldingSetTrait<T, Ctx> {}; 2613063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2620a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek//===--------------------------------------------------------------------===// 263c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// FoldingSetNodeIDRef - This class describes a reference to an interned 264c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// FoldingSetNodeID, which can be a useful to store node id data rather 265c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// than using plain FoldingSetNodeIDs, since the 32-element SmallVector 266c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// is often much larger than necessary, and the possibility of heap 267c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman/// allocation means it requires a non-trivial destructor call. 268c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohmanclass FoldingSetNodeIDRef { 2696311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner const unsigned *Data; 270c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman size_t Size; 271c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohmanpublic: 272c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman FoldingSetNodeIDRef() : Data(0), Size(0) {} 2731878aba8e4753f82a8e7c7390e0adbeb0a393bb5Dan Gohman FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} 274c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman 2753063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, 2763063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// used to lookup the node in the FoldingSetImpl. 2773063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman unsigned ComputeHash() const; 2783063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2793063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman bool operator==(FoldingSetNodeIDRef) const; 2803063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 2810d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek /// Used to compare the "ordering" of two nodes as defined by the 2820d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek /// profiled bits and their ordering defined by memcmp(). 2830d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek bool operator<(FoldingSetNodeIDRef) const; 2840d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek 2851878aba8e4753f82a8e7c7390e0adbeb0a393bb5Dan Gohman const unsigned *getData() const { return Data; } 286c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman size_t getSize() const { return Size; } 287c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman}; 288c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman 289c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman//===--------------------------------------------------------------------===// 2900a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek/// FoldingSetNodeID - This class is used to gather all the unique data bits of 2910a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek/// a node. When all the bits are gathered this class is used to produce a 2923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman/// hash value for the node. 2930a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek/// 2940a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenekclass FoldingSetNodeID { 2950a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek /// Bits - Vector of all the data bits that make the node unique. 2960a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek /// Use a SmallVector to avoid a heap allocation in the common case. 2970a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek SmallVector<unsigned, 32> Bits; 2983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2990a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenekpublic: 3000a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek FoldingSetNodeID() {} 3013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 302c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman FoldingSetNodeID(FoldingSetNodeIDRef Ref) 303c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman : Bits(Ref.getData(), Ref.getData() + Ref.getSize()) {} 3043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3050a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek /// Add* - Add various data types to Bit data. 3060a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek /// 3070a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek void AddPointer(const void *Ptr); 3080a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek void AddInteger(signed I); 3090a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek void AddInteger(unsigned I); 31020cd13f54f2b1a6307016c47330045de13b140e2Dan Gohman void AddInteger(long I); 31120cd13f54f2b1a6307016c47330045de13b140e2Dan Gohman void AddInteger(unsigned long I); 31220cd13f54f2b1a6307016c47330045de13b140e2Dan Gohman void AddInteger(long long I); 31320cd13f54f2b1a6307016c47330045de13b140e2Dan Gohman void AddInteger(unsigned long long I); 3148bb332d45dd266b9678446cea5812371d8d3e8afTed Kremenek void AddBoolean(bool B) { AddInteger(B ? 1U : 0U); } 31527dba671c3f158a33c8cbdf5196a6fd16489be03Daniel Dunbar void AddString(StringRef String); 316e27c3ea2bcdabf1b8be87675c66a38c3ad0ac1f9Chris Lattner void AddNodeID(const FoldingSetNodeID &ID); 3173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3181f801fa5ada9cb40fb97ae755c282e91af54a1bcTed Kremenek template <typename T> 3196311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner inline void Add(const T &x) { FoldingSetTrait<T>::Profile(x, *this); } 3203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 321c899b33b830c360e53eb35440a1371542925414fTed Kremenek /// clear - Clear the accumulated profile, allowing this FoldingSetNodeID 3220ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman /// object to be used to compute a new profile. 323c899b33b830c360e53eb35440a1371542925414fTed Kremenek inline void clear() { Bits.clear(); } 3243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3250a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek /// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used 3260ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman /// to lookup the node in the FoldingSetImpl. 3270a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek unsigned ComputeHash() const; 3283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3290a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek /// operator== - Used to compare two nodes to each other. 3300a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek /// 3310a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek bool operator==(const FoldingSetNodeID &RHS) const; 3323063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman bool operator==(const FoldingSetNodeIDRef RHS) const; 333c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman 3340d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek /// Used to compare the "ordering" of two nodes as defined by the 3350d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek /// profiled bits and their ordering defined by memcmp(). 3360d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek bool operator<(const FoldingSetNodeID &RHS) const; 3370d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek bool operator<(const FoldingSetNodeIDRef RHS) const; 3380d651e0c9d47a459b91755ccf711119f5b085dc5Ted Kremenek 339c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman /// Intern - Copy this node's data to a memory region allocated from the 340c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman /// given allocator and return a FoldingSetNodeIDRef describing the 341c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman /// interned data. 342c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const; 3433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman}; 34418529f35151f18345519e38496ac72350ee15f38Jim Laskey 3450a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenek// Convenience type to hide the implementation of the folding set. 3460a3fecad0a4bf48a83eb7370a4d46880efdc6971Ted Kremenektypedef FoldingSetImpl::Node FoldingSetNode; 347116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnertemplate<class T> class FoldingSetIterator; 34826e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenektemplate<class T> class FoldingSetBucketIterator; 3493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3503063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman// Definitions of FoldingSetTrait and ContextualFoldingSetTrait functions, which 3513063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman// require the definition of FoldingSetNodeID. 3523063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T> 3533063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmaninline bool 3543063410e52a760584501b825dc6ffb4c52f4d93bDan GohmanDefaultFoldingSetTrait<T>::Equals(T &X, const FoldingSetNodeID &ID, 355f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer unsigned IDHash, FoldingSetNodeID &TempID) { 3563063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetTrait<T>::Profile(X, TempID); 3573063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman return TempID == ID; 3583063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman} 3593063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T> 3603063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmaninline unsigned 3613063410e52a760584501b825dc6ffb4c52f4d93bDan GohmanDefaultFoldingSetTrait<T>::ComputeHash(T &X, FoldingSetNodeID &TempID) { 3623063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetTrait<T>::Profile(X, TempID); 3633063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman return TempID.ComputeHash(); 3643063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman} 3653063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T, typename Ctx> 3663063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmaninline bool 3673063410e52a760584501b825dc6ffb4c52f4d93bDan GohmanDefaultContextualFoldingSetTrait<T, Ctx>::Equals(T &X, 3683063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman const FoldingSetNodeID &ID, 369f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer unsigned IDHash, 3703063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID, 3713063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman Ctx Context) { 3723063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 3733063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman return TempID == ID; 3743063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman} 3753063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmantemplate<typename T, typename Ctx> 3763063410e52a760584501b825dc6ffb4c52f4d93bDan Gohmaninline unsigned 3773063410e52a760584501b825dc6ffb4c52f4d93bDan GohmanDefaultContextualFoldingSetTrait<T, Ctx>::ComputeHash(T &X, 3783063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID, 3793063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman Ctx Context) { 3803063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman ContextualFoldingSetTrait<T, Ctx>::Profile(X, TempID, Context); 3813063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman return TempID.ComputeHash(); 3823063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman} 3833063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman 384a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek//===----------------------------------------------------------------------===// 38518529f35151f18345519e38496ac72350ee15f38Jim Laskey/// FoldingSet - This template class is used to instantiate a specialized 3863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman/// implementation of the folding set to the node class T. T must be a 38718529f35151f18345519e38496ac72350ee15f38Jim Laskey/// subclass of FoldingSetNode and implement a Profile function. 38818529f35151f18345519e38496ac72350ee15f38Jim Laskey/// 38918529f35151f18345519e38496ac72350ee15f38Jim Laskeytemplate<class T> class FoldingSet : public FoldingSetImpl { 39018529f35151f18345519e38496ac72350ee15f38Jim Laskeyprivate: 39132f3bd43dbf4082ed05478c6ef69727925ab1646Chris Lattner /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 39232f3bd43dbf4082ed05478c6ef69727925ab1646Chris Lattner /// way to convert nodes into a unique specifier. 3936616f7e2f147c2320973993cbfb241a82262b764Dan Gohman virtual void GetNodeProfile(Node *N, FoldingSetNodeID &ID) const { 39418529f35151f18345519e38496ac72350ee15f38Jim Laskey T *TN = static_cast<T *>(N); 3953063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetTrait<T>::Profile(*TN, ID); 3963063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman } 3973063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// NodeEquals - Instantiations may optionally provide a way to compare a 3983063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// node with a specified ID. 399f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer virtual bool NodeEquals(Node *N, const FoldingSetNodeID &ID, unsigned IDHash, 4003063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID) const { 4013063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman T *TN = static_cast<T *>(N); 402f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer return FoldingSetTrait<T>::Equals(*TN, ID, IDHash, TempID); 4033063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman } 404f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer /// ComputeNodeHash - Instantiations may optionally provide a way to compute a 4053063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman /// hash value directly from a node. 406f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer virtual unsigned ComputeNodeHash(Node *N, FoldingSetNodeID &TempID) const { 4073063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman T *TN = static_cast<T *>(N); 4083063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman return FoldingSetTrait<T>::ComputeHash(*TN, TempID); 40918529f35151f18345519e38496ac72350ee15f38Jim Laskey } 4103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 41118529f35151f18345519e38496ac72350ee15f38Jim Laskeypublic: 41281975f6dfd9d306d0ea7ce3ef22561c949de9af9Dan Gohman explicit FoldingSet(unsigned Log2InitSize = 6) 4131f67a99260917d33fefc6a7d863b0cd850a34431Jim Laskey : FoldingSetImpl(Log2InitSize) 4141f67a99260917d33fefc6a7d863b0cd850a34431Jim Laskey {} 4153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 416116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner typedef FoldingSetIterator<T> iterator; 417116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner iterator begin() { return iterator(Buckets); } 418116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner iterator end() { return iterator(Buckets+NumBuckets); } 419116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 420116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner typedef FoldingSetIterator<const T> const_iterator; 421116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner const_iterator begin() const { return const_iterator(Buckets); } 422116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 4231f67a99260917d33fefc6a7d863b0cd850a34431Jim Laskey 4243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman typedef FoldingSetBucketIterator<T> bucket_iterator; 42526e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek 42626e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek bucket_iterator bucket_begin(unsigned hash) { 42726e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 42826e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek } 4293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 43026e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek bucket_iterator bucket_end(unsigned hash) { 43126e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 43226e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek } 4333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 43418529f35151f18345519e38496ac72350ee15f38Jim Laskey /// GetOrInsertNode - If there is an existing simple Node exactly 43518529f35151f18345519e38496ac72350ee15f38Jim Laskey /// equal to the specified node, return it. Otherwise, insert 'N' and 43618529f35151f18345519e38496ac72350ee15f38Jim Laskey /// return it instead. 43718529f35151f18345519e38496ac72350ee15f38Jim Laskey T *GetOrInsertNode(Node *N) { 43818529f35151f18345519e38496ac72350ee15f38Jim Laskey return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 43918529f35151f18345519e38496ac72350ee15f38Jim Laskey } 4403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 44118529f35151f18345519e38496ac72350ee15f38Jim Laskey /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 44218529f35151f18345519e38496ac72350ee15f38Jim Laskey /// return it. If not, return the insertion token that will make insertion 44318529f35151f18345519e38496ac72350ee15f38Jim Laskey /// faster. 44418529f35151f18345519e38496ac72350ee15f38Jim Laskey T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 44532f3bd43dbf4082ed05478c6ef69727925ab1646Chris Lattner return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 44618529f35151f18345519e38496ac72350ee15f38Jim Laskey } 44718529f35151f18345519e38496ac72350ee15f38Jim Laskey}; 4480e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 449116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner//===----------------------------------------------------------------------===// 450edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// ContextualFoldingSet - This template class is a further refinement 451edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// of FoldingSet which provides a context argument when calling 452edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// Profile on its nodes. Currently, that argument is fixed at 453edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// initialization time. 454edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// 455edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// T must be a subclass of FoldingSetNode and implement a Profile 456edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// function with signature 457edce58fbd94fd8f274b34729c182fc156a2bda37John McCall/// void Profile(llvm::FoldingSetNodeID &, Ctx); 458edce58fbd94fd8f274b34729c182fc156a2bda37John McCalltemplate <class T, class Ctx> 459edce58fbd94fd8f274b34729c182fc156a2bda37John McCallclass ContextualFoldingSet : public FoldingSetImpl { 460edce58fbd94fd8f274b34729c182fc156a2bda37John McCall // Unfortunately, this can't derive from FoldingSet<T> because the 461edce58fbd94fd8f274b34729c182fc156a2bda37John McCall // construction vtable for FoldingSet<T> requires 462edce58fbd94fd8f274b34729c182fc156a2bda37John McCall // FoldingSet<T>::GetNodeProfile to be instantiated, which in turn 463edce58fbd94fd8f274b34729c182fc156a2bda37John McCall // requires a single-argument T::Profile(). 464edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 465edce58fbd94fd8f274b34729c182fc156a2bda37John McCallprivate: 466edce58fbd94fd8f274b34729c182fc156a2bda37John McCall Ctx Context; 467edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 468edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// GetNodeProfile - Each instantiatation of the FoldingSet needs to provide a 469edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// way to convert nodes into a unique specifier. 4706616f7e2f147c2320973993cbfb241a82262b764Dan Gohman virtual void GetNodeProfile(FoldingSetImpl::Node *N, 4716616f7e2f147c2320973993cbfb241a82262b764Dan Gohman FoldingSetNodeID &ID) const { 472edce58fbd94fd8f274b34729c182fc156a2bda37John McCall T *TN = static_cast<T *>(N); 4733063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman ContextualFoldingSetTrait<T, Ctx>::Profile(*TN, ID, Context); 4743063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman } 4753063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman virtual bool NodeEquals(FoldingSetImpl::Node *N, 476f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer const FoldingSetNodeID &ID, unsigned IDHash, 4773063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID) const { 4783063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman T *TN = static_cast<T *>(N); 479f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer return ContextualFoldingSetTrait<T, Ctx>::Equals(*TN, ID, IDHash, TempID, 480f7c3e5f05199e1202c86198e0827cac19c0f48b5Benjamin Kramer Context); 4813063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman } 4823063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman virtual unsigned ComputeNodeHash(FoldingSetImpl::Node *N, 4833063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman FoldingSetNodeID &TempID) const { 4843063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman T *TN = static_cast<T *>(N); 4853063410e52a760584501b825dc6ffb4c52f4d93bDan Gohman return ContextualFoldingSetTrait<T, Ctx>::ComputeHash(*TN, TempID, Context); 486edce58fbd94fd8f274b34729c182fc156a2bda37John McCall } 487edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 488edce58fbd94fd8f274b34729c182fc156a2bda37John McCallpublic: 489edce58fbd94fd8f274b34729c182fc156a2bda37John McCall explicit ContextualFoldingSet(Ctx Context, unsigned Log2InitSize = 6) 490edce58fbd94fd8f274b34729c182fc156a2bda37John McCall : FoldingSetImpl(Log2InitSize), Context(Context) 491edce58fbd94fd8f274b34729c182fc156a2bda37John McCall {} 492edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 493edce58fbd94fd8f274b34729c182fc156a2bda37John McCall Ctx getContext() const { return Context; } 494edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 495edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 496edce58fbd94fd8f274b34729c182fc156a2bda37John McCall typedef FoldingSetIterator<T> iterator; 497edce58fbd94fd8f274b34729c182fc156a2bda37John McCall iterator begin() { return iterator(Buckets); } 498edce58fbd94fd8f274b34729c182fc156a2bda37John McCall iterator end() { return iterator(Buckets+NumBuckets); } 499edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 500edce58fbd94fd8f274b34729c182fc156a2bda37John McCall typedef FoldingSetIterator<const T> const_iterator; 501edce58fbd94fd8f274b34729c182fc156a2bda37John McCall const_iterator begin() const { return const_iterator(Buckets); } 502edce58fbd94fd8f274b34729c182fc156a2bda37John McCall const_iterator end() const { return const_iterator(Buckets+NumBuckets); } 503edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 504edce58fbd94fd8f274b34729c182fc156a2bda37John McCall typedef FoldingSetBucketIterator<T> bucket_iterator; 505edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 506edce58fbd94fd8f274b34729c182fc156a2bda37John McCall bucket_iterator bucket_begin(unsigned hash) { 507edce58fbd94fd8f274b34729c182fc156a2bda37John McCall return bucket_iterator(Buckets + (hash & (NumBuckets-1))); 508edce58fbd94fd8f274b34729c182fc156a2bda37John McCall } 509edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 510edce58fbd94fd8f274b34729c182fc156a2bda37John McCall bucket_iterator bucket_end(unsigned hash) { 511edce58fbd94fd8f274b34729c182fc156a2bda37John McCall return bucket_iterator(Buckets + (hash & (NumBuckets-1)), true); 512edce58fbd94fd8f274b34729c182fc156a2bda37John McCall } 513edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 514edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// GetOrInsertNode - If there is an existing simple Node exactly 515edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// equal to the specified node, return it. Otherwise, insert 'N' 516edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// and return it instead. 517edce58fbd94fd8f274b34729c182fc156a2bda37John McCall T *GetOrInsertNode(Node *N) { 518edce58fbd94fd8f274b34729c182fc156a2bda37John McCall return static_cast<T *>(FoldingSetImpl::GetOrInsertNode(N)); 519edce58fbd94fd8f274b34729c182fc156a2bda37John McCall } 520edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 521edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// FindNodeOrInsertPos - Look up the node specified by ID. If it 522edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// exists, return it. If not, return the insertion token that will 523edce58fbd94fd8f274b34729c182fc156a2bda37John McCall /// make insertion faster. 524edce58fbd94fd8f274b34729c182fc156a2bda37John McCall T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 525edce58fbd94fd8f274b34729c182fc156a2bda37John McCall return static_cast<T *>(FoldingSetImpl::FindNodeOrInsertPos(ID, InsertPos)); 526edce58fbd94fd8f274b34729c182fc156a2bda37John McCall } 527edce58fbd94fd8f274b34729c182fc156a2bda37John McCall}; 528edce58fbd94fd8f274b34729c182fc156a2bda37John McCall 529edce58fbd94fd8f274b34729c182fc156a2bda37John McCall//===----------------------------------------------------------------------===// 530a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// FoldingSetVectorIterator - This implements an iterator for 531a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// FoldingSetVector. It is only necessary because FoldingSetIterator provides 532a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// a value_type of T, while the vector in FoldingSetVector exposes 533a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// a value_type of T*. Fortunately, FoldingSetIterator doesn't expose very 534a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// much besides operator* and operator->, so we just wrap the inner vector 535a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// iterator and perform the extra dereference. 536a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruthtemplate <class T, class VectorIteratorT> 537a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruthclass FoldingSetVectorIterator { 538a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth // Provide a typedef to workaround the lack of correct injected class name 539a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth // support in older GCCs. 540a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth typedef FoldingSetVectorIterator<T, VectorIteratorT> SelfT; 541a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 542a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth VectorIteratorT Iterator; 543a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 544a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruthpublic: 545a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth FoldingSetVectorIterator(VectorIteratorT I) : Iterator(I) {} 546a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 547a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth bool operator==(const SelfT &RHS) const { 548a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth return Iterator == RHS.Iterator; 549a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 550a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth bool operator!=(const SelfT &RHS) const { 551a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth return Iterator != RHS.Iterator; 552a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 553a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 554a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth T &operator*() const { return **Iterator; } 555a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 556a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth T *operator->() const { return *Iterator; } 557a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 558a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth inline SelfT &operator++() { 559a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth ++Iterator; 560a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth return *this; 561a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 562a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth SelfT operator++(int) { 563a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth SelfT tmp = *this; 564a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth ++*this; 565a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth return tmp; 566a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 567a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth}; 568a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 569a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth//===----------------------------------------------------------------------===// 570a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// FoldingSetVector - This template class combines a FoldingSet and a vector 571a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// to provide the interface of FoldingSet but with deterministic iteration 572a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// order based on the insertion order. T must be a subclass of FoldingSetNode 573a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth/// and implement a Profile function. 574a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruthtemplate <class T, class VectorT = SmallVector<T*, 8> > 575a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruthclass FoldingSetVector { 576a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth FoldingSet<T> Set; 577a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth VectorT Vector; 578a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 579a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruthpublic: 580a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth explicit FoldingSetVector(unsigned Log2InitSize = 6) 581a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth : Set(Log2InitSize) { 582a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 583a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 584a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth typedef FoldingSetVectorIterator<T, typename VectorT::iterator> iterator; 585a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth iterator begin() { return Vector.begin(); } 586a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth iterator end() { return Vector.end(); } 587a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 588a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth typedef FoldingSetVectorIterator<const T, typename VectorT::const_iterator> 589a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth const_iterator; 590a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth const_iterator begin() const { return Vector.begin(); } 591a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth const_iterator end() const { return Vector.end(); } 592a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 593a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// clear - Remove all nodes from the folding set. 594a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth void clear() { Set.clear(); Vector.clear(); } 595a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 596a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// FindNodeOrInsertPos - Look up the node specified by ID. If it exists, 597a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// return it. If not, return the insertion token that will make insertion 598a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// faster. 599a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth T *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos) { 600a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth return Set.FindNodeOrInsertPos(ID, InsertPos); 601a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 602a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 603a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// GetOrInsertNode - If there is an existing simple Node exactly 604a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// equal to the specified node, return it. Otherwise, insert 'N' and 605a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// return it instead. 606a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth T *GetOrInsertNode(T *N) { 607a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth T *Result = Set.GetOrInsertNode(N); 608a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth if (Result == N) Vector.push_back(N); 609a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth return Result; 610a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 611a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 612a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// InsertNode - Insert the specified node into the folding set, knowing that 613a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// it is not already in the folding set. InsertPos must be obtained from 614a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// FindNodeOrInsertPos. 615a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth void InsertNode(T *N, void *InsertPos) { 616a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth Set.InsertNode(N, InsertPos); 617a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth Vector.push_back(N); 618a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 619a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 620a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// InsertNode - Insert the specified node into the folding set, knowing that 621a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// it is not already in the folding set. 622a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth void InsertNode(T *N) { 623a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth Set.InsertNode(N); 624a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth Vector.push_back(N); 625a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth } 626a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 627a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// size - Returns the number of nodes in the folding set. 628a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth unsigned size() const { return Set.size(); } 629a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 630a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth /// empty - Returns true if there are no nodes in the folding set. 631a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth bool empty() const { return Set.empty(); } 632a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth}; 633a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth 634a83a6d3725a9a488e2d10c1f2af46d9c6d82958dChandler Carruth//===----------------------------------------------------------------------===// 635116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner/// FoldingSetIteratorImpl - This is the common iterator support shared by all 636116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner/// folding sets, which knows how to walk the folding set hash table. 637116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnerclass FoldingSetIteratorImpl { 638116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnerprotected: 639116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner FoldingSetNode *NodePtr; 640116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner FoldingSetIteratorImpl(void **Bucket); 641116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner void advance(); 6423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 643116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnerpublic: 644116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner bool operator==(const FoldingSetIteratorImpl &RHS) const { 645116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner return NodePtr == RHS.NodePtr; 646116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner } 647116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner bool operator!=(const FoldingSetIteratorImpl &RHS) const { 648116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner return NodePtr != RHS.NodePtr; 649116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner } 650116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner}; 651116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 652116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner 653116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnertemplate<class T> 654116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnerclass FoldingSetIterator : public FoldingSetIteratorImpl { 655116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattnerpublic: 6561002c0203450620594a85454c6a095ca94b87cb2Dan Gohman explicit FoldingSetIterator(void **Bucket) : FoldingSetIteratorImpl(Bucket) {} 6573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 658116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner T &operator*() const { 659116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner return *static_cast<T*>(NodePtr); 660116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner } 6613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 662116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner T *operator->() const { 663116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner return static_cast<T*>(NodePtr); 664116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner } 6653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6666311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner inline FoldingSetIterator &operator++() { // Preincrement 667116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner advance(); 668116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner return *this; 669116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner } 670116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner FoldingSetIterator operator++(int) { // Postincrement 671116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner FoldingSetIterator tmp = *this; ++*this; return tmp; 672116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner } 673116c3219df347f169b1bd24acca2d53ab0ae26ecChris Lattner}; 6743a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 675a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek//===----------------------------------------------------------------------===// 67626e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek/// FoldingSetBucketIteratorImpl - This is the common bucket iterator support 6770ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman/// shared by all folding sets, which knows how to walk a particular bucket 6780ba422ba6ebfb3fbcbac4f786ebc44136d5df3b2Dan Gohman/// of a folding set hash table. 6793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 68026e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenekclass FoldingSetBucketIteratorImpl { 68126e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenekprotected: 68226e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek void *Ptr; 68326e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek 6841002c0203450620594a85454c6a095ca94b87cb2Dan Gohman explicit FoldingSetBucketIteratorImpl(void **Bucket); 6853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 68626e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek FoldingSetBucketIteratorImpl(void **Bucket, bool) 687ccd95b5f9ceb4f022d29cd14173ccdf0333ff77bDan Gohman : Ptr(Bucket) {} 68826e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek 68926e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek void advance() { 69026e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek void *Probe = static_cast<FoldingSetNode*>(Ptr)->getNextInBucket(); 69126e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek uintptr_t x = reinterpret_cast<uintptr_t>(Probe) & ~0x1; 69226e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek Ptr = reinterpret_cast<void*>(x); 69326e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek } 6943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 69526e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenekpublic: 69626e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek bool operator==(const FoldingSetBucketIteratorImpl &RHS) const { 69726e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek return Ptr == RHS.Ptr; 69826e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek } 69926e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek bool operator!=(const FoldingSetBucketIteratorImpl &RHS) const { 70026e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek return Ptr != RHS.Ptr; 70126e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek } 70226e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek}; 7033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 70526e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenektemplate<class T> 70626e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenekclass FoldingSetBucketIterator : public FoldingSetBucketIteratorImpl { 70726e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenekpublic: 7083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman explicit FoldingSetBucketIterator(void **Bucket) : 70926e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek FoldingSetBucketIteratorImpl(Bucket) {} 7103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman FoldingSetBucketIterator(void **Bucket, bool) : 71226e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek FoldingSetBucketIteratorImpl(Bucket, true) {} 7133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7146311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner T &operator*() const { return *static_cast<T*>(Ptr); } 7156311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner T *operator->() const { return static_cast<T*>(Ptr); } 7163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7176311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner inline FoldingSetBucketIterator &operator++() { // Preincrement 71826e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek advance(); 71926e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek return *this; 7203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 72126e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek FoldingSetBucketIterator operator++(int) { // Postincrement 72226e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek FoldingSetBucketIterator tmp = *this; ++*this; return tmp; 72326e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek } 72426e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek}; 7253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 72626e3c445fc844b2f241dfdde9ce7e0602ba13cc4Ted Kremenek//===----------------------------------------------------------------------===// 727a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek/// FoldingSetNodeWrapper - This template class is used to "wrap" arbitrary 728a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek/// types in an enclosing object so that they can be inserted into FoldingSets. 729a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenektemplate <typename T> 730a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenekclass FoldingSetNodeWrapper : public FoldingSetNode { 731a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek T data; 732a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenekpublic: 7336311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner explicit FoldingSetNodeWrapper(const T &x) : data(x) {} 7347afe973add96f7b189b018239b5b9e43fe4a8dcfTed Kremenek virtual ~FoldingSetNodeWrapper() {} 7353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 736a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek template<typename A1> 7376311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner explicit FoldingSetNodeWrapper(const A1 &a1) 738a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek : data(a1) {} 7393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 740a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek template <typename A1, typename A2> 7416311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2) 742a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek : data(a1,a2) {} 7433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 744a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek template <typename A1, typename A2, typename A3> 7456311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3) 746a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek : data(a1,a2,a3) {} 7473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 748a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek template <typename A1, typename A2, typename A3, typename A4> 7496311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, 7506311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner const A4 &a4) 751a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek : data(a1,a2,a3,a4) {} 7523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 753a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek template <typename A1, typename A2, typename A3, typename A4, typename A5> 7546311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner explicit FoldingSetNodeWrapper(const A1 &a1, const A2 &a2, const A3 &a3, 7556311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner const A4 &a4, const A5 &a5) 756a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek : data(a1,a2,a3,a4,a5) {} 757a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek 7583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 759e27c3ea2bcdabf1b8be87675c66a38c3ad0ac1f9Chris Lattner void Profile(FoldingSetNodeID &ID) { FoldingSetTrait<T>::Profile(data, ID); } 760a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek 7616311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner T &getValue() { return data; } 7626311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner const T &getValue() const { return data; } 7637afe973add96f7b189b018239b5b9e43fe4a8dcfTed Kremenek 764a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek operator T&() { return data; } 765a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek operator const T&() const { return data; } 7663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman}; 7673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 768e1bf7fdcb4be19c556f4c789dd43864f5d13c5e4Ted Kremenek//===----------------------------------------------------------------------===// 769d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman/// FastFoldingSetNode - This is a subclass of FoldingSetNode which stores 770d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman/// a FoldingSetNodeID value rather than requiring the node to recompute it 771d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman/// each time it is needed. This trades space for speed (which can be 772d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman/// significant if the ID is long), and it also permits nodes to drop 773d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman/// information that would otherwise only be required for recomputing an ID. 774d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohmanclass FastFoldingSetNode : public FoldingSetNode { 775d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman FoldingSetNodeID FastID; 776d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohmanprotected: 777d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman explicit FastFoldingSetNode(const FoldingSetNodeID &ID) : FastID(ID) {} 778d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohmanpublic: 7796311a55b9dae82977c892ef9bda7c39f781ea564Chris Lattner void Profile(FoldingSetNodeID &ID) const { 780e27c3ea2bcdabf1b8be87675c66a38c3ad0ac1f9Chris Lattner ID.AddNodeID(FastID); 781e27c3ea2bcdabf1b8be87675c66a38c3ad0ac1f9Chris Lattner } 782d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman}; 783d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman 784d6a2aab53e3c4fcd53399cfa6f66d62913e53663Dan Gohman//===----------------------------------------------------------------------===// 785e1bf7fdcb4be19c556f4c789dd43864f5d13c5e4Ted Kremenek// Partial specializations of FoldingSetTrait. 786e1bf7fdcb4be19c556f4c789dd43864f5d13c5e4Ted Kremenek 787e1bf7fdcb4be19c556f4c789dd43864f5d13c5e4Ted Kremenektemplate<typename T> struct FoldingSetTrait<T*> { 788aea7689e622ae46e854d01d61bf8db80890e6074Zhongxing Xu static inline void Profile(T *X, FoldingSetNodeID &ID) { 789e1bf7fdcb4be19c556f4c789dd43864f5d13c5e4Ted Kremenek ID.AddPointer(X); 790e1bf7fdcb4be19c556f4c789dd43864f5d13c5e4Ted Kremenek } 791a753f703d1e532dbec5f89c6af834ccd72581ca9Ted Kremenek}; 7922f6d4c9766e920602326cfe26f5985077156d890Jim Laskey} // End of namespace llvm. 7930e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey 7940e5af195f6c54dbf5a24a1ec12ed2d0bd02f5b7fJim Laskey#endif 795