LLVM  15.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 /// \file
10 /// This file defines the ImmutableList class.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_IMMUTABLELIST_H
15 #define LLVM_ADT_IMMUTABLELIST_H
16 
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/Support/Allocator.h"
19 #include <cassert>
20 #include <cstdint>
21 #include <new>
22 
23 namespace llvm {
24 
25 template <typename T> class ImmutableListFactory;
26 
27 template <typename T>
29  friend class ImmutableListFactory<T>;
30 
31  T Head;
32  const ImmutableListImpl* Tail;
33 
34  template <typename ElemT>
35  ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)
36  : Head(std::forward<ElemT>(head)), Tail(tail) {}
37 
38 public:
39  ImmutableListImpl(const ImmutableListImpl &) = delete;
41 
42  const T& getHead() const { return Head; }
43  const ImmutableListImpl* getTail() const { return Tail; }
44 
45  static inline void Profile(FoldingSetNodeID& ID, const T& H,
46  const ImmutableListImpl* L){
47  ID.AddPointer(L);
48  ID.Add(H);
49  }
50 
52  Profile(ID, Head, Tail);
53  }
54 };
55 
56 /// ImmutableList - This class represents an immutable (functional) list.
57 /// It is implemented as a smart pointer (wraps ImmutableListImpl), so it
58 /// it is intended to always be copied by value as if it were a pointer.
59 /// This interface matches ImmutableSet and ImmutableMap. ImmutableList
60 /// objects should almost never be created directly, and instead should
61 /// be created by ImmutableListFactory objects that manage the lifetime
62 /// of a group of lists. When the factory object is reclaimed, all lists
63 /// created by that factory are released as well.
64 template <typename T>
66 public:
67  using value_type = T;
69 
70  static_assert(std::is_trivially_destructible<T>::value,
71  "T must be trivially destructible!");
72 
73 private:
74  const ImmutableListImpl<T>* X;
75 
76 public:
77  // This constructor should normally only be called by ImmutableListFactory<T>.
78  // There may be cases, however, when one needs to extract the internal pointer
79  // and reconstruct a list object from that pointer.
80  ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
81 
83  return X;
84  }
85 
86  class iterator {
87  const ImmutableListImpl<T>* L = nullptr;
88 
89  public:
90  iterator() = default;
92 
93  iterator& operator++() { L = L->getTail(); return *this; }
94  bool operator==(const iterator& I) const { return L == I.L; }
95  bool operator!=(const iterator& I) const { return L != I.L; }
96  const value_type& operator*() const { return L->getHead(); }
98  return &L->getHead();
99  }
100 
101  ImmutableList getList() const { return L; }
102  };
103 
104  /// begin - Returns an iterator referring to the head of the list, or
105  /// an iterator denoting the end of the list if the list is empty.
106  iterator begin() const { return iterator(X); }
107 
108  /// end - Returns an iterator denoting the end of the list. This iterator
109  /// does not refer to a valid list element.
110  iterator end() const { return iterator(); }
111 
112  /// isEmpty - Returns true if the list is empty.
113  bool isEmpty() const { return !X; }
114 
115  bool contains(const T& V) const {
116  for (iterator I = begin(), E = end(); I != E; ++I) {
117  if (*I == V)
118  return true;
119  }
120  return false;
121  }
122 
123  /// isEqual - Returns true if two lists are equal. Because all lists created
124  /// from the same ImmutableListFactory are uniqued, this has O(1) complexity
125  /// because it the contents of the list do not need to be compared. Note
126  /// that you should only compare two lists created from the same
127  /// ImmutableListFactory.
128  bool isEqual(const ImmutableList& L) const { return X == L.X; }
129 
130  bool operator==(const ImmutableList& L) const { return isEqual(L); }
131 
132  /// getHead - Returns the head of the list.
133  const T& getHead() const {
134  assert(!isEmpty() && "Cannot get the head of an empty list.");
135  return X->getHead();
136  }
137 
138  /// getTail - Returns the tail of the list, which is another (possibly empty)
139  /// ImmutableList.
141  return X ? X->getTail() : nullptr;
142  }
143 
144  void Profile(FoldingSetNodeID& ID) const {
145  ID.AddPointer(X);
146  }
147 };
148 
149 template <typename T>
150 class ImmutableListFactory {
151  using ListTy = ImmutableListImpl<T>;
152  using CacheTy = FoldingSet<ListTy>;
153 
154  CacheTy Cache;
155  uintptr_t Allocator;
156 
157  bool ownsAllocator() const {
158  return (Allocator & 0x1) == 0;
159  }
160 
161  BumpPtrAllocator& getAllocator() const {
162  return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
163  }
164 
165 public:
167  : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
168 
170  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
171 
173  if (ownsAllocator()) delete &getAllocator();
174  }
175 
176  template <typename ElemT>
178  // Profile the new list to see if it already exists in our cache.
180  void* InsertPos;
181 
182  const ListTy* TailImpl = Tail.getInternalPointer();
183  ListTy::Profile(ID, Head, TailImpl);
184  ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
185 
186  if (!L) {
187  // The list does not exist in our cache. Create it.
188  BumpPtrAllocator& A = getAllocator();
189  L = (ListTy*) A.Allocate<ListTy>();
190  new (L) ListTy(std::forward<ElemT>(Head), TailImpl);
191 
192  // Insert the new list into the cache.
193  Cache.InsertNode(L, InsertPos);
194  }
195 
196  return L;
197  }
198 
199  template <typename ElemT>
201  return concat(std::forward<ElemT>(Data), L);
202  }
203 
204  template <typename ...CtorArgs>
206  CtorArgs &&...Args) {
207  return concat(T(std::forward<CtorArgs>(Args)...), Tail);
208  }
209 
211  return ImmutableList<T>(nullptr);
212  }
213 
214  template <typename ElemT>
216  return concat(std::forward<ElemT>(Data), getEmptyList());
217  }
218 };
219 
220 //===----------------------------------------------------------------------===//
221 // Partially-specialized Traits.
222 //===----------------------------------------------------------------------===//
223 
224 template <typename T> struct DenseMapInfo<ImmutableList<T>, void> {
225  static inline ImmutableList<T> getEmptyKey() {
226  return reinterpret_cast<ImmutableListImpl<T>*>(-1);
227  }
228 
230  return reinterpret_cast<ImmutableListImpl<T>*>(-2);
231  }
232 
233  static unsigned getHashValue(ImmutableList<T> X) {
234  uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
235  return (unsigned((uintptr_t)PtrVal) >> 4) ^
236  (unsigned((uintptr_t)PtrVal) >> 9);
237  }
238 
240  return X1 == X2;
241  }
242 };
243 
244 } // end namespace llvm
245 
246 #endif // LLVM_ADT_IMMUTABLELIST_H
llvm::DenseMapInfo< ImmutableList< T >, void >::getHashValue
static unsigned getHashValue(ImmutableList< T > X)
Definition: ImmutableList.h:233
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::ImmutableList::iterator::operator==
bool operator==(const iterator &I) const
Definition: ImmutableList.h:94
Allocator.h
llvm::ImmutableListImpl::getTail
const ImmutableListImpl * getTail() const
Definition: ImmutableList.h:43
llvm::ImmutableList::iterator::getList
ImmutableList getList() const
Definition: ImmutableList.h:101
llvm::ImmutableListFactory::ImmutableListFactory
ImmutableListFactory()
Definition: ImmutableList.h:166
llvm::ImmutableList::iterator::operator->
const std::remove_reference< value_type >::type * operator->() const
Definition: ImmutableList.h:97
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::ImmutableList::getTail
ImmutableList getTail() const
getTail - Returns the tail of the list, which is another (possibly empty) ImmutableList.
Definition: ImmutableList.h:140
llvm::ImmutableList::iterator
Definition: ImmutableList.h:86
llvm::ImmutableList::getInternalPointer
const ImmutableListImpl< T > * getInternalPointer() const
Definition: ImmutableList.h:82
llvm::BumpPtrAllocator
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:372
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::DenseMapInfo< ImmutableList< T >, void >::getEmptyKey
static ImmutableList< T > getEmptyKey()
Definition: ImmutableList.h:225
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::ImmutableList::ImmutableList
ImmutableList(const ImmutableListImpl< T > *x=nullptr)
Definition: ImmutableList.h:80
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:106
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:115
llvm::ImmutableListFactory
Definition: ImmutableList.h:25
llvm::ImmutableList::operator==
bool operator==(const ImmutableList &L) const
Definition: ImmutableList.h:130
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:172
llvm::ImmutableList::Profile
void Profile(FoldingSetNodeID &ID) const
Definition: ImmutableList.h:144
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:110
llvm::ImmutableListFactory::concat
LLVM_NODISCARD ImmutableList< T > concat(ElemT &&Head, ImmutableList< T > Tail)
Definition: ImmutableList.h:177
llvm::ImmutableListFactory::add
LLVM_NODISCARD ImmutableList< T > add(ElemT &&Data, ImmutableList< T > L)
Definition: ImmutableList.h:200
llvm::DenseMapInfo< ImmutableList< T >, void >::getTombstoneKey
static ImmutableList< T > getTombstoneKey()
Definition: ImmutableList.h:229
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:205
llvm::ImmutableList
ImmutableList - This class represents an immutable (functional) list.
Definition: ImmutableList.h:65
llvm::DenseMapInfo< ImmutableList< T >, void >::isEqual
static bool isEqual(ImmutableList< T > X1, ImmutableList< T > X2)
Definition: ImmutableList.h:239
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::ImmutableListFactory::ImmutableListFactory
ImmutableListFactory(BumpPtrAllocator &Alloc)
Definition: ImmutableList.h:169
llvm::ImmutableList::iterator::iterator
iterator()=default
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ImmutableList::iterator::iterator
iterator(ImmutableList l)
Definition: ImmutableList.h:91
llvm::ImmutableListImpl::Profile
void Profile(FoldingSetNodeID &ID)
Definition: ImmutableList.h:51
llvm::ImmutableListImpl
Definition: ImmutableList.h:28
llvm::ImmutableList::isEqual
bool isEqual(const ImmutableList &L) const
isEqual - Returns true if two lists are equal.
Definition: ImmutableList.h:128
llvm::ImmutableList::isEmpty
bool isEmpty() const
isEmpty - Returns true if the list is empty.
Definition: ImmutableList.h:113
llvm::ImmutableListImpl::getHead
const T & getHead() const
Definition: ImmutableList.h:42
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:135
llvm::ImmutableListFactory::create
ImmutableList< T > create(ElemT &&Data)
Definition: ImmutableList.h:215
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:317
llvm::ImmutableList::value_type
T value_type
Definition: ImmutableList.h:67
FoldingSet.h
llvm::ImmutableListImpl::operator=
ImmutableListImpl & operator=(const ImmutableListImpl &)=delete
std
Definition: BitVector.h:851
H
#define H(x, y, z)
Definition: MD5.cpp:57
llvm::ImmutableList::iterator::operator*
const value_type & operator*() const
Definition: ImmutableList.h:96
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::ImmutableListImpl::Profile
static void Profile(FoldingSetNodeID &ID, const T &H, const ImmutableListImpl *L)
Definition: ImmutableList.h:45
llvm::ImmutableList::getHead
const T & getHead() const
getHead - Returns the head of the list.
Definition: ImmutableList.h:133
llvm::ImmutableList::iterator::operator++
iterator & operator++()
Definition: ImmutableList.h:93
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:142
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::ImmutableList::iterator::operator!=
bool operator!=(const iterator &I) const
Definition: ImmutableList.h:95
llvm::ImmutableListFactory::getEmptyList
ImmutableList< T > getEmptyList() const
Definition: ImmutableList.h:210
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37