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