Movatterモバイル変換

Go to the documentation of this file.

1//===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===//

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 implements the SmallPtrSet class. See SmallPtrSet.h for an

10// overview of the algorithm.

11//

12//===----------------------------------------------------------------------===//

14#include "llvm/ADT/SmallPtrSet.h"

15#include "llvm/ADT/DenseMapInfo.h"

16#include "llvm/Support/MathExtras.h"

17#include "llvm/Support/MemAlloc.h"

18#include <algorithm>

19#include <cassert>

20#include <cstdlib>

22using namespacellvm;

24void SmallPtrSetImplBase::shrink_and_clear() {

25assert(!isSmall() &&"Can't shrink a small set!");

26 free(CurArray);

28// Reduce the number of buckets.

29unsignedSize =size();

30CurArraySize =Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32;

31NumNonEmpty =NumTombstones = 0;

33// Install the new array. Clear all the buckets to empty.

34CurArray = (constvoid**)safe_malloc(sizeof(void*) *CurArraySize);

36 memset(CurArray, -1,CurArraySize*sizeof(void*));

37}

39std::pair<const void *const *, bool>

40SmallPtrSetImplBase::insert_imp_big(constvoid *Ptr) {

41if (LLVM_UNLIKELY(size() * 4 >=CurArraySize * 3)) {

42// If more than 3/4 of the array is full, grow.

43 Grow(CurArraySize < 64 ? 128 :CurArraySize * 2);

44 }elseif (LLVM_UNLIKELY(CurArraySize -NumNonEmpty <CurArraySize / 8)) {

45// If fewer of 1/8 of the array is empty (meaning that many are filled with

46// tombstones), rehash.

47 Grow(CurArraySize);

48 }

50// Okay, we know we have space. Find a hash bucket.

51constvoid **Bucket =const_cast<constvoid**>(FindBucketFor(Ptr));

52if (*Bucket ==Ptr)

53return std::make_pair(Bucket,false);// Already inserted, good.

55// Otherwise, insert it!

56if (*Bucket ==getTombstoneMarker())

57 --NumTombstones;

58else

59 ++NumNonEmpty;// Track density.

60 *Bucket =Ptr;

61incrementEpoch();

62return std::make_pair(Bucket,true);

63}

65constvoid *const *SmallPtrSetImplBase::doFind(constvoid *Ptr) const{

66unsigned BucketNo =

67DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize - 1);

68unsigned ProbeAmt = 1;

69while (true) {

70constvoid *const *Bucket =CurArray + BucketNo;

71if (LLVM_LIKELY(*Bucket ==Ptr))

72return Bucket;

73if (LLVM_LIKELY(*Bucket ==getEmptyMarker()))

74returnnullptr;

76// Otherwise, it's a hash collision or a tombstone, continue quadratic

77// probing.

78 BucketNo += ProbeAmt++;

79 BucketNo &=CurArraySize - 1;

80 }

81}

83constvoid *const *SmallPtrSetImplBase::FindBucketFor(constvoid *Ptr) const{

84unsigned Bucket =DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);

85unsigned ArraySize =CurArraySize;

86unsigned ProbeAmt = 1;

87constvoid *const *Array =CurArray;

88constvoid *const *Tombstone =nullptr;

89while (true) {

90// If we found an empty bucket, the pointer doesn't exist in the set.

91// Return a tombstone if we've seen one so far, or the empty bucket if

92// not.

93if (LLVM_LIKELY(Array[Bucket] ==getEmptyMarker()))

94return Tombstone ? Tombstone : Array+Bucket;

96// Found Ptr's bucket?

97if (LLVM_LIKELY(Array[Bucket] ==Ptr))

98return Array+Bucket;

100// If this is a tombstone, remember it. If Ptr ends up not in the set, we

101// prefer to return it than something that would require more probing.

102if (Array[Bucket] ==getTombstoneMarker() && !Tombstone)

103 Tombstone = Array+Bucket;// Remember the first tombstone found.

104

105// It's a hash collision or a tombstone. Reprobe.

106 Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);

107 }

108}

109

110/// Grow - Allocate a larger backing store for the buckets and move it over.

111///

112void SmallPtrSetImplBase::Grow(unsigned NewSize) {

113constvoid **OldBuckets =CurArray;

114constvoid **OldEnd =EndPointer();

115bool WasSmall =isSmall();

116

117// Install the new array. Clear all the buckets to empty.

118constvoid **NewBuckets = (constvoid**)safe_malloc(sizeof(void*) * NewSize);

119

120// Reset member only if memory was allocated successfully

121CurArray = NewBuckets;

122CurArraySize = NewSize;

123 memset(CurArray, -1, NewSize*sizeof(void*));

124

125// Copy over all valid entries.

126for (constvoid **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) {

127// Copy over the element if it is valid.

128constvoid *Elt = *BucketPtr;

129if (Elt !=getTombstoneMarker() && Elt !=getEmptyMarker())

130 *const_cast<void**>(FindBucketFor(Elt)) =const_cast<void*>(Elt);

131 }

132

133if (!WasSmall)

134 free(OldBuckets);

135NumNonEmpty -=NumTombstones;

136NumTombstones = 0;

137IsSmall =false;

138}

139

140SmallPtrSetImplBase::SmallPtrSetImplBase(constvoid **SmallStorage,

141constSmallPtrSetImplBase &that) {

142IsSmall = that.isSmall();

143if (IsSmall) {

144// If we're becoming small, prepare to insert into our stack space

145CurArray = SmallStorage;

146 }else {

147// Otherwise, allocate new heap space (unless we were the same size)

148CurArray = (constvoid**)safe_malloc(sizeof(void*) * that.CurArraySize);

149 }

150

151// Copy over the that array.

152 copyHelper(that);

153}

154

155SmallPtrSetImplBase::SmallPtrSetImplBase(constvoid **SmallStorage,

156unsigned SmallSize,

157constvoid **RHSSmallStorage,

158SmallPtrSetImplBase &&that) {

159 moveHelper(SmallStorage, SmallSize, RHSSmallStorage, std::move(that));

160}

161

162voidSmallPtrSetImplBase::copyFrom(constvoid **SmallStorage,

163constSmallPtrSetImplBase &RHS) {

164assert(&RHS !=this &&"Self-copy should be handled by the caller.");

165

166if (isSmall() &&RHS.isSmall())

167assert(CurArraySize ==RHS.CurArraySize &&

168"Cannot assign sets with different small sizes");

169

170// If we're becoming small, prepare to insert into our stack space

171if (RHS.isSmall()) {

172if (!isSmall())

173 free(CurArray);

174CurArray = SmallStorage;

175IsSmall =true;

176// Otherwise, allocate new heap space (unless we were the same size)

177 }elseif (CurArraySize !=RHS.CurArraySize) {

178if (isSmall())

179CurArray = (constvoid**)safe_malloc(sizeof(void*) *RHS.CurArraySize);

180else {

181constvoid **T = (constvoid**)safe_realloc(CurArray,

182sizeof(void*) *RHS.CurArraySize);

183CurArray =T;

184 }

185IsSmall =false;

186 }

187

188 copyHelper(RHS);

189}

190

191void SmallPtrSetImplBase::copyHelper(constSmallPtrSetImplBase &RHS) {

192// Copy over the new array size

193CurArraySize =RHS.CurArraySize;

194

195// Copy over the contents from the other set

196 std::copy(RHS.CurArray,RHS.EndPointer(),CurArray);

197

198NumNonEmpty =RHS.NumNonEmpty;

199NumTombstones =RHS.NumTombstones;

200}

201

202voidSmallPtrSetImplBase::moveFrom(constvoid **SmallStorage,

203unsigned SmallSize,

204constvoid **RHSSmallStorage,

205SmallPtrSetImplBase &&RHS) {

206if (!isSmall())

207 free(CurArray);

208 moveHelper(SmallStorage, SmallSize, RHSSmallStorage, std::move(RHS));

209}

210

211void SmallPtrSetImplBase::moveHelper(constvoid **SmallStorage,

212unsigned SmallSize,

213constvoid **RHSSmallStorage,

214SmallPtrSetImplBase &&RHS) {

215assert(&RHS !=this &&"Self-move should be handled by the caller.");

216

217if (RHS.isSmall()) {

218// Copy a small RHS rather than moving.

219CurArray = SmallStorage;

220 std::copy(RHS.CurArray,RHS.CurArray +RHS.NumNonEmpty,CurArray);

221 }else {

222CurArray =RHS.CurArray;

223RHS.CurArray = RHSSmallStorage;

224 }

225

226// Copy the rest of the trivial members.

227CurArraySize =RHS.CurArraySize;

228NumNonEmpty =RHS.NumNonEmpty;

229NumTombstones =RHS.NumTombstones;

230IsSmall =RHS.IsSmall;

231

232// Make the RHS small and empty.

233RHS.CurArraySize = SmallSize;

234RHS.NumNonEmpty = 0;

235RHS.NumTombstones = 0;

236RHS.IsSmall =true;

237}

238

239voidSmallPtrSetImplBase::swap(constvoid **SmallStorage,

240constvoid **RHSSmallStorage,

241SmallPtrSetImplBase &RHS) {

242if (this == &RHS)return;

243

244// We can only avoid copying elements if neither set is small.

245if (!this->isSmall() && !RHS.isSmall()) {

246std::swap(this->CurArray, RHS.CurArray);

247std::swap(this->CurArraySize, RHS.CurArraySize);

248std::swap(this->NumNonEmpty,RHS.NumNonEmpty);

249std::swap(this->NumTombstones, RHS.NumTombstones);

250return;

251 }

252

253// FIXME: From here on we assume that both sets have the same small size.

254

255// If only RHS is small, copy the small elements into LHS and move the pointer

256// from LHS to RHS.

257if (!this->isSmall() && RHS.isSmall()) {

258 std::copy(RHS.CurArray,RHS.CurArray +RHS.NumNonEmpty, SmallStorage);

259std::swap(RHS.CurArraySize, this->CurArraySize);

260std::swap(this->NumNonEmpty,RHS.NumNonEmpty);

261std::swap(this->NumTombstones, RHS.NumTombstones);

262RHS.CurArray = this->CurArray;

263 RHS.IsSmall =false;

264 this->CurArray = SmallStorage;

265 this->IsSmall =true;

266return;

267 }

268

269// If only LHS is small, copy the small elements into RHS and move the pointer

270// from RHS to LHS.

271if (this->isSmall() && !RHS.isSmall()) {

272 std::copy(this->CurArray, this->CurArray + this->NumNonEmpty,

273 RHSSmallStorage);

274std::swap(RHS.CurArraySize, this->CurArraySize);

275std::swap(RHS.NumNonEmpty, this->NumNonEmpty);

276std::swap(RHS.NumTombstones, this->NumTombstones);

277 this->CurArray = RHS.CurArray;

278 this->IsSmall =false;

279 RHS.CurArray = RHSSmallStorage;

280RHS.IsSmall =true;

281return;

282 }

283

284// Both a small, just swap the small elements.

285assert(this->isSmall() && RHS.isSmall());

286unsigned MinNonEmpty = std::min(this->NumNonEmpty,RHS.NumNonEmpty);

287 std::swap_ranges(this->CurArray, this->CurArray + MinNonEmpty,RHS.CurArray);

288if (this->NumNonEmpty > MinNonEmpty) {

289 std::copy(this->CurArray + MinNonEmpty, this->CurArray + this->NumNonEmpty,

290RHS.CurArray + MinNonEmpty);

291 }else {

292 std::copy(RHS.CurArray + MinNonEmpty,RHS.CurArray +RHS.NumNonEmpty,

293 this->CurArray + MinNonEmpty);

294 }

295assert(this->CurArraySize == RHS.CurArraySize);

296std::swap(this->NumNonEmpty,RHS.NumNonEmpty);

297std::swap(this->NumTombstones, RHS.NumTombstones);

298}

LLVM_UNLIKELY

#define LLVM_UNLIKELY(EXPR)

Definition:Compiler.h:320

LLVM_LIKELY

#define LLVM_LIKELY(EXPR)

Definition:Compiler.h:319

DenseMapInfo.h

This file defines DenseMapInfo traits for DenseMap.

Size

uint64_t Size

Definition:ELFObjHandler.cpp:81

MathExtras.h

MemAlloc.h

This file defines counterparts of C library allocation functions defined in the namespace 'std'.

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

SmallPtrSet.h

This file defines the SmallPtrSet class.

Ptr

@ Ptr

Definition:TargetLibraryInfo.cpp:77

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

llvm::DebugEpochBase::incrementEpoch

void incrementEpoch()

Definition:EpochTracker.h:90

llvm::SmallPtrSetImplBase

SmallPtrSetImplBase - This is the common code shared among all the SmallPtrSet<>'s,...

Definition:SmallPtrSet.h:52

llvm::SmallPtrSetImplBase::size

size_type size() const

Definition:SmallPtrSet.h:94

llvm::SmallPtrSetImplBase::NumTombstones

unsigned NumTombstones

Number of tombstones in CurArray.

Definition:SmallPtrSet.h:66

llvm::SmallPtrSetImplBase::SmallPtrSetImplBase

SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that)

Definition:SmallPtrSet.cpp:140

llvm::SmallPtrSetImplBase::isSmall

bool isSmall() const

Definition:SmallPtrSet.h:233

llvm::SmallPtrSetImplBase::CurArray

const void ** CurArray

The current set of buckets, in either small or big representation.

Definition:SmallPtrSet.h:57

llvm::SmallPtrSetImplBase::IsSmall

bool IsSmall

Whether the set is in small representation.

Definition:SmallPtrSet.h:68

llvm::SmallPtrSetImplBase::copyFrom

void copyFrom(const void **SmallStorage, const SmallPtrSetImplBase &RHS)

Definition:SmallPtrSet.cpp:162

llvm::SmallPtrSetImplBase::NumNonEmpty

unsigned NumNonEmpty

Number of elements in CurArray that contain a value or are a tombstone.

Definition:SmallPtrSet.h:64

llvm::SmallPtrSetImplBase::moveFrom

void moveFrom(const void **SmallStorage, unsigned SmallSize, const void **RHSSmallStorage, SmallPtrSetImplBase &&RHS)

Definition:SmallPtrSet.cpp:202

llvm::SmallPtrSetImplBase::CurArraySize

unsigned CurArraySize

CurArraySize - The allocated size of CurArray, always a power of two.

Definition:SmallPtrSet.h:59

llvm::SmallPtrSetImplBase::EndPointer

const void ** EndPointer() const

Definition:SmallPtrSet.h:142

llvm::SmallPtrSetImplBase::getEmptyMarker

static void * getEmptyMarker()

Definition:SmallPtrSet.h:136

llvm::SmallPtrSetImplBase::getTombstoneMarker

static void * getTombstoneMarker()

Definition:SmallPtrSet.h:134

llvm::SmallPtrSetImplBase::swap

void swap(const void **SmallStorage, const void **RHSSmallStorage, SmallPtrSetImplBase &RHS)

swap - Swaps the elements of two sets.

Definition:SmallPtrSet.cpp:239

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::Log2_32_Ceil

unsigned Log2_32_Ceil(uint32_t Value)

Return the ceil log base 2 of the specified value, 32 if the value is zero.

Definition:MathExtras.h:354

llvm::safe_malloc

LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)

Definition:MemAlloc.h:25

llvm::safe_realloc

LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_realloc(void *Ptr, size_t Sz)

Definition:MemAlloc.h:52

std::swap

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

Definition:BitVector.h:860

llvm::DenseMapInfo

An information struct used to provide DenseMap with the various necessary components for a given valu...

Definition:DenseMapInfo.h:52