LLVM  15.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 /// \file
10 /// This file defines CachedHashString and CachedHashStringRef. These are
11 /// owning and not-owning string types that store their hash in addition to
12 /// their string data.
13 ///
14 /// Unlike std::string, CachedHashString can be used in DenseSet/DenseMap
15 /// (because, unlike std::string, CachedHashString lets us have empty and
16 /// tombstone values).
17 ///
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_ADT_CACHEDHASHSTRING_H
21 #define LLVM_ADT_CACHEDHASHSTRING_H
22 
23 #include "llvm/ADT/DenseMapInfo.h"
24 #include "llvm/ADT/StringRef.h"
25 
26 namespace llvm {
27 
28 /// A container which contains a StringRef plus a precomputed hash.
30  const char *P;
31  uint32_t Size;
32  uint32_t Hash;
33 
34 public:
35  // Explicit because hashing a string isn't free.
37  : CachedHashStringRef(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
38 
40  : P(S.data()), Size(S.size()), Hash(Hash) {
42  }
43 
44  StringRef val() const { return StringRef(P, Size); }
45  const char *data() const { return P; }
46  uint32_t size() const { return Size; }
47  uint32_t hash() const { return Hash; }
48 };
49 
50 template <> struct DenseMapInfo<CachedHashStringRef> {
53  }
56  }
57  static unsigned getHashValue(const CachedHashStringRef &S) {
58  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
59  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
60  return S.hash();
61  }
62  static bool isEqual(const CachedHashStringRef &LHS,
63  const CachedHashStringRef &RHS) {
64  return LHS.hash() == RHS.hash() &&
66  }
67 };
68 
69 /// A container which contains a string, which it owns, plus a precomputed hash.
70 ///
71 /// We do not null-terminate the string.
74 
75  char *P;
76  uint32_t Size;
77  uint32_t Hash;
78 
79  static char *getEmptyKeyPtr() { return DenseMapInfo<char *>::getEmptyKey(); }
80  static char *getTombstoneKeyPtr() {
82  }
83 
84  bool isEmptyOrTombstone() const {
85  return P == getEmptyKeyPtr() || P == getTombstoneKeyPtr();
86  }
87 
88  struct ConstructEmptyOrTombstoneTy {};
89 
90  CachedHashString(ConstructEmptyOrTombstoneTy, char *EmptyOrTombstonePtr)
91  : P(EmptyOrTombstonePtr), Size(0), Hash(0) {
92  assert(isEmptyOrTombstone());
93  }
94 
95  // TODO: Use small-string optimization to avoid allocating.
96 
97 public:
98  explicit CachedHashString(const char *S) : CachedHashString(StringRef(S)) {}
99 
100  // Explicit because copying and hashing a string isn't free.
102  : CachedHashString(S, DenseMapInfo<StringRef>::getHashValue(S)) {}
103 
105  : P(new char[S.size()]), Size(S.size()), Hash(Hash) {
106  memcpy(P, S.data(), S.size());
107  }
108 
109  // Ideally this class would not be copyable. But SetVector requires copyable
110  // keys, and we want this to be usable there.
112  : Size(Other.Size), Hash(Other.Hash) {
113  if (Other.isEmptyOrTombstone()) {
114  P = Other.P;
115  } else {
116  P = new char[Size];
117  memcpy(P, Other.P, Size);
118  }
119  }
120 
122  swap(*this, Other);
123  return *this;
124  }
125 
127  : P(Other.P), Size(Other.Size), Hash(Other.Hash) {
128  Other.P = getEmptyKeyPtr();
129  }
130 
132  if (!isEmptyOrTombstone())
133  delete[] P;
134  }
135 
136  StringRef val() const { return StringRef(P, Size); }
137  uint32_t size() const { return Size; }
138  uint32_t hash() const { return Hash; }
139 
140  operator StringRef() const { return val(); }
141  operator CachedHashStringRef() const {
142  return CachedHashStringRef(val(), Hash);
143  }
144 
146  using std::swap;
147  swap(LHS.P, RHS.P);
148  swap(LHS.Size, RHS.Size);
149  swap(LHS.Hash, RHS.Hash);
150  }
151 };
152 
153 template <> struct DenseMapInfo<CachedHashString> {
155  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
156  CachedHashString::getEmptyKeyPtr());
157  }
159  return CachedHashString(CachedHashString::ConstructEmptyOrTombstoneTy(),
160  CachedHashString::getTombstoneKeyPtr());
161  }
162  static unsigned getHashValue(const CachedHashString &S) {
163  assert(!isEqual(S, getEmptyKey()) && "Cannot hash the empty key!");
164  assert(!isEqual(S, getTombstoneKey()) && "Cannot hash the tombstone key!");
165  return S.hash();
166  }
167  static bool isEqual(const CachedHashString &LHS,
168  const CachedHashString &RHS) {
169  if (LHS.hash() != RHS.hash())
170  return false;
171  if (LHS.P == CachedHashString::getEmptyKeyPtr())
172  return RHS.P == CachedHashString::getEmptyKeyPtr();
173  if (LHS.P == CachedHashString::getTombstoneKeyPtr())
174  return RHS.P == CachedHashString::getTombstoneKeyPtr();
175 
176  // This is safe because if RHS.P is the empty or tombstone key, it will have
177  // length 0, so we'll never dereference its pointer.
178  return LHS.val() == RHS.val();
179  }
180 };
181 
182 } // namespace llvm
183 
184 #endif
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
llvm::CachedHashString::val
StringRef val() const
Definition: CachedHashString.h:136
llvm::CachedHashString::CachedHashString
CachedHashString(CachedHashString &&Other) noexcept
Definition: CachedHashString.h:126
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::CachedHashStringRef::hash
uint32_t hash() const
Definition: CachedHashString.h:47
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:57
llvm::DenseMapInfo< CachedHashString >::getTombstoneKey
static CachedHashString getTombstoneKey()
Definition: CachedHashString.h:158
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::CachedHashString::size
uint32_t size() const
Definition: CachedHashString.h:137
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
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:101
llvm::CachedHashString::operator=
CachedHashString & operator=(CachedHashString Other)
Definition: CachedHashString.h:121
llvm::DenseMapInfo< CachedHashString >::isEqual
static bool isEqual(const CachedHashString &LHS, const CachedHashString &RHS)
Definition: CachedHashString.h:167
llvm::CachedHashString::CachedHashString
CachedHashString(StringRef S, uint32_t Hash)
Definition: CachedHashString.h:104
llvm::CachedHashString::CachedHashString
CachedHashString(const char *S)
Definition: CachedHashString.h:98
llvm::CachedHashStringRef
A container which contains a StringRef plus a precomputed hash.
Definition: CachedHashString.h:29
llvm::CachedHashString
A container which contains a string, which it owns, plus a precomputed hash.
Definition: CachedHashString.h:72
llvm::CachedHashStringRef::CachedHashStringRef
CachedHashStringRef(StringRef S, uint32_t Hash)
Definition: CachedHashString.h:39
llvm::DenseMapInfo< CachedHashString >::getEmptyKey
static CachedHashString getEmptyKey()
Definition: CachedHashString.h:154
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CachedHashStringRef::size
uint32_t size() const
Definition: CachedHashString.h:46
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
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:58
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:54
llvm::DenseMapInfo< CachedHashString >::getHashValue
static unsigned getHashValue(const CachedHashString &S)
Definition: CachedHashString.h:162
llvm::CachedHashStringRef::CachedHashStringRef
CachedHashStringRef(StringRef S)
Definition: CachedHashString.h:36
llvm::DenseMapInfo< CachedHashStringRef >::getEmptyKey
static CachedHashStringRef getEmptyKey()
Definition: CachedHashString.h:51
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1869
llvm::CachedHashString::hash
uint32_t hash() const
Definition: CachedHashString.h:138
llvm::CachedHashString::~CachedHashString
~CachedHashString()
Definition: CachedHashString.h:131
P
#define P(N)
llvm::CachedHashStringRef::val
StringRef val() const
Definition: CachedHashString.h:44
DenseMapInfo.h
llvm::CachedHashString::swap
friend void swap(CachedHashString &LHS, CachedHashString &RHS)
Definition: CachedHashString.h:145
llvm::DenseMapInfo< CachedHashStringRef >::isEqual
static bool isEqual(const CachedHashStringRef &LHS, const CachedHashStringRef &RHS)
Definition: CachedHashString.h:62
llvm::CachedHashStringRef::data
const char * data() const
Definition: CachedHashString.h:45
llvm::CachedHashString::CachedHashString
CachedHashString(const CachedHashString &Other)
Definition: CachedHashString.h:111
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236