| d715e07efe29451afe2849abd4bd362d0f75a004 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add more checks to IntervalMapOverlaps::advance() to ensure that advanceTo sees
monotonic keys.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122093 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 5049ee5b11fe55e5a553b5388406aab874717672 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122092 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 4aec85ae01188f87e45e5e91baab4f303cbcd336 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Fix crash when IntervalMapOverlaps::advanceTo moves past the last overlap.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122081 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 90675c882d50e420153039c0c013c4ec0f78dc67 |
|
17-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Complete tests for IntervalMapOverlaps.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122019 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 460ee0fd19b13ba4c1410e43d8d253bf34673817 |
|
16-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add basic test exposing many bugs.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121995 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 7a26aca73ff2c8c4cb3205a776cc6743949b1fb7 |
|
03-Dec-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120829 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 5f456cda98c57b6dea8bc716978b69776d0d0e8f |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120264 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 9a08ca318e63912e4c19977abc1173f30866b704 |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120239 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 180e1247ca330b047eabafbc72926ce9bfd8bf8e |
|
28-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Implement const_iterator::advanceTo().
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
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 055942529bbc8487f86b47940dbd6a790516573e |
|
27-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Add more tests for erase(). Fix a few exposed bugs.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120227 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| b0b7214fc90febbbe71e1e989130194ce2b70a36 |
|
27-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120226 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 53bb5c009b04f4a5dd2388b25efe88b5579b282c |
|
26-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120171 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 655fbb4f9b46ea93eddf0815eaed0020e9347416 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Implement IntervalMap::clear().
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119872 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| db52566d684a36cf1f320f91ca5c15d5cd075b95 |
|
20-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Support backwards iteration starting from end().
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119871 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 8dc926755f287e33765a8da0c4b3922a289a9d2d |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119787 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 737d2816c42c1f9a63524e39ccfa7560777b6b42 |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
Revert "Add ADT/IntervalMap.", GCC doesn't like it.
This reverts r119772.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119773 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|
| 8408edffcbd7f436c05018fafbfb9911146b208a |
|
19-Nov-2010 |
Jakob Stoklund Olesen <stoklund@2pi.dk> |
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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@119772 91177308-0d34-0410-b5e6-96231b3b80d8
/external/llvm/unittests/ADT/IntervalMapTest.cpp
|