LLVM  14.0.0git
CachedHashString.h
Go to the documentation of this file.
1 //===- llvm/ADT/CachedHashString.h - Prehashed string/StringRef -*- 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 CachedHashString and CachedHashStringRef. These are owning
10 // and not-owning string types that store their hash in addition to their string
11 // data.
12 //
13 // Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
14 // (because, unlike std::string, CachedHashString lets us have empty and
15 // tombstone values).
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #ifndef LLVM_ADT_CACHEDHASHSTRING_H
20 #define LLVM_ADT_CACHEDHASHSTRING_H
21 
22 #include "llvm/ADT/DenseMapInfo.h"
23 #include "llvm/ADT/StringRef.h"
24 
25 namespace llvm {
26 
27 /// A container which contains a StringRef plus a precomputed hash.
29  const char *P;
30  uint32_t Size;
31  uint32_t Hash;
32 
33 public:
34  // Explicit because hashing a string isn't free.
36  : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
37 
39  : P(S.data()), Size(S.size()), Hash(Hash) {
41  }
42 
43  StringRef val() const { return StringRef(P, Size); }
44  const char *data() const { return P; }
45  uint32_t size() const { return Size; }
46  uint32_t hash() const { return Hash; }
47 };
48 
49 template <> struct DenseMapInfo<CachedHashStringRef> {
52  }
55  }
56  static unsigned getHashValue(const CachedHashStringRef &S) {
57  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
58  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
59  return S.hash();
60  }
61  static bool isEqual(const CachedHashStringRef &LHS,
62  const CachedHashStringRef &RHS) {
63  return LHS.hash() == RHS.hash() &&
65  }
66 };
67 
68 /// A container which contains a string, which it owns, plus a precomputed hash.
69 ///
70 /// We do not null-terminate the string.
73 
74  char *P;
75  uint32_t Size;
76  uint32_t Hash;
77 
78  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
79  static char *getTombstoneKeyPtr() {
81  }
82 
83  bool isEmptyOrTombstone() const {
84  return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
85  }
86 
87  struct ConstructEmptyOrTombstoneTy {};
88 
89  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
90  : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
91  assert(isEmptyOrTombstone());
92  }
93 
94  // TODO: Use small-string optimization to avoid allocating.
95 
96 public:
97  explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
98 
99  // Explicit because copying and hashing a string isn't free.
101  : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
102 
104  : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
105  memcpy(P, S.data(), S.size());
106  }
107 
108  // Ideally this class would not be copyable. But SetVector requires copyable
109  // keys, and we want this to be usable there.
111  : Size(Other.Size), Hash(Other.Hash) {
112  if (Other.isEmptyOrTombstone()) {
113  P = Other.P;
114  } else {
115  P = new char[Size];
116  memcpy(P, Other.P, Size);
117  }
118  }
119 
121  swap(*this, Other);
122  return *this;
123  }
124 
126  : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
127  Other.P = getEmptyKeyPtr();
128  }
129 
131  if (!isEmptyOrTombstone())
132  delete[] P;
133  }
134 
135  StringRef val() const { return StringRef(P, Size); }
136  uint32_t size() const { return Size; }
137  uint32_t hash() const { return Hash; }
138 
139  operator StringRef() const { return val(); }
140  operator CachedHashStringRef() const {
141  return CachedHashStringRef(val(), Hash);
142  }
143 
144  friend void swap(CachedHashString &LHS, CachedHashString &RHS) {
145  using std::swap;
146  swap(LHS.P, RHS.P);
147  swap(LHS.Size, RHS.Size);
148  swap(LHS.Hash, RHS.Hash);
149  }
150 };
151 
152 template <> struct DenseMapInfo<CachedHashString> {
154  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
155  CachedHashString::getEmptyKeyPtr());
156  }
158  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
159  CachedHashString::getTombstoneKeyPtr());
160  }
161  static unsigned getHashValue(const CachedHashString &S) {
162  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
163  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
164  return S.hash();
165  }
166  static bool isEqual(const CachedHashString &LHS,
167  const CachedHashString &RHS) {
168  if (LHS.hash() != RHS.hash())
169  return false;
170  if (LHS.P == CachedHashString::getEmptyKeyPtr())
171  return RHS.P == CachedHashString::getEmptyKeyPtr();
172  if (LHS.P == CachedHashString::getTombstoneKeyPtr())
173  return RHS.P == CachedHashString::getTombstoneKeyPtr();
174 
175  // This is safe because if RHS.P is the empty or tombstone key, it will have
176  // length 0, so we'll never dereference its pointer.
177  return LHS.val() == RHS.val();
178  }
179 };
180 
181 } // namespace llvm
182 
183 #endif
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::CachedHashString::val
StringRef val() const
Definition: CachedHashString.h:135
llvm::CachedHashString::CachedHashString
CachedHashString(CachedHashString &&Other) noexcept
Definition: CachedHashString.h:125
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::CachedHashStringRef::hash
uint32_t hash() const
Definition: CachedHashString.h:46
StringRef.h
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::DenseMapInfo< CachedHashStringRef >::getHashValue
static unsigned getHashValue(const CachedHashStringRef &S)
Definition: CachedHashString.h:56
llvm::DenseMapInfo< CachedHashString >::getTombstoneKey
static CachedHashString getTombstoneKey()
Definition: CachedHashString.h:157
llvm::CachedHashString::size
uint32_t size() const
Definition: CachedHashString.h:136
llvm::isEqual
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
Definition: GCNRegPressure.cpp:55
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::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::CachedHashString::CachedHashString
CachedHashString(StringRef S)
Definition: CachedHashString.h:100
llvm::CachedHashString::operator=
CachedHashString & operator=(CachedHashString Other)
Definition: CachedHashString.h:120
llvm::DenseMapInfo< CachedHashString >::isEqual
static bool isEqual(const CachedHashString &LHS, const CachedHashString &RHS)
Definition: CachedHashString.h:166
llvm::CachedHashString::CachedHashString
CachedHashString(StringRef S, uint32_t Hash)
Definition: CachedHashString.h:103
llvm::CachedHashString::CachedHashString
CachedHashString(const char *S)
Definition: CachedHashString.h:97
llvm::CachedHashStringRef
A container which contains a StringRef plus a precomputed hash.
Definition: CachedHashString.h:28
llvm::CachedHashString
A container which contains a string, which it owns, plus a precomputed hash.
Definition: CachedHashString.h:71
llvm::CachedHashStringRef::CachedHashStringRef
CachedHashStringRef(StringRef S, uint32_t Hash)
Definition: CachedHashString.h:38
llvm::DenseMapInfo< CachedHashString >::getEmptyKey
static CachedHashString getEmptyKey()
Definition: CachedHashString.h:153
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CachedHashStringRef::size
uint32_t size() const
Definition: CachedHashString.h:45
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
uint32_t
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::DenseMapInfo< CachedHashStringRef >::getTombstoneKey
static CachedHashStringRef getTombstoneKey()
Definition: CachedHashString.h:53
llvm::DenseMapInfo< CachedHashString >::getHashValue
static unsigned getHashValue(const CachedHashString &S)
Definition: CachedHashString.h:161
llvm::CachedHashStringRef::CachedHashStringRef
CachedHashStringRef(StringRef S)
Definition: CachedHashString.h:35
llvm::DenseMapInfo< CachedHashStringRef >::getEmptyKey
static CachedHashStringRef getEmptyKey()
Definition: CachedHashString.h:50
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1854
llvm::CachedHashString::hash
uint32_t hash() const
Definition: CachedHashString.h:137
llvm::CachedHashString::~CachedHashString
~CachedHashString()
Definition: CachedHashString.h:130
P
#define P(N)
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::CachedHashStringRef::val
StringRef val() const
Definition: CachedHashString.h:43
DenseMapInfo.h
llvm::CachedHashString::swap
friend void swap(CachedHashString &LHS, CachedHashString &RHS)
Definition: CachedHashString.h:144
llvm::DenseMapInfo< CachedHashStringRef >::isEqual
static bool isEqual(const CachedHashStringRef &LHS, const CachedHashStringRef &RHS)
Definition: CachedHashString.h:61
llvm::CachedHashStringRef::data
const char * data() const
Definition: CachedHashString.h:44
llvm::CachedHashString::CachedHashString
CachedHashString(const CachedHashString &Other)
Definition: CachedHashString.h:110
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1195