EquivalenceClasses.h Source File (original) (raw)

15#ifndef LLVM_ADT_EQUIVALENCECLASSES_H

16#define LLVM_ADT_EQUIVALENCECLASSES_H

18#include

19#include

20#include

21#include

22#include

24namespace llvm {

59template <class ElemTy, class Compare = std::less>

71 class ECValue {

74 mutable const ECValue *Leader, *Next;

75 ElemTy Data;

79 ECValue(const ElemTy &Elt)

80 : Leader(this), Next((ECValue*)(intptr_t)1), Data(Elt) {}

82 const ECValue *getLeader() const {

83 if (isLeader()) return this;

84 if (Leader->isLeader()) return Leader;

86 return Leader = Leader->getLeader();

87 }

89 const ECValue *getEndOfList() const {

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

91 return Leader;

92 }

94 void setNext(const ECValue *NewNext) const {

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

96 Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader());

97 }

99 public:

100 ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1),

101 Data(RHS.Data) {

102

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

104 }

105

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

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

108

109 const ECValue *getNext() const {

110 return (ECValue*)((intptr_t)Next & ~(intptr_t)1);

111 }

112 };

113

114

115 struct ECValueComparator {

116 using is_transparent = void;

117

118 ECValueComparator() : compare(Compare()) {}

119

120 bool operator()(const ECValue &lhs, const ECValue &rhs) const {

121 return compare(lhs.Data, rhs.Data);

122 }

123

124 template

125 bool operator()(const T &lhs, const ECValue &rhs) const {

126 return compare(lhs, rhs.Data);

127 }

128

129 template

130 bool operator()(const ECValue &lhs, const T &rhs) const {

131 return compare(lhs.Data, rhs);

132 }

133

134 const Compare compare;

135 };

136

137

138

139 std::set<ECValue, ECValueComparator> TheMapping;

140

141public:

145 }

146

148 TheMapping.clear();

150 if (I->isLeader()) {

155 }

156 return *this;

157 }

158

159

160

161

162

163

165 typename std::set<ECValue, ECValueComparator>::const_iterator;

166

169

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

171

172

173 class member_iterator;

175

177 }

180 }

181

182

183

185 return TheMapping.find(V);

186 }

187

188

189

190

194 return *MI;

195 }

196

197

198

199

203 return *MI;

204 }

205

206

207

209 unsigned NC = 0;

211 if (I->isLeader()) ++NC;

212 return NC;

213 }

214

215

216

217

218

219

221 return TheMapping.insert(ECValue(Data)).first;

222 }

223

224

225

226

227

229 if (I == TheMapping.end()) return member_end();

231 }

233 return findLeader(TheMapping.find(V));

234 }

235

236

237

241 }

244 if (L1 == L2) return L1;

245

246

247

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

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

250

251

252 L1LV.Leader = L2LV.getEndOfList();

253

254

255 L2LV.Next = L2LV.getNext();

256

257

258 L2LV.Leader = &L1LV;

259 return L1;

260 }

261

262

263

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

265

266 if (V1 == V2)

267 return true;

270 }

271

274

275 const ECValue *Node;

276

277 public:

284

287

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

290 return Node->getData();

291 }

293

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

297 return *this;

298 }

299

302 ++*this;

303 return tmp;

304 }

305

308 }

311 }

312 };

313};

314

315}

316

317#endif

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

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

bool operator!=(const member_iterator &RHS) const

bool operator==(const member_iterator &RHS) const

member_iterator(const ECValue *N)

member_iterator & operator++()

pointer operator->() const

member_iterator operator++(int)

reference operator*() const

std::forward_iterator_tag iterator_category

member_iterator()=default

std::ptrdiff_t difference_type

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...

iterator findValue(const ElemTy &V) const

findValue - Return an iterator to the specified value.

member_iterator findLeader(iterator I) const

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

const ElemTy & getOrInsertLeaderValue(const ElemTy &V)

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

iterator insert(const ElemTy &Data)

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

member_iterator member_end() const

unsigned getNumClasses() const

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

typename std::set< ECValue, ECValueComparator >::const_iterator iterator

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

member_iterator findLeader(const ElemTy &V) const

member_iterator member_begin(iterator I) const

EquivalenceClasses()=default

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...

const EquivalenceClasses & operator=(const EquivalenceClasses &RHS)

EquivalenceClasses(const EquivalenceClasses &RHS)

member_iterator unionSets(member_iterator L1, member_iterator L2)

const ElemTy & getLeaderValue(const ElemTy &V) const

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

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

This is an optimization pass for GlobalISel generic memory operations.