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> class ImutAVLTreeGenericIterator {
655  SmallVector<uintptr_t,20> stack;
656 
657 public:
658  using iterator_category = std::bidirectional_iterator_tag;
660  using difference_type = std::ptrdiff_t;
661  using pointer = value_type *;
663 
665  Flags=0x3 };
666 
668 
669  ImutAVLTreeGenericIterator() = default;
671  if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
672  }
673 
674  TreeTy &operator*() const {
675  assert(!stack.empty());
676  return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
677  }
678  TreeTy *operator->() const { return &*this; }
679 
680  uintptr_t getVisitState() const {
681  assert(!stack.empty());
682  return stack.back() & Flags;
683  }
684 
685  bool atEnd() const { return stack.empty(); }
686 
687  bool atBeginning() const {
688  return stack.size() == 1 && getVisitState() == VisitedNone;
689  }
690 
691  void skipToParent() {
692  assert(!stack.empty());
693  stack.pop_back();
694  if (stack.empty())
695  return;
696  switch (getVisitState()) {
697  case VisitedNone:
698  stack.back() |= VisitedLeft;
699  break;
700  case VisitedLeft:
701  stack.back() |= VisitedRight;
702  break;
703  default:
704  llvm_unreachable("Unreachable.");
705  }
706  }
707 
709  return stack == x.stack;
710  }
711 
713  return !(*this == x);
714  }
715 
717  assert(!stack.empty());
718  TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
719  assert(Current);
720  switch (getVisitState()) {
721  case VisitedNone:
722  if (TreeTy* L = Current->getLeft())
723  stack.push_back(reinterpret_cast<uintptr_t>(L));
724  else
725  stack.back() |= VisitedLeft;
726  break;
727  case VisitedLeft:
728  if (TreeTy* R = Current->getRight())
729  stack.push_back(reinterpret_cast<uintptr_t>(R));
730  else
731  stack.back() |= VisitedRight;
732  break;
733  case VisitedRight:
734  skipToParent();
735  break;
736  default:
737  llvm_unreachable("Unreachable.");
738  }
739  return *this;
740  }
741 
743  assert(!stack.empty());
744  TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
745  assert(Current);
746  switch (getVisitState()) {
747  case VisitedNone:
748  stack.pop_back();
749  break;
750  case VisitedLeft:
751  stack.back() &= ~Flags; // Set state to "VisitedNone."
752  if (TreeTy* L = Current->getLeft())
753  stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);
754  break;
755  case VisitedRight:
756  stack.back() &= ~Flags;
757  stack.back() |= VisitedLeft;
758  if (TreeTy* R = Current->getRight())
759  stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);
760  break;
761  default:
762  llvm_unreachable("Unreachable.");
763  }
764  return *this;
765  }
766 };
767 
768 template <typename ImutInfo> class ImutAVLTreeInOrderIterator {
769  using InternalIteratorTy = ImutAVLTreeGenericIterator<ImutInfo>;
770 
771  InternalIteratorTy InternalItr;
772 
773 public:
774  using iterator_category = std::bidirectional_iterator_tag;
776  using difference_type = std::ptrdiff_t;
777  using pointer = value_type *;
779 
781 
782  ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
783  if (Root)
784  ++*this; // Advance to first element.
785  }
786 
787  ImutAVLTreeInOrderIterator() : InternalItr() {}
788 
790  return InternalItr == x.InternalItr;
791  }
792 
794  return !(*this == x);
795  }
796 
797  TreeTy &operator*() const { return *InternalItr; }
798  TreeTy *operator->() const { return &*InternalItr; }
799 
801  do ++InternalItr;
802  while (!InternalItr.atEnd() &&
803  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
804 
805  return *this;
806  }
807 
809  do --InternalItr;
810  while (!InternalItr.atBeginning() &&
811  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
812 
813  return *this;
814  }
815 
816  void skipSubTree() {
817  InternalItr.skipToParent();
818 
819  while (!InternalItr.atEnd() &&
820  InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
821  ++InternalItr;
822  }
823 };
824 
825 /// Generic iterator that wraps a T::TreeTy::iterator and exposes
826 /// iterator::getValue() on dereference.
827 template <typename T>
830  ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
831  typename std::iterator_traits<
832  typename T::TreeTy::iterator>::iterator_category,
833  const typename T::value_type> {
834  ImutAVLValueIterator() = default;
835  explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
837 
839  return this->I->getValue();
840  }
841 };
842 
843 //===----------------------------------------------------------------------===//
844 // Trait classes for Profile information.
845 //===----------------------------------------------------------------------===//
846 
847 /// Generic profile template. The default behavior is to invoke the
848 /// profile method of an object. Specializations for primitive integers
849 /// and generic handling of pointers is done below.
850 template <typename T>
852  using value_type = const T;
853  using value_type_ref = const T&;
854 
857  }
858 };
859 
860 /// Profile traits for integers.
861 template <typename T>
863  using value_type = const T;
864  using value_type_ref = const T&;
865 
867  ID.AddInteger(X);
868  }
869 };
870 
871 #define PROFILE_INTEGER_INFO(X)\
872 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
873 
875 PROFILE_INTEGER_INFO(unsigned char)
877 PROFILE_INTEGER_INFO(unsigned short)
878 PROFILE_INTEGER_INFO(unsigned)
879 PROFILE_INTEGER_INFO(signed)
881 PROFILE_INTEGER_INFO(unsigned long)
882 PROFILE_INTEGER_INFO(long long)
883 PROFILE_INTEGER_INFO(unsigned long long)
884 
885 #undef PROFILE_INTEGER_INFO
886 
887 /// Profile traits for booleans.
888 template <>
889 struct ImutProfileInfo<bool> {
890  using value_type = const bool;
891  using value_type_ref = const bool&;
892 
894  ID.AddBoolean(X);
895  }
896 };
897 
898 /// Generic profile trait for pointer types. We treat pointers as
899 /// references to unique objects.
900 template <typename T>
901 struct ImutProfileInfo<T*> {
902  using value_type = const T*;
904 
906  ID.AddPointer(X);
907  }
908 };
909 
910 //===----------------------------------------------------------------------===//
911 // Trait classes that contain element comparison operators and type
912 // definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
913 // inherit from the profile traits (ImutProfileInfo) to include operations
914 // for element profiling.
915 //===----------------------------------------------------------------------===//
916 
917 /// ImutContainerInfo - Generic definition of comparison operations for
918 /// elements of immutable containers that defaults to using
919 /// std::equal_to<> and std::less<> to perform comparison of elements.
920 template <typename T>
921 struct ImutContainerInfo : public ImutProfileInfo<T> {
926  using data_type = bool;
927  using data_type_ref = bool;
928 
930  static data_type_ref DataOfValue(value_type_ref) { return true; }
931 
932  static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
933  return std::equal_to<key_type>()(LHS,RHS);
934  }
935 
936  static bool isLess(key_type_ref LHS, key_type_ref RHS) {
937  return std::less<key_type>()(LHS,RHS);
938  }
939 
940  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
941 };
942 
943 /// ImutContainerInfo - Specialization for pointer values to treat pointers
944 /// as references to unique objects. Pointers are thus compared by
945 /// their addresses.
946 template <typename T>
952  using data_type = bool;
953  using data_type_ref = bool;
954 
956  static data_type_ref DataOfValue(value_type_ref) { return true; }
957 
958  static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; }
959 
960  static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; }
961 
962  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
963 };
964 
965 //===----------------------------------------------------------------------===//
966 // Immutable Set
967 //===----------------------------------------------------------------------===//
968 
969 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
971 public:
972  using value_type = typename ValInfo::value_type;
973  using value_type_ref = typename ValInfo::value_type_ref;
975 
976 private:
978 
979 public:
980  /// Constructs a set from a pointer to a tree root. In general one
981  /// should use a Factory object to create sets instead of directly
982  /// invoking the constructor, but there are cases where make this
983  /// constructor public is useful.
984  explicit ImmutableSet(TreeTy *R) : Root(R) {}
985 
986  class Factory {
987  typename TreeTy::Factory F;
988  const bool Canonicalize;
989 
990  public:
991  Factory(bool canonicalize = true)
992  : Canonicalize(canonicalize) {}
993 
994  Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
995  : F(Alloc), Canonicalize(canonicalize) {}
996 
997  Factory(const Factory& RHS) = delete;
998  void operator=(const Factory& RHS) = delete;
999 
1000  /// getEmptySet - Returns an immutable set that contains no elements.
1002  return ImmutableSet(F.getEmptyTree());
1003  }
1004 
1005  /// add - Creates a new immutable set that contains all of the values
1006  /// of the original set with the addition of the specified value. If
1007  /// the original set already included the value, then the original set is
1008  /// returned and no memory is allocated. The time and space complexity
1009  /// of this operation is logarithmic in the size of the original set.
1010  /// The memory allocated to represent the set is released when the
1011  /// factory object that created the set is destroyed.
1013  TreeTy *NewT = F.add(Old.Root.get(), V);
1014  return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1015  }
1016 
1017  /// remove - Creates a new immutable set that contains all of the values
1018  /// of the original set with the exception of the specified value. If
1019  /// the original set did not contain the value, the original set is
1020  /// returned and no memory is allocated. The time and space complexity
1021  /// of this operation is logarithmic in the size of the original set.
1022  /// The memory allocated to represent the set is released when the
1023  /// factory object that created the set is destroyed.
1025  TreeTy *NewT = F.remove(Old.Root.get(), V);
1026  return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1027  }
1028 
1029  BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
1030 
1031  typename TreeTy::Factory *getTreeFactory() const {
1032  return const_cast<typename TreeTy::Factory *>(&F);
1033  }
1034  };
1035 
1036  friend class Factory;
1037 
1038  /// Returns true if the set contains the specified value.
1039  bool contains(value_type_ref V) const {
1040  return Root ? Root->contains(V) : false;
1041  }
1042 
1043  bool operator==(const ImmutableSet &RHS) const {
1044  return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
1045  }
1046 
1047  bool operator!=(const ImmutableSet &RHS) const {
1048  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
1049  : Root != RHS.Root;
1050  }
1051 
1053  if (Root) { Root->retain(); }
1054  return Root.get();
1055  }
1056 
1057  TreeTy *getRootWithoutRetain() const { return Root.get(); }
1058 
1059  /// isEmpty - Return true if the set contains no elements.
1060  bool isEmpty() const { return !Root; }
1061 
1062  /// isSingleton - Return true if the set contains exactly one element.
1063  /// This method runs in constant time.
1064  bool isSingleton() const { return getHeight() == 1; }
1065 
1066  template <typename Callback>
1067  void foreach(Callback& C) { if (Root) Root->foreach(C); }
1068 
1069  template <typename Callback>
1070  void foreach() { if (Root) { Callback C; Root->foreach(C); } }
1071 
1072  //===--------------------------------------------------===//
1073  // Iterators.
1074  //===--------------------------------------------------===//
1075 
1077 
1078  iterator begin() const { return iterator(Root.get()); }
1079  iterator end() const { return iterator(); }
1080 
1081  //===--------------------------------------------------===//
1082  // Utility methods.
1083  //===--------------------------------------------------===//
1084 
1085  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1086 
1087  static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
1088  ID.AddPointer(S.Root.get());
1089  }
1090 
1091  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1092 
1093  //===--------------------------------------------------===//
1094  // For testing.
1095  //===--------------------------------------------------===//
1096 
1097  void validateTree() const { if (Root) Root->validateTree(); }
1098 };
1099 
1100 // NOTE: This may some day replace the current ImmutableSet.
1101 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT>>
1103 public:
1104  using value_type = typename ValInfo::value_type;
1105  using value_type_ref = typename ValInfo::value_type_ref;
1107  using FactoryTy = typename TreeTy::Factory;
1108 
1109 private:
1111  FactoryTy *Factory;
1112 
1113 public:
1114  /// Constructs a set from a pointer to a tree root. In general one
1115  /// should use a Factory object to create sets instead of directly
1116  /// invoking the constructor, but there are cases where make this
1117  /// constructor public is useful.
1118  ImmutableSetRef(TreeTy *R, FactoryTy *F) : Root(R), Factory(F) {}
1119 
1121  return ImmutableSetRef(0, F);
1122  }
1123 
1125  return ImmutableSetRef(Factory->add(Root.get(), V), Factory);
1126  }
1127 
1129  return ImmutableSetRef(Factory->remove(Root.get(), V), Factory);
1130  }
1131 
1132  /// Returns true if the set contains the specified value.
1133  bool contains(value_type_ref V) const {
1134  return Root ? Root->contains(V) : false;
1135  }
1136 
1137  ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
1138  return ImmutableSet<ValT>(
1139  canonicalize ? Factory->getCanonicalTree(Root.get()) : Root.get());
1140  }
1141 
1142  TreeTy *getRootWithoutRetain() const { return Root.get(); }
1143 
1144  bool operator==(const ImmutableSetRef &RHS) const {
1145  return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
1146  }
1147 
1148  bool operator!=(const ImmutableSetRef &RHS) const {
1149  return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
1150  : Root != RHS.Root;
1151  }
1152 
1153  /// isEmpty - Return true if the set contains no elements.
1154  bool isEmpty() const { return !Root; }
1155 
1156  /// isSingleton - Return true if the set contains exactly one element.
1157  /// This method runs in constant time.
1158  bool isSingleton() const { return getHeight() == 1; }
1159 
1160  //===--------------------------------------------------===//
1161  // Iterators.
1162  //===--------------------------------------------------===//
1163 
1165 
1166  iterator begin() const { return iterator(Root.get()); }
1167  iterator end() const { return iterator(); }
1168 
1169  //===--------------------------------------------------===//
1170  // Utility methods.
1171  //===--------------------------------------------------===//
1172 
1173  unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
1174 
1175  static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
1176  ID.AddPointer(S.Root.get());
1177  }
1178 
1179  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
1180 
1181  //===--------------------------------------------------===//
1182  // For testing.
1183  //===--------------------------------------------------===//
1184 
1185  void validateTree() const { if (Root) Root->validateTree(); }
1186 };
1187 
1188 } // end namespace llvm
1189 
1190 #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:1060
llvm::IntrusiveRefCntPtr::get
T * get() const
Definition: IntrusiveRefCntPtr.h:195
llvm::ImmutableSetRef::Profile
static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S)
Definition: ImmutableSet.h:1175
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:1012
llvm::ImmutableSetRef::begin
iterator begin() const
Definition: ImmutableSet.h:1166
right
the custom lowered code happens to be right
Definition: README-SSE.txt:480
llvm::ImutAVLTreeGenericIterator::atEnd
bool atEnd() const
Definition: ImmutableSet.h:685
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ImmutableSet::getRootWithoutRetain
TreeTy * getRootWithoutRetain() const
Definition: ImmutableSet.h:1057
llvm::ImmutableSet::isSingleton
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
Definition: ImmutableSet.h:1064
llvm::ImutProfileInfo< bool >::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:893
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:929
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:953
llvm::ImutAVLTreeInOrderIterator::ImutAVLTreeInOrderIterator
ImutAVLTreeInOrderIterator(const TreeTy *Root)
Definition: ImmutableSet.h:782
llvm::ImutContainerInfo< T * >::isEqual
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:958
llvm::ImutAVLValueIterator::operator*
ImutAVLValueIterator::reference operator*() const
Definition: ImmutableSet.h:838
llvm::ImutAVLFactory::recoverNodes
void recoverNodes()
Definition: ImmutableSet.h:488
llvm::ImmutableSet::Factory::getTreeFactory
TreeTy::Factory * getTreeFactory() const
Definition: ImmutableSet.h:1031
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:922
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:1133
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:217
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:789
llvm::ImutAVLValueIterator
Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference.
Definition: ImmutableSet.h:828
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:1148
Right
Vector Shift Left Right
Definition: README_P9.txt:118
llvm::ImutAVLTreeGenericIterator::getVisitState
uintptr_t getVisitState() const
Definition: ImmutableSet.h:680
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:932
llvm::ImutAVLTreeGenericIterator::ImutAVLTreeGenericIterator
ImutAVLTreeGenericIterator()=default
llvm::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:211
llvm::ImmutableSet::Factory::getEmptySet
ImmutableSet getEmptySet()
getEmptySet - Returns an immutable set that contains no elements.
Definition: ImmutableSet.h:1001
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:664
llvm::ImutContainerInfo< T * >::isDataEqual
static bool isDataEqual(data_type_ref, data_type_ref)
Definition: ImmutableSet.h:962
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:903
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::ImutAVLTreeInOrderIterator::operator!=
bool operator!=(const ImutAVLTreeInOrderIterator &x) const
Definition: ImmutableSet.h:793
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:180
llvm::ImutContainerInfo::data_type_ref
bool data_type_ref
Definition: ImmutableSet.h:927
llvm::ImutAVLFactory::incrementHeight
unsigned incrementHeight(TreeTy *L, TreeTy *R) const
Definition: ImmutableSet.h:441
llvm::ImutContainerInfo::data_type
bool data_type
Definition: ImmutableSet.h:926
llvm::ImutContainerInfo::DataOfValue
static data_type_ref DataOfValue(value_type_ref)
Definition: ImmutableSet.h:930
llvm::ImutContainerInfo::value_type_ref
typename ImutProfileInfo< T >::value_type_ref value_type_ref
Definition: ImmutableSet.h:923
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:950
llvm::ImutAVLTreeGenericIterator::operator++
ImutAVLTreeGenericIterator & operator++()
Definition: ImmutableSet.h:716
llvm::ImutAVLTreeInOrderIterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: ImmutableSet.h:774
llvm::ImmutableSetRef::remove
ImmutableSetRef remove(value_type_ref V)
Definition: ImmutableSet.h:1128
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:851
llvm::ImmutableSetRef::value_type
typename ValInfo::value_type value_type
Definition: ImmutableSet.h:1104
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:984
llvm::ImutContainerInfo< T * >::isLess
static bool isLess(key_type_ref LHS, key_type_ref RHS)
Definition: ImmutableSet.h:960
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:664
llvm::ImutAVLTreeGenericIterator::VisitFlag
VisitFlag
Definition: ImmutableSet.h:664
llvm::IntrusiveRefCntPtrInfo< ImutAVLTree< ImutInfo > >::retain
static void retain(ImutAVLTree< ImutInfo > *Tree)
Definition: ImmutableSet.h:363
llvm::ImutAVLTreeGenericIterator::VisitedRight
@ VisitedRight
Definition: ImmutableSet.h:664
llvm::ImutAVLFactory
Definition: ImmutableSet.h:36
llvm::ImutProfileInfo::value_type_ref
const T & value_type_ref
Definition: ImmutableSet.h:853
llvm::ImutProfileInteger
Profile traits for integers.
Definition: ImmutableSet.h:862
llvm::ImutAVLTreeInOrderIterator::operator*
TreeTy & operator*() const
Definition: ImmutableSet.h:797
llvm::ImutContainerInfo< T * >::KeyOfValue
static key_type_ref KeyOfValue(value_type_ref D)
Definition: ImmutableSet.h:955
llvm::ImutAVLValueIterator::ImutAVLValueIterator
ImutAVLValueIterator(typename T::TreeTy *Tree)
Definition: ImmutableSet.h:835
llvm::ImutProfileInfo< bool >::value_type_ref
const bool & value_type_ref
Definition: ImmutableSet.h:891
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::ImmutableSet::begin
iterator begin() const
Definition: ImmutableSet.h:1078
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:72
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:1087
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:1024
llvm::ImmutableSetRef::value_type_ref
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableSet.h:1105
llvm::ImutContainerInfo::key_type
value_type key_type
Definition: ImmutableSet.h:924
llvm::ImutAVLTreeGenericIterator::iterator_category
std::bidirectional_iterator_tag iterator_category
Definition: ImmutableSet.h:658
llvm::ImmutableSet::contains
bool contains(value_type_ref V) const
Returns true if the set contains the specified value.
Definition: ImmutableSet.h:1039
llvm::ImutContainerInfo::isDataEqual
static bool isDataEqual(data_type_ref, data_type_ref)
Definition: ImmutableSet.h:940
llvm::ImmutableSet::Factory::Factory
Factory(bool canonicalize=true)
Definition: ImmutableSet.h:991
llvm::ImmutableSet::end
iterator end() const
Definition: ImmutableSet.h:1079
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:1137
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:952
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:691
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:1120
llvm::ImutProfileInfo::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:855
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:1043
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:994
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ImmutableSetRef
Definition: ImmutableSet.h:1102
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:936
llvm::ImutProfileInfo< bool >::value_type
const bool value_type
Definition: ImmutableSet.h:890
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:902
llvm::ImutAVLTreeGenericIterator::operator==
bool operator==(const ImutAVLTreeGenericIterator &x) const
Definition: ImmutableSet.h:708
llvm::ImmutableSetRef::operator==
bool operator==(const ImmutableSetRef &RHS) const
Definition: ImmutableSet.h:1144
llvm::ImmutableSet::value_type_ref
typename ValInfo::value_type_ref value_type_ref
Definition: ImmutableSet.h:973
llvm::ImmutableSet::Factory::getAllocator
BumpPtrAllocator & getAllocator()
Definition: ImmutableSet.h:1029
llvm::ImutAVLTreeGenericIterator::operator*
TreeTy & operator*() const
Definition: ImmutableSet.h:674
llvm::DefaultFoldingSetTrait::Profile
static void Profile(const T &X, FoldingSetNodeID &ID)
Definition: FoldingSet.h:229
llvm::ImutAVLTreeInOrderIterator::operator->
TreeTy * operator->() const
Definition: ImmutableSet.h:798
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:687
llvm::ImmutableSet
Definition: ImmutableSet.h:970
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:871
llvm::ImutProfileInfo< T * >
Generic profile trait for pointer types.
Definition: ImmutableSet.h:901
llvm::ImutAVLTreeGenericIterator::Flags
@ Flags
Definition: ImmutableSet.h:665
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:864
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:852
llvm::ImmutableSet::getRoot
TreeTy * getRoot()
Definition: ImmutableSet.h:1052
llvm::ImmutableSet::getHeight
unsigned getHeight() const
Definition: ImmutableSet.h:1085
llvm::ImutAVLTreeInOrderIterator::operator--
ImutAVLTreeInOrderIterator & operator--()
Definition: ImmutableSet.h:808
llvm::ImmutableSet::Factory
Definition: ImmutableSet.h:986
llvm::ImmutableSet::operator!=
bool operator!=(const ImmutableSet &RHS) const
Definition: ImmutableSet.h:1047
llvm::ImmutableSetRef::isSingleton
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
Definition: ImmutableSet.h:1158
llvm::ImutContainerInfo< T * >::key_type_ref
value_type_ref key_type_ref
Definition: ImmutableSet.h:951
llvm::ImmutableSet::iterator
ImutAVLValueIterator< ImmutableSet > iterator
Definition: ImmutableSet.h:1076
llvm::ImmutableSetRef::validateTree
void validateTree() const
Definition: ImmutableSet.h:1185
llvm::ImutAVLTreeGenericIterator::ImutAVLTreeGenericIterator
ImutAVLTreeGenericIterator(const TreeTy *Root)
Definition: ImmutableSet.h:670
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:800
llvm::ImutAVLTreeInOrderIterator::ImutAVLTreeInOrderIterator
ImutAVLTreeInOrderIterator()
Definition: ImmutableSet.h:787
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
x
TODO unsigned x
Definition: README.txt:10
llvm::ImmutableSetRef::getHeight
unsigned getHeight() const
Definition: ImmutableSet.h:1173
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1928
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:816
llvm::ImmutableSetRef::isEmpty
bool isEmpty() const
isEmpty - Return true if the set contains no elements.
Definition: ImmutableSet.h:1154
llvm::ImmutableSet::validateTree
void validateTree() const
Definition: ImmutableSet.h:1097
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:925
llvm::ImmutableSetRef::ImmutableSetRef
ImmutableSetRef(TreeTy *R, FactoryTy *F)
Constructs a set from a pointer to a tree root.
Definition: ImmutableSet.h:1118
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:905
llvm::ImmutableSet::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableSet.h:1091
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:956
llvm::ImmutableSetRef::getRootWithoutRetain
TreeTy * getRootWithoutRetain() const
Definition: ImmutableSet.h:1142
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:678
llvm::ImutProfileInteger::value_type
const T value_type
Definition: ImmutableSet.h:863
llvm::ImutAVLTree
Definition: ImmutableSet.h:42
llvm::ImutProfileInteger::Profile
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Definition: ImmutableSet.h:866
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:660
llvm::ImmutableSetRef::iterator
ImutAVLValueIterator< ImmutableSetRef > iterator
Definition: ImmutableSet.h:1164
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:972
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
llvm::ImutAVLTreeInOrderIterator::difference_type
std::ptrdiff_t difference_type
Definition: ImmutableSet.h:776
llvm::ImutAVLTreeGenericIterator::operator!=
bool operator!=(const ImutAVLTreeGenericIterator &x) const
Definition: ImmutableSet.h:712
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:1107
llvm::ImutAVLTreeGenericIterator::operator--
ImutAVLTreeGenericIterator & operator--()
Definition: ImmutableSet.h:742
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:1124
llvm::ImutAVLValueIterator::ImutAVLValueIterator
ImutAVLValueIterator()=default
llvm::ImmutableSetRef::end
iterator end() const
Definition: ImmutableSet.h:1167
llvm::ImmutableSetRef::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableSet.h:1179
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
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:921