[ADT] Explicitly delete copy/move constructors and operator= in IntervalMap

The default implementations will perform a shallow copy instead of a deep
copy, causing some internal data structures to b

[ADT] Explicitly delete copy/move constructors and operator= in IntervalMap

The default implementations will perform a shallow copy instead of a deep
copy, causing some internal data structures to be shared between different
objects. Disable these operations so they don't get accidentally used.

Differential Revision: https://reviews.llvm.org/D126401

show more ...

[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3]

Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to
address a compile-time explosion issue in LiveDebugValues.

--

[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3]

Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to
address a compile-time explosion issue in LiveDebugValues.

---

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

CoalescingBitVector efficiently represents sets which predominantly
contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues,
which are very long sequences that look like {1, 2, 3, ...}). OTOH,
CoalescingBitVector isn't good at representing sets with lots of gaps
between elements. The first N coalesced intervals of set bits are stored
in-place (in the initial heap allocation).

Compared to SparseBitVector, CoalescingBitVector offers more predictable
performance for non-sequential find() operations. This provides a
crucial speedup in LiveDebugValues.

Differential Revision: https://reviews.llvm.org/D74984

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[ADT] IntervalMap: add overlaps(a, b) method

Summary:
This function checks whether the mappings in the interval map overlap
with the given range [a;b]. The motivation is to enable checking for
overl

[ADT] IntervalMap: add overlaps(a, b) method

Summary:
This function checks whether the mappings in the interval map overlap
with the given range [a;b]. The motivation is to enable checking for
overlap before inserting a new interval into the map.

Reviewers: vsk, dblaikie

Subscribers: dexonsmith, kristina, llvm-commits

Differential Revision: https://reviews.llvm.org/D55760

llvm-svn: 349898

show more ...

[ADT] IntervalMap: fix setStart and setStop

Summary:
These functions currently require that the new closed interval has a length of
at least 2. They also currently permit empty half-open intervals.

[ADT] IntervalMap: fix setStart and setStop

Summary:
These functions currently require that the new closed interval has a length of
at least 2. They also currently permit empty half-open intervals. This patch
defines nonEmpty in each traits structure and uses it to correct the
implementations of setStart and setStop.

Reviewers: stoklund, chandlerc

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D26064

llvm-svn: 285957

show more ...

Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo sees
monotonic keys.

llvm-svn: 122093

It is allowed to call IntervalMap::const_iterator::advanceTo() with a key that
moves the iterator to end(), and it is valid to call it on end().

That means it is valid to call advanceTo() with any m

It is allowed to call IntervalMap::const_iterator::advanceTo() with a key that
moves the iterator to end(), and it is valid to call it on end().

That means it is valid to call advanceTo() with any monotonic key sequence.

llvm-svn: 122092

show more ...

Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap.

llvm-svn: 122081

Complete tests for IntervalMapOverlaps.

llvm-svn: 122019

Add basic test exposing many bugs.

llvm-svn: 121995

Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limited
editing of the current interval.

These methods may cause coalescing, there are corresponding set*Unchecked
methods for edi

Add IntervalMap::iterator::set{Start,Stop,Value} methods that allow limited
editing of the current interval.

These methods may cause coalescing, there are corresponding set*Unchecked
methods for editing without coalescing. The non-coalescing methods are useful
for applying monotonic transforms to all keys or values in a map without
accidentally coalescing transformed and untransformed intervals.

llvm-svn: 120829

show more ...

Disallow overlapping inserts, even when inserting the same value.

We always disallowed overlapping inserts with different values, and this makes
the insertion code smaller and faster.

If an overwri

Disallow overlapping inserts, even when inserting the same value.

We always disallowed overlapping inserts with different values, and this makes
the insertion code smaller and faster.

If an overwriting insert is needed, it can be added as a separate method that
trims any existing intervals before inserting. The immediate use cases for
IntervalMap don't need this - they only use disjoint insertions.

llvm-svn: 120264

show more ...

Add default constructors for iterators.

These iterators don't point anywhere, and they can't be compared to anything.
They are only good for assigning to.

llvm-svn: 120239

Implement const_iterator::advanceTo().

This is a version of find() that always searches forwards and is faster for
local searches.

llvm-svn: 120237

Add more tests for erase(). Fix a few exposed bugs.

llvm-svn: 120227

Add test case with randomly ordered insertions, massive coalescing.

Implement iterator::erase() in a simple version that erases nodes when they
become empty, but doesn't try to redistribute elements

Add test case with randomly ordered insertions, massive coalescing.

Implement iterator::erase() in a simple version that erases nodes when they
become empty, but doesn't try to redistribute elements among siblings for better
packing.

Handle coalescing across leaf nodes which may require erasing entries.

llvm-svn: 120226

show more ...

Add B+-tree test case that creates a height 3 tree with a smaller root node.

Change temporary debugging code to write a dot file directly.

llvm-svn: 120171

Implement IntervalMap::clear().

llvm-svn: 119872

Support backwards iteration starting from end().

llvm-svn: 119871

Add ADT/IntervalMap.

This is a sorted interval map data structure for small keys and values with
automatic coalescing and bidirectional iteration over coalesced intervals.

Except for coalescing int

Add ADT/IntervalMap.

This is a sorted interval map data structure for small keys and values with
automatic coalescing and bidirectional iteration over coalesced intervals.

Except for coalescing intervals, it provides similar functionality to std::map.
It is however much more compact for small keys and values, and hopefully faster
too.

The container object itself can hold the first few intervals without any
allocations, then it switches to a cache conscious B+-tree representation. A
recycling allocator can be shared between many containers, even between
containers holding different types.

The IntervalMap is initially intended to be used with SlotIndex intervals for:

- Backing store for LiveIntervalUnion that is smaller and faster than std::set.

- Backing store for LiveInterval with less overhead than std::vector for typical
intervals and O(N log N) merging of large intervals. 99% of virtual registers
need 4 entries or less and would benefit from the small object optimization.

- Backing store for LiveDebugVariable which doesn't exist yet, but will track
debug variables during register allocation.

This is a work in progress. Missing items are:

- Performance metrics.
- erase().
- insert() shrinkage.
- clear().
- More performance metrics.
- Simplification and detemplatization.

llvm-svn: 119787

show more ...

Add ADT/IntervalMap.

This is a sorted interval map data structure for small keys and values with
automatic coalescing and bidirectional iteration over coalesced intervals.

Except for coalescing int

Add ADT/IntervalMap.

This is a sorted interval map data structure for small keys and values with
automatic coalescing and bidirectional iteration over coalesced intervals.

Except for coalescing intervals, it provides similar functionality to std::map.
It is however much more compact for small keys and values, and hopefully faster
too.

The container object itself can hold the first few intervals without any
allocations, then it switches to a cache conscious B+-tree representation. A
recycling allocator can be shared between many containers, even between
containers holding different types.

The IntervalMap is initially intended to be used with SlotIndex intervals for:

- Backing store for LiveIntervalUnion that is smaller and faster than std::set.

- Backing store for LiveInterval with less overhead than std::vector for typical
intervals and O(N log N) merging of large intervals. 99% of virtual registers
need 4 entries or less and would benefit from the small object optimization.

- Backing store for LiveDebugVariable which doesn't exist yet, but will track
debug variables during register allocation.

This is a work in progress. Missing items are:

- Performance metrics.
- erase().
- insert() shrinkage.
- clear().
- More performance metrics.
- Simplification and detemplatization.

llvm-svn: 119772

show more ...