EquivalenceClasses.h Source File (original) (raw)

15#ifndef LLVM_ADT_EQUIVALENCECLASSES_H

16#define LLVM_ADT_EQUIVALENCECLASSES_H

23#include

24#include

25#include

26#include

28namespace llvm {

63public:

74 class ECValue {

77 mutable const ECValue *Leader, *Next;

78 ElemTy Data;

82 ECValue(const ElemTy &Elt)

83 : Leader(this),

84 Next(reinterpret_cast<ECValue *>(static_cast<intptr_t>(1))),

85 Data(Elt) {}

87 const ECValue *getLeader() const {

89 return this;

91 return Leader;

93 return Leader = Leader->getLeader();

94 }

96 const ECValue *getEndOfList() const {

97 assert(isLeader() && "Cannot get the end of a list for a non-leader!");

98 return Leader;

99 }

100

101 void setNext(const ECValue *NewNext) const {

102 assert(getNext() == nullptr && "Already has a next pointer!");

103 Next = reinterpret_cast<const ECValue *>(

104 reinterpret_cast<intptr_t>(NewNext) |

105 static_cast<intptr_t>(isLeader()));

106 }

107

108 public:

110 : Leader(this),

111 Next(reinterpret_cast<ECValue *>(static_cast<intptr_t>(1))),

112 Data(RHS.Data) {

113

114 assert(RHS.isLeader() && RHS.getNext() == nullptr && "Not a singleton!");

115 }

116

117 bool isLeader() const { return (intptr_t)Next & 1; }

118 const ElemTy &getData() const { return Data; }

119

121 return reinterpret_cast<ECValue *>(reinterpret_cast<intptr_t>(Next) &

122 ~static_cast<intptr_t>(1));

123 }

124 };

125

126private:

127

128

130

131

133

135

136public:

139

141 TheMapping.clear();

142 Members.clear();

143 for (const auto &E : RHS)

144 if (E->isLeader()) {

145 member_iterator MI = RHS.member_begin(*E);

149 }

150 return *this;

151 }

152

153

154

155

156

157

159

162

163 bool empty() const { return TheMapping.empty(); }

164

165

166 class member_iterator;

168

169 return member_iterator(ECV.isLeader() ? &ECV : nullptr);

170 }

171

172 member_iterator member_end() const { return member_iterator(nullptr); }

173

177

181

182

183 [[nodiscard]] bool contains(const ElemTy &V) const {

184 return TheMapping.contains(V);

185 }

186

187

188

189

195

196

197

198

204

205

206

208 unsigned NC = 0;

209 for (const auto &E : *this)

210 if (E->isLeader())

211 ++NC;

212 return NC;

213 }

214

215

216

217

218

219

221 auto [I, Inserted] = TheMapping.try_emplace(Data);

222 if (!Inserted)

223 return *I->second;

224

225 auto *ECV = new (ECValueAllocator) ECValue(Data);

226 I->second = ECV;

227 Members.push_back(ECV);

228 return *ECV;

229 }

230

231

232

233 bool erase(const ElemTy &V) {

234 if (!TheMapping.contains(V))

235 return false;

236 const ECValue *Cur = TheMapping[V];

237 const ECValue *Next = Cur->getNext();

238

239

240

241

242 if (Cur->isLeader() && Next) {

243 Next->Leader = Cur->Leader;

244 Next->Next = reinterpret_cast<const ECValue *>(

245 reinterpret_cast<intptr_t>(Next->Next) | static_cast<intptr_t>(1));

246

247 const ECValue *NewLeader = Next;

248 while ((Next = Next->getNext())) {

249 Next->Leader = NewLeader;

250 }

251 } else if (!Cur->isLeader()) {

252 const ECValue *Leader = findLeader(V).Node;

253 const ECValue *Pre = Leader;

254 while (Pre->getNext() != Cur) {

255 Pre = Pre->getNext();

256 }

258

259

260

261

262 Pre->Next = reinterpret_cast<const ECValue *>(

263 static_cast<intptr_t>(Pre->isLeader()));

264 Leader->Leader = Pre;

265 } else {

266

267

268 Pre->Next = reinterpret_cast<const ECValue *>(

269 reinterpret_cast<intptr_t>(Next) |

270 static_cast<intptr_t>(Pre->isLeader()));

271 Next->Leader = Pre;

272 }

273 }

274

275

276 assert(TheMapping.contains(V) && "Can't find input in TheMapping!");

277 TheMapping.erase(V);

278 auto I = find(Members, Cur);

279 assert(I != Members.end() && "Can't find input in members!");

280 Members.erase(I);

281 return true;

282 }

283

284

285

286

287

288 member_iterator findLeader(const ElemTy &V) const {

289 auto I = TheMapping.find(V);

290 if (I == TheMapping.end())

291 return member_iterator(nullptr);

293 }

294 member_iterator findLeader(const ECValue &ECV) const {

295 return member_iterator(ECV.getLeader());

296 }

297

298

299

300 member_iterator unionSets(const ElemTy &V1, const ElemTy &V2) {

301 const ECValue &V1I = insert(V1), &V2I = insert(V2);

303 }

304 member_iterator unionSets(member_iterator L1, member_iterator L2) {

306 if (L1 == L2)

307 return L1;

308

309

310

311 const ECValue &L1LV = *L1.Node, &L2LV = *L2.Node;

312 L1LV.getEndOfList()->setNext(&L2LV);

313

314

315 L1LV.Leader = L2LV.getEndOfList();

316

317

318 L2LV.Next = L2LV.getNext();

319

320

321 L2LV.Leader = &L1LV;

322 return L1;

323 }

324

325

326

327 bool isEquivalent(const ElemTy &V1, const ElemTy &V2) const {

328

329 if (V1 == V2)

330 return true;

333 }

334

337

339

340 public:

347

350

352 assert(Node != nullptr && "Dereferencing end()!");

353 return Node->getData();

354 }

356

358 assert(Node != nullptr && "++'d off the end of the list!");

359 Node = Node->getNext();

360 return *this;

361 }

362

365 ++*this;

366 return tmp;

367 }

368

370 return Node == RHS.Node;

371 }

373 return Node != RHS.Node;

374 }

375 };

376};

377

378}

379

380#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file defines the BumpPtrAllocator interface.

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file defines the DenseMap class.

This file defines the SmallVector class.

ECValue - The EquivalenceClasses data structure is just a set of these.

Definition EquivalenceClasses.h:74

bool isLeader() const

Definition EquivalenceClasses.h:117

const ECValue * getNext() const

Definition EquivalenceClasses.h:120

friend class EquivalenceClasses

Definition EquivalenceClasses.h:75

ECValue(const ECValue &RHS)

Definition EquivalenceClasses.h:109

const ElemTy & getData() const

Definition EquivalenceClasses.h:118

std::forward_iterator_tag iterator_category

Definition EquivalenceClasses.h:341

std::size_t size_type

Definition EquivalenceClasses.h:343

value_type * pointer

Definition EquivalenceClasses.h:345

member_iterator(const ECValue *N)

Definition EquivalenceClasses.h:349

member_iterator & operator++()

Definition EquivalenceClasses.h:357

friend class EquivalenceClasses

Definition EquivalenceClasses.h:336

member_iterator()=default

std::ptrdiff_t difference_type

Definition EquivalenceClasses.h:344

const ElemTy value_type

Definition EquivalenceClasses.h:342

pointer operator->() const

Definition EquivalenceClasses.h:355

member_iterator operator++(int)

Definition EquivalenceClasses.h:363

value_type & reference

Definition EquivalenceClasses.h:346

reference operator*() const

Definition EquivalenceClasses.h:351

bool operator!=(const member_iterator &RHS) const

Definition EquivalenceClasses.h:372

bool operator==(const member_iterator &RHS) const

Definition EquivalenceClasses.h:369

EquivalenceClasses()=default

iterator begin() const

Definition EquivalenceClasses.h:160

member_iterator member_begin(const ECValue &ECV) const

Definition EquivalenceClasses.h:167

iterator_range< member_iterator > members(const ECValue &ECV) const

Definition EquivalenceClasses.h:174

bool contains(const ElemTy &V) const

Returns true if V is contained an equivalence class.

Definition EquivalenceClasses.h:183

member_iterator findLeader(const ECValue &ECV) const

Definition EquivalenceClasses.h:294

bool empty() const

Definition EquivalenceClasses.h:163

const ElemTy & getOrInsertLeaderValue(const ElemTy &V)

getOrInsertLeaderValue - Return the leader for the specified value that is in the set.

Definition EquivalenceClasses.h:199

const ECValue & insert(const ElemTy &Data)

insert - Insert a new value into the union/find set, ignoring the request if the value already exists...

Definition EquivalenceClasses.h:220

bool isEquivalent(const ElemTy &V1, const ElemTy &V2) const

Definition EquivalenceClasses.h:327

member_iterator member_end() const

Definition EquivalenceClasses.h:172

const ElemTy & getLeaderValue(const ElemTy &V) const

getLeaderValue - Return the leader for the specified value that is in the set.

Definition EquivalenceClasses.h:190

iterator_range< member_iterator > members(const ElemTy &V) const

Definition EquivalenceClasses.h:178

EquivalenceClasses & operator=(const EquivalenceClasses &RHS)

Definition EquivalenceClasses.h:140

iterator end() const

Definition EquivalenceClasses.h:161

typename SmallVector< const ECValue * >::const_iterator iterator

iterator* - Provides a way to iterate over all values in the set.

Definition EquivalenceClasses.h:158

member_iterator findLeader(const ElemTy &V) const

findLeader - Given a value in the set, return a member iterator for the equivalence class it is in.

Definition EquivalenceClasses.h:288

unsigned getNumClasses() const

getNumClasses - Return the number of equivalence classes in this set.

Definition EquivalenceClasses.h:207

member_iterator unionSets(member_iterator L1, member_iterator L2)

Definition EquivalenceClasses.h:304

member_iterator unionSets(const ElemTy &V1, const ElemTy &V2)

union - Merge the two equivalence sets for the specified values, inserting them if they do not alread...

Definition EquivalenceClasses.h:300

bool erase(const ElemTy &V)

erase - Erase a value from the union/find set, return "true" if erase succeeded, or "false" when the ...

Definition EquivalenceClasses.h:233

EquivalenceClasses(const EquivalenceClasses &RHS)

Definition EquivalenceClasses.h:138

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

A range adaptor for a pair of iterators.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

This is an optimization pass for GlobalISel generic memory operations.

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

FunctionAddr VTableAddr uintptr_t uintptr_t Data

FunctionAddr VTableAddr Next

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.