CoalescingBitVector.h Source File (original) (raw)

15#ifndef LLVM_ADT_COALESCINGBITVECTOR_H

16#define LLVM_ADT_COALESCINGBITVECTOR_H

25#include <initializer_list>

27namespace llvm {

39 static_assert(std::is_unsigned::value,

40 "Index must be an unsigned integer.");

49 using IntervalT = std::pair<IndexT, IndexT>;

51public:

57 : Alloc(&Alloc), Intervals(Alloc) {}

63 : Alloc(Other.Alloc), Intervals(*Other.Alloc) {

65 }

70 return *this;

71 }

82 bool empty() const { return Intervals.empty(); }

86 unsigned Bits = 0;

87 for (auto It = Intervals.begin(), End = Intervals.end(); It != End; ++It)

88 Bits += 1 + It.stop() - It.start();

89 return Bits;

90 }

98 assert( test (Index) && "Setting already-set bits not supported/efficient, "

99 "IntervalMap will assert");

101 }

102

103

104

105

106

108 for (auto It = Other.Intervals.begin(), End = Other.Intervals.end();

109 It != End; ++It)

110 insert(It.start(), It.stop());

111 }

112

113

114 void set(std::initializer_list Indices) {

115 for (IndexT Index : Indices)

117 }

118

119

121 const auto It = Intervals.find(Index);

122 if (It == Intervals.end())

123 return false;

124 assert(It.stop() >= Index && "Interval must end after Index");

125 return It.start() <= Index;

126 }

127

128

132 }

133

134

137 if (It == Intervals.end())

138 return;

139

140

141

142

143

144 IndexT Start = It.start();

145 if (Index < Start)

146

147 return;

148 IndexT Stop = It.stop();

149 assert(Index <= Stop && "Wrong interval for index");

150 It.erase();

151 if (Start < Index)

152 insert(Start, Index - 1);

153 if (Index < Stop)

154 insert(Index + 1, Stop);

155 }

156

157

158

160

162 getOverlaps(RHS, Overlaps);

163

164

165 for (auto It = RHS.Intervals.begin(), End = RHS.Intervals.end();

166 It != End; ++It) {

167 IndexT Start = It.start();

168 IndexT Stop = It.stop();

170 getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts);

171 for (IntervalT AdditivePortion : NonOverlappingParts)

172 insert(AdditivePortion.first, AdditivePortion.second);

173 }

174 }

175

176

178

180 getOverlaps(RHS, Overlaps);

181

183 for (IntervalT Overlap : Overlaps)

184 insert(Overlap.first, Overlap.second);

185 }

186

187

190 if (!getOverlaps(Other, Overlaps)) {

191

192 return;

193 }

194

195

196

197 for (IntervalT Overlap : Overlaps) {

198 IndexT OlapStart, OlapStop;

199 std::tie(OlapStart, OlapStop) = Overlap;

200

201 auto It = Intervals.find(OlapStart);

202 IndexT CurrStart = It.start();

203 IndexT CurrStop = It.stop();

204 assert(CurrStart <= OlapStart && OlapStop <= CurrStop &&

205 "Expected some intersection!");

206

207

208

209

210

211 It.erase();

212 if (CurrStart < OlapStart)

213 insert(CurrStart, OlapStart - 1);

214 if (OlapStop < CurrStop)

215 insert(OlapStop + 1, CurrStop);

216 }

217 }

218

220

221

222

223 auto ItL = Intervals.begin();

224 auto ItR = RHS.Intervals.begin();

225 while (ItL != Intervals.end() && ItR != RHS.Intervals.end() &&

226 ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) {

227 ++ItL;

228 ++ItR;

229 }

230 return ItL == Intervals.end() && ItR == RHS.Intervals.end();

231 }

232

234

237

238 public:

244

245 private:

246

247

248 static constexpr unsigned kIteratorAtTheEndOffset = ~0u;

249

250 UnderlyingIterator MapIterator;

251 unsigned OffsetIntoMapIterator = 0;

252

253

254

255 IndexT CachedStart = IndexT();

256 IndexT CachedStop = IndexT();

257

258 void setToEnd() {

259 OffsetIntoMapIterator = kIteratorAtTheEndOffset;

260 CachedStart = IndexT();

261 CachedStop = IndexT();

262 }

263

264

265

266 void resetCache() {

267 if (MapIterator.valid()) {

268 OffsetIntoMapIterator = 0;

269 CachedStart = MapIterator.start();

270 CachedStop = MapIterator.stop();

271 } else {

272 setToEnd();

273 }

274 }

275

276

277

278

279 void advanceTo(IndexT Index) {

280 assert(Index <= CachedStop && "Cannot advance to OOB index");

281 if (Index < CachedStart)

282

283 return;

284 OffsetIntoMapIterator = Index - CachedStart;

285 }

286

287 const_iterator(UnderlyingIterator MapIt) : MapIterator(MapIt) {

288 resetCache();

289 }

290

291 public:

293

295

296

297 return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) ==

298 std::tie(RHS.OffsetIntoMapIterator, RHS.CachedStart,

299 RHS.CachedStop);

300 }

301

304 }

305

306 IndexT operator*() const { return CachedStart + OffsetIntoMapIterator; }

307

309 if (CachedStart + OffsetIntoMapIterator < CachedStop) {

310

311 ++OffsetIntoMapIterator;

312 } else {

313

314 ++MapIterator;

315 resetCache();

316 }

317 return *this;

318 }

319

323 return tmp;

324 }

325

326

327

328

329

331 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)

332 return;

333

334

335 while (Index > CachedStop) {

336 ++MapIterator;

337 resetCache();

338 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)

339 return;

340 }

341

342 advanceTo(Index);

343 }

344 };

345

347

349

350

351

352

353

355 auto UnderlyingIt = Intervals.find(Index);

356 if (UnderlyingIt == Intervals.end())

357 return end();

359 It.advanceTo(Index);

360 return It;

361 }

362

363

364

366 IndexT End) const {

367 assert(Start < End && "Not a valid range");

368 auto StartIt = find(Start);

369 if (StartIt == end() || *StartIt >= End)

370 return {end(), end()};

371 auto EndIt = StartIt;

373 return {StartIt, EndIt};

374 }

375

377 OS << "{";

378 for (auto It = Intervals.begin(), End = Intervals.end(); It != End;

379 ++It) {

380 OS << "[" << It.start();

381 if (It.start() != It.stop())

382 OS << ", " << It.stop();

383 OS << "]";

384 }

385 OS << "}";

386 }

387

388#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

390

391

392 dbgs() << "\n";

394 dbgs() << "\n";

395 }

396#endif

397

398private:

399 void insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); }

400

401

402

403 bool getOverlaps(const ThisT &Other,

404 SmallVectorImpl &Overlaps) const {

405 for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);

406 I.valid(); ++I)

407 Overlaps.emplace_back(I.start(), I.stop());

409 [](IntervalT LHS, IntervalT RHS) {

410 return LHS.second < RHS.first;

411 }) &&

412 "Overlaps must be sorted");

413 return !Overlaps.empty();

414 }

415

416

417

418

419 void getNonOverlappingParts(IndexT Start, IndexT Stop,

420 const SmallVectorImpl &Overlaps,

421 SmallVectorImpl &NonOverlappingParts) {

422 IndexT NextUncoveredBit = Start;

423 for (IntervalT Overlap : Overlaps) {

424 IndexT OlapStart, OlapStop;

425 std::tie(OlapStart, OlapStop) = Overlap;

426

427

428

429 bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop;

430 if (!DoesOverlap)

431 continue;

432

433

434

435 if (NextUncoveredBit < OlapStart)

436 NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1);

437 NextUncoveredBit = OlapStop + 1;

438 if (NextUncoveredBit > Stop)

439 break;

440 }

441 if (NextUncoveredBit <= Stop)

442 NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);

443 }

444

446 MapT Intervals;

447};

448

449}

450

451#endif

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

This file implements a coalescing interval map for small objects.

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

This file defines the SmallVector class.

const_iterator operator++(int)

std::forward_iterator_tag iterator_category

bool operator!=(const const_iterator &RHS) const

bool operator==(const const_iterator &RHS) const

void advanceToLowerBound(IndexT Index)

Advance the iterator to the first set bit AT, OR AFTER, Index.

std::ptrdiff_t difference_type

const_iterator & operator++()

A bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals.

void set(IndexT Index)

Set the bit at Index.

bool operator==(const ThisT &RHS) const

LLVM_DUMP_METHOD void dump() const

iterator_range< const_iterator > half_open_range(IndexT Start, IndexT End) const

Return a range iterator which iterates over all of the set bits in the half-open range [Start,...

void operator|=(const ThisT &RHS)

Set union.

CoalescingBitVector(ThisT &&Other)=delete

bool operator!=(const ThisT &RHS) const

const_iterator end() const

bool test(IndexT Index) const

Check whether the bit at Index is set.

typename MapT::Allocator Allocator

const_iterator begin() const

void operator&=(const ThisT &RHS)

Set intersection.

bool empty() const

Check whether no bits are set.

CoalescingBitVector(Allocator &Alloc)

Construct by passing in a CoalescingBitVector::Allocator reference.

void intersectWithComplement(const ThisT &Other)

Reset all bits present in Other.

const_iterator find(IndexT Index) const

Return an iterator pointing to the first set bit AT, OR AFTER, Index.

void print(raw_ostream &OS) const

ThisT & operator=(const ThisT &Other)

void clear()

Clear all the bits.

CoalescingBitVector(const ThisT &Other)

unsigned count() const

Count the number of set bits.

ThisT & operator=(ThisT &&Other)=delete

void set(const ThisT &Other)

Set the bits set in Other.

void test_and_set(IndexT Index)

Set the bit at Index. Supports setting an already-set bit.

void reset(IndexT Index)

Reset the bit at Index. Supports resetting an already-unset bit.

void set(std::initializer_list< IndexT > Indices)

Set the bits at Indices. Used for testing, primarily.

const_iterator begin() const

void insert(KeyT a, KeyT b, ValT y)

insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.

typename Sizer::Allocator Allocator

const_iterator find(KeyT x) const

find - Return an iterator pointing to the first interval ending at or after x, or end().

friend class const_iterator

bool empty() const

empty - Return true when no intervals are mapped.

const_iterator end() const

void clear()

clear - Remove all entries.

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 class implements an extremely fast bulk output stream that can only output to a stream.

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.

raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

bool is_sorted(R &&Range, Compare C)

Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...