LLVM  14.0.0git
ImmutableList.h
Go to the documentation of this file.
1 //==--- ImmutableList.h - Immutable (functional) list 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 ImmutableList class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_IMMUTABLELIST_H
14 #define LLVM_ADT_IMMUTABLELIST_H
15 
16 #include "llvm/ADT/FoldingSet.h"
17 #include "llvm/Support/Allocator.h"
18 #include <cassert>
19 #include <cstdint>
20 #include <new>
21 
22 namespace llvm {
23 
24 template <typename T> class ImmutableListFactory;
25 
26 template <typename T>
28  friend class ImmutableListFactory<T>;
29 
30  T Head;
31  const ImmutableListImpl* Tail;
32 
33  template <typename ElemT>
34  ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)
35  : Head(std::forward<ElemT>(head)), Tail(tail) {}
36 
37 public:
38  ImmutableListImpl(const ImmutableListImpl &) = delete;
40 
41  const T& getHead() const { return Head; }
42  const ImmutableListImpl* getTail() const { return Tail; }
43 
44  static inline void Profile(FoldingSetNodeID& ID, const T& H,
45  const ImmutableListImpl* L){
46  ID.AddPointer(L);
47  ID.Add(H);
48  }
49 
51  Profile(ID, Head, Tail);
52  }
53 };
54 
55 /// ImmutableList - This class represents an immutable (functional) list.
56 /// It is implemented as a smart pointer (wraps ImmutableListImpl), so it
57 /// it is intended to always be copied by value as if it were a pointer.
58 /// This interface matches ImmutableSet and ImmutableMap. ImmutableList
59 /// objects should almost never be created directly, and instead should
60 /// be created by ImmutableListFactory objects that manage the lifetime
61 /// of a group of lists. When the factory object is reclaimed, all lists
62 /// created by that factory are released as well.
63 template <typename T>
65 public:
66  using value_type = T;
68 
69  static_assert(std::is_trivially_destructible<T>::value,
70  "T must be trivially destructible!");
71 
72 private:
73  const ImmutableListImpl<T>* X;
74 
75 public:
76  // This constructor should normally only be called by ImmutableListFactory<T>.
77  // There may be cases, however, when one needs to extract the internal pointer
78  // and reconstruct a list object from that pointer.
79  ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
80 
82  return X;
83  }
84 
85  class iterator {
86  const ImmutableListImpl<T>* L = nullptr;
87 
88  public:
89  iterator() = default;
91 
92  iterator& operator++() { L = L->getTail(); return *this; }
93  bool operator==(const iterator& I) const { return L == I.L; }
94  bool operator!=(const iterator& I) const { return L != I.L; }
95  const value_type& operator*() const { return L->getHead(); }
97  return &L->getHead();
98  }
99 
100  ImmutableList getList() const { return L; }
101  };
102 
103  /// begin - Returns an iterator referring to the head of the list, or
104  /// an iterator denoting the end of the list if the list is empty.
105  iterator begin() const { return iterator(X); }
106 
107  /// end - Returns an iterator denoting the end of the list. This iterator
108  /// does not refer to a valid list element.
109  iterator end() const { return iterator(); }
110 
111  /// isEmpty - Returns true if the list is empty.
112  bool isEmpty() const { return !X; }
113 
114  bool contains(const T& V) const {
115  for (iterator I = begin(), E = end(); I != E; ++I) {
116  if (*I == V)
117  return true;
118  }
119  return false;
120  }
121 
122  /// isEqual - Returns true if two lists are equal. Because all lists created
123  /// from the same ImmutableListFactory are uniqued, this has O(1) complexity
124  /// because it the contents of the list do not need to be compared. Note
125  /// that you should only compare two lists created from the same
126  /// ImmutableListFactory.
127  bool isEqual(const ImmutableList& L) const { return X == L.X; }
128 
129  bool operator==(const ImmutableList& L) const { return isEqual(L); }
130 
131  /// getHead - Returns the head of the list.
132  const T& getHead() const {
133  assert(!isEmpty() && "Cannot get the head of an empty list.");
134  return X->getHead();
135  }
136 
137  /// getTail - Returns the tail of the list, which is another (possibly empty)
138  /// ImmutableList.
140  return X ? X->getTail() : nullptr;
141  }
142 
143  void Profile(FoldingSetNodeID& ID) const {
144  ID.AddPointer(X);
145  }
146 };
147 
148 template <typename T>
149 class ImmutableListFactory {
150  using ListTy = ImmutableListImpl<T>;
151  using CacheTy = FoldingSet<ListTy>;
152 
153  CacheTy Cache;
154  uintptr_t Allocator;
155 
156  bool ownsAllocator() const {
157  return (Allocator & 0x1) == 0;
158  }
159 
160  BumpPtrAllocator& getAllocator() const {
161  return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
162  }
163 
164 public:
166  : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
167 
169  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
170 
172  if (ownsAllocator()) delete &getAllocator();
173  }
174 
175  template <typename ElemT>
177  // Profile the new list to see if it already exists in our cache.
179  void* InsertPos;
180 
181  const ListTy* TailImpl = Tail.getInternalPointer();
182  ListTy::Profile(ID, Head, TailImpl);
183  ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
184 
185  if (!L) {
186  // The list does not exist in our cache. Create it.
187  BumpPtrAllocator& A = getAllocator();
188  L = (ListTy*) A.Allocate<ListTy>();
189  new (L) ListTy(std::forward<ElemT>(Head), TailImpl);
190 
191  // Insert the new list into the cache.
192  Cache.InsertNode(L, InsertPos);
193  }
194 
195  return L;
196  }
197 
198  template <typename ElemT>
200  return concat(std::forward<ElemT>(Data), L);
201  }
202 
203  template <typename ...CtorArgs>
205  CtorArgs &&...Args) {
206  return concat(T(std::forward<CtorArgs>(Args)...), Tail);
207  }
208 
210  return ImmutableList<T>(nullptr);
211  }
212 
213  template <typename ElemT>
215  return concat(std::forward<ElemT>(Data), getEmptyList());
216  }
217 };
218 
219 //===----------------------------------------------------------------------===//
220 // Partially-specialized Traits.
221 //===----------------------------------------------------------------------===//
222 
223 template <typename T> struct DenseMapInfo<ImmutableList<T>, void> {
224  static inline ImmutableList<T> getEmptyKey() {
225  return reinterpret_cast<ImmutableListImpl<T>*>(-1);
226  }
227 
229  return reinterpret_cast<ImmutableListImpl<T>*>(-2);
230  }
231 
232  static unsigned getHashValue(ImmutableList<T> X) {
233  uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
234  return (unsigned((uintptr_t)PtrVal) >> 4) ^
235  (unsigned((uintptr_t)PtrVal) >> 9);
236  }
237 
239  return X1 == X2;
240  }
241 };
242 
243 } // end namespace llvm
244 
245 #endif // LLVM_ADT_IMMUTABLELIST_H
llvm::DenseMapInfo< ImmutableList< T >, void >::getHashValue
static unsigned getHashValue(ImmutableList< T > X)
Definition: ImmutableList.h:232
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::ImmutableList::iterator::operator==
bool operator==(const iterator &I) const
Definition: ImmutableList.h:93
Allocator.h
llvm::ImmutableListImpl::getTail
const ImmutableListImpl * getTail() const
Definition: ImmutableList.h:42
llvm::ImmutableList::iterator::getList
ImmutableList getList() const
Definition: ImmutableList.h:100
llvm::ImmutableListFactory::ImmutableListFactory
ImmutableListFactory()
Definition: ImmutableList.h:165
llvm::ImmutableList::iterator::operator->
const std::remove_reference< value_type >::type * operator->() const
Definition: ImmutableList.h:96
llvm::ImmutableList::getTail
ImmutableList getTail() const
getTail - Returns the tail of the list, which is another (possibly empty) ImmutableList.
Definition: ImmutableList.h:139
llvm::ImmutableList::iterator
Definition: ImmutableList.h:85
llvm::ImmutableList::getInternalPointer
const ImmutableListImpl< T > * getInternalPointer() const
Definition: ImmutableList.h:81
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:369
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::DenseMapInfo< ImmutableList< T >, void >::getEmptyKey
static ImmutableList< T > getEmptyKey()
Definition: ImmutableList.h:224
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::ImmutableList::ImmutableList
ImmutableList(const ImmutableListImpl< T > *x=nullptr)
Definition: ImmutableList.h:79
llvm::ImmutableList::begin
iterator begin() const
begin - Returns an iterator referring to the head of the list, or an iterator denoting the end of the...
Definition: ImmutableList.h:105
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::ImmutableList::contains
bool contains(const T &V) const
Definition: ImmutableList.h:114
llvm::ImmutableListFactory
Definition: ImmutableList.h:24
llvm::ImmutableList::operator==
bool operator==(const ImmutableList &L) const
Definition: ImmutableList.h:129
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::ImmutableListFactory::~ImmutableListFactory
~ImmutableListFactory()
Definition: ImmutableList.h:171
llvm::ImmutableList::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableList.h:143
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
llvm::ImmutableList::end
iterator end() const
end - Returns an iterator denoting the end of the list.
Definition: ImmutableList.h:109
llvm::ImmutableListFactory::concat
LLVM_NODISCARD ImmutableList< T > concat(ElemT &&Head, ImmutableList< T > Tail)
Definition: ImmutableList.h:176
llvm::ImmutableListFactory::add
LLVM_NODISCARD ImmutableList< T > add(ElemT &&Data, ImmutableList< T > L)
Definition: ImmutableList.h:199
llvm::DenseMapInfo< ImmutableList< T >, void >::getTombstoneKey
static ImmutableList< T > getTombstoneKey()
Definition: ImmutableList.h:228
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
llvm::ImmutableListFactory::emplace
LLVM_NODISCARD ImmutableList< T > emplace(ImmutableList< T > Tail, CtorArgs &&...Args)
Definition: ImmutableList.h:204
llvm::ImmutableList
ImmutableList - This class represents an immutable (functional) list.
Definition: ImmutableList.h:64
llvm::DenseMapInfo< ImmutableList< T >, void >::isEqual
static bool isEqual(ImmutableList< T > X1, ImmutableList< T > X2)
Definition: ImmutableList.h:238
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ImmutableListFactory::ImmutableListFactory
ImmutableListFactory(BumpPtrAllocator &Alloc)
Definition: ImmutableList.h:168
llvm::ImmutableList::iterator::iterator
iterator()=default
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ImmutableList::iterator::iterator
iterator(ImmutableList l)
Definition: ImmutableList.h:90
llvm::ImmutableListImpl::Profile
void Profile(FoldingSetNodeID &ID)
Definition: ImmutableList.h:50
llvm::ImmutableListImpl
Definition: ImmutableList.h:27
llvm::ImmutableList::isEqual
bool isEqual(const ImmutableList &L) const
isEqual - Returns true if two lists are equal.
Definition: ImmutableList.h:127
llvm::ImmutableList::isEmpty
bool isEmpty() const
isEmpty - Returns true if the list is empty.
Definition: ImmutableList.h:112
llvm::ImmutableListImpl::getHead
const T & getHead() const
Definition: ImmutableList.h:41
X
Since we know that Vector is byte aligned and we know the element offset of X
Definition: README_ALTIVEC.txt:37
llvm::FoldingSetBase::Node
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:133
llvm::ImmutableListFactory::create
ImmutableList< T > create(ElemT &&Data)
Definition: ImmutableList.h:214
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
llvm::ImmutableList::value_type
T value_type
Definition: ImmutableList.h:66
FoldingSet.h
llvm::ImmutableListImpl::operator=
ImmutableListImpl & operator=(const ImmutableListImpl &)=delete
std
Definition: BitVector.h:838
H
#define H(x, y, z)
Definition: MD5.cpp:58
llvm::ImmutableList::iterator::operator*
const value_type & operator*() const
Definition: ImmutableList.h:95
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::ImmutableListImpl::Profile
static void Profile(FoldingSetNodeID &ID, const T &H, const ImmutableListImpl *L)
Definition: ImmutableList.h:44
llvm::ImmutableList::getHead
const T & getHead() const
getHead - Returns the head of the list.
Definition: ImmutableList.h:132
llvm::ImmutableList::iterator::operator++
iterator & operator++()
Definition: ImmutableList.h:92
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::ImmutableList::iterator::operator!=
bool operator!=(const iterator &I) const
Definition: ImmutableList.h:94
llvm::ImmutableListFactory::getEmptyList
ImmutableList< T > getEmptyList() const
Definition: ImmutableList.h:209
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38