| Commit message (Collapse) | Author | Age |
|---|
| |
|
|
|
|
| |
monotonic keys.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122093 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
|
|
| |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122092 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
| |
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122081 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
| |
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122019 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
| |
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121995 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
|
|
|
|
|
| |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120829 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
|
|
|
|
|
| |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120264 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
|
| |
These iterators don't point anywhere, and they can't be compared to anything.
They are only good for assigning to.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120239 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
|
| |
This is a version of find() that always searches forwards and is faster for
local searches.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120237 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
| |
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
|
|
|
|
| |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120226 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
| |
Change temporary debugging code to write a dot file directly.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120171 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
| |
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
| |
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119787 91177308-0d34-0410-b5e6-96231b3b80d8
|
| |
|
|
|
|
| |
This reverts r119772.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
|
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119772 91177308-0d34-0410-b5e6-96231b3b80d8
|
