LLVM  13.0.0git
ImmutableSet.h
Go to the documentation of this file.
1 //===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the ImutAVLTree and ImmutableSet classes.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_IMMUTABLESET_H
14 #define LLVM_ADT_IMMUTABLESET_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/FoldingSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/iterator.h"
21 #include "llvm/Support/Allocator.h"
23 #include <cassert>
24 #include <cstdint>
25 #include <functional>
26 #include <iterator>
27 #include <new>
28 #include <vector>
29 
30 namespace llvm {
31 
32 //===----------------------------------------------------------------------===//
33 // Immutable AVL-Tree Definition.
34 //===----------------------------------------------------------------------===//
35 
36 template <typename ImutInfo> class ImutAVLFactory;
37 template <typename ImutInfo> class ImutIntervalAVLFactory;
38 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
39 template <typename ImutInfo> class ImutAVLTreeGenericIterator;
40 
41 template <typename ImutInfo >
42 class ImutAVLTree {
43 public:
44  using key_type_ref = typename ImutInfo::key_type_ref;
45  using value_type = typename ImutInfo::value_type;
46  using value_type_ref = typename ImutInfo::value_type_ref;
49 
50  friend class ImutAVLFactory<ImutInfo>;
51  friend class ImutIntervalAVLFactory<ImutInfo>;
52  friend class ImutAVLTreeGenericIterator<ImutInfo>;
53 
54  //===----------------------------------------------------===//
55  // Public Interface.
56  //===----------------------------------------------------===//
57 
58  /// Return a pointer to the left subtree. This value
59  /// is NULL if there is no left subtree.
60  ImutAVLTree *getLeft() const { return left; }
61 
62  /// Return a pointer to the right subtree. This value is
63  /// NULL if there is no right subtree.
64  ImutAVLTree *getRight() const { return right; }
65 
66  /// getHeight - Returns the height of the tree. A tree with no subtrees
67  /// has a height of 1.
68  unsigned getHeight() const { return height; }
69 
70  /// getValue - Returns the data value associated with the tree node.
71  const value_type& getValue() const { return value; }
72 
73  /// find - Finds the subtree associated with the specified key value.
74  /// This method returns NULL if no matching subtree is found.
76  ImutAVLTree *T = this;
77  while (T) {
78  key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
79  if (ImutInfo::isEqual(K,CurrentKey))
80  return T;
81  else if (ImutInfo::isLess(K,CurrentKey))
82  T = T->getLeft();
83  else
84  T = T->getRight();
85  }
86  return nullptr;
87  }
88 
89  /// getMaxElement - Find the subtree associated with the highest ranged
90  /// key value.
92  ImutAVLTree *T = this;
93  ImutAVLTree *Right = T->getRight();
94  while (Right) { T = Right; Right = T->getRight(); }
95  return T;
96  }
97 
98  /// size - Returns the number of nodes in the tree, which includes
99  /// both leaves and non-leaf nodes.
100  unsigned size() const {
101  unsigned n = 1;
102  if (const ImutAVLTree* L = getLeft())
103  n += L->size();
104  if (const ImutAVLTree* R = getRight())
105  n += R->size();
106  return n;
107  }
108 
109  /// begin - Returns an iterator that iterates over the nodes of the tree
110  /// in an inorder traversal. The returned iterator thus refers to the
111  /// the tree node with the minimum data element.
112  iterator begin() const { return iterator(this); }
113 
114  /// end - Returns an iterator for the tree that denotes the end of an
115  /// inorder traversal.
116  iterator end() const { return iterator(); }
117 
119  // Compare the keys.
120  if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),
121  ImutInfo::KeyOfValue(V)))
122  return false;
123 
124  // Also compare the data values.
125  if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),
126  ImutInfo::DataOfValue(V)))
127  return false;
128 
129  return true;
130  }
131 
132  bool isElementEqual(const ImutAVLTree* RHS) const {
133  return isElementEqual(RHS->getValue());
134  }
135 
136  /// isEqual - Compares two trees for structural equality and returns true
137  /// if they are equal. This worst case performance of this operation is
138  // linear in the sizes of the trees.
139  bool isEqual(const ImutAVLTree& RHS) const {
140  if (&RHS == this)
141  return true;
142 
143  iterator LItr = begin(), LEnd = end();
144  iterator RItr = RHS.begin(), REnd = RHS.end();
145 
146  while (LItr != LEnd && RItr != REnd) {
147  if (&*LItr == &*RItr) {
148  LItr.skipSubTree();
149  RItr.skipSubTree();
150  continue;
151  }
152 
153  if (!LItr->isElementEqual(&*RItr))
154  return false;
155 
156  ++LItr;
157  ++RItr;
158  }
159 
160  return LItr == LEnd && RItr == REnd;
161  }
162 
163  /// isNotEqual - Compares two trees for structural inequality. Performance
164  /// is the same is isEqual.
165  bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
166 
167  /// contains - Returns true if this tree contains a subtree (node) that
168  /// has an data element that matches the specified key. Complexity
169  /// is logarithmic in the size of the tree.
170  bool contains(key_type_ref K) { return (bool) find(K); }
171 
172  /// foreach - A member template the accepts invokes operator() on a functor
173  /// object (specified by Callback) for every node/subtree in the tree.
174  /// Nodes are visited using an inorder traversal.
175  template <typename Callback>
176  void foreach(Callback& C) {
177  if (ImutAVLTree* L = getLeft())
178  L->foreach(C);
179 
180  C(value);
181 
182  if (ImutAVLTree* R = getRight())
183  R->foreach(C);
184  }
185 
186  /// validateTree - A utility method that checks that the balancing and
187  /// ordering invariants of the tree are satisfied. It is a recursive
188  /// method that returns the height of the tree, which is then consumed
189  /// by the enclosing validateTree call. External callers should ignore the
190  /// return value. An invalid tree will cause an assertion to fire in
191  /// a debug build.
192  unsigned validateTree() const {
193  unsigned HL = getLeft() ? getLeft()->validateTree() : 0;
194  unsigned HR = getRight() ? getRight()->validateTree() : 0;
195  (void) HL;
196  (void) HR;
197 
198  assert(getHeight() == ( HL > HR ? HL : HR ) + 1
199  && "Height calculation wrong");
200 
201  assert((HL > HR ? HL-HR : HR-HL) <= 2
202  && "Balancing invariant violated");
203 
204  assert((!getLeft() ||
205  ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
206  ImutInfo::KeyOfValue(getValue()))) &&
207  "Value in left child is not less that current value");
208 
209  assert((!getRight() ||
210  ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
211  ImutInfo::KeyOfValue(getRight()->getValue()))) &&
212  "Current value is not less that value of right child");
213 
214  return getHeight();
215  }
216 
217  //===----------------------------------------------------===//
218  // Internal values.
219  //===----------------------------------------------------===//
220 
221 private:
222  Factory *factory;
223  ImutAVLTree *left;
225  ImutAVLTree *prev = nullptr;
226  ImutAVLTree *next = nullptr;
227 
228  unsigned height : 28;
229  bool IsMutable : 1;
230  bool IsDigestCached : 1;
231  bool IsCanonicalized : 1;
232 
233  value_type value;
234  uint32_t digest = 0;
235  uint32_t refCount = 0;
236 
237  //===----------------------------------------------------===//
238  // Internal methods (node manipulation; used by Factory).
239  //===----------------------------------------------------===//
240 
241 private:
242  /// ImutAVLTree - Internal constructor that is only called by
243  /// ImutAVLFactory.
245  unsigned height)
246  : factory(f), left(l), right(r), height(height), IsMutable(true),
247  IsDigestCached(false), IsCanonicalized(false), value(v)
248  {
249  if (left) left->retain();
250  if (right) right->retain();
251  }
252 
253  /// isMutable - Returns true if the left and right subtree references
254  /// (as well as height) can be changed. If this method returns false,
255  /// the tree is truly immutable. Trees returned from an ImutAVLFactory
256  /// object should always have this method return true. Further, if this
257  /// method returns false for an instance of ImutAVLTree, all subtrees
258  /// will also have this method return false. The converse is not true.
259  bool isMutable() const { return IsMutable; }
260 
261  /// hasCachedDigest - Returns true if the digest for this tree is cached.
262  /// This can only be true if the tree is immutable.
263  bool hasCachedDigest() const { return IsDigestCached; }
264 
265  //===----------------------------------------------------===//
266  // Mutating operations. A tree root can be manipulated as
267  // long as its reference has not "escaped" from internal
268  // methods of a factory object (see below). When a tree
269  // pointer is externally viewable by client code, the
270  // internal "mutable bit" is cleared to mark the tree
271  // immutable. Note that a tree that still has its mutable
272  // bit set may have children (subtrees) that are themselves
273  // immutable.
274  //===----------------------------------------------------===//
275 
276  /// markImmutable - Clears the mutable flag for a tree. After this happens,
277  /// it is an error to call setLeft(), setRight(), and setHeight().
278  void markImmutable() {
279  assert(isMutable() && "Mutable flag already removed.");
280  IsMutable = false;
281  }
282 
283  /// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
284  void markedCachedDigest() {
285  assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
286  IsDigestCached = true;
287  }
288 
289  /// setHeight - Changes the height of the tree. Used internally by
290  /// ImutAVLFactory.
291  void setHeight(unsigned h) {
292  assert(isMutable() && "Only a mutable tree can have its height changed.");
293  height = h;
294  }
295 
296  static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
297  value_type_ref V) {
298  uint32_t digest = 0;
299 
300  if (L)
301  digest += L->computeDigest();
302 
303  // Compute digest of stored data.
304  FoldingSetNodeID ID;
305  ImutInfo::Profile(ID,V);
306  digest += ID.ComputeHash();
307 
308  if (R)
309  digest += R->computeDigest();
310 
311  return digest;
312  }
313 
314  uint32_t computeDigest() {
315  // Check the lowest bit to determine if digest has actually been
316  // pre-computed.
317  if (hasCachedDigest())
318  return digest;
319 
320  uint32_t X = computeDigest(getLeft(), getRight(), getValue());
321  digest = X;
322  markedCachedDigest();
323  return X;
324  }
325 
326  //===----------------------------------------------------===//
327  // Reference count operations.
328  //===----------------------------------------------------===//
329 
330 public:
331  void retain() { ++refCount; }
332 
333  void release() {
334  assert(refCount > 0);
335  if (--refCount == 0)
336  destroy();
337  }
338 
339  void destroy() {
340  if (left)
341  left->release();
342  if (right)
343  right->release();
344  if (IsCanonicalized) {
345  if (next)
346  next->prev = prev;
347 
348  if (prev)
349  prev->next = next;
350  else
351  factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
352  }
353 
354  // We need to clear the mutability bit in case we are
355  // destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
356  IsMutable = false;
357  factory->freeNodes.push_back(this);
358  }
359 };
360 
361 template <typename ImutInfo>
363  static void retain(ImutAVLTree<ImutInfo> *Tree) { Tree->retain(); }
364  static void release(ImutAVLTree<ImutInfo> *Tree) { Tree->release(); }
365 };
366 
367 //===----------------------------------------------------------------------===//
368 // Immutable AVL-Tree Factory class.
369 //===----------------------------------------------------------------------===//
370 
371 template <typename ImutInfo >
372 class ImutAVLFactory {
373  friend class ImutAVLTree<ImutInfo>;
374 
376  using value_type_ref = typename TreeTy::value_type_ref;
377  using key_type_ref = typename TreeTy::key_type_ref;
379 
380  CacheTy Cache;
381  uintptr_t Allocator;
382  std::vector<TreeTy*> createdNodes;
383  std::vector<TreeTy*> freeNodes;
384 
385  bool ownsAllocator() const {
386  return (Allocator & 0x1) == 0;
387  }
388 
389  BumpPtrAllocator& getAllocator() const {
390  return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
391  }
392 
393  //===--------------------------------------------------===//
394  // Public interface.
395  //===--------------------------------------------------===//
396 
397 public:
399  : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
400 
402  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
403 
405  if (ownsAllocator()) delete &getAllocator();
406  }
407 
408  TreeTy* add(TreeTy* T, value_type_ref V) {
409  T = add_internal(V,T);
410  markImmutable(T);
411  recoverNodes();
412  return T;
413  }
414 
415  TreeTy* remove(TreeTy* T, key_type_ref V) {
416  T = remove_internal(V,T);
417  markImmutable(T);
418  recoverNodes();
419  return T;
420  }
421 
422  TreeTy* getEmptyTree() const { return nullptr; }
423 
424 protected:
425  //===--------------------------------------------------===//
426  // A bunch of quick helper functions used for reasoning
427  // about the properties of trees and their children.
428  // These have succinct names so that the balancing code
429  // is as terse (and readable) as possible.
430  //===--------------------------------------------------===//
431 
432  bool isEmpty(TreeTy* T) const { return !T; }
433  unsigned getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }
434  TreeTy* getLeft(TreeTy* T) const { return T->getLeft(); }
435  TreeTy* getRight(TreeTy* T) const { return T->getRight(); }
436  value_type_ref getValue(TreeTy* T) const { return T->value; }
437 
438  // Make sure the index is not the Tombstone or Entry key of the DenseMap.
439  static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
440 
441  unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
442  unsigned hl = getHeight(L);
443  unsigned hr = getHeight(R);
444  return (hl > hr ? hl : hr) + 1;
445  }
446 
448  typename TreeTy::iterator& TI,
449  typename TreeTy::iterator& TE) {
450  typename TreeTy::iterator I = T->begin(), E = T->end();
451  for ( ; I!=E ; ++I, ++TI) {
452  if (TI == TE || !I->isElementEqual(&*TI))
453  return false;
454  }
455  return true;
456  }
457 
458  //===--------------------------------------------------===//
459  // "createNode" is used to generate new tree roots that link
460  // to other trees. The function may also simply move links
461  // in an existing root if that root is still marked mutable.
462  // This is necessary because otherwise our balancing code
463  // would leak memory as it would create nodes that are
464  // then discarded later before the finished tree is
465  // returned to the caller.
466  //===--------------------------------------------------===//
467 
468  TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {
469  BumpPtrAllocator& A = getAllocator();
470  TreeTy* T;
471  if (!freeNodes.empty()) {
472  T = freeNodes.back();
473  freeNodes.pop_back();
474  assert(T != L);
475  assert(T != R);
476  } else {
477  T = (TreeTy*) A.Allocate<TreeTy>();
478  }
479  new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
480  createdNodes.push_back(T);
481  return T;
482  }
483 
484  TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
485  return createNode(newLeft, getValue(oldTree), newRight);
486  }
487 
488  void recoverNodes() {
489  for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
490  TreeTy *N = createdNodes[i];
491  if (N->isMutable() && N->refCount == 0)
492  N->destroy();
493  }
494  createdNodes.clear();
495  }
496 
497  /// balanceTree - Used by add_internal and remove_internal to
498  /// balance a newly created tree.
499  TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {
500  unsigned hl = getHeight(L);
501  unsigned hr = getHeight(R);
502 
503  if (hl > hr + 2) {
504  assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
505 
506  TreeTy *LL = getLeft(L);
507  TreeTy *LR = getRight(L);
508 
509  if (getHeight(LL) >= getHeight(LR))
510  return createNode(LL, L, createNode(LR,V,R));
511 
512  assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1");
513 
514  TreeTy *LRL = getLeft(LR);
515  TreeTy *LRR = getRight(LR);
516 
517  return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
518  }
519 
520  if (hr > hl + 2) {
521  assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
522 
523  TreeTy *RL = getLeft(R);
524  TreeTy *RR = getRight(R);
525 
526  if (getHeight(RR) >= getHeight(RL))
527  return createNode(createNode(L,V,RL), R, RR);
528 
529  assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1");
530 
531  TreeTy *RLL = getLeft(RL);
532  TreeTy *RLR = getRight(RL);
533 
534  return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
535  }
536 
537  return createNode(L,V,R);
538  }
539 
540  /// add_internal - Creates a new tree that includes the specified
541  /// data and the data from the original tree. If the original tree
542  /// already contained the data item, the original tree is returned.
543  TreeTy* add_internal(value_type_ref V, TreeTy* T) {
544  if (isEmpty(T))
545  return createNode(T, V, T);
546  assert(!T->isMutable());
547 
548  key_type_ref K = ImutInfo::KeyOfValue(V);
549  key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
550 
551  if (ImutInfo::isEqual(K,KCurrent))
552  return createNode(getLeft(T), V, getRight(T));
553  else if (ImutInfo::isLess(K,KCurrent))
555  else
557  }
558 
559  /// remove_internal - Creates a new tree that includes all the data
560  /// from the original tree except the specified data. If the
561  /// specified data did not exist in the original tree, the original
562  /// tree is returned.
563  TreeTy* remove_internal(key_type_ref K, TreeTy* T) {
564  if (isEmpty(T))
565  return T;
566 
567  assert(!T->isMutable());
568 
569  key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));
570 
571  if (ImutInfo::isEqual(K,KCurrent)) {
572  return combineTrees(getLeft(T), getRight(T));
573  } else if (ImutInfo::isLess(K,KCurrent)) {
574  return balanceTree(remove_internal(K, getLeft(T)),
575  getValue(T), getRight(T));
576  } else {
577  return balanceTree(getLeft(T), getValue(T),
578  remove_internal(K, getRight(T)));
579  }
580  }
581 
583  if (isEmpty(L))
584  return R;
585  if (isEmpty(R))
586  return L;
587  TreeTy* OldNode;
588  TreeTy* newRight = removeMinBinding(R,OldNode);
589  return balanceTree(L, getValue(OldNode), newRight);
590  }
591 
592  TreeTy* removeMinBinding(TreeTy* T, TreeTy*& Noderemoved) {
593  assert(!isEmpty(T));
594  if (isEmpty(getLeft(T))) {
595  Noderemoved = T;
596  return getRight(T);
597  }
598  return balanceTree(removeMinBinding(getLeft(T), Noderemoved),
599  getValue(T), getRight(T));
600  }
601 
602  /// markImmutable - Clears the mutable bits of a root and all of its
603  /// descendants.
605  if (!T || !T->isMutable())
606  return;
607  T->markImmutable();
610  }
611 
612 public:
614  if (!TNew)
615  return nullptr;
616 
617  if (TNew->IsCanonicalized)
618  return TNew;
619 
620  // Search the hashtable for another tree with the same digest, and
621  // if find a collision compare those trees by their contents.
622  unsigned digest = TNew->computeDigest();
623  TreeTy *&entry = Cache[maskCacheIndex(digest)];
624  do {
625  if (!entry)
626  break;
627  for (TreeTy *T = entry ; T != nullptr; T = T->next) {
628  // Compare the Contents('T') with Contents('TNew')
629  typename TreeTy::iterator TI = T->begin(), TE = T->end();
630  if (!compareTreeWithSection(TNew, TI, TE))
631  continue;
632  if (TI != TE)
633  continue; // T has more contents than TNew.
634  // Trees did match! Return 'T'.
635  if (TNew->refCount == 0)
636  TNew->destroy();
637  return T;
638  }
639  entry->prev = TNew;
640  TNew->next = entry;
641  }
642  while (false);
643 
644  entry = TNew;
645  TNew->IsCanonicalized = true;
646  return TNew;
647  }
648 };
649 
650 //===----------------------------------------------------------------------===//
651 // Immutable AVL-Tree Iterators.
652 //===----------------------------------------------------------------------===//
653 
654 template <typename ImutInfo>
655 class ImutAVLTreeGenericIterator
656  : public std::iterator<std::bidirectional_iterator_tag,
657  ImutAVLTree<ImutInfo>> {
658  SmallVector<uintptr_t,20> stack;
659 
660 public:
662  Flags=0x3 };
663 
665 
666  ImutAVLTreeGenericIterator() = default;
668  if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
669  }
670 
671  TreeTy &operator*() const {
672  assert(!stack.empty());
673  return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
674  }
675  TreeTy *operator->() const { return &*this; }
676 
677  uintptr_t getVisitState() const {
678  assert(!stack.empty());
679  return stack.back() & Flags;
680  }
681 
682  bool atEnd() const { return stack.empty(); }
683 
684  bool atBeginning() const {
685  return stack.size() == 1 && getVisitState() == VisitedNone;
686  }
687 
688  void skipToParent() {
689  assert(!stack.empty());
690  stack.pop_back();
691  if (stack.empty())
692  return;
693  switch (getVisitState()) {
694  case VisitedNone:
695  stack.back() |= VisitedLeft;
696  break;
697  case VisitedLeft:
698  stack.back() |= VisitedRight;
699  break;
700  default:
701  llvm_unreachable("Unreachable.");
702  }
703  }
704 
706  return stack == x.stack;
707  }
708 
710  return !(*this == x);
711  }
712 
714  assert(!stack.empty());
715  TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
716  assert(Current);
717  switch (getVisitState()) {
718  case VisitedNone:
719  if (TreeTy* L = Current->getLeft())
720  stack.push_back(reinterpret_cast<uintptr_t>(L));
721  else
722  stack.back() |= VisitedLeft;
723  break;
724  case VisitedLeft:
725  if (TreeTy* R = Current->getRight())
726  stack.push_back(reinterpret_cast<uintptr_t>(R));
727  else
728  stack.back() |= VisitedRight;
729  break;
730  case VisitedRight:
731  skipToParent();
732  break;
733  default:
734  llvm_unreachable("Unreachable.");
735  }
736  return *this;
737  }
738 
740  assert(!stack.empty());
741  TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
742  assert(Current);
743  switch (getVisitState()) {
744  case VisitedNone:
745  stack.pop_back();
746  break;
747  case VisitedLeft:
748  stack.back() &= ~Flags; // Set state to "VisitedNone."
749  if (TreeTy* L = Current->getLeft())
750  stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
751  break;
752  case VisitedRight:
753  stack.back() &= ~Flags;
754  stack.back() |= VisitedLeft;
755  if (TreeTy* R = Current->getRight())
756  stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
757  break;
758  default:
759  llvm_unreachable("Unreachable.");
760  }
761  return *this;
762  }
763 };
764 
765 template <typename ImutInfo>
766 class ImutAVLTreeInOrderIterator
767  : public std::iterator<std::bidirectional_iterator_tag,
768  ImutAVLTree<ImutInfo>> {
769  using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>;
770 
771  InternalIteratorTy InternalItr;
772 
773 public:
775 
776  ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
777  if (Root)
778  ++*this; // Advance to first element.
779  }
780 
781  ImutAVLTreeInOrderIterator() : InternalItr() {}
782 
784  return InternalItr == x.InternalItr;
785  }
786 
788  return !(*this == x);
789  }
790 
791  TreeTy &operator*() const { return *InternalItr; }
792  TreeTy *operator->() const { return &*InternalItr; }
793 
795  do ++InternalItr;
796  while (!InternalItr.atEnd() &&
797  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
798 
799  return *this;
800  }
801 
803  do --InternalItr;
804  while (!InternalItr.atBeginning() &&
805  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
806 
807  return *this;
808  }
809 
810  void skipSubTree() {
811  InternalItr.skipToParent();
812 
813  while (!InternalItr.atEnd() &&
814  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
815  ++InternalItr;
816  }
817 };
818 
819 /// Generic iterator that wraps a T::TreeTy::iterator and exposes
820 /// iterator::getValue() on dereference.
821 template <typename T>
824  ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
825  typename std::iterator_traits<
826  typename T::TreeTy::iterator>::iterator_category,
827  const typename T::value_type> {
828  ImutAVLValueIterator() = default;
829  explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
831 
832  typename ImutAVLValueIterator::reference operator*() const {
833  return this->I->getValue();
834  }
835 };
836 
837 //===----------------------------------------------------------------------===//
838 // Trait classes for Profile information.
839 //===----------------------------------------------------------------------===//
840 
841 /// Generic profile template. The default behavior is to invoke the
842 /// profile method of an object. Specializations for primitive integers
843 /// and generic handling of pointers is done below.
844 template <typename T>
846  using value_type = const T;
847  using value_type_ref = const T&;
848 
851  }
852 };
853 
854 /// Profile traits for integers.
855 template <typename T>
857  using value_type = const T;
858  using value_type_ref = const T&;
859 
861  ID.AddInteger(X);
862  }
863 };
864 
865 #define PROFILE_INTEGER_INFO(X)\
866 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
867 
869 PROFILE_INTEGER_INFO(unsigned char)
871 PROFILE_INTEGER_INFO(unsigned short)
872 PROFILE_INTEGER_INFO(unsigned)
873 PROFILE_INTEGER_INFO(signed)
875 PROFILE_INTEGER_INFO(unsigned long)
876 PROFILE_INTEGER_INFO(long long)
877 PROFILE_INTEGER_INFO(unsigned long long)
878 
879 #undef PROFILE_INTEGER_INFO
880 
881 /// Profile traits for booleans.
882 template <>
883 struct ImutProfileInfo<bool> {
884  using value_type = const bool;
885  using value_type_ref = const bool&;
886 
888  ID.AddBoolean(X);
889  }
890 };
891 
892 /// Generic profile trait for pointer types. We treat pointers as
893 /// references to unique objects.
894 template <typename T>
895 struct ImutProfileInfo<T*> {
896  using value_type = const T*;
898 
900  ID.AddPointer(X);
901  }
902 };
903 
904 //===----------------------------------------------------------------------===//
905 // Trait classes that contain element comparison operators and type
906 // definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
907 // inherit from the profile traits (ImutProfileInfo) to include operations
908 // for element profiling.
909 //===----------------------------------------------------------------------===//
910 
911 /// ImutContainerInfo - Generic definition of comparison operations for
912 /// elements of immutable containers that defaults to using
913 /// std::equal_to<> and std::less<> to perform comparison of elements.
914 template <typename T>
915 struct ImutContainerInfo : public ImutProfileInfo<T> {
920  using data_type = bool;
921  using data_type_ref = bool;
922 
924  static data_type_ref DataOfValue(value_type_ref) { return true; }
925 
926  static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
927  return std::equal_to<key_type>()(LHS,RHS);
928  }
929 
930  static bool isLess(key_type_ref LHS, key_type_ref RHS) {
931  return std::less<key_type>()(LHS,RHS);
932  }
933 
934  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
935 };
936 
937 /// ImutContainerInfo - Specialization for pointer values to treat pointers
938 /// as references to unique objects. Pointers are thus compared by
939 /// their addresses.
940 template <typename T>
946  using data_type = bool;
947  using data_type_ref = bool;
948 
950  static data_type_ref DataOfValue(value_type_ref) { return true; }
951 
952  static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; }
953 
954  static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; }
955 
956  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
957 };
958 
959 //===----------------------------------------------------------------------===//
960 // Immutable Set
961 //===----------------------------------------------------------------------===//
962 
963 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
965 public:
966  using value_type = typename ValInfo::value_type;
967  using value_type_ref = typename ValInfo::value_type_ref;
969 
970 private:
972 
973 public:
974  /// Constructs a set from a pointer to a tree root. In general one
975  /// should use a Factory object to create sets instead of directly
976  /// invoking the constructor, but there are cases where make this
977  /// constructor public is useful.
978  explicit ImmutableSet(TreeTy *R) : Root(R) {}
979 
980  class Factory {
981  typename TreeTy::Factory F;
982  const bool Canonicalize;
983 
984  public:
985  Factory(bool canonicalize = true)
986  : Canonicalize(canonicalize) {}
987 
988  Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
989  : F(Alloc), Canonicalize(canonicalize) {}
990 
991  Factory(const Factory& RHS) = delete;
992  void operator=(const Factory& RHS) = delete;
993 
994  /// getEmptySet - Returns an immutable set that contains no elements.
996  return ImmutableSet(F.getEmptyTree());
997  }
998 
999  /// add - Creates a new immutable set that contains all of the values
1000  /// of the original set with the addition of the specified value. If
1001  /// the original set already included the value, then the original set is
1002  /// returned and no memory is allocated. The time and space complexity
1003  /// of this operation is logarithmic in the size of the original set.
1004  /// The memory allocated to represent the set is released when the
1005  /// factory object that created the set is destroyed.
1007  TreeTy *NewT = F.add(Old.Root.get(), V);
1008  return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1009  }
1010 
1011  /// remove - Creates a new immutable set that contains all of the values
1012  /// of the original set with the exception of the specified value. If
1013  /// the original set did not contain the value, the original set is
1014  /// returned and no memory is allocated. The time and space complexity
1015  /// of this operation is logarithmic in the size of the original set.
1016  /// The memory allocated to represent the set is released when the
1017  /// factory object that created the set is destroyed.
1019  TreeTy *NewT = F.remove(Old.Root.get(), V);
1020  return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1021  }
1022 
1023  BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
1024 
1025  typename TreeTy::Factory *getTreeFactory() const {
1026  return const_cast<typename TreeTy::Factory *>(&F);
1027  }
1028  };
1029 
1030  friend class Factory;
1031 
1032  /// Returns true if the set contains the specified value.
1033  bool contains(value_type_ref V) const {
1034  return Root ? Root->contains(V) : false;
1035  }
1036 
1037  bool operator==(const ImmutableSet &RHS) const {
1038  return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
1039  }
1040 
1041  bool operator!=(const ImmutableSet &RHS) const {
1042  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
1043  : Root != RHS.Root;
1044  }
1045 
1047  if (Root) { Root->retain(); }
1048  return Root.get();
1049  }
1050 
1051  TreeTy *getRootWithoutRetain() const { return Root.get(); }
1052 
1053  /// isEmpty - Return true if the set contains no elements.
1054  bool isEmpty() const { return !Root; }
1055 
1056  /// isSingleton - Return true if the set contains exactly one element.
1057  /// This method runs in constant time.
1058  bool isSingleton() const { return getHeight() == 1; }
1059 
1060  template <typename Callback>
1061  void foreach(Callback& C) { if (Root) Root->foreach(C); }
1062 
1063  template <typename Callback>
1064  void foreach() { if (Root) { Callback C; Root->foreach(C); } }
1065 
1066  //===--------------------------------------------------===//
1067  // Iterators.
1068  //===--------------------------------------------------===//
1069 
1071 
1072  iterator begin() const { return iterator(Root.get()); }
1073  iterator end() const { return iterator(); }
1074 
1075  //===--------------------------------------------------===//
1076  // Utility methods.
1077  //===--------------------------------------------------===//
1078 
1079  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1080 
1081  static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
1082  ID.AddPointer(S.Root.get());
1083  }
1084 
1085  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1086 
1087  //===--------------------------------------------------===//
1088  // For testing.
1089  //===--------------------------------------------------===//
1090 
1091  void validateTree() const { if (Root) Root->validateTree(); }
1092 };
1093 
1094 // NOTE: This may some day replace the current ImmutableSet.
1095 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
1097 public:
1098  using value_type = typename ValInfo::value_type;
1099  using value_type_ref = typename ValInfo::value_type_ref;
1101  using FactoryTy = typename TreeTy::Factory;
1102 
1103 private:
1105  FactoryTy *Factory;
1106 
1107 public:
1108  /// Constructs a set from a pointer to a tree root. In general one
1109  /// should use a Factory object to create sets instead of directly
1110  /// invoking the constructor, but there are cases where make this
1111  /// constructor public is useful.
1112  ImmutableSetRef(TreeTy *R, FactoryTy *F) : Root(R), Factory(F) {}
1113 
1115  return ImmutableSetRef(0, F);
1116  }
1117 
1119  return ImmutableSetRef(Factory->add(Root.get(), V), Factory);
1120  }
1121 
1123  return ImmutableSetRef(Factory->remove(Root.get(), V), Factory);
1124  }
1125 
1126  /// Returns true if the set contains the specified value.
1127  bool contains(value_type_ref V) const {
1128  return Root ? Root->contains(V) : false;
1129  }
1130 
1131  ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
1132  return ImmutableSet<ValT>(
1133  canonicalize ? Factory->getCanonicalTree(Root.get()) : Root.get());
1134  }
1135 
1136  TreeTy *getRootWithoutRetain() const { return Root.get(); }
1137 
1138  bool operator==(const ImmutableSetRef &RHS) const {
1139  return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
1140  }
1141 
1142  bool operator!=(const ImmutableSetRef &RHS) const {
1143  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
1144  : Root != RHS.Root;
1145  }
1146 
1147  /// isEmpty - Return true if the set contains no elements.
1148  bool isEmpty() const { return !Root; }
1149 
1150  /// isSingleton - Return true if the set contains exactly one element.
1151  /// This method runs in constant time.
1152  bool isSingleton() const { return getHeight() == 1; }
1153 
1154  //===--------------------------------------------------===//
1155  // Iterators.
1156  //===--------------------------------------------------===//
1157 
1159 
1160  iterator begin() const { return iterator(Root.get()); }
1161  iterator end() const { return iterator(); }
1162 
1163  //===--------------------------------------------------===//
1164  // Utility methods.
1165  //===--------------------------------------------------===//
1166 
1167  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1168 
1169  static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
1170  ID.AddPointer(S.Root.get());
1171  }
1172 
1173  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1174 
1175  //===--------------------------------------------------===//
1176  // For testing.
1177  //===--------------------------------------------------===//
1178 
1179  void validateTree() const { if (Root) Root->validateTree(); }
1180 };
1181 
1182 } // end namespace llvm
1183 
1184 #endif // LLVM_ADT_IMMUTABLESET_H
llvm::ImutAVLTree::getLeft
ImutAVLTree * getLeft() const
Return a pointer to the left subtree.
Definition: ImmutableSet.h:60
i
i
Definition: README.txt:29
llvm::ImutIntervalAVLFactory
Definition: ImmutableSet.h:37
llvm::ImmutableSet::isEmpty
bool isEmpty() const
isEmpty - Return true if the set contains no elements.
Definition: ImmutableSet.h:1054
llvm::IntrusiveRefCntPtr::get
T * get() const
Definition: IntrusiveRefCntPtr.h:195
llvm::ImmutableSetRef::Profile
static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S)
Definition: ImmutableSet.h:1169
llvm::ImmutableSet::Factory::add
LLVM_NODISCARD ImmutableSet add(ImmutableSet Old, value_type_ref V)
add - Creates a new immutable set that contains all of the values of the original set with the additi...
Definition: ImmutableSet.h:1006
llvm::ImmutableSetRef::begin
iterator begin() const
Definition: ImmutableSet.h:1160
right
the custom lowered code happens to be right
Definition: README-SSE.txt:480
llvm::ImutAVLTreeGenericIterator::atEnd
bool atEnd() const
Definition: ImmutableSet.h:682
llvm::ImutAVLTree::validateTree
unsigned validateTree() const
validateTree - A utility method that checks that the balancing and ordering invariants of the tree ar...
Definition: ImmutableSet.h:192
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::ImmutableSet::getRootWithoutRetain
TreeTy * getRootWithoutRetain() const
Definition: ImmutableSet.h:1051
llvm::ImmutableSet::isSingleton
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
Definition: ImmutableSet.h:1058
llvm::ImutProfileInfo< bool >::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:887
llvm::ImutAVLFactory::getLeft
TreeTy * getLeft(TreeTy *T) const
Definition: ImmutableSet.h:434
llvm::ImutContainerInfo::KeyOfValue
static key_type_ref KeyOfValue(value_type_ref D)
Definition: ImmutableSet.h:923
llvm::ImutAVLTree::getMaxElement
ImutAVLTree * getMaxElement()
getMaxElement - Find the subtree associated with the highest ranged key value.
Definition: ImmutableSet.h:91
llvm::ImutAVLFactory::~ImutAVLFactory
~ImutAVLFactory()
Definition: ImmutableSet.h:404
llvm::ImutContainerInfo< T * >::data_type_ref
bool data_type_ref
Definition: ImmutableSet.h:947
llvm::ImutAVLTreeInOrderIterator::ImutAVLTreeInOrderIterator
ImutAVLTreeInOrderIterator(const TreeTy *Root)
Definition: ImmutableSet.h:776
llvm::ImutContainerInfo< T * >::isEqual
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:952
llvm::ImutAVLValueIterator::operator*
ImutAVLValueIterator::reference operator*() const
Definition: ImmutableSet.h:832
llvm::ImutAVLFactory::recoverNodes
void recoverNodes()
Definition: ImmutableSet.h:488
llvm::ImmutableSet::Factory::getTreeFactory
TreeTy::Factory * getTreeFactory() const
Definition: ImmutableSet.h:1025
llvm::ImutAVLFactory::isEmpty
bool isEmpty(TreeTy *T) const
Definition: ImmutableSet.h:432
llvm::ImutContainerInfo::value_type
typename ImutProfileInfo< T >::value_type value_type
Definition: ImmutableSet.h:916
llvm::ImutAVLTree::isNotEqual
bool isNotEqual(const ImutAVLTree &RHS) const
isNotEqual - Compares two trees for structural inequality.
Definition: ImmutableSet.h:165
llvm::ImutAVLFactory::getHeight
unsigned getHeight(TreeTy *T) const
Definition: ImmutableSet.h:433
llvm::ImmutableSetRef::contains
bool contains(value_type_ref V) const
Returns true if the set contains the specified value.
Definition: ImmutableSet.h:1127
llvm::iterator_adaptor_base< ImutAVLValueIterator< T >, T::TreeTy::iterator, std::iterator_traits< T::TreeTy::iterator >::iterator_category, const T::value_type >::I
T::TreeTy::iterator I
Definition: iterator.h:213
llvm::ImutAVLTree::find
ImutAVLTree * find(key_type_ref K)
find - Finds the subtree associated with the specified key value.
Definition: ImmutableSet.h:75
ErrorHandling.h
Allocator.h
llvm::ImutAVLTreeInOrderIterator::operator==
bool operator==(const ImutAVLTreeInOrderIterator &x) const
Definition: ImmutableSet.h:783
llvm::ImutAVLValueIterator
Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference.
Definition: ImmutableSet.h:822
llvm::ImutAVLFactory::combineTrees
TreeTy * combineTrees(TreeTy *L, TreeTy *R)
Definition: ImmutableSet.h:582
llvm::ImutAVLFactory::getEmptyTree
TreeTy * getEmptyTree() const
Definition: ImmutableSet.h:422
llvm::ImmutableSetRef::operator!=
bool operator!=(const ImmutableSetRef &RHS) const
Definition: ImmutableSet.h:1142
Right
Vector Shift Left Right
Definition: README_P9.txt:118
llvm::ImutAVLTreeGenericIterator::getVisitState
uintptr_t getVisitState() const
Definition: ImmutableSet.h:677
llvm::ImutAVLTree::retain
void retain()
Definition: ImmutableSet.h:331
DenseMap.h
llvm::ImutContainerInfo::isEqual
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:926
llvm::ImutAVLTreeGenericIterator::ImutAVLTreeGenericIterator
ImutAVLTreeGenericIterator()=default
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:207
llvm::ImmutableSet::Factory::getEmptySet
ImmutableSet getEmptySet()
getEmptySet - Returns an immutable set that contains no elements.
Definition: ImmutableSet.h:995
llvm::ImutAVLTree::size
unsigned size() const
size - Returns the number of nodes in the tree, which includes both leaves and non-leaf nodes.
Definition: ImmutableSet.h:100
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::ImutAVLFactory::markImmutable
void markImmutable(TreeTy *T)
markImmutable - Clears the mutable bits of a root and all of its descendants.
Definition: ImmutableSet.h:604
llvm::ImutAVLTreeGenericIterator::VisitedNone
@ VisitedNone
Definition: ImmutableSet.h:661
llvm::ImutContainerInfo< T * >::isDataEqual
static bool isDataEqual(data_type_ref, data_type_ref)
Definition: ImmutableSet.h:956
IntrusiveRefCntPtr.h
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
llvm::ImutAVLTree::end
iterator end() const
end - Returns an iterator for the tree that denotes the end of an inorder traversal.
Definition: ImmutableSet.h:116
llvm::ImutProfileInfo< T * >::value_type_ref
value_type value_type_ref
Definition: ImmutableSet.h:897
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::ImutAVLTreeInOrderIterator::operator!=
bool operator!=(const ImutAVLTreeInOrderIterator &x) const
Definition: ImmutableSet.h:787
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:129
llvm::ImutContainerInfo::data_type_ref
bool data_type_ref
Definition: ImmutableSet.h:921
llvm::ImutAVLFactory::incrementHeight
unsigned incrementHeight(TreeTy *L, TreeTy *R) const
Definition: ImmutableSet.h:441
llvm::ImutContainerInfo::data_type
bool data_type
Definition: ImmutableSet.h:920
llvm::ImutContainerInfo::DataOfValue
static data_type_ref DataOfValue(value_type_ref)
Definition: ImmutableSet.h:924
llvm::ImutContainerInfo::value_type_ref
typename ImutProfileInfo< T >::value_type_ref value_type_ref
Definition: ImmutableSet.h:917
f
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ImutContainerInfo< T * >::key_type
value_type key_type
Definition: ImmutableSet.h:944
llvm::ImutAVLTreeGenericIterator::operator++
ImutAVLTreeGenericIterator & operator++()
Definition: ImmutableSet.h:713
llvm::ImmutableSetRef::remove
ImmutableSetRef remove(value_type_ref V)
Definition: ImmutableSet.h:1122
llvm::ImutAVLFactory::ImutAVLFactory
ImutAVLFactory(BumpPtrAllocator &Alloc)
Definition: ImmutableSet.h:401
llvm::ImutAVLTree::contains
bool contains(key_type_ref K)
contains - Returns true if this tree contains a subtree (node) that has an data element that matches ...
Definition: ImmutableSet.h:170
llvm::ImutAVLTree::getHeight
unsigned getHeight() const
getHeight - Returns the height of the tree.
Definition: ImmutableSet.h:68
l
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
Definition: README.txt:100
false
Definition: StackSlotColoring.cpp:142
llvm::ImutProfileInfo
Generic profile template.
Definition: ImmutableSet.h:845
llvm::ImmutableSetRef::value_type
typename ValInfo::value_type value_type
Definition: ImmutableSet.h:1098
llvm::ImutAVLFactory::getCanonicalTree
TreeTy * getCanonicalTree(TreeTy *TNew)
Definition: ImmutableSet.h:613
llvm::ImmutableSet::ImmutableSet
ImmutableSet(TreeTy *R)
Constructs a set from a pointer to a tree root.
Definition: ImmutableSet.h:978
llvm::ImutContainerInfo< T * >::isLess
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:954
llvm::ImutAVLFactory::removeMinBinding
TreeTy * removeMinBinding(TreeTy *T, TreeTy *&Noderemoved)
Definition: ImmutableSet.h:592
llvm::ImutAVLTree::begin
iterator begin() const
begin - Returns an iterator that iterates over the nodes of the tree in an inorder traversal.
Definition: ImmutableSet.h:112
llvm::ImutAVLTreeGenericIterator::VisitedLeft
@ VisitedLeft
Definition: ImmutableSet.h:661
llvm::ImutAVLTreeGenericIterator::VisitFlag
VisitFlag
Definition: ImmutableSet.h:661
llvm::IntrusiveRefCntPtrInfo< ImutAVLTree< ImutInfo > >::retain
static void retain(ImutAVLTree< ImutInfo > *Tree)
Definition: ImmutableSet.h:363
llvm::ImutAVLTreeGenericIterator::VisitedRight
@ VisitedRight
Definition: ImmutableSet.h:661
llvm::ImutAVLFactory
Definition: ImmutableSet.h:36
llvm::ImutProfileInfo::value_type_ref
const T & value_type_ref
Definition: ImmutableSet.h:847
llvm::ImutProfileInteger
Profile traits for integers.
Definition: ImmutableSet.h:856
llvm::ImutAVLTreeInOrderIterator::operator*
TreeTy & operator*() const
Definition: ImmutableSet.h:791
llvm::ImutContainerInfo< T * >::KeyOfValue
static key_type_ref KeyOfValue(value_type_ref D)
Definition: ImmutableSet.h:949
llvm::ImutAVLValueIterator::ImutAVLValueIterator
ImutAVLValueIterator(typename T::TreeTy *Tree)
Definition: ImmutableSet.h:829
llvm::ImutProfileInfo< bool >::value_type_ref
const bool & value_type_ref
Definition: ImmutableSet.h:885
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::ImmutableSet::begin
iterator begin() const
Definition: ImmutableSet.h:1072
llvm::ImutAVLTree::isElementEqual
bool isElementEqual(const ImutAVLTree *RHS) const
Definition: ImmutableSet.h:132
llvm::ImmutableSet::Profile
static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S)
Definition: ImmutableSet.h:1081
llvm::ImutAVLTree::getValue
const value_type & getValue() const
getValue - Returns the data value associated with the tree node.
Definition: ImmutableSet.h:71
llvm::ImmutableSet::Factory::remove
LLVM_NODISCARD ImmutableSet remove(ImmutableSet Old, value_type_ref V)
remove - Creates a new immutable set that contains all of the values of the original set with the exc...
Definition: ImmutableSet.h:1018
llvm::ImmutableSetRef::value_type_ref
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableSet.h:1099
llvm::ImutContainerInfo::key_type
value_type key_type
Definition: ImmutableSet.h:918
llvm::ImmutableSet::contains
bool contains(value_type_ref V) const
Returns true if the set contains the specified value.
Definition: ImmutableSet.h:1033
llvm::ImutContainerInfo::isDataEqual
static bool isDataEqual(data_type_ref, data_type_ref)
Definition: ImmutableSet.h:934
llvm::ImmutableSet::Factory::Factory
Factory(bool canonicalize=true)
Definition: ImmutableSet.h:985
llvm::ImmutableSet::end
iterator end() const
Definition: ImmutableSet.h:1073
llvm::ImutAVLTree::getRight
ImutAVLTree * getRight() const
Return a pointer to the right subtree.
Definition: ImmutableSet.h:64
llvm::ImutAVLTree::release
void release()
Definition: ImmutableSet.h:333
llvm::ImmutableSetRef::asImmutableSet
ImmutableSet< ValT > asImmutableSet(bool canonicalize=true) const
Definition: ImmutableSet.h:1131
llvm::ImmutableSet::Factory::operator=
void operator=(const Factory &RHS)=delete
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ImutContainerInfo< T * >::data_type
bool data_type
Definition: ImmutableSet.h:946
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::ImutAVLTreeGenericIterator
Definition: ImmutableSet.h:39
llvm::DenseMap< unsigned, TreeTy * >
llvm::ImutAVLFactory::getRight
TreeTy * getRight(TreeTy *T) const
Definition: ImmutableSet.h:435
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ImutAVLTreeGenericIterator::skipToParent
void skipToParent()
Definition: ImmutableSet.h:688
llvm::ImutAVLFactory::remove_internal
TreeTy * remove_internal(key_type_ref K, TreeTy *T)
remove_internal - Creates a new tree that includes all the data from the original tree except the spe...
Definition: ImmutableSet.h:563
llvm::ImmutableSetRef::getEmptySet
static ImmutableSetRef getEmptySet(FactoryTy *F)
Definition: ImmutableSet.h:1114
llvm::ImutProfileInfo::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:849
llvm::ImutAVLFactory::add
TreeTy * add(TreeTy *T, value_type_ref V)
Definition: ImmutableSet.h:408
llvm::ImmutableSet::operator==
bool operator==(const ImmutableSet &RHS) const
Definition: ImmutableSet.h:1037
llvm::ImutAVLTree::iterator
ImutAVLTreeInOrderIterator< ImutInfo > iterator
Definition: ImmutableSet.h:48
llvm::ImutAVLTree::isElementEqual
bool isElementEqual(value_type_ref V) const
Definition: ImmutableSet.h:118
llvm::ImmutableSet::Factory::Factory
Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)
Definition: ImmutableSet.h:988
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ImmutableSetRef
Definition: ImmutableSet.h:1096
llvm::ImutAVLTree::isEqual
bool isEqual(const ImutAVLTree &RHS) const
isEqual - Compares two trees for structural equality and returns true if they are equal.
Definition: ImmutableSet.h:139
llvm::ImutContainerInfo::isLess
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:930
llvm::ImutProfileInfo< bool >::value_type
const bool value_type
Definition: ImmutableSet.h:884
llvm::ImutAVLFactory::maskCacheIndex
static unsigned maskCacheIndex(unsigned I)
Definition: ImmutableSet.h:439
llvm::ImutAVLFactory::balanceTree
TreeTy * balanceTree(TreeTy *L, value_type_ref V, TreeTy *R)
balanceTree - Used by add_internal and remove_internal to balance a newly created tree.
Definition: ImmutableSet.h:499
llvm::ImutProfileInfo< T * >::value_type
const T * value_type
Definition: ImmutableSet.h:896
llvm::ImutAVLTreeGenericIterator::operator==
bool operator==(const ImutAVLTreeGenericIterator &x) const
Definition: ImmutableSet.h:705
llvm::ImmutableSetRef::operator==
bool operator==(const ImmutableSetRef &RHS) const
Definition: ImmutableSet.h:1138
llvm::ImmutableSet::value_type_ref
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableSet.h:967
llvm::ImmutableSet::Factory::getAllocator
BumpPtrAllocator & getAllocator()
Definition: ImmutableSet.h:1023
llvm::ImutAVLTreeGenericIterator::operator*
TreeTy & operator*() const
Definition: ImmutableSet.h:671
llvm::DefaultFoldingSetTrait::Profile
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:229
llvm::ImutAVLTreeInOrderIterator::operator->
TreeTy * operator->() const
Definition: ImmutableSet.h:792
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
A
* A
Definition: README_ALTIVEC.txt:89
uint32_t
llvm::ImutAVLTreeGenericIterator::atBeginning
bool atBeginning() const
Definition: ImmutableSet.h:684
llvm::ImmutableSet
Definition: ImmutableSet.h:964
llvm::IntrusiveRefCntPtrInfo
Class you can specialize to provide custom retain/release functionality for a type.
Definition: IntrusiveRefCntPtr.h:152
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::IntrusiveRefCntPtrInfo< ImutAVLTree< ImutInfo > >::release
static void release(ImutAVLTree< ImutInfo > *Tree)
Definition: ImmutableSet.h:364
PROFILE_INTEGER_INFO
#define PROFILE_INTEGER_INFO(X)
Definition: ImmutableSet.h:865
llvm::ImutProfileInfo< T * >
Generic profile trait for pointer types.
Definition: ImmutableSet.h:895
llvm::ImutAVLTreeGenericIterator::Flags
@ Flags
Definition: ImmutableSet.h:662
llvm::ImutAVLTree::value_type
typename ImutInfo::value_type value_type
Definition: ImmutableSet.h:45
llvm::ImutProfileInteger::value_type_ref
const T & value_type_ref
Definition: ImmutableSet.h:858
llvm::ImutAVLTree::key_type_ref
typename ImutInfo::key_type_ref key_type_ref
Definition: ImmutableSet.h:44
FoldingSet.h
llvm::ImutProfileInfo::value_type
const T value_type
Definition: ImmutableSet.h:846
llvm::ImmutableSet::getRoot
TreeTy * getRoot()
Definition: ImmutableSet.h:1046
llvm::ImmutableSet::getHeight
unsigned getHeight() const
Definition: ImmutableSet.h:1079
llvm::ImutAVLTreeInOrderIterator::operator--
ImutAVLTreeInOrderIterator & operator--()
Definition: ImmutableSet.h:802
llvm::ImmutableSet::Factory
Definition: ImmutableSet.h:980
llvm::ImmutableSet::operator!=
bool operator!=(const ImmutableSet &RHS) const
Definition: ImmutableSet.h:1041
llvm::ImmutableSetRef::isSingleton
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
Definition: ImmutableSet.h:1152
llvm::ImutContainerInfo< T * >::key_type_ref
value_type_ref key_type_ref
Definition: ImmutableSet.h:945
llvm::ImmutableSet::iterator
ImutAVLValueIterator< ImmutableSet > iterator
Definition: ImmutableSet.h:1070
llvm::ImmutableSetRef::validateTree
void validateTree() const
Definition: ImmutableSet.h:1179
llvm::ImutAVLTreeGenericIterator::ImutAVLTreeGenericIterator
ImutAVLTreeGenericIterator(const TreeTy *Root)
Definition: ImmutableSet.h:667
llvm::ImutAVLTree::value_type_ref
typename ImutInfo::value_type_ref value_type_ref
Definition: ImmutableSet.h:46
llvm::ImutAVLTreeInOrderIterator::operator++
ImutAVLTreeInOrderIterator & operator++()
Definition: ImmutableSet.h:794
llvm::ImutAVLTreeInOrderIterator::ImutAVLTreeInOrderIterator
ImutAVLTreeInOrderIterator()
Definition: ImmutableSet.h:781
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:160
x
TODO unsigned x
Definition: README.txt:10
llvm::ImmutableSetRef::getHeight
unsigned getHeight() const
Definition: ImmutableSet.h:1167
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1920
llvm::ImutAVLTree::foreach
void foreach(Callback &C)
foreach - A member template the accepts invokes operator() on a functor object (specified by Callback...
Definition: ImmutableSet.h:176
llvm::ImutAVLTreeInOrderIterator::skipSubTree
void skipSubTree()
Definition: ImmutableSet.h:810
llvm::ImmutableSetRef::isEmpty
bool isEmpty() const
isEmpty - Return true if the set contains no elements.
Definition: ImmutableSet.h:1148
llvm::ImmutableSet::validateTree
void validateTree() const
Definition: ImmutableSet.h:1091
llvm::ImutAVLFactory::ImutAVLFactory
ImutAVLFactory()
Definition: ImmutableSet.h:398
llvm::ImutAVLFactory::createNode
TreeTy * createNode(TreeTy *newLeft, TreeTy *oldTree, TreeTy *newRight)
Definition: ImmutableSet.h:484
llvm::ImutContainerInfo::key_type_ref
value_type_ref key_type_ref
Definition: ImmutableSet.h:919
llvm::ImmutableSetRef::ImmutableSetRef
ImmutableSetRef(TreeTy *R, FactoryTy *F)
Constructs a set from a pointer to a tree root.
Definition: ImmutableSet.h:1112
llvm::ImutAVLFactory::compareTreeWithSection
static bool compareTreeWithSection(TreeTy *T, typename TreeTy::iterator &TI, typename TreeTy::iterator &TE)
Definition: ImmutableSet.h:447
SmallVector.h
llvm::ImutAVLTreeInOrderIterator
Definition: ImmutableSet.h:38
llvm::ImutProfileInfo< T * >::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:899
llvm::ImmutableSet::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableSet.h:1085
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
llvm::ImutAVLTree::destroy
void destroy()
Definition: ImmutableSet.h:339
N
#define N
llvm::ImutContainerInfo< T * >::DataOfValue
static data_type_ref DataOfValue(value_type_ref)
Definition: ImmutableSet.h:950
llvm::ImmutableSetRef::getRootWithoutRetain
TreeTy * getRootWithoutRetain() const
Definition: ImmutableSet.h:1136
stack
S is passed via registers r2 But gcc stores them to the stack
Definition: README.txt:189
llvm::ImutAVLTreeGenericIterator::operator->
TreeTy * operator->() const
Definition: ImmutableSet.h:675
llvm::ImutProfileInteger::value_type
const T value_type
Definition: ImmutableSet.h:857
llvm::ImutAVLTree
Definition: ImmutableSet.h:42
llvm::ImutProfileInteger::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:860
h
the multiplication has a latency of four as opposed to two cycles for the movl lea variant It appears gcc place string data with linkonce linkage in section coalesced instead of section coalesced Take a look at darwin h
Definition: README.txt:261
llvm::ImmutableSetRef::iterator
ImutAVLValueIterator< ImmutableSetRef > iterator
Definition: ImmutableSet.h:1158
llvm::ImutAVLFactory::createNode
TreeTy * createNode(TreeTy *L, value_type_ref V, TreeTy *R)
Definition: ImmutableSet.h:468
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::ImutAVLFactory::add_internal
TreeTy * add_internal(value_type_ref V, TreeTy *T)
add_internal - Creates a new tree that includes the specified data and the data from the original tre...
Definition: ImmutableSet.h:543
llvm::ImmutableSet::value_type
typename ValInfo::value_type value_type
Definition: ImmutableSet.h:966
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1827
llvm::ImutAVLTreeGenericIterator::operator!=
bool operator!=(const ImutAVLTreeGenericIterator &x) const
Definition: ImmutableSet.h:709
llvm::IntrusiveRefCntPtr
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
Definition: IntrusiveRefCntPtr.h:163
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:339
llvm::ImutAVLFactory::remove
TreeTy * remove(TreeTy *T, key_type_ref V)
Definition: ImmutableSet.h:415
llvm::ImmutableSetRef::FactoryTy
typename TreeTy::Factory FactoryTy
Definition: ImmutableSet.h:1101
llvm::ImutAVLTreeGenericIterator::operator--
ImutAVLTreeGenericIterator & operator--()
Definition: ImmutableSet.h:739
llvm::ImutAVLFactory::getValue
value_type_ref getValue(TreeTy *T) const
Definition: ImmutableSet.h:436
llvm::ImmutableSetRef::add
ImmutableSetRef add(value_type_ref V)
Definition: ImmutableSet.h:1118
llvm::ImutAVLValueIterator::ImutAVLValueIterator
ImutAVLValueIterator()=default
llvm::ImmutableSetRef::end
iterator end() const
Definition: ImmutableSet.h:1161
llvm::ImmutableSetRef::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableSet.h:1173
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::ImutAVLTree::Factory
ImutAVLFactory< ImutInfo > Factory
Definition: ImmutableSet.h:47
llvm::ImutContainerInfo
ImutContainerInfo - Generic definition of comparison operations for elements of immutable containers ...
Definition: ImmutableSet.h:915